IDEAS home Printed from https://ideas.repec.org/a/eee/ejores/v300y2022i3p1005-1016.html
   My bibliography  Save this article

The vehicle routing problem with load-dependent travel times for cargo bicycles

Author

Listed:
  • Fontaine, Pirmin

Abstract

Cities, retailers, and delivery services are trying to find more environmental friendly solutions for last mile delivery. One very promising and partly used option are cargo bicycles. A critical factor of cargo bicycles is their travel speed, which depends on the mass of the load and the gradient of the chosen streets. Therefore, we define load-dependent travel speed and introduce the vehicle routing problem with load-dependent travel times (VRPLTT). We introduce a mixed-integer programming formulation and show the benefits of considering load-dependent travel times in last mile delivery with cargo bicycles. To efficiently solve larger instances, we develop an adaptive large neighborhood search (ALNS). For the numerical study, we introduce a new set of instances and show that the travel time can be reduced by 4.5% on average and up to 22% compared to the vehicle routing problem with time windows. Moreover, ignoring the load-dependent travel times can lead to the underestimation of travel time in such a way that time windows are violated.

Suggested Citation

  • Fontaine, Pirmin, 2022. "The vehicle routing problem with load-dependent travel times for cargo bicycles," European Journal of Operational Research, Elsevier, vol. 300(3), pages 1005-1016.
    • Handle: RePEc:eee:ejores:v:300:y:2022:i:3:p:1005-1016
    DOI: 10.1016/j.ejor.2021.09.009
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377221721007682
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.ejor.2021.09.009?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
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Stefan Ropke & David Pisinger, 2006. "An Adaptive Large Neighborhood Search Heuristic for the Pickup and Delivery Problem with Time Windows," Transportation Science, INFORMS, vol. 40(4), pages 455-472, November.
    2. Tom Assmann & Sebastian Lang & Florian Müller & Michael Schenk, 2020. "Impact Assessment Model for the Implementation of Cargo Bike Transshipment Points in Urban Districts," Sustainability, MDPI, vol. 12(10), pages 1-19, May.
    3. Bektas, Tolga & Laporte, Gilbert, 2011. "The Pollution-Routing Problem," Transportation Research Part B: Methodological, Elsevier, vol. 45(8), pages 1232-1250, September.
    4. Teodor Gabriel Crainic & Nicoletta Ricciardi & Giovanni Storchi, 2009. "Models for Evaluating and Planning City Logistics Systems," Transportation Science, INFORMS, vol. 43(4), pages 432-454, November.
    5. Ba Hung, Nguyen & Jaewon, Sung & Lim, Ocktaeck, 2017. "A study of the effects of input parameters on the dynamics and required power of an electric bicycle," Applied Energy, Elsevier, vol. 204(C), pages 1347-1362.
    6. Potvin, Jean-Yves & Rousseau, Jean-Marc, 1993. "A parallel route building algorithm for the vehicle routing and scheduling problem with time windows," European Journal of Operational Research, Elsevier, vol. 66(3), pages 331-340, May.
    7. Zachariadis, Emmanouil E. & Tarantilis, Christos D. & Kiranoudis, Chris T., 2015. "The load-dependent vehicle routing problem and its pick-up and delivery extension," Transportation Research Part B: Methodological, Elsevier, vol. 71(C), pages 158-181.
    8. Chryssi Malandraki & Mark S. Daskin, 1992. "Time Dependent Vehicle Routing Problems: Formulations, Properties and Heuristic Algorithms," Transportation Science, INFORMS, vol. 26(3), pages 185-200, August.
    9. Gmira, Maha & Gendreau, Michel & Lodi, Andrea & Potvin, Jean-Yves, 2021. "Tabu search for the time-dependent vehicle routing problem with time windows on a road network," European Journal of Operational Research, Elsevier, vol. 288(1), pages 129-140.
    10. Mühlbauer, Ferdinand & Fontaine, Pirmin, 2021. "A parallelised large neighbourhood search heuristic for the asymmetric two-echelon vehicle routing problem with swap containers for cargo-bicycles," European Journal of Operational Research, Elsevier, vol. 289(2), pages 742-757.
    11. Marius M. Solomon, 1987. "Algorithms for the Vehicle Routing and Scheduling Problems with Time Window Constraints," Operations Research, INFORMS, vol. 35(2), pages 254-265, April.
    12. Pan, Binbin & Zhang, Zhenzhen & Lim, Andrew, 2021. "Multi-trip time-dependent vehicle routing problem with time windows," European Journal of Operational Research, Elsevier, vol. 291(1), pages 218-231.
    13. Kuhn, Heinrich & Schubert, Daniel & Holzapfel, Andreas, 2021. "Integrated order batching and vehicle routing operations in grocery retail – A General Adaptive Large Neighborhood Search algorithm," European Journal of Operational Research, Elsevier, vol. 294(3), pages 1003-1021.
    14. P. Matl & R. F. Hartl & T. Vidal, 2018. "Workload Equity in Vehicle Routing Problems: A Survey and Analysis," Transportation Science, INFORMS, vol. 52(2), pages 239-260, March.
    15. Luce Brotcorne & Guido Perboli & Mariangela Rosano & Qu Wei, 2019. "A Managerial Analysis of Urban Parcel Delivery: A Lean Business Approach," Sustainability, MDPI, vol. 11(12), pages 1-23, June.
    16. Gilbert Laporte, 2009. "Fifty Years of Vehicle Routing," Transportation Science, INFORMS, vol. 43(4), pages 408-416, November.
    17. Turkeš, Renata & Sörensen, Kenneth & Hvattum, Lars Magnus, 2021. "Meta-analysis of metaheuristics: Quantifying the effect of adaptiveness in adaptive large neighborhood search," European Journal of Operational Research, Elsevier, vol. 292(2), pages 423-442.
    18. Fontaine, Pirmin & Crainic, Teodor Gabriel & Jabali, Ola & Rei, Walter, 2021. "Scheduled service network design with resource management for two-tier multimodal city logistics," European Journal of Operational Research, Elsevier, vol. 294(2), pages 558-570.
    19. 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.
    20. 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.
    21. Ángel Corberán & Güneş Erdoğan & Gilbert Laporte & Isaac Plana & José M. Sanchis, 2018. "The Chinese Postman Problem with Load-Dependent Costs," Transportation Science, INFORMS, vol. 52(2), pages 370-385, March.
    22. Renaud Masson & Fabien Lehuédé & Olivier Péton, 2013. "An Adaptive Large Neighborhood Search for the Pickup and Delivery Problem with Transfers," Transportation Science, INFORMS, vol. 47(3), pages 344-355, August.
    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. Liu, Yiming & Roberto, Baldacci & Zhou, Jianwen & Yu, Yang & Zhang, Yu & Sun, Wei, 2023. "Efficient feasibility checks and an adaptive large neighborhood search algorithm for the time-dependent green vehicle routing problem with time windows," European Journal of Operational Research, Elsevier, vol. 310(1), pages 133-155.
    2. 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.
    3. Frey, Christian M.M. & Jungwirth, Alexander & Frey, Markus & Kolisch, Rainer, 2023. "The vehicle routing problem with time windows and flexible delivery locations," European Journal of Operational Research, Elsevier, vol. 308(3), pages 1142-1159.
    4. Behnke, Martin & Kirschstein, Thomas & Bierwirth, Christian, 2021. "A column generation approach for an emission-oriented vehicle routing problem on a multigraph," European Journal of Operational Research, Elsevier, vol. 288(3), pages 794-809.
    5. 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.
    6. Raeesi, Ramin & Zografos, Konstantinos G., 2020. "The electric vehicle routing problem with time windows and synchronised mobile battery swapping," Transportation Research Part B: Methodological, Elsevier, vol. 140(C), pages 101-129.
    7. Tomáš Režnar & Jan Martinovič & Kateřina Slaninová & Ekaterina Grakova & Vít Vondrák, 2017. "Probabilistic time-dependent vehicle routing problem," Central European Journal of Operations Research, Springer;Slovak Society for Operations Research;Hungarian Operational Research Society;Czech Society for Operations Research;Österr. Gesellschaft für Operations Research (ÖGOR);Slovenian Society Informatika - Section for Operational Research;Croatian Operational Research Society, vol. 25(3), pages 545-560, September.
    8. 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.
    9. Guo, Feng & Wei, Qu & Wang, Miao & Guo, Zhaoxia & Wallace, Stein W., 2023. "Deep attention models with dimension-reduction and gate mechanisms for solving practical time-dependent vehicle routing problems," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 173(C).
    10. Emna Marrekchi & Walid Besbes & Diala Dhouib & Emrah Demir, 2021. "A review of recent advances in the operations research literature on the green routing problem and its variants," Annals of Operations Research, Springer, vol. 304(1), pages 529-574, September.
    11. Ran Liu & Zhibin Jiang, 2019. "A constraint relaxation-based algorithm for the load-dependent vehicle routing problem with time windows," Flexible Services and Manufacturing Journal, Springer, vol. 31(2), pages 331-353, June.
    12. Vidal, Thibaut & Laporte, Gilbert & Matl, Piotr, 2020. "A concise guide to existing and emerging vehicle routing problem variants," European Journal of Operational Research, Elsevier, vol. 286(2), pages 401-416.
    13. Yiming Liu & Yang Yu & Yu Zhang & Roberto Baldacci & Jiafu Tang & Xinggang Luo & Wei Sun, 2023. "Branch-Cut-and-Price for the Time-Dependent Green Vehicle Routing Problem with Time Windows," INFORMS Journal on Computing, INFORMS, vol. 35(1), pages 14-30, January.
    14. Malladi, Satya S. & Christensen, Jonas M. & Ramírez, David & Larsen, Allan & Pacino, Dario, 2022. "Stochastic fleet mix optimization: Evaluating electromobility in urban logistics," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 158(C).
    15. Dumez, Dorian & Tilk, Christian & Irnich, Stefan & Lehuédé, Fabien & Olkis, Katharina & Péton, Olivier, 2023. "A matheuristic for a 2-echelon vehicle routing problem with capacitated satellites and reverse flows," European Journal of Operational Research, Elsevier, vol. 305(1), pages 64-84.
    16. Baals, Julian & Emde, Simon & Turkensteen, Marcel, 2023. "Minimizing earliness-tardiness costs in supplier networks—A just-in-time truck routing problem," European Journal of Operational Research, Elsevier, vol. 306(2), pages 707-741.
    17. Paraskevopoulos, Dimitris C. & Laporte, Gilbert & Repoussis, Panagiotis P. & Tarantilis, Christos D., 2017. "Resource constrained routing and scheduling: Review and research prospects," European Journal of Operational Research, Elsevier, vol. 263(3), pages 737-754.
    18. Dukkanci, Okan & Karsu, Özlem & Kara, Bahar Y., 2022. "Planning sustainable routes: Economic, environmental and welfare concerns," European Journal of Operational Research, Elsevier, vol. 301(1), pages 110-123.
    19. 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.
    20. Goeke, Dominik & Schneider, Michael, 2015. "Routing a mixed fleet of electric and conventional vehicles," European Journal of Operational Research, Elsevier, vol. 245(1), pages 81-99.

    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:eee:ejores:v:300:y:2022:i:3:p:1005-1016. 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: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/locate/eor .

    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.