Heiko Schilling

For a given number L, an L-length-bounded edge-cut (node-cut, respectively) in a graph G with source s and sink t is a set C of edges (nodes, respectively) such that no s-t-path of length at most L remains in the graph after removing the edges (nodes, respectively) in C. An L-length-bounded flow is a flow that can be decomposed into flow paths of length at most L. In contrast to classical flow theory, we describe instances for which the minimum L-length-bounded edge-cut (node-cut, respectively)… Mehr anzeigen

For a given number L, an L-length-bounded edge-cut (node-cut, respectively) in a graph G with source s and sink t is a set C of edges (nodes, respectively) such that no s-t-path of length at most L remains in the graph after removing the edges (nodes, respectively) in C. An L-length-bounded flow is a flow that can be decomposed into flow paths of length at most L. In contrast to classical flow theory, we describe instances for which the minimum L-length-bounded edge-cut (node-cut, respectively) is Θ(n2/3)-times (Θ(&sqrt;n)-times, respectively) larger than the maximum L-length-bounded flow, where n denotes the number of nodes; this is the worst case. We show that the minimum length-bounded cut problem is NP-hard to approximate within a factor of 1.1377 for L≥ 5 in the case of node-cuts and for L≥ 4 in the case of edge-cuts. We also describe algorithms with approximation ratio O(min{L,n/L}) ⊆ O&sqrt;n in the node case and O(min {L,n2/L2,&sqrt;m} ⊆ O2/3 in the edge case, where m denotes the number of edges. Concerning L-length-bounded flows, we show that in graphs with unit-capacities and general edge lengths it is NP-complete to decide whether there is a fractional length-bounded flow of a given value. We analyze the structure of optimal solutions and present further complexity results. Weniger anzeigen

In this paper, we conduct a detailed study of the arc-flag approach introduced in [Lau97, Lau04]. Arc-flags are a modification of Dijkstra’s algorithm to accelerate point-to-point (p2p) shortest path computations. The usage of arc-flags avoids exploring unnecessary paths during shortest path query computations. We present two improvements of the original arc-flag method that reduce the pre-calculation times significantly, tweak the efficiency of queries, and cut down the space requirements… Mehr anzeigen

In this paper, we conduct a detailed study of the arc-flag approach introduced in [Lau97, Lau04]. Arc-flags are a modification of Dijkstra’s algorithm to accelerate point-to-point (p2p) shortest path computations. The usage of arc-flags avoids exploring unnecessary paths during shortest path query computations. We present two improvements of the original arc-flag method that reduce the pre-calculation times significantly, tweak the efficiency of queries, and cut down the space requirements. First, we improve the preprocessing of the arc-flags by introducing a centralized shortest path algorithm and thereby we overcome the main drawback of the arc-flag method: for the first time it is now possible to apply the pure arc-flag method to large networks such as continental road networks (US network: 24M nodes, 58M edges). Second, we improve the partitioning used in our revised arc-flag method by using multi-way arc separators. Thereby we almost doubled the efficiency of queries on some instances compared to [Lau06] and further reduced the space requirements. This achievement stresses the vital importance of the right choice of partitioning for the performance of the arc-flag method. On the US network, our revised arc-flag method requires only between 4.1 and 15.5 bytes of additional preprocessed data per arc and p2p queries can be answered within 3 to 9 milliseconds (depending on the metric and the underlying partitioning). These results make our revised arc-flags method the currently best-performing purely goal-directed approach. Without having to use combinations with other advanced acceleration techniques or any network compression method we have kept the modification of Dijkstra’s original algorithm minimal—literally only one additional line of code in the route search algorithm needs to be implemented. Its simplicity suggests its usage in existing code bases of route finding applications—whether that be website routers, mobile phones, or personal navigation devices. Weniger anzeigen

The Cargo Express service of Swiss Federal Railways (SBB Cargo) offers fast overnight transportation of goods between selected train stations in Switzerland and is operated as a hub-and-spoke system with two hubs. We present three different models for planning the operation of this service as a whole. All models capture the underlying optimization problem with a high level of detail: Traffic routing, train routing, makeup, scheduling, and locomotive assignment are all addressed. At the same… Mehr anzeigen

The Cargo Express service of Swiss Federal Railways (SBB Cargo) offers fast overnight transportation of goods between selected train stations in Switzerland and is operated as a hub-and-spoke system with two hubs. We present three different models for planning the operation of this service as a whole. All models capture the underlying optimization problem with a high level of detail: Traffic routing, train routing, makeup, scheduling, and locomotive assignment are all addressed. At the same time we respect hard constraints like tight service time windows and train capacities, and we avoid hub overloading. We describe our approaches for obtaining provably good quality solutions. Our algorithmic techniques involve branch-and-cut, branch-and-price, and problem-specific exact and heuristic acceleration methods. We conclude our study with computational results on realistic data. Weniger anzeigen

We present a number of improvements of the basic variant of the arc-flag acceleration (Lauther, 1997, 2004) for point-to-point (P2P) shortest path computations on large graphs. Arc-flags are a modification to the standard Dijkstra algorithm and are used to avoid exploring unnecessary paths during shortest path computation.We assume that for the same input graph the shortest path problem has to be solved repeatedly for different node pairs. Thus, precomputing the arc-flags is possible. We show… Mehr anzeigen

We present a number of improvements of the basic variant of the arc-flag acceleration (Lauther, 1997, 2004) for point-to-point (P2P) shortest path computations on large graphs. Arc-flags are a modification to the standard Dijkstra algorithm and are used to avoid exploring unnecessary paths during shortest path computation.We assume that for the same input graph the shortest path problem has to be solved repeatedly for different node pairs. Thus, precomputing the arc-flags is possible. We show that the improved arc-flag acceleration achieves speedups of P2P shortest path queries of more than 1,470 on a subnetwork of the German road network1 with 1M node and 2.5M arcs using 450 bits of additional information per arc. The acceleration factors increase with the size of the input graph. Finally, we present an improved preprocessing version which allows precomputing arc-flags for European and North-American road networks within hours. Weniger anzeigen

FAST ROUTE PLANNING: We presented a number of improvements of the basic variant of the arc-flag acceleration (Lauther, 1997, 2004) for speeding up the P2P shortest path search on static networks. Arc flags are a modification to the standard Dijkstra algorithm and are used to avoid exploring unnecessary paths during shortest path computation. We showed that the improved arc-flags achieve speedups of P2P shortest path queries of more than 1,470 on a subnetwork of the German road network with 1M… Mehr anzeigen

FAST ROUTE PLANNING: We presented a number of improvements of the basic variant of the arc-flag acceleration (Lauther, 1997, 2004) for speeding up the P2P shortest path search on static networks. Arc flags are a modification to the standard Dijkstra algorithm and are used to avoid exploring unnecessary paths during shortest path computation. We showed that the improved arc-flags achieve speedups of P2P shortest path queries of more than 1,470 on a subnetwork of the German road network with 1M node and 2.5M arcs using 450 bits of additional information per arc.

LOAD-BALANCED ROUTE PLANNING: We introduced an innovative model for flows over time, which captures the behavior of cars traveling through a road network better than previous models working with inflow-dependent or load-dependent transit times. Our new model is called the Rate-Dependent model. It describes the dependence of travel speed on the current flow situation: the maximal possible speed at any position on an arc, at any point in time, always depends directly on the current flow rate. We showed that computing an optimal solution in the new model is NP-hard and we presented an LP-based algorithm which we evaluated with several experiments on real world data of road networks and generated requests.

NETWORK FLOWS: We presented a number of results concerning the complexity and approximability of length-bounded cut and flow problems. We showed that the minimum length-bounded cut problem in graphs with unit edge lengths is NP-hard to approximate within a factor of at least 1.1377 for L ≥ 5 in the case of node-cuts and for L ≥ 4 in the case of edge-cuts. For L = n−c, where c ∈ N is an arbitrary constant, a minimum length-bounded node-cut can be computed in polynomial time in (un-)directed graphs. Our results improve the results in (Lovász et al., 1978) and in (Mahjoub and McCormick, 2003). Weniger anzeigen

Traffic management and route guidance are optimization problems by nature. In this article, we consider algorithms for centralized route guidance and discuss fairness aspects for the individual user resulting from optimal route guidance policies. The first part of this article deals with the mathematical aspects of these optimization problems from the viewpoint of network flow theory.We present algorithms which solve the constrained multicommodity minimum cost flow problem (CMCF) to optimality.… Mehr anzeigen

Traffic management and route guidance are optimization problems by nature. In this article, we consider algorithms for centralized route guidance and discuss fairness aspects for the individual user resulting from optimal route guidance policies. The first part of this article deals with the mathematical aspects of these optimization problems from the viewpoint of network flow theory.We present algorithms which solve the constrained multicommodity minimum cost flow problem (CMCF) to optimality. A feasible routing is given by a flow x, and the cost of flow x is the total travel time spent in the network. The corresponding optimum is a restricted system optimum with a globally controlled constrained or fairness factor L > 1. This approach implements a compromise between user equilibrium and system optimum. The goal is to find a route guidance strategy which minimizes global and community criteria with individual needs as constraints. The fairness factor L restricts the set of all feasible routes to the subset of acceptable routes. This might include the avoidance of routes which are much longer than shortest routes, the exclusion of certain streets, preferences for scenic paths, or restrictions on the number of turns to be taken. Most remarkably is that the subset of acceptable routes can also be interpreted as a mental map of routes.
In the second part we apply our CMCF algorithms in a large scale multi-agent transportation simulation toolkit, which is called MATSIM-T. We use as initial routes the ones computed by our CMCF algorithms. This choice of initial routes makes it possible to exploit the optimization potential within the simulation much better then it was done before. The result is a speed up of the iteration process in the simulation. We compare the existing simulation toolkit with the new integration of CMCF to proof our results. Weniger anzeigen

An L-length-bounded cut in a graph G with source s, and sink t is a cut that destroys all s-t-paths of length at most L. An L-length-bounded flow is a flow in which only flow paths of length at most L are used. We show that the minimum length-bounded cut problem in graphs with unit edge lengths is NP-hard to approximate within a factor of at least 1.1377 for L ≧ 5 in the case of node-cuts and for L ≧ 4 in the case of edge-cuts. We also give approximation algorithms of ratio min{L, n/L} in the… Mehr anzeigen

An L-length-bounded cut in a graph G with source s, and sink t is a cut that destroys all s-t-paths of length at most L. An L-length-bounded flow is a flow in which only flow paths of length at most L are used. We show that the minimum length-bounded cut problem in graphs with unit edge lengths is NP-hard to approximate within a factor of at least 1.1377 for L ≧ 5 in the case of node-cuts and for L ≧ 4 in the case of edge-cuts. We also give approximation algorithms of ratio min{L, n/L} in the node case and min{L, n2/L2,√m} in the edge case, where n denotes the number of nodes and m denotes the number of edges. We discuss the integrality gaps of the LP relaxations of length-bounded flow and cut problems, analyze the structure of optimal solutions, and present further complexity results for special cases. Weniger anzeigen

We discuss the problem of computing routes for ships. Depending on the weather situation and the sea state we try to find a route that minimizes the fuel consumption of a ship. Additionally, parameters such as the rolling angle of a ship have to be kept below a given bound on the route to be computed.
We distinguish two scenarios: the common routing and the disaster scenario. In the first case, there is a fixed point in time up to which the destination has to be reached. In the case of a… Mehr anzeigen

We discuss the problem of computing routes for ships. Depending on the weather situation and the sea state we try to find a route that minimizes the fuel consumption of a ship. Additionally, parameters such as the rolling angle of a ship have to be kept below a given bound on the route to be computed.
We distinguish two scenarios: the common routing and the disaster scenario. In the first case, there is a fixed point in time up to which the destination has to be reached. In the case of a ship disaster, we have to solve the problem of reaching the nearest refuge in the shortest possible time and coping with limited manoeuvring capabilities.
To solve the problem, we suggest a discretized network which models turning possibilities of ships on the sea. In this network, nodes are associated with costs. The costs vary with the turning angle and the following three parameters: wave height, wave period, wave direction. These parameters are time-dependent and can be derived from the weather forecast. Obviously, the forecast is less reliable when the point in time to which it refers is further away in the future.
We present routing algorithms for this dynamic network setting. The algorithms will be part of a weather and sea routing advice decision support system for ships. Weniger anzeigen

We study an acceleration method for point-to-point shortest-path computations in large and sparse directed graphs with given nonnegative arc weights. The acceleration method is called the arc-flag approach and is based on Dijkstra’s algorithm. In the arc-flag approach, we allow a preprocessing of the network data to generate additional information, which is then used to speedup shortest-path queries. In the preprocessing phase, the graph is divided into regions and information is gathered on… Mehr anzeigen

We study an acceleration method for point-to-point shortest-path computations in large and sparse directed graphs with given nonnegative arc weights. The acceleration method is called the arc-flag approach and is based on Dijkstra’s algorithm. In the arc-flag approach, we allow a preprocessing of the network data to generate additional information, which is then used to speedup shortest-path queries. In the preprocessing phase, the graph is divided into regions and information is gathered on whether an arc is on a shortest path into a given region. The arc-flag method combined with an appropriate partitioning and a bidirected search achieves an average speedup factor of more than 500 compared to the standard algorithm of Dijkstra on large networks (1 million nodes, 2.5 million arcs). This combination narrows down the search space of Dijkstra’s algorithm to almost the size of the corresponding shortest path for long-distance shortest-path queries. We conduct an experimental study that evaluates which partitionings are best suited for the arc-flag method. In particular, we examine partitioning algorithms from computational geometry and a multiway arc separator partitioning. The evaluation was done on German road networks. The impact of different partitions on the speedup of the shortest path algorithm are compared. Furthermore, we present an extension of the speedup technique to multiple levels of partitions. With this multilevel variant, the same speedup factors can be achieved with smaller space requirements. It can, therefore, be seen as a compression of the precomputed data that preserves the correctness of the computed shortest paths. Weniger anzeigen

We study acceleration methods for point-to-point shortest path and constrained shortest path computations in directed graphs, in particular in road and railroad networks. Our acceleration methods are allowed to use a preprocessing of the network data to create auxiliary information which is then used to speed-up shortest path queries. We focus on two methods based on Dijkstra’s algorithm for shortest path computations and two methods based on a generalized version of Dijkstra for constrained… Mehr anzeigen

We study acceleration methods for point-to-point shortest path and constrained shortest path computations in directed graphs, in particular in road and railroad networks. Our acceleration methods are allowed to use a preprocessing of the network data to create auxiliary information which is then used to speed-up shortest path queries. We focus on two methods based on Dijkstra’s algorithm for shortest path computations and two methods based on a generalized version of Dijkstra for constrained shortest paths. The methods are compared with other acceleration techniques, most of them published only recently.We also look at appropriate combinations of different methods to find further improvements. For shortest path computations we investigate hierarchical multiway-separator and arc-flag approaches. The hierarchical multiway-separator approach divides the graph into regions along a multiway-separator and gathers information to improve the search for shortest paths that stretch over several regions. A new multiway-separator heuristic is presented which improves the hierarchical separator approach. The arc-flag approach divides the graph into regions and gathers information on whether an arc is on a shortest path into a given region. Both methods yield significant speed-ups of the plain Dijkstra’s algorithm. The arc flag method combined with an appropriate partition and a bi-directed search achieves an average speed-up of up to 1,400 on large networks. This combination narrows down the search space of Dijkstra’s algorithm to almost the size of the corresponding shortest path for long distance shortest path queries. For the constrained shortest path problem we show that goal-directed and bi-directed acceleration methods can be used both individually and in combination. The goal-directed search achieves the best speed-up factor of 110 for the constrained problem. Weniger anzeigen

In this paper, we consider Dijkstra’s algorithm for the point-to-point shortest path problem in large and sparse graphs with a given layout. In [1], a method has been presented that uses a partitioning of the graph to perform a preprocessing which allows to speed-up Dijkstra’s algorithm considerably.
We present an experimental study that evaluates which partitioning methods are suited for this approach. In particular, we examine partitioning algorithms from computational geometry and compare… Mehr anzeigen

In this paper, we consider Dijkstra’s algorithm for the point-to-point shortest path problem in large and sparse graphs with a given layout. In [1], a method has been presented that uses a partitioning of the graph to perform a preprocessing which allows to speed-up Dijkstra’s algorithm considerably.
We present an experimental study that evaluates which partitioning methods are suited for this approach. In particular, we examine partitioning algorithms from computational geometry and compare their impact on the speed-up of the shortest-path algorithm. Using a suited partitioning algorithm speed-up factors of 500 and more were achieved.
Furthermore, we present an extension of this speed-up technique to multiple levels of partitionings. With this multi-level variant, the same speed-up factors can be achieved with smaller space requirements. It can therefore be seen as a compression of the precomputed data that conserves the correctness of the computed shortest paths. Weniger anzeigen

We introduce a novel model for "Fows over time" which captures the behavior of cars traveling through a road network better than previous models. We show that computing an optimal solution in the new model is NP-hard and present an LP-based algorithm which we evaluate with several experiments on real world data of road networks and generated requests. Among other things we compare the quality of the solutions with solutions generated by an FPTAS for a related but considerably less realistic… Mehr anzeigen

We introduce a novel model for "Fows over time" which captures the behavior of cars traveling through a road network better than previous models. We show that computing an optimal solution in the new model is NP-hard and present an LP-based algorithm which we evaluate with several experiments on real world data of road networks and generated requests. Among other things we compare the quality of the solutions with solutions generated by an FPTAS for a related but considerably less realistic model. Weniger anzeigen