Top

OR Spectrum

Published in:

27-12-2019 | Regular Article

A matheuristic for the swap body vehicle routing problem

Authors: Sandra Huber, Jean-François Cordeau, Martin Josef Geiger

Published in: OR Spectrum | Issue 1/2020

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

We consider the swap body vehicle routing problem, an extension of the capacitated vehicle routing problem, in which intermediate locations can be used to change the configuration of a vehicle. Possible actions include a parking operation that decouples the semitrailer as well as a swapping operation that switches the swap body with another one, which was previously parked at an intermediate location. Successful ideas that combine mathematical programming and heuristics have been recently presented for several vehicle routing problems. In this line, the contribution of this paper is the development of a column generation-based approach, in which a variable neighborhood search heuristic populates the route pool. A detailed numerical analysis is carried out for 138 instances with up to 1000 customers and at most 100 intermediate locations. Comparisons with existing metaheuristics show that our solution strategy is suitable for solving this problem. It has obtained 42 new best known solutions with a maximal improvement of 18.54% on published benchmark instances.

previous article A new matheuristic approach for the multi-depot vehicle routing problem with inter-depot routes

next article Enhancing Benders decomposition algorithm to solve a combat logistics problem

Dont have a licence yet? Then find out more about our products and how to get one now:

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!

inform now

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!

inform now

Absi N, Cattaruzza D, Feillet D, Housseman S (2015) A relax-and-repair heuristic for the swap-body vehicle routing problem. Ann Oper Res 253(2):1–22

Archetti C, Speranza MG (2014) A survey on matheuristics for routing problems. EURO J Comput Optim 2(4):223–246CrossRef

Ball MO (2011) Heuristics based on mathematical programming. Surv Oper Res Manag Sci 16(1):21–38

Boschetti MA, Maniezzo V, Roffilli M, Bolufé Röhler A (2009) Matheuristics: optimization, simulation and control. In: Blesa MJ, Blum C, Di Gaspero L, Roli A, Sampels M, Schaerf A (eds) Hybrid Metaheuristics: 6th international workshop, HM 2009. Springer, Berlin, pp 171–177CrossRef

Cordeau JF, Laganà D, Musmanno R, Vocaturo F (2015) A decomposition-based heuristic for the multiple-product inventory-routing problem. Comput Oper Res 55(Supplement C):153–166CrossRef

Doerner KF, Schmid V (2010) Survey: matheuristics for rich vehicle routing problems. In: Blesa MJ, Blum C, Raidl G, Roli A, Sampels M (eds) Hybrid metaheuristics: 7th international workshop, HM 2010, vol 6373. Lecture Notes in Computer Science. Berlin, Heidelberg, pp 206–221CrossRef

Erdoğan G, McLeod F, Cherrett T, Bektaş T (2015) Matheuristics for solving a multi-attribute collection problem for a charity organisation. J Oper Res Soc 66(2):177–190CrossRef

Grangier P, Gendreau M, Lehuédé F, Rousseau LM (2017) A matheuristic based on large neighborhood search for the vehicle routing problem with cross-docking. Comput Oper Res 84:116–126CrossRef

Heid W, Hasle G, Vigo D (2014) Verolog solver challenge 2014–VSC2014 problem description. http://verolog.deis.unibo.it/news-events/general-news/verolog-solver-challenge-2014

Huber S, Geiger MJ (2014) Swap body vehicle routing problem: a heuristic solution approach. In: González-Ramírez RG, Schulte F, Voß S, Ceroni Díaz JA (eds) Computational logistics, vol 8760. Lecture Notes in Computer Science. Springer, Berlin, pp 16–30

Huber S, Geiger MJ (2017) Order matters—a variable neighborhood search for the swap-body vehicle routing problem. Eur J Oper Res 263(2):419–445CrossRef

Kobesen V (2019) PTV Group. URL https://www.ptvgroup.com

Kramer R, Subramanian A, Vidal T, dos Anjos F, Cabral L (2015) A matheuristic approach for the pollution-routing problem. Eur J Oper Res 243(2):523–539CrossRef

