HK1179018B - Journey planning in public transportation networks - Google Patents

Description

Travel planning in public transportation networks

Technical Field

The present application relates to travel planning, in particular in public transportation networks.

Background

With the push of map services, there is abundant research on determining travel in a transportation network. Many studies have focused on calculating driving directions on a road network. Existing computer programs, known as road map programs, provide digital maps, typically with an exhaustive road network up to the city-street level. Typically, a user may enter a location and the road map program will display an on-screen map of the selected location. Several existing road map products typically include the ability to calculate an optimal route between two locations. In other words, the user can enter two locations and the road map program will calculate the direction of travel from the source location to the destination location. The direction is typically based on distance, travel time, etc. Computing the optimal route between locations may require significant computational time and resources.

Some road map programs use a variant of the well-known method attributed to Dijkstra to calculate the shortest route. Note that in this case, "shortest" means "lowest cost" because each road segment is assigned a cost or weight that need not be directly related to the length of the road segment. By varying the way the cost of each road is calculated, the shortest path can be generated for the fastest, shortest or preferred route. However, the original method of Dijkstra is not always effective in practical applications due to the large number of positions and possible paths that are scanned. In contrast, many known road mapping programs use a heuristic variant of the Dijkstra's method.

Recent developments in road map algorithms use a two-stage process that includes a preprocessing stage and a query stage. During the pre-processing stage, the graphic or map undergoes offline processing in order to more efficiently complete subsequent real-time queries between any two destinations on the graphic. The pre-processing phase may take several minutes (or even hours) and compute some helper data, which is then used to speed up the query. Examples of known preprocessing algorithms use geographic information, hierarchical decomposition, and a-search combined with landmark distances.

Routing in public transportation networks (e.g., planning a trip between two points in a public transportation system starting at a given time) may appear seemingly large or small, but this problem becomes significantly more difficult to do. Technologies developed for highway networks help little for public transportation. There are two reasons for this. First, public transportation networks do not have the strong hierarchical nature of a highway network where almost all long distance travel is concentrated on major highways. Second, public transportation networks are time-dependent in nature (e.g., buses and trains have schedules that are considered in determining the shortest or lowest cost trip). Third, the number of transfers needs to be considered in addition to travel time. This is typically done by reporting more than one trip. In addition, public transportation systems are dynamic, with frequent false positives and cancellations. Unlike a road network, a small miss point may have a large impact on the resulting route, as a missed connection may result in waiting hours at a transit station or stop (e.g., a train or bus stop). There is no known conventional technique that can efficiently handle the above-described features in a transportation network of a large urban area.

Disclosure of Invention

Techniques are provided for determining optimal travel in a public transportation network. The determination of Pareto best travel from one site to another in a public transportation network uses conditions such as travel time and minimum transfers.

In one implementation, a technique for dual-condition trip planning in a public transportation network operates in a round-robin (K cycles at most) fashion, with arrival times for sites that can be reached until K trips being calculated after a cycle K (K ≦ K).

In one implementation, optimization techniques may be used. Such techniques include iterating over the route, marking, tightening stop conditions, pruning, parallel, and post-processing to minimize the total time of transit.

This summary is provided to introduce a selection of concepts in a simplified form that are further described below in the detailed description. This summary is not intended to identify key features or essential features of the claimed subject matter, nor is it intended to be used to limit the scope of the claimed subject matter.

Drawings

The foregoing summary, as well as the following detailed description of illustrative embodiments, is better understood when read in conjunction with the appended drawings. For the purpose of illustrating the embodiments, there is shown in the drawings exemplary constructions of the embodiments; however, the embodiments are not limited to the specific methods and instrumentalities disclosed. In the drawings:

FIG. 1 illustrates an example of a computing environment in which aspects and embodiments may be utilized;

FIG. 2 is an operational flow of an implementation of a method of determining travel in a public transportation network;

FIG. 3 is an operational flow of another implementation of a method of determining travel in a public transportation network;

FIG. 4 is an operational flow of an optimization usable in an implementation of a method of determining travel in a public transportation network, such as one of FIG. 3;

FIG. 5 is a diagram illustrating various routes that may be scanned during a query;

FIG. 6 is another optimized operational flow usable in an implementation of a method of determining travel in a public transportation network;

FIG. 7 is an illustration of an example data structure that may be used in determining a trip in a public transportation network;

FIG. 8 is an illustration of another example data structure that may be used in determining a trip in a public transportation network; and

FIG. 9 illustrates an exemplary computing environment.

Detailed Description

