Abstract

This paper aims to examine the capacitated vehicle routing problem (CVRP). It is a major logistics problem encountered by any company that must organize the distribution of its products. The CVRP is an NP-hard problem. This problem involves planning vehicle routes that are to serve a number of customers from a depot. The capacity of each vehicle is limited and each customer has demanded who must be satisfied. The objective of this problem is to minimize the total distance travelled by vehicles. It is a very broad class of problems, including the famous traveling salesman problem (TSP). The goal of this paper is to find a solution for CVRP using a hybrid heuristic. This heuristic, called, genetic local search algorithm (GA-LS). We propose a genetic algorithm with a new procedure crossover operator to minimize the total travelled distance. To simplify the problem, a natural number coding is used and to assure enough diversification into the algorithm the best selection is retained. Local search uses performance indicators in order to maintain a balance between convergence and the diversity of the solutions obtained. Large numerical experiments are made to prove the efficiency of the proposed algorithm. Our approach is compared to the different existing approaches. The results show that our approach is very competitive in terms of the solutions obtained. Based on five reference data sets our approach obtains a total of 45 values equal to the best- known solution for 57 instances.

Keyword

Capacitated vehicle routing problem, Genetic algorithm, Optimization, Local search.

Cite this article

Refference

[1][1]Eksioglu B, Vural AV, Reisman A. The vehicle routing problem: a taxonomic review. Computers & Industrial Engineering. 2009; 57(4):1472-83.

[2][2]Fisher M. Vehicle routing. Handbooks in operations research and management science. 1995; 8:1-33.

[3][3]Golden BL, Raghavan S, Wasil EA. The vehicle routing problem: latest advances and new challenges. Springer Science & Business Media; 2008.

[4][4]Braekers K, Ramaekers K, Van Nieuwenhuyse I. The vehicle routing problem: state of the art classification and review. Computers & Industrial Engineering. 2016; 99:300-13.

[5][5]Berger J, Salois M, Begin R. A hybrid genetic algorithm for the vehicle routing problem with time windows. In conference of the Canadian society for computational studies of intelligence 1998 (pp. 114-27). Springer, Berlin, Heidelberg.

[6][6]Berger J, Barkaoui M. A new hybrid genetic algorithm for the capacitated vehicle routing problem. Journal of the Operational Research Society. 2003; 54(12):1254-62.

[7][7]Baker BM, Ayechew MA. A genetic algorithm for the vehicle routing problem. Computers & Operations Research. 2003; 30(5):787-800.

[8][8]Jeon G, Leep HR, Shim JY. A vehicle routing problem solved by using a hybrid genetic algorithm. Computers & Industrial Engineering. 2007; 53(4):680-92.

[9][9]Alvarenga GB, Mateus GR, De Tomi G. A genetic and set partitioning two-phase approach for the vehicle routing problem with time windows. Computers & Operations Research. 2007; 34(6):1561-84.

[10][10]Ho W, Ho GT, Ji P, Lau HC. A hybrid genetic algorithm for the multi-depot vehicle routing problem. Engineering Applications of Artificial Intelligence. 2008; 21(4):548-57.

[11][11]Yurtkuran A, Emel E. A new hybrid electromagnetism-like algorithm for capacitated vehicle routing problems. Expert Systems with Applications. 2010; 37(4):3427-33.

[12][12]Cui L, Wang L, Deng J, Zhang J. A new improved quantum evolution algorithm with local search procedure for capacitated vehicle routing problem. Mathematical Problems in Engineering. 2013.

[13][13]De Carvalho Oliveira RA, Delgado KV. Capacitated vehicle routing system applying monte carlo methods. proceedings of the xi brazilian symposium on information systems (SBSI), Goiânia. 2015 (pp.1-8).

[14][14]Mazidi A, Fakhrahmad M, Sadreddini MH. A meta-heuristic approach to CVRP problem: local search optimization based on GA and ant colony. Journal of Advances in Computer Research. 2016; 7(1):1-22.

[15][15]Vincent FY, Redi AP, Yang CL, Ruskartina E, Santosa B. Symbiotic organisms search and two solution representations for solving the capacitated vehicle routing problem. Applied Soft Computing. 2017; 52:657-72.

[16][16]Sun X, Fu Y, Liu T. A hybrid ACO algorithm for capacitated vehicle routing problems. In 2nd advanced information technology, electronic and automation control conference (IAEAC) 2017 (pp. 510-4). IEEE.

[17][17]Azad T, Hasin MA. Capacitated vehicle routing problem using genetic algorithm: a case of cement distribution. International Journal of Logistics Systems and Management. 2019; 32(1):132-46.

[18][18]Letchford AN, Salazar-González JJ. The capacitated vehicle routing problem: stronger bounds in pseudo-polynomial time. European Journal of Operational Research. 2019; 272(1):24-31.

[19][19]Hosseinabadi AA, Slowik A, Sadeghilalimi M, Farokhzad M, Sangaiah AK. An ameliorative hybrid algorithm for solving the capacitated vehicle routing problem. IEEE Access. 2019; 7:175454-65.

[20][20]Wei L, Zhang Z, Zhang D, Lim A. A variable neighborhood search for the capacitated vehicle routing problem with two-dimensional loading constraints. European Journal of Operational Research. 2015; 243(3):798-814.

[21][21]Wei L, Zhang Z, Zhang D, Leung SC. A simulated annealing algorithm for the capacitated vehicle routing problem with two-dimensional loading constraints. European Journal of Operational Research. 2018; 265(3):843-59.

[22][22]Mohammed MA, Ghani MK, Hamed RI, Mostafa SA, Ahmad MS, Ibrahim DA. Solving vehicle routing problem by using improved genetic algorithm for optimal solution. Journal of Computational Science. 2017; 21:255-62.

[23][23]Amous M, Toumi S, Jarboui B, Eddaly M. A variable neighborhood search algorithm for the capacitated vehicle routing problem. Electronic Notes in Discrete Mathematics. 2017; 58:231-8.

[24][24]Akpinar S. Hybrid large neighbourhood search algorithm for capacitated vehicle routing problem. Expert Systems with Applications. 2016; 61:28-38.

[25][25]Stanojević M, Stanojević B, Vujošević M. Enhanced savings calculation and its applications for solving capacitated vehicle routing problem. Applied Mathematics and Computation. 2013; 219(20):10302-12.

[26][26]Faiz A, Arief UM. An efficient meta-heuristic algorithm for solving capacitated vehicle routing problem. International Journal of Advances in Intelligent Informatics. 2018; 4(3):212-25.

[27][27]Chen P, Huang HK, Dong XY. Iterated variable neighborhood descent algorithm for the capacitated vehicle routing problem. Expert Systems with Applications. 2010; 37(2):1620-7.

[28][28]Kao Y, Chen MH, Huang YT. A hybrid algorithm based on ACO and PSO for capacitated vehicle routing problems. Mathematical Problems in Engineering. 2012.

[29]