Skip to Main content Skip to Navigation
Conference papers

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

Abstract : 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.
Document type :
Conference papers
Complete list of metadatas
Contributor : Jean-Baptiste Vu Van <>
Submitted on : Thursday, July 9, 2020 - 2:25:36 PM
Last modification on : Friday, July 10, 2020 - 3:36:14 AM





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⟩



Record views