Demand-responsive rebalancing zone generation for reinforcement learning-based on-demand mobility

2.1. Vehicle rebalancing

Rebalancing for MoD can be categorized in the approaches relying on static rebalancing zones [1,10,12,29,30] and dynamic zones [19]. In static rebalancing zone generation, geographical coverage of relocation zones is predefined at design time. For example, in [12], NYC Lower Manhattan area is divided in predefined zones which do not change over time. Each vehicle, using RL, learns and decides at each time step whether to relocate to one of the neighbouring zones or to stay in its current zone. In [10], rebalancing areas in Austin, Texas, are defined by partitioning the area in 2-mile by 2-mile square blocks. Block balance is calculated for each zone, capturing the excess or deficit of vehicles within the block in relation to supply and expected travel demand. Blocks with a negative balance try to gather vehicles from neighbourhood where there is a surplus, and expected travel demand is estimated from historical data and current requests. In [1], zones are defined using a fine-grained but also static grid. In [30], if a vehicle is idling, it can rebalance based on its local knowledge: according to the demand distribution in surrounding areas, it decides to rebalance to a neighbouring zone or not. The work presented in [29] partitions the area into rebalancing zones according to the road network layout. Zones are defined such as that for each region r i , exists a zone which allows to reach r i within the established maximum travel time. Idle vehicles are rebalanced by taking into account travel time, to limit empty travels, and future demand, estimated from current demand, to avoid an excess of vehicles in the same area. However, the zones, once defined at the start, do not change based on traffic or fleet conditions.

The majority of the approaches allow rebalancing only for idle (and empty) vehicles, while [1] and [12] enable vehicles to rebalance during the execution of the routes, and as such is available in any system that enables ride-sharing. Mix rebalancing with RS assignment allow RS pick-ups from neighbouring zones, shortening waiting time for passengers, but increasing their travel time.

The only current work that uses dynamic zone generation for rebalancing is presented in [19]; rebalancing zones are computed using a clustering algorithm. A k-means clustering is applied on virtual requests generated by a distribution defined on historical data. Therefore the coverage and the size of the zones can change, but the total number of zones remains fixed. This approach is the closest related work, however, we allow different number of zones based on different density of requests. Furthermore, our approach relies on real time data rather than historical to have a better respond to dynamic demand.

Table 1 summarizes existing work on rebalancing for MoD systems, categorized by four main characteristics: Analysed data, which can be historical, real-time or both, depending on what kind of data is rebalancing based; Dynamic # zones, i.e., whether the number of rebalancing zones can change over time; RB empty, whether the vehicles relocate only when empty or can relocate as a part of RS assignment; and Dynamic boundaries, whether the area covered by each rebalancing zone can adapt dynamically.

We observe that the main issue of reviewed research is the low adaptability to demand changes (daily, seasonal, or more long-term ones resulting from new city developments), as the addition of new city areas/zones, or changing their granularity, requires system redesign.

With respect to request assignment, multiple algorithms are used in the literature to match riders and vehicles. A full review of vehicle assignment algorithms is out of scope of this paper as our contribution focuses on rebalancing, nevertheless, we highlight some of the vehicle-requests assignment techniques.

A basic vehicle-rider matching systems, e.g., [4,17], simplify the matching by grouping passengers with common pick-up and drop-off locations. Similarly, [9,22] enable ride-sharing by defining a common pick-up and/or drop-off location which suits multiple riders at the cost of a short walk to reach the pick-up point or from the drop-off location to their final destination.

More sophisticated systems include a centralized schedule-based vehicle-request assignment, where schedules are computed to enable ride-sharing and updated on a fixed time base, e.g., [2,29] or graph-based models, e.g., [19] which represent requests on a graph and solve using Integer Linear Programming.

RL-based approaches are also common, and can be divided into two categories, centralized, where a single agent controls the whole fleet, e.g., [10,30]. Decentralized approaches define vehicles as agents which independently explore the environment and discover a policy to serve the ride requests. To simplify the problem, limitations can be applied while picking requests, e.g., that requests served in ride-sharing are within the same zone [1], or that have at most a one-zone-detour [11].

