Future electrical power networks should support the integration of distributed renewable energy sources, which may be contributed by individual customers instead of utility companies. Such a demand poses new challenges to power distribution network design, since the energy generation, energy consumption, and power flow all become highly dynamic. An inappropriate network design may not only waste much energy in power distribution but also incur high cost in network construction. In this thesis, we study the optimal network design problem under a dynamic current injection model. We investigate different optimization methods to obtain the optimal network structure that can better adapt to dynamic energy generation/consumption requirements and is more efficient than traditional tree-structured power networks. By predicting users' potential load in the network, network design with our method results in significant energy saving. / Graduate / 0984

Περιληπτικά, στη συγκεκριμένη διδακτορική διατριβή μελετήθηκαν οι θεωρίες της βελτιστοποίησης και των κατανεμημένων αλγορίθμων με σκοπό την χρήση τους σε ένα διομότιμο σύστημα σύγχρονου διαμοιρασμού αντικειμένων. Επιπλέον μελετήθηκε το περιβάλλον και οι συνθήκες λειτουργίας ενός τέτοιου συστήματος. καθώς και τα χαρακτηριστικά του. Αποτέλεσμα της μελέτης αυτής είναι η εξαγωγή συμπερασμάτων σχετικά με τις απαιτήσεις που πρέπει να πληρούνται κατά τη δημιουργία ενός διομότιμου συστήματος σύγχρονου διαμοιρασμού αντικειμένων και οι τεχνικοί στόχοι που πρέπει αυτό να ικανοποιεί. Με αυτά τα κριτήρια σχεδιάστηκε η αρχιτεκτονική του συστήματος και ορίστηκαν τα προβλήματα που πρέπει να επιλυθούν. Για την λειτουργία ενός τέτοιου συστήματος ορίστηκαν οι ακόλουθες απαιτήσεις: • Μεγιστοποίηση της χρήσης από το σύστημα του διαθέσιμου εύρους ζώνης των συμμετεχόντων κόμβων. Φυσικά, οι κόμβοι έχουν ετερογενείς τιμές του διαθέσιμου εύρους ζώνης και, μάλιστα, με μεγάλη διασπορά. • Ελαχιστοποίηση της καθυστέρησης από τη στιγμή δημιουργίας ενός αντικειμένου μέχρι τον διαμοιρασμό του σε κάθε συμμετέχοντα κόμβο. • Ομοιόμορφη διαρκής κατανομή του συνολικού εύρους ζώνης του συστήματος στους συμμετέχοντες κόμβους. • Ανεκτικότητα του συστήματος στη δυναμική συμπεριφορά των χρηστών που προκαλείται από εισόδους και εξόδους των χρηστών στο σύστημα σε μη προκαθορισμένες χρονικές στιγμές. • Ικανότητα κλιμάκωσης του συστήματος σε αριθμό συμμετεχόντων χρηστών κάτι που επάγει την κατανεμημένη διαχείριση του συστήματος. • Προσαρμογή του σχεδιαζόμενου συστήματος στην κίνηση του δικτύου στο οποίο αυτό επικάθεται και ανεκτικότητά του στις μεταβολές του εύρους ζώνης των συμμετεχόντων κόμβων. • Ελαχιστοποίηση του φορτίου το οποίο εισάγει η λειτουργία του συστήματος στο δίκτυο. Για τη λειτουργία του προτεινόμενου συστήματος απαιτείται η δημιουργία ενός γράφου διασύνδεσης. Ως γράφος διασύνδεσης ορίζεται ο γράφος που προκύπτει αν κάθε κόμβος συνδεθεί με ένα μικρό υποσύνολο των συμμετεχόντων κόμβων που ονομάζονται και γείτονες του κόμβου. Για την ικανοποίηση των προαναφερθεισών απαιτήσεων. μελετήθηκαν τα χαρακτηριστικά του γράφου διασύνδεσης και προέκυψε ότι κάθε κόμβος: α) πρέπει να έχει γείτονες με όσο το δυνατόν μικρότερη δικτυακή καθυστέρηση μεταξύ τους, β) πρέπει να έχει αριθμό εξερχόμενων συνδέσεων ανάλογο με το εύρος ζώνης του, γ) οι συνδέσεις αυτές πρέπει να κατανέμονται ομοιόμορφα στους συμμετέχοντες κόμβους για την ικανοποίηση των αναγκών όλων των κόμβων, δ) οι κόμβοι με σχετικά μεγάλο εύρος ζώνης πρέπει να ομαδοποιούνται στο γράφο με σκοπό την γρήγορη αρχικά διάχυση του αντικειμένου και ε) ο γράφος διασύνδεσης πρέπει να αναδιατάσσεται δυναμικά έτσι ώστε να διατηρεί τις ιδιότητες αυτές στο δυναμικό δικτυακό περιβάλλον που επικάθεται και για δυναμική συμπεριφορά των συμμετεχόντων κόμβων. Για την ικανοποίηση αυτών των τεχνικών στόχων αναπτύχθηκε μία δομή του γράφου που ικανοποιεί αυτά τα χαρακτηριστικά. Η βελτιστοποίηση του γράφου γίνεται μέσω αλγορίθμων κατά την λειτουργία των οποίων κάθε κόμβος επιλέγει περιοδικά ένα τυχαίο κόμβο ο οποίος είναι γείτονάς του στον γράφο διασύνδεσης. Μεταξύ των δύο αυτών κόμβων εκτελείται ανακατανομή των γειτόνων τους με σκοπό την εξισορρόπηση του αριθμού των γειτόνων που κάθε ένας από αυτούς διαθέτει. αλλά και την ελαχιστοποίηση της μέσης καθυστέρησης που έχουν αθροιστικά οι κόμβοι από τους γείτονές τους. Οι αλλαγές στον γράφο διασύνδεσης που προκύπτουν από κάθε εκτέλεση του αλγορίθμου αυτού μεταβάλλουν και τους γείτονες ενός υποσυνόλου κόμβων εκτός των δύο συμμετεχόντων στον αλγόριθμο εναλλαγής. Οι αλλαγές αυτές επιφέρουν άλλες αλλαγές με την σειρά τους και έτσι προκύπτει τελικά ένας γράφος διασύνδεσης όπου κάθε κόμβος έχει τον προκαθορισμένο αριθμό γειτόνων και. παράλληλα. ελαχιστοποιείται το άθροισμα των μέσων δικτυακών καθυστερήσεων που έχουν οι συμμετέχοντες κόμβοι με τους γείτονές τους. Για τον διαμοιρασμό του αντικειμένου ο δημιουργός του το τεμαχίζει σε τεμάχια (μπλοκ). Τα τεμάχια προωθούνται σε ένα πολύ μικρό σύνολο κόμβων και αποτελούν τις λογικές μονάδες δεδομένων που ανταλλάσσονται μεταξύ των κόμβων. Σκοπός είναι ο διαμοιρασμός του κάθε τεμαχίου σε κάθε κόμβο μέσα σε ένα προκαθορισμένο χρονικό διάστημα. Για την ανταλλαγή τεμαχίων μεταξύ των γειτόνων του γράφου διασύνδεσης του προς διαμοιρασμού αντικειμένου μεταξύ των συμμετεχόντων κόμβων αναπτύχθηκε ένας Κατανεμημένος Χρονοπρογραμματιστής Ανταλλαγής Τεμαχίων (ΚΧΑΤ). Τεχνικοί στόχοι της ανάπτυξης του ΚΧΑΜ αποτέλεσαν α) ο χρονισμός διαπραγμάτευσης αποστολής τεμαχίων μεταξύ κάθε αποστολέα και παραλήπτη, β) η γρήγορη διάδοση πρόσφατα παραγόμενων τεμαχίων και σπάνιων σε μία γειτονία του γράφου διασύνδεσης (τεμάχια που δημιουργήθηκαν μεταγενέστερα από άλλα ευνοούνται από το χρονοπρογραμματιστή αρχικά για την επιτυχή και γρήγορη διάδοσή τους σε μία κρίσιμη μάζα από κόμβους), γ) η τροφοδότηση όλων των κόμβων με ομοιόμορφο και σταθερό ρυθμό, δ) η προτεραιότητα σε κόμβους με μεγάλο εύρος ζώνης, ε) η αποφυγή μετάδοσης του ίδιου τεμαχίου από δύο αποστολείς προς τον ίδιο παραλήπτη και στ) η αποφυγή μιας κατάστασης όπου αποστολέας και παραλήπτης δεν έχουν τεμάχια προς ανταλλαγή. Ο χρονισμός του ΚΧΑΜ που αναπτύχθηκε αποτελείται από τρείς φάσεις. Στην πρώτη φάση που εκτελείται περιοδικά από κάθε αποστολέα εκδίδεται και αποστέλλεται στους πιθανούς παραλήπτες ένα σύνολο από «κουπόνια» μεγέθους ανάλογου με το εύρος ζώνης του αποστολέα. Στη δεύτερη φάση ο εκάστοτε παραλήπτης ζητά προκαταβολικά ένα τεμάχιο στην περίπτωση που επιλεγεί από τον αποστολέα για μετάδοση τεμαχίου. Στην τρίτη φάση ο αποστολέας επιλέγει τον παραλήπτη ακριβώς πριν την μετάδοση κάθε τεμαχίου και αποστέλλει το τεμάχιο που έχει ζητηθεί. Ο αλγόριθμος ο οποίος προτείνεται για τη δημιουργία κουπονιών έχει ως στόχο τη μεγιστοποίηση της χρήσης του εύρους ζώνης όλων των κόμβων και την ικανοποίηση των αναγκών κάθε συμμετέχοντα κόμβου. Είναι αυτός που, στην ουσία, καθορίζει τις ροές δεδομένων μεταξύ των γειτόνων του γράφου διασύνδεσης. Η χρησιμότητά του αναδεικνύεται σε περιπτώσεις όπου ο ρυθμός αναπαραγωγής του προς διαμοιρασμό αντικειμένου είναι παρόμοιος με το μέσο εύρος ζώνης του συστήματος. Οι απαιτήσεις του αλγορίθμου ζήτησης τεμαχίων μοντελοποιούνται μέσω της γραμμικής βελτιστοποίησης και διασφαλίζεται η γρήγορη και αποτελεσματική διάχυση των τεμαχίων ελαχιστοποιώντας την ύπαρξη ανενεργών πόρων. Τέλος, ο αλγόριθμος επιλογής γείτονα είναι αυτός που ρυθμίζει την ομοιόμορφη κατανομή του εύρους ζώνης στους συμμετέχοντες κόμβους, αλλά και δίνει προτεραιότητα στους κόμβους με μεγάλο εύρος ζώνης έτσι ώστε να επιτευχθεί ο γρήγορος διαμοιρασμός κάθε τεμαχίου και η ελαχιστοποίηση της καθυστέρησης του συστήματος. Η αξιολόγηση της προτεινόμενης αρχιτεκτονικής, της τοπολογίας του γράφου διασύνδεσης και του ΚΧΑΜ, έγινε μέσω προσομοίωσης σε προσομοιωτή δικτυακών συστημάτων. Μοντελοποιήθηκε το εύρος ζώνης των συμμετεχόντων κόμβων και δικτυακές καθυστερήσεις χρησιμοποιώντας πραγματικά δεδομένα από διομότιμα συστήματα.. Το σύστημα που αναπτύχθηκε μοντελοποιήθηκε πλήρως σε επίπεδο πακέτου. Εξετάστηκαν αρκετά σενάρια αξιολόγησης του συστήματος τα οποία, μεταξύ άλλων, περιλαμβάνουν, ευαισθησία του συστήματος σε παραμέτρους των προτεινόμενων αλγορίθμων, δυναμικά σενάρια όσον αφορά τη συμπεριφορά των χρηστών και του δικτύου και σενάρια εύρεσης των ορίων του προτεινόμενου συστήματος. Η αξιολόγηση των αποτελεσμάτων έδειξε ότι ικανοποιούνται οι απαιτήσεις που τέθηκαν για τη δημιουργία του συστήματος, καθώς και βελτίωση της συμπεριφοράς του συστήματος σε σχέση με αντίστοιχα συστήματα της διεθνούς βιβλιογραφίας με τα οποία συγκρίθηκε. / Peer-to-peer live streaming is a network application, where peers (users) contribute their upload bandwidth for the real time distribution of a video stream. The objective of this work is the optimization of this data diffusion with a distributed and self-organized architecture. Peers have heterogeneous and dynamic uploading bandwidth. This fact combined with the characteristics of the topology of the underlying network and the dynamic traffic conditions e.g. latency create a volatile and complex environment for P2P live streaming delivery, which strongly affect the success of a P2P system measured by a number of performance metrics. The first important factor is the uploading bandwidth utilization that corresponds to the ability of the system to exploit as much as possible of the overall uploading bandwidth of the participating peers. The maximization of the upload bandwidth utilization increases the video playback delivery rate and ensures the stability of the distribution. Equally important parameter is the setup time defined as the time interval between the generation of a block from an origin server and its delivery to every peer in the system. Furthermore, a P2P live streaming system has to remain stable and its delivery rate must remain high in a dynamic environment, where peers arrive and depart randomly. .Finally, fairness among nodes indicates the ability of the system to distribute continuously and uniformly the aggregate uploading bandwidth to the participating peers. This ensures that every peer will acquire a percentage of blocks above a critical threshold for an “affordable” video playback regardless the aggregate uploading bandwidth is not sufficient for the complete delivery of the video stream. For the development of the proposed system is required the creation of a content diffusion overlay (CDO). For every peer, CDO defines the graph which includes the subset of adjacent participating peers (neighbors) that are connected with it. For the fulfillment of the aforementioned requirements CDO must ensure the following features: • Each peer must have neighbors close to it in the underlying network. • The number of the neighbors has to be proportional to its upload bandwidth. • The number of the neighbors from which each peer receives data has to be balanced among participating peers. • In the CDO, peers with high upload bandwidth must be clustered for the fast diffusion of each video block to a critical mass of peers. • The CDO has to be adapted dynamically according to the underlying network conditions and the behavior of the participating peers. The optimization of the CDO and the fulfillment of these technical objectives is done with the use of a distributed optimization and maintenance algorithm (DOMA) that reorganizes the “neighborhoods” of CDO and so it keeps almost stable the attributes of the graph during peer arrivals and departures. It also ensures the high levels of bandwidth utilization. The algorithm based on a cost function, denoted as energy function between two nodes and can represent for example the network latency between two nodes. DOMA is executed between two neighbors that we note as initiators and their neighbors that we called satellites. Its purpose is to minimize the sum of the energy functions between initiators and satellites under the constraints on the number of neighbors that the graph structure implies. In p2p live streaming every user and/or content provider that generates a multimedia block stream is indicated as source. A P2P block exchange scheduling algorithm (P2P-BESA) ensures the distribution of each block to every user and with low latency. P2P-BESA focuses on the following properties: • The consistent message sequence between two peers for the negotiation of the transmission of a video block. • The fast diffusion of blocks that are recently produced. • The transmission of blocks to every peer with a stable and equal rate among the peers. • The prioritization of transmission to peers with relatively high upload bandwidth. • The avoidance of block retransmission. • The avoidance of content bottleneck between two peers. The decision for the transmission of a block is done in three phases. In the first phase, every peer acting as block sender issues tokens periodically proportional with its upload bandwidth. This ensures the maximization of the upload bandwidth of the participating peers and determines the data flows between participating peers. In the second phase, each peer periodically is acting as receiver and requests a different block from each one of its potential senders. As potential senders we define the set of peers that have recently sent a token to it. This algorithm ensures the fast and complete diffusion of every block by also minimizing the idle bandwidth resources in the systems. Finally in the third phase, before the transmission of each block each sender selects the destination peer according to the blocks that it misses and its upload bandwidth capabilities. The evaluation of the proposed system is done with a network simulator. A detailed packet level P2P live streaming simulator models the bandwidth of the participating peers, the network latency between them, peer arrivals and departures and finally dynamic changes in the underlying network. The evaluation of the system shows that: • It achieves very high levels of bandwidth utilization (around 95%) • low latency in the diffusion of its video block (2-4 seconds) • system is almost immune to peer arrivals and departures • very tolerant to underlying network changes Finally the proposed system outperforms when it is compared with other recently proposed systems in the international bibliography.

