含凹形節線成本最小成本轉運問題鄰近搜尋法之研究

Neighborhood Search Algorithms for Concave Cost Transshipment Problems

顏上堯(Shang-Yao Yan) ； 陳建榮(Chien-Rong Chen) ； 湯慶輝(Chin-Hui Tang)

《運輸計劃季刊》 33卷2期 (2004/06) Pp. 277-306

https://doi.org/10.6402/TPJ.200406.0277

摘要

傳統在最小成本轉運問題的定式上，常以線性方式來定義運送成本，藉以簡化問題的複雜度。在實務上，貨物運送的單位成本常隨數量的增加而遞減，成本函數曲線為凹形。以往有不少含凹形成本節線之研究，但侷限於不同之特殊網路且方法屬傳統區域搜尋法或傳統啟發解法，近期雖有學者開始以新近鄰近搜尋法求解簡化的運輸問題，以達到較大範圍的搜尋方式，期能找到較優於傳統啟發解法的解，卻忽略運輸網路常見的轉運問題。緣此，本研究針對含凹形節線成本一般性最小成本網路流動問題，參考新近鄰近搜尋法，如門檻值接受法與大洪水法，發展有效率的鄰近搜尋法，以求解問題。在求解的方法上，本研究首先設計適合凹形成本網路流動特性之初始解產生方法，快速得到一組解，再使用新近鄰近搜尋法的改善機制以達到改善效果，以找到近似最佳解。為測試本研究演算法在不同規模及參數的網路問題的求解績效，本研究設計一隨機網路產生器，產生大量的隨機網路，並以C++語言撰寫所有相關的電腦程式，在個人電腦上測試分析。測試結果顯示，本研究採行的方式求解品質良好。

關鍵字

鄰近搜尋 ； 凹形節線成本 ； 轉運問題 ； 門檻值接受法 ； 大洪水法

並列摘要

The minimum cost transshipment problems are traditionally defined as a linear cost problem, to reduce problem complexity. In reality, the unit cost decreases as the amount transported increases, resulting in a concave cost function. Great efforts have been devoted to the development of solution algorithms. However they were confined to specical transportation networks. Besdies, their methods were focused on local search algorithms or traditional heuristics. Recently, researchers began to use advanced neighborhood search algorithms to solve concave cost bi-partite transportation network problems to enlarge search area and find near-optimal solutions. This type of research, however, neglected flow transfers in transportation networks. We developed two neighborhood search algorithms referring to the threshold accepting algorithm and the great deluge algorithm to efficiently solve transshipment problems. Problem characteristics were first explored to efficiently generate initial solutions, which are then improved by neighborhood search algorithms to near-optimal solutions. To evaluate the proposed neighborhood search algorithms, we designed a randomized network generator to produce many test problems. We employed C++ computer language to code all necessary pro grams and perform tests on personal computers. The results show that the developed neighborhood search algorithms performed well in the tests.

並列關鍵字

Neighborhood search ； Concave arc cost ； Transshipment problem ； Threshold accepting algorithm ； Great deluge algorithm