FIG. 1 illustrates an example of a computing environment in which aspects and embodiments may be utilized. Computing device 100 includes a network interface card (not specifically shown) that facilitates communication over a communication medium. Example computing devices include Personal Computers (PCs), mobile communication devices, and the like. In some implementations, computing device 100 may comprise a desktop personal computer, workstation, laptop, PDA (personal digital assistant), smart phone, cellular phone, or any WAP-enabled device or any other computing device capable of interfacing directly or indirectly with a network. For example, computing device 100 of one example is described with respect to computing device 900 of FIG. 9.

The computing device 100 may communicate with the local area network 102 through a physical connection. Alternatively, the computing device 100 may communicate with the local area network 102 over a wireless wide area network or wireless local area network medium, or over other communication mediums. Although shown as a local area network 102, the network may be of various network types including the Public Switched Telephone Network (PSTN), cellular telephone networks (e.g., 3G, 4G, CDMA, etc.), and packet-switched networks (e.g., the internet). Any type of network and/or network interface may be used for the network.

As a result of the supported network media, a user of the computing device 100 can access network resources, typically through use of a browser application 104 running on the computing device 100. The browser application 104 facilitates communication with remote networks over, for example, the internet 105. One exemplary network resource is a map routing service 106 running on a map routing server 108. The map routing server 108 hosts (host) a database 110 of transportation sites, physical locations, and street addresses, as well as route information such as schedules, transfer information, transportation information, location information, adjacencies, distances, speed limits, and other relationships between stored locations.

A user of computing device 100 typically enters source and destination locations as query requests through browser application 104. The map routing server 108 receives the request and generates a shortest path from the source location to the destination location among the locations stored in the database 110. The map routing server 108 then sends the shortest path (e.g., a list of Pareto best trips between two locations) back to the requesting computing device 100. Alternatively, the map routing service 106 is hosted on the computing device 100, and the computing device 100 need not communicate with the local area network 102.

The Earliest Arrival (EABT) problem with limited transfers arises in travel planning for public transportation (also referred to herein as "public transport"). Given two sites v_sAnd v_t(source and destination locations, respectively) and a non-negative integer K, EABT being defined as a find from v_sTo v_tSo as to be on v_tThe arrival time of (b) is the problem of the earliest possible time and is subject to the additional constraint that the total number of individual journeys spent in this path is not more than K (i.e. the total number of transfers is at most K-1). There are many uses for the algorithm to solve the EABT problem and the techniques, processes and systems described herein are not meant to be limited to maps.

During the query phase, the user may wish to find a valid trip between two particular sites that is subject to the two conditions set forth above. The originating site, which may be referred to as the source location, is labeled v_sAnd the destination site may be referred to as a destination location (or target site), labeled v_t. The user can then specify their starting point (i.e. source location v)_s) And their destination location (v)_t）。

Existing techniques for solving the (P) EABT problem are typically based on processing stations one by one in chronological order (i.e., stations that arrive first are processed first). This requires a priority query. Since a station may be reached at different times depending on the number of transfers, the same station may be processed multiple times. If only the earliest arrival time is determined regardless of the number of transfers, a version of the time-dependent Dijkstra algorithm may be used, which guarantees that each site processes at most once.

In particular, typically, routing algorithms on public transportation networks use a collection of routes, and sites to build a graph, followed by some variant of the Dijkstra algorithm. This is effective enough when only travel time is minimized: the Dijkstra algorithm simply computes the single fastest way to reach each site in the graph. The algorithm becomes significantly less practical when the number of transfers is taken into account in addition to the travel time. In this case, the "best" way to reach any intermediate site is no longer unique. It is more advantageous to take a later bus through the stop if the later bus continues toward the destination (while the earlier bus goes elsewhere).

Unlike previous schemes, the techniques described herein are no longer based on Dijkstra's algorithm and do not require a priority queue. Instead of working on one site at a time, the techniques described herein use loops (rounds) and take into account both total travel time (the earlier the better the arrival) and the total number of transfers (the fewer the transfers the better). The technique determines and provides a Pareto best path based on these two conditions. As used herein, Pareto is best defined as a set of unmanaged paths. For example, if path a does not take more time and make no more transfers than path B, path a dominates path B. If multiple paths are associated with two conditions (time and number of transfers), only one of the paths may be returned by the techniques described herein.

Calculated until v is reached from the source position_sTo a destination location v_tThe path of at most K journeys (K-1 transfers) leaves no earlier than time τ. A cycle (at most K cycles) is used, wherein after cycle K, arrival times are calculated for those stations that can be reached for at most K journeys. Loop k determines the best path from the source to each site to make up to k-1 transfers at the same time (or determines that no such path exists). In other words, loop k calculates the fastest way to reach each site over at most k-1 transfers (i.e., taking at most k trips), and notes that some sites may not be reachable at all. On a typical transport network, a small number of cycles is sufficient to determine all Pareto best paths.

