2725. A branch-and-cut algorithm for vehicle routing problems with three-dimensional loading constraints
Invited abstract in session MD-58: Branch-and-Cut, stream Vehicle Routing and Logistics.
Monday, 14:30-16:00Room: Liberty 1.13
Authors (first author is the speaker)
| 1. | Udo Buscher
|
| Industrial Management, TU Dresden | |
| 2. | Felix Tamke
|
| TU Dresden | |
| 3. | Florian Linß
|
| Chair of Business Management, especially Industrial Management, TU Dresden | |
| 4. | Leopold Kuttner
|
| Chair of Industrial Management |
Abstract
This study 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. A key observation is that a previously infeasible route may become feasible when adding a new customer if previously violated support constraints in the loading subproblem can now be satisfied. We refer to this as the incremental feasibility property. Consequently, infeasible path definitions vary across different 3L-CVRP variants, and we introduce variant-specific lifting steps to strengthen infeasible path inequalities. To determine route feasibility, we employ a flexible constraint programming model that solves the loading subproblem exactly. An extreme point-based packing heuristic reduces time-consuming calls to the exact loading algorithm. Furthermore, we introduce a start solution procedure and periodically combine memorized feasible routes using a set-partitioning-based heuristic to generate improved upper bounds. A comprehensive computational study on well-known benchmark instances demonstrates the substantial performance improvements achieved through these algorithmic enhancements. As a result, we prove the optimality of numerous best-known heuristic solutions for the first time and establish new optimal and best-known solutions for many instances.
Keywords
- Vehicle Routing
- Branch and Cut
- Logistics
Status: accepted
Back to the list of papers