IP Library › Granted Patent US 12,264,921
Granted Patent B2
US 12,264,921 · App. 16/830,609 · Granted Apr 1, 2025

Method for preprocessing a set of feasible transfers for computing itineraries in a multimodal transportation network

Inventors: Vassilissa Lehoux-Lebacque (Corenc, FR); Darko Drakulic (Grenoble, FR)
Assignee: Naver Corporation
G01C21/3423G01C21/343G01C21/3446G01C21/3453G06Q10/047G06Q50/14
View Patent ↗
Loading inventors, assignments & file history…
Monitor This Case
Get email alerts when status or documents change.
Order Certified Copies
Most orders are placed with the USPTO same day — all within 24 business hours.
Order via The Patent Place →
Pre-filled with this patent's details
Quick Facts
Patent No.
US 12,264,921
App. No.
16/830,609
Granted
Apr 1, 2025
Kind
B2
Abstract

A method for preprocessing a set of feasible transfers within a multimodal transportation network of predetermined stations, comprising, for each trip in the multimodal transportation network hereafter called origin trip: (a) for each station (p t i ) of the origin trip (t), computing at this station (p t i ) an earliest arrival/change time associated with all transportation modes (m) of the multimodal transportation network; (b) for at least one transfer of the set of feasible transfers from a station (p t i ) on the origin trip (t) to a reachable station (p u j ) on a target trip (u), computing, at each station (p u k>j ) of the target trip (u) after the reachable station (p u j ), a value of the earliest arrival/change time specifically associated with the transportation mode (m u ) of the multimodal transportation network used by the target trip (u); (c) removing the transfer only if determining that each computed value of the earliest arrival/change time is not improved by the transfer; (d) outputting the set of feasible transfers for computing at least one itinerary in the multimodal transportation network; and (e) performing a routing optimization algorithm so as to build, among the itineraries having a main part from an initial trip belonging to the set of possible initial trips to a final trip belonging to the set of possible final trips, at least one optimal itinerary according to the earliest arrival time and the number of transfers or the latest departure time and the number of transfers, when considering only trips from the set of possible trips using the selected transportation modes, and only transfers from the subset of feasible transfers between considered trips.

Claims (74)

1. A method for electronically computing an itinerary from a departure location to an arrival location for use by a user to plan a trip travelling in a multimodal transportation network, the itinerary being defined as the departure location to an initial station of a multimodal transportation network of predetermined stations, a main part in the multimodal transportation network, a sequence of trips from a set of possible trips within the multimodal transportation network and transfers from a set of feasible transfers within the multimodal transportation network, and a final station of the multimodal transportation network to the arrival location, the method comprising:

(a) electronically preprocessing the set of feasible transfers to obtain a subset of feasible transfers;

said (a) electronically preprocessing the set of feasible transfers by

(a1) for each station (p t i ) of the origin trip (t), electronically computing, using an electronic processor and electronic memory, at this station (p t i ) a value of an earliest arrival time (τ A (p t i , m)) or an earliest change time (τ C (p t i , m)) associated with all transportation modes (m) of the multimodal transportation network,

