Skip to main content
Erschienen in: OR Spectrum 4/2018

01.02.2018 | Regular Article

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

verfasst von: Henriette Koch, Andreas Bortfeldt, Gerhard Wäscher

Erschienen in: OR Spectrum | Ausgabe 4/2018

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

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.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Fußnoten
1
Note that we omit the 14 instances with drop times and maximum distance constraints since those problem aspects are not considered here and the instances are identical to the other 14 instances with respect to the other problem information.
 
2
Computer used by Gonçalves and Resende (2012): AMD 2.2 GHz Opteron 6-core CPU with Linux (Fedora release 12) operating system.
 
Literatur
Zurück zum Zitat Cook W, Rich JL (1999) A parallel cutting-plane algorithm for the vehicle routing problem with time windows. Computational and Applied Mathematics Department, Rice University, Houston, TX, Technical Report Cook W, Rich JL (1999) A parallel cutting-plane algorithm for the vehicle routing problem with time windows. Computational and Applied Mathematics Department, Rice University, Houston, TX, Technical Report
Zurück zum Zitat Dominguez O, Guimarans D, Juan AA (2015) A hybrid heuristic for the 2L-VRP with clustered backhauls. In: Proceedings of the XVI Conferencia de la Asociación Española para la Inteligencia Artificial (CAEPIA) Dominguez O, Guimarans D, Juan AA (2015) A hybrid heuristic for the 2L-VRP with clustered backhauls. In: Proceedings of the XVI Conferencia de la Asociación Española para la Inteligencia Artificial (CAEPIA)
Zurück zum Zitat Halse K (1992) Modeling and solving complex vehicle routing problems. Ph.D. Thesis, Technical University of Denmark, Lyngby Halse K (1992) Modeling and solving complex vehicle routing problems. Ph.D. Thesis, Technical University of Denmark, Lyngby
Zurück zum Zitat Hopper E (2000) Two-dimensional packing utilising evolutionary algorithms and other meta-heuristic methods. Ph.D. Thesis, University of Wales. Cardiff Hopper E (2000) Two-dimensional packing utilising evolutionary algorithms and other meta-heuristic methods. Ph.D. Thesis, University of Wales. Cardiff
Zurück zum Zitat Irnich S, Toth P, Vigo D (2014) The family of vehicle routing problems. In: Toth P, Vigo D (eds) Vehicle routing, MOS-SIAM series on optimization. SIAM, Philadelphia, pp 1–33 Irnich S, Toth P, Vigo D (2014) The family of vehicle routing problems. In: Toth P, Vigo D (eds) Vehicle routing, MOS-SIAM series on optimization. SIAM, Philadelphia, pp 1–33
Zurück zum Zitat Kallehauge B, Larsen J, Madsen OB (2000) Lagrangian duality and non-differentiable optimization applied on routing with time windows-experimental results. Relatório interno IMM-REP-2000-8, Department of Mathematical Modeling, Technical University of Denmark, Lyngby, Dinamarca Kallehauge B, Larsen J, Madsen OB (2000) Lagrangian duality and non-differentiable optimization applied on routing with time windows-experimental results. Relatório interno IMM-REP-2000-8, Department of Mathematical Modeling, Technical University of Denmark, Lyngby, Dinamarca
Zurück zum Zitat Larsen J (1999) Parallelization of the vehicle routing problem with time windows. Ph.D. Thesis, Technical University of Denmark, Department of Informatics and Mathematical Modeling Larsen J (1999) Parallelization of the vehicle routing problem with time windows. Ph.D. Thesis, Technical University of Denmark, Department of Informatics and Mathematical Modeling
Zurück zum Zitat Maquera G, Laguna M, Gandelman DA, Sant’Anna AP (2012) Scatter search applied to the vehicle routing problem with simultaneous delivery and pickup. In: Yin PY (ed) Trends in developing metaheuristics, algorithms, and optimization approaches. IGI Global, pp 149–168. https://doi.org/10.4018/978-1-4666-2145-9.ch010 Maquera G, Laguna M, Gandelman DA, Sant’Anna AP (2012) Scatter search applied to the vehicle routing problem with simultaneous delivery and pickup. In: Yin PY (ed) Trends in developing metaheuristics, algorithms, and optimization approaches. IGI Global, pp 149–168. https://​doi.​org/​10.​4018/​978-1-4666-2145-9.​ch010
Zurück zum Zitat Moura A (2008) A multi-objective genetic algorithm for the vehicle routing with time windows and loading problem. In: Bortfeldt A, Homberger J, Kopfer H, Pankratz G, Strangmeier R (eds) Intelligent decision support, Gabler Edition Wissenschaft, Betriebswirtschaftlicher Verlag Dr. Th. Gabler/GWV Fachverlage GmbH Wiesbaden, Wiesbaden, pp 187–201. https://doi.org/10.1007/978-3-8349-9777-7_11 Moura A (2008) A multi-objective genetic algorithm for the vehicle routing with time windows and loading problem. In: Bortfeldt A, Homberger J, Kopfer H, Pankratz G, Strangmeier R (eds) Intelligent decision support, Gabler Edition Wissenschaft, Betriebswirtschaftlicher Verlag Dr. Th. Gabler/GWV Fachverlage GmbH Wiesbaden, Wiesbaden, pp 187–201. https://​doi.​org/​10.​1007/​978-3-8349-9777-7_​11
Zurück zum Zitat Reimann M, Doerner K, Hartl RF (2002) Insertion based ants for vehicle routing problems with backhauls and time windows. In: Dorigo M, Di Caro G, Sampels M (eds) Ant algorithms: third international workshop, ANTS 2002 Brussels, Belgium, September 12–14, 2002 Proceedings, Springer, Berlin, pp 135–148. https://doi.org/10.1007/3-540-45724-0_12 CrossRef Reimann M, Doerner K, Hartl RF (2002) Insertion based ants for vehicle routing problems with backhauls and time windows. In: Dorigo M, Di Caro G, Sampels M (eds) Ant algorithms: third international workshop, ANTS 2002 Brussels, Belgium, September 12–14, 2002 Proceedings, Springer, Berlin, pp 135–148. https://​doi.​org/​10.​1007/​3-540-45724-0_​12 CrossRef
Zurück zum Zitat Salani M (2006) Branch-and-price algorithms for vehicle routing problems. Ph.D. Thesis, Università degli studi di Milano Salani M (2006) Branch-and-price algorithms for vehicle routing problems. Ph.D. Thesis, Università degli studi di Milano
Zurück zum Zitat Shaw P (1997) A new local search algorithm providing high quality solutions to vehicle routing problems Shaw P (1997) A new local search algorithm providing high quality solutions to vehicle routing problems
Zurück zum Zitat Shaw P (1998) Using constraint programming and local search methods to solve vehicle routing problems. In: Maher M, Puget JF (eds) Principles and practice of constraint programming—CP98. Lecture Notes in Computer Science, vol 1520. Springer, Berlin, pp 417–431. https://doi.org/10.1007/3-540-49481-2_30 CrossRef Shaw P (1998) Using constraint programming and local search methods to solve vehicle routing problems. In: Maher M, Puget JF (eds) Principles and practice of constraint programming—CP98. Lecture Notes in Computer Science, vol 1520. Springer, Berlin, pp 417–431. https://​doi.​org/​10.​1007/​3-540-49481-2_​30 CrossRef
Zurück zum Zitat Solomon MM (1987) Algorithms for the vehicle routing and scheduling problems with time window constraints. Oper Res 35(2):254–265CrossRef Solomon MM (1987) Algorithms for the vehicle routing and scheduling problems with time window constraints. Oper Res 35(2):254–265CrossRef
Zurück zum Zitat Wang L, Guo S, Chen S, Zhu W, Lim A (2010) Two natural heuristics for 3D packing with practical loading constraints. In: Zhang BT, Orgun MA (eds) PRICAI 2010: trends in artificial intelligence. Lecture Notes in Computer Science, Lecture Notes in Artificial Intelligence, vol 6230. Springer, Berlin, pp 256–267. https://doi.org/10.1007/978-3-642-15246-7_25 CrossRef Wang L, Guo S, Chen S, Zhu W, Lim A (2010) Two natural heuristics for 3D packing with practical loading constraints. In: Zhang BT, Orgun MA (eds) PRICAI 2010: trends in artificial intelligence. Lecture Notes in Computer Science, Lecture Notes in Artificial Intelligence, vol 6230. Springer, Berlin, pp 256–267. https://​doi.​org/​10.​1007/​978-3-642-15246-7_​25 CrossRef
Zurück zum Zitat Wisniewski MA, Ritt M, Buriol LS (2011) A tabu search algorithm for the capacitated vehicle routing problem with three-dimensional loading constraints. In: XLIII Simposio Brasilero de Pesquisa Operacional Wisniewski MA, Ritt M, Buriol LS (2011) A tabu search algorithm for the capacitated vehicle routing problem with three-dimensional loading constraints. In: XLIII Simposio Brasilero de Pesquisa Operacional
Metadaten
Titel
A hybrid algorithm for the vehicle routing problem with backhauls, time windows and three-dimensional loading constraints
verfasst von
Henriette Koch
Andreas Bortfeldt
Gerhard Wäscher
Publikationsdatum
01.02.2018
Verlag
Springer Berlin Heidelberg
Erschienen in
OR Spectrum / Ausgabe 4/2018
Print ISSN: 0171-6468
Elektronische ISSN: 1436-6304
DOI
https://doi.org/10.1007/s00291-018-0506-6

Weitere Artikel der Ausgabe 4/2018

OR Spectrum 4/2018 Zur Ausgabe