跳到主要內容

臺灣博碩士論文加值系統

(3.237.6.124) 您好!臺灣時間:2021/07/24 04:38
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

我願授權國圖
: 
twitterline
研究生:劉俊男
研究生(外文):Jyun-NanLiu
論文名稱:事件相依圖網之動態最快路徑即時演算法
論文名稱(外文):On-the-fly Fastest Path Computation in Event Dependent Network
指導教授:張大緯
指導教授(外文):Da-Wei Chang
學位類別:碩士
校院名稱:國立成功大學
系所名稱:資訊工程學系碩博士班
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2012
畢業學年度:100
語文別:英文
論文頁數:49
中文關鍵詞:引導預先處理重新運算反應時間關鍵區域混和機制
外文關鍵詞:navigationpre-computationre-computationresponse timecritical regionhybrid
相關次數:
  • 被引用被引用:0
  • 點閱點閱:119
  • 評分評分:
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
近年來,最快路徑演算法常被應用於路徑的引導上。然而,現有的演算法不僅存在著重複運算的問題,當圖網過大時,更有運算時間過長或提供的答案不準確的狀況。因而不適用於緊急的需求。不過,假設圖網是可以被預知的狀況下,這些問題都可以用事先運算並將結果保存來解決。很不幸的,緊急的環境通常會伴隨著不可預知的狀況,造成事先運算的結果錯誤,對此,需要即時的重新運算來確保其準確性。
這篇論文最主要的貢獻就是針對這種不可預知的狀況建立了事件相依圖網模型和在不影響結果準確性的狀況下降低回饋最快路徑的時間。由於重新運算的過程中,我們無法提供正確的最快路徑,因此,反應時間會被延遲。為此,我們藉由找尋關鍵區域和部分修復大幅降低了整體的運算量。另外,為了避免受損區域過大時造成過長的反應時間,我們增加了運算時間估測方法並混合了較快速的方法。結果顯示,在不同大小的圖網中,我們的效能平均提升了20-70倍。

In recent years, the fastest path algorithms were applied on the navigation. However, existing algorithms have two disadvantages. One is repeated computation, and the other is long response time or inaccurate results on large networks. Hence, they are not suitable for emergency related systems. But, the problems can be solved by pre-computation if the network is predictable. Unfortunately, the networks are unpredictable in an emergency condition. To address this, real-time re-computation is performed when the network is changed.
The contributions of this study are to propose the event-dependent network model and to reduce the response time of computing the accurate fastest path. The response delay is re-computation time because we cannot provide the correct fastest paths on the process of re-computation. For reducing the re-computation time, our method focuses on reducing the input size by critical region finding and re-computing. Besides, a method is proposed to avoid long response time due to a large critical region. The results show that, the proposed methods improve the response time by 20-70times.
摘要 i
Abstract ii
致謝 iii
List of Contents v
List of Tables vii
Chapter 1. Introduction 1
Chapter 2. Overview 4
Chapter 3. Related Work 8
3.1 Shortest Path Problem 8
3.2 The Algorithms for Shortest Path Problem 8
3.3 Relay Methods 11
3.4 Pre-Computing 14
3.5 Others 14
3.6 Summary 15
Chapter 4. Problem Definition 16
4.1 Fastest Path and FP(o, d) 16
4.2 Impaired Range and IR(P, D, R) 16
4.3 Events and Break Nodes 17
4.4 Extend Range and ER(o, d) 18
4.5 Cross Edge 19
4.6 C & CM Nodes 20
4.7 Time Even Nodes (TENs) 20
Chapter 5. On-the-Fly Fastest Path Computation 22
5.1 Pre-Computation of EDFP 23
5.2 Online EDFP Computation 24
5.2.1 Impaired Range Finding Algorithm 24
5.2.2 IRFA-TEN 27
5.2.3 Hybrid method 31
Chapter 6. Experimental Evaluation 33
Chapter 7. Discussion & Future Work 43
Reference 44
[1]E. W. Dijkstra. “A Note on Two Problems in Connexion with Graphs, Numerische Mathematik, vol. 1, pp. 269-271, 1959.
[2]X. Wang and J. Ma “Distributed Energy Optimization for Target Tracking in Wireless Sensor Networks, IEEE Transactions on Mobile Computing, vol. 9, no. 1, 73-86, 2009
[3]Y. Wang and H. Liu, “A Practical Intelligent Navigation System based on Travel Speed Prediction, IEEE Conference on ITSC 2008 Intelligent Transportation Systems, pp.470-475, 2008.
[4]A.X. Falcao and J. Stolfi, The image foresting transform: theory, algorithms, and applications , IEEE Transactions on Pattern Analysis and Machine Intelligenc, vol. 26, no. 1, pp. 19-29, 2004.
[5]P. Richard and R. Gleen, “I mproving Rural Emergency Medical Service Response Time with Global Positioning System Navigation, Journal of Trauma-Injury Infection & Critical Care, vol. 67, no. 5, pp. 899,902, 2009.
[6]U. Demiryurek and F. Banaei-Kashani, “A case for time-dependent shortest path computation in spatial networks, GIS '10 Proceedings of the 18th SIGSPATIAL International Conference on Advances in Geographic Information Systems, pp. 474-477, 2010
[7]S. Ichouaa and M. Gendreaua, “Vehicle dispatching with time-dependent travel times, European Journal of Operational Research, vol. 144, no. 2, pp. 379-396, 2003

