KR-102962376-B1 - METHOD FOR PREPROCESSING A SET OF NON-SCHEDULED LINES WITHIN A MULTIMODAL TRANSPORTATION NETWORK OF PREDETERMINED STATIONS AND FOR COMPUTING AT LEAST ONE ITINERARY

KR102962376B1KR 102962376 B1KR102962376 B1KR 102962376B1KR-102962376-B1

Abstract

The method comprises a set of unscheduled routes within a multimodal transport network of a set of stations, wherein for each unscheduled route ( l ) of the set of unscheduled routes, a sequence of stations defining the unscheduled route ( l ) (b) for each station ( p l j ) of ) at least one time interval ( I(l,j) ) - during at least one time interval, a trip on an unscheduled route ( l ) can depart from station ( p l j ); (b) for each first station ( p l j ) of an unscheduled route ( l ) reachable from a second station ( p t i ) of a scheduled route, to add the earliest transfer from the second station ( p t i) to the first station (p l j ) on the trip ( t ) to a set of feasible transfers between the scheduled route and the unscheduled route, if there exists a trip ( t ) on the scheduled route such that the departure time from the first station ( p l j ) after the transfer is compatible with at least one time interval (I (l , j )) associated with the first station ( p l j ); and (c) preprocess by outputting a set of feasible transfers between scheduled routes and non-scheduled routes to calculate at least one journey within a multimodal transport network.

Inventors

르우-르바케, 바실리사
드라쿨릭, 다르코

Assignees

네이버 주식회사

Dates

Publication Date: 20260511
Application Date: 20200512
Priority Date: 20190529

Claims (20)

