模糊軸式三維指派問題是軸式三維指派問題的延伸。在指派成本模糊化的情況下,我們無法直接使用針對軸式三維指派問題的方法進行求解。在回顧過去的文獻過程中,我們發現分支界限法是很適合求解此問題的精確解演算法。然而分支界限法的正確率雖然很高,但卻有著如窮舉法一般的低效率。因此,我們針對模糊軸式三維指派問題建構了一個改良式的分支界限法,稱之為投影分支界限法。本論文提出投影分支界限法將三維空間投影至二維的平面,再利用求解二維指派問題的匈牙利法得到分支的界限,最後再將所得到的界限轉換回三維空間做運算。如此一來維持了正確率高的特性,同時也提高了演算的效率。藉由測試題組的結果顯示,本研究所提出的投影分支界限法優於先前文獻中所提出的演算法。
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.
為了持續優化網站功能與使用者體驗,本網站將Cookies分析技術用於網站營運、分析和個人化服務之目的。
若您繼續瀏覽本網站,即表示您同意本網站使用Cookies。