Genetic Algorithm applied to the Capacitated Vehicle Routing Problem: an analysis of the influence of different encoding schemes on the population behavior

  • Stanley Jefferson de Araujo Lima Universidade Nove de Julho - UNINOVE, Informatics and Knowledge Management Graduate Program., Rua Vergueiro, 235/249 - Liberdade, Zip Code: 01504-001, São Paulo / SP, Brazil
  • Sidnei Alves de Araújo Universidade Nove de Julho - UNINOVE, Informatics and Knowledge Management Graduate Program., Rua Vergueiro, 235/249 - Liberdade, Zip Code: 01504-001, São Paulo / SP, Brazil
Keywords: Genetic Algorithm, Encoding Scheme, GA Behavior, Capacitated Vehicle Routing Problem

Abstract

Genetic Algorithm (GA) is an optimization method that has been widely used in the solution of NP-Hard (Non-deterministic Polynomial-time) problems, among which is the Vehicle Routing Problem (VRP), widely known in the literature due to its applications in the logistics and supply sectors, and which is considered in this work. However, finding solution for any optimization problem using GA presupposes the adoption of a solution encoding scheme that, according to the literature, impacts its performance. However, there is a lack of works in the literature exploring this theme. In this work we carry out an analysis of the main encoding schemes (binary and integer) employed in the GA for the solution of the capacitated VRP (CVRP), in order to evaluate the influence of each of them on the behavior of the GA population and, consequently, on the algorithm performance. To this end, we developed a computational tool that allows visualizing the GA individuals (solutions) mapped to a two-dimensional space. Based on the experiments conducted, we observed that, in general, integer vectors provide better conditions for GA individuals to explore the solution space, leading to better results. The results found, besides corroborating some assumptions in the literature, may justify the preference for integer encoding schemes to solve CVRP in recent literature works. In addition, this study can contribute to the choice and/or proposition of heuristics that allow GA to search for better quality solutions for the VRP with less computational effort.

References

. Holland, J. H. Adaptation in natural and artificial systems. Cambridge: MIT Press, 1992, pp. 228.

. Lee, S. L., Nazif, H. Optimised crossover genetic algorithm for capacitated vehicle routing problem. Applied Mathematical Modelling, v. 36, 2011, pp. 2110-2117.

. Sánchez-Oro, J., López-Sánchez, A. D., Colmenar, J. M. A general variable neighborhood search for solving the multi-objective open vehicle routing problem. Journal of Heuristics, 2017, pp. 1-30.

. Mandal, S. K., Pacciarelli, D., Lokketangen, A., Hasle, G. A memetic NSGA-II for the bi-objective mixed capacitated general routing problem. J. Heuristics, v.21, 2015, pp. 359-390.

. Azad, T., Hasin, M. Ahsan Akhtar. Capacitated vehicle routing problem using genetic algorithm: a case of cement distribution. International Journal of Logistics Systems and Management, v. 32, n. 1, 2019, pp. 132-146.

. Lima, S. J. A., Araújo, S. A., Schimit, P. T. H. A hybrid approach based on genetic algorithm and nearest neighbor heuristic for solving the capacitated vehicle routing problem. Acta Scientiarum Technology, v. 40, 2018, pp. e36708.

. Cheng, X., AN, L., Zhang, Z. Integer Encoding Genetic Algorithm for Optimizing Redundancy Allocation of Series-parallel Systems. Journal of Engineering Science & Technology Review, v. 12, n. 1, 2019, pp. 126-136.

. Kumar, A. Encoding schemes in genetic algorithm. International Journal of Advanced Research in IT and Engineering. v. 2, n. 3, 2013, pp. 1-7.

. Lima, S. J. A., Araújo, S. A. A new binary encoding scheme in genetic algorithm for solving the capacitated vehicle routing problem. In: International Conference on Bioinspired Methods and Their Applications. Springer, Cham, 2018, pp. 174-184.

. Vieira, H. P. Metaheuristics for solving vehicle routing problems with time window. 2013, 108f. Dissertation (master’s degree in applied mathematics) - Institute of Mathematics, Statistics and Scientific Computing, State University of Campinas, Campinas, Brazil.

. Goldberg, D. E. Genetic Algorithms in search, optimization and machine learning. U.S.A., Addison-Wesley Publishing Company, 1989.

. Brooker, R. J. Concepts of genetics. New York: McGraw-Hill, 2012.

. Michalewicz, Z, Hartley, S. J. Genetic algorithms + data structures = evolution programs. Mathematical Intelligencer, v. 18, n. 3, 1996, pp. 71.

. Lu, C., Yu, V. F. Data envelopment analysis for evaluating the efficiency of genetic algorithms on solving the vehicle routing problem with soft time windows. Computers & Industrial Engineering. v. 63, 2012, pp. 520-529.

