A set-covering based heuristic algorithm for the periodic vehicle routing problem

Cacchiani, Valentina and Hemmelmayr, Vera and Tricoire, Fabien (2014) A set-covering based heuristic algorithm for the periodic vehicle routing problem. Discrete Applied Mathematics, 163 (1). pp. 53-64. ISSN 0166-218X

Available under License Creative Commons Attribution Non-commercial No Derivatives 3.0 Austria (CC BY-NC-ND 3.0 AT).

Download (294kB)


We present a hybrid optimization algorithm for mixed-integer linear programming, embedding both heuristic and exact components. In order to validate it we use the periodic vehicle routing problem (PVRP) as a case study. This problem consists of determining a set of minimum cost routes for each day of a given planning horizon, with the constraints that each customer must be visited a required number of times (chosen among a set of valid day combinations), must receive every time the required quantity of product, and that the number of routes per day (each respecting the capacity of the vehicle) does not exceed the total number of available vehicles. This is a generalization of the well-known vehicle routing problem (VRP). Our algorithm is based on the linear programming (LP) relaxation of a set-covering-like integer linear programming formulation of the problem, with additional constraints. The LP-relaxation is solved by column generation, where columns are generated heuristically by an iterated local search algorithm. The whole solution method takes advantage of the LP-solution and applies techniques of fixing and releasing of the columns as a local search, making use of a tabu list to avoid cycling. We show the results of the proposed algorithm on benchmark instances from the literature and compare them to the state-of-the-art algorithms, showing the effectiveness of our approach in producing good quality solutions. In addition, we report the results on realistic instances of the PVRP introduced in Pacheco et al. (2011) [24] and on benchmark instances of the periodic traveling salesman problem (PTSP), showing the efficacy of the proposed algorithm on these as well. Finally, we report the new best known solutions found for all the tested problems. (authors' abstract)

Item Type: Article
Additional Information: Financial support from the Austrian Science Fund (FWF), by grant #P20342, as well as from the Austrian Research Promotion Agency (FFG), by grant #822739, is gratefully acknowledged. The authors would also like to thank Karl F. Doerner and Paolo Toth for their valuable comments and the support of the project. We are grateful to the two anonymous referees for their helpful comments. Open Access funded by Austrian Science Fund (FWF).
Keywords: periodic vehicle routing / matheuristics / column generation
Divisions: Departments > Welthandel > Transportwirtschaft und Logistik
Version of the Document: Published
Variance from Published Version: None
Depositing User: ePub Administrator
Date Deposited: 17 Apr 2013 09:33
Last Modified: 10 Aug 2016 00:15
Related URLs:
FIDES Link: https://bach.wu.ac.at/d/research/results/59393/
URI: https://epub.wu.ac.at/id/eprint/3858


View Item View Item


Downloads per month over past year

View more statistics