Mobility Service

Figures can be modified from this google folder.

The following video training sessions are available:

• Overview of the Mobility Service framework: download
• Code walk-through: download

Documentation for "pricing and passenger choice" feature

Documentation for "how to configure controller"

Introduction

A Mobility Service is a service provided by an organization (either public or private) satisfying trip requests from users. There may be different mobility services running in parallel, e.g. taxi service, Uber, Lyft, ..., each one associated with a MobilityServiceController. A single user may have access to different services at the same time and can choose on a trip-base. Actual trips are carried out by drivers. A driver may join different services at the same time and is thus able to receive communication from any of them. Note that, in case of Autonomous Cars (AVs), we assume that the driver is a robot. When a MobilityServiceDriver is created, she does nothing until she sends a joinMsg to one or more service controllers and receives the related confirmations.

The basic function of the controller is to receive join and leave messages from drivers. The OnHailTaxiController only has this function, in fact just authorizing taxi drivers to operate in the streets and leaving them free to choose their pick-ups and drop-offs, the places where to cruise, etc. On the contrary, an OnCallController has richer functions. It receives TripRequestMsg by users, keeps them in a request queue and, periodically, decides a schedule for a subset of drivers under its control, specifying the sequence of pickups and dropoffs.

A MobilityServiceUser generates a TripRequest to a specified service, denoted with a serviceId. Only a MobilityServiceDriver who has joined that service can pick up this user. A trip request can be expressed in two ways, depending on the serviceId:

• If the service is of type OnHailTaxi, the user hails on the street and can be picked up by any driver joining that service
• If the service is of type OnCall, the user sends a TripRequestMsg to the respective controller and can be picked up only by the driver that the controller has assigned to her, following a procedure described later in this document.

The classes we use to model mobility services are depicted in the figure below. __AA: is the code compliant with this now? __

Driver status

A MobilityServiceDriver can be in one of the states depicted ( bòue, yellow or green rectangles) in the figure below. A driver can pass from a state to another if a specific event, serving as trigger (red rectangles), occurs. With the trigger "?" I denote an event that we have still to define (AA: I should look at the taxi document to see if already defined). Transitions from a state to another are denoted by arrows. Note that some transition can happen only if the driver is joining an OnHail service or an OnCall state. All the other transitions can happen in either case.

Once the driver is created in the simulation, her initial state is inactive. In this state, she does nothing. After she joins a service, shed goes to the aggregated state free: she exists but she is not serving any trip or schedule. This aggregated state is composed of three states: if cruising, the driver is moving in the road network. If she decides to stop immediately, she will go immediately to the waiting state. If she decides to stop at a location different from her current one, she will be driving to parking and, once the target parking is reached, she will start waiting. Note that by defining free as an aggregated state, we allow that, whenever a transition enters this state, we implicitly assume that the driver will be in one of the the component states. For example, after joining a service, a driver can enter in any of the component states. Similarly, if a transition is exiting the free aggregated states, it means that this transition is allowed to occur if the driver is in any of the three component states. If a driver is joining a OnHail service, she can pick up a user, provided that that user has expressed a TripRequest for an OnHail service that the driver is joining. In this case, the driver enters the serving OnHail trip state, from which she will exit only after she drops the user off, after which she returns to the free state. If the driver is joining a OnCall service, she can accept a schedule from the respective controller and start serving that schedule, i.e., start obeying to the instructions the controller imposed. When a driver is serving a schedule she may be carrying a user, or her vehicle may be empty, e.g., if she is going to a pick up location imposed by the controller. While serving a schedule the driver can accept on line modifications of the schedule. Only after the schedule is completed, the driver returns to the free state. When the driver is free, she may decide to finish operating. A particular case of the end of operations is when a driver does a shift and gives the vehicle to another driver. In any case, before the driver finishes operating, she has to bring the vehicle in some specific location, e.g. the shift location, a garage, etc. To do so, she enters the driving to finish state, in which she does not accept neither schedules nor pick-ups. After she reaches the intended "end location" she sends a leave message to all the services she is joining and she disappears from the simulation.

AA: with respect to the taxi specification, I made these changes:

• I renamed the state queueing to waiting. waiting may happen in a specific taxi stand, parking location, or aside on the street. This is why I preferred a more generic name.
• I duplciated occupied in serving OnHail trip and serving schedule
• I renamed drive for driver shift in driving to finish, since if a driver is joining, at the same time, an OnHail service and an OnCall service, if he does the shift with a driver of the OnHail service, she has, in any case, to finish all her activities, with all the services she is currently joining. Therefore, the OnCall service she was joining, in the example I am giving, does not have the visibility of whether the driving is shifting in the other OnHail service or not. In general, the driver is finishing all her activities, since she has no more a vehicle to operate.

