以NSGA-III演化演算法求解雙目標汙染車輛路由問題

Solving a Bi-objective Pollution Routing Problem Using NSGA-III

陳柏宇(Chen Bo-Yu)

指導教授 ： 蔣宗哲

國立臺灣師範大學/理學院/資訊工程學系/碩士(2023年)

https://doi.org/10.6345/NTNU202300283

摘要

隨著工業蓬勃發展，溫室氣體排放量逐年成長。根據行政院統計，我國 2019 年的運輸排放占二氧化碳排放的 14.17%，故本研究從運輸方面下手，透過最佳化運送路徑，可以有效的減少油耗量，進而改善環境問題。本文的研究題目為雙目標汙染車輛路由問題，是由具時間窗的車輛路由問題所延伸；兩個目標為油耗量和時間。根據研究，車速越快的時候，所消耗的油量亦愈高，因此縮短時間與減少油耗量兩個目標存在衝突。本研究使用多目標演算法，能夠在一定的時間內，求得所需要的解集合。使用 NSGA-III 演算法，透過設立參考點的方式維持族群的多樣性。為了在一開始獲得較好的族群，使用最近鄰點法結合節省法的方式去建立良好的初始解。以動態規劃解碼生成路徑，配合改良的交配機制使得子代容易將優良的基因繼承下去。考慮到解空間過大的問題，本研究使用區域搜尋來探勘較優秀的解。為了避免多樣性下降，會移除表現較不好的重複個體。相較於過去的實驗結果，本研究能夠在計算成本與過去研究近似的情況下，得出更全面的柏拉圖凌越解集合。

關鍵字

雙目標汙染車輛路由問題 ； 多目標演化演算法

並列摘要

none

並列關鍵字

Pollution Routing Problem ； Evolutionary Algorithm

參考文獻

行政院環保署。網址：https://www.epa.gov.tw/Page/81825C40725F211C/6a1ad12a-4903-4b78-b246-8709e7f00c2b上網日期：2018年9月9日。

T. Bektaş and G. Laporte, “The pollution-routing problem,” Transportation Research Part B, vol. 45, no. 8, pp. 1232–1250, 2011.

E. Demir, T. Bektaş, and G. Laporte, “The bi-objective pollution-routing problem,” European Journal of Operational Research, vol. 232, no. 3, pp. 464–478, 2014.

E. Demir, T. Bektaş, and G. Laporte, “An adaptive large neighborhood search heuristic for the pollution-routing problem,” European Journal of Operational Research, vol. 223, no. 9, pp. 346–359, 2012.

T. Bäck, “Evolutionary algorithms in theory and practice: evolution strategies, evolutionary programming, genetic algorithms,” Oxford university press, pp. 120, 1996.