Emergent micro-communities for ride-sharing enabled Mobility-on-Demand systems

Abstract

Mobility-on-Demand (MoD) systems offer a flexible mobility alternative to classical public transportation services in urban areas. However, a significant part of MoD vehicles operating time can be spent waiting empty or driving to reach new potential ride requests. Improving vehicle fleet operation is an extremely challenging problem, as the number of vehicles in operation at a time cannot be controlled. To cope with this issue, new forms of mobility are being deployed successfully: for instance, ride-sharing enabled MoD systems can match riders from several requests. Existing work considers that the best way to achieve significant performance is to control vehicles. However, travel times are hard to predict in congested traffic, and optimizing a relocation scheme of empty vehicles can be hard for large-scale networks and big fleets. In this paper, we take the perspective of riders that collaborate with other travellers in order to walk to locations where they are more likely to get picked up by a MoD system. We introduce a multi-agent model that accounts for vehicles, riders and the MoD platform. The aim of this interactionbased model is to enable riders to dynamically form emergent microcommunities that physically meet, wait and share a vehicle together for part of their trip. Our approach is evaluated in a simulation framework that allows to investigate the respective behaviour of vehicles and riders. Ride requests are generated from New York City taxi dataset. We show that our approach allows riders to improve their chance to be picked up and reduce their travel costs while improving overall efficiency of the fleet.

INTRODUCTION

New forms of mobility, such as Mobility-on-Demand (MoD) systems, offer a competitive alternative to travellers against traditional taxi services or public transportation options. These new mobility services offer a fast, private, flexible and personalised travel solution to individuals. As part of a MoD fleet, vehicles are waiting for trip requests, transmitted from an online MoD booking platform. Profits of these systems can only be guaranteed if the distance travelled empty to reach a pick-up location can be balanced with the distance travelled carrying passengers. Variability of mobility demand can make the MoD fleet management task harder. For instance, in Paris, these systems have quickly reached their limits when fleet sizes grew too much [ 5, 2 ]. Similarly, in London, a significant increase of the number of MoD vehicles did not result in an improved level of service. This can be explained by the constant increase of fuel prices, and an overall underutilisation of the fleet: it has been estimated that traditional taxis can spend up to 40% of their operating time empty, waiting or looking for new passengers [ 4 ].

Recently, major MoD companies launched ride-sharing (RS) enabled services (like Uberpool [ 22 ] or Lyft Line) that propose reduced fares by allowing one vehicle to match several riders with similar origin and/or destination. RS further increases the complexity of vehicle-riders assignment and trip planning. Related work focused on solutions to optimise shared trips. However, riders (and their objectives) are often considered as constraints in the assignment problem [ 1, 16, 15 ] and are not directly taking part in the process. A few approaches [ 27, 11, 6 ] include riders objectives in the assignment algorithm, however indirectly, in a RS-enabled MoD system. Existing centralised approaches provide an efficient solution to the assignment problem [ 26, 9, 21 ], but neglect riders individual objectives.

The goal of our approach is to consider riders as active actors of the problem, being able to interact with vehicles (or drivers) trying to reach their own goals: minimising their waiting time and the cost of their trip. Multi-agent approaches seem particularly suited to tackle this problem which is, by definition, decentralised, large-scale and taking place in an uncertain environment. Here, two emergent behaviours can be studied simultaneously: travellers can collaborate and form micro-communities with a common destination; and the opportunistic behaviour of vehicles trying to maximise their time driving with passengers by increasing their occupancy. In this context, this paper proposes a multi-agent RS-enabled MoD system that allows travellers to self-organise to improve their chances to find a ride and improve the efficiency at the fleet level. Micro-communities of riders are emerging from travellers interaction and influence the MoD system. Our approach is evaluated in a multi-agent simulation, using ride requests generated from the New York City taxi dataset [ 17 ]. We show that the emergent formation of micro-communities of travellers allows riders, by walking short distances, to increase their chances to be picked by a vehicle of the MoD system fleet, reducing overall waiting times and increasing vehicles occupancy when compared to a traditional MoD system.

The rest of this paper is organised as follows. Following Section 2 reviews existing work on MoD fleet assignment strategies. Then, Section 3 introduces our multi-agent model for vehicle-riders assignment and riders-riders interaction. In Section 4, the simulation framework and setup used for evaluation are presented, and results of experiments conducted using real data are described in Section 5. Finally, Section 6 gives a summary of the work and presents some future work directions.

