Titly: Improved exact algorithms for the vehicle routing problem

Speaker: Diego Galindo Pecin, Polytechnique Montréal

Abstract

The best performing exact algorithms for the Capacitated Vehicle Routing Problem (CVRP) developed in the last 10 years are based on the combination of cut and column generation. Some authors only used cuts expressed over the variables of the original formulation, in order to keep the pricing subproblem relatively easy. Other authors could reduce the duality gaps by also using a restricted number of cuts over the Master LP variables, stopping when the pricing becomes prohibitively hard. A particularly effective family of such cuts are the Subset Row Cuts (SRCs). This talk introduces a technique for greatly reducing this impact on the pricing of these cuts, thus allowing much more cuts to be added. This new form of SRCs, called limited memory SRCs (lm-SRCs), relies on a parameter ('the memory') that allows a smooth way to balance the strength of the cuts and their impact on the pricing. The newly proposed Branch-Cut-and-Price algorithm also incorporates and combines for the first time (often in an improved way) several elements found in previous works, like ng-routes, route enumeration, variable fixing and strong branching. All the instances used for benchmarking exact algorithms, with up to 199 customers, were solved to optimality, two of them for the first time. Moreover, some larger instances with up to 360 customers, only considered before by heuristic methods, were solved too.