An exact algorithm for multilevel uncapacitated facility location

Camilo Ortiz-Astorquiza; Ivan Contreras; Gilbert Laporte

doi:10.1287/trsc.2018.0868

An exact algorithm for multilevel uncapacitated facility location

Camilo Ortiz-Astorquiza, Ivan Contreras, Gilbert Laporte

Research output: Contribution to journal › Article › peer-review

8 Citations (Scopus)

Abstract

We study a general class of multilevel uncapacitated p-location problems in which the selection of links between levels of facilities is part of the decision process. We propose an exact algorithm based on a Benders reformulation to solve large-scale instances of the general problem and some well-known particular cases. We exploit the network flow structure of the reformulation to efficiently generate Pareto-optimal cuts. We perform extensive computational experiments to assess the performance of several different variants of the Benders algorithm. Results obtained on benchmark instances with up to 3,000 customers, 250 potential facilities, and four levels confirm its efficiency.

Original language	English
Pages (from-to)	1085-1106
Number of pages	22
Journal	Transportation Science
Volume	53
Issue number	4
DOIs	https://doi.org/10.1287/trsc.2018.0868
Publication status	Published - 1 Jan 2019

Keywords

Benders decomposition
Multilevel facility location
Network design
Pareto-optimal cuts

ASJC Scopus subject areas

Civil and Structural Engineering
Transportation

Access to Document

10.1287/trsc.2018.0868

Link to publication in Scopus

Fingerprint Dive into the research topics of 'An exact algorithm for multilevel uncapacitated facility location'. Together they form a unique fingerprint.

Cite this

@article{d79e1d0d9d8b407ab0d4f98b5e620380,

title = "An exact algorithm for multilevel uncapacitated facility location",

abstract = "We study a general class of multilevel uncapacitated p-location problems in which the selection of links between levels of facilities is part of the decision process. We propose an exact algorithm based on a Benders reformulation to solve large-scale instances of the general problem and some well-known particular cases. We exploit the network flow structure of the reformulation to efficiently generate Pareto-optimal cuts. We perform extensive computational experiments to assess the performance of several different variants of the Benders algorithm. Results obtained on benchmark instances with up to 3,000 customers, 250 potential facilities, and four levels confirm its efficiency.",

keywords = "Benders decomposition, Multilevel facility location, Network design, Pareto-optimal cuts",

author = "Camilo Ortiz-Astorquiza and Ivan Contreras and Gilbert Laporte",

year = "2019",

month = jan,

day = "1",

doi = "10.1287/trsc.2018.0868",

language = "English",

volume = "53",

pages = "1085--1106",

journal = "Transportation Science",

issn = "0041-1655",

publisher = "INFORMS Inst.for Operations Res.and the Management Sciences",

number = "4",

}

TY - JOUR

T1 - An exact algorithm for multilevel uncapacitated facility location

AU - Ortiz-Astorquiza, Camilo

AU - Contreras, Ivan

AU - Laporte, Gilbert

PY - 2019/1/1

Y1 - 2019/1/1

N2 - We study a general class of multilevel uncapacitated p-location problems in which the selection of links between levels of facilities is part of the decision process. We propose an exact algorithm based on a Benders reformulation to solve large-scale instances of the general problem and some well-known particular cases. We exploit the network flow structure of the reformulation to efficiently generate Pareto-optimal cuts. We perform extensive computational experiments to assess the performance of several different variants of the Benders algorithm. Results obtained on benchmark instances with up to 3,000 customers, 250 potential facilities, and four levels confirm its efficiency.

AB - We study a general class of multilevel uncapacitated p-location problems in which the selection of links between levels of facilities is part of the decision process. We propose an exact algorithm based on a Benders reformulation to solve large-scale instances of the general problem and some well-known particular cases. We exploit the network flow structure of the reformulation to efficiently generate Pareto-optimal cuts. We perform extensive computational experiments to assess the performance of several different variants of the Benders algorithm. Results obtained on benchmark instances with up to 3,000 customers, 250 potential facilities, and four levels confirm its efficiency.

KW - Benders decomposition

KW - Multilevel facility location

KW - Network design

KW - Pareto-optimal cuts

UR - http://www.scopus.com/inward/record.url?scp=85071853723&partnerID=8YFLogxK

U2 - 10.1287/trsc.2018.0868

DO - 10.1287/trsc.2018.0868

M3 - Article

AN - SCOPUS:85071853723

VL - 53

SP - 1085

EP - 1106

JO - Transportation Science

JF - Transportation Science

SN - 0041-1655

IS - 4

ER -