基植於蟻群最佳化的逆物流管理-以印尼醫療廢棄物回收為例

簡易檢索 / 詳目顯示

回結果列表

研究生：	德温 Devin - Meidya Fonda
論文名稱：	基植於蟻群最佳化的逆物流管理-以印尼醫療廢棄物回收為例 Reverse Logistics Management Based on the Ant Colony Optimization - A Case Study on Hospital Waste in Indonesia
指導教授：	羅士哲 Shih-Che Lo
口試委員:	林希偉 Shi-Woei Lin 蔡鴻旭 Hung-Hsu Tsai 周正芳 Mabel C. Chou
學位類別：	碩士 Master
系所名稱：	管理學院 - 工業管理系 Department of Industrial Management
論文出版年：	2014
畢業學年度：	102
語文別：	英文
論文頁數：	59
中文關鍵詞：	廢棄物管理、逆物流、車輛運途問題、蟻群演算法、掃描法
外文關鍵詞：	Waste management, Reverse logistics, Vehicle routing problem, Antcolony optimization, Sweep method
相關次數：	點閱：486 下載：8
分享至:	分享至facebook 分享至twitter

查詢本校圖書館目錄查詢臺灣博碩士論文知識加值系統勘誤回報

上一筆

在避免汙染鄰近的環境中，廢棄物管理是很重要的一環。廢棄物管理有兩大活動，是指從廢棄物出產地，到廢棄物處理場的收集與運送作業。這些活動需要有效且有效率的方法去特別地執行。找尋從每個廢棄物出產地到廢棄物處理場的最短路徑，進而去最小化在廢棄物管理的成本。此類找尋最短路徑的問題可以被視為是車輛運途問題。而在收集與運送廢棄物的個案中，因為有包含廢棄物出產地的廢棄物量與收集廢棄物的車輛數目等等的容量限制，所以此類型的車輛運途問題稱為具容量限制的車輛運途問題。本論文是以印尼雅加達的真實例子為案例，將焦點集中於以醫院為起點的廢棄物收集與運送到以垃圾填埋場為最終處理點的具容量限制的車輛運途問題。
本論文提出了一個結合掃描法與蟻群演算法的混合型演算法，去尋找從醫院到垃圾填埋場的最短路徑之最佳解。我們將所提的混合型演算法與基因演算法做比較，證明了我們所提出的混合型演算法在求解車輛運途問題是可靠的。實驗結果顯示，在求解30個標竿問題上，我們所提的混合型演算法是堅耐、具競爭力且優於基因演算法的。

The waste management is one of important processes to manage wastes to avoid contaminating the surrounding neighborhood. Two main activities in managing wastes is collecting and transporting wastes from the place which produced them to final disposal place called dumping place. These kind of activities need effective and efficient way to be implemented especially in finding the minimum distance from each source of wastes to the final disposal place so it will minimize the cost in the waste management system. Finding minimum distance can be associated as the Vehicle Routing Problem (VRP). In the case of collecting and transporting the wastes, the type of VRP used is called the Capacitated Vehicle Routing Problem (CVRP) because it involves capacity constraint between the amount of wastes of each place and the vehicle used to pick up the wastes. This thesis is based on real case in Jakarta, Indonesia which focuses on the CVRP in picking up and transporting wastes from the hospitals to the landfill as final disposal place.
The hybrid method combining the sweep method and the Ant Colony Optimization (ACO) method is proposed to find the optimal solutions of minimum distance in picking up wastes from the hospitals to the landfill. Comparisons are made between the proposed hybrid method and the Genetic Algorithm (GA) to test that our algorithm is reliable to solve the problem. Experiment results show that the proposed hybrid method was able to find the optimal solution better than the GA for all 30 benchmark problems and also for the real case involving the hospitals in Jakarta, Indonesia. The hybrid method is also robust and competitive over the GA.

