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 language | English |
---|---|
Pages (from-to) | 6876-6897 |
Number of pages | 22 |
Journal | Management Science |
Volume | 69 |
Issue number | 11 |
DOIs | |
Publication status | Published - 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