Leggieri V, Haouari M (2016) A matheuristic for the asymmetric capacitated vehicle routing problem. Discret Appl Math 49(1):193–212

Lum O, Chen P, Wang X, Golden B, Wasil E (2015) A heuristic approach for the swap-body vehicle routing problem. In: 14th INFORMS computing society conference, pp 172–187

Mendoza JE, Rousseau LM, Villegas JG (2016) A hybrid metaheuristic for the vehicle routing problem with stochastic demand and duration constraints. J Heuristics 22(4):539–566CrossRef

Miranda-Bront JJ, Curcio B, Méndez-Díaz I, Montero A, Pousa F, Zabala P (2017) A cluster-first route-second approach for the swap body vehicle routing problem. Ann Oper Res 253(2):935–956CrossRef

Parragh SN, Cordeau JF (2017) Branch-and-price and adaptive large neighborhood search for the truck and trailer routing problem with time windows. Comput Oper Res 83:28–44CrossRef

Parragh SN, Schmid V (2013) Hybrid column generation and large neighborhood search for the dial-a-ride problem. Comput Oper Res 40(1):490–497CrossRef

Penna PHV, Afsar HM, Prins C, Prodhon C (2016) A hybrid iterative local search algorithm for the electric fleet size and mix vehicle routing problem with time windows and recharging stations. IFAC-PapersOnLine 49(12):955–960CrossRef

Souravlias D, Huber S (2019) Detecting patterns in benchmark instances of the swap-body vehicle routing problem. In: Brunato M, Kotsireas I, Pardalos PM, Battiti R (eds) Learning and intelligent optimization. Springer, Berlin, pp 370–385CrossRef

Subramanian A, Penna PHV, Uchoa E, Ochi LS (2012) A hybrid algorithm for the heterogeneous fleet vehicle routing problem. Eur J Oper Res 221(2):285–295CrossRef

Subramanian A, Uchoa E, Ochi LS (2013) A hybrid algorithm for a class of vehicle routing problems. Comput Oper Res 40(10):2519–2531CrossRef

Talbi EG (ed) (2013) Hybrid metaheuristics. Springer, Berlin

Todosijević R, Hanafi S, Urošević D, Jarboui B, Gendron B (2016) A general variable neighborhood search for the swap-body vehicle routing problem. Comput Oper Res 78:468–479CrossRef

Toffolo TA, Christiaens J, Malderen SV, Wauters T, Vanden Berghe G (2018) Stochastic local search with learning automaton for the swap-body vehicle routing problem. Comput Oper Res 89:68–81CrossRef

Uchoa E, Pecin D, Pessoa A, Poggi M, Vidal T, Subramanian A (2017) New benchmark instances for the capacitated vehicle routing problem. Eur J Oper Res 257(3):845–858CrossRef

Wang Z, Liang W, Hu X (2014) A metaheuristic based on a pool of routes for the vehicle routing problem with multiple trips and time windows. J Oper Res Soc 65(1):37–48CrossRef

Yıldırım UM, Çatay B (2014) A parallel matheuristic for solving the vehicle routing problems. In: de Sousa JF (ed) Computer-based modelling and optimization in transportation. Springer, Cham, pp 477–489CrossRef

Title: A matheuristic for the swap body vehicle routing problem
Authors: Sandra Huber
Jean-François Cordeau
Martin Josef Geiger
Publication date: 27-12-2019
Publisher: Springer Berlin Heidelberg
Published in: OR Spectrum / Issue 1/2020
Print ISSN: 0171-6468
Electronic ISSN: 1436-6304
DOI: https://doi.org/10.1007/s00291-019-00570-z

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft"

Springer Professional "Wirtschaft+Technik"

Other articles of this Issue 1/2020

Enhancing Benders decomposition algorithm to solve a combat logistics problem

Acknowledgement to Reviewers

Mathematical models to improve the current practice in a Home Healthcare Unit

A multi-cover routing problem for planning rapid needs assessment under different information-sharing settings

A column generation-based decomposition and aggregation approach for combining orders in inland transportation of containers

A new matheuristic approach for the multi-depot vehicle routing problem with inter-depot routes