The aim of the most network flow interdiction problems is to minimize the maximum flow of goods through a capacitated network. In this paper, we introduce a variation of this problem in which to each arc is associated a given reliability. Based on this assumption, an arc could be used in the network if its corresponding reliability is greater than a given threshold. Moreover, in order to increase the flow through the network, we allow to repair or develop the arcs with the presence of limitation on the maximum available budget. To solve the model, we use a comprehensive enumeration to identify all interdiction strategies. Moreover, in order to reduce the computing time, we extend two heuristics to create high quality initial solutions. Finally, particle swarm optimization metaheuristic algorithm is applied to reach high quality solutions within a reasonable running time.

Keywords