Vehicle routing under time-dependent travel times: The impact of congestion avoidance

摘要

Daily traffic congestion forms a major problem for businesses such as logistic service providers and distribution firms. It causes late arrivals at customers and additional costs for hiring the truck drivers. Such costs caused by traffic congestion can be reduced by taking into account and avoiding predictable traffic congestion within vehicle route plans. In the literature, various strategies are proposed to avoid traffic congestion, such as selecting alternative routes, changing the customer visit sequences, and changing the vehicle-customer assignments. We investigate the impact of these and other strategies in off-line vehicle routing on the performance of vehicle route plans in reality. For this purpose, we develop a set of vehicle routing problem instances on real road networks, and a speed model that reflects the key elements of peak hour traffic congestion. The instances are solved for different levels of congestion avoidance using a modified Dijkstra algorithm and a restricted dynamic programming heuristic. Computational experiments show that 99% of late arrivals at customers can be eliminated if traffic congestion is accounted for off-line. On top of that, about 87% of the extra duty time caused by traffic congestion can be eliminated by clever congestion avoidance strategies.