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 | |
Publication status | Published - 1 Jul 2016 |
Funding
We are thankful to the reviewer׳s comments and suggestions which dramatically improved the clarity and presentation of the paper. This research was partially supported by the Canadian Natural Sciences and Engineering Research council under Grants 39682-05 and 183631-05 . This support is gratefully acknowledged.
Keywords
- Capacity acquisition
- Dynamic programming
- Location-allocation problem
- Shooting algorithm
ASJC Scopus subject areas
- General Computer Science
- Modelling and Simulation
- Management Science and Operations Research