American Journal of Applied Sciences

Optimized Crossover Genetic Algorithm for Vehicle Routing Problem with Time Windows

H. Nazif and L.S. Lee

DOI : 10.3844/ajassp.2010.95.101

American Journal of Applied Sciences

Volume 7, Issue 1

Pages 95-101

Abstract

Problem statement: In this study, we considered the application of a genetic algorithm to vehicle routing problem with time windows where a set of vehicles with limits on capacity and travel time are available to service a set of customers with demands and earliest and latest time for serving. The objective is to find routes for the vehicles to service all the customers at a minimal cost without violating the capacity and travel time constraints of the vehicles and the time window constraints set by the customers. Approach: We proposed a genetic algorithm using an optimized crossover operator designed by a complete undirected bipartite graph that finds an optimal set of delivery routes satisfying the requirements and giving minimal total cost. Various techniques have also been introduced into the proposed algorithm to further enhance the solutions quality. Results: We tested our algorithm with benchmark instances and compared it with some other heuristics in the literature. The results showed that the proposed algorithm is competitive in terms of the quality of the solutions found. Conclusion/Recommendations: This study presented a genetic algorithm for solving vehicle routing problem with time windows using an optimized crossover operator. From the results, it can be concluded that the proposed algorithm is competitive when compared with other heuristics in the literature.

Copyright

© 2010 H. Nazif and L.S. Lee. This is an open access article distributed under the terms of the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original author and source are credited.