Path relinking based intensification strategies for a simulation-optimization scheduling problem arising in hydroinformatics

摘要

Water contamination events in a urban hydraulic network can be handled by operating two types of network devices: valves, to divert flow, and hydrants, to dispel flow. No remote control can activate these devices, which must be operated on site, therefore teams of technicians have to move from device to device on the city streets. The response to the contamination corresponds to a feasible schedule of the devices' activation times, which can be modelled as a multiple Travelling Salesman Problem; the quality of the schedule is the volume of contaminated water consumed by the users until water quality returns to safety levels. This quantity is highly sensitive to the schedule and is computed by way of a computational demanding hydraulic simulation, which takes about 5 seconds for the Ferrara's hydraulic network serving around 130'000 citizens. Previous studies proved that minimizing the makespan, as it would be intuitive in case of emergency, yields worse solutions than random approaches. Genetic Algorithms were proposed to optimize the schedules, however they converge to local optima, depending on the initial population. We propose to apply Path Relinking to explore the space between pairs of local optima; the experiments showed that this technique improves the local best. This work is a follow up of what presented at AIxIA 2015, enpowered with a light introduction to Path Relinking and its applications. Moreover, the experimental campaign has been extended on a larger set of scenarios, i.e. 42 contamination scenarios, to gain more insight into the performance of the proposed methodology.