[8]R. Hall, “The Fastest Path through a Network with Random Time-Dependent Travel Time, Transportation Science, vol. 20, no. 3, pp.182-188, 1986.
[9]L. Fu, “Adaptive Routing Algorithm for In-Vehicle Route Guidance Systems with Real-Time Information, Transportation Research Part B: Methodological, vol. 35, no. 8, pp. 749-765, 2001.
[10]L. Fu, L. R. Rilett, “Expected Shortest Paths in Dynamic and Stochastic Traffic Networks, Transportation Research Part B: Methodological, vol. 32, no. 7, pp. 499-511, 1998.
[11]D. P. Bertsekas, and J. N. Tsitsiklis, An Analysis of Stochastic Shortest Path Problems, Mathematics of Operations Research, vol. 16, no. 3, pp. 580-595, 1991.
[12]H. Frank, “Shortest Paths in Probabilistic Graphs, Operations Research, vol. 17, pp. 583-599, 1969.
[13]G. Polychronopoulos, and J. Tsitsiklis, “Stochastic Shortest Path Problems with Recourse, Networks, vol. 27, pp. 133-143, 1996.
[14]P. B. Eiger, Mirchandani, and H. Soroush, “Path preferences and optimal paths in probabilistic networks, Transportation Science, vol. 19, no. 1, pp. 75-84, 1985.
[15]G. Andreatta, and L. Romeo, “Stochastic Shortest Paths with Recourse, Networks, vol. 18, pp. 193-204, 1988.
[16]C. Alexopoulos, “State Space Partitioning Methods for Stochastic Shortest Path Problems, Networks, vol. 30, pp. 9-21, 1997.

