| 1. |
- Bredström, David, 1975-, et al.
(författare)
-
A genetic algorithm for a pulp distribution problem
- 2003
-
Rapport (övrigt vetenskapligt/konstnärligt)abstract
- In this paper we present a genetic algorithm for the pulp distribution problem at a large pulp producer in Scandinavia. The distribution is a major part of the company's supply chain and includes transports with cargo vessels, by train and trucks and storages at terminals in port, at pulp mills and in customer locations. The problem we focus on is to find ship schedules and pulp deliveries in order to minimize the total cost of distribution.The genetic algorithm utilizes two linear programming models. The first model optimizes all transport flows given a schedule and the second model approximates the performance of a schedule, measured in the total distribution cost. In the computational experiments we use instances from the real world and compare the results with an exact mixed integer programming approach.
|
|
| 2. |
- Henningsson, Mathias, et al.
(författare)
-
A column generation approach for a ring network design problem
- 2003
-
Rapport (övrigt vetenskapligt/konstnärligt)abstract
- When designing a telecommunication network, one often wish to include some kind of survivability requirement, for example that there should be at least two paths between every pair of nodes in the network. A design model who fulfills this requirement is a network build up with rings. The network design problem is to choose links from a given network, and compose them into a number of rings. The rings are connected to each other at certain transit nodes. The number of possible rings is enormous, and each possible ring is associated with a certain fixed cost. A ring has a fixed capacity, however, we model it as a linear cost depending on the traffic using the ring and the length of the ring. We describe the problem, and model it is a set covering model, where a column describes how a specific ring is used. Even with a small set of rings, number of possible columns in the model is large. Therefore, a column generation approach is used to solve the set covering model with a given set of rings. An important part of the problem is to generate new rings, were the dual solution from the set covering model gives rewards on the nodes, representing a nodes’ wish to be included in a new ring. The ring generation problem is a modification of a traveling salesman subtour problem. New rings are generated using a heuristic. We present some computational results for a real data network and a number of random generated networks.
|
|
| 3. |
- Henningsson, Mathias, 1970-, et al.
(författare)
-
A ring network design problem and heuristics for generating a set of feasible rings
- 2003
-
Rapport (övrigt vetenskapligt/konstnärligt)abstract
- We discuss the problem of designing a telecommunication network with the survivability requirement that the network should be composed of connected rings of links. The work design problem is then to choose links from a given network, and compose them into a number of rings. Furthermore, the rings should be connected at certain transit nodes. The traffic between rings may pass through other rings. Each ring is associated with a certain fixed cost depending on the length of the ring. We describe the problem, modeled as a linear integer programming problem. We find a feasible solution to the problem by first find good rings in the network using two heuristics, and then solve the optimization model using only these rings. Finally, we give some computational results for different networks.
|
|
| 4. |
- Henningsson, Mathias, 1970-, et al.
(författare)
-
A ring network design problem solved by a ring generation and allocation approach
- 2003
-
Rapport (övrigt vetenskapligt/konstnärligt)abstract
- The development of optical fibers in telecommunications has lead large changes in the field. When design a telecommunication network, capacity nowadays is cheap, and the minimal cost design tends to be a tree. Since such a design is very vulnerable for link or node failures, one often wish to include some kind of survivability requirement, for example that the network should be two-edge-connected or two-node-connected. Another form of design model is to prescribe that the network should be composed of connected rings of links. The network design problem is then to choose links from a give network, and compose them into a number of rings. Furthermore, the rings should be connected at certain transit nodes. Each possible ring is associated with a certain fixed cost, and all links in a certain ring are given the same capacity. Traffic between rings may pass through other rings, which is an important element of the problem. Finally, reserve capacity allocation according to certain principles is included. We describe the problem, modeled as a linear integer programming problem, and discuss different formulations and different solution methods. As the problem is quite difficult, we focus on heuristic solution methods, including elements of column generation and Lagrangean relaxation.
|
|
| 5. |
|
|
