Integrated network routing and scheduling problem for salt trucks with replenishment before snowfall

Timely salting of roads before the snowfall is an important preventive activity for improving traffic safety and avoiding traffic congestions. We study the problem of routing and scheduling of salt trucks on a city road network. The problem is motivated by the operational problem that the Istanbul Metropolitan Municipality face in case of a heavy snowfall, and thereby should be solved in a periodic manner.In this problem, the vehicle fleet consists of heterogeneous vehicles that differ in salt capacity and there are multiple salt replenishment points. At the beginning of the current planning horizon, given a set of salt needing roads with different urgency levels, the vehicles start from different points of the network (i.e., their final locations at the end of the former planning horizon) and should cover all salt needing roads with the objective of minimizing the total weighted completion time of salting operation of each service needing arc. Each service needing arc should be serviced by exactly one vehicle, however, can be traversed for deadheading by a vehicle as part of its route.Vehicles visit replenishment points when they run out of salt. We first develop a Mixed-Integer Programming model for the problem. Since the performance of the model degrades rapidly as the problem size increases, we propose a simulated annealing metaheuristic, which obtains an initial solution by a constructive heuristic in the first phase, and then improves the solution in the next phase. The efficiency of our solution approach is evaluated on randomly generated instances reflecting real life road networks.