Online Vehicle Routing: The Edge of Optimization in Large-Scale Applications

Dimitris Bertsimas (), Patrick Jaillet, () and Sébastien Martin ()
Additional contact information
Dimitris Bertsimas: Operations Research Center, Massachusetts Institute of Technology, Cambridge, Massachusetts 02142
Patrick Jaillet,: Operations Research Center, Massachusetts Institute of Technology, Cambridge, Massachusetts 02142
Sébastien Martin: Operations Research Center, Massachusetts Institute of Technology, Cambridge, Massachusetts 02142

Operations Research, 2019, vol. 67, issue 1, 143-162

Abstract: With the emergence of ride-sharing companies that offer transportation on demand at a large scale and the increasing availability of corresponding demand data sets, new challenges arise to develop routing optimization algorithms that can solve massive problems in real time. In this paper, we develop an optimization framework, coupled with a novel and generalizable backbone algorithm, that allows us to dispatch in real time thousands of taxis serving more than 25,000 customers per hour. We provide evidence from historical simulations using New York City routing network and yellow cab data to show that our algorithms improve upon the performance of existing heuristics in such real-world settings.

Keywords: online vehicle routing; taxis; mixed-integer optimization; simulation; large scale (search for similar items in EconPapers)
Date: 2019
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (32)

Downloads: (external link)
https://doi.org/10.1287/opre.2018.1763 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:67:y:2019:i:1:p:143-162

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().