JP6966598B2 - How to handle a feasible set of transfers to calculate an itinerary within a multi-modal transportation network - Google Patents

Description

The present application is 35 U.S. S. C. Claims the prior filing date and priority benefit of European patent application EP19305687.6 filed on May 29, 2019 under §119 (a), all of which are incorporated herein by reference.

A travel planner (also known as a trip planner) is one and / or more modes of transportation, especially public transport modes (eg, subways, trams, buses, etc.). It is a service used to determine the optimal itinerary from the departure point (first departure point (origin)) to the arrival point (destination). The travel planner covers many types of traffic modes and allows the modes to be connected to each other (that is, switching from a predetermined mode to another mode) is called "multimodal". The search is optimized by different criteria such as, for example, fastest, shortest, minimum number of changes, and / or lowest prices. These may be restricted, for example, to depart and / or arrive at a particular time, or to avoid a particular waypoint.

Public transport mode operates on a schedule that is open to the public. The travel planner algorithm is intended when considering that public transport services depart only at specific times (unlike private modes such as driving, walking, and / or biking a private car that can depart at any time). Instead of searching only for the route to the ground, the route must be optimized to minimize arrival time within a time-dependent setting.

One of the highest performance algorithms used for this is the "trip-based public transport routing" algorithm ("Trip-Based Public Routing Algorithm" and / or "TB algorithm"). This is an iteration-based method similar to breadth-first search (BFR) of a graph, and corresponds to adopting one iteration with one trip (taking a trip). .. This is described in Non-Patent Document 1.

The TB algorithm takes into account Pareto front and (first) origin, destination, and departure time, and is multimodal, limited to station-to-station transfers and walking. It is an algorithm for calculating together the optimum route having such a value for each value in Pareto efficiency for two kinds of criteria in the network. The two criteria considered are the minimum arrival time (ie, the earliest arrival time considering the departure time) and the minimum transfer number (ie, the minimum number of connections). , In other words, within the same network (eg, from the subway to others) and / or the number of intermodal public transport mode changes (changes).

The earliest arrival time query consists of a search similar to a breadth-first search (ie, the next depth) within a time-independent graph where the trip is at the top and the feasible transfers are arcs. Search for all adjacent trips on the graph at the current depth before moving to the level trip). Therefore, at each iteration, an additional trip is adopted as each solution to reach the destination.

Extensions to the TB algorithm, which consist of the latest late departure time query, may be considered. In the latest departure time query, the expected arrival time is given instead of the start time, and the two criteria considered to calculate the Pareto route are the Max departure time (ie, the end). The latest departure time considering the time) and the minimum number of transfers (Mintransfer number).

The latest departure time query consists of a search similar to the backward search of the time-independent graph defined above, with trips at the vertices and feasible transfers being arcs. NS.

The TB algorithm is based on feasible transfer pre-processing and pruning within the trip. Such optimal values are such that adjacent sets preprocessed for any optimal value within Pareto efficiency include a trip and a transition to and from that trip within the optimal route. The goal is to build next to a trip that can be reached for each trip by a method that ensures that there is an optimal route to have.

In practice, the exact consequential method may not be known, but using a complete set of feasible transfers between trips during the exploration phase is a huge and wasteful arc exploration. It is also unfavorable in that it also affects time.

For example, when used on the Korean transportation network, pruning by the TB algorithm is about 8 out of 9 feasible transfers, considering only the earliest feasible transfers to each route. Eliminate.

In fact, considering all feasible transfers between one trip and another line (a set of totally ordered trips with the same stop sequence), the earliest trip ( Only the minimum trip with respect to the line order) will be associated with the Pareto query as defined above.

Therefore, for all optimal values (ie, Pareto efficiency) and for each element within Pareto efficiency, sufficient transfers are maintained to calculate at least one optimal route with such values. However, it is preferable to pruning a set of feasible transfers. To this end, there are two types of pruning methods: (1) For each trip, transfer to a U-turn (someone (at a time after the arrival time of the stop point before adopting the trip) the previous stop in the trip). Eliminating transfers that only take you to the stop, and (2) transfers that do not improve your arrival time (later transfers (or those that remain on your current trip). It is provided that all trips that lead to equivalent and / or even better arrival times and are arriving by the applicable transfer will arrive by the subsequent transfer).

はプルーニングされてよい。 For example, in FIG. 2, transfer from the stop point p _t ⁱ of the trip t to the stopping point p _u ^j of the trip u leads to the always excellent arrival time than the next transfer to the stopping point p _{u j} ^{+ 1} of the trip u Should be, therefore, transfer

May be pruned.

Sufficient to calculate the correct set of transfers for the earliest arrival time query (ie, in any case, Pareto efficiency and at least one optimal route for each optimal value with such a value). Keep in mind that (including transfers) is also correct for the latest departure time queries. This is described in Non-Patent Document 2.

The limitation of the current TB algorithm is that at the time of query, it is not possible to specify exactly which combination of modes the user wants to include and / or exclude. More specifically, the user tries to avoid using the bus because the bus is not reliable enough, or / additionally avoids the tram due to the congestion of the tram from other sources. Or try.

In fact, pruning may eliminate transfers that are actually useful when the modes are limited to a particular combination, which may result in non-optimal solutions searched during mode selection.

For example, in FIG. 3, _{it is assumed that the three trips t 1} , t ₂ , and t ₃ are in different modes, such as, for example, a bus 302, a tram 304, and a subway (metro) 306. When considering a transfer from trip t _{1, it is possible to transfer from t 1} to t ₃ at station p, and to transfer from t _{1 to t 2} by walking between stations p and q. (The route by foot is shown by a solid line in Fig. 3).

Pruning excludes the transfer from trip t ₁ to trip t ₂ because it is more efficient to transfer to _{trip t 3} without improving the arrival time at a given station. _{However, in configurations where trip t 3} (where the user does not want to use the subway) is excluded, trip t ₂ must be adopted to reach an additional stop.

In order for the TB algorithm to manage mode selections reliably, preprocessing must be performed for each possible combination of selected modes. This requires multiple repeats of preprocessing and multiple servers to execute to handle such queries, and the number of combinations increases exponentially with the number of modes.

As a result, there is a need for a method for calculating an itinerary in a multi-modal transportation network that considers the user's desired transportation mode.

