Skip to main content

A Hypergraph Multi-Exchange Heuristic for the Single-Source Capacitated Facility Location Problem

Tran, Trung Hieu, Scaparra, Maria Paola, O'Hanley, Jesse R. (2017) A Hypergraph Multi-Exchange Heuristic for the Single-Source Capacitated Facility Location Problem. European Journal of Operational Research, 263 (1). pp. 173-187. ISSN 0377-2217. (doi:10.1016/j.ejor.2017.04.032) (KAR id:61407)

PDF Author's Accepted Manuscript
Language: English

Download (578kB) Preview
[thumbnail of HMEH_EJOR2017.pdf]
This file may not be suitable for users of assistive technology.
Request an accessible format
PDF Author's Accepted Manuscript
Language: English

Restricted to Repository staff only

Contact us about this Publication
[thumbnail of HMEH_EJOR2017.pdf]
Official URL


In this paper, we introduce a large-scale neighborhood search procedure for solving the single-source capacitated facility location problem (SSCFLP). The neighborhood structures are induced by innovative split multi-customer multi-exchanges, where clusters of customers assigned to one facility can be moved simultaneously to multiple destination facilities and vice versa. To represent these exchanges, we use two types of improvement hypergraphs. The improvement hypergraphs are built dynamically and the moving customers associated with each hyperedge are selected by solving heuristically a suitably defined mixed-integer program. We develop a hypergraph search framework, including forward and backward procedures, to identify improving solutions efficiently. Our proposed algorithm can obtain improving moves more quickly and even find better solutions than a traditional multi-exchange heuristic (Ahuja et al., 2004). In addition, when compared with the Kernel Search algorithm (Guastaroba and Speranza, 2014), which at present is the most effective for solving SSCFLP, our algorithm is not only competitive but can find better solutions or even the best known solution to some very large scale benchmark instances from the literature.

Item Type: Article
DOI/Identification number: 10.1016/j.ejor.2017.04.032
Uncontrolled keywords: facility location; large-scale neighborhood search; multi-exchange heuristic; hypergraphs
Subjects: H Social Sciences
Divisions: Divisions > Kent Business School - Division > Kent Business School (do not use)
Divisions > Kent Business School - Division > Centre for Logistics and Heuristic Optimisation (do not use)
Depositing User: Paola Scaparra
Date Deposited: 20 Apr 2017 13:22 UTC
Last Modified: 16 Feb 2021 13:44 UTC
Resource URI: (The current URI for this page, for reference purposes)
Scaparra, Maria Paola:
O'Hanley, Jesse R.:
  • Depositors only (login required):