以進化式演算法於QAP問題之應用

Use of Evolutionary Computation approaches for the Quadratic Assignment Problem

白貿元(Mao-Yuan Pai)

國立虎尾科技大學/管理學院/資訊管理研究所/碩士(2007年)

摘要

本研究主要探討對於非線性多類產品生產線（multi-product flowline）的機器位址指派問題於決策上如何同時考量多種類產品於不同機器設備之間的流量以及其被傳輸移動距離達到最小。產品於生產線之機器設備之動線流量除了單向性外更考量雙向性的流動因素，換言之、因不同機器位置的配置會影響兩部機器設備間產品遞送的距離而呈現動態之非線性模式。而相關研究仍被廣泛的應用，例如製造系統，運籌管理，數位資料儲存配置等等都是二指派問題（Quadratic Assignment Problem; QAP），這些問題都是二次指派問題（QAP），雖然應用相當廣泛且多樣，但QAP仍為難以解決的NP-hard問題。由於二次指派問題的複雜特性使得數學規劃方法求解變得困難，然而實際的機器配置問題規模常大於20，因此使用啟發式方法取代數學規劃方法是值得思考。
透過本研究所發展出交換機制來提升進化式演算法求解的能力，能夠避免在最佳化過程中陷入區域最佳解中。利用QAPLib所提供測試資料，我們發現多重最佳解可以透過本研究所利用的進化式演算法求得，證明本研究所利用的進化式演算法能有效求得多重最佳解。

並列摘要

This research is to investigate the nonlinear multi-product flowline machine allocation assignment problems, in which the product flow and distance between any pair of machines are to be considered for minimizing the total product flow distance so as to minimize the total cost. These problems are characterized as the quadratic assignment problem (QAP). The problems with the symmetrical distance between two machines and bi-directional flow are considered. In other words, the distance between two machines is changeable based on the machine location assignment. It makes the objective coefficients become dynamic with high nonlinear property. This study in practice is widely applied. For example, it can be used in manufacturing system, logistic management, the storage of digital data in disc or magnetic tape, etc. It belongs to the NP-hard problem so that it makes the solution finding be more difficult and complex. By using the traditional mathematic programming approach will be impractical because only the problems with n ≤ 20 can be solved but not for the large size problems. So, the heuristic methods are to be considered for solving the QAP problems.
Two evolutionary computation based approaches with swap procedure are proposed for finding the optimal or near optimal solutions. Above all, when the optimal solution is not unique, the multiple optimal solutions can be obtained by using the one of the proposed methodologies. The proposed methodologies are tested by using the benchmarking testing problems in QAPLib. Numerical results indicated that the proposed approaches can find the solutions as well as other approaches.

參考文獻

1.Ahuja, R. K., Orlin, J. B., and Tiwari, A. (2000), “A greedy genetic algorithm for the quadratic assignment,” Computers and Operations Research, 27, pp.917-934.

2.Aneke, N. A. G., and Carrie, A. S. (1986), “A design technique for the layout of multi-product flowlines,” International Journal of Production Research, 24, pp.917-934.

4.Bandara, S., and Wirasinghe, S. C. (1992), “Walking distance minimization for airport terminal configurations,” Transportation Research-A, 26(1), pp.59-74.

5.Bazara, M. S., and Kirca, O. (1983), “A branch-and-bound heuristic for solving the quadratic assignment problem,” Naval Research Quarterly, 30, pp.287-304.

6.Bozer, Y. A., Meller, R. D, and Erlebacher, S. J. (1994), “An improvement-type layout algorithm for single and multiple-floor facilities,” Management Science, 40, pp.918-932.