(a2) for at least one transfer (p t i →p u j ) of the set of feasible transfers from a station (p t i ) on an origin trip (t) to a reachable station (p u j ) on a target trip (u), electronically computing, using an electronic processor and electronic memory, at each station (p u k>j ) of the target trip (u) after the reachable station (p u j ), a value of the earliest arrival time (τ A (p u k>j , m u ) or the earliest change time (τ C (p u k>j , m)) specifically associated with the transportation mode (m u ) of the multimodal transportation network used by the target trip (u), or if the transportation mode (m u ) of the multimodal transportation network used by the target trip (u) is the same as the transportation mode (m t ) of the multimodal transportation network used by the origin trip (t), a value of the earliest arrival time (τ A (p u k>j , m)) or the earliest change time (τ C (p u k>j , m)) associated with all transportation modes (m) of the multimodal transportation network,

(a3) electronically removing, using an electronic processor and electronic memory, before receiving information corresponding to a user's desired mode of transportation, the transfer (p t i →p u j ) from the set of feasible transfers only if determining that each computed value of the earliest arrival time (τ A (p u k>j , m)) or the earliest change time (τ C (p u k>j , m)) is not improved by the transfer (p t i →p u j ) and the transfer (p t i →p u j ) is not of a different mode of transportation, thereby preventing a transfer corresponding to a different mode of transportation from being removed from the set of feasible transfers and increasing effectiveness of computing an optimal itinerary consistent with the user's desired mode of transportation, and

(a4) electronically outputting, using an electronic processor and electronic memory, the set of feasible transfers for computing at least one itinerary in the multimodal transportation network, the set of feasible transfers including transfers of all possible modes of transportation;

(b) receiving, after electronically preprocessing the set of feasible transfers, from a user, via a user interface, information corresponding to the user's desired mode of transportation;

(c) electronically determining, using an electronic processor and electronic memory, based upon the set of feasible transfers and the user's desired mode of transportation, a set of possible trips in a multimodal transportation network;

(d) electronically performing, using an electronic processor and electronic memory, a routing optimization algorithm so as to build at least one optimal itinerary, without losing an optimal itinerary corresponding to the user's desired mode of transportation, according to at least one criterion including an earliest arrival time, based upon the set of possible trips in the multimodal transportation network, the routing optimization algorithm electronically computing, using an electronic processor and electronic memory, a Pareto front; and

(e) outputting to the user, via the user interface, the at least one optimal itinerary for use by the user to plan a trip travelling in the multimodal transportation network.

2. The method according to claim 1 , further comprising electronically initializing, using an electronic processor and electronic memory, the earliest arrival time or the earliest change time as a function of schedules.

3. The method according to claim 1 , wherein the value of the earliest arrival time or the earliest change time specifically associated with a transportation mode (m u ) of the multimodal transportation network corresponds to the earliest arrival time or the earliest change time when using only the transportation mode (m u ) or the transportation mode (m t ) of the multimodal transportation network used by the origin trip (t).

4. The method according to claim 2 , wherein the value of the earliest arrival time or the earliest change time specifically associated with a transportation mode (m u ) of the multimodal transportation network corresponds to the earliest arrival time or the earliest change time when using only the transportation mode (m u ) or the transportation mode (m t ) of the multimodal transportation network used by the origin trip (t).

5. The method according to claim 1 , further comprising electronically performing (c) and (d), using an electronic processor and electronic memory, iteratively for each transfer of the set of feasible transfers which is the earliest transfer from a station on the origin trip to any reachable station on any target trip.

6. The method according to claim 2 , further comprising electronically performing (c) and (d), using an electronic processor and electronic memory, iteratively for each transfer of the set of feasible transfers which is the earliest transfer from a station on the origin trip to any reachable station on any target trip.

7. The method according to claim 3 , further comprising electronically performing (c) and (d), using an electronic processor and electronic memory, iteratively for each transfer of the set of feasible transfers which is the earliest transfer from a station on the origin trip to any reachable station on any target trip.

8. The method according to claim 4 , further comprising electronically performing (c) and (d), using an electronic processor and electronic memory, iteratively for each transfer of the set of feasible transfers which is the earliest transfer from a station on the origin trip to any reachable station on any target trip.

9. The method according to claim 5 , further comprising electronically iteratively considering), using an electronic processor and electronic memory, the transfers from each successive station of the origin trip when travelling the stations on the origin trip from a final station to an initial station.

10. The method according to claim 6 , further comprising electronically iteratively considering), using an electronic processor and electronic memory, the transfers from each successive station of the origin trip when travelling the stations on the origin trip from a final station to an initial station.

11. The method according to claim 7 , further comprising by electronically iteratively considering), using an electronic processor and electronic memory, the transfers from each successive station of the origin trip when travelling the stations on the origin trip from a final station to an initial station.

12. The method according to claim 8 , further comprising electronically iteratively considering), using an electronic processor and electronic memory, the transfers from each successive station of the origin trip when travelling the stations on the origin trip from a final station to an initial station.

13. The method according to claim 1 , wherein the earliest arrival time and/or the earliest change time is also computed at each neighboring station of each station on the origin trip and on the target trip after said reachable station.

14. The method according to claim 2 , wherein the earliest arrival time and/or the earliest change time is also computed at each neighboring station of each station on the origin trip and on the target trip after said reachable station.

15. The method according to claim 3 , wherein the earliest arrival time and/or the earliest change time is also computed at each neighboring station of each station on the origin trip and on the target trip after said reachable station.

16. The method according to claim 4 , wherein the earliest arrival time and/or the earliest change time is also computed at each neighboring station of each station on the origin trip and on the target trip after said reachable station.

17. The method according to claim 5 , wherein the earliest arrival time and/or the earliest change time is also computed at each neighboring station of each station on the origin trip and on the target trip after said reachable station.

18. The method according to claim 6 , wherein the earliest arrival time and/or the earliest change time is also computed at each neighboring station of each station on the origin trip and on the target trip after said reachable station.

19. The method according to claim 7 , wherein the earliest arrival time and/or the earliest change time is also computed at each neighboring station of each station on the origin trip and on the target trip after said reachable station.

20. The method according to claim 8 , wherein the earliest arrival time and/or the earliest change time is also computed at each neighboring station of each station on the origin trip and on the target trip after said reachable station.

21. The method according to claim 9 , wherein the earliest arrival time and/or the earliest change time is also computed at each neighboring station of each station on the origin trip and on the target trip after said reachable station.

22. The method according to claim 10 , wherein the earliest arrival time and/or the earliest change time is also computed at each neighboring station of each station on the origin trip and on the target trip after said reachable station.

23. The method according to claim 11 , wherein the earliest arrival time and/or the earliest change time is also computed at each neighboring station of each station on the origin trip and on the target trip after said reachable station.

