| 1. |
- Broström, Peter, 1973-, et al.
(author)
-
Determining the Non-Existence of a Compatible OSPF Metric
- 2004
-
Reports (other academic/artistic)abstract
- Many telecommunication networks use Internet Protocol for deciding the routing of traffic. The specifications OSPF (Open Shortest Path First) and ECM (Equal Cost Multipath) are very common, and state that each router sends the traffic on the shortest path to the destination. If there are several shortest path, the router splits the traffic evenly. In order to have some control over the traffic distribution, the operator can assign weights to the links in the network, and these weights are used by the routers when calculating the shortest paths. It has been shown that by optimizing over the values of the weights, the performance of a network can be much improved. A difficult question is whether or not for a set of desired traffic patterns there exists a compatible metric, i.e. weights making the routers give the specified traffic patterns. There is one known necessary condition for the existence of such a metric, but up to now no sufficient conditions. We investigate this problem, and find more general necessary conditions for the existence of compatible weights for a set of given desired "shortest path"-graphs. A polynomial algorithm that for most cases verifies the non-existence of a compatible metric is presented. The algorithm also indicates which parts of the traffic patterns that are in conflict. A few numer;cal examples are used to illustrate the procedure, and some computational tests are reported.
|
|
| 2. |
|
|
| 3. |
- Broström, Peter, 1973-, et al.
(author)
-
Stronger Necessary Conditions for the Existence of a Compatible OSPF Metric
- 2004
-
Reports (other academic/artistic)abstract
- A dominating standard for routing in telecommunication networks is Internet Protocol with OSPF (Open Shortest Path First) and ECM (Equal Cost Multipath). Each router sends the traffic on the shortest path to the destination. If there are several shortest path, the router splits the traffic evenly. The operator can assign weights to the links in the network, which are used by the routers when calculating the shortest paths. An important question is whether or not for a set of desired traffic patterns there exists a compatible metric, i.e. weights making the routers give the specified traffic patterns. We describe necessary conditions, stronger than those previously discovered, for the existence of compatible weights for a set of given desired shortest path-graphs.
|
|
| 4. |
- Hajizadeh, Roghayeh, 1986-, et al.
(author)
-
Coordination of vehicles in urban snow removal
- 2021
-
Reports (other academic/artistic)abstract
- 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.
|
|
| 5. |
- Hajizadeh, Roghayeh, 1986-, et al.
(author)
-
In search of good relaxations for the urban snow removal problem
- 2023
-
Reports (other academic/artistic)abstract
- 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.
|
|
| 6. |
- Hajizadeh, Roghayeh, 1986-, et al.
(author)
-
Lagrangian relaxation for the urban snow removal problem
- 2023
-
Reports (other academic/artistic)abstract
- 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.
|
|
| 7. |
- Hajizadeh, Roghayeh, 1986-, et al.
(author)
-
The Non Zealous Snow Remover Problem
- 2022
-
Reports (other academic/artistic)abstract
- 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.
|
|
| 8. |
- Hajizadeh, Roghayeh, 1986-, et al.
(author)
-
Urban snow removal : Tree elimination
- 2022
-
Reports (other academic/artistic)abstract
- 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.
|
|
| 9. |
- Henningsson, Mathias, 1970-, et al.
(author)
-
A ring generation problem based on the traveling salesman subtour problem
- 2003
-
Reports (other academic/artistic)abstract
- Survivability and high redundancy are two critical issues in field of telecommunications. If a telecommunication network is built up by rings, high redundancy can be established, since the traffic can be sent in either direction. Traffic is usually sent using one direction, and if a failure occurs, the opposite direction is used. There is often a number of requirements on a ring, such as a limit on the number of connected nodes. This means that the network will include a number of rings, and traffic between rings must be possible. Therefore, a network must include a number of transit nodes, where it is possible to send traffic between the rings. We focus on the case where network includes two transit nodes and each ring must include at least one transit node. Since the number of rings is enormous one needs to generate rings.This paper discusses how to generate new rings, given that each node has a reward for connecting the node to the ring. The problem that occurs is a modification of a traveling salesman subtour problem with a additional constraint on the number of nodes connected. A problem formulation is given and some solution approaches are suggested. Two different scenarios are discussed, one where the aim is to modify an already existing ring, and one where the aim is to build a complete new ring. Some computational results are given for a real data network.
|
|
| 10. |
- Henningsson, Mathias, 1970-, et al.
(author)
-
A ring network design problem and heuristics for generating a set of feasible rings
- 2003
-
Reports (other academic/artistic)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.
|
|
