A hybrid tabu search for the m-peripatetic vehicle routing problem

Sandra Ulrich NGUEVEU Christian PRINS Roberto WOLFLER-CALVO

Institut Charles Delaunay - LOSI
Universite de Technologie de Troyes (UTT)
12 rue Marie Curie - 10010 Troyes - FRANCE
ngueveus@utt.fr, christian.prins@utt.fr, roberto.wolfler calvo@utt.fr

29th April 2008

Abstract
This article presents a hybridization of a perfect b-matching within a tabu search frame-
work for the m-Peripatetic Vehicle Routing Problem (m-PVRP). The m-PVRP models
for example money transports and cash machines supply where, for security reasons, no
path can be used more than once during m periods and the amount of money allowed
per vehicle is limited. It consists in finding a set of routes of minimum total cost over
m periods from an undirected graph such that each customer is visited exactly once per
period and each edge can be used at most once during the m periods. Each route starts
and finishes at the depot with a total demand not greater than vehicle capacity. The
aim is to minimize the total cost of the routes. The m-PVRP can be considered as a
generalization of two well-known NP-hard problems: the vehicle routing problem (VRP
or 1-PVRP) and the m-Peripatetic Salesman Problem (m-PSP). Computational results
show that the hybrid algorithm obtained improves the tabu search, not only on the m-
PVRP in general, but also on the VRP and the m-PSP using classical VRP instances and
TSPLIP instances.