Mobile networks have rapidly evolved over decades, and have arrived at the fifth generation (5G) system in recent years. From 2019, companies started to bring 5G networks into business, providing higher data rates, lower latency, and larger network capacity to the world. One of the main advancements in 5G network systems is the use of millimetre waves for wireless transmission. This not only grants higher throughput with wide bandwidth but also introduces new challenges to the radio access networks in 5G systems. To tackle the challenges, a new type of network, which is called the Integrated Access and Backhaul (IAB) network, has been proposed as a deployment solution for 5G cellular networks. In this work, we investigate the routing mechanism of an IAB network and propose a novel load balancing algorithm that can be applied to the IAB network for improvement in throughput as well as load distribution. We extend the work from previous studies on IAB networks and evaluate the performance of the proposed algorithm in comparison to previous work. Through radio network simulations, we find that the shortest path routing outperforms a greedy algorithm in terms of path selection in the network and that the proposed algorithm achieves load balancing among the network, combined with an improvement in the user throughput. Finally, we conclude our work and suggest directions for future work in the study of IAB networks. / Mobilnäten har utvecklats snabbt de senaste decennierna och är nu framme vid femte generationens system (5G). Under 2019 började telekomföretag lansera 5G-nätverk, med högre datahastigheter, lägre fördröjningar och högre nätverkskapacitet. Ett av de största framstegen inom 5G-nätverkssystem är användningen av millimetervågor för trådlös överföring. Detta ger högre datahastigheter och större bandbredd, men leder också till nya utmaningar för radioaccessnätverket. För att hantera några av dessa har en ny typ av nätverk, kallat Integrated Access and Backhaul (IAB) föreslagits. I det här arbetet undersöker vi routingmekanismer för ett IAB-nätverk och föreslår en ny lastbalanseringsalgoritm som kan användas för att förbättra såväl genomströmning som lastfördelning. Arbetet är en utvidgning av tidigare studier av IAB-nätverk och jämför prestanda för den nya algoritmen med tidigare förslag. Genom simuleringar har vi funnit att shortest path routing överträffar en ”greedy” algoritm när det gäller vägval i nätverket och att den föreslagna algoritmen uppnår såväl lastbalansering som förbättrad genomströmning. Avslutningsvis ges förlag till fortsatt arbete inom studiet av IAB-nätverk.

In 2019, 770 million people worldwide lived without electricity. As many as 490 million people could be electrified with 210,000 mini-grids by 2030. Obtaining information for decision-making is crucial to determine the viability of such a project. Currently, it is a major challenge for mini-grid developers to gather this information at the speed and scale necessary to make effective investment choices. Village Data Analytics (VIDA) is a decision-making tool used for mini-grid project planning and site selection. This paper presents a method to estimate the cost of a mini-grid distribution network on a site-by-site basis. This method can estimate the total demand, potential connections, distribution infrastructure components and corresponding costs for each site. The model can make predictions for 50 sites within two hours so the tool is especially useful for preliminary estimates in the planning phase. A more detailed study of the individual sites is recommended. Comparison with a benchmark has shown that on-site conditions often reveal activities that can only be captured by a survey. However, collecting on-site data is time-consuming and costly. Therefore, GIS and modelling tools can serve as a good approximation of the on-ground reality and are relevant to accelerate planning and support timely decision-making. / 2019 levde 770 miljoner människor världen över utan elektricitet. Så många som 490 miljoner människor skulle kunna elektrifieras med 210 000 mininät till 2030. Att få information för beslutsfattande är avgörande för att avgöra om ett sådant projekt är lönsamt. För närvarande är det en stor utmaning för utvecklare av mininät att samla in denna information i den hastighet och skala som krävs för att göra effektiva investeringsval. Village Data Analytics (VIDA) är ett beslutsfattande verktyg som används för projektering av mininät och platsval. Det här dokumentet presenterar en metod för att uppskatta kostnaden för ett distributionsnät för mininät på plats för plats. Denna metod kan uppskatta den totala efterfrågan, potentiella anslutningar, komponenter för distribution sinfrastruktur och motsvarande kostnader för varje plats. Modellen kan göra förutsägelser för 50 platser inom två timmar, så verktyget är särskilt användbart för preliminära uppskattningar i planeringsfasen. En mer detaljerad studie av de enskilda platserna rekommenderas. Jämförelse med ett riktmärke har visat att förhållanden på plats ofta avslöjar aktiviteter som bara kan fångas genom en undersökning. Men att samla in data på plats är tidskrävande och kostsamt. Därför kan GIS- och modelleringsverktyg fungera som en bra approximation av verkligheten på marken och är relevanta för att påskynda planering och stödja beslutsfattande i rätt tid.

