Dynamic Programming for Set Partitioning Problems in Vehicle Routing

The best exact algorithms for several variants of vehicle routing problems are based on Branch-Cut-and-Price. In many cases, it is possible to enumerate all routes whose reduced cost is smaller than the optimality gap, after which the optimal solution can be obtained by solving a set partitioning problem (SPP). In this work, we propose dynamic programming algorithms aimed at the efficient solution of such large-scale SPPs. The methodology exploits the particular structure of the route sets generated in vehicle routing problems, making it possible to solve instances that are much larger than those tractable by MIP solvers. Computational results demonstrate the potential of the proposed approach as a component of advanced exact algorithms for vehicle routing.