Project topics and materials
Get Complete Project Material File(s) Now! »
Single Networks
In this section, we introduce approaches to model foot, bicycle, road, and public transporta-tion networks.
Foot network
The construction of the model of the foot network is straightforward. Junctions are rep-resented by nodes, and arcs between two nodes exist if there is a footpath between two junctions (see Figure 3.1 for an example). 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. Di erent 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 tra c, etc. Arcs may be labeled accordingly. Arc costs represent cycling time and depend on geographical length and on average cycling speed. See [114] for information about multi- critera routing on cycling networks and for advanced graph modeling of cycling networks which also consider security aspects1.
Road network
For the road network, nodes represent road junctions and arcs represent roads connecting the junctions. Di erent 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 tra c conditions (see Figure 3.2 for an example of a cost function and Section 3.3.1 for more information about tra c data).
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 [107, 117] for an in depth discussion. All these models are based on a timetable. We will introduce this concept rst.
Condensed model
A simple approach to model a public transportation system is the use of the condensed model. It represents the network structure but not the scheduling, thus it is non time dependent. Examples of condensed models are subway or bus maps which only indicate stations, connections, and lines, but no departure or travel times. Every station s 2 B is represented by exactly one node v 2 V in the graph. An arc (si; sj) is introduced if and only if at least one elementary connection exists in the timetable that goes from station si to station sj. Arc costs are omitted or are de ned as the minimum travel time over all elementary connections from si to sj. The condensed model provides an overview of the structure of the public transportation system but is not useful for exact shortest path
calculations.
Time-expanded model
A more complete representation of a public transportation system provides the time-expanded model. Two versions exist: a simple version and a realistic version. The latter incorporates realistic transfer times between two vehicles at stations. Simple version. Nodes represent departure events and arrival events. For each elementary connection c = (z; s1; s2; 1; 2) two nodes are created: a departure node v, which represents the departure event of vehicle z at station s1 at time 1, and an arrival node u which represents the arrival event of vehicle z at station s2 at time 2. Each node is assigned its station s and its timestamp when the event occurs. Two types of arcs exist, travel arcs and internal station arcs. A travel arc connects the node representing the departure event with the node representing the arrival event of an elementary connection c. The arc cost represents travel time and is set to ( 1; 2). Internal station arcs are only inserted between nodes which are associated with the same station. First, all nodes associated with the same station are sorted in ascending order with respect to their timestamp; we obtain an ordered series of nodes (v1; : : : ; vk). Then for two subsequent nodes vi, vj having timestamps i and j, a transfer arc e := (vi; vj) is inserted in the graph. It has arc cost ( i; j) which represents the waiting or transfer time between arrival and departure event. To allow transfers over the end of the period (midnight), an arc connecting the node vk with the latest timestamp and the node v1 having the lowest timestamp is inserted into the graph. See Figure 3.3 for an example.
Realistic version. The simple version is enhanced by inserting transfer nodes and transfer arcs to correctly model and include transfer times at stations. See Figure 3.3 for an example.
Time-dependent model
In the time-dependent model, travel times are represented by functions. Again two versions exist [107,117]: a simple and a realistic version. The realistic version incorporates transfer times. Simple version. The simple version is an expansion of the condensed model. There is a node for every station in B and an arc if there exists at least one elementary connection between the two stations represented by the node. Unlike the condensed model, arc costs are time-dependent and are represented by piecewise linear functions. For each elementary connection c = (Z; s1; s2; 1; 2) an interpolation point p = ( 1; ( 1; 2)) is added to the function f of the arc between stations s1 and s2. 1 is the departure time and ( 1; 2) the travel time. To evaluate the function f for a time point we apply the equation.
Rental bicycle and rental car networks
Major cities in recent years have adopted bicycle rental systems, e.g., Paris (France), Lon-don (UK), Washington DC (US), Hangzhou (China). Besides providing a ordable 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 pub-lic transportation stops and the departure or nal location. For this reason, they are an important component of a multi-modal transportation network.
We consider bicycle sharing systems with xed 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 cmaxv 2 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’ system4 in Paris which o ers 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. Availability of rental vehicles. Rental vehicles are subject to availability. Furthermore, they can only be returned at stations with free return slots. This information must be known before a shortest path query is started. It is easy to incorporate this constraint in the Dijkstra algorithm. It su ces to assign a ag to each node v labeled as a station, which is true, if rental vehicles are available (fbike avail(v) = true), and a second ag which is true if return slots are available (ffree slots(v) = true). The ags have to be updated periodically.
Locations of interest
The user may want to pass by an intermediate stop before reaching the target location. How-ever, a user might not specify the precise geographical location of this stop and just wish to pass by any pharmacy, post-o ce, supermarket, etc. In this case, the route planning service has to determine autonomously the exact location of the intermediate stop and adapt the path between source and target location accordingly. We use the following simple approach to include information about such locations of interest in a graph. We duplicate arcs mod-eling roads on which locations of interest are located and we substitute the assigned label with a new label indicating the presence of, e.g., a pharmacy along a footpath. Note that in this way no information on the time spent at the location of interest can be incorporated in the model. However, this can easily be done by appropriately expanding the graph and by modeling a location of interest through the insertion of additional nodes.
Multi-Modal Network
In this section, we combine the di erent networks described in the previous section into a single multi-modal network. This requires the choice of the locations at which di erent networks meet (e.g., public transportation stations, parking places). Once the locations are identi ed the networks have to be linked by the insertion of transfer arcs between nodes of di erent networks. A technical di culty is the identi cation of nodes which are located close to each other in a graph. We discuss this problem rst. Let Rn be the n-dimensional vector space over R and P Rn a nite set of vectors. The set P is called candidate points. Let d : R ! R be a metric on Rn.
Table of contents :
1 Introduction
1.1 Introduction
1.2 Contribution
1.3 Overview
2 Denitions 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 Denition
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 Diversication and intensication
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 f0(s)
7.4.4 Comparison on f00(s)
7.4.5 Discussion
7.5 Summary
8 Conclusions