In one implementation, the input may be a schedule based schedule, source location (or start point) v_sDestination location (or target point) v_tDeparture time τ and an upper limit K on the number of transfers allowed (i.e. transfers of trains, buses, etc.). The output includes, for each value K ≦ K, leaving the source location v no earlier than the departure time τ_sTo arrive at the destination location v as early as possible_tAnd has no more than k-1 transfers of travel. Resolving the EABT may be used to determine a trip using the minimum number of transfers and may output a set of Pareto best trips, allowing the user to trade off between arrival time and number of transfers. As described further herein, loop-based techniques are used to address EABT based on the concept of slack routes in the network. In each cycle, arrival times may be calculated for stations that can be reached for exactly k-1 transfers along the route. The techniques described herein are not based on Dijkstra (looking at each route in the schedule at most once in each loop) and can be made faster with optimizations such as pruning rules and parallelism using a variety of kernels as described further below.

In one implementation, the public transportation network is modeled as follows. The input to the algorithm is a schedule-based schedule comprising a set of stations in the network, the set of journeys in the network during a certain time period, the set of routes in the network and the set of tradeoffs allowed. In particular toIn other words, V = { V = { V =₀，v₁，v₂，...，v_|V|-1Is the set of sites in the network. Each station corresponds to a different location where a person can board or board a vehicle (bus, tram, train, etc.). Typical examples are bus stations and train stations. T = { T = { (T)₀，t₁，t₂，...，t_|T|-1Is the set of journeys in the network during a certain period of time, typically a day or a week. A journey corresponds to a sequence of stations visited by a particular vehicle (train, bus, subway, etc.) along a route. It has an initial site, a final site, and several sites in between that may drop or get on. Each site in the journey is also associated with an arrival and departure time. R = { R =₀，r₁，r₂，...，r_|R|-1Is the set of routes in the network. A route consists of all trips sharing exactly the same sequence of stops. A typical example is a bus line in a bus network. A single route may correspond to several journeys (all following the same trajectory) during the day. Typically, there are many more trips than routes. C = { C₀，c₁，c₂，...，c_|C|-1Is the set of trades. Transfers are used to merge trips (walking) between stations (typically in nearby surrounding areas) to allow exchanges between transport vehicles. Each transfer consists of exactly one transfer with an associated constant travel time l (v)_i，v_j) Two sites v of_iAnd v_jAnd (4) forming.

In one implementation, the output produced by the route planning technique on the schedule-based schedule is a set of trips J = { J = { (J) }₀，...，j_|J|-1}. For example, each trip in the set corresponds to an alternative trip plan for a single query. The trip is defined as a sequence and transfer of journeys in the travel order. In addition, each trip in the sequence is associated with two stops corresponding to the boarding and disembarking points. Moreover, to form an effective output, the trip is consistent in the sense that: for any two subsequent items (journeys or transfers) along the journey, their sitesMust match and the departure time of the second item must be after the arrival time of the first item. Note that a trip with k trips has exactly k-1 transfers.

FIG. 2 is an operational flow of an implementation of a method 200 of determining travel in a public transportation network. At block 210, a query is received from, for example, a user. The query includes a source location, a destination location, and a departure time (e.g., the earliest departure time that the user wants to be away from the source location). Thus, at query time, the user enters the start and destination locations (e.g., using computing device 100), respectively, and the query (e.g., information about the start and destination sites) is sent to a map service (e.g., map routing service 106).

At 220, an integer K representing a maximum number of tours is received (e.g., from a user or from storage). At 230, a counter corresponding to the number of cycles k is initialized. For example, k is set equal to zero,

at 240, data representing the public transportation network is obtained, for example, by retrieval from storage or a user, generation using a schedule, and the like. Depending on the implementation, the data may represent more than one public transportation network. The technique used here takes as input a network with stations (each of which may be, for example, a train or subway station, a bus station, etc.). In addition, information about the itinerary and the route is used. A trip may be a sequential stop of individual buses or trains with scheduled departure and arrival times at each stop. A route is a collection of journeys with the same sequence of sites (possibly at different times of the day).

In one implementation, the algorithm takes as input a source location, a destination location, and a start time. One goal is to find all the non-dominated routes from the source to the destination (leaving at the start time or later) based on two conditions: the earliest arrival time and the least number of transfers. As defined above, route R1 is dominated by route R2 if route R1 neither arrives earlier nor makes fewer transfers. On a typical transportation network, the total number of such routes will be quite small, particularly since the route that usually has the least transfer is the route with the earliest arrival time.

This technique works in a cyclic fashion: loop k ensures that the fastest path from the source to each station (e.g., bus station, train station, etc.) in the network is found for at most k-1 transfers. Each loop consists of traversing each possible route at most once and updating the information of the sites along the route.

In one implementation, each site v maintains a series of labels L (v, k) representing the best known arrival times with exactly k-1 transfers at v. These values are initially set to infinity and L (v, k) is updated at the appropriate time during loop k. To update these values during cycle k, the algorithm goes through each route at most once. When analyzing a route at cycle k, the algorithm implicitly considers all possible paths that use the route after their last (i.e., k-1 st) transfer (i.e., the kth trip).

At 245, initialization is performed to set the arrival time at the start position of cycle 0 to the departure time requested by the user. At 250, a loop is executed for a corresponding number of loops k. For this loop, the best path is found from the start location to each other site in the network reachable using at most k-1 transfers (i.e., k journeys). The arrival times of the sites reachable by k-1 transfers are determined and a label is set for each site with the best known arrival time.

At 260, k is incremented (e.g., by 1) to increase the number of subsequent cycles. At 270 it is determined whether K is greater than the maximum number of cycles to be executed, K. If so, then at 280, the results that have been determined so far (i.e., Pareto best path) are output. The output is provided to a user computing device or other device. If the new value of K (from 270) does not exceed K, as determined at 280, then processing continues with the next cycle using the new value of K at 250.

Paths may be analyzed in any order and the present technique does not require a priority queue. The present algorithm does not require a pre-processing stage and, therefore, can also be well used in dynamic scenarios: for example, a journey may be added or modified (e.g. due to a false point) without requiring a change to the algorithm. As will be described further below, suitable data structures ensure that the path can be efficiently traversed and the tags can be efficiently updated. Additionally, the present algorithm may incorporate one or more acceleration techniques to limit the number of routes that must be viewed. Each loop may be processed time-linearly in the input size.

In one implementation, each site v is associated with a plurality of tags l (v) = (τ)₀(v)，τ₁(v)，τ₂(v)，...，τ_K(v) Are in a correlation of where τ is_i(v) Representing the earliest known arrival time at v when at most i journeys are allowed. The value in the tag is initialized to infinity. Then, τ₀(v_s) Is set equal to τ (recall v_sIs the source). Note that by setting τ for each source station v₀(v) = τ, multiple source stations can be processed.

In addition, the following invariants are maintained: at the beginning of cycle k (for k ≧ 1), at (from τ)₀(v) To tau_k-1(v) The first k recordings in L (v) of (1) are correct, i.e. recording τ_i(v) Representing the earliest arrival time at v using at most i journeys. The remaining records are set to ∞. The purpose of the loop k is to calculate τ for all v_k(v) In that respect This is done in three stages, for example as described below with reference to fig. 3.

Fig. 3 is an operational flow of another implementation of a method 300 of determining travel in a public transportation network. At 310, the first phase of loop k is performed. The first phase of the cycle k sets τ for all stations v_k(v)=τ_k-1(v) In that respect This phase sets an upper limit on the earliest arrival time at v with k journeys.

At 320, the second phase of loop k is performed. The second phase of loop k includes processing each journey exactly once. When processing journey t, at t isThe last (kth) trip taken results in a trip. To process the itinerary, the sites are visited sequentially (from earliest to latest). Let it go to the departure time (annotated as dep (t, v) on the journey_i) At least with τ)_k-1(v_i) V equally late_iBecomes the first site in the journey. If no such site exists, the journey cannot be used in this cycle. However, if such a site is present, as is known, it may be at v_i"jump to" the site (i.e., the journey may be used to determine a solution to the query). For all subsequent sites v in the journey_jSetting τ_k(v_j)←min{τ_k(v_j)，arr(t，v_j)}. Here, arr (t, v)_j) Is journey t at station v_jThe arrival time of (c).

At 330, the third phase of loop k is performed. The third phase of cycle k takes into account the transfer (e.g., the trip). For each transfer (v, w) from each site v to outside site w, τ is set_k(w)←min{τ_k(w)，τ_k(v) + l (v, w) }. In one implementation, the retrieval of the Pareto best path may use a data structure and/or parent pointer, as further described herein with reference to fig. 7 and 8.

Routing techniques may be improved using algorithms such as iterating over the route, marking, tightening stop conditions, pruning, paralleling, and running multiple times. These optimizations do not affect the correctness of the algorithm: the algorithm will also determine the location v to the destination_tTo do Pareto best travel.

In one implementation, the techniques described herein may iterate over a route rather than over a journey during the second phase of each loop k. Multiple journeys explicitly traversing the same route r may be useless. For reasons of clarity, consider site v in r_i. τ has been calculated from the previous cycle_k-1(v_i) (i.e. at v)_iThe earliest arrival time of k-1 journeys). If the trip is extended during cycle k using route r, then as is knownWhich trip is taken from r: at time τ_k-1(v_i) Or leave v afterwards_iThe first itinerary of (1). The earlier journeys are not realistic and the latter journeys are dominated by t. Note that for station v appearing later along the route_jIn practice, an earlier trip may be taken.

FIG. 4 is an operational flow of an optimization that may be used in an implementation of a method 400 of determining travel in a public transportation network. Method 400 is similar to method 300, but the second stage is different. The first stage at 410 is similar to the first stage described above with reference to 310, while the third stage at 430 is similar to the third stage described above with reference to 330, and their descriptions are omitted for the sake of brevity. In the second phase of 420, an iteration is performed on the route, rather than on the journey as in 320.

In one implementation, each way is processed exactly once in the second phase of loop k at 420. Consider route r and let T (r) = (t)₁，t₂，...，t_|T(r)|-1) Is a sequence of journeys following route r from earliest to latest. When route r is processed, a trip is generated in which the last (kth) trip taken is in route r. So that (r, v)_i) Is that someone in route r may be at v_iOn the earliest journey, i.e. to dep (t, v)_i)≥τ_k-1(v_i) The earliest journey t. Note that et (r, v) is undefined_i) In this case, the journey may not exist.

