论文标题
针对拨号问题和最小疾病传递风险的拨号问题的分支机构和价格算法
A branch-cut-and-price algorithm for a dial-a-ride problem with minimum disease-transmission risk
论文作者
论文摘要
本文调查了拨号载问题（DARP）的变体，即风险意识DARP（RDARP）。我们的RDARP通过（1）最大程度地降低了载载乘客的旅行成本和疾病转移风险的加权总和，以及（2）为每辆车引入最大累积暴露风险限制，以确保较低外部暴露的旅行。这两种扩展都要求以最小化的方式繁殖每个载载乘客的风险曝光，同时满足DARP的其他现有限制。为了充分描述RDARP，我们首先提供了三个基于弧形的配方，并将RDARP重新制定为基于同等的最低最大行程的配方，该配方由精确的分支切割和价格（BCP）算法解决。对于分支树中的每个节点，我们通过将问题分解为主问题和子问题来采用列生成方法。后者采取了基本最短路径问题的形式，并具有资源约束，并最大程度地减少了最大风险（ESPPRCMMR）。为了有效地解决ESPPRCMMR，我们开发了一种新的标签算法，并根据风险相关的资源建立了资源扩展功能的家庭。我们采用现实世界中的paratransit旅行数据集，在早晨和下午的时间内生成17至55名异质乘客的RDARP实例。计算结果表明，我们的BCP算法可以在5分钟内最佳地解决所有中小型实例（32或更少的乘客）。对于大型实例（39至55名乘客），我们的BCP算法可以在一个小时的时间限制内最佳地解决30个实例中的23个实例。
This paper investigates a variant of the dial-a-ride problem (DARP), namely Risk-aware DARP (RDARP). Our RDARP extends the DARP by (1) minimizing a weighted sum of travel cost and disease-transmission risk exposure for onboard passengers and (2) introducing a maximum cumulative exposure risk constraint for each vehicle to ensure a trip with lower external exposure. Both extensions require that the risk exposure of each onboard passenger is propagated in a minimized fashion while satisfying other existing constraints of the DARP. To fully describe the RDARP, we first provide a three-index arc-based formulation and reformulate the RDARP into an equivalent min-max trip-based formulation, which is solved by an exact Branch-Cut-and-Price (BCP) algorithm. For each node in the branching tree, we adopt the column generation method by decomposing the problem into a master problem and a subproblem. The latter takes the form of an elementary shortest path problem with resource constraints and minimized maximum risk (ESPPRCMMR). To solve the ESPPRCMMR efficiently, we develop a new labeling algorithm and establish families of resource extension functions in compliance with the risk-related resources. We adopt a real-world paratransit trip dataset to generate the RDARP instances ranging from 17 to 55 heterogeneous passengers with 3 to 13 vehicles during the morning and afternoon periods. Computational results show that our BCP algorithm can optimally solve all small- and medium-sized instances (32 or fewer passengers) within 5 minutes. For the large instances (39 to 55 passengers), our BCP algorithm can solve 23 of 30 instances optimally within a time limit of one hour.
