蟻群最佳化回收便利性清運模式之發展

The ants colony optimization enhanced model for residents access convenience of municipal solid waste collection and recycling

蔡宗沛(Zong-pei Cai)

指導教授 ： 林宏嶽

朝陽科技大學/理工學院/環境工程與管理系/碩士(2009年)

摘要

隨著經濟發展，國民所得增加，民眾生活和消費能力也不斷提升，卻也造成廢棄物快速的增加。台灣地區許多都市區域，民眾生活作息不完全一致，導致垃圾或資源回收物收集的時間無法完全符合民眾的需求。因此本研究考量清運時間與空間之便利性，將清運作業分成日間和夜間兩時段加以收集。並建立兩個混合整數規劃模式，找出能在不大幅增加或維持原來清運成本的前提下，改善民眾回收與清運便利性之清運路線。第一個模式的目的在於將現有之清運點，依照時間及空間便利性特性，分為兩群，以便規劃日間與夜間之收集路線，第二個模式，即路線規劃模式，則是根據第一個模式的收集點結果，分別求取日、夜間最短清運路線。為增加求解效率，第二個模式之求解，本研究利用螞蟻最佳化加以進行。第二個模式是混合整數規劃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.

並列關鍵字

time flexibility ； mixed integer programming ； ants colony optimization. ； Municipal solid waste collection

參考文獻

48. 行政院環境保護署，「垃圾清理概況」，中華民國臺灣地區環境保護統計年報，(2009)。

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).

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).