Optimized crossover genetic algorithm for vehicle routing problem with time windows
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 o...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Science Publications
2010
|
| Online Access: | http://psasir.upm.edu.my/id/eprint/15960/ http://psasir.upm.edu.my/id/eprint/15960/1/ajassp.2010.95.101.pdf |
| _version_ | 1848842826386767872 |
|---|---|
| author | Nazif, Habibeh Lee, Lai Soon |
| author_facet | Nazif, Habibeh Lee, Lai Soon |
| author_sort | Nazif, Habibeh |
| building | UPM Institutional Repository |
| collection | Online Access |
| description | 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. |
| first_indexed | 2025-11-15T08:05:18Z |
| format | Article |
| id | upm-15960 |
| institution | Universiti Putra Malaysia |
| institution_category | Local University |
| language | English |
| last_indexed | 2025-11-15T08:05:18Z |
| publishDate | 2010 |
| publisher | Science Publications |
| recordtype | eprints |
| repository_type | Digital Repository |
| spelling | upm-159602017-11-30T09:51:00Z http://psasir.upm.edu.my/id/eprint/15960/ Optimized crossover genetic algorithm for vehicle routing problem with time windows Nazif, Habibeh Lee, Lai Soon 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. Science Publications 2010 Article PeerReviewed application/pdf en http://psasir.upm.edu.my/id/eprint/15960/1/ajassp.2010.95.101.pdf Nazif, Habibeh and Lee, Lai Soon (2010) Optimized crossover genetic algorithm for vehicle routing problem with time windows. American Journal of Applied Sciences, 7 (1). pp. 95-101. ISSN 1546-9239; ESSN: 1554-3641 http://thescipub.com/abstract/10.3844/ajassp.2010.95.101 10.3844/ajassp.2010.95.101 |
| spellingShingle | Nazif, Habibeh Lee, Lai Soon Optimized crossover genetic algorithm for vehicle routing problem with time windows |
| title | Optimized crossover genetic algorithm for vehicle routing problem with time windows |
| title_full | Optimized crossover genetic algorithm for vehicle routing problem with time windows |
| title_fullStr | Optimized crossover genetic algorithm for vehicle routing problem with time windows |
| title_full_unstemmed | Optimized crossover genetic algorithm for vehicle routing problem with time windows |
| title_short | Optimized crossover genetic algorithm for vehicle routing problem with time windows |
| title_sort | optimized crossover genetic algorithm for vehicle routing problem with time windows |
| url | http://psasir.upm.edu.my/id/eprint/15960/ http://psasir.upm.edu.my/id/eprint/15960/ http://psasir.upm.edu.my/id/eprint/15960/ http://psasir.upm.edu.my/id/eprint/15960/1/ajassp.2010.95.101.pdf |