=Paper=
{{Paper
|id=Vol-2144/paper6
|storemode=property
|title=Multimodal Shortest Path Algorithm for Carsharing Systems with Operation Area Constraint
|pdfUrl=https://ceur-ws.org/Vol-2144/paper6.pdf
|volume=Vol-2144
|authors=Wesam Herbawi,Stefan Landsbek
}}
==Multimodal Shortest Path Algorithm for Carsharing Systems with Operation Area Constraint==
https://ceur-ws.org/Vol-2144/paper6.pdf
Multimodal Shortest Path Algorithm for Carsharing
Systems with Operation Area Constraint
Wesam Herbawi and Stefan Landsbek
moovel Lab
moovel Group GmbH
Stuttgart, Germany
Email: firstname.lastname@moovel.com
a short period for the duration of their trips. This
kind of systems is gaining more and more interest and
Abstract widespread recently.
The types of car sharing systems vary according to
This paper studies the problem of computing the constraints imposed by the system operator. Free
the shortest path in free floating carsharing floating one-way carsharing (simply called free float-
systems with operation area constraint. In ing carsharing) is the most flexible type of carsharing
this type of systems, The shortest path, be- where the user can rent a vehicle and return it at any
tween a given source and destination points, place within the operation area of the carsharing sys-
consists of a walking part from the source to tem operator. The operation area is usually defined as
some carsharing vehicle, then a driving part, a multipolygon with included and excluded geographi-
probably, followed by a final walking part to cal areas. Example free floating carsharing systems are
the destination. The return of carsharing ve- car2go (www.car2go.com) and DriveNow (www.drive-
hicles is limited by an operation area con- now.com).
straint represented as geographical multipoly- Finding the shortest path in such systems is a mul-
gon. timodal shortest path problem with the modes walk
In this work we propose a multimodal short- and drive. It includes finding a walking path from the
est path algorithm that takes the operation source to a nearby vehicle, then a driving path to the
area constraint into consideration to solve the destination point. Often the destination point is not
shortest path problem in free floating carshar- directly accessible by driving mode. It could be out-
ing. The proposed algorithm has been tested side the operation area of the carsharing operator or
using real world carsharing data. Experimen- it could be within a pedestrian zone. In both cases, a
tation results showed that the algorithm was final walking path has to be computed.
able to successfully solve the problem and The multimodal shortest path problem has been
cope with the different problems settings in widely studied. In [Paj09, HJ13, YL12], different solu-
reasonable time suitable for online applica- tion approaches for the multimodal shortest path prob-
tions. lem have been proposed considering different modes
including walk, drive and public transport. The driv-
1 Introduction ing mode was supposed to be possible everywhere on
the street network as long as the street types allow for
A carsharing system consists of a fleet of vehicles dis- driving. This is because the driving mode was thought
tributed throughout the city and available to the sys- for private car or for a taxi. However, to the best of
tem users for rental on a short notice and usually for our knowledge, no work has considered the multimodal
shortest path problem for carsharing where the driving
Copyright c by the paper’s authors. Copying permitted for
mode cannot be started and ended everywhere on the
private and academic purposes.
street network, nonetheless, limited by the availability
In: A. Editor, B. Coeditor (eds.): Proceedings of the XYZ
Workshop, Location, Country, DD-MMM-YYYY, published at of vehicles and by the operation area constraint.
http://ceur-ws.org In this work, we integrate the operation area con-
1
located on a street where no detour is required to head
toward the destination. This problem is a multimodal
shortest path problem where a switch between differ-
ent modes of transport is required. The shortest path
might include a walk to some carsharing vehicle fol-
lowed by a drive segment and ends with another walk
segment. The operation area constraint is a new com-
ponent to this type of problems and to our knowledge,
this is the first work to consider such constraint. In
the following, we provide the modeling of the different
components of the problem.
The street network is represented as a diagraph
G = (V, E), E ⊆ V × V . We assume that the set of
nodes V consists of integer values in the range [0, |V |).
We use the functions w and d : E → {true, f alse} to
denote if an edge e ∈ E is accessible by walk and
Figure 1: Sample free floating carsharing system set-
drive modes respectively. Edges E are annotated with
tings. A set of vehicles distributed through the city
travel time for both modes walk and drive. We use
along with a multipolygon operation area constraint.
the functions timew and timed : E → R≥0 to denote
Data is taken from car2go. Blue icons are car2go vehi-
the travel times of an edge e ∈ E for the modes
cles (clustered for visualization purposes) and the blue
walk and drive respectively with the following hold
multipolygon represents the main part of the operation
w(e) ⊕ (timew (e) = ∞) and d(e) ⊕ (timed (e) = ∞) i.e.
area.
if an edge e is not accessible for some mode, then the
straint in the graph representation of the street net- travel time of that mode on e is infinity.
work and propose a multimodal shortest path algo- For each carsharing vehicle, we find the geographi-
rithm to answer shortest path queries of the form walk- cally closest node v ∈ V to get the set C ⊆ V of nodes
carsharing-walk. The algorithm takes the operation that will represent the carsharing vehicles in our graph
area constraint into consideration while computing the G. New nodes are added to V if necessary, to represent
multimodal shortest path. vehicles that are located close to long edges and far
The rest of the paper is organized as follows. We from the end nodes of the edges. Using the operation
describe the problem in more details in Section 2. The area multipolygon, we generate the set of nodes that
proposed algorithm is explained in Section 3 followed are geographically withing the operation area. This
by the experimentation and results in Section 4. Fi- set is denoted by O = {v ∈ V | v is geographically
nally, we outline the conclusions of the paper. within operation area}, C ⊆ O ⊆ V .
2 Problem description and modeling 3 The proposed algorithm
Typically, a free floating carsharing system has a set To solve the multimodal shortest path problem in free
of vehicles on specific geolocations and a geographical floating carsharing, we propose an extension of Di-
multipolygon defining the operation area of the car- jkstra algorithm [Dij59], that alternates between the
sharing system as shown in Figure 1. Carsharing rental modes walk and drive, and takes the operation area
can be started everywhere where a vehicle is available constraint into consideration. Algorithm 1 is a pseu-
and can be ended only within the operation area de- docode representation of the proposed algorithm.
fined by the multipolygon. The task is to find the Algorithm 1 follows the basic structure of Dijkstra
shortest path on the street network between a given algorithm. However, the different modes of travel and
source s and target t points (later will be denoted the operation area constraint have to be taken into
nodes) using the modes walk and drive. The mode consideration. The mode switch (from walk to drive
walk can be used everywhere on the street network as and vice versa) and its trigger has to be handled in
long as the street types allow for walk mode. A switch the algorithm. In comparison to single mode short-
from walk mode to drive mode can be triggered only est path problem, in multimodal shortest path, the
if a carsharing vehicle is reached. Obviously the walk same node could have different predecessors at the
mode cannot be simply stopped after reaching a car- same time (namely, one per travel mode) as shown in
sharing vehicle. It might be necessary to walk a bit Figure 2. This happens, for example, when the system
farther to reach another carsharing vehicle that might user has to walk in some direction to reach a vehicle
result in the shortest path. Such a vehicle might be and then drive back the same way. This behavior will
2
result in some nodes, where the same node is reached
at different durations from different predecessor nodes
and despite that the different predecessors have to be
accepted as valid predecessors. In single mode shortest
path, this behavior is not allowed. If node x is reached
through predecessor y with duration d1 , then no pre-
decessor for x will be accepted with duration d2 ≥ d1 .
Algorithm 1: Multimodal Operation Area Aware An edge base traversal Dijkstra will manage to solve
Dijkstra the problem depicted in Figure 2. However, it will fail
in handling the case where the same edge has to be
begin
reached both by walk and drive even if the drive mode
Input: G = (V, E) source s ∈ V target t ∈ V
results in less duration. Walking a bit farther might
vehicle nodes C ⊆ V Operation area
result in the shortest path as explained earlier in this
nodes O ⊆ V
section.
Output: Multimodal shortest path tree
rooted at s At the early stages of the algorithm, it behaves as
1 Q ← Priority Queue a typical Dijkstra exploring G in the walk mode (lines
2 Q.insert(s,0) 10 − 17). A mode switch from walk to drive is trig-
3 d[i] ← ∞, i ∈ 0, 1, .., 2 |V | gered once a node v ∈ C is settled (removed from
4 d[s] ← 0 the priority queue). This means a carsharing vehi-
5 while !Q.isEmpty() do cle is reached, and from there one can start driving
6 v ← Q.dequeue() mode (line 18). Once we start exploring G in drive
7 if v = t or ((v mod |V | = t) and t ∈ O) mode, we might face the problem depicted in Figure
then 2. Node b has already been reached through a with
8 Stop duration timew ((a, b)). Once the node c is settled, we
can start exploring in mode drive. Now the algorithm
9 for each e = (v mod |V | , u) ∈ E do tries to reach node b through node c with a total dura-
10 if v < |V | or v mod |V | ∈ O then tion of timew ((a, b)) + timew ((b, c)) + timed ((c, b)) ≥
11 tmpD ← d[v] + timew (e) timew ((a, b)). In a single mode shortest path, this step
12 if tmpD < d[u] then is not allowed as b has already been reached with less
13 if d[u] = ∞ then duration through a. However, in our case, this step
14 Q.insert(u, tmpD) should be allowed as the vehicle has to be reached first
else and the shortest path might be the one with the ve-
15 Q.decreaseKey(u, tmpD) hicle driving back the walk path. The algorithm han-
16 d[u] ← tmpD dles that by making local graph copies. For each node
17 pred[u] ← v v ∈ V that is to be explored in drive mode, the algo-
rithm makes a copy of v and assign it the value v +|V |.
18 if v ∈ C or v ≥ |V | then Now the new node v +|V | can be reached with a higher
19 tmpD ← d[v] + timed (e) duration compared to its walk mode node v (lines 20
20 if tmpD < d[u + |V |] then − 25). Note that the node v + |V | preserves all the at-
21 if d[u + |V |] = ∞ then tributes and outgoing edges as (v + |V |) mod |V | = v.
22 Q.insert(u + |V |, tmpD) Now, any node v ≥ |V | indicates that the algorithm is
else exploring the driving mode. Hence, the condition at
23 Q.decreaseKey(u + line 18 indicates that we can explore nodes in driving
|V |, tmpD) mode either if the settled node is a vehicle node v ∈ C
24 d[u + |V |] ← tmpD or it is already a driving mode node v ≥ |V |.
25 pred[u + |V |] ← v The operation area constraint is enforced by the set
O. It is used to define a valid transition from the drive
mode to the walk mode in line 10. A transition from
drive to walk is allowed only if the settled drive node is
within the operation area (v + |V |) mod |V | = v ∈ O.
This means that a carsharing vehicle can be returned
only within the operation area. The set O is also used
to define a valid algorithm stop condition at line 8
where the solution is found. For a valid stop condition,
the settled node v has to be in a walk mode or the
3
d c
b
a
Figure 2: Multiple predecessors problem. Node b is
reached by walk mode (green) through a and by drive
mode (black) through c
destination has to be within the operation area, t ∈ O,
if v is in drive mode. It could happen that v ≥ |V | and Figure 3: Pictorial representation of the algorithm be-
v mod |V | = t but t ∈ / O. This means the destination havior. Green and Gray nodes are nodes inside and
is reached in drive mode but it is outside the operation, outside the operation area respectively. Dashed nodes
yet solution is not found. are the node copies. The node with black stroke rep-
What the algorithm conceptually does is shown in resents a vehicle node.
Figure 3. It splits the graph into two graphs, one for
walk and another for drive. The two graphs are bidi- destination points are within the operation area and
rectional connected at vehicle nodes and one direction- the destination is reachable by drive mode. The short-
ally connected, from drive to walk, at nodes within the est path consists of a walking part to reach a vehicle
operation area. The algorithm does that on the fly and followed by a drive part. No final walk is required
locally. Instead of splitting the whole graph into two as the destination is reachable by drive mode. The
graphs, the algorithm only splits the part of the graph destination point is outside the operation in 5(b) and
that is visited during the search. The visited part is therefore the destination has to be reached walking as
usually small compared to the size of the graph as car- the vehicle has to be returned within the operation
sharing trips are usually short distance. Also, this ap- area. 5(c) shows the result of the algorithm when the
proach is more suitable to the highly dynamic nature source is within one of the polygons defining the op-
of the problem as vehicles updates typically happen eration area and the destination is close to another
at least once a minute. The algorithm has the same polygon. The vehicle is returned in the polygon close
computational complexity, O(E log V ), as Dijkstra. It to the destination and a walking part to the desti-
operates in the same way as Dijkstra but on a larger nation is computed. A single mode walking result is
graph with a maximum graph size factor of 2 if the computed in 5(d) as the end points are close to each
whole graph is visited during the search. other. Often, carsharing providers exclude parts of the
operation and, hence, it is not allowed to return the
vehicle in such excluded parts. 5(e) shows the result
4 Experientation and Results when the destination is within an excluded area.
We have tested the proposed algorithm using real Table 1 summarizes the average runtime and num-
world carsharing data provided by car2go. The car2go ber of settled nodes for different scenarios of carshar-
dataset contains 945 vehicles operating in Berlin in ing trips. For each scenario, 10 different trips, between
an operation area as shown in Figure 4. The Open- randomly selected source and destination points, have
street map (OSM) data of Berlin is used to build the been computed. The trips are categorized as short and
street network graph. Our algorithm is implemented long distance. We consider trips of an average dis-
as an extra module plugged to Graphhoper (graphhop- tance 7-8km as short and trips of an average distance
per.com). Experiments are performed on a computer 23-27km as long. While both, short and long distance
with 4G RAM and 2.5GHz, 64bit dual core processor. trips in our study, are considered very short trips for
Figure 5 shows the results of the algorithm for dif- typical single mode routing, still a 23km trip in car-
ferent carsharing use cases. In 5(a), the source and sharing systems is considered a long one. The first sce-
4
Figure 4: Operation area of car2go in Berlin
Table 1: Experimentation Results. runtime in milliseconds, number of settled nodes, total trip distance of all
modes and the walk distance
drive walk-drive drive-walk
total walk total walk total walk
runtime settled runtime settled runtime settled
distance distance distance distance distance distance
Short 20 16551 7732 0 19 15761 7962 1039 60 51767 6975 1062
Long 61 49561 23514 0 60 50698 27230 1015 110 95402 23987 1060
nario of carsharing trips is the drive only trip where tination is reached. The algorithm settles all nodes
a carsharing vehicle is available directly at the source with duration less than the duration needed to reach
and can be returned at the destination. No walk is the destination and therefore it settles larger number
required. The second scenario is the walk-drive where of drive nodes as driving is usually faster and takes
some walk is needed to reach the vehicle and the des- less duration. This behavior does not happen when
tination can be directly reached by the vehicle. In the the walking part is at the beginning of the trip even
last scenario, drive-walk, the vehicle is directly avail- that it results in longer trip duration. This is because,
able at the source but some walk is needed at the end a walk at the beginning of the trip means that a vehi-
to reach the destination. cle is not reached yet and drive mode is not active. So
the algorithm mainly expands walking nodes.
We notice that there is no considerable difference in
the runtime and the number of settled nodes between
5 Final remark
the scenarios drive and walk-drive. However, a consid-
erable higher runtime and number of settled nodes for In this work we have proposed an algorithm for the
drive-walk on both short and long trips. This is be- multimodal shortest path problem in free-floating car-
cause, when the destination is not directly reachable sharing systems with operation area constraint. The
by the vehicle, either because of being in a pedestrian algorithm has been tested, under different trip sce-
zone or outside the operation area, the algorithm set- narios, using real world carsharing data. Test results
tles high number of drive mode nodes. It could hap- showed that the algorithm was able to efficiently solve
pen that the algorithm reaches the destination in drive the problem.
mode but cannot stop the search as it is outside the op- An interesting extension of this work is to combine
eration area. The algorithm then has to explore more the carsharing routing with public transport. This is
walk nodes to reach the destination. As the walk mode very interesting especially if the destination is far from
is slower than the drive mode, walk mode nodes get the operation area, then a last mile public transport
less priority in the priority queue, as they have higher could be taken instead of walking. This will affect the
duration, and the algorithm tends to settle more and return point near the borders of the operation area
more drive mode nodes. In other words, having a walk depending on the availability of public transport stops
at the end results in longer trip duration till the des- and trips.
5
(a) source and destination are within the operation (b) destination is outside the operation area
area
(c) destination is outside the operation area and close (d) close source and destination
to a polygon other than the polygon of the source
(e) destination is in excluded polygon
Figure 5: Algorithm results for different carsharing use cases based on different positions of the source (green)
and destination (red). Green is walk and black is drive.
6
References
[Dij59] Edsger W Dijkstra. A note on two problems
in connexion with graphs. Numerische math-
ematik, 1(1):269–271, 1959.
[HJ13] Jan Hrncir and Michal Jakob. Generalised
time-dependent graphs for fully multimodal
journey planning. In Intelligent Transporta-
tion Systems-(ITSC), 2013 16th International
IEEE Conference on, pages 2138–2145. IEEE,
2013.
[Paj09] Thomas Pajor. Multi-modal route planning.
Universität Karlsruhe, 2009.
[YL12] Haicong Yu and Feng Lu. A multi-modal route
planning approach with an improved genetic
algorithm. Advances in Geo-Spatial Informa-
tion Science, 1:0, 2012.
7