Bus route plan/transport algorithm

所需积分/C币:1 2014-10-15 2.32MB PDF
评分

ulti-Modal Route Planning. Master's thesis, Universität Karlsruhe (TH), Fakultät für Informatik, 2009. online available at http://i11www.ira.uka.de/extra/publications/p-mmrp-09.pdf the section on railway routing also applies for bus routing. The gist of it: the naive approach of expanding space an
Contents Introduction 1. 1. Related work I 2. Our Contributions ·D 1.3. Overview 2 Foundations 1. Graph Theor 2.2. Languages and Automata.......... 11 3. Models 13 3.1. Timc-Indcpendent and Timc- Dependent models 3 3.1.1.lime-Independent Models 3. 1.2. Time-Dependent Models ..... 3. 2. The Road Network 16 3.3. The Railway Network ·鲁 17 3.3.I. Timetables 3. 3.2. The Condensed Model 8 3. 3. Time-Expanded Models 3.3.4. Time-Dependent Models 3. 4. The Flight Network 3. 4.1. Timetables 26 3. 4. 2. USing the Railway Model 3. 4.3. A Flexible Model for Flight Nety worKs 3. 5. Combining the Networks 3.5.1. The Nearest Neighbor Problem 3. 5.2. Merging and Linking 36 Contents 3.6. Summary 8 4. Routi g 41 4.1. The Earliest Arrival Problem and Shortest Paths 4.1.1. The Earliest Arrival Problem 4 Shortest Path 42. Uni-Modal routing·. 45 4.2.1.Time-Independent Routing 4.2.2. Time-Dependent Routing 47 4.3. Multi-Modal Routing 4.3.1. The Label Constrained Shortest Path Problem 52 4.3.2. Algorithms 8 5. Speed-Up Techniques 61 5.1. Basic Ingredients 5.I.1. Bi-Directional Search 6 5.1.2. A* with Landmarks(ALT) 66 Arc-Flags 5.1.4. Contraction 6 5.2. Core-Based Routing 2 5.2.1. Preprocessing Query 5.2.3. Proof of Correctness 5.2. 4. Discussion 53. Core-ALT 1 I. Prepro 2 32 92 5.3.3. Proof of correctness 534 4. Access-Node routing 5.4.1. Motivation 5. 4.2. Formal Introduction 5.4-3. Preprocessing 100 544· Query 5.4.5. Core-Based Access-Node routing 107 5. 4.6. Proof of Correctness 110 5.4.7. Discussion 1工 Contents Summar 114 6. Experiments 117 6. I. Input 7 6.1.1.G1 118 6.1.2. Automata 120 6.2. Experimental Setup ,工2工 6.3. Multi-Modal routing 6.4. Core-ALT 123 6.5.A Routing 6.6. Summary 130 7. Conclusion 133 7. 1. Future Work 13 A, Data Structures 139 A.I. Graphs 139 A.I.I. Static Graphs 140 A. 2. Dynamic graphs A. 2. Piecewise Linear functions .144 A. 3. Finite Automata 45 A. 4. Priority Queue...... 47 B. Raw Data Processing 149 B. 1. Road data ·:····· 149 B 2. Railway Data 50 B 3. Flight Data 15 Chapter Introduction In modern life, route planning is gaining more and more importance. As transporta- tion nctworks bccomc morc complex and mobility in our socicty morc important, the demand for efficient methods in route planning increases even further. Handheld sat- nav systems for cars already established as commodity items and most railway and flight companies offer some kind of route planning facilities through the Internet However, all these systems have one common limitation: They only allow route planning within their respective domain. For example, sat-nav system only show the way around the road network. If we rather like to use means of public transportation, we are stuck with the task of getting to and from the nearest station or airport since route planning facilities of public transportation companies usually do not involve the road nctwork. Even worse, when planning a flight, this usually involves putting the following stages of the journey together manually. First, select a convenient flight after that, choose a train that arrives at the airport in time and, further, match the time f leaving the house correctly in order to catch the train at the station The problem of route planning involving diffcrent modes of transportation is called multi-modal route planning. Our goal is very simple. We would like to be able to state source and target addresses (in the road network) together with a departure time, select our desired means of transportation(for example, car, trains and flights, but the car only in the beginning) and the system should return an optimal route with respect to travel time that shows us what roads to use and which trains and flights to take The involved networks may have very different properties. For example, the road nctwork can be uscd at any given timc, however, trains and flights only operate at defined times according to some timetable. The challenge of combining the individual networks in a realistic way such that we are able to perform efficient queries is the topic of this thesis Chapter 1. Introduction 1.1 Related Work Routing is a widely researched topic in computer science, mainly because of its rel vance to real world applications. The problem of route planning can be modeled by finding a shortest path on a directed weighted graph. First algorithms to solve this problem are quite old and are presented in the 1950s and 6os by Dijkstra [Dij591 Bellmann and Ford [r. 56, Bel58] and Hart, Nilsson and Raphael [HNR68I(A"). While these algorithms compute optimal shortest paths with optimal theoretic timc complexity, they are too slow to process real world data sets like large scale road net- works, even on today's computers However only in recent years computer hardware has become efficient enough to allow the handling of large networks like they occur in route planning, at all. Thus, during the past years research focused on developing speed-up techniques to accelerate the basic shortest paths algorithms by reducing their search space. A comprehensive overview is given in [DSSWoga]. In this section we mention work on the subject of road and public transportation networks separately. Routing in Road Networks. Although, the first attempts to speed up DIJKSTRA's algorithm were conducted regarding timetable information on railway networks in 1999(scc [SWWgg D ), in 2005 huge road networks were madc publicly available which led research toward road networks. This culminated in the th DImACS Challenge on shortest paths [DGJog] in 2006 It turns out that there are a few basic ingredients to all modern speed-up tech niques [Scho8a, DelogaF: Bi-directional search, goal-directed search and contraction In Section 5. 1 we present these basic ingredients in more detail In short, bi-directional search(due to [Dan62, GHo5])not only computes the shortest path from the source s to the target t, but simultaneously computes the shortest path from t to s on the backward graph. The final shortest path is then combined from partial paths obtained by the forward and backward searches. While this approach works well in time-independent networks where the edge weights are constant in the graph, adapting bi-directional routing to time-dependent networks where the edge weights arc timc-dcpcndent functions is not straightforward [NDlSo8 Regarding goal-directed search basically two approaches exist. Based on the A* al gorithm by Nilsson and Raphael [HNR68 Goldberg et al. enhanced A* by intro- ducing landmarks to compute feasible potential functions using the triangle inequal- ity [GHo5, GWo5]. Their approach is called ALT and turns out as a very robust tech- nique [BDWo7]. The adaption to time-dependency is easy as shown in [Dwo7l The second goal-directed approach is using edge-labels to guide the search. Wag ner et al. introduced in [WWo,, WWZo5] a method called geometric containers where 1.1 Related work each edge contains a label that represents some geometric object containing all nodes to which a shortest path begins at the respective edge urin g the query, edges that do not contain the target node can be pruned. This approach is refined by Lauther in [Lauo4] called Arc- Flags. Instead of geometric containers, the graph is partitioned into k cells and k edge-labels(arc-flags)are attached to every edge to indicate whether the respective edge is important for at least one target node in each cell. Regard ing the choice of the partition, studies have been conducted using grid based ap proaches [Lauo4, KMSo5] and several partitioning algorithms that do not rely on geo- metric information [MSo4, Karoz, Pclo7] Regarding contraction there are a variety of approaches. Highway Hierarchies by Sanders and Schultes [ssos, SSo6a] exploits the implicitly given hierarchy in road net- works regarding different road categories. Contraction Hierarchies presented by Geis berger et al. [Geio8, GSSDo8] is solely based on contracting the graph yielding a very efficient speed-up technique Although, not a basic ingredients as mentioned above, there is another approach or speeding up shortest path queries: Table-lookups. In Transit- Node routing [SSo6b BFMto, BiSSoz] a set of relevant transit nodes are determined where almost all'far shortest path pass through. Distances are then precomputed between each pair of transit-nodes. Several approaches exist for selecting transit-nodes: Separators Milo6 DHMtogl, border nodes of partitions [BFM*o7, BFSSo7, BFMog] and nodes turning out important by other spced -up techniques [BFMfo7, BFSSo7, SSogI Several speed-up techniques arose that use combinations of the ingredients from abovc [HSWo4, HSWwo6, Scho8a, BDS+o8]. Bi-dircctional routing can be combincd with goal-direction and contraction [BDSto8, DNo8]. Relevant for this work is the combination of contraction with goal-directed search(especially ALT). In [BDSto8l Corc-aLt is introduced for timc-indcpendent and timc-dcpendent nctworks where the graph is contracted yielding a much smaller core-graph on which then ALT is applied. Further combinations of contraction with ALt are presented in [GKWo6b GKWoba, GKWog, DSSWogb]. Combining contraction with Arc-Flags yields a very efficient uni-directional speed-up technique called SHARC [BDog, Delogb] which can be combincd furthcr with bi-dircctional routing. The fastest spccd-up techniqucs on road networks as of today are CHASE( Contraction Hierarchies plus Arc-Flags)and the combination of Transit-Node Routing with Arc-Flags [BDS+o8, BDS+og] yielding query times down to 2 microseconds on continental-sized road networks Routing in Public Transportation Networks. Routing in public transportation net- works turns out harder than in road networks. Research focused on timetable informa tion for railway networks. In ISWw99, PSWZo4, Scho5, PSWZo7, MSWZo7, DPWo8 Chapter 1. Introduction different models regarding different levels of realism and algorithms are presented Basically there are two approaches to cope with the inherent time-dependency of a railway timetable: The time-expanded and the time-dependent approach. While the first allows more flexible modeling of additional constraints, the latter yields smaller graph sizes and, thus, faster query times [PSWZo7 ]. See also Section 3. 3 for an in depth presentation of the several models DIJKSTRAS algorithm can be adapted to solve the EARLIEsT ARRIVAL PROBLEM (i.e we minimize travel timc)on both the timc-indcpendent and timc-dependent approach Experimental studies on timetable information have been conducted using speed up techniques from road networks [PSWZoy BDWo7, BDWog, DPWo8]. It turns out that spccd-up techniques arc much harder to adapt to timetable information than one might expect, although a combination of alt and Arc-Flags harmonizes well [DPWo8 Furthermore, in public transportation networks multi-criteria optimization turns out more important(e.g not only minimize the travel time, but also costs, transfers, etc) This problem has been studied by Miiller-Hannemann et al. [MWoI, MSoz, DMSo8 However, in this work we restrict ourselves to single-criteria search, i.e. optimizing travel time alone Multi-Modal Routing. Multi-modal route planning can be solved by the LABel con- STRAINED SHORTEST PATH PROBLEM [BBHTog]. In [B]Moo] an extensive theoretical study is conducted on the complexity of the LABEL. CONSTRAINED SHORTEST PATH PROBLEM regarding various types of languages. It is shown in [BJMoo] that the La bEL CONSTRAINED SHORTEST PATH PROBLEM is solvable in deterministic polynomial time when restricted to regular languages by a generalization of DIjKSTRA's algo- rithm [Dij59]. The first experimental study is conducted in [BB+o2] using the special casc of lincar regular languages Basic speed-up techniques including bi-directional search(see [Dan62, GHo5D), A (see[HnR68])and the Sedgewick-Vitter-Heuristic(see [sv86]are tested in the context of multi-modal routing in [Holo8, BBH*o91 1.2 Our Contributions In this thesis we approach the problem of cfficient multi-modal routing on hetero- eneous continental-sized networks composed of road, railway and flight networks Basically, our work is divided into three parts: Modeling, Routing and Speed-Up Tech niqlles

...展开详情
立即下载 最低0.43元/次 身份认证VIP会员低至7折
举报 举报 收藏 收藏
分享
img
DawsonSally

关注 私信 TA的资源

上传资源赚积分,得勋章
相关内容推荐