24. The method according to claim 12 , wherein the earliest arrival time and/or the earliest change time is also computed at each neighboring station of each station on the origin trip and on the target trip after said reachable station.

25. The method according to claim 1 , wherein the routing optimization algorithm computes at least one optimal solution per element in the Pareto front for the earliest arrival time and number of transfers or latest departure time and number of transfers in multimodal networks by taking one additional trip of the set of the selected modes at each iteration based on the precomputed transfer set.

26. A method for electronically computing an itinerary from a departure location to an arrival location for use by a user to plan a trip travelling in a multimodal transportation network, the itinerary being defined as the departure location to an initial station of a multimodal transportation network of predetermined stations, a main part in the multimodal transportation network, a sequence of trips from a set of possible trips within the multimodal transportation network and transfers from a set of feasible transfers within the multimodal transportation network, and a final station of the multimodal transportation network to the arrival location, the method comprising:

(a) electronically preprocessing the set of feasible transfers by removing, using an electronic processor and electronic memory, before receiving information corresponding to a user's desired mode of transportation, a transfer from the set of feasible transfers only if determining that each computed value of an earliest arrival time or an earliest change time is not improved by the transfer and the transfer is not of a different mode of transportation, thereby preventing a transfer corresponding to a different mode of transportation from being removed from the set of feasible transfers and increasing effectiveness of computing an optimal itinerary consistent with the user's desired mode of transportation;

(b) electronically outputting, using an electronic processor and electronic memory, the preprocessed set of feasible transfers for computing at least one itinerary in the multimodal transportation network;

(c) receiving, after electronically preprocessing the set of feasible transfers, from a user, via a user interface, information corresponding to a user's desired mode of transportation;

(d) electronically determining, using an electronic processor and electronic memory, based upon the preprocessed set of feasible transfers and the user's desired mode of transportation, a set of possible trips in a multimodal transportation network;

(e) electronically performing, using an electronic processor and electronic memory, a routing optimization algorithm so as to build at least one optimal itinerary, without losing an optimal itinerary corresponding to the user's desired mode of transportation, according to at least one criterion including an earliest arrival time, based upon the set of possible trips in the multimodal transportation network, the routing optimization algorithm electronically computing, using an electronic processor and electronic memory, a Pareto front; and

(f) outputting to the user, via the user interface, the at least one optimal itinerary for use by the user to plan a trip travelling in the multimodal transportation network.

27. The method according to claim 26 , wherein the routing optimization algorithm computes at least one optimal solution with this value per element in the Pareto front for the earliest arrival time and number of transfers or latest departure time and number of transfers in multimodal networks by taking one additional trip of the set of the selected modes at each iteration based on the precomputed transfer set.

28. A computer program product for electronically computing an itinerary from a departure location to an arrival location for use by a user to plan a trip travelling in a multimodal transportation network, the itinerary being defined as the departure location to an initial station of a multimodal transportation network of predetermined stations, a main part in the multimodal transportation network, a sequence of trips from a set of possible trips within the multimodal transportation network and transfers from a set of feasible transfers within the multimodal transportation network, and a final station of the multimodal transportation network to the arrival location, the computer program product being executed on a computer to perform a process, the process comprising:

(a) electronically preprocessing the set of feasible transfers to obtain a subset of feasible transfers;

said (a) electronically preprocessing the set of feasible transfers by

(a1) for each station (p t i ) of the origin trip (t), electronically computing, using the computer, at this station (p t i ) a value of an earliest arrival time (τ A (p t i , m)) or an earliest change time (τ C (p t i , m)) associated with all transportation modes (m) of the multimodal transportation network,

(a2) for at least one transfer (p t i →p u j ) of the set of feasible transfers from a station (p t i ) on an origin trip (t) to a reachable station (p u j ) on a target trip (u), electronically computing, using the computer, at each station (p u k>j ) of the target trip (u) after the reachable station (p u j ), a value of the earliest arrival time (τ A (p u k>j , m u )) or the earliest change time (τ C (p u k>j , m u )) specifically associated with the transportation mode (m u ) of the multimodal transportation network used by the target trip (u), or if the transportation mode (m u ) of the multimodal transportation network used by the target trip (u) is the same as the transportation mode (m t ) of the multimodal transportation network used by the origin trip (t), a value of the earliest arrival time (τ A (p u k>j , m)) or the earliest change time (τ C (p u k>j , m)) associated with all transportation modes (m) of the multimodal transportation network,

(a3) electronically removing, using the computer, before receiving information corresponding to a user's desired mode of transportation, the transfer (p t i →p u j ) from the set of feasible transfers only if determining that each computed value of the earliest arrival time (τ A (p u k>j , m)) or the earliest change time (τ C (p u k>j , m)) is not improved by the transfer (p t i →p u j ) and the transfer (p t i →p u j ) is not of a different mode of transportation, thereby preventing a transfer corresponding to a different mode of transportation from being removed from the set of feasible transfers and increasing effectiveness of computing an optimal itinerary consistent with the user's desired mode of transportation, and

