Scientific Program > Talks by Speaker > Feillet Dominique

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.