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.
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.
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.
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.
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.
Keywords
- Keywords: Dask library, Big Data, HPDA, Optimization, Smart City.
- Industry Sector: Smart City, Intelligent Transportation Systems, Bus Route Timetable Optimization, Public Transportation.
- Technology: Big Data, HPC, HPDA.