{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,10]],"date-time":"2026-06-10T15:44:01Z","timestamp":1781106241642,"version":"3.54.1"},"reference-count":24,"publisher":"IGI Global Scientific Publishing","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2011,4,1]]},"abstract":"<p>Scatter search (SS) and path relinking (PR) are evolutionary methods that have been successfully applied to a wide range of hard optimization problems. The fundamental concepts and principles of the methods were first proposed in the 1970s and 1980s, and were based on formulations, dating back to the 1960s, for combining decision rules and problem constraints. The methods use strategies for search diversification and intensification that have proved effective in a variety of optimization problems and that have sometimes been embedded in other evolutionary methods to yield improved performance. This paper examines the scatter search and path relinking methodologies from both conceptual and practical points of view, and identifies certain connections between their strategies and those adopted more recently by particle swarm optimization. The authors describe key elements of the SS &amp; PR approaches and apply them to a hard combinatorial optimization problem: the minimum linear arrangement problem, which has been used in applications of structural engineering, VLSI and software testing.<\/p>","DOI":"10.4018\/jsir.2011040101","type":"journal-article","created":{"date-parts":[[2011,10,19]],"date-time":"2011-10-19T12:51:03Z","timestamp":1319028663000},"page":"1-21","source":"Crossref","is-referenced-by-count":13,"title":["Scatter Search and Path Relinking"],"prefix":"10.4018","volume":"2","author":[{"given":"Rafael","family":"Mart\u00ed","sequence":"first","affiliation":[{"name":"Universidad de Valencia, Spain"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Juan-Jos\u00e9","family":"Pantrigo","sequence":"additional","affiliation":[{"name":"Universidad Rey Juan Carlos, Spain"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Abraham","family":"Duarte","sequence":"additional","affiliation":[{"name":"Universidad Rey Juan Carlos, Spain"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Vicente","family":"Campos","sequence":"additional","affiliation":[{"name":"Universidad de Valencia, Spain"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Fred","family":"Glover","sequence":"additional","affiliation":[{"name":"OptTek Systems, Inc., USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"2432","reference":[{"key":"jsir.2011040101-0","doi-asserted-by":"publisher","DOI":"10.1137\/0125042"},{"key":"jsir.2011040101-1","author":"M. R.Garey","year":"1979","journal-title":"Computers and intractability: A guide to the theory of completeness"},{"key":"jsir.2011040101-2","doi-asserted-by":"publisher","DOI":"10.1111\/j.1540-5915.1977.tb01074.x"},{"key":"jsir.2011040101-3","author":"F.Glover","year":"1982","journal-title":"Ejection chains, reference structures and alternating path methods"},{"key":"jsir.2011040101-4","doi-asserted-by":"crossref","unstructured":"Glover, F. (1989). Tabu search - Part I. ORSA Journal on Computing, 1(3) 190-206.","DOI":"10.1287\/ijoc.1.3.190"},{"key":"jsir.2011040101-5","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(94)00037-E"},{"key":"jsir.2011040101-6","unstructured":"Glover, F. (1997). A template for scatter search and path relinking. In J.-K. Hao, E. Lutton, E. Ronald, M. Schoenauer, & D. Snyers (Eds.), Proceedings of the Conference on Artificial Evolution (LNCS 1363, pp. 13-54)."},{"key":"jsir.2011040101-7","first-page":"71","article-title":"Tabu search","author":"F.Glover","year":"1993","journal-title":"Modern heuristic techniques for combinatorial problems"},{"key":"jsir.2011040101-8","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4615-6089-0","author":"F.Glover","year":"1997","journal-title":"Tabu search"},{"key":"jsir.2011040101-9","doi-asserted-by":"publisher","DOI":"10.1137\/0112012"},{"key":"jsir.2011040101-10","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(92)90229-4"},{"key":"jsir.2011040101-11","doi-asserted-by":"publisher","DOI":"10.1109\/ICNN.1995.488968"},{"key":"jsir.2011040101-12","doi-asserted-by":"publisher","DOI":"10.1126\/science.220.4598.671"},{"key":"jsir.2011040101-13","doi-asserted-by":"publisher","DOI":"10.1287\/ijoc.11.1.44"},{"key":"jsir.2011040101-14","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4615-0337-8","author":"M.Laguna","year":"2003","journal-title":"Scatter search: Methodology and implementations in C"},{"key":"jsir.2011040101-15","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2004.08.003"},{"key":"jsir.2011040101-16","doi-asserted-by":"publisher","DOI":"10.1016\/S0377-2217(00)00325-8"},{"key":"jsir.2011040101-17","unstructured":"McAllister, A. J. (1999). A new heuristic algorithm for the linear arrangement problem (Tech. Rep. No. TR-99-126a). New Brunswick, CA: University of New Brunswick."},{"key":"jsir.2011040101-18","doi-asserted-by":"publisher","DOI":"10.1142\/S0129626403001161"},{"key":"jsir.2011040101-19","doi-asserted-by":"crossref","unstructured":"Petit, J. (2003b). Experiments on the minimum linear arrangement problem. ACM Journal of Experimental Algorithmics, 8.","DOI":"10.1145\/996546.996554"},{"key":"jsir.2011040101-20","doi-asserted-by":"publisher","DOI":"10.1016\/S0377-2217(02)00715-4"},{"key":"jsir.2011040101-21","doi-asserted-by":"crossref","first-page":"219","DOI":"10.1007\/0-306-48056-5_8","article-title":"Greedy randomized adaptive search procedures","author":"M. G. C.Resende","year":"2003","journal-title":"Handbook of metaheuristic"},{"key":"jsir.2011040101-22","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4419-1665-5_4"},{"key":"jsir.2011040101-23","doi-asserted-by":"publisher","DOI":"10.1016\/j.cor.2007.03.001"}],"container-title":["International Journal of Swarm Intelligence Research"],"original-title":[],"language":"ng","link":[{"URL":"https:\/\/www.igi-global.com\/viewtitle.aspx?TitleId=55317","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,6,1]],"date-time":"2022-06-01T17:06:18Z","timestamp":1654103178000},"score":1,"resource":{"primary":{"URL":"https:\/\/services.igi-global.com\/resolvedoi\/resolve.aspx?doi=10.4018\/jsir.2011040101"}},"subtitle":["A Tutorial on the Linear Arrangement Problem"],"short-title":[],"issued":{"date-parts":[[2011,4,1]]},"references-count":24,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2011,4]]}},"URL":"https:\/\/doi.org\/10.4018\/jsir.2011040101","relation":{},"ISSN":["1947-9263","1947-9271"],"issn-type":[{"value":"1947-9263","type":"print"},{"value":"1947-9271","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011,4,1]]}}}