Success Story: Timetable Optimization in Public Transport

NCC presenting the success story

The Turkish NCC is led by TUBITAK-TRUBA, one of the two main HPC centers in the country. Besides TRUBA, three partners, Middle East Technical University (METU), Sabanci University (SU), and National Center for High-Performance Computing (UHeM) of Istanbul Technical University (ITU), act as third- party. METU, proudly presenting this achievement, is a public university based in Ankara and SU is a private one located in Istanbul. ITU UHeM, also based in Istanbul, provides supercomputing and data storage services for academic and industrial users. Our skills span High-Performance Computing, High-Performance Data Analytics, Artificial Intelligence, CUDA, Materials Science, Computational Fluid Dynamics, and several other areas. This achievement is presented by the third-party METU.

Technical/scientific Challenge:

Utilizing the TRUBA environment enabled Parabol to have a faster R&D cycle and continue their first case study related to origin-destination analysis. They have used those results to get optimal timetables for each route governed by different terminals. However, optimizing PT services and exploring passenger mobility requires handling large amounts of data, solving complex combinatorial optimization problems, and dealing with uncertainty. Solving this NP-hard problem requires a significant amount of time, and even impossible to get a solution in a reasonable time as the problem space gets larger.

Business impact:

The Dask-based solution developed in this case study can provide optimized timetables for bus routes to increase fuel savings and passenger satisfaction, as well as improve timetable governance. Using the TRUBA HPC environment allows us to achieve this goal with significantly improved performance.

In addition to this high-tech solution allowing us to work with large-scale PT networks, the parallelization framework we had here can be inspired and easily applied to other complex optimization problems in the PT domain. All these create a very fast, highly accurate, less expensive, and more efficient decision support mechanism, which gives a competitive advantage in the market.

Industrial organisations Involved:

This success story results from the second case study jointly led by METU and TRUBA in cooperation with an SME, Parabol, in METU’s Technopark. Parabol (paraboly.com) has been conducting R&D activities in Intelligent Transportation Systems since 2011. They have been developing a public transportation (PT) analysis platform (cermoni.app) to analyze public transport (PT) demand in a city and to make more efficient PT investment decisions. By merging the company’s main areas of expertise (big data analysis, smart mobility algorithms, mobility management, cloud computing) with R&D activities, they have been able to provide mobility management and analysis software tools in several countries and more than 50 cities in three continents willing to improve various modes of transportation such as PT mobility.

Solution:

The initial heuristic algorithm, dealing with all routes iteratively to get a feasible solution in the company’s production environment, was first extended to achieve the global optimum solution. After redefining the algorithm, a Dask cluster was set up on TRUBA to parallelize the optimization algorithm so that each instance solves the timetables of the bus routes originating from a separate regional terminal. Hence, the Dask cluster size in this data-parallelization approach will be proportional to the number of regional terminals involved, which is generally also proportional to the number of bus routes. We chose Dask to parallelize our algorithm as it requires no code modification in the original algorithm, providing a very time-efficient solution.

When we ran the optimization algorithm on TRUBA with the actual PT data, we achieved an optimal solution in minutes to a couple of hours, depending on the problem size. We also observed that a near-optimal solution could be reached much earlier.

Benefits:

• Saving time in the R&D process.
• Achieving optimized timetables of bus lines within a reasonable time.
• Having a parallel execution framework for complex optimization algorithms.