<p>Sweden experiences heavy snowfall during the winter season and cost effective road maintenance is significantly affected by the routing of snowplows. The routing problem becomes more complex as the SwedishNational Road Administration (Vägverket) sets operational requirements such as satisfying a time window for each road segment. </p><p>This thesis focuses on route optimization for snowplows after snowfall; to develop and implement an algorithm for finding combinations of generated routes which minimize the total cost. The results are compared to those stated in the licentiate thesis by Doctoral student Nima Golbaharan (2001). </p><p>The algorithm calculates a lower bound to the problem using a Lagrangian master problem. A common subgradient approach is used to find near-optimal dual variables to be sent to a column-generation program which returns routes for the snowplows. A greedy heuristic chooses a feasible solution, which gives an upper bound to the problem. This entire process is repeated as needed. </p><p>This method for routing snowplows produces favorable results with a relatively small number of routes and are comparable to Golbaharan's results. An interesting observation involves the allocation of vehicles in which certain depots were regularly over- or under-utilized. This suggests that the quantity and/or distribution of available vehicles may not be optimal.</p>

<p>Nynas produces bitumen at two refineries in Sweden. The bitumen is shipped to seven depots along the swedish coast line, and from the depots special trucks handle the transportation to customers. Recently Nynas has transformed its supply chain and closed down a few depots. At the moment the company is considering a further reduction of the number of depots. In connection to these discussions an analyse of the companys distributionsystem and of possible changes is required. In this thesis an optimization model is developed that simulates Nynas distribution of bitumen from the depots to the customers. The model is used to investigate the required vehicle fleet size for a number of different scenarios, that is with different depots closed down. The question to be answered is, thus, what depots could be closed without any dramatic increase in the required vehicle fleet size? Scenarios where customers are allocated an increased storage capacity are also studied. </p><p>The distribution model that is developed is an inventory route planning problem. It is solved by column generation. Each column represents a route and is generated by a subproblem with restrictions on permitted working hours for the truck drivers. Integer solutions are generated heuristically. </p><p>Simulations that have been performed with the model reveals interesting differences concerning how the distribution is handled in different parts of Sweden. In western Sweden the transportation planning works well, but the distribution in the central parts of the country could be planned in a better way. Results from simulations also show that the depots in Norrköping and Västerås could be closed down without increasing the vehicle fleet. Probably, the existing vehicle fleet size will be sufficient even with the Kalmar-depot closed down. Nevertheless, Nynas transportation suppliers will have to purchase new vehicles if the Sandarne-depot is to be closed. </p><p>Another interesting conclusion that can be drawn from this thesis is that there is a potential for reducing the vehicle fleet size if the storage capacity is increased at a few chosen customers. A considerably small increase in the storage capacity at a few big customers that are located far from the depots will have a great effect.</p>

<p>We analyse several facets of bilevel decision problems under uncertainty. These problems can be interpreted as an extension of stochastic programming problems where part of the uncertainty is attributed to the behaviour of another actor.</p><p>The field of decision making under uncertainty with bilevel features is quite new and most approaches focus on the interactions and relations between the decision makers. In contrast to these studies, the approach of bilevel stochastic programming pursued here stresses the stochastic programming aspect of the problem formulation. The framework enables a direct application of stochastic programming concepts and solution methods to the bilevel relationship between the actors. Thus more complex problem structures can be studied and the aspect of uncertainty can be treated adequately.</p><p>Our analysis covers both theoretical and more practically oriented issues. We study different formulations of one and two stage bilevel stochastic programming problems and state necessary optimality conditions for each of the problem instances. Additionally we present a solution algorithm utilising a stochastic quasi-gradient method. A further study is concerned with the uniqueness of the minima of a convex stochastic programming problem with uncertainty about the decision variables. We state conditions on the distribution of the parameters representing the uncertainty such that the minima of the optimisation problem are unique. We formulate a model of competition and collaboration of two different types of telecom service providers, the owner of a bottleneck facility and a virtual network operator. This represents an application of a bilevel stochastic programming formulation to a liberalised telecommunications environment. Furthermore, the utilisation of the bilevel stochastic programming framework and the developed solution concepts for the analysis of principal agent models is demonstrated. Also here the background of a regulated telecom environment, more specific the relations between a regulator and a regulated telecommunications company, was chosen.</p>

