IDEAS home Printed from https://ideas.repec.org/a/inm/ortrsc/v59y2025i1p28-59.html
   My bibliography  Save this article

The Online Shortest Path Problem: Learning Travel Times Using a Multiarmed Bandit Framework

Author

Listed:
  • Tomás Lagos

    (Discipline of Business Analytics, The University of Sydney, Sydney, New South Wales 2000, Australia)

  • Ramón Auad

    (Universidad Católica del Norte, Antofagasta 1240000, Chile)

  • Felipe Lagos

    (Faculty of Engineering and Sciences, Universidad Adolfo Ibáñez, Santiago de Chile 7941169, Chile)

Abstract

In the age of e-commerce, logistics companies often operate within extensive road networks without accurate knowledge of travel times for their specific fleet of vehicles. Moreover, millions of dollars are spent on routing services that fail to accurately capture the unique characteristics of the drivers and vehicles of the companies. In this work, we address the challenge faced by a logistic operator with limited travel time information, aiming to find the optimal expected shortest path between origin-destination pairs. We model this problem as an online shortest path problem, common to many last-mile routing settings; given a graph whose arcs’ travel times are stochastic and follow an unknown distribution, the objective is to find a vehicle route of minimum travel time from an origin to a destination. The planner progressively collects travel condition data as drivers complete their routes. Inspired by the combinatorial multiarmed bandit and kriging literature, we propose three methods with distinct features to effectively learn the optimal shortest path, highlighting the practical advantages of incorporating spatial correlation in the learning process. Our approach balances exploration (improving estimates for unexplored arcs) and exploitation (executing the minimum expected time path) using the Thompson sampling algorithm. In each iteration, our algorithm executes the path that minimizes the expected travel time based on data from a posterior distribution of the speeds of the arcs. We conduct a computational study comprising two settings: a set of four artificial instances and a real-life case study. The case study uses empirical data of taxis in the 17-km-radius area of the center of Beijing, encompassing Beijing’s “5th Ring Road.” In both settings, our algorithms demonstrate efficient and effective balancing of the exploration-exploitation trade-off.

Suggested Citation

  • Tomás Lagos & Ramón Auad & Felipe Lagos, 2025. "The Online Shortest Path Problem: Learning Travel Times Using a Multiarmed Bandit Framework," Transportation Science, INFORMS, vol. 59(1), pages 28-59, January.
  • Handle: RePEc:inm:ortrsc:v:59:y:2025:i:1:p:28-59
    DOI: 10.1287/trsc.2023.0196
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/trsc.2023.0196
    Download Restriction: no

    File URL: https://libkey.io/10.1287/trsc.2023.0196?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
    ---><---

    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:ortrsc:v:59:y:2025:i:1:p:28-59. 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.

    We have no bibliographic references for this item. You can help adding them by using 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.