IDEAS home Printed from https://ideas.repec.org/a/spr/orspec/v40y2018i4d10.1007_s00291-018-0506-6.html
   My bibliography  Save this article

A hybrid algorithm for the vehicle routing problem with backhauls, time windows and three-dimensional loading constraints

Author

Listed:
  • Henriette Koch

    (Otto-von-Guericke-University Magdeburg)

  • Andreas Bortfeldt

    (Otto-von-Guericke-University Magdeburg)

  • Gerhard Wäscher

    (Otto-von-Guericke-University Magdeburg
    Beijing Jiaotong University)

Abstract

This paper deals with a special vehicle routing problem with backhauls where customers may want to receive items from a depot and, at the same time, return items back to the depot. Moreover, time windows are assumed and three-dimensional loading constraints are to be observed, i.e. the items are three-dimensional boxes and packing constraints, e.g. regarding load stability, are to be met. The resulting problem is the vehicle routing problem with simultaneous delivery and pickup (VRPSDP), time windows and three-dimensional loading constraints (3L-VRPSDPTW). This problem occurs, for example, if retail stores are supplied by a central warehouse and wish to return packaging material. A particular challenge of the problem consists of transporting delivery and pickup items simultaneously on the same vehicle. In order to avoid any reloading effort during a tour, we consider two different approaches for loading the vehicles: (i) loading from the back with separation of the loading space into a delivery section and a pickup section and (ii) loading from the (long) side. A hybrid algorithm is proposed for the 3L-VRPSDPTW consisting of an adaptive large neighbourhood search for the routing and different packing heuristics for the loading part of the problem. Extensive numerical experiments are conducted with VRPSDP instances from the literature and newly generated instances for the 3L-VRPSDPTW.

