The flowtime network construction problem

Igor Averbakh and Jordi Pereira

IISE Transactions, 2012, vol. 44, issue 8, 681-694

Abstract: 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.

Date: 2012
References: Add references at CitEc
Citations: View citations in EconPapers (18)

Downloads: (external link)
http://hdl.handle.net/10.1080/0740817X.2011.636792 (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:taf:uiiexx:v:44:y:2012:i:8:p:681-694

Ordering information: This journal article can be ordered from
http://www.tandfonline.com/pricing/journal/uiie20

DOI: 10.1080/0740817X.2011.636792

Access Statistics for this article

IISE Transactions is currently edited by Jianjun Shi

More articles in IISE Transactions from Taylor & Francis Journals
Bibliographic data for series maintained by Chris Longhurst ().