Publication Date:
2014-10-05
Description:
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. Extensive 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. Content Type Journal Article Pages - DOI 10.3233/AIC-140638 Authors Marco Gavanelli, ENDIF, Università di Ferrara, Via Saragat, 1, 44122 Ferrara, Italy. E-mails: marco.gavanelli@unife.it, maddalena.nonato@unife.it, andrea.peano@unife.it, stefano.alvisi@unife.it, marco.franchini@unife.it Maddalena Nonato, ENDIF, Università di Ferrara, Via Saragat, 1, 44122 Ferrara, Italy. E-mails: marco.gavanelli@unife.it, maddalena.nonato@unife.it, andrea.peano@unife.it, stefano.alvisi@unife.it, marco.franchini@unife.it Andrea Peano, ENDIF, Università di Ferrara, Via Saragat, 1, 44122 Ferrara, Italy. E-mails: marco.gavanelli@unife.it, maddalena.nonato@unife.it, andrea.peano@unife.it, stefano.alvisi@unife.it, marco.franchini@unife.it Stefano Alvisi, ENDIF, Università di Ferrara, Via Saragat, 1, 44122 Ferrara, Italy. E-mails: marco.gavanelli@unife.it, maddalena.nonato@unife.it, andrea.peano@unife.it, stefano.alvisi@unife.it, marco.franchini@unife.it Marco Franchini, ENDIF, Università di Ferrara, Via Saragat, 1, 44122 Ferrara, Italy. E-mails: marco.gavanelli@unife.it, maddalena.nonato@unife.it, andrea.peano@unife.it, stefano.alvisi@unife.it, marco.franchini@unife.it Journal AI Communications Online ISSN 1875-8452 Print ISSN 0921-7126
Print ISSN:
0921-7126
Electronic ISSN:
1875-8452
Topics:
Computer Science
Permalink