A relax-and-repair heuristic for the Swap-Body Vehicle Routing Problem

Nabil Absi, Diego Cattaruzza (), Dominique Feillet and Sylvain Housseman
Additional contact information
Nabil Absi: Ecole des Mines de Saint-Etienne
Diego Cattaruzza: Ecole des Mines de Saint-Etienne
Dominique Feillet: Ecole des Mines de Saint-Etienne
Sylvain Housseman: Ecole des Mines de Saint-Etienne

Annals of Operations Research, 2017, vol. 253, issue 2, No 12, 957-978

Abstract: Abstract In this paper we address the Swap-Body Vehicle Routing Problem (SB-VRP), a variant of the truck and trailer routing problem. It was introduced in the VeRoLog Challenge 2014. We develop a solution approach that we coin Relax-and-Repair. It consists in solving a relaxed version of the SB-VRP and deriving a feasible solution by repairing the relaxed one. We embed this approach within a population-based heuristic. During computation we store all feasible routes in order to derive better solutions by solving a set-partitioning problem. In order to take advantages of nowadays multi-core machines, our algorithm is designed as a collaborative parallel population-based heuristic. Experimental results show that our relax-and-repair algorithm is very competitive and point the impact of each phase on the quality of the obtained solutions. The advantage of our approach is that it can be adapted to solve complex industrial routing problems.

Keywords: Vehicle routing; Swap-body; Genetic algorithm; Relax-and-repair (search for similar items in EconPapers)
Date: 2017
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://link.springer.com/10.1007/s10479-015-2098-8 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:annopr:v:253:y:2017:i:2:d:10.1007_s10479-015-2098-8

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10479

DOI: 10.1007/s10479-015-2098-8

Access Statistics for this article

Annals of Operations Research is currently edited by Endre Boros

More articles in Annals of Operations Research from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().