This paper studies the problem of computing the shortest path in free oating carsharing systems with operation area constraint. In this type of systems, The shortest path, between a given source and destination points, consists of a walking part from the source to some carsharing vehicle, then a driving part, probably, followed by a nal walking part to the destination. The return of carsharing vehicles is limited by an operation area constraint represented as geographical multipolygon. In this work we propose a multimodal shortest path algorithm that takes the operation area constraint into consideration to solve the shortest path problem in free oating carsharing. The proposed algorithm has been tested using real world carsharing data. Experimentation results showed that the algorithm was able to successfully solve the problem and cope with the di erent problems settings in reasonable time suitable for online applications.
A carsharing system consists of a eet of vehicles distributed throughout the city and available to the system users for rental on a short notice and usually for a short period for the duration of their trips. This kind of systems is gaining more and more interest and widespread recently.
The types of car sharing systems vary according to the constraints imposed by the system operator. Free oating one-way carsharing (simply called free oating carsharing) is the most exible type of carsharing where the user can rent a vehicle and return it at any place within the operation area of the carsharing system operator. The operation area is usually de ned as a multipolygon with included and excluded geographical areas. Example free oating carsharing systems are car2go (www.car2go.com) and DriveNow (www.drivenow.com).
Finding the shortest path in such systems is a multimodal shortest path problem with the modes walk and drive. It includes nding a walking path from the source to a nearby vehicle, then a driving path to the destination point. Often the destination point is not directly accessible by driving mode. It could be outside the operation area of the carsharing operator or it could be within a pedestrian zone. In both cases, a nal walking path has to be computed.
The multimodal shortest path problem has been widely studied. In [Paj09, HJ13, YL12], di erent solution approaches for the multimodal shortest path problem have been proposed considering di erent modes including walk, drive and public transport. The driving mode was supposed to be possible everywhere on the street network as long as the street types allow for driving. This is because the driving mode was thought for private car or for a taxi. However, to the best of our knowledge, no work has considered the multimodal shortest path problem for carsharing where the driving mode cannot be started and ended everywhere on the street network, nonetheless, limited by the availability of vehicles and by the operation area constraint.
In this work, we integrate the operation area constraint in the graph representation of the street network and propose a multimodal shortest path algorithm to answer shortest path queries of the form walkcarsharing-walk. The algorithm takes the operation area constraint into consideration while computing the multimodal shortest path.
The rest of the paper is organized as follows. We describe the problem in more details in Section 2. The proposed algorithm is explained in Section 3 followed by the experimentation and results in Section 4. Finally, we outline the conclusions of the paper. 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 di erent modes of transport is required. The shortest path might include a walk to some carsharing vehicle followed by a drive segment and ends with another walk segment. The operation area constraint is a new component to this type of problems and to our knowledge, this is the rst work to consider such constraint. In the following, we provide the modeling of the di erent 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; jV j). We use the functions w and d : E ! ftrue; f alseg to denote if an edge e 2 E is accessible by walk and drive modes respectively. Edges E are annotated with travel time for both modes walk and drive. We use the functions timew and timed : E ! R 0 to denote the travel times of an edge e 2 E for the modes walk and drive respectively with the following hold w(e) (timew(e) = 1) and d(e) (timed(e) = 1) i.e. if an edge e is not accessible for some mode, then the travel time of that mode on e is in nity.
For each carsharing vehicle, we nd the geographically closest node v 2 V to get the set C V of nodes that will represent the carsharing vehicles in our graph G. New nodes are added to V if necessary, to represent vehicles that are located close to long edges and far from the end nodes of the edges. Using the operation area multipolygon, we generate the set of nodes that are geographically withing the operation area. This set is denoted by O = fv 2 V j v is geographically within operation areag; C O V . 2
Typically, a free oating carsharing system has a set of vehicles on speci c geolocations and a geographical multipolygon de ning the operation area of the carsharing system as shown in Figure 1. Carsharing rental can be started everywhere where a vehicle is available and can be ended only within the operation area dened by the multipolygon. The task is to nd the shortest path on the street network between a given source s and target t points (later will be denoted nodes) using the modes walk and drive. The mode walk can be used everywhere on the street network as long as the street types allow for walk mode. A switch from walk mode to drive mode can be triggered only if a carsharing vehicle is reached. Obviously the walk mode cannot be simply stopped after reaching a carsharing vehicle. It might be necessary to walk a bit farther to reach another carsharing vehicle that might result in the shortest path. Such a vehicle might be To solve the multimodal shortest path problem in free oating carsharing, we propose an extension of Dijkstra algorithm [Dij59], that alternates between the modes walk and drive, and takes the operation area constraint into consideration. Algorithm 1 is a pseudocode representation of the proposed algorithm.
Algorithm 1 follows the basic structure of Dijkstra algorithm. However, the di erent modes of travel and the operation area constraint have to be taken into consideration. The mode switch (from walk to drive and vice versa) and its trigger has to be handled in the algorithm. In comparison to single mode shortest path problem, in multimodal shortest path, the same node could have di erent predecessors at the same time (namely, one per travel mode) as shown in Figure 2. This happens, for example, when the system user has to walk in some direction to reach a vehicle and then drive back the same way. This behavior will tmpD
v
Q:decreaseKey(u; tmpD) else if v 2 C or v jV j then tmpD d[v] + timed(e) if tmpD < d[u + jV j] then if d[u + jV j] = 1 then
Q:insert(u + jV j; tmpD) Q:decreaseKey(u + jV j; tmpD) d[u + jV j] pred[u + jV j] tmpD v result in some nodes, where the same node is reached at di erent durations from di erent predecessor nodes and despite that the di erent 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 predecessor for x will be accepted with duration d2 d1. An edge base traversal Dijkstra will manage to solve the problem depicted in Figure 2. However, it will fail in handling the case where the same edge has to be reached both by walk and drive even if the drive mode results in less duration. Walking a bit farther might result in the shortest path as explained earlier in this section.
At the early stages of the algorithm, it behaves as a typical Dijkstra exploring G in the walk mode (lines 10 17). A mode switch from walk to drive is triggered once a node v 2 C is settled (removed from the priority queue). This means a carsharing vehicle is reached, and from there one can start driving mode (line 18). Once we start exploring G in drive mode, we might face the problem depicted in Figure 2. Node b has already been reached through a with duration timew((a; b)). Once the node c is settled, we can start exploring in mode drive. Now the algorithm tries to reach node b through node c with a total duration of timew((a; b)) + timew((b; c)) + timed((c; b)) timew((a; b)). In a single mode shortest path, this step is not allowed as b has already been reached with less duration through a. However, in our case, this step should be allowed as the vehicle has to be reached rst and the shortest path might be the one with the vehicle driving back the walk path. The algorithm handles that by making local graph copies. For each node v 2 V that is to be explored in drive mode, the algorithm makes a copy of v and assign it the value v +jV j. Now the new node v +jV j can be reached with a higher duration compared to its walk mode node v (lines 20 25). Note that the node v + jV j preserves all the attributes and outgoing edges as (v + jV j) mod jV j = v. Now, any node v jV j indicates that the algorithm is exploring the driving mode. Hence, the condition at line 18 indicates that we can explore nodes in driving mode either if the settled node is a vehicle node v 2 C or it is already a driving mode node v jV j.
The operation area constraint is enforced by the set O. It is used to de ne 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 + jV j) mod jV j = v 2 O. This means that a carsharing vehicle can be returned only within the operation area. The set O is also used to de ne 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 b a We have tested the proposed algorithm using real world carsharing data provided by car2go. The car2go dataset contains 945 vehicles operating in Berlin in an operation area as shown in Figure 4. The Openstreet map (OSM) data of Berlin is used to build the street network graph. Our algorithm is implemented as an extra module plugged to Graphhoper (graphhopper.com). Experiments are performed on a computer with 4G RAM and 2.5GHz, 64bit dual core processor.
Figure 5 shows the results of the algorithm for different carsharing use cases. In 5(a), the source and destination points are within the operation area and the destination is reachable by drive mode. The shortest path consists of a walking part to reach a vehicle followed by a drive part. No nal walk is required as the destination is reachable by drive mode. The destination point is outside the operation in 5(b) and therefore the destination has to be reached walking as the vehicle has to be returned within the operation area. 5(c) shows the result of the algorithm when the source is within one of the polygons de ning the operation area and the destination is close to another polygon. The vehicle is returned in the polygon close to the destination and a walking part to the destination is computed. A single mode walking result is computed in 5(d) as the end points are close to each 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 when the destination is within an excluded area.
Table 1 summarizes the average runtime and number of settled nodes for di erent scenarios of carsharing trips. For each scenario, 10 di erent trips, between randomly selected source and destination points, have been computed. The trips are categorized as short and long distance. We consider trips of an average distance 7-8km as short and trips of an average distance 23-27km as long. While both, short and long distance trips in our study, are considered very short trips for typical single mode routing, still a 23km trip in carsharing systems is considered a long one. The rst scenario of carsharing trips is the drive only trip where a carsharing vehicle is available directly at the source and can be returned at the destination. No walk is required. The second scenario is the walk-drive where some walk is needed to reach the vehicle and the destination can be directly reached by the vehicle. In the last scenario, drive-walk, the vehicle is directly available at the source but some walk is needed at the end to reach the destination.
We notice that there is no considerable di erence in the runtime and the number of settled nodes between the scenarios drive and walk-drive. However, a considerable higher runtime and number of settled nodes for drive-walk on both short and long trips. This is because, when the destination is not directly reachable by the vehicle, either because of being in a pedestrian zone or outside the operation area, the algorithm settles high number of drive mode nodes. It could happen that the algorithm reaches the destination in drive mode but cannot stop the search as it is outside the operation area. The algorithm then has to explore more walk nodes to reach the destination. As the walk mode is slower than the drive mode, walk mode nodes get less priority in the priority queue, as they have higher duration, and the algorithm tends to settle more and more drive mode nodes. In other words, having a walk at the end results in longer trip duration till the destination is reached. The algorithm settles all nodes with duration less than the duration needed to reach the destination and therefore it settles larger number of drive nodes as driving is usually faster and takes less duration. This behavior does not happen when the walking part is at the beginning of the trip even that it results in longer trip duration. This is because, a walk at the beginning of the trip means that a vehicle is not reached yet and drive mode is not active. So the algorithm mainly expands walking nodes. 5
In this work we have proposed an algorithm for the multimodal shortest path problem in free- oating carsharing systems with operation area constraint. The algorithm has been tested, under di erent trip scenarios, using real world carsharing data. Test results showed that the algorithm was able to e ciently solve the problem.
An interesting extension of this work is to combine the carsharing routing with public transport. This is very interesting especially if the destination is far from the operation area, then a last mile public transport could be taken instead of walking. This will a ect the return point near the borders of the operation area depending on the availability of public transport stops and trips. (a) source and destination are within the operation area (b) destination is outside the operation area (c) destination is outside the operation area and close to a polygon other than the polygon of the source (d) close source and destination (e) destination is in excluded polygon