O desenho e a gestão de uma cadeia de suprimentos apresentam-se, hoje, como um dos problemas mais importantes e de difícil resolução encontrado pelos gestores. A gestão da cadeia de suprimentos é uma das áreas de maior interesse da Pesquisa Operacional aplicada, buscando determinar a melhor estratégia de produção, transporte e estoque com menor custo e tempo possíveis. Esta dissertação apresenta os resultados de um estudo que objetivou implementar e avaliar uma heurística baseada em Busca Tabu para otimização de uma rede de cadeia de suprimentos. Para tanto, foi utilizada uma modelagem single-source proposta por Farias e Borenstein (2012). O problema foi resolvido com uma adaptação do método de Lee e Kwon (2010), buscando por meio de operações de troca de centros de distribuição (CDs) e arcos encontrar a configuração de menor custo para uma rede de cadeia de suprimentos. Foram resolvidas as 22 instâncias propostas por Farias e Borenstein (2012) e os resultados comprovam que, para esses cenários, o método aplicado teve um bom desempenho computacional, obtendo resultados com uma redução de 81,03% no tempo médio de processamento; contudo, as soluções obtidas pela heurística apresentaram custos médios 4,98% superiores aos resultados ótimos. Por fim, o problema foi resolvido para outras quatro instâncias com características reais, comprovando a eficiência da heurística para problemas de grande escala, visto que todas as soluções foram obtidas em um tempo inferior a 2 minutos de processamento. / The design and supply chain management are currently one of the most important and difficult problems encountered by business managers. Supply chain management is one of the most engaging areas in applied Operations Research, which seeks to determine the best strategy regarding production, shipping and storage at the lowest cost and shortest time possible. This thesis shows the results of a research that aimed to implement and evaluate a heuristic based on Tabu Search to optimize a supply chain network. For this purpose, a single-source model proposed by Farias and Borenstein (2012) was used. The problem was solved by adapting the Lee and Kwon method (2010), exchanging distribution centers (DCs) and arcs, to find the lowest cost for a supply chain network. Twenty two instances proposed by Farias and Borenstein (2012) were resolved and the results indicate that, for these scenarios, the applied method had a good computational performance, getting results with 81.03% of reduction in the average processing time. However, there was an increase of 4.98% in the average cost of the solutions obtained through the heuristic method when compared to the optimal results. Finally, the problem was solved for four other instances with real features, proving the efficiency of the heuristic for large-scale problems, since all solutions were obtained in a time less than 2 minutes of processing.

