TY - GEN A1 - Bley, Andreas T1 - On the Hardness of Finding Small Shortest Path Routing Conflicts N2 - Nowadays most data networks use shortest path protocols such as OSPF or IS-IS to route traffic. Given administrative routing lengths for the links of a network, all data packets are sent along shortest paths with respect to these lengths from their source to their destination. One of the most fundamental problems in planning shortest path networks is to decide whether a given set of routing paths forms a valid routing and, if this is not the case, to find a small subset of the given paths that cannot be shortest paths simultaneously for any routing lengths. In this paper we show that it is NP-hard to approximate the size of the smallest shortest path conflict by a factor less than 7/6. T3 - ZIB-Report - 09-15 KW - shortest path routing KW - computational complexity Y1 - 2009 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-11276 SN - 1438-0064 ER - TY - GEN A1 - Torres, Luis Miguel A1 - Torres, Ramiro A1 - Borndörfer, Ralf A1 - Pfetsch, Marc T1 - Line Planning on Paths and Tree Networks with Applications to the Quito Trolebus System N2 - Line planning is an important step in the strategic planning process of a public transportation system. In this paper, we discuss an optimization model for this problem in order to minimize operation costs while guaranteeing a certain level of quality of service, in terms of available transport capacity. We analyze the problem for path and tree network topologies as well as several categories of line operation that are important for the Quito Trolebus system. It turns out that, from a computational complexity worst case point of view, the problem is hard in all but the most simple variants. In practice, however, instances based on real data from the Trolebus System in Quito can be solved quite well, and significant optimization potentials can be demonstrated. T3 - ZIB-Report - 08-35 KW - line planning KW - computational complexity KW - public transport KW - integer programming Y1 - 2008 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-10869 SN - 1438-0064 ER - TY - GEN A1 - Torres, Luis Miguel A1 - Torres, Ramiro A1 - Borndörfer, Ralf A1 - Pfetsch, Marc T1 - On the Line Planning Problem in Tree Networks N2 - We introduce an optimization model for the line planning problem in a public transportation system that aims at minimizing operational costs while ensuring a given level of quality of service in terms of available transport capacity. We discuss the computational complexity of the model for tree network topologies and line structures that arise in a real-world application at the Trolebus Integrated System in Quito. Computational results for this system are reported. T3 - ZIB-Report - 08-52 KW - line planning KW - computational complexity KW - public transport optimization Y1 - 2008 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-11069 SN - 1438-0064 ER - TY - GEN A1 - Torres, Luis Miguel A1 - Torres, Ramiro A1 - Borndörfer, Ralf A1 - Pfetsch, Marc T1 - Line Planning on Paths and Tree Networks with Applications to the Quito Trolebus System (Extended Abstract) N2 - Line planning is an important step in the strategic planning process of a public transportation system. In this paper, we discuss an optimization model for this problem in order to minimize operation costs while guaranteeing a certain level of quality of service, in terms of available transport capacity. We analyze the problem for path and tree network topologies as well as several categories of line operation that are important for the Quito Trolebus system. It turns out that, from a computational complexity worst case point of view, the problem is hard in all but the most simple variants. In practice, however, instances based on real data from the Trolebus System in Quito can be solved quite well, and significant optimization potentials can be demonstrated. T3 - ZIB-Report - 08-53 KW - line planning KW - computational complexity KW - public transport KW - integer programming Y1 - 2008 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-11076 SN - 1438-0064 ER - TY - GEN A1 - Bley, Andreas T1 - Approximability of Unsplittable Shortest Path Routing Problems N2 - In this paper, we discuss the relation of unsplittable shortest path routing (USPR) to other routing schemes and study the approximability of three USPR network planning problems. Given a digraph $D=(V,A)$ and a set $K$ of directed commodities, an USPR is a set of flow paths $\Phi_{(s,t)}$, $(s,t)\in K$, such that there exists a metric $\lambda=(\lambda_a)\in \mathbb{Z}^A_+$ with respect to which each $\Phi_{(s,t)}$ is the unique shortest $(s,t)$-path. In the \textsc{Min-Con-USPR} problem, we seek for an USPR that minimizes the maximum congestion over all arcs. We show that this problem is hard to approximate within a factor of $\mathcal{O}(|V|^{1-\epsilon})$, but easily approximable within min$(|A|,|K|)$ in general and within $\mathcal{O}(1)$ if the underlying graph is an undirected cycle or a bidirected ring. We also construct examples where the minimum congestion that can be obtained by USPR is a factor of $\Omega(|V|^2)$ larger than that achievable by unsplittable flow routing or by shortest multi-path routing, and a factor of $\Omega(|V|)$ larger than by unsplittable source-invariant routing. In the CAP-USPR problem, we seek for a minimum cost installation of integer arc capacities that admit an USPR of the given commodities. We prove that this problem is $\mathcal{NP}$-hard to approximate within $2-\epsilon$ (even in the undirected case), and we devise approximation algorithms for various special cases. The fixed charge network design problem \textsc{Cap-USPR}, where the task is to find a minimum cost subgraph of $D$ whose fixed arc capacities admit an USPR of the commodities, is shown to be $\mathcal{NPO}$-complete. All three problems are of great practical interest in the planning of telecommunication networks that are based on shortest path routing protocols. Our results indicate that they are harder than the corresponding unsplittable flow or shortest multi-path routing problems. T3 - ZIB-Report - 06-02 KW - Shortest path routing KW - unsplittable flow KW - computational complexity KW - approximation Y1 - 2006 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-8968 ER -