臺灣博碩士論文加值系統

一般市鎮廢棄物的清運，是地方環保機關的重要工作項目之一，其所需的經費往往佔廢棄物清理成本的一半以上。近年來，隨著環保意識提升，民眾也逐漸配合回收。目前國內最重要的回收方式，即是配合垃圾車清運進行回收。然而，過去在清運路並修正現有之路線規劃模式，以其改善目前之收集路線。
本研究利用混合整數規劃，考量成本、民眾便利性以及清運相關因素，建立相關數學模式。並利用優選工具針對虛擬案例進行運算，測試比較在不同便利性下，對所規劃之路線總清運成本的影響。而在模式的測試過程中，發現在進行大範圍區域運算時，CPLEX所需求解時間往往超出所預期之時間，因此視需求，尋找適當的啟發式解法，本研究採用遺傳演算法進行求解。依案例結果及地理資訊系統圖形展示，本研究所發展之鄰域多次清運模式能有效降低清運時間平均約30％；而遺傳演算法雖然所求之解較CPLEX差，但所求之解仍在可接受範圍內，與CPLEX之比值，約有70％的達成度。上述結果顯示本研究所建立之鄰域多次清運模式能有效降低清運成本，提高民眾傾倒垃圾之便利性，提升服務品質。

Collections and transports of the municipal solid wastes (MSW) are important works for local environmental authorities. The cost of collection and transport is often more than half of the total budget of MSW collection and treatment services. Nowadays the public are more willing to participate in recycling works as the environment protection consensus gradually grows. In Taiwan, the major recycle efforts are from curbside collection, it means the public used to contribute the recycled materials to the MSW collection vehicles where they dump wastes to. However, the concerns of former MSW routing were mainly in cost and equity issues, factors about time convenience of the public are not included in these routing models. Due to the inappropriate collection time schedule, some citizens could not dump their waste during the collection tours, and not to say to participate in the curbside recycling works. Thereby, the proposed model with time convenience was explored in this study.
The mathematical model with different definitions of time convenience was compared, in respects of cost, time and other MSW collection factors. In the process of analysis, a large scale scenario was found to cost much more time than expected to find the optimal solution. The heuristic method, which is the genetic algorithms in our work, was thus applied to reduce the solving time. Based on the results of scenarios, the routing plans generated by the proposed model averagely saved 30% of the total collection time than those generated by traditional models. In addition, the results of the proposed model provided both conveniences of spatial and temporal. Although the results of genetic algorithms are not as good as those generated by the proposed model, they still achieve an average 70 % of the optimal solutions and can be solved under expected time. The results also demonstrate the satisfaction and flexibility of the proposed model and genetic algorithms to be applied in the MSW collection and curbside recycling problems.

目錄
中文摘要 Ⅰ
英文摘要 Ⅱ
目錄 Ⅲ
表目錄 Ⅴ
圖目錄 Ⅵ
第一章 前言 1
1.1 研究背景 1
1.2 研究目的 2
1.3 論文內容 2
第二章 文獻回顧 4
2.1 垃圾清運路線相關研究 4
2.2 時窗問題 6
2.3 啟發式解法 7
2.4 小結 8
第三章 研究方法 9
3.1 資料蒐集 10
3.2 便利性定義 10
3.3 建立模式 11
3.3.1 一車次清運模式 11
3.3.2 二車次清運模式 13
3.3.3 鄰域多次清運模式 16
3.4 CPLEX 17
3.5 遺傳演算法 18
3.5.1 遺傳演算法原理 18
3.5.2 遺傳演算法演算過程 18
3.5.3 遺傳演算法之優點 28
3.5.4 遺傳演算法應用於便利性清運路線問題 28
第四章 案例研究 32
4.1虛擬案例測試 32
4.2實際案例測試 32
4.2.3案例區域介紹 32
4.3結果與討論 33
4.3.1小結 35
第五章 結論與建議 40
5.1 結論 40
5.2 建議 41
參考文獻 42









