Snowplow Route Optimization Using Chinese Postman Problem and Tabu Search Algorithm

Snowplowing is critical to winter road operation and maintenance since it can improve driver's safety and mobility. The goal of this study is to generate optimal routes for snowplowing that can reduce travel distance and improve efficiency by considering operational constraints. To achieve this goal, we first adopted the Chinese Postman Problem to generate initial routes to be Euler circuits, and then the shortest path was generated using Dijkstra's algorithm. For an optimization process, the tabu search algorithm as a meta-heuristic approach was applied to find near-optimal routes by optimizing the order of precedence of snowplow routes, and the minimum maintenance standards and turn directions were considered as a constraint of the defined objective function. Through a simulation study, we compared routes generated by different approaches in terms of total travel distance, turning restriction, and road maintenance priority.