A branch-and-cut algorithm for vehicle routing problems with three-dimensional loading constraints
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866914689607270400 |
|---|---|
| author | Tamke, Felix Linß, Florian Kuttner, Leopold Buscher, Udo |
| author_facet | Tamke, Felix Linß, Florian Kuttner, Leopold Buscher, Udo |
| contents | This paper presents a new branch-and-cut algorithm based on infeasible path elimination for the three-dimensional loading capacitated vehicle routing problem (3L-CVRP) with different loading problem variants. We show that a previously infeasible route can become feasible by adding a new customer if support constraints are enabled in the loading subproblem and call this the incremental feasibility property. Consequently, different infeasible path definitions apply to different 3L-CVRP variants and we introduce several variant-depending lifting steps to strengthen infeasible path inequalities. The loading subproblem is solved exactly using a flexible constraint programming model to determine the feasibility or infeasibility of a route. An extreme point-based packing heuristic is implemented to reduce time-consuming calls to the exact loading algorithm. Furthermore, we integrate a start solution procedure and periodically combine memoized feasible routes in a set-partitioning-based heuristic to generate new upper bounds. A comprehensive computational study, employing well-known benchmark instances, showcases the significant performance improvements achieved through the algorithmic enhancements. Consequently, we not only prove the optimality of many best-known heuristic solutions for the first time but also introduce new optimal and best solutions for a large number of instances. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2402_14868 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | A branch-and-cut algorithm for vehicle routing problems with three-dimensional loading constraints Tamke, Felix Linß, Florian Kuttner, Leopold Buscher, Udo Optimization and Control 90B06 (Primary) 90C57 (Secondary) This paper presents a new branch-and-cut algorithm based on infeasible path elimination for the three-dimensional loading capacitated vehicle routing problem (3L-CVRP) with different loading problem variants. We show that a previously infeasible route can become feasible by adding a new customer if support constraints are enabled in the loading subproblem and call this the incremental feasibility property. Consequently, different infeasible path definitions apply to different 3L-CVRP variants and we introduce several variant-depending lifting steps to strengthen infeasible path inequalities. The loading subproblem is solved exactly using a flexible constraint programming model to determine the feasibility or infeasibility of a route. An extreme point-based packing heuristic is implemented to reduce time-consuming calls to the exact loading algorithm. Furthermore, we integrate a start solution procedure and periodically combine memoized feasible routes in a set-partitioning-based heuristic to generate new upper bounds. A comprehensive computational study, employing well-known benchmark instances, showcases the significant performance improvements achieved through the algorithmic enhancements. Consequently, we not only prove the optimality of many best-known heuristic solutions for the first time but also introduce new optimal and best solutions for a large number of instances. |
| title | A branch-and-cut algorithm for vehicle routing problems with three-dimensional loading constraints |
| topic | Optimization and Control 90B06 (Primary) 90C57 (Secondary) |
| url | https://arxiv.org/abs/2402.14868 |