An explanation of the states follows:

• inactive: the driver cannot do anything. This is the initial state after the driver is created in the simulation.
• cruising: the driver moves into the road network. This can be done in three ways: 1 By default, the driver cruises randomly, i.e., at any intersection she chooses to go in one of the next links randomly; 2 If the driver is subscribed to the OnCall controller and she is executing a CruiseTAZ schedule item (i.e. command), then the driver movement is not random but she follows the path to one of the node of the TAZ specified in the CruiseTAZ schedule item; this node is selected randomly from all the nodes in that TAZ. Note that CruiseTAZ schedule items are generated by the Rebalancer, a component of the controller whose goal is to distribute the drivers where the demand is expected to be denser in the next future 3 the driver cruises toward specific areas or parking spot, chosen independently, without any command from the controller. The driver choice model was presented in HEART Conference, 2017, by Bat-hen Nahmias-Biran et Al. The cruising state can be in one of the two mutually exclusive sub-states
  • cruising and searching: the driver moves in the road network and is willing to pickup any user hailing on the street. This only applies to a driver subscribed to a OnHail service.
  • cruising only: not willing to pick up anyone.
• drive to taxi stand and searching: the driver is moving toward the taxi stand and she is willing to pick up users, subject to the constraint above
• queueing at taxi stand and searching: the driver is in the taxi stand, she does not move and she is willing to pick up, subject to the constraint above
• servicing hailer: the driver is carrying a user to the destination node. In this state, she cannot pick up anyone else
• driving to shift: the driver is finishing her work activity and she is driving toward the location in which the shift to another driver will happen. She cannot pickup anyone in this state.
• waiting: the driver is parked.
• scheduled: a driver is performing a schedule she has previously accepted. In other words, she is performing what the controller has commanded, e.g. she is driving toward a pick-up or drop-off location. In this state, she may or may not carry users, subject to the constraint that the users cannot exceed the vehicle capacity.

Interaction with the controller

The sequence diagram below is an example of typical sequence of interactions between the entities specified so far. Note that, in case of OnHailTaxiController, the interaction stops at the confirm to the joinMsg.

MobilityServiceControllerManager (i) reads from the input (DB or XML?) the mobility services that must be instantiated, (ii) instantiate the relative MobilityServiceControllers and (iii) keeps a map of the pointers to them vs. their identifiers. Whenever a MobilityServiceUser is constructed in the simulation, she gets from the Manager a list of pointers to the Controllers to which that user has access. Note that Manager is an pure simulation abstraction and it does not match any entity in reality. Indeed, in reality users already knows a list of services that they can access (they can browse the web, make a call on the phone, use an application to contact those services) and do not need any external entity that tells them. Moreover, there is no entity that "creates" services, as they are run by independent organizations.

Each MobilityServiceDriver chooses for which service she wants to work. At any moment, she can send a joinMsg or leaveMsg to the different controllers. If she is currently joining a OnCall service, she will receive the schedulePropositionMsgs from the respective controller. Each joinMsg is directed to a single controller. In case this controller handles different subservices (e.g., Uber XL, Uber pool, etc.), the driver can specify the list of subServiceIds.

Users can send TripRequestMsgs to different OnCall controllers, which keep these requests in a pending list. This TripRequestMsg has a field ACCEPT. By default it is set to 0, meaning that the user want to see the offer from the controller before accepting the trip. In case the controller offers different subservices, the user can express the list of subServiceIds she is interested in (for example pool service or exclusive service). Every scheduleComputationPeriod, an OnCallController calls on itself computeSchedules(), which computes a list of Schedules. Note that computeSchedules() is an algorithm that is specific of the kind of service (this is why it is abstract). A schedule defines the sequence of operations the Controller wants its drivers to perform, e.g., moving from a node to another (either leaving to the Driver the freedom to choose the path or specifying it), stopping at a certain node to recharge energy, to have a break or to pick OnCallMobilityServiceUsers up or drop them off. Based on the computed schedules, the controller generates TripPropositions to the users, specifying the exact pick up and drop-off location, a time window in which the user must wait at the origin location to be picked up, a time window in which she is expected to arrive to the drop-off location and a price. A OnCallMobilityServiceUser may accept one of the propositions or decline all. In case she accepts, she sends a TripRequestMsg with ACCEPT=1 to the controller, which, in turn, selects a OnCallMobilityServiceDriver and sends the Schedule to the Driver. The OnCallMobilityServiceDriver evaluates the Schedule and can accept or refuse. If she accepts, the driver starts to obey to the schedule. Otherwise, the controller must find another schedule to satisfy the proposed trip. While the driver performs her schedule, she notifies to the controller every time she drops off a user.

