Branch-Price-and-Cut Accelerated with a Pricing for Integrality Heuristic for the Electrical Vehicle Routing Problem with Time Windows and Charging Time Slots
Lukas Eveborn, Elina Rönnberg · 2026
Read Branch-Price-and-Cut Accelerated with a Pricing for Integrality Heuristic for the Electrical Vehicle Routing Problem with Time Windows and Charging Time Slots by Lukas Eveborn, Elina Rönnberg (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2602-08673.txt.
Description
Branch-price-and-cut solves vehicle routing exactly, but its column generation follows linear-relaxation signals that may mislead integer solutions. Lukas Eveborn and Elina Rönnberg propose a primal heuristic based on pricing for integrality to find good integer solutions earlier. Their arXiv paper targets electric vehicle routing with time windows and charging slots.
The heuristic builds a partial integer solution from the column pool, then iteratively searches for columns that complement it, guided by modified pricing, dual information, and previously generated columns. Tests show it closes thirty to forty percent of the root-node gap on average versus a restricted-master heuristic. Readers get a practical accelerator for exact routing solvers.
Catalog record
| CREATOR | Lukas Eveborn, Elina Rönnberg |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 98 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2602-08673