Plowing with precedence: A variant of the windy postman problem

摘要

In winter, a common problem is to determine the route that a snowplow should take in order to minimize the distance traveled. We propose a variant of this arc routing problem that is motivated by the fact that deadhead travel over streets that have already been plowed is significantly faster than the time it takes to plow the street. This problem differs from most arc routing problems because the cost of traversing a street changes depending on the order of the streets on a route. We develop a method that generates near-optimal solutions to instances as large as 200 nodes.