The accompanying drawings are intended to illustrate the various embodiments and should not be understood in a limited manner.
It is a figure which showed the example of the architecture which executes the method described later. It is a figure which showed the configuration example of a trip and a transfer. It is a figure which showed the configuration example of a trip and a transfer. It is a figure which showed the method of pre-processing the set of transfer which can be realized in the multi-modal transportation network of a predetermined station. FIG. 5 illustrates a method of calculating at least one itinerary from origin to destination based on a feasible transfer preprocessed set processed as performed in FIG. It is a figure which showed the method of pruning a set of transfer in the multi-modal traffic which has a user desired mode of traffic.

As shown in FIGS. 4, 5, and 6, method 403 preprocesses a set of feasible transfers (ie, feasible transfers) for each trip within the multimodal transportation network of a given station. The method 410, however, calculates at least one itinerary from the departure point to the arrival point based on a set of preprocessed and feasible transfers (more on which will be described in FIG. 4). More specifically, preprocessing reduces all feasible transfer sets as a subset, and the itinerary utilizes only such feasible transfer subset transfers.

Keep in mind that the set of transfers is correct (ie, for any input, and any optimal value corresponding to such an input, the set of transfers is part of the optimal solution with such values. Including transfer).

A multimodal transportation network is preferably a network in public transportation mode, in particular a network in "scheduled" transportation mode, i.e. its timetable as a route (such as a given sequence of stations). It has been published. Examples of scheduled public transport modes include buses, subways, trams, trains, water shuttles, carpooling, and the like.

In an alternative embodiment, the multimodal transportation network includes scheduled private transportation modes including those combined with networks of these single and / or public transportation modes, such as aircraft, van shuttles, ships, ferries, etc. Network may be included.

Multimodal transportation networks include chartered buses (on-demand bus), ride-hailing, or shared bicycles (users can easily ride a bicycle from one station to another without restrictions). Non-scheduled transportation modes, such as those combined with single or public and private transportation modes, may also be included, but for the purposes of the explanation provided below, only scheduled public transportation modes are included. Shall be involved in a multimodal transportation network. Keep in mind that multiple modes of traffic, ie at least two of these, are involved.

A station and / or "stop point" means a facility at a given location, where at least one of the traffic modes of a multimodal traffic network stops periodically to board or disembark passengers, eg, It means a transportation hub such as a bus stop, a subway station, a train station (including, for example, a bus stop and a train station).

A "displacement" within a multimodal transportation network is defined as a sequence of trips to other stations that may or may not be associated with changing traffic modes between stations in a multimodal transportation network. NS.

"Trip" means a displacement that uses a single one along the route, like a bus in a traffic mode. In general, any displacement involves a transfer between two consecutive trips (ie, considered as a trip and alternation).

（以下を参照）として表現される乗り換えは、ステーションｐ_ｔ ^ｉでトリップｔを出発してステーションｐ_ｕ ^ｊでトリップｕに乗ることができればトリップｔに対して「実現可能な」ものとなり、すなわち、乗り換え存続期間（ｄｕｒａｔｉｏｎ）は、トリップｔおよびｕのスケジュールと両立される。 Transfer means a connection from one traffic mode to another, for example, a displacement between a station where a trip ends and a station where a new trip begins.

Transfer represented as (see below), it is assumed "feasible" to trip t if it is possible to ride the trip u at station p _t ⁱ station starting a trip t in p _u ^j, i.e., The transfer duration is compatible with the trip t and u schedules.

In the following description, the trips t and u before and after the transfer are referred to as "origin" trips and "target" trips to distinguish them, respectively. In other words, the user switches from the origin trip t to the target trip u. Keep in mind that the target trip can also be an origin trip for additional transfers.

Such a transfer is carried out by the "first traffic mode". This is not a public transport mode of the network, but generally includes portable or wearable auxiliary equipment (assists) such as walking, kickboarding, and / or skating.

The first traffic mode is a non-scheduled station-free mode, which is freely available to the user without limitation. Normally, the first mode of traffic is universal and does not require any vehicle (in the worst case, it requires something "light" and transportable, such as skating). Keep in mind that transfers are not necessarily associated with mutations (stations may be common for two trips in the same traffic mode, for example two subway lines).

For the purposes of the following description, the first traffic mode may be assumed to be walking, i.e., displacement within the network is limited to transit and walking between stations.

Considering all feasible transfer sets T, the purpose of the preprocessing is to output a subset T'as described above, by pruning such a set T to get the best results for the query. While granting, the search time can be significantly reduced when calculating the itinerary based on this. Note that the set of trips does not change, so the preprocessing corresponds to the simplification of the graph to eliminate arcs (transfers) between vertices (trips).

When the itinerary must be calculated within the network, the itinerary, in turn, is the starting part from the departure point to the first station of the multimodal transportation network of a given station, and (trips using the transportation mode of the multimodal transportation network). Includes the main part of the multimodal transportation network (defined as alternation and transfer changes using the first mode of traffic) and the end part of the multimodal transportation network from the last station to the destination.

Departure and arrival points are geographical locations, usually locations on a map defined by addresses, points of interest, coordinates, and the like.

The beginning and ending parts of the itinerary allow the user to "connect" with stations on the network. These may be "null", especially if the departure / arrival points are isolated stations, and such stations may be used as the first / last station. However, even in such a case, the user may move to another station on foot.

The main part begins as the first trip from the first station, which is the entry point to the multimodal transportation network for this itinerary (the term "source stop" is found), and the station, which is the exit point of the multimodal transportation network. Ends on the last trip on the target route to (the term "target stop" is found).

The itinerary is preferably (earlier) arrival time, (lowest) itinerary duration, (latest) departure time, (shortest) itinerary length, (lowest) number of transfers, (lowest). ) It is optimal according to at least one criterion, such as cost (or at least close to such optimal, i.e., an approximation of the optimal value).

In the example of the Trip-Based Public Transit Routing Algorithm, which will be described in detail below, both the arrival time and the number of transfers are considered.

The start and end parts are by the first traffic mode (ie, on foot) or, as an alternative possible, without any unscheduled, station of the second traffic mode (which has a longer range than the first traffic mode). Performed by mode (which may not be one of the modes of a multimodal transportation network).

