Integrated journey planner

• US 6,834,229 B2
• Filed: 10/18/2002
• Issued: 12/21/2004
• Est. Priority Date: 02/09/2000
• Status: Expired due to Term

• Current Assignee: Travelfusion Ltd. (Trip.com Group Ltd.)
• Original Assignee: Travelfusion Ltd. (Trip.com Group Ltd.)
• Inventors: Rice, James Robert, Sadler, Andrew John, Harrison, Paul Richard, Rafiah, Moshe, Ferguson, John Spencer Guy
• Primary Examiner(s): Zanelli, Michael J.
• Application Number:
  US10/204,934
• Publication Number:
  US 20030109266A1
• Time in Patent Office: 795 Days
• Field of Search: 701/201, 701/209, 701/202, 701/207, 701/210, 340/995.19, 705/6
• US Class Current: 701/201
• CPC Class Codes: G01C 21/3423 Multimodal routing, i.e. combining two or more modes of transportation, where the modes can be any of, e.g. driving, walking, cycling, public transport
• CPC Class Codes: G06Q 10/047 Optimisation of routes or paths, e.g. travelling salesman problem

Abstract

An integrated journey planner deconstructs user enquiries into information requests, each specifying a journey part using a single transport mode, e.g., rail, car or coach. The planner sends each request to one of a plurality of local and on-line databases, each corresponding to a different transport mode. Responses from the databases are reconstructed into multi-modal travel option(s) for the user specified journey, incorporating different transport modes. The multi-modal travel option(s) incorporates timetable travel information and non-timetable travel information. Also, a user can specify a geographical location and a transport mode to find the most suitable terminals and services for uni-modal point to point travel.

Claims

1. A method of providing journey information to a user, the method comprising:

receiving unique location reference information identifying the start and end locations of a user-defined journey;

considering at least some possible predetermined pairs of access points to a transport network of a single mode of transport, the access points being at different locations than the start and end locations;

selecting those pairs of access points which minimize a selection factor between the start and end locations and the access points respectively;

generating an information request containing a selected pair of access points and sending the request to a knowledge store holding information regarding the single mode of transport;

receiving multiple different responses representing different travel options from the knowledge store;

constructing comparative multiple travel options for the user-specified journey from the response received from the knowledge store; and

providing all the comparative multiple travel options to the user on a single viewing page for ease of comparison and user selection.

2. A method according to claim 1, wherein the selection factor comprises one of the group comprising:

a route cost;

a route distance; and

a route traveling time between the access points and the start and end locations.

3. A method according to claim 2, wherein the selection factor is weighted by consideration of the distance of the user-defined journey.

4. A method according to claim 1, wherein the considering step comprises for a given service operator considering only those pairs of access points which are available as part of the service operator'"'"'s network service.

5. A method according to 1, wherein the unique location reference is a unique co-ordinate position of the location.

6. A method according to claim 1, wherein the unique location reference information comprises a user recognizable identifier name of a location.

7. A method according to claim 1, wherein the considering step comprises identifying respective start and end geographic regions within which the start and end locations are present, and considering only those pairs of access points provided within these regions.

8. A method according to claim 7, wherein the regions are non-overlapping.

9. A method according to claim 1, further comprising determining the unique location reference information from user-specified start and end location names.

10. A method according to claim 9, wherein the determining step comprises interpreting the user-entered location names by finding the closest matches to pre-stored location names have predetermined unique location references for use with the receiving step.

11. A method according to claim 9, further comprising noting one of the group comprising:

a user-specified departure time from the start location; and

a user-specified arrival time for the end location, and providing this noted time information in the information request.

12. A method according to claim 9, wherein the determining step is carried out via a mobile telecommunications device.

13. A method according to claim 1, further comprising determining the unique location reference information from a user-specified location name and from an automatic current location of user determining procedure.

14. A method according to claim 13, wherein the automatic user current location determining procedure comprises automatically determining a current unique geographic location reference of the user by using radio transmission techniques for the subsequent receiving step.

15. A method according to claim 13, wherein the determining step comprises interpreting a user-entered location name by finding the closest match to pre-stored location names having predetermined location co-ordinates for use with the receiving step.

16. A method according to claim 14, wherein the automatically determining step is carried out via a mobile telecommunications device.

17. A method according to claim 16, wherein the automatically determining step is carried out using a Wireless Application Protocol.

18. A computer-readable medium/electrical carrier signal encoded with a program for causing a computer to perform the method of claim 14.

