{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,26]],"date-time":"2026-03-26T04:27:27Z","timestamp":1774499247073,"version":"3.50.1"},"reference-count":49,"publisher":"MDPI AG","issue":"4","license":[{"start":{"date-parts":[[2020,4,16]],"date-time":"2020-04-16T00:00:00Z","timestamp":1586995200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>This paper presents a hybrid grasshopper optimization algorithm using a novel decoder and local search to solve instances of the open vehicle routing problem with capacity and distance constraints. The algorithm\u2019s decoder first defines the number of vehicles to be used and then it partitions the clients, assigning them to the available routes. The algorithm performs a local search in three neighborhoods after decoding. When a new best solution is found, every route is locally optimized by solving a traveling salesman problem, considering the depot and clients in the route. Three sets containing a total of 30 benchmark problems from the literature were used to test the algorithm. The experiments considered two cases of the problem. In the first, the primary objective is to minimize the total number of vehicles and then the total distance to be traveled. In the second case, the total distance traveled by the vehicles is minimized. The obtained results showed the algorithm\u2019s proficient performance. For the first case, the algorithm was able to improve or match the best-known solutions for 21 of the 30 benchmark problems. For the second case, the best-known solutions for 18 of the 30 benchmark problems were found or improved by the algorithm. Finally, a case study from a real-life problem is included.<\/jats:p>","DOI":"10.3390\/a13040096","type":"journal-article","created":{"date-parts":[[2020,4,16]],"date-time":"2020-04-16T13:01:39Z","timestamp":1587042099000},"page":"96","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":19,"title":["A Hybrid Grasshopper Optimization Algorithm Applied to the Open Vehicle Routing Problem"],"prefix":"10.3390","volume":"13","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-8171-8994","authenticated-orcid":false,"given":"Valeria","family":"Soto-Mendoza","sequence":"first","affiliation":[{"name":"Centro de Investigaci\u00f3n en Matem\u00e1ticas Aplicadas, Universidad Aut\u00f3noma de Coahuila Edificio \u201cS\u201d Camporredondo, Saltillo, Coahuila 25280, Mexico"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0609-4223","authenticated-orcid":false,"given":"Irma","family":"Garc\u00eda-Calvillo","sequence":"additional","affiliation":[{"name":"Centro de Investigaci\u00f3n en Matem\u00e1ticas Aplicadas, Universidad Aut\u00f3noma de Coahuila Edificio \u201cS\u201d Camporredondo, Saltillo, Coahuila 25280, Mexico"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1625-7084","authenticated-orcid":false,"given":"Efra\u00edn","family":"Ruiz-y-Ruiz","sequence":"additional","affiliation":[{"name":"Divisi\u00f3n de Estudios de Posgrado e Investigaci\u00f3n, Tecnol\u00f3gico Nacional de M\u00e9xico\/Instituto Tecnol\u00f3gico de Saltillo. Blvd. Venustiano Carranza 2400, Saltillo, Coahuila 25280, Mexico"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jaime","family":"P\u00e9rez-Terrazas","sequence":"additional","affiliation":[{"name":"Divisi\u00f3n de Estudios de Posgrado e Investigaci\u00f3n, Tecnol\u00f3gico Nacional de M\u00e9xico\/Instituto Tecnol\u00f3gico de Saltillo. Blvd. Venustiano Carranza 2400, Saltillo, Coahuila 25280, Mexico"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2020,4,16]]},"reference":[{"key":"ref_1","unstructured":"Kennedy, J., and Eberhat, R. (December, January 27). Particle swarm optimization. Proceedings of the IEEE international conference on neural networks, Perth, WA, Australia."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"29","DOI":"10.1109\/3477.484436","article-title":"Ant system: Optimization by a colony of cooperating agents","volume":"26","author":"Dorigo","year":"1996","journal-title":"IEEE Trans. Syst. Man Cybern. Part B (Cybern.)"},{"key":"ref_3","unstructured":"Holland, J.H. (1975). Adaptation in Natural and Artificial Systems, University of Michigan Press."},{"key":"ref_4","unstructured":"Karaboga, D. (2020, March 20). An Idea Based on Honey Bee Swarm for Numerical Optimization. Available online: https:\/\/pdfs.semanticscholar.org\/015d\/f4d97ed1f541752842c49d12e429a785460b.pdf."},{"key":"ref_5","doi-asserted-by":"crossref","unstructured":"Glover, F., and Laguna, M. (1998). Tabu search. Handbook of Combinatorial Optimization, Springer.","DOI":"10.1007\/978-1-4615-6089-0"},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"1097","DOI":"10.1016\/S0305-0548(97)00031-2","article-title":"Variable neighborhood search","volume":"24","author":"Hansen","year":"1997","journal-title":"Comput. Oper. Res."},{"key":"ref_7","unstructured":"Pham, D., Ghanbarzadeh, A., Koc, E., Otri, S., Rahim, S., and Zaidi, M. (2005). The Bees Algorithm Technical Note, Manufacturing Engineering Centre, Cardiff University."},{"key":"ref_8","unstructured":"Filho, C.J.A.B., de Lima Neto, F.B., Lins, A.J.C.C., Nascimento, A.I.S., and Lima, M.P. (2008, January 12\u201315). A novel search algorithm based on fish school behavior. Proceedings of the IEEE International Conference on Systems, Man and Cybernetics, SMC 2008, Singapore."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"429","DOI":"10.1007\/s00521-012-0939-9","article-title":"Swallow swarm optimization algorithm: A new method to optimization","volume":"23","author":"Neshat","year":"2013","journal-title":"Neural Comput. Appl."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"40","DOI":"10.1016\/j.compstruc.2014.07.012","article-title":"An efficient hybrid Particle Swarm and Swallow Swarm Optimization algorithm","volume":"143","author":"Kaveh","year":"2014","journal-title":"Comput. Struct."},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"30","DOI":"10.1016\/j.advengsoft.2017.01.004","article-title":"Grasshopper Optimisation Algorithm: Theory and application","volume":"105","author":"Saremi","year":"2017","journal-title":"Adv. Eng. Softw."},{"key":"ref_12","first-page":"65","article-title":"A New Metaheuristic Bat-Inspired Algorithm","volume":"284","author":"Yang","year":"2010","journal-title":"Nat. Inspired Coop. Strateg. Optim."},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"51","DOI":"10.1016\/j.advengsoft.2016.01.008","article-title":"The whale optimization algorithm","volume":"95","author":"Mirjalili","year":"2016","journal-title":"Adv. Eng. Softw."},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"141","DOI":"10.3390\/a12070141","article-title":"OPTIMUS: Self-Adaptive Differential Evolution with Ensemble of Mutation Strategies for Grasshopper Algorithmic Modeling","volume":"12","author":"Cubukcuoglu","year":"2019","journal-title":"Algorithms"},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"25","DOI":"10.1016\/j.knosys.2017.12.037","article-title":"Evolutionary population dynamics and grasshopper optimization approaches for feature selection problems","volume":"145","author":"Mafarja","year":"2018","journal-title":"Knowl.-Based Syst."},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"497","DOI":"10.1016\/j.ast.2017.08.037","article-title":"Distributed trajectory optimization for multiple solar-powered UAVs target tracking in urban environment by Adaptive Grasshopper Optimization Algorithm","volume":"70","author":"Wu","year":"2017","journal-title":"Aerosp. Sci. Technol."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"58","DOI":"10.1016\/j.ymssp.2017.11.029","article-title":"A parameter-adaptive VMD method based on grasshopper optimization algorithm to analyze vibration signals from rotating machinery","volume":"108","author":"Zhang","year":"2018","journal-title":"Mech. Syst. Signal Process."},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"710","DOI":"10.1016\/j.energy.2017.12.156","article-title":"A regional hybrid GOA-SVM model based on similar day approach for short-term load forecasting in Assam, India","volume":"145","author":"Barman","year":"2018","journal-title":"Energy"},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"80","DOI":"10.1287\/mnsc.6.1.80","article-title":"The truck dispatching problem","volume":"6","author":"Dantzig","year":"1959","journal-title":"Manag. Sci."},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"650","DOI":"10.1016\/j.ejor.2006.12.065","article-title":"A general vehicle routing problem","volume":"191","author":"Goel","year":"2008","journal-title":"Eur. J. Oper. Res."},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"414","DOI":"10.6036\/5561","article-title":"Siatema inteligente de planificaci\u00f3n de rutas para la distribuci\u00f3n de mercancias\u00edas basado en las t\u00e9cnicas metaheur\u00edsticas, b\u00fasqueda de entorno variable y b\u00fasqueda tab\u00fa","volume":"88","author":"Sicilia","year":"2013","journal-title":"DYNA"},{"key":"ref_22","unstructured":"Sicilia, J.A., Royo-Agustin, B., Quemada-Mayoral, C., Olivares-Colay, M.J., and Larrod\u00e9, E. (2015). A decision support system to long haul freight transportation by means of ant colony optimization. Transp. Syst. Technol."},{"key":"ref_23","doi-asserted-by":"crossref","unstructured":"Cassettari, L., Demartini, M., Mosca, R., Revetria, R., and Tonelli, F. (2018). A multi-stage algorithm for a capacitated vehicle routing problem with time constraints. Algorithms, 11.","DOI":"10.3390\/a11050069"},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"468","DOI":"10.1016\/j.cam.2015.03.050","article-title":"An optimization algorithm for solving the rich vehicle routing problem based on Variable Neighborhood Search and Tabu Search metaheuristics","volume":"291","author":"Sicilia","year":"2016","journal-title":"J. Comput. Appl. Math."},{"key":"ref_25","doi-asserted-by":"crossref","unstructured":"Nepomuceno, N., Barboza Saboia, R., and Rog\u00e9rio Pinheiro, P. (2019). A Fast Randomized Algorithm for the Heterogeneous Vehicle Routing Problem with Simultaneous Pickup and Delivery. Algorithms, 12.","DOI":"10.3390\/a12080158"},{"key":"ref_26","doi-asserted-by":"crossref","unstructured":"Ait Haddadene, S.R., Labadie, N., and Prodhon, C. (2019). Bicriteria Vehicle Routing Problem with Preferences and Timing Constraints in Home Health Care Services. Algorithms, 12.","DOI":"10.3390\/a12080152"},{"key":"ref_27","doi-asserted-by":"crossref","unstructured":"Zhao, M., and Lu, Y. (2019). A heuristic approach for a real-world electric vehicle routing problem. Algorithms, 12.","DOI":"10.3390\/a12020045"},{"key":"ref_28","doi-asserted-by":"crossref","unstructured":"Ju\u00e1rez P\u00e9rez, M.A., P\u00e9rez Loaiza, R.E., Flores, Q., Malaquias, P., Atriano Ponce, O., and Flores Peralta, C. (2019). A Heuristic Algorithm for the Routing and Scheduling Problem with Time Windows: A Case Study of the Automotive Industry in Mexico. Algorithms, 12.","DOI":"10.3390\/a12050111"},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"633","DOI":"10.3923\/jas.2013.633.638","article-title":"Harmony search algorithm for time-dependent vehicle routing problem with time windows","volume":"13","author":"Liang","year":"2013","journal-title":"J. Appl. Sci."},{"key":"ref_30","doi-asserted-by":"crossref","first-page":"564","DOI":"10.1057\/palgrave.jors.2600924","article-title":"A heuristic method for the open vehicle routing problem","volume":"51","author":"Sariklis","year":"2000","journal-title":"J. Oper. Res. Soc."},{"key":"ref_31","doi-asserted-by":"crossref","first-page":"229","DOI":"10.1002\/net.3230110212","article-title":"Formulation and structure of more complex\/realistic routing and scheduling problems","volume":"11","author":"Schrage","year":"1981","journal-title":"Networks"},{"key":"ref_32","doi-asserted-by":"crossref","first-page":"552","DOI":"10.1016\/S0377-2217(03)00238-8","article-title":"A tabu search algorithm for the open vehicle routing problem","volume":"157","year":"2004","journal-title":"Eur. J. Oper. Res."},{"key":"ref_33","doi-asserted-by":"crossref","first-page":"588","DOI":"10.1057\/palgrave.jors.2601848","article-title":"Solving the open vehicle routeing problem via a single parameter metaheuristic algorithm","volume":"56","author":"Tarantilis","year":"2005","journal-title":"J. Oper. Res. Soc."},{"key":"ref_34","doi-asserted-by":"crossref","first-page":"803","DOI":"10.1016\/j.ejor.2007.06.064","article-title":"A variable neighbourhood search algorithm for the open vehicle routing problem","volume":"195","author":"Fleszar","year":"2009","journal-title":"Eur. J. Oper. Res."},{"key":"ref_35","doi-asserted-by":"crossref","first-page":"2918","DOI":"10.1016\/j.cor.2005.11.018","article-title":"The open vehicle routing problem: Algorithms, large-scale test problems, and computational results","volume":"34","author":"Li","year":"2007","journal-title":"Comput. Oper. Res."},{"key":"ref_36","doi-asserted-by":"crossref","first-page":"443","DOI":"10.1016\/j.cor.2008.11.003","article-title":"A hybrid evolution strategy for the open vehicle routing problem","volume":"37","author":"Repoussis","year":"2010","journal-title":"Comput. Oper. Res."},{"key":"ref_37","doi-asserted-by":"crossref","first-page":"80","DOI":"10.1016\/j.swevo.2013.12.003","article-title":"A Bumble Bees Mating Optimization algorithm for the Open Vehicle Routing Problem","volume":"15","author":"Marinakis","year":"2014","journal-title":"Swarm Evol. Comput."},{"key":"ref_38","doi-asserted-by":"crossref","first-page":"712","DOI":"10.1016\/j.cor.2009.06.021","article-title":"An open vehicle routing problem metaheuristic for examining wide solution neighborhoods","volume":"37","author":"Zachariadis","year":"2010","journal-title":"Comput. Oper. Res."},{"key":"ref_39","doi-asserted-by":"crossref","first-page":"2106","DOI":"10.1016\/j.cor.2010.02.010","article-title":"An ILP improvement procedure for the open vehicle routing problem","volume":"37","author":"Salari","year":"2010","journal-title":"Comput. Oper. Res."},{"key":"ref_40","doi-asserted-by":"crossref","first-page":"267","DOI":"10.1057\/palgrave.jors.2601817","article-title":"A new tabu search heuristic for the open vehicle routing problem","volume":"56","author":"Fu","year":"2005","journal-title":"J. Oper. Res. Soc."},{"key":"ref_41","doi-asserted-by":"crossref","first-page":"326","DOI":"10.1145\/321043.321046","article-title":"Integer programming formulation of traveling salesman problems","volume":"7","author":"Miller","year":"1960","journal-title":"J. ACM (JACM)"},{"key":"ref_42","unstructured":"Ruiz-y Ruiz, E., and Soto-Mendoza, V. (2017). A GRASP Algorithm for the Open Vehicle Routing Problem, Instituto Tecnol\u00f3gico de Saltillo. Technical Report."},{"key":"ref_43","doi-asserted-by":"crossref","first-page":"207","DOI":"10.1016\/j.cie.2019.05.002","article-title":"Solving the Open Vehicle Routing Problem with Capacity and Distance Constraints with a Biased Random Key Genetic Algorithm","volume":"133","author":"Ruiz","year":"2019","journal-title":"Comput. Ind. Eng."},{"key":"ref_44","doi-asserted-by":"crossref","unstructured":"Marinakis, Y., and Marinaki, M. (2011). A honey bees mating optimization algorithm for the open vehicle routing problem. 2011 Genetic and Evolutionary Computation Conference, Taylor and Francis.","DOI":"10.1145\/2001576.2001591"},{"key":"ref_45","doi-asserted-by":"crossref","first-page":"2403","DOI":"10.1016\/j.cor.2005.09.012","article-title":"A general heuristic for vehicle routing problems","volume":"34","author":"Pisinger","year":"2007","journal-title":"Comput. Oper. Res."},{"key":"ref_46","doi-asserted-by":"crossref","first-page":"1012","DOI":"10.1057\/palgrave.jors.2602644","article-title":"An ant colony optimization metaheuristic hybridized with tabu search for open vehicle routing problems","volume":"60","author":"Li","year":"2009","journal-title":"J. Oper. Res. Soc."},{"key":"ref_47","doi-asserted-by":"crossref","unstructured":"Marinakis, Y., and Marinaki, M. (2012). A hybrid particle swarm optimization algorithm for the open vehicle routing problem. International Conference on Swarm Intelligence, Springer.","DOI":"10.1007\/978-3-642-32650-9_16"},{"key":"ref_48","doi-asserted-by":"crossref","unstructured":"Ruiz-y Ruiz, E., and Ruiz-Barbosa, A. (2019). A Cutting Plane Algorithm for the Open Vehicle Routing Problem with Capacity and Distance Constraints, Instituto Tecnol\u00f3gico de Saltillo. Technical Report.","DOI":"10.1016\/j.cie.2019.05.002"},{"key":"ref_49","doi-asserted-by":"crossref","first-page":"1642","DOI":"10.1057\/palgrave.jors.2602345","article-title":"A branch-and-cut algorithm for the capacitated open vehicle routing problem","volume":"58","author":"Letchford","year":"2007","journal-title":"J. Oper. Res. Soc."}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/13\/4\/96\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,13]],"date-time":"2025-10-13T14:09:14Z","timestamp":1760364554000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/13\/4\/96"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,4,16]]},"references-count":49,"journal-issue":{"issue":"4","published-online":{"date-parts":[[2020,4]]}},"alternative-id":["a13040096"],"URL":"https:\/\/doi.org\/10.3390\/a13040096","relation":{},"ISSN":["1999-4893"],"issn-type":[{"value":"1999-4893","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,4,16]]}}}