The (Over)zealous Snow Remover Problem
研究了单辆除雪车在街道分类、优先约束和转弯惩罚下的路径规划问题，通过转化为非对称旅行商问题求解，并比较了两种除雪策略的实际效果。
Planning snow removal is a difficult, infrequently occurring optimization problem, concerning complicated routing of vehicles. Clearing a street includes several different activities, and the tours must be allowed to contain subtours. The streets are classified into different types, each type requiring different activities. We address the problem facing a single vehicle, including details such as precedence requirements and turning penalties. We describe a solution approach based on a reformulation to an asymmetric traveling salesman problem in an extended graph, plus a heuristic for finding feasible solutions. The method have been implemented and tested on real life examples, and the solution times are short enough to allow online usage. We compare two different principles for the number of sweeps on a normal street, encountered in discussions with snow removal contractors. A principle using a first sweep in the middle of the street around the block, in order to quickly allow usage of the streets, is found to yield interesting theoretical and practical difficulties.