10-12 Jul 2017 Amsterdam (Netherlands)
Prof. Guy Desaulniers
Full Professor, Polytechnique Montreal
Department of Mathematics and Industrial Engineering
Branch-price-and-cut (BPC) is the leading methodology for solving many vehicle routing problems exactly such as the capacitated vehicle routing problem, the vehicle routing problem with time windows, and the split delivery vehicle routing problem with time windows, to name just a few. It consists of a column generation algorithm embedded in a branch-and-cut framework and involves, thus, several algorithmic components that often need to be specialized for the problem considered. In this talk, we review the main ingredients that are part of the most recent BPC algorithms. Among others, we discuss the ng-route pricing algorithm, the route enumeration procedure, and the non-robust cuts that are defined directly on the master problem variables. We highlight certain tradeoffs that need to be addressed when designing a BPC algorithm. Also, to illustrate the effectivness of some BPC algorithms, we report recent computational results obtained for different vehicle routing problems. To conclude, we present current challenges that arise from complex vehicle routing problems.
* * * * *
Full Professor, Technical University of Denmark
Department of Management Engineering