19. A method according to claim 1, wherein multiple different responses representing different travel options are received from the knowledge store and the constructing step comprises constructing comparative multiple travel options for the user-specified journey for user comparison.

20. A method according to claim 19, wherein the multiple travel options are ranked according to a user-defined criterion.

21. A method according to claim 20, wherein the user-defined criterion is selected from the group comprising:

cost of the journey, speed of the journey;

closeness to user-specified departure time; and

closeness to user-specified arrival time.

22. A system for providing journey information to a user, the system comprising:

input means for receiving unique location reference information identifying the start and end locations of a user-defined journey;

means for considering at least some possible predetermined pairs of access points to a transport network of a single mode of transport, the access points being at different locations than the start and end locations;

selection means for selecting those pairs of access points which minimize a selection factor between the start and end locations and the access points respectively;

requesting means for generating an information request containing a selected pair of access points and sending the request to a knowledge store holding information regarding the single mode of transport;

receiving means for receiving multiple different responses representing different travel options from the knowledge store;

constructing means for constructing a travel option for the user specified journey from the response received from the knowledge store; and

means for providing all the comparative multiple travel options to the user on a single viewing page for ease of comparison and user selection.

23. A method of determining a unique location reference from user-specified location name, the method comprising:

reading a user-specified location name;

interpreting the user-specified location name by finding the closest matches thereto from pre-stored location names having predetermined unique location references associated therewith;

accessing demographic data regarding the closest matches from a geographic/demographic database of the predetermined location references; and

ranking the closest matches in order of the demographic size of each possible match.

24. An integrated journey planner for providing travel information for a user-specified journey;

the journey planner comprising;

means for deconstructing a user enquiry specifying the journey into a plurality of information requests, each specifying a part of the journey using a single mode of transport;

means for sending each request to an appropriate one of a plurality of knowledge stores, each store holding travel information regarding a different mode of transport;

means for reconstructing the responses to the requests received from the plurality of knowledge stores into at least one multi-modal travel option, for the user-specified journey, incorporating different modes of transport;

means for displaying travel options determined by the journey planner to the user; and

means for expanding the travel options provided to the user for the purposes of travel option comparison.

25. An integrated journey planner according to claim 24, wherein the user enquiry includes time information specifying one of the group comprising the desired departure time for the journey and the desired arrival time.

26. An integrated journey planner according to claim 25, wherein the user enquiry includes user preference information for use in ranking or filtering a plurality of multi-modal transport options.

27. An integrated journey planner according to claim 24, wherein the user enquiry includes user preference information for use in ranking or filtering a plurality of multi-modal transport options.

28. An integrated journey planner according to claim 24, wherein the user preference information comprises one of the group comprising fastest journey information, cheapest journey information, most comfortable journey information and most scenic journey information.

29. An integrated journey planner according to claim 24, wherein the user preference information includes preferred modes of transport information.

30. An integrated journey planner according to claim 24, further comprising a user enquiry processing means for understanding and linking the enquiry to associated locally stored data.

31. An integrated journey planner according to claim 24, further comprising an assignment means for assigning pre-stored data to a data record representing the user enquiry, the pre-stored data being associated with the user-specified journey.

32. An integrated journey planner according to claim 31, wherein the assignment means is arranged to assign to the start and end points of the user-specified journey, the closest known access points to a transport network for each mode of transport.

33. An integrated journey planner according to claim 24, wherein the deconstruction means is arranged to estimate, using pre-stored information relating to user-defined start/end time and a geographic subdivision, a start/end time result for any subdivision.

34. An integrated journey planner according to claim 24, wherein the deconstruction means is arranged to create requests specifying that travel information pertaining only to currently available routes is provided for each of the responses.

35. An integrated journey planner according to claim 24, further comprising a road routing engine for searching stored road data representing a road network to return a route best meeting a user defined criteria.

36. An integrated journey planner according to claim 35, wherein the road routing engine is arranged to implement a depth first recursive search for a road route over at least a subdivision of the user-specified journey, and to recursively optimise an initially found route in accordance with user-specified criteria.

37. An integrated journey planner according to claim 36, wherein the user-specified criteria includes minimum journey time.

38. An integrated journey planner according to claim 24, wherein each of the plurality of knowledge stores comprises either timetable and fare information for a service provider or journey time and distance information for a road route.

39. An integrated journey planner according to claim 24, wherein the plurality of knowledge stores are provided on a single data storage device.

40. An integrated journey planner according to claim 24, wherein at least one of the plurality of knowledge stores comprises a remote database accessible via a communications network and the sending means is arranged to transmit some of the requests to this remote database.

