Stefan's Site

Dynamic Vehicle Routing in Public Transportation

Planning public transportation is difficult. You have to decide where to locate stops and how to route vehicles to the stops to achieve good coverage while keeping capacity high, traveling time short and not breaking any laws of labor. Usually, the public transportation companies publish schedule updates a few times every year.

What if, given a set of stops, the timetables were planned dynamically based on actual demand? You (as a customer) would only need to order a trip between two stops and the system would tell you which vehicle to take and when to departure. You would also be told if you would have to change vehicle to reach your final destination.

The Finnish company Kutsuplus tried something like this in Helsinki. It was something like Uber for public transportation but started before Uber appeared. According to the Kutsuplus final report, this type of public transportation is a “competitive alternative to the private car and the leased car.” Also, it is not economically feasible for small scale operation since many vehicles run empty. Having many vehicles and many potential passengers increases the overall efficiency of the dynamic network. A first step might be to include Taxi into public transportation.

A couple of years ago I worked my way through the first edition of Approximate Dynamic Programming by Warren B. Powell. The dynamic vehicle routing problem is well suited to be attacked by ADP since we would want to use approximations to solve the curse of dimensionality. Dynamic Programming is able to solve optimization problems where future inputs are not entirely known. One example is the dice game Yahtzee where you have to assign your dice outcome to different positions in a protocol. How to assign your points depends on the current state of the protocol and the current result of the dice trying to navigate a finite tree structure which would end up in the highest score on average.

The public transportation problem is, of course, more complicated than Yahtzee with many more dimensions of information to take into consideration. But it is an interesting problem to think about.