{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,14]],"date-time":"2026-10-14T01:26:02Z","timestamp":1791941162668,"version":"4.3.4"},"reference-count":58,"publisher":"MDPI AG","issue":"3","license":[{"start":{"date-parts":[[2018,3,15]],"date-time":"2018-03-15T00:00:00Z","timestamp":1521072000000},"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>The classical capacitated vehicle routing problem (CVRP) is a very popular combinatorial optimization problem in the field of logistics and supply chain management. Although CVRP has drawn interests of many researchers, no standard way has been established yet to obtain best known solutions for all the different problem sets. We propose an efficient algorithm Bilayer Local Search-based Particle Swarm Optimization (BLS-PSO) along with a novel decoding method to solve CVRP. Decoding method is important to relate the encoded particle position to a feasible CVRP solution. In bilayer local search, one layer of local search is for the whole population in any iteration whereas another one is applied only on the pool of the best particles generated in different generations. Such searching strategies help the BLS-PSO to perform better than the existing proposals by obtaining best known solutions for most of the existing benchmark problems within very reasonable computational time. Computational results also show that the performance achieved by the proposed algorithm outperforms other PSO-based approaches.<\/jats:p>","DOI":"10.3390\/a11030031","type":"journal-article","created":{"date-parts":[[2018,3,15]],"date-time":"2018-03-15T16:07:17Z","timestamp":1521130037000},"page":"31","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":14,"title":["Bilayer Local Search Enhanced Particle Swarm Optimization for the Capacitated Vehicle Routing Problem"],"prefix":"10.3390","volume":"11","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-4185-4518","authenticated-orcid":false,"given":"A.","family":"Ahmed","sequence":"first","affiliation":[{"name":"Department of Industrial and Management Engineering, Hankuk University of Foreign Studies, Yongin 17035, Korea"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6586-9116","authenticated-orcid":false,"given":"Ji","family":"Sun","sequence":"additional","affiliation":[{"name":"Department of Industrial and Management Engineering, Hankuk University of Foreign Studies, Yongin 17035, Korea"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"1968","published-online":{"date-parts":[[2018,3,15]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"4245","DOI":"10.1016\/j.eswa.2014.01.005","article-title":"Green logistic vehicle routing problem: Routing light delivery vehicles in urban areas using a neuro-fuzzy model","volume":"41","year":"2014","journal-title":"Expert Syst. Appl."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"235","DOI":"10.1287\/trsc.1050.0118","article-title":"A branch-and-price approach to the vehicle routing problem with simultaneous distribution and collection","volume":"40","author":"Righini","year":"2006","journal-title":"Transp. Sci."},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"100","DOI":"10.1016\/j.tre.2011.08.001","article-title":"A green vehicle routing problem","volume":"48","year":"2012","journal-title":"Transp. Res. Part E"},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"1775","DOI":"10.1016\/j.cor.2011.02.007","article-title":"The capacitated vehicle routing problem with stochastic demands and time windows","volume":"38","author":"Lei","year":"2011","journal-title":"Comput. Oper. Res."},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"1419","DOI":"10.1016\/j.cor.2011.08.013","article-title":"Development of a fuel consumption optimization model for the capacitated vehicle routing problem","volume":"39","author":"Xiao","year":"2012","journal-title":"Comput. Oper. Res."},{"key":"ref_6","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_7","doi-asserted-by":"crossref","first-page":"221","DOI":"10.1002\/net.3230110211","article-title":"Complexity of vehicle routing and scheduling problems","volume":"11","author":"Lenstra","year":"1981","journal-title":"Networks"},{"key":"ref_8","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_9","doi-asserted-by":"crossref","first-page":"568","DOI":"10.1287\/opre.12.4.568","article-title":"Scheduling of vehicles from a central depot to a number of delivery points","volume":"12","author":"Clarke","year":"1964","journal-title":"Oper. Res."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"281","DOI":"10.1057\/jors.1967.44","article-title":"Bases for vehicle fleet scheduling","volume":"18","author":"Gaskell","year":"1967","journal-title":"J. Oper. Res. Soc."},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"503","DOI":"10.1057\/jors.1976.95","article-title":"A sequential route-building algorithm employing a generalised savings criterion","volume":"27","author":"Mole","year":"1976","journal-title":"J. Oper. Res. Soc."},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"336","DOI":"10.1016\/0377-2217(88)90154-3","article-title":"The savings algorithm for the vehicle routing problem","volume":"34","author":"Paessens","year":"1988","journal-title":"Eur. J. Oper. Res."},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"109","DOI":"10.1002\/net.3230110205","article-title":"A generalized assignment heuristic for vehicle routing","volume":"11","author":"Fisher","year":"1981","journal-title":"Networks"},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"340","DOI":"10.1287\/opre.22.2.340","article-title":"A heuristic algorithm for the vehicle-dispatch problem","volume":"22","author":"Gillett","year":"1974","journal-title":"Oper. Res."},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"403","DOI":"10.1016\/0305-0483(83)90033-6","article-title":"Route first\u2014Cluster second methods for vehicle routing","volume":"11","author":"Beasley","year":"1983","journal-title":"Omega"},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"95","DOI":"10.1023\/A:1022602019183","article-title":"Genetic Algorithms in Search, Optimization, and Machine Learning","volume":"3","author":"Goldberg","year":"1988","journal-title":"Mach. Learn."},{"key":"ref_17","doi-asserted-by":"crossref","unstructured":"Berger, J., and Barkaoui, M. (2003, January 12\u201316). A hybrid genetic algorithm for the capacitated vehicle routing problem. Proceedings of the Conference on Genetic and Evolutionary Computation, Chicago, IL, USA.","DOI":"10.1007\/3-540-45105-6_80"},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"190","DOI":"10.1287\/ijoc.1.3.190","article-title":"Tabu search\u2014Part I","volume":"1","author":"Glover","year":"1989","journal-title":"ORSA J. Comput."},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"4","DOI":"10.1287\/ijoc.2.1.4","article-title":"Tabu search\u2014Part II","volume":"2","author":"Glover","year":"1990","journal-title":"ORSA J. Comput."},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"333","DOI":"10.1287\/ijoc.15.4.333.24890","article-title":"The granular tabu search and its application to the vehicle-routing problem","volume":"15","author":"Toth","year":"2003","journal-title":"Informs J. Comput."},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"671","DOI":"10.1126\/science.220.4598.671","article-title":"Optimization by simulated annealing","volume":"220","author":"Kirkpatrick","year":"1983","journal-title":"Science"},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"1505","DOI":"10.1016\/j.eswa.2007.11.060","article-title":"Applying hybrid meta-heuristics for capacitated vehicle routing problem","volume":"36","author":"Lin","year":"2009","journal-title":"Expert Syst. Appl."},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"787","DOI":"10.1016\/S0305-0548(02)00051-5","article-title":"A genetic algorithm for the vehicle routing problem","volume":"30","author":"Baker","year":"2003","journal-title":"Comput. Oper. Res."},{"key":"ref_24","doi-asserted-by":"crossref","unstructured":"Carwalo, T., Thankappan, J., and Patil, V. (2017, January 7\u20138). Capacitated vehicle routing problem. Proceedings of the 2nd International IEEE Conference on Communication Systems, Computing and IT Applications (CSCITA), Mumbai, India.","DOI":"10.1109\/CSCITA.2017.8066555"},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"129","DOI":"10.1287\/opre.48.1.129.12455","article-title":"A tabu search heuristic for the capacitated arc routing problem","volume":"48","author":"Hertz","year":"2000","journal-title":"Oper. Res."},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"354","DOI":"10.1016\/j.ins.2015.11.036","article-title":"Enhanced intelligent water drops and cuckoo search algorithms for solving the capacitated vehicle routing problem","volume":"334","author":"Teymourian","year":"2016","journal-title":"Inf. Sci."},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"171","DOI":"10.1016\/j.ejor.2008.02.028","article-title":"An improved ant colony optimization for vehicle routing problem","volume":"196","author":"Yu","year":"2009","journal-title":"Eur. J. Oper. Res."},{"key":"ref_28","doi-asserted-by":"crossref","unstructured":"Blum, C., and Merkle, D. (2008). Swarm Intelligence. Swarm Intelligence in Optimization, Springer.","DOI":"10.1007\/978-3-540-74089-6"},{"key":"ref_29","unstructured":"Hu, X., Eberhart, R.C., and Shi, Y. (2003, January 26). Swarm intelligence for permutation optimization: A case study of n-queens problem. Proceedings of the IEEE Swarm Intelligence Symposium, Indianapolis, IN, USA."},{"key":"ref_30","doi-asserted-by":"crossref","first-page":"1446","DOI":"10.1016\/j.eswa.2009.06.085","article-title":"A hybrid genetic\u2013Particle Swarm Optimization Algorithm for the vehicle routing problem","volume":"37","author":"Marinakis","year":"2010","journal-title":"Expert Syst. Appl."},{"key":"ref_31","doi-asserted-by":"crossref","first-page":"1620","DOI":"10.1016\/j.eswa.2009.06.047","article-title":"Iterated variable neighborhood descent algorithm for the capacitated vehicle routing problem","volume":"37","author":"Chen","year":"2010","journal-title":"Expert Syst. Appl."},{"key":"ref_32","doi-asserted-by":"crossref","first-page":"2743","DOI":"10.1016\/j.cor.2005.10.010","article-title":"An efficient variable neighborhood search heuristic for very large scale vehicle routing problems","volume":"34","author":"Nuortio","year":"2007","journal-title":"Comput. Oper. Res."},{"key":"ref_33","doi-asserted-by":"crossref","first-page":"181","DOI":"10.1016\/j.endm.2004.06.029","article-title":"An ant colony algorithm for the capacitated vehicle routing","volume":"18","author":"Mazzeo","year":"2004","journal-title":"Electron. Notes Discret. Math."},{"key":"ref_34","doi-asserted-by":"crossref","first-page":"2110","DOI":"10.1016\/j.apm.2011.08.010","article-title":"Optimised crossover genetic algorithm for capacitated vehicle routing problem","volume":"36","author":"Nazif","year":"2012","journal-title":"Appl. Math. Model."},{"key":"ref_35","doi-asserted-by":"crossref","first-page":"1877","DOI":"10.1016\/j.cor.2009.06.014","article-title":"An effective memetic algorithm for the cumulative capacitated vehicle routing problem","volume":"37","author":"Ngueveu","year":"2010","journal-title":"Comput. Oper. Res."},{"key":"ref_36","doi-asserted-by":"crossref","first-page":"126","DOI":"10.1016\/j.ejor.2011.06.006","article-title":"An artificial bee colony algorithm for the capacitated vehicle routing problem","volume":"215","author":"Szeto","year":"2011","journal-title":"Eur. J. Oper. Res."},{"key":"ref_37","doi-asserted-by":"crossref","first-page":"255","DOI":"10.1007\/978-3-319-26245-1_12","article-title":"A hybrid bat algorithm with path relinking for the capacitated vehicle routing problem","volume":"Volume 7","author":"Zhou","year":"2016","journal-title":"Metaheuristics and Optimization in Civil Engineering"},{"key":"ref_38","doi-asserted-by":"crossref","first-page":"467","DOI":"10.1007\/s11047-007-9049-5","article-title":"A review of particle swarm optimization. Part I: Background and development","volume":"6","author":"Banks","year":"2007","journal-title":"Nat. Comput."},{"key":"ref_39","doi-asserted-by":"crossref","first-page":"109","DOI":"10.1007\/s11047-007-9050-z","article-title":"A review of particle swarm optimization. Part II: Hybridisation, combinatorial, multicriteria and constrained optimization, and indicative applications","volume":"7","author":"Banks","year":"2008","journal-title":"Nat. Comput."},{"key":"ref_40","unstructured":"Eberhart, R.C., and Kennedy, J. (December, January 27). Particle swarm optimization. Proceedings of the IEEE International Conference on Neural Network, Perth, Australia."},{"key":"ref_41","doi-asserted-by":"crossref","first-page":"607","DOI":"10.1631\/jzus.2006.A0607","article-title":"Hybrid discrete particle swarm optimization algorithm for capacitated vehicle routing problem","volume":"7","author":"Chen","year":"2006","journal-title":"J. Zhejiang Univ.-Sci. A"},{"key":"ref_42","unstructured":"Yang, S., and Wang, M. (2004, January 19\u201323). A quantum particle swarm optimization. Proceedings of the Congress on Evolutionary Computation, Portland, OR, USA."},{"key":"ref_43","unstructured":"Kao, Y., and Chen, M. (2011, January 24\u201326). A Hybrid PSO Algorithm for the CVRP Problem. Proceedings of the IJCCI (ECTA-FCTA), Paris, France."},{"key":"ref_44","doi-asserted-by":"crossref","first-page":"380","DOI":"10.1016\/j.cie.2008.06.012","article-title":"Particle swarm optimization and two solution representations for solving the capacitated vehicle routing problem","volume":"56","author":"Ai","year":"2009","journal-title":"Comput. Ind. Eng."},{"key":"ref_45","unstructured":"Pongchairerks, C., and Kachitvichyanukul, V. (2005, January 17\u201319). A non-homogenous particle swarm optimization with multiple social structures. Proceedings of the International Conference on Simulation and Modeling, Nakorn Pathom, Thailand."},{"key":"ref_46","first-page":"50","article-title":"A particle swarm optimization for the capacitated vehicle routing problem","volume":"2","author":"Ai","year":"2007","journal-title":"Int. J. Logist. SCM Syst."},{"key":"ref_47","doi-asserted-by":"crossref","first-page":"463","DOI":"10.1016\/j.engappai.2010.02.002","article-title":"A hybrid particle swarm optimization algorithm for the vehicle routing problem","volume":"23","author":"Marinakis","year":"2010","journal-title":"Eng. Appl. Artif. Intell."},{"key":"ref_48","doi-asserted-by":"crossref","first-page":"134","DOI":"10.1007\/s10878-007-9104-2","article-title":"Multiple phase neighborhood Search\u2013GRASP based on Lagrangean relaxation, random backtracking Lin\u2013Kernighan and path relinking for the TSP","volume":"17","author":"Marinakis","year":"2009","journal-title":"J. Comb. Optim."},{"key":"ref_49","doi-asserted-by":"crossref","first-page":"231","DOI":"10.1007\/s10589-005-4798-5","article-title":"Expanding neighborhood GRASP for the traveling salesman problem","volume":"32","author":"Marinakis","year":"2005","journal-title":"Comput. Optim. Appl."},{"key":"ref_50","doi-asserted-by":"crossref","first-page":"311","DOI":"10.1007\/s10878-005-4921-7","article-title":"A Hybrid Genetic\u2013GRASP Algorithm Using Lagrangean Relaxation for the Traveling Salesman Problem","volume":"10","author":"Marinakis","year":"2005","journal-title":"J. Comb. Optim."},{"key":"ref_51","doi-asserted-by":"crossref","unstructured":"Glover, F., Laguna, M., and Marti, R. (2003). Scatter Search and Path Relinking: Advances and Applications. Handbook of Metaheuristics, Springer.","DOI":"10.1007\/978-3-642-18965-4_20"},{"key":"ref_52","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1155\/2012\/726564","article-title":"A hybrid algorithm based on ACO and PSO for capacitated vehicle routing problems","volume":"2012","author":"Kao","year":"2012","journal-title":"Math. Probl. Eng."},{"key":"ref_53","unstructured":"Shi, Y., and Eberhart, R.C. (1998, January 4\u20139). A modified particle swarm optimizer. Proceedings of the IEEE International Conference on Evolutionary Computation, Anchorage, AK, USA."},{"key":"ref_54","unstructured":"Wang, K.P., Huang, L., Zhou, C.G., and Pang, W. (2003, January 5). Particle swarm optimization for traveling salesman problem. Proceedings of the IEEE International Conference on Machine Learning and Cybernetics, Xi\u2019an, China."},{"key":"ref_55","unstructured":"Augerat, P., Belenguer, J., Benavent, E., Corber\u00e1n, A., Naddef, D., and Rinaldi, G. (1995). Computational Results with a Branch and Cut Code for the Capacitated Vehicle Routing Problem, Universit\u00e9 Joseph Fourier. Technical report 949-M."},{"key":"ref_56","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":"Oper. Res. Q."},{"key":"ref_57","unstructured":"Christofides, N., Mingozzi, A., and Toth, P. (1979). The Vehicle Routing Problem. Combinatorial Optimization, Wiley Interscience."},{"key":"ref_58","first-page":"221","article-title":"Velocity Tentative PSO: An Optimal Velocity Implementation based Particle Swarm Optimization to Solve Traveling Salesman Problem","volume":"42","author":"Akhand","year":"2015","journal-title":"Prod. Plan. Control"}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/11\/3\/31\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T14:57:17Z","timestamp":1760194637000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/11\/3\/31"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,3,15]]},"references-count":58,"journal-issue":{"issue":"3","published-online":{"date-parts":[[2018,3]]}},"alternative-id":["a11030031"],"URL":"https:\/\/doi.org\/10.3390\/a11030031","relation":{},"ISSN":["1999-4893"],"issn-type":[{"value":"1999-4893","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,3,15]]}}}