US20120253856A1

US20120253856A1 - System and method for itinerary planning

Info

Publication number: US20120253856A1
Application number: US13/432,819
Authority: US
Inventors: Matthew David FRANCIS
Original assignee: Trapeze Software Inc
Current assignee: Trapeze Software Inc; Trapeze Group UK Ltd
Priority date: 2011-03-28
Filing date: 2012-03-28
Publication date: 2012-10-04
Also published as: EP2691740A1; CA2830578C; EP2691739A4; EP2691739A1; US9946978B2; CA2772725A1; CA2806774C; US20120253657A1; WO2012129687A1; US20140012610A1; EP2691740A4; CA2772809C; WO2012129688A1; AU2012234696A1; CA2772809A1; CA2830578A1; CA2806774A1; CA2772725C; AU2012234696B2; US20140012611A1

Abstract

The present invention relates to a method and system for itinerary planning. The method commences with the receipt of an itinerary-planning request specifying an origin and a destination. A build of network segments extending from the origin is generated. A continuing network segment extending from the build is identified. The continuing network segment is discarded if the continuing network segment is marked as a local network segment and is distant from the origin and from the destination. The continuing network segment is evaluated if the network segment is proximate to one of the origin and the destination. At least one suitable itinerary is determined for the itinerary-planning request. The at least one suitable itinerary is outputted.

Description

This application claims priority from U.S. Provisional Patent Application Ser. No. 61/468,393, filed on Mar. 28, 2011, U.S. Provisional Patent Application Ser. No. 61/468,400 filed on Mar. 28, 2011, U.S. Provisional Patent Application Ser. No. 61/490,100, filed on May 26, 2011, and U.S. Provisional Patent Application Ser. No. 61/490,105, filed on May 26, 2011, the contents of all of which are incorporated herein in their entirety by reference.

FIELD OF THE INVENTION

The present invention relates to the field of transportation. In particular, it relates to a system and method for itinerary planning.

BACKGROUND OF THE INVENTION

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, the process of identifying suitable itineraries can be onerous. The finding of suitable itineraries can involve exploring a large number of relatively small local routes, only to later determine that many of these local routes are infeasible as part of a solution. This exploration, however, can expend significant processing resources. As a result, providing such service can be costly, hardware-wise. Further, the load placed on such systems can be erratic, leading to overprovisioning to provide responses within a desired time period most of the time.
In some cases, it may be desirable to iteratively generate one or more itineraries using different parameters to identify possible itinerary solutions for an itinerary request. Such iterative solving can be expensive for long journeys, however, where the exploration of the travel network takes significantly more time.
It is therefore an object of this invention to provide a system and method for itinerary planning.

SUMMARY OF THE INVENTION

According to an aspect of the invention, there is provided a method for itinerary planning, comprising:
receiving an itinerary-planning request specifying an origin and a destination;
generating a build of network segments extending from said origin;
identifying a continuing network segment extending from said build; discarding said continuing network segment if said continuing network segment is marked as a local network segment and is distant from said origin and from said destination;
evaluating said continuing network segment if said network segment is proximate to one of said origin and said destination;
determining at least one suitable itinerary for said itinerary-planning request; and
outputting said at least one suitable itinerary.
The discarding can include:
determining a distance between said origin and the end point of said continuing network segment; and
discarding said continuing network segment if said distance exceeds a threshold.
The distance can be a travel distance between the origin and the end point of the continuing network segment.
The threshold can be constant or variable.
The discarding can include discarding the continuing network segment if the continuing network segment is outside a region of the destination. The region can be defined by a distance threshold.
According to another aspect of the invention, there is provided a method for itinerary planning, comprising:
receiving an itinerary-planning request specifying an origin and a destination;
generating a build of network segments extending from said origin;
identifying a continuing network segment extending from said build;
if said continuing network segment is distant from said origin and from a destination, evaluating said continuing network segment only if said continuing network segment is marked as a trunk network segment;
determining at least one suitable itinerary for said itinerary-planning request; and
outputting said at least one suitable itinerary.
According to a further aspect of the invention, there is provided a system for itinerary planning, comprising:
a database of network segments;
a processor executing computer-executable instructions for analyzing said network segments and, in response to an itinerary-planning request specifying an origin and a destination, generating a build of network segments extending from said origin, identifying a continuing network segment extending from said build, discarding said continuing network segment if said continuing network segment is marked as a local network segment and is distant from said origin and from a destination, evaluating said continuing network segment if said network segment is proximate to one of said origin and said destination, determining at least one suitable itinerary for said itinerary-planning request, and outputting said at least one suitable itinerary.
The processor can determine a distance between the origin and the end point of the continuing network segment, and discard the continuing network segment if the distance exceeds a threshold. The threshold can be constant or variable.
The distance can be a travel distance between the origin and the end point of the continuing network segment.
The processor can discard the continuing network segment if the continuing network segment is outside a region of said destination. The region can be defined by a distance threshold.
Other and further advantages and features of the invention will be apparent to those skilled in the art from the following detailed description thereof, taken in conjunction with the accompanying drawings.

