Enabling Ride-sharing (RS) in existing Mobility-ondemand (MoD) systems allows to reduce the operating vehicle fleet size while achieving a similar level of service. This however requires an efficient vehicle to multiple requests assignment, which is the focus of most RS-related research, and an adaptive fleet rebalancing strategy, which counter-acts the uneven geographical spread of demand and relocates unoccupied vehicles to the areas of higher demand. Existing research into rebalancing generally divides the system coverage area into predefined geographical zones, however, this is done statically at design-time and can limit their adaptivity to evolving demand patterns. To enable dynamic, and therefore more accurate rebalancing, this paper proposes a Dynamic Demand-Responsive Rebalancer (D2R2) for RS systems. D2R2 uses Expectation-Maximization (EM) clustering to determine relocation zones at runtime. D2R2 re-calculates zones at each decision step and assigns them relative probabilities based on current demand. We demonstrate the use of D2R2 by integrating it with a Deep Reinforcement Learning multi-agent RS-enabled MoD system in a fleet of 200 vehicle agents serving 10,000 trips extracted from New York taxi trip data. Results show a more fair workload division across the fleet without loss of performance with respect to waiting time and distribution of passengers per vehicle, when compared to baselines with no rebalancing and static pre-defined equiprobable zones.
Mobility-on-Demand (MoD) systems are gaining popularity over
privately owned vehicles and public transportation due to reduced
prices and shorter overall journey times [
Vehicle to request matching has been widely investigated.
Offline methods relying on constraint solving [
However, fleet rebalancing in MoD systems has been less
investigated while shown to have a strong impact on level of service of
RS-enabled systems [
Adaptively following (or even preventing) changes in the demand spatial patterns can improve the perceived level of service from the perspective of the use of the MoD system, and also, assuming a joined fleet in which human drivers can participate with their vehicles, its capability to consistently enable drivers to meet the actual demand while optimizing vehicles usage and increase the ROI (return on investment), assuming that the participation to the RS system would imply a subscription cost (due to setup and operating costs of the system).
To address this issue, existing work define rebalancing strategies
that consist in relocating vehicles according to past or current
demand. Rebalancing can be achieved using pre-defined location per
vehicles (station-based relocation) or by defining a set of areas (also
called zones) each vehicle can be sent to. Rebalancing approaches
can rely on a static [
In this paper, we propose a Dynamic Demand-Responsive Rebalancer (D2R2) which, using Expectation-Maximization (EM) clustering technique, generates a dynamic set of rebalancing zones and computes relocating probability per zone from current demand trend every time a vehicle needs to relocate. Novelty of our approach is twofold: first, boundaries and number of relocating areas are computed when required and second, rebalancing probability for each zone is allocated dynamically using only unserved requests data available in real-time. Therefore, D2R2 does not require data collection and no learning phase is required, enabling our proposal to operate from the beginning while being responsive to current demand.
We evaluate D2R2 in an implementation of a Multi-Agent
Reinforcement Learning (MARL) ride-sharing enabled MoD system
where 200 vehicle agents serve 10,000 ride requests in lower
Manhattan road network. Requests have been generated from the open
NYC taxi dataset [
Rebalancing for MoD can be categorized in the approaches relying
on static rebalancing zones [
The only current work that uses dynamic zone generation for
rebalancing is presented in [
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 drivers (or vehicles). For
example, [
This section introduces the background information needed to understand D2R2 design and implementation: Reinforcement Learning (RL) used for vehicle assignment problem and expectation maximization (EM) with model selection criterion for rebalancing. 3.1
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 [
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) [
i (1) is the policy’s parameter vector. The first term LCLIP is the clipped objective function defined in Equation 2. c1 is a coefficient, defined between 0:5 and 1, applied to LV F = (V (st) Vttarg)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 c2, ranging from 0 to 0:01. S of a stochastic policy refers to state at time t.
LCLIP ( ) = E^thmin(rt( )A^t; clip(rt( ); 1 ; 1 + )A^t)i (2) In the LCLIP objective function definition (Equation 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 Equation 3 and rt( ) denotes the probability ratio (a(tajtsjts)t) that expresses the difference beold tween 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.
A^t = t + ( ) t+1 + ( )2 t+2 + + ( )(T t+1) t 1 where, t = rt +
V (st+1)
V (St) (3) During training, PPO method collects a sequence of samples of length T from the environment and then estimates the advantage A^t for the complete sequence. Finally, several epochs of optimization on LCLIP are performed on the same batch, to maximize gathered experiences.
While we are not aware of any application of PPO in a
ridesharing problem, it shows good performance in many other
applications with similar characteristics, such as portfolio management [
Expectation-Maximization (EM) is an iterative algorithm to find the
maximum-likelihood estimates of parameters by computing
probabilities of cluster memberships across several probability
distributions [
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:
Q( ; (t)) = Eh X ln(py(yk; jX; (t)))i
k where is the unknown parameter vector and the term inside the logarithm expresses the conditional probability of a datapoint to belong to a cluster k given the observed samples X and value of at the previous step.
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.
(t + 1) : EM algorithm terminates when difference between expectation at time t and time t 1, obtained from Equation 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
overfitting 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) [
BIC = ln(n)k 2 ln(L^) Where L^ is the maximized value of the likelihood function, result of Equation 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 because it computes clusters by estimating normal distribution with their parameters, which underlies data. By doing that, 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. 4
This section describes the main contribution of our paper, a DemandResponsive Zone Generation for Real-Time Vehicle Rebalancing (D2R2) in RS fleets. We first introduce our unpublished RS system using multi-agent Deep Reinforcement Learning, and then our novel rebalancer. 4.1
We designed a multi-agent decentralized algorithm for RS applied to
a fleet composed of 5-seater autonomous vehicles for a MoD system,
(4)
(5)
(6)
which is model-free and designed to be replicable to any city in the
world. To take a decision, agent implements PPO [
Parameters: V vehicle, a action, r request, PPO model 1 Perceive and act (V ) 2 update vehicle perception and status 3 a PPO.getAction([V.perception, V.status]) 4 if a is parked then 5 if (V.queue ^ V.perception) are empty then 6 rebalance(V ) // Alg. 2 7 reward 0:01
The agent’s internal state is composed by 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 ri that can be served the quickest, as shown in line 14 in Alg. 1. The vehicle location on the road network is updated every time that a new position is reached, either destination or pick-up point.
Perception P is composed of the three closest requests that an agent could serve. 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.
Perception is defined as the aggregation of states of requests perceived by an agent, P : Sr1 ; Sr2 ; Sr3 . Where, Sri : rPios ; rDiest ; rPiassengers represents the state of the i-th request perceived by an agent. Each requests consists of a pick-up location, the destination and number of passengers.
Vehicles can choose between 5 actions, organized in three categories: (1) drop-off, in which an agent serves a request by driving the passenger(s) to their destination; (2) park, in which an agent waits one minute being parked. (3) pick-up, an agent drives to a pick-up point of the selected request. 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), line 19 in Algorithm 1. When the vehicle perception is empty and it is not serving any requests, it is enabled to rebalance as shown at line 6 in Algorithm 1. We further discuss rebalancing in next section.
Rewards associated with actions are also shown in Algorithm 1. An agent get a negative reward of -10 for attempting to try to pickup a request while it does not have enough free seats. Otherwise, the best (+5) and the potential worst reward are related to the same action: when a vehicle is doing a drop-off while carrying passenger from several requests, if the travel time for passengers to reach their destination exceed the estimated travel time without RS by 30% or more, then the reward is reduced according to the total additional detour distance travelled. 4.2
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 when a 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: pr(v; zi) = jRij jRj (7) where zi is the ith zone, Ri is the set of pending requests within current zone, and R is the set of pending requests across all zones. R2D2 framework is illustrated in Figure 3, depicting the rebalancing module and an agent behaviour. The demand filter has a double role: it selects three requests for agents perception and also filters demand for rebalancing, according to used time frame. D2R2 takes as input pending requests available at current time. All previous unsatisfied requests and future requests (estimated or scheduled), are not taken into account, as illustrated in Figure 4.
Algorithm 2 describes the procedure applied to relocate an idle vehicle to a new position. First, R2D2 generates new clusters, based on pending requests, following Algorithm 3. For a single rebalancing task, several runs of EM occur, producing different number of clusters. 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 Equation 7 (lines 3-4 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.
Result: relocates a vehicle V to a new position 1 rebalance (V ) 2 clusters, relocatingProbability updatingClusters(reqsAvailable, V.time) rnd generate random value 2 [0; 1] 3 i 0 4 do i++ while rnd<relocatingProbability[i] 5 V.destination clusters[i].getCenter() 6 V.driveToDestination() // Alg 3
Each agent therefore, at each timestep, takes an action using its policy trained though PPO and, when needed, relocates by using EM as described in this section. 5
We evaluate the performance of D2R2 in an RL-based RS system by using a fleet of 200 5-seater vehicles controlled by autonomous agents. Requests have been extracted from NYC city taxi data, and filtered to include only requests within lower Manhattan in New York City. Our evaluation is performed using data for the evening peak hour (from 6 to 9 pm), and consists of 10,000 requests. These 10,000 requests have been generated by aggregating trips from 50 consecutive Tuesdays between July 2015 and June 2016 (to represent a typical weekday demand pattern). Passengers by request, during evening peak time, are distributed as follows: 71.95% of demand is composed by a single passenger request, 13% by two, 4.1% by three, 2.28% by four, 5.3% by 5 and the remaining 3.37% by 6.
Agents learning stage is performed by running multiple rounds of single-vehicle training. Only a single vehicle vt is allowed to explore the environment at a given time t and can perceive remaining requests that the previous vehicle vt 1 could not serve.
This emulates a multi-vehicle concurrent exploration without competition between vehicles in serving customers. All the experience gained by all of the vehicle agents during training is gathered into a single learning process. In this way, all vehicles update the same learning process, to optimize the use of acquired knowledge and speed up the overall learning process. However, if one vehicle fails to do the update, or is not available to serve requests in a particular location, the others can continue seamlessly. Once training is completed, knowledge is replicated to all vehicles of the fleet. This allows new vehicles/agents to join the fleet without carrying out any additional training.
Travel information for vehicles is estimated using the Open Source
Routing Machine (OSRM) [
Agents, which are implemented through Tensorforce [
PPO batching capacity is 100, and we executed 10 iterations over the batches of the PPO objective. The model was trained during 20 episodes, and each episode is composed of 10 rounds in which a vehicle serves requests. Each episode does not have a fixed number of iterations, as it terminates when a given agent does not have any more requests to serve. During training, rebalancing is disabled to avoid unpredictable bias as it relies on a random weighted choice to select the new zone in which a vehicle is relocated into. For this reason integrating rebalancing as an action would have affected agents learning, requiring more exploration. 6
To evaluate the performance of D2R2 rebalancing strategy, we propose 5 different scenarios, as presented in Table 2.
The first baseline scenario (Base - no RB, no RS) imitates the behaviour of a simple MoD system without ride-sharing or rebalancing. In the second baseline scenario (RS only) ride-sharing alone is enabled. Third baseline is a MoD with both ride-sharing and rebalancing, but the number, size, and boundaries of zones is fixed (similarly to existing related work) and the zone for rebalancing is chosen randomly. We also evaluate two variations of D2R2. (D2R2 RB only) uses D2R2 without ride-sharing while (D2R2 RB and RS) uses both ride-sharing and rebalancing. This combination of scenarios allows to evaluate the benefits of rebalancing overall as well as the benefits of D2R2-based rebalancing specifically.
For all simulations, we assumed each vehicle to have a capacity of 5 passengers, therefore requests with more passengers are ignored by vehicles. This means that, based on the dataset used, the maximum level of service the fleet can reach is serving 96.63% of the 10,000 requests. 6.1
We rely on commonly used measures adopted by related work
[
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 (dt). 6.2
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 D2R2 rebalancing, decreases number of request ride-share (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.
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 Figure 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 Figure 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. 6.3
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%. We showed that D2R2 improves the average and individual performance of all vehicles when enabled in combination with ride-sharing (D2R2 RB and RS) compared to Base - no RD, no RS. Passenger waiting time for (D2R2 RB and RS) (a) Waiting time for request (b) Number of passengers served per vehicle (c) Vehicle mileage is almost halved when compared to a normal taxi cab service (Scenario Base - no RB, no RS). 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 (Figure 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). Interestly, 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 R2D2 scenarios) generate additional travelled distance: total mileage is slightly increased due to empty vehicles travelling as a part of relocation process.
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 (Figure 6). 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 Figure 7, with majority being in range between 13 and 20. 7
This paper presents a Dynamic Demand-Responsive Rebalancer (D2R2), a novel vehicle rebalancing algorithm for ride-sharing mobility-on-demand systems. Unlike existing approaches which use a fixed number and fixed geographical division of the network in zones to relocate empty vehicles, D2R2 uses EM clustering to dynamically generate zones. D2R2 enables zones to be dynamic in terms of their number, position and boundaries. First, rebalancing zones are identified by analysing real-time pending requests at each time step from each vehicle perspective. The zone to which a vehicle rebalances is then selected, among the defined zones according to a probability distribution defined over the zones. Thus, idle vehicles are spread across the area rather than rebalanced to the same zone(s). D2R2 effectiveness is shown by integrating it with 200 RL-based ride-sharing vehicles, which serve 10,000 ride-sharing requests in the lower Manhattan area. We compare D2R2 to approaches with no rebalancing and fixed-zone rebalancing, and observe a more fair workload division across the fleet when using D2R2, indicating a more accurate rebalancing strategy, without loss of performance with respect to waiting time and distribution of passengers per vehicle.
This work can be expanded in multiple directions. To verify its general applicability, it should be integrated with other RS approaches, and evaluated on other road network maps and datasets. In terms of improving the underlying PPO learning process, vehicles could be enabled with further online learning, to fine-tune their behaviours to new request patterns as they arise. Rebalancing could be further improved by taking into account vehicle position, for estimating travel time, when selecting the cluster to which to relocate. Thus, probability computed by Equation 7 would be conditioned by vehicle position and then normalized. Additionally to be more precise, it could integrates real-time traffic congestion data. It could further be integrated with existing approaches, as reviewed in Related Work, which use historical data to predict future demand, and tune cluster probabilities accordingly.
This publication has emanated from research supported in part by a research grant from Science Foundation Ireland (SFI) under Grant Number 18/CRT/6223, Center for Research Training in Artificial Intelligence.