Busca de melhor caminho entre múltiplas origens e múltiplos destinos em redes complexas que representam cidades
This work addresses pathfinding efficiency for urban planning and transportation systems, but it is incremental as it extends prior research from a single city to multiple cities.
The paper tackles the problem of finding optimal paths between multiple origins and destinations in complex urban networks, using a heuristic search strategy with Haversine distance to substantially reduce search time, though it introduces errors due to loss of admissibility in the heuristic.
Was investigated in this paper the use of a search strategy in the problem of finding the best path among multiple origins and multiple destinations. In this kind of problem, it must be decided within a lot of combinations which is the best origin and the best destination, and also the best path between these two regions. One remarkable difficulty to answer this sort of problem is to perform the search in a reduced time. This monography is a extension of previous research in which the problem described here was studied only in a bus network in the city of Fortaleza. This extension consisted of an exploration of the search strategy in graphs that represent public ways in cities like Fortaleza, Mumbai and Tokyo. Using this strategy with a heuristic algorithm, Haversine distance, was noticed that is possible to reduce substantially the time of the search, but introducing an error because of the loss of the admissible characteristic of the heuristic function applied.