IDEAS home Printed from https://ideas.repec.org/a/inm/oropre/v67y2019i1p143-162.html
   My bibliography  Save this article

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

Author

Listed:
  • 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)

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.

Suggested Citation

  • Dimitris Bertsimas & Patrick Jaillet, & Sébastien Martin, 2019. "Online Vehicle Routing: The Edge of Optimization in Large-Scale Applications," Operations Research, INFORMS, vol. 67(1), pages 143-162, January.
    • Handle: RePEc:inm:oropre:v:67:y:2019:i:1:p:143-162
    DOI: 10.1287/opre.2018.1763
    as

    Download full text from publisher

    File URL: https://doi.org/10.1287/opre.2018.1763
    Download Restriction: no
    File URL: https://libkey.io/10.1287/opre.2018.1763?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    References listed on IDEAS

    as
    1. Pillac, Victor & Gendreau, Michel & Guéret, Christelle & Medaglia, Andrés L., 2013. "A review of dynamic vehicle routing problems," European Journal of Operational Research, Elsevier, vol. 225(1), pages 1-11.
    2. Michel Gendreau & Alain Hertz & Gilbert Laporte, 1994. "A Tabu Search Heuristic for the Vehicle Routing Problem," Management Science, INFORMS, vol. 40(10), pages 1276-1290, October.
    3. Gerardo Berbeglia & Jean-François Cordeau & Gilbert Laporte, 2012. "A Hybrid Tabu Search and Constraint Programming Algorithm for the Dynamic Dial-a-Ride Problem," INFORMS Journal on Computing, INFORMS, vol. 24(3), pages 343-355, August.
    4. Gutiérrez-Jarpa, Gabriel & Desaulniers, Guy & Laporte, Gilbert & Marianov, Vladimir, 2010. "A branch-and-price algorithm for the Vehicle Routing Problem with Deliveries, Selective Pickups and Time Windows," European Journal of Operational Research, Elsevier, vol. 206(2), pages 341-349, October.
    5. Berbeglia, Gerardo & Cordeau, Jean-François & Laporte, Gilbert, 2010. "Dynamic pickup and delivery problems," European Journal of Operational Research, Elsevier, vol. 202(1), pages 8-15, April.
    6. Zhi-Long Chen & Hang Xu, 2006. "Dynamic Column Generation for Dynamic Vehicle Routing with Time Windows," Transportation Science, INFORMS, vol. 40(1), pages 74-88, February.
    7. Xiang, Zhihai & Chu, Chengbin & Chen, Haoxun, 2006. "A fast heuristic for solving a large-scale static dial-a-ride problem under complex constraints," European Journal of Operational Research, Elsevier, vol. 174(2), pages 1117-1139, October.
    8. Olli Bräysy & Michel Gendreau, 2005. "Vehicle Routing Problem with Time Windows, Part I: Route Construction and Local Search Algorithms," Transportation Science, INFORMS, vol. 39(1), pages 104-118, February.
    9. Miles Lubin & Iain Dunning, 2015. "Computing in Operations Research Using Julia," INFORMS Journal on Computing, INFORMS, vol. 27(2), pages 238-248, May.
    10. Mitrovic-Minic, Snezana & Krishnamurti, Ramesh & Laporte, Gilbert, 2004. "Double-horizon based heuristics for the dynamic pickup and delivery problem with time windows," Transportation Research Part B: Methodological, Elsevier, vol. 38(8), pages 669-685, September.
    11. Russell W. Bent & Pascal Van Hentenryck, 2004. "Scenario-Based Planning for Partially Dynamic Vehicle Routing with Stochastic Customers," Operations Research, INFORMS, vol. 52(6), pages 977-987, December.
    12. Patrick Jaillet & Michael R. Wagner, 2008. "Generalized Online Routing: New Competitive Ratios, Resource Augmentation, and Asymptotic Analyses," Operations Research, INFORMS, vol. 56(3), pages 745-757, June.
    13. G. A. Croes, 1958. "A Method for Solving Traveling-Salesman Problems," Operations Research, INFORMS, vol. 6(6), pages 791-812, December.
    14. Guy Desaulniers & Fausto Errico & Stefan Irnich & Michael Schneider, 2016. "Exact Algorithms for Electric Vehicle-Routing Problems with Time Windows," Operations Research, INFORMS, vol. 64(6), pages 1388-1405, December.
    15. Olli Bräysy & Michel Gendreau, 2005. "Vehicle Routing Problem with Time Windows, Part II: Metaheuristics," Transportation Science, INFORMS, vol. 39(1), pages 119-139, February.
    16. Baldacci, Roberto & Mingozzi, Aristide & Roberti, Roberto, 2012. "Recent exact algorithms for solving the vehicle routing problem under capacity and time window constraints," European Journal of Operational Research, Elsevier, vol. 218(1), pages 1-6.
    17. Jian Yang & Patrick Jaillet & Hani Mahmassani, 2004. "Real-Time Multivehicle Truckload Pickup and Delivery Problems," Transportation Science, INFORMS, vol. 38(2), pages 135-148, May.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Tubagus Robbi Megantara & Sudradjat Supian & Diah Chaerani, 2022. "Strategies to Reduce Ride-Hailing Fuel Consumption Caused by Pick-Up Trips: A Mathematical Model under Uncertainty," Sustainability, MDPI, vol. 14(17), pages 1-18, August.
    2. Ge, Qian & Han, Ke & Liu, Xiaobo, 2021. "Matching and routing for shared autonomous vehicles in congestible network," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 156(C).
    3. Bongiovanni, Claudia & Kaspi, Mor & Cordeau, Jean-François & Geroliminis, Nikolas, 2022. "A machine learning-driven two-phase metaheuristic for autonomous ridesharing operations," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 165(C).
    4. Husemann, Michael & Lahrs, Lennart & Stumpf, Eike, 2023. "The impact of dispatching logic on the efficiency of Urban Air Mobility operations," Journal of Air Transport Management, Elsevier, vol. 108(C).
    5. Long He & Sheng Liu & Zuo‐Jun Max Shen, 2022. "Smart urban transport and logistics: A business analytics perspective," Production and Operations Management, Production and Operations Management Society, vol. 31(10), pages 3771-3787, October.
    6. You, Jintao & Wang, Yuan & Xue, Zhaojie, 2023. "An exact algorithm for the multi-trip container drayage problem with truck platooning," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 175(C).
    7. Haoyuan Hu & Ying Zhang & Jiangwen Wei & Yang Zhan & Xinhui Zhang & Shaojian Huang & Guangrui Ma & Yuming Deng & Siwei Jiang, 2022. "Alibaba Vehicle Routing Algorithms Enable Rapid Pick and Delivery," Interfaces, INFORMS, vol. 52(1), pages 27-41, January.
    8. Alfandari, Laurent & Ljubić, Ivana & De Melo da Silva, Marcos, 2022. "A tailored Benders decomposition approach for last-mile delivery with autonomous robots," European Journal of Operational Research, Elsevier, vol. 299(2), pages 510-525.
    9. Zhang, Jian & Woensel, Tom Van, 2023. "Dynamic vehicle routing with random requests: A literature review," International Journal of Production Economics, Elsevier, vol. 256(C).
    10. Rajendran, Suchithra & Srinivas, Sharan & Grimshaw, Trenton, 2021. "Predicting demand for air taxi urban aviation services using machine learning algorithms," Journal of Air Transport Management, Elsevier, vol. 92(C).
    11. Li, Jianbin & Zheng, Yuting & Dai, Bin & Yu, Jiang, 2020. "Implications of matching and pricing strategies for multiple-delivery-points service in a freight O2O platform," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 136(C).
    12. Gaul, Daniela & Klamroth, Kathrin & Stiglmayr, Michael, 2022. "Event-based MILP models for ridepooling applications," European Journal of Operational Research, Elsevier, vol. 301(3), pages 1048-1063.
    13. Peng, Zixuan & Shan, Wenxuan & Zhu, Xiaoning & Yu, Bin, 2022. "Many-to-one stable matching for taxi-sharing service with selfish players," Transportation Research Part A: Policy and Practice, Elsevier, vol. 160(C), pages 255-279.
    14. Xue Han & Peixin Zhao & Qingchun Meng & Shengnan Yin & Di Wan, 2020. "Optimal scheduling of airport ferry vehicles based on capacity network," Annals of Operations Research, Springer, vol. 295(1), pages 163-182, December.
    15. Wang, Dujuan & Wang, Qi & Yin, Yunqiang & Cheng, T.C.E., 2023. "Optimization of ride-sharing with passenger transfer via deep reinforcement learning," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 172(C).
    16. Schiffer, Maximilian & Hiermann, Gerhard & Rüdel, Fabian & Walther, Grit, 2021. "A polynomial-time algorithm for user-based relocation in free-floating car sharing systems," Transportation Research Part B: Methodological, Elsevier, vol. 143(C), pages 65-85.
    17. Dimitris Bertsimas & Bartolomeo Stellato, 2022. "Online Mixed-Integer Optimization in Milliseconds," INFORMS Journal on Computing, INFORMS, vol. 34(4), pages 2229-2248, July.
    18. Yunke Mai & Bin Hu & Saša Pekeč, 2023. "Courteous or Crude? Managing User Conduct to Improve On-Demand Service Platform Performance," Management Science, INFORMS, vol. 69(2), pages 996-1016, February.
    19. Al-Kanj, Lina & Nascimento, Juliana & Powell, Warren B., 2020. "Approximate dynamic programming for planning a ride-hailing system using autonomous fleets of electric vehicles," European Journal of Operational Research, Elsevier, vol. 284(3), pages 1088-1106.
    20. Fleckenstein, David & Klein, Robert & Steinhardt, Claudius, 2023. "Recent advances in integrating demand management and vehicle routing: A methodological review," European Journal of Operational Research, Elsevier, vol. 306(2), pages 499-518.
    21. Zhen, Lu & Baldacci, Roberto & Tan, Zheyi & Wang, Shuaian & Lyu, Junyan, 2022. "Scheduling heterogeneous delivery tasks on a mixed logistics platform," European Journal of Operational Research, Elsevier, vol. 298(2), pages 680-698.
    22. Wang, Hai & Yang, Hai, 2019. "Ridesourcing systems: A framework and review," Transportation Research Part B: Methodological, Elsevier, vol. 129(C), pages 122-155.
    23. Lee, Enoch & Cen, Xuekai & Lo, Hong K., 2022. "Scheduling zonal-based flexible bus service under dynamic stochastic demand and Time-dependent travel time," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 168(C).
    24. Homsi, Gabriel & Martinelli, Rafael & Vidal, Thibaut & Fagerholt, Kjetil, 2020. "Industrial and tramp ship routing problems: Closing the gap for real-scale instances," European Journal of Operational Research, Elsevier, vol. 283(3), pages 972-990.
    25. Sharif Azadeh, Sh. & Atasoy, Bilge & Ben-Akiva, Moshe E. & Bierlaire, M. & Maknoon, M.Y., 2022. "Choice-driven dial-a-ride problem for demand responsive mobility service," Transportation Research Part B: Methodological, Elsevier, vol. 161(C), pages 128-149.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Zhang, Jian & Woensel, Tom Van, 2023. "Dynamic vehicle routing with random requests: A literature review," International Journal of Production Economics, Elsevier, vol. 256(C).
    2. Pillac, Victor & Gendreau, Michel & Guéret, Christelle & Medaglia, Andrés L., 2013. "A review of dynamic vehicle routing problems," European Journal of Operational Research, Elsevier, vol. 225(1), pages 1-11.
    3. Bhoopalam, Anirudh Kishore & Agatz, Niels & Zuidwijk, Rob, 2018. "Planning of truck platoons: A literature review and directions for future research," Transportation Research Part B: Methodological, Elsevier, vol. 107(C), pages 212-228.
    4. Schyns, M., 2015. "An ant colony system for responsive dynamic vehicle routing," European Journal of Operational Research, Elsevier, vol. 245(3), pages 704-718.
    5. Schneider, Michael & Schwahn, Fabian & Vigo, Daniele, 2017. "Designing granular solution methods for routing problems with time windows," European Journal of Operational Research, Elsevier, vol. 263(2), pages 493-509.
    6. Baris Yildiz & Martin Savelsbergh, 2019. "Provably High-Quality Solutions for the Meal Delivery Routing Problem," Transportation Science, INFORMS, vol. 53(5), pages 1372-1388, September.
    7. Nikola Mardešić & Tomislav Erdelić & Tonči Carić & Marko Đurasević, 2023. "Review of Stochastic Dynamic Vehicle Routing in the Evolving Urban Logistics Environment," Mathematics, MDPI, vol. 12(1), pages 1-44, December.
    8. Nicolas Rincon-Garcia & Ben J. Waterson & Tom J. Cherrett, 2018. "Requirements from vehicle routing software: perspectives from literature, developers and the freight industry," Transport Reviews, Taylor & Francis Journals, vol. 38(1), pages 117-138, January.
    9. Zolfagharinia, Hossein & Haughton, Michael, 2018. "The importance of considering non-linear layover and delay costs for local truckers," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 109(C), pages 331-355.
    10. Ehmke, Jan Fabian & Campbell, Ann Melissa, 2014. "Customer acceptance mechanisms for home deliveries in metropolitan areas," European Journal of Operational Research, Elsevier, vol. 233(1), pages 193-207.
    11. Regnier-Coudert, Olivier & McCall, John & Ayodele, Mayowa & Anderson, Steven, 2016. "Truck and trailer scheduling in a real world, dynamic and heterogeneous context," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 93(C), pages 389-408.
    12. Srour, F.J. & Agatz, N.A.H. & Oppen, J., 2014. "Strategies for Handling Temporal Uncertainty in Pickup and Delivery Problems with Time Windows," ERIM Report Series Research in Management ERS-2014-015-LIS, Erasmus Research Institute of Management (ERIM), ERIM is the joint research institute of the Rotterdam School of Management, Erasmus University and the Erasmus School of Economics (ESE) at Erasmus University Rotterdam.
    13. Bhusiri, Narath & Qureshi, Ali Gul & Taniguchi, Eiichi, 2014. "The trade-off between fixed vehicle costs and time-dependent arrival penalties in a routing problem," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 62(C), pages 1-22.
    14. Srour, F.J. & Agatz, N.A.H. & Oppen, J., 2014. "The Value of Inaccurate Advance Time Window Information in a Pick-up and Delivery Problem," ERIM Report Series Research in Management ERS-2014-002-LIS, Erasmus Research Institute of Management (ERIM), ERIM is the joint research institute of the Rotterdam School of Management, Erasmus University and the Erasmus School of Economics (ESE) at Erasmus University Rotterdam.
    15. Quirion-Blais, Olivier & Chen, Lu, 2021. "A case-based reasoning approach to solve the vehicle routing problem with time windows and drivers’ experience," Omega, Elsevier, vol. 102(C).
    16. Yan Cheng Hsu & Jose L. Walteros & Rajan Batta, 2020. "Solving the petroleum replenishment and routing problem with variable demands and time windows," Annals of Operations Research, Springer, vol. 294(1), pages 9-46, November.
    17. Cheung, Bernard K.-S. & Choy, K.L. & Li, Chung-Lun & Shi, Wenzhong & Tang, Jian, 2008. "Dynamic routing model and solution methods for fleet management with mobile technologies," International Journal of Production Economics, Elsevier, vol. 113(2), pages 694-705, June.
    18. Vidal, Thibaut & Crainic, Teodor Gabriel & Gendreau, Michel & Prins, Christian, 2013. "Heuristics for multi-attribute vehicle routing problems: A survey and synthesis," European Journal of Operational Research, Elsevier, vol. 231(1), pages 1-21.
    19. Zolfagharinia, Hossein & Haughton, Michael, 2014. "The benefit of advance load information for truckload carriers," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 70(C), pages 34-54.
    20. van Lon, Rinde R.S. & Ferrante, Eliseo & Turgut, Ali E. & Wenseleers, Tom & Vanden Berghe, Greet & Holvoet, Tom, 2016. "Measures of dynamism and urgency in logistics," European Journal of Operational Research, Elsevier, vol. 253(3), pages 614-624.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:inm:oropre:v:67:y:2019:i:1:p:143-162. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.