O desenho e a gestão de uma cadeia de suprimentos apresentam-se, hoje, como um dos problemas mais importantes e de difícil resolução encontrado pelos gestores. A gestão da cadeia de suprimentos é uma das áreas de maior interesse da Pesquisa Operacional aplicada, buscando determinar a melhor estratégia de produção, transporte e estoque com menor custo e tempo possíveis. Esta dissertação apresenta os resultados de um estudo que objetivou implementar e avaliar uma heurística baseada em Busca Tabu para otimização de uma rede de cadeia de suprimentos. Para tanto, foi utilizada uma modelagem single-source proposta por Farias e Borenstein (2012). O problema foi resolvido com uma adaptação do método de Lee e Kwon (2010), buscando por meio de operações de troca de centros de distribuição (CDs) e arcos encontrar a configuração de menor custo para uma rede de cadeia de suprimentos. Foram resolvidas as 22 instâncias propostas por Farias e Borenstein (2012) e os resultados comprovam que, para esses cenários, o método aplicado teve um bom desempenho computacional, obtendo resultados com uma redução de 81,03% no tempo médio de processamento; contudo, as soluções obtidas pela heurística apresentaram custos médios 4,98% superiores aos resultados ótimos. Por fim, o problema foi resolvido para outras quatro instâncias com características reais, comprovando a eficiência da heurística para problemas de grande escala, visto que todas as soluções foram obtidas em um tempo inferior a 2 minutos de processamento. / The design and supply chain management are currently one of the most important and difficult problems encountered by business managers. Supply chain management is one of the most engaging areas in applied Operations Research, which seeks to determine the best strategy regarding production, shipping and storage at the lowest cost and shortest time possible. This thesis shows the results of a research that aimed to implement and evaluate a heuristic based on Tabu Search to optimize a supply chain network. For this purpose, a single-source model proposed by Farias and Borenstein (2012) was used. The problem was solved by adapting the Lee and Kwon method (2010), exchanging distribution centers (DCs) and arcs, to find the lowest cost for a supply chain network. Twenty two instances proposed by Farias and Borenstein (2012) were resolved and the results indicate that, for these scenarios, the applied method had a good computational performance, getting results with 81.03% of reduction in the average processing time. However, there was an increase of 4.98% in the average cost of the solutions obtained through the heuristic method when compared to the optimal results. Finally, the problem was solved for four other instances with real features, proving the efficiency of the heuristic for large-scale problems, since all solutions were obtained in a time less than 2 minutes of processing.

