Development Of A New Genetic Algorithm For Solving Capacitated Vehicle Routing Problem In Short Time
Bapi Raju Vangipurapu1, Rambabu Govada2, Narayana Rao Kandukuri3
1Vangipurapu Bapi Raju, Dept. of Mechanical Engg, V.R. Siddhartha Engineering College, Vijayawada, 520007, India
2Govada Rambabu , Dept. of Mechanical Engg, Andhra University, Visakhapatnam, 530003, AP, India.
3Kandukuri Narayana Rao, Dept. of Mechanical Engg, Government Polytechnic College, AP, India.
Manuscript received on 23 August 2019. | Revised Manuscript received on 13 September 2019. | Manuscript published on 30 September 2019. | PP: 903-907 | Volume-8 Issue-11, September 2019. | Retrieval Number: K15450981119/2019©BEIESP | DOI: 10.35940/ijitee.K1545.0981119
Open Access | Ethics and Policies | Cite | Mendeley | Indexing and Abstracting
© The Authors. Blue Eyes Intelligence Engineering and Sciences Publication (BEIESP). This is an open access article under the CC-BY-NC-ND license (http://creativecommons.org/licenses/by-nc-nd/4.0/)
Abstract: In this paper a new genetic algorithm is developed for solving capacitated vehicle routing problem (CVRP) in situations where demand is unknown till the beginning of the trip. In these situations it is not possible normal metaheuristics due to time constraints. The new method proposed uses a new genetic algorithm based on modified sweep algorithm that produces a solution with the least number of vehicles, in a relatively short amount of time. The objective of having least number of vehicles is achieved by loading the vehicles nearly to their full capacity, by skipping some of the customers. The reduction in processing time is achieved by restricting the number of chromosomes to just one. This method is tested on 3 sets of standard benchmark instances (A, M, and G) found in the literature. The results are compared with the results from normal metaheuristic method which produces reasonably accurate results. The results indicate that whenever the number of customers and number of vehicles are large the new genetic algorithm provides a much better solution in terms of the CPU time without much increase in total distance traveled. If time permits the output from this method can be further improved by using normal established metaheuristics to get better solution.
Keywords: CVRP, Genetic algorithm, modified sweep algorithm, dynamic demand, Minimum no of Vehicles.
Scope of the Article: Recent Trends & Developments in Computer Networks