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.
Similar content being viewed by others
References
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–246
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–177
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–166
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–221
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–190
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–126
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–445
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–539
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–566
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–956
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–44
Parragh SN, Schmid V (2013) Hybrid column generation and large neighborhood search for the dial-a-ride problem. Comput Oper Res 40(1):490–497
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–960
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–385
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–295
Subramanian A, Uchoa E, Ochi LS (2013) A hybrid algorithm for a class of vehicle routing problems. Comput Oper Res 40(10):2519–2531
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–479
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–81
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–858
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–48
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–489
Author information
Authors and Affiliations
Corresponding author
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Rights and permissions
About this article
Cite this article
Huber, S., Cordeau, JF. & Geiger, M.J. A matheuristic for the swap body vehicle routing problem. OR Spectrum 42, 111–160 (2020). https://doi.org/10.1007/s00291-019-00570-z
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00291-019-00570-z