{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,11]],"date-time":"2025-03-11T04:33:05Z","timestamp":1741667585964,"version":"3.38.0"},"reference-count":30,"publisher":"SAGE Publications","issue":"1-2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["HIS"],"published-print":{"date-parts":[[2022,5,31]]},"abstract":"<jats:p>The Hub Location Problems (HLP) have gathered great interest due to the complexity and to the many applications in industry such as aviation, public transportation, telecommunications, among others. The HLP have many variants regarding allocation (single or multiple) and capacity (uncapacitated or capacitated). This paper presents a variant of the HLP, encompassing single allocation with capacity constraints. The Capacitated Single Allocation p-Hub Location Problem (CSApHLP) objective consists on determine the set of p hubs in a network that minimizes the total cost of allocating all the non-hub nodes to the p hubs. In this work, it is proposed a sophisticated RAMP approach (PD-RAMP) to improve the results obtained previously by the simple version (Dual-RAMP). Thus, a parallel implementation is conducted to assess the effectiveness of a parallel RAMP model applied to the CSApHLP. The first algorithm, the sequential PD-RAMP, incorporates Dual-RAMP with a Scatter Search procedure to create a Primal-Dual RAMP approach. The second algorithm, the parallel PD-RAMP, also take advantage of the dual and primal, parallelizing the primal side of the problem and interconnecting both sides as it is expected in the RAMP sequential algorithm. The quality of the results carried out on a standard testbed shows that the PD-RAMP approach managed to improve the state-of-the-art algorithms for the CSApHLP.<\/jats:p>","DOI":"10.3233\/his-220003","type":"journal-article","created":{"date-parts":[[2022,4,26]],"date-time":"2022-04-26T17:19:51Z","timestamp":1650993591000},"page":"1-17","source":"Crossref","is-referenced-by-count":2,"title":["Primal-dual algorithms for the Capacitated Single Allocation p-Hub Location Problem"],"prefix":"10.1177","volume":"18","author":[{"given":"Telmo","family":"Matos","sequence":"first","affiliation":[]}],"member":"179","reference":[{"key":"10.3233\/HIS-220003_ref1","doi-asserted-by":"publisher","first-page":"393","DOI":"10.1016\/S0377-2217(87)80007-3","article-title":"A quadratic integer program for the location of interacting hub facilities","volume":"32","author":"O\u2019Kelly","year":"1987","journal-title":"Eur. J. Oper. Res"},{"key":"10.3233\/HIS-220003_ref2","doi-asserted-by":"publisher","first-page":"1096","DOI":"10.1016\/j.cie.2013.01.012","article-title":"Hub location problems: A review of models, classification, solution techniques, and applications","volume":"64","author":"Farahani","year":"2013","journal-title":"Comput. Ind. Eng"},{"key":"10.3233\/HIS-220003_ref3","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.ejor.2007.06.008","article-title":"Network hub location problems: The state of the art","volume":"190","author":"Alumur","year":"2008","journal-title":"Eur. J. Oper. Res"},{"key":"10.3233\/HIS-220003_ref4","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1016\/0966-6923(94)90032-9","article-title":"The hub network design problem: A review and synthesis","volume":"2","author":"O\u2019Kelly","year":"1994","journal-title":"J. Transp. Geogr"},{"key":"10.3233\/HIS-220003_ref5","doi-asserted-by":"publisher","first-page":"125","DOI":"10.1016\/S0966-8349(96)00015-0","article-title":"Hub network design with single and multiple allocation: A computational study","volume":"4","author":"O\u2019Kelly","year":"1996","journal-title":"Locat. Sci"},{"key":"10.3233\/HIS-220003_ref6","first-page":"31","article-title":"A survey of network hub location","volume":"6","author":"Campbell","year":"1994","journal-title":"Stud. Locat. Anal"},{"key":"10.3233\/HIS-220003_ref7","doi-asserted-by":"crossref","first-page":"139","DOI":"10.1016\/S0966-8349(96)00011-3","article-title":"Efficient algorithms for the uncapacitated single allocation p-hub median problem","volume":"4","author":"Ernst","year":"1996","journal-title":"Locat. Sci"},{"key":"10.3233\/HIS-220003_ref8","doi-asserted-by":"publisher","first-page":"100","DOI":"10.1016\/S0377-2217(96)00340-2","article-title":"Exact and heuristic algorithms for the uncapacitated multiple allocation p-hub median problem","volume":"104","author":"Ernst","year":"1998","journal-title":"Eur. J. Oper. Res"},{"key":"10.3233\/HIS-220003_ref9","doi-asserted-by":"crossref","first-page":"25","DOI":"10.1016\/0377-2217(91)90090-I","article-title":"Theory and methodology: Heuristics for the p-hub location problem","volume":"53","author":"Klincewicz","year":"1991","journal-title":"Eur. J. Oper. Res"},{"key":"10.3233\/HIS-220003_ref10","doi-asserted-by":"publisher","first-page":"923","DOI":"10.1287\/opre.44.6.923","article-title":"Hub location and the p-hub median problem","volume":"44","author":"Campbell","year":"1996","journal-title":"Oper. Res"},{"doi-asserted-by":"publisher","key":"10.3233\/HIS-220003_ref11","DOI":"10.1007\/978-3-030-13709-0_20"},{"doi-asserted-by":"publisher","key":"10.3233\/HIS-220003_ref12","DOI":"10.1007\/978-3-030-14347-3_32"},{"key":"10.3233\/HIS-220003_ref14","doi-asserted-by":"crossref","first-page":"109","DOI":"10.1007\/BF01096763","article-title":"Greedy randomized adaptive search procedures","volume":"134","author":"Feo","year":"1995","journal-title":"J. Glob. Optim"},{"key":"10.3233\/HIS-220003_ref16","doi-asserted-by":"publisher","first-page":"851","DOI":"10.11175\/easts.10.851","article-title":"Lagrangian relaxation for the capacitated single allocation p-hub median problem","volume":"10","author":"Ting","year":"2013","journal-title":"J. East. Asia Soc. Transp. Stud"},{"key":"10.3233\/HIS-220003_ref17","doi-asserted-by":"publisher","first-page":"483","DOI":"10.1007\/s00291-008-0159-y","article-title":"Lagrangean relaxation for the capacitated hub location problem with single assignment","volume":"31","author":"Contreras","year":"2009","journal-title":"OR Spectr"},{"key":"10.3233\/HIS-220003_ref18","doi-asserted-by":"publisher","first-page":"819","DOI":"10.11175\/easts.11.819","article-title":"Reactive GRASP for the capacitated single allocation p-hub median problem","volume":"11","author":"Ting","year":"2015","journal-title":"J. East. Asia Soc. Transp. Stud"},{"doi-asserted-by":"publisher","key":"10.3233\/HIS-220003_ref19","DOI":"10.1007\/978-3-030-96305-7_19"},{"key":"10.3233\/HIS-220003_ref21","first-page":"652","article-title":"Fundamentals of scatter search and path relinking","volume":"29","author":"Glover","year":"2000","journal-title":"Control Cybern"},{"doi-asserted-by":"publisher","key":"10.3233\/HIS-220003_ref22","DOI":"10.1007\/978-1-4615-6089-0"},{"doi-asserted-by":"publisher","key":"10.3233\/HIS-220003_ref23","DOI":"10.1007\/978-3-030-38629-0_20"},{"doi-asserted-by":"publisher","key":"10.3233\/HIS-220003_ref24","DOI":"10.1007\/s10472-021-09756-0"},{"doi-asserted-by":"publisher","key":"10.3233\/HIS-220003_ref25","DOI":"10.1007\/s10472-021-09757-z"},{"doi-asserted-by":"publisher","key":"10.3233\/HIS-220003_ref26","DOI":"10.1007\/978-3-030-38629-0_14"},{"key":"10.3233\/HIS-220003_ref27","doi-asserted-by":"publisher","first-page":"325","DOI":"10.1016\/S0377-2217(99)00260-X","article-title":"New trends in exact algorithms for the 0\u20131 knapsack problem","volume":"123","author":"Martello","year":"2000","journal-title":"Eur. J. Oper. Res"},{"key":"10.3233\/HIS-220003_ref28","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/978-1-4615-0337-8","article-title":"Scatter search: Methodology and implementations in C","volume":"24","author":"Laguna","year":"2003","journal-title":"Oper. Res. Comput. Sci. Interfaces Ser"},{"doi-asserted-by":"publisher","key":"10.3233\/HIS-220003_ref29","DOI":"10.1007\/0-306-48056-5_17"},{"doi-asserted-by":"publisher","key":"10.3233\/HIS-220003_ref30","DOI":"10.1002\/0471739383"},{"key":"10.3233\/HIS-220003_ref32","doi-asserted-by":"publisher","first-page":"1278","DOI":"10.1109\/TLA.2017.7959347","article-title":"A parallel heuristics for the single allocation hub location problem","volume":"15","author":"de Carvalho","year":"2017","journal-title":"IEEE Lat. Am. Trans"},{"key":"10.3233\/HIS-220003_ref34","doi-asserted-by":"crossref","first-page":"1069","DOI":"10.1057\/jors.1990.166","article-title":"OR-Library: Distributing test problems by electronic mail","volume":"65","author":"Beasley","year":"1990","journal-title":"J. Oper. Res. Soc"},{"key":"10.3233\/HIS-220003_ref35","doi-asserted-by":"publisher","first-page":"141","DOI":"10.1023\/A:1018994432663","article-title":"Solution algorithms for the capacitated single allocation hub location problem","volume":"86","author":"Ernst","year":"1999","journal-title":"Ann. Oper. Res"}],"container-title":["International Journal of Hybrid Intelligent Systems"],"original-title":[],"link":[{"URL":"https:\/\/content.iospress.com\/download?id=10.3233\/HIS-220003","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,10]],"date-time":"2025-03-10T20:54:00Z","timestamp":1741640040000},"score":1,"resource":{"primary":{"URL":"https:\/\/journals.sagepub.com\/doi\/full\/10.3233\/HIS-220003"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,5,31]]},"references-count":30,"journal-issue":{"issue":"1-2"},"URL":"https:\/\/doi.org\/10.3233\/his-220003","relation":{},"ISSN":["1448-5869","1875-8819"],"issn-type":[{"type":"print","value":"1448-5869"},{"type":"electronic","value":"1875-8819"}],"subject":[],"published":{"date-parts":[[2022,5,31]]}}}