O desenho e a gestão de uma cadeia de suprimentos apresentam-se, hoje, como um dos problemas mais importantes e de difícil resolução encontrado pelos gestores. A gestão da cadeia de suprimentos é uma das áreas de maior interesse da Pesquisa Operacional aplicada, buscando determinar a melhor estratégia de produção, transporte e estoque com menor custo e tempo possíveis. Esta dissertação apresenta os resultados de um estudo que objetivou implementar e avaliar uma heurística baseada em Busca Tabu para otimização de uma rede de cadeia de suprimentos. Para tanto, foi utilizada uma modelagem single-source proposta por Farias e Borenstein (2012). O problema foi resolvido com uma adaptação do método de Lee e Kwon (2010), buscando por meio de operações de troca de centros de distribuição (CDs) e arcos encontrar a configuração de menor custo para uma rede de cadeia de suprimentos. Foram resolvidas as 22 instâncias propostas por Farias e Borenstein (2012) e os resultados comprovam que, para esses cenários, o método aplicado teve um bom desempenho computacional, obtendo resultados com uma redução de 81,03% no tempo médio de processamento; contudo, as soluções obtidas pela heurística apresentaram custos médios 4,98% superiores aos resultados ótimos. Por fim, o problema foi resolvido para outras quatro instâncias com características reais, comprovando a eficiência da heurística para problemas de grande escala, visto que todas as soluções foram obtidas em um tempo inferior a 2 minutos de processamento. / The design and supply chain management are currently one of the most important and difficult problems encountered by business managers. Supply chain management is one of the most engaging areas in applied Operations Research, which seeks to determine the best strategy regarding production, shipping and storage at the lowest cost and shortest time possible. This thesis shows the results of a research that aimed to implement and evaluate a heuristic based on Tabu Search to optimize a supply chain network. For this purpose, a single-source model proposed by Farias and Borenstein (2012) was used. The problem was solved by adapting the Lee and Kwon method (2010), exchanging distribution centers (DCs) and arcs, to find the lowest cost for a supply chain network. Twenty two instances proposed by Farias and Borenstein (2012) were resolved and the results indicate that, for these scenarios, the applied method had a good computational performance, getting results with 81.03% of reduction in the average processing time. However, there was an increase of 4.98% in the average cost of the solutions obtained through the heuristic method when compared to the optimal results. Finally, the problem was solved for four other instances with real features, proving the efficiency of the heuristic for large-scale problems, since all solutions were obtained in a time less than 2 minutes of processing.