[17]K. Seongmoon, M. E. Lewis, and C. C. White III, Optimal vehicle routing with real-time traffic information, IEEE Transactions on Intelligent Transportation Systems, vol. 6, no. 2, pp. 178-188, 2005.
[18]K. Seongmoon, M. E. Lewis, and C. C. White III, State space reduction for nonstationary stochastic shortest path problems with real-time traffic information, IEEE Transactions on Intelligent Transportation Systems, vol. 6, no. 3, pp. 273-284, 2005.
[19]F. Benjamin Zhan, “Three Fastest Shortest Path Algorithms on Real Road Networks: Data Structures and Procedures, Journal of Geographic Information and Decision Analysis, vol.1, no.1, pp. 69-82, 2001
[20]Fu L. “Real-time vehicle routing and scheduling in dynamic and stochastic traffic networks, Unpublished Ph.D. Dissertation, University of Alberta, Edmonton, Alberta, 1996.
[21]HA. Karimi, “Real-time optimal route computation: a heuristic approach, ITS Journal, vol. 3, no. 2, pp. 111-127, 1996.
[22]J. Lysgaard, “A two-phase shortest path algorithm for networks with node coordinates, European Journal of Operational Research, vol. 87, no. 2, pp. 368-374, 1995.
[23]Pohl I. “Bi-directional search. Machine Intelligence, 1971;6:127–40.
[24]G.B. Dantzig, “On the shortest route through a road network, Management Science, vol. 6, pp. 187-190. 1960
[25]T.A.J. Nicholson, “Finding the shortest route between two points in a network, Computer Journal, vol. 9, no. 3, pp. 275-280, 1966.
[26]J.L. Bander, “A new route optimization algorithm for rapid decision support, Proceedings of Vehicle Navigation Information Systems Conference, vol. 2, pp. 709-728, 1991.
[27]J.F. Dillenburg and P.C. Nelson, “Improving Search Efficiency Using Possible Subgoals, Mathematical and Computer Modelling, vol. 22, no. 4, pp. 397-414, 1995.
[28]D. He, “An Efficient Algorithm for the One to Some Shortest Path Problem on Road Maps, ALGORITHMIC ASPECTS IN INFORMATION AND MANAGEMENT, vol. 4508 pp. 346- 357, 2007
[29]P.E. Hart and N.J. Nilsson, “A formal basis for the heuristic determination of minimum cost paths, IEEE Transaction, System Science and Cybernetics, vol. 4, no. 2, pp. 100-107, 1968.
[30]L.B. Golden and M. Ball, “Shortest paths with euclidean distance: an explanatory model, Networks, vol. 8, no. 4, pp. 287-314, 1978.
[31]A.V. Goldberg and C. Harrelson, “Computing the Shortest Path: A* Search Meets Graph Theory, SODA '05 Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, pp. 156-165, 2005.
[32]G. Apostolopopoulos, “On the Effectiveness of Path Pre-Computation in Reducing the Processing Cost of On-Demand QoS Path Computation, ISCC '98 Proceedings. Third IEEE Symposium on Computers and Communications, pp. 43-46, 1998.
[33]R. B. Dial, “Shortest Path Forest with Topological Ordering, Communications of the ACM, vol. 12, pp. 632-633, 1969.
[34]B. V. Cherkassky and A.V. Goldberg, “Shortest Paths Algorithms: Theory and Experimental Evaluation, MATHEMATICAL PROGRAMMING, vol. 73, pp. 129-174, 1996.
[35]M.L. Fredman and R.E. Tarjan, “Fibonacci heaps and their uses in improved network optimization algorithms, Journal of the ACM, vol. 34, no. 3, pp. 596-615, 1987
[36]R.L.Rivest and C.E. Leiserson, Introduction to Algorithms 1990.
[37]R. Rajagopalan and K. Mehrotra, “Hierarchical path computation approach for large graphs, IEEE Transactions on Aerospace and Electronic Systems, vol. 44, no. 2, pp. 427-440, 2008.
[38]E.S. Dreyfus, “An appraisal of some shortest path algorithms, Operations Research, vol.17, no. 3, pp. 395-412, 1969.
[39]D.D. Champeaux and L. Sint, “An improved bi-directional heuristic search Algorithm, Journal of Association for Computing Machinery, vol. 24, no. 2, pp. 177-191, 1977.
[40]D.D. Champeaux, “Bidirectional heuristic search again, Journal of Association for Computing Machinery, vol. 30, no. 1, pp. 22-32, 1983.
[41]J. Kwa J, “BS∗: an admissible bi-directional staged heuristic search algorithm, Artificial Intelligence, vol. 42, no. 2, pp. 189–212, 1989.
[42]H. Kaindl and G. Kainz, “Bidirectional heuristic search reconsidered, Journal of Artificial Intelligence Research, vol. 7, pp. 283-317, 1997.


[43]H. Gonzalez and J. Han, “Adaptive Fastest Path Computation on a Road Network: A Traffic Mining Approach, VLDB '07 Proceedings of the 33rd international conference on Very large data bases, pp. 794-805, 2007.
[44]D.Z. Chen, “Solving the all-pair shortest path query problem on interval and circular-arc graphs, Parallel Processing Symposium, pp. 224-228, 1994
[45]M.A. Batalin and G.S. Sukhatme “Mobile Robot Navigation using a Sensor Network, ICRA '04 IEEE International Conference on Robotics and Automation, vol. 1, pp. 636-641, 2004
[46]Q. Li and M.D. Rosa, “Distributed Algorithms for Guiding Navigation across a Sensor Network, MobiCom '03 Proceedings of the 9th annual international conference on Mobile computing and networking, pp. 313-325, 2003
[47]Y. Chen and L. Sun, “Congestion-aware Indoor Emergency Navigation Algorithm for Wireless Sensor Networks, IEEE Globecom, 2011.
[48]C. Buragohain and D. Agrawal,“Distributed Navigation Algorithms for Sensor Networks, IEEE INFOCOM, 2006
[49]http://www.cs.utah.edu/~lifeifei/datasets.html

連結至畢業學校之論文網頁點我開啟連結
註: 此連結為研究生畢業學校所提供,不一定有電子全文可供下載,若連結有誤,請點選上方之〝勘誤回報〞功能,我們會盡快修正,謝謝!
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top