(a4) electronically outputting, using the computer, the set of feasible transfers for computing at least one itinerary in the multimodal transportation network, the set of feasible transfers including transfers of all possible modes of transportation;

(b) receiving, after electronically preprocessing the set of feasible transfers, from a user, via a user interface, information corresponding to the user's desired mode of transportation;

(c) electronically determining, using the computer, based upon the set of feasible transfers and the user's desired mode of transportation, a set of possible trips in a multimodal transportation network;

(d) electronically performing, using the computer, a routing optimization algorithm so as to build at least one optimal itinerary, without losing an optimal itinerary corresponding to the user's desired mode of transportation, according to at least one criterion including an earliest arrival time, based upon the set of possible trips in the multimodal transportation network, the routing optimization algorithm electronically computing, using an electronic processor and electronic memory, a Pareto front; and

(e) outputting to the user, via the user interface, the at least one optimal itinerary for use by the user to plan a trip travelling in the multimodal transportation network.

29. The computer program product according to claim 28 , wherein the process further comprises initializing, using the computer, the earliest arrival time or the earliest change time as a function of schedules.

30. The computer program product according to claim 29 , wherein the value of the earliest arrival time or the earliest change time specifically associated with a transportation mode (m u ) of the multimodal transportation network corresponds to the earliest arrival time or the earliest change time when using only the transportation mode (m u ) or the transportation mode (m t ) of the multimodal transportation network used by the origin trip (t).

31. The computer program product according to claim 28 , wherein (c) and (d), using the computer, are iteratively performed for each transfer of the set of feasible transfers which is the earliest transfer from a station on the origin trip to any reachable station on any target trip.

32. The computer program product according to claim 29 , wherein (c) and (d), using the computer, are iteratively performed for each transfer of the set of feasible transfers which is the earliest transfer from a station on the origin trip to any reachable station on any target trip.

33. The computer program product according to claim 30 , wherein the earliest arrival time and/or the earliest change time is also computed at each neighboring station of each station on the origin trip and on the target trip after said reachable station.

34. The computer program product according to claim 28 , wherein the routing optimization algorithm computes at least one optimal solution per element in the Pareto front for the earliest arrival time and number of transfers or latest departure time and number of transfers in multimodal networks by taking one additional trip of the set of the selected modes at each iteration based on the precomputed transfer set.

35. The computer program product according to claim 28 , wherein the computer program product is a computer-readable medium.

36. A computer program product for electronically computing an itinerary from a departure location to an arrival location for use by a user to plan a trip travelling in a multimodal transportation network, the itinerary being defined as the departure location to an initial station of a multimodal transportation network of predetermined stations, a main part in the multimodal transportation network, a sequence of trips from a set of possible trips within the multimodal transportation network and transfers from a set of feasible transfers within the multimodal transportation network, and a final station of the multimodal transportation network to the arrival location, the computer program product being executed on a computer to perform a process, the process comprising:

(a) electronically preprocessing the set of feasible transfers by removing, using the computer, before receiving information corresponding to a user's desired mode of transportation, a transfer from the set of feasible transfers only if determining that each computed value of an earliest arrival time or an earliest change time is not improved by the transfer and the transfer is not of a different mode of transportation, thereby preventing a transfer corresponding to a different mode of transportation from being removed from the set of feasible transfers and increasing effectiveness of computing an optimal itinerary consistent with the user's desired mode of transportation;

(b) electronically outputting, using the computer, the preprocessed set of feasible transfers for computing at least one itinerary in the multimodal transportation network;

(c) receiving, after electronically preprocessing the set of feasible transfers, from a user, via a user interface, information corresponding to a user's desired mode of transportation;

(d) electronically determining, using the computer, based upon the preprocessed set of feasible transfers and the user's desired mode of transportation, a set of possible trips in a multimodal transportation network;

(e) electronically performing, using the computer, a routing optimization algorithm so as to build at least one optimal itinerary, without losing an optimal itinerary corresponding to the user's desired mode of transportation, according to at least one criterion including an earliest arrival time, based upon the set of possible trips in the multimodal transportation network, the routing optimization algorithm electronically computing, using an electronic processor and electronic memory, a Pareto front; and

(f) outputting to the user, via the user interface, the at least one optimal itinerary for use by the user to plan a trip travelling in the multimodal transportation network.

37. The computer program product according to claim 36 , wherein the routing optimization algorithm computes at least one solution with this value per element in the Pareto front for the earliest arrival time and number of transfers or latest departure time and number of transfers in multimodal networks by taking one additional trip of the set of the selected modes at each iteration based on the precomputed transfer set.

38. The computer program product according to claim 36 , wherein the computer program product is a computer-readable medium.

39. The method according to claim 1 , wherein, for the set of possible trips in the multimodal transportation network, the at least one optimal itinerary directing the user, via the user interface, to stations of the multimodal transportation network based upon the user's desired mode of transportation, wherein the at least one optimal itinerary starts with an initial trip from an initial station which is defined as an entry point of the multimodal transportation network, and ends with a final trip on a target line up to a station which is defined as an exit point of the multimodal transportation network.

