US5276768A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Automated telephone information system
Assignee: TIDEWATER CONSULTANTS Inc A CORP OF VIRGINIA
•
Filing: 1991-03-20
•
Granted: 1994-01-04
•
Expires: 2011-03-20
Abstract
Abstract A system for responding to telephone queries for transit system information is disclosed in which the information received by transit information operators is used to initiate a pathfinding query, which results in a search using a heuristic method with Island Sets being performed in order to determine, for example, an itinerary which the operator can relate to the caller which answers the caller's query. A stopping rule, based on clock time, iteration count, openings of goal nodes, adjustments of goal node labels and the state of the transaction queue is also disclosed.
Inventors
- 👤 James L. Bander
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-30 09:11
CPC Classifications
G; G08; G08G; G08G1/00; G08G1/09; G08G1/0962; G08G1/0968; G08G1/096805; G08G1/096811; G06; G06Q; G06Q10/00; G06Q10/04; G06Q10/047; G08G1/096816; G08G1/096855; G08G1/096866
Claims Analysis
Total Claims: 3
Claim 1
Independent Claim
363 words
A method for computing shortest paths through a network that includes a plurality of nodes in which each node is connected to at least one successor node in said plurality of nodes, comprising the steps of: (a) selecting a starting node from said plurality of nodes on said network and selecting a goal set of nodes from said plurality of nodes on said network; (b) identifying each of the successor nodes to the selected node from said plurality of nodes on said network; (c) computing a value for an evaluation function corresponding to each of said successor nodes; (d) placing each of said successor nodes on a list; (e) removing from the list a node which has an extreme value for the evaluation function computed in step (c) when compared with all other nodes which are on the list; (f) identifying each of the successor nodes for each of said successor nodes identified in step (b), and calculating a value corresponding to each of said successor nodes in accordance with an evaluation function; (g) placing each of said successor nodes identified in step (f) on said list; (h) comparing each of the nodes identified in step (f) to a set of predetermined island nodes and, for each node that is determined to be an island node, (h 1 ) determining the successor nodes for each island node that are also island nodes (h 2 ) computing a value for an evaluation function corresponding to each of said nodes identified in step (h 1 ); and (h 3 ) placing each of said nodes for which a value is computed in step (h 2 ) in said list; (i) continuing identification of successor nodes of nodes removed from said list and computing a value for each of said identified successor nodes until certain predetermined stopping criteria are achieved; and (j) counting the total number of nodes removed from the list in step (e), the number of nodes removed from the list in step (e) since the last improved path was found, and the number of signals issued by a timer; and terminating step (i) when one of said numbers exceeds a given critical level.
Claim 2
Independent Claim
363 words
A method for computing shortest paths through a network that includes a plurality of nodes in which each node is connected to at least one successor node in said plurality of nodes, comprising the steps of: (a) selecting a starting node from said plurality of nodes on said network and selecting a goal set of nodes from said plurality of nodes on said network; (b) identifying each of the successor nodes to the selected node from said plurality of nodes on said network; (c) computing a value for an evaluation function corresponding to each of said successor nodes; (d) placing each of said successor nodes on a list; (e) removing from the list a node which has an extreme value for the evaluation function computed in step (c) when compared with all other nodes which are on the list; (f) identifying each of the successor nodes for each of said successor nodes identified in step (b), and calculating a value corresponding to each of said successor nodes in accordance with an evaluation function; (g) placing each of said successor nodes identified in step (f) on said list; (h) comparing each of the nodes identified in step (f) to a set of predetermined island nodes and, for each node that is determined to be an island node, (h 1 ) determining the successor nodes for each island node that are also island nodes (h 2 ) computing a value for an evaluation function corresponding to each of said nodes identified in step (h 1 ); and (h 3 ) placing each of said nodes for which a value is computed in step (h 2 ) in said list; (i) continuing identification of successor nodes of nodes removed from said list and computing a value for each of said identified successor nodes until certain predetermined stopping criteria are achieved; and (j) counting the total number of nodes removed from the list in step (e), the number of nodes removed from the list in step (e) since the last improved path was found, and the number of signals issued by a timer; and terminating step (i) when one of said numbers exceeds a given critical level.
Claim 3
Dependent Claim
14 words
The method of claim 1 wherein said plurality of nodes comprises a transit network.
References Cited (Backward Citations)
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1997-01-03 | 1997-07-05 | 1998-01-04 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2001-01-03 | 2001-07-05 | 2002-01-04 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2005-01-03 | 2005-07-05 | 2006-01-04 | $7700.00 | Window Closed / Lapsed |