×

zbMATH — the first resource for mathematics

Genetic algorithms for scheduling devices operation in a water distribution system in response to contamination events. (English) Zbl 1292.90329
Hao, Jin-Kao (ed.) et al., Evolutionary computation in combinatorial optimization. 12th European conference, EvoCOP 2012, Málaga, Spain, April 11–13, 2012. Proceedings. Berlin: Springer (ISBN 978-3-642-29123-4/pbk). Lecture Notes in Computer Science 7245, 124-135 (2012).
Summary: This paper heuristically tackles a challenging scheduling problem arising in the field of hydraulic distribution systems in case of a contamination event, that is, optimizing the scheduling of a set of tasks so that the consumed volume of contaminated water is minimized. Each task consists of manually activating a given device, located on the hydraulic network of the water distribution system. In practice, once contamination has been detected, a given number of response teams move along the network to operate each device on site. The consumed volume of contaminated water depends on the time at which each device is operated, according to complex hydraulic laws, so that the value associated to each schedule must be evaluated by a hydraulic simulation.
We explore the potentials of Genetic Algorithms as a viable tool for tackling this optimization-simulation problem. We compare different encodings and propose ad hoc crossover operators that exploit the combinatorial structure of the feasible region, featuring hybridization with Mixed Integer Linear Programming.
Computational results are provided for a real life hydraulic network of average size, showing the effectiveness of the approach. Indeed, we greatly improve upon common sense inspired solutions which are commonly adopted in practice.
For the entire collection see [Zbl 06026017].

MSC:
90C59 Approximation methods and heuristics in mathematical programming
90B35 Deterministic scheduling theory in operations research
90B90 Case-oriented studies in operations research
Full Text: DOI