Evolutionary Algorithms (EAs) for Vehicle Routing Problem (VRP)

^Authors: Andrew Owusu-Hemeng¹, Peter Kwasi Sarpong², Joseph Ackora-Prah³

^1,2,3Department of Mathematics, Kwame Nkrumah University of Science and Technology,Kumasi,Ghana

Email:  owusuhemengandrew@gmail.com, kp.sarp@yahoo.co.uk, ackph@yahoo.co.uk

 Abstract

Genetic Algorithms (GAs) are powerful and widely applicable stochastic search technique and optimization methods based on the principles of genetics, natural selection and natural evaluation. Thus GA is a stochastic global search method that mimics the metaphor of natural biological evolution. This work discusses the concept of design procedure of Genetic Algorithm and explores a well-established methodology of the literature to realize the workability and application of genetic algorithm. The Vehicle Routing Problem (VRP) is a complex combinatorial optimization problem where one or more vehicles can be used in the solution. The optimization can be described as follows: given a fleet of vehicles, a common depot and several requests by the customers, find the set of routes with overall minimum route cost which service all the demands. Because of the fact that VRP is already a complex, namely an NP-complex problem, heuristic optimization algorithms, like Genetic Algorithms (GAs) need to be taken into account. This requires special, interpretable encoding to ensure efficiency. In this paper, GA is used to solve these problems and propose a novel, easily interpretable. Genetic algorithms are used to model the Vehicle Routing Problem. MATLAB simulations was carried out to find the optimal route of Amponsah Efah Pharmaceuticals Limited as. The corresponding distances (fitness) of their distribution route was found to be 7560m.

 Keywords: Evolutionary Algorithms (EAs, Vehicle Routing Problem (VRP)

Download