Routing Optimization with Vehicle-Customer Coordination

• 成果类型: Article
• 署名作者: Zhang, Wei; Jacquillat, Alexandre; Wang, Kai; Wang, Shuaian
• 署名单位: Tsinghua University; Hong Kong Polytechnic University; Massachusetts Institute of Technology (MIT)
• 刊物名称: MANAGEMENT SCIENCE
• ISSN/ISSBN: 0025-1909
• DOI: 10.1287/mnsc.2023.4739
• 发表日期: 2023
• 页码: 6876-6897
• 关键词: vehicle-customer coordination; Vehicle Routing; ride-sharing; time-space network

摘要

In several transportation systems, vehicles can choose where to meet customers rather than stopping in fixed locations. This added flexibility, however, requires coordination between vehicles and customers that adds complexity to routing operations. This paper develops scalable algorithms to optimize these operations. First, we solve the one-stop subproblem in the l(1) space and the l(2) space by leveraging the geometric structure of operations. Second, to solve a multistop problem, we embed the single-stop optimization into a tailored coordinate descent scheme, which we prove converges to a global optimum. Third, we develop a new algorithm for dial-a-ride problems based on a subpath-based time-space network optimization combining set partitioning and time-space principles. Finally, we propose an online routing algorithm to support real-world ride-sharing operations with vehicle-customer coordination. Computational results show that our algorithm outperforms state-of-the-art benchmarks, yielding far superior solutions in shorter computational times and can support real-time operations in very large-scale systems. From a practical stand-point, most of the benefits of vehicle-customer coordination stem from comprehensively reoptimizing upstream operations as opposed to merely adjusting downstream stopping locations. Ultimately, vehicle-customer coordination provides win-win-win outcomes: higher profits, better customer service, and smaller environmental footprint.