[Zurück]

S. Pirkwieser, G. Raidl:
"A column generation approach for the periodic vehicle routing problem with time windows";
Vortrag: International Network Optimization Conference (INOC), Pisa; 26.04.2009 - 29.04.2009; in: "Proceedings of the International Network Optimization Conference 2009", (2009), 6 S.

We present a column generation approach for obtaining strong lower bounds to the periodic vehicle
routing problem with time windows (PVRPTW) where customers must be served several times
during a planning period. For this a set-covering model is introduced whose linear programming relaxation
is solved. The pricing subproblem, responsible for generating new columns, is an elementary
shortest path problem with resource constraints. The latter is solved by a label correcting dynamic
programming algorithm for which we introduce appropriate label resources, extension functions, and
dominance rules. Different settings for this algorithm are suggested and applied in combination to
tune its behavior. We further propose a greedy randomized adaptive search procedure (GRASP) to
solve the pricing subproblem. Experimental results on test instances differing in size, time windows
and period length indicate strong lower bounds for many instances and the advantage of applying the
metaheuristic in combination with the dynamic programming algorithm to save computation time on
larger instances.

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