Optimal valve location in long oil pipelines

We address the valve location problem, one of the basic problems in design of long oil pipelines. Whenever a pipeline is depressurized, the shutoff valves block the oil flow and seal the damaged part of the pipeline. Thus, the quantity of oil possibly contaminating the area around the pipeline is determined by the volume of the damaged section of the pipeline between two consecutive valves. Then, ecologic damage can be quantified by the amount of leaked oil and the environmental characteristics of the accident area. Given a pipe network together with environmental characteristics of the area, and given a number of valves to be installed, the task is to find a valve location minimizing the maximal possible environmental damage. In this paper we present a complete framework for fast computing of an optimal valve location.