Note that the user can also directly send a TripRequestMsg with ACCEPT=1. This means that she is implicitly accepting any TripProposition that the controller can propose her. In this case, the controller does not need to send any TripProposition and will try to assign the request immediately.

Note also that the TripPropositionMsg can also be a refusal: the controller refuses to serve this request. The controller may decide to refuse if it estimates it is unable to serve the request.

For simplicity, for the moment, we assume that the driver always accept the ScheduleProposition.

An example of schedule exchange follows (the figure is off for the moment):

Types of controllers

On Hail Taxi Controller

As explained before, a OnHailTaxiController has the only function to authorize drivers to pick up users expressing requests to itself. The drivers joining this controller are free to pick up any of these users, wherever they are. They are also free to move in the road network as they want.

On Call Controller

In this kind of service, the Driver is free to decide the path to reach the next pick up location from its current one, the drop off location and what to do, e.g. where to cruise, in case no passengers are in. The schedules of an on-call service with drivers are a sequence of ScheduledPickUps and SchedulingDropOffs. In general, the same SchedulePickup may concern more than one user. The same applies to a ScheduledDropOffs. In general, more than one user can be in the vehicle at any moment, as long as the capacity of the vehicle is not exceeded. The parameter maxSharing of the controller determines the maximum number of people that can be present at a moment, subject in any case to the maximum capacity of the vehicle. If a controller has maxSharing=1, then no sharing is possible and a pickup up can only be followed by a drop-off (and not another pickup). In this case, the service represent an on-call taxi service (how to model the situation when I am with my friends and we decide to take a taxi together?).

GreedyController

It is the simplest controller is implemented in SimMobility. It allows no sharing, one passenger only at a time can be assigned to a vehicle. It is not able to handle TripRequestMsg with ACCEPT=0. The computeSchedules() is a simple greedy algorithm. Every time it is invoked (at any computation period), it iterates over the requests received and, for each, iterates over the available drivers (the ones that are not currently busy with some other passenger) to assign the closest to the pick up point of the request. This driver will be removed from the list of available drivers.

SharedController

It is able to match 2 passengers to the same vehicle. Only vehicles that are completely free, with no passengers, are considered by the algorithm. It is not able to handle TripRequestMsg with ACCEPT=0. The function computeSchedules() implements the algorithm in [Ratti]. In few words, a "feasibility graph" is constructed, where the nodes are the requests. An edge is drawn between two requests if it is possible to serve both in the same trip. To verify this, for each request we first estimate the time needed to go from the pick up location to the dropoff location, supposing there is one vehicle entirely dedicated to that request and able to be, instantaneously, at the pick up location. We call this time desiredTravelTime. Then, we compute one possible sequence of pickups and dropoffs of the two requests. Denoting with o1, o2, d1,d2 the origins of the 1st and 2nd request and the destinations of the 1st and 2nd requests, respectively, one sequence is o1,o2,p1,p2. In this case, the passenger 1 would suffer an extra delay, due to the fact that the vehicle is not exclusively serving her, but is also serving passenger 2. This extra time is the difference between the time to go over the sequence o1,o2,p2,p1 and the desired time for passenger 1. Similarly, that sequence induces an extra delay to passenger 2. The sequence s feasible if the extra delay for both passengers is below a extraTripTimeThreshold. There may be different sequences to serve two requests. If there exists at least one feasible sequence, than we say that the two requests can share a trip, and we draw an edge in the feasibility graph. We evaluate all the possible request pairs and draw edges in the feasibility graph, if possible. After we have constructed the entire feasibility graph, we run a maximum matching algorithm to select a subset of edges. The edges we have selected represent the pairs of requests we want to serve with one vehicle. Then, we iterate over all these selected pairs, and we assign each to the vehicle closest to the first pick up in the sequence of pickups and dropoffs.

FrazzoliController