BRIEF DESCRIPTION OF THE DRAWINGS

The invention will now be described in more detail, by way of example only, with reference to the accompanying drawings, in which like numbers refer to like elements, wherein:

FIG. 1 is a schematic diagram of a computer system for itinerary planning in accordance with an embodiment of the invention, and its operating environment;

FIG. 2 is a block diagram of the computer system shown in FIG. 1;

FIG. 3 shows illustrative network segments of a large travel network with a point of departure and a destination for a trip desired to be made by a user of the computer system of FIG. 1;

FIG. 4 shows the travel network of FIG. 3, with a perimeter drawn around the point of departure and around the region of the destination;

FIGS. 5A and 5B show a flowchart of the general method of itinerary planning performed by the computer system of FIG. 1; and

FIG. 6 is a flowchart of the determination of whether a build including a continuing network segment is suitable in the method of FIGS. 5A and 5B.

DETAILED DESCRIPTION OF THE EMBODIMENTS

The invention relates to a system and method of itinerary planning. Given an itinerary-planning request that includes an origin (commonly referred to as a “point of departure”), a destination, a desired time of departure or arrival and various other constraints, one or more suitable travel itineraries is generated, if possible. Each solution is known as an itinerary. An itinerary can include some combination of public transportation, walking and road travel by private vehicle or taxi. Nodes are physical locations, such as intersections, bus stops and train stations. Network segments represent means for traveling between the nodes. A network segment is usually one of the following: a set of trips between consecutive stopping points, a walk transfer between vehicles, and the traversal of a street segment, either on foot or by private vehicle (for example, car or taxi).
It has been found that, by only considering network segments that traverse trunk routes during the generation of a series (or “build”) of connected network segments when proximate to neither the point of departure nor the destination, processing time can be reduced significantly for itineraries that span large distances in most circumstances. Further, solutions that incorporate unsuitable network segments in the middle of the solution (unsuitable due to reliability, limited capacity, unsafe interchanges, etc.) can be automatically excluded.
FIG. 1 shows a computer system 20 for itinerary planning in accordance with an embodiment of the invention, and its operating environment. The computer system 20 stores travel network data about various travel networks. The computer system 20 is coupled to a large communications network 24, such as the Internet. The computer system 20 operates a web service for serving web pages in response to requests for the same. A personal computer 28 is also shown in communication with the communications network 24 and executes an operating system and a web browser for enabling a user to access content available through web servers. A mobile device 32 is additionally in communication with the communications network 24 via a number of intermediate cellular communications towers, servers and switches that are not shown. Like the personal computer 28, the mobile device 32 executes an operating system and a web browser for enabling a user to access functionality and data available through web servers.
FIG. 2 shows a number of components of the computer system 20 for itinerary planning of FIG. 1. As shown, the computer system 20 has a number of components, including a central processing unit (“CPU”) 44 (also referred to simply as a “processor”), random access memory (“RAM”) 48, an input/output interface 52, a network interface 56, non-volatile storage 60, and a local bus 64 enabling the CPU 44 to communicate with the other components. The CPU 44 executes computer-executable instructions for an operating system and programs that provide the desired functionality. RAM 48 provides relatively-responsive volatile storage to the CPU 44. The input/output interface 52 allows for input to be received from one or more devices, such as a keyboard, a mouse, etc., and enables the CPU 44 to present output to a user via a monitor, a speaker, etc. The network interface 56 permits communication with other systems for receiving itinerary-planning requests and for providing itinerary responses, in the form of web pages. Non-volatile storage 60 stores the computer-executable instructions. During operation of the computer system 20, the computer-executable instructions for providing the operating system and the programs, and the data may be retrieved from the non-volatile storage 60 and placed in RAM 48 to facilitate execution. A travel network database 68 storing travel network data is maintained by the computer system 20 in non-volatile storage 60.
The computer system 20 executes computer-executable instructions in the form of itinerary-planning software stored in the non-volatile storage 60. The itinerary-planning software generates itineraries for itinerary-planning requests that include some request parameters, such as, for example, the origin of the journey, the journey destination, the preferred time of departure and/or the preferred time of arrival, etc. The itineraries include one or more journey segments. The journey segments correspond to rides on transit vehicles such as buses and trains, walked passages, taxi rides, etc.
Using the travel network data stored in the travel network database 68, the itinerary-planning software is able to generate one or more itineraries for travel from the origin to the destination. The generated itineraries can be generally optimized on one or more of time, cost, the amount of walking, the number of vehicle transfers, the timeliness of the arrival, the timeliness of the departure, the number of travel means changes (such as interchanges between buses), etc. In addition to the itinerary-planning software, the computer system 20 executes a web service for serving web pages in response to requests received from clients such as the personal computer 28 and the mobile device 32.
The travel network database 68 stores information about various public transportation networks and street networks. The various networks include a set of nodes connected via network segments. As there are often two or more means for traveling from one node to another, nodes can be connected by more than one network segment. The travel network data can include public transportation route and schedule information, road networks, gradients for street network segments, traffic volume information, etc. Public transportation routes can include, for example, intercity trains, buses, ferries, airplanes, and urban bus and train routes. Using the travel network data, the computer system 20 can receive an itinerary-planning request generated via a served request page, analyze the travel network data, generate one or more itineraries, and generate and serve one or more web pages that show the itineraries generated for the itinerary-planning request.
In the travel network database 68, network segments representing the travel of a vehicle in one direction between a set of stops along a fixed route are identified as belonging to the same pattern. This enables the computer system 20 to understand which network segments represent travel along the same route and which represent a change of vehicle. Schedule information for each pattern is also stored in the travel network database 68.
Further, the travel network database 68 stores information about pattern-transfers. Pattern-transfers are connections between all inbound trip segments belonging to the same pattern and all outbound trip segments belonging to another pattern. An amount of walking may be involved. For various reasons, notably performance, transfers are pre-calculated during data preparation. There is also usually a transfer comfort time associated with each transfer. This ensures that there are no dangerously-tight connections in itineraries returned. The comfort time is in addition to the walk time required to make the transfer. The comfort time is set when transfers are created and has a typical value of 5 minutes.
Administrators can mark network segments in the travel network data as trunk or local network segments via a network segment marking tool. Network segments are marked as trunk network segments based on their suitability for use in the middle of a long-distance journey. Network segments may be suitable for use in the middle of a long-distance journey for a variety of reasons. It is generally desirable to traverse the middle of a long-distance journey at a faster pace, either by faster travel speeds or by making less stops. As it can be undesirable to have to find alternative, slower routers while en route to a destination, reliability and capacity availability are two characteristics that may be desirable for trunk routes. That is, once a person is en route to a destination and finds out that a leg of the itinerary is unavailable, either due to a lack of available capacity or due to a service outage, the person may have to spend significant additional time getting to the destination via an alternate route. The same can be true where a person is onboard a vehicle that undergoes a failure. Further, some interchanges may be excluded because they are deemed to be unsafe by the administrator. This could be a temporary or permanent arrangement due to poor street lighting, road safety issues, crowd segregation, or any reason known to the local authorities. By selecting more reliable network segments with a better chance of having available passenger capacity for the middle of a long-distance journey, the likelihood of encountering such issues, and suffering significant additional travel time, can be reduced.
The administrator preferably has knowledge of the travel network and is able to select network segments that have characteristics that are desirable for the middle of a long-distance journey. In doing so, the administrator may mark some or all of the network segments of a transit route as trunk network segments. In some cases, sections of a transit route can have characteristics that make them suitable for use in the middle of a long-distance journey, whereas other sections of the transit route may be unsuitable for the same. Further, what constitutes the middle of a long-distance journey may vary depending on the size and make-up of the travel network. Thus, a network segment marked as a trunk network segment in a small travel network may not be deemed a trunk network segment by an administrator for a larger travel network.
The computer system 20 allows for the selection of itinerary solutions based on any one or more of a number of factors. Typically, itinerary planning is associated with finding solutions that have the shortest duration. However, time may not be the only concern for a typical traveler. Many travelers are willing to compromise on the optimization of time provided that the solutions offer some other benefit, such as fewer transfers.
FIG. 3 shows exemplary network segments of a relatively-large travel network over which a user may wish to make a trip. A point of departure 104 shown on the left is in a first urban area. A destination 108 shown on the right resides in a separate urban area a significant distance away, perhaps even across the country. Note that while there are many more than the illustrated network segments in the two urban areas in which the point of departure 104 and the destination 108 reside and in between them, they are not shown. Traditional large itinerary-planning solutions would explore each network segment connected to the end of a build generated during the itinerary-generating process, regardless of the type of network segment that the network segments represent. With long trips, such solutions can require the exploration of a vast number of various builds in an effort to find a suitable solution. Generally in such circumstances, the solution found after exploring all routes involves travel over a trunk route between the area of the point of departure and the area of the destination.
The method of the invention simplifies the process of locating such solutions by only considering trunk routes when selecting network segments outside the proximity of the point of departure and the destination.
FIG. 4 shows the travel network of FIG. 3 with a first perimeter 112 drawn around the point of departure. This first perimeter 112 represents a boundary of a region of the travel network that may be traversed before exceeding a travel distance threshold. While the first perimeter 112 appears as generally circular, those skilled in the art will appreciate that the first perimeter 112 may vary in irregularity depending on the travel network and the threshold. In addition, a second perimeter 116 is shown drawn around the region in which the destination 108 resides. An external region 120 resides outside of the first perimeter 112 and the second perimeter 116. In generating an itinerary, network segments explored around the point of departure 104 are limited to those within a pre-defined travel distance of the point of departure 104, after which only continuing network segments traveling over trunk routes are considered in the external region 120. Thus, the builds continue to be generated using trunk routes in the external region 120. Once the builds generated near the destination, local routes can be employed to extend the builds.
Using this approach, local network segments that are not proximate the point of departure 104 or the destination 108 (i.e., that are in the external region 120) are not explored, thereby significantly reducing the number of builds that have to be generated before a suitable itinerary is found in many cases.
FIGS. 5A and 5B illustrate the general method 200 of itinerary planning employed by the itinerary-planning software of the computer system 20.
The method commences with the initialization of two thresholds, Dmaxo and Dmaxd (202). Dmaxo defines a travel distance along the travel network from the origin within which local network segments may be explored during itinerary generation. Dmaxd defines the size of a region around the destination in which travel via local network segments is explored. When building toward the destination, a more crude approximation is required, since the distance along the travel network to the destination is not yet known. A square around the destination is used to approximate the destination zone. Dmaxd represents the distance from the destination to the sides of a square bounding the region and the destination. Typically, Dmaxo and Dmaxd are constants that are both set to the same fixed value for the generation of a single itinerary solution; e.g., 50 miles.
Upon initializing Dmaxo and Dmaxd, an input queue is created for all network segments connected to the origin (204). The itinerary-planning software selects all network segments departing from the origin on or after the desired departure time from the travel network database 68, and places them in a first queue referred to as an input queue. The order in which the selected network segments are placed in the input queue is not important.
One of the builds is then removed for analysis from the input queue (208). As previously noted, builds are series of one or more connected network segments that form at least part of a potential solution. Immediately after 204, the builds in the input queue consist of one network segment each. As the builds are arbitrarily ordered in the input queue, the builds removed from the input queue are arbitrarily ordered. Upon removing the network segment from the input queue, the itinerary-planning software determines if there are network segments in the travel network database 68 that continue from the end node of the removed build (212). The itinerary-planning software searches the travel network database 68 for all network segments that continue from the end node of the build removed from the input queue and places them in a continuing network segment processing queue. As the itinerary-planning software appends continuing network segments onto builds, it is aware of the timing points of preceding network segments and is able to identify the first trip of a pattern for the continuing network segments. All of this information regarding which particular trip along each network segment of a build of network segments representing at least a part of a solution is maintained by the itinerary-planning software.
If there are any network segments that continue from the end node of the removed network segment, one is selected from the continuing network segment processing queue (216).
Upon the selection of a continuing segment, the suitability of the build including the continuing segment is determined (218). It is at this point that continuing network segments over local routes and builds that include them are permitted or excluded based on proximity to the point of departure and/or destination. As a result, only those portions of builds that are proximate the point of departure and/or the destination can traverse local routes. The intermediate portion, if any, can only employ trunk routes.
FIG. 6 shows the general method 218 of determining whether a build is suitable. The method 218 commences with the determination of whether the continuing network segment selected at 216 is part of a local route (310). If the continuing network segment is part of a trunk route, the build is deemed suitable (320), after which the method 218 ends. If, instead, the continuing network segment is determined to be part of a local route at 310, it is determined whether the “length” of the build is greater than Dmaxo (330). The “length” in this case refers to the travel distance from the point of departure to the end of the build including the continuing network segment. As it is desirable to only explore builds continuing over local routes proximate the point of departure or destination, builds that end with continuing network segments using local routes outside of these areas are quickly located and discarded. If the length of the build is determined to be lesser than Dmaxo at 330, then the build is deemed to be suitable at 320, after which the method 218 ends. That is, if the continuing network segment travels over local routes and is proximate the point of departure, the build is deemed suitable. If the continuing network segment is found to traverse a local route at 310 and the length of the build is determined to exceed Dmaxo at 330, it is then determined if the continuing network segment is in the region of the destination (340). Here, it is determined if the continuing network segment has a start point and an end point that are both within the region of the destination. Again, the region of the destination is defined as a square of length (2×Dmaxd) that is centered on the destination. If both the start point and the end point of the continuing network segment are in the region of the destination, the build terminating with the continuing network segment is deemed to be suitable at 320, after which the method 218 ends. If, instead, either the start point or the end point of a continuing network segment are outside of the region of the destination, the build terminating with the particular continuing network segment is deemed unsuitable (350), after which the method 218 ends.
Returning again to FIGS. 5A and 5B, if the build including the continuing network segment selected at 216 is deemed unsuitable, the method 200 returns to 212 where it is determined if there are unexamined continuing network segments. If, instead, the build including the continuing network segment selected at 216 is deemed suitable, the itinerary-planning software determines if the continuing network segment has been previously considered for this particular itinerary plan (220). If the continuing network segment has not been considered before, the continuing network segment is examined to determine if it arrives at the destination (224). If it does, the total cost to arrive at the destination via the currently-analyzed build including the continuing network segment is noted (228), and the method returns to 212 to analyze other unanalyzed continuing network segments, if any. If the continuing network segment does not arrive at the destination, the itinerary-planning software determines if the total cost to arrive at the end of the continuing network segment via the currently-analyzed build is, in fact, the best cost to arrive at the end of the network segment (232). If the cost to arrive at the end of the continuing network segment via the currently-analyzed build is not the best found so far for that network segment, the method returns to 212 to analyze another unanalyzed continuing network segment, if any. If, instead, the cost to arrive at the end of the continuing network segment via the currently-analyzed build is the best found thus far, the currently-analyzed build, including the build removed from the input queue and the continuing network segment, is placed as an expansion in a second queue, referred to as an output queue (236). After placement of the expansion in the output queue, the method returns to 212 to analyze another unanalyzed continuing network segment, if any.
If, instead, at 220, the itinerary-planning software determines that the continuing network segment has previously been considered, the itinerary-planning software determines if the total cost to arrive at the end of the continuing network segment via the currently-analyzed build is the best cost to arrive at the end of that network segment (240). If it is not, that continuing network segment is discarded as an expansion of the build removed from the input queue, after which the method thereafter returns to 212 to analyze another unanalyzed continuing network segment, if any. If, however, the cost for arriving at the end of the continuing network segment via the currently-analyzed build is the best found thus far, the itinerary-planning software determines if the continuing network segment arrives at the destination (244). If it does, the itinerary-planning software notes the total cost (248), and the method returns to 212 to analyze another unanalyzed continuing network segment, if any. If the continuing network segment does not arrive at the destination, the itinerary-planning software determines if the total cost to arrive at the end of the particular network segment via the currently-analyzed build exceeds the best cost found thus far to arrive at the destination (252). If the cost to arrive at the end of the network segment via the currently-analyzed build exceeds the best cost found thus far to arrive at the destination, the method returns to 212 to analyze another unanalyzed continuing network segment, if any. If, however, the cost to arrive at the end of the continuing network segment via the currently-analyzed build is, in fact, lower than the best cost found thus far to arrive at the destination, the itinerary-planning software determines if the continuing network segment is already in the output queue (256). If the continuing network segment is already in the output queue, the method returns to 212 to analyze another unanalyzed continuing network segment, if any. If, however, the continuing network segment is not found in the output queue, the build removed from the input queue and the continuing network segment are “captured” and re-placed in the input queue as a build (260). Thereafter, the method returns to 212 to analyze another unanalyzed continuing network segment, if any.
Once the itinerary-planning software determines that there are no further unanalyzed continuing network segments at 212, the itinerary-planning software determines if there are builds remaining in the input queue (264). If there are, the method returns to 208, at which the itinerary-planning software removes another build from the input queue for analysis. If, however, there are no further builds in the input queue, the itinerary-planning software determines if there are builds in the output queue (268). If the output queue is not empty, the builds in the output queue are moved to the input queue (272). Thereafter, the method returns to 208, with the itinerary-planning software removing a build from the input queue for further analysis. If the output queue is found to be empty at 268, the method ends.
The computer system 20 then outputs the itinerary to storage and prepares and serves a web page presenting the itinerary to the user.
In cases where the distance between the origin and the destination is slightly more than Dmaxo, it may be the case that one or more builds of that length arrive in the region of the destination and, as a result, itinerary solutions may be found that traverse local routes only.
While, in the described embodiment, the itinerary-planning system finds a solution from the origin to the destination, those skilled in the art will appreciate that the origin may represent a network node close to the address specified by a user as a starting point, and that the destination may represent a network node close to the address specified by the user as an end point for the desired trip.
Other means of defining proximity to the origin and/or the destination will occur to those skilled in the art. For example, Dmaxo and Dmaxd can be set to different values. These values may also vary depending on the location of the origin and the destination, respectively. In another example, regions can be pre-defined and used for determining proximity for both the origin and the destination. In a further example, the region of the destination in which travel over local network segments is permitted can be circular.
The thresholds Dmaxo and Dmaxd may be varied in various circumstances. For example, where a person has expressed a desire to travel by bus, a mode deemed “local” by the administrator, the thresholds can be increased to enable consideration of travel from the origin to the destination completely by bus.
The method may be performed repeatedly using different parameters and inputs in an effort to locate satisfactory alternative solutions.
Computer-executable instructions for implementing the itinerary-planning software on a computer system could be provided separately from the computer system, for example, on a computer-readable medium (such as, for example, an optical disk, a hard disk, a USB drive or a media card) or by making them available for downloading over a communications network, such as the Internet.
While the computer system is shown as a single physical computer, it will be appreciated that the computer system can include two or more physical computers in communication with each other. Accordingly, while the embodiment shows the various components of the itinerary-planning software residing on the same physical computer, those skilled in the art will appreciate that the components can reside on separate physical computers.
This concludes the description of the presently preferred embodiments of the invention. The foregoing description has been presented for the purpose of illustration and is not intended to be exhaustive or to limit the invention to the precise form disclosed. It is intended the scope of the invention be limited not by this description but by the claims that follow.

