臺灣博碩士論文加值系統

隨著經濟發展，國民所得增加，民眾生活和消費能力也不斷提升，卻也造成廢棄物快速的增加。台灣地區許多都市區域，民眾生活作息不完全一致，導致垃圾或資源回收物收集的時間無法完全符合民眾的需求。因此本研究考量清運時間與空間之便利性，將清運作業分成日間和夜間兩時段加以收集。並建立兩個混合整數規劃模式，找出能在不大幅增加或維持原來清運成本的前提下，改善民眾回收與清運便利性之清運路線。第一個模式的目的在於將現有之清運點，依照時間及空間便利性特性，分為兩群，以便規劃日間與夜間之收集路線，第二個模式，即路線規劃模式，則是根據第一個模式的收集點結果，分別求取日、夜間最短清運路線。為增加求解效率，第二個模式之求解，本研究利用螞蟻最佳化加以進行。第二個模式是混合整數規劃MIP用來求解典型TSP問題，是為分別求取日、夜間最短清運路線。為了增進第二種模式的求解效率, 本研究利用螞蟻最佳化加以進行。這個案例的研究已經被證實其推薦的方法之適用性與彈性。結果也顯示藉由本研究方法可發現比原始實際案例在同時間與空間的便利性之下更優越。

As the economy growth and national income increasing, the quality of life and consumption of level also rapidly raise. The above phenomena result in increasing municipal solid waste (MSW) as well. There are a lot of citizens in urban areas of Taiwan, because of their various daily life schedule, who can’t match up the curbside collection time of MSW or recyclable materials. Therefore, temporal convenience and spatial convenience of MSW collection are evaluated in this study to modify the original single shift collection plan into day-and-night shift collection. Two mixed integer programming (MIP) models are established to analyze the problem. The first model is to divide the collection points into two groups while considering the convenience of residents, for day shift and night shift, respectively. The second model is a typical traveling salesman problem MIP model, which is used for solving the optimal collection pan of each shift. To improve the solving efficiently of second model, a heuristic skill, ants colony optimization has been introduced. A case study has been demonstrated to realize the suitability and flexibility of the proposed methodology. The results also reveals that the collection plans generated by the proposed methodology in all the scenarios are superior to the collection plan at present based on the same temporal and spatial convenience.

摘要 I
ABSTRACT II
目錄 IV
表目錄 VI
圖目錄 VII
第一章 前言 1
1.1研究背景 1
1.2研究目的: 2
1.3論文內容 3
第二章 文獻回顧 5
2.1清運與資源回收時間及空間便利性 5
2.2清運模式 9
2.3啟發式解法 10
第三章 研究方法 14
3.1資料收集 16
3.2 便利性定義 17
3.2.1時間便利性 17
3.2.2空間便利性 18
3.3模式一(收集點分群) 19
3.3.1 收集點分群模式 19
3.4 模式二（路線規劃TSP）： 23
3.4.1 模式求解工具 26
3.4.2 MIP 26
3.4.3 蟻群最佳化(ACO) 27
3.5 全區和局部日夜分群 33
第四章 案例研究 35
4.1 ACO參數設定 35
4.2虛擬案例測試 37
4.2.1 日夜分群運算 38
4.2.2利用MIP運算TSP 39
4.2.3利用ACO運算TSP 40
4.2.4 MIP及ACO結果之比較 41
4.3案例討論 43
4.3.1案例介紹 43
4.3.2南屯區全區日夜分群 45
4.3.3 南屯區局部日夜分群 47
4.3.4 南屯全區日夜分群和局部日夜分群比較 49
4.3.5 TSP直線運算結果與實際運算結果比較 50
4.3.6覆蓋半徑與清運成本之關係 56
4.4 小結 57
第五章 結論與建議 58
5.1 結論 58
5.2 建議 60
參考文獻 61
附錄I 蟻群最佳化(ANT COLONY OPTIMIZATION；ACO) 67
I.1螞蟻系統(ANT SYSTEM;AS) 68
I.2螞蟻族群系統(ANT COLONY SYSTEM;ACS) 74
表目錄

表 4- 1 參數m比較表36
表 4- 2 參數q0比較表36
表 4- 3 參數α比較表37
表 4- 4 虛擬案例收集點數38
表 4- 5 MIP 虛擬案例日夜分群運算結果39
表 4- 6 MIP 虛擬案例TSP運算結果40
表 4- 7 ACO 虛擬案例TSP運算結果41
表 4- 8 CPLEX與ACOTSPV10運算結果比較42
表 4- 9 南屯區原始實際案例清運距離46
表 4- 10 南屯區全區收集點日夜分群實際案例運算結果46
表 4- 11 南屯區全區日夜分群實際案例運算結果47
表 4- 12南屯區局部收集點日夜分群實際案例運算結果49
表 4- 13南屯區全區及分局部日夜分群清運結果比較表50
表 4- 14南屯區全區日夜分群TSP直線距離與實際距離結果比較表51

