IDEAS home Printed from https://ideas.repec.org/a/inm/orijoc/v34y2022i2p1086-1114.html
   My bibliography  Save this article

Dynamic Discretization Discovery Algorithms for Time-Dependent Shortest Path Problems

Author

Listed:
  • Edward Yuhang He

    (H. Milton Stewart School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, Georgia 30332)

  • Natashia Boland

    (H. Milton Stewart School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, Georgia 30332)

  • George Nemhauser

    (H. Milton Stewart School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, Georgia 30332)

  • Martin Savelsbergh

    (H. Milton Stewart School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, Georgia 30332)

Abstract

Finding a shortest path in a network is a fundamental optimization problem. We focus on settings in which the travel time on an arc in the network depends on the time at which traversal of the arc begins. In such settings, reaching the destination as early as possible is not the only objective of interest. Minimizing the duration of the path, that is, the difference between the arrival time at the destination and the departure from the origin, and minimizing the travel time along the path from origin to destination, are also of interest. We introduce dynamic discretization discovery algorithms to efficiently solve such time-dependent shortest path problems with piecewise linear arc travel time functions. The algorithms operate on partially time-expanded networks in which arc costs represent lower bounds on the arc travel time over the subsequent time interval. A shortest path in this partially time-expanded network yields a lower bound on the value of an optimal path. Upper bounds are easily obtained as by-products of the lower bound calculations. The algorithms iteratively refine the discretization by exploiting breakpoints of the arc travel time functions. In addition to time discretization refinement, the algorithms permit time intervals to be eliminated, improving lower and upper bounds, until, in a finite number of iterations, optimality is proved. Computational experiments show that only a small fraction of breakpoints must be explored and that the fraction decreases as the length of the time horizon and the size of the network increases, making the algorithms highly efficient and scalable. Summary of Contribution: New data collection techniques have increased the availability and fidelity of time-dependent travel time information, making the time-dependent variant of the classic shortest path problem an extremely relevant problem in the field of operations research. This paper provides novel algorithms for the time-dependent shortest path problem with both the minimum duration and minimum travel time objectives, which aims to address the computational challenges faced by existing algorithms. A computational study shows that our new algorithm is indeed significantly more efficient than existing approaches.