FIG. 5 is a diagram illustrating the possible locations v through which a source can be located during a query_sAnd destination location v_tTo the various routes scanned 500. Each stop on the route is a stop on that particular route. As shown in this example, the source position v_sOn the line r₀Upper, and destination location v_tOn the line r₃The above. During cycle 1, only assays with v are analyzed using the technique described above with reference to method 200_sThe route of (1); thus, only route r₀Is analyzed. During cycle 2, there are stations during cycle 1All routes of (a) are analyzed; thus, the route r₀、r₁And r₂Is analyzed. During cycle 3, all routes having a station during cycle 2 are analyzed; thus, the route r₀、r₁、r₂And r₃Is analyzed. Destination location v_tStay on the route r₃And thus the analysis can be stopped after cycle 3.

To process the route, its sites are visited in sequence until site v is determined_iTo define et (r, v)_i). This is when the route can be "jumped to". Let the corresponding journey t be the current journey of r and keep traversing the route. For each subsequent site v_jUpdate τ using the journey_k(v_i). Also, the current trip of r may be updated: at each site v along r_iWhere it is possible to catch up with an earlier journey (e.g. because a trip to v has been found using a different route_iFaster path) of the network. Thus, it is checked whether τ is_k-1(v_i)<arr(t，v_i) And by recalculating et (r, v)_i) To update t.

