Winter Road Maintenance Operation Optimization for a Multi-Depot Mixed Capacitated Location-Arc Routing Problem

In wintertime, snowfall causes road blockages especially in areas located at high altitudes and consequently interrupts daily activities of dwellers in these areas. Damavand is a city located in the Alborz mountain range whose roads are mostly covered by snow in winter. An initial action to open roads is to spread salt on the roads to accelerate snow melting. There are two important decisions for salt spreading operation as a winter road maintenance operation, i.e. determining salt storage depot locations and routing salt spreading vehicles. Considering these two decisions simultaneously leads to efficient salt spreading operation. In this paper, the salt spreading problem in Damavand area is formulated as a multi depot capacitated location-arc routing problem with heterogeneous fleet and service frequency (MDCLARPF) on a mixed network where demands are on edges rather than nodes. Due to NP-hardness of the problem, two-stage simulated annealing (SA) and genetic algorithm (GA) metaheuristics are designed to deal with large-sized problems. Before employing these methods for the case of Damavand city, the validity of the proposed methods are investigated. For this purpose, first the results of the proposed two-stage GA and SA are compared with an exact method for small-sized problems. The results show that these methods have close performance to the exact method. For large-sized problems, the proposed metaheuristics are compared upon a set of instances taken from the literature and the results show that the proposed two-stage GA results in high quality solutions. Therefore, it is used to deal with the case of Damavand city and the results are validated through a set of simulation experiments. The results are useful for road maintenance and transportation organizations