摘要	i
ABSTRACT	ii
ACKNOWLEDGEMENTS	iii
CONTENTS	iv
LIST OF FIGURES	vi
LIST OF TABLES	vii
CHAPTER I INTRODUCTION	1
1.1	Research Motivation	1
1.2	Objectives	3
1.3	Research Structures 	4
CHAPTER II LITERATURE REVIEW	6
2.1	The Vehicle Routing Problem (VRP) 	6
2.1.1	The Capacitated Vehicle Routing Problem (CVRP)	7
2.2	Methods and Measures to Solve the VRP	8
2.2.1	 The Ant Colony Optimization (ACO)	10
2.2.2	 The Ant Colony Optimization and the Genetic Algorithm	12
2.3	Background Case	13
2.3.1	The Reverse Logistics 	13
2.3.2	The Waste Management System	14
CHAPTER III PROBLEM FORMULATION	16
3.1	Problem Proposition	16
3.2	The Sweep Algorithm	18
3.3	The Ant Colony Optimization Method	21
3.3.1.	Route Construction	23
3.3.2.	Pheromone Updating	24
3.4	The Genetic Algorithm	24
3.4.1	Crossover	25
3.4.2	Mutation	26
3.5	The Hybrid Method 	26
CHAPTER IV COMPUTATIONAL EXPERIMENTS OF BENCHMARK PROBLEMS	28
4.1	Computational Results 	28
CHAPTER V COMPUTATIONAL EXPERIMENTS OF HOSPITAL WASTE	32
5.1	Hospital Waste Management System in Jakarta, Indonesia 	32
5.2	Computational Results 	35
CHAPTER VI CONCLUSIONS AND FURTHER RESEARCH	40
6.1	Conclusions 	40
6.2	Further Research 	41
REFERENCES	43
Appendix A. The Solution of the Sweep ACO for Instance 12G1	46
Appendix B. The Best Routing Plan of the Sweep ACO for Instance 12G1	47
Appendix C. The Solution of the Sweep ACO for Instance 16G1	48
Appendix D. The Best Routing Plan of the Sweep ACO for Instance 16G1	49
Appendix E. The Solution of the Sweep ACO for Instance 21G1	50
Appendix F. The Best Routing Plan of the Sweep ACO for Instance 21G1	51

                                

