In this paper, we introduce a Dantzig-Wolfe reformulation to compute aircraft arrival routes in a terminal maneuvering area (TMA) where the aircraft are flying according to theoptimal continuous-descent-operation (CDO) speed profile with idle thrust. This model assumes fixed entry times for all aircraft and a single separation time that is independent of wake-turbulence categories.Preliminary experiments show that this approach leads to significantly reduced runtimes.Moreover, the results indicate the possiblity of extending the reformulation to the full model and applying it to address additional practical considerations, such as wind effects in the future.

Snow removal is, in Sweden, an infrequently occurring challenge. Doing the snow removal more efficiently could give much benefits for society. Since the amounts of snow vary a lot from day to day, and from year to year, fixed plans are not the best. Optimization of the snow removal tours could save much money. In this paper, we study the multi-vehicle urban snow removal problem from a mixed integer programming perspective. It is a very hard problem, and obtaining the exact optimum seems to be out of reach. Therefore, we study relaxations of the problem. Our goal is simply to find the best bounds for the optimal objective function value that is possible in limited time. We present some promising possibilities, verified by extensive computational tests.  

Snow removal problem in cities is a challenging task in Nordic countries. The problem is finding optimal tours for a certain number of vehicles with some circumstances in order to clear a number of streets in a city. We have formulated the urban snow removal problem as a time-indexed mixed integer linear programming model which is huge and complicated. In our previous work, we studied the model and its different relaxations which show that the problem is not solvable in practice. Since the problem has many sets of constraints with complicated structures, relaxing them with Lagrangian relaxation might be beneficial. In this paper, we discuss different possibilities of relaxing sets of constraints and develop a Lagrangian heuristic which consists of a suitable Lagrangian relaxation of the problem, a subgradient optimization method for solving the Lagrangian dual, and procedures for obtaining feasible solutions. The heuristic has been implemented and applied to artificial and real life city networks. The results show that the bounds have been improved. 

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.

We study designing a tour for a snow removal vehicle. Several sweeps are required to clear a street of snow. We compare two variations for normal streets, the first is doing a middle sweep before the two side sweeps, and the second is not doing the middle sweep. We apply a previously developed method called branch-and-dive, and show that it yields very good results if the middle sweep is not used.

Planning urban snow removal, which is a complex optimization problem, is an important task in some countries like Sweden. A number of streets in a city must 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 modern real life city networks often contain parts that are trees, one can take advantage of the tree structure, in order to improve the computational eÿciency. In this paper, we study tree parts and develop a tree elimination procedure for the snow removal problem, to be used before searching for optimal tours. We have implemented the procedure and applied it to real life city networks. The numerical results compare obtaining feasible tours for real life city networks with and without tree elimination. It shows that the total solution time is signifcantly decreased with tree elimination, and larger areas can be handled. 

Snow removal is an unavoidable problem in Nordic countries like Sweden. A number of streets in a city need to be cleared of snow by a limited number of vehicles. The problem can be formulated as a very large mixed integer programming model, which is practically unsolvable. In order to find a feasible solution, first we break done the work into smaller parts, one for each vehicle. To find which streets a vehicle shall take care of, we solve a weighted k-Chinese postman problem. Based on the allocation obtained, we consider snow removal problems for single vehicles, where details such as turning penalties and precedences are included. These problems can be reformulated to asymmetric traveling salesman problems in extended graphs, and we have a heuristic for finding feasible solution of those. In this paper, we discuss combined solution approaches and coordination of the vehicles to find a feasible solution for the whole original problem including all details. We use an iterative procedure to combine the tours, based on the tools mentioned above, and a procedure for constructive coordination of the tours. We also have new improvement procedures for the combined solution. We have implemented the methods and applied them to real life city networks. The numerical results show that the methods obtain feasible tours for large problems within a reasonable time.

This paper deals with planning of a tour for a vehicle to clear a certain set of streets in a city of snow. Our previous results on the problem contain a heuristic based on reformulation to an asymmetric traveling salesman problem (ATSP) which yields feasible solutions and upper bounds, and a relaxation of a MIP model for obtaining lower bounds. The goal now is to try to improve the solutions and bounds. In this paper we describe a branch-and-dive heuristic which is based on branch-and-bound principles. We discuss how branching can be done so that the fixations can be utilized in both the relaxation and the ATSP model, and how the search for better solutions can be done. The heuristic has been implemented and applied to real life city networks. The method is shown to outperform two other heuristics for the ATSP with precedence constraints.