Urban Snow Removal:: Modeling and Relaxations
2014 (English)Report (Other academic)
Snow removal is an important problem in certain countries. It is also difficult, especially in urban areas. The main questions are which vehicle shall do what task, when shall the tasks be done and how shall the vehicles travel. In this paper we describe the problem in detail and formulate a detailed mathematical time-indexed model that contains all practical complications we have encountered, for example different vehicles and switching times between tasks. We investigate the solvability of the model, and present a number of alternate formulations, relaxations and simplifications, yielding several different models of different sizes and different strength. We can either solve very small problems exactly or larger problems more approximately. Our main goal is to find good lower bounds on the optimal objective function value in a limited time, and we present extensive computational tests comparing the obtained bounds and the times needed for the different models. As a result we find some rather efficient models, in the sense that they yield rather good lower bounds in rather short time. With these models, we find lower bounds for several real life instances in the form of small local cities.
Place, publisher, year, edition, pages
Linköping University Electronic Press, 2014. , 88 p.
LiTH-MAT-R, ISSN 0348-2960 ; 2014:08
IdentifiersURN: urn:nbn:se:liu:diva-107921ISRN: LiTH-MAT-R--2014/08--SEOAI: oai:DiVA.org:liu-107921DiVA: diva2:728056