In this paper, we adopt such a decentralized approach. It is worth mentioning, however, that, even though we illustrate D2R2 application in conjunction with an RL-based vehicle assignment, D2R2 is designed to be independent from the assignment algorithm used in the MoD system.

3.1. Deep reinforcement learning

RL is a branch of machine learning in which an agent learns autonomously by trial-and-error to map actions to the current environment state, by receiving a positive or negative reward for their execution [28]. The goal of the agent is to learn actions that maximize the long term cumulative reward. RL iterates three tasks: at each time step an agent obtains the perception of the environment and maps it to a state s from its overall state space. Based on past experience, it can select an action a from the action space. The agent then, at timestep t receives a reward r t = R ( s t , a t ) which expresses how good was the selected action.

In most of real-world scenarios, the environment space is complex or continuous, making it intractable to handle all possible state-action pairs. To overcome this issue, RL has been combined with deep neural networks to approximate states, giving rise to a range of Deep RL techniques. The approach we choose for our implementation is Proximal Policy Optimization (PPO) [27], which is simpler to implement and tune without affecting the performance when compared to other state-of-the-art Deep RL approaches. PPO uses a novel objective function, formed by three terms, which is maximized each iteration: (1) L t CLIP + VF + S ( Θ ) = E ˆ t [ L t CLIP ( Θ ) − c 1 L t VF ( Θ ) + c 2 S [ π Θ ] ( s t ) ] Θ is the policy’s parameter vector. The first term L CLIP is the clipped objective function defined in Eq. (2). c 1 is a coefficient, defined between 0.5 and 1, applied to L VF = ( V Θ ( s t ) − V t targ ) 2 , which computes the squared-error loss of V, the learned state-value function, compared to the target value at time t. Last term S is the entropy bonus, used to ensure sufficient exploration which is regulated by c 2 , ranging from 0 to 0.01. S of a stochastic policy π Θ refers to state at time t. (2) L CLIP ( Θ ) = E ˆ t [ min ( r t ( Θ ) A t ˆ , clip ( r t ( Θ ) , 1 − ϵ , 1 + ϵ ) A t ˆ ) ] In the L CLIP objective function definition (Eq. (2)), the first term inside the min is the surrogate objective with a conservative policy iteration which is clipped by the second term. A ˆ is an estimator of the advantage function shown in Eq. (3) and r t ( Θ ) denotes the probability ratio π Θ ( a t | s t ) π Θ old ( a t | s t ) that expresses the difference between current and old policy, which is clipped if difference falls out of boundaries by ϵ, a small hyper-parameter which weighs distance from new policy in respect to the old. Finally, γ and λ are hyper-parameters regarding discount factor and GAE parameter that helps to improve the stability of the training. (3) A t ˆ = σ t + ( γ λ ) σ t + 1 + ( γ λ ) 2 σ t + 2 + ⋯ + ( γ λ ) ( T − t + 1 ) σ t − 1 where , σ t = r t + γ V ( s t + 1 ) − V ( S t )

While we are not aware of any application of PPO in a ride-sharing problem, it shows good performance in many other applications with similar characteristics, such as portfolio management [18], robot control [15,20,23] or simulation and games [3,31], which motivated our decision to use it as basis for our implementation.

During training, PPO method collects a sequence of samples of length T from the environment and then it begins the update process through Eq. (1) to maximise gathered experience. As first, it estimates the advantage A t ˆ , defined at Eq. (3), for the complete sequence. Then, L CLIP (Eq. (2)) is calculated, clipping the changes of the new policy over the old within the ϵ-interval.

3.2. Clustering

Expectation-Maximization (EM) is an iterative algorithm to find the maximum-likelihood estimates of parameters of a statistical model [25]. Although, its nature is to estimate the latent parameters, it has proved as good method for clustering as well. In fact, over the year has been largely used for that scope, to cite but a few, see [5,6,13]. In this work, we use EM to estimate cluster memberships across several Gaussian distributions. EM consists of two steps, Expectation (E step), which computes the complete log-likelihood of data memberships in clusters, and Maximization (M step), which, by maximizing the computed likelihood, updates the hidden parameters θ related to normal distribution, hence mean, variance and prior probability for each cluster.

