The puzzle of dispatch, part 2 : Ride-pooling

Yuso
Yuso
Sep 5, 2018 · 11 min read

After analyzing in a first article the best way to dispatch in advance bookings, we are now going to study the case of ride pooling between several passengers. As a matter of a fact, ride sharing is becoming an increasingly important issue in transport and logistics industries.

From a fleets’ point of view, ride sharing allows to optimize resources and to make their business more profitable. Creating an optimized route and simultaneously transporting several packages or several passengers in the same vehicle (like it’s done for example by Via, or UberPOOL) enables to minimize the time spent empty and the driver’s working time, in a sector that is highly sensitive to operating margins.

From clients’ point of view, the use of a shared transport service between several passengers (or between several packages in the case of delivery) makes it possible to obtain more attractive prices, in exchange for a slightly downgraded experience (longer waiting time, detours during the ride, etc). For instance, the fares proposed by UberPOOL are 25% to 30% cheaper than the price for an identical ride using UberX.

Finally, from cities’ point of view, ride sharing helps relieving traffic congestion, and reshape current individual means of transport (taxis or personal cars) as a new form of shared transport. As mentioned in our previous article, an MIT study based on New York taxis reservation data shows that is it possible to share up to 97% of the requests of rides, without significantly impacting the passengers’ rides ( the time added to the journey remains less than 3 minutes).

The taxi is getting closer and closer to become a bus. For example, in medium-sized or rural towns, there is an increasing demand for school based transport or the transport of PRMs (People with Reduced Mobility). Another example would be path pooling, it could be used to transform public transport into a smart and digitized model, which would be not based on rigid lines at fixed timing but rather on dynamic routes, that adapt according to demand.

If we now consider the subject of sharing a journey from the point of view of dispatch, it raises three major issues, between which we must find a balance : a technological issue, an operational issue, and finally an issue in terms of user experience.


Pooling rides from a technological point of view

“This is the story of a travelling salesman”

The technological challenge associated with pooling is actually close to a well-known problem in computer science and optimization, known as the “travelling salesman problem” (TSP).

This problem has a very simple statement: a travelling salesman must go successfully to several cities while minimizing the total distance he travels. The distance between each of the cities is known, so it is necessary to determine in what order the salesman should visit the cities.

If the problem statement seems easy, it is actually more complex to solve, because it requires to test all the possible combinations: if the traveler has to go to 10 cities, it is 10! different paths to calculate, i.e. 3,628,800 combinations. If he has to go to 20 cities, then you would have to calculate 20! possible paths, which represents more than 2 billion billion solutions! Even with a million calculations per second, it would take more than 77,000 years to test everything.

The issue here is not so much to solve the problem, which remains algorithmically relatively simple, but to solve it in a very limited time. In fact, a fleet operator should be able to provide in only a few seconds an answer to a customer, who would like to for example to book a ride that starts immediately.


The case of an immediate departure

When a ride with an immediate departure must be pooled with other rides already planned, we must take into consideration as vehicles able to pick up a client all the vehicles circulating, even if another passenger is already on board. In this case, the objective is not to minimize approach time, but to find the most optimal route. For example, a vehicle could realize an intermediate stop before picking up the new passenger.

In terms of calculations, we are here faced with problems very similar to those of advance reservation, with a large number of possibilities in the choice of the vehicle. The only possible filter at the vehicle level is based on the time windows for the pick-up or the drop-off of the passenger, which will limit the possibilities of sequencing the rides.


The case of an advance booking

When it comes to advance booking, the problem is even more complex to solve: the response speed to customer is not as important in this case, but the number of calculations is very important to establish the schedules of the drivers, because it is essential to calculate all intermediary travel times between stops. The diagram below allows to better visualize the arrangement of different rides.

Let’s try to determine the number of calculations needed with this new configuration. Consider, for example, a case where there are 10 available vehicles, and they receive 100 requests for bookings, to be divided among these 10 vehicles. We will try to calculate the number of intermediate travel times. For this, we must consider :

  • 200 intermediate stops (one point to pick up and one point to drop off each of the 100 journeys)
  • 10 starting points of vehicles (1 stop per vehicle)
  • 10 points of arrivals of vehicles (1 stop per vehicle)

That is in total 220 points, from which it is necessary to calculate the routes to the other 219 points. Therefore, there are 220 * 219 = 48 180 travel times to calculate.

If x is the number of vehicles and y is the number of journeys, the number of intermediate travel durations N is obtained with the following formula :

N = (2x + 2y) *(2x +2y-1)

In this case, the number of computations is quadratic to the entry n. In computer science, it’s called a complexity in O(n²). Calculating travel times in a limited time remains possible.

However, our work does not stop there: once these journey times are calculated, it is still necessary to determine which is is the best schedule arrangement. And this is where the problem shows up, because the number of possibilities of planning is factorial to n. It’s called in this case a complexity in O(n!). If we take again the example aforementioned, then we would have (200+10+10)! = 220! possible arrangements, which is more than the number of atoms in the universe! It is therefore impossible to calculate in this way the most optimal schedule, whereas 100 requests divided over 10 vehicles actually corresponds to a low volume of passengers.


Using a local map

