  As extreme weather events become more frequent and disruptive, service
restoration is increasingly important for many infrastructures, e.g., power
grids and communication networks. In many studies on service restoration, the
logistics issue of traveling over the road network, however, is often
overlooked due to the complexity of considering multiple networks
simultaneously, resulting in prolonged disruption time. In this work, we
address such a problem arising in power systems, where technical crew and
utility trucks travel to a number of sites to repair damaged equipment, with
the goal of minimizing the total service disruption time within the service
region. We call this problem the Power Restoration Traveling Repairman Problem
(PRTRP). What makes it significantly more challenging than a typical routing
problem is that the service disruption time in a location depends on the
interaction of the routing sequence with both networks, i.e., the road network
and the power grid. To solve the problem, we develop an exact method based on
bi-directional dynamic programming. We then improve the method by reducing the
search space with solution upper and lower bounds, and threshold rules derived
from the precedence relations in the power grid. We also propose efficient
heuristic variants of the method. We present computational results and compare
our method with benchmark heuristics.
