模糊軸式三維指派問題的演算法探討

An Algorithm for Solving Fuzzy Axial Three-Dimensional Assignment Problem

謝百翰(Bai-Han Hsieh)

指導教授 ： 溫于平 ； 林吉仁

國立清華大學/工學院/工業工程與工程管理學系/碩士(2013年)

摘要

模糊軸式三維指派問題是軸式三維指派問題的延伸。在指派成本模糊化的情況下，我們無法直接使用針對軸式三維指派問題的方法進行求解。在回顧過去的文獻過程中，我們發現分支界限法是很適合求解此問題的精確解演算法。然而分支界限法的正確率雖然很高，但卻有著如窮舉法一般的低效率。因此，我們針對模糊軸式三維指派問題建構了一個改良式的分支界限法，稱之為投影分支界限法。本論文提出投影分支界限法將三維空間投影至二維的平面，再利用求解二維指派問題的匈牙利法得到分支的界限，最後再將所得到的界限轉換回三維空間做運算。如此一來維持了正確率高的特性，同時也提高了演算的效率。藉由測試題組的結果顯示，本研究所提出的投影分支界限法優於先前文獻中所提出的演算法。

關鍵字

軸式三維指派問題 ； 模糊指派問題 ； 分支界限法 ； 匈牙利法

並列摘要

Fuzzy axial three-dimensional assignment problem is an extension of axial three-dimensional assignment problems. In this situation, when the assignment cost is fuzzied, we cannot use the traditional algorithms for solving axial three-dimensional assignment problems to solve the variant assignment problem. In reviewing the literatures, we find out that the B&B algorithm is a suitable way to find the exact solution of this kind of problem. However, the existing B&B algorithm has low efficiency as the complete enumerational procedure. For this reason, we propose an improved B&B algorithm for solving fuzzy axial three-dimensional assignment problem called the projected B&B algorithm. We first transfer the fuzzy axial three-dimensional assignment into two dimensions, then use the projection method followed by the Hungarian algorithm to obtain the upper bound of the resulting problem. In this way, we maintain the high accuracy and improve the efficiency. In order to demonstrate the procedure of the proposed algorithm, we present a numerical example in this thesis. Besides, computational results show that the performance of the proposed algorithm is superior to the existing algorithm for solving the fuzzy axial three-dimensional assignment problem.

並列關鍵字

Axial three-dimensional assignment problem ； Fuzzy assignment problem ； The B&B algorithm ； The Hungarian method

參考文獻

Alan, F., Gregory, B. S. (2013). Efficient algorithms for three-dimensional axial and planar random assignment problems, Data Structures and Algorithms.

Balas, E., Saltzman, M. J. (1991). An Algorithm for the Three-Index Assignment Problem, Operations Research, vol. 39, pp. 150-161.

Bellman, R. E., Zadeh L.A. (1970). Decision-Making in a Fuzzy Environment, Management Science, vol. 17, pp. 141-164.

Chanas, S., Kuchta, D. (1996). A concept of the optimal solution of the transportation problem with fuzzy cost coefficients, Fuzzy Sets and Systems, Vol. 82, pp. 299–305.

Chanas, S., Kuchta, D. (1998). Fuzzy integer transportation problem, Fuzzy Sets and Systems, Vol. 98, pp. 291–298.