School of Traffic and Transportation Engineering, Central South University, Changsha, Hunan, China.
School of Transportation and Logistics, East China Jiao Tong University, Nanchang, Jiangxi, China.
PLoS One. 2020 Feb 6;15(2):e0227702. doi: 10.1371/journal.pone.0227702. eCollection 2020.
The One-to-one Pickup and Delivery Problem with Shortest-path Transport along Real-life Paths (OPDPSTRP) is presented in this paper. It is a variation of the One-to-one Pickup and Delivery Problem (OPDP), which is common in daily life, such as the Passenger Train Operation Plans (PTOP) and partial Taxi-sharing Problem. Unlike the classical OPDP, in the OPDPSTRP, (1) each demand must be transported along the shortest path according to passengers/shippers requirements, and (2) each vehicle should travel along a real-life path. First, six route structure rules are proposed for the OPDPSTRP, and a kind of Mixed-Integer Programming (MIP) models is formulated for it. Second, A Variable Neighborhood Descent (VND), a Variable Neighborhood Research (VNS), a Multi-Start VND (MS_VND) and a Multi-Start VNS (MS_VNS) with five neighborhood operators has been developed to solve the problem. Finally, The Gurobi solver, the VND, the VNS, the MS_VND and the MS_VNS have been compared with each other by 84 random instances partitioned in small size connected graphs, medium size connected graphs and large size connected graphs. From the test results we found that solutions generated by these approaches are often comparable with those found by the Gurobi solver, and the solutions found by these approaches are better than the solutions found by the Gurobi solver when solving instances with larger numbers of demands. In almost all instances, the MS_VND significantly outperforms the VND and the VNS in terms of solution quality, and outperforms the MS_VNS both in terms of solution quality and CPU time. In the instances with large numbers of demands, the MS_VND is still able to generate good feasible solutions in a reasonable CPU time, which is of vital practical significance for real-life instances.
本文提出了一种带有实际路径最短路径运输的一对一接送和交付问题（OPDPSTRP）。它是一对一接送和交付问题（OPDP）的变体，在日常生活中很常见，例如旅客列车运营计划（PTOP）和部分出租车共享问题。与经典的 OPDP 不同，在 OPDPSTRP 中，（1）根据乘客/托运人的要求，每个需求都必须沿着最短路径运输，（2）每辆车都应该沿着实际路径行驶。首先，针对 OPDPSTRP 提出了六种路线结构规则，并为其制定了一种混合整数规划（MIP）模型。其次，开发了一种变邻域下降（VND）、变邻域搜索（VNS）、多起点 VND（MS_VND）和带有五个邻域操作器的多起点 VNS（MS_VNS）来解决该问题。最后，通过将 84 个随机实例划分为小尺寸连通图、中尺寸连通图和大尺寸连通图，比较了 Gurobi 求解器、VND、VNS、MS_VND 和 MS_VNS 之间的性能。从测试结果中我们发现，这些方法生成的解通常与 Gurobi 求解器生成的解相当，并且在解决需求数量较大的实例时，这些方法生成的解优于 Gurobi 求解器生成的解。在几乎所有实例中，MS_VND 在解的质量方面明显优于 VND 和 VNS，在解的质量和 CPU 时间方面均优于 MS_VNS。在需求数量较大的实例中，MS_VND 仍能够在合理的 CPU 时间内生成良好的可行解，这对实际实例具有重要的实际意义。
