Exact solution of vehicle routing problems with multigraphs or road-network-type graphs
Dominique Feillet  1, 2@  , Nabil Absi  3@  , Hamza Ben Ticha  4@  , Alain Quilliot  5, *@  
1 : Laboratoire d'Informatique, de Modélisation et d'optimisation des Systèmes  (LIMOS)  -  Website
CNRS : UMR6158
F-13541 Gardanne -  France
2 : École des Mines de Saint-Étienne  (EMSE)  -  Website
Ecole des Mines de Saint-Etienne
3 : Ecole des Mines de Saint-Etienne - CMP  (CMP -EMSE)
EMSE
880 avenue de Mimet, F-13541 Gardanne -  France
4 : Mines Saint-Etienne and LIMOS
Ecole Nationale Supérieure des Mines de Saint-Etienne
5 : Laboratoire d'Informatique, de Modélisation et d'optimisation des Systèmes  (LIMOS)  -  Website
CNRS : UMR6158, Université Clermont Auvergne
Bât ISIMA Campus des Cézeaux BP 10025 63173 AUBIERE cedex -  France
* : Corresponding author

In this presentation, we investigate the exact solution of vehicle routing problems when a route is characterized by several attributes, e.g., travel cost and travel time as in the VRPTW (Vehicle Routing Problem with Time windows). Recent works confirmed that the best solutions are missed using the standard modeling, where the road network is represented with a complete graph. Indeed, in this case, an arc (i,j) represents a specific path between i and j and all alternative paths, with different compromises betwwen the attributes are lost.

We explore two different representations of the road network that avoid restricting abusively the solution space: a representation as a multigraph and a representation reproducing the road network. For both cases, we develop branch-and-price algorithms. Experiments compare computationnally the two approaches.


Online user: 1 RSS Feed