Tsung-Che Chiang >> Publications >> KBEA for MOVRPTW, COR 2014

Associate Professor Tsung-Che Chiang

Department of Computer Science and Information Engineering
National Taiwan Normal University

Tel: +886-2-77346692 Fax: +886-2-29322378 Email

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, pp. 25 - 37, 2014.

=*= Top 25 Hottest Articles in C&OR during 2014/1-2014/3 =*=

Full text: Unedited version; Official version

Abstract

This paper addresses the multiobjective vehicle routing problem with time windows (MOVRPTW). The objectives are to minimize the number of vehicles and the total distance simultaneously. Our approach is based on an evolutionary algorithm and aims to find the set of Pareto optimal solutions. We incorporate problem-specific knowledge into the genetic operators. The crossover operator exchanges one of the best routes, which has the shortest average distance, the relocation mutation operator relocates a large number of customers in non-decreasing order of the length of the time window, and the split mutation operator breaks the longest-distance link in the routes. Our algorithm is compared with 10 existing algorithms by standard 100-customer and 200-customer problem instances. It shows competitive performance and updates more than 1/3 of the net set of the non-dominated solutions.

Benchmark problem instances

Solomon's VRPTW instances (r1/r2/rc1/rc2 categories, 39 100-customer instances)
Gehring and Homberger's VRPTW instances (6 categories, 60 200-customer instances)

Benchmark algorithms

[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.
[V] T. Vidal, T. G. Crainic, M. Gendreau, and C. Prins, "A hybrid genetic algorithm with adaptive diversity management for a large class of vehicle routing problems with time-windows," Computers & Operations Research, vol. 40, no. 1, pp. 475–489, 2013.

List of non-dominated solutions