We analyse several facets of bilevel decision problems under uncertainty. These problems can be interpreted as an extension of stochastic programming problems where part of the uncertainty is attributed to the behaviour of another actor. The field of decision making under uncertainty with bilevel features is quite new and most approaches focus on the interactions and relations between the decision makers. In contrast to these studies, the approach of bilevel stochastic programming pursued here stresses the stochastic programming aspect of the problem formulation. The framework enables a direct application of stochastic programming concepts and solution methods to the bilevel relationship between the actors. Thus more complex problem structures can be studied and the aspect of uncertainty can be treated adequately. Our analysis covers both theoretical and more practically oriented issues. We study different formulations of one and two stage bilevel stochastic programming problems and state necessary optimality conditions for each of the problem instances. Additionally we present a solution algorithm utilising a stochastic quasi-gradient method. A further study is concerned with the uniqueness of the minima of a convex stochastic programming problem with uncertainty about the decision variables. We state conditions on the distribution of the parameters representing the uncertainty such that the minima of the optimisation problem are unique. We formulate a model of competition and collaboration of two different types of telecom service providers, the owner of a bottleneck facility and a virtual network operator. This represents an application of a bilevel stochastic programming formulation to a liberalised telecommunications environment. Furthermore, the utilisation of the bilevel stochastic programming framework and the developed solution concepts for the analysis of principal agent models is demonstrated. Also here the background of a regulated telecom environment, more specific the relations between a regulator and a regulated telecommunications company, was chosen.

Sweden experiences heavy snowfall during the winter season and cost effective road maintenance is significantly affected by the routing of snowplows. The routing problem becomes more complex as the SwedishNational Road Administration (Vägverket) sets operational requirements such as satisfying a time window for each road segment. This thesis focuses on route optimization for snowplows after snowfall; to develop and implement an algorithm for finding combinations of generated routes which minimize the total cost. The results are compared to those stated in the licentiate thesis by Doctoral student Nima Golbaharan (2001). The algorithm calculates a lower bound to the problem using a Lagrangian master problem. A common subgradient approach is used to find near-optimal dual variables to be sent to a column-generation program which returns routes for the snowplows. A greedy heuristic chooses a feasible solution, which gives an upper bound to the problem. This entire process is repeated as needed. This method for routing snowplows produces favorable results with a relatively small number of routes and are comparable to Golbaharan's results. An interesting observation involves the allocation of vehicles in which certain depots were regularly over- or under-utilized. This suggests that the quantity and/or distribution of available vehicles may not be optimal.

Nynas produces bitumen at two refineries in Sweden. The bitumen is shipped to seven depots along the swedish coast line, and from the depots special trucks handle the transportation to customers. Recently Nynas has transformed its supply chain and closed down a few depots. At the moment the company is considering a further reduction of the number of depots. In connection to these discussions an analyse of the companys distributionsystem and of possible changes is required. In this thesis an optimization model is developed that simulates Nynas distribution of bitumen from the depots to the customers. The model is used to investigate the required vehicle fleet size for a number of different scenarios, that is with different depots closed down. The question to be answered is, thus, what depots could be closed without any dramatic increase in the required vehicle fleet size? Scenarios where customers are allocated an increased storage capacity are also studied. The distribution model that is developed is an inventory route planning problem. It is solved by column generation. Each column represents a route and is generated by a subproblem with restrictions on permitted working hours for the truck drivers. Integer solutions are generated heuristically. Simulations that have been performed with the model reveals interesting differences concerning how the distribution is handled in different parts of Sweden. In western Sweden the transportation planning works well, but the distribution in the central parts of the country could be planned in a better way. Results from simulations also show that the depots in Norrköping and Västerås could be closed down without increasing the vehicle fleet. Probably, the existing vehicle fleet size will be sufficient even with the Kalmar-depot closed down. Nevertheless, Nynas transportation suppliers will have to purchase new vehicles if the Sandarne-depot is to be closed. Another interesting conclusion that can be drawn from this thesis is that there is a potential for reducing the vehicle fleet size if the storage capacity is increased at a few chosen customers. A considerably small increase in the storage capacity at a few big customers that are located far from the depots will have a great effect.

No description available.

