========== [Paper] ========== Tsung-Che Chiang and Wei-Huai Hsu, A knowledge-based evolutionary algorithm for the multiobjective vehicle routing problem with time windows, Computers & Operations Research, vol. 45, 2014. http://dx.doi.org/10.1016/j.cor.2013.11.014 ========== [Benchmark instances] ============= Solomon's 100-customer VRPTW problem instances. (r1/r2/rc1/rc2 categories, 39 instances in total) http://web.cba.neu.edu/~msolomon/problems.htm ========== [Benchmark algorithms] ============= Benchmark algorithms and notations: [T] C. J. Ting and C.H. Huang, "An improved genetic algorithm for vehicle routing problem with time windows," International Journal of Industrial Engineering, vol. 12, no. 3, pp. 216–226, 2005. [O] B. Ombuki, B. J. Ross, and F. Hanshar, "Multi-objective genetic algorithms for vehicle routing problem with time windows," Applied Intelligence, vol. 24, no. 1, pp. 17–30, 2006. [A] G. B. Alvarenga, G. R. Mateus, G. de Tomi, "A genetic and set partitioning two-phase approach for the vehicle routing problem with time windows," Computers & Operations Research, vol. 34, no. 6, pp. 1561–1584, 2007. [L] A. Lim and X. Zhang, "A two-stage heuristic with ejection pools and generalized ejection chains for the vehicle routing problem with time windows," Journal on Computing, vol. 19, no. 3, pp. 443–457, 2007. [B] N. Labadi, C Prins, and M. Reghioui, "A memetic algorithm for the vehicle routing problem with time windows," RAIRO-Operations Research, vol. 42, no. 3, pp. 415–431, 2008. [N] Y. Nagata, O. Bräysy, and W. Dullaert, "A penalty-based edge assembly memetic algorithm for the vehicle routing problem with time windows," Computers & Operations Research, vol. 37, no. 4, pp. 724–737, 2010. [H] K. Ghoseiri and S. F. Ghannadpour, "Multi-objective vehicle routing problem with time windows using goal programming and genetic algorithm," Applied Soft Computing, vol. 10, no.4, 1096–1107, 2010. [G] A. Garica-Najera, J. A. Bullinaria, "An improved multi-objective evolutionary algorithm for the vehicle routing problem with time windows," Computer & Operations Research, vol. 38, no. 1, pp. 287–300, 2011. [Y] B. Yu, Z. Z., Yang, and B. Z., Yao, "A hybrid algorithm for vehicle routing problem with time windows," Expert Systems with Applications, vol. 38, no. 1, pp. 435–441, 2011. [K] is our paper ========== [Net set of non-dominated solutions] ========== Each row represents the number of vehicles, the total distance, and the papers that found the solution. r101------------------ Totally 2 Pareto optimal solutions: 19 1650.8 [G][L][N] 20 1642.87 [A] r102------------------ Totally 2 Pareto optimal solutions: 17 1486.12 [L][N] 18 1472.62 [A] r103------------------ Totally 2 Pareto optimal solutions: 13 1292.68 [L][N] 14 1213.62 [A][B] r104------------------ Totally 2 Pareto optimal solutions: 9 1007.31 [L][N] 10 974.24 [H] r105------------------ Totally 2 Pareto optimal solutions: 14 1377.11 [G][L][N] 15 1360.78 [A][B][K] r106------------------ Totally 2 Pareto optimal solutions: 12 1252.03 [L][N] 13 1239.98 [K] r107------------------ Totally 2 Pareto optimal solutions: 10 1104.66 [L][N] 11 1074.24 [B] r108------------------ Totally 2 Pareto optimal solutions: 9 958.66 [Y] 10 942.895 [K] r109------------------ Totally 2 Pareto optimal solutions: 11 1194.73 [L][N] 12 1101.99 [Y] r110------------------ Totally 3 Pareto optimal solutions: 10 1118.84 [L][N] 11 1086.82 [K] 12 1072.42 [B] r111------------------ Totally 3 Pareto optimal solutions: 10 1096.73 [L][N] 11 1054.23 [K] 12 1053.5 [A][K] r112------------------ Totally 2 Pareto optimal solutions: 9 982.14 [N] 10 960.675 [A] r201------------------ Totally 5 Pareto optimal solutions: 4 1252.37 [L][N] 5 1193.29 [K] 6 1171.2 [K] 8 1150.92 [B] 9 1148.48 [A] r202------------------ Totally 4 Pareto optimal solutions: 3 1191.7 [L][N] 4 1079.39 [K] 5 1041.1 [K] 7 1037.5 [B] r203------------------ Totally 4 Pareto optimal solutions: 3 939.5 [L][N] 4 901.201 [K] 5 890.5 [O] 6 874.869 [B] r204------------------ Totally 4 Pareto optimal solutions: 2 825.52 [N] 3 749.417 [K] 4 743.233 [K] 5 735.861 [B] r205------------------ Totally 3 Pareto optimal solutions: 3 994.43 [L][N] 4 959.74 [G][K] 5 954.16 [O] r206------------------ Totally 3 Pareto optimal solutions: 3 906.14 [L][N][K] 4 889.39 [O] 5 879.893 [B] r207------------------ Totally 3 Pareto optimal solutions: 2 890.61 [N] 3 812.755 [K] 4 800.786 [B] r208------------------ Totally 2 Pareto optimal solutions: 2 726.82 [L][N] 3 706.855 [B] r209------------------ Totally 3 Pareto optimal solutions: 3 909.16 [L][N] 4 864.149 [K] 5 859.39 [B] r210------------------ Totally 4 Pareto optimal solutions: 3 938.58 [H] 4 924.785 [K] 5 922.297 [K] 6 912.533 [B] r211------------------ Totally 3 Pareto optimal solutions: 2 885.71 [N] 3 778.041 [K] 4 755.949 [B] rc101------------------ Totally 2 Pareto optimal solutions: 14 1650.14 [Y] 15 1624.97 [K] rc102------------------ Totally 3 Pareto optimal solutions: 12 1554.75 [L][N] 13 1477.54 [K] 14 1461.33 [K] rc103------------------ Totally 1 Pareto optimal solutions: 11 1261.67 [L][N] rc104------------------ Totally 1 Pareto optimal solutions: 10 1135.48 [L][N][K] rc105------------------ Totally 4 Pareto optimal solutions: 13 1629.44 [L][N] 14 1540.18 [G] 15 1519.29 [K] 16 1518.6 [A] rc106------------------ Totally 3 Pareto optimal solutions: 11 1424.73 [L][N] 12 1394.43 [G] 13 1377.35 [A] rc107------------------ Totally 2 Pareto optimal solutions: 11 1222.1 [H] 12 1212.83 [A][B] rc108------------------ Totally 2 Pareto optimal solutions: 10 1139.82 [L][N] 11 1117.53 [A] rc201------------------ Totally 4 Pareto optimal solutions: 4 1406.94 [L][N] 5 1279.65 [Y] 7 1273.51 [K] 8 1272.28 [K] rc202------------------ Totally 4 Pareto optimal solutions: 3 1365.65 [L][N] 4 1162.54 [G] 5 1118.66 [K] 8 1099.54 [B] rc203------------------ Totally 3 Pareto optimal solutions: 3 1049.62 [N] 4 945.083 [K] 5 926.819 [K] rc204------------------ Totally 2 Pareto optimal solutions: 3 798.46 [L][N] 4 788.663 [K] rc205------------------ Totally 4 Pareto optimal solutions: 4 1297.65 [L][N] 5 1236.78 [K] 6 1187.98 [K] 7 1161.81 [A] rc206------------------ Totally 4 Pareto optimal solutions: 3 1146.32 [L][N] 4 1081.83 [K] 5 1068.77 [K] 7 1054.61 [B] rc207------------------ Totally 4 Pareto optimal solutions: 3 1061.14 [L][N] 4 1001.85 [G] 5 982.58 [O] 6 966.372 [B] rc208------------------ Totally 2 Pareto optimal solutions: 3 828.14 [N] 4 783.035 [K]