An iterated local search algorithm for the vehicle routing problem with backhauls

Daniel Palhazi Cuervo, Peter Goos (), Kenneth Sörensen and Emely Arráiz

Working Papers from University of Antwerp, Faculty of Business and Economics

Abstract: The Vehicle Routing Problem with Backhauls (VRPB) is an extension of the VRP that deals with two types of customers: the consumers (linehaul) that request goods from the depot and the suppliers (backhaul) that send goods to the depot. In this paper, we propose a simple yet effective iterated local search algorithm for the VRPB. Its main component is an oscillating local search heuristic that has two main features. First, it explores a wide neighborhood structure at each iteration. This is efficiently done using an additional data structure that stores information about the set of neighboring solutions. Second, the heuristic performs constant transitions between feasible and infeasible regions of the solution space. These transitions are regulated by a dynamic adjustment of the penalty applied to infeasible solutions. An extensive statistical analysis was carried out in order to identify the most important components of the algorithm and to properly tune the values of their parameters. The results of the computational experiments carried out show that this algorithm is very competitive in comparison to the best metaheuristic algorithms for the VRPB. Additionally, new best solutions have been found for two instances in one of the benchmark sets. Through these results, the paper shows that by expanding the exploration area and improving the efficiency of the local search heuristic, it is possible to develop simpler and faster metaheuristic algorithms without compromising the quality of the solutions obtained.

Pages: 21 pages
Date: 2013-06
New Economics Papers: this item is included in nep-cmp
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
https://repository.uantwerpen.be/docman/irua/731304/09ef1d8e.pdf (application/pdf)

Related works:
Journal Article: An iterated local search algorithm for the vehicle routing problem with backhauls (2014)
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:ant:wpaper:2013010

Access Statistics for this paper

More papers in Working Papers from University of Antwerp, Faculty of Business and Economics Contact information at EDIRC.
Bibliographic data for series maintained by Joeri Nys ().