Branch-and-Price-and-Cut for the Active-Passive Vehicle-Routing Problem
Branch-and-Price-and-Cut for the Active-Passive Vehicle-Routing Problem
复制标题
DOI：
10.1287/trsc.2016.0730
复制
发表时间：
2017-06
期刊：
影响因子：
--
通讯作者：
Christian Tilk;Nicola Bianchessi;Michael Drexl;Stefan Irnich;F. Meisel
中科院分区：
文献类型：
--
作者：
Christian Tilk;Nicola Bianchessi;Michael Drexl;Stefan Irnich;F. Meisel
提出了一种求解主被动车辆路径问题（APVRP）精确解的分支-价格-切割算法。APVRP涵盖了一系列物流应用，其中拾取和交付请求需要主动车辆的联合操作（例如，卡车）和被动车辆（例如，装载装置，例如容器或交换体）。目标是最小化总行驶距离、路线的总完成时间和未处理请求的数量的加权和。为此，该问题支持在客户位置处的主动车辆和被动车辆的灵活耦合和解耦。因此，在规划中必须仔细同步车辆的操作。本文的贡献是双重的：首先，我们提出了一个精确的分支和价格和切割算法这类同步约束的路由问题。据我们所知，该算法是第一个这样的方法，认为明确的时间相互依赖…
This paper presents a branch-and-price-and-cut algorithm for the exact solution of the active-passive vehicle-routing problem (APVRP). The APVRP covers a range of logistics applications where pickup-and-delivery requests necessitate a joint operation of active vehicles (e.g., trucks) and passive vehicles (e.g., loading devices such as containers or swap bodies). The objective is to minimize a weighted sum of the total distance traveled, the total completion time of the routes, and the number of unserved requests. To this end, the problem supports a flexible coupling and decoupling of active and passive vehicles at customer locations. Accordingly, the operations of the vehicles have to be synchronized carefully in the planning. The contribution of the paper is twofold: First, we present an exact branch-and-price-and-cut algorithm for this class of routing problems with synchronization constraints. To our knowledge, this algorithm is the first such approach that considers explicitly the temporal interdepend...