40. The method according to claim 26 , wherein, for the set of possible trips in the multimodal transportation network, the at least one optimal itinerary directing the user, via the user interface, to stations of the multimodal transportation network based upon the user's desired mode of transportation, wherein the at least one optimal itinerary starts with an initial trip from an initial station which is defined as an entry point of the multimodal transportation network, and ends with a final trip on a target line up to a station which is defined as an exit point of the multimodal transportation network.

41. The computer program product according to claim 28 , wherein, for the set of possible trips in the multimodal transportation network, the at least one optimal itinerary directing the user, via the user interface, to stations of the multimodal transportation network based upon the user's desired mode of transportation, wherein the at least one optimal itinerary starts with an initial trip from an initial station which is defined as an entry point of the multimodal transportation network, and ends with a final trip on a target line up to a station which is defined as an exit point of the multimodal transportation network.

42. The computer program product according to claim 36 , wherein, for the set of possible trips in the multimodal transportation network, the at least one optimal itinerary directing the user, via the user interface, to stations of the multimodal transportation network based upon the user's desired mode of transportation, wherein the at least one optimal itinerary starts with an initial trip from an initial station which is defined as an entry point of the multimodal transportation network, and ends with a final trip on a target line up to a station which is defined as an exit point of the multimodal transportation network.