表目錄
表4-1案例收集點數及線段表 36
表4-2 CPLEX案例運算結果表 36
表4-3 GA案例運算結果表 37
表4-4 CPLEX與GA運算結果比較表 37






















圖目錄
圖3-1研究流程圖 9
圖3-2鄰域示意圖 11
圖3-3鄰域路線關係圖 16
圖3-4遺傳演算法演算流程圖 18
圖3-5節線型示意圖 19
圖3-6二元型示意圖 20
圖3-7單點交配示意圖 22
圖3-8雙點交配示意圖 22
圖3-9局部對應交配示意圖 23
圖3-10順序交配示意圖 24
圖3-11循環交配示意圖 25
圖3-12二元編碼突變示意圖 26
圖3-13反轉突變示意圖 27
圖3-14交換突變示意圖 27
圖3-15節點型編碼示意圖 28
圖3-16初始化族群染色體組成說明圖 29
圖4-1 scenario 1街道路線示意圖 38
圖4-2 scenario 2街道路線示意圖 38
圖4-3 scenario 3街道路線示意圖 39
圖4-4 scenario 4街道路線示意圖 39
圖4-5實際案例區域示意圖 40
圖4-6實際清運路線示意圖 40
圖4-7 scenario 1傳統兩車次清運路線示意圖 41
圖4-8 scenario 2傳統兩車次清運路線示意圖 41
圖4-9 scenario 3傳統兩車次清運路線示意圖 42
圖4-10 scenario 4傳統兩車次清運路線示意圖 42
圖4-11 scenario 1鄰域範圍半徑50公尺多次清運路線示意圖 43
圖4-12 scenario 1鄰域範圍半徑70公尺多次清運路線示意圖 43
圖4-13 scenario 1鄰域範圍半徑100公尺多次清運路線示意圖 44
圖4-14 scenario 2鄰域範圍半徑50公尺多次清運路線示意圖 44
圖4-15 scenario 2鄰域範圍半徑70公尺多次清運路線示意圖 45
圖4-16 scenario 2鄰域範圍半徑100公尺多次清運路線示意圖 45
圖4-17 scenario 3鄰域範圍半徑50公尺多次清運路線示意圖 46
圖4-18 scenario 3鄰域範圍半徑70公尺多次清運路線示意圖 46
圖4-19 scenario 3鄰域範圍半徑100公尺多次清運路線示意圖 47
圖4-20 scenario 4鄰域範圍半徑50公尺多次清運路線示意圖 47
圖4-21 scenario 4鄰域範圍半徑70公尺多次清運路線示意圖 48
圖4-22 scenario 4鄰域範圍半徑100公尺多次清運路線示意圖 48
圖4-23 GA scenario 1鄰域範圍半徑50公尺多次清運路線示意圖 49
圖4-24 GA scenario 1鄰域範圍半徑70公尺多次清運路線示意圖 49
圖4-25 GA scenario 1鄰域範圍半徑100公尺多次清運路線示意圖 50
圖4-26 GA scenario 2鄰域範圍半徑50公尺多次清運路線示意圖 50
圖4-27 GA scenario 2鄰域範圍半徑70公尺多次清運路線示意圖 51
圖4-28 GA scenario 2鄰域範圍半徑100公尺多次清運路線示意圖 51
圖4-29 GA scenario 3鄰域範圍半徑50公尺多次清運路線示意圖 52
圖4-30 GA scenario 3鄰域範圍半徑70公尺多次清運路線示意圖 52
圖4-31 GA scenario 3鄰域範圍半徑100公尺多次清運路線示意圖 53
圖4-32 GA scenario 3鄰域範圍半徑100公尺多次清運路線示意圖 53
圖4-33 GA scenario 4鄰域範圍半徑70公尺多次清運路線示意圖 54
圖4-34 GA scenario 4鄰域範圍半徑100公尺多次清運路線示意圖 54
圖4-35 GA實際案例清運路線示意圖 55

參考文獻

