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

Solving a Bi-objective Pollution Routing Problem Using Multi-objective Evolutionary Algorithms

吳政遠(Wu Cheng-Yuan)

指導教授 ： 蔣宗哲

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

https://doi.org/10.6345/THE.NTNU.DCSIE.006.2019.B02

摘要

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

關鍵字

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

並列摘要

無資料

並列關鍵字

Evolutionary Algorithm ； Vehicle Routing Problem ； Pollution Routing Problem

參考文獻

[1]行政院環保署。網址：https://www.epa.gov.tw/ct.asp?xItem=10052&ctNode=31352&mp=epa

上網日期：2018年9月9日。

[2]P. Augerat, J. M. Belenguer, E. Benavent, A. Corberán and D. Naddef, “Separating capacity constraints in the CVRP using tabu search,” European Journal of Operational Research, vol. 106, pp. 546-557, 1998.

[3]S. Erdoğan and E. Miller-Hooks, “A green vehicle routing problem,” Transportation Research Part E：Logistics and Transportation Review, vol. 48, pp. 100-114, 2012.

[4]H. Li and A. Lim, “Local search with annealing-like restarts to solve the VRPTW,” European Journal of Operational Research, vol. 150, pp. 115-127, 2003.