Esta dissertação apresenta uma metodologia de otimização do fluxo de potência em sistemas elétricos de subtransmissão utilizando duas técnicas da Computação Evolutiva, os Algoritmos Genéticos e as Estratégias Evolutivas. A metodologia decompõe o problema em duas partes e o trata seqüencialmente. A primeira parte procede com a otimização do fluxo de potência ativa e a segunda com a otimização do fluxo de potência reativa. São apresentadas as características e estruturas básicas dos Algoritmos Genéticos e das Estratégias Evolutivas. A técnica dos Algoritmos Genéticos é implementada no modelo de otimização do fluxo de potência ativa e a técnica das Estratégias Evolutivas no modelo de otimização do fluxo de potência reativa. As variáveis de controle dos modelos desenvolvidos são, respectivamente, os estados dos dispositivos de seccionamento e os níveis de tensão dos barramentos dos pontos de fronteira, associadas ao sistema analisado. Analisam-se os sistemas elétricos de subtransmissão que contêm múltiplos pontos de fronteira (conexão) com a Rede Básica e diversas possibilidades de configuração operativa. A metodologia proposta é aplicada a um sistema elétrico de subtransmissão real a fim de minimizar o custo dos encargos de uso dos sistemas de transmissão. Os resultados obtidos mostram a eficácia dos algoritmos desenvolvidos na busca das soluções desejadas. / This dissertation presents a power flow optimization methodology on subtransmission electric systems using two techniques of Evolutionary Computation, namely the Genetic Algorithms and the Evolution Strategies. The methodology splits the problem into two parts and treats it separately. On the first step it proceeds to optimize the active power flow and on the second step to optimize the reactive power flow. Characteristics and basic structures of the Genetic Algorithms and the Evolution Strategies are shown. The Genetic Algorithms technique is implemented on the active power flow optimization model and the Evolution Strategies technique on the reactive power flow optimization model. The control variables of developed models are, respectively, the switch states and the border point bar voltage levels, associated to the analyzed system. The subtransmission electric systems that have multiple border (connection) points to the Basic Network and many operative configuration possibilities are analyzed. The proposed methodology is applied to a real subtransmission electric system in order to minimizes the transmission system use duty costs. The obtained results show the efficacy of the developed algorithms in the search of desired solutions.

