Enforcing TSP-Optimality in Fair Vehicle Routing by Cutting Planes
Fuente:
arXiv
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2026
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866910167153508352 |
|---|---|
| author | van Rossum, Bart Chen, Rui Lodi, Andrea |
| author_facet | van Rossum, Bart Chen, Rui Lodi, Andrea |
| contents | We study the fair capacitated vehicle routing problem, in which a fleet of vehicles must serve a set of customers such that the difference between the longest and shortest route, the range, is minimized. A key challenge is that the range objective is non-monotonic: it can be reduced by artificially lengthening routes, leading to solutions that violate TSP-optimality of individual routes. Existing exact methods struggle to handle this efficiently. We propose a branch-price-and-cut framework that enforces TSP-optimality through TSP-optimality cuts, which forbid TSP-dominated arc sequences. We strengthen the cuts through a dedicated lifting procedure. Computational experiments on benchmark instances with up to 25 customers show the method solves nearly all instances to optimality, achieving an average gap of 0.27% on the hardest configurations. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2604_23748 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Enforcing TSP-Optimality in Fair Vehicle Routing by Cutting Planes van Rossum, Bart Chen, Rui Lodi, Andrea Optimization and Control We study the fair capacitated vehicle routing problem, in which a fleet of vehicles must serve a set of customers such that the difference between the longest and shortest route, the range, is minimized. A key challenge is that the range objective is non-monotonic: it can be reduced by artificially lengthening routes, leading to solutions that violate TSP-optimality of individual routes. Existing exact methods struggle to handle this efficiently. We propose a branch-price-and-cut framework that enforces TSP-optimality through TSP-optimality cuts, which forbid TSP-dominated arc sequences. We strengthen the cuts through a dedicated lifting procedure. Computational experiments on benchmark instances with up to 25 customers show the method solves nearly all instances to optimality, achieving an average gap of 0.27% on the hardest configurations. |
| title | Enforcing TSP-Optimality in Fair Vehicle Routing by Cutting Planes |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/2604.23748 |