Suggested Citation

  • Edward Yuhang He & Natashia Boland & George Nemhauser & Martin Savelsbergh, 2022. "Dynamic Discretization Discovery Algorithms for Time-Dependent Shortest Path Problems," INFORMS Journal on Computing, INFORMS, vol. 34(2), pages 1086-1114, March.
  • Handle: RePEc:inm:orijoc:v:34:y:2022:i:2:p:1086-1114
    DOI: 10.1287/ijoc.2021.1084
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/ijoc.2021.1084
    Download Restriction: no

    File URL: https://libkey.io/10.1287/ijoc.2021.1084?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. Wang, Xiubin & Regan, Amelia C., 2002. "Local truckload pickup and delivery with hard time window constraints," Transportation Research Part B: Methodological, Elsevier, vol. 36(2), pages 97-112, February.
    2. Nachtigall, K., 1995. "Time depending shortest-path problems with applications to railway networks," European Journal of Operational Research, Elsevier, vol. 83(1), pages 154-166, May.
    3. Natashia Boland & Mike Hewitt & Luke Marshall & Martin Savelsbergh, 2017. "The Continuous-Time Service Network Design Problem," Operations Research, INFORMS, vol. 65(5), pages 1303-1321, October.
    Full references (including those not matched with items on IDEAS)

    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. Jinming Liu & Guoting Zhang & Lining Xing & Weihua Qi & Yingwu Chen, 2022. "An Exact Algorithm for Multi-Task Large-Scale Inter-Satellite Routing Problem with Time Windows and Capacity Constraints," Mathematics, MDPI, vol. 10(21), pages 1-24, October.
    2. Natashia L. Boland & Martin W. P. Savelsbergh, 2019. "Perspectives on integer programming for time-dependent models," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 27(2), pages 147-173, July.
    3. Lara, Cristiana L. & Koenemann, Jochen & Nie, Yisu & de Souza, Cid C., 2023. "Scalable timing-aware network design via lagrangian decomposition," European Journal of Operational Research, Elsevier, vol. 309(1), pages 152-169.
    4. Scherr, Yannick Oskar & Hewitt, Mike & Neumann Saavedra, Bruno Albert & Mattfeld, Dirk Christian, 2020. "Dynamic discretization discovery for the service network design problem with mixed autonomous fleets," Transportation Research Part B: Methodological, Elsevier, vol. 141(C), pages 164-195.
    5. Luke Marshall & Natashia Boland & Martin Savelsbergh & Mike Hewitt, 2021. "Interval-Based Dynamic Discretization Discovery for Solving the Continuous-Time Service Network Design Problem," Transportation Science, INFORMS, vol. 55(1), pages 29-51, 1-2.
    6. Natashia Boland & Mike Hewitt & Luke Marshall & Martin Savelsbergh, 2019. "The price of discretizing time: a study in service network design," EURO Journal on Transportation and Logistics, Springer;EURO - The Association of European Operational Research Societies, vol. 8(2), pages 195-216, June.
    7. de Lima, Vinícius L. & Alves, Cláudio & Clautiaux, François & Iori, Manuel & Valério de Carvalho, José M., 2022. "Arc flow formulations based on dynamic programming: Theoretical foundations and applications," European Journal of Operational Research, Elsevier, vol. 296(1), pages 3-21.
    8. Arturo E. Pérez Rivera & Martijn R. K. Mes, 2019. "Integrated scheduling of drayage and long-haul operations in synchromodal transport," Flexible Services and Manufacturing Journal, Springer, vol. 31(3), pages 763-806, September.
    9. Naoto Katayama, 2020. "MIP neighborhood search heuristics for a service network design problem with design-balanced requirements," Journal of Heuristics, Springer, vol. 26(4), pages 475-502, August.
    10. Kenneth Stoop & Mario Pickavet & Didier Colle & Pieter Audenaert, 2024. "The dynamic stochastic container drayage problem with truck appointment scheduling," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 46(3), pages 953-985, September.
    11. Liu, Chuanju & Lin, Shaochong & Shen, Zuo-Jun Max & Zhang, Junlong, 2023. "Stochastic service network design: The value of fixed routes," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 174(C).
    12. Gupta, Gautam & Goodchild, Anne & Hansen, Mark, 2011. "A competitive, charter air-service planning model for student athlete travel," Transportation Research Part B: Methodological, Elsevier, vol. 45(1), pages 128-149, January.
    13. Escobar-Vargas, David & Crainic, Teodor Gabriel, 2024. "Multi-attribute two-echelon location routing: Formulation and dynamic discretization discovery approach," European Journal of Operational Research, Elsevier, vol. 314(1), pages 66-78.
    14. Lu, Jiawei & Nie, Qinghui & Mahmoudi, Monirehalsadat & Ou, Jishun & Li, Chongnan & Zhou, Xuesong Simon, 2022. "Rich arc routing problem in city logistics: Models and solution algorithms using a fluid queue-based time-dependent travel time representation," Transportation Research Part B: Methodological, Elsevier, vol. 166(C), pages 143-182.
    15. Nourinejad, Mehdi & Zhu, Sirui & Bahrami, Sina & Roorda, Matthew J., 2015. "Vehicle relocation and staff rebalancing in one-way carsharing systems," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 81(C), pages 98-113.
    16. Xue, Zhaojie & Zhang, Canrong & Lin, Wei-Hua & Miao, Lixin & Yang, Peng, 2014. "A tabu search heuristic for the local container drayage problem under a new operation mode," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 62(C), pages 136-150.
    17. Zhang, Ruiyou & Lu, Jye-Chyi & Wang, Dingwei, 2014. "Container drayage problem with flexible orders and its near real-time solution strategies," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 61(C), pages 235-251.
    18. Christine Tawfik & Sabine Limbourg, 2019. "A Bilevel Model for Network Design and Pricing Based on a Level-of-Service Assessment," Transportation Science, INFORMS, vol. 53(6), pages 1609-1626, November.
    19. 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.
    20. Ichoua, Soumia & Gendreau, Michel & Potvin, Jean-Yves, 2003. "Vehicle dispatching with time-dependent travel times," European Journal of Operational Research, Elsevier, vol. 144(2), pages 379-396, January.

    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:orijoc:v:34:y:2022:i:2:p:1086-1114. 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.