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

Abstract

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