應用全因子實驗與克利金法改善差分進化算法解車輛途程問題之研究

Using Full Factorial Experiment and Kriging Method to Improve Differential Evolution Algorithm to Solve Vehicle Routing Problems

李政鋼(C. K. Lee) ； 蔡明諺(M. Y. Cai)

《危機管理學刊》 15卷2期 (2018/09) Pp. 1-8

https://doi.org/10.6459/JCM.201809_15(2).0001

摘要

本研究之目的是探討何種模式之差分進化算法(Differential Evolution Algorithm, DE)適合求解車輛途程問題(Vehicle Routing Problem, VRP)，並以全因子實驗及克利金法來改善算法之控制參數以提高算法之求解能力。算法所求解的問題是由NEO (Networking and Emerging Optimization)網站所下載的15題VRP測試問題。算法的求解能力定義為算法解得之最短距離與問題真正最短距離之平均差異百分比。本研究結果顯示DE/best/1/bin模式之差分進化算法最適合求解車輛途程問題。為改善算法之控制參數(縮放因子F與交叉機率Cr)，本研究先以全因子實驗找到參數的最佳水準值，再以克利金法將離散的實驗數據轉換為連續的目標函數，並以最佳化方法求得控制參數的最佳解。算法控制參數在未改善前，算法的平均差異百分比高達46.27%，經全因子實驗改善後，算法的平均差異百分比可降至24.46%，再經克利金法改善後，算法平均差異百分比可再降至21.23%。以DE/best/1/bin差分進化算法解車輛途程問題時，縮放因子F之最佳設定是0.475259，交叉機率Cr之最佳設定是0.60151。

關鍵字

車輛途程問題 ； 差分進化算法 ； 全因子實驗 ； 克利金法

並列摘要

The purpose of this study is to explore which model of Differential Evolution Algorithm (DE) is suitable for solving Vehicle Routing Problem (VRP). To improve the control parameters of the algorithm to enhance the solving ability of the algorithm, a full factor experiment and Kriging method are applied. The 15 test problems solved by the algorithm are downloaded from the NEO website. The solving ability of the algorithm is defined as the average of percentages of differences between the solved shortest distances and the true shortest distances. The results of this study have shown that DE/best/1/bin is most suitable for solving vehicle routing problems. In order to improve the control parameters (scaling factor F and crossover probability Cr) of DE/best/1/bin, a full factorial experiment is applied firstly to find the best level of parameters. Then, Kriging method is applied to convert the discrete experimental data into a continuous objective function. The optimization method is applied to find the best solution of parameters. Before improving the control parameters, the average of percentages of differences was as high as 46.27%. After applying the full-factorial experiment, the average of percentages of differences can be reduced to 24.46%. After applying the Kriging method, the average of percentages of differences can be reduced to 21.23%. When using DE/best/1/bin differential evolution algorithm to solve the vehicle routing problem, the optimal setting of the scaling factor F is 0.475259, and the optimal setting of the crossover probability Cr is 0.60151.

並列關鍵字

VRP ； Differential Evolution Algorithm ； Full Factorial Experiment ； Kriging Method

參考文獻

Baker, E. K. and Schaffer, J. R. (1986). “Solution improvement heuristics for the vehicle routing and scheduling problem with time window constraints,” American Journal of Mathematical and Management Sciences, 6, 261-300

Dantzig, G. B. and Ramser, J. H. (1959). “The Truck Dispatching Problem,” Management Science, 6, 80-91

Boding, L. and Golden, B. (1981). “Classification in Vehicle Routing and Scheduling,” Networks, 11(2) , 97-108

Bodin, L. D., Golden, B. L., Assad, A. A. and Ball, M. O. (1983). “Routing and Scheduling of vehicles and crews: The State of the art,” Computers & Operations Research, 10(20), 63-211

Lenstra, J. K. and Rinnooy Kan, A. H. G. (1981). “Complexity of Vehicle Routing and Stochastic Problems,” Networks, 11(2), 221-227