Interest has been growing in the interaction of various power demand transformations, such as demand side management (DSM) and voltage control, with the power demand. Initial studies have highlighted the need for a better understanding of the power demand of low voltage (LV) residential networks. Furthermore, it is expected that future alteration of the residential appliance mixture, because of the advances in technology, will have an impact on both the demand curve as well as the electrical characteristics. This thesis presents a study of the impact of current and future household load on the power demand curve and the network operation. In order to achieve this, a bottom-up load modelling tool was developed to create LV detailed demand profiles that include not only the active and reactive power demand, but their electrical characteristics as well. The methodology uses a Markov chain Monte Carlo approach to generate residential LV demand profiles taking into account the user activity and behaviour to represent UK population. An appliance database has also been created which corresponds to the UK residential appliance mixture in order to calculate more accurately the power demand. The main advantages of the approach presented here are the flexibility in altering the type and number of the appliances that populate a household and how easily it can be adapted to a different population, location and climate. The tool is used to investigate the impact of scenarios that simulate future load replacement and the network behaviour under certain methods of demand control, implementation of DSM and control of voltage on the secondary of the LV transformer. The algorithm that was developed to apply the DSM actions on the power demand focused on the management of individual loads. The drivers used in this approach were the financial and environmental benefit of customers and the increase in the quality of the network operation. The control of the voltage as a method for power reduction takes into account the voltage dependence of the demand. The primary target is to quantify the benefits of this strategy either in combination with DSM for higher power reduction during the peak hours or on the current network as a quicker, easier and less expensive alternative to DSM. The study shows that there is a significant power reduction in both cases which is dependent on the time of day and not constant as expected from the literature. The results show that there are significant differences between current and future load demand characteristics that would be very difficult to acquire without the modelling technique presented. The alternative solution would require extensive local load and network modifications and a long period of expensive tests and measurements in the field.

