TY - JOUR
T1 - Lagrangean relaxation heuristics for the p-cable-trench problem
AU - Marianov, Vladimir
AU - Gutiérrez-Jarpa, Gabriel
AU - Obreque, Carlos
AU - Cornejo, Oscar
N1 - Funding Information:
We thank two anonymous referees for providing many insightful comments, as well as for suggesting a source for the Sobolev problem instances. We gratefully acknowledge the funding of this research by Dirección de Investigación de la Universidad Católica de la Santísima Concepción under Project DIN12-2008 ; Instituto Milenio Complex Engineering Systems , under grants ICM P-05-004-F and CONICYT FBO16 , and FONDECYT 1100296 .
PY - 2012/3
Y1 - 2012/3
N2 - We address the p-cable-trench problem. In this problem, p facilities are located, a trench network is dug and cables are laid in the trenches, so that every customer-or demand-in the region is connected to a facility through a cable. The digging cost of the trenches, as well as the sum of the cable lengths between the customers and their assigned facilities, are minimized. We formulate an integer programming model of the problem using multicommodity flows that allows finding the solution for instances of up to 200 nodes. We also propose two Lagrangean Relaxation-based heuristics to solve larger instances of the problem. Computational experience is provided for instances of up to 300 nodes.
AB - We address the p-cable-trench problem. In this problem, p facilities are located, a trench network is dug and cables are laid in the trenches, so that every customer-or demand-in the region is connected to a facility through a cable. The digging cost of the trenches, as well as the sum of the cable lengths between the customers and their assigned facilities, are minimized. We formulate an integer programming model of the problem using multicommodity flows that allows finding the solution for instances of up to 200 nodes. We also propose two Lagrangean Relaxation-based heuristics to solve larger instances of the problem. Computational experience is provided for instances of up to 300 nodes.
KW - Lagrangean relaxation heuristics
KW - Location
KW - Network design
UR - http://www.scopus.com/inward/record.url?scp=79960179134&partnerID=8YFLogxK
U2 - 10.1016/j.cor.2011.05.015
DO - 10.1016/j.cor.2011.05.015
M3 - Article
AN - SCOPUS:79960179134
SN - 0305-0548
VL - 39
SP - 620
EP - 628
JO - Computers and Operations Research
JF - Computers and Operations Research
IS - 3
ER -