Patent ID: 8862386

Claim:
A method of journey planning comprising: determining the K shortest paths through a time/space transportation network including a plurality of nodes for scheduled travel of a plurality of vehicles of one or more modes of transportation between an origin location and a destination location, at least one of the plurality of vehicles being scheduled for departure from the origin location, and at least one of the plurality of vehicles being scheduled for arrival at the destination location, determining the K shortest paths including: defining a plurality of trip legs between nodes of the plurality of nodes in the time/space transportation network; defining a plurality of paths from the origin location to the destination location in the time/space transportation network, wherein each path of the plurality of paths comprises one or more of the plurality of trip legs; and enumerating a plurality of journeys for transportation of a passenger on one or more vehicles of the plurality of vehicles from the origin location to the destination location, the plurality of journeys being enumerated from the plurality of paths that satisfy a maximum journey threshold that is greater than a minimum cost value calculated according to a selected cost function, and utilizing a branch and bound analysis of partial paths, thereby defining a set of the K shortest paths in the plurality of paths; applying one or more sorting criteria to the plurality of journeys; and selecting a journey from the plurality of journeys based on application of the one or more sorting criteria, wherein at least the determining the K shortest paths, defining of the plurality of paths and enumerating the plurality of journeys are performed utilizing an apparatus including a processor and computer-readable medium including computer program code executable by the processor to cause the apparatus to at least perform the same.