Baker, B.M. and Ayechew, M.A., 2003. A genetic algorithm for the vehicle routing problem, Computers & Operation Research, 30, 787 - 800.
Bautista, J., Fernandez, E., and Pereira, J., 2008. Solving an urban waste collection problem using ants heuristics, Computers & Operation Research, 35, 3020 – 3033.
Clark, G. and Wright, J.W., 1964. Scheduling of vehicles from a central depot to a number of delivery points, Operations Research 12, 568 – 581.
Cordeau, J.F., Laporte, G., Savelsbergh, M.W.P., and Vigo, D., 2007. Vehicle routing, Handbook in OR & MS, 14, 367 – 428.
Daneshzand, F., 2011. The vehicle-routing problem, Logistics Operations and Management, 8, 127 – 153.
Dorigo, M., Maniezzo, V., and Colorni, A., 1996. The ant system: optimization by a colony of cooperating agents, IEEE Transactions on Systems, Man, and Cybernetics – Part B, 26(1), 29 - 41.
Dorigo, M. and Gambardella, L.M., 1997. Ant colonies for the traveling salesman problem, BioSystems, 43, 73 - 81.
Dorigo, M. and Stutzel, T., 2003. The ant colony optimization metaheuristic: algorithm, application, and advances, International Series in Operations Research & Management Science, 57, 250 - 285.
Dorigo, M. and Stutzel, T., 2004. Ant Colony Optimization, The MIT Press.
Dueck, G. and Scheurer T., 1990. Threshold accepting: a general purpose optimization algorithm, Journal of Computational Physics, 90, 161 – 175.
Dueck, G., 1993. New optimization heuristics: the great deluge algorithm and the record-to-record travel, Journal of Computational Physics, 104, 86 – 92.
Ergun, O., Orlin, J.B., and Steele-Feldman, A., 2006. Creating very large-scale neighbourhoods out of smaller ones by compounding moves, Journal of Heuristics, 12, 115 – 140.
Gendreau, M., Laporte, G., and Potvin, J.Y., 2002. Metaheuristics for the capacitated VRP, The vehicle routing problem, 9, 129 - 154.
Glover, F., 1986. Future paths for integer programming and links to artificial intelligence, Computers & Operations Research, 13, 533 – 549.
Golden, B.L., Assad, A.A., and Wasil, E.A., 2002. Routing vehicles in the real world: applications in the solid waste, beverage, food, dairy, and newspaper industries, The Vehicle Routing Problem, 245 – 286.
Guo, W., 2009. Study on reverse logistics in enterprises, Second International Symposium on Information Science and Engineering, 87 - 90.
Horvath, P.A., Autry, C.W., and Wilcox, W.E., 2005. Liquidity implications of reverse logistics for retailers: A Markov chain approach, Journal of Retailing, 81, 191 - 203.
Kim, H., Yang, J., and Lee, K.D., 2009. Vehicle routing in reverse logistics for recycling end-of-life consumer electronic goods in South Korea, Transportation Research Part D, 14, 291 – 299.
Kirkpatrick, S., Gelatt Jr, C.D., and Vecchi, M.P., 1983. Optimization by simulated annealing, Science, 220, 671 – 680.
Laporte, G., 2009. Fifty years of vehicle routing, Transportation Science, 01, 43, 408 – 416.
Lenstra, J.K. and Rinnooy Kan, A.H.G., 1981. Complexity of vehicle and scheduling problems, Networks 11, 2, 221 – 227.
Liu, J. and He, Y., 2012. Ant colony algorithm for waste collection vehicle arc routing problem with turn constraints, Eighth International Conference on Computational Intelligence and Security, 35 – 39.
Mladenovic, N. and Hansen, P., 1997. Variable neighborhood search, Computers & Operations Research, 24, 1097 – 1100.
Raghumani Singh, C. and Dey, M., 2011. Solid waste management of Thoubal Municipality, Manipur – a case study, International Conference on Green Technology and Environmental Conservation, 21 – 24.
Ramos, T.R.P., Gomes, M.I., and Barbosa-Povoa, A.P., 2013. Planning waste cooking collection systems, Waste Management, 33, 1691 – 1703.
Reimann, M., Shtovba, S., and Nepomuceno, E., 2001. A hybrid ACO - GA approach to solve vehicle routing problems, Student Papers of the Complex System Summer School, Santa Fe Institute.
Rochat, Y. and Taillard, E.D., 1995. Probabilistic diversification and intensification in local search for vehicle routing, Journal of Heuristics, 1, 147 – 167.
Rogers, D.S. and Tibben-Lembke, R.S., 1999. Going backwards: reverse logistics trends and practices, Reverse Logistics Executive Council. The University of Nevada, Reno, Center for Logistics Management, Pittsburgh.
Ropke, S. and Pisinger, D., 2006. A unified heuristic for a large class of vehicle routing problems with backhauls, European Journal of Operational Research, 171, 750 – 775.
Silva, C.A., Faria, J.M., Abrantes, P., Sousa, J.M.C., Surico, M., and Naso, D., 2005. Concrete delivery using a combination of GA and ACO, Proceeding of the 44th IEEE Conference on Decision and Control, and the European Control Conference, art no. 1583394, 7633 - 7638.
Toth, P. And Vigo, D., 2002. The vehicle routing problem, SIAM Monograph on Discrete Mathematics and Applications, Philadelphia.
Tung, D.V. and Pinnoi, A., 2000. Vehicle routing-scheduling for waste collection in Hanoi, European Journal of Operational Research, 125, 449 – 468.
Won, J.M. and Karray F., 2008. Personal rapid transit network design using genetic algorithm and ant colony system hybridization, International Conference on Control, Automation and Systems, 406 - 411.
Zhang, Y. And Wu, L., 2012. A novel genetic ant colony algorithm, Journal of Convergence Information Technology, 7(1), 268 - 274.
Zhao, C., Liu, W., and Wang, B., 2008. Reverse logistics, International Conference on Information Management, Innovation Management and Industrial Engineering, 349 -353.

簡易檢索 / 詳目顯示

相關論文