liu.seSearch for publications in DiVA
Change search
ReferencesLink to record
Permanent link

Direct link
Snow removal routing problems: theory and applications
Linköping University, Department of Mathematics, Optimization . Linköping University, The Institute of Technology.
2004 (English)Doctoral thesis, monograph (Other academic)
Abstract [en]

The focus of this dissertation is on constructing optimization models and developing solution methods for Snow Removal Routing Problems with Time V\lindows. Two cases, after and during snowfall, are studied. We discuss theoretical aspects of these problems and considerations to be taken when modeling and solving the real-world problem of the Swedish National Road Agency.

In the case of after snowfall we are concerned with finding a set of routes, with minimal total cost, for homogeneous snowplows, where every road segment is plowed in its associated time window. The routes must start from and end at the same depot, at which a numbers of snowplows are stationed. This case is solved by Dantzig-Wolfe decomposition combined with a column generation procedure. An integer solution to the master problem is found by a greedy algorithm or a variable reduction procedure. The case of generating routes for snowplows during snowfall is studied in two versions; the problems with and without time horizon on the duration of the snowfall. The focus is put on the latter problem, which is solved in two ways using a Dantzig-Wolfe decomposition scheme and a Tabu Search heuristic. The Dantzig-Wolfe master problem, is a Constrained Set Covering Problem and the subproblems are Prize Collecting Connected Subgraph Problems. Further, we show that the Prize Collecting Connected Subgraph Problem is a generalization of Prize Collecting Steiner Tree Problem and thus is NP-hard. An integer solution to the master problem is extracted by a greedy search procedure and the obtained solution is improved by post processing. The solution approaches for both cases are implemented and tested on the real-world problem under consideration and on an artificial, generated problem.

Place, publisher, year, edition, pages
Linköping: Linköpings universitet , 2004. , 129 p.
Linköping Studies in Science and Technology. Dissertations, ISSN 0345-7524 ; 888
National Category
URN: urn:nbn:se:liu:diva-23691Local ID: 3190ISBN: 91-7373-983-9OAI: diva2:244006
Public defence
2004-09-08, Sal BL32, Hus B, Linköpings Universitet, Linköping, 10:15 (Swedish)
Available from: 2009-10-07 Created: 2009-10-07 Last updated: 2012-12-18

Open Access in DiVA

No full text

Search in DiVA

By author/editor
Razmara, Gholamreza
By organisation
Optimization The Institute of Technology

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Total: 377 hits
ReferencesLink to record
Permanent link

Direct link