Enhancing Kernel Search with Pattern Recognition: the Single-Source Capacitated Facility Location Problem Article Swipe
Bakker, Hannah
,
Guastaroba, Gianfranco
,
Nickel, Stefan
,
Speranza, M. Grazia
·
YOU?
·
· 2025
· Open Access
·
YOU?
·
· 2025
· Open Access
·
We introduce Pattern-based Kernel Search (PaKS), a two-phase matheuristic for the solution of the Single-Source Capacitated Facility Location Problem (SSCFLP). In the first phase, PaKS employs a pattern recognition technique to identify an implicit spatial separation of potential locations and customers into subsets, called regions, within which location and assignment decisions are strongly interdependent. In the second phase, PaKS employs an enhanced Kernel Search (KS) heuristic that leverages the interdependencies among the decision variables identified in the first phase. On a set of 112 benchmark instances, consisting of up to 1,000 locations and 1,000 customers, computational results show that PaKS consistently outperforms both a standard KS implementation and the current state-of-the-art heuristic for solving the SSCFLP, as well as CPLEX when run with a time limit. For these instances, PaKS achieved an average gap compared to the best known solution of 0.02%. Experimental results conducted on a large set of new very large test problems, comprising up to 2,000 locations and 2,000 customers, demonstrate that PaKS outperforms both the standard KS heuristic and CPLEX in terms of quality of the solution found, finding the largest number of best solutions, and achieving the smallest average gap.
Related Topics
Concepts
Kernel (algebra)
Benchmark (surveying)
Heuristic
Set (abstract data type)
Computer science
Mathematical optimization
Facility location problem
Quality (philosophy)
Test case
Algorithm
Kernel density estimation
Kernel method
Variable neighborhood search
Data mining
Local search (optimization)
Test set
Resource (disambiguation)
Mathematics
Metadata
- Type
- article
- Landing Page
- http://arxiv.org/abs/2512.08576
- https://arxiv.org/pdf/2512.08576
- OA Status
- green
- OpenAlex ID
- https://openalex.org/W7114820943
All OpenAlex metadata
Raw OpenAlex JSON
- OpenAlex ID
-
https://openalex.org/W7114820943Canonical identifier for this work in OpenAlex
- Title
-
Enhancing Kernel Search with Pattern Recognition: the Single-Source Capacitated Facility Location ProblemWork title
- Type
-
articleOpenAlex work type
- Publication year
-
2025Year of publication
- Publication date
-
2025-12-09Full publication date if available
- Authors
-
Bakker, Hannah, Guastaroba, Gianfranco, Nickel, Stefan, Speranza, M. GraziaList of authors in order
- Landing page
-
https://arxiv.org/abs/2512.08576Publisher landing page
- PDF URL
-
https://arxiv.org/pdf/2512.08576Direct link to full text PDF
- Open access
-
YesWhether a free full text is available
- OA status
-
greenOpen access status per OpenAlex
- OA URL
-
https://arxiv.org/pdf/2512.08576Direct OA link when available
- Concepts
-
Kernel (algebra), Benchmark (surveying), Heuristic, Set (abstract data type), Computer science, Mathematical optimization, Facility location problem, Quality (philosophy), Test case, Algorithm, Kernel density estimation, Kernel method, Variable neighborhood search, Data mining, Local search (optimization), Test set, Resource (disambiguation), MathematicsTop concepts (fields/topics) attached by OpenAlex
- Cited by
-
0Total citation count in OpenAlex
Full payload
| id | https://openalex.org/W7114820943 |
|---|---|
| doi | |
| ids.openalex | https://openalex.org/W7114820943 |
| fwci | 0.0 |
| type | article |
| title | Enhancing Kernel Search with Pattern Recognition: the Single-Source Capacitated Facility Location Problem |
| biblio.issue | |
| biblio.volume | |
| biblio.last_page | |
| biblio.first_page | |
| topics[0].id | https://openalex.org/T11502 |
| topics[0].field.id | https://openalex.org/fields/14 |
| topics[0].field.display_name | Business, Management and Accounting |
| topics[0].score | 0.8814742565155029 |
| topics[0].domain.id | https://openalex.org/domains/2 |
| topics[0].domain.display_name | Social Sciences |
| topics[0].subfield.id | https://openalex.org/subfields/1407 |
| topics[0].subfield.display_name | Organizational Behavior and Human Resource Management |
| topics[0].display_name | Facility Location and Emergency Management |
| topics[1].id | https://openalex.org/T10567 |
| topics[1].field.id | https://openalex.org/fields/22 |
| topics[1].field.display_name | Engineering |
| topics[1].score | 0.08430660516023636 |
| topics[1].domain.id | https://openalex.org/domains/3 |
| topics[1].domain.display_name | Physical Sciences |
| topics[1].subfield.id | https://openalex.org/subfields/2209 |
| topics[1].subfield.display_name | Industrial and Manufacturing Engineering |
| topics[1].display_name | Vehicle Routing Optimization Methods |
| topics[2].id | https://openalex.org/T11814 |
| topics[2].field.id | https://openalex.org/fields/22 |
| topics[2].field.display_name | Engineering |
| topics[2].score | 0.003521046368405223 |
| topics[2].domain.id | https://openalex.org/domains/3 |
| topics[2].domain.display_name | Physical Sciences |
| topics[2].subfield.id | https://openalex.org/subfields/2209 |
| topics[2].subfield.display_name | Industrial and Manufacturing Engineering |
| topics[2].display_name | Advanced Manufacturing and Logistics Optimization |
| is_xpac | False |
| apc_list | |
| apc_paid | |
| concepts[0].id | https://openalex.org/C74193536 |
| concepts[0].level | 2 |
| concepts[0].score | 0.6926611065864563 |
| concepts[0].wikidata | https://www.wikidata.org/wiki/Q574844 |
| concepts[0].display_name | Kernel (algebra) |
| concepts[1].id | https://openalex.org/C185798385 |
| concepts[1].level | 2 |
| concepts[1].score | 0.6882950067520142 |
| concepts[1].wikidata | https://www.wikidata.org/wiki/Q1161707 |
| concepts[1].display_name | Benchmark (surveying) |
| concepts[2].id | https://openalex.org/C173801870 |
| concepts[2].level | 2 |
| concepts[2].score | 0.6478341221809387 |
| concepts[2].wikidata | https://www.wikidata.org/wiki/Q201413 |
| concepts[2].display_name | Heuristic |
| concepts[3].id | https://openalex.org/C177264268 |
| concepts[3].level | 2 |
| concepts[3].score | 0.602584958076477 |
| concepts[3].wikidata | https://www.wikidata.org/wiki/Q1514741 |
| concepts[3].display_name | Set (abstract data type) |
| concepts[4].id | https://openalex.org/C41008148 |
| concepts[4].level | 0 |
| concepts[4].score | 0.5700903534889221 |
| concepts[4].wikidata | https://www.wikidata.org/wiki/Q21198 |
| concepts[4].display_name | Computer science |
| concepts[5].id | https://openalex.org/C126255220 |
| concepts[5].level | 1 |
| concepts[5].score | 0.5115529894828796 |
| concepts[5].wikidata | https://www.wikidata.org/wiki/Q141495 |
| concepts[5].display_name | Mathematical optimization |
| concepts[6].id | https://openalex.org/C108005400 |
| concepts[6].level | 2 |
| concepts[6].score | 0.49042248725891113 |
| concepts[6].wikidata | https://www.wikidata.org/wiki/Q1305598 |
| concepts[6].display_name | Facility location problem |
| concepts[7].id | https://openalex.org/C2779530757 |
| concepts[7].level | 2 |
| concepts[7].score | 0.3381395936012268 |
| concepts[7].wikidata | https://www.wikidata.org/wiki/Q1207505 |
| concepts[7].display_name | Quality (philosophy) |
| concepts[8].id | https://openalex.org/C128942645 |
| concepts[8].level | 3 |
| concepts[8].score | 0.33058878779411316 |
| concepts[8].wikidata | https://www.wikidata.org/wiki/Q1568346 |
| concepts[8].display_name | Test case |
| concepts[9].id | https://openalex.org/C11413529 |
| concepts[9].level | 1 |
| concepts[9].score | 0.30190569162368774 |
| concepts[9].wikidata | https://www.wikidata.org/wiki/Q8366 |
| concepts[9].display_name | Algorithm |
| concepts[10].id | https://openalex.org/C71134354 |
| concepts[10].level | 3 |
| concepts[10].score | 0.29095861315727234 |
| concepts[10].wikidata | https://www.wikidata.org/wiki/Q458825 |
| concepts[10].display_name | Kernel density estimation |
| concepts[11].id | https://openalex.org/C122280245 |
| concepts[11].level | 3 |
| concepts[11].score | 0.2803824245929718 |
| concepts[11].wikidata | https://www.wikidata.org/wiki/Q620622 |
| concepts[11].display_name | Kernel method |
| concepts[12].id | https://openalex.org/C2776435737 |
| concepts[12].level | 3 |
| concepts[12].score | 0.2705672085285187 |
| concepts[12].wikidata | https://www.wikidata.org/wiki/Q7915703 |
| concepts[12].display_name | Variable neighborhood search |
| concepts[13].id | https://openalex.org/C124101348 |
| concepts[13].level | 1 |
| concepts[13].score | 0.2691284716129303 |
| concepts[13].wikidata | https://www.wikidata.org/wiki/Q172491 |
| concepts[13].display_name | Data mining |
| concepts[14].id | https://openalex.org/C135320971 |
| concepts[14].level | 2 |
| concepts[14].score | 0.26302340626716614 |
| concepts[14].wikidata | https://www.wikidata.org/wiki/Q1868524 |
| concepts[14].display_name | Local search (optimization) |
| concepts[15].id | https://openalex.org/C169903167 |
| concepts[15].level | 2 |
| concepts[15].score | 0.262093186378479 |
| concepts[15].wikidata | https://www.wikidata.org/wiki/Q3985153 |
| concepts[15].display_name | Test set |
| concepts[16].id | https://openalex.org/C206345919 |
| concepts[16].level | 2 |
| concepts[16].score | 0.2598578631877899 |
| concepts[16].wikidata | https://www.wikidata.org/wiki/Q20380951 |
| concepts[16].display_name | Resource (disambiguation) |
| concepts[17].id | https://openalex.org/C33923547 |
| concepts[17].level | 0 |
| concepts[17].score | 0.2568108141422272 |
| concepts[17].wikidata | https://www.wikidata.org/wiki/Q395 |
| concepts[17].display_name | Mathematics |
| keywords[0].id | https://openalex.org/keywords/kernel |
| keywords[0].score | 0.6926611065864563 |
| keywords[0].display_name | Kernel (algebra) |
| keywords[1].id | https://openalex.org/keywords/benchmark |
| keywords[1].score | 0.6882950067520142 |
| keywords[1].display_name | Benchmark (surveying) |
| keywords[2].id | https://openalex.org/keywords/heuristic |
| keywords[2].score | 0.6478341221809387 |
| keywords[2].display_name | Heuristic |
| keywords[3].id | https://openalex.org/keywords/set |
| keywords[3].score | 0.602584958076477 |
| keywords[3].display_name | Set (abstract data type) |
| keywords[4].id | https://openalex.org/keywords/facility-location-problem |
| keywords[4].score | 0.49042248725891113 |
| keywords[4].display_name | Facility location problem |
| keywords[5].id | https://openalex.org/keywords/quality |
| keywords[5].score | 0.3381395936012268 |
| keywords[5].display_name | Quality (philosophy) |
| keywords[6].id | https://openalex.org/keywords/test-case |
| keywords[6].score | 0.33058878779411316 |
| keywords[6].display_name | Test case |
| language | |
| locations[0].id | pmh:oai:arXiv.org:2512.08576 |
| locations[0].is_oa | True |
| locations[0].source.id | https://openalex.org/S4306400194 |
| locations[0].source.issn | |
| locations[0].source.type | repository |
| locations[0].source.is_oa | True |
| locations[0].source.issn_l | |
| locations[0].source.is_core | False |
| locations[0].source.is_in_doaj | False |
| locations[0].source.display_name | arXiv (Cornell University) |
| locations[0].source.host_organization | https://openalex.org/I205783295 |
| locations[0].source.host_organization_name | Cornell University |
| locations[0].source.host_organization_lineage | https://openalex.org/I205783295 |
| locations[0].license | cc-by |
| locations[0].pdf_url | https://arxiv.org/pdf/2512.08576 |
| locations[0].version | submittedVersion |
| locations[0].raw_type | text |
| locations[0].license_id | https://openalex.org/licenses/cc-by |
| locations[0].is_accepted | False |
| locations[0].is_published | False |
| locations[0].raw_source_name | |
| locations[0].landing_page_url | http://arxiv.org/abs/2512.08576 |
| indexed_in | arxiv |
| authorships[0].author.id | |
| authorships[0].author.orcid | |
| authorships[0].author.display_name | Bakker, Hannah |
| authorships[0].author_position | first |
| authorships[0].raw_author_name | Bakker, Hannah |
| authorships[0].is_corresponding | True |
| authorships[1].author.id | |
| authorships[1].author.orcid | |
| authorships[1].author.display_name | Guastaroba, Gianfranco |
| authorships[1].author_position | middle |
| authorships[1].raw_author_name | Guastaroba, Gianfranco |
| authorships[1].is_corresponding | False |
| authorships[2].author.id | |
| authorships[2].author.orcid | |
| authorships[2].author.display_name | Nickel, Stefan |
| authorships[2].author_position | middle |
| authorships[2].raw_author_name | Nickel, Stefan |
| authorships[2].is_corresponding | False |
| authorships[3].author.id | |
| authorships[3].author.orcid | |
| authorships[3].author.display_name | Speranza, M. Grazia |
| authorships[3].author_position | last |
| authorships[3].raw_author_name | Speranza, M. Grazia |
| authorships[3].is_corresponding | False |
| has_content.pdf | True |
| has_content.grobid_xml | False |
| is_paratext | False |
| open_access.is_oa | True |
| open_access.oa_url | https://arxiv.org/pdf/2512.08576 |
| open_access.oa_status | green |
| open_access.any_repository_has_fulltext | False |
| created_date | 2025-12-11T00:00:00 |
| display_name | Enhancing Kernel Search with Pattern Recognition: the Single-Source Capacitated Facility Location Problem |
| has_fulltext | False |
| is_retracted | False |
| updated_date | 2025-12-12T23:20:42.204495 |
| primary_topic.id | https://openalex.org/T11502 |
| primary_topic.field.id | https://openalex.org/fields/14 |
| primary_topic.field.display_name | Business, Management and Accounting |
| primary_topic.score | 0.8814742565155029 |
| primary_topic.domain.id | https://openalex.org/domains/2 |
| primary_topic.domain.display_name | Social Sciences |
| primary_topic.subfield.id | https://openalex.org/subfields/1407 |
| primary_topic.subfield.display_name | Organizational Behavior and Human Resource Management |
| primary_topic.display_name | Facility Location and Emergency Management |
| cited_by_count | 0 |
| locations_count | 1 |
| best_oa_location.id | pmh:oai:arXiv.org:2512.08576 |
| best_oa_location.is_oa | True |
| best_oa_location.source.id | https://openalex.org/S4306400194 |
| best_oa_location.source.issn | |
| best_oa_location.source.type | repository |
| best_oa_location.source.is_oa | True |
| best_oa_location.source.issn_l | |
| best_oa_location.source.is_core | False |
| best_oa_location.source.is_in_doaj | False |
| best_oa_location.source.display_name | arXiv (Cornell University) |
| best_oa_location.source.host_organization | https://openalex.org/I205783295 |
| best_oa_location.source.host_organization_name | Cornell University |
| best_oa_location.source.host_organization_lineage | https://openalex.org/I205783295 |
| best_oa_location.license | cc-by |
| best_oa_location.pdf_url | https://arxiv.org/pdf/2512.08576 |
| best_oa_location.version | submittedVersion |
| best_oa_location.raw_type | text |
| best_oa_location.license_id | https://openalex.org/licenses/cc-by |
| best_oa_location.is_accepted | False |
| best_oa_location.is_published | False |
| best_oa_location.raw_source_name | |
| best_oa_location.landing_page_url | http://arxiv.org/abs/2512.08576 |
| primary_location.id | pmh:oai:arXiv.org:2512.08576 |
| primary_location.is_oa | True |
| primary_location.source.id | https://openalex.org/S4306400194 |
| primary_location.source.issn | |
| primary_location.source.type | repository |
| primary_location.source.is_oa | True |
| primary_location.source.issn_l | |
| primary_location.source.is_core | False |
| primary_location.source.is_in_doaj | False |
| primary_location.source.display_name | arXiv (Cornell University) |
| primary_location.source.host_organization | https://openalex.org/I205783295 |
| primary_location.source.host_organization_name | Cornell University |
| primary_location.source.host_organization_lineage | https://openalex.org/I205783295 |
| primary_location.license | cc-by |
| primary_location.pdf_url | https://arxiv.org/pdf/2512.08576 |
| primary_location.version | submittedVersion |
| primary_location.raw_type | text |
| primary_location.license_id | https://openalex.org/licenses/cc-by |
| primary_location.is_accepted | False |
| primary_location.is_published | False |
| primary_location.raw_source_name | |
| primary_location.landing_page_url | http://arxiv.org/abs/2512.08576 |
| publication_date | 2025-12-09 |
| publication_year | 2025 |
| referenced_works_count | 0 |
| abstract_inverted_index.a | 6, 26, 80, 103, 123, 146 |
| abstract_inverted_index.In | 20, 54 |
| abstract_inverted_index.KS | 105, 170 |
| abstract_inverted_index.On | 79 |
| abstract_inverted_index.We | 0 |
| abstract_inverted_index.an | 32, 60, 131 |
| abstract_inverted_index.as | 116, 118 |
| abstract_inverted_index.in | 75, 174 |
| abstract_inverted_index.of | 12, 36, 82, 87, 140, 149, 176, 178, 186 |
| abstract_inverted_index.on | 145 |
| abstract_inverted_index.to | 30, 89, 135, 157 |
| abstract_inverted_index.up | 88, 156 |
| abstract_inverted_index.112 | 83 |
| abstract_inverted_index.For | 126 |
| abstract_inverted_index.and | 39, 48, 92, 107, 160, 172, 189 |
| abstract_inverted_index.are | 51 |
| abstract_inverted_index.for | 9, 112 |
| abstract_inverted_index.gap | 133 |
| abstract_inverted_index.new | 150 |
| abstract_inverted_index.run | 121 |
| abstract_inverted_index.set | 81, 148 |
| abstract_inverted_index.the | 10, 13, 21, 55, 68, 71, 76, 108, 114, 136, 168, 179, 183, 191 |
| abstract_inverted_index.(KS) | 64 |
| abstract_inverted_index.PaKS | 24, 58, 99, 129, 165 |
| abstract_inverted_index.best | 137, 187 |
| abstract_inverted_index.both | 102, 167 |
| abstract_inverted_index.gap. | 194 |
| abstract_inverted_index.into | 41 |
| abstract_inverted_index.show | 97 |
| abstract_inverted_index.test | 153 |
| abstract_inverted_index.that | 66, 98, 164 |
| abstract_inverted_index.time | 124 |
| abstract_inverted_index.very | 151 |
| abstract_inverted_index.well | 117 |
| abstract_inverted_index.when | 120 |
| abstract_inverted_index.with | 122 |
| abstract_inverted_index.1,000 | 90, 93 |
| abstract_inverted_index.2,000 | 158, 161 |
| abstract_inverted_index.CPLEX | 119, 173 |
| abstract_inverted_index.among | 70 |
| abstract_inverted_index.first | 22, 77 |
| abstract_inverted_index.known | 138 |
| abstract_inverted_index.large | 147, 152 |
| abstract_inverted_index.terms | 175 |
| abstract_inverted_index.these | 127 |
| abstract_inverted_index.which | 46 |
| abstract_inverted_index.0.02%. | 141 |
| abstract_inverted_index.Kernel | 3, 62 |
| abstract_inverted_index.Search | 4, 63 |
| abstract_inverted_index.called | 43 |
| abstract_inverted_index.found, | 181 |
| abstract_inverted_index.limit. | 125 |
| abstract_inverted_index.number | 185 |
| abstract_inverted_index.phase, | 23, 57 |
| abstract_inverted_index.phase. | 78 |
| abstract_inverted_index.second | 56 |
| abstract_inverted_index.within | 45 |
| abstract_inverted_index.(PaKS), | 5 |
| abstract_inverted_index.Problem | 18 |
| abstract_inverted_index.SSCFLP, | 115 |
| abstract_inverted_index.average | 132, 193 |
| abstract_inverted_index.current | 109 |
| abstract_inverted_index.employs | 25, 59 |
| abstract_inverted_index.finding | 182 |
| abstract_inverted_index.largest | 184 |
| abstract_inverted_index.pattern | 27 |
| abstract_inverted_index.quality | 177 |
| abstract_inverted_index.results | 96, 143 |
| abstract_inverted_index.solving | 113 |
| abstract_inverted_index.spatial | 34 |
| abstract_inverted_index.Facility | 16 |
| abstract_inverted_index.Location | 17 |
| abstract_inverted_index.achieved | 130 |
| abstract_inverted_index.compared | 134 |
| abstract_inverted_index.decision | 72 |
| abstract_inverted_index.enhanced | 61 |
| abstract_inverted_index.identify | 31 |
| abstract_inverted_index.implicit | 33 |
| abstract_inverted_index.location | 47 |
| abstract_inverted_index.regions, | 44 |
| abstract_inverted_index.smallest | 192 |
| abstract_inverted_index.solution | 11, 139, 180 |
| abstract_inverted_index.standard | 104, 169 |
| abstract_inverted_index.strongly | 52 |
| abstract_inverted_index.subsets, | 42 |
| abstract_inverted_index.(SSCFLP). | 19 |
| abstract_inverted_index.achieving | 190 |
| abstract_inverted_index.benchmark | 84 |
| abstract_inverted_index.conducted | 144 |
| abstract_inverted_index.customers | 40 |
| abstract_inverted_index.decisions | 50 |
| abstract_inverted_index.heuristic | 65, 111, 171 |
| abstract_inverted_index.introduce | 1 |
| abstract_inverted_index.leverages | 67 |
| abstract_inverted_index.locations | 38, 91, 159 |
| abstract_inverted_index.potential | 37 |
| abstract_inverted_index.problems, | 154 |
| abstract_inverted_index.technique | 29 |
| abstract_inverted_index.two-phase | 7 |
| abstract_inverted_index.variables | 73 |
| abstract_inverted_index.assignment | 49 |
| abstract_inverted_index.comprising | 155 |
| abstract_inverted_index.consisting | 86 |
| abstract_inverted_index.customers, | 94, 162 |
| abstract_inverted_index.identified | 74 |
| abstract_inverted_index.instances, | 85, 128 |
| abstract_inverted_index.separation | 35 |
| abstract_inverted_index.solutions, | 188 |
| abstract_inverted_index.Capacitated | 15 |
| abstract_inverted_index.demonstrate | 163 |
| abstract_inverted_index.outperforms | 101, 166 |
| abstract_inverted_index.recognition | 28 |
| abstract_inverted_index.Experimental | 142 |
| abstract_inverted_index.consistently | 100 |
| abstract_inverted_index.matheuristic | 8 |
| abstract_inverted_index.Pattern-based | 2 |
| abstract_inverted_index.Single-Source | 14 |
| abstract_inverted_index.computational | 95 |
| abstract_inverted_index.implementation | 106 |
| abstract_inverted_index.interdependent. | 53 |
| abstract_inverted_index.state-of-the-art | 110 |
| abstract_inverted_index.interdependencies | 69 |
| cited_by_percentile_year | |
| countries_distinct_count | 0 |
| institutions_distinct_count | 4 |
| citation_normalized_percentile.value | 0.88182023 |
| citation_normalized_percentile.is_in_top_1_percent | False |
| citation_normalized_percentile.is_in_top_10_percent | True |