Loading...
Please wait, while we are loading the content...
Similar Documents
Minimum Cost Disjoint Paths under Arc Dependences. Algorithms for Practice
| Content Provider | Semantic Scholar |
|---|---|
| Author | Oellrich, Martin |
| Copyright Year | 2008 |
| Abstract | In this thesis, we develop a unified algorithmic framework fo r Minimum Cost Disjoint Paths Problems . These problems arise in a variety of applied contexts, in par ticular telecommunication networks and automated vehicle routing. The main motivation typically i s the desire to plan a structure which is safe in a certain way. In telecommunications, survivability of n etworks is a paramount issue. In guiding of cargo vehicles, it is prevention of collisions. We have take n the initial impulse for our research from a project with T-Systems Darmstadt. Planners needed a tool t o support the pricing of so-called Virtual Private Networks . We developed a software called ODEA to aid their processes. It was also applied to realistic instances from a logistics project with Containe rterminal Altenwerder at Hamburg harbour. Disjoint Paths Problems are posed in the form of a directed or undirected graph with nonnegative arc/edge costs and a set of node pairs in it. A feasible soluti on is a set of connecting paths, one for each node pair, such that two conditions are satisfied: 1. all path s re pairwise nonintersecting in a given sense, 2. the total cost of the solution is a minimum among all soluti ns. This problem is known to be NP-hard even in very restricted cases. Literature reports about spe cial cases allowing polynomial time algorithms as well as heuristic approximation schemes. There is an appa rent l ck on exact approaches suitable for deployment in broad purpose software. Our work addresses th is gap. We present an integer programming model flexible enough to ac c mmodate several disjointness modes, yet practical enough to allow for efficient algorithm ic treatment of real-world instances. We introduce a new modelling technique called arc dependences . It generalizes the traditional notion of disjointness which differentiates between arc-, edgeor n ode-disjointness only. With its help, planners can restrict their work to specially constructed abstracti ons of the input graph, comprising significantly less data without losing the essence needed for safety. Whil e the main focus of this model lies on paths in the graph, we also investigate an alternative featuring s o-calledstar flows. The main part of this book describes in detail the methods dev eloped for encoding in our software. We devise a Branch-and-Bound scheme and fill in the contents f or its functional ingredients: branching strategies, structural pruning, upper and lower cost bound s. This includes two novel ideas for strengthening the latter. Behind all these tasks, the combinatorial core engine of the solver is an assortment of specially adapted cheapest paths routines. We set up a representative testbed and perform extensive tes ting of our algorithms throughout all development stages. We conclude with a competition between ODEA and the commercial general purpose CPLEX MIP solver. |
| File Format | PDF HTM / HTML |
| DOI | 10.14279/depositonce-1857 |
| Alternate Webpage(s) | https://depositonce.tu-berlin.de/bitstream/11303/2154/2/Dokument_28.pdf |
| Alternate Webpage(s) | https://doi.org/10.14279/depositonce-1857 |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
