Optimised crossover genetic algorithm for capacitated vehicle routing problem
This paper presents a genetic algorithm for solving capacitated vehicle routing problem, which is mainly characterised by using vehicles of the same capacity based at a central depot that will be optimally routed to supply customers with known demands. The proposed algorithm uses an optimised crosso...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Elsevier
2012
|
| Online Access: | http://psasir.upm.edu.my/id/eprint/25245/ http://psasir.upm.edu.my/id/eprint/25245/1/Optimised%20crossover%20genetic%20algorithm%20for%20capacitated%20vehicle%20routing%20problem.pdf |
| _version_ | 1848845256192163840 |
|---|---|
| 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 | This paper presents a genetic algorithm for solving capacitated vehicle routing problem, which is mainly characterised by using vehicles of the same capacity based at a central depot that will be optimally routed to supply customers with known demands. The proposed algorithm uses an optimised crossover operator designed by a complete undirected bipartite graph to find an optimal set of delivery routes satisfying the requirements and giving minimal total cost. We tested our algorithm with benchmark instances and compared it with some other heuristics in the literature. Computational results showed that the proposed algorithm is competitive in terms of the quality of the solutions found. |
| first_indexed | 2025-11-15T08:43:55Z |
| format | Article |
| id | upm-25245 |
| institution | Universiti Putra Malaysia |
| institution_category | Local University |
| language | English |
| last_indexed | 2025-11-15T08:43:55Z |
| publishDate | 2012 |
| publisher | Elsevier |
| recordtype | eprints |
| repository_type | Digital Repository |
| spelling | upm-252452018-01-16T08:59:39Z http://psasir.upm.edu.my/id/eprint/25245/ Optimised crossover genetic algorithm for capacitated vehicle routing problem Nazif, Habibeh Lee, Lai Soon This paper presents a genetic algorithm for solving capacitated vehicle routing problem, which is mainly characterised by using vehicles of the same capacity based at a central depot that will be optimally routed to supply customers with known demands. The proposed algorithm uses an optimised crossover operator designed by a complete undirected bipartite graph to find an optimal set of delivery routes satisfying the requirements and giving minimal total cost. We tested our algorithm with benchmark instances and compared it with some other heuristics in the literature. Computational results showed that the proposed algorithm is competitive in terms of the quality of the solutions found. Elsevier 2012-05 Article PeerReviewed application/pdf en http://psasir.upm.edu.my/id/eprint/25245/1/Optimised%20crossover%20genetic%20algorithm%20for%20capacitated%20vehicle%20routing%20problem.pdf Nazif, Habibeh and Lee, Lai Soon (2012) Optimised crossover genetic algorithm for capacitated vehicle routing problem. Applied Mathematical Modelling, 36 (5). pp. 2110-2117. ISSN 0307-904X; ESSN: 1872-8480 10.1016/j.apm.2011.08.010 |
| spellingShingle | Nazif, Habibeh Lee, Lai Soon Optimised crossover genetic algorithm for capacitated vehicle routing problem |
| title | Optimised crossover genetic algorithm for capacitated vehicle routing problem |
| title_full | Optimised crossover genetic algorithm for capacitated vehicle routing problem |
| title_fullStr | Optimised crossover genetic algorithm for capacitated vehicle routing problem |
| title_full_unstemmed | Optimised crossover genetic algorithm for capacitated vehicle routing problem |
| title_short | Optimised crossover genetic algorithm for capacitated vehicle routing problem |
| title_sort | optimised crossover genetic algorithm for capacitated vehicle routing problem |
| url | http://psasir.upm.edu.my/id/eprint/25245/ http://psasir.upm.edu.my/id/eprint/25245/ http://psasir.upm.edu.my/id/eprint/25245/1/Optimised%20crossover%20genetic%20algorithm%20for%20capacitated%20vehicle%20routing%20problem.pdf |