City of Edmonton spent $9,815,000 to plow snow in 2008. Vehicle routing is a frequent activity and small improvements in routing efficiency can result in large cost reductions. Routing problem for snow plowing operation is generally considered as a network optimization problem in the existing research. However, the formulation and solution approaches can be very different and diverse, since each area has its own unique environmental conditions and operation constraints. Assuming a district and a single depot are given, the problem is to determine a set of routes, which ensures that all road links are serviced, all the operational constraints are satisfied and the total cost is minimized. This study presents a mathematical optimization model based on Capacitated Arc Routing Problem (CARP) to minimize the deadhead distance during which the vehicle traverses the arcs without service. A Genetic Algorithm is used to solve this model and the sensitivity of the algorithm is also tested. The proposed model and algorithm are applied to a road sub-network from the south part of Edmonton. The results show that the percentage of deadhead distance is less than 1 % of the total travel distance. Sensitivity analyses also show that the final results are sensitive to the depot location. The proposed model needs to be expanded by considering more operation constraints in Edmonton.
展开▼