The second traffic mode is usually a taxi, but an equivalent traffic mode, especially private, such as a car ride (usually a friend's lift, park-and-ride, ride hailing, etc.). It may be a car ride, a motorcycle ride, and / or a helicopter.

An example of the second traffic mode is disclosed in Patent Document 1 entitled "A Method of Calculating At least One Itinerary from Departure to Arrival" filed on December 2, 2019. All of the contents of Patent Document 1 are here incorporated as references.

The first and / or second traffic modes must be understood to be limited only by the presence of cartography, ie roads (especially roads), approaches, etc., and a given list of stations. In contrast to the mode of multimodal transportation network that relies on, it is considered to be able to reach some location.

In summary, a possible given itinerary begins at the beginning, which moves the user from the departure point to the first station, then in the main part, various public transport modes (multimodal transport networks) and walks for transfers. The user uses (first traffic mode) and moves the user from the final station to the destination. In order to finish the itinerary at the end portion, the user travels to the final station by a network (multimodal transportation network) (travel).

The method described above is performed by the server 1, the mobile computer 2a, or the mobile phone 2b and is implemented within the architecture as shown in FIG.

Each such device connects to an extended network 20 such as the Internet for exchanging data. Each device includes data processing means 11, 21a and 21b such as a processor and storage means 12, 22a and 22b such as a computer memory such as a hard disk.

More specifically, the server 1 performs the pre-processing of the transfer set, and the user generally makes a mobile phone (mobile phone) 2b, such as a smartphone, a request for the itinerary (departure, arrival, and departure). Own to enter the time). The request for the itinerary may be processed directly by the mobile phone 2b or may be transmitted to the server 1 for processing. The method should not be restricted to any particular realization.

As mentioned above, pruning may eliminate transfers that are actually useful if the mode is limited to a particular combination. As a result, the pretreatment method performs the pruning step and prevents the transfer from being pruned simply because the other transfers show better results than the transfer if the associated modes are different.

で表現され、したがって、オリジントリップｔ上のステーションｐ_ｔ ^ｉ（ｉ^ｔｈステーション）からターゲットトリップｕ上の到着可能なステーションｐ_ｕ ^ｊ（ｊ^ｔｈステーション）への乗り換えは

で表現されてよい。説明したように、乗り換え

は、ステーションｐ_ｔ ^ｉからトリップｔを出発してステーションｐ_ｕ ^ｊからトリップｕに乗ることができれば実現可能となる。

が実現可能であれば、ｔから同じ路線の以後のいかなるトリップへの乗り換えも可能となる。 The station sequence of trip t is

In are represented, therefore, transfer to the origin trip t on the station _p ^{t i (i th} station) from the target trip u on arrival possible station _p ^{u j (j th} station) is

It may be expressed by. As explained, transfer

Is, it is possible to realize if you can get on the trip u from the station p _u ^j starting the trip t from station p _t ^i.

If is feasible, it is possible to transfer from t to any subsequent trip on the same route.

および／または最先の変更時刻

の値を「初期化」することと、その次に、段階４０６で、ターゲットトリップｕ上の到着可能なステーションｐ_ｕ ^ｊへの実現可能な乗り換えのセットのうちの少なくとも１つの乗り換え（および、好ましくは各実現可能な乗り換え）に対し、到着可能なステーション後のターゲットトリップ上の各ステーション（すなわち、ｋ＞ｊを有するトリップｕ上のステーションｐ_ｕ ^ｊ）で最先の到着時刻

および／または最先の変更時刻

（ステーションｐの変更時刻

は、一般的にこのようなステーションｐの最先の到着時刻

に該当のステーションｐの２つのトリップ間の最小変更時間

を加えたことに対応する）を（好ましくは、２つとも）計算することを含む。 FIG. 4 generally describes a feasible transfer seat pretreatment method 403 received in step 402, wherein the method 403 is between two stations of the multimodal transportation network and within the multimodal transportation network. _{For each station pt} ⁱ of the origin trip t, first in step 404, for each station _pt ⁱ of the origin trip t, with all traffic modes of the multimodal transportation network at such station _pt ^i. Related earliest arrival time

And / or the earliest change time

And that the value is "initialized", the next, at step 406, at least one transfer of the set of possible switching to reachable station p _u ^j on the target trip u (and, preferably For each feasible transfer), the earliest arrival time at each station on the target trip after the reachable station (ie, station _pu ^j on trip u with k> j).

And / or the earliest change time

(Change time of station p

Is generally the earliest arrival time of such a station p

Minimum change time between two trips of the corresponding station p

Includes calculating (preferably both) (corresponding to the addition of).

In the pretreatment, adopting a subsequent (later) transfer for each origin trip cannot improve the arrival time and / or the number of transfers in the solution, so each at a given station on the target route. Only the earliest feasible transfer on the target trip of the route is considered. Then, at stage 407, all feasible sets of transfers (before being output for further processing) are optional in the network compared to previously added transfers for the current origin trip. It is reduced by keeping the relevant transfer in the search graph only if you want to improve the arrival time at the stop point of.

および／または最先の変更時刻

を有するように提案する。言い換えれば、可能な交通モードが存在することにより、それだけステーションで最先の到着／変更時刻の多くの値が存在するようになり、各値は交通モードに具体的に関連する。 The pretreatment method 403 is the earliest arrival time according to the traffic mode.

And / or the earliest change time

Suggest to have. In other words, the existence of possible traffic modes means that there are many values of the earliest arrival / change times at the station, and each value is specifically related to the traffic mode.

Preferably, the earliest arrival / change time values associated with a given traffic mode in a multimodal traffic network are the earliest arrivals / or when using only the traffic mode of origin trip t. Corresponds to the change time. In fact, the traffic modes of trips t and u must be allowed for such transfers to occur. Such a method contrasts with other methods in which the earliest arrival / change time is defined independently of the traffic mode used.

でモードｍおよび／またはオリジントリップｔのモードｍ_ｔだけを使用するステーションｐの最先の到着／変更時刻

が計算される。現実的に、ターゲットトリップｕを考慮するとき、計算される最先の到着／変更時刻の値は、ターゲットトリップｕによって使用された交通モードと関連したものとなる。 For example, if the M set of possible transportation mode (transportation mode and m _t is associated with a trip t),

In mode m and / or origin trip t mode m _t only the earliest arrival / modification time of the station p use of

Is calculated. Realistically, when considering the target trip u, the earliest arrival / change time value calculated will be associated with the traffic mode used by the target trip u.

Therefore, at step 407, the transfer is excluded only if it does not provide any improvement for any of the earliest arrival / change time values calculated for the origin trip t. become. That is, if it is determined that the arrival time and / or change time associated with such a traffic mode is not improved by the traffic (or the trip of the first and the destination) for each traffic mode. Only if the traffic modes are the same and there is no improvement for either mode) will they be excluded from the feasible set of transfers. In other words, if there is a station on the target trip u with an improved earliest arrival / change time (or a station adjacent to such a station on the target trip u), the transfer is maintained.

