Method and system for generating viable pattern-transfers for an itinerary -planning system

Abstract

The present invention relates to a method and system for generating viable pattern-transfers for an itinerary-planning system. The method commences with the identification of pairs of patterns along fixed transit routes that are proximate one another. Each of the patterns include a number of stops connected by pattern segments traveled in a specific order. Pattern-transfers are identified between the stops along an inbound pattern of the pairs and the stops along an outbound pattern of the pairs. At least one of the pattern-transfers is discarded if traveling from the inbound pattern to the outbound pattern via the at least one of the pattern-transfers is unadvantageous compared to traveling from the inbound pattern to the outbound pattern via at least one other of the pattern-transfers. The undiscarded pattern-transfers are stored in storage for use by an itinerary-planning system.

What is claimed is: 
     
         1 . A method for generating viable pattern-transfers for an itinerary-planning system, comprising:
 identifying pairs of patterns along fixed transit routes that are proximate one another, each of said patterns comprising a number of stops connected by pattern segments traveled in a specific order;   identifying pattern-transfers between said stops along an inbound pattern of said pairs and said stops along an outbound pattern of said pairs;   discarding at least one of said pattern-transfers if traveling from said inbound pattern to said outbound pattern via said at least one of said pattern-transfers is unadvantageous compared to traveling from said inbound pattern to said outbound pattern via at least one other of said pattern-transfers; and   storing said undiscarded pattern-transfers in storage for use by an itinerary-planning system.   
     
     
         2 . The method of  claim 1 , wherein said pattern-transfers traverse a walking network. 
     
     
         3 . The method of  claim 2 , wherein said identifying pattern-transfers comprises:
 determining if said pattern-transfers between one of said stops along said inbound pattern and stops along said outbound pattern and other patterns have been previously identified.   
     
     
         4 . The method of  claim 3 , wherein said identifying pattern-transfers further comprises:
 performing an itinerary query over a walking network to identify said pattern-transfers between said one stop along said inbound pattern and stops proximate said one stop along said outbound pattern and other patterns if said pattern-transfers have not been identified for said one stop along said inbound pattern.   
     
     
         5 . The method of  claim 4 , wherein said itinerary query includes said one stop along said inbound pattern as an origin, an arbitrary location relatively distant from said one stop as a destination and a specified maximum walking distance. 
     
     
         6 . The method of  claim 5 , wherein said itinerary query includes an arbitrary departure time. 
     
     
         7 . The method of  claim 5 , wherein said identified pattern-transfers are registered in a node-connection map. 
     
     
         8 . The method of  claim 7 , wherein said node-connection map indicates that said itinerary query was performed for said one stop along said inbound pattern. 
     
     
         9 . The method of  claim 8 , wherein said determining comprises:
 determining if said itinerary query has been performed for said one stop.   
     
     
         10 . The method of  claim 2 , wherein said identifying pattern-transfers comprises:
 performing an itinerary query over a walking network to identify said pattern-transfers available at a stop along segment between one of said stops on said first pattern and one of said stops on said second pattern.   
     
     
         11 . The method of  claim 1 , wherein said identifying pattern-transfers comprises:
 identifying pattern-transfers between said stops along said inbound pattern and said stops on said outbound pattern.   
     
     
         12 . The method of  claim 1 , wherein said discarding comprises:
 identifying at least one alternate route from said inbound pattern to said outbound pattern via said other pattern-transfers having a shorter expected travel time and walking distance than via said at least one pattern-transfers.   
     
     
         13 . The method of  claim 1 , wherein said discarding comprises:
 selecting outbound pattern segments along said outbound pattern, commencing with a first of said outbound pattern segments and subsequently selecting immediately-subsequent outbound pattern segments; and   selecting inbound pattern segments along said inbound pattern, commencing with a last of said inbound pattern segments and subsequently selecting immediately-preceding inbound pattern segments.   
     
     
         14 . The method of  claim 13 , wherein said discarding further comprises:
 evaluating transferring from said inbound pattern to said outbound pattern via said pattern-transfers bridging from the end of said selected inbound pattern segments to the start of said selected outbound pattern segments in comparison to transferring from said inbound pattern to said outbound pattern via said pattern-transfers bridging from the end of previously-selected inbound pattern segments to the start of said previously-selected outbound pattern segments.   
     
     
         15 . The method of  claim 14 , wherein said discarding further comprises:
 discarding said pattern-transfers bridging from the end of said selected inbound pattern segments to the start of said selected outbound pattern segments if transferring from said inbound pattern to said outbound pattern via said pattern-transfers bridging from the end of said selected inbound pattern segments to the start of said selected outbound pattern segments is unadvantageous in comparison to transferring from said inbound pattern to said outbound pattern via said pattern-transfers bridging from the end of said previously-selected inbound pattern segments to the start of said previously-selected outbound pattern segments.   
     
     
         16 . The method of  claim 14 , wherein said discarding further comprises:
 discarding said pattern-transfers between said selected inbound pattern segments to the start of said selected outbound pattern segments if transferring from said inbound pattern to said outbound pattern via said pattern-transfers bridging from the end of said selected inbound pattern segments to the start of said selected outbound pattern segments is unadvantageous in comparison to transferring from said inbound pattern to said outbound pattern via said pattern-transfers bridging from the end of said previously-selected inbound pattern segments and said previously-selected outbound pattern segments.   
     
     
         17 . The method of  claim 14 , wherein said discarding further comprises:
 discarding said pattern-transfers bridging from the end of said selected inbound pattern segments to the start of said selected outbound pattern segments if said pattern-transfers bridging from the end of said selected inbound pattern segments to the start of said selected outbound pattern segments are longer than said pattern-transfers bridging from the start of said selected inbound pattern segments to the start of said previously-selected outbound pattern segments.   
     
     
         18 . The method of  claim 14 , wherein said discarding further comprises:
 discarding said pattern-transfers bridging from the end of said selected inbound pattern segments to the start of said selected outbound pattern segments if said pattern-transfers bridging from the end of said selected inbound pattern segments to the start of said selected outbound pattern segments are longer than said pattern-transfers bridging from the end of said selected inbound pattern segments to the end of said selected outbound pattern segments.   
     
     
         19 . The method of  claim 14 , wherein said discarding further comprises:
 discarding said pattern-transfers bridging from the end of said selected inbound pattern segments to the start of said selected outbound pattern segments if said pattern-transfers bridging from the end of said selected inbound pattern segments to the start of said selected outbound pattern segments are longer than said pattern-transfers bridging from the start of said selected inbound pattern segments to the end of said selected outbound pattern segments.   
     
     
         20 . The method of  claim 14 , wherein said discarding further comprises:
 discarding said pattern-transfers bridging from the end of said selected inbound pattern segments to the start of said selected outbound pattern segments if transferring from said inbound pattern to said outbound pattern via said pattern-transfers bridging from the end of said selected inbound pattern segments to the start of said selected outbound pattern segments is slower than transferring from said inbound pattern to said outbound pattern via said pattern-transfers bridging from the start of said selected inbound pattern segments to the end of said selected outbound pattern segments.   
     
     
         21 . The method of  claim 14 , wherein said discarding further comprises:
 discarding said pattern-transfers bridging from the end of said selected inbound pattern segments to the start of said selected outbound pattern segments if traveling along said selected inbound segments and transferring from said inbound pattern to said outbound pattern via said pattern-transfers bridging from the end of said selected inbound pattern segments to the start of said selected outbound pattern segments is unadvantageous in comparison to transferring from said inbound pattern to said outbound pattern at the start of said selected inbound pattern segments and traveling along said outbound pattern to the start of said selected outbound pattern segments.   
     
     
         22 . The method of  claim 14 , wherein said discarding further comprises:
 discarding said pattern-transfers bridging from the end of said selected inbound pattern segments to the start of said selected inbound pattern segments if transferring from said inbound pattern to said outbound pattern via said pattern-transfers bridging from the end of said selected inbound pattern segments to the start of said selected outbound pattern segments and traveling along said selected outbound pattern segments is unadvantageous in comparison to traveling further along said inbound pattern past the end of said selected inbound pattern segments and then transferring from said inbound pattern to said outbound pattern via said pattern-transfers bridging to the end of said selected outbound pattern segments.   
     
     
         23 . The method of  claim 1 , wherein said identifying pairs of patterns comprises:
 determining that said pairs of patterns are proximate one another if rectangles bounding said patterns in said pair overlap or are proximate one another.   
     
     
         24 . A computer system for generating viable pattern-transfers for an itinerary-planning system, comprising:
 a processor executing computer-readable instructions for identifying pairs of patterns along fixed transit routes in a travel network database that are proximate one another, each of said patterns comprising a number of stops connected by pattern segments traveled in a specific order, identifying pattern-transfers between said stops along an inbound pattern of said pairs and said stops along an outbound pattern of said pairs, discarding at least one of said pattern-transfers if traveling from said inbound pattern to said outbound pattern via said at least one of said pattern-transfers is unadvantageous compared to traveling from said inbound pattern to said outbound pattern via at least one other of said pattern-transfers, and storing said undiscarded pattern-transfers in storage accessible to said computer system for use by an itinerary-planning system.   
     
     
         25 . A method for generating viable pattern-transfers for an itinerary-planning system, comprising:
 identifying pairs of patterns along fixed transit routes that are proximate one another, each of said patterns comprising a number of stops connected by pattern segments traveled in a specific order;   selecting one of said pairs of patterns;   setting one of said patterns in said one pair as an inbound pattern and another of said patterns in said one pair as an outbound pattern;   identifying pattern-transfers between said stops along an inbound pattern and said stops along an outbound pattern; and   storing at least one of said pattern-transfers in storage for use by an itinerary-planning system if traveling from said inbound pattern to said outbound pattern via said at least one of said pattern-transfers provides an advantage compared to traveling from said inbound pattern to said outbound pattern via other of said pattern-transfers.