Lateness Minimization in Pairwise Connectivity Restoration Problems

Igor Averbakh () and Jordi Pereira ()
Additional contact information
Igor Averbakh: Department of Management, University of Toronto Scarborough, Toronto, Ontario M1C 1A4, Canada
Jordi Pereira: Faculty of Engineering and Sciences, Universidad Adolfo Ibáñez, Viña del Mar 2581793, Chile

INFORMS Journal on Computing, 2018, vol. 30, issue 3, 522-538

Abstract: A network is given whose edges need to be constructed (or restored after a disaster). The lengths of edges represent the required construction/restoration times given available resources, and one unit of length of the network can be constructed per unit of time. All points of the network are accessible for construction at any time. For each pair of vertices, a due date is given. It is required to find a construction schedule that minimizes the maximum lateness of all pairs of vertices, where the lateness of a pair is the difference between the time when the pair becomes connected by an already constructed path and the pair’s due date. We introduce the problem and analyze its structural properties, present a mixed-integer linear programming formulation, develop a number of lower bounds that are integrated in a branch-and-bound algorithm, and discuss results of computational experiments both for instances based on randomly generated networks and for instances based on 2010 Chilean earthquake data.

Keywords: combinatorial optimization; networks: scheduling; programming: branch and bound; network restoration; network construction; integrated network design and scheduling (search for similar items in EconPapers)
Date: 2018
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (3)

Downloads: (external link)
https://doi.org/10.1287/ijoc.2017.0796 (application/pdf)

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:inm:orijoc:v:30:y:2018:i:3:p:522-538

Access Statistics for this article

More articles in INFORMS Journal on Computing from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().