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

Abstract

本論文使用多目標演化演算法NSGAIII求解雙目標汙染車輛路由問題 (Pollution Routing Problem)，此問題為車輛路由問題 (Vehicle Routing Prolbem) 的延伸。雙目標汙染車輛路由問題中物流車有最大容量 (capacity) 限制；客戶與倉庫都有最早開始服務時間 (ready time) 與最晚服務時間 (due time)，物流車必須在這段時間內抵達，此為時間限制。我們希望同時最小化總油耗量與最小化總花費時間，但速度在一定速度後越快變得越耗油，想要降低耗油會拉長花費時間，兩者無法同時下降。然而，我們可以求出非凌越解 (non-dominated solution)，這些解在目標空間中形成柏拉圖前緣 (Pareto front)，本論文的目標是求得接近此問題之真實解的柏拉圖前緣。 我們使用最近鄰點法 (Nearest Neighborhood, NN) 初始化方式來使初始解具備一定品質。多目標路線建構來提前使解具有多目標特性與更具多樣性。探討多種速度對於汙染車輛路由問題的影響性。使用NEH與2-Opt搜尋法的來增強最小化總行駛距離來接近真實解之柏拉圖前緣。 本論文提出的演算法在使解族群更具有多目標特性有較佳的效果。