To search, Click below search items. |
| All Published Papers Search Service |
|
|
|
Title |
Comparison of Four Genetic Crossover Operators for Solving Distance-constrained Vehicle Routing Problem |
|
Author |
Khawlah Alabdulkareem and Zakir Hussain Ahmed |
| Citation |
Vol. 20 No. 7 pp. 114-123 |
|
Abstract |
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. |
|
Keywords |
Vehicle routing problem, Distance-constrained, NP-hard, Genetic algorithm, Sequential constructive crossover. |
|
URL |
