[Zurück]

M. Ruthmair, G. Raidl:
"An Adaptive Layers Framework for Vehicle Routing Problems";
Vortrag: International Symposium on Mathematical Programming, Berlin, Deutschland; 19.08.2012 - 24.08.2012.

Current exact solution methods for vehicle routing problems are
mostly based on set partitioning formulations enhanced by strong valid
inequalities. We present a different approach where resources, e.g., capacities
or times, are modeled on a layered graph in which the original
graph is duplicated for each achievable resource value. MIP models on
this layered graph typically yield tight LP bounds. However, as the size of
this graph strongly depends on the resource bounds, such models may
be huge and impracticable. We propose a framework for approximating
the LP bound of such a resource-indexed formulation by a sequence of
much smaller models. Based on a strongly reduced node set in the layered
graph we redirect arcs in a way to obtain lower and upper bounds to
the LP value of the complete model. This reduced layered graph is iteratively
extended, decreasing the gap. Moreover, a sequence of improving
primal bounds can be provided. The final model extended by inequalities
to ensure feasibility is solved by branch-and-cut. Obtained results,
e.g., for the vehicle routing problem with time windows, look promising
although we currently cannot compete with state-of-the-art methods