1.Awadnt, B. and Sepehris, N. and Hawaleshka, O., “A computer-aided process planning model based on genetic algorithms”, Computer Ops RES. Vol. 22, No. 8, pp. 841-856, 1995.
2.Azadivar, F. and Wang, J., “Facility layout optimization using simulation and genetic algorithms”, INT. J .PROD. RES., Vol. 38, No. 17, 4369-4383, 2000.
3.Baker, B. M. and Ayechew, M.A. “A genetic algorithm tor the vehicle routing problem”, Computer & Operations Research 30, pp. 787-800, 2003.
4.Bapitista, S. and Oliverira, R. C. and Zuguete, E., “A period vehicle routing case study”, European Journal of Operational Research, Vol. 139, pp. 200-229, 2002.
5.Berger, J. and Barkaoui, M., “A parallel hybrid genetic algorithm for vehicle routing problem with time windows”, Computer & Operations Research, Vol. 31, pp. 2037-2053, 2004.
6.Brandao, J. and Mercer, A., “A tabu search algorithm the multi-trip vehicle routing and scheduling problem”, European Journal of Operational Research, Vol. 100, pp. 180-191, 1997.
7.Braysy, O. and Hasle, G. and Dullaert, W., “A multi-start local search algorithm for the vehicle routing problem with time windows”, European Journal of Operational Research, Vol. 159, pp. 586-605, 2004.
8.Bazgan, C. and Hassin, R. and Monnot, J., “Approximation algorithms for some vehicle routing problems”, Discrete Applied Mathematics, Vol. 146, pp. 27-42, 2005.
9.Chen, X. and Wan, W. and Xu, X., “Modelimg rolling batch planning as vesicle routing problem with time windows”, Computers and Operations Research. Vol. 25, No. 12, pp. 1127-1136, 1997.
10.Chakroboty, P. and Mandal, A., “An asexual genetic algorithm for the general single vehicle routing problem”, Engineering Optimization, Vol. 37, No. 1, January, pp. 1-27, 2005.
11.Chang, N. B. and Yang, Y. C. and Wang, S. F., “Solid-waste mangmen system analysis with noise contro and traffic congestion limitations”, Journal of Environmental, Vol. 122, No. 2, pp. 122-131, 1996.
12.Chang, N. B. and Member, A. and ASCE and Lu, H. Y. and Wei, Y. L., “GIS technology for vehicle routing and scheduling in solid waste collection systems”, Journal of environmental engineering, Vol. 123, No. 9, pp. 901-910, 1997.
13.Filipec, M. and Skrlec, D. and Krajcar, S., “An efficient implementation of genetic algorithms for constrained vehicle routing problem”, Ieee International Conference on Systems, Man, and Cybernetics 3, pp. 2231-2236, 1998.
14.Goldberg, D. E., “Genetic algorithms in search, optimization and machine learning”, Addison-wesley publishing company, INC, 1989.
15.Hong, S. C. and Park, Y. B., “A heuristic for bi-objective vehicle routing with time window constraints”, Int. J. Production Economics, Vol. 62, pp. 249-258, 1999.
16.Holland, J. H., “Adaptation in natural and artificial system”, University of Michigan Press, Ann Arbor. MI., 1975.
17.Hwang, H. S., “An improved model for vehicle routing problem wish time constraint based on genetic algorithm”, Computer & Industrial Engineering, Vol. 42, pp. 361-369, 2002.
18.Kim, B. I. and Kim, S. and Sahoo, S., “Waste collection vehicle routing problem with time windows”, Computers & Operations Research, Vol. 33, pp. 3624-3642, 2006.
19.Kao, J. J. and Lin, T. I., “Shortest service location model for planning waste pickup”, Journal of the Air & Waste Management Association, Vol. 52, pp. 585-592, 2002.
20.Lau, H. C. and Sim, M. and Teo, K. M., “Vehicle routing problem with time windows and a limited number of vehicles”, European Journal of Operational Research, Vol. 140, pp. 559-569, 2003.
21.Lin, F. T. and Kao, C. Y. and Hsu, C. C., “Applying the genetic approach to simulated annealing in solving some np-hard problems”, Ieee Transactions on Systems, Man, and Cybernetics, Vol. 23, No. 6, pp. 1752-1767, 1993.
22.Liu, F. H. F. and Shen, S. Y., “A route-neighborhood-based metaheuristic for vehicle routing problem with windows”, European Journal of Operational Research Vol. 188, pp. 485-504, 1998.
23.Malmbrog, C. J., “A genetic algorithm for service level based vehicle scheduling”, European Joumal of Operational Research, pp. 121-134, 1996.
24.McDonald, S. and Ball, R., “Public participation in plastics recycling scheme”, Resources, Conservation and Recycling, Vol. 22, pp. 123-141, 1998.
25.Prins, C., “A simple and effective evolutionary algorithm for the vehicle routing problem”, Computer & Operations Research, Vol. 31, 1985-2002, 2004.
26.Schnecke, V. and Vornbrger, O., “Hybrid genetic algorithms for constrained placement problems”, Ieee transactions on Evolutionary Computation, Vol. 1, No. 4, pp. 266-277, 1997.
27.Srinivas, M. and Patnaik, L. M., “Genetic algorithms: a survey”, Ieee Computer, June, pp. 17-26, 1994.
28.Sakanashi, H. and Suzuki, K. and Kakazu, Y., “Filtering-GA: the evolutionary TSP landscape modifier”, Int. Conf. Evolutionary Comput., Vol. 1, pp. 390-395, 1995.
29.Seik, F. T., “Recycling of domestic waste: early experiences in singapore”, Habitintl, Vol. 21, No. 3, pp. 277-289, 1997.
30.Shih, L. H. and Lin, Y. T., “Optimal routing for infectious waste collection”, Journal of Environmental Engineering, Vol. 125, No. 5, pp. 479-484, 1999.
31.Sahoo, S. and Kim, S. and Kim, B. I. and Kraas, B. and Jr, A. P., “Routing optimization for waste management”, Interfaces, Vol. 35, No. 1, pp. 24-36, 2005.
32.Tan, K.C. and Lee, L.H. and Zhu, Q.L. and Ou, K., “Heuristic methods for vehicle routing problem with time windows”, Artificial Intelligence in Engineering, Vol. 15, pp. 281-295, 2001.
33.Tilman, C. and Sandhu, R., “A model recycling program for alabama”, Resources, Conservation and Recycling, Vol. 24, pp. 183-190, 1998.
34.Tung, D. V. and Pinnoi, A., “Vehicle routing-scheduling for waste collection in Hanoi”, European Journal of Operational Research, Vol. 125, pp. 449-468, 2000.
35.Viotti, P. and Polettini, A. and Pomi, R., “Genetic algorithms as a promising tool for optimization of the MSW collection routes”, Waste Manage Res, 21, 292-298, 2003.
36.Tom, V. M. and Mohan, S., “Transit route network design using frequency coded genetic algorithm”, Journal of Transportation Engineering, Vol. 129, No. 2, pp. 186-195, 2003.
37.Valeo, C. and Baetz, B. W. and Tsanis, I. K., “Location of recycling depots with GIS”, Journal of Urban Planning and Development, Vol. 124, No. 2, pp. 93-99, 1998.
38.黃承威，“以工作負荷與轉彎合適性為基準之垃圾車巡迴路線規劃”，碩士論文，國立交通大學環境工程研究所，新竹市，1998。
39.王耿彬，“應用遺傳演算法於低溫冷凍物流中心之車輛配送排程規劃”，碩士論文，私立朝陽科技大學工業工程與管理系研究所，台中縣，2001。
40.行政院環境保護署，“垃圾清理概況”，中華民國臺灣地區環境保護統計年報95年版，2006。
41.東森新聞報，“中市╱環保重大政策11/21起實施夜間收運垃圾”，http://www.ettoday.com.tw/2005/10/23/329-1860376.htm，2005。