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)

Abstract

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 > Department of Analytics, Operations and Systems
Depositing User: Paola Scaparra
Date Deposited: 20 Apr 2017 13:22 UTC
Last Modified: 11 Jan 2024 10:23 UTC
Resource URI: https://kar.kent.ac.uk/id/eprint/61407 (The current URI for this page, for reference purposes)

University of Kent Author Information

  • Depositors only (login required):

Total unique views for this document in KAR since July 2020. For more details click on the image.