A global shooting algorithm for the facility location and capacity acquisition problem on a line with dense demand

Alper Murat; Gilbert Laporte; Vedat Verter

doi:10.1016/j.cor.2015.12.018

A global shooting algorithm for the facility location and capacity acquisition problem on a line with dense demand

Alper Murat, Gilbert Laporte, Vedat Verter

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

5 Citations (Scopus)

Abstract

This paper describes the development of an exact allocation-based solution algorithm for the facility location and capacity acquisition problem (LCAP) on a line with dense demand data. Initially, the n-facility problem on a line is studied and formulated as a dynamic programming model in the allocation decision space. Next, we cast this dynamic programming formulation as a two-point boundary value problem and provide conditions for the existence and uniqueness of solutions. We derive sufficient conditions for non-empty service regions and necessary conditions for interior facility locations. We develop an efficient exact shooting algorithm to solve the problem as an initial value problem and illustrate on an example. A computational study is conducted to study the effect of demand density and other problem parameters on the solutions.

Original language	English
Pages (from-to)	1-15
Number of pages	15
Journal	Computers and Operations Research
Volume	71
DOIs	https://doi.org/10.1016/j.cor.2015.12.018
Publication status	Published - 1 Jul 2016

Keywords

Capacity acquisition
Dynamic programming
Location-allocation problem
Shooting algorithm

ASJC Scopus subject areas

Computer Science(all)
Modelling and Simulation
Management Science and Operations Research

Access to Document

10.1016/j.cor.2015.12.018

Link to publication in Scopus

Fingerprint Dive into the research topics of 'A global shooting algorithm for the facility location and capacity acquisition problem on a line with dense demand'. Together they form a unique fingerprint.

Cite this

@article{e9905bad60734ed7b142bf7e18f1177d,

title = "A global shooting algorithm for the facility location and capacity acquisition problem on a line with dense demand",

abstract = "This paper describes the development of an exact allocation-based solution algorithm for the facility location and capacity acquisition problem (LCAP) on a line with dense demand data. Initially, the n-facility problem on a line is studied and formulated as a dynamic programming model in the allocation decision space. Next, we cast this dynamic programming formulation as a two-point boundary value problem and provide conditions for the existence and uniqueness of solutions. We derive sufficient conditions for non-empty service regions and necessary conditions for interior facility locations. We develop an efficient exact shooting algorithm to solve the problem as an initial value problem and illustrate on an example. A computational study is conducted to study the effect of demand density and other problem parameters on the solutions.",

keywords = "Capacity acquisition, Dynamic programming, Location-allocation problem, Shooting algorithm",

author = "Alper Murat and Gilbert Laporte and Vedat Verter",

year = "2016",

month = jul,

day = "1",

doi = "10.1016/j.cor.2015.12.018",

language = "English",

volume = "71",

pages = "1--15",

journal = "Computers and Operations Research",

issn = "0305-0548",

publisher = "Elsevier",

}

TY - JOUR

T1 - A global shooting algorithm for the facility location and capacity acquisition problem on a line with dense demand

AU - Murat, Alper

AU - Laporte, Gilbert

AU - Verter, Vedat

PY - 2016/7/1

Y1 - 2016/7/1

N2 - This paper describes the development of an exact allocation-based solution algorithm for the facility location and capacity acquisition problem (LCAP) on a line with dense demand data. Initially, the n-facility problem on a line is studied and formulated as a dynamic programming model in the allocation decision space. Next, we cast this dynamic programming formulation as a two-point boundary value problem and provide conditions for the existence and uniqueness of solutions. We derive sufficient conditions for non-empty service regions and necessary conditions for interior facility locations. We develop an efficient exact shooting algorithm to solve the problem as an initial value problem and illustrate on an example. A computational study is conducted to study the effect of demand density and other problem parameters on the solutions.

AB - This paper describes the development of an exact allocation-based solution algorithm for the facility location and capacity acquisition problem (LCAP) on a line with dense demand data. Initially, the n-facility problem on a line is studied and formulated as a dynamic programming model in the allocation decision space. Next, we cast this dynamic programming formulation as a two-point boundary value problem and provide conditions for the existence and uniqueness of solutions. We derive sufficient conditions for non-empty service regions and necessary conditions for interior facility locations. We develop an efficient exact shooting algorithm to solve the problem as an initial value problem and illustrate on an example. A computational study is conducted to study the effect of demand density and other problem parameters on the solutions.

KW - Capacity acquisition

KW - Dynamic programming

KW - Location-allocation problem

KW - Shooting algorithm

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

U2 - 10.1016/j.cor.2015.12.018

DO - 10.1016/j.cor.2015.12.018

M3 - Article

AN - SCOPUS:84956984530

VL - 71

SP - 1

EP - 15

JO - Computers and Operations Research

JF - Computers and Operations Research

SN - 0305-0548

ER -