Search

US-12626197-B2 - Method for computing a set of itineraries from a departure location to an arrival location using cluster-based searching

US12626197B2US 12626197 B2US12626197 B2US 12626197B2US-12626197-B2

Abstract

A method and system for preprocessing and query stages for a trip-based public transit routing algorithm, which is used for multimodal routing computations, clusters the public transit network and computes relevant network parts when transiting between different clusters in order to prune the search at query time. The processing phase is modified to use only a subset of the network, depending on the clusters associated to the origin and destination locations.

Inventors

  • Vassilissa Lehoux-Lebacque
  • Christelle Loiodice
  • Maxime Raynal

Assignees

  • NAVER CORPORATION

Dates

Publication Date
20260512
Application Date
20220801

Claims (20)

  1. 1 . A method for reducing computation time for a computer, having an electronic processor and an electronic memory, processing a set of feasible transfers (T) between trips and a set of trips (U) within a multimodal transportation network of predetermined stations to determine at least one optimal itinerary between an origin and a destination, a trip corresponding to a sequence of stops of a line L, {right arrow over (p)} (L)=(L@i, L@i+1, . . . ) wherein L@ is a stop in the sequence of stops and i is a position of the stop L@ within the sequence of stops, the method comprising: (a) electronically computing a set of feasible transfers (T) between stations of an origin trip t and a destination trip t′; (b) reducing computation time for the computer processing the set of feasible transfers (T) between trips and a set of trips (U) within a multimodal transportation network of predetermined stations to determine at least one itinerary between an origin and a destination by (b1) electronically partitioning a set of stops in the multimodal transportation network to form clusters, and for each cluster (S), computing a set of entry points (L entry , i entry ) of cluster (S) to be such that position value (i entry ) is greater than or equal to one, stop (L entry ) at position (i entry ) is part of cluster (S), and the stop (L entry ) at a position before position (i entry ) is not part of cluster (S) is defined, and computing a set of the exit points (L exit , i exit ) of cluster (S) being such that position value (i exit ) is less than one less than a number of stops of line L, stop (L exit ) at position (i exit ) is part of cluster (S), and the stop (L exit ) at a position after position (i exit ) is not part of cluster (S) is defined, (b2) electronically determining, for each cluster (S), a crown (C S ), crown (C S ) being a set of lines that form part of at least one Pareto-optimal journey for any origin-destination within a cluster and being defined for a given line L, if there exists position value (i) is less than one less than a number of stops of line L such that sop L@i is part of cluster (S) and stop L@(i+1) is part of cluster (S), then line L is part of crown (C S ), and (b3) electronically determining, for each cluster (S), links (L S→D ) of cluster (S) to cluster (D) for all clusters (D) different from cluster (S), link (L S→D ) being defined for a given line L, if there exists an exit point (L exit , i exit ) of S, and an entry point (L entry , i entry ) of D such that a trip of L belongs to at least one journey between (L exit , i exit ) and (L entry , i entry ) in a reference solution set of link computations, then L is part of links (L S→D ) of cluster (S) to cluster (D) for all clusters (D) different from cluster (S); (c) receiving a query to determine possible itineraries between an origin and a destination; (d) electronically computing a set of trips (U), to be used to process the received query, based upon the determined crowns (C S ) and determined links (L S→D ); and (e) electronically processing the received query, using only the computed set of trips (U) and the computed set of feasible transfers (T), by electronically performing a routing optimization algorithm to electronically compute a Pareto front, the routing optimization algorithm, using the computed Pareto front, generating at least one optimal itinerary for the origin, the destination, and a range of start times.
  2. 2 . The method as claimed in claim 1 , wherein the crowns (C S ) are further defined for a given line L, if there exists an entry point (L entry , i entry ) of S, and an exit point (L exit , i exit ) of S such that a trip of L belongs to at least one journey between (L exit , i exit ) and (L entry , i entry ) in a reference solution set of crown computations, then line L is an element of the crowns C S .
  3. 3 . The method as claimed in claim 2 , wherein the reference solution set of crown computations includes a complete solution set for a profile query between (L entry , i entry ) and (L exit , i exit ).
  4. 4 . The method as claimed in claim 3 , wherein the reference solution set of link computations includes a complete solution set for a profile query between (L exit , i exit ) and (L entry , i entry ).
  5. 5 . The method as claimed in claim 4 , wherein the complete solution sets are obtained using a one-to-many exact profile query algorithm.
  6. 6 . The method as claimed in claim 3 , wherein the reference solution set of link computations is a union of complete solution sets for profile queries between a given exit point (L exit , i exit ) of S and a given entry point (L′ entry , i′ entry ) of D.
  7. 7 . The method as claimed in claim 6 , wherein the complete solution sets are obtained using a one-to-many exact profile query algorithm.
  8. 8 . The method as claimed in claim 3 , wherein the complete solution sets are obtained using a one-to-many exact profile query algorithm.
  9. 9 . The method as claimed in claim 2 , wherein the reference solution set of link computations includes a complete solution set for a profile query between (L exit , i exit ) and (L entry , i entry ).
  10. 10 . The method as claimed in claim 9 , wherein the reference solution set of crown computations is a union of complete solution sets for profile queries between a given entry point (L entry , entry i) and a given exit point (L′ exit , i′ exit ) of S.
  11. 11 . The method as claimed in claim 10 , wherein the complete solution sets are obtained using a one-to-many exact profile query algorithm.
  12. 12 . The method as claimed in claim 9 , wherein the complete solution sets are obtained using a one-to-many exact profile query algorithm.
  13. 13 . The method as claimed in claim 2 , wherein the reference solution set of link computations is a union of complete solution sets for profile queries between a given exit point (L exit , i exit ) of S and a given entry point (L′ entry , i′ entry ) of D.
  14. 14 . The method as claimed in claim 13 , wherein the reference solution set of crown computations is a union of complete solution sets for profile queries between a given entry point (L entry , entry i) and a given exit point (L′ exit , i′ exit ) of S.
  15. 15 . The method as claimed in claim 14 , wherein the complete solution sets are obtained using a one-to-many exact profile query algorithm.
  16. 16 . The method as claimed in claim 13 , wherein the complete solution sets are obtained using a one-to-many exact profile query algorithm.
  17. 17 . The method as claimed in claim 2 , wherein the reference solution set of crown computations is a union of complete solution sets for profile queries between a given entry point (L entry , entry i) and a given exit point (L′ exit , i′ exit ) of S.
  18. 18 . The method as claimed in claim 17 , wherein the complete solution sets are obtained using a one-to-many exact profile query algorithm.
  19. 19 . The method as claimed in claim 2 , wherein the set of trips (U) is the union of a trips of a crowns of all the clusters and trips of the links between all transfer pairs.
  20. 20 . The method as claimed in claim 2 , wherein the reference solution sets of link and crowns computations are computed using a model of the multimodal transportation network wherein public transit information is represented using a graph having nodes representing trips of the public transit network belonging to the set of trips (U) and arcs representing possible transfers between two trips at given stops.

