TY - JOUR

T1 - The flowtime network construction problem

AU - Averbakh, Igor

AU - Pereira, Jordi

N1 - Funding Information:
The research of Igor Averbakh was supported by a grant from the Natural Sciences and Engineering Research Council of Canada.

PY - 2012/8

Y1 - 2012/8

N2 - Given a network whose edges need to be constructed, the problem is to find a construction schedule that minimizes the total recovery time of the vertices, where the recovery time of a vertex is the time when the vertex becomes connected to a special vertex (depot) that is the initial location of the construction crew. The construction speed is constant and is assumed to be incomparably slower than the travel speed of the construction crew in the already constructed part of the network. In this article, this new problem is introduced, its complexity is discussed, mixed-integer linear programming formulations are developed, fast and simple heuristics are proposed, and an exact branch-and-bound algorithm is presented which is based on specially designed lower bounds and dominance tests that exploit the problem's combinatorial structure. The results of extensive computational experiments are also presented. Connections between the problem and the Traveling Repairman Problem, also known as the Delivery Man Problem, and applications in emergency restoration operations are discussed.

AB - Given a network whose edges need to be constructed, the problem is to find a construction schedule that minimizes the total recovery time of the vertices, where the recovery time of a vertex is the time when the vertex becomes connected to a special vertex (depot) that is the initial location of the construction crew. The construction speed is constant and is assumed to be incomparably slower than the travel speed of the construction crew in the already constructed part of the network. In this article, this new problem is introduced, its complexity is discussed, mixed-integer linear programming formulations are developed, fast and simple heuristics are proposed, and an exact branch-and-bound algorithm is presented which is based on specially designed lower bounds and dominance tests that exploit the problem's combinatorial structure. The results of extensive computational experiments are also presented. Connections between the problem and the Traveling Repairman Problem, also known as the Delivery Man Problem, and applications in emergency restoration operations are discussed.

KW - Deliveryman problem

KW - Emergency restoration operations

KW - Network construction planning

KW - Scheduling

KW - Traveling repairman problem

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

U2 - 10.1080/0740817X.2011.636792

DO - 10.1080/0740817X.2011.636792

M3 - Article

AN - SCOPUS:84870874106

SN - 0740-817X

VL - 44

SP - 681

EP - 694

JO - IIE Transactions (Institute of Industrial Engineers)

JF - IIE Transactions (Institute of Industrial Engineers)

IS - 8

ER -