Performances improvement of the column generation algorithm: application to vehicle routing problems

作者：Moungla Nora Touati^*

来源：4OR-A Quarterly Journal of Operations Research, 2010, 8(2): 217-220.

DOI：10.1007/s10288-010-0117-9

• Column generation
• Diversification
• Reoptimization
• Dantzig-Wolfe decomposition
• Lagrangian decomposition
• Dynamic programming
• Vehicle routing problem with time windows

We survey the main results obtained by the author in his PhD dissertation supervised by Anass Nagih and Lucas L,tocart. It was defended in December 2008 at The Computer Science lab of the Paris-Nord University (L.I.P.N.), Villetaneuse, France. The thesis is written in French and is available from http://www-lipn.univ-paris13.fr/similar to touati/TM_Thesis.pdf . Column generation algorithms are instrumental in many areas of applied optimization, where linear programs with an enormous number of variables need to be solved. Although successfully used in many applications, this method suffers from well-known "instability" issues that somewhat limit its efficiency. This work focuses on accelerating strategies in a column generation scheme; on the first iterations using diversification, on the last iterations using reoptimization and on the overall GC scheme using an improving technique to solve the pricing problems (dynamic programming with blocs). The effectiveness of these approaches is validated on the Vehicle Routing Problem with Time Windows.

• 出版日期2010-6