The paper:
Time-Dependent Vehicle Routing Problem with Path Flexibility
which is joint work with Yixiao Zhang, Lei Zhao, and Jean-Philippe Gross is accepted in Transportation Research part B Methodological.
This paper explicitly considers path selection in the road network as an integrated decision in the time-dependent vehicle routing problem, denoted as path flexibility (PF). This means that any arc between two customer nodes has multiple corresponding paths in the road network (geographical graph). Hence, the decisions to make are involving not only the routing decision but also the path selection decision depending upon the departure time at the customers and the congestion levels in the relevant road network.
Consider the example in the above figure, there are two typical path options, one via the 4th Ring Road (the lower path) and the other off the ring road (the upper path). Between these two paths, the faster path depends on the actual departure time and on the (spread of the) traffic congestion in the road network. Note that the congestion in the road network is also region-dependent. Consider the example in Figure 2, where the colors of the roads represent the traffic conditions (green for free flow, yellow for medium congestion, and red for heavy congestion). Observe that the traffic conditions of the ring roads change significantly between peak and off-peak hours, while those of the roads within the 2nd ring remain almost unchanged. Jointly considering routing and path selection decisions makes it possible to explicitly consider the temporal and spatial differences of congestion in the road network.
The experimental results demonstrate the benefits of path flexibility. Compared to the TDVRP without path flex- ibility, the TDVRP-PF results in significant savings in terms of cost and fuel consumption, by explicitly considering path flexibility in routing and scheduling. The role of time flexibility (i.e., flexible departure time at the depot and post-service waiting time at customer sites) appears to be less significant. Moreover, the results and insights obtained are robust on a wide range of instances (considering customer topology and the number of alternative paths).
More information needed? Contact me.
Homepage of Tom Van Woensel 