More efficient deliveries thanks to integrated route and loading optimization

Vehicle routing plays a central role in many industries, especially when transportation needs to be efficient and space-saving. A particular challenge is to integrate the three-dimensional loading of each vehicle directly into the route planning process.

In the new publication entitled "A branch-and-cut algorithm for vehicle routing problems with three-dimensional loading constraints", the team consisting of Felix Tamke, Florian Linß, Leopold Kuttner, and Udo Buscher addresses this problem. They developed an exact solution method that considers both route optimization and the three-dimensional loading of the vehicles.

The method is based on a branch-and-cut approach using so-called "infeasible path elimination" techniques. This automatically excludes routes for which there is no permissible load. The loading of the vehicles is checked precisely using a flexible constraint programming model, while a special packing heuristics approach significantly reduces the number of time-consuming calculations.

Additionally, the process generates initial solutions and regularly combines them to create new, improved ones. Extensive calculation studies on known benchmark instances have shown significant improvements in performance: 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.

Felix Tamke, Florian Linß, Leopold Kuttner, Udo Buscher, European Journal of Operational Research
https://doi.org/10.1016/j.ejor.2025.10.010