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

Journal of Advances in Computer Research

شناسنامه علمی شماره، دوره 7، شماره 1، اردیبهشت 2016، صفحه 1-22   

نویسندگان

Arash Mazidi^* ؛ Mostafa Fakhrahmad؛ Mohammadhadi Sadreddini

Department of Computer Engineering, Shiraz University, Shiraz ,Iran

چکیده

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.

کلیدواژه‌ها

Vehicle routing problem؛ Capacitated Vehicle Routing Problem؛ Meta-heuristic algorithms؛ Local Search؛ genetic algorithm