Scientific Program > Plenary Talks

GuyDesaulniers

 Prof. Guy Desaulniers

Director, GERAD

Full Professor, Polytechnique Montreal

Department of Mathematics and Industrial Engineering

Title: "Branch-price-and-cut for Vehicle Routing: Recent Advances"

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.

* * * * *

david_1.jpg

Prof. David Pisinger

Full Professor, Technical University of Denmark

Department of Management Engineering

Title: "Network Design in Liner Shipping"

Online user: 1