A method for constructing at least one optimal itinerary to be used to plan a trip by a user moving within a multimodal transport network by preprocessing a set of non-scheduled routes within a multimodal transport network of predetermined stations to enable the construction of itineraries combining non-scheduled routes and scheduled routes, A scheduled route is a predetermined sequence of stations having known timetables, and an unscheduled route is a non-walking mode of transport that does not have known timetables, and The above method is: (a) receiving a starting location and an arrival location from the user through a user interface; (b) For each non-scheduled route ( l ) of the set of non-scheduled routes, a sequence of stations defining the non-scheduled route ( l ) A step of associating at least one time interval ( I(l,j) ) to each station ( p l j ) of ) - during said at least one time interval, a trip ( t n ) on an unscheduled route ( l ) can depart from said station ( p l j ); (c) For each first station ( plj ) of an unscheduled route ( l ) reachable from a second station ( pti ) of a scheduled route, if there exists a trip (ts) on the scheduled route such that the departure time from the first station ( plj ) after the transfer is compatible with at least one time interval ( I(l,j) ) associated with the first station ( plj ) , in the set of feasible transfers between the scheduled route and the unscheduled route, the earliest transfer from the second station ( pti ) to the first station ( plj ) on the trip ( ts ); (d) outputting a set of feasible transfers between a scheduled route and an unscheduled route to calculate at least one journey within the multimodal transport network; (e) a step of determining, based on the set of feasible transfers, a set of initial trips possible as a function of the departure position and a set of final trips possible as a function of the arrival position in a multimodal transport network; (f) performing a path optimization algorithm to construct at least one optimal journey according to at least one criterion including the best arrival time, based on trips on scheduled or unscheduled routes and transfers between trips from the set of feasible transfers, among journeys 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; and (g) outputting the at least one optimal itinerary to be used by the user to plan a trip moving in the multimodal transport network through a user interface to the user. A method for constructing at least one optimal journey including
In paragraph 1, (c) is a step of generating a set of feasible transfers between scheduled routes, and a step of pruning this set to obtain a reduced set of feasible transfers between scheduled routes. A method for constructing at least one optimal journey including
In paragraph 1, Inequality An instance that ensures ) is verified ( If ) exists, the departure time from the first station ( p l j ) after the transfer is considered to be compatible with at least one time interval ( I(l,j) ), and is the time of arrival at the second station ( p t i ) on the trip ( t ), and A method for constructing at least one optimal journey, wherein is the transfer duration from the second station ( p t i ) to the first station ( p l j ) on the trip ( t ).
In paragraph 2, Inequality An instance that ensures ) is verified ( If ) exists, the departure time from the first station ( p l j ) after the transfer is considered to be compatible with at least one time interval ( I(l,j) ), and is the time of arrival at the second station ( p t i ) on the trip ( t ), and A method for constructing at least one optimal journey, wherein is the transfer duration from the second station ( p t i ) to the first station ( p l j ) on the trip ( t ).
In paragraph 3, The best transfer from the second station ( pti ) to the first station ( plj ) on the trip ( t ) is, The best instant to make it happen A method for constructing at least one optimal journey, which is a transfer to the first station ( p l j ) on the best trip ( t' ) of the above unscheduled route ( l ) that becomes ).
In paragraph 4, The best transfer from the second station ( pti ) to the first station ( plj ) on the trip ( t ) is, The best instant to make it happen A method for constructing at least one optimal journey, which is a transfer to the first station ( p l j ) on the best trip ( t' ) of the above unscheduled route ( l ) that becomes ).
In paragraph 1, For a transfer between a trip ( t ) at an index ( i ) that becomes valid and a trip ( t' ) at an index ( j ), the waiting time associated with the transfer is bounded by a maximum value ( w ), and A method for constructing at least one optimal journey.
In paragraph 2, For a transfer between a trip ( t ) at an index ( i ) that becomes valid and a trip ( t' ) at an index ( j ), the waiting time associated with the transfer is bounded by a maximum value ( w ), and A method for constructing at least one optimal journey.
In paragraph 3, For a transfer between a trip ( t ) at an index ( i ) that becomes valid and a trip ( t' ) at an index ( j ), the waiting time associated with the transfer is bounded by a maximum value ( w ), and A method for constructing at least one optimal journey.
In paragraph 5, For a transfer between a trip ( t ) at an index ( i ) that becomes valid and a trip ( t' ) at an index ( j ), the waiting time associated with the transfer is bounded by a maximum value ( w ), and A method for constructing at least one optimal journey.
In paragraph 1, boarding time ) and/or alighting time( A method for constructing at least one optimal journey, wherein each is added before departure from the first station ( p l j ) and/or after arrival at the second station ( p t i ).
In paragraph 2, boarding time ) and/or alighting time( A method for constructing at least one optimal journey, wherein each is added before departure from the first station ( p l j ) and/or after arrival at the second station ( p t i ).
In paragraph 3, boarding time ) and/or alighting time( A method for constructing at least one optimal journey, wherein each is added before departure from the first station ( p l j ) and/or after arrival at the second station ( p t i ).
In paragraph 5, boarding time ) and/or alighting time( A method for constructing at least one optimal journey, wherein each is added before departure from the first station ( p l j ) and/or after arrival at the second station ( p t i ).
In Paragraph 7, boarding time ) and/or alighting time( A method for constructing at least one optimal journey, wherein each is added before departure from the first station ( p l j ) and/or after arrival at the second station ( p t i ).
In paragraph 1, (b) is a step of defining the travel time between any pair of stations ( p, q ) of the above unscheduled route ( l ) such that i < j , p = p | i , and q = p | j. A method for constructing at least one optimal journey including
In paragraph 2, (b) is a step of defining the travel time between any pair of stations ( p, q ) of the above unscheduled route ( l ) such that i < j , p = p | i , and q = p | j. A method for constructing at least one optimal journey including
In paragraph 3, (b) is a step of defining the travel time between any pair of stations ( p, q ) of the above unscheduled route ( l ) such that i < j , p = p | i , and q = p | j. A method for constructing at least one optimal journey including
In paragraph 5, (b) is a step of defining the travel time between any pair of stations ( p, q ) of the above unscheduled route ( l ) such that i < j , p = p | i , and q = p | j. A method for constructing at least one optimal journey including
In Paragraph 7, (b) is a step of defining the travel time between any pair of stations ( p, q ) of the above unscheduled route ( l ) such that i < j , p = p | i , and q = p | j. A method for constructing at least one optimal journey including

Description

Method for preprocessing a set of non-scheduled lines within a multimodal transportation network of pre-scheduled stations and for computing at least one itinerary Pursuant to 35 U.S.C.§ 119(a), this application claims the benefit of the prior filing date and priority of European patent application EP19305689.2 filed on May 29, 2019, the contents of which are incorporated herein by reference in their entirety. A journey planner (also called a trip planner) is a solution used to determine the optimal journey from a transportation origin (initial point of origin) to an arrival point (destination) using one and/or more modes of transportation, particularly public transport modes (e.g., subway, tram, bus, etc.). A journey planner is called "multimodal" when it covers multiple modes of transportation and allows connections between modes (i.e., transfers from one mode to another). Searches can be optimized based on different criteria, such as the fastest, shortest, smallest number of changes, and/or lowest cost. For some criteria, the maximal set of optimal values becomes the Pareto front, and the maximal set of optimal solutions becomes the Pareto set. A planner is optimal if it returns a Pareto set. Searches may be dependent on, for example, leaving and/or arriving at a specific time, avoiding specific waypoints, etc. Public transport modes generally operate according to public schedules; given that public transport services depart only at specific times (unlike private modes of transport such as driving, walking, and/or cycling, which can depart at any time), travel planner algorithms should therefore not only find a route to a destination but also optimize the route to minimize the arrival time in these time-dependent settings. One of the highest-performance algorithms used for this purpose is the "Trip-Based Public Transit Routing Algorithm"("Trip-Based Public Transit Routing Algorithm" and/or "TB Algorithm"), which is a method based on iterations similar to Breadth-First Search (BFR) in a graph, where one iteration corresponds to taking a trip. This is disclosed in the document " Sacha Witt. Trip-based public transit routing. In N. Bansal and I. Finocchi, editors, ESA 2015, Computer Science Lecture Notes Vol. 9294, Berlin, Heidelberg 2015. Springer ". The TB algorithm is an algorithm for calculating the optimal path with these values together with Pareto fronts (for each value within the Pareto front for two criteria in multimodal networks limited to transit and walking between stations, considering the origin, destination, and time of departure). The two criteria considered are: the minimum arrival time (i.e., the earliest arrival time considering the time of departure); and the minimum transfer number (i.e., the minimum number of connections, that is, the number of changes in public transport modes within the same network—e.g., from the subway to another—and/or intermodally). The best time to arrival query consists of a breadth-first search-like search within a time-independent graph where trips are vertices and feasible transfers are arcs (i.e., exploring all neighboring trips in the graph at the current depth before moving to trips at the next depth level). Thus, for each iteration, one additional trip is taken from each solution to attempt and reach the destination. The TB algorithm is based on the preprocessing and pruning of feasible transfers between trips. For any optimal path, the goal is to construct neighbors of reachable trips for each trip in such a way that the preprocessed set of neighbors includes a transfer between a trip and its neighbors within the optimal path. In practice, while the resulting method will be accurate, using a complete set of feasible transfers between trips during the search phase is undesirable, given that it is large and useless arcs will affect search time. In fact, when all feasible transfers between one trip and another route (a set of entirely ordered trips with the same stop sequence) are considered, only the best trip (the minimum trip with respect to line order) will be relevant to the Pareto queries defined above. Therefore, for the Pareto front and each value within the Pareto front, it is desirable to prun the set of feasible transfers while maintaining a sufficient number of transfers to calculate a possible optimal path having these values. As explained, current TB algorithms are limited to transit between stations and walking, and do not allow combinations with non-scheduled modes of transport such as bicycles or car-sharing. However, mixed journeys that use both scheduled and unscheduled modes of transport simultaneously can be very efficient. For example, arriving at a train station using an on-demand bus becomes very efficient in rural areas. In the example of bike sharing, it was suggested, for instance, in the document " Trip planning within a multimodal urban mobility. IET Intelligent Transport Systems, 12(2):8792, 2018." by Luis Ulloa, Vassilissa L