The incremental connected facility location problem

Arulselvan, Ashwin and Bley, Andreas and Ljubić, Ivana (2019) The incremental connected facility location problem. Computers & Operations Research, 112. pp. 1-17. 104763. ISSN 0305-0548 (https://doi.org/10.1016/j.cor.2019.104763)

[thumbnail of Arulselvan-etal-COR-2019-The-incremental-connected-facility-location-problem]
Preview
 Text. Filename: Arulselvan_etal_COR_2019_The_incremental_connected_facility_location_problem.pdf
Accepted Author Manuscript
License: Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 logo
Download (2MB)| Preview

Abstract

We consider the incremental connected facility location problem (incremental ConFL), in which we are given a set of potential facilities, a set of interconnection nodes, a set of customers with demands, and a planning horizon. For each time period, we have to select a set of facilities to open, a set of customers to be served, the assignment of these customers to the open facilities, and a network that connects the open facilities. Once a customer is served, it must remain served in subsequent periods. Furthermore, in each time period the total demand of all customers served must be at least equal to a given minimum coverage requirement for that period. The objective is to minimize the total cost for building the network given by the investment and maintenance costs for the facilities and the network summed up over all time periods. We propose a mixed integer programming approach in which, in each time period, a single period ConFL with coverage restrictions has to be solved. For this latter problem, which is of particular interest in itself, new families of valid inequalities are proposed: these are set union knapsack cover (SUKC) inequalities, which are further enhanced by lifting and/or combined with cut-set inequalities, which are primarily used to ensure connectivity requirements. Details of an efficient branch-and-cut implementation are presented and computational results on a benchmark set of large instances are given, including examples of telecommunication networks in Germany

ORCID iDs

Arulselvan, Ashwin ORCID logoORCID: https://orcid.org/0000-0001-9772-5523, Bley, Andreas and Ljubić, Ivana;
  • Item type:Article
    ID code:69136
    Dates:
    Date
    Event
    1 December 2019
    Published
    30 July 2019
    Published Online
    30 July 2019
    Accepted
    16 May 2019
    Submitted
    Notes:© 2019 Elsevier Ltd. All rights reserved. Ashwin Arulselvan, Andreas Bley, Ivana Ljubić, The incremental connected facility location problem, Computers & Operations Research, Volume 112, 2019, 104763, https://doi.org/10.1016/j.cor.2019.104763
    Subjects:Science > Mathematics > Electronic computers. Computer science
    Department:Strathclyde Business School > Management Science
    Depositing user: Pure Administrator
    Date deposited:30 Jul 2019 13:50
    Last modified:16 Nov 2024 01:15
    Related URLs:
    URI:https://strathprints.strath.ac.uk/id/eprint/69136
CORE (COnnecting REpositories)