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. 

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.

Real life optimization often concerns difficult objective functions, in two aspects, namely that gradients are unavailable, and that evaluation of the objective function takes a long time. Such problems are often attacked with model building algorithms, where an approximation of the function is constructed and solved, in order to find a new promising point to evaluate. We study several ways of saving time by using parallel calculations in the context of model building algorithms, which is not trivial, since such algorithms are inherently sequential. We present a number of ideas that has been implemented and tested on a large number of known test functions, and a few new ones. The computational results reveal that some ideas are quite promising.

In a democratic proportional election system, it is vital that the mandates in the parliament are allocated as proportionally as possible to the number of votes the parties got in the election. We formulate an optimization model for allocation of seats in a parliament so as to minimize the disproportionality. By applying separable programming techniques, we obtain an easily solvable problem, and present a method for solving it optimally. The obtained solution is the feasible solution that has the minimal disproportionality (with the measure chosen), even in the presence of a parliament threshold, which is not always the case for the practical procedures used in many countries. We apply the approach to real life data from the last three elections in Sweden, and show that the result is better, i.e. more proportional, than what was obtained with the modified Sainte-Laguë method, which is presently used. A natural suggestion would be to use our method instead.

We also consider the issue about constituencies, and suggest a procedure, based on the same kind of optimization problem, for allocating mandates in the constituencies, without changing the overall allocation with respect to parties. The numbers of mandates for the constituencies are based on the number of votes given, not on estimated numbers of inhabitants entitled to vote. This removes the need for compensatory mandates, and makes the question about sizes of the constituencies less important.

In a democratic proportional election system, it is vital that the mandates in the parliament are allocated as proportionally as possible to the number of votes the parties got in the election. We formulate an optimization model for allocation of seats in a parliament so as to minimize the disproportionality. By applying separable programming techniques, we obtain an easily solvable problem, and present a method for solving it optimally. The obtained solution is thus the feasible solution that has the minimal disproportionality (with the measure chosen), in contrast to the heuristic procedures used in many countries. We apply the approach to real life data from the last three elections in Sweden, and show that the result is better, i.e. more proportional, than what was obtained with the “adjusted odd number rule”, which is presently used. A natural suggestion would be to use our method instead.

We also consider the issue about constituencies, and suggest a procedure, based on the same kind of optimization problem, for allocating mandates in the constituencies, without changing the overall allocation with respect to parties. In our approach, the numbers of mandates for the constituencies are based on the number of votes given, not on estimated numbers of inhabitants. This removes the need for fixed and equalization mandates, and also makes the question about sizes of the constituencies less important.

We investigate the effect of different reductions when importing networksfrom OpenStreetMap data. We describe the network reductions and report computationaltests for doing the network extraction and reduction. We also show the effect ofthe reductions by solving a few standard optimization problems in the resulting networks.Computational tests show that the reductions have a dramatic effect on thenetwork size and the time needed for solving the optimization problems. In many cases,the reductions are necessary in order to be able to solve the optimization problem inreasonable time. A practical result of this work is a set of networks that will be usedas benchmarks in future research, and are publically available for other researchers.

We discuss the problem of projecting points on their convex hull. Points in the interior of the convex hull are moved outwards to the boundary of the convex hull. While finding the convex hull is a well treated problem, projecting each interior point on the convex hull is not. It is a harder problem, since each point has to be treated. We first discuss a solution approach in two dimensions, and then generalize it to three dimensions. After some significant improvements and changes, we arrive at efficient solutions method for the three dimensional case, using various column and/or constraint generation techniques.