Note that the scheme can also be extended to handle circular routes by linking the last site of such a route to its first site. By doing so, the route can be traversed until the entire loop is performed without improvement.

In one implementation, the number of ways accessed during each cycle may be limited. In particular, there is no need to traverse routes that cannot be reached by the previous cycle, as there is no way to "jump" to any of its journeys. More precisely, it is sufficient to only traverse the route containing at least one station reached through exactly k-1 journeys, instead of looping through all routes during loop k. For example, consider a route where the last improvement occurs at loop k' < k-1. The route is visited again during the loop k' +1< k and no stations along the route are improved. It is not traversed again until at least one of its sites improves due to some other route.

FIG. 6 is another optimized operational flow that may be used in an implementation of a method 600 of determining travel in a public transportation network. At 610, during cycle k-1, arrival time τ is improved_k-1(v_i) Those sites v of_iAnd (6) marking. At 620, at the beginning of loop k, the loop traverses all the marked sites and finds exactly those routes that contain the individual sites, accumulating them in set Q. Then, at 630, only the way from Q needs to be considered to scan in cycle k.

Since the set of marked sites correspond exactly to those sites to which the journey may "jump" in cycle k, it is only necessary to traverse a route starting at the earliest marked site contained in the route. More specifically, when route r is added to Q while circulating through the marked sites, the earliest (marked) site of r within Q is maintained (possibly updated). It is then sufficient to start scanning r from its associated earliest site.

In this way, the route is scanned starting at the earliest marked station. Thus, using such a route optimization as in FIG. 5, for example, the route r is scanned in cycle 1 as described above₀In cycle 2, however, only route r₁And r₂From the earliest marked site (e.g. route r)₁Station 510 and route r₂Station 520) is analyzed. Earlier of these routes (e.g. route r)₁Stations 502 and 503 and route r₂Stations 518 and 519) are not analyzed because they were not routed r in the earlier cycle₀And (4) arriving. Similarly, at cycle 3, the route r starting at station 530 is analyzed₃Because the route r is not reached in the earlier cycle₃Station 528.

