车辆路径问题
计算机科学
水准点(测量)
计算
英里
集合(抽象数据类型)
数学优化
运筹学
布线(电子设计自动化)
算法
数学
计算机网络
物理
大地测量学
天文
程序设计语言
地理
作者
Sihan Wang,Roberto Baldacci,Yang Yu,Yu Zhang,Jiafu Tang,Xinggang Luo,Wei Sun
标识
DOI:10.1287/trsc.2022.0139
摘要
Motivated by the worldwide development of shared mobility, we investigate a vehicle routing problem with time windows and deadlines called the first-mile ridesharing problem (FMRSP). The FMRSP involves routing a fleet of vehicles, each servicing customers within specific time windows. The FMRSP generalizes the well-known vehicle routing problem with time windows (VRPTW), additionally imposing that each vehicle route arrives at the destination before the earliest deadline associated with the set of customers served by the route. The FMRSP is also related to the VRPTW and release dates, where in addition to time window constraints, a release date is associated with each customer defining the earliest time that the order is available to leave the depot for delivery. For the FMRSP, we present an exact method based on a branch-price-and-cut (BPC) algorithm combining state-of-the-art techniques and an innovative pricing algorithm. The pricing algorithm is based on a bidirectional bucket graph-based labeling algorithm, in which the backward extension of a label is computed in a constant time. Effective dominance rules used to speed up the computation are also described. Extensive computational studies demonstrate that our proposed BPC algorithm can solve optimality-modified Solomon benchmark instances involving up to 100 customers and real-world instances involving up to 290 customers. Funding: This research was supported by the National Natural Science Foundation of China [Grants 71831003, 72171043, 71831006, and 71901180]. Supplemental Material: The online appendix is available at https://doi.org/10.1287/trsc.2022.0139 .
科研通智能强力驱动
Strongly Powered by AbleSci AI