A comparison of column-generation approaches to the Synchronized Pickup and Delivery Problem
A comparison of column-generation approaches to the Synchronized Pickup and Delivery Problem
复制标题
DOI：
10.1016/j.ejor.2015.06.017
复制
发表时间：
2015-11
期刊：
影响因子：
--
通讯作者：
Timo Gschwind
中科院分区：
文献类型：
--
作者：
Timo Gschwind
在SPDP问题中，用户指定的从起点到目的地的运输请求必须由同质车辆组成的车队来服务。该任务是找到一组最小成本的路线，满足配对和优先级，容量和时间窗口。此外，时间同步约束耦合的服务时间在皮卡和交付位置的客户请求在以下方式：一个请求必须在预先指定的最小和最大的时间滞后（称为乘车时间）后，它已经被拿起。这些行驶时间的限制的存在严重复杂的自然列生成的SPDP制定的子问题，使其不清楚，如果他们的集成到子问题中的整数列生成方法的回报。因此，我们开发了四个分支和切割和价格算法的SPDP列生成配方的基础上，使用不同的子问题。其中有两个子问题是本文首次考虑的，以前没有研究过。我们推导出新的优势规则和标记算法，其有效的解决方案。大量的计算结果表明，无论是集成两种类型的乘车时间的限制，或只有最大乘车时间的限制到子问题的结果在最强的整体方法。
In the Synchronized Pickup and Delivery Problem (SPDP), user-specified transportation requests from origin to destination points have to be serviced by a fleet of homogeneous vehicles. The task is to find a set of minimum-cost routes satisfying pairing and precedence, capacities, and time windows. Additionally, temporal synchronization constraints couple the service times at the pickup and delivery locations of the customer requests in the following way: a request has to be delivered within prespecified minimum and maximum time lags (called ride times) after it has been picked up. The presence of these ride-time constraints severely complicates the subproblem of the natural column-generation formulation of the SPDP so that it is not clear if their integration into the subproblem pays off in an integer column-generation approach. Therefore, we develop four branch-and-cut-and-price algorithms for the SPDP based on column-generation formulations that use different subproblems. Two of these subproblems are considered for the first time in this paper have not been studied before. We derive new dominance rules and labeling algorithms for their effective solution. Extensive computational results indicate that integrating either both types of ride-time constraints or only the maximum ride-time constraints into the subproblem results in the strongest overall approach.