(not tested yet - work in progress) FrazzoliController is able to match multiple requests to the same driver, up to a parameter MobilityServiceController::maxAggregatedRequests, that can be configured (hard-coded, for the moment, in MobilityServiceController.cpp). It is not able to handle TripRequestMsg with ACCEPT=0. The algorithm is incremental, i.e., it can match a request to a driver that is already carrying some other passengers, triggering a modification of its schedule in that case. The function computeSchedules() implements Alg.1 and Alg.2 of [Frazzoli], supplemental material. Similarly to the SharedController, it is based on graphs. In particular, two graphs are constructed: 1. an RD_Graph, which stands for Request-Driver graph (corresponding to the RV graph of the paper) and 2. an RGD_Graph. which stands for Request-Group-Driver graph (corresponding to the RTV graph of the paper). The nodes of the RD graph are requests and drivers. An edge is drawn between two requests if they can share the same driver, both suffering an extra-delay below the extraTripTimeThreshold, as in the SharedController. Moreover, an edge is drawn between a driver and a request if 1. the driver is able to pick up the driver within the MobilityServiceController::maxWaitingTime and 2. that request does not suffer an extra delay larger than MobilityServiceController::extraTripTimeThreshold and 3. the same waiting time and extra time constraints are satisfied for all the requests that have been assigned to the driver in the previous computation periods. After a the RD graph is completed, we construct the RGD graph. The nodes here are requests, drivers and groups, where a group is a subset of the requests. A group of requests is feasible is they can be served together, respecting the waiting time and extra time constraints for all of them. If this is the case, a node corresponding to that group is added to the graph and an edge is drawn between that group and all the components requests. Then, an edge is drawn between a group and a driver if the driver can serve all the requests in the group respecting the time constrains for the requests in the group and for the requests that have been already assigned to her in previous computation periods. In the final phase, we select some of these edges.

IncrementalSharing

(TODO: FOR THE MOMENT, SHAREABLE/NON-SHAREABLE REQUESTS ARE NOT DISCERNED) It is able to match 2 passengers to the same vehicle. The algorithm is incremental, i.e., it can match a request to a driver that is already carrying some other passengers, triggering a modification of its schedule in that case. It is supposed to be faster than SharedController and FrazzoliController. Moreover, it can also handle shareable and non-shareable requests.

When a user sends a TripRequestMsg, it specifies in a field [TODO: WRITE THE NAME OF THE FIELD] whether she is available to share her trip with other users or not. Therefore, in the matching computed in computeSchedules(), the controller has to take care to satisfy the "shareable/non shareable" requirement specified in each request. The unserved shareable and non-shareable requests are maintained in two different lists. Moreover, the controller keeps different lists of subscribed drivers: i) unavailableDrivers, i.e., those who are already at full passenger capacity or are currently handling a non-shareable user, ii) partiallyAvailableDrivers, i.e., those currently handling some shareable requests and are not at full passenger capacity yet and iii) availableDrivers, who are currently handling no requests. Note that we do not have an explicit data structure for unavailableDrivers, they are just the subscribed drivers who are neither among the available nor the partially available drivers.

Matching algorithm

At every computation period (with this controller the suggested computation period is few frame ticks, e.g., 1 to 5 frame ticks), we perform the matching algorithm. We divide the computation in 3 stages.

• Stage 1. At the beginning of the schedule computation period, the controller attempts to match the unserved shareable requests to the partiallyAvailableDrivers. To do so, it iterates over all these drivers and, for each, over all the unserved shareable requests. A request can be assigned to a partially available driver if there exists a re-arrangement of the driver schedule such that the new request can be satisfied within the time constraints (waiting time and extra delay constraints, as explained in the previous sections) and also the requests previously assigned to the driver continue to meet their constraints.
• Stage 2. After we are done with the partially available drivers, we try to match the unserved non-shareable requests to the available drivers. Again, for each of these drivers, we iterate over all the unserved non-shareable requests and we are able to assign a request if the driver can arrive at the pick up point within the MobilityServiceController::maxWaitingTime.
• Stage 3. Finally, we repeat the operations of stage 2, with the shareable requests that have not been matched in stage 1. Note that if we are only dealing with non-shareable requests, we do nothing in stage 1 and stage 3. On the contrary, when only dealing with shareable requests, we do nothing in stage 2. More details can be found in this technical report.

Interaction with user

TODO: So far, we have only talked about request with ACCEPT=1. All the requests with ACCEPT=0 are handled at the end of the matching algorithm. To handle requests with ACCEPT=0, the controller has to measure its performance. In particular, it observes the rate of assigned requests and the length of the queue. Based on these measure, it estimates in how much time it is able to assign the request. The controller will send back this estimation to the user, in the TripPropositionMsg. If the user accepts, later she will send another TripRequestMsg with ACCEPT=1.