This prevents pruning of transfers that improve the earliest arrival time and / or the earliest change time for one mode, but not for another mode.

Checking the arrival and change time values at the station for each mode ensures that all transfers that can belong to the optimal solution were maintained by preprocessing.

It is noted that only the pruning portion of the pretreatment is changed at the station based on the improvement of the arrival / change time, and therefore the well-known pretreatment principle can be maintained as it is.

In fact, the algorithm 502 shown in FIG. 6 may be used to prune a given feasible transfer set T and a possible transfer mode set M.

から繰り返し減少する）、スケジュールの到着時刻（スケジュールによって定義されたように、オリジントリップｔのｉ^ｔｈステーションｐ_ｔ ^ｉの到着時刻は

と表現される）から最先の到着／変更時刻を初期化し、乗り換えによって該当のステーションからすべての可能な隣り合うステーションｑに到着するようにすることである。 In Algorithm 502, the idea of pruning is preferably to start pruning from the last station of the schedule for each origin trip t (i value is).

From repeatedly decreasing), as defined by the arrival time (schedule of schedule, i ^th station p _t ⁱ arrival time of the origin trip t is

It is to initialize the earliest arrival / change time from (expressed as) so that it arrives at all possible adjacent stations q from the corresponding station by transfer.

は（第１交通モードの関数であって、通常は徒歩デュレーションである）ステーションｐおよびステーションｑ間の乗り換えデュレーションを表現するために使用される。結果的に、これは、これらのステーションに対して最先の到着および変更時間を初期化する。 By "adjacent (Neighboring)", uses that itself becomes reachable by an additional feasible transfer from the station _p ^{t i,} i.e., the first traffic mode (e.g., by walking route of the pedestrian) It means that it will be possible to arrive.

Is used to represent the transfer duration between station p and station q (which is a function of the first traffic mode and is usually a walking duration). As a result, this initializes the earliest arrival and modification times for these stations.

が実現可能になるように（好ましくは、ｕが、

が実現可能になる該当の路線の最先の（ｅａｒｌｉｅｓｔ）トリップｖとなるように）、順にターゲットトリップｕおよびこれらの隣り合うステーションｕのよりも多くのステーションｐ_ｕ ^ｋに到着するようにスキャンされ、（再び、隣り合うステーションｑは、ターゲットトリップｕのステーションｐ_ｕ ^ｋからの追加的な実現可能な乗り換えによって到着可能となるステーションとなる）、または／追加的に既に到着されたステーションの最先の到着／変更時間をアップデートするようにスキャンされる。交通モードが変更されると、到着可能なステーション（ｐ_ｕ ^ｋおよび／またはｑ）に対し、ターゲットトリップｕの運送ボードと関連する値

だけがアップデートされる。アップデートは、与えられた交通モードに対して最先の到着および／または変更時刻の現在の値を、乗り換えを使用することがオリジントリップｔおよび以前に維持された乗り換えに比べて改善に繋がるときに計算された値に代替されることを意味する。比較は、改善（および、これによるアップデート）が発生するか否かを知るためになされてよい。ブーリアンキープ（Ｂｏｏｌｅａｎ ｋｅｅｐ）が、少なくとも１つの改善が発生したかをモニタリングするために使用されてよい。 Next, each target trip u transfers

(Preferably u,

So it becomes the earliest (earliest) trip v of the corresponding line becomes feasible), which sequentially scanned to arrive at the target trip u and many stations p _u ^k than the station u adjacent thereof (again, the adjacent station q is a station to be reachable by an additional feasible transfer from station p _u ^k of the target trip u), or / earliest additionally stations already arrived Scanned to update arrival / change times. When the transportation mode is changed, for reachable station (p _u ^k and / or q), the value associated with the transportation board of the target trip u

Only will be updated. The update is when the current value of the earliest arrival and / or change time for a given traffic mode leads to an improvement over the origin trip t and previously maintained transfers using transfers. Means to be replaced by the calculated value. Comparisons may be made to see if improvements (and updates caused by them) will occur. A Boolean keep may be used to monitor if at least one improvement has occurred.

が交通モードを変更しない（言わば、トリップｔおよびｕが同じモードである）場合、オリジントリップｔのモードｍ_ｔがｔからの乗り換えを考慮するときに必ず許容されるため、

に対してもアップデートされてよい。 a _{m t} = m _u, ie, transfer

There does not change the traffic mode (so to speak, trip t and u are the same mode) when, for always acceptable when the mode m _t of origin trip t is considering transfer from t,

May be updated for.

According to the second aspect shown in FIGS. 4 and 5, the method 410 calculates at least one itinerary from the departure point, arrival point, and departure time for the earliest arrival time query received in step 409.

As mentioned above, each itinerary is defined as a sequence of transfers from a set of possible trips within a multimodal transportation network and from a set of feasible transfers within a multimodal transportation network. Includes the main part of the modal transportation network.

What is special is that the itinerary is limited to a combination of possible traffic modes of the multimodal traffic network, eg, the traffic mode selected by the user on the client device 2b of FIG. 1 using the user interface 23b. It is a point.

Implemented by the data processor 11 of the server 1 to allow any combination of traffic modes, stage 412 preprocesses a set of feasible transfers within a multimodal traffic network by means of the first aspect. Get a subset of feasible transfers that are compatible with any combination of selected traffic modes.

It should be noted that only by changing the preprocessing, in particular, the subsequent routing algorithm, which is the TB algorithm, can be applied thereafter. The only difference is that at the time of the query, only acceptable trips and transfers between trips (ie, those received at step 408, compatible with the selected traffic mode) should be considered for the request. That is the point. In fact, this preprocessing easily provides smarter pruning of transfers, thus allowing routing algorithms to handle any combination of traffic modes in a reliable manner. More specifically, preprocessing will be useful for any query with any set of authorized traffic modes, transfer will not be pruned, and therefore some optimal solutions will not be lost. Guarantee to do so.

As mentioned above, the TB algorithm (or any other suitable routing algorithm) is a set L of routes that can reach the destination and the earliest trip that can arrive from the first departure point. Begins with the initialization stage in which the set of is calculated. In other words, at stage 414, the set of possible first trips within the multimodal transportation network, executed by the data processor 11 of server 1 or the data processor 21b of client device 2b, is determined and possible as a function of origin. The final set of trips is determined as a function of the destination. The departure time and / or the departure time range (for the query that is the profile) (for the earliest arrival time query) is the origin trip and / or the origin trip (for the latest departure time query) to determine the final trip. It should also be taken into account when determining arrival times.

As mentioned above, the method may also be considered in the context of the extension of the TB algorithm that constitutes the latest departure time query, where the desired arrival time is given instead of the start time, and after and after the start time. The earliest possible arrival times prior to the arrival time of are both given as secondary criteria used for the break tie.

The initialization step may be performed by any well-known method.

At step 414, a well-known suitable routing optimization algorithm such as TB may be performed based on a set of first trips and last trips.

Only trips from a set of trips possible using the selected traffic mode 408 and transfers from a subset of feasible transfers between trips 412 (which is a subset of all possible traffic modes in a multi-modal traffic network). However, it may be considered in step 414. Keep in mind that the choice of traffic mode combination is performed at this stage.

Preferably, some requirements may be performed to select a plurality of optimal itineraries, potentially corresponding to different combinations of selected traffic modes.

The itinerary selected is preferably optimal for the criteria of arrival time, as described above, and preferably for additional criteria such as the number of transfers.

For the latest departure time query, the same set of transfers for the earliest arrival time query may be used in the search.

For example, in the TB algorithm, each earliest trip may be considered only once, starting at the station with the lower index in the station sequence for that trip. For each iteration, additional trips are adopted as each solution for attempting and reaching the final trip.

In an alternative embodiment, a feasible transfer pre-processed set (eg, for a transfer bus route) may be used to build and evaluate a timetable. More preferably, such timetables built using a set of feasible transfers may be combined to avoid long wait times between trips, providing robustness in case of delay. It can be evaluated and therefore the missed transfer can be minimized.

Also in other embodiments, the feasible transfer pre-processed set is to manage transportation network resources (eg, which vehicle on the route should wait if some vehicles on the route are delayed). May be used (to support the decision).

または最先の変更時刻

の値を計算し、（ｂ）前記オリジントリップｔ上のステーションｐ_ｔ ^ｉからターゲットトリップｕ上の到着可能なステーションｐ_ｕ ^ｊへの実現可能な乗り換えのセットのうちの少なくとも１つの乗り換え

に対し、前記到着可能なステーションｐ_ｕ ^ｊ以降に前記ターゲットトリップｕの各ステーションｐ_ｕ ^ｋ＞ｊで前記ターゲットトリップｕによって使用される前記マルチモーダル交通ネットワークの交通モードｍ_ｕと具体的に関連する最先の到着時刻

または最先の変更時刻

の値、あるいは前記ターゲットトリップｕによって使用される前記マルチモーダル交通ネットワークの交通モードｍ_ｕが前記オリジントリップｔによって使用される前記マルチモーダル交通ネットワークの交通モードｍ_ｔと等しければ、前記マルチモーダル交通ネットワークのすべての交通モードｍと関連する最先の到着時刻

または最先の変更時刻

の値を計算し、（ｃ）最先の到着時刻

または最先の変更時刻

の各計算された値が前記乗り換え

によって改善されないと判定された場合にのみ、前記実現可能な乗り換えのセットから前記乗り換え

を排除する。 For each trip t (hereinafter referred to as origin trip) in the multimodal transportation network between two stations of the multimodal transportation network, a set of feasible transfers within the multimodal transportation network of a predetermined station is provided. a method of pretreating, (a) for each station _p ^{t i} of the origin trip t, appropriate station _p ^{t i} in the multi-modal transport all network traffic mode m and related earliest (earliest) arrival Times of Day

Or the earliest change time

The values were calculated, (b) at least one transfer of the set of the feasible transfer from station p _t ⁱ on the origin trip t to reachable station p _u ^j on the target trip u

To, transportation mode m u and specifically related to the multimodal transportation network to be used by the target trip u at each station p u k> j of the target trip u to the reachable station p u j later First arrival time

Or the earliest change time

Equal value or a traffic mode m _t of the multimodal transportation network traffic mode m _u of the multimodal transportation network to be used is used by the origin trip t by the target trip u, the multimodal transportation network First arrival time associated with all traffic modes m

Or the earliest change time

Calculate the value of (c) Earlier arrival time

Or the earliest change time

Each calculated value of is the transfer

Only if it is determined that the transfer is not improved by the above transfer from the feasible transfer set.

To eliminate.

The method described above further initializes the earliest arrival time or the earliest change time as a function of the schedule.

The value of the multi-modal transportation network traffic mode m _u and specifically related to the earliest arrival time or earliest modification time, the multimodal transportation network to be used by the traffic mode m _u or the origin trip t corresponding to the earliest arrival time or the earliest of the change time when only the use of transportation mode m _t.

The method is further performed for each transfer of a set of feasible transfers, which is an earliest transfer from a station on the origin trip to any reachable station on any target trip. ..

The method repeatedly further considers the transfer from each continuous station of the origin trip as it travels from the last station to the first station on the origin trip.

The earliest arrival time and / or the earliest change time is also calculated for each adjacent station of each station on the origin trip and the target trip after the reachable station.

The method is a trip from a set of possible trips using the selected traffic mode of the itinerary having the main part of the last trip belonging to the set of possible last trips from the first trip belonging to the set of possible first trips. At least one optimal by the earliest arrival time and number of transfers, or the latest departure time and number of transfers, when considering only transfers from a subset of feasible transfers between the considered trips. Further runs a routing optimization algorithm to build the itinerary.

The routing optimization algorithm may calculate Pareto front. The routing optimization algorithm adopts one additional trip of a set of modes selected from each iteration based on a pre-computed transfer set to obtain the earliest arrival time and transfer within the multimodal network. For the number of times, or the latest departure time and number of transfers, at least one optimal solution per element within the Pareto efficiency may be further calculated.

In the method of calculating at least one itinerary from the departure point to the arrival point, each itinerary is a main part within the multimodal transportation network of a given station (trips from a set of possible trips within the multimodal transportation network, said. And defined as a sequence of transfers from a set of feasible transfers within the multimodal transportation network), the method of which is (a) the multimodal transportation to obtain a subset of feasible transfers. Preprocessing the set of feasible transfers in the network, (b) the set of first trips possible as a function of the departure point, and the final trip possible as a function of the destination in the multimodal transportation network. And (c) use the selected traffic mode of the itinerary having the main part of the last trip belonging to the set of possible last trips to the first trip belonging to the set of possible first trips. When considering only trips from a set of possible trips and only transfers from a subset of feasible transfers between considered trips, the earliest arrival time and number of transfers, or the latest departure time and A routing optimization algorithm is executed to construct at least one optimal itinerary based on the number of transfers.

The routing optimization algorithm calculates Pareto front. The routing optimization algorithm adopts one additional trip of a set of modes selected from each iteration based on a pre-computed transfer set, thereby making the earliest arrival time and transfer within the multimodal network. For the number of times, or the latest departure time and number of transfers, at least one optimal solution per element within the Pareto efficiency may be further calculated.

または最先の変更時刻

の値を計算し、（ｂ）前記オリジントリップｔ上のステーションｐ_ｔ ^ｉからターゲットトリップｕ上の到着可能なステーションｐ_ｕ ^ｊへの実現可能な乗り換えのセットのうちの少なくとも１つの乗り換え

に対し、前記到着可能なステーションｐ_ｕ ^ｊ以降に前記ターゲットトリップｕの各ステーションｐ_ｕ ^ｋ＞ｊで、前記ターゲットトリップｕによって使用される前記マルチモーダル交通ネットワークの交通モードｍ_ｕと具体的に関連する最先の到着時刻

または最先の変更時刻

の値、あるいは前記ターゲットトリップｕによって使用される前記マルチモーダル交通ネットワークの交通モードｍ_ｕが前記オリジントリップｔによって使用される前記マルチモーダル交通ネットワークの交通モードｍ_ｔと等しければ、前記マルチモーダル交通ネットワークのすべての交通モードｍと関連する最先の到着時刻

または最先の変更時刻

の値を計算し、（ｃ）最先の到着時刻

または最先の変更時刻

の各計算された値が前記乗り換え

によって改善されないと判定された場合にのみ、前記実現可能な乗り換えのセットから前記乗り換え

を排除し、（ｄ）前記マルチモーダル交通ネットワークの少なくとも１つの旅程を計算するために前記実現可能な乗り換えのセットを出力する。 In a computer program product that preprocesses a set of feasible transfers within a multimodal transportation network of a given station to calculate at least one itinerary from departure to arrival, said computer program product processes. is running on the computer to execute, the process is associated with all the traffic mode m in (a) for each station p _t ⁱ of origin trip t, wherein the appropriate stations p _t ⁱ multimodal transportation network Earliest arrival time

Or the earliest change time

The values were calculated, (b) at least one transfer of the set of the feasible transfer from station p _t ⁱ on the origin trip t to reachable station p _u ^j on the target trip u

To, in each station p u k> j target trip u, the multimodal transportation transport mode m u and specifically related network used by the target trip u in the subsequent reachable station p u j First arrival time

Or the earliest change time

Equal value or a traffic mode m _t of the multimodal transportation network traffic mode m _u of the multimodal transportation network to be used is used by the origin trip t by the target trip u, the multimodal transportation network First arrival time associated with all traffic modes m

Or the earliest change time

Calculate the value of (c) Earlier arrival time

Or the earliest change time

Each calculated value of is the transfer

Only if it is determined that the transfer is not improved by the above transfer from the feasible transfer set.

(D) Output the feasible set of transfers to calculate at least one itinerary of the multimodal transportation network.

The process further initializes the earliest arrival time or the earliest modification time as a function of the schedule.

The value of the multi-modal transportation network traffic mode m _u and specifically related to the earliest arrival time or earliest modification time, the multimodal transportation network to be used by the traffic mode m _u or the origin trip t when only the use of transportation mode m _t, corresponding to the arrival time or the earliest of the change time of the earliest.

For each transfer in a set of feasible transfers, the process is an earliest transfer from a station on the origin trip to any reachable station on any target trip (b) and (C) is executed repeatedly.

As the process travels the stations on the origin trip from the last station to the first station, it further iteratively considers the transfer from each continuous station of the origin trip.

The process further calculates the earliest arrival time and / or the earliest modification time at each adjacent station of each station on the origin trip and the target trip after the reachable station.

The computer program product is a computer-readable medium.

A computer program product that preprocesses a set of feasible transfers within a multimodal transportation network of a given station to calculate at least one itinerary from departure to arrival, said computer program product. Performed on a computer to perform the process, the process preprocesses the set of feasible transfers within the multimodal transportation network to obtain (a) a subset of feasible transfers. (B) Within the multimodal transportation network, the set of possible first trips as a function of the departure point and the set of final trips possible as a function of the destination are determined, and (c) the set of possible first trips. Of the itineraries having the main part of the last trip belonging to the set of possible last trips from the first trip belonging to, only the trips from the set of possible trips using the selected traffic mode were considered and considered. Optimal routing to build at least one optimal itinerary with the earliest arrival time and number of transfers, or the latest departure time and number of transfers, when only transfers from a subset of feasible transfers between trips are considered. Executes a routing optimization algorithm.

The routing optimization algorithm arrives first in a multimodal network by adopting one additional trip of a set of modes selected from each iteration based on a Pareto set and a pre-computed transfer set. Calculate at least one optimal solution per element within Pareto efficiency for the time and number of transfers, or the latest departure time and number of transfers.

The computer program product is a computer-readable medium.

It is understood that features and functions that differ from the disclosed embodiments as described above, and / or variants of these alternatives, may preferably be combined with many other systems and / or applications. Will. Also, current unanticipated and / or unanticipated alternatives, changes, modifications, and / or improvements thereof may be made subsequently by a person of ordinary knowledge in the art, which is described and attached above. It is intended to be covered by the claims of.

U.S. Patent Application 16/700,096

Sacha Witt. Trip-based public transport routing. In N. Bansal and I. Fennel, editors, ESA 2015, Computer Science Lecture Note Volume 9294, Berlin, Heidelberg 2015. Springa Vassilissa Lehoux and Darko Drakulić, 2019. Mode Personalization in Trip-Based Transit Routing. 19th Symposium on Traffic Modeling, Optimization, and Algorithmic Approaches to Systems (ATMOS 2019). OASIcs (Open Access Systems in Informatics), Volume 75, Pages 13: 1-13: 15

Claims (44)

A method of preprocessing each trip t in a multimodal transportation network between two stations of a multimodal transportation network, i.e., a set of feasible transfers within the multimodal transportation network of a given station for an origin trip. hand,
(A) said to each station p _t ⁱ of origin trip t, the corresponding station p _t ⁱ in the multi-modal transportation and all modes of transport m and related to the earliest arrival time of the network

Or the earliest change time

At the stage of calculating the value of,
(B) at least one transfer of the set of the feasible transfer from station p _t ⁱ on the origin trip t to reachable station p _u ^j on the target trip u

To, in each station p u k> j target trip u, the multimodal transportation transport mode m u and specifically related network used by the target trip u in the subsequent reachable station p u j First arrival time

Or the earliest change time

Equal value or a traffic mode m _t of the multimodal transportation network traffic mode m _u of the multimodal transportation network to be used is used by the origin trip t by the target trip u, the multimodal transportation network First arrival time associated with all traffic modes m

Or the earliest change time

At the stage of calculating the value of,
(C) First arrival time

Or the earliest change time

Each calculated value of is the transfer

Only if it is determined that the transfer is not improved by the above transfer from the feasible transfer set.

A method comprising the steps of eliminating the above and (d) outputting the set of feasible transfers to calculate at least one itinerary of the multimodal transportation network. The method of claim 1, further comprising the step of initializing the earliest arrival time or the earliest modification time as a function of the schedule. The value of the multi-modal transportation network traffic mode m _u and specifically related to the earliest arrival time or earliest modification time, the multimodal transportation network to be used by the traffic mode m _u or the origin trip t when using only the traffic mode m _t, corresponding to the arrival time or the earliest modification time of the earliest method of claim 1. The value of the multi-modal transportation network traffic mode m _u and specifically related to the earliest arrival time or earliest modification time, the multimodal transportation network to be used by the traffic mode m _u or the origin trip t when using only the traffic mode m _t, corresponding to the arrival time or the earliest modification time of the earliest method of claim 2. Repeat (b) and (c) for each transfer in a set of feasible transfers that is the earliest transfer from a station on the origin trip to any reachable station on any target trip. The method of claim 1, further comprising a step. Repeat (b) and (c) for each transfer in a set of feasible transfers that is the earliest transfer from a station on the origin trip to any reachable station on any target trip. The method of claim 2, further comprising steps. Repeat (b) and (c) for each transfer in a set of feasible transfers that is the earliest transfer from a station on the origin trip to any reachable station on any target trip. The method of claim 3, further comprising steps. Repeat (b) and (c) for each transfer in a set of feasible transfers that is the earliest transfer from a station on the origin trip to any reachable station on any target trip. The method of claim 4, further comprising steps. The method of claim 5, further comprising the step of repeatedly considering transfers from each successive station of the origin trip when patrolling the station on the origin trip from the last station to the first station. The method of claim 6, further comprising the step of repeatedly considering transfers from each successive station of the origin trip when patrolling the station on the origin trip from the last station to the first station. The method of claim 7, further comprising the step of repeatedly considering transfers from each successive station of the origin trip when patrolling the station on the origin trip from the last station to the first station. The method of claim 8, further comprising the step of repeatedly considering transfers from each successive station of the origin trip when patrolling the station on the origin trip from the last station to the first station. The method of claim 1, wherein the earliest arrival time and / or the earliest change time is also calculated at the station next to each station on the origin trip and the target trip after the reachable station. .. The method of claim 2, wherein the earliest arrival time and / or the earliest change time is also calculated at the station next to each station on the origin trip and the target trip after the reachable station. .. The method of claim 3, wherein the earliest arrival time and / or the earliest change time is also calculated at the station next to each station on the origin trip and the target trip after the reachable station. .. The method of claim 4, wherein the earliest arrival time and / or the earliest change time is also calculated at the station next to each station on the previous origin trip and the target trip after the reachable station. .. The method of claim 5, wherein the earliest arrival time and / or the earliest change time is also calculated at the station next to each station on the origin trip and the target trip after the reachable station. .. The method of claim 6, wherein the earliest arrival time and / or the earliest change time is also calculated at the station next to each station on the origin trip and the target trip after the reachable station. .. The method of claim 7, wherein the earliest arrival time and / or the earliest change time is also calculated at the station next to each station on the origin trip and the target trip after the reachable station. .. The method of claim 8, wherein the earliest arrival time and / or the earliest change time is also calculated at the station next to each station on the origin trip and the target trip after the reachable station. .. The method of claim 9, wherein the earliest arrival time and / or the earliest change time is also calculated at the station next to each station on the origin trip and the target trip after the reachable station. .. 10. The method of claim 10, wherein the earliest arrival time and / or the earliest change time is also calculated at the station next to each station on the origin trip and the target trip after the reachable station. .. 11. The method of claim 11, wherein the earliest arrival time and / or the earliest change time is also calculated at the station next to each station on the origin trip and the target trip after the reachable station. .. 12. The method of claim 12, wherein the earliest arrival time and / or the earliest change time is also calculated at the station next to each station on the origin trip and the target trip after the reachable station. .. (E) Only trips from the set of possible trips with the selected traffic mode of the itinerary having the main part from the first trip belonging to the set of possible first trips to the last trip belonging to the set of possible last trips. At least one optimal itinerary by the earliest arrival time and number of transfers, or the latest departure time and number of transfers, when considering only transfers from a subset of feasible transfers between the considered trips. The method of claim 1, further comprising performing a routing optimization algorithm to construct. 25. The method of claim 25, wherein the routing optimization algorithm calculates Pareto efficiency. The routing optimization algorithm adopts one additional trip of a set of modes selected from each iteration based on a pre-computed transfer set, thereby making the earliest arrival time and transfer within the multimodal network. 26. The method of claim 26, wherein at least one optimal solution per factor within said Pareto efficiency is calculated for the number of times, or the latest departure time and number of transfers. A method of calculating at least one itinerary from departure to arrival, where each itinerary is from the main part of a given station's multimodal transportation network (from the set of possible trips within said multimodal transportation network). The itinerary is defined as a sequence of transfers from a trip and a feasible set of transfers within the multimodal transportation network), and the itinerary is a transportation selected from among the possible transportation modes of the multimodal transportation network. Limited to the combination of modes,
(A) The step of preprocessing the set of feasible transfers within the multimodal transportation network to obtain a subset of feasible transfers.
(B) Within the multimodal transportation network, a step of determining a set of possible first trips as a function of said origin and a set of possible final trips as a function of said destination, and (c) said possible first. Of the itineraries having the main part from the first trip belonging to the set of trips to the last trip belonging to the set of possible last trips, only trips from the set of possible trips using the selected traffic mode are considered. Build at least one optimal itinerary by the earliest arrival time and number of transfers, or the latest departure time and number of transfers, when considering only transfers from a subset of feasible transfers between the considered trips. A method that includes the steps of running a routing optimization algorithm for. 28. The method of claim 28, wherein the routing optimization algorithm calculates Pareto efficiency. The routing optimization algorithm adopts one additional trip of a set of modes selected from each iteration based on a pre-computed transfer set to obtain the earliest arrival time and transfer within the multimodal network. 29. The method of claim 29, which calculates at least one optimal solution per factor within said Pareto efficiency for the number of times, or the latest departure time and number of transfers. A computer program that preprocesses a set of feasible transfers within a multimodal transportation network at a given station to calculate at least one itinerary from departure to arrival, which computer program processes. Runs on the computer to run,
The process
(A) for each station p _t ⁱ of origin trip t, the corresponding station p _t ⁱ in the multi-modal transportation and all modes of transport m and related to the earliest arrival time of the network

Or the earliest change time

At the stage of calculating the value of,
(B) at least one transfer of the set of the feasible transfer from station p _t ⁱ on the origin trip t to reachable station p _u ^j on the target trip u

To, in each station p u k> j target trip u, the multimodal transportation transport mode m u and specifically related network used by the target trip u in the subsequent reachable station p u j First arrival time

Or the earliest change time

Equal value or a traffic mode m _t of the multimodal transportation network traffic mode m _u of the multimodal transportation network to be used is used by the origin trip t by the target trip u, the multimodal transportation network First arrival time associated with all traffic modes m

Or the earliest change time

At the stage of calculating the value of,
(C) First arrival time

Or the earliest change time

Each calculated value of is the transfer

Only if it is determined that the transfer is not improved by the above transfer from the feasible transfer set.

A computer program comprising the steps of eliminating the above and (d) outputting the set of feasible transfers to calculate at least one itinerary of the multimodal transportation network. 31. The computer program of claim 31, wherein the process further comprises, as a function of the schedule, a step of initializing the earliest arrival time or the earliest modification time. The value of the multi-modal transportation network traffic mode m _u and specifically related to the earliest arrival time or earliest modification time, the multimodal transportation network to be used by the traffic mode m _u or the origin trip t Transport mode when m _t only use, corresponds to the earliest arrival time or earliest modification time, a computer program according to claim 32. (B) and (c) are repeatedly executed for each transfer of a set of feasible transfers, which is the earliest transfer from a station on the origin trip to any reachable station on any target trip. The computer program according to claim 31. 32. The computer of claim 32, wherein (b) and (c) repeatedly consider transfers from each successive station of the origin trip when patrolling the stations on the origin trip from the last station to the first station. program. 33. The earliest arrival time and / or the earliest change time is calculated at the station next to each station on the origin trip and the target trip after the reachable station. Computer program. The process is (e) a set of possible trips using the selected traffic mode of the itinerary having the main part of the last trip belonging to the set of possible last trips to the first trip belonging to the set of possible first trips. At least by the earliest arrival time and number of transfers, or the latest departure time and number of transfers, when considering only trips from and only transfers from a subset of feasible transfers between the considered trips. 31. The computer program of claim 31, further comprising performing a routing optimization algorithm to build one optimal itinerary. 37. The computer program of claim 37, wherein the routing optimization algorithm calculates Pareto efficiency. The routing optimization algorithm adopts one additional trip of a set of modes selected from each iteration based on a pre-computed transfer set to achieve the earliest arrival time and transfer within the multimodal network. 38. The computer program of claim 38, which calculates at least one optimal solution per element within said Pareto efficiency for the number of times, or the latest departure time and number of transfers. The computer program according to claim 31, wherein the computer program is a computer-readable medium. A computer program that preprocesses a set of feasible transfers within a multimodal transportation network at a given station to calculate at least one itinerary from departure to arrival, which computer program executes the process. Run on your computer to
The process
(A) The step of preprocessing the set of feasible transfers within the multimodal transportation network to obtain a subset of feasible transfers.
(B) Within the multimodal transportation network, a step of determining a set of possible first trips as a function of said origin and a set of possible final trips as a function of said destination, and (c) said possible first. Of the itineraries having the main part from the first trip belonging to the set of trips to the last trip belonging to the set of possible last trips, only the trips from the set of possible trips using the selected traffic mode are considered. Build at least one optimal itinerary by the earliest arrival time and number of transfers, or the latest departure time and number of transfers, when considering only transfers from a subset of feasible transfers between the considered trips. A computer program that includes the steps to execute a routing optimization algorithm for. 41. The computer program of claim 41, wherein the routing optimization algorithm calculates Pareto efficiency. The routing optimization algorithm adopts one additional trip of a set of modes selected from each iteration based on a pre-computed transfer set to achieve the earliest arrival time and transfer within the multimodal network. 42. The computer program of claim 42, which calculates at least one optimal solution per element within said Pareto efficiency for the number of times, or the latest departure time and number of transfers. The computer program according to claim 41, wherein the computer program is a computer-readable medium.

Images