论文标题
通用预算分配问题和运输系统中应用的近似算法
Approximation Algorithm for Generalized Budgeted Assignment Problems and Applications in Transportation Systems
论文作者
论文摘要
在运输系统中的运输线计划问题的激励下，我们在预算限制下调查了以下电容分配问题。我们的型号涉及$ l $ bin和$ p $项目。每个bin $ l $具有利用率$ c_l $和$ n_l $二维容量向量。每个项目$ p $都有$ n_l $ -Dimensional二进制重量vector $ r_ {lp} $，其中$ 1 $ s in $ r_ {lp} $（如果有）在连续职位上出现，其分配给bin $ l $，产生了奖励$ v_ v_ {lp} $。目的是通过满足三个约束的任务来最大化总奖励：（i）分配项目的总权重不违反任何垃圾箱的容量； （ii）每个项目最多分配给一个开放式垃圾箱； （iii）总体利用成本保留在总预算$ b $之内。 我们提出了对于此问题的第一个随机圆形算法，具有恒定的近似值。然后，我们将框架应用于激励的公交线计划问题，提出相应的模型并使用现实世界数据进行数值实验。我们的结果表明，在应对这一关键运输挑战时，对以前的方法有了重大改进。
Motivated by a transit line planning problem in transportation systems, we investigate the following capacitated assignment problem under a budget constraint. Our model involves $L$ bins and $P$ items. Each bin $l$ has a utilization cost $c_l$ and an $n_l$-dimensional capacity vector. Each item $p$ has an $n_l$-dimensional binary weight vector $r_{lp}$, where the $1$s in $r_{lp}$ (if any) appear in consecutive positions, and its assignment to bin $l$ yields a reward $v_{lp}$. The objective is to maximize total rewards through an assignment that satisfies three constraints: (i) the total weights of assigned items do not violate any bin's capacity; (ii) each item is assigned to at most one open bin; and (iii) the overall utilization costs remain within a total budget $B$. We propose the first randomized rounding algorithm with a constant approximation ratio for this problem. We then apply our framework to the motivating transit line planning problem, presenting corresponding models and conducting numerical experiments using real-world data. Our results demonstrate significant improvements over previous approaches in addressing this critical transportation challenge.