E step: hidden parameters are initialized by some random values or, more likely, computed from data points. Then, expectation of the complete log-likelihood, conditioned by observed samples and current estimation of θ, is computed. Expected value is: (4) Q ( θ ; θ ( t ) ) = E [ ∑ k ln ( p y ( y k ; θ | X ; θ ( t ) ) ) ] where θ is the unknown parameter vector and the term inside the logarithm expresses the conditional probability of a datapoint of being generated by a distribution, hence to belong to a cluster k, given the observed samples X and value of θ at the previous step. y represents all the samples including those that cannot be observed and therefore p y is a many-to-one mapping, while y k are all the samples belonging to the k-th cluster.

M step: computes the next ( t + 1 ) -th estimation of the unknown parameter vector by maximising the expected value Q ( θ ; θ ( t ) ) obtained from previous step. (5) θ ( t + 1 ) : ∂ Q ( θ ; θ ( t ) ) ∂ θ = 0 EM algorithm terminates when difference between expectation at time t and time t − 1 , obtained from Eq. (4), is smaller than a threshold ϵ.

Once terminated, the likelihood indicates how good our model fits data. However, this parameter alone does not take into account over-fitting and the number of clusters; in fact likelihood could be maximized with each datapoint belonging to a different cluster. An option to validate and select a model is by using Bayesian Information Criteria (BIC) [7]. It prevents over-fitting by taking into account number of clusters. BIC is computed through Eq. (6), where number of free parameters, k, depends on number of clusters. BIC measure weighs the number of free parameters with the number of samples available. It looks for the true model among the set of candidates. (6) BIC = ln ( n ) k − 2 ln ( Q ˆ ) Where Q ˆ is the maximized value of the likelihood function, result of Eq. (4), n is the number of data points within a dataset and k is the number of free parameters to be estimated.

We have opted to use EM over other clustering techniques, i.e., k-means, because it derives clusters by estimating parameters of normal distribution that underlies data. As result, EM defines good clusters, compared to other clustering techniques, even when some data are missing or not observable since it does not work directly on the data, i.e., by using a distance measure. Furthermore, EM enables clusters to have different shapes unlike other clustering methods which tends to find clusters with comparable areas by working directly on data points. Since EM aims to maximise the complete log-likelihood, as reported by Eq. (4), it could sometimes lead to suboptimal results due to local maxima. To overcome this, multiple runs of EM could be performed. However, we limit this issue by picking the best model across several candidates using BIC defined in Eq. (6).

4.1. Ride-sharing using deep reinforcement learning

We designed a multi-agent decentralized algorithm for RS applied to a fleet composed of 5-seater autonomous vehicles for a MoD system, which is model-free and designed to be replicable to any other city.

To take a decision during exploration, agent samples an action based on some probabilities defined over the q-values where actions with higher q-values have higher probability of getting selected. The policy, i.e., Q-value estimates, are learnt using PPO [27], introduced in Section 3.1.

Each agent controls a vehicle, taking an action at each step by evaluating its internal state and perception, without communicating or coordinating with other vehicles. Agents evaluate and decide of an action in a sequential order. At each time step, each agent perceives the environment, updating perception and internal state, and decides of the next action: to pick-up a ride, to drop-off passengers or to wait being parked. Finally, it stores the transition in a buffer and evaluates if an update is necessary (line 33 in Algorithm 1). This cycle is described in Algorithm 1. Policy update relies on Eq. (1), after T transitions have been stored, the agent uses these samples to estimate the advantage (Eq. (3)).

OPEN IN VIEWER

Algorithm 1:

Controller for a single vehicle V

The agent’s internal state (V.status in Algorithm 1) is composed of the vehicle position, represented by latitude-longitude pair, its destination, and the number of vacant seats. For an empty vehicle, destination is void, and if a vehicle is serving one or more requests, its destination matches to that of the request r i that can be served the quickest, as shown in line 16 in Algorithm 1. The vehicle location on the road network is updated every time that a new position is reached, either destination or pick-up point.

The representation of agent internal state has been kept simple to enable multiple agents sharing the same knowledge. When designing the requests assignment module, we aimed for a solution that could easily scale up by treating vehicles in a standard way regardless the equipped seats. Thus, internal state records the available free seats rather than information of carried passengers. Vehicle destination matches the one of the passenger(s) that can be served the quickest.

