臺灣博碩士論文加值系統

(44.200.86.95) 您好！臺灣時間：2024/05/20 08:42

:::

詳目顯示

:

• 被引用: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誌謝ContentsList of Figures and TablesIntroductionPreliminariesDouble-valued GraphThe Uniform Jam Cost Modelk-CTP for Metric TSPRandomized algorithmConclusionReferences