{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,3]],"date-time":"2026-03-03T18:57:53Z","timestamp":1772564273232,"version":"3.50.1"},"reference-count":45,"publisher":"MDPI AG","issue":"1","license":[{"start":{"date-parts":[[2021,12,28]],"date-time":"2021-12-28T00:00:00Z","timestamp":1640649600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100002848","name":"Agencia Nacional de Investigaci\u00f3n y Desarrollo","doi-asserted-by":"publisher","award":["21191028"],"award-info":[{"award-number":["21191028"]}],"id":[{"id":"10.13039\/501100002848","id-type":"DOI","asserted-by":"publisher"}]},{"name":"STIC AM-SUD 2019","award":["-"],"award-info":[{"award-number":["-"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Entropy"],"abstract":"<jats:p>Vehicle Routing Problems (VRP) comprise many variants obtained by adding to the original problem constraints representing diverse system characteristics. Different variants are widely studied in the literature; however, the impact that these constraints have on the structure of the search space associated with the problem is unknown, and so is their influence on the performance of search algorithms used to solve it. This article explores how assignation constraints (such as a limited vehicle capacity) impact VRP by disturbing the network structure defined by the solution space and the local operators in use. This research focuses on Fitness Landscape Analysis for the multiple Traveling Salesman Problem (m-TSP) and Capacitated VRP (CVRP). We propose a new Fitness Landscape Analysis measure that provides valuable information to characterize the fitness landscape\u2019s structure under specific scenarios and obtain several relationships between the fitness landscape\u2019s structure and the algorithmic performance.<\/jats:p>","DOI":"10.3390\/e24010053","type":"journal-article","created":{"date-parts":[[2021,12,28]],"date-time":"2021-12-28T06:55:03Z","timestamp":1640674503000},"page":"53","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":10,"title":["Constrained Fitness Landscape Analysis of Capacitated Vehicle Routing Problems"],"prefix":"10.3390","volume":"24","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-7374-4420","authenticated-orcid":false,"given":"Sebasti\u00e1n","family":"Mu\u00f1oz-Herrera","sequence":"first","affiliation":[{"name":"Departamento de Ingenier\u00eda Industrial, Universidad Cat\u00f3lica de la Sant\u00edsima Concepci\u00f3n, Alonso de Ribera 2850, Concepcion 4090541, Chile"},{"name":"Facultad de Ingenier\u00eda y Ciencias, Universidad Adolfo Ib\u00e1\u00f1ez, Av. Diagonal las Torres 2640, Santiago 7941169, Chile"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0793-0924","authenticated-orcid":false,"given":"Karol","family":"Suchan","sequence":"additional","affiliation":[{"name":"Facultad de Ingenier\u00eda y Ciencias, Universidad Diego Portales, Av. Ej\u00e9rcito Libertador 441, Santiago 8370191, Chile"},{"name":"Faculty of Applied Mathematics, AGH University of Science and Technology, al. A. Mickiewicza 30, 30-059 Krakow, Poland"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2021,12,28]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","unstructured":"Toth, P., and Vigo, D. (2014). The Family of Vehicle Routing Problems. Vehicle Routing, SIAM.","DOI":"10.1137\/1.9781611973594"},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/j.ejor.2013.02.053","article-title":"Heuristics for Multi-Attribute Vehicle Routing Problems: A Survey and Synthesis","volume":"231","author":"Vidal","year":"2013","journal-title":"Eur. J. Oper. Res."},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"33","DOI":"10.1007\/BF02430364","article-title":"Testing Heuristics: We Have It All Wrong","volume":"1","author":"Hooker","year":"1995","journal-title":"J. Heuristics"},{"key":"ref_4","unstructured":"Pitzer, E. (2013). Applied Fitness Landscape Analysis. [Ph.D. Thesis, Johannes Kepler University Linz]."},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"480","DOI":"10.1016\/0377-2217(94)00064-J","article-title":"Improvement Heuristics for the Vehicle Routing Problem Based on Simulated Annealing","volume":"86","year":"1995","journal-title":"Eur. J. Oper. Res."},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"1985","DOI":"10.1016\/S0305-0548(03)00158-8","article-title":"A Simple and Effective Evolutionary Algorithm for the Vehicle Routing Problem","volume":"31","author":"Prins","year":"2004","journal-title":"Comput. Oper. Res."},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"209","DOI":"10.1016\/j.omega.2004.10.004","article-title":"The Multiple Traveling Salesman Problem: An Overview of Formulations and Solution Procedures","volume":"34","author":"Bektas","year":"2006","journal-title":"Omega"},{"key":"ref_8","doi-asserted-by":"crossref","unstructured":"Diestel, R. (2017). Graph Theory, Springer.","DOI":"10.1007\/978-3-662-53622-3"},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"255","DOI":"10.1007\/BF01589353","article-title":"Exact Algorithms for the Vehicle Routing problem, based on Spanning Tree and Shortest Path Relaxations","volume":"20","author":"Christofides","year":"1981","journal-title":"Math. Program."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"119","DOI":"10.1287\/trsc.1030.0057","article-title":"Vehicle Routing Problem with Time Windows, Part II: Metaheuristics","volume":"39","author":"Gendreau","year":"2005","journal-title":"Transp. Sci."},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"104","DOI":"10.1287\/trsc.1030.0056","article-title":"Vehicle Routing Problem with Time Windows, Part I: Route Construction and Local Search Algorithms","volume":"39","author":"Gendreau","year":"2005","journal-title":"Transp. Sci."},{"key":"ref_12","first-page":"78","article-title":"Towards a Theory of Landscapes","volume":"Volume 461","author":"Waelbroeck","year":"1995","journal-title":"Complex Systems and Binary Networks"},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"325","DOI":"10.1007\/BF00202749","article-title":"Correlated and Uncorrelated Fitness Landscapes and How to Tell the Difference","volume":"63","author":"Weinberger","year":"1990","journal-title":"Biol. Cybern."},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"31","DOI":"10.1162\/106365600568095","article-title":"Information Characteristics and the Structure of Landscapes","volume":"8","author":"Vassilev","year":"2000","journal-title":"Evol. Comput."},{"key":"ref_15","doi-asserted-by":"crossref","unstructured":"Malan, K.M., Oberholzer, J.F., and Engelbrecht, A.P. (2015, January 25\u201328). Characterising Constrained Continuous Optimisation Problems. Proceedings of the IEEE Congress on Evolutionary Computation, Sendai, Japan.","DOI":"10.1109\/CEC.2015.7257045"},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"229","DOI":"10.1016\/S0304-3975(97)00176-X","article-title":"Autocorrelation Coefficient for the Graph Bipartitioning Problem","volume":"191","author":"Angel","year":"1998","journal-title":"Theor. Comput. Sci."},{"key":"ref_17","first-page":"243","article-title":"Genetic Algorithm Difficulty and the Modality of Fitness Landscapes","volume":"Volume 3","author":"Whitley","year":"1995","journal-title":"Foundations of Genetic Algorithms 3"},{"key":"ref_18","doi-asserted-by":"crossref","unstructured":"Malan, K.M., and Engelbrecht, A.P. (2009, January 18\u201321). Quantifying Ruggedness of Continuous Landscapes Using Entropy. Proceedings of the IEEE Congress on Evolutionary Computation, Trondheim, Norway.","DOI":"10.1109\/CEC.2009.4983112"},{"key":"ref_19","unstructured":"Boese, K.D. (1995). Cost Versus Distance In the Traveling Salesman Problem, UCLA Computer Science Department. Technical Report."},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"265","DOI":"10.1007\/s10732-017-9334-0","article-title":"Mapping the Global Structure of TSP Fitness Landscapes","volume":"24","author":"Ochoa","year":"2018","journal-title":"J. Heuristics"},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"373","DOI":"10.1006\/jtbi.1993.1195","article-title":"Anisotropy in Fitness Landscapes","volume":"165","author":"Stadler","year":"1993","journal-title":"J. Theor. Biol."},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"347","DOI":"10.1162\/EVCO_a_00154","article-title":"An Analysis of the Fitness Landscape of Travelling Salesman Problem","volume":"24","year":"2016","journal-title":"Evol. Comput."},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"345","DOI":"10.1007\/978-0-387-71921-4_18","article-title":"Distance Measures and Fitness-Distance Analysis for the Capacitated Vehicle Routing Problem","volume":"Volume 39","author":"Doerner","year":"2007","journal-title":"Metaheuristics: Progress in Complex Systems Optimization"},{"key":"ref_24","doi-asserted-by":"crossref","unstructured":"Czech, Z.J. (2008, January 14\u201318). Statistical Measures of a Fitness Landscape for the Vehicle Routing Problem. Proceedings of the IEEE International Symposium on Parallel and Distributed Processing, Miami, FL, USA.","DOI":"10.1109\/IPDPS.2008.4536369"},{"key":"ref_25","doi-asserted-by":"crossref","unstructured":"Runka, A., Ombuki-Berman, B., and Ventresca, M. (2009, January 8\u201312). A Search Space Analysis for the Waste Collection Vehicle Routing Problem with Time Windows. Proceedings of the 11th Annual Conference on Genetic and Evolutionary Computation (GECCO \u201909), Montreal, QC, Canada.","DOI":"10.1145\/1569901.1570175"},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"214","DOI":"10.1007\/978-3-642-37198-1_19","article-title":"Predicting Genetic Algorithm Performance on the Vehicle Routing Problem Using Information Theoretic Landscape Measures","volume":"Volume 7832","author":"Middendorf","year":"2013","journal-title":"Evolutionary Computation in Combinatorial Optimization"},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"75","DOI":"10.1007\/978-3-319-01128-8_6","article-title":"Fitness Landscape Analysis of NK Landscapes and Vehicle Routing Problems by Expanded Barrier Trees","volume":"Volume 227","author":"Emmerich","year":"2013","journal-title":"EVOLVE\u2014A Bridge Between Probability, Set Oriented Numerics, and Evolutionary Computation IV"},{"key":"ref_28","first-page":"119","article-title":"Fitness Landscape Analysis for Capacitated Vehicle Routing Problem","volume":"Volume 163","author":"Zhong","year":"2012","journal-title":"Proceedings of the 2012 International Conference on Cybernetics and Informatics"},{"key":"ref_29","doi-asserted-by":"crossref","unstructured":"Kov\u00e1cs, L., Ag\u00e1rdi, A., and B\u00e1nyai, T. (2020). Fitness Landscape Analysis and Edge Weighting-Based Optimization of Vehicle Routing Problems. Processes, 8.","DOI":"10.3390\/pr8111363"},{"key":"ref_30","doi-asserted-by":"crossref","unstructured":"Ag\u00e1rdi, A., Kov\u00e1cs, L., and B\u00e1nyai, T. (2021). An Attraction Map Framework of a Complex Multi-Echelon Vehicle Routing Problem with Random Walk Analysis. Appl. Sci., 11.","DOI":"10.3390\/app11052100"},{"key":"ref_31","doi-asserted-by":"crossref","unstructured":"Diez, P., Neittaanm\u00e4ki, P., Periaux, J., Tuovinen, T., and Pons-Prats, J. (2020). Application of a Knowledge Discovery Process to Study Instances of Capacitated Vehicle Routing Problems. Computation and Big Data for Transport, Springer. Computational Methods in Applied Sciences.","DOI":"10.1007\/978-3-030-37752-6"},{"key":"ref_32","doi-asserted-by":"crossref","first-page":"148","DOI":"10.1016\/j.ins.2013.04.015","article-title":"A Survey of Techniques for Characterising Fitness Landscapes and Some Possible Ways Forward","volume":"241","author":"Malan","year":"2013","journal-title":"Inf. Sci."},{"key":"ref_33","doi-asserted-by":"crossref","unstructured":"Malan, K.M. (2021). A Survey of Advances in Landscape Analysis for Optimisation. Algorithms, 14.","DOI":"10.3390\/a14020040"},{"key":"ref_34","doi-asserted-by":"crossref","unstructured":"Kokoska, S., and Zwillinger, D. (2000). CRC Standard Probability and Statistics Tables and Formulae, Student Edition, CRC Press.","DOI":"10.1201\/b16923"},{"key":"ref_35","unstructured":"Augerat, P., Belenguer, J.M., Benavent, E., Corberan, A., Naddef, D., and Rinaldi, G. (1995). Computacional Results with a Branch-and-Cut Code for the Capacited Vehicle Routing Problem. Technical Report INPG-RR-949-M, Institut National Polytechnique."},{"key":"ref_36","unstructured":"Christofides, N., Mingozzi, A., Toth, P., and Sandi, C. (1979). The Vehicle Routing Problem. Combinatorial Optimization, Wiley."},{"key":"ref_37","doi-asserted-by":"crossref","first-page":"845","DOI":"10.1016\/j.ejor.2016.08.012","article-title":"New Benchmark Instances for the Capacitated Vehicle Routing Problem","volume":"257","author":"Uchoa","year":"2017","journal-title":"Eur. J. Oper. Res."},{"key":"ref_38","doi-asserted-by":"crossref","first-page":"40","DOI":"10.1016\/j.cor.2015.11.012","article-title":"Split Algorithm in O(n) for the Capacitated Vehicle Routing Problem","volume":"69","author":"Vidal","year":"2016","journal-title":"Comput. Oper. Res."},{"key":"ref_39","unstructured":"Helsgaun, K. (2017). An Extension of the Lin-Kernighan-Helsgaun TSP Solver for Constrained Traveling Salesman and Vehicle Routing Problems, Roskilde University. Technical Report."},{"key":"ref_40","unstructured":"Bishop, C. (2021). Pattern Recognition and Machine Learning, Springer."},{"key":"ref_41","unstructured":"Murphy, K.P. (2012). Machine Learning: A Probabilistic Perspective, MIT Press."},{"key":"ref_42","doi-asserted-by":"crossref","unstructured":"Mu\u00f1oz-Herrera, S., and Suchan, K. (2021, December 20). Constrained Fitness Landscape Analysis of Vehicle Routing Problems. Available online: https:\/\/zenodo.org\/record\/5532805#.YcpuSJpBxPY.","DOI":"10.3390\/e24010053"},{"key":"ref_43","doi-asserted-by":"crossref","unstructured":"Davis, C.S. (2002). Statistical Methods for the Analysis of Repeated Measurements, Springer. Springer Texts in Statistics.","DOI":"10.1007\/b97287"},{"key":"ref_44","unstructured":"Jones, T. (1995). Evolutionary Algorithms, Fitness Landscapes and Search, Santa Fe Institute. Working Papers."},{"key":"ref_45","doi-asserted-by":"crossref","first-page":"309","DOI":"10.1057\/jors.1969.75","article-title":"An Algorithm for the Vehicle-Dispatching Problem","volume":"20","author":"Christofides","year":"1969","journal-title":"J. Oper. Res. Soc."}],"container-title":["Entropy"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1099-4300\/24\/1\/53\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T07:54:46Z","timestamp":1760169286000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1099-4300\/24\/1\/53"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,12,28]]},"references-count":45,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2022,1]]}},"alternative-id":["e24010053"],"URL":"https:\/\/doi.org\/10.3390\/e24010053","relation":{},"ISSN":["1099-4300"],"issn-type":[{"value":"1099-4300","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,12,28]]}}}