Aging

TODO: At the end of the matching algorithm, there may be still requests with ACCEPT=1 in the queue. These requests have an age. If they are still in the queue, and thus have not been matched, this age is increased. If the age is above a certain threshold, these requests are moved to an emergencyQueue, meaning that we have to serve these requests as soon as possible. If the emergencyQueue is non empty, before running the matching algorithm on the ordinary requests, we run the matching algorithm on these requests only. We run the matching algorithm in several iterations, with increasing values of maxWaitingTime and toleratedExtraTime, until all these requests are served or no vehicles are present anymore. Note that we are theoretically willing to increase the maxWaitingTime and the toleratedExtraTime to the infinite, i.e., we want to serve these requests, even if with poor level of quality.

TODO: Note that if the TripRequestMsg is with ACCEPT=1, every time we find a feasible assignment with the algorithm above, we really assign that request to the feasible driver, and we remove the driver from the pool of available drivers or partially available drivers. On the contrary, if ACCEPT=0, we keep the driver from the pool of available or partially available drivers as well, we increase a counter requestWaitingToConfirm and we send only a TripPropositionMsg to the user with an estimation of the waiting time and the additional trip time due to detour (these are still to be computed, let us start with waiting time first)

ProximityBasedController

(not tested - work in progress) It is able to associate to the same vehicle up to maxAggregatedRequests. The algorithm is incremental, i.e., it can match a request to a driver that is already carrying some other passengers, triggering a modification of its schedule in that case. The logic of computeSchedules() is summarized as follows. First, we will try to assign request to drivers trying to respect the time constraints. It may happen, however, that after doing this attempt, which we call "1st round", there may be some un-associated requests and drivers that have nothing to do. The reason why this may happen is that those drivers may be too far away from the request pick up locations. We store those drivers in this emptyDriversAfter1stRound list. Then, we will perform a "2nd round" in which we associate each un-associated request to one of these empty drivers. This controller aims to aggregate together requests that have pickups and dropoffs sufficiently close each other, so that the vehicle does not have to make long detours to pickup and dropoff all the passengers. For this, a pickUpBarycenter and a dropOffBarycenter of the current schedule of a driver is computed. If the pickup location of a new request is sufficiently close to the pickUpBarycenter and the same applies to the dropoff, then the request is associated to that driver and the barycenters recomputed accordingly. More precisely, a request is associate to the driver if 1. the time to go from her current position to the pick up location of the new request is within maxWaitingTime and 2. the time to go from that pick up location to the current pickup barycentre is within toleratedExtraTime and 3. the same applies to the dropoff. Note that here toleratedExtraTime is used improperly, but we re-use this parameter just to avoid proliferation of additional parameters. [AA: we may want to change it].

Implementation in SimMobility

In MidTerm, Drivers should be created by MT_PersonLoader, instantiated in performMainSupply(). In ShortTerm, Drivers should be created in the function loadAgentsInOrder(..).

The interactions between SimMobility and Mobility Services are as depicted below.

Schedule

A Schedule is a sequence of ScheduleItems, each being a command that the controller sends to the driver. Here, we report the most common schedule items, but the developer can introduce new ones as needed.

• PickUp: the controller instructs the driver to pick up a User at a certain node. The node and the user id are specified in this schedule item
• DropOff: the controller instructs the driver to drop off a User at a certain node. The node and the user id are specified in this schedule item
• CruiseTAZ: the driver must cruise in a specific Traffic Analysis Zone (TAZ), i.e. a specific area of the city
• GoToPark [not important now]: the controller wants the user to go to a specific node and park there. If a station id is specified, the driver will park at the station. Otherwise, she will park on the street. This schedule item may be used, for example, to implement fleet rebalancing.

Rebalancing

Rebalancing means directing vehicles that are in the available state to a specific area of the network, in order to anticipate future trips requests that are predicted to come from there. In an OnHail service, each single driver decides where to go based on his experience. In an OnCall service the same may happen but the controller can as well instruct drivers where to go when they are available. In this section, we only describe rebalancing mechanisms handled by the controller. We have different possibilities:

• Reactive probabilistic rebalancing: every time the controller receives a trip request, not only it sends a driver to pick up the user, but also send, with a specified probability, say 50%, a CruiseTAZ ScheduleItem to a driver, randomly selected amongst the available.
• Prediction based rebalancing: a prediction mechanism provides the zones in which many requests are expected to come and the controller sends proactively CruiseTAZ messages to some drivers to move them in those zones.