Assignments (1)
ASSIGNMENT OF ASSIGNOR'S INTEREST Recorded Mar 27, 2020
From: LEHOUX-LEBACQUE, VASSILISSA; DRAKULIC, DARKO
To: NAVER CORPORATION
Reel/Frame 052241/0936 →
Priority Claims (1)
EP 19305687 · May 29, 2019 · regional
Continuity (1)
Related Publication 20200378772A1 · Dec 3, 2020
References Cited (137)
US 5991688A · Fukushima et al. · 1999 [cited by applicant]
US 6779060B1 · Azvine et al. · 2004 [cited by applicant]
US 6785608B1 · Milici et al. · 2004 [cited by applicant]
US 8005610B2 · Bast et al. · 2011 [cited by applicant]
US 8335643B2 · Vandivier et al. · 2012 [cited by applicant]
US 8417409B2 · Bast · 2013 [cited by examiner]
US 8494771B2 · Delling · 2013 [cited by examiner]
US 8504034B2 · Miyake et al. · 2013 [cited by applicant]
US 8786605B1 · Curtis et al. · 2014 [cited by applicant]
US 9082134B2 · Gishen · 2015 [cited by applicant]
US 10036647B2 · Barraci · 2018 [cited by examiner]
US 10436597B1 · Faaborg · 2019 [cited by examiner]
US 20020059025A1 · Kim et al. · 2002 [cited by applicant]
US 20030109266A1 · Rafiah et al. · 2003 [cited by applicant]
US 20040218536A1 · Yasukawa et al. · 2004 [cited by applicant]
US 20050043884A1 · Atarashi · 2005 [cited by applicant]
US 20070008949A1 · Balandin · 2007 [cited by applicant]
US 20080075007A1 · Mehta et al. · 2008 [cited by applicant]
US 20100036606A1 · Jones · 2010 [cited by applicant]
US 20100082245A1 · Patenaude et al. · 2010 [cited by applicant]
US 20100153004A1 · Natsume · 2010 [cited by examiner]
US 20100228574A1 · Mundinger et al. · 2010 [cited by applicant]
US 20100280748A1 · Mundinger et al. · 2010 [cited by applicant]
US 20100280853A1 · Petralia et al. · 2010 [cited by applicant]
US 20100305984A1 · Ben-Yitschak et al. · 2010 [cited by applicant]
US 20110112759A1 · Bast et al. · 2011 [cited by applicant]
US 20110125666A1 · Laurent et al. · 2011 [cited by applicant]
US 20110302214A1 · Frye et al. · 2011 [cited by applicant]
US 20120008536A1 · Borghei · 2012 [cited by applicant]
US 20120253657A1 · Francis · 2012 [cited by applicant]
US 20130060468A1 · Delling · 2013 [cited by examiner]
US 20130245940A1 · Shinagawa et al. · 2013 [cited by applicant]
US 20130261967A1 · Shinagawa et al. · 2013 [cited by applicant]
US 20130262222A1 · Gibson et al. · 2013 [cited by applicant]
US 20130304378A1 · Graells · 2013 [cited by examiner]
US 20140200807A1 · Geisberger · 2014 [cited by applicant]
US 20140257697A1 · Gishen · 2014 [cited by applicant]
US 20140278086A1 · San Filippo et al. · 2014 [cited by applicant]
US 20140343974A1 · Graells · 2014 [cited by examiner]
US 20150095355A1 · Patton · 2015 [cited by applicant]
US 20150356759A1 · Delling et al. · 2015 [cited by applicant]
US 20150371157A1 · Jaffe · 2015 [cited by applicant]
US 20160033283A1 · Ulloa Paredes · 2016 [cited by examiner]
US 20160203422A1 · Demarchi · 2016 [cited by examiner]
US 20170074669A1 · Newlin · 2017 [cited by examiner]
US 20170123421A1 · Kentley et al. · 2017 [cited by applicant]
US 20180038706A1 · Ellenby et al. · 2018 [cited by applicant]
US 20180102985A1 · Byers et al. · 2018 [cited by applicant]
US 20190057340A1 · Wang · 2019 [cited by applicant]
US 20190130350A1 · Nguyen et al. · 2019 [cited by applicant]
US 20190383621A1 · Isaacs et al. · 2019 [cited by applicant]
US 20190383622A1 · Aich et al. · 2019 [cited by applicant]
US 20190383623A1 · Aich · 2019 [cited by examiner]
US 20190392368A1 · Raghunathan et al. · 2019 [cited by applicant]
US 20200134747A1 · Zhang · 2020 [cited by applicant]
US 20200173808A1 · Beaurepaire · 2020 [cited by examiner]
US 20200182637A1 · Kumar et al. · 2020 [cited by applicant]
US 20200272954A1 · Serra et al. · 2020 [cited by applicant]
US 20200273333A1 · Elshenawy · 2020 [cited by examiner]
US 20200378773A1 · Lehoux-Lebacque et al. · 2020 [cited by applicant]
US 20210182751A1 · Pan · 2021 [cited by examiner]
US 20210248633A1 · Simpson · 2021 [cited by examiner]
US 20220018667A1 · Al-Dujaili · 2022 [cited by examiner]
US 20220065651A1 · Beaurepaire et al. · 2022 [cited by applicant]
US 20220095079A1 · Volkerink et al. · 2022 [cited by applicant]
EP 3339806A1 · 2018 [cited by applicant]
EP 3683742 · 2020 [cited by applicant]
IN 4559CHE2012A · 2014 [cited by examiner]
JP 2007520685 · 2007 [cited by applicant]
JP 2013511095 · 2013 [cited by applicant]
JP 2014032139A · 2014 [cited by applicant]
JP 2016045020 · 2016 [cited by applicant]
JP 2017075967A · 2017 [cited by applicant]
JP 2018109621A · 2018 [cited by applicant]
KR 20180081022A · 2018 [cited by examiner]
WO 2005013234A1 · 2005 [cited by applicant]
WO WO2008142783A1 · 2008 [cited by applicant]
WO WO201718583 · 2017 [cited by applicant]
Multimodal_route_and_tour_planning_in_urban_environments.pdf (Year: 2017). [cited by examiner]
Trip-based_public_transit.pdf (Year: 2015). [cited by examiner]
Translation of In 4559/CHE/2012 A retrieved from IP.com on Mar. 30, 2023 (Year: 2023). [cited by examiner]
Translation of KR-20180081022-A retrieved from Espacenet on Mar. 8, 2024 (Year: 2024). [cited by examiner]
E n g i n e e r i n g A l g o r i t h m s f o r R o u t e P l a n n i n g i n M u l t i m o d a l T r a n s p o r t a t i o n N e t w o r k s (Year: 2016). [cited by examiner]
European Search Report for EP 19305687.6 (Jul. 25, 2019) Jul. 25, 2019. [cited by applicant]
European Search Report for EP 19305689.2 (Jul. 26, 2019) Jul. 26, 2019. [cited by applicant]
U.S. Appl. No. 17/335,402, filed Jun. 1, 2021, entitled, “Method for Computing a Personalized Itinerary From a Departure Location to an Arrival Location” 2021. [cited by applicant]
Office Action from Japanese Patent Office for Japanese Patent Application No. 2020-093731 (Japanese copunter part to U.S. Appl. No. 16/830,621) May 11, 2021 May 11, 2021. [cited by applicant]
English Translation of Abstract of Published Japanese Patent Application No. JP 2007-520685 (A) Jul. 26, 2007 2007. [cited by applicant]
English Translation of Abstract of Published Japanese Patent Application No. JP 2016-045020 (A) Apr. 4, 2016 2016. [cited by applicant]
English Translation of Abstract of Published Japanese Patent Application No. JP 2013-511095 (A) Feb. 28, 2013 2013. [cited by applicant]
Liu, Lu, and Liqiu Meng. ‘Algorithms of Multi-Modal Route Planning Based on the Concept of Switch Point’. Photogrammetrie—Fernerkundung—Geoinformation 2009, No. 5 (Nov. 1, 2009): 431-44. https://doi.org/10.1127/1432-836… [cited by applicant]
Hannah Bast, Mirko Brodesser, and Sabine Storandt. Result Diversity for Multi-Modal Route Plan-ning. In Daniele Frigioni and Sebastian Stiller, editors, 13th Workshop on Algorithmic Approaches for Transportation Modelli… [cited by applicant]
Julian Dibbelt, Thomas Pajor, and Renato F. Werneck. Public transit labeling. In Bampis E., editor, Experimental Algorithms SEA 2015, vol. 9125 of Lecture Notes in Computer Science. Springer, 2015 2015. [cited by applicant]
Moritz Baum, Valentin Buchhold, Jonas Sauer, Dorothea Wagner, and Tobias Zündorf. Unlimited transfers for multi-modal route planning: An efficient solution. In Proceedings of ESA 2019, to appear, 2019 2019. [cited by applicant]
Vassilissa Lehoux and Darko Drakulic. Mode Personalization in Trip-Based Transit Routing. In Gianlorenzo D'Angelo and Twan Dollevoet, editors, 19th Workshop on Algorithmic Approaches for Transportation Modelling, Optimi… [cited by applicant]
I^le De France Mobilités. Open data. https://www.iledefrance-mobilites.fr 2018. [cited by applicant]
Duc-Minh Phan and Laurent Viennot. Fast public transitrouting with unrestrict-edwalking through hub labeling. In Proceedings of the Special Event on Analysis of Experimental Algorithms (SEA2), Lecture Notes in Computer … [cited by applicant]
Dorothea Wagner and Tobias Zundorf. Public Transit Routing with Unrestricted Walking. In Gianlorenzo D'Angelo and Twan Dollevoet, editors, 17th Workshop on Algorithmic Approaches for Transportation Modelling, Optimizati… [cited by applicant]
U.S. Appl. No. 16/830,621, filed Mar. 26, 2020, entitled, “Method for Preprocessing a Set of Non-Scheduled Lines Within a Multimodal Transportation Network of Predetermined Stations and for Computing at Least One Itiner… [cited by applicant]
U.S. Appl. No. 16/700,096, filed Dec. 2, 2019, entitled, “Method for Computing at Least One Itinerary From a Departure Location to an Arrival Location” 2019. [cited by applicant]
U.S. Appl. No. 16/853,914, filed Apr. 21, 2020, entitled, “Method for Computing an Itinerary From a Departure Location to an Arrival Location” 2020. [cited by applicant]
I^le De France Mobilités. Open data. https://www.iledefrance-mobilites.fr 2019. [cited by applicant]
U.S. Appl. No. 16/995,969, filed Aug. 18, 2020, entitled, “Method for Computing an Itinerary From a Departure Location to an Arrival Location” 2020. [cited by applicant]
Barrett, Chris, Riko Jacob, and Madhav Marathe. ‘Formal-Language-Constrained Path Problems’. SIAM Journal on Computing 30 (2000): 200-0. 2000. [cited by applicant]
Bast, Hannah, Erik Carlsson, Arno Eigenwillig, Robert Geisberger, Chris Harrelson, Veselin Raychev, and Fabien Viger. ‘Fast Routing in Very Large Public Transportation Networks Using Transfer Patterns’. In in Proceeding… [cited by applicant]
Bast, Hannah, Daniel Delling, Andrew V. Goldberg, Matthias Müller-hannemann, Thomas Pajor, Peter Sanders, Dorothea Wagner, and Renato F. Werneck. ‘Route Planning in Transportation Networks’, 2014. 2014. [cited by applicant]
E. Cohen, E. Halperin, H. Kaplan, and U. Zwick. Reachability and distance queries via 2-hop labels. SIAM Journal on Computing, 32(5):13381355, 2003 2003. [cited by applicant]
Dibbelt, Julian, Thomas Pajor, Ben Strasser, and Dorothea Wagner. ‘Intriguingly Simple and Fast Transit Routing’. In in SEA, vol. 7933 of LNCS, 43-54. Springer, 2013. 2013. [cited by applicant]
Daniel Delling, Thomas Pajor, and Renato F. Werneck. Round-based public transit routing. In Proceedings of the Fourteenth Workshop on Algorithm Engineering and Experiments (ALENEX), 2013. 2013. [cited by applicant]
Julian Dibbelt, Thomas Pajor, and Dorothea Wagner. User-constrained multi-modal route plan¬ning. In SIAM, editor, Proceedings of the 14th Meeting on Algorithm Engineering and Experiments (ALENEX12), p. 118129, 2012 2012. [cited by applicant]
Geisberger, Robert, Peter Sanders, Dominik Schultes, and Daniel Delling. ‘Contraction Hierarchies: Faster and Simpler Hierarchical Routing in Road Networks’. In Experimental Algorithms, edited by Catherine C. McGeoch, 5… [cited by applicant]
Goldberg, Andrew V., and Chris Harrelson. ‘Computing the Shortest Path: A Search Meets Graph Theory’. In Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 156-165. SODA '05. Vancouver, Briti… [cited by applicant]
Matthias Hertel Hannah Bast and Sabine Storandt. Scalable transfer patterns. In Proceedings of the Eighteenth Workshop on Algorithm Engineering and Experiments (ALENEX), 2016 2016. [cited by applicant]
Kirchler, Dominik. ‘Efficient Routing on Multi-Modal Transportation Networks’. Phdthesis, Ecole Polytechnique X, 2013. https://pastel.archives-ouvertes.fr/pastel-00877450. 2013. [cited by applicant]
Witt, Sascha. ‘Trip-Based Public Transit Routing’. ArXiv:1504.07149 [Cs] 9294 (2015): 1025-36. https://doi.org/10.1007/978-3-662-48350-3_85. 2015. [cited by applicant]
Witt, Sacha. Trip-based public transit routing using condensed search trees. In Marc Goerigk and Renato Werneck, editors, 16th Workshop on Algorithmic Approaches for Transporation Modelling, Optimization, and Systems (A… [cited by applicant]
Liu, Xudong, Christian Fritz, and Matthew Klenk. ‘On Extensibility and Personalizability of Multi-Modal Trip Planning’, n.d., 7. 2018. [cited by applicant]
Ulloa Luis, Lehoux Vassilissa, Roulland Fréderic. Trip planning within a multimodal urban mobility, IET Intelligent Transport Systems, 12(2):87-92, 2018. 2018. [cited by applicant]
Bast, Hannah, Daniel Delling, Andrew Goldberg, Matthias Müller-Hannemann, Thomas Pajor, Peter Sanders, Dorothea Wagner, and Renato F. Werneck. ‘Route Planning in Transportation Networks’. ArXiv:1504.05140 [Cs], Apr. 20,… [cited by applicant]
Web page: https://data.grandlyon.com/ Home ⋅ Metropolitan Data of the Grand Lyon.Pdf, n.d. 2018. [cited by applicant]
Web page : https://opendata.stif.info. ‘Home page—Portail Open Data Île-de-France Mobilités—Open Data Île-de-France Mobilités.Pdf’, n.d. 2018. [cited by applicant]
“General transit feed standard format reference documentation,” https://developers.google.com/transit/gtfs/reference/2018. [cited by applicant]
Artigues, Christian, Marie-josé Huguet, Fallou Gueye, Frédéric Schettini, and Laurent Dezou. State-Based Accelerations and Bidirectional Search for Bi-Objective Multi-Modal Shortest Paths, 2013. 2013. [cited by applicant]
Bast, Hannah, Mirko Brodesser, and Sabine Stor. ‘Result Diversity for Multi-Modal Route Planning’. In 13th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems, vol. 33 of OpenAcces… [cited by applicant]
Delling, Daniel, Julian Dibbelt, Thomas Pajor, Dorothea Wagner, and Renato F. Werneck. Computing Multimodal Journeys in Practice?, n.d. 2018. [cited by applicant]
Garey M. R. and D. S. Johnson. Computers and intractability: A guide to the theory of NP-completeness. Freeman, 1979. 1979. [cited by applicant]
Hansen, Pierre. ‘Bicriterion Path Problems’. In Multiple Criteria Decision Making Theory and Application, edited by Günter Fandel and Tomas Gal, 177:109-27. Berlin, Heidelberg: Springer Berlin Heidelberg, 1980. https://… [cited by applicant]
Idri, Abdelfattah, Mariyem Oukarfi, Azedine Boulmakoul, Karine Zeitouni, and Ali Masri. ‘A Distributed Approach for Shortest Path Algorithm in Dynamic Multimodal Transportation Networks’. Transportation Research Procedi… [cited by applicant]
Office Action from Japanese Patent Office for Japanese Patent Application No. 2020-093731 (Japanese copunter part to U.S. Appl. No. 16/830,621) Mar. 23, 2021 2021. [cited by applicant]
English Translation of Abstract of Published Japanese Patent Application No. JP 2014-032139 (A) 2014. [cited by applicant]
English Translation of Abstract of Published Japanese Patent Application No. JP 2017-075967 (A) 2017. [cited by applicant]
English Translation of Abstract of Published Japanese Patent Application No. JP 2018-109621 (A) 2018. [cited by applicant]
Dorothea Wagner et al: “Geometric containers for efficient shortest-path computation”, ACM Journal of Experimental Algorithmics, Association of Computing Machinery, New York, NY, US, vol. 10, Dec. 31, 2005 (Dec. 31, 200… [cited by applicant]
Office Action dated Nov. 16, 2022 of the European Patent Office for corresponding European Patent Application 19305687.6 filed May 29, 2019 Nov. 16, 2022. [cited by applicant]
European Search Report for EP 19305064.8 (Apr. 18, 2019). [cited by applicant]
Witt, Sasha “Trip Based Public Transit Routing,” N. Bansal and I. Finocchi (Eds.): ESA 2015, LNCS 9294, pp. 1025-1036, 2015 2015. [cited by applicant]
Daniel Delling et al., “Computing Multimodal Journeys in Practice,” V. Bonifaci et al. (Eds.): SEA 2013, LNCS 7933, pp. 260-271, 2013 2013. [cited by applicant]