淡江大學覺生紀念圖書館 (TKU Library)
進階搜尋


下載電子全文限經由淡江IP使用) 
系統識別號 U0002-1607200920573400
中文論文名稱 演化演算法應用於結合正逆向物流之多目標區位網路設計問題之研究
英文論文名稱 A Study on the Application of Evolutionary Algorithm on Multiple Objective Location Network Design with Forward and Reverse Logistics
校院名稱 淡江大學
系所名稱(中) 運輸管理學系碩士班
系所名稱(英) Department of Transportation Management
學年度 97
學期 2
出版年 98
研究生中文姓名 江鎮宇
研究生英文姓名 Chen-Yu Chiang
學號 696660397
學位類別 碩士
語文別 中文
口試日期 2009-06-15
論文頁數 100頁
口試委員 指導教授-邱顯明
委員-顏上堯
委員-石豐宇
中文關鍵字 多目標規劃  柏瑞圖最佳解  演化演算法  逆物流  區位問題 
英文關鍵字 Multi-Objective Programming  Pareto Optimal Solution  Evolutionary Algorithm  Reverse Logistics  Location Problem 
學科別分類 學科別社會科學管理學
中文摘要 以企業經營實務而言,必需面對處理越來越多有關產品退貨、維修及回收等關係到顧客滿意度之服務;而且面對越來越嚴格的環保法律要求,廢棄產品再利用與再生資源之利用已經成為企業經營的關鍵議題之一。企業不管是面對顧客滿意度,以及法律與獲利等因素,都必須要正視產品回收的問題,這將是企業面臨這股綠色浪潮的機會與挑戰。
再者,現今企業已經花許多心力在採購生產和產品運輸等作業上,而運輸成本佔總成本的比例為最大宗,又因環境和法規的因素,企業不得不再投入成本在回收服務上,使得成本負擔更加吃力。根據Rogers et al.(2001)的研究指出,若將逆物流和正物流產品分別獨立處理,會花費許多成本在運送逆物流產品上。若有第三方物流公司(3PL)可以同時分擔正逆向物流服務的部份,提供倉儲設施執行儲存運送作業,廠商不需增設回收設施,不僅可以提供專家經驗意見和更廣的視野,也可以分散成本風險。
本研究在模式構建上主要是以第三方物流業者與廠商兩方面為出發點,考量系統總成本最小化、顧客涵蓋數最大化及設施平均利用率差異最小化等目標,來構建多目標區位指派模式。問題的求解則是以C 語言自行撰寫改良之演化演算法進行求解。
以自行設計的兩個小型範例配合窮舉法來驗證模式的正確性,並利用此結果來進行演算法的正確性測試;並以區位標竿例題來測試本研究設計之演算法,對於其它區位模式之精度與效度;與張立偉(2001)所設計之基因演算法比較測試,以範例二與大型問題(一)來比較兩者的求解品質,由測試結果可知本研究演算法之求解品質較佳。最後分別求解大型問題(一)、(二)之柏瑞圖最佳解,與情境敏感度分析。經由多次的測試,發現最小系統總成本與最大顧客涵蓋數之間呈反向關係;最大顧客涵蓋數與最小設施平均使用率差異之間呈反向關係;最小系統總成本與最小設施平均使用率差異之間呈些許正向關係,但不完全正向。由權衡結果可知合乎一般的邏輯性,更可證明本模式正確性,具有應用價值,可以作為實務單位營運決策之參考。
英文摘要 In business practical operation, enterprises have to face problems related to services of customer satisfaction such as product returning, maintenance and recycling; with the ever-increasingly stricter laws and requests related to environmental protection, the recycling of discarded product and use of recycling resources have become one of the key issues of business management. From the perspectives of customer satisfaction, laws or profit, enterprises have to face the problem of product recycling which will be their opportunities and challenges under this green wave.
Moreover, nowadays many enterprises have devoted efforts in purchase, production and transportation, among them, transportation is the most cost, but due to environment and laws, they have to invest funds in recycling services which will further increase their cost. The study of Rogers et al. (2001) showed that if enterprises deal with products of reverse and forward logistics respectively, then the cost of transporting products of reverse logistics will be higher. A third-party logistics (3PL) company can deal with products of both reverse and forward logistics, provide warehousing facilities and implement warehousing and transportation operations, so that enterprises do not have to set up recycling facilities. They can not only offer advices of past experiences and professional opinions but also provide a broader view and lower the risk of cost.
In model construction, considering the minimization of total cost of system, the maximization of customer coverage number, and the minimization of difference of facility average utilization rate, this study constructed a multi-objective location-allocation model from the perspective of third-party logistics companies and enterprises. To solve the problem, a comprehensive solution procedure is developed based on Evolutionary Algorithm using C language.
This study used two self-designed examples coupled with enumeration to verify the validity of the model with solid result. In addition, the proposed procedure was applied to location benchmark examples to verify the validity of the algorithm. Compared with the genetic algorithm designed by Chang Li-Wei (2001), this study used example 2 and large question (1) to compare their solution quality; the test results indicated that the solution quality of the algorithm designed in this study was better. Finally, this study tried to find out Pareto optimal solution of large question (1) and (2) and conducted scenario sensitivity analysis. After many times of testing, it was found out that system total cost minimum and customer coverage number maximum was negatively correlated; customer coverage number maximum and minimum of facility average utilization rate difference was negatively correlated; system total cost minimum and minimum of facility average utilization rate difference was slightly positively correlated but not totally positively. The results were logical and the validity of this model was verified, and it could be used as decision support for operational decisions within enterprises.
論文目次 中文摘要
英文摘要
誌謝
目錄 i
表目錄 iv
圖目錄 vii
第一章、緒論 1
1.1 研究動機與背景 1
1.2 研究目的 2
1.3 研究範疇 4
1.4 研究方法與流程 4
1.5 論文內容 6
第二章、文獻回顧 7
2.1 逆物流 7
2.1.1 小結 9
2.2 基本區位模式 10
2.2.1 中位問題 10
2.2.2 中心問題 11
2.2.3 涵蓋問題 11
2.2.4 混合整數規劃問題 12
2.2.5 區位問題之相關文獻回顧 13
2.2.6 小結 16
2.3 多目標區位問題 18
2.3.1 多目標規劃基本原理介紹 18
2.3.2 多目標規劃之基本模式及求解方法 20
2.3.3 多目標逆物流區位問題相關文獻 24
2.3.4 小結 25
2.4 演化演算法 26
2.4.1 個體編碼表示方式 29
2.4.2 挑選運算元 29
2.4.3 交配運算元 30
2.4.4 突變運算元 31
2.4.5 小結 32
三、問題界定與模式建構 33
3.1 問題描述 33
3.1.1 基本假設 35
3.1.2 模式輸入輸出 36
3.2 模式建構 37
3.2.1 參數符號說明 37
3.2.2 數學模式 39
3.3 小結 41
第四章、演算法應用求解與程式設計 42
4.1 演算設計與解題流程 44
4.2 模式與演算法驗證 50
4.2.1 範例一 51
4.2.2 範例二 54
4.2.3 小結 57
4.3 改良演化演算法與基本基因演算法比較 58
4.3.1 小結 61
4.4 區位標竿例題測試 62
第五章、實驗設計 64
5.1 演算法參數設計比較 64
5.2 大型問題(一)之測試結果 67
5.2.1 各目標近似最佳解 67
5.2.2 多目標求解 68
5.3 大型問題(二)之測試結果 72
5.3.1 各目標近似最佳解 72
5.3.2 多目標求解 73
5.4 情境分析與參數敏感度分析 77
5.4.1 零售商需求量變動之情境分析 77
5.4.2 最少回收站設置數量之情境分析 80
5.4.2 成本參數變動之敏感度分析 82
5.5 小結 84
第六章、結論與建議 86
6.1 結論 86
6.2 建議 88
參考文獻 89
附錄一 94
附錄二 97
附錄三 99
表目錄
表2-1、國外逆物流區位文獻整理 16
表2-2、國內逆物流區位文獻整理 17
表2-3、國內外多目標逆物流區位問題 25
表2-4、基本名詞解釋 28
表2-5、選擇運算元類型 30
表2-6、交配運算元類型 31
表2-7、突變運算元類型 32
表4-1、範例一基本資料 51
表4-2、範例一參數資料 51
表4-3、範例一演算法參數資料 52
表4-4、範例一需求量資料 52
表4-5、範例一最小系統總成本 53
表4-6、範例一最大顧客涵蓋數 53
表4-7、範例一最小平均倉儲使用率差異 53
表4-8、範例二基本資料 54
表4-9、範例二參數資料 54
表4-10、範例二演算法參數資料 55
表4-11、範例二需求量資料 55
表4-12、範例二最小系統總成本 56
表4-13、範例二最大顧客涵蓋數 56
表4-14、範例二最小設施平均利用率差異 56
表4-15、範例二演算法參數設計比較 60
表4-16、範例二比較結果 60
表4-17、大型問題演算法參數設計比較 61
表4-18、大型問題比較結果 61
表4-19、標竿例題之演算法參數設計 62
表4-20、P1~P4之設施容量限制與設施建置成本 62
表4-21、P5~P8之設施容量限制與設施建置成本 63
表4-22、求解速度比較 63
表5-1、演算法世代數設計參數比較 65
表5-2、世代數參數設計結果比較 65
表5-3、演算法染色體數設計參數比較 66
表5-4、染色體數參數設計結果比較 66
表5-5、大問題(一)各目標近似最佳解 67
表5-6、150代各群體隨機產生之權重值 69
表5-7、執行150代各群體柏瑞圖解集合 69
表5-8、200代各群體隨機產生之權重值 70
表5-9、執行200代各群體柏瑞解集合 71
表5-10、大問題(二)各目標近似最佳解 72
表5-11、150代各群體隨機產生之權重值 73
表5-12、執行150代各群體柏瑞圖解集合 74
表5-13、200代各群體隨機產生之權重值 75
表5-14、執行200代各群體柏瑞圖解集合 76
表5-15、零售商需求量變化 78
表5-16、增加需求量之計算結果 79
表5-17、減少需求量之計算結果 79
表5-18、增加最少回收站數量計算結果 81
表5-19、減少最少回收站數量計算結果 81
表5-20、成本參數之變動 82
表5-21、運輸作業成本變動之計算結果 83
表5-22、設施建置營運成本變動之計算結果 83
圖目錄
圖1-1、研究流程圖 5
圖2-1、產品回收再利用示意圖 8
圖2-2、權重法求解圖示 22
圖2-3、柏瑞圖最佳解求解圖示 23
圖2-4、基本演化流程圖 28
圖3-1、網路架構圖 35
圖3-2、模式輸入輸出 36
圖4-1、分群演算法示意圖 43
圖4-2、2期染色體組合 44
圖4-3、分群示意圖 45
圖4-4、兩點交配示意圖 47
圖4-5、突變示意圖 48
圖4-6、本研究多目標演化演算法流程圖 49
圖4-7、基本基因演算法流程圖 59



