Though its origins can be traced back to 1977, the development and application of the metaheuristic Scatter Search (SS) has stayed dormant for 20 years. However, in the last 10 years, research interest has positioned SS as one of the recognizable methodologies within the umbrella of evolutionary search. This paper presents an application of SS to the problem of routing vehicles that are required both to deliver and pickup goods (VRPSDP). This specialized version of the vehicle routing problem is particularly relevant to organizations that are concerned with sustainable and environmentally-friendly business practices. In this work, the efficiency of SS is evaluated when applied to this problem. Computational results of the application to instances in the literature are presented.<\/p>","DOI":"10.4018\/jamc.2011040101","type":"journal-article","created":{"date-parts":[[2011,10,19]],"date-time":"2011-10-19T16:03:40Z","timestamp":1319040220000},"page":"1-20","source":"Crossref","is-referenced-by-count":10,"title":["Scatter Search Applied to the Vehicle Routing Problem with Simultaneous Delivery and Pickup"],"prefix":"10.4018","volume":"2","author":[{"given":"Gladys","family":"Maquera","sequence":"first","affiliation":[{"name":"Universidad Peruana Uni\u00f3n, Peru"}]},{"given":"Manuel","family":"Laguna","sequence":"additional","affiliation":[{"name":"University of Colorado, USA"}]},{"given":"Dan Abensur","family":"Gandelman","sequence":"additional","affiliation":[{"name":"Universidade Federal do Rio de Janeiro, Brasil"}]},{"given":"Annibal Parracho","family":"Sant\u2019Anna","sequence":"additional","affiliation":[{"name":"Universidade Federal Fluminense, Brasil"}]}],"member":"2432","reference":[{"key":"jamc.2011040101-0","volume":"Vol. 8","author":"M. O.Ball","year":"1995","journal-title":"Network routing: Handbooks in operations research and management science"},{"key":"jamc.2011040101-1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cor.2005.03.014"},{"key":"jamc.2011040101-2","first-page":"63","article-title":"Vehicle routing: Bridging the gap between theory and practice. Belgian Journal of Operations Research","volume":"35","author":"A. V.Breedam","year":"1995","journal-title":"Statistics and Computer Science"},{"key":"jamc.2011040101-3","doi-asserted-by":"publisher","DOI":"10.1023\/A:1012793906010"},{"key":"jamc.2011040101-4","first-page":"85","article-title":"Reverse logistics: A review of the literature and framework for future investigation.","volume":"19","author":"C.Carter","year":"1998","journal-title":"Journal of Business Logistics"},{"key":"jamc.2011040101-5","doi-asserted-by":"publisher","DOI":"10.1057\/palgrave.jors.2602028"},{"key":"jamc.2011040101-6","first-page":"315","article-title":"The vehicle routing problem","author":"N.Christofides","year":"1979","journal-title":"Combinatorial optimization"},{"key":"jamc.2011040101-7","doi-asserted-by":"publisher","DOI":"10.1057\/palgrave.jors.2601324"},{"key":"jamc.2011040101-8","doi-asserted-by":"publisher","DOI":"10.1057\/palgrave.jors.2601935"},{"key":"jamc.2011040101-9","doi-asserted-by":"publisher","DOI":"10.1007\/PL00013346"},{"key":"jamc.2011040101-10","first-page":"1","article-title":"Greedy randomized adaptive search procedures.","volume":"2","author":"T.Feo","year":"1995","journal-title":"Journal of Global Optimization"},{"key":"jamc.2011040101-11","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2008.02.025"},{"key":"jamc.2011040101-12","doi-asserted-by":"publisher","DOI":"10.1016\/0377-2217(90)90344-B"},{"key":"jamc.2011040101-13","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2006.01.037"},{"key":"jamc.2011040101-14","unstructured":"Gehring, H., & Homberger, J. (1999). A parallel hybrid evolutionary metaheuristic for the vehicle routing problem with time windows. In Proceedings of the EUROGEN Conference on Evolutionary Algorithms in Engineering and Computer Science (pp. 57-64)."},{"key":"jamc.2011040101-15","doi-asserted-by":"publisher","DOI":"10.1111\/j.1540-5915.1977.tb01074.x"},{"key":"jamc.2011040101-16","doi-asserted-by":"crossref","unstructured":"Glover, F. (1998). A template for scatter search and path relinking. In J. K. Hao, E. Lutton, E. Ronald, M. Schoenauer, & D. Snyers (Eds.), Proceedings of the Third European Conference on Artificial Evolution (LNCS 1363, pp. 3-54).","DOI":"10.1007\/BFb0026589"},{"key":"jamc.2011040101-17","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4615-0337-8","author":"M.Laguna","year":"2003","journal-title":"Scatter search: Methodology and implementations"},{"key":"jamc.2011040101-18","doi-asserted-by":"crossref","first-page":"2245","DOI":"10.1002\/j.1538-7305.1965.tb04146.x","article-title":"Computer solutions of the traveling salesman problem.","volume":"44","author":"S.Lin","year":"1965","journal-title":"The Bell System Technical Journal"},{"key":"jamc.2011040101-19","unstructured":"Maquera Sosa, N. G., Gandelman, D., & Sant'Anna, A. (2007). Log\u00edstica inversa y ruteo de veh\u00edculos: B\u00fasqueda dispersa aplicada al problema de ruteo de veh\u00edculos con colecta y entrega simultanea. In Proceedings of the 1er Congreso de Log\u00edstica y Gesti\u00f3n de la Cadena de Suministro."},{"key":"jamc.2011040101-20","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2004.08.004"},{"key":"jamc.2011040101-21","doi-asserted-by":"crossref","first-page":"377","DOI":"10.1016\/0191-2607(89)90085-X","article-title":"The multiple vehicle routing problem with simultaneous delivery and pickup points.","volume":"23A","author":"H.Min","year":"1989","journal-title":"Transportation Research"},{"key":"jamc.2011040101-22","doi-asserted-by":"publisher","DOI":"10.1016\/j.cor.2004.07.009"},{"key":"jamc.2011040101-23","doi-asserted-by":"publisher","DOI":"10.1016\/0377-2217(94)90360-3"},{"key":"jamc.2011040101-24","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2002.11.003"},{"key":"jamc.2011040101-25","doi-asserted-by":"publisher","DOI":"10.1016\/0377-2217(83)90099-1"},{"key":"jamc.2011040101-26","unstructured":"Rego, C. (2000). Scatter search for vehicle routing problem. Paper presented at the INFORMS National Meeting, Salt Lake City, UT."},{"key":"jamc.2011040101-27","doi-asserted-by":"publisher","DOI":"10.1007\/BF02430370"},{"key":"jamc.2011040101-28","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2004.08.018"},{"key":"jamc.2011040101-29","doi-asserted-by":"crossref","first-page":"1034","DOI":"10.1057\/palgrave.jors.2600808","article-title":"A cluster insertion heuristic for single and multiple depot vehicle routing problems with backhauling.","volume":"50","author":"S.Salhi","year":"1999","journal-title":"The Journal of the Operational Research Society"},{"key":"jamc.2011040101-30","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2004.08.014"},{"key":"jamc.2011040101-31","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2005.01.016"},{"key":"jamc.2011040101-32","doi-asserted-by":"publisher","DOI":"10.1287\/opre.35.2.254"},{"key":"jamc.2011040101-33","doi-asserted-by":"publisher","DOI":"10.1590\/S0101-74382007000200006"},{"key":"jamc.2011040101-34","doi-asserted-by":"crossref","DOI":"10.1137\/1.9780898718515","author":"P.Toth","year":"2002","journal-title":"The vehicle routing problem: SIAM monographs on discrete, mathematics and applications"},{"key":"jamc.2011040101-35","doi-asserted-by":"publisher","DOI":"10.1007\/s10878-007-9090-4"},{"key":"jamc.2011040101-36","doi-asserted-by":"publisher","DOI":"10.1016\/j.eswa.2007.11.005"}],"container-title":["International Journal of Applied Metaheuristic Computing"],"original-title":[],"language":"ng","link":[{"URL":"https:\/\/www.igi-global.com\/viewtitle.aspx?TitleId=55295","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,6,1]],"date-time":"2022-06-01T23:10:05Z","timestamp":1654125005000},"score":1,"resource":{"primary":{"URL":"https:\/\/services.igi-global.com\/resolvedoi\/resolve.aspx?doi=10.4018\/jamc.2011040101"}},"subtitle":[""],"short-title":[],"issued":{"date-parts":[[2011,4,1]]},"references-count":37,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2011,4]]}},"URL":"https:\/\/doi.org\/10.4018\/jamc.2011040101","relation":{},"ISSN":["1947-8283","1947-8291"],"issn-type":[{"value":"1947-8283","type":"print"},{"value":"1947-8291","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011,4,1]]}}}