IBTS-77-RP-1000
Single Networks
Foot network :The construction of the model of the foot network is straightforward. Junctions are represented by nodes, and arcs between two nodes exist if there is a footpath between two junctions. Arc costs depend on geographical length and on average pedestrian walking speed. Labels on arcs mark the type of path, such as side-way, stairs, trail, etc.
Bicycle network :The bicycle network is constructed in a similar way to the foot network. Nodes represent road junctions and arcs are inserted into the graph whenever biking is allowed between two junctions. Different road types for cycling exist, such as roads with a separate cycling path, roads with a separate lane for cyclists which are shared with buses, roads shared with general traffic, etc. Arcs may be labeled accordingly. Arc costs represent cycling time and depend on geographical length and on average cycling speed.
Road network :For the road network, nodes represent road junctions and arcs represent roads connecting the junctions. Different road types exist, e.g., local roads, urban roads, inter-urban roads, motorways, toll roads, etc. Arc costs may be time-dependent and represent travel time which depends on the geographical length, the speed limits, and the traffic conditions .
Public transportation network :A public transportation network consists of buses, subways, tramways, ferries, local trains, etc. Several approaches for modeling a public transportation network exist. We will shortly introduce the condensed, the time-expanded, and the time-dependent model. We refer to for an in-depth discussion. All these models are based on a timetable. We will introduce this concept first.
Rental bicycle and rental car networks
Major cities in recent years have adopted bicycle rental systems, e.g., Paris (France), London (UK), Washington DC (US), Hangzhou (China). Besides providing affordable access to bicycles for short-distance trips in an urban area as an alternative to motorized vehicles, these systems are also supposed to cover the Last Kilometer, i.e., the distance between public transportation stops and the departure or final location. For this reason, they are an important component of a multi-modal transportation network. We consider bicycle sharing systems with fixed rental stations, like the bicycle sharing systems in operation in Paris2 or Washington DC3. In such systems, users retrieve and return bicycles at bicycle rental stations distributed evenly over the served area. Each rental station v is characterized by a maximal number of bicycles it can hold c max v ∈ Z+. Bicycle rental costs may also be an important characteristic of a rental bicycle system. The modeling of a rental bicycle system is straightforward. It uses the bicycle network, and nodes representing locations near bicycle rental stations are labeled accordingly. Shortest path queries are only allowed between these labeled nodes.
Recently, similar rental principles have been adapted to rental car systems. See for example the Autolib’ system in Paris which offers electric cars to rent for short trips. The modeling of a rental car system is similar to the modeling of a bicycle rental system, but instead of using the bicycle network, the car network is used. Nodes of the car network next to car rental stations are labeled accordingly.
Labeling Method
The labeling method for the shortest path [56] finds shortest paths from a source node r to all other nodes in a graph. It works as follows: it maintains for every node v a tentative distance label d(v), a parent node p(v), and a status S(v). A status of a node can be unreached, explored, or settled. Initially, for every node v, d(v) = ∞, p(v) = nil, and S(v) = unreached. The algorithm starts by setting d(r) = 0 and S(v) = explored. At every successive iteration, the algorithm selects a node with status explored, it relaxes all outgoing arcs, and sets its status to settled. Relaxing an arc (v, w) means to first check if d(w) > d(v) + cvw, and, if that is the case, to set d(w) = d(v) + cvw, p(w) = v, and S(w) = explored. The algorithm terminates when there are no more nodes with status explored and if the graph does not contain cycles with negative cost, it produces a shortest path tree, i.e., all distances and shortest paths starting at the source node r to all other nodes of the graph. The shortest path to a node v can be retrieved by following the parent nodes backward starting at v.
Label setting methods and Dijkstra’s algorithm
The order in which the next node to be scanned is selected highly influences the efficiency of the labeling method. On a static graph with non-negative arc cost, it is easy to see that if the algorithm always selects nodes v for which d(v) corresponds exactly to the shortest distance between r and v, then each node is scanned at most once and arcs (w, v) for which the status of v is settled have to not be relaxed. In this case, the algorithm is called label setting. If the cost function is non-negative and the node to be explored at each step is the one with smallest distance label d(v), then d(v) will correspond exactly to the shortest distance between r and v. This has first been observed by Dijkstra and the labeling method with minimum distance label selection rule is referred to as Dijkstra’s algorithm, which we will call Dijkstra. It scans nodes in non-decreasing order of distance to the source node r. The algorithm terminates as soon as the target node t is assigned the status settled.
Complexity depends on the priority queue used to hold the distance labels. Runtime is in O(|E| + |V | log |V |) if a Fibonacci heap is used and O((|E| + |V |) log |V |) if a binary heap is used. Computing the shortest path from r with starting time τstart on a graph with time-dependent arc costs can be solved by a slightly modified algorithm: when relaxing arc (v, w), it evaluates arc costs for time τstart + d(v), so d(w) = d(v) + cvw(τstart + d(v)) . Dijkstra can also be applied to dynamic networks .
Label correction methods
We will call label correcting methods those labeling methods which may update distance labels for nodes with status settled. In this case, a distance label may be re-inserted in the priority queue, and the status of a node may change from settled back to explored multiple times. On a time-dependent graph, label-correcting algorithms may be used to compute the distant function between d∗(r, t) : T → (R), d∗(r, t)(τ ) = d(r, t, τ ), which finds the cost of the shortest path for every starting time τ ∈ T . It is implemented similarly to Dijkstra, but uses functions instead of scalars as distance labels. Dijkstra works correctly only on graphs with non-negative arc costs. To find shortest paths on graphs with negative arc costs, the Bellman-Ford algorithm can be used. In its basic structure it is similar to Dijkstra algorithm, but instead of selecting the minimum-weight node not yet processed to relax, it simply relaxes all the arcs, and does this |V | − 1 times. Runtime of Bellman-Ford is in O(|V ||E|). Note that if a graph contains a negative cycle, i.e., a cycle with total negative arc cost, then paths of arbitrarily low weight can be constructed by repeatedly following the cycle. Such cases can be detected by the Bellman-Ford algorithm, but a correct shortest path cannot be produced.One variant of SDALT will use the label correction method .
Uni-Modal Routing
Routing on road networks :Running times of Dijkstra on large road networks are far too high for practical application. In the early years of the 2000s, huge road networks were made publicly available which stimulated widespread research on speed-up techniques for Dijkstra. This culminated in the 9th DIMACS Challenge on shortest paths , where many new fundamental works on efficiently finding shortest paths were presented. Three basic components are common to many speed-up techniques of shortest path algorithms on road networks: bi-directional search, goal-directed search, and contraction . Also table lookups are becoming increasingly relevant. The fastest search techniques use a combination of these basic components. In the following, we will introduce these basic components as well as some of the more recent fast algorithms. Relevant for this work are bi-directional search and goal-directed search (the ALT algorithm).
Bi-directional search. When applying bi-directional search, two searches are started, one starting at the source node and another starting at the target node. The search stops when the two searches meet and the shortest path is the concatenation of the partial paths produced by the two searches. This approach has been introduced and refined by .
Bi-directional search is quite a simple technique and works well on static graphs with no time-dependent cost functions. Its application on time-dependent graphs is more complicated .
Goal-directed search. The ALT algorithm is a goal directed search as it preferably settles nodes that are close to the target. It combines the characteristics of the A algorithm, the use of landmarks, and the triangle inequality, and is very robust and works in dynamic and time-dependent scenarios. A second goal directed approach on static networks is called Geometric Containers . This approach has been enhanced by yielding the Arc-Flags algorithm. Here arcs of the network are explored by the search only if they are relevant for shortest paths toward nodes near the target node. The algorithm PCD exploits precomputed distances between clusters of the graph to produce upper and lower bounds on the distance to the target to reduce the search space. All these search techniques require a preprocessing phase. Usually there is a trade-off between memory size of preprocessed data and query time.
|
Table des matières
1 Introduction
1.1 Introduction
1.2 Contribution
1.3 Overview
2 Definitions and Notations
2.1 Languages and Automata
2.2 Graph Theory
2.3 Shortest Path Problem
2.4 Summary
3 Network Modeling
3.1 Single Networks
3.1.1 Foot network
3.1.2 Bicycle network
3.1.3 Road network
3.1.4 Public transportation network
3.1.5 Rental bicycle and rental car networks
3.1.6 Locations of interest
3.2 Multi-Modal Network
3.3 Application
3.3.1 Multi-modal transportation network IDF (Ile-de-France)
3.3.2 Multi-Modal Transportation Network NY (New York City)
3.4 Summary
4 Shortest Path Problem
4.1 Labeling Method
4.1.1 Label setting methods and Dijkstra’s algorithm
4.1.2 Label correction methods
4.2 Uni-Modal Routing
4.2.1 Bi-directional search
4.2.2 The ALT algorithm
4.3 Multi-Modal Routing
4.3.1 Regular language constrained shortest path problem
4.3.2 Algorithm to solve RegLCSP
4.4 Summary
5 SDALT
5.1 State Dependent ALT: SDALT .
5.1.1 Query phase
5.1.2 Preprocessing phase
5.1.3 Constrained landmark distances
5.2 Label Setting SDALT: lsSDALT
5.2.1 Feasible potential functions
5.2.2 Correctness
5.2.3 Complexity and memory requirements
5.3 Label Correcting SDALT: lcSDALT
5.3.1 Query
5.3.2 Correctness
5.3.3 Constrained landmark distances
5.3.4 Complexity and memory requirements
5.4 Bi-directional SDALT: biSDALT
5.4.1 Query
5.4.2 Constrained landmark distances and potential function
5.4.3 Correctness .
5.4.4 Memory requirements
5.5 Experimental Results
5.5.1 Test instances
5.5.2 Discussion
5.6 Summary
6 2-Way Multi-Modal Shortest Path Problem
6.1 Problem Definition
6.2 Basic Algorithm
6.2.1 Correctness
6.2.2 Complexity
6.3 Speed-up Techniques
6.4 Experimental Results
6.5 Summary
7 Dial-A-Ride
7.1 Introduction
7.2 The dial-a-ride problem
7.3 Solution Framework
7.3.1 The granular neighborhood
7.3.2 Preprocessing
7.3.3 Initial Solution
7.3.4 Local search
7.3.5 Tabu list and aspiration criteria
7.3.6 Diversification and intensification
7.3.7 Stopping criterion
7.4 Experimental Results
7.4.1 Test instances
7.4.2 Evaluation of Granular Tabu Search
7.4.3 Comparison on f'(s)
7.4.4 Comparison on f »(s)
7.4.5 Discussion
7.5 Summary
8 Conclusions
Télécharger le rapport complet
