We study extensions of the shortest-path problem in road networks: given a road network, a start and a destination location, determine the best path to drive from start to destination.
For truck drivers several additional constraints apply. For example, it is sometimes necessary or beneficial to stop and wait somewhere on the way from start to destination. Reasons for such a waiting stop include time-dependent driving bans and regulations on drivers' working hours. In reality, it is not possible to just wait anywhere in the road network and hence must be planned only where a parking area is available.
Further extensions for more realistic solutions are time-dependent driving times and the consideration of a sequence of planned stops at customers. The latter extension constitutes the main use-case our research is targeted on: typically when solving a VRP not all path constraints can be taken into account, but for tour execution a path that is as realistic as possible is desired.
We focus on allowing waiting only at designated parking areas and at customers. In the main approach that we present, time-dependent driving bans are considered, and we optimize two criteria, the arrival time and the driving time. Since waiting is not allowed everywhere the problem is NP-hard. Our heuristic approach returns multiple Pareto-optimal solutions. The algorithms are evaluated using real-world data.
Another approach combines designated parking areas and the regulations on drivers' working hours. It can deal also with planned intermediate stops at customers and time-dependent driving times.
| Subject : | : | Abstracts |
| Topics | : | Shortest Path Problems |
| Topics | : | Social Problems and other related Routing Problems |
| Keywords | : | Time Dependent Shortest Path Problem ; Drivers' Working Hours |
| PDF version | : |  PDF version |
