Time-dependent earliest arrival routes with drivers legislation and preferences

Abstract

Freight transporters use software kits to plan the routes for their trucks. Breaks required by the European drivers legislation are nowadays planned as late as possible. However, in some cases it is beneficial to plan these mandatory breaks during waiting time, such as truck driving bans. In this thesis this problem is addressed by computing earliest arrival routes with optimal break planning. The problem is formulated and optimally solved as a variation of Dijkstra's algorithm. The slow Dijkstra computation times of several seconds per route are improved using time-dependent contraction hierachies, which enable a query time of several milliseconds per route while the solution quality remains good. For two days of driving with a night rest in between, 17% of the analysed routes improves with optimal break scheduling, resulting in an average improvement of 5 hours of driving time.

If the taking of breaks is additionally restricted to parking lots, the influence on the arrival time is on average increased with only 3 minutes. However, 5% of the considered routes are not feasible any more due to absence of truck parking lots along the planned route. Another 15% of the routes face large changes in roads that should be taken.

The planned routes are all optimized for having the earliest arrival time. However, the freight company's objective also concerns fuel optimized driving or providing reliable arrival times to the customer. This thesis analyses such preferences and combines them into a route planner that incorporates results of stated and revealed choice experiments. It is shown that generally toll avoidance and congestion avoidance have most influence on the route choice and arrival time. On average differences are small, but for some routes this leads to changes of up to 15% in travel time.

This thesis analyses the problem of route planning from two perspectives: algorithmic and behavioural. Several observations are made: algorithms are not suitable for obtaining the best route instead of the fastest, and the output of behavioural research cannot be used directly in practice to compute preferred routes. Effort could be made in future to integrate both research communities such that algorithms are able to reflect what a freight transporter actually wants.