Itinerary planning is generally known. Given a travel network, and a set of parameters that form an itinerary planning request, an itinerary is generated that best satisfies the parameters. The travel network typically is a street network or a public transportation network, but, in some cases, can incorporate two or more travel means to enable a comprehensive solution to be provided. The travel network consists of a set of paths, or network segments, that are terminated at both ends by nodes. For example, both metropolitan trains and transit buses travel along fixed routes that have scheduled stops therealong. Nodes can be used to represent the stops and network segments model the travel of the trains and buses between the stops. Nodes are often defined to denote points where interchange between various travel means can occur.
To further complicate things, when dealing with scheduled services such as bus and train services, network nodes may be used to not only represent physical locations, but also can be used to represent locations at particular times. This information can be important in determining estimated travel times, whether interchanges at nodes are possible and, if so, how long may have to be waited, etc. It can be undesirable to plan arrival at an intersection of a first bus route being traveled, for example, to change to a second bus route when the last bus for the day will have already departed from that location.
Itinerary planning requests typically include a departure location (referred to as an “origin”), a destination, and a desired departure time. The itinerary planning requests may also include a desired arrival time, possibly instead of the desired departure time. Using the parameters provided in the itinerary planning request, the travel network can be analyzed to identify itineraries that may be suitable and select the best one from them. Where the travel network is large, however, the process of identifying suitable itineraries can be onerous.
Many systems for itinerary planning use an approach known as Dijkstra's Algorithm to solve this problem. Dijkstra's Algorithm is a graph search algorithm that solves the single-source shortest route problem for a graph with non-negative network segment costs, producing a shortest route tree. Using this approach, the route with the lowest cost between the origin node and every other node is identified. It can also be used for finding the costs of the shortest (i.e., least costly) routes from the origin node to a destination node by stopping the algorithm once the shortest route to the destination node has been determined. This can be done since Dijkstra's Algorithm relies on maintaining partial solutions ordered by cost. This ordering of partial solutions can, however, be processor-intensive.
While Dijkstra's Algorithm and other such approaches provide a reasonably efficient solution in some scenarios, it can be cumbersome for other scenarios, such as travel networks that have relatively-uniform topologies; that is, where the lowest cost solution between any two nodes usually involves traversing the fewest network segments.
It is therefore an object of this invention to provide a system and method for itinerary planning.
USPTO Backgrounds
USPTO Backgrounds