This thesis presents new solution approaches for land leveling, using optimal earthmoving vehicle routing. It addresses the Shortest Route Cut and Fill Problem (SRCFP) developed by Henderson, Vaughan, Wakefield and Jacobson [2000]. The SRCFP is a discrete optimization search problem, proven to be NP-hard. The SRCFP describes the process of reshaping terrain through a series of cuts and fills. This process is commonly done when leveling land for building homes, parking lots, etc. The model used to represent this natural system is a variation of the Traveling Salesman Problem. The model is designed to limit the time needed to operate expensive, earthmoving vehicles. The model finds a vehicle route that minimizes the total time required to travel between cut and fill locations while leveling the site. An optimal route is a route requiring the least amount of travel time for an individual earthmoving vehicle. This research addresses the SRCFP by evaluating minimum function values across an unknown response surface. The result is a cost estimating strategy that provides construction planners a strategy for contouring terrain as cheaply as possible. Other applications of this research include rapid runway repair, and robotic vehicle routing. / Master of Science

Maximum Subarray Problem (MSP) is to find the consecutive array portion that maximizes the sum of array elements in it. The goal is to locate the most useful and informative array segment that associates two parameters involved in data in a 2D array. It's an efficient data mining method which gives us an accurate pattern or trend of data with respect to some associated parameters. Distance Matrix Multiplication (DMM) is at the core of MSP. Also DMM and MSP have the worst-case complexity of the same order. So if we improve the algorithm for DMM that would also trigger the improvement of MSP. The complexity of Conventional DMM is O(n³). In the average case, All Pairs Shortest Path (APSP) Problem can be modified as a fast engine for DMM and can be solved in O(n² log n) expected time. Using this result, MSP can be solved in O(n² log² n) expected time. MSP can be extended to K-MSP. To incorporate DMM into K-MSP, DMM needs to be extended to K-DMM as well. In this research we show how DMM can be extended to K-DMM using K-Tuple Approach to solve K-MSP in O(Kn² log² n log K) time complexity when K ≤ n/log n. We also present Tournament Approach which solves K-MSP in O(n² log² n + Kn²) time complexity and outperforms the K-Tuple