41. An integrated journey planner according to claim 40, wherein the communications network comprises the Internet.

42. An integrated journey planner according to claim 24, wherein at least some of the generated responses include travel time information obtained from timetables and the reconstructing means is arranged to accumulate the timetable information for each travel option.

43. An integrated journey planner according to claim 24, wherein at least some of the generated responses to a user enquiry include travel time information not obtained from timetables and the reconstructing means is arranged to accumulate the travel time information for each travel option.

44. An integrated journey planner according to claim 24, wherein the reconstructing means is arranged to accumulate ranking information for each travel option returned from each of the responses.

45. An integrated journey planner according to claim 44, wherein the ranking information accumulated by the reconstructing means includes price information.

46. An integrated journey planner according to claim 44, further comprising means for ranking each of the travel options using the accumulated ranking information and user-selected ranking criteria.

47. A method of determining a route between start and end map locations, the method comprising:

searching a network of nodes, representing road data at a plurality of geographic road locations and neighboring locations, in a recursive manner to establish a route between the nodes representing the start and the end locations; and

traversing the selected route from the end node to the start node in order to optimise the route selection along the route from each intermediate node to the end node,

wherein the traversing/optimising step comprises for each intermediate node calculating a hypothetical route from the start to the end node and comparing it with the selected route, the hypothetical route being identical to the selected route from the start to the current intermediate node and including a partial hypothetical route from the current intermediate node to the end node, the partial hypothetical route being an ideal route maximising a user-defined criterion.

48. A method according to claim 47, wherein the searching step comprises recursing the network of nodes using a depth first recursive technique.

49. A method according to claim 47, wherein the searching step comprises recursing the network of nodes using an exhaustive search technique.

50. A method according to claim 47, wherein the searching step comprises selecting the next neighboring node to be searched on the basis of geographic bearing information between the start and end nodes.

51. A method according to claim 47, wherein the user-defined criterion is fastest road route and the ideal route is an idealised freeway/highway link.

52. A method according to claim 47, wherein the traversing/optimising step comprises pruning a partial route if the comparison shows the hypothetical route to be worse in terms of the user-defined criterion than the selected route and moving the current intermediate node to the next intermediate node in the selected route.

53. A method according to claim 52, wherein the traversing/optimising step comprises searching all neighboring nodes to the current intermediate node and selecting the node with the best route to the end node in terms of the user-defined criterion.

54. A method according to claim 53, wherein the step of searching the neighboring nodes is carried out in order of the degree to which each heads towards the end node.

55. A method according to claim 47, further comprising creating the network of nodes representing road data at a plurality of geographic road locations, each node storing information about its neighboring nodes.

56. A method according to claim 55, wherein the stored information in each node comprises geographic position information and distance of each neighbor information.

57. A method according to claim 56, wherein the stored information in each node further comprises information relating to the type of road connection between each neighbor.

58. A method according to claim 47, further comprising the step of calculating the distance of a traversed/optimised route between the start and end nodes.

59. A method according to claim 47, further comprising the step of calculating the time taken to travel between the start and end nodes using the optimised route.

60. A method according to claim 59, wherein the time calculating step includes using pre-stored speed data relating to the type of road used.

61. A road network routing engine for determining a route between start and end map locations, the routing engine comprising:

a search engine for searching a network of nodes, representing road data at a plurality of geographic road locations and neighboring locations, in a recursive manner to establish a route between the nodes representing the start and the end locations;

optimising means for traversing the selected route from the end node to the start node optimising the route selection along the route from each intermediate node to the end node; and

calculating means for calculating, for each intermediate node, a hypothetical route from the start to the end node and comparing it with the selected route, the hypothetical route being identical to the selected route from the start to the current intermediate node and including a partial hypothetical route from the current intermediate node to the end node, the partial hypothetical route being an ideal route maximising a user-defined criteria.

62. An integrated journey planner for providing travel information for a user-specified journey;

the journey planner comprising;

means for deconstructing a user enquiry specifying the journey into a plurality of information requests, each specifying a part of the journey using a single mode of transport;

means for sending each request to an appropriate one of a plurality of knowledge stores, each store holding travel information regarding a different mode of transport; and

means for reconstructing the responses to the requests received from the plurality of knowledge stores into at least one multi-modal travel option, for the user-specified journey, incorporating different modes of transport, wherein

the deconstruction means is arranged to deconstruct each user enquiry using a recursive subdivision procedure for each possible mode of transport until for each subdivision one of the following group of conditions is met;

the group comprising;

