Vehicle Routing with Traffic Congestion and

For the intensively studied vehicle routing problem (VRP), two real-life restrictions have received only minor attention in the VRP-literature: traffic congestion and driving hours regulations. Traffic congestion causes late arrivals at customers and long travel times re-sulting in large transport costs. To account for traffic congestion, time-dependent travel times should be considered when constructing vehicle routes. Next, driving hours regulations, which restrict the available driving and working times for truck drivers, must be respected. Since violations are severely fined, also driving hours regulations should be considered when constructing vehicle routes, even more in combina-tion with congestion problems. The objective of this paper is to de-velop a solution method for the VRP with time windows (VRPTW), time-dependent travel times, and driving hours regulations. The ma-jor difficulty of this VRPTW extension is to optimize each vehicle’s departure times to minimize the duty time of each driver. Having compact duty times leads to cost savings. However, obtaining com-pact duty times is much harder when time-dependent travel times and driving hours regulations are considered. We propose a restricted dynamic programming (DP) heuristic for constructing the vehicles routes, and an efficient heuristic for optimizing the vehicle’s depar-ture times for each (partial) vehicle route, such that the complete so-lution algorithm runs in polynomial time. Computational experiment