Lower and upper bounds for the m-peripatetic vehicle routing problem - Université de technologie de Troyes Accéder directement au contenu
Article Dans Une Revue 4OR: A Quarterly Journal of Operations Research Année : 2010

Lower and upper bounds for the m-peripatetic vehicle routing problem

Résumé

The m-Peripatetic Vehicle Routing Problem (m-PVRP) consists in finding a set of routes of minimum total cost over m periods so that two customers are never sequenced consecutively during two different periods. It models for example money transports or cash machines supply, and the aim is to minimize the total cost of the routes chosen. 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). In this paper we discuss some complexity results of the problem before presenting upper and lower bounding procedures. Good results are obtained not only on the m-PVRP in general, but also on the VRP and the m-PSP using classical VRP instances and TSPLIB instances.
Fichier non déposé

Dates et versions

hal-02369851 , version 1 (19-11-2019)

Identifiants

Citer

Sandra Ulrich Ngueveu, Christian Prins, Roberto Wolfler Calvo. Lower and upper bounds for the m-peripatetic vehicle routing problem. 4OR: A Quarterly Journal of Operations Research, 2010, 8 (4), pp.387-406. ⟨10.1007/s10288-010-0148-2⟩. ⟨hal-02369851⟩
40 Consultations
0 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More