. Nguyen, T.T., Yang, S., Branke, J. Evolutionary dynamic optimization: A survey of the state of the art. Swarm and Evolutionary Computation. 6, 2012, pp. 1-24.

. Bermudez, C., Graglia, P., Stark, N., Salto, C., Alfonso, H. Comparison of recombination operators in panmictic and cellular gas to solve a vehicle routing problem. Inteligencia Artificial, v.46, 2010, pp. 34-44.

. Kansou, A., Yassine, A. New upper bounds for the multi-depot capacitated arc routing problem. International Journal of Metaheuristics, v. 1, n. 1, 2010, pp. 81-95.

. Lau, H. C. W, Chan, T. M., Tsui, W. T., Pang, W. K. Application of genetic algorithms to solve the multidepot vehicle routing problem. IEEE Transactions on Automation Science and Engineering, v. 7, n. 2, 2010, pp. 383-392.

. Wang, C., Lu, J. An effective evolutionary algorithm for the practical capacitated vehicle routing problems. Journal of Intelligent Manufacturing, v. 21, n. 4, 2010, pp. 363-375.

. Ursani, Z., Essam, D., Cornforth, D., Stocker, R. Localized genetic algorithm for vehicle routing problem with time windows. Applied Soft Computing, v. 11, n. 8, 2011, pp. 5375-5390.

. Masum, A. K. M., Shahjalal, M., Faruque, Md. F., Sarker, Md. I. H. Solving the vehicle routing problem using genetic algorithm. Internacional Journal of Advanced Computer Science and Applications, v. 2, n.7, 2012, pp. 126-131.

. Reiter, P., Gutjahr, W. J. Exact hybrid algorithms for solving a bi-objective vehicle routing problem. Central European Journal of Operations Research, v. 20, n. 1, 2012, pp. 19-43.

. Vidal, T., Crainic, T. G., Gendreau, M., Lahrichi, N., Rei, W. A hybrid genetic algorithm for multi-depot and periodic vehicle routing problems. Operations Research, v. 60, n. 3, 2012, pp. 611-624.

. Cho, D. W., Lee, Y. H., Lee, T. Y., Gen, M. An adaptive genetic algorithm for the time dependent inventory routing problem. Journal of Intelligent Manufacturing, v. 25, n. 5, 2014, pp. 1025-1042.

. Liu, R., Jiang, Z., Geng, N. A hybrid genetic algorithm for the multi-depot open vehicle routing problem. OR spectrum, v. 36, n. 2, 2014, pp. 401-421.

. Osaba, E., Diaz, F., Oniera, E. Golden Ball: a novel meta-heuristic to solve combinatorial optimization problems based on soccer concepts. Applications Intelligence. v.41, 2014, pp. 145-166.

. Khalili-Damghani, K., Abtahi, A., Ghasemi, A. A new bi-objective location-routing problem for distribution of perishable products: evolutionary computation approach. Journal of Mathematical Modelling and Algorithms in Operations Research, v. 14, n. 3, 2015, pp. 287-312.

. Lima, S. J. A., Santos, R. A. R., Araújo, S. A. Optimization of the Capacitated Vehicle Routing Problem Using Genetic Algorithms and the Heuristics Downhill and Gillett & Miller. In: Proc. of XXXV National Meeting of Production Engineering. Rio de Janeiro: ABEPRO, v. 1. 2015, pp. 1-15.

. Wang, K., Lan, S, Zhao, Y. A genetic-algorithm-based approach to the two-echelon capacitated vehicle routing problem with stochastic demands in logistics service. Journal of the Operational Research Society, v. 68, n. 11, 2017, pp. 1409-1421.

. Hosseinabadi, A. A. R, Slowik, A., Sadeghilalimi, M., Farokhzad, M., Sangaiah, A. K. An Ameliorative Hybrid Algorithm for Solving the Capacitated Vehicle Routing Problem. IEEE Access, v. 7, 2019, pp. 175454-175465.

. Christofides, N. Vehicle Routing. In: The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization, Lawer, EL., Lenstra, J.K, Kan, A.H.G.R., Shmoys, D.B (Eds), John Wiley & Sons, 1985.

. Kalatzantonakis, P., Sifaleras, A., Samaras, N. Cooperative versus non-cooperative parallel variable neighborhood search strategies: a case study on the capacitated vehicle routing problem. Journal of Global Optimization, 2019, pp. 1-22.

. Reinelt, G., Wenger, M. K. Maximally violated mod-p cuts for the capacitated vehicle-routing problem. INFORMS Journal on Computing, v. 18, 2006, pp.466-476.

. Gillett, B., Miller, L. R. A heuristic algorithm for the vehicle dispatch problem. Operations Research, v. 22, 1974, pp. 340-349.

Published
2020-10-19
Section
Articles