A new exact algorithm for the multi-depot vehicle routing problem under capacity and route length constraints

Contardo, Claudio (2012). A new exact algorithm for the multi-depot vehicle routing problem under capacity and route length constraints. Université du Québec à Montréal, Montréal, Québec, Canada, 25 p.

Fichier(s) associé(s) à ce document :
[img]
Prévisualisation
PDF
Télécharger (220kB)

Résumé

This article presents an exact algorithm for the multi-depot vehicle routing problem (MDVRP) under capacity and route length constraints. The MDVRP is formulated using a vehicle-flow and a set-partitioning formulation, both of which are exploited at different stages of the algorithm. The lower bound computed with the vehicle-flow formulation is used to eliminate non-promising edges, thus reducing the complexity of the pricing subproblem used to solve the set-partitioning formulation. Several classes of valid inequalities are added to strengthen both formulations, including a new family of valid inequalities used to forbid cycles of an arbitrary length. To validate our approach, we also consider the capacitated vehicle routing problem (CVRP) as a particular case of the MDVRP, and conduct extensive computational experiments on several instances from the literature to show its effectiveness. The computational results show that the proposed algorithm is competitive against stateof-the-art methods for these two classes of vehicle routing problems, and is able to solve to optimality some previously open instances. Moreover, for the instances that cannot be solved by the proposed algorithm, the final lower bounds prove stronger than those obtained by earlier methods.

Type: Rapport de recherche
Mots-clés ou Sujets: multi-depot vehicle routing problem, capacitated vehicle routing problem, column generation, exact algorithm
Unité d'appartenance: École des sciences de la gestion > Département de management et technologie
Déposé par: Claudio Contardo Vera
Date de dépôt: 11 déc. 2012 13:26
Dernière modification: 01 nov. 2014 02:23
Adresse URL : http://www.archipel.uqam.ca/id/eprint/5078

Statistiques

Voir les statistiques sur cinq ans...