Each OnCall controller owns a Rebalancer, which abstracts the rebalancing logic. Each different rebalancing policy is implemented in a separate class, which extends Rebalancer and implements the function rebalance(). The rebalancer is triggered every time a schedule is computed. Every time a new request is received, the OnCall controller notifies the rebalancer by calling the function onRequestReceived(..), in which the developer can write the operations to collect the historical request data that can be later used for the rebalance logic.

The Rebalancer is called at specified intervals, given by the parameter rebalancingInterval declared in OnCallController.hpp. Once the current frame reaches or exceeds this, the rebalancing is performed and the update is given by nextRebalancingFrame. The default value of rebalancingInterval is 720 frames (corresponding to 1 hour).

KasiaRebalancer function

The function KasiaRebalancer performs the dynamic rebalancing algorithm as described in Chapter 5 of Katarzyna (Kasia) Marczuk's thesis [Marczuk]. NOTE: It is yet to be fully tested!

The availableDrivers provides the supply of vehicles to use for rebalancing. The getNumVehicles() function obtains the vehicle IDs from each of the available drivers by zone. The latestStartNodes vector stores the nodes of all requests received in the prior interval. From these, we obtain the stations, which are considered as zones. The getNumCustomers() function obtains the demand by zone. Currently, we use the demand from the prior interval as a proxy for the demand in the current interval, in order to initialize the rebalancing procedure.

If there are available drivers, the solver proceeds. The objective of the linear program is to minimize the total cost of moving one vehicle from one zone to another. We obtain the zone-based OD travel time using the getArrivalBasedTT() function. This serves as the cost. The decision variable is the number of vehicles to send from the zones in which drivers are currently available to zones in which there is excess demand (based on prior interval).

Driver movement

Types of stop locations

• In MT the pick-up and drop-off happen at nodes. The vehicle doesn't actually 'stop' at these points. Additionally, parking locations are currently defined at nodes. As a result, the vehicle can safely exit the simulation temporarily at the node. As none of the scenarios requires a special implementation of a 'Stop location', a special class does not exit in MT.
• In ST, the vehicles cannot be allowed to pick-up or drop-off passengers at nodes as these are intersections. Hence, we perform these tasks on the last segment in the path to the pick-up/drop-off node. The structure StopPoint defined in DriverUpdateParams.hpp is used for this purpose. The following parameters (AA: parameters of what? of the StopPoint struct?) are set in the functions beginDriveToPickUpPoint() and beginDriveToDropOffPoint() in the file OnCallDriverFacets.cpp:
  distance = This is the distance to the stop point (AA: distance from where?) on the road segment. (Currently set as 2/3 of the length of last segment)
  dwellTime = Time for which the vehicle waits at the stop point. (Currently fixed at 5 seconds for each stop point)
  segmentId = Id of the segment at which the stop point is inserted.
  Currently, as the parking locations are defined as nodes, a vehicle being parked at the node simply vanishes on reaching the parking node (Work in progress)

AA: Does the structure of the ScheduleItem changes? I ask this since, as for the documentation in this page, the ScheduleItem indicates a node.

AA: Can we write here all the types of stops we will need, separating the ones needed in MidTerm and the ones for ShortTerm? Do we need nodes, segments, bus stops, high density building, taxi stands, parking, etc?

Dwell time

The dwell time for every stop point is current fixed at 5 seconds. The corresponding code is implemented before in the functions beginDriveToPickUpPoint() and beginDriveToDropOffPoint() in the file OnCallDriverFacets.cpp. Enhancement: Dwell times can be computed based on the sum of boarding/alighting times of the individual passengers at the stop locations (Refer to dwell time computation for bus drivers done in BusDriverMovement::frame_tick() in the file BusDriverFacets.cpp)

How-To

Installation

Pull the mid-ftr-taxi-controller branch, compile, and run (if you are in Boston). To compile in debug mode:

mkdir Debug
cd Debug
cmake .. -DCMAKE_BUILD_TYPE=Debug -DBUILD_MEDIUM:BOOL=ON

Use of Mobility Service Controller

To check which database you are using, retrieve the database symbolic name from <network_database> tag in simrun_MidTerm.xml. Then, check what is the actual name of the database, by checking that symbolic name in simulation.xml.

In simulation.xml, there is a tag called mobilityServiceController that is enabled if the enabled tag is set to true. This activates the mobility services. To activate a controller, you can add a new controller tag with a unique identifier and fill out the fields corresponding to the controller you want to instantiate. To deactivate a controller, you can remove the tag corresponding to the controller from simulation.xml.