the subdivision relates only to one service provider and one mode of transport;

the subdivision relates to a continuous portion of a road network; and

the mode of transport is not available for the subdivision.

63. An integrated journey planner for providing travel information for a user-specified journey;

the journey planner comprising;

means for deconstructing a user enquiry specifying the journey into a plurality of information requests, each specifying a part of the journey using a single mode of transport;

means for sending each request to an appropriate one of a plurality of knowledge stores, each store holding travel information regarding a different mode of transport, wherein the sending means is arranged to send the requests to different knowledge stores in batches, each batch containing requests with a specified start or end time, the batches being sent sequentially from a user-defined time such that the start or end time results for one batch can be used as the end or start time specifications for the next batch; and

means for reconstructing the responses to the requests received from the plurality of knowledge stores into at least one multi-modal travel option, for the user-specified journey, incorporating different modes of transport.

64. An integrated journey planner for providing travel information for a user-specified journey, the journey planner comprising:

means for deconstructing a user enquiry specifying the journey into a plurality of information requests, each specifying a part of the journey using a single mode of transport;

means for sending each request to an appropriate one of a plurality of knowledge stores, each store holding travel information regarding a different mode of transport;

means for reconstructing the responses to the requests received from the plurality of knowledge stores into at least one multi-modal travel option, for the user-specified journey, incorporating different modes of transport;

means for displaying travel options determined by the journey planner to the user;

means for expanding the travel option details provided to the user for the purposes of travel option comparison;

means for selecting one of the displayed travel options, and booking means receptive to the selecting means for carrying out on-line booking of any of the selected modes of transport requiring ticket purchasing; and

means for obtaining information related to the selected travel option, the obtaining means being arranged to retrieve the desired information over a communications network.

65. An integrated journey planner according to claim 64, wherein the information includes one of the group comprising:

weather reports; and

city guides.

66. An integrated journey planner for providing travel information for a user-specified journey;

the journey planner comprising;

means for deconstructing a user enquiry specifying the journey into a plurality of information requests, each specifying a part of the journey using a single mode of transport;

means for sending each request to an appropriate one of a plurality of knowledge stores, each stare holding travel information regarding a different mode of transport;

means for reconstructing the responses to the requests received from the plurality of knowledge stores into at least one multi-modal travel option, for the user-specified journey, incorporating different modes of transport;

a user enquiry processing means for understanding and linking the enquiry to associated locally stored data, wherein the processing means comprises a name resolver arranged to interpret the user-specified journey by finding the closest match of pre-stored data to the user-specified journey, and is arranged to use artificial intelligence to determine its acceptance.

67. An integrated journey planner according to claim 66, wherein the name resolver is arranged to provide a list of closest matches for user selection if the user-specified journey is sufficiently different from the closest matching pre-stored data.

68. An integrated journey planner for providing travel information for a user-specified journey;

the journey planner comprising;

means for deconstructing a user enquiry specifying the journey into a plurality of information requests, each specifying a part of the journey using a single mode of transport;

means for sending each request to an appropriate one of a plurality of knowledge stores, each store holding travel information regarding a different mode of transport; and

means for reconstructing the responses to the requests received from the plurality of knowledge stores into at least one multi-modal travel option, for the user-specified journey, incorporating different modes of transport,

wherein the deconstruction means is arranged to deconstruct each user enquiry using a recursive subdivision procedure for each possible mode of transport until for each subdivision one of the following group of conditions is met, the group comprising;

the subdivision relates only to one mode of transport; and

the mode of transport is not available for the subdivision.

69. An integrated journey planner according to claim 68, wherein the deconstruction means is arranged to stop the recursive subdivision when for each subdivision one of the following group of conditions is met, the group comprising:

the subdivision relates only to one service provider and one mode of transport;

the subdivision relates to a continuous portion of a road network; and

the mode of transport is not available for the subdivision.

70. An integrated journey planner according to claim 68, wherein the deconstruction means is arranged to carry out each subdivision step of the recursive procedure using pre-stored data associated with the user-specified journey or a newly created subdivision.

71. An integrated journey planner for providing travel information for a user-specified journey;

the journey planner comprising;

means for deconstructing a user enquiry specifying the journey into a plurality of information requests, each specifying a part of the journey using a single mode of transport;

means for sending each request to an appropriate one of a plurality of knowledge stores, each store holding travel information regarding a different mode of transport; and

means for reconstructing the responses to the requests received from the plurality of knowledge stores into at least one multi-modal travel option, for the user-specified journey, incorporating different modes of transport,

