Page 365 -

SHORTEST-ROUTE PROBLEM 345

MANAGEMENT SCIENCE IN ACTION

Optimizing Restoration Capacity At AT&T
T&T is a global telecommunications company To optimize restoration capacity, the RestNet
A that provides long-distance voice and data, team developed a large-scale linear programming
video, wireless, satellite and Internet services. The model. One subproblem in their model involves
company uses state-of-the-art switching and trans- determining the shortest route connecting an origin
mission equipment to provide service to more than and destination whenever a failure occurs in a span
80 million customers. In the continental United States, of the transmission network. Another subproblem
AT&T’s transmission network consists of more than solves a maximal flow problem to find the best
40000 miles of fibre-optic cable. On peak days AT&T restoration paths from each switch to a disaster
handles as many as 290 million calls of various types. recovery switch.
Power outages, natural disasters, cable cuts and The RestNet team was successful, and their work
other events can disable a portion of the transmis- is an example of how valuable management science
sion network. When such events occur, spare methodology is to companies. According to
capacity comprising the restoration network must C. Michael Armstrong, chair and CEO, ‘Last year
be immediately employed so that service is not dis- the work of the RestNet team allowed us to reduce
rupted. Critical issues with respect to the restoration capital spending by tens of millions of dollars’.
network are: How much capacity is necessary?
Based on Ken Ambs, Sebastian Cwilich, Mei Deng, David J. Houck,
Where should it be located? AT&T assembled a
David F. Lynch and Dicky Yan, ‘Optimizing Restoration Capacity in the
RestNet team to address these issues. AT&T Network’, Interfaces (January/February 2000): 26–44.

Many managerial problems in areas such as transportation systems design, infor-
mation systems design and project scheduling have been successfully solved with the
aid of network models and network analysis techniques. In Chapter 7 we showed
how networks consisting of nodes and arcs can be used to provide graphical repre-
sentations of transportation, assignment and transshipment problems. In this chap-
ter we present three additional network problems: the shortest-route problem, the
minimal spanning tree problem and the maximal flow problem. In each case, we will
show how a network model can be developed and solved in order to provide an
optimal solution to the problem. The Management Science in Action, Optimizing
Restoration Capacity at AT&T, notes that AT&T solved shortest-route and max-
imal flow problems in designing their transmission network.

8.1 Shortest-Route Problem

In this section we consider a network application in which the primary objective is to
determine the shortest route or path between any pair of nodes in a network. We
demonstrate the shortest-route problem by considering the situation facing the
Government Development Agency (GDA) operating in Brunei, southeast Asia.
The GDA has several economic development construction projects located through-
out one region. The projects are designed to support local economic development in
the area and consist of projects such as road-building, school construction and
building medical clinics. Construction sites are sometimes located as far as 50km
from GDA’s main office. With multiple daily trips carrying personnel, equipment
and supplies to and from the construction locations, the costs associated with

Copyright 2014 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part. Due to electronic rights, some third party content may be suppressed from the eBook and/or eChapter(s). Editorial review has
deemed that any suppressed content does not materially affect the overall learning experience. Cengage Learning reserves the right to remove additional content at any time if subsequent rights restrictions require it.