Another look at snow removal
Kaj Holmberg  1@  
1 : Linkoping University, Department of Mathematics, Division of Optimization  (liu)

Planning urban 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.

Our earlier research in this area has produced the following results:
* A large intractable time-indexed MIP-model, including all details such as different vehicles, precedence requirements, turning penalties and environmental aspects.
* Some solvable relaxations of the total model, yielding lower bounds.
* Heuristic solution procedures for the k-Chinese postman problem, to find a good allocation of streets to identical vehicles, also addressing the question of the number of vehicles.
* Optimization approaches for the map matching problem, i.e. transferring a number of GPS-positions to a tour on the edges of a digital map.
* A detailed ATSP-based solution procedure for the (over) zealous snow remover problem, i.e. the problem facing a single vehicle, based on a reformulation to an asymmetric traveling salesman problem in an extended graph, plus a heuristic for finding feasible solutions.

The methods have been implemented and tested on real life examples.

In this talk we give an overview of the whole picture, including all the parts mentioned above, and discuss what is missing for making the picture complete.


Online user: 1 RSS Feed