Within this tag, there are tags called controller. These tags correspond to the controllers that are in use in the simulation. Each tag contains 4 fields: id, type, scheduleComputationPeriod, and vehicleIds (which is currently not in use). id corresponds to the ID of the controller (this is a unique identifier per controller). type corresponds to the type of controller that the tag corresponds to. The code for each type is written in entities/controllers/MobilityServiceController.hpp, in the enum MobilityServiceControllerType.

To check to which controller the drivers are subscribing, check the name of the SQL procedure associated to taxi_fleet in simrun_MidTerm.xml (AA: bad naming, as it refers not only to taxi, but also to SMS). With a database system, e.g., pgAdmin or psql, open the declaration of that procedure (it should be under the public schema) and check the name of the SQL table from which these drivers are loaded. In these table, some of the vehicles subscribe to the OnHail service, some others to some OnCall controllers. In particular, the column subscribed_controllers tells the controller type at which each driver is subscribed (AA: This is bad. Indeed, now a driver subscribes to a controller type and not a controller id. Now, let us suppose we are running two different controllers that are identical, but have two different ids. With the current representation, this is impossible to represent). You can cross-check the column value with the code of the controller type written in entities/controllers/MobilityServiceController.hpp, in the enum MobilityServiceControllerType. If you want to use a different controller in your simulation without changing the table (which can be useful in case the same table is used by different experimenters at the same time), you can change the hard coded values of entities/controllers/MobilityServiceController.hpp, in the enum MobilityServiceControllerType to reflect the SQL table values.

The controller logic depends on some parameters. scheduleComputationPeriod, written in the mobilityServiceController> tag of simulation.xml decides the interval after which the control algorithm runs. maxWaitingTime decides the maximum time we want users to wait before getting into a vehicle, toleratedExtraTime is the upper bound to the additional time we impose to a user with respect to the situation in which a vehicle exclusively serves her, maxAggregatedRequests is the number of passengers that can be simultaneously in a vehicle. These three values are hardcoded in entities/controllers/MobilityServiceController.cpp.

There are different types of rebalancer. In shared/entities/controllers/Rebalancer.hpp you can see the various rebalancer classes that extend the parent Rebalancer class. Currently, we have LazyRebalancer, SimpleRebalancer and KasiaRebalancer. To select or change the rebalancer in use, modify the parameter rebalancerType in the simulation.xml file as follows:

• 1 : selects the LazyRebalancer (does nothing; essentially no rebalancing)
• 2 : selects the SimpleRebalancer (sends a vehicle to cruise at each node a request is made)
• 3 : selects the KasiaRebalancer (solves an LP to minimize travel time for zone-based redispatching)

Further, to select the interval at which the rebalancing is performed during the simulation, modify the rebalancingInterval parameter that follows in the controller field. The number represents the number of frames in the simulation. For instance, if the base granularity is set to 5 seconds, then a rebalancingInterval of 720 frames will correspond to 1 hr, which means that the selected rebalancing routine will be executed every hour.

You can disable the output, disable all the lines in shared/logging/ControllerLog.hpp, function ControllerLog::operator<<(..), keeping just the return statement. Check if the output is actually produced or not.

Remember that any modification of C++ code requires recompilation.

Use cases (temporary)

AA: not sure this is updated.

To run the base case (without mobility services), in data/simrun_MidTerm.xml change the mapping of day_activity_schedule to get_persons_between_base_case. To run the case with mobility services, in data/simurun_MidTerm.xml change the mapping of day_activity_schedule to get_persons_between_no_subsidy

Creating a new controller

When creating a new controller, you must do the following things:

1. The new controller must extend MobilityServiceController (or one of its children)
2. The new controller should be in shared and should work with both MT and ST
3. The new controller should only override methods that it needs
4. The new controller must have a specific type, which is specified in addMobilityServiceController in MobilityServiceManager.cpp (e.g., the greedy controller is type 1, the shared controller is type 2).

TODO:

• Not urgent
  • Model the time spent for boarding and alighting of passengers
  • Think about a cookbook of functionalities decoupled from the classes. Have a look at Builder or Decorator or other design patterns.
• Need 4 and 10 people sharing capability [Urgent - @AA?]
• Rebalancing. Currently only lazy re-balancing mechanism is tested with the old branch. The latest development branch should be tested with the lazy re-balancer and need to implement a proper re-balancer [@Jimi]
• Shift duration stored procedure must take care to initialize the drivers whose shifts are active during the simulation time [Urgent - Kakali]
• Delayed message delivery for driver shift is implemented through Conflux in Mid-term and the similar process need to implement in ST [@aditi]
• Update the driver state diagram [@neeraj]
• Pickup/Drop-off at the bus stop
• Vehicle capacity (for supply and for controller)

