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