In order to calculate these intermediate travel times, most dispatch solutions are based on data provided by Google via its Google Maps API. However, the number of requests per second is limited, and the service becomes paying beyond a certain number of requests. This issue limits the number of possible calculations and can ultimately cost a lot, especially since Google has just sharply increased its prices.

To not be dependent on a third-party service and to be able to make an unlimited number of requests, it may be wise to develop one’s own mapping solution. In this scenario, it must be possible to guarantee a very short response time, especially in the case of a reservation with an immediate departure. This is the choice we have made at Yuso. We have developed our own local map that allows intensive calculations, or in other words, compute a very large number of travel times in a few seconds.

An example of a local map is available down below. In this map, the roads are all prioritized according to the volume of vehicles passing through. Thus, the structuring axes are in red, the second level axes are in orange, etc. In this map of Paris, provided by OpenStreetMap, the ring road is in red because it is an axis that allows you to go around Paris very quickly.

As mentioned in the article “Engineering highway hierarchies”, in order to travel as quickly as possible, the objective is to reach a major axis as soon as possible, and then go down the hierarchy of axes when approaching the arrival point. Through this way of building a route, which is actually quite intuitive for a driver, can drastically reduce the number of calculations necessary to establish the number of travel durations.

From a mathematical point of view, this map is actually a graph that models Paris, through edges (streets) and nodes (street corners). A travel time is assigned to each edge, similarly to the travelling salesman problem. This simplifies the mapping of a city and thus simplifies the calculations of travel times.

The use of this kind of graph with hierarchy of axes makes it possible to reduce the computation time up to 75% compared to a graph without hierarchy, and to also improve the precision of the results, because its mesh is denser. The only drawback of this solution is that it requires to create a similar build for every city where a company wants to deploy a fleet, which can be a very time-consuming process depending on its scope and the number of axes to prioritize.

If then we plan on to optimize the schedules for drivers, we must test all possible combinations between the different travels, and in the case of shared rides, this issue increases substantially the number of calculations. To minimize the number of calculations, it is necessary to pre-filter the vehicles (vehicles located too far away, or ones who have already many passengers on board, etc).


Pooling rides in operational terms

As a matter of a fact, a transport service offering ride pooling between several passengers cannot work if we do not put some constraints (in terms of availability, authorized routes or zones), because then the probability of pooling rides can strongly decrease. For example, a journey in the off-hours from London to far southwest suburbs will be unlikely to be shared with a similar journey, while a trip to Paddington during rush hours in the morning will be more likely to be shared with similar requests for a booking.

Here are some examples of constraints that can be used to maximize the probability of pooling multiple trips:

  • Define as points of pick-up or drop off some strategically located virtual stops, to which the passenger will have to go to (rather than being picked up or dropped off at the exact address he requested). This is what was put in place by Via in New York or Washington or by Bridj in Sydney for example.
  • Define hourly constraints regarding the availability of the service (for example, only available during the rush hour in the morning and evening, to serve commuters).
  • Authorize some areas or pick up corridors as “hot areas” that have a lot of demand ( this model is used by Chariot in San Francisco)
  • Make the client wait for a few minutes before offering a ride, to maximize the chances of finding a similar route in a way that the ride can be pooled.

On the other hand, if the scheduling or the operational constraints laid out are too restrictive (service is only available during a reduced time period, or in a limited geographical area), the service will not work either because the probability that a trip will meet exactly the criterias requested is very low.

The difficulty here is to find the right balance between the constraints; they must ensure profitability to the service and a minimum occupancy rate, but they do not have to frustrate the client and decrease the quality of their user experience when using the service.


Last, but not least: the user experience

The case of UberPOOL service is very interesting regarding this issue: Uber initially chose to offer door-to-door service, and picked up customers from the addresses they requested. This model, which seems to be the most satisfying for the customer, is actually not the most optimal. Picking up or dropping off other customers at specific addresses forces the vehicle to make detours in narrow streets (and in Paris, there are a lot of one way streets) which leads to wasting a lot of time. Following the claims of its users, Uber has decided to change their model and offer another one called “UberPOOL Express”, tested in the United States. It requires its customers to walk to meeting points ideally located on major roads to minimize the loss of time associated with picking up or dropping off customers.

Hence, this implies that the customer must walk for a few minutes to get to a point of pick-up, but the overall benefit is important : the other passengers save time individually on their journey, and the driver can be available for more rides and have a better hourly wage.

This is also the conclusion made by Via in New York, which requires its users to go to the points of pick-up that are located at street corners. They also must wait for a few minutes before getting a proposal of a journey, and confirm the reservation within 30 seconds, because the place is pre-booked in the vehicle.

Just as when a shared mobility service places operational constraints, the challenge here is to balance the effort required by the user and the overall quality of the service provided. It is the balance between the attractive prices and optimal operational constraints that increases the efficiency and comfort of the passenger. This will be the challenge for all the services of bus on demand, whether they are private or public, in the following years.

Yuso blog articles (in English)

Find here all our articles about urban transportation, mobility or dispatch

Yuso

Written by

Yuso

Yuso develops a global white-label platform dedicated to on-demand mobility services (taxi, private hire, delivery). Read more on www.yuso.tech

Yuso blog articles (in English)

Find here all our articles about urban transportation, mobility or dispatch

Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch
Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore
Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just $5/month. Upgrade