TY - CHAP
T1 - MIP Modeling of Incremental Connected Facility Location
AU - Arulselvan, Ashwin
AU - Bley, Andreas
AU - Gollowitzer, Stefan
AU - Ljubic, Ivana
AU - Maurer, Olaf
PY - 2011
Y1 - 2011
N2 - We consider the incremental connected facility location problem, 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 also be 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 maximize the net present value of the network, which is given by the discounted revenues of serving the customers and by the discounted investments and maintenance costs for the facilities and the network. We study different MIP models for this problem, discuss some valid inequalities to strengthen these formulations, and present a branch and cut algorithm for finding its solution. Finally, we report (preliminary) computational results of our implementation of this algorithm.
AB - We consider the incremental connected facility location problem, 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 also be 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 maximize the net present value of the network, which is given by the discounted revenues of serving the customers and by the discounted investments and maintenance costs for the facilities and the network. We study different MIP models for this problem, discuss some valid inequalities to strengthen these formulations, and present a branch and cut algorithm for finding its solution. Finally, we report (preliminary) computational results of our implementation of this algorithm.
KW - facility location
KW - valid inequality
KW - greedy randomize adaptive search procedure
KW - facility location problem
KW - Steiner tree problem (STP)
U2 - 10.1007/978-3-642-21527-8_54
DO - 10.1007/978-3-642-21527-8_54
M3 - Chapter
VL - 6701
T3 - Lecture Notes in Computer Science
SP - 490
EP - 502
BT - Network Optimization
A2 - Pahl, J.
A2 - Reiners , T.
A2 - Voß, S.
PB - Springer
CY - Berlin
T2 - International Conference on Network Optimization - INOC2011
Y2 - 13 June 2011 through 16 June 2011
ER -