There’s been quite some buzz lately around automated transport solutions and driverless buses. Personalized, dynamic time tables would be one piece in the puzzle to improve public bus transportation. Find out about a prototype system for this – and how you can get involved.
Last week in Kista, the Mobility Week put Intelligent Transport in the limelight. Driverless buses running on electric power picked up passengers travelling to and from the Kista Galleria shopping mall. This demonstrated how ICT can transform the efficiency, responsiveness and sustainability of transport systems in cities around the world.
Earlier, we’ve also talked about what it would be like if you didn’t need to wait for the bus but instead the bus would wait for you. Now let’s look into what kind of machinery it takes to make this happen.
And note: The source code for this work is available on github, so you experiment with it yourself!
First just a quick recap of what we’re trying to achieve:
- Can bus schedules consider individual needs of passengers?
- Can bus capacity and expected passenger load be matched better?
- Can routes be dynamic, so they don’t pass by empty bus stops?
What’s needed is a more direct link between the bus operator and its users, similar to how services like Uber work. How do we create this link, and – most importantly – what can we do once we have it?
Figure 1 – Platform overview
The overall platform is illustrated in Figure 1. For the purposes of simplicity, we will focus on Client Application, Vehicle Application, Look Ahead and Travel Recommendation modules in this post.
The Client App contains the usual set of features one would expect such as personalized trip recommendations, bus search function and notifications. As we will explain later on, the busses now don’t have a “regular” schedule therefore you need to be notified when the buses are actually there to pick you up. With the user’s permission, the Client App would start recording the user’s requests in order to produce personalized recommendations and improve timetables, optimize routes and overall reduce the passenger’s waiting time. Last but not least it offers the option for providing feedback such as rating a trip, but also allowing the user to directly protest if a recommended trip is taking longer than what has been originally predicted.
The Vehicle App is about creating a link between the “virtual control center” – remember our original goal is to minimize and even eliminate the need for such a control center – and the bus driver. Via this link the bus driver can receive input such as: information about routes, the maps to follow, and the number of passengers expected to board and leave at each stop. Additionally, the Vehicle Application collects information from the bus drivers, such as alerts about accidents which have affected the routes.
The travel recommendations module is what feeds the client app with useful personalized recommendations. As such it is based on the idea that humans are creatures of habit and they tend to use public transportation at least for commuting between their home and their work. The usual suspect for dealing with such tasks is K-Means and in our case we used Apache Spark MLib in order to utilize this algorithm in our platform.
The Look Ahead module aims at figuring out what the next day’s timetable should look like based on previous requests but also taking into consideration special cases such as holidays or special events (football matches/concerts etc.). The Look Ahead module employs a genetic algorithm approach in order to generate the timetable. There are two reasons why we’ve chosen this approach: a genetic algorithm allows for experimenting with different parameters we would like to take into consideration while trying to generate the solution. Moreover, it allows for approximating a good (or good enough solution) instead of going all out and using a lot of processing cycles in order to find an ideal solution that may not exist.
More specifically the main goal of the genetic algorithm is to minimize the passengers waiting time and number of trips the bus operator allocated for a particular line per day. As such, the scheduling of buses was approached as an optimization problem. For each individual solution we’ve taken into consideration the bus line, the capacity of the bus, the frequency of the trip and the starting time of the trip. Tournament selection was used as a selection operation. One-point crossover and mutation were used as genetic operators – made it possible to avoid getting stuck in a local minimum or global minimum for too long while generating different solutions (also known as “individuals” in the genetic algorithm terminology).
As we said, the source code is available on github so feel free to fork and start experimenting with different approaches for generating new solutions especially for the LookAhead module.
The work presented in this blog post was done last year together with a group of students from Uppsala University, in the context of Project CS 2015/2016. For a more detailed analysis go ahead and grab a copy of the project report!
So what’s next? One of our current limitations is that we assume static routes for our buses even though we are generating dynamic timetables. It will be interesting to investigate the same process when dealing with dynamic routes, either influenced by the timetable or by unforeseeable events, hopefully reducing any oscillation that may occur during the decision process that renders this loop undecidable. This work will be done together with our partners in EU Citypulse utilizing the Decision support component, and Geospatial Database for Smart Cities.
So stay tuned!