As described above, for example, the technique of fig. 2 stops after K cycles. In one implementation, tighter conditions may be employed to loop through which no sites are markedThe process is suspended immediately after k, i.e. in this loop, τ for all v_k(v)=τ_k-1(v) In that respect This means that there is no improvement in this cycle.

In one implementation, local pruning may be used as an acceleration technique. That is, v for each site_iIs maintained at v_iValue of the earliest known arrival time of (v) is obtained_i). Since only the Pareto optimal path is preserved, during the traversal of the path at cycle k, the arrival time is earlier than τ (v) only for the journey when k-1_i) The sites in time are marked.

Additional pruning is possible when computing point-to-point paths. In this case, the interest is focused on computing two v_sAnd v_tPareto best travels between sites. During cycle k, there is no need to mark its arrival time greater than τ (v)_t) (at v)_tBest known arrival time at).

In one implementation, the present techniques may be extended to work in parallel. Part of the present technique consists of processing the individual routes in an unspecified order. If several CPUs are available, each CPU can process a different subset of the ways. However, during cycle k, multiple cores may attempt to write to the same memory location τ at the same time_k(v) Therefore, proper attention must be paid to ensure correctness. Well known techniques such as locks or transactions may be used.

For performance reasons, the use of such coordination primitives (e.g., locks) should be minimized because they are costly. In particular, if all the routes containing site v are assigned to the same core, then there is no need to protect the routes corresponding to τ_k(v) The memory location of (2). When partitioning routes between cores one should consider: the number of sites allocated to more than one core should be minimized.

As suggested above, the present technique finds the best solution to the EABT problem: given a start time τ, it looks for a location having a location v at the destination_tA trip with the earliest possible arrival time τ' with limited transfer. Note, however, that the source v is left at time τ (or later)_sAnd reaches v at time τ_tThere may be several trips. In some applications, it is preferable to have a trip that minimizes the travel time, i.e., leaves v as late as possible_s(but still τ') is reached.

In one implementation, this version of the problem can be solved by running the algorithm multiple times. The first run is from v leaving at time τ as described above_sTo v_tForward search of (2). It finds the earliest possible arrival time τ 'for each k'_k. Then, for each k, a reverse search is run, at time τ'_kV is_tIs started and has v_sAs a target. The algorithm is the same as described above, but backed off in time. This will be found at v_sHaving a latest departure time τ of at most k journeys "_k. Note that, to obtain τ "_kIt is sufficient to limit the number of cycles in the reverse search to k.

In another implementation, if such a multi-step scheme is expensive (e.g., because running the algorithm K +1 times is too expensive), a heuristic replacement may be used. First, a standard algorithm is run to find a candidate trip J. The trip corresponds to a sequence of trips. Then, at a post-processing step, J is traversed in reverse order (from the last journey to the first journey), replacing each journey with the latest possible actual-fit journey in the same route. Although this does not guarantee that the results found are as good as those found by running multiple full searches, it can actually find a good enough alternative.

Data structures may be implemented for the techniques described above. In one implementation, the routes, itineraries, and stops have consecutive integer identifiers, each beginning with 0. FIG. 7 is an illustration of an example data structure 700 that may be used in determining a trip in a public transportation network. As described above, the route is traversed. For route i, its sequence of sites is used (in order) toAnd a list of all journeys (from earliest to latest) following the route. In one implementation, an array of routes 710 may be stored, with the ith record holding the relevant route r_iThe information of (1). For example, the sum r may be stored_iThe number of associated journeys and the number of stops in the route (for which all journeys are the same). Also, it may store pointers to lists.

In one implementation, in route [ i ]]（Routes[i]) The pointer in (1) indicates along the route r_iList of site sequences made. Instead of representing each list of sites (one per route) separately, they are grouped into a single array of route sites (RouteStops) 720. Route site 720 may first contain the sequence of sites for route 0, followed by those for route 1, and so on. In the route [ i]Points to the first record in route site 720, which relates to route i.

In the route [ i]Is a representation of a list of journeys actually following the route. Instead of maintaining separate lists for different routes, a single array site time (StopTimes) 730 may be used. The site time 730 may be divided into blocks, and the ith block contains data corresponding to the route r_iAll journeys of (1). In block, the itineraries may be sorted by departure time (at the first site). Each journey is simply a sequence of site times, each represented by a corresponding arrival time and departure time. Note that for each journey, the site time corresponding to the first/last site only has a set of departure/arrival times respectively.

Can be obtained by traversing and routing r_iRoutes r are processed by stations in associated route stations 720_i. To find the earliest journey along the route after a certain time τ from a certain stop v, the route r at v can be visited within a fixed time on each journey, because of the way the stop times 730 are ordered_iThe site times of all journeys. In particular, if when processing r_iWhen journey t is already being used, then the continuation in site time 730 is passedThe arrival time of the next station is recorded. Furthermore, to check whether r improves for earlier journeys_iR (═ route r stored in route 710)_iLength) records a trip to the left to take the next earlier trip.