Traffic Engineering (TE) uses methods and models from a variety of mathematical fields, such as statistics and optimization, to improve the performance of telecommunication networks. In this thesis, we study TE problems dealing with networks that impose single-path routing. As the name infers, in this type of routing, the traffic flow of each "commodity" cannot be split in its path between its origin and destination. Given its cheap cost, single-path routing is widely used in today's data centers, where thousands of stored servers perform computations or host Internet services. One common case of single-path routing is the one enforced by the Spanning Tree Protocol (STP) in switched Ethernet networks. The STP requires the network to keep its activated links loop-free, while maintaining the other redundant links ready for back-up, in case of link failure. The Multiple Spanning Tree Protocol (MSTP) extends the STP by installing multiple virtual networks compliant with the STP, over a single physical topology. Therefore, the MSTP is greatly beneficial for network service providers, as it allows for a more efficient use of the existing resources.Network design problems dealing with the MSTP are generally highly combinatorial and very hard to solve. As such, TE literature mainly suggests heuristic methods, which can quickly produce reasonable designs. Notwithstanding, due to a scarce existence of lower bounds to the optimum values of such problems, there is little knowledge about the quality of the solutions provided by these heuristics.In this sense, we propose mathematical programming models and methods that can provide optimal designs for these networks, or at the very least, obtain valid lower bounds. Taking into mind the goal of avoiding congestion in the network, we focus on two problems that deal with the following load-balancing objectives: the minimization of the worst-case link utilization, and the minimization of flow costs given by piecewise linear functions that penalize heavily-loaded links. The study of both these problems yielded relevant by-products: the first is the study of a MSTP network design problem, where we minimize the total load, and the second is the study of a fundamental unsplittable multicommodity flow problem with piecewise linear costs.For all the considered problems, we provide studies of complexity, extensive polyhedral studies to compare the proposed formulations, and a wide array of computational experiments to evaluate the performance of the proposed models and methods. / Doctorat en Sciences / info:eu-repo/semantics/nonPublished

