The network maintenance problem on an arc with uncapacitated repair

Abstract

The network maintenance problem is motivated by the need to maintain infrastructure networks over time. We consider networks in which a commodity is transported between 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 thus reducing the system capacity. The objective is to maximise the total throughput by aligning the maintenance activities efficiently. In this paper, we study a special case of the network maintenance problem where the network consists of a single arc connecting an origin to a destination. Furthermore, there is no restriction on the amount of repair if the resource is to perform maintenance in a time period. <br/> This problem is of interest for the following reasons. Firstly, it generalises variants of the lot-sizing problem and the warehouse problem, both of which have been well-studied in the literature. Secondly, we hope that understanding this special case will be useful in tackling more general variants of the network maintenance problem. <br/> In this paper, we present a mixed integer linear programming formulation. We then show that a special class of feasible solutions, called Maximum Flow Order Up (MFOU) solutions, contains at least one optimal solution. Based on this result, we introduce an alternative integer linear programming formulation with only five decision variables. As a consequence, the optimal objective function value for any instance of the problem can be obtained in polynomial time.