Serving more passengers with less taxis

Jesper Provoost is a visiting researcher at ITRL from the University of Twente, The Netherlands. In this interview Jesper shares insights in to the project PREDICT  and his most recent paper:

“DemandProp: a scalable algorithm for real-time predictive positioning of fleets in dynamic ridesharing systems”

In order to make ITRL’s research more accessible to both the industry and the public, we asked a range of questions that give an overview of Jesper’s paper and inspire you to learn more.

What is the article about?

A common problem in ridesharing and taxi systems is that the drivers are making the decisions of dispatching and repositioning in an individual manner, which means that they can decide themselves and don’t have the information or the system wide benefits in mind when they make these decisions.

With predictive repositioning, we can utilize proactive knowledge and optimize for the system wide benefits instead of the individual, “greedy” benefits of the drivers. What we did in this research is that we created an algorithm to do this predictive repositioning. We do this based on machine learning models which can predict the demand in the taxi network. Based on that we can reposition or distribute the vehicles when they are idle. We proved the effectiveness and benefits of our algorithm by running simulations of the real world road network of Manhattan with thousands of vehicles.

What were the results?

We compared our method, called DemandProp, to five different baseline methods with different levels of complexity. The baseline methods in this case are different repositioning strategies. For example, we consider an egotistical strategy, where drivers just go to the area with the highest demand within a certain distance. In that case many drivers just end up at the same spot, leading to an oversupply in concentrated areas but a shortage of vehicles in other areas.

A better alternative would be to adopt an altruistic method, which is performing a system-wide optimization. We wanted to show that our system is able to do a better job than such methods. In the end we observed that our method gave 69% less delays than the egotistical strategy and 31% less delays than the most intelligent baseline method. With regard to resource efficiency, we also demonstrated that it yields 45 minutes less idle time for vehicles per day on average. The reject rate, the percentage of rides that has to be rejected because there are no available vehicles, is far less for our method. Almost 1,5% to 2% of all requested rides were rejected with the egoistical method, but only 0,5% were rejected with DemandProp.

How do you see this being used in the “real world”?

So far we only use DemandProp as an algorithm which provides us with system-wide repositioning strategies. In practice, DemandProp can be implemented as a kind of a navigation for drivers, for instance in a system like Uber or Lyft where drivers can follow the repositioning path that our system suggests them. This could resemble Google Maps, where instead of showing the way from A to B we show a path that our system has selected for that particular driver. If you coordinate this centrally with the algorithm that we have implemented, it will provide large benefits for both the driver and the service operator.

The system is also very suitable for autonomous vehicles. When they are idle and don’t carry passengers, they can reposition themselves according to the decision made by the algorithm. Obviously with autonomous vehicles it is easier to let the vehicles follow the exact repositioning path, and hence it will be easier to fully utilize the fine granularity with which the DemandProp algorithm can predict and compute repositioning paths.

What is the next step for this research?

We want to incorporate electric vehicles into this research and take the constraints of electric vehicles (i.e. batteries) into the mix. When we calculate these repositioning paths, you have to account for the battery charge because you cannot anticipate to pick up passengers when the battery is almost empty. We will therefore incorporate charging stops as an integral part of the repositioning routes.

What is the take home message?

Predictive and proactive repositioning strategies like the one we propose provide a lot of benefits in terms of transport and research efficiency compared to more conventional and egotistical methods. It can result in large benefits for customers but also operators. When using our algorithm we can cut down on delays while increasing passenger comfort. Also, resource costs can be lowered because less vehicles will be needed. For example, in a New York scenario we would need approximately 1000 less vehicles (which is approximately 20% of the entire fleet) and still have the same performance as with other strategies. If the operator can reduce the fleet, it will be better for traffic congestion and it’s more sustainable - you essentially drive less kilometres and serve more customers. In the future I think this will be a very good step towards reaching crucial sustainability goals. There is obviously a big shift towards electric mobility so we are working hard to ensure that our algorithms are also ready to optimize for these scenarios.

You can read Jesper's preliminary paper here (pdf 6.2 MB) , or feel free to contact Jesper  for any questions or comments.