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)


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: Faculties > Social Sciences > Kent Business School > Management Science
Faculties > Social Sciences > Kent Business School > Centre for Logistics and Heuristic Organisation (CLHO)
Depositing User: Paola Scaparra
Date Deposited: 20 Apr 2017 13:22 UTC
Last Modified: 17 Dec 2019 13:54 UTC
Resource URI: (The current URI for this page, for reference purposes)
Scaparra, Maria Paola:
O'Hanley, Jesse R.:
  • Depositors only (login required):


Downloads per month over past year