即時路徑規劃：從演算法角度探討加拿大旅行者問題

Online Route Planning: Exploring the Canadian Traveller Problem from an Algorithmic Point of View

黃彥銘(Yam-Ming Huang)

指導教授 ： 廖崇碩

國立清華大學/工學院/工業工程與工程管理學系/碩士(2013年)

摘要

本研究探討即時路徑規劃的加拿大旅行者問題，其可實際應用在動態導航系統等，可用以避免交通阻塞的發生。對於一個有固定起點 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.

並列關鍵字

Canadian traveller problem ； competitive ratio ； online algorithm

參考文獻

[1] B. Awerbuch and R. Kleinberg. Online linear optimization and adaptive

[2] A. Bar-Noy and B. Schieber. The Canadian traveller problem. In Proc. of

[4] A. Borodin and R. El-Yaniv. Online computation and competitive analysis.

[6] E.W. Dijkstra. A note on two problems in connexion with graphs. Numerische

[7] D. Eppstein. Finding the k shortest paths. Society for Industrial and