[Back]

S. Pirkwieser, G. Raidl:
"Matheuristics for the periodic vehicle routing problem with time windows";
Talk: International Workshop on Model-Based Metaheuristics, Wien; 2010-06-28 - 2010-06-30; in: "Proceedings of Matheuristics 2010: Third International Workshop on Model-Based Metaheuristics,", (2010), 83 - 95.

We investigate two matheuristic strategies using the periodic
vehicle routing problem with time windows as a testbed. Two di erent
metaheuristics are suitably combined with parts of a developed column
generation approach: On the one hand a variable neighborhood search
(VNS) acts as the sole provider of columns for a set covering model, hence
realizing a pure metaheuristic column generation. Hereby, the VNS and
the resolving of the model are performed in an intertwined way. On the
other hand the solution to the linear programming (LP) relaxation of the
set covering model, i.e. the columns (routes) and their respective (accumulated)
LP values, found by a classical column generation approach
are successfully exploited in a subsequent evolutionary algorithm. Both
matheuristics often yield signi cantly better results than their pure metaheuristic
counterparts. These approaches are applicable to other classes
of combinatorial optimization problems as well.

http://publik.tuwien.ac.at/files/PubDat_189077.pdf