Research On Snow-removal Vehicle Routing Problem Based On Criticality Of Road Segment

In the winter, urban road network can not operate properly as a result of accumulated snow covering the road. The effective program of snow-removal vehicle routing to clear accumulated snow is an important approach for winter road maintenance. In this paper, criticality of road segment under snow condition is proposed, which is used to divide priority level of removal services in order to study vehicle routing model satisfying service level restraint. Thus, we can reduce economic loss and increase reliability of road network on maximum extent in winter.First, service features of snow-removal vehicle and decision-making principles of snow removal is analyzed. With that, the objective of routing planning is confirmed, and further analysis of multi-lane constraint, service uniqueness constraint and load balancing constraint is given out. Based on studying road capacity and travel time function under snow condition, evaluation of criticality of each road segment by increases of the entire network travel costs when the road segment is blocked is proposed, which is used to divide priority level. Then the vehicle routing model whose objective is minimum of service completion time and satisfying service level restraint is constructed.Because the model has numerous complicated constraints, two kinds of two-stage algorithm is adopted for model solution: parallel algorithm and serial algorithm. The parallel algorithm is based on decomposition that the model is divided into several sub-problems, which means the routing model is transformed to several m-RPP models. By consideration of the specificity of parallel algorithm, one effective heuristic algorithm is proposed to get routing optimization, and there are two kinds of optimization process in the heuristic algorithm: sub-process optimization and whole process optimization. The serial algorithm is based on decomposition that all directed arcs are divided into several clusters, with that, the very cluster is serviced by each vehicle. Then, genetic algorithm is adopted for solution in serial algorithm to get the best snow removal routing associated with each vehicle.In the final, the typical medium-sized road network-Sioux Falls network is chose as a example for comparison and analysis of parallel algorithm and serial algorithm. After that, the conclusion that the two two-stage algorithms are effective and have different applicability is concluded.