二次指派問題在設施規劃上之應用--以捷運機廠佈設為例

Abstract

設施規劃問題係考慮設施佈設時的最小成本；目前一般應用於：工廠 佈置、電路板繞線設計、平面單一設施設置、儲存系統佈線及網路位置方 電等各方面。進行設施規劃工作時，可發覺針對設施規劃所建立之數學目 標式，具有二次指派問題型式。 二次指派問題本身具有離散、非線性 及非凸性整數規劃問題等特性，並已被Sahni & Gonzalez證明其屬於NP- Hard問題，因此二次指派問題的精確解演算法複雜性非常高，所以有必要 發展啟發式解法以確保在可接受時間內求得精確度高的近似最佳解。而大 部份傳統的啟發式解法屬於區域搜尋技術，所求到的結果只能保證為區域 最佳解。本研究之主要目的係針對設施規劃問題，應用近期發展中的智慧 型啟發式解法－門檻值接受法及記錄更新法，做為全域搜尋技術基礎，使 求解二次指派問題時能夠跳離區域最佳解情形，並使用目前國際上已發表 文獻中所提出的題庫做為測試基礎；此外為考量實際面臨設施佈設問題時 將面臨的情況，提出一考量到設施受限制的數學模式，同時選取一實際捷 運機廠，對其內部設施間各項交互成本、流量予以量化，建立出一考量到 設施受限制的二次指派問題數學模式，並以本研究所發展之演算法求解， 期能做為將來捷運機廠設施佈設時的參考。 怳p成本；目前一般應用於： 工廠 The problem for facility planning is considered for get minimize cost of the facility layout. There have been many other proposed applications of these, forexample, factory layout problems, circuit layout on PCB, plannar facility layout, information retrieval for storage facility and site position in network., etc. We can find this kind problem can be modelled as a Quadratic Assignment Problem (QAP).Quadratic assignment problem is a discrete, nonlinear, nonconvex problem. Sahni and Gonzale have been proved it belong to the class of NP-hard problems, which are not likely to be solved exactly in the reasonable time. And most traditional heuristic can only offer the technical for local search method. Get the cost can only be optimal solution.In this research, the main purpose is try to solve the problem of facility planning, using these AI heuristic that developed in recently, Threshold Accepting (TA), Record to Record Traveling (RRT), to be the kind technology for global searching. Use testing problems in QAPLIB for test AI heuristic efficient and cost. When considering the practical problem will meet the situation for site constraint , therefore we make a new mathematical model for solve this problem. After modelling, use an example from factory of the mass rapid transit, then use the AI heuristics that we developed for solve this example. lity planning is considered for get minimize cost of the