Some additional operations are supported. In one implementation, for these additional operations, array sites 810 (Stops 810) are used, which contain information about each individual site. FIG. 8 is an illustration of an example data structure 800 that may be used in determining travel in a public transportation network. In particular, v for each site_iA list of all routes through the site is stored-in one implementation, this may be used in the marking routine described above (e.g., with reference to method 600 of fig. 6). And, maintenance is from v_iA list of all transfers available in (1) and their corresponding transfer times. As previously described, these two sets of lists are aggregated into two arrays. Array site routes (stoppages) 820 contain a list of routes associated with each site: first is with v₀Associated route followed by v₁Associated routes, and so on. Furthermore, each record of a route of a station is stored in the order in which the stations associated on the respective route are stored. This is used to quickly calculate the earliest site along the route from which the route traversal must start in the next cycle of the algorithm. Similarly, array transfer 830 indicates allowed slave v₀Transfer, followed by allowed slave v₁Transfer, and so on. From v_iBy its destination station v each individual transfer_jAnd a transfer time l (v)_i，v_j) Are shown together. The ith record in site 810 points to site v_iThe first record in the associated site route 820 and transfer (Transfers) 830.

To support the retrieval of actual travels (and not just arrival times and transfer times), one implementation associates an additional field with each tag τ representing the kth trip on the travel_k(v) And the site to which the journey "jumped". To retrieve actual journeys, follow theseThe "parent pointer" produces (from last to first) the corresponding trip.

FIG. 9 illustrates an exemplary computing environment in which example implementations and aspects may be implemented. The computing system environment is only one example of a suitable computing environment and is not intended to suggest any limitation as to the scope of use or functionality.

Numerous other general purpose or special purpose computing system environments or configurations may be used. Examples of well known computing systems, environments, and/or configurations that may be suitable for use include, but are not limited to, PCs, server computers, hand-held or laptop devices, multiprocessor systems, microprocessor-based systems, network PCs, minicomputers, mainframe computers, embedded systems, distributed computing environments that include any of the above systems or devices, and the like.

Computer-executable instructions, such as program modules, may be used that are executable by a computer. Generally, program modules include routines, programs, objects, components, data structures, etc. that perform particular tasks or implement particular abstract data types. Distributed computing environments may also be used where tasks are performed by remote processing devices that are linked through a communications network or other data transmission medium. In a distributed computing environment, program modules and other data may be located in both local and remote computer storage media including memory storage devices.

With reference to FIG. 9, an exemplary system for implementing aspects described herein includes a computing device, such as computing device 900. In its most basic configuration, computing device 900 typically includes at least one processing unit 902 and memory 904. Depending on the exact configuration and type of computing device, memory 904 may be volatile (such as Random Access Memory (RAM)), non-volatile (such as read-only memory (ROM), flash memory, etc.) or some combination of the two. This most basic configuration is illustrated in fig. 9 by dashed line 906.

Computing device 900 may have additional features or functionality. For example, computing device 900 may also include additional storage (removable and/or non-removable) including, but not limited to, magnetic or optical disks or tape. Such additional storage is illustrated in FIG. 9 by removable storage 908 and non-removable storage 910.

Computing device 900 typically includes a variety of computer-readable media. Computer readable media can be any available media that can be accessed by computing device 900 and includes both volatile and nonvolatile media, removable and non-removable media.

Computer storage media includes volatile and nonvolatile, removable and non-removable media implemented in any method or technology for storage of information such as computer readable instructions, data structures, program modules or other data. Memory 904, removable storage 908 and non-removable storage 910 are all examples of computer storage media. Computer storage media includes, but is not limited to, RAM, ROM, electrically erasable programmable read-only memory (EEPROM), flash memory or other memory technology, CD-ROM, Digital Versatile Disks (DVD) or other optical storage, magnetic cassettes, magnetic tape, magnetic disk storage or other magnetic storage devices, or any other medium which can be used to store the desired information and which can accessed by computing device 900. Any such computer storage media may be part of computing device 900.

Computing device 900 may contain communication connections 912 that allow the device to communicate with other devices. Computing device 900 may also include input device(s) 914 such as keyboard, mouse, pen, voice input device, touch input device, etc. Output device(s) 916 such as a display, speakers, printer, etc. may also be included. All of these devices are well known in the art and need not be discussed at length here.