Including an higher level of details into internal state, i.e., reporting all the passengers destination, not only demands a complicated model, but also requires multiple models when scaling the problem to a fleet composed by vehicles with different number of equipped seats. In addition, many times these neurons are fed with empty values, since the vehicle is not always getting around full.

Perception P (V.perception in Algorithm 1) is composed of the three closest requests that an agent could serve and are filtered from the set of available requests at the given time. A request r is available to a vehicle v if v has enough empty seats to accommodate the number of passengers associated with the request (ranging from 1 to 6), and the total waiting time for r, i.e., the delay between request being created and estimated passengers pick-up time, is less than the maximum time allowed (set to 15 minutes). All customers, who have waited more than 15 minutes leave the system without being served, and the request is recorded as not served. Finally, requests already picked-up by the vehicle, are represented as V.queue in Algorithm 1.

Perception is defined as the aggregation of states of requests perceived by an agent, P : { S r 1 , S r 2 , S r 3 } . Where, S r i : [ r Pos i , r Dest i , r Passengers i ] represents the state of the i-th request perceived by an agent. For each request, an agent takes into account its pick-up location, the destination and number of passengers. Figure 3 summarizes vehicle state and perception. Vehicles can choose between 5 actions, organized in three categories: (1) park, in which an agent waits one minute at the location where it is or rebalances; (2) drop-off, in which an agent serves a request by driving the passenger(s) to their destination (V.goToDestination()); (3) pick-up, an agent drives to a pick-up point of the selected request (V.pickUp()). As we see in the list of action, rebalancing module is integrated with the vehicle assignment module through an option within the park action, where vehicle decides to park where it is, or rebalances to park at a more suitable location based on current demand. Pick-up action has three variations, pick-up first, second or third request from the perception set. Once an agent selects a pick-up action, is first checked whether in perception corresponds a request and then if the vehicle can accommodate the new passenger(s), lines 24–25 in Algorithm 1. When the vehicle is not serving nor perceiving any requests, it is enabled to rebalance as shown at line 6 in Algorithm 1. We further discuss rebalancing in next section.

OPEN IN VIEWER

Fig. 3.

Vehicle state and perception. Vehicle is already carrying a single passenger and evaluates whether pick-up one of the three perceived requests, doing ride-sharing, or not.

Rewards associated to actions are shown in Algorithm 1. An agent get a penalty (impossibleActionReward) whenever tries to perform an action impossible to fulfill: attempting to drop-off while being empty, as shown at line 14, or trying to assign a request that could not be assigned, line 29. When the vehicle successfully assigns the request, a reward is received, lines 26–27. This, corresponds to commonReward if the picked passengers are the firsts, otherwise corresponds to RSReward. The best (DOReward) and the potential worst reward are related to the same action, lines 18–20: when a vehicle is doing a drop-off while carrying passengers from several requests. If the travel time for passengers to reach their destination exceeds the estimated travel time without RS from request origin to destination more than a defined value, then DOReward is penalised based on the additional travel time caused by the detour. In detail, we compute the detour ratio (detourRatio), defined as travel time to serve the request enabling ride-sharing over the expected travel time from the origin to the destination of the request, we compare it to a fixed threshold (max_detourRatio) and finally, if needed, reward is penalised.

Finally, a mild penalty is given whenever the agent decides to being parked, lines 4–8. This is tuned according to the possibility of the agent to perform other valid actions. In detail, ordered by severity of penalty, onlyPossibleAReward whether the agent would receive impossibleActionReward if trying to perform other actions, notOptimalAReward if the vehicle, being empty, decides of stay parked rather than evaluating new requests, and lastly badActionReward if the agent could have performed any of the other actions instead.

