期刊名称:International Journal of Computer Science and Network Security
印刷版ISSN:1738-7906
出版年度:2020
卷号:20
期号:7
页码:114-123
出版社:International Journal of Computer Science and Network Security
摘要:The vehicle routing problem (VRP) is a very difficult optimization problem. It is an important NP-hard problem that has many real-life applications. The problem is seeking to obtain an optimal tour with minimum distance or cost to serve n customers by m vehicles, such that each vehicle starts from the depot, every customer is visited only once, and all vehicles end tour at the depot. There are many variations of the problem. In this paper, we consider distance-constrained VRP (DVRP) in which entire distance traveled by each vehicle is within a predetermined distance limit. Many exact, heuristic, and metaheuristic methods had been applied to solve the VRP and its variations. We propose to apply genetic algorithm (GA) to solve the problem. In GA, crossover operator plays an important role and hence, selection of good crossover operator leads to efficient GA. We compared four crossover operators on TSPLIB instances to determine the best operator. The experimental study shows that the sequential constructive crossover is superior to the other crossover operators in terms of solution quality for the problem.