跳到主要內容

臺灣博碩士論文加值系統

(44.200.86.95) 您好!臺灣時間:2024/05/20 08:42
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

: 
twitterline
研究生:黃彥銘
研究生(外文):Huang, Yam-Ming
論文名稱:即時路徑規劃:從演算法角度探討加拿大旅行者問題
論文名稱(外文):Online Route Planning: Exploring the Canadian Traveller Problem from an Algorithmic Point of View
指導教授:廖崇碩
學位類別:碩士
校院名稱:國立清華大學
系所名稱:工業工程與工程管理學系
學門:工程學門
學類:工業工程學類
論文種類:學術論文
論文出版年:2013
畢業學年度:101
語文別:英文
論文頁數:34
中文關鍵詞:加拿大旅行者問題競爭比率旅行推銷員問題
外文關鍵詞:Canadian traveller problemcompetitive ratioonline algorithm
相關次數:
  • 被引用被引用:0
  • 點閱點閱:296
  • 評分評分:
  • 下載下載:19
  • 收藏至我的研究室書目清單書目收藏:0
本研究探討即時路徑規劃的加拿大旅行者問題,其可實際應用在動態導航系統等,可用以避免交通阻塞的發生。對於一個有固定起點 s 與終點 t 的道路網路圖 G=(V,E) 中,每個路段 e 都有兩種可能的距離,分別是原本距離 d(e) 與阻塞距離 d^+ (e),旅行者只有在到達一個路段的其中一個端點才能得知此路段的真正距離,本問題的目的是要發展一個合適的策略使旅行者從起點 s 到終點 t 的行走距離與在預先了解所有路段的實際距離之情況下的最短行走距離的競爭比率為最小。本問題已被Papadimitriou與 Yannakakis提出並證明要找出一個有界限的競爭比率的演算法是PSPACE-complete的難度。在本論文中,我們提出一個當交通阻塞的次數是常數的問題的下界值,並且介紹一個競爭比率為min{ r,2k+1} 的確定性演算法來達到此下界,其中 r 是代表最壞情況下的比率;我們也考慮在均等的阻塞成本之模型(d^+ (e)=d(e)+c),其中 c 是常數。此外,我們將旅行推銷員問題放入本問題的假設來進一步探討,並提出一個競爭比率為 O(√k) 的旅行策略。最後,我們以隨機演算法的策略嘗試改良目前最好的競爭比率。
We investigate online route planning problems, which find real applications in dynamic navigation systems used to avoid traffic congestion. This study focuses on several generalizations of the well-known CANADIAN TRAVELLER PROBLEM (CTP). Given a road network G=(V,E) in which there is a source s and a destination t in V, every edge e in E is associated with two possible distances: original d(e) and jam d^+ (e). A traveller only finds out which one of the two distances of an edge upon reaching an end vertex incident to the edge. The objective is to derive an adaptive strategy for travelling from s to t so that the competitive ratio, which compares the distance traversed with that of the static s, t-shortest path in hindsight, is minimized. This problem was initiated by Papadimitriou and Yannakakis. They proved that it is PSPACE-complete to obtain an algorithm with a bounded competitive ratio. In this study, we propose tight lower bounds of the problem when the number of traffic jams is a given constant k, and introduce a deterministic algorithm with a min{r,2k+1}-ratio, which meets the proposed lower bound, where r is the worst-case performance ratio. We also study an extension to the metric Travelling Salesman Problem (TSP) and propose a touring strategy within an O(√k)-competitive ratio. Finally, we discuss randomized strategies, in the hope of surpassing the barrier of obtaining better approximation algorithms.
摘要
Abstract
誌謝
Contents
List of Figures and Tables
Introduction
Preliminaries
Double-valued Graph
The Uniform Jam Cost Model
k-CTP for Metric TSP
Randomized algorithm
Conclusion
References
[1] B. Awerbuch and R. Kleinberg. Online linear optimization and adaptive
routing. Journal of Computer and System Sciences, (2008), 74, pp. 97–
114.
[2] A. Bar-Noy and B. Schieber. The Canadian traveller problem. In Proc. of
the 2nd ACM-SIAM Symposium on Discrete Algorithms (SODA), (1991),
pp. 261–270.
[3] S. Ben-David and A. Borodin. A new measure for the study of online
algorithms. Algorithmica, (1994), 11(1), pp. 73–91.
[4] A. Borodin and R. El-Yaniv. Online computation and competitive analysis.
Cambridge University Press, Cambridge, (1998).
[5] N. Christofides. Worst-case analysis of a new heuristic for the traveling
salesman problem. Technical report, Graduate School of Industrial Administration,
Carnegie-Mellon University, (1976).
[6] E.W. Dijkstra. A note on two problems in connexion with graphs. Numerische
Mathematik, (1959), 1(1), pp. 269–271.
[7] D. Eppstein. Finding the k shortest paths. Society for Industrial and
Applied Mathematics Journal on Computing (SICOMP), (1998), 28(2),
pp. 652–673.
[8] A. Gy¨orgy, T. Linder, G. Lugosi and G. Ottucs´ak. The on-line shortest
path problem under partial monitoring. Journal of Machine Learning
Research, (2007), 8, pp. 2369–2403.
[9] L. H¨ame and H. Hakula. Dynamic journeying under uncertainty. European
Journal of Operational Research, (2013), 225(3), pp.455–471.
[10] A. Kalai and S. Vempala. Efficient algorithms for online decision problems.
Journal of Computer and System Sciences, (2005), 71, pp. 291–307.
[11] K.H. Kao, J.M. Chang, Y.L. Wang and J.S.T. Juan. A Quadratic Algorithm
for Finding Next-to-Shortest Paths in Graphs. Algorithmica,
(2011), 61, pp.402–418.
[12] D. Karger and E. Nikolova. Exact algorithms for the Canadian
traveller problem on paths and trees. Technical report,
MIT Computer Science &; Artificial Intelligence Lab, (2008). URL
http://hdl.handle.net/1721.1/40093.
[13] I. Krasikov and S.D. Noble. Finding next-to-shortest paths in a graph.
Information Processing Letters, (2004), 92, pp.117–119.
[14] K.N. Lalgudi and M.C. Papaefthymiou. Computing strictly-second
shortest paths. Information Processing Letters, (1997), 63, pp.177–181.
[15] G. Laporte. What you should know about the vehicle routing problem.
Naval Research Logistics (2007), 54(8), pp.811–819.
[16] G. Laporte. Fifty years of vehicle routing. Tranportation Science (2009),
43(4), pp.408–416.
[17] A. Larsen, O.B.G. Madsen, and M.M. Solomon. The a priori dynamic
traveling salesman problem with time windows. Transportation Science,
(2004), 38(4), pp.459–472.
[18] A. Larsen, O.B.G. Madsen, and M.M. Solomon. Recent Developments in
Dynamic Vehicle Routing Systems. In: B. Golden, S. Raghavan, and E.
Wasil (Eds.), The Vehicle Routing Problem: Latest Advances and New
Challenges, Operations Research/Computer Science Interfaces, Springer
Science Publishers, (2008), 43, pp.199–218.
[19] S. Li, G. Sun and G. Chen. Improved algorithm for finding next-toshortest
paths. Information Processing Letters, (2006), 99, pp.192–194.
[20] C.H. Papadimitriou and M. Yannakakis. Shortest paths without a map.
Theoretical Computer Science, (1991), 84(1), pp. 127–150.
32
[21] V. Pillac, M. Gendreau, C. Gu´eret, and A.L. Medaglia. A review of
dynamic vehicle routing problems. European Journal of Operational Research,
(2013), 225(1), pp.1–11.
[22] H.E. Psaraftis. Dynamic vehicle routing problems. In: B. Golden, A.
Assas (Eds.), Vehicle Routing: Methods and Studies, Elsevier Science
Publishers, (1988), pp.223–248.
[23] H.E. Psaraftis, J.N. Tsitsiklis. Dynamic shortest paths in acyclic networks
with markovian arc costs. Operations Research, (1993), 41(1),
pp.91–101.
[24] D. Sleator and R.E. Tarjan. Amortized efficiency of list update and
paging rules. Communications of the ACM, (1985), 28, pp. 202–208.
[25] B. Su and Y.F. Xu. Online recoverable Canadian traveller problem. In
Proc. of the International Conference on Management Science and Engineering,
(2004), pp.633–639.
[26] B. Su, Y.F. Xu, P. Xiao, and L. Tian. A risk-reward competitive analysis
for the recoverable Canadian traveller problem. In Proc. of the 2nd
Conference on Combinatorial Optimization and Applications (COCOA),
(2008), LNCS 5165, pp. 417–426.
[27] B.W. Thomas and Chelsea C. White III. Anticipatory route selection.
Transportation Science, (2004), 38(4), pp.473–487.
[28] B.W. Thomas and Chelsea C. White III. The dynamic shortest path
problem with anticipation. European Journal of Operational Research,
(2007), 176, pp.836–854.
[29] S. Westphal. A note on the k-Canadian traveller problem. Information
Processing Letters, (2008), 106, pp. 87–89.
[30] Y.F. Xu, M.L. Hu, B. Su, B.H. Zhu, and Z.J. Zhu. The Canadian traveller
problem and its competitive analysis. Journal of combinatorial optimization,
(2009), 18, pp.195–205.
[31] H. Zhang and Y.F. Xu. The k-Canadian traveller problem with communication.
In Proc. of the 5th International Frontiers of Algorithmics
Workshop (FAW-AAIM), (2011), LNCS 6681, pp. 17–28.
34
連結至畢業學校之論文網頁點我開啟連結
註: 此連結為研究生畢業學校所提供,不一定有電子全文可供下載,若連結有誤,請點選上方之〝勘誤回報〞功能,我們會盡快修正,謝謝!
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top