A Meta-heuristic Approach to CVRP Problem: Local Search Optimization Based on GA and Ant Colony

Subject Areas : B. Computer Systems Organization

Arash Mazidi ¹ , Mostafa Fakhrahmad ² , Mohammadhadi Sadreddini ³

1 - Department of Computer Engineering, Shiraz University, Shiraz ,Iran
2 - Department of Computer Engineering, Shiraz University, Shiraz ,Iran
3 - Department of Computer Engineering, Shiraz University, Shiraz ,Iran

Received: 2016-01-18 Accepted : 2016-01-18 Published : 2016-02-01

Keywords: genetic algorithm, Vehicle routing problem, Local Search, Capacitated Vehicle Routing Problem, Meta-heuristic algorithms,

Abstract :

The Capacitated Vehicle Routing Problem (CVRP) is a well-known combinatorial optimization problem that holds a central place in logistics management. The Vehicle Routing is an applied task in the industrial transportation for which an optimal solution will lead us to better services, save more time and ultimately increase in customer satisfaction. This problem is classified into NP-Hard problems and deterministic approaches will be time-consuming to solve it. In this paper, we focus on enhancing the capability of local search algorithms. We use six different meta-heuristic algorithms to solve VRP considering the limited carrying capacity and we analyze their performance on the standard datasets. Finally, we propose an improved genetic algorithm and use the ant colony algorithm to create the initial population. The experimental results show that using of heuristic local search algorithms to solve CVRP is suitable. The results are promising and we observe the proposed algorithm has the best performance among its counterparts.