Consistent Vehicle Routing Problem Considering Traffic Congestion and Workload Balance

In order to investigate the effects of transportation congestion and workload balance on the delivery routing of express delivery companies which wish to provide consistent services, a consistent vehicle routing problem considering traffic congestion and workload balance was proposed and a mixed integer programming model for this problem was constructed. In view of the model' s NP-hard property, a two-phase template-based simulated annealing method (TSA) was applied to solve this problem. The TSA attains an initial route plan by constructing template routes first, and then optimizes them using the simulated annealing method to decrease the total travel time. To verify the validity of the proposed model and algorithm, numerical experiments were conducted using three benchmark data sets. Results show that the model and TSA can solve this problem effectively. The traffic congestion will significantly increase the total travel time by an average of 18.38% and increase the difference between the earliest and latest arrival time at the same customer within any two days by an average of 12.92%. Besides, when the average difference of the delivery men's shipment quantity decreases by 35.82%, the total travel time and the difference between the earliest and latest arrival time at the same customer are only increased by 2.29% and 1.68%, respectively.