D2R2 rebalancer can be used with different MoD systems, however for illustration we describe its implementation as combined with the Deep RL ride-sharing request assignment strategy presented in previous section. Rebalancing is triggered by the park action and when the vehicle is not serving any requests and it has no further requests to serve in its neighbourhood. D2R2 aims to dispatch vehicles efficiently and dynamically according to current demand, preventing fleet unbalance, which in turn can result in longer passenger waiting times, or an increased number of unserved requests. D2R2 infers relocating zones and computes their associated probabilities (Eq. (7)) for a vehicle to be relocated into: (7) p r ( v , z i ) = | R i | | R | where z i is the ith zone, R i is the set of pending requests within current zone, and R is the set of pending requests across all zones.

The D2R2 framework is illustrated in Fig. 4, depicting the rebalancing module and an agent behaviour. The demand filter has a double role: it filters three requests for the agent perception and also provide those for computing rebalancing zone and probabilities. D2R2 takes as input pending requests available at current time filtered according to the time frame timeFrame (line 2–5 Algorithm 3). All previous unsatisfied requests and future requests (estimated or scheduled), are not taken into account. Algorithm 2 describes the procedure applied to relocate an idle vehicle to a new position. First, D2R2 generates new clusters, based on pick-up position for pending requests, following Algorithm 3. For a single rebalancing task, several runs of EM occur, producing different number of clusters ranging between min_#zones and max_#zones as shown in Algorithm 3 at line 7. The algorithm then selects the model which better represents the data by choosing the clustering model which minimizes BIC measure (line 7 in Algorithm 3). The vehicle is then rebalanced to a zone within the selected clustering model according to a weighted random selection defined over a probability distribution among clusters and computed in Eq. (7) (line 3 in Algorithm 2). Among different approaches we preferred a weighted random selection to enable vehicles exploring different zones while rebalancing, avoiding all the vehicles to rebalance in a similar area.

OPEN IN VIEWER

Fig. 4.

Architecture of the implemented framework from a single agent perspective. D2R2 is integrated to the requests assigner module.

OPEN IN VIEWER

Algorithm 2:

Single vehicle relocating by D2R2

OPEN IN VIEWER

Algorithm 3:

Defining relocating zones for rebalancing

Each agent therefore, at each timestep, takes an action using its policy trained though PPO and, when needed, relocates by computing zones through EM as described in this section.

We rely on commonly used measures adopted by related work [1,2,12,29] to evaluate the performance of D2R2 in the proposed scenarios. The overall performance of the MoD fleet is assessed by analysing the number/percentage of served requests and the percentage of requests that involved ride-sharing (as opposed to occupancy of the vehicle only by one or more passengers from a single request). From the passenger perspective, we evaluate the average detour ratio ( D r ‾ ) (i.e., the percentage of extra travel time used to facilitate ride-sharing) and the average waiting time ( w t ‾ ). D r ‾ is obtained by comparing actual time spent to reach the passenger destination serving other RS requests, and the expected travel time for a direct trip between the passenger origin and destination. w t ‾ represents the average time passengers have to wait between creating a request and being picked-up. The maximum waiting time per request is limited to 15 minutes and after this the request leaves the system and flagged as unserved.

From the vehicles perspective, we recorded the distribution of the number of passengers per vehicle in the fleet and computed its variance (σpass). We also recorded the average distance travelled per vehicle ( d t ‾ ).

6.2. Simulation results

This section presents the simulation results for all the scenarios.

Level of service. From the system perspective, as reported in Table 3, each scenario shows a different level of service. Scenario Base – no RB, no RS, which models a classical taxi service, serves around 74% of requests, and D2R2 RB only serves 95% of the requests. All other scenarios (RS only, RS with fixed zones RB, and D2R2 RB and RS) achieve maximum level of service possible with 5-seater cars, of 96.63% requests. The results show that by enabling ride-sharing in combination with a rebalancing strategy, with fixed zones or D2R2, decreases number of request ride-share (70% and 68% vs 80%) when compared to RS only. However, detour ratio is decreased (1.5 vs 1.7), which means that average time needed for passengers to reach their destination is decreased in D2R2 RB and RS and RS only with fixed zones RB. Note that, D r ‾ , increases with any ride-sharing strategy, when compared to no RS scenarios (Base and D2R2 RB only), and is not affected by any rebalancing strategies.

OPEN IN VIEWER

Fig. 5.

