Abstract
| In this talk, we describe an optimization problem motivated by the need to
maintain infrastructure networks over time. We consider infrastructure networks
in which product is transported between distinct origin-destination pairs, and
at the same time the infrastructure assets need to be maintained by resources
moving in the network. In order to perform maintenance the assets have to be
shut down from time to time thus reducing the system capacity for those time
periods. The objective is to maximize the total transported product by aligning
the maintenance activities appropriately. Combining flow maximization and
maintenance scheduling, taking into account the interaction between utilization
of network assets and their maintenance demand gives rise to a rich and
challenging class of optimization problem which we call the network maintenance
problem.
We formally introduce the problem and present a mixed integer programming
formulation. Next, we consider the case of a single commodity and a single
maintenance resource when the network is a single path. We describe polynomial
time algorithms which, under some simplifying assumptions, solve the single path
case to optimality. |