Project topics and materials
Get Complete Project Material File(s) Now! »
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 aordable 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 nal location. For this reason, they are an important component of a multi-modal transportation network.
Multi-Modal Network 19
We consider bicycle sharing systems with xed rental stations, like the bicycle sharing systems in operation in Paris2 orWashington 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 cmax v 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 oers 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 suces 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. However, a user might not specify the precise geographical location of this stop and just wish to pass by any pharmacy, post-oce, 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 modeling 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 dierent networks described in the previous section into a single multi-modal network. This requires the choice of the locations at which dierent networks meet (e.g., public transportation stations, parking places). Once the locations are identied the networks have to be linked by the insertion of transfer arcs between nodes of dierent networks. A technical diculty is the identication of nodes which are located close to each other in a graph. We discuss this problem rst.
Table of contents :
1 Introduction 1
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