<p>The transportation cost of logs from forest to customers is a large part of the overall cost for the Swedish forestry industry. Finding good routes from harvesting points to saw and pulp mills is a complex task, where the total number of feasible routes is extremely high. In this thesis we present two methods for log truck scheduling. </p><p>The first is to, from a given set of routes, find the most valuable subset that fulfils the customers demand. We use a model that is similar to the set partitioning problem and a method that is referred to as a composite pricing coupled with Branch and Bound. The composite pricing based method prices the routes (columns) and chooses the most valuable ones that are then added to the LP relaxation. Once an LP optimum is found, the Branch and Bound method is used to find an integer optimum solution. We have tested this on a case of realistic size. </p><p>The second method is a tabu search heuristic. Here, the purpose is to create efficient and qualitative routes from a given number of trips (referred to as predefined trips). From a start solution tabu search systematically generates new solutions. This method was tested on a small problem and on a five times larger problem to study how the size of the problem affected the result. It was also tested and compared on two cases in which the backhauling possibilities (i.e. instead of traveling empty the truck picks up another load on the return trip) had and had not been studied. The composite pricing based method and the tabu search method proved to be very useful for this kind of scheduling.</p>

<p>Traffic planning in a modern congested society is an important and time consuming procedure. Finding fast algorithms for solving traffic problems is therefore of great interest for traffic planners allover the world. </p><p>This thesis concerns solving the fixed demand traffic assignment problem (TAP) on a number of different transportation test networks. TAP is solved using the Frank-Wolfe algorithm and the shortest path problems that arise as subproblems to the Frank-Wolfe algorithm are solved using the network simplex algorithm. We evaluate how a number of existing pricing strategies to the network simplex algorithm performs with TAP. We also construct a new efficient pricing strategy, the Bucket Pricing Strategy, inspired by the heap implementation of Dijkstra's method for shortest path problems. This pricing strategy is, together with the actual use of the network simplex algorithm, the main result of the thesis and the pricing strategy is designed to take advantage of the special structure of TAP. In addition to performing tests on the conventional Frank-Wolfe algorithm, we also test how the different pricing strategies perform on Frank-Wolfe algorithms using conjugate and bi-conjugate search directions. </p><p>These test results show that the updating shortest path calculations obtained by using the network simplex outperforms the non-updating Frank-Wolfe algorithms. Comparisons with Bar-Gera's OBA show that our implementation, especially together with the bucket pricing strategy, also outperforms this algorithm for relative gaps down to 10E-6.</p>

Analytical interpolation theory has several applications in systems and control. In particular, solutions of low degree, or more generally of low complexity, are of special interest since they allow for synthesis of simpler systems. The study of degree constrained analytic interpolation was initialized in the early 80's and during the past decade it has had significant progress. This thesis contributes in three different aspects to complexity constrained analytic interpolation: theory, numerical algorithms, and design paradigms. The contributions are closely related; shortcomings of previous design paradigms motivate development of the theory, which in turn calls for new robust and efficient numerical algorithms. Mainly two theoretical developments are studied in the thesis. Firstly, the spectral Kullback-Leibler approximation formulation is merged with simultaneous cepstral and covariance interpolation. For this formulation, both uniqueness of the solution, as well as smoothness with respect to data, is proven. Secondly, the theory is generalized to matrix-valued interpolation, but then only allowing for covariance-type interpolation conditions. Again, uniqueness and smoothness with respect to data is proven. Three algorithms are presented. Firstly, a refinement of a previous algorithm allowing for multiple as well as matrix-valued interpolation in an optimization framework is presented. Secondly, an algorithm capable of solving the boundary case, that is, with spectral zeros on the unit circle, is given. This also yields an inherent numerical robustness. Thirdly, a new algorithm treating the problem with both cepstral and covariance conditions is presented. Two design paradigms have sprung out of the complexity constrained analytical interpolation theory. Firstly, in robust control it enables low degree Hinf controller design. This is illustrated by a low degree controller design for a benchmark problem in MIMO sensitivity shaping. Also, a user support for the tuning of controllers within the design paradigm for the SISO case is presented. Secondly, in ARMA estimation it provides unique model estimates, which depend smoothly on the data as well as enables frequency weighting. For AR estimation, a covariance extension approach to frequency weighting is discussed, and an example is given as an illustration. For ARMA estimation, simultaneous cepstral and covariance matching is generalized to include prefiltering. An example indicates that this might yield asymptotically efficient estimates. / QC 20100928