RELATED WORK

Existing work on Mobility-on-Demand (MoD) systems has gained interest thanks to the development of Ride-Sharing (RS) enabled platforms. Advances in autonomous driving technologies enables new transportation solutions, allowing several users to share the same journey, in a vehicle without a driver, with the potential to replace conventional mobility systems such as taxis with a significantly smaller fleet [ 1 ]. With a fleet composed of autonomous or humandriven vehicles, the problem of dynamically assigning one or more riders to a vehicle remains open, as it faces several challenges.

First, the problem is naturally distributed. Mobility demand is generally asymmetrical, in space and time, and requires to dynamically redistribute the fleet to optimise the system performance [ 26 ]. Centralised approaches have been developed [ 9, 21 ] and are applicable for a single fleet [ 23 ] and a limited spatial scale [ 24 ]. However, in the case of a dynamic fleet, with several competing fleets [ 18 ], or for a larger network, decentralised approaches such as [ 16, 15 ] seem particularly promising. Learning-based techniques [ 25 ] (and multiagent approaches [ 6 ]) enable MoD systems to adapt to demand dynamically.

In addition, this problem is multi-actor and multi-objective: users (passengers/riders) have goals (to minimise their journey time, cost, etc.) which differ from those of vehicles (to minimise travelled distances, to maximise the number of passengers, etc.). In their assignment algorithm (multi-passengers), Zhang et al. [ 27 ] define a notion of cost for vehicles, which includes distance constraints for vehicles, financial cost, and waiting time for users considered in a planned shared journey. Levin et al. [ 11 ] define spatial zones in which potential passengers automatically agree to share a vehicle already serving another request, with a preference for users who have waited the longest. In SAMoD [ 6 ], vehicle agents learn to assign themselves to existing requests, with a preference for users closer to nearby vehicles (empty or not). If this strategy is shown to have a good impact the average waiting time, some riders might be penalised by longer journeys or longer individual times. Recent approaches also proposed to compute optimal meeting points for travellers [ 14, 12 ], but are not designed to cope with dynamic and large scale systems such as in RS-enabled MoD.

Existing work highlights the potential of agent-based approaches to provide a distributed and dynamic solution to the assignment problem in RS-enabled MoD systems. Although related work tried to integrate the users needs in the route selection or during request assignment, existing approaches only considered riders goals through indirect constraints (such as travelled distance or travel time) which do not accurately reflect individual objectives. Indeed, in these approaches, travellers are considered (or modelled) as goods since they do not make any decision (for example, they never individually refuse a trip, but it is assumed that the booking platform filters not reachable requests using a fixed and high-level threshold, e.g., a maximum waiting time). In this article, we propose a modelling framework based on reactive agent that allows to specify individual objectives for the MoD system users. We also enable the emergent formation of micro-communities of travellers that allow riders to dynamically meet and share a journey in an existing RS-enabled MoD system, increasing their chance to be picked up by a vehicle operating in the fleet. Our proposal is evaluated as part of a multi-agent RS-enabled MoD system in an agent-based simulation.

A MULTI-AGENT MODEL FOR

RS-ENABLED MoD SYSTEMS

In this section, we present a multi-agent Mobility-on-Demand system model and describe how riders and vehicles interact in a ride-sharing enabled mobility environment. 3.1

Overview

The problem of rider-driver assignment (or rider-vehicle assignment in the case of Autonomous MoD) can be described in a multi-agent environment. Here agents are vehicles and riders, both trying to fulfil their own goals. The MoD booking platform allows vehicles to access pending requests from riders, and unlike traditional MoD systems, this information is shared with all riders. This framework is described in the UML diagram depicted in following Figure 1.

Each class corresponds to an agent type and implementations are used to describe agent-agent and agent-environment interaction. 3.2

Physics-inspired agents environment

The environment is a 2D representation of the city road network. The vehicle decision process is carried out in a virtual environment, modelled as a dynamic influence field such as a gravitational field. The presence of an agent has an influence on the shape of this environment, similarly to the presence of non-void mass objects in a gravitational field, as illustrated in Figure 2.

