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

Sandra Ulrich Ngueveu (1) , Christian Prins (1) , Roberto Wolfler Calvo (1)

1 LOSI - Laboratoire d'Optimisation des Systèmes Industriels

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.

Domaines: Recherche opérationnelle [math.OC]

Sandra Ulrich Ngueveu, Christian Prins, Roberto Wolfler Calvo. A Hybrid Tabu Search for the m-Peripatetic Vehicle Routing Problem. Matheuristics 2008, Jun 2008, Bertinoro, Italy. pp.253-266, ⟨10.1007/978-1-4419-1306-7_11⟩. ⟨hal-02895064⟩