A learned route archive speeds exact vehicle routing

Can an exact routing solver spend less time finding useful routes and still prove that no improving route remains? The paper tests changes to the initial search and exact pricing, measuring whether they shorten root column generation while preserving its certified bound.

The method supplies learned routes on demand, starts pricing from a learned dual center, and uses GPU exact pricing with CPU certification to reach the same root bound faster.

In 95 capacitated vehicle-routing instances, the full pipeline reached the same certified root bound using 13.2% of vanilla RouteOpt’s root-pricing time. The figure is an instance-equal geometric mean of time ratios; it measures the initial root stage, before cuts and branching.

The component comparison helps explain the result: learned prefill alone used 26.1% of vanilla’s root time on average, while GPU pricing alone used 88.4%. The full combination’s faster certified root search supports the method’s value within this tested stage and panel.

The experiments measure only root pricing, before later cuts and branching. They do not establish whether the method reduces total solution time for the full branch-price-and-cut tree.