Séminaire 'Un chercheur du GERAD vous parle!'

Titre : Branch-price-and-cut for vehicle routing

Conférencier : Guy Desaulniers – Directeur, GERAD, Canada

Branch-price-and-cut (BPC) is the leading methodology for solving many vehicle routing problems exactly such as the capacitated vehicle routing problem (CVRP), the vehicle routing problem with time windows (VRPTW), 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 seminar, we begin by briefly describing certain vehicle routing problem variants. We then present the basics of a BPC algorithm. Finally, we review some of the main ingredients that are part of the most recent BPC algorithms: ng-route pricing, route enumeration, and non-robust cuts. Finally, to illustrate the effectiveness of some BPC algorithms, we report recent computational results obtained for the CVRP and the VRPTW.

---

Du café et des biscuits seront offerts au début du séminaire.
Bienvenue à tous!