For winter road maintenance, a fleet of snowplow trucks is operated by government agencies to remove snow and ice on roadways and spread materials for anti-icing, de-icing, or increasing friction. Winter road maintenance is essential for providing safe and efficient service for road users (Usman et al., 2010). It is also costly due to the high cost of equipment, crew, and materials. Optimizing winter road maintenance operations could result in significant cost savings, improved safety and mobility, and reduced environmental and social impacts (Salazar-Aguilar et al., 2012).

The first topic in this study focuses on designing routes for winter maintenance trucks from a single depot. Real-world winter road maintenance constraints, including road segment service cycle time, heterogeneous vehicle capacity, fleet size, and road-vehicle dependency, are taken into consideration. The problem is formulated as a variation of the capacitated arc routing problem (CARP) to minimize total travel distance. A metaheuristic algorithm, memetic algorithm (MA), is developed to find nearly optimal solutions. This is the first study that developed the model that includes all the constraints listed. This is the first study that used the MA to solve the routing problem with all those constraints, and the first study that developed the route split procedure that satisfies all those constraints. In addition, a paralleled metaheuristic algorithm is proposed to enhance the solution quality and computation efficiency.

The second topic of this study focuses on designing routes from multiple depots with intermediate facilities. The service boundaries of depots are redesigned. Each truck must start and end at its home depot, but they can reload at other depots or reload stations (i.e., intermediate facilities). This problem is a variation of the multi-depot CARP with intermediate facilities (MDCARPIF). The second topic includes all constraints employed in the first topic. Since the trucks can be reloaded at any stations, a constraint that restricts the length of work time for truck drivers is also included in this topic. This is the first study that developed the model that includes all the constraints listed. This is the first study that uses the MA to solve the problem and the first study that developed the route split procedure that satisfies all those constraints.

The proposed algorithms are implemented to solve real-world problems. Deadhead (travelling without servicing) speed, service speed, and the spreading rate are estimated by the sample from historical winter road maintenance data.

Eighteen traffic networks are used as instances for the first topic. The optimized route in the first topic reduced 13.2% of the deadhead distance comparing to the current practice. Comparing to the single core result, the parallel computation improved the solution fitness on 2 of the 18 instances tested, with slightly less time consumed.

Based on the optimized result in the first topic, the reduction of the deadhead distance of the second topic is insignificant. This could be due to the network structure and depot location of the current operation. A test instance is created to verify the effectiveness of the proposed algorithm. The result shows 10.4% of deadhead distance can be saved by using the reload and multiple depot scenario instead of the single depot scenario on the test instance.