It should be understood that the various techniques described herein may be implemented in connection with hardware or software or, where appropriate, with a combination of both. Thus, the processes and apparatus of the presently disclosed subject matter, or certain aspects or portions thereof, may take the form of program code (i.e., instructions) embodied in tangible media, such as floppy diskettes, CD-ROMs, hard drives, or any other machine-readable storage medium wherein, when the program code is loaded into and executed by a machine, such as a computer, the machine becomes an apparatus for practicing the presently disclosed subject matter.

While exemplary implementations may involve utilizing aspects of the presently disclosed subject matter in the context of one or more stand-alone computer systems, the subject matter is not so limited, but may be implemented in connection with any computing environment, such as a network or distributed computing environment. Further, aspects of the presently disclosed subject matter may be implemented in or across a plurality of processing chips or devices, and storage may similarly be effected across a plurality of devices. These devices may include, for example, PCs, web servers, and handheld devices.

Although the subject matter has been described in language specific to structural features and/or methodological acts, it is to be understood that the subject matter defined in the appended claims is not necessarily limited to the specific features or acts described above. Rather, the specific features and acts described above are disclosed as example forms of implementing the claims.

Claims (12)

1. A method of determining travel between two locations in a public transportation network, comprising:

receiving as input at a computing device data relating to the public transportation network, and the public transportation network including a plurality of sites and itineraries grouped into routes;

performing, by the computing device, a Pareto optimal travel calculation between a first site and a second site of the plurality of sites as a function of a received query, wherein the first site is a source location and the second site is a destination location, and wherein the Pareto optimal travel calculation is subject to conditions that minimize travel time and minimize a number of transfers, while excluding a pre-processing stage prior to receiving the query to be suitable for use in a dynamic scenario;

outputting, by the computing device, at least one Pareto best trip between the source location and the destination location if the Pareto best trip exists.

2. The method of claim 1, wherein performing Pareto optimal travel calculations between the first site and the second site comprises performing a plurality of loops on the network, each loop of the plurality of loops determining an optimal travel from a first site on the network to each other site reachable using a predetermined number of journeys.

3. The method of claim 2, further comprising receiving an integer representing a maximum number of journeys, wherein the plurality of cycles is based on the integer representing the maximum number of journeys, and each cycle corresponds to a different number that is not greater than the maximum number of journeys.

4. The method of claim 3, wherein the predetermined number of journeys per cycle is equal to the different number corresponding to each cycle.

5. The method of claim 2, wherein performing each loop comprises:

determining a time of arrival for each transit station corresponding to a station reachable on the network using the predetermined number of journeys; and

a tag is set with the earliest determined arrival time for each reachable site.

6. The method of claim 2, wherein the query identifies the source location, the destination location, and a departure time.

7. The method of claim 1, wherein performing the Pareto optimal travel calculation between the first site and the second site comprises performing a plurality of loops on the network, wherein each loop of the plurality of loops iterates over a plurality of tours reachable using a predetermined number of transfers.

8. The method of claim 1, wherein performing the Pareto optimal travel calculation between the first site and the second site comprises performing a plurality of loops on the network, wherein each loop of the plurality of loops iterates over a plurality of routes reachable using a predetermined number of transfers.

9. The method of claim 8, further comprising limiting the routes iterated in each loop by traversing only routes reached by a previous loop.

10. The method of claim 1, wherein at least one Pareto-best trip between the source location and the destination location comprises a total number of transfers performed in the trip being less than a predetermined number of earliest possible arrival times.

11. A method of determining travel between two locations in a public transportation network, comprising:

receiving, at a computing device, a query comprising a source location in a public transportation network, a destination location in the public transportation network, and a departure time;

performing, by the computing device, a plurality of loops using data representing the public transportation network, the data comprising a plurality of sites, wherein a first site is associated with the source location and a second site is associated with the destination location, wherein performing each loop comprises:

setting an upper limit, if any, for the earliest arrival time of each site reachable at a predetermined number of journeys in the cycle, taking into account delays or cancellations of one or more services;

processing each of a plurality of journeys in said cycle by visiting each stop in said journey from earliest to latest, wherein the earliest is the first stop in said journey having a departure time at least as late as the arrival time in the previous cycle, if such a stop is present, and for each subsequent stop in said journey, setting the arrival time at that stop to the minimum of said arrival time and a previously set upper limit; and

determining at least one travel plan between the source location and the destination location based on the loop executed by the computing device;

wherein the loop excludes a pre-processing stage prior to receiving the query to be suitable for use in a dynamic scenario.

12. A method of determining travel between two locations in a public transportation network, comprising:

performing, by a computing device, path computation between a source location and a destination location in a transport network using a predetermined departure time or a predetermined arrival time in accordance with a received query, wherein the path computation includes minimizing travel time and eliminating a pre-processing stage prior to receiving the query to be suitable for use in a dynamic scenario; and

outputting, by the computing device, at least one travel itinerary between the source location and the destination location.