A wireless mesh network is a mesh network implemented over a wireless network system such as wireless LANs. Wireless Mesh Networks(WMNs) are promising for numerous applications such as broadband home networking, enterprise networking, transportation systems, health and medical systems, security surveillance systems, etc. Therefore, it has received considerable attention from both industrial and academic researchers. This dissertation explores schemes for resource management and optimization in WMNs by means of network routing and network coding. In this dissertation, we propose three optimization schemes. (1) First, a triple-tier optimization scheme is proposed for load balancing objective. The first tier mechanism achieves long-term routing optimization, and the second tier mechanism, using the optimization results obtained from the first tier mechanism, performs the short-term adaptation to deal with the impact of dynamic channel conditions. A greedy sub-channel allocation algorithm is developed as the third tier optimization scheme to further reduce the congestion level in the network. We conduct thorough theoretical analysis to show the correctness of our design and give the properties of our scheme. (2) Then, a Relay-Aided Network Coding scheme called RANC is proposed to improve the performance gain of network coding by exploiting the physical layer multi-rate capability in WMNs. We conduct rigorous analysis to find the design principles and study the tradeoff in the performance gain of RANC. Based on the analytical results, we provide a practical solution by decomposing the original design problem into two sub-problems, flow partition problem and scheduling problem. (3) Lastly, a joint optimization scheme of the routing in the network layer and network coding-aware scheduling in the MAC layer is introduced. We formulate the network optimization problem and exploit the structure of the problem via dual decomposition. We find that the original problem is composed of two problems, routing problem in the network layer and scheduling problem in the MAC layer. These two sub-problems are coupled through the link capacities. We solve the routing problem by two different adaptive routing algorithms. We then provide a distributed coding-aware scheduling algorithm. According to corresponding experiment results, the proposed schemes can significantly improve network performance.

While the traditional approach to ease traffic congestion has focused on building infrastructure, the recent emergence of Connected and Automated Vehicles (CAVs) and urban mobility services (e.g., Autonomous Mobility-on-Demand (AMoD) systems) has opened a new set of alternatives for reducing travel times. This thesis seeks to exploit these advances to improve the operation and efficiency of Intelligent Transportation Systems using a network optimization perspective. It proposes novel methods to evaluate the prospective benefits of adopting socially optimal routing schemes, intermodal mobility, and contraflow lane reversals in transportation networks. This dissertation makes methodological and empirical contributions to the transportation domain. From a methodological standpoint, it devises a fast solver for the Traffic Assignment Problem with Side Constraints which supports arbitrary linear constraints on the flows. Instead of using standard column-generation methods, it introduces affine approximations of the travel latency function to reformulate the problem as a quadratic (or linear) programming problem. This framework is applied to two problems related to urban planning and mobility policy: social routing with rebalancing in intermodal mobility systems and planning lane reversals in transportation networks. Moreover, it proposes a novel method to jointly estimate the Origin-Destination demand and travel latency functions of the Traffic Assignment Problem. Finally, it develops a model to jointly optimize the pricing, rebalancing and fleet sizing decisions of a Mobility-on-Demand service. Empirically, it validates all the methods by testing them with real transportation topologies and real traffic data from Eastern Massachusetts and New York City showing the achievable benefits obtained when compared to benchmarks.