圖 2-1文獻回顧架構圖 5
圖 3- 1研究流程圖 15

圖 3- 2覆蓋半徑示意圖19
圖 3- 3模式一日夜分群示意圖22
圖 3- 4模式二路線規劃TSP示意圖26
圖 3- 5自然界螞蟻行為示意圖( Dorigo et al, 1996)28
圖 3- 6 ACO針對TSP搜尋示意圖(Dreo, 2006)33
圖 4- 1 實際案例區域示意圖 44

圖 4- 2 實際案例清運點示意圖45
圖 4- 3南屯區人口分布圖層48
圖 4- 4南屯區人口密度分佈圖48
圖 4- 5覆蓋半徑50公尺實際案例TSP清運路線示意圖52
圖 4- 6蓋半徑75公尺實際案例TSP清運路線示意圖52
圖 4- 7覆蓋半徑100公尺實際案例TSP清運路線示意圖53
圖 4- 8覆蓋半徑500公尺實際案例TSP清運路線示意圖53
圖 4- 9覆蓋半徑50公尺實際案例清運路線示意圖54
圖 4- 10覆蓋半徑75公尺實際案例清運路線示意圖54
圖 4- 11覆蓋半徑100公尺實際案例清運路線示意圖55
圖 4- 12覆蓋半徑500公尺實際案例清運路線示意圖55
圖 4- 13實際案例比較圖56