Comparison of simulation results for all the 5 analysed scenarios for the following metrics: waiting time ( a ) , passengers distribution per vehicle ( b ) and distance travelled per vehicle ( c ) . The y-axis represents the probability that a request for ( a ) , or vehicle in ( b , c ) , assumes a specific value.

Passenger waiting time. Figure 5a shows passenger waiting times for each scenario. By enabling ride-sharing in the baseline scenario (RS with fixed zones RB) or D2R2 (D2R2 RB and RS), we observed a significant reduction when compared to Base – no RB, no RS. RS only shows lower overall waiting times (3.761 minutes) when compared to D2R2 RB only (4.218 min). However, ride-sharing can generate additional delay for passengers as vehicles are following a detour to serve more requests as shown in Table 3. Rebalancing in addition can limit the additional travelled distance due to detours as the vehicle relocates in zones with closer requests that can be matched. Hence, D2R2 RB only results as the best option for passengers with respect to travel time.

Passenger distribution. We can observe in Fig. 5b that in Base – no RB, no RS many vehicles are driving with only a few passengers. These vehicles, once serving one or few requests, may end up in an area of the network that is empty of any further request. Enabling rebalancing or ride-sharing can prevent them from staying idle and help vehicle to find new requests. This can be observed from scenarios D2R2 RB only and RS only, where further improvements are achieved by enabling ride-sharing and rebalancing, as all vehicles serve a similar number of passengers. In particular, D2R2 RB and RS seems to converge to a higher average value when compared to baseline rebalancer RS with fixed zones RB. Moreover, as shown in Table 3, the variance of the number of served passengers is also lower: the combinations of these leads to conclude that the ROI for the individual vehicle/agent, member of this network, is more consistent and stable (for a fixed number of vehicles serving shared rides).

Vehicle mileage. Distance travelled by agents is depicted in Fig. 5c. Base scenario Base – no RB, no RS shows that around one fourth of vehicles are travelling only a few kilometres, confirming they only serve a few requests and then stay idle in an area with no further demand. Also, since the number of served requests varies by scenario, an important difference in terms of distance travelled was recorded. We further investigate travelled distance in Table 3. From the table, we can confirm that enabling rebalancing adds additional travel distance for empty vehicles.

As our approach relies on learning and clustering techniques, we further investigated its performance by performing additional simulations to observe if the results are consistent across runs. Here we focus only on scenarios combining ride-sharing and rebalancing, specifically our approach D2R2 RB and RS, and a baseline RS with fixed zones RB. Figure 6 and Table 4 show the same three metrics (waiting time, number of passengers served, vehicle mileage) across the two RS- RB- enabled scenarios over 20 simulations. Figure 6a shows waiting time for all satisfied requests over the different runs (193,260 requests in total over 20 simulations), while the remaining, served passengers Fig. 6b and distance travelled Fig. 6c, regard 200 vehicles, composing the fleet, over 20 simulations, i.e, total of 4,000 vehicles. We can observe that D2R2 provides consistent performance, with waiting time mean being 196 seconds, from Table 4 and 90% confidence interval ranging from 1 to 4 minutes and 57 seconds, with served passengers mean being 73 and 90% confidence interval ranging from 49 to 97 and with distance travelled mean being 140.3, from Table 4 and 90% confidence interval ranging from 143 to 150.

As graphs show, our proposal D2R2 RB and RS is consistent across multiple runs, even though it relies on a degree of randomness given by a RL-based system for vehicle-request matching and a dynamic demand-responsive strategy to relocate empty vehicles.

OPEN IN VIEWER

Fig. 6.

Comparison of simulation results over 20 simulations for the RS- RB-enabled scenarios: waiting time (a), passengers distribution per vehicle (b) and distance travelled per vehicle (c). Data shown are obtained by aggregating results generated from 20 simulations composed by 10,000 requests served by a fleet of 200 5-seater vehicles.

