Article ID: | iaor2013755 |
Volume: | 40 |
Issue: | 4 |
Start Page Number: | 1047 |
End Page Number: | 1059 |
Publication Date: | Apr 2013 |
Journal: | Computers and Operations Research |
Authors: | Wasil Edward, Golden Bruce, Gror Chris, Dussault Benjamin |
Keywords: | combinatorial optimization |
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.