Geintra

This article describes a search algorithm adapted to the Spanish
Railway Network for generating as many traveling options as possible between
two railway stations. This algorithm (Warshall’s algorithm) uses connecting
matrices to find all possible railway journeys. The Spanish Railway Company
has imposed severe restrictions: less than 1 second per query in a 600Mhz
processor PC with 32Mb RAM and 150Mb hard disk free memory. The final
average time for a simple query is around 0.25 seconds and the whole memory
consumption is 127Mb. The final implementation has been divided into 3
modules. In the first module, we store additional information in the connecting
matrices to accelerate the later search, proposing several strategies for reducing
thier size. The journey option calculation module accesses the matrix information
and composes the traveling options. Finally, in the filtering module we
describe the selection criteria considering the algorithm embedded in a general
information service.