Genetic Algorithm applied to the Capacitated Vehicle Routing Problem: an analysis of the influence of different encoding schemes on the population behavior
AbstractGenetic 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.
. 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.
Copyright (c) 2020 American Scientific Research Journal for Engineering, Technology, and Sciences (ASRJETS)
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.
Authors who submit papers with this journal agree to the following terms:
- Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
- Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
- Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work (See The Effect of Open Access).
- By submitting the processing fee, it is understood that the author has agreed to our terms and conditions which may change from time to time without any notice.
- It should be clear for authors that the Editor In Chief is responsible for the final decision about the submitted papers; have the right to accept\reject any paper. The Editor In Chief will choose any option from the following to review the submitted papers:A. send the paper to two reviewers, if the results were negative by one reviewer and positive by the other one; then the editor may send the paper for third reviewer or he take immediately the final decision by accepting\rejecting the paper. The Editor In Chief will ask the selected reviewers to present the results within 7 working days, if they were unable to complete the review within the agreed period then the editor have the right to resend the papers for new reviewers using the same procedure. If the Editor In Chief was not able to find suitable reviewers for certain papers then he have the right to accept\reject the paper.B. sends the paper to a selected editorial board member(s). C. the Editor In Chief himself evaluates the paper.
- Author will take the responsibility what so ever if any copyright infringement or any other violation of any law is done by publishing the research work by the author
- Before publishing, author must check whether this journal is accepted by his employer, or any authority he intends to submit his research work. we will not be responsible in this matter.
- If at any time, due to any legal reason, if the journal stops accepting manuscripts or could not publish already accepted manuscripts, we will have the right to cancel all or any one of the manuscripts without any compensation or returning back any kind of processing cost.
- The cost covered in the publication fees is only for online publication of a single manuscript.