Incremental search based multi-modal journey planning

Patent metadata

Field	Value
Publication number	US-11599958-B2
Application number	US-202117464986-A
Country	US
Kind code	B2
Filing date	Sep 2, 2021
Priority date	Aug 31, 2015
Publication date	Mar 7, 2023
Grant date	Mar 7, 2023

Abstract

A method incrementally solves a current journey planning request from a user. The solving step performs a current search for at least one journey plan that satisfies the request by accessing a database storing journey planning information derived from results to a plurality of previous requests. The solving step stores, in the database, information discovered during the current search for responding to a subsequent request. The information discovered during the current search for responding to the request includes a reusable portion of a search graph, pairs of a state and a lower bound on a best arrival time and pairs of a state and an exact value for the arrival time. The lower bound is employed to increase an accuracy of a pre-computer heuristic function which guides the search based on state dominance in search spaces in which heuristic values are back propagated and stored in the database.

First claim

What is claimed is:

1. A method, comprising:
incrementally solving, by a processor-based journey plan incremental searcher, a current journey planning request from a user, wherein said solving step includes:
performing a current search for at least one journey plan that satisfies the current journey planning request by accessing a database storing journey planning information derived from results to a plurality of previous journey planning requests;
storing, in the database, at least part of the information discovered during the current search for responding to a subsequent journey planning request; and
providing, on a display device, the at least one journey plan to the user,

wherein the at least part of the information discovered during the current search for responding to the subsequent journey planning request includes a reusable portion of a search graph, pairs of a state and a lower bound on a best arrival time and pairs of a state and an exact value for the arrival time, the lower bound employed to increase an accuracy of a pre-computer heuristic function which guides the search based on state dominance in one or more search spaces in which heuristic values are back propagated and stored in the database.

2. The method of claim 1 , wherein the database includes a cache, and wherein results stored for the current journey planning request or a previous journey planning request include a reusable portion, the reusable portion being stored in the cache.

3. The method of claim 1 , wherein the database includes a cache, and wherein results stored for a previous journey planning request include a reusable portion stored in the cache, and wherein the at least one journey plan for the current journey planning request is computed while utilizing the reusable portion stored in the cache.

4. The method of claim 1 , wherein transportation links corresponding to the at least one journey plan are time dependent, and multiple constraints are imposed on the at least one journey plan that include minimizing a travel time and minimizing transportation mode changes.

5. The method of claim 1 , wherein the current search is performed over at least one search space having a plurality of states, each of the plurality of states having a respective temporal component.

6. The method of claim 5 , wherein at least one of the plurality of states includes respective maximum thresholds for interchanges, a walking time, and a cycling time.

7. The method of claim 1 , wherein results stored for the current journey planning request or a previous journey planning request include a reusable portion of a search graph, the reusable portion including at least one of a cost-to-goal estimation and an actual journey plan from a subset of states to a goal.

8. The method of claim 1 , wherein results stored for a given state in a search space can be transferred to one or more other states in the search space or in another search space, based on dominance and commonality relations.

9. The method of claim 1 , wherein the at least part of the information stored in the database comprises an information pair that includes a state of a search space and a lower bound on an arrival time.

10. The method of claim 1 , wherein the at least part of the information stored in the database comprises an information pair that includes a state of a search space and an exact value of an arrival time.

11. The method of claim 1 , wherein performing the current search for the at least one journey plan comprises guiding the search using a heuristic function.

12. The method of claim 11 , wherein the heuristic function is used to estimate a travel time from a state of a search space to a given location.

13. The method of claim 12 , wherein the given location is specified in the current journey planning request, and wherein the state of the search space includes a location that is unspecified in, but implicated by, the current journey planning request.

14. The method of claim 11 , further comprising updating the heuristic function based on state dominance of states in one or more search spaces.

15. The method of claim 11 , further comprising performing a back propagation technique that propagates heuristic values through a search graph space commencing at an end state of a graph search space or subgraph search space and traversing in a direction from end-to-beginning.

16. The method of claim 1 , further comprising pruning a search space having a plurality of states using state dominance.

17. The method of claim 1 , further comprising incrementally building the database at least from results of the plurality of previous journey planning requests.

18. A non-transitory article of manufacture tangibly embodying a computer readable program which when executed causes a computer to perform the steps of claim 1 .

19. A system, comprising:
a processor-based journey planning incremental searcher for incrementally solving a current journey planning request from a user, wherein said journey planning incremental searcher incremental solves the journey planning request from the user by:
incrementally solving a current journey planning request from a user, wherein said solving step includes:
performing a current search for at least one journey plan that satisfies the current journey planning request by accessing a database storing journey planning information derived from results to a plurality of previous journey planning requests;
storing, in the database, at least part of the information discovered during the current search for responding to a subsequent journey planning request; and
providing, on a display device, the at least one journey plan to the user,

wherein the at least part of the information discovered during the current search for responding to the subsequent journey planning request includes a reusable portion of a search graph, pairs of a state and a lower bound on a best arrival time and pairs of a state and an exact value for the arrival time, the lower bound employed to increase an accuracy of a pre-computer heuristic function which guides the search based on state dominance in one or more search spaces in which heuristic values are back propagated and stored in the database.

20. The system of claim 19 , wherein the processor-based journey planning incremental searcher guides the current search using a heuristic function, and performs a back propagation technique that propagates heuristic values through a search graph space commencing at an end state of a graph search space or subgraph search space and traversing in a direction from end-to-beginning.

Assignees

• IBM

Inventors

• Botea Adi
• Daly Elizabeth
• Kishimoto Akihiro

Classifications

• G06Q50/14 Primary

  Travel agencies · CPC title

• G06Q10/047

  Optimisation of routes or paths, e.g. travelling salesman problem · CPC title