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

• 成果类型: Article
• 署名作者: Bertsimas, Dimitris; Jaillet, Patrick; Martin, Sebastien
• 署名单位: Massachusetts Institute of Technology (MIT)
• 刊物名称: OPERATIONS RESEARCH
• ISSN/ISSBN: 0030-364X
• DOI: 10.1287/opre.2018.1763
• 发表日期: 2019
• 页码: 143-162
• 关键词: time windows; tabu search; algorithm; pickup

摘要

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.