A Self-Bounding Branch \& Bound procedure for truck routing and scheduling

Csongor Gy. Csehi, Ádám Tóth, Márk Farkas


In this paper we study a part of a core algorithm of a complex software solution for truck itinerary construction for one of the largest public road transportation companies in the EU.
The problem is to construct a cost optimal itinerary, given an initial location with an asset state, the location and other properties of tasks to be performed. Such an itinerary specifies the location and activity of the truck and the driver until the completition of the last routing task.
The calculation of possible itineraries is a branch and bound algorithm. The nodes of the search tree have the following arguments: position, time, driver-state and truck-state. For each node we calculate the cumulative cost for the road reaching that state, and a heuristic lower bound for the cost of the remaining road. In each step the procedure expands the next unexpanded node with the best sum for cumulative and heuristical costs.\\
It is hard to give a sharp lower bound if the model contains time windows. To make a sharp heuristic we run the same branch and bound algorithm (from each node) but with simplified data (hypothetical positions and simplified activities: no refuelling, no road costs, etc.).
We have reached significant gains in performance and quality compared to the previous approach.

Full Text:




M. W. Carter, C. C. Price (2000) {it Operations research: a practical introduction}, Crc Press.


C. S. Chung, J. Flynn, "{O}. Kirca, (2006) A branch and bound algorithm to minimize the total tardiness for m-machine permutation flowshop problems. {it European Journal of Operational Research}, 174(1), 1--10.


R. Companys, M. Mateo (2007) Different behaviour of a double branch-and-bound algorithm on Fm| prmu| Cmax and Fm| block| Cmax problems. {it Computers & Operations Research}, 34(4), 938--953.


Cs. Gy. Csehi, M. Farkas (2016) Truck routing and scheduling, Central {it European Journal of Operations Research}, 1--17. doi: 10.1007/s10100-016-0453-8


Y. Cui, Y. Yang, X. Cheng, P. Song (2008) A recursive branch-and-bound algorithm for the rectangular guillotine strip packing problem. {it Computers & Operations Research}, 35(4), 1281--1291.


R. W. Floyd (1962) Algorithm 97: Shortest path, {it Communications of the ACM} 5(6):345


A. Hartwig (1985) Recursive branch and bound. {it Optimization}, 16(2), 219--228.


A. Hartwig, F. Daske, S. Kobe (1984) A recursive branch-and-bound algorithm for the exact ground state of Ising spin-glass models. {it Computer Physics Communications}, 32(2), 133--138.


R. Matsuzaki, A. Todoroki (2007) Stacking-sequence optimization using fractal branch-and-bound method for unsymmetrical laminates. {it Composite Structures}, 78(4), 537--550.


M. Vanhoucke (2002) Optimal due date assignment in project scheduling. {it Vlerick Management School.}


M. Vanhoucke (2006) Scheduling an R&D project with quality-dependent time slots. {it International Conference on Computational Science and Its Applications} (pp. 621--630). Springer Berlin Heidelberg.


S. Warshall (1962) A theorem on Boolean matrices, {it Journal of the ACM} 9(1):11--12

DOI: https://doi.org/10.31449/inf.v43i1.2681

Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.