In this virtual environment and similarly to social potential fieldbased models [ 19 ], functions inspired by Newtonian physics can be applied during agent’s decision process. Agent perception is here limited to a close neighbourhood in the environment and used to compute influences on the agent. By projecting the computed agent goal from his local perception space to the virtual environment, it is possible to estimate an agent final decision (for instance, moving towards his next pick-up location for vehicles). 3.3

Riders and vehicles agents

The behaviour of an agent can be described as a state machine. It has internal variables and functions allowing it to take a decision. Decisions are then translated into actions and executed in the environment. We define two types of agents: vehicle (or driver in case of a non-self-driving fleet) and rider. 3.3.1

Rider agents

A rider i is defined by the vector Ri : fOi; Di; Pi; Ti; Ji; Sijf cit g where Oi is its origin (where the request is created), Di its destination, Pi its field of view, Ti time of the request creation, Ji denotes its impatience, Si its current state and f cit is an internal function that drives the agent decision. fit uses all the other agent parameters to minimize the waiting time and the cost of the trip. To remain active in the environment, each rider agent must keep an impatience gauge below 100%, otherwise, we assume that the client leaves the system (completing its trip using an alternative transportation mode) and his request is recorded as unserved. Riders tend to exhibit a gregarious behaviour: each rider tries to minimize is own waiting time and the cost of the journey by moving (walking) in the environment to form groups of riders. 3.3.2

Vehicle (or driver) agents

Each vehicle Vj is defined by a field of view Pj , a working time Tj and the number of free seats Cj . Similarly to riders, each vehicle has an internal function called f djt that traduces its objective of maximizing profit: Vj : fPj ; Tj ; Cj jf djt g. Each vehicle tries to pick-up more passengers and attempts to avoid travelling empty. The behavior of a vehicle can be divided into two phases: waiting (vehicle is empty waiting for new requests) and traveling (with at least one rider on board). 3.3.3

Behaviours