Cette thèse porte sur le problème de l'estimation des temps de parcours, de véhicules, par section de route dans un contexte urbain, en utilisant les données GPS à faible densité d’échantillon. L'un des défis de cette thèse est d'utiliser ce genre de données. Dans le cadre de ce travail de recherche, j'ai développé une carte numérique avec son nouveau système d'information géographique (SIG), qui traite la problématique du map-matching, où nous avons apporté des améliorations, ainsi que le problème du plus court chemin.La thèse s'inscrit dans le cadre du projet PUMAS (Plate-forme Urbaine de Mobilité Avancée et Soutenable), ce qui est un avantage pour nos recherches en ce qui concerne le processus de collecte de données réelles sur le terrain ainsi que pour faire nos tests. Le projet PUMAS est un projet préindustriel qui a pour objectif d'informer sur la situation du trafic mais également de développer et de mettre en œuvre une plate-forme de mobilité durable afin de l'évaluer dans la région, notamment à Rouen, France. Le résultat offre un cadre pour tout contrôleur de la situation, gestionnaire ou chercheur pour accéder à de vastes réserves de données sur l'estimation du flux du trafic, sur les prévisions et sur l'état du trafic. / This dissertation is concerned with the problem of estimating travel time per links in urban context using sparsely sampled GPS data. One of the challenges in this thesis is use the sparsely sampled data. A part of this research work, i developed a digital map with its new geographic information system (GIS), dealing with map-matching problem, where we come out with an enhancement tecnique, and also the shortest path problem.The thesis research work was conduct within the project PUMAS, which is an avantage for our research regarding the collection process of our data from the real world field and also in making our tests. The project PUMAS (Plate-forme Urbaine de Mobilité Avancée et Soutenable / Urban Platform for Sustainable and Advanced Mobility) is a preindustrial project that has the objective to inform about the traffic situation and also to develop an implement a platform for sustainable mobility in order to evaluate it in the region, specifically Rouen, France. The result is a framework for any traffic controller or manager and also estimation researcher to access vast stores of data about the traffic estimation, forecasting and status.

Este trabalho traz um estudo inicial do acoplamento elétrico-energético no planejamento da operação de curto-curtíssimo prazo utilizando Fluxo de Potência Ótimo em Corrente Alternada (FPOCA) com o objetivo de averiguar possíveis desvios entre o planejamento energético e o planejamento elétrico. É feita uma análise da influência dos aspectos elétricos do sistema de transmissão no planejamento energético de curto prazo utilizando-se um FPOCA, juntamente com a minimização do custo da geração e das perdas na transmissão. A minimização do custo da geração é feita através de uma otimização do sistema hidrotérmico utilizando-se um Programa de Otimização de Sistema Hidrotérmico (POSH) baseado em um algoritmo simplex convexo e na aplicação da teoria de fluxo em rede, enquanto que a minimização das perdas na transmissão é feita utilizando-se um FPOCA baseado no método Dual-Newton. Estas ferramentas permitem analisar a necessidade de ajustes para compatibilizar a otimização energética e a otimização elétrica de um sistema eletroenergético, e buscar um planejamento \"ótimo\" que atenda os planejamentos energético e elétrico. Dessa forma, a interface elétrico-energética se torna mais \"forte\", pois as metas de geração obtidas pelo planejamento de curto prazo que serão passadas para o planejamento de curtíssimo prazo, já incluem o efeito dos aspectos elétricos do sistema. Isto proporciona um controle dos desvios da trajetória \"ótima\" do sistema, o que contribui para melhorar a otimização global do planejamento da operação eletroenergética. / This work brings a beginning study of the electric-energetic coupling in the short-shortest term operation planning using Optimal Power Flow in Alternate Current (OPFAC) aiming to inquire possible mismatches between the energetic planning and the eletric planning. It is made an analysis of the electrical aspects influence in the short term energetic planning using OPFAC together with the minimization of generation cost and the transmission losses. The generation cost minimization is made for the hidrothermal system optimization using a Hydrothermal System Optimization Program (POSH) based on a convex simplex algorithm and the application of the network flow theory, while the transmission losses minimization is made using an OPFAC based on the Dual-Newton method. These tools allow to analyze the necessity of adjustments to make compatible the energetic optimization and the electric optimization of the power system, and to search an \"optimal\" planning that attends both the energetic planning and electric planning. Like this, the electric-energetic interface becomes strongest, therefore the generation goals gotten by the short-term planning, that will be passed to the shortest-term planning, already includes the effect of the electric system aspects. These one provide the mismatches control in the optimal trajectory of the system and it contributes to improve the global optimization of power system operation planning. The analyzed system is the 440 kV Equivalent System of CESP (Energetic Company of São Paulo), with 53 bus, being 7 generation bus, 85 transmission lines and 48 transformers.