Claims

1. A method for itinerary planning, comprising:

receiving an itinerary-planning request specifying an origin and a destination;

generating a build of network segments extending from said origin;

identifying a continuing network segment extending from said build;

discarding said continuing network segment if said continuing network segment is marked as a local network segment and is distant from said origin and from said destination;

evaluating said continuing network segment if said network segment is proximate to one of said origin and said destination;

determining at least one suitable itinerary for said itinerary-planning request; and

outputting said at least one suitable itinerary.

2. The method of claim 1, wherein said discarding comprises:

determining a distance between said origin and the end point of said continuing network segment; and

discarding said continuing network segment if said distance exceeds a threshold.

3. The method of claim 1, wherein said distance is a travel distance between said origin and the end point of said continuing network segment.

4. The method of claim 2, wherein said threshold is constant.

5. The method of claim 2, wherein said threshold is variable.

6. The method of claim 1, wherein said discarding comprises:

discarding said continuing network segment if said continuing network segment is outside a region of said destination.

7. The method of claim 6, wherein said region is defined by a distance threshold.

8. A method for itinerary planning, comprising:

receiving an itinerary-planning request specifying an origin and a destination;

generating a build of network segments extending from said origin;

identifying a continuing network segment extending from said build;

if said continuing network segment is distant from said origin and from a destination, evaluating said continuing network segment only if said continuing network segment is marked as a trunk network segment;

outputting said at least one suitable itinerary.

9. A system for itinerary planning, comprising:

a database of network segments;

a processor executing computer-executable instructions for analyzing said network segments and, in response to an itinerary-planning request specifying an origin and a destination, generating a build of network segments extending from said origin, identifying a continuing network segment extending from said build, discarding said continuing network segment if said continuing network segment is marked as a local network segment and is distant from said origin and from a destination, evaluating said continuing network segment if said network segment is proximate to one of said origin and said destination, determining at least one suitable itinerary for said itinerary-planning request, and outputting said at least one suitable itinerary.

10. The system of claim 9, wherein said processor determines a distance between said origin and the end point of said continuing network segment, and discards said continuing network segment if said distance exceeds a threshold.

11. The system of claim 9, wherein said distance is a travel distance between said origin and the end point of said continuing network segment.

12. The system of claim 10, wherein said threshold is constant.

13. The system of claim 10, wherein said threshold is variable.

14. The system of claim 9, wherein said processor discards said continuing network segment if said continuing network segment is outside a region of said destination.

15. The system of claim 14, wherein said region is defined by a distance threshold.

16. The system of claim 9, further comprising a marking tool for enabling the marking of said network segments as local or trunk network segments.