楊烽正臺灣大學：工業工程學研究所余致緯YU, Chih-WeiChih-WeiYU2007-11-232018-06-292007-11-232018-06-292005http://ntur.lib.ntu.edu.tw//handle/246246/49098本研究提出仿電磁吸斥離散優化演算法，求解物件排序優化問題及物件分群優化問題。求解問題包括旅行銷售員問題、裝箱重量均等問題、及節點著色問題。本研究針對物件排序優化問題本研究提出「虛擬映射」和「真實映射」兩種粒子移動模式及四種連續座標值映射成離散值的「離散映射作業」法。至於物件分群優化問題，本研究以區間指派法求解裝箱重量均等問題。針對有容量限制的裝箱重量均等問題提出懲罰函數及嘗試修補機制求解。求解節點著色問題是應用群合併法將節線限制問題轉成物件著色群合併作業的排序問題，最後並以求解物件排序優化法求解。本研究成功地擴展仿電磁吸斥優化演算法的應用範圍，使能求解組合優化問題。研究並測試甚多標竿問題的測試顯示效能甚佳。This thesis proposes a new heuristic based on Electromagnetic-like mechanism （EM）. The method can be used in object sequencing problem and object grouping problem. It still contains an attraction-repulsion mechanism to move the particles towards the global optimality together. The object sequencing problem includes Traveling Salesman Problem（TSP）. The object grouping problem contains Bin Packing Balance Problem and Vertex Coloring Problem（VCP）. In solving object sequencing problem, the thesis proposes two scenario：Keep Continued and Keep Discritied, and also proposes four methods about Discritied Mapping Operation. In solving object grouping problem, the thesis uses Interval Assignment method to solve Bin Packing Balance Problem. The thesis uses Penalty Function and Repair Method to solve Bin Packing Balance Problem with Limited Capacity. In solving Vertex Coloring Problem, the thesis uses Merge Method（Juhos）and solving object sequencing problem methods. Some test results about Benchmark problem of these problems are included. The method extends successfully to discrete problems. We hope the thesis introduces EM to more researchers. More researches can be attracted to EM, more problem can be solved by EM.誌謝 i 摘要 ii Abstract iii 目錄 iv 圖目錄 vi 表目錄 vii 中英文名詞對照表 viii 中英文名詞對照表 viii 符號說明 ix 第1章 緒論 1 1.1 研究背景 1 1.2 研究動機 2 1.3 研究目的 3 1.4 研究範疇及流程 4 1.5 章節概要 6 第2章 文獻探討 7 2.1 常見的啟發式演算法 7 2.2 仿電磁演吸斥優化演算法 8 2.3 旅行推銷員問題(Traveling Salesman Problem) 15 2.4 裝箱問題(Bin Packing Problem) 18 2.5 節點著色問題(Vertex Coloring Problem) 21 2.6 常見求解旅行銷售員問題的區域搜尋方法 24 2.7 文獻探討結語 27 第3章 仿電磁吸斥離散優化演算法應用於物件排序與分群優化問題 28 3.1 優化問題介紹 28 3.1.1 物件排序優化問題 28 3.1.2 物件分群優化問題 29 3.2 仿電磁吸斥離散優化演算法求解模式 31 3.3 物件排序問題之仿電磁吸斥離散優化演算法 34 3.3.1 物件排序主流程 34 3.3.2 虛擬映射模式與真實映射模式的差異 46 3.4 仿電磁吸斥離散優化演算法的跳動搜尋作業應用於物件排序 47 3.5 物件分群問題之仿電磁吸斥離散優化演算法 48 3.5.1 求解裝箱重量均等問題的主流程 49 3.5.2 求解有容量限制的裝箱重量均等問題的流程 54 3.5.3 求解節點著色問題的流程 59 3.5.4 群合併法 64 3.5.5 範例展示 73 3.6 小結 78 第4章 系統介紹及範例驗證 80 4.1 仿電磁離散優化系統介紹 80 4.2 自動讀檔動態鏈結庫的功能介紹 90 4.3 旅行銷售員問題範例演練 91 4.4 裝箱問題範例演練 95 4.5 節點著色問題範例演練 97 4.6 標竿問題測試 100 4.7 小結 108 第5章 結論與未來研究建議 109 5.1 結論 109 5.2 未來研究方向與建議 110 參考文獻 111en-US仿電磁吸斥優化演算法物件排序優化問題物件分群優化問題旅行銷售員問題節點著色問題裝箱問題Electromagnetic Attraction and Repulsion Optimization Algorithm.Object Sequencing ProblemsObject Grouping ProblemsTraveling Salesman ProblemVertex Coloring ProblemBin Packing Problemthesis