Devido a restrições de aplicabilidade presentes nos algoritmos para a solução de problemas de otimização combinatória, os sistemas baseados em redes neurais artificiais e algoritmos genéticos oferecem um método alternativo para solucionar tais problemas eficientemente. Os algoritmos genéticos devem a sua popularidade à possibilidade de percorrer espaços de busca não-lineares e extensos. Já as redes neurais artificiais possuem altas taxas de processamento por utilizarem um número elevado de elementos processadores simples com alta conectividade entre si. Complementarmente, redes neurais com conexões realimentadas fornecem um modelo computacional capaz de resolver vários tipos de problemas de otimização, os quais consistem, geralmente, da otimização de uma função objetivo que pode estar sujeita ou não a um conjunto de restrições. Esta tese apresenta uma abordagem inovadora para resolver problemas de conexão em otimização combinatória utilizando uma arquitetura neuro-genética. Mais especificamente, uma rede neural de Hopfield modificada é associada a um algoritmo genético visando garantir a convergência da rede em direção aos pontos de equilíbrio factíveis que representam as soluções para os problemas de otimização combinatória. / Due to applicability constraints involved with the algorithms for solving combinatorial optimization problems, systems based on artificial neural networks and genetic algorithms are alternative methods for solving these problems in an efficient way. The genetic algorithms must its popularity to make possible cover nonlinear and extensive search spaces. On the other hand, artificial neural networks have high processing rates due to the use of a massive number of simple processing elements and the high degree of connectivity between these elements. Additionally, neural networks with feedback connections provide a computing model capable of solving a large class of optimization problems, which refer to optimization of an objective function that can be subject to constraints. This thesis presents a novel approach for solving connection problems in combinatorial optimization using a neurogenetic approach. More specifically, a modified Hopfield neural network is associated with a genetic algorithm in order to guarantee the convergence of the network to the equilibrium points, which represent feasible solutions for the combinatorial optimization problems.

Submitted by William Justo Figueiro (williamjf) on 2015-07-21T22:37:51Z No. of bitstreams: 1 63c.pdf: 2699232 bytes, checksum: 1ae2013ef31101508f9fef3997d71790 (MD5) / Made available in DSpace on 2015-07-21T22:37:51Z (GMT). No. of bitstreams: 1 63c.pdf: 2699232 bytes, checksum: 1ae2013ef31101508f9fef3997d71790 (MD5) Previous issue date: 2013 / SIMTUR - Sistema Inteligente De Monitoramento de Tráfego Urbano / O crescente aumento do uso de automóveis e de motocicletas tem provocado uma contínua degradação no trânsito urbano das grandes metrópoles. Este cenário é agravado pelas deficiências nos atuais sistemas de transporte público, geradas, em parte, pela falta de informação ao usuário. O presente trabalho apresenta um modelo computacional para um sistema de informação ao usuário de transporte público. Ao contrário de outros trabalhos baseados no algoritmo clássico Dijkstra, a abordagem apresentada faz uso do algoritmo A* para resolução do problema de caminhos mínimos, presente neste contexto, a fim de reduzir o tempo de resposta de maneira que o modelo possa ser utilizado em um sistema real de informação ao usuário. O modelo proposto considera múltiplos critérios de decisão, como a distância total percorrida e o número de transbordos. Um estudo de caso foi realizado utilizando dados reais do transporte público da cidade Porto Alegre com o objetivo de avaliar o modelo computacional desenvolvido. Os resultados gerados foram comparados com aqueles obtidos através do emprego do algoritmo Dijkstra e indicam que a combinação do algoritmo A* com técnicas de aceleração permite reduzir, significativamente, a complexidade de espaço, o tempo de processamento e o número de transbordos. / The increasing use of automobiles and motorcycles has caused a continuous degradation in the traffic of large cities. This scenario gets worse due to shortcomings in the current public transportation, which is entailed, in a certain way, by the lack of information provided to the user. This study shows a computing model for a public transportation user information system. Unlike other studies based on the classical Dijkstra’s algorithm, the approach makes use of the algorithm A* to solve a shortest path problem to reduce the response time so that the model can be used in an real-time web information system. The proposed model takes into account multiple criteria of decision, such as total distance traveled and number of transfers and it was evaluated with data from Porto Alegre’s public transportation. The results were compared to those ones obtained by the use of Dijkstra’s algorithm and indicate that the combination of algorithm A* with acceleration techniques allows reducing significantly the space complexity, processing time and the number of transfers.

