| Popis: |
Removing snow in a city is an unavoidable task in Nordic countries like Sweden. A number of streets in an area need to be cleared of snow by a limited number of vehicles and the tours for the vehicles must be planned in order to minimize the time and/or cost. Since the amount of snow can vary significantly from one year to another, the plans/tours of one year cannot be used for the next year. Hence, new tours need to be planned each time. Snow removal can be done in rural or urban areas and in addition during snowfall or after a snowfall. In this thesis, we study urban snow removal after a snowfall. There are different relevant specifics of the urban snow removal problem. For instance, there are different types of streets which need different numbers of sweeps in order to remove the snow. In addition, some tasks must be done before other tasks can be started. This leads to precedence constraints. Furthermore, each vehicle needs a certain time to switch from a task to another task. The problem can be formulated as a huge time-indexed mixed integer programming which often is not directly solvable in practice. The contributions of this thesis include the study of different relaxations and heuristics to find feasible solutions and improve the bounds on the optimal objective function values which are discussed in five papers. Paper I deals with single vehicle snow removal. A branch-and-dive heuristic based on branch-and-bound principles is given in order to improve the solutions and bounds. In Paper II, feasible solutions for the snow removal problem with a limited number of identical vehicles are obtained. First, the work is broken down into smaller parts, one for each vehicle. Based on the obtained allocation, a feasible tour for each single vehicle snow removal is obtained. Finally, combined solution approaches and co-ordination of the vehicles to find a feasible solution for the original problem are discussed. In order to improve the computational efficiency, one can take advantage of the tree structure, since modern real life city networks often contain parts that are trees. In Paper III, tree parts are studied and a tree elimination procedure is given for the snow removal problem, to be used before searching for optimal tours. Two variations encountered in practice for normal streets are compared in Paper IV. The first variant is doing a middle sweep before the two side sweeps and the second one is doing only side sweeps. Paper V studies the problem from modeling perspective. The problem is formulated as a mixed integer programming model and different relaxations of it are investigated. Finally, Lagrangian relaxation of the problem is studied in Paper VI. Different possibilities for Lagrangian relaxations are investigated and subgradient optimization is used to solve the Lagrangian dual. Snöröjning i en stad är ett oundvikligt problem i nordiska länder som Sverige. Ett antal gator i ett område behöver röjas från snö av ett begränsat antal fordon och turerna för fordonen måste planeras för att minimera tiden och/eller kostnaden. Eftersom snömängden kan variera avsevärt från ett år till ett annat kan ett visst års planer inte alltid användas nästa år. Därför måste nya turer kunna planeras vid behov. I denna avhandling studerar vi snöröjning i tätorter efter ett snöfall, vilket är annorlunda än snöröjning på landsbygden eller under pågående snöfall. Vid snöröjning i städer finns gator av olika bredd som behöver olika mycket arbete för att få bort snön. Dessutom måste vissa uppgifter utföras innan andra uppgifter kan påbörjas, såsom att röja en gata innan anslutande korsningar röjs. Dessutom behöver varje fordon ofta en viss tid för att byta från en uppgift till en annan uppgift, speciellt om de inte är närliggande. Problemet kan formuleras som en stor tidsindexerad blandad heltalsprogrammeringsmodell, som oftast inte är direkt lösbar med standardmetoder. Denna avhandling inkluderar studier av olika relaxationer och heuristiker för att hitta tillåtna lösningar och förbättra gränserna för det optimala målfunktions-värdet. Artikel I handlar om snöröjning med enstaka fordon. En så kallad branch-and-dive-heuristik baserad på trädsökningsprinciper används för att förbättra lösningarna och gränserna. I artikel II behandlas koordinationsproblemet att planera för flera fordon sam-tidigt i samma område. En sammansatt metod används. Först delas arbetet upp i mindre delar, en för varje fordon, och bra rundturer finnes för varje del. Därefter samordnas de olika turerna i tid och rum, vilket inte är så enkelt. Trots indelning finns alltid ett stort antal beröringspunkter där fordonen påverkar varandra. I artikel III utnyttjas det faktum att moderna stadsnätverk ofta innehåller delar, ofta bostadsområden, som är träd, det vill säga inte tillåter rundturer. I sådana områden kan optimeringen göras på ett enklare sätt, vilket förenklar optimering av hela problemet, och möjliggör optimering av större områden. I artikel IV görs en jämförelse av två olika metoder som används i praktiken då stora mängder av snö har kommit. Den första är att först röja mitten av gatorna i ett område, så att trafik överhuvudtaget kan komma fram, och sedan därefter göra finröjningen längs sidorna samt i korsningarna. Den andra är att inte röja mitten först. Det visar sig att optimering utan mittröjning är enklare än med mittröjning, och att vår metod fungerar bättre. Artikel V studerar olika typer av relaxation av den blandade heltalsprogrammeringsmodellen för hela problemet, och artikel VI studerar Lagrangerelaxation med subgradientoptimering. Det finns många olika möjligheter att relaxera problemet, och de undersöks med avseende på˚ lösningstid och målfunktionsvärde. |
