Bus route plan/transport algorithm

ultiModal 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/pmmrp09.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. TimcIndcpendent and Timc Dependent models 3 3.1.1.limeIndependent Models 3. 1.2. TimeDependent 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. TimeExpanded Models 3.3.4. TimeDependent 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. UniModal routing·. 45 4.2.1.TimeIndependent Routing 4.2.2. TimeDependent Routing 47 4.3. MultiModal Routing 4.3.1. The Label Constrained Shortest Path Problem 52 4.3.2. Algorithms 8 5. SpeedUp Techniques 61 5.1. Basic Ingredients 5.I.1. BiDirectional Search 6 5.1.2. A* with Landmarks(ALT) 66 ArcFlags 5.1.4. Contraction 6 5.2. CoreBased Routing 2 5.2.1. Preprocessing Query 5.2.3. Proof of Correctness 5.2. 4. Discussion 53. CoreALT 1 I. Prepro 2 32 92 5.3.3. Proof of correctness 534 4. AccessNode routing 5.4.1. Motivation 5. 4.2. Formal Introduction 5.43. Preprocessing 100 544· Query 5.4.5. CoreBased AccessNode 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. MultiModal routing 6.4. CoreALT 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, satnav 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 multimodal 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 speedup 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 speedup tech niques [Scho8a, DelogaF: Bidirectional search, goaldirected search and contraction In Section 5. 1 we present these basic ingredients in more detail In short, bidirectional 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 timeindependent networks where the edge weights are constant in the graph, adapting bidirectional routing to timedependent networks where the edge weights arc timcdcpcndent functions is not straightforward [NDlSo8 Regarding goaldirected 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 timedependency is easy as shown in [Dwo7l The second goaldirected approach is using edgelabels 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 edgelabels(arcflags)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 speedup technique Although, not a basic ingredients as mentioned above, there is another approach or speeding up shortest path queries: Tablelookups. 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 transitnodes. Several approaches exist for selecting transitnodes: 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 speedup techniques arose that use combinations of the ingredients from abovc [HSWo4, HSWwo6, Scho8a, BDS+o8]. Bidircctional routing can be combincd with goaldirection and contraction [BDSto8, DNo8]. Relevant for this work is the combination of contraction with goaldirected search(especially ALT). In [BDSto8l CorcaLt is introduced for timcindcpendent and timcdcpendent nctworks where the graph is contracted yielding a much smaller coregraph on which then ALT is applied. Further combinations of contraction with ALt are presented in [GKWo6b GKWoba, GKWog, DSSWogb]. Combining contraction with ArcFlags yields a very efficient unidirectional speedup technique called SHARC [BDog, Delogb] which can be combincd furthcr with bidircctional routing. The fastest spccdup techniqucs on road networks as of today are CHASE( Contraction Hierarchies plus ArcFlags)and the combination of TransitNode Routing with ArcFlags [BDS+o8, BDS+og] yielding query times down to 2 microseconds on continentalsized 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 timedependency of a railway timetable: The timeexpanded and the timedependent 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 timcindcpendent and timcdependent approach Experimental studies on timetable information have been conducted using speed up techniques from road networks [PSWZoy BDWo7, BDWog, DPWo8]. It turns out that spccdup techniques arc much harder to adapt to timetable information than one might expect, although a combination of alt and ArcFlags harmonizes well [DPWo8 Furthermore, in public transportation networks multicriteria optimization turns out more important(e.g not only minimize the travel time, but also costs, transfers, etc) This problem has been studied by MiillerHannemann et al. [MWoI, MSoz, DMSo8 However, in this work we restrict ourselves to singlecriteria search, i.e. optimizing travel time alone MultiModal Routing. Multimodal 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 speedup techniques including bidirectional search(see [Dan62, GHo5D), A (see[HnR68])and the SedgewickVitterHeuristic(see [sv86]are tested in the context of multimodal routing in [Holo8, BBH*o91 1.2 Our Contributions In this thesis we approach the problem of cfficient multimodal routing on hetero eneous continentalsized networks composed of road, railway and flight networks Basically, our work is divided into three parts: Modeling, Routing and SpeedUp Tech niqlles
 543B
算法可视化AlgorithmVisualizer.zip
20190718Algorithm Visualizer，算法可视化。在线Demo： http://parkjs814.github.io/AlgorithmVisualizer算法目录层次结构
 9KB
LaTex算法库——algorithmic.sty
20190508LaTex算法库文件——algorithm.sty，可以下载直接使用。
 34KB
algorithm_头文件_说明
20110603algorithm algorithm STL 算法 algorithm_头文件_说明 algorithm algorithm STL 算法 algorithm_头文件_说明 algorithm al
 3.39MB
AlgorithmD.S.ALeet.zip
20190917AlgorithmD.S.ALeet.zip,leetcode高频算法问题的参考与总结,算法是为计算机程序高效、彻底地完成任务而创建的一组详细的准则。
 2.66MB
CMU《Approximation Algorithm (近似算法)》课件全套
20181105CMU近似算法《Approximation Algorithm》课件全套，研究网络及离散优化必备，方便自学。
 17KB
Algorithmalgorithm.zip
20190917Algorithmalgorithm.zip,这句话的意思是,算法是为计算机程序高效、彻底地完成任务而创建的一组详细的准则。
 1.22MB
AlgorithmAlgorithm.zip
20190917AlgorithmAlgorithm.zip,算法问题求解,算法是为计算机程序高效、彻底地完成任务而创建的一组详细的准则。
 5KB
遗传算法进展GA
20121018很好用的// Genetic Algorithm for nonlinear programming // Written by Microsoft Visual C++
 13.77MB
AlgorithmNewBiePlan.zip
20190917AlgorithmNewBiePlan.zip,Java中间件,算法是为计算机程序高效、彻底地完成任务而创建的一组详细的准则。
 90KB
LevenbergMarquardt Algorithm
20180729LevenbergMarquardt Algorithm LevenbergMarquardt Algorithm
 20.41MB
Algorithm Design Solutions answer
20171005Algorithm Design（算法设计）的课后习题答案，方便学习
 18.53MB
算法设计答案 Algorithm Design Solution
20160229算法设计答案 Algorithm Design Solution
 45KB
Algorithm伪代码无法正常编写，所有Algorithm命令均无效
20181207LATEX中，Algorithm伪代码无法正常编写，所有Algorithm命令均无效
 4.68MB
data structure and algorithm in Java
20130416data structure and algorithm in java 3
 298KB
latex algorithm2e公式介绍
20160126latex algorithm2e 公式 介绍 里面是详细稳当很有用的
 374KB
很全的C/C++库参考手册英文版(含algorithm)
20111207很全的C/C++程库库参考手册，英文版，含有algorithm
 801KB
DSP28335完整invter电机控制程序
20181210调试PWM口，及V/F算法,参数辨识程序,磁场定向程序，从转速测量、参数辨识方面改善性能,转速PI调节,电流闭环 使用PI函数,串口SCI控制，ADC、DQ、CLARKE、park变换。Debug P
 118KB
经典的c算法
20110908经典c算法 http://caterpillar.onlyfun.net/GossipCN/AlgorithmGossip/AlgorithmGossip.htm
 3.23MB
Data Structures and Algorithm Analysis in C++ 4th 原版pdf by Weiss
20180427The fourth edition of Data Structures and Algorithm Analysis in C++ describes data structures, metho
 1.55MB
MOEA/D: A Multiobjective Evolutionary Algorithm Based on Decomposition.pdf
20200421张青富经典论文MOEA/D: A Multiobjective Evolutionary Algorithm Based on Decomposition

DawsonSally
等级：
关注 私信 TA的资源

下载
算法可视化AlgorithmVisualizer.zip
算法可视化AlgorithmVisualizer.zip

下载
LaTex算法库——algorithmic.sty
LaTex算法库——algorithmic.sty

下载
algorithm_头文件_说明
algorithm_头文件_说明

下载
AlgorithmD.S.ALeet.zip
AlgorithmD.S.ALeet.zip

下载
CMU《Approximation Algorithm (近似算法)》课件全套
CMU《Approximation Algorithm (近似算法)》课件全套

下载
Algorithmalgorithm.zip
Algorithmalgorithm.zip

下载
AlgorithmAlgorithm.zip
AlgorithmAlgorithm.zip

下载
遗传算法进展GA
遗传算法进展GA

下载
AlgorithmNewBiePlan.zip
AlgorithmNewBiePlan.zip

下载
LevenbergMarquardt Algorithm
LevenbergMarquardt Algorithm

下载
Algorithm Design Solutions answer
Algorithm Design Solutions answer

下载
算法设计答案 Algorithm Design Solution
算法设计答案 Algorithm Design Solution

下载
Algorithm伪代码无法正常编写，所有Algorithm命令均无效
Algorithm伪代码无法正常编写，所有Algorithm命令均无效

下载
data structure and algorithm in Java
data structure and algorithm in Java

下载
latex algorithm2e公式介绍
latex algorithm2e公式介绍

下载
很全的C/C++库参考手册英文版(含algorithm)
很全的C/C++库参考手册英文版(含algorithm)

下载
DSP28335完整invter电机控制程序
DSP28335完整invter电机控制程序

下载
经典的c算法
经典的c算法

下载
Data Structures and Algorithm Analysis in C++ 4th 原版pdf by Weiss
Data Structures and Algorithm Analysis in C++ 4th 原版pdf by Weiss

下载
MOEA/D: A Multiobjective Evolutionary Algorithm Based on Decomposition.pdf
MOEA/D: A Multiobjective Evolutionary Algorithm Based on Decomposition.pdf

博客
大学四年自学走来，这些私藏的实用工具/学习网站我贡献出来了
大学四年自学走来，这些私藏的实用工具/学习网站我贡献出来了

博客
在中国程序员是青春饭吗？
在中国程序员是青春饭吗？

博客
程序员请照顾好自己，周末病魔差点一套带走我。
程序员请照顾好自己，周末病魔差点一套带走我。

博客
技术大佬：我去，你写的 switch 语句也太老土了吧
技术大佬：我去，你写的 switch 语句也太老土了吧

博客
你以为这样写Java代码很6，但我看不懂
你以为这样写Java代码很6，但我看不懂

博客
上班一个月，后悔当初着急入职的选择了
上班一个月，后悔当初着急入职的选择了

博客
女程序员，为什么比男程序员少？？？
女程序员，为什么比男程序员少？？？

博客
副业收入是我做程序媛的3倍，工作外的B面人生是怎样的？
副业收入是我做程序媛的3倍，工作外的B面人生是怎样的？

博客
MySQL数据库面试题（2020最新版）
MySQL数据库面试题（2020最新版）

博客
如果你是老板，你会不会踢了这样的员工？
如果你是老板，你会不会踢了这样的员工？