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

A Shortest-Path Algorithm for the Departure Time and Speed Optimization Problem

Author

Listed:
  • Anna Franceschetti

    (Distribution Management, HEC Montréal, Montréal, Québec H3T 2A7, Canada)

  • Dorothée Honhon

    (Naveen Jindal School of Management, University of Texas at Dallas, Richardson, Texas 75080)

  • Gilbert Laporte

    (Distribution Management, HEC Montréal, Montréal, Québec H3T 2A7, Canada)

  • Tom Van Woensel

    (School of Industrial Engineering, Eindhoven University of Technology, 5600 MB Eindhoven, Netherlands)

Abstract

We present a shortest-path algorithm for the departure time and speed optimization problem under traffic congestion. The objective of the problem is to determine an optimal schedule for a vehicle visiting a fixed sequence of customer locations to minimize a total cost function encompassing emissions cost and labor cost. We account for the presence of traffic congestion, which limits the vehicle speed during peak hours. We show how to cast this problem as a shortest-path problem by exploiting some structural results of the optimal solution. We illustrate the solution method and discuss some properties of the problem.

Suggested Citation

  • Anna Franceschetti & Dorothée Honhon & Gilbert Laporte & Tom Van Woensel, 2018. "A Shortest-Path Algorithm for the Departure Time and Speed Optimization Problem," Transportation Science, INFORMS, vol. 52(4), pages 756-768, August.
    • Handle: RePEc:inm:ortrsc:v:52:y:2018:i:4:p:756-768
    DOI: 10.1287/trsc.2018.0820
    as

    Download full text from publisher

    File URL: https://doi.org/10.1287/trsc.2018.0820
    Download Restriction: no
    File URL: https://libkey.io/10.1287/trsc.2018.0820?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. Lindstad, Haakon & Asbjørnslett, Bjørn E. & Strømman, Anders H., 2011. "Reductions in greenhouse gas emissions and cost by shipping at lower speeds," Energy Policy, Elsevier, vol. 39(6), pages 3456-3464, June.
    2. Franceschetti, Anna & Honhon, Dorothée & Van Woensel, Tom & Bektaş, Tolga & Laporte, Gilbert, 2013. "The time-dependent pollution-routing problem," Transportation Research Part B: Methodological, Elsevier, vol. 56(C), pages 265-293.
    3. repec:cdl:itsrrp:qt67f0v3zf is not listed on IDEAS
    4. Kramer, Raphael & Maculan, Nelson & Subramanian, Anand & Vidal, Thibaut, 2015. "A speed and departure time optimization algorithm for the pollution-routing problem," European Journal of Operational Research, Elsevier, vol. 247(3), pages 782-787.
    5. K Fagerholt & G Laporte & I Norstad, 2010. "Reducing fuel emissions by optimizing speed on shipping routes," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 61(3), pages 523-529, March.
    6. Christos Kontovas & Harilaos N. Psaraftis, 2011. "Reduction of emissions along the maritime intermodal container chain: operational models and policies," Maritime Policy & Management, Taylor & Francis Journals, vol. 38(4), pages 451-469, March.
    7. Demir, Emrah & Bektaş, Tolga & Laporte, Gilbert, 2012. "An adaptive large neighborhood search heuristic for the Pollution-Routing Problem," European Journal of Operational Research, Elsevier, vol. 223(2), pages 346-359.
    8. Harilaos N. Psaraftis & Christos A. Kontovas, 2016. "Green Maritime Transportation: Speed and Route Optimization," International Series in Operations Research & Management Science, in: Harilaos N. Psaraftis (ed.), Green Transportation Logistics, edition 127, chapter 0, pages 299-349, Springer.
    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. Edward He & Natashia Boland & George Nemhauser & Martin Savelsbergh, 2021. "Time-Dependent Shortest Path Problems with Penalties and Limits on Waiting," INFORMS Journal on Computing, INFORMS, vol. 33(3), pages 997-1014, July.
    2. Daiane Maria Genaro Chiroli & Sérgio Fernando Mayerle & João Neiva Figueiredo, 2022. "Using state-space shortest-path heuristics to solve the long-haul point-to-point vehicle routing and driver scheduling problem subject to hours-of-service regulatory constraints," Journal of Heuristics, Springer, vol. 28(1), pages 23-59, February.
    3. Tom Woensel, 2019. "Comments on: 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 180-183, July.
    4. Haodong Feng, 2025. "Study of Impact of Moment Information in Demand Forecasting on Distributionally Robust Fulfillment Rate Improvement Algorithm," Mathematics, MDPI, vol. 13(7), pages 1-35, April.
    5. Xing, Zheng & Liu, Haitao & Wang, Tingsong & Chew, Ek Peng & Lee, Loo Hay & Tan, Kok Choon, 2023. "Integrated automated guided vehicle dispatching and equipment scheduling with speed optimization," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 169(C).

    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. Bektaş, Tolga & Ehmke, Jan Fabian & Psaraftis, Harilaos N. & Puchinger, Jakob, 2019. "The role of operational research in green freight transportation," European Journal of Operational Research, Elsevier, vol. 274(3), pages 807-823.
    2. Fukasawa, Ricardo & He, Qie & Song, Yongjia, 2016. "A disjunctive convex programming approach to the pollution-routing problem," Transportation Research Part B: Methodological, Elsevier, vol. 94(C), pages 61-79.
    3. Mohammad Asghari & Seyed Mohammad Javad Mirzapour Al-E-Hashem, 2021. "Green vehicle routing problem: A state-of-the-art review," Post-Print hal-03182944, HAL.
    4. He, Qie & Zhang, Xiaochen & Nip, Kameng, 2017. "Speed optimization over a path with heterogeneous arc costs," Transportation Research Part B: Methodological, Elsevier, vol. 104(C), pages 198-214.
    5. Asghari, Mohammad & Mirzapour Al-e-hashem, S. Mohammad J., 2021. "Green vehicle routing problem: A state-of-the-art review," International Journal of Production Economics, Elsevier, vol. 231(C).
    6. Franceschetti, Anna & Demir, Emrah & Honhon, Dorothée & Van Woensel, Tom & Laporte, Gilbert & Stobbe, Mark, 2017. "A metaheuristic for the time-dependent pollution-routing problem," European Journal of Operational Research, Elsevier, vol. 259(3), pages 972-991.
    7. Zhang, Shuai & Gajpal, Yuvraj & Appadoo, S.S. & Abdulkader, M.M.S., 2018. "Electric vehicle routing problem with recharging stations for minimizing energy consumption," International Journal of Production Economics, Elsevier, vol. 203(C), pages 404-413.
    8. Qian, Jiani & Eglese, Richard, 2016. "Fuel emissions optimization in vehicle routing problems with time-varying speeds," European Journal of Operational Research, Elsevier, vol. 248(3), pages 840-848.
    9. Laporte, Gilbert, 2024. "Fifty years of operational research: 1972–2022," European Journal of Operational Research, Elsevier, vol. 319(2), pages 347-360.
    10. Mansouri, S. Afshin & Lee, Habin & Aluko, Oluwakayode, 2015. "Multi-objective decision support to enhance environmental sustainability in maritime shipping: A review and future directions," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 78(C), pages 3-18.
    11. Ricardo Fukasawa & Qie He & Fernando Santos & Yongjia Song, 2018. "A Joint Vehicle Routing and Speed Optimization Problem," INFORMS Journal on Computing, INFORMS, vol. 30(4), pages 694-709, November.
    12. Qiu, Rui & Xu, Jiuping & Ke, Ruimin & Zeng, Ziqiang & Wang, Yinhai, 2020. "Carbon pricing initiatives-based bi-level pollution routing problem," European Journal of Operational Research, Elsevier, vol. 286(1), pages 203-217.
    13. Huang, Yixiao & Zhao, Lei & Van Woensel, Tom & Gross, Jean-Philippe, 2017. "Time-dependent vehicle routing problem with path flexibility," Transportation Research Part B: Methodological, Elsevier, vol. 95(C), pages 169-195.
    14. Raeesi, Ramin & Zografos, Konstantinos G., 2019. "The multi-objective Steiner pollution-routing problem on congested urban road networks," Transportation Research Part B: Methodological, Elsevier, vol. 122(C), pages 457-485.
    15. Xiao, Yiyong & Zuo, Xiaorong & Huang, Jiaoying & Konak, Abdullah & Xu, Yuchun, 2020. "The continuous pollution routing problem," Applied Mathematics and Computation, Elsevier, vol. 387(C).
    16. Ehmke, Jan Fabian & Campbell, Ann M. & Thomas, Barrett W., 2018. "Optimizing for total costs in vehicle routing in urban areas," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 116(C), pages 242-265.
    17. Xiangang Lan & Xiaode Zuo & Qin Tao, 2023. "Container Shipping Optimization under Different Carbon Emission Policies: A Case Study," Sustainability, MDPI, vol. 15(10), pages 1-20, May.
    18. Yagcitekin, Bunyamin & Uzunoglu, Mehmet, 2016. "A double-layer smart charging strategy of electric vehicles taking routing and charge scheduling into account," Applied Energy, Elsevier, vol. 167(C), pages 407-419.
    19. Liu, Yiming & Yu, Yang & Baldacci, Roberto & Tang, Jiafu & Sun, Wei, 2025. "Optimizing carbon emissions in green logistics for time-dependent routing," Transportation Research Part B: Methodological, Elsevier, vol. 192(C).
    20. Behnke, Martin & Kirschstein, Thomas, 2017. "The impact of path selection on GHG emissions in city logistics," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 106(C), pages 320-336.

    More about this item

    Keywords

    ;
    ;
    ;

    Statistics

    Access and download statistics

    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:52:y:2018:i:4:p:756-768. 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.