Description

PRIORITY INFORMATION The present application claims priority, under 35 USC § 119(e), from U.S. Provisional Patent Application, Ser. No. 63/291,632, filed on Dec. 20, 2021. The entire content of U.S. Provisional Patent Application, Ser. No. 63/291,632, filed on Dec. 20, 2021, is hereby incorporated by reference. The present application claims priority, under 35 USC § 119(e), from U.S. Provisional Patent Application, Ser. No. 63/294,183, filed on Dec. 28, 2021. The entire content of U.S. Provisional Patent Application, Ser. No. 63/294,183, filed on Dec. 28, 2021, is hereby incorporated by reference. BACKGROUND A journey planner (also called trip planner) is a solver used to determine an itinerary from an origin location (the origin) to an arrival location (the destination), using one or more transport modes, in particular public transportation modes (subway, tram, bus, etc.—the planner is said to be “multimodal” when covering several transportation modes and allowing intermodal transfers from one mode to another). Searches may be optimized on different criteria, for example fastest, shortest, least changes, cheapest. Searches may be constrained for example to leave or arrive at a certain time, to avoid certain waypoints, etc. Public transport modes generally operate according to published schedules, given that public transport services only depart at specific times (unlike private modes of transportation such as driving, walking, or cycling, which may leave at any time), an algorithm must therefore not only find a path to a destination, but seek to optimize it so as to minimize the arrival time in this time-dependent setting. In mobility applications or websites, finding possible paths between an origin and a destination is a classical problem. One algorithm used to this end is the “Trip-Based Public Transit Routing” algorithm, which is a method based on iterations, similar to breadth-first search in a graph, where one iteration corresponds to taking a trip. It is disclosed in the document Sacha Witt. “Trip-based public transit routing.” In N. Bansal and I. Finocchi, editors, ESA 2015, volume 9294 of Lecture Notes in Computer Science, Berlin, Heidelberg, 2015. Springer. The Trip-Based Public Transit Routing algorithm is an algorithm for computing a Pareto front and a solution with this value for each element in the Pareto front for two criteria in multimodal networks restricted to transit and walking between stations, considering an origin, a destination, and a start time. In the Trip-Based Public Transit Routing algorithm, the criteria, minimum arrival time (i.e., the earliest arrival time considering the start time) and minimum transfer number (i.e., the minimum number of changes of vehicle or transport mode, either within the same network or intermodally), are optimized. If a set of criteria (c1,c2, . . . , cn) is to be minimized, a n-tuple (v1,v2, . . . , vn) of values for those criteria is non-dominated in the Pareto sense if there is no other n-tuple (v′1,v′2, . . . , v′n) such that for all i∈{1, 2, . . . , n}, v′i≤vi and ∃i∈{1, 2, . . . , n} such that v′i<vi. The set of non-dominated criterion values of feasible paths is called Pareto front. An optimal path, in the Pareto sense, for minimum arrival time and minimum number of transfers is hence a path whose values belong to the Pareto front for those criteria. The Trip-Based Public Transit Routing algorithm builds the Pareto front for minimum arrival time and minimum number of transfers and returns one optimal itinerary with this value for each element in the Pareto front in polynomial time. The Trip-Based Public Transit Routing algorithm is based on the preprocessing and pruning of the feasible transfers between trips. The aim is to build for each trip a neighborhood of reachable trips in such way that when searching this graph structure, the Pareto front can be obtained. An earliest arrival time query then consists in a breadth-first search like exploration in a time-independent network where the trips are vertices and the possible transfers the arcs. This graph representation of the transportation network is illustrated in FIG. 2. The Trip-Based Public Transit Routing algorithm can also cover profile queries, where all the optimal paths must be found for a given starting time range. FIG. 2 illustrates the modeling of the network in the Trip-Based Public Transit Routing algorithm search phase. Public transit information is represented using a graph, whose vertices (or nodes) are the trips of the public transit network and whose arcs represent the possibility to transfer between two trips at given stops. FIG. 2 illustrates the modeling of a transfer 15 between a first trip 10 of a public transit network at station (stop) (i) and a second trip 20 of the public transit network at station (stop) (j). FIG. 2 further illustrates a second transfer 25 between the first trip 10 of the public transit network at station (stop) (u) and a third trip 30 of the publ