具差異性替選道路演算法之研究

An Algorithm For Finding Dissimilar Alternate Paths

陳冠佑(Kuan-Yu Chen)

指導教授 ： 王晉元

國立交通大學/管理學院/運輸科技與管理學系/碩士(2009年)

https://doi.org/10.6842/NCTU.2009.00585

摘要

替代道路的資訊對於用路人而言是相當重要的參考依據。良好的替代道路可以讓用路人有效地避開擁塞的路段，縮短旅次時間。對於社會而言，能提高公路容量利用率，降低整體社會成本。然而若提供的替代道路數量過少，在車流量極大的狀況下，這些替代道路仍舊可能無法應付這龐大的車流，造成擁塞。因此若能提供足夠數量的替代道路，將能更有效的進行車輛分流，提昇道路的容量利用率。在過去的應用中，通常以k條最短路徑(k shortest path problem, ksp)為求解多條替代道路演算法。此演算法雖可計算出成本差異最小的替代道路，但對於用路人而言，過多的重疊會造成此替代道路無替代效果。本研究認為好的替代道路應在經過路段上有一定的差異度，而總成本的差異也必須在可接受範圍內，如此的替代道路方有分散並吸引車流的效果。因此本研究以k條最短路徑演算法做為基礎，加入重覆避免與過濾機制，可在有限的時間內透過預先刪除易重複路段，以及加入最大重疊度判斷的權重影響，求得滿足需求數量且具有差異性的最短路徑，同時這些路徑間的成本差距也在一定的範圍之內，足以做為替代道路資訊發佈的求解演算法。

關鍵字

替代道路 ； 最短路徑 ； k條最短路徑演算法

並列摘要

Alternate paths information is very important for road users. Well design alternate paths can help road users avoid crowded roads to shorten their travel time and improve transportation efficiency.
K shortest paths(KSP) algorithm is normally used to generate alternate paths. However, these k shortest paths are very similar in term of their geomantic shapes. In many applications, especially transportation routing planning, this similarity characteristic cause serious implementation difficulties for practical application.
This paper introduced an effective algorithm to generate alternative paths. We considered the “good” alternative paths must have enough variance in passed arcs and little different in travel distance. So we defined two indicators, overlapping and detour, to identify the quality of alternative paths. We build an algorithm based on Yen’s ksp algorithm and pre-delete some arcs that may cause high overlap and put overlapping distance into consideration before choose each shortest path.
In order to evaluate this algorithm, we compare it with IPM and CKSP in several scenarios and network types. The result is this algorithm may use more computing time, but it takes great advantage in paths quality and solving ability. The alternative paths that generated from my algorithm are requested to be geographically different and also requested to have little different in travel distance.
This algorithm is useful in real-time path guiding system. It can provide road users several paths to avoid jammed arcs and disperse traffic flow. In the other hand, it can use to solve hazardous material transportation problem, decrease the risk of effected area.

並列關鍵字

Alternate Paths ； Shortest Path ； K Shortest Paths

參考文獻

2. G.-H. Chen and Y.-C. Hung, Algorithms for the constrained quickest path problem and the enumeration of quickest paths, Computers & Operation Research, 21 (1994), pp. 113-118.

3. Y. L. Chen, An algorithm for Finding the k quickest paths in a network, Computers & Operation Research, 20 (1993), pp. 59-65.

4. Y. L. Chen, Finding the k quickest simple paths in a network, Inform. Process. Letter, 50 (1994), pp. 89-92.

6. N. Katoh, T. Ibaraki, and H. Mine, An efficient algorithm for K shortest simple paths, Networks, 12 (1982), pp. 411-427.

7. E. L. Lawler, A procedure for computing the K best solutions to discrete optimization problems and its application to the shortest path problem, Management Science, 18 (1972), pp. 401- 405.