Simulation results show that enabling ride-sharing alone is enough to satisfy all of the requests possible to serve, when the baseline Base – no RB, no RS only serves 74%. Introducing rebalancing (whether fixed, or D2R2) increases level of service to satisfying 97% requests. However, D2R2 rebalancing results in slightly shorter waiting time and lower detour ratio than fixed zone rebalancing. However, the main observed advantage of D2R2 (with RB and RS) is that the workload that each vehicle has to carry out seems to better converge to a global average value (Fig. 5b), resulting in fairer workload distribution. This is in contrast to other scenarios, where we observed that a few agents are contributing more that the others and some vehicles can be under-utilized, serving only a few requests. The closest in terms of workload distribution to our approach is (RS with fixed zones RB), however the variance is still larger at 82 passengers vs 63 in our approach (as σ pass in Table 3 shows). Interestingly, fairness is not a metric existing work considered. Our results show that this should be included as a standard measure when evaluating ride-sharing systems, along side other system, user and vehicle metrics. We also observe that approaches with rebalancing (RS with fixed zones RB and both D2R2 scenarios) generate additional travelled distance: total mileage is slightly increased due to empty vehicles travelling as a part of relocation process.

OPEN IN VIEWER

Fig. 7.

Sample D2R2 outcome, during a simulation run of D2R2 RB and RS scenario over the evening peak, while evaluating rebalancing zones for a single vehicle. Requests origin that lead to this partitioning are also displayed.

To illustrate the zone outcomes of D2R2 and how does it differ from fixed zone clustering, we here show a snapshot of the number, size, and shape of the clusters it generated for a particular vehicle v at time t (Fig. 7). In this instance, 10 relocation zones were computed by D2R2. Cluster centres are represented by a cross and colours intensity indicates its rebalancing probability. However, the number of clusters throughout the simulation, based on the demand at any particular time, ranged from 4 to 30, as illustrated in Fig. 8, with the majority being in range between 13 and 20. To conclude, at the cost of additional processing in onboard devices, D2R2 removes the need for more complex centralized computation. The required processing cost is not really resource demanding and can be affordable by onboard devices since are not either power or processing constrained.

OPEN IN VIEWER

Fig. 8.

Distribution of number of zones identified by D2R2 during a single run of the simulated scenarioD2R2 RB and RS for a fleet composed by 200 vehicles.

While evaluating our proposed rebalancer D2R2, we had to make some simplyfing assumptions which introduced limitations in the current version of the approach. We discuss these limitations here. First, since we are retrieving the travel time through the use of an external engine as OSRM, our vehicles are not impacted by, or impact on, current congestion. Second, D2R2 does not evaluate the distances between vehicle and zones when computing rebalancing probabilities. By taking into account these distances, relocating cost, due to travelling while being empty, could be reduced and total travelled distance further minimised. Third, when picking up a request, an agent can choose only between closest three requests. This limitation has been added to reduce the complexity of the decision-making neural network. A change in filtered requests would require a re-training of the model from scratch. Forth, we kept our reward structure for underlying RS system simple. Many reward models with different granularity are proposed in RL-literature, (e.g., based on distance to additional request, or waiting time) but these were never compared in a common scenario to select optimal one. Fifth, we only present the results in terms of temporal metrics for passengers (e.g., waiting time) and vehicle load, without analysing impact and implications of these results on economic benefits. RS systems have three sets of stakeholders: passengers, vehicle drivers, and overall fleet operators,each aiming to maximize their own performance, from financial, as well as from quality of service perspective. If we consider the impact of the RS system on the comprehensive traffic context, probably also the hosting municipality and regional authorities should probably be included, both as relevant economical actors as well as regulators. Such an analysis, which would require an interdisciplinary effort, is out of scope of this paper, but our results indicate that fairness, in the form of passenger to vehicle distribution, should be added as a metric when evaluating economic benefits. Lastly, there are few constraints applied to our scenario that can be tuned without requiring a full re-training process. Vehicles are equipped of 5 seats dedicated to passengers, while in real world there are several options available. Maximum detour ratio when picking up an additional request is fixed to 30% added to the estimated journey time of the original passenger from origin to destination. 1.3, which means that when planning for a new pick-up, the onboard passengers will not be required to pick other. Note that, after arriving to destination, the detour experienced by passengers could exceed the fixed threshold, this can happen when the agent gives the drop-off priority to other passengers, since vehicle destination matches the one of the request that can be served the quickest. Further development and evaluation of the approach should remove these limitations and evaluate their impact on the overall performance.