Αλγόριθμος αναζήτησης μέσω στοχευμένης διαδρομής για τη βελτιστοποίηση δικτύων διανομής νερού

Abstract

The concept of optimization is examined in detail in this dissertation. Particular emphasis is placed on its applications to the problem of the optimal dimensioning of pipes of looped water distribution networks. Analysis of the existing methods is attempted and the conditions for their application are considered. It is apparent that their efficiency depends on the careful calibration of their parameters, which may change in any attempt to solve a new network. In addition, the main method that has been adopted for the selection of solutions that do not violate the constraints of the problem is the penalty function, which should also be appropriately chosen. One way to calibrate the parameters and the penalty function of existing methods is to have a good prior knowledge of the search space, which is generally not available on a new network. The execution of many tests seems to be the only safe way to configure them, which leads to unnecessary network solutions and therefore, delays.The main purpose of the dissertation is to develop a new optimization algorithm that is free from the problem of parameters and penalty function calibration. The new algorithm is called Targeted Path Search since it searches for the optimal in specific paths of water in the network. The optimization process is driven by independent subroutines which evolve a random initial solution, while information is gathered from the neighboring search space. The reliability and effectiveness of the new algorithm is checked using three known networks of the literature, namely the two-loop, Hanoi and Balerma networks.While in studies of looped water distribution networks the velocity of water in the pipes is taken into account, the literature does not offer any reliable optimization method that produces solutions which respect velocity restrictions. To make up for this shortcoming, a variation of the original algorithm was designed, called Targeted Path Search with Velocity Restrictions. In this variant, the philosophy of the original algorithm is preserved. The variant is applied to the same networks as the original algorithm. The resulting solutions show that velocity restrictions are not violated indeed.

Στα πλαίσια της παρούσας διατριβής εξετάζεται κατ’ αρχήν το αντικείμενο της βελτιστοποίησης. Ειδικότερα, έμφαση δίνεται στο πρόβλημα της βέλτιστης διαστασιολόγησης αγωγών των βροχωτών δικτύων διανομής νερού. Γίνεται ανασκόπηση των υφιστάμενων μεθόδων και κρίνονται οι προϋποθέσεις εφαρμογής τους. Σχολιάζεται η αποδοτικότητα των διαφόρων μεθόδων και η ανάγκη για προσεκτικές ρυθμίσεις των παραμέτρων τους, οι οποίες ενδεχομένως να μεταβάλλονται σε κάθε προσπάθεια επίλυσης ενός νέου δικτύου. Το ίδιο ισχύει για την αντιμετώπιση των περιορισμών στη βελτιστοποίηση, μέσω συναρτήσεων ποινής, των οποίων εξετάζεται η εφαρμογή σε προβλήματα δικτύων διανομής νερού. Διαπιστώνεται ότι η ρύθμιση των παραμέτρων ποινής γίνεται μόνο μέσω πολλαπλών δοκιμών με αποτέλεσμα άσκοπες ενδιάμεσες επιλύσεις του δικτύου.Βασικός σκοπός της παρούσας διατριβής είναι η ανάπτυξη ενός νέου αλγορίθμου βελτιστοποίησης που να είναι απαλλαγμένος από το πρόβλημα της ρύθμισης παραμέτρων και της συνάρτησης ποινής. Ο νέος αλγόριθμος ονομάζεται Αναζήτηση μέσω Στοχευμένης Διαδρομής επειδή αναζητεί το βέλτιστο σε συγκεκριμένες διαδρομές του νερού με βάση τα υδραυλικά χαρακτηριστικά του δικτύου. Η διαδικασία της βελτιστοποίησης οδηγείται από ανεξάρτητες υπορουτίνες οι οποίες εξελίσσουν μία τυχαία αρχική λύση, ενώ λαμβάνονται πληροφορίες από τον γειτονικό χώρο αναζήτησης. Για να ελεγχθεί η αξιοπιστία και η αποτελεσματικότητα του νέου αλγορίθμου, δοκιμάζεται σε τρία γνωστά δίκτυα της βιβλιογραφίας και συγκεκριμένα στα δίκτυα δύο βρόχων, Ανόι και Μπαλέρμα.Ενώ σε μελέτες βροχωτών δικτύων διανομής νερού η ταχύτητα του νερού στους αγωγούς λαμβάνεται υπόψιν, στη βιβλιογραφία το πρόβλημα εμφανίζεται συνήθως χωρίς περιορισμούς ταχύτητας. Στις ελάχιστες μεθόδους που εφαρμόζονται στο πρόβλημα με περιορισμούς ταχύτητας, ο τρόπος εφαρμογής δε φαίνεται να είναι ιδιαίτερα αποδοτικός. Για να καλυφθεί αυτή η έλλειψη, παρουσιάζεται μία παραλλαγή του αρχικού αλγορίθμου η οποία ονομάζεται Αναζήτηση μέσω Στοχευμένης Διαδρομής με Περιορισμούς Ταχύτητας. Στην παραλλαγή αυτή, διατηρείται η φιλοσοφία του αρχικού αλγορίθμου. Η παραλλαγή εφαρμόζεται στα ίδια δίκτυα με τον αρχικό αλγόριθμο. Οι λύσεις που προκύπτουν δείχνουν ότι πράγματι οι περιορισμοί ταχύτητας δεν παραβιάζονται.