Improving vehicle routing and scheduling with learned column prefilling
Imperfect Is Perfect: Learned Column Prefilling for Branch-Price-and-Cut
Machine Learning
Summary
When solving complex routing and scheduling problems, computers often generate and test many possible routes to find the best solution. This paper shows that starting with a good set of initial routes, even if they are not perfect, can actually speed up the process. The authors use neural networks to quickly generate useful starting routes and guide the solver, making it much faster than traditional methods. Their approach works well on challenging problems like routing hundreds of customers and scheduling tasks on multiple machines.
What this means in practice
- •For logistics planners: Speed up exact route planning for large vehicle fleets using learned columns that improve solver initialization.
- •For manufacturing schedulers: Reduce computation time in exact scheduling of unrelated parallel machines by preloading routes generated via neural network guidance.
Authors
Haoran Liu, Yu Yang
Abstract
Column generation folklore warns that initial columns hurt: a warm start may bias the dual and slow the root of branch-price-and-cut. We show the opposite once the columns are imperfect in the right way. Preloading the support of the optimal root LP, the best columns one could know in advance, fails to finish on half of our hardest instances; a pool of ordinary routes that need not belong to any optimal solution, held outside the master and priced at the current smoothed dual, speeds the root up. Because the columns need not be optimal, producing them becomes a learning task: a neural edge scorer guides a constructive generator that builds the pool in seconds. A second network predicts the initial center of Wentges smoothing from the instance file, and with it the direction of the smoothed pricing queries; the solver's own updates run unchanged. With prefill and center in place, exact pricing dominates root pricing time, so we rebuild bucket-graph labeling around its dominance test for the GPU and certify on the CPU. Inside RouteOpt, the state-of-the-art exact solver for capacitated vehicle routing, the pipeline reaches the same certified root bound in 13.2% of vanilla RouteOpt's root pricing time over 95 instances with 300 to 1000 customers, prefill alone in 26.1%, and 17.5 times faster in the best case. In an exact branch-price-and-cut solver for unrelated parallel machine scheduling, prefill with smoothing and the learned center certifies all 25 benchmark instances, 12 times faster than the solver's own column generation, which certifies 20 of them.