參考文獻 中文部份
1. 王治元(2004),「智慧型基因演算法於多目標排程之發展與應用—以PCB鑽孔作業為例」,元智大學工業工程與管理學系碩士論文,民國93年。
2. 吳國碩(2007),「應用啟發式演算法於逆向物流網路系統之區位指派問題」,國立雲林科技大學工業工程與管理研究所碩士論文,民國96年。
3. 李軍、郭耀煌(2001),「物流配送車輛優化調度理論與方法」,中國物資出版社,民國90年。
4. 林祖德、樂以媛(2001),「我國流通頁電子化現況與展望-3C產業」,資策會商業電子化標準建立與制定計畫,民國90年。
5. 林耕全(2005),「裝修工程廢棄物回收站與再利用廠設置最佳化區位評選之研究」,國立中央大學營建管理研究所碩士論文,民國94年。
6. 林豐澤(2003),「演化式計算上篇:演化式演算法的三種理論模式」,智慧科技與應用統計學報,頁1-28,民國92年。
7. 林昆霖(2005),「子群體基因演算法於多目標排程之應用─以PCB鑽孔作業為例」,元智大學工業工程與管理學系碩士論文,民國94年。
8. 邱于家(2006),「醫療廢棄物逆向物流聯合處理營運模式之研究」,國立交通大學交通運輸研究所碩士論文,民國95年。
9. 邱顯明、鄭博王(1995),「以遺傳演算法應用於旅行推銷員問題」,中華民國運輸學會第十屆學術論文研討會論文集,民國84年。
10. 洪子盛(2003),「以模糊多目標規劃法求解消防站配置問題之最佳化」,國立成功大學工業管理科學研究所碩士論文,民國92年。
11. 張立偉(2001),「災後工程緊急搶修作業排程之研究」,淡江大學運輸管理研究所碩士論文,民國90年。
12. 張淑卿(2002),「臺灣地區廢電腦回收業市場研究」,輔仁大學應用統計學系在職專班碩士論文,民國91年。
13. 張嘉雄(2007),「混合演算法於多類型回收中心之逆物流系統之應用」,國立嘉義大學運輸與物流工程研究所碩士論文,民國96年。
14. 許志義(1994),「多目標決策」,五南圖書出版公司,台北市,民國83年。
15. 許義男(2008),「都市公共醫療設施區位規劃模型之設計與應用」,國立台北大學都市計畫研究所碩士論文,民國97年。
16. 陳尚駿(2008),「應用基因演算法於多目標土地使用規劃問題求解」,逢甲大學都市計畫研究所碩士論文,民國97年。
17. 陳郁文(1999),「模糊多目標組合規劃基因演算法應用於提昇運輸系統災後應變效率之研究」,國立交通大學交通運輸研究所碩士論文,民國88年。
18. 陳啟嘉(2006),「基因結構探勘於承接式子群體基因演算法求解多目標組合性問題」,元智大學工業工程與管理學系碩士論文,民國95年。
19. 陳潤明、王瀅琇(2003),「電子電機產品綠色革命之背景探討」,永續產業發展雙月刊,民國92年。
20. 彭浚忠(2003),「模糊多目標震災疏散指派問題之研究,以台中市為例」,大葉大學工業工程學系碩士論文,民國92年。
21. 曾惠鈺(2003),「即時行車資訊下物流配送作業規劃之研究」,淡江大學運輸管理研究所碩士論文,民國92年。
22. 黃冠雄(2002),「台灣地區有害廢棄物處理廠商最適化處理之研究」,國立高雄第一科技大學運輸與倉儲營運研究所碩士論文,民國91年。
23. 楊文正(2005),「廢棄物物流系統規劃之研究」,國立成功大學工業管理科學系碩士論文,民國94年。
24. 蔡麗敏(2000),「廢輪胎處理廠區位指派與運送路線選擇之研究」,國立交通大學交通運輸研究所碩士論文,民國89年。
25. 鄭力誠(2005),「應用啟發式演算法於逆物流系統之區位選擇問題」,國立嘉義大學運輸與物流工程研究所碩士論文,民國94年。
26. 鄭翔鴻(2007),「逆物流之區位指派多目標規劃-以維修產業為例」,國立雲林科技大學工業工程與管理研究所碩士論文,民國96年。
27. 戴吉亮(2001),「從3C產品的市場分佈特性探討專業物流公司之特質」,國立東華大學企業管理研究所碩士論文,民國90年。
28. 謝國倫(2000),「基因演算法應用於捷運轉乘公車區位路徑問題之研究」,淡江大學運輸管理研究所碩士論文,民國89年。
29. 謝嘉鴻(1999),「都市地區震災避難疏散指派規劃之研究,以台北市為例」,國立交通大學交通運輸研究所碩士論文,民國88年。
英文部份
1. Ahluwalia, P. K. and Nema, A. K. (2007), “A life cycle based multi-objective optimization model for the management of computer waste,” Resources, Conservation and Recycling, Vol. 51, pp.792-826.
2. Altiparmak, F., Gen, M., Lin, L. and Paksoy, T. (2006), “A genetic algorithm approach for multi-objective optimization of supply chain networks,” Computers & Industrial Engineering, Vol. 51, pp. 197-216.
3. Aras, N., Aksen, D. and Tanug˘ur, A. G. (2008), “Locating collection centers for incentive-dependent Locating collection centers for incentive-dependent,” European Journal of Operational Research, Vol. 191, pp. 1223-1240.
4. Barros, A. I., Dekker, R. and Scholten, V. (1998), “A two-level network for recycling sand: A case study,” Vol. 110, pp. 199-214.
5. Bautisa, J. and Pereira, J. (2006), “Modeling the problem of locating collection areas for urban waste management. An application to the metropolitan area of Barcelona,” Omega, Vol. 34, pp.617-629.
6. Carter, C. R. and Ellram, L. M. (1998), “Reverse logistics: A review of the literature and framework for future investigation,” Journal of Business Logistics, Vol. 19, pp. 85-102.
7. Chang, P. C. and Chen, S. H. (2009), “The development of a sub-population genetic algorithm II (SPGA II) for multi-objective combinatorial problems,” Applied Soft Computing, Vol. 9, pp. 173-181.
8. Curch, R.L. (1984), “The planer maximal covering location problem,” Journal of Regional Science, Vol. 24, pp. 185-201.
9. Dowlatshahi, S. (2000), “Developing a theory of reverse logistics,” Interfaces, Vol. 30, pp. 143-155.
10. Du, F. and Evans, G. W. (2008), “A bi-objective reverse logistics network analysis for post-sale service,” Computers & Operations Research, Vol. 35, pp. 2617- 2634.
11. Fleischmann, M., Jacqueline, Bloemhof-Ruwaard, M., Dekker, R., Vander Laan, E., Nunen, J. V. and Wassenhove, L. V. (1997), “Quantitative Models for Reverse Logistics: A Review,” European Journal of Operation Research, Vol. 103, No. 1, pp. 1-17.
12. Fleischmann, M., Krikke, H. R., Dekker, R. and Flapper, S. D. P. (2000), “A characterisation of logistics networks for product recovery,” Omega, Vol. 28, pp. 653-666.
13. Fleischmann, M., Beullens, P., Bloemhof-Ruwaard, J. M., and Van Wassenhove, L. N. (2001), “The impact of product recovery on logistics network design,” Production and Operations Management, Vol. 10, No. 2, pp. 156-173.
14. Holmberg, K., Ronnqvist, M., and Yuan, D. (1999), “An exact algorithm for the capacitated facility location problems with single sourcing,” European Journal of Operational Research, Vol. 113, pp. 544-559.
15. Jayaraman, V., Patterson, R. A. and Rolland, E. (2003), “The design of reverse distribution networks: models and solution procedures,” European Journal of Operational Research, Vol. 150, pp. 128-149.
16. Jones, D. F., Mirrazavi, S. K. and Tamiz, M. (2002), “Multi-objective meta-heuristics: an overview of current state-of-the-art,” European Journal of Operation Research, Vol. 137, pp. 1-9.
17. Klose, A. and Drexl, A. (2005), “Facility location models for distribution system design,” European Journal of Operational Research, Vol. 162, pp. 4-29.
18. Ko, H. J. and Evans, G. W. (2007), “A genetic algorithm-based heuristic for the dynamic integrated forward/reverse logistics network for 3PLs,” Computers & Operations Research, Vol. 34, pp. 346-366.
19. Lee, D. H., and Dong, M. (2008), “A heuristic approach to logistics network design for end-of-lease computer products recovery,” Transportation Research Part E, Vol. 44, pp. 455-474.
20. Listes, O. (2007), “A generic stochastic model for supply-and-return network design,” Computers & Operations Research, Vol. 34, pp. 417-442.
21. Louwers, D., Kip, B. J., Peters, E., Souren, F. and Flapper, S. D. P. (1999), “A facility location allocation model for reusing carpet materials,” Computers & Industrial Engineering, Vol. 36, pp. 855-869.
22. Melachrinoudis, E., Min, H. and Wu, X. (1995), “A multiobjective model for the dynamic location,” Location Science, Vol. 3, No. 3, pp. 143-166.
23. Min, H., Ko, C. S. and Ko, H., J. (2006), “The spatial and temporal consolidation of returned products in a closed-loop supply chain network,” Computers & Industrial Engineering, Vol. 51, pp. 309-320.
24. Min, H. and Ko, H. J. (2008), “The dynamic design of a reverse logistics network from the perspective of third-party logistics service providers,” Int. J. Production Economics, Vol. 113, pp. 176-192.
25. Minahan, T. (1998), “Manufacturers take aim at the end of the supply chain,” Purchasing, Vol. 124 No. 6, pp. 111-112.
26. Murata, T., Ishibuchi, H. and Tanaka, H. (1996), “Multi-objective genetic algorithm and its applications to flowshop scheduling,” Computers & Industrial Engineering, Vol. 30, No. 4, pp. 957-968.
27. Pati, R. K., Vrat, P. and Kumar, P. (2008), “A goal programming model for paper recycling system,” Omega, Vol. 36, pp. 405-417.
28. Quariguasi Frota Neto, J., Walther, G., Bloemhof, J., van Nunen, J. A. E. E. and Spengler, T. (2009), “A methodology for assessing eco-efficiency in logistics networks,” European Journal of Operational Research, Vol. 193, pp. 670-682.
29. Rogers, D. S. and Tibben-Lembke, R. (2001), “An examination of reverse logistics practices,” Journal of Business Logistics, Vol. 22, No. 2, pp. 129-148.
30. Salema, M. I. G., Barbosa-Povoa, A. P. and Novais, A. Q. (2007), “An optimization model for the design of a capacitated multi-product reverse logistics network with uncertainty,” European Journal of Operational Research, Vol. 179, pp. 1063-1077.
31. Scaffer, J. D. (1985), “Multi objective optimization with vector evaluated genetic algorithms,” Proceedings of 1st International Conference on Genetic Algorthm, pp.93-100.
32. Shih, L. H. (2001), “Reverse logistics system planning for recycling electrical appliances and computers in Taiwan,” Resources, Conservation and Recycling, Vol. 32, pp. 55-72.
33. Stock, J. R. (1992), “Reverse Logistics,” Council of Logistics Management, Oak Brook, IL.
34. Turkcan, A. and Akturk, M. S. (2002), “A Problem Space Genetic Algorithm in Multiobjective Optimization,” Journal of Intelligent Manufacturing, Vol. 14, pp. 250-257.
35. Vlachos, D., Georgiadis, P. and Iakovou, E. (2007), “A system dynamics model for dynamic capacity planning of remanufacturing in closed-loop supply chains,” Computers & Operations Research, Vol. 34, pp. 367-394.
36. Whitely, D., Starkweather T. and Fuquay, D. (1989), “Scheduling Problems and Traveling Salesman: The Genetic Edge Recombination Operator,” in Schafer(ed), Proceedings of the Third International Conference for Genetic Algorithms, Morgan Kaufmann PubIishers, Inc., pp. 133-140.
37. Zeleny, M. ( 1982), Multiple Criteria Decision Making, McCrew Hill, New York.
論文使用權限
  • 同意紙本無償授權給館內讀者為學術之目的重製使用,於2011-07-22公開。
  • 同意授權瀏覽/列印電子全文服務,於2011-07-22起公開。


  • 若您有任何疑問,請與我們聯絡!
    圖書館: 請來電 (02)2621-5656 轉 2281 或 來信