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

Abstract

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.