Interactions of an agent i are limited to its perception (close neighbourhood as defined in its filed of view Pi. The final behaviour of an agent results from the sum of interactions calculated by the agent with other entities (other agents and the environment). As opposed to related work that pre-compute meeting points for both riders and vehicles [ 14, 12 ], our approach accounts for the mutual and dynamic influence of both riders and vehicles movements in the environment. We defined 4 types of interaction, as follows:

Rider-rider interaction: this interaction is modeled as a simple linear attraction force defined, for agent i, as follows: 8Ai 2 A and 8Aj 2 Pi; F!ai = Ji:Ai:Aj (1) where A is the set of agents, Pi is agent Ai perception, composed of other riders with a similar destination. Knowledge of riders destinations in Ai neighborhood is shared by the MoD platform. Ji is a factor that modulates the force according to the impatience of the client. This interaction can be illustrated as elements sliding in a gravitational well, resulting in mutual attraction for riders with similar destination, thus this leads to the emergence of small groups of riders that gather in a close location. The emergence of such a micro-community is illustrated in the following Figure 3. Rider-vehicle interaction: To reduce the waiting time of riders, we enable them to walk to a location where he is more likely to be pick-up by a vehicle, by meeting more riders with a similar destination, hence making the newly formed group more attractive to the MoD system vehicles. When a vehicle passes (or plans to drive) near a potential rider, and goes in the same direction, the MoD system sends a notification containing the coordinates of the meeting point (on the current trajectory of the vehicle, where riders should meet). This meeting point is defined taking into account the capacity of the vehicle and its dynamics (i.e., a vehicle will be attracted if he can accommodate all the riders that are waiting there. Attraction to this point is calculated as a linear force: 8Ai 2 A and Cj 2 Pi and Cj 6= ?; F!ci = :Ji:Ai:Aj (2) where A is the set of agents, Cj denotes a shared meeting point, Pi is agent Ai perception, composed of requests with a similar destination. Factor Ji modulates the force according to the impatience of the rider and denotes the rider ’laziness’ (which also tunes how far a rider is willing to walk to join a micro-community). An illustration of computed meeting points for riders is given in Figure 4.

Vehicle-vehicle interaction: for empty (waiting) vehicles, this interaction acts as a repulsive force computed through a classical Newtonian repulsion force in 1=d2, where d is the distance between two vehicles. Considering two agents i and j located at positions Di and Dj , this force can be expressed as: ! F rij =

Di~Dj Di~Dj 2

(3)

Di~Dj for each agent i such as < IR, where IR denotes the agent perception radius. This repulsion helps to rebalance vehicles in the environment, by ensuring a more even coverage of available cars.

Vehicle-rider interaction: vehicles tend to be attracted by riders, and the intensity of this attraction is weighted by the number of riders going to a similar destination and located close to each other (for instance, forming a micro-community). All riders (even individually) impact vehicles trajectories, as follows: 8Ai 2 Pj ; F~dai =

Ji:Ai:Vj where A is the set of agents in the vehicle perception Pj , Vj is the current vehicle, is a representation of free seats in vehicle.

The definition of these interactions allows to place agents in a virtual environment. Each agent state can be computed using Newton’s law of motion and taking into account all influences (agents, destination, environment) in the agent frustum. For this computation, the environment model is considered to be continuous and decision is triggered every discrete time step, by the environment. Let ~i denote agent i acceleration and m its mass, then:

1 ~i = (F!ri + F!oi) (5)

m By substituting all the forces by their expressions (Equations 1 to 4) and integrating twice, the following equation is obtained: Z~i(t) = Z~i(t 1) +

V~i(t 1) t + ( t)2 2m ! ! ! F ri + F oi + F di (4) (6) where Z~i(t) = (xi(t); yi(t)) and V~ is the resulting velocity vector.

The sum of all forces applied to an agent (attraction and repulsion) is used to compute its speed in the virtual environment. Each time step, a new position is then computed according to the vector Z~i(t), as illustrated in Figure 5.

The sum of these interactions leads to the observation of an emergent behaviour. Customers tend to gather in small communities while drivers move to the areas with the largest community. This results in the apparition of common meeting points that act as temporary taxi stations, which locations can dynamically adapt to demand in time and space. 4

SIMULATION SET-UP

To evaluate our approach, we proposed an implementation of our RSenabled multi-agent MoD system in a novel simulation framework. Some of the well-known transportation simulation platforms include TRANSYT [ 20 ], CORSIM [ 8 ], and MITSim [ 3 ]. Each of them is designed with a different granularity, and each might be used for different applications as well. More recently, the advances in multi-agent technology have also motivated researchers to construct simulations that are capable of treating individual actors inside a transportation system as agents. Some notable open-source multi-agent simulation projects include MATSim [ 10 ] and SUMO [ 13 ]. After benchmarking, the latter did not show enough flexibility and genericity by design to be extended for our needs, and we opted for the development of a new and lighter simulation framework, less ambitious but more in line with our needs.

We designed the Python reActive Multi agEnt pLAtform (PAMELA), as an open source simulator designed for various multiagent applications. PAMELA is written in python and respects object and agent paradigms. The Core source of PAMELA is generic and offers a large number of abstractions to enable a personalised simulation (for instance, to design different applications). In this paper, we focused on modelling RS-enabled MoD vehicles and riders behaviours. Traffic conditions are considered homogeneous and are therefore not modelled explicitly. This simplifies the specification of PAMELA environment, however, it should not have an adverse impact on the realism of the simulation, since MoD fleet vehicles only constitute a small percentage of all vehicles and we assume they can operate on dedicated lanes (e.g. sharing bus lanes). A simplified overview of PAMELA framework is depicted in Figure 6. To generate ride requests, we used the open New York City taxi dataset [ 17 ], limiting the scope of this study to the lower Manhattan area (up to 14th Street). We extracted recorded trips from 4 consecutive Tuesdays (in July 2015) to extract a typical weekday demand. From this set of requests, we specifically filtered trips between 7 and 10 a.m., corresponding to the highest demand period. The final set of requests we obtained counts 11,728 trips (for 18,288 passengers, with a number of passengers per request ranging from 1 to 5). Each vehicle in the simulation has a capacity of 5 riders. Ride requests are created dynamically and rider agents are initialised according to their pick-up location. To evaluate the behaviour of our MoD system under different loads, we created several scenarios, as summarised in the following Table 1:

FCFS: a traditional centralized MoD system that relies on the first come first serve (FCFS) rule. FCFS can be summerized by a simples rules : une request by vehicle, no sharing, no rebalancing of empty fleet vehicles, no adaptative policy.

MAS: our proposal; a multi-agent RS-enabled MoD system that allow riders to walk short distances and vehicles to react to pending requests (following the interaction model presented in Section 3).

The first scenario (FCFS) is our baseline scenario, showing the behaviour of a traditional MoD system. For our proposal, we evaluated the impact of two different fleet sizes, selected to show a case where supply is static and not sufficient to fulfill the demand (MAS 1) and then a dynamic demand where 45 additional vehicle agents are added to the simulation 200 min after simulation starts (MAS 2). The latter scenario (MAS 2) was designed to determine the expected limit of fleet size scaling. 4.3

Metrics

To evaluate if the respective objectives of vehicles and riders are met, we studied the following list of indicators:

Number of passengers per vehicle: allows to observe if riders

are sharing their trips and if vehicles are serving more than one request at a time. A higher value usually results in a better efficiency at the system level.

Number of kilometers without passengers: this indicator

records empty trips of vehicles (e.g. when driving to pick up new requests). From both vehicles and the system perspective, lower values indicate a better operation of the fleet.

Riders waiting times: the percentage of unserved requests is directly linked to riders waiting time; after waiting 10 min, we assume that the request is discarded and the trip is cancelled. One objective of our approach is to increase the chances for riders to be selected by a vehicle, meaning that overall waiting times should be reduced.

Riders walking distance: our model introduces an incentive to walk short distances for riders. We expect that our proposal allows for shorter waiting times at the cost of a few hundred meters walked by riders to meet others to share a ride.

Travelled distance: by allowing ride-sharing, vehicles can take a short detour to pick up more passengers, and the introduction of a vehicle/client interaction in the model tends to incentive drivers to take routes that pass closer from pending requests. Therefore, paths taken by vehicles can be less direct than the shortest path between one request origin and destination.

Unserved requests: indicates the overall level of service reached by the MoD system, assuming that a request not assigned to a vehicle within 10 min is considered as unserved. 5

EVALUATION

The evaluation of our approach has been carried out in the PAMELA simulator. We investigated the behaviour of riders and vehicles in two different set-ups: (1) our proposal (MAS), an RS-enabled MoD system where riders and vehicles influence each other and where riders can walk to meet and form micro-communities and (2) a baseline modelling a traditional MoD system where riders are served on a first-come first-served (FCFS) basis. FCFS baseline allows to have a first comparison with the most-used model in related work. We evaluate the performance of the two MoD systems from the perspective of vehicles and riders, then at the system level. 5.1

Effects on vehicles

We begin our investigation by studying the effect of rider-vehicle, vehicle-rider and rider-rider interaction from the vehicles perspective.

s r e t e 1500 lom rse ik g f n roeb ssaep1000 m t ltaenud itohuw 500 u m u C 0 0

FCFS MAS 1 100

Figure 7 shows the distance travelled by vehicles without any passengers. Vehicles spend less time looking for passengers with MAS approach as compared to FCFS. This confirms that the combination of vehicle-vehicle interaction and vehicle-rider interaction allows empty cars to better distribute on the network and to find pending requests more easily. Reducing empty travelled distance in MoD systems directly links to more profits from the system perspective, traducing a better use of the operating fleet. However, further investigation of the number of passengers travelling in vehicles is required to confirm that vehicles are not solely travelling for a single request at a time.

0.4

Vehicles occupancy is shown in Figure 8. We observed that enabling ride-sharing, in combination to vehicle-* forms of interaction leads to an increased number of passengers on board. While most trips are happening with a single passenger in the FCFS baseline, this trend is completely reversed for our proposal: here, most of MAS vehicles carry between 3 to 4 passengers. This confirms that vehicles’ objectives defined in the model are met, allowing at the same time for shorter empty travelled distance and an increased overall occupancy. 5.2

Impact on riders

As our proposal introduces more flexibility for riders, enabling them to dynamically form micro-communities and meet on expected vehicles routes, results should confirm this can benefit to riders. Figure 9 depicts the distance travelled by riders to reach their destination. 5

10 15 20 Travelled distance (km) 25

Results show that riders journeys are longer with our approach: MAS allows vehicles to take a detour to serve more requests. The average additional distance travelled by riders in MAS is 971 meters, which corresponds to an extra 3 minutes travel time. FCFS uses direct trips from riders origin and destination, showing the shortest distance riders could expect to travel when they are not sharing a vehicle.

FCFS

MAS 1 2 3

4 5 6 7 Riders waiting time (min) 8 9

This short detour and extra travel time is however balanced by much shorter waiting times for riders, as highlighted by Figure 10. In our simulation set-up, we observed that while average waiting time in FCFS is around 5 to 6 minutes, a significant proportion (around 25%) of riders have to wait 9 min. Similarly to related work [ 27, 6 ], we set a timeout when riders waiting time reaches 10 min. The distribution depicted in Figure 10 then suggests that in FCFS, a significant number of requests are discarded after riders waited too long. In MAS, on average, a rider will wait 3 minutes less than in a FCFS system before being assigned to a vehicle. This arises from the movement and attraction that riders have on vehicles (which is weighted by the riders group size).

However, to form micro-communities, riders need to walk and a major part of the acceptability of the system is to ensure that walking distance can be reasonable. In our simulations, we observed that 26% walked to meet other riders (Figure 11), and 31% walk towards a vehicle pick-up location (Figure 12). In total, 44.1% of riders walked.

To Rider 100

200 300 walking distance per request 400

In MAS, riders can walk for a maximum of 400 m to meet new riders and form micro-communities. The distribution of walking distance from riders to riders is depicted in Figure 11. We observed a uniform distribution of walking distances, suggesting that riderrider interaction is symmetrical, and solely depends on the riders origins. This can be explained by the definition of rider-rider interaction (Equation 1) that does not account of the riders individual group To Vehicle 100

200 300 walking distance per request 400 size. This influence could be further investigated by tuning this interaction. From Figure 12, we observed that riders walk on average 112 meters before meeting a vehicle, confirming that this extra distance, which can easily be covered, should not significantly impact the system acceptability. 5.3

System performance

From the MoD fleet system perspective, one of the most important metric to maximize is the overall level of service i.e., minimizing the number of requests missed by vehicles or discarded by riders. The results presented in this section confirm the benefits of emergent micro-communities formation in an RS-enabled MoD system. However, simulations also highlighted that the benefits for riders are balanced by additional travelled distance (detours taken by vehicles when riders share a trip) and short walking distances (to both meet other riders and/or reach a potential vehicle route). Under our simulation set-up, this additional times (respectively on average 3 mins in-car and up to 10 mins walking) were limited but can be important for the acceptability of the system, hence would require further investigation. The additional walking distance observed is however under the threshold (500-600m) commonly accepted by related work [ 14, 12 ]. We also showed that, while vehicles tend to be attracted by larger groups of riders, we defined rider-rider interaction without accounting for the individual groups sizes. A modified form of this interaction could result in different micro-communities formation and its influence on vehicles and the system should be studied. 6

CONCLUSIONS AND FUTURE WORK

This paper investigated a novel approach to further improve the efficiency of a fleet of vehicles operating in a ride-sharing enabled Mobility-on-Demand system. While existing research focuses on optimising vehicle-riders assignment or tries to better balance the fleet to anticipate upcoming demand, existing approaches consider the MoD fleet management problem by taking the perspective of the fleet manager. We studied how riders (i.e. MoD system customers) objectives could affect the behaviour of vehicles and how could riders take part in the decision when assigning cars to requests. Our proposal is to enable riders, by sharing information about current pending requests, to walk and meet at a specific location where they are more likely to find a vehicle to drive them to their destination. In addition, we wanted to model how larger groups of travellers (that we called micro-communities) can impact the behaviour of vehicles (or drivers).

We proposed a multi-agent model where we defined 4 different types of interaction, which account for the mutual effect riders and vehicles can have between each other. This allows to design, through a virtual environment ruled by physics-inspired influences, complex behaviours that can benefit at the system level: cars tend to rebalance by avoiding to stay to close from each other when waiting empty; riders from several requests can meet and then walk to a cross a potential vehicle route; and vehicles take small detours to get closer to pending requests. Within a simulation framework and by comparing our proposal to a traditional MoD system, we have shown that it is possible to increase the quality of service and the efficiency of a fleet of vehicles on demand by allowing flexibility and self-organisation, enabling to better cover both vehicles and riders objectives. First results, when increasing fleet size, tend to show that our approach can scale dynamically, but further evaluation is required to investigate how the model would react to a growing number of requests.

When discussing the results, we highlighted some future work avenues that should be investigated. For instance, our multi-agent model could be easily extended to allow riders to adapt their behaviour to several MoD fleets in competition [ 18 ] or to different transportation mode options available. Riders, similarly to vehicles [ 7 ], could learn the locations where they are more likely to encounter cars based on historical data. Traffic congestion should also be integrated in the riders and vehicles decision, allowing pick-ups or drop-off in close and less busy roads.

FCFS MAS 1

MAS 2 0 100

Figure 13 allows to compare the efficiency of FCFS, MAS 1, and MAS 2: a variant of MAS 1 where 45 additional vehicles are introduced 200 minutes after the simulation starts. First, MAS in general shows a better overall efficiency, serving more requests than FCFS thanks to ride-sharing and riders interactions. The increased number of vehicles in MAS 2 also confirms that the performance at the system level depends on the fleet size. Interestingly, while FCFS shows a stable number of unserved requests, both MAS 1 and MAS 2 seems to improve over time. This is due to the vehicle-vehicle interaction, that results in a more evenly distributed relocation of empty car on the network. Further rebalancing schemes should however be investigated in both FCFS and MAS to estimate the potential gain of this behaviour when compared to centralized strategies.

ACKNOWLEDGEMENTS

This research has been sponsored in part by a research grant from Science Foundation Ireland (SFI) under Grant Number 16/SP/3804 and by the Irish Research Council through ”Surpass: how shared autonomous cars will transform cities” New Horizons award.

References

[1] Javier Alonso-Mora , Samitha Samaranayake, Alex Wallar, Emilio Frazzoli, and Daniela Rus, ' On-demand high-capacity ride-sharing via dynamic trip-vehicle assignment' , Proceedings of the National Academy of Sciences , 114 ( 3 ), 462 - 467 , ( 2017 ).

[2] Marie-Flavie Brasseur , Florian Lezec, and Guillaume Wemelbeke, ' Les taxis et vtc en 2017-2018 rapport de l'observatoire national des transports publics particuliers de personnes' , Technical report , ( 2020 ).

[3] W Burghout , ' Mitsimlab model description. evaluation of the mitsim microsimulation model' , Technical report, Internal report, Department of Infrastructure and Planning , Royal Institute . . . , ( 1999 ).

[4] T Donna Chen , Kara M Kockelman , and Josiah P Hanna , ' Operations of a shared, autonomous, electric vehicle fleet: Implications of vehicle & charging infrastructure decisions' , Transportation Research Part A: Policy and Practice , 94 , 243 - 254 , ( 2016 ).

[5] Simona Frazzani , Gabriele Grea, and Alessandro Zamboni, ' Study on passenger transport by taxi, hire car with driver and ridesharing in the eu' , Final Report for the European Commission , 2015 - 564 , ( 2016 ).

[6] Maxime Gue ´riau and Ivana Dusparic, 'Samod: Shared autonomous mobility-on-demand using decentralized reinforcement learning' , in 2018 21st International Conference on Intelligent Transportation Systems (ITSC) , pp. 1558 - 1563 . IEEE, ( 2018 ).

[7] Maxime Gue ´riau, Federico Cugurullo, Ransford A . Acheampong , and Ivana Dusparic, ' Shared autonomous mobility-on-demand: Learningbased approach and its performance in the presence of traffic congestion' , IEEE Intelligent Transportation Systems Magazine , ( 2020 ).

[8] Abolhassan Halati , Henry Lieu , and Susan Walker, ' Corsim-corridor traffic simulation model', in Traffic Congestion and Traffic Safety in the 21st Century: Challenges, Innovations, and OpportunitiesUrban Transportation Division, ASCE; Highway Division, ASCE; Federal Highway Administration, USDOT; and National Highway Traffic Safety Administration, USDOT ., ( 1997 ).

[9] Sebastian Ho ¨rl, Milos Balac, and Kay W Axhausen, ' Dynamic demand estimation for an amod system in paris' , in 2019 IEEE Intelligent Vehicles Symposium (IV) , pp. 260 - 266 . IEEE, ( 2019 ).

[10] Andreas Horni , Kai Nagel, and Kay W Axhausen, The multi-agent transport simulation MATSim , Ubiquity Press London, 2016 .

[11] Michael W. Levin , Kara M. Kockelman , Stephen D. Boyles , and Tianxin Li , 'A general framework for modeling shared autonomous vehicles with dynamic network-loading and dynamic ride-sharing application' , Computers, Environment and Urban Systems , 64 , 373 - 383 , ( 2017 ).

[12] N. Li , L. Kong , W. Shu , and M. Wu , ' Benefits of short-distance walking and fast-route scheduling in public vehicle service' , IEEE Transactions on Intelligent Transportation Systems , 1 - 12 , ( 2019 ).

[13] Pablo Alvarez Lopez , Michael Behrisch, Laura Bieker-Walz, Jakob Erdmann, Yun-Pang Flo ¨ttero¨d, Robert Hilbrich, Leonhard Lu¨cken, Johannes Rummel, Peter Wagner , and Evamarie Wießner, ' Microscopic traffic simulation using sumo' , in The 21st International Conference on Intelligent Transportation Systems. IEEE , ( 2018 ).

[14] Yan Lyu , Victor CS Lee, Chi-Yin Chow , Joseph Kee-Yin Ng , Yanhua Li , and Jia Zeng, 'R-sharing: Rendezvous for personalized taxi sharing' , IEEE Access , 6 , 5023 - 5036 , ( 2017 ).

[15] Michal Maciejewski and Joschka Bischoff, ' Congestion effects of autonomous taxi fleets' , Transport , 33 ( 4 ), 971 - 980 , ( 2018 ).

[16] L Miguel Mart ´ınez , Gonc¸alo Homem de Almeida Correia, Filipe Moura, and Mafalda Mendes Lopes, ' Insights into carsharing demand dynamics: Outputs of an agent-based model application to lisbon , portugal', International Journal of Sustainable Transportation , 11 ( 2 ), 148 - 159 , ( 2017 ).

[17] NYC Taxi and Limousine Commission . Tlc trip record data , 2020 .

[18] Venktesh Pandey , Julien Monteil, Claudio Gambella, and Andrea Simonetto, ' On the needs for maas platforms to handle competition in ridesharing mobility' , Transportation Research Part C: Emerging Technologies, 108 , 269 - 288 , ( 2019 ).

[19] Y. Rasekhipour , A. Khajepour , S. Chen , and B. Litkouhi , ' A potential field-based model predictive path-planning controller for autonomous road vehicles' , IEEE Transactions on Intelligent Transportation Systems , 18 ( 5 ), 1255 - 1267 , ( 2017 ).

[20] Dennis I Robertson, ' Transyt: a traffic network study tool' , ( 1969 ).

[21] Claudio Ruch , Sebastian Ho¨rl, and Emilio Frazzoli, ' Amodeus, a simulation-based testbed for autonomous mobility-on-demand systems' , in 2018 21st International Conference on Intelligent Transportation Systems (ITSC) , pp. 3639 - 3644 . IEEE, ( 2018 ).

[22] Joseph Schwieterman and C Scott Smith , ' Sharing the ride: A pairedtrip analysis of uberpool and chicago transit authority services in chicago , illinois', Research in Transportation Economics, 71 , 9 - 16 , ( 2018 ).

[23] Andrea Simonetto , Julien Monteil, and Claudio Gambella, ' Real-time city-scale ridesharing via linear assignment problems' , Transportation Research Part C: Emerging Technologies, 101 , 208 - 232 , ( 2019 ).

[24] Reza Vosooghi , Jakob Puchinger, Marija Jankovic, and Anthony Vouillon, ' Shared autonomous vehicle simulation and service design' , Transportation Research Part C: Emerging Technologies, 107 , 15 - 33 , ( 2019 ).

[25] J. Wen , J. Zhao , and P. Jaillet , ' Rebalancing shared mobility-on-demand systems: A reinforcement learning approach' , in 2017 IEEE 20th International Conference on Intelligent Transportation Systems (ITSC) , pp. 220 - 225 , (Oct 2017 ).

[26] Konstanze Winter , Oded Cats, Bart van Arem, and Karel Martens, ' Impact of relocation strategies for a fleet of shared automated vehicles on service efficiency, effectiveness and externalities' , in 2017 5th IEEE International Conference on Models and Technologies for Intelligent Transportation Systems (MT-ITS) , pp. 844 - 849 . IEEE, ( 2017 ).

[27] Wenwen Zhang , Subhrajit Guhathakurta, Jinqi Fang, and Ge Zhang, ' The performance and benefits of a shared autonomous vehicles based dynamic ridesharing system: An agent-based simulation approach' , in Transportation Research Board 94th Annual Meeting , ( January 2015 ).