[go: up one dir, main page]
IDEAS home Printed from https://ideas.repec.org/a/eee/ejores/v266y2018i3p877-894.html
   My bibliography  Save this article

Heuristics for vehicle routing problems with backhauls, time windows, and 3D loading constraints

Author

Listed:
  • Reil, Sebastian
  • Bortfeldt, Andreas
  • Mönch, Lars
Abstract
In this paper, we consider vehicle routing problems with backhauls and time windows (VRPBTW). Different backhaul variants are studied, namely clustered backhauls (CB), mixed linehauls and backhauls, and variants with simultaneous delivery and pickup and with divisible delivery and pickup. Three dimensional loading constraints are assumed. A two-phase approach following the principle packing first, routing second is proposed. In the first phase, the packing of goods is carried out by solving a 3D strip packing problem for each customer using tabu search. The resulting VRPTW instance is solved in the second phase using first a multi-start evolutionary strategy to minimize the number of vehicles while again tabu search is applied to minimize the total travel distance. We show that the various backhaul types can be incorporated into this framework. For the backhaul variants different from CB, unloading and reloading efforts are taken into account. Moreover, side loading and a separation of the loading space into separate compartments for goods of linehaul and backhaul customers are proposed. Computational results for benchmark instances and new randomly generated problem instances are presented that demonstrate that the heuristics determine high-quality solutions in a short amount of computing time. The unloading and reloading strategies outperform the strategies based on two separate compartments.