L'objectif de ce travail de thèse est de proposer des approches algorithmiques permettant de traiter la problématique du routage adaptatif (RA) dans un réseau de communication à trafic irrégulier. L'analyse des algorithmes existants nous a conduit à retenir comme base de travail l'algorithme Q-Routing (QR); celui-ci s'appuie sur la technique d'apprentissage par renforcement basée sur les modèles de Markov. L'efficacité de ce type de routage dépend fortement des informations sur la charge et la nature du trafic sur le réseau. Ces dernières doivent être à la fois, suffisantes, pertinentes et reflétant la charge réelle du réseau lors de la phase de prise de décision. Pour remédier aux inconvénients des techniques utilisant le QR, nous avons proposé deux algorithmes de RA. Le premier, appelé Q-Neural Routing, s'appuie sur un modèle neuronal stochastique pour estimer et mettre à jour les paramètres nécessaires au RA. Afin d'accélérer le temps de convergence, une deuxième approche est proposée : K-Shortest path Q-Routing. Elle est basée sur la technique de routage multi chemin combiné avec l'algorithme QR, l'espace d'exploration étant réduit aux k meilleurs chemins. Les deux algorithmes proposés sont validés et comparés aux approches traditionnelles en utilisant la plateforme de simulation OPNET, leur efficacité au niveau du RA est mise particulièrement en évidence. En effet, ceux-ci permettent une meilleure prise en compte de l'état du réseau contrairement aux approches classiques.

Devido a restrições de aplicabilidade presentes nos algoritmos para a solução de problemas de otimização combinatória, os sistemas baseados em redes neurais artificiais e algoritmos genéticos oferecem um método alternativo para solucionar tais problemas eficientemente. Os algoritmos genéticos devem a sua popularidade à possibilidade de percorrer espaços de busca não-lineares e extensos. Já as redes neurais artificiais possuem altas taxas de processamento por utilizarem um número elevado de elementos processadores simples com alta conectividade entre si. Complementarmente, redes neurais com conexões realimentadas fornecem um modelo computacional capaz de resolver vários tipos de problemas de otimização, os quais consistem, geralmente, da otimização de uma função objetivo que pode estar sujeita ou não a um conjunto de restrições. Esta tese apresenta uma abordagem inovadora para resolver problemas de conexão em otimização combinatória utilizando uma arquitetura neuro-genética. Mais especificamente, uma rede neural de Hopfield modificada é associada a um algoritmo genético visando garantir a convergência da rede em direção aos pontos de equilíbrio factíveis que representam as soluções para os problemas de otimização combinatória. / Due to applicability constraints involved with the algorithms for solving combinatorial optimization problems, systems based on artificial neural networks and genetic algorithms are alternative methods for solving these problems in an efficient way. The genetic algorithms must its popularity to make possible cover nonlinear and extensive search spaces. On the other hand, artificial neural networks have high processing rates due to the use of a massive number of simple processing elements and the high degree of connectivity between these elements. Additionally, neural networks with feedback connections provide a computing model capable of solving a large class of optimization problems, which refer to optimization of an objective function that can be subject to constraints. This thesis presents a novel approach for solving connection problems in combinatorial optimization using a neurogenetic approach. More specifically, a modified Hopfield neural network is associated with a genetic algorithm in order to guarantee the convergence of the network to the equilibrium points, which represent feasible solutions for the combinatorial optimization problems.