1.Barlishen, K. D., and Baetz, B. W., “Development of a decision support system for municipal solid waste management systems planning”, Waste Management & Research 14, pp.71–86, (1996).
2.Baptista, S., Oliveira, R. C., and Zuquete, E., “A period vehicle routing case study”, European Journal of Operational Research, 139, pp.220-229, (2002).
3.Bazgan, C., Hassin, R., and Monnot, J., “Approximation algorithms for some vehicle routing problems”, Discrete Applied Mathematics, 146, pp27-42, (2005).
4.Brandao, J., and Mercer, A., “A tabu search algorithm for the multi-trip vehicle routing and scheduling problem”, European Journal of Operational Research, 100, pp180-191, (1997).
5.Badran, M. F., and El-Haggar S. M., “Optimization of municipal solid waste management in Port-Egypt”, Waste Management 26, pp. 534-545, (2006).
6.Church, R., ReVelle, C., “The maximal covering location problem; papers of the regional science association”, 32, pp.101-118, (1974).
7.Chang, N. B., and Wang, S. F., “Solid waste management system analysis by multi objective mixed integer programming model”, Journal of Environmental Management 48, pp.17–43, (1995).
8.Chang, N. B., Chang, Y. H., and Chen, Y. L., “Cost-effective and equitable workload operation in solid-waste management system”, Journal of Environmental Engineering, 123(2), pp.178-190, (1997).
9.Chang, N. B., Yang, Y. C., and Wang, S. F., “Solid-waste management system analysis with noise control and traffic congestion limitations”, Journal of Environmental Engineering, 122(2), pp.122-131, (1996).
10.Cheng, C. B., and Mao, C. P., “A modified ant colony system for solving the travelling salesman problem with time windows”, Mathematical and Computer Modelling 46, pp. 1225-1235, 2007.
11.Dorigo, M., “Ant Colony System: A cooperative learning approach to the traveling salesman problem”, IEEE Transactions on Evolutionary Computation, 1(1), pp.53-66, (1996).
12.Dorigo, M., and Gambardella, L. M., “Ant colonies for the traveling salesman problem,” BioSystems, Vol. 43,pp.73-81 (1997).
13.Dorigo, M., and Caro. G. D., “The ant colony optimization meta-heuristic” New Ideas in Optimization, McGraw Hill, pp.11-32. (1999).
14.Glover, F., “Future paths for Integer programming and links to artificial intelligence”, Computers and Operations Research, 5:pp.533-549, (1986).
15.Holland, J. H., “Adaptation in natural and artificial system”, University of Michigan Press, Ann Arbor. MI., (1975).
16.Hong, S. C., and Park, Y. B., “A heuristic for bi-objective vehicle routing with time window constraints”, Int. J. Production Economics, 62, pp.249-258, (1999).
17.ILOG Inc., Using the CPLEX callable library. ILOG Inc., Incline Villiage, NV (1997).
18.Kirkpatrick, S., Gelatt, C. D., and Vecchi, M. P., “Optimization by Simulated Annealing”, Science, 220, 4598, pp.671-680, (1983).
19.Kao, J. J., and Lin, T. I., “Shortest service location model for planning waste pickup locations”, Air & Waste Manage. Assoc. 52., pp.585-592, (2002).
20.Kenyou, A. S., and Morton, D. P., “Stochastic vehicle routing with random travel times”, Transportation Science, Vol. 37, No. 1, pp. 69-82, (2003).
21.Lin, H. Y., and Chen, G. H., “Regional optimization model for locating supplemental recycling depots” Waste Management, pp.1473-1479, (2008).
22.Mulvey, J. M., and Ruszczynski, A., “A New Scenario Decomposition Method for Large-scale Stochastic Optimization”, Operations Research, Vol. 43, pp. 477-490, (1995).
23.McDonald, S., and Ball, R., “Public participation in plastics recycling schemes”, Resource, Conservation and Recycling, 22, pp.123-141, (1998).
24.Montemanni, R., Gambardella, L.M., Rizzoli, A.E., and Donati, A.V., “A new algorithm for a dynamic vehicle routing problem based on ant colony system”, Proceedings of ODYSSEUS 2, pp.27-30, (2003).
25.Raluy, R.G., Serra, L., Uche, J. and Valero, A., “Life-cycle assessment of desalination technologies integrated with energy production systems”, Desalination 167, pp.445-458, (2004).
26.Sahoo, S., Kim, S., Kim, B. I., Kraas, B., and Jr, A. P., “Routing optimization for waste management”, Interfaces, 35(1), pp.24-36, (2005).
27.Seik, F., “Recycling of domestic wastes: early experiences in Singapore”, Habitat International, 21(3), pp.277-289, (1997).
28.Shih, L. H., and Lin, Y. T., “Optimal routing for infectious waste collection”, Journal of Environmental Engineering, 125(5), pp.479-484, (1999).
29.Toregas, C., ReVelle, C., “Optimal location under time or distance constraints”, Papers of the Regional Science Association, 28, pp.133-143, (1972).
30.Tan, K. C., Lee, L. H., Zhu, Q. L., and Ou, K., “Heuristic methods for vehicle routing problem with time windows”, Artificial Intelligence in Engineering, 15, pp.281-295, (2001).
31.Tchobanoglous, G., Theisen, H., and Vigil, S. A., “Integrated solid waste management engineering principles and management issues”, McGraw-Hill Book Co. Singapore, (1993).
32.Tilman, C., and Sandhu, R., “A model recycling program for Alabama”, Resource, Conservation and Recycling, 24, pp.183-190, (1998).
33.Tom, V. M., and Mohan, S., “Transit route network design using frequency coded genetic algorithm”, Journal of Environmental Engineering, 129(2), pp.186-195, (2003).
34.Tung, D. V., and Pinnoi, A., “Vehicle routing-scheduling for waste collection in Hanoi”, European Journal of Operational Research, 125, pp.449-468, (2000).
35.Thomas Stuetzle. ACOTSP, Version 1.0. Available from http://www.aco-metaheuristic.org/aco-code, (2004).
36.Valeo, C., Baetz, B. W., and Tsanis, I. K., “Location of recycling depots with GIS”, Journal of Urban Plng. and Devel. ASCE. 124(2) pp.93-99, (1998).
37.Yan, S., and Chen, H. L., “A scheduling model and a solution algorithm for inter-city bus carriers”, Transportation Research, Vol. 36A, pp. 805-825, (2002).
38.Zhang, Y., Pei, Z. L., Yang, J. H., and Liang, Y. C., “An improved Ant colony optimization algorithm based on route optimization and its applications in travelling salesman problem”, Bioinformatics and Bioengineering, Proceedings of the 7th IEEE International Conference, 14-17 Oct., pp.693 – 698, (2007).
39.朱文正， “考量旅行時間可靠度車輛途程問題-螞蟻族群演算法之應用”，碩士論文，交通大學交通運輸研究所，新竹市，(2003)。
40.林振展， “應用自然界螞蟻的經驗分享機制萃取個人化推薦知識之研究”，碩士論文，銘傳大學資訊工程研究所，台北市，(2008)。
41.黃承威，“以工作負荷與轉彎合適性為基準之垃圾車巡迴路線規劃”，國立交通大學環境工程研究所碩士論文，(1998)。
42.林靖凱， “考量市鎮廢棄物清運與回收時間便利性路線之規劃”，碩士論文，朝陽科技大學環境公程與管理研究所，台中縣，(2007)。
43.台中市環境保護局，“垃圾收集時刻表”， http://www.tcepb.gov.tw/index/07_sch/sch_01.asp，(2008)。
44.台中市環境保護局，“中市/環保重大政策11/21起實施夜間收運垃圾”，http://www.tcepb.gov.tw/team/convenience/con1_03.asp?nec_id=132，(2008)。
45.自由時報電子報， “四月一號起一三五日間垃圾收集 二四六夜間垃圾收集”，http://www.libertytimes.com.tw/2007/new/mar/31/today-center5.htm，(2007)。
46.環保署，「垃圾全分類零廢棄群組行動計畫」， (2009)。
47.行政院環境保護署，“空氣、水、廢棄物、毒化物管理資訊整合”，http://www.epa.gov.tw/ch/aioshow.aspx?busin=323&path=8476&guid=e70c9daf-1fa2-452c-bfc4-43161e17723a&lang=zh-tw，(2008)。
48.行政院環境保護署，「垃圾清理概況」，中華民國臺灣地區環境保護統計年報，(2009)。