{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,4]],"date-time":"2026-06-04T14:33:24Z","timestamp":1780583604931,"version":"3.54.1"},"reference-count":40,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2020,2,3]],"date-time":"2020-02-03T00:00:00Z","timestamp":1580688000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2020,2,3]],"date-time":"2020-02-03T00:00:00Z","timestamp":1580688000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Cloud Comp"],"published-print":{"date-parts":[[2020,12]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>A novel parallelization method of genetic algorithm (GA) solution of the Traveling Salesman Problem (TSP) is presented. The proposed method can considerably accelerate the solution of the equivalent TSP of many complex vehicle routing problems (VRPs) in the cloud implementation of intelligent transportation systems. The solution provides routing information besides all the services required by the autonomous vehicles in vehicular clouds. GA is considered as an important class of evolutionary algorithms that can solve optimization problems in growing intelligent transport systems. But, to meet time criteria in time-constrained problems of intelligent transportation systems like routing and controlling the autonomous vehicles, a highly parallelizable GA is needed. The proposed method parallelizes the GA by designing three concurrent kernels, each of which running some dependent effective operators of GA. It can be straightforwardly adapted to run on many-core and multi-core processors. To best use the valuable resources of such processors in parallel execution of the GA, threads that run any of the triple kernels are synchronized by a low-cost switching mechanism. The proposed method was experimented for parallelizing a GA-based solution of TSP over multi-core and many-core systems. The results confirm the efficiency of the proposed method for parallelizing GAs on many-core as well as on multi-core systems.<\/jats:p>","DOI":"10.1186\/s13677-020-0157-4","type":"journal-article","created":{"date-parts":[[2020,2,3]],"date-time":"2020-02-03T16:03:42Z","timestamp":1580745822000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":101,"title":["An efficient parallel genetic algorithm solution for vehicle routing problem in cloud implementation of the intelligent transportation systems"],"prefix":"10.1186","volume":"9","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-5373-5778","authenticated-orcid":false,"given":"Mahdi","family":"Abbasi","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Milad","family":"Rafiee","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Mohammad R.","family":"Khosravi","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Alireza","family":"Jolfaei","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Varun G.","family":"Menon","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Javad Mokhtari","family":"Koushyar","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2020,2,3]]},"reference":[{"key":"157_CR1","doi-asserted-by":"publisher","first-page":"87","DOI":"10.1016\/j.tre.2019.04.004","volume":"126","author":"J Wu","year":"2019","unstructured":"Wu J, Zhou L, Du Z, Lv Y (2019) Mixed steepest descent algorithm for the traveling salesman problem and application in air logistics. Transport Res Part E Logistic Transport Rev 126:87\u2013102","journal-title":"Transport Res Part E Logistic Transport Rev"},{"key":"157_CR2","unstructured":"Menon VG, Prathap J (2018) Vehicular fog computing: challenges applications and future directions. In: fog computing: breakthroughs in research and practice. IGI global, pp 220-229"},{"key":"157_CR3","doi-asserted-by":"crossref","unstructured":"Vidal T, Laporte G, Matl P (2019) A concise guide to existing and emerging vehicle routing problem variants. Eur J Oper Res","DOI":"10.1016\/j.ejor.2019.10.010"},{"key":"157_CR4","doi-asserted-by":"crossref","unstructured":"Vu DM, Hewitt M, Boland N, Savelsbergh M (2019) Dynamic discretization discovery for solving the time-dependent traveling salesman problem with time windows. Transp Sci","DOI":"10.1287\/trsc.2019.0911"},{"issue":"1","key":"157_CR5","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1186\/s13677-019-0147-6","volume":"8","author":"B Li","year":"2019","unstructured":"Li B, Peng Z, Hou P, He M, Anisetti M, Jeon G (2019) Reliability and capability based computation offloading strategy for vehicular ad hoc clouds. J Cloud Comput 8(1):21. https:\/\/doi.org\/10.1186\/s13677-019-0147-6","journal-title":"J Cloud Comput"},{"key":"157_CR6","doi-asserted-by":"publisher","first-page":"325","DOI":"10.1016\/j.jnca.2013.08.004","volume":"40","author":"M Whaiduzzaman","year":"2014","unstructured":"Whaiduzzaman M, Sookhak M, Gani A, Buyya R (2014) A survey on vehicular cloud computing. J Netw Comput Appl 40:325\u2013344","journal-title":"J Netw Comput Appl"},{"key":"157_CR7","unstructured":"Mistareehi H, Manivannan D (2019) Classification, challenges and critical comparison of proposed solutions for vehicular clouds. Int J Next Gen Comput 10(1)"},{"key":"157_CR8","doi-asserted-by":"crossref","unstructured":"Ahmed ZE, Saeed RA, Mukherjee A (2019) Challenges and opportunities in vehicular cloud computing. In: cloud security: concepts, methodologies, tools, and applications. IGI global, pp 2168-2185","DOI":"10.4018\/978-1-5225-8176-5.ch106"},{"key":"157_CR9","volume-title":"The data-driven time-dependent traveling salesperson problem","author":"E Avraham","year":"2019","unstructured":"Avraham E, Raviv T (2019) The data-driven time-dependent traveling salesperson problem"},{"key":"157_CR10","unstructured":"Giap CN, Ha DT Parallel genetic algorithm for minimum dominating set problem. In: Computing, Management and Telecommunications (ComManTel), 2014 International Conference on, 2014. IEEE, pp 165\u2013169"},{"key":"157_CR11","doi-asserted-by":"crossref","unstructured":"Jain DK, Jacob S, Alzubi J, Menon V (2019) An efficient and adaptable multimedia system for converting PAL to VGA in real-time video processing. J Real-Time Image Proc:1\u201313","DOI":"10.1007\/s11554-019-00889-4"},{"issue":"3","key":"157_CR12","doi-asserted-by":"publisher","first-page":"149","DOI":"10.1007\/s11626-018-00317-0","volume":"55","author":"S Munroe","year":"2019","unstructured":"Munroe S, Sandoval K, Martens DE, Sipkema D, Pomponi SA (2019) Genetic algorithm as an optimization tool for the development of sponge cell culture media. In Vitro Cell Dev Biol Anim 55(3):149\u2013158","journal-title":"In Vitro Cell Dev Biol Anim"},{"key":"157_CR13","unstructured":"Yasmin S (2019) Linear colour image processing in Hypercomplex algebra guided by genetic algorithms. Dissertaion, University of Essex"},{"issue":"3","key":"157_CR14","doi-asserted-by":"publisher","first-page":"371","DOI":"10.1007\/s40313-019-00454-1","volume":"30","author":"AA Lima","year":"2019","unstructured":"Lima AA, de Barros FK, Yoshizumi VH, Spatti DH, Dajer ME (2019) Optimized artificial neural network for biosignals classification using genetic algorithm. J Control Autom Electric Syst 30(3):371\u2013379","journal-title":"J Control Autom Electric Syst"},{"issue":"21","key":"157_CR15","doi-asserted-by":"publisher","first-page":"7281","DOI":"10.1007\/s00500-017-2729-x","volume":"22","author":"MH Arif","year":"2018","unstructured":"Arif MH, Li J, Iqbal M, Liu K (2018) Sentiment analysis and spam detection in short informal text using learning classifier systems. Soft Comput 22(21):7281\u20137291","journal-title":"Soft Comput"},{"key":"157_CR16","doi-asserted-by":"crossref","unstructured":"Zhu J, Li Q Application of Hybrid MPI+ TBB Parallel Programming Model for Traveling Salesman Problem. In: Green Computing and Communications (GreenCom), 2013 IEEE and Internet of Things (iThings\/CPSCom), IEEE International Conference on and IEEE Cyber, Physical and Social Computing, 2013. IEEE, pp 2164\u20132167","DOI":"10.1109\/GreenCom-iThings-CPSCom.2013.408"},{"key":"157_CR17","doi-asserted-by":"crossref","unstructured":"Fujimoto N, Tsutsui S A highly-parallel TSP solver for a GPU computing platform. In: International Conference on Numerical Methods and Applications, 2010. Springer, pp 264\u2013271","DOI":"10.1007\/978-3-642-18466-6_31"},{"key":"157_CR18","doi-asserted-by":"crossref","unstructured":"Chen S, Davis S, Jiang H, Novobilski A (2011) CUDA-based genetic algorithm on traveling salesman problem. In: computer and information science 2011. Springer, pp 241-252","DOI":"10.1007\/978-3-642-21378-6_19"},{"key":"157_CR19","unstructured":"S\u00e1nchez LNG, Armenta JJT, Ram\u00edrez VHD (2015) Parallel genetic algorithms on a GPU to solve the travelling salesman problem. Difu100ci@ Revista en Ingenier\u00eda y Tecnolog\u00eda, UAZ 8 (2)"},{"issue":"11","key":"157_CR20","doi-asserted-by":"publisher","first-page":"4399","DOI":"10.1007\/s11227-016-1748-1","volume":"72","author":"S Kang","year":"2016","unstructured":"Kang S, Kim S-S, Won J, Kang Y-M (2016) GPU-based parallel genetic approach to large-scale travelling salesman problem. J Supercomput 72(11):4399\u20134414","journal-title":"J Supercomput"},{"key":"157_CR21","doi-asserted-by":"crossref","unstructured":"Moumen Y, Abdoun O, Daanoun A Parallel approach for genetic algorithm to solve the Asymmetric Traveling Salesman Problems. In: Proceedings of the 2nd International Conference on Computing and Wireless Communication Systems, 2017. ACM, p 24","DOI":"10.1145\/3167486.3167510"},{"key":"157_CR22","doi-asserted-by":"crossref","unstructured":"Cekmez U, Ozsiginan M, Sahingoz OK Adapting the GA approach to solve Traveling Salesman Problems on CUDA architecture. In: Computational Intelligence and Informatics (CINTI), 2013 IEEE 14th International Symposium on, 2013. IEEE, pp 423\u2013428","DOI":"10.1109\/CINTI.2013.6705234"},{"key":"157_CR23","doi-asserted-by":"publisher","first-page":"65","DOI":"10.1016\/j.procs.2017.09.009","volume":"114","author":"D Radford","year":"2017","unstructured":"Radford D, Calvert D (2017) A comparative analysis of the performance of scalable parallel patterns applied to genetic algorithms and configured for NVIDIA GPUs. Procedia Comput Sci 114:65\u201372","journal-title":"Procedia Comput Sci"},{"issue":"7","key":"157_CR24","first-page":"168781401770741","volume":"9","author":"C-C Li","year":"2017","unstructured":"Li C-C, Lin C-H, Liu J-C (2017) Parallel genetic algorithms on the graphics processing units using island model and simulated annealing. Adv Mech Eng 9(7):1687814017707413","journal-title":"Adv Mech Eng"},{"issue":"3","key":"157_CR25","doi-asserted-by":"publisher","first-page":"2387","DOI":"10.3233\/JIFS-169950","volume":"36","author":"R Saxena","year":"2019","unstructured":"Saxena R, Jain M, Sharma D, Jaidka S (2019) A review on VANET routing protocols and proposing a parallelized genetic algorithm based heuristic modification to mobicast routing for real time message passing. J Intell Fuzzy Systems 36(3):2387\u20132398","journal-title":"J Intell Fuzzy Systems"},{"key":"157_CR26","unstructured":"NVIDIA. NVIDIA CUDA (Compute Unified Device Architecture) Programming Guide, (accessed September 2019) http:\/\/docs.nvidia.com\/cuda\/pdf\/CUDA_C_Programming_Guide.pdf. Accessed 1 Sept 2019"},{"key":"157_CR27","doi-asserted-by":"crossref","unstructured":"Abbasi M, Rafiee M (2019) A calibrated asymptotic framework for analyzing packet classification algorithms on GPUs. The Journal of Supercomputing:1\u201338","DOI":"10.1007\/s11227-019-02861-2"},{"issue":"1","key":"157_CR28","first-page":"48","volume":"30","author":"S Jam","year":"2017","unstructured":"Jam S, Shahbahrami A, Ziyabari S (2017) Parallel implementation of particle swarm optimization variants using graphics processing unit platform. Int J Eng Trans A Basic 30(1):48\u201356","journal-title":"Int J Eng Trans A Basic"},{"key":"157_CR29","doi-asserted-by":"publisher","DOI":"10.7717\/peerj-cs.185","volume":"5","author":"M Abbasi","year":"2019","unstructured":"Abbasi M, Tahouri R, Rafiee M (2019) Enhancing the performance of the aggregated bit vector algorithm in network packet classification using GPU. Peer J Comput Sci 5:e185","journal-title":"Peer J Comput Sci"},{"key":"157_CR30","doi-asserted-by":"crossref","unstructured":"Yip CM, Asaduzzaman A A promising CUDA-accelerated vehicular area network simulator using NS-3. In: Performance Computing and Communications Conference (IPCCC), 2014 IEEE International, 2014. IEEE, pp 1\u20132","DOI":"10.1109\/PCCC.2014.7017048"},{"key":"157_CR31","unstructured":"Intel T (2018) Intel Threading Building Blocks. Available: http:\/\/threadingbuildingblocks.org\/. Accessed 16 Mar 2019"},{"issue":"2","key":"157_CR32","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1007\/s11042-011-0906-y","volume":"68","author":"CG Kim","year":"2014","unstructured":"Kim CG, Kim JG, Lee DH (2014) Optimizing image processing on multi-core CPUs with Intel parallel programming technologies. Multimed Tools Appl 68(2):237\u2013251","journal-title":"Multimed Tools Appl"},{"key":"157_CR33","doi-asserted-by":"crossref","unstructured":"Hougardy S, Wilde M (2014) On the nearest neighbor rule for the metric traveling salesman problem. Discret Appl Math","DOI":"10.1016\/j.dam.2014.03.012"},{"key":"157_CR34","doi-asserted-by":"publisher","first-page":"22","DOI":"10.1016\/j.cor.2014.10.012","volume":"56","author":"C Groba","year":"2015","unstructured":"Groba C, Sartal A, V\u00e1zquez XH (2015) Solving the dynamic traveling salesman problem using a genetic algorithm with trajectory prediction: an application to fish aggregating devices. Comput Oper Res 56:22\u201332","journal-title":"Comput Oper Res"},{"key":"157_CR35","unstructured":"Hussain A, Muhammad YS (2019) Trade-off between exploration and exploitation with genetic algorithm using a novel selection operator. Complex Intell Syst:1\u201314"},{"issue":"9","key":"157_CR36","doi-asserted-by":"publisher","first-page":"e0137724","DOI":"10.1371\/journal.pone.0137724","volume":"10","author":"C Contreras-Bolton","year":"2015","unstructured":"Contreras-Bolton C, Parada V (2015) Automatic combination of operators in a genetic algorithm to solve the traveling salesman problem. PLoS One 10(9):e0137724\u2013e0137724. https:\/\/doi.org\/10.1371\/journal.pone.0137724","journal-title":"PLoS One"},{"issue":"2","key":"157_CR37","doi-asserted-by":"publisher","first-page":"148","DOI":"10.1109\/MCOM.2014.6736756","volume":"52","author":"E Lee","year":"2014","unstructured":"Lee E, Lee E-K, Gerla M, Oh SY (2014) Vehicular cloud networking: architecture and design principles. IEEE Commun Mag 52(2):148\u2013155","journal-title":"IEEE Commun Mag"},{"key":"157_CR38","unstructured":"VLSI TSP Collection, September 2019, [online] Available:. http:\/\/www.math.uwaterloo.ca\/tsp\/vlsi\/index.html. Accessed 2 Feb 2018"},{"key":"157_CR39","doi-asserted-by":"crossref","unstructured":"Jaros J Multi-GPU island-based genetic algorithm for solving the knapsack problem. In: Evolutionary Computation (CEC), 2012 IEEE congress on, 2012. IEEE, pp 1\u20138","DOI":"10.1109\/CEC.2012.6256131"},{"key":"157_CR40","doi-asserted-by":"publisher","first-page":"8","DOI":"10.1016\/j.cpc.2018.10.003","volume":"236","author":"F Orts","year":"2019","unstructured":"Orts F, Ortega G, Garz\u00f3n EM, Puertas A (2019) Finite size effects in active microrheology in colloids. Comput Phys Commun 236:8\u201314","journal-title":"Comput Phys Commun"}],"container-title":["Journal of Cloud Computing"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1186\/s13677-020-0157-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1186\/s13677-020-0157-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1186\/s13677-020-0157-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,2,25]],"date-time":"2021-02-25T18:36:44Z","timestamp":1614278204000},"score":1,"resource":{"primary":{"URL":"https:\/\/journalofcloudcomputing.springeropen.com\/articles\/10.1186\/s13677-020-0157-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,2,3]]},"references-count":40,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2020,12]]}},"alternative-id":["157"],"URL":"https:\/\/doi.org\/10.1186\/s13677-020-0157-4","relation":{},"ISSN":["2192-113X"],"issn-type":[{"value":"2192-113X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,2,3]]},"assertion":[{"value":"30 November 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"22 January 2020","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"3 February 2020","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"The authors declare that they have no competing interests.","order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing interests"}}],"article-number":"6"}}