by Tim Nonner, Adi Botea, Marco Laumanns
As part of an IBM First-Of-A-Kind project, the IBM research labs in Dublin and Zurich joined forces to investigate planning approaches for unreliable and highly stochastic public transportation systems (PTS).
When commuting via public transport, a common problem is finding the right direction. Typically getting to the correct destination requires several bus or train changes. Many public transport providers, as well as independent companies, offer online planning tools to simplify this task. The use of these tools usually involves the user entering the origin and destination locations for a given journey along with nominating several preferences (e.g., maximum number of interchanges). The results then provide the user with a sequence of directions, nominating the different buses and trains that must be taken. Ideally, multiple options are suggested, each with its own advantages and disadvantages. For example, Option 1 might present a route with a short travel time, but requiring multiple changes, Option 2 a slow but direct route, and Option 3 may be the cheapest option but it includes an extended wait time at an intermediate stop. For any given option, missing one step in the sequence can result in the route requiring re-planning to address the different conditions now faced by the user.
A traveller who is familiar with a PTS might blend aspects from the variety of solutions presented to develop their own unique solution. This offers the user the advantage of being able to adjust their journey dynamically in response to their own shifting needs. For example, if the user misses a connecting bus, he/she may be aware of an alternative bus which also suits their current needs. This dynamism is especially necessary if the PTS is unreliable and features “rule of thumb” scheduling or only publishes vehicle frequencies as opposed to actual times (e.g., three buses per hour vs. three buses at 11:20am, 11:40am and 12:00pm).
Challenge and Policy-based Planning
Turning this intuitive planning approach based on personal experiences into a stochastic planning tool presents an ongoing challenge which the authors have addressed using a number of different approaches. Instead of providing a simple sequence of options to follow, these approaches all suggest a tree of options, called a policy. The policy outlined above (Figure 1) includes four stops A, B, C and D: at each stop the traveller can pick one of the provided alternatives. For example, at Stop A the user can select Bus 1 or Metro 1. Choices can be made according to a first-come-first-serve rule which is easy to execute (even in an offline mode) or to a more detailed timing regime which might be supported by a smartphone application. We have developed several algorithms to compute such policies.
Drawing on the heuristic search used in the Artificial Intelligence area, the first algorithm uses a forward planning perspective (i.e., the user is at the beginning of their journey) [1] [2] and attempts to factor in all the possible events and options to find a policy that is flexible within each situation. The second algorithm, inspired by the classical shortest path algorithms, takes a backward planning perspective using dynamic programming techniques [3]. Thus, this algorithm iteratively builds stochastic plans starting from the destination. Both the algorithms we developed are fast enough to allow for real-time application.
There is, of course, the need to build an abstraction of reality in both algorithms. For example, the stochastic behaviour of buses must be simplified to make their movements computationally tractable. Therefore, to make a final check and comparison of the algorithms proposed solutions, we used a more detailed simulation that aims to more closely approximating the real world. For example, tests undertaken on public transport timetable data showed that waiting times can be significantly decreased in many cases by providing more alternatives at each stop: in fact our results showed a 25% decrease in waiting time in 20% of the scenarios considered. Therefore, mainstreaming such policy-based planning approaches in every-day life would significantly improve the user experience of many PTS.
Link:
http://resweb.watson.ibm.com/researcher/view_group_subpage.php?id=4130
References:
[1] A. Botea, E. Nikolova, M. Berlingerio: “Multi-modal jour-
ney planning in the presence of uncertainty”, in proc. of ICAPS'13,
AAAI, 2013.
[2] B. Chen, et al.: “Uncertainty in urban mobility: Predicting waiting times for shared bicycles and parking lots” in proc. of ITSC'13, IEEE, 2013.
[3] T. Nonner: “Polynomial-time approximation schemes for shortest path with alternatives” in proc. of ESA’12, Springer, 2012.
Please contact:
Tim Nonner, Marco Laumanns
IBM Research - Zurich, Switzerland
E-mail:
Adi Botea
IBM Research - Dublin, Ireland
E-mail:
