TY - JOUR
T1 - Network construction problems with due dates
AU - Averbakh, Igor
AU - Pereira, Jordi
N1 - Funding Information:
The work of Igor Averbakh was supported by a grant from the Natural Sciences and Engineering Research Council of Canada (NSERC). The authors thank the CIGIDEN (Chilean center for natural disaster management) and the Chilean ministry of public works for providing data on restoration works for 2010 Chilean earthquake.
Publisher Copyright:
© 2015 Elsevier B.V. All rights reserved.
PY - 2015/8/1
Y1 - 2015/8/1
N2 - Abstract A network needs to be constructed by a server (construction crew) that has a constant construction speed which is incomparably slower than the server's travel speed within the already constructed part of the network. A vertex is recovered when it becomes connected to the depot by an already constructed path. Due dates for recovery times are associated with vertices. The problem is to obtain a construction schedule that minimizes the maximum lateness of vertices, or the number of tardy vertices. We introduce these new problems, discuss their computational complexity, and present mixed-integer linear programming formulations, heuristics, a branch-and-bound algorithm, and results of computational experiments.
AB - Abstract A network needs to be constructed by a server (construction crew) that has a constant construction speed which is incomparably slower than the server's travel speed within the already constructed part of the network. A vertex is recovered when it becomes connected to the depot by an already constructed path. Due dates for recovery times are associated with vertices. The problem is to obtain a construction schedule that minimizes the maximum lateness of vertices, or the number of tardy vertices. We introduce these new problems, discuss their computational complexity, and present mixed-integer linear programming formulations, heuristics, a branch-and-bound algorithm, and results of computational experiments.
KW - Emergency restoration
KW - Integrated network design and scheduling
KW - Network construction
KW - Network design
KW - Scheduling
UR - http://www.scopus.com/inward/record.url?scp=84926415771&partnerID=8YFLogxK
U2 - 10.1016/j.ejor.2015.02.014
DO - 10.1016/j.ejor.2015.02.014
M3 - Article
AN - SCOPUS:84926415771
SN - 0377-2217
VL - 244
SP - 715
EP - 729
JO - European Journal of Operational Research
JF - European Journal of Operational Research
IS - 3
M1 - 12783
ER -