Evolução da componente algorítmica de cálculo de rotas do Move-Me

Abstract

Nowadays, public transportation have been affirming more and more its importance in the day-to-day life of the general population, whether to avoid traffic queues at rush hours, or to reduce costs at the end of the month. Therefore, there is a need for a rapid and effective response to public transport users. Is is in this context that the IMS project, developed by OPT S.A, was created. The purpose of this project is to assist choosing routes inside a multimodal public transportation network. The project is divided in several modules, responsible for carrying out specific functions. With the development of this master thesis it is expected to refine the algorithmic component of route calculation in the PADA module. The current algorithm presents query times in the order of seconds since the network has expanded to Lisbon. Thus, the main focus of this master thesis is to determine how the query times can be reduced, taking in account criteria that can be defined by users, such as the closest time of arrival, numbers of transfers and the maximum walking distance. If should be noted that the system is already in operation, so the current restrictions must be respected. This fact does not invalidate that the sophistication of the algorithm will be a minor challenge since in the last years large investments were done in the subject of algorithms on public transportation networks, which culminated in the invention of new algorithms such as RAPTOR and CSA, that are not based on graphs and can be easily parallelized, capable of running orders of magnitude faster than previous algorithm based on Dijkstra for the calculation of shortest path between two vertices of a graph. At the same time, new speed-up techniques such as A* with Landmarks, Arc Flags, Contraction and bidirectional search have been developed, however, all of them require a time-consuming pre-processing phase, followed by an extremely fast query phase. For this problem, the data that is provided corresponds to an estimate of the arrival time of a vehicle on a stop of the public transportation network. If possible, the actual times should be used. If they are not available, then the default static timetables will be used instead. By accessing other modules it is possible to build and characterize the public transportation network. The main module responsible for the network management, BITA, stores information about all the lines of all providers, the variants of a single line, the order of the stops of a single line and the arrival times of a vehicle in a stop, on a given day. These data is crucial in order to get the correct results during the route calculation. The sophistication of the PADA module will impact essentially the user experience as users will have access to the most convenient travel routes almost immediately. The chosen algorithm was RAPTOR because it can be easily parallelized, taking advantage of the high number of cores of the server where the algorithm will be executed in production. During the test phase, the performance of this algorithm was quite satisfactory. It was able to run, in average, 100 times faster than the current algorithm in production. The results with real time access were also quite satisfactory. Since the access to real time data in non peak hours is fast, the performance of the algorithm was not affected. To get around the problem of possible high response times for peak hours, a limit time was defined. If the function that accesses real time data does not return a value in the predefined limit time, then the planned times will be shown to the user.