Suggested Citation

  • Reil, Sebastian & Bortfeldt, Andreas & Mönch, Lars, 2018. "Heuristics for vehicle routing problems with backhauls, time windows, and 3D loading constraints," European Journal of Operational Research, Elsevier, vol. 266(3), pages 877-894.
    • Handle: RePEc:eee:ejores:v:266:y:2018:i:3:p:877-894
    DOI: 10.1016/j.ejor.2017.10.029
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377221717309426
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.ejor.2017.10.029?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. Fuellerer, Guenther & Doerner, Karl F. & Hartl, Richard F. & Iori, Manuel, 2010. "Metaheuristics for vehicle routing problems with three-dimensional loading constraints," European Journal of Operational Research, Elsevier, vol. 201(3), pages 751-759, March.
    2. Michel Gendreau & Manuel Iori & Gilbert Laporte & Silvano Martello, 2006. "A Tabu Search Algorithm for a Routing and Container Loading Problem," Transportation Science, INFORMS, vol. 40(3), pages 342-350, August.
    3. Goetschalckx, Marc & Jacobs-Blecha, Charlotte, 1989. "The vehicle routing problem with backhauls," European Journal of Operational Research, Elsevier, vol. 42(1), pages 39-51, September.
    4. Sprenger, Ralf & Mönch, Lars, 2012. "A methodology to solve large-scale cooperative transportation planning problems," European Journal of Operational Research, Elsevier, vol. 223(3), pages 626-636.
    5. Lahyani, Rahma & Khemakhem, Mahdi & Semet, Frédéric, 2015. "Rich vehicle routing problems: From a taxonomy to a definition," European Journal of Operational Research, Elsevier, vol. 241(1), pages 1-14.
    6. 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.
    7. Vidal, Thibaut & Crainic, Teodor Gabriel & Gendreau, Michel & Prins, Christian, 2014. "A unified solution framework for multi-attribute vehicle routing problems," European Journal of Operational Research, Elsevier, vol. 234(3), pages 658-673.
    8. Bortfeldt, Andreas & Hahn, Thomas & Männel, Dirk & Mönch, Lars, 2015. "Hybrid algorithms for the vehicle routing problem with clustered backhauls and 3D loading constraints," European Journal of Operational Research, Elsevier, vol. 243(1), pages 82-96.
    9. 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.
    10. Marc Reimann & Heinz Ulrich, 2006. "Comparing backhauling strategies in vehicle routing using Ant Colony Optimization," 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. 14(2), pages 105-123, June.
    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. Männel, Dirk & Bortfeldt, Andreas, 2016. "A hybrid algorithm for the vehicle routing problem with pickup and delivery and three-dimensional loading constraints," European Journal of Operational Research, Elsevier, vol. 254(3), pages 840-858.
    13. Bischoff, E. E. & Ratcliff, M. S. W., 1995. "Issues in the development of approaches to container loading," Omega, Elsevier, vol. 23(4), pages 377-390, August.
    14. Wade, A. C. & Salhi, S., 2002. "An investigation into a new class of vehicle routing problem with backhauls," Omega, Elsevier, vol. 30(6), pages 479-487, December.
    15. Zachariadis, Emmanouil E. & Tarantilis, Christos D. & Kiranoudis, Chris T., 2013. "Designing vehicle routes for a mix of different request types, under time windows and loading constraints," European Journal of Operational Research, Elsevier, vol. 229(2), pages 303-317.
    16. Emmanouil E. Zachariadis & Christos D. Tarantilis & Chris T. Kiranoudis, 2012. "The Pallet-Packing Vehicle Routing Problem," Transportation Science, INFORMS, vol. 46(3), pages 341-358, August.
    17. Homberger, Jorg & Gehring, Hermann, 2005. "A two-phase hybrid metaheuristic for the vehicle routing problem with time windows," European Journal of Operational Research, Elsevier, vol. 162(1), pages 220-238, April.
    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. Xiang Song & Dylan Jones & Nasrin Asgari & Tim Pigden, 2020. "Multi-objective vehicle routing and loading with time window constraints: a real-life application," Annals of Operations Research, Springer, vol. 291(1), pages 799-825, August.
    2. Ostermeier, Manuel & Henke, Tino & Hübner, Alexander & Wäscher, Gerhard, 2021. "Multi-compartment vehicle routing problems: State-of-the-art, modeling framework and future directions," European Journal of Operational Research, Elsevier, vol. 292(3), pages 799-817.
    3. Maria João Santos & Pedro Amorim & Alexandra Marques & Ana Carvalho & Ana Póvoa, 2020. "The vehicle routing problem with backhauls towards a sustainability perspective: a review," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 28(2), pages 358-401, July.
    4. Cherkesly, Marilène & Gschwind, Timo, 2022. "The pickup and delivery problem with time windows, multiple stacks, and handling operations," European Journal of Operational Research, Elsevier, vol. 301(2), pages 647-666.
    5. Bortfeldt, Andreas & Yi, Junmin, 2020. "The Split Delivery Vehicle Routing Problem with three-dimensional loading constraints," European Journal of Operational Research, Elsevier, vol. 282(2), pages 545-558.
    6. Canan G. Corlu & Rocio de la Torre & Adrian Serrano-Hernandez & Angel A. Juan & Javier Faulin, 2020. "Optimizing Energy Consumption in Transportation: Literature Review, Insights, and Research Opportunities," Energies, MDPI, vol. 13(5), pages 1-33, March.
    7. Corinna Krebs & Jan Fabian Ehmke & Henriette Koch, 2021. "Advanced loading constraints for 3D vehicle routing problems," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 43(4), pages 835-875, December.
    8. Tibor Holczinger & Olivér Ősz & Máté Hegyháti, 2020. "Scheduling approach for on-site jobs of service providers," Flexible Services and Manufacturing Journal, Springer, vol. 32(4), pages 913-948, December.
    9. 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.
    10. Henriette Koch & Maximilian Schlögell & Andreas Bortfeldt, 2020. "A hybrid algorithm for the vehicle routing problem with three-dimensional loading constraints and mixed backhauls," Journal of Scheduling, Springer, vol. 23(1), pages 71-93, February.
    11. Majsa Ammouriova & Massimo Bertolini & Juliana Castaneda & Angel A. Juan & Mattia Neroni, 2022. "A Heuristic-Based Simulation for an Education Process to Learn about Optimization Applications in Logistics and Transportation," Mathematics, MDPI, vol. 10(5), pages 1-18, March.
    12. Rajaei, Maryam & Moslehi, Ghasem & Reisi-Nafchi, Mohammad, 2022. "The split heterogeneous vehicle routing problem with three-dimensional loading constraints on a large scale," European Journal of Operational Research, Elsevier, vol. 299(2), pages 706-721.
    13. Vélez-Gallego, Mario C. & Teran-Somohano, Alejandro & Smith, Alice E., 2020. "Minimizing late deliveries in a truck loading problem," European Journal of Operational Research, Elsevier, vol. 286(3), pages 919-928.
    14. Zongyi Chen & Mingkang Yang & Yijun Guo & Yu Liang & Yifan Ding & Li Wang, 2020. "The Split Delivery Vehicle Routing Problem with Three-Dimensional Loading and Time Windows Constraints," Sustainability, MDPI, vol. 12(17), pages 1-21, August.
    15. Julio C. Londoño & Rafael D. Tordecilla & Leandro do C. Martins & Angel A. Juan, 2021. "A biased-randomized iterated local search for the vehicle routing problem with optional backhauls," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 29(2), pages 387-416, July.
    16. Lei Chen & Haiyan Ma & Yi Wang & Feng Li, 2022. "Vehicle Routing Problem for the Simultaneous Pickup and Delivery of Lithium Batteries of Small Power Vehicles under Charging and Swapping Mode," Sustainability, MDPI, vol. 14(16), pages 1-23, August.
    17. Xiaobo Liu & Yen-Lin Chen & Lip Yee Por & Chin Soon Ku, 2023. "A Systematic Literature Review of Vehicle Routing Problems with Time Windows," Sustainability, MDPI, vol. 15(15), pages 1-20, August.
    18. Amir Saeed Nikkhah Qamsari & Seyyed-Mahdi Hosseini-Motlagh & Seyed Farid Ghannadpour, 2022. "A column generation approach for an inventory routing problem with fuzzy time windows," Operational Research, Springer, vol. 22(2), pages 1157-1207, April.

    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. Henriette Koch & Andreas Bortfeldt & Gerhard Wäscher, 2018. "A hybrid algorithm for the vehicle routing problem with backhauls, time windows and three-dimensional loading constraints," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 40(4), pages 1029-1075, October.
    2. Henriette Koch & Andreas Bortfeldt & Gerhard Wäscher, 2017. "A hybrid solution approach for the 3L-VRP with simultaneous delivery and pickups," FEMM Working Papers 170005, Otto-von-Guericke University Magdeburg, Faculty of Economics and Management.
    3. Bortfeldt, Andreas & Yi, Junmin, 2020. "The Split Delivery Vehicle Routing Problem with three-dimensional loading constraints," European Journal of Operational Research, Elsevier, vol. 282(2), pages 545-558.
    4. Maria João Santos & Pedro Amorim & Alexandra Marques & Ana Carvalho & Ana Póvoa, 2020. "The vehicle routing problem with backhauls towards a sustainability perspective: a review," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 28(2), pages 358-401, July.
    5. Carlos A. Vega-Mejía & Jairo R. Montoya-Torres & Sardar M. N. Islam, 2019. "Consideration of triple bottom line objectives for sustainability in the optimization of vehicle routing and loading operations: a systematic literature review," Annals of Operations Research, Springer, vol. 273(1), pages 311-375, February.
    6. Lahyani, Rahma & Khemakhem, Mahdi & Semet, Frédéric, 2015. "Rich vehicle routing problems: From a taxonomy to a definition," European Journal of Operational Research, Elsevier, vol. 241(1), pages 1-14.
    7. 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.
    8. Bortfeldt, Andreas & Hahn, Thomas & Männel, Dirk & Mönch, Lars, 2015. "Hybrid algorithms for the vehicle routing problem with clustered backhauls and 3D loading constraints," European Journal of Operational Research, Elsevier, vol. 243(1), pages 82-96.
    9. Henriette Koch & Maximilian Schlögell & Andreas Bortfeldt, 2020. "A hybrid algorithm for the vehicle routing problem with three-dimensional loading constraints and mixed backhauls," Journal of Scheduling, Springer, vol. 23(1), pages 71-93, February.
    10. Rajaei, Maryam & Moslehi, Ghasem & Reisi-Nafchi, Mohammad, 2022. "The split heterogeneous vehicle routing problem with three-dimensional loading constraints on a large scale," European Journal of Operational Research, Elsevier, vol. 299(2), pages 706-721.
    11. Männel, Dirk & Bortfeldt, Andreas, 2016. "A hybrid algorithm for the vehicle routing problem with pickup and delivery and three-dimensional loading constraints," European Journal of Operational Research, Elsevier, vol. 254(3), pages 840-858.
    12. Schmid, Verena & Doerner, Karl F. & Laporte, Gilbert, 2013. "Rich routing problems arising in supply chain management," European Journal of Operational Research, Elsevier, vol. 224(3), pages 435-448.
    13. 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.
    14. Xiang Song & Dylan Jones & Nasrin Asgari & Tim Pigden, 2020. "Multi-objective vehicle routing and loading with time window constraints: a real-life application," Annals of Operations Research, Springer, vol. 291(1), pages 799-825, August.
    15. Andrew Lim & Xingwen Zhang, 2007. "A Two-Stage Heuristic with Ejection Pools and Generalized Ejection Chains for the Vehicle Routing Problem with Time Windows," INFORMS Journal on Computing, INFORMS, vol. 19(3), pages 443-457, August.
    16. 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.
    17. Cherkesly, Marilène & Gschwind, Timo, 2022. "The pickup and delivery problem with time windows, multiple stacks, and handling operations," European Journal of Operational Research, Elsevier, vol. 301(2), pages 647-666.
    18. Corinna Krebs & Jan Fabian Ehmke, 2023. "Solution validator and visualizer for (combined) vehicle routing and container loading problems," Annals of Operations Research, Springer, vol. 326(1), pages 561-579, July.
    19. Alcaraz, Juan J. & Caballero-Arnaldos, Luis & Vales-Alonso, Javier, 2019. "Rich vehicle routing problem with last-mile outsourcing decisions," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 129(C), pages 263-286.
    20. Zachariadis, Emmanouil E. & Tarantilis, Christos D. & Kiranoudis, Chris T., 2013. "Designing vehicle routes for a mix of different request types, under time windows and loading constraints," European Journal of Operational Research, Elsevier, vol. 229(2), pages 303-317.

    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:266:y:2018:i:3:p:877-894. 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.