Quotation Cacchiani, Valentina, Hemmelmayr, Vera, Tricoire, Fabien. 2014. A set covering based heuristic for the periodic vehicle routing problem. Discrete Applied Mathematics. 163 (1), 53-64.




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.


Press 'enter' for creating the tag

Publication's profile

Status of publication Published
Affiliation External
Type of publication Journal article
Journal Discrete Applied Mathematics
Citation Index SCI
WU Journalrating 2009 A
WU-Journal-Rating new FIN-A, INF-A, STRAT-A, WH-A
Language English
Title A set covering based heuristic for the periodic vehicle routing problem
Volume 163
Number 1
Year 2014
Page from 53
Page to 64
Reviewed? Y
URL https://www.sciencedirect.com/science/article/pii/S0166218X12003320
DOI https://doi.org/10.1016/j.dam.2012.08.032
Open Access Y
Open Access Link https://www.sciencedirect.com/science/article/pii/S0166218X12003320


Hemmelmayr, Vera (Details)
Tricoire, Fabien (Former researcher)
Cacchiani, Valentina (DEIS, University of Bologna, Italy)
Google Scholar: Search