TY - JOUR
T1 - A knowledge-based evolutionary algorithm for the multiobjective vehicle routing problem with time windows
AU - Chiang, Tsung Che
AU - Hsu, Wei Huai
N1 - Funding Information:
The authors are grateful to the editor and the reviewers for their valuable suggestions and comments. This research was supported by the National Science Council of the Republic of China (Taiwan) under Grant no. NSC100-2221-E-003-004.
PY - 2014/5
Y1 - 2014/5
N2 - 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.
AB - 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.
KW - Evolutionary algorithm
KW - Multiobjective
KW - Pareto optimal
KW - Time windows
KW - Vehicle routing problem
UR - http://www.scopus.com/inward/record.url?scp=84891442641&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84891442641&partnerID=8YFLogxK
U2 - 10.1016/j.cor.2013.11.014
DO - 10.1016/j.cor.2013.11.014
M3 - Article
AN - SCOPUS:84891442641
SN - 0305-0548
VL - 45
SP - 25
EP - 37
JO - Computers and Operations Research
JF - Computers and Operations Research
ER -