A Hybrid Tabu Search for the m-Peripatetic Vehicle Routing Problem

This chapter presents a hybridization of a perfect

b

-matching within a tabu search framework 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 the 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 on classical VRP instances and TSPLIP instances 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.