System and method for journey planning, finding K shortest paths through a time/space network

摘要

A method and apparatus for selecting a path defining a journey through a time-tabled transportation network comprises determining forming a data set comprising a sequence of K shortest paths through the transportation network from an origin location “o” to a destination location “d”, each path with an increasing cost; and selecting a path from the K shortest paths based upon a filter criteria which may be one not used in the determination of the K shortest paths. The network comprises a public transportation network. The filter criteria not used in the determination of the K shortest paths may be one that does not obey the principal of optimality. The determining step is performed utilizing an algorithm that filters the available paths through the network according to a selected filter criteria plus a selected buffer amount Δ of the filter criteria. The selecting step utilizes only the rankings of the K shortest paths.