應用基因演算法求解優先順序旅行推銷員問題

A Genetic Algorithm for the Sequential Ordering Problem

廖雯慈(Liaw Wen-Tsu)

指導教授 ： 徐旭昇

元智大學/工程學院/工業工程與管理學系/碩士(1998年)

摘要

優先順序旅行推銷員問題（Sequential Ordering Problem，SOP），是一個非對稱的旅行推銷員問題（Asymmetric Traveling Salesman Problem）加上優先順序的限制。其定義為：有N個城市，城市與城市間來去的距離並不相等，試找出一條路徑能夠拜訪每一個城市一次，使得該路徑之總距離為最小，並符合拜訪各城市間的優先順序條件。基因演算法（Genetic Algorithms，GAs）的應用領域已相當廣泛，但尚未有學者應用基因演算法於限制條件較為嚴格的規劃模式中，而SOP即是屬於此類問題，因此本研究旨在將Gas應用於求解SOP。
本研究首先設計適用於SOP之基因運算元，再透過田口實驗設計方法（Taguchi Method）得到一最佳參數設定組合，最後以此最佳參數組合測試系統績效，採用TSPLIB中SOP題庫做為測試題目。本研究之基因演算法之績效測試得到誤差率平均10％的結果。

關鍵字

優先順序旅行推銷員問題 ； 基因演算法 ； 田口方法

並列摘要

Sequential ordering problem is an asymmetric traveling salesman problem with precedence constraints. Given a set of n nodes and the distances between each pair of nodes, find a path from node 1 to node n with minimal distance, taking the given precedence constraints into account. Each precedence constraint requires that some node i have to be visited before some other node j.
Although Genetic Algorithm has already been used widely today, no scholar has applied Genetic Algorithms in a programming model with straitlaced constraints which sequential ordering problem belongs to. Therefore, the main purpose of this research is to apply Genetic Algorithm on sequential ordering problem.
This research first developed the genetic operators applicable to sequential ordering problem, then found the best parameters through the Taguchi method. It then used the best parameters to test my Genetic Algorithm, using the test problems taken from the TSPLIB, which is a library of traveling salesman and related problem instances. The test result of this research''s Genetic Algorithm has an average error ratio of 10%.

並列關鍵字

Sequential Ordering Problem ； Genetic Algorithm ； Taguchi method

參考文獻

〔1〕 Bui T. N. and Moon B. R., "A New Genetic Approach for the Traveling Salesman Problem," in Proceedings of the First IEEE Conference on Evolutionary Computation, vol.1, pp.7-12, 1994.

〔2〕 Chyu C. C. and Yeh H. P., "A Tabu Search Heuristic for the Traveling Salesman Problem with Precedence Constraints," Automation ''98 and ICPR Asia Meeting, A2-2, pp.1-6, 1998.

〔6〕 Escudero L. F., Guignard M., and Malik K., "A Lagrangean relax-and cut approach for the sequential ordering problem with precedence constraints," Annals of Operations Research, Vol.50, pp.219-237, 1994.

〔7〕 Fox B. R. and McMahon M. B., "Genetic Operators for Sequencing Problems," Foundations of Genetic Algorithms, Morgan Kaufmann Publishers, 1991.

〔8〕 Forrest S., "Genetic Algorithms: Principles of Natural Selection Applied to Computation," Science, Vol.261, pp.872-878, 1993.