Suggested Citation

  • 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.
    • Handle: RePEc:spr:orspec:v:40:y:2018:i:4:d:10.1007_s00291-018-0506-6
    DOI: 10.1007/s00291-018-0506-6
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s00291-018-0506-6
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.
    File URL: https://libkey.io/10.1007/s00291-018-0506-6?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. 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.
    3. 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.
    4. 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.
    5. Ropke, Stefan & Pisinger, David, 2006. "A unified heuristic for a large class of Vehicle Routing Problems with Backhauls," European Journal of Operational Research, Elsevier, vol. 171(3), pages 750-775, June.
    6. Kalayci, Can B. & Kulak, Osman & Günther, Hans-Otto, 2015. "A perturbation based variable neighborhood search heuristic for solving the Vehicle Routing Problem with Simultaneous Pickup and Delivery with Time LimitAuthor-Name: Polat, Olcay," European Journal of Operational Research, Elsevier, vol. 242(2), pages 369-382.
    7. Ana Moura, 2008. "A Multi-Objective Genetic Algorithm for the Vehicle Routing with Time Windows and Loading Problem," Springer Books, in: Andreas Bortfeldt & Jörg Homberger & Herbert Kopfer & Giselher Pankratz & Reinhard Strangmeier (ed.), Intelligent Decision Support, pages 187-201, Springer.
    8. Jakobs, Stefan, 1996. "On genetic algorithms for the packing of polygons," European Journal of Operational Research, Elsevier, vol. 88(1), pages 165-181, January.
    9. Andrea Lodi & Silvano Martello & Daniele Vigo, 1999. "Heuristic and Metaheuristic Approaches for a Class of Two-Dimensional Bin Packing Problems," INFORMS Journal on Computing, INFORMS, vol. 11(4), pages 345-357, November.
    10. Zachariadis, Emmanouil E. & Tarantilis, Christos D. & Kiranoudis, Chris T., 2016. "The Vehicle Routing Problem with Simultaneous Pick-ups and Deliveries and Two-Dimensional Loading Constraints," European Journal of Operational Research, Elsevier, vol. 251(2), pages 369-386.
    11. Dirk Männel & Andreas Bortfeldt, 2015. "A Hybrid Algorithm for the Vehicle Routing Problem with Pickup and Delivery and 3D Loading Constraints," FEMM Working Papers 150015, Otto-von-Guericke University Magdeburg, Faculty of Economics and Management.
    12. J Crispim & J Brandão, 2005. "Metaheuristics applied to mixed and simultaneous extensions of vehicle routing problems with backhauls," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 56(11), pages 1296-1302, November.
    13. 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.
    14. Mads Jepsen & Bjørn Petersen & Simon Spoorendonk & David Pisinger, 2008. "Subset-Row Inequalities Applied to the Vehicle-Routing Problem with Time Windows," Operations Research, INFORMS, vol. 56(2), pages 497-511, April.
    15. Paolo Toth & Daniele Vigo, 1997. "An Exact Algorithm for the Vehicle Routing Problem with Backhauls," Transportation Science, INFORMS, vol. 31(4), pages 372-385, November.
    16. 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.
    17. 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.
    18. G. Clarke & J. W. Wright, 1964. "Scheduling of Vehicles from a Central Depot to a Number of Delivery Points," Operations Research, INFORMS, vol. 12(4), pages 568-581, August.
    19. Manuel Iori & Silvano Martello, 2010. "Routing problems with loading constraints," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 18(1), pages 4-27, July.
    20. Roberto Baldacci & Aristide Mingozzi & Roberto Roberti, 2011. "New Route Relaxation and Pricing Strategies for the Vehicle Routing Problem," Operations Research, INFORMS, vol. 59(5), pages 1269-1283, October.
    21. 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.
    22. Tao Zhang & W. Art Chaovalitwongse & Yuejie Zhang, 2014. "Integrated Ant Colony and Tabu Search approach for time dependent vehicle routing problems with simultaneous pickup and delivery," Journal of Combinatorial Optimization, Springer, vol. 28(1), pages 288-309, July.
    23. Manuel Iori & Silvano Martello, 2010. "Rejoinder on: Routing problems with loading constraints," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 18(1), pages 41-42, July.
    24. 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.
    25. Niaz A. Wassan & A. Hameed Wassan & Gábor Nagy, 2008. "A reactive tabu search algorithm for the vehicle routing problem with simultaneous pickups and deliveries," Journal of Combinatorial Optimization, Springer, vol. 15(4), pages 368-386, May.
    26. Stefan Irnich & Daniel Villeneuve, 2006. "The Shortest-Path Problem with Resource Constraints and k -Cycle Elimination for k (ge) 3," INFORMS Journal on Computing, INFORMS, vol. 18(3), pages 391-406, August.
    27. Liu, Dequan & Teng, Hongfei, 1999. "An improved BL-algorithm for genetic algorithm of the orthogonal packing of rectangles," European Journal of Operational Research, Elsevier, vol. 112(2), pages 413-420, January.
    28. Niklas Kohl & Jacques Desrosiers & Oli B. G. Madsen & Marius M. Solomon & François Soumis, 1999. "2-Path Cuts for the Vehicle Routing Problem with Time Windows," Transportation Science, INFORMS, vol. 33(1), pages 101-116, February.
    29. Gajpal, Yuvraj & Abad, P.L., 2009. "Multi-ant colony system (MACS) for a vehicle routing problem with backhauls," European Journal of Operational Research, Elsevier, vol. 196(1), pages 102-117, July.
    30. S Salhi & G Nagy, 1999. "A cluster insertion heuristic for single and multiple depot vehicle routing problems with backhauling," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 50(10), pages 1034-1042, October.
    31. Davies, A. Paul & Bischoff, Eberhard E., 1999. "Weight distribution considerations in container loading," European Journal of Operational Research, Elsevier, vol. 114(3), pages 509-527, May.
    32. Mauro Dell’Amico & Giovanni Righini & Matteo Salani, 2006. "A Branch-and-Price Approach to the Vehicle Routing Problem with Simultaneous Distribution and Collection," Transportation Science, INFORMS, vol. 40(2), pages 235-247, May.
    33. Zachariadis, Emmanouil E. & Tarantilis, Christos D. & Kiranoudis, Chris T., 2010. "An adaptive memory methodology for the vehicle routing problem with simultaneous pick-ups and deliveries," European Journal of Operational Research, Elsevier, vol. 202(2), pages 401-411, 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. 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.
    3. 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.
    4. 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.
    5. 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.
    6. 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.
    7. Yong Liu & Zhicheng Yue & Yong Wang & Haizhong Wang, 2023. "Logistics Distribution Vehicle Routing Problem with Time Window under Pallet 3D Loading Constraint," Sustainability, MDPI, vol. 15(4), pages 1-25, February.
    8. 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.
    9. Alexander Hübner & Pedro Amorim & Heinrich Kuhn & Stefan Minner & Tom Woensel, 2018. "Retail operations," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 40(4), pages 831-835, October.
    10. 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.
    11. 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.

    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, 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.
    2. 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.
    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. 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.
    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. 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.
    7. Lei, Jieyu & Che, Ada & Van Woensel, Tom, 2024. "Collection-disassembly-delivery problem of disassembly centers in a reverse logistics network," European Journal of Operational Research, Elsevier, vol. 313(2), pages 478-493.
    8. 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.
    9. 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.
    10. Dominguez, Oscar & Guimarans, Daniel & Juan, Angel A. & de la Nuez, Ignacio, 2016. "A Biased-Randomised Large Neighbourhood Search for the two-dimensional Vehicle Routing Problem with Backhauls," European Journal of Operational Research, Elsevier, vol. 255(2), pages 442-462.
    11. Liu, Ran & Xie, Xiaolan & Augusto, Vincent & Rodriguez, Carlos, 2013. "Heuristic algorithms for a vehicle routing problem with simultaneous delivery and pickup and time windows in home health care," European Journal of Operational Research, Elsevier, vol. 230(3), pages 475-486.
    12. 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.
    13. 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.
    14. 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.
    15. 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.
    16. Bonet Filella, Guillem & Trivella, Alessio & Corman, Francesco, 2023. "Modeling soft unloading constraints in the multi-drop container loading problem," European Journal of Operational Research, Elsevier, vol. 308(1), pages 336-352.
    17. Bortfeldt, Andreas & Wäscher, Gerhard, 2013. "Constraints in container loading – A state-of-the-art review," European Journal of Operational Research, Elsevier, vol. 229(1), pages 1-20.
    18. Zhang, Zhenzhen & Wei, Lijun & Lim, Andrew, 2015. "An evolutionary local search for the capacitated vehicle routing problem minimizing fuel consumption under three-dimensional loading constraints," Transportation Research Part B: Methodological, Elsevier, vol. 82(C), pages 20-35.
    19. Bhusiri, Narath & Qureshi, Ali Gul & Taniguchi, Eiichi, 2014. "The trade-off between fixed vehicle costs and time-dependent arrival penalties in a routing problem," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 62(C), pages 1-22.
    20. 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.

    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:spr:orspec:v:40:y:2018:i:4:d:10.1007_s00291-018-0506-6. 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: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    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.