Using Goal Directed Techniques for Journey Planning with Multi-criteria Range Queries in Public Transit
| Autor: | Jean-Charles Régin, Arthur Finkelstein |
|---|---|
| Přispěvatelé: | Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA), ANR-19-P3IA-0002,3IA@cote d'azur,3IA Côte d'Azur(2019) |
| Rok vydání: | 2021 |
| Předmět: |
Range query (data structures)
Operations research Computer science business.industry [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS] Pareto principle Response time [INFO.INFO-RO]Computer Science [cs]/Operations Research [cs.RO] Shortest Path Pareto Optimization Order (business) Factor (programming language) Public transport 11. Sustainability Graph (abstract data type) Public Transit Routing Duration (project management) business Preprocessing computer computer.programming_language |
| Zdroj: | ICORES SCITEPRESS Digital Library SCITEPRESS Digital Library, In press |
| DOI: | 10.5220/0010235300002859 |
| Popis: | International audience; One of the main problems for a realistic journey planning in public transit is the need to give the user multiple qualitative choices. Usually, public transit journeys involve 4 main criteria: the departure time, the arrival time, the number of transfers and the walking distance. The problem of computing Pareto sets with these criteria is called the Pareto range query problem. This problem is complex and difficult to solve within the constraints of the industrial world of smartphone applications, like a response time of the order of a second. In this paper, we present the Goal Directed Connection Scan Algorithm (GDCSA), an algorithm that allows, for the first time, to solve this problem with run times of less than 0.5 seconds on most European city or country-wide networks, like Berlin or Switzerland. In addition, GDCSA satisfies other industrial needs: it is conceptually simple and easy to implement. It partitions the graph in geographically small areas and precomputes some lower bounds on the duration of a trip in order to select for each itinerary a subset of these areas to decrease the number of scanned connections. Combining this subset and a journey planning using 4 criteria, we scan up to 17 times fewer connections than the best algorithms (CSA and RAPTOR), the number of nodes opened during the search is lowered by a factor of up to 2.9 and the query times are lowered by a factor of up to 9 on metropolitan networks. The integration of GDCSA in a smartphone app backend server led to an improvement in results by a factor of 5. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|