替選方案產生模式在最短路徑與節線排程問題中之應用

Abstract

決策者在使用數學模式求解公共政策問題時, 常因一些無法量化或事先得 知的因素, 使得所找出的最佳解或近似最佳解, 不能滿足決策者所需。為 此原因有些學者提出替選方案產生模式的方法, 希望藉由這些方法產生一 些與最佳解在目標值上差距不大, 但解的形態卻有較大差異的替選方案, 用於解釋最佳解未能考量的因素, 提供給決策者較佳的選擇。本研究的目 的是將替選方案產生模式的方法應用在兩個交通運輸問題上, 即最短路徑 與容量限制性節線排程問題, 找出這兩個問題的替選方案產生模式。在以 往的研究中以k 條最短路徑做為最短路徑的替選方案, 而其替選方案產生 模式就是k 條最短路徑演算法。本研究則提出一個新的k 條最短路徑演算 法, 除演算複雜度比現有的演算法好外, 新演算法更能用於產生不限制迴 圈出現的k 條最短路徑與限制迴圈出現的k 條最短路徑兩種情形, 而再將 新演算法擴充至一對多的k 條最短路徑演算法時, 因只需重複新演算法的 幾個步驟, 所以此時新演算法的演算複雜度亦比現有演算法好。本研究在 第二部份的容量限制性節線排程問題探討上, 先回顧現有容量限制性節線 排程問題的演算法, 並收集其它公共政策問題所使用的替選方案產生模 式, 運用現有的演算法, 發展出適合於容量限制性節線排程問題的替選方 案產生模式。並提出一個相對性的差異度指標, 用於比較兩個容量限制性 節線排程問題的差異性, 並將這個差異度指標加入容量限制性節線排程問 題的數學規劃式中, 提出一個容量限制性節線排程問題的三級跳法 , 並 設計求解此三級跳法的演算法, 而發展出一個具有理論基楚的替選方案產 生模式。 A mathematical model is generally not a perfect representation of a complex real world planning problem, especially for some unmodeled factors. There are some alternate solutions that are nearly the same with respect to the objectives but are drastically different from each othre in decision space. Some of these alternatives probably can explain more regarding those un- modeled issues. Modeling to generate alternatives(MGA) technique have been designed to serve this purpose. This research uses MGA techniques on both the shortest path and Capacitated Arc Routing Problem(CARP). K-shortest path algorithms can be viewed as the MGA of the shortest path. An efficient k-shortest path algorithm is devel- oped in the firest part of this study. This algorithm is suit- able for directed graphs as well as undirected graphs. Also, the generate paths can contain cycles or no cycles, depending on user's specification. The complexity analysis demonstrates that this newly developed algorithm is better than other existing al- gorithms under most circumstances. The second part of this study focus on generating alternatives for CARP. We begin with designing a new index for measuring di- fferences between sets of routes. Then, a MGA technique called the Hop, Skip and Jump( HSJ) is introduced for this purpose. A heuristic algorithm for integrating HSJ into CARP platform is also develop. Some synthetic examples are given to illustrate this idea and its implementation.