wherein the sending means is arranged to send the requests to the different knowledge stores in batches, each batch containing requests with a specified start or end time.

72. An integrated journey planner according to claim 71, wherein the batches are sent sequentially from a user-defined time such that the start or end time results for one batch can be used as the end or start time specifications for the next batch.

73. An integrated journey planner according to claim 71, wherein within each batch, a plurality of requests are sent in parallel to the knowledge stores.

74. An integrated journey planner for providing travel information for a user-specified journey;

the journey planner comprising;

means for deconstructing a user enquiry specifying the journey into a plurality of information requests, each specifying a part of the journey using a single mode of transport;

means for sending each request to an appropriate one of a plurality of knowledge stores, each store holding travel information regarding a different mode of transport; and

means for reconstructing the responses to the requests received from the plurality of knowledge stores into at least one multi-modal travel option, for the user-specified journey, incorporating different modes of transport,

wherein the reconstructing means is arranged to reconstruct the received responses into a plurality of multi-modal travel options over the user-specified journey, each travel option using a plurality of different modes of transport.

75. An integrated journey planner according to claim 74, wherein the reconstructing means is arranged recursively to combine together each of the received responses until all possible travel options corresponding graphically to the user-specified journey are assembled.

76. An integrated journey planner for providing travel information for a user-specified journey;

the journey planner comprising;

means for deconstructing a user enquiry specifying the journey into a plurality of information requests, each specifying a part of the journey using a single mode of transport;

means for sending each request to an appropriate one of a plurality of knowledge stores, each store holding travel information regarding a different mode of transport; and

means for reconstructing the responses to the requests received from the plurality of knowledge stores into at least one multi-modal travel option, for the user-specified journey, incorporating different modes of transport,

wherein the reconstructing means is arranged recursively to combine together each of the received responses until all possible travel options corresponding geographically to the user-specified journey are assembled.

77. An integrated journey planner for providing travel information for a user-specified journey;

the journey planner comprising;

means for deconstructing a user enquiry specifying the journey into a plurality of information requests, each specifying a part of the journey using a single mode of transport;

means for sending each request to an appropriate one of a plurality of knowledge stores, each store holding travel information regarding a different mode of transport;

means for reconstructing the responses to the requests received from the plurality of knowledge stores into at least one multi-modal travel option, for the user-specified journey, incorporating different modes of transport;

means for displaying travel options determined by the journey planner to the user; and

means for selecting one of the displayed travel options, and booking means receptive to the selecting means for carrying out on-line booking of any of the selected modes of transport requiring ticket purchasing.

78. An integrated journey planner according to claim 77, further comprising means for obtaining information related to the selected travel option, the obtaining means being arranged to retrieve the desired information over a communications network.

79. An integrated journey planner according to claim 77, wherein the information includes one of the group comprising:

weather reports; and

city guides.

80. A method of providing journey information to a user, the method comprising:

receiving unique location reference information identifying the start and end locations of a user-defined journey;

considering at least some possible predetermined pairs of access points to a transport network of a single mode of transport, the access points being at different locations than the start and end locations;

selecting those pairs of access points which minimize a selection factor between the start and end locations and the access points respectively;

generating an information request containing a selected pair of access points and sending the request to a knowledge store holding information regarding the single mode of transport;

constructing a travel option for the user-specified journey from the response received from the knowledge store;

determining the unique location reference information from user-specified start and end location names,

wherein the determining step comprises interpreting the user-entered location names by finding the closest matches to pre-stored location names having predetermined unique location references for use with the receiving step, and using artificial intelligence to determine acceptance of the closest matching pre-stored location names to the user-entered names.

81. A computer-readable medium/electrical carrier signal encoded with a program for causing a computer to perform the method of claim 80.

82. A method of providing journey information to a user, the method comprising:

receiving unique location reference information identifying the start and end locations of a user-defined journey;

considering at least some possible predetermined pairs of access points to a transport network of a single mode of transport, the access points being at different locations than the start and end locations;

selecting those pairs of access points which minimize a selection factor between the start and end locations and the access points respectively;

generating an information request containing a selected pair of access points and sending the request to a knowledge store holding information regarding the single mode of transport;

constructing a travel option for the user-specified journey from the response received from the knowledge store;

determining the unique location reference information from a user-specified location name and from an automatic current location of user determining procedure;

interpreting a user-entered location name by finding the closest match to pre-stored location names having predetermined location co-ordinates for use with the receiving step; and

using artificial intelligence to determine acceptance of the closest matching pre-stored location names to the user-entered location name.