Quotation Cacchiani, Valentina, Hemmelmayr, Vera, Tricoire, Fabien. 2014. A Set-Covering based Heuristic Algorithm for the Periodic Vehicle Routing Problem. Discrete Applied Mathematics 163, 53-64.


RIS


BibTeX

Abstract

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.

Tags

Press 'enter' for creating the tag

Publication's profile

Status of publication Published
Affiliation WU
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 Algorithm for the Periodic Vehicle Routing Problem
Volume 163
Year 2014
Page from 53
Page to 64
Reviewed? Y
URL http://www.sciencedirect.com/science/article/pii/S0166218X12003320
DOI http://dx.doi.org/10.1016/j.dam.2012.08.032

Associations

People
Hemmelmayr, Vera (Details)
External
Cacchiani, Valentina
Tricoire, Fabien
Organization
Institute for Transport and Logistics Management (Details)
Google Scholar: Search