Routing Optimization with Vehicle–Customer Coordination

Wei Zhang, Alexandre Jacquillat, Kai Wang, Shuaian Wang

Research output: Journal article publicationReview articleAcademic researchpeer-review

4 Citations (Scopus)

Abstract

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 sub-problem in the ℓ1 space and the ℓ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 standpoint, 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.

Original languageEnglish
Pages (from-to)6876-6897
Number of pages22
JournalManagement Science
Volume69
Issue number11
DOIs
Publication statusPublished - Nov 2023

Keywords

  • ride-sharing
  • time–space network
  • vehicle routing
  • vehicle–customer coordination

ASJC Scopus subject areas

  • Strategy and Management
  • Management Science and Operations Research

Fingerprint

Dive into the research topics of 'Routing Optimization with Vehicle–Customer Coordination'. Together they form a unique fingerprint.

Cite this