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

Wei-Huai Hsu and Tsung-Che Chiang, A multiobjective evolutionary algorithm with enhanced reproduction operators for the vehicle routing problem with time windows, Proc. of IEEE World Congress on Computational Intelligence, pp. 2629 - 2636, Brisbane, June, 2012.

Full text: Official version

Abstract

This paper addresses the vehicle routing problem with time windows (VRPTW). The task is to assign customers to multiple vehicles and determine the visiting sequences of customers for the vehicles without violating the vehicle capacity constraint and customer service time window constraints. Two common objectives of VRPTW are to minimize the number of vehicles and the total traveling distance. Most of previous studies assumed that the number of vehicles is more important than the total distance. Hence, they solved the VRPTW by minimizing the number of vehicles first and then minimizing the total distance under the minimal number of vehicles. Recently, researchers started to solve the VRPTW without this assumption and tried to minimize both objectives simultaneously through searching for the Pareto optimal set of solutions. Following this perspective, we use a multiobjective evolutionary algorithm to solve the VRPTW. We propose enhanced crossover and mutation operators by incorporating the domain knowledge. Performance of the proposed algorithm is verified on a widely used benchmark problem set. Comparing with seven existing algorithms, our algorithm shows competitive performance and contributes many new best known Pareto optimal solutions.

Benchmark problem instances

• Solomon's VRPTW instances (6 categories, 56 instances)

Benchmark algorithms

• 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.

• 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, 724–737, 2010.

• 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. 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.

• 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.

• 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.

List of non-dominated solutions

Download