For L2NIC 3B project some of the above functionalities are required for urgent basis. Please check the timeline

Input-Output

Input for Controller Type

Please refer here for complete input configuration.

Output

At the end of the simulation we will find a controller.log which contains detailed text depicting the workings of the mobility services in the simulation. However, after running controller_create_csv.py, a file named mobilityService.csv will be created, with a row for each trip request with the following columns:

• request id
• user id
• service id
• request creation time
• origin location center
• origin location radius: the Users who issued this request was accepting to be picked up in a circle centered in the origin location center and with radius specified in this column. If the user wants to be picked up exactly at the location center, the radius will be 0.
• destination location center
• destination location radius
• earliest requested pick up time
• latest requested pick up time: the user was accepting to be picked up in the interval between the earliest and the latest pick up time
• earliest requested drop off time
• latest requested drop off time
• actual start location
• actual destination location
• request processed timestamp: the first time that the controller reads this request from its request queue
• actual pick up time
• actual drop off time
• driver id: the driver that actually picked up the user

Checking how requests are handled

• Look for "Request sent" in controller.log
• Look for "Person <person_id> has trip <trip_id> with the same origin and destination. This trip is not loaded." in warn.log
• Look for "Computing schedule: <num_req> requests are in the queue, available drivers " in controller.log
• Look for "Computation schedule done: now <num_req> requests are in the queue, available drivers "

Output analysis

• On Linux, use the script dev/tools/mobility-service-test/complete_analysis.bash following the instructions written there

References

[Ratti] Santi, P., Resta, G., Szell, M., Sobolevsky, S., Strogatz, S. H., & Ratti, C. (2014). Quantifying the benefits of vehicle pooling with shareability networks. Proceedings of the National Academy of Sciences, 111(37), 13290–4. https://doi.org/10.1073/pnas.1403657111

[Frazzoli] Alonso-mora, J., Samaranayake, S., Wallar, A., Frazzoli, E., & Rus, D. (2017). On-demand high-capacity ride-sharing via dynamic trip-vehicle assignment - Supplemental Material. Proceedings of the National Academy of Sciences of the United States of America, 114(3).

[Marczuk] Marczuk, K., (2017). Modeling and Analysis of an Autonomous Mobility on Demand System. Department of Civil and Environmental Engineering, National University of Singapore.

Taxi Driver Subscription Implementation

The driver subscriptions are added to the taxi_fleet table in the form a new column. The data type of this column is bigint. Each bit in the value corresponds to a controller. The association for the bits are as follows: Greedy: 0b0001 Shared: 0b0010 OnHail: 0b0100 So, a driver subscribed to the greedy controller will have value = 1, but the one subscribed to both, greedy and shared, will have value = 3

Incremental

Schedule may be a list instead of a vector.Tolerated extra time is defined in the request and in the MobilityService as well. This redundancy is dangerous. Bad use of .begin()

For every possible insertion, evaluateSchedule is called and re-evaluate many of the things that have already been evaluated. For example, if a certain pickup time was ok (because it was respecting the maxWaitTime), everytime we do another insertion of another requests, due to the fact that we call evaluateSchedule from the beginning, we always check if that pickup is ok.

Things we may want to consider to improve efficiency

Given that most of the time we use Node* instead of nodeId, we should direcyl write Node* in the request instead of nodeId, as searchin the nodeVsIdMap is expensive. To insert elements in a list at a certain position, I use something like

scheduleHypothesis.insert(scheduleHypothesis.begin()+pickupIdx, newPickup);

I guess it is inefficient to always start from begin() and then adding an offset. I guess there are other more efficient ways (like std::advance). But, pay attention: as you will see in the logic of the algorithm, we need to move at the same time across different schedules (for example schedule and scheduleHypothesis) and we want to make the same moves (for example move at location i in both vectors). With the indices I am using is relatively easy. With other techniques, it may be possible as well, but I did not even try.

Testing

For extracting Requests vs Available drivers:
grep "Computing schedule:" controller.log > ReqVsAvlDrivers.log

For extracting Pick-up information:
grep "Pickup succeeded" controller.log > Pickups.log

For extracting Drop-off information:
grep "Drop-off of user" controller.log > Dropoffs.log

For extracting Parked vehicle information:
grep "Parked at node" controller.log > Parked.log