IDEAS home Printed from https://ideas.repec.org/a/spr/jsched/v23y2020i1d10.1007_s10951-019-00625-7.html
   My bibliography  Save this article

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

Author

Listed:
  • Henriette Koch

    (Otto-von-Guericke-University Magdeburg)

  • Maximilian Schlögell

    (Otto-von-Guericke-University Magdeburg)

  • Andreas Bortfeldt

    (Otto-von-Guericke-University Magdeburg)

Abstract

In this paper, a variant of the vehicle routing problem with mixed backhauls (VRPMB) is presented, i.e. goods have to be delivered from a central depot to linehaul customers, and, at the same time, goods have to be picked up from backhaul customers and brought to the depot. Both types of customers can be visited in mixed sequences. The goods to be delivered or picked up are three-dimensional (cuboid) items. Hence, in addition to a routing plan, a feasible packing plan for each tour has to be provided considering a number of loading constraints. The resulting problem is the vehicle routing problem with three-dimensional loading constraints and mixed backhauls (3L-VRPMB). The simultaneous transport of linehaul and backhaul items presents a particular challenge of the problem. We consider two different loading variants in order to avoid any reloading during the tour: (i) rear loading with separate linehaul and backhaul sections and (ii) loading at a long side. In order to solve the problem, we propose a hybrid metaheuristic consisting of a reactive tabu search for the routing problem and different packing heuristics for the loading problem. Numerical experiments are reported with benchmark instances from the literature for the one-dimensional VRPMB to examine the performance of the routing algorithm and with newly generated instances for the 3L-VRPMB.

Suggested Citation

  • 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.
    • Handle: RePEc:spr:jsched:v:23:y:2020:i:1:d:10.1007_s10951-019-00625-7
    DOI: 10.1007/s10951-019-00625-7
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10951-019-00625-7
    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/s10951-019-00625-7?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. 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.
    2. 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.
    3. Niaz A. Wassan & Said Salhi & Gábor Nagy & Naveed Wassan & Anne C. Wade, 2013. "Solving the Mixed Backhauling Vehicle Routing: Problem with Ants," International Journal of Energy Optimization and Engineering (IJEOE), IGI Global, vol. 2(2), pages 62-77, April.
    4. 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.
    5. 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.
    6. 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.
    7. 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.
    8. Billy E. Gillett & Leland R. Miller, 1974. "A Heuristic Algorithm for the Vehicle-Dispatch Problem," Operations Research, INFORMS, vol. 22(2), pages 340-349, April.
    9. 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.
    10. 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.
    11. 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.
    12. 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.
    13. 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.
    14. 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.
    15. 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.
    16. Célia Paquay, 2017. "The three-dimensional rectangular Multiple Bin Size Bin Packing Problem with transportation constraints," 4OR, Springer, vol. 15(4), pages 431-432, December.
    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. 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.
    20. 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.
    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. Yaoting Huang & Boyu Chen & Wenlian Lu & Zhong-Xiao Jin & Ren Zheng, 2022. "Asynchronous optimization of part logistics routing problem," Journal of Global Optimization, Springer, vol. 82(4), pages 803-834, 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. 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. 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.
    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. 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.
    7. 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.
    8. 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.
    9. 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.
    10. 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.
    11. Qiuping Ni & Yuanxiang Tang, 2023. "A Bibliometric Visualized Analysis and Classification of Vehicle Routing Problem Research," Sustainability, MDPI, vol. 15(9), pages 1-37, April.
    12. 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.
    13. YazgI Tütüncü, G. & Carreto, Carlos A.C. & Baker, Barrie M., 2009. "A visual interactive approach to classical and mixed vehicle routing problems with backhauls," Omega, Elsevier, vol. 37(1), pages 138-154, February.
    14. Yang, Senyan & Ning, Lianju & Shang, Pan & (Carol) Tong, Lu, 2020. "Augmented Lagrangian relaxation approach for logistics vehicle routing problem with mixed backhauls and time windows," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 135(C).
    15. 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.
    16. Männel, Dirk & Bortfeldt, Andreas, 2018. "Solving the pickup and delivery problem with three-dimensional loading constraints and reloading ban," European Journal of Operational Research, Elsevier, vol. 264(1), pages 119-137.
    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. 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.
    19. S Mitra, 2008. "A parallel clustering technique for the vehicle routing problem with split deliveries and pickups," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 59(11), pages 1532-1546, November.
    20. N Wassan, 2007. "Reactive tabu adaptive memory programming search for the vehicle routing problem with backhauls," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 58(12), pages 1630-1641, December.

    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:jsched:v:23:y:2020:i:1:d:10.1007_s10951-019-00625-7. 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.