Develop new strategies to design and operate the multilateration systems, used for air traffic control operations, in a more efficient way. The design strategies are based on the utilization of metaheuristic optimization techniques and they are intended to found the optimal spatial distribution of the system ground stations, taking into account the most relevant system operation parameters. The strategies to operate the systems are based on the development of new positioning methods which allow solving the problems of uncertainty position and poor accuracy that the current systems can present. The new strategies can be applied to design, deploy and operate the multilateration systems for airport surface surveillance as well as takeoff-landing, approach and enroute control. An important advance in the current knowledge of air traffic control is expected from the development of these strategies, because they solve several deficiencies that have been made clear, by the international scientific community, in the last years. / Mantilla Gaviria, IA. (2013). New Strategies to Improve Multilateration Systems in the Air Traffic Control [Tesis doctoral]. Editorial Universitat Politècnica de València. https://doi.org/10.4995/Thesis/10251/29688 / Alfresco

Engineering problems have characteristics such as a large number of variables, non-linear, computationally expensive, complex and black-box (i.e. unknown internal structure). These characteristics prompt difficulties for existing optimisation techniques. A consequence of this is that the required optimisation time rapidly increases beyond what is practical. There is a needfor dedicated techniques to exploit the power of mathematical optimisation tosolve engineering problems. The objective of this thesis is to investigate thisneed within the field of automation, specifically for control optimisation ofautomated systems.The thesis proposes an optimisation algorithm for optimising the controlof automated interacting production stations (i.e. independent stations thatinteract by for example material handling robots). The objective of the optimisation is to increase the production rate of such systems. The non-separable nature of these problems due to the interactions, makes them hard to optimise.The proposed algorithm is called the Constructive Cooperative CoevolutionAlgorithm (C3). The thesis presents the experimental evaluation of C3, bothon theoretical and real-world problems. For the theoretical problems, C3 istested on a set of standard benchmark functions. The performance, robustness and convergence speed of C3 is compared with the algorithms. This shows that C3 is a competitive optimisation algorithm for large-scale non-separable problems.C3 is also evaluated on real-world industrial problems, concerning thecontrol of interacting production stations, and compared with other optimisation algorithms on these problems. This shows that C3 is very well-suited for these problems. The importance of considering the energy consumption and equipment wear, next to the production rate, in the objective function is also investigated. This shows that it is crucial that these are considered to optimise the overall performance of interacting production stations.

The design of public transportation networks includes the problem of finding efficient transit routes. This problem is called the Urban Transit Routing Problem (UTRP) and it is a highly complex combinatorial optimization problem. Solving the UTRP and finding more efficient transit routes may lead to large cost savings as well as shorter average travel times for the passengers. The most common approach to solving it, in the literature, is with the usage of a metaheuristic algorithm. The purpose of this thesis is to solve the UTRP with such an algorithm, and to make the algorithm efficient. To this end, the multi-objective Discrete Cuckoo Search (MODCS) algorithm is introduced and it solves the UTRP with respect to both passenger and operator objectives. Two network instances are solved for: the common benchmark network of Mandl's network, and the Södertälje bus network. For Mandl's network, the results were compared to other algorithms in the literature. The results showed great performance of the MODCS algorithm with respect to the passenger objective, and not as good with respect to the operator objective. The computation times of the MODCS were higher than those of the other algorithms. For the Södertälje bus network, the MODCS algorithm found route sets with significantly better objective values than those of a previous master thesis algorithm. Furthermore, the average computation times of the MODCS algorithm were much less than those of the previous master thesis algorithm. / Att designa kollektivtrafiknät inkluderar problemet av att hitta effektiva kollektivtrafiklinjer. Detta problem kallas för Urban Transit Routing Problem (UTRP) och det är ett mycket komplext kombinatoriskt optimeringsproblem. Att lösa UTRP och hitta effektivare kollektivtrafiklinjer kan leda till stora besparingar samt lägre genomsnittliga restider för passagerare. Den vanligaste metoden för att lösa problemet, inom litteraturen, är med en metaheuristisk algoritm. Syftet med detta examensarbete är att lösa UTRP med en sådan algoritm samt att göra algoritmen effektiv. Den multiobjektiva diskreta Cuckoo Search (MODCS) algoritmen blev introducerad för att uppnå syftet, och den löste UTRP med avseende på både passagerar- och operatörintressen. Två olika nätverk har lösts: Mandls nätverk som är det vanligaste att jämföra med, och Södertäljes bussnätverk. Resultaten för Mandls nätverk blev jämförda med resultaten av andra algoritmer i litteraturen. MODCS algoritmen hittade linjenät med mycket bra värden för passagerarintresset, men inte lika bra för operatörintresset. Beräkningstiden för MODCS var högre än för de andra algoritmerna. För Södertäljes bussnätverk så hittade MODCS algoritmen linjenät som hade mycket bättre objektiva värden än en algoritm från ett tidigare examensarbete. De genomsnittliga beräkningstiderna var dessutom mycket lägre för MODCS än för algoritmen från det tidigare examensarbetet.

Dans ce mémoire, nous étudions un problème de tournées de véhicules dans lequel une flotte privée de véhicules n’a pas la capacité suffisante pour desservir les demandes des clients. Dans un tel cas, on fait appel à un transporteur externe. Ce dernier n’a aucune contrainte de capacité, mais un coût est encouru lorsqu’un client lui est affecté. Il n’est pas nécessaire de mettre tous les véhicules de la flotte privée en service si cette approche se révèle plus économique. L’objectif consiste à minimiser le coût fixe des véhicules, puis le coût variable de transport et le coût chargé par le transporteur externe. Notre travail consiste à appliquer la métaheuristique de recherche adaptative à grand voisinage sur ce problème. Nous comparons nos résultats avec ceux obtenus précédemment avec différentes techniques connues sur les instances de Christofides et celles de Golden. / In this master thesis, we study a vehicle routing problem in which a private fleet does not have sufficient capacity to serve all customers. Therefore, an external common carrier is required. The external common carrier has no constraint of capacity, but there is a cost when a customer it assigned to it. It is not necessary for all the vehicles of the private fleet to be used. The objective is to minimize the sum of the fixed cost of the private fleet, the variable routing cost and the external carrier cost. Our work applies the adaptative large neighborhood search metaheuristic on this problem. We compare our results with those obtained previously with different well-known techniques on the benchmark instances of Christofides and Golden.

This paper proposes and investigates a metaheuristic tabu search algorithm (TSA) that generates optimal or near optimal solutions sequences for the feedback length minimization problem (FLMP) associated to a design structure matrix (DSM). The FLMP is a non-linear combinatorial optimization problem, belonging to the NP-hard class, and therefore finding an exact optimal solution is very hard and time consuming, especially on medium and large problem instances. First, we introduce the subject and provide a review of the related literature and problem definitions. Using the tabu search method (TSM) paradigm, this paper presents a new tabu search algorithm that generates optimal or sub-optimal solutions for the feedback length minimization problem, using two different neighborhoods based on swaps of two activities and shifting an activity to a different position. Furthermore, this paper includes numerical results for analyzing the performance of the proposed TSA and for fixing the proper values of its parameters. Then we compare our results on benchmarked problems with those already published in the literature. We conclude that the proposed tabu search algorithm is very promising because it outperforms the existing methods, and because no other tabu search method for the FLMP is reported in the literature. The proposed tabu search algorithm applied to the process layer of the multidimensional design structure matrices proves to be a key optimization method for an optimal product development. / Ce mémoire présente un nouvel algorithme métaheuristique de recherche taboue pour trouver des solutions optimales ou sous-optimales au problème de minimisation de la longueur des dépendances d’une matrice de conception (FLMP). Ce problème comporte une fonction économique non-linéaire et il appartient à la classe NP-ardu. Il s’ensuit qu’il est très difficile à trouver une solution optimale exacte en temps réel pour les problèmes de taille moyenne ou grande. D’abord, on présente le problème et une revue de la littérature associée. Ensuite, on analyse le problème, et on présente les détails du nouvel algorithme de recherche taboue produisant des solutions au problème de réduction de l’effet de retour en utilisant deux voisinages différents, le premier basé sur l’échange des positions de deux activités ("swap"), et le second sur le déplacement d’une activité à une position différente ("shift"). Des résultats numériques permettent d’analyser le comportement de l’algorithme et de comparer les deux voisinages. La première étape consiste à déterminer de bonnes valeurs pour les paramètres en utilisant des problèmes générés aléatoirement. Ensuite nos résultats sont comparés avec ceux obtenus dans la littérature. On conclut que l’algorithme de recherche taboue proposé est très prometteur, car nos résultats sont meilleurs que ceux publiés dans la litérature. D’autant plus que la recherche taboue semble avoir été utilisée pour la première fois sur ce problème.

Le problème de tournées de véhicules est un des problèmes d’optimisation combinatoire les plus connus et les plus difficiles. Il s’agit de déterminer les tournées optimales pour une flotte de véhicules afin de servir un ensemble donné de clients. Dans les problèmes classiques de transport, chaque client est normalement servi à partir d’un seul nœud (ou arc). Pour cela, on définit toujours un ensemble donné de nœuds (ou arcs) obligatoires à visiter ou traverser, et on recherche la solution à partir de cet ensemble de nœuds (ou arcs). Mais dans plusieurs applications réelles où un client peut être servi à partir de plus d’un nœud, (ou arc), les problèmes généralisés qui en résultent sont plus complexes. Le but principal de cette thèse est d’étudier trois problèmes généralisés de tournées de véhicules. Le premier problème de la tournée sur arcs suffisamment proche (CEARP), comporte une application réelle intéressante en routage pour le relevé des compteurs à distance ; les deux autres problèmes, problème de tournées couvrantes multi-véhicules (mCTP) et problème généralisé de tournées sur nœuds (GVRP), permettent de modéliser des problèmes de conception des réseaux de transport à deux niveaux. Pour résoudre ces problèmes, nous proposons une approche exacte ainsi que des métaheuristiques. Pour développer la méthode exacte, nous formulons chaque problème comme un programme mathématique, puis nous construisons des algorithmes de type branchement et coupes. Les métaheuristiques sont basées sur le ELS (ou Evolutionary Local Search) et sur le GRASP (ou Greedy Randomized Adaptive Search Procedure). De nombreuses expérimentations montrent la performance de nos méthodes. / The Routing Problem is one of the most popular and challenging combinatorial optimization problems. It involves finding the optimal set of routes for fleet of vehicles in order to serve a given set of customers. In the classic transportation problems, each customer is normally served by only one node (or arc). Therefore, there is always a given set of required nodes (or arcs) that have to be visited or traversed, and we just need to find the solution from this set of nodes (or arcs). But in many real applications where a customer can be served by from more than one node (or arc), the generalized resulting problems are more complex. The primary goal of this thesis is to study three generalized routing problems. The first one, the Close-Enough Arc Routing Problem(CEARP), has an interesting real-life application to routing for meter reading while the others two, the multi-vehicle Covering Tour Problem (mCTP) and the Generalized Vehicle Routing Problem(GVRP), can model problems concerned with the design of bilevel transportation networks. The problems are solved by exact methods as well as metaheuristics. To develop exact methods, we formulate each problem as a mathematical program, and then develop branch-and-cut algorithms. The metaheuristics are based on the evolutionary local search (ELS) method et on the greedy randomized adaptive search procedure (GRASP) method. The extensive computational experiments show the performance of our methods.

Ce travail porte sur la modélisation et la résolution de problèmes d’optimisation robuste et multi-objectifs du transport multimodal. Après une synthèse des travaux de la littérature et des concepts de base de l’optimisation robuste et l’optimisation multi-objectif, nous proposons un nouveau modèle d’optimisation multi-objectif du transport multimodal des produits agricoles marocains vers des clients européens. L’objectif est de déterminer la meilleure stratégie d’exportation qui minimise simultanément le coût total de transport multimodal et l’overtime maximal en prenant en considération des contraintes réalistes. Nous proposons également des nouvelles approches de résolution avec une application sur un réseau de transport multimodal réel.Nous avons étudié une autre problématique du transport multimodal avec localisation de terminaux intermodaux. Outre la version déterministe, une optimisation robuste qui tient compte des incertitudes sur les capacités, les coûts d’utilisation et les coûts de transport. Deux approches hybrides ont été proposées pour la résolution du problème.Dans ces contributions, des modèles et des méthodes sont présentés, des remarques et des interprétations sont tirées à propos de l’impact de la périssabilité des produits et de la robustesse sur les flux, le choix des ports, des trajets et des modes de transport. / Because of the importance of multimodal transport for goods importation and exportation from Morocco to international customers, our goals are modeling and solving multimodal freight transportation problems by more focusing on some issues confronted by our country. After presenting the required mathematical background on robust and multiobjective optimization and surveying the literature works on multimodal transport problems, its variants and solution approaches; and instead of testing them only on traditional benchmarks; we dealt with new variants and methods. A multi-objective mathematical model is proposed to optimize the multimodal transport of agricultural products from Morocco to Europe. To solve this model adapted to a real network, two multiobjective version algorithms are presented in order to optimize simultaneously the total transportation cost and the over-time.Given the complexity of the global logistics chain by various operations and several stakeholders, the data of the problem may sometimes be ignored or uncompleted. That’s why we have developed a mathematical model for multimodal terminal location problem by integrating uncertainties of the transportation costs, the capacities and the using costs of terminals. A population based simulated annealing and a hybrid method combining an exact and a metaheuristic approaches are proposed to effectively solving the problem. The test is then performed on a real intermodal network. These contributions are concluded by remarks and highlights about the impact of perishability and robustness on flows, location strategies of ports, the choice of paths and transportation modes.

Orientador: Rubén Augusto Romero Lázaro / Resumo: A grande maioria dos sistemas de distribuição de energia elétrica opera de forma radial. Isso significa que cada carga é alimentada por apenas uma subestação por meio de um único caminho. Entretanto, as redes de distribuição apresentam estrutura malhada, de forma que, caso uma contingência ocorra, o restabelecimento do fornecimento possa ser realizado para o maior número possível de consumidores. Os trabalhos que lidam com o problema de planejamento da expansão de sistemas de distribuição, no entanto, geralmente consideram a expansão do sistema para apenas uma topologia radial, sem levar em conta aspectos da restauração do fornecimento para melhoria dos índices de confiabilidade. Nesse contexto, este trabalho aborda o planejamento de sistemas de distribuição considerando aspectos econômicos e de confiabilidade, de forma a incluir a restauração do fornecimento no problema de planejamento da expansão. Na formulação do problema considera-se a expansão de novas subestações, o reforço de subestações existentes, a construção de novos alimentadores em novos caminhos, a troca de condutores existentes e a alocação de geradores distribuídos, além de expansão multiestágio e restauração do fornecimento para melhoria dos índices de confiabilidade. Dois métodos alternativos são propostos para resolver o problema descrito: o primeiro considera modelos matemáticos com diversos graus de precisão, para serem resolvidos por métodos exatos, e o segundo é uma meta-heurística de busca e vizinhança... (Resumo completo, clicar acesso eletrônico abaixo) / Abstract: The vast majority of electricity distribution systems are operated radially. This means that each load is supplied by only one substation through a single path. However, distribution networks have a meshed structure so that, in the case of a contingency, the supply is restored to as many customers as possible. The works that deal with the distribution systems expansion planning problem, however, generally consider the expansion of the system for only one radial topology, disregarding the restoration aspects to improve reliability indices. In this context, this work deals with the planning of distribution systems considering economic and reliability aspects, to include the service restoration in the planning problem. In the formulation of the problem, it is considered the expansion of new substations, the reinforcement of existing substations, the construction of new feeders in new paths, the exchange of existing conductors, and the allocation of distribution generation, besides multistage expansion and service restoration to improve the reliability indices of the system. Two alternative methods are proposed to solve the described problem: the first one considers relaxed or approximated mathematical models to be solved by exact methods, and the second one is a variable neighborhood search metaheuristic, which solves the complete model for the problem approximately, without guarantee of optimality. The initial solution of the metaheuristic is generated by a strategy that constr... (Complete abstract click electronic access below) / Doutor

Este trabalho propõe uma metodologia baseada em técnicas inteligentes capaz de fornecer uma coordenação otimizada de relés direcionais de sobrecorrente instalados em sistemas de energia elétrica. O problema é modelado como um caso de programação não linear inteira mista, em que os relés permitem ajustes discretizados de múltiplos de tempo e/ou múltiplos de corrente. A solução do problema de otimização correspondente é obtida através de uma metaheurística nomeada como Discrete Particle Swarm Optimization. Na literatura técnico-científica esse problema geralmente é linearizado e aplicam-se arredondamentos das variáveis discretas. Na metodologia proposta, as variáveis discretas são tratadas adequadamente para utilização na metaheurística e são apresentados os resultados que foram comparados com os obtidos pelo modelo clássico de otimização implementado no General Algebraic Modeling System (GAMS). Tendo em vista os aspectos observados, o método permite ao engenheiro de proteção ter um subsídio adicional na tarefa da coordenação dos relés direcionais de sobrecorrente, disponibilizando uma técnica eficaz e de fácil aplicabilidade ao sistema elétrico a ser protegido, independentemente da topologia e condição operacional. / This work proposes a methodology that based on intelligent technique to obtain an optimized coordination of directional overcurrent relays in electric power systems. The problem is modeled as a mixed integer nonlinear problem, because the relays allows a discrete setting of time and/or current multipliers. The solution of the proposed optimization problem is obtained from the proposed metaheuristic named as Discrete Particle Swarm Optimization. In scientific and technical literature this problem is usually linearized and discrete variables are rounded off. In the proposed method, the discrete variables are modeled adequately in the metaheuristic and the results are compared to the classical optimization solvers implemented in General Algebraic Modeling System (GAMS). The method provides an important method for helping the engineers in to coordinate directional overcurrent relays in a very optimized way. It has high potential for the application to realistic systems, regardless of topology and operating condition.

Le succès dans l'utilisation de méthodes exactes d’optimisation combinatoire pour des problèmes de grande taille est encore limité à certains problèmes ou à des classes spécifiques d'instances de problèmes. Une approche alternative consiste soit à utiliser des métaheuristiques ou des matheuristiques qui reposent en partie sur des méthodes exactes. Dans le contexte de l'optimisation combinatoire, nous nous intéressons des heuristiques permettant de choisir les heuristiques appliquées au problème traité. Dans cette thèse, nous nous concentrons sur l'optimisation à l’aide d’hyperheuristiques pour des problèmes logistiques. Nous proposons un cadre hyperheuristique qui effectue une recherche dans l'espace des algorithmes heuristiques et apprend comment changer l'heuristique courante systématiquement tout au long du processus de telle sorte qu'une bonne séquence d'heuristiques permet d’obtenir des solutions de haute qualité. Nous étudions plus particulièrement deux problèmes en logistique pour lesquels nous proposons des HHs: un problème de planification d’interventions sur des puits de forage et un problème conjoint de localisation de hubs et de routage. Ensuite, nous comparons les performances de plusieurs HH décrites dans la littérature pour le second problème abordé reposant sur différentes méthodes de sélection heuristique telles que la sélection aléatoire, la fonction de choix, une approche de Q-Learning et un algorithme de colonie de fourmis. Les résultats numériques prouvent l'efficacité de HHs pour les deux problèmes traités, et la pertinence d'inclure l'information venant d’une relaxation de Lagrangienne pour le deuxième problème. / Success in using exact methods for large scale combinatorial optimization is still limited to certain problems or to specific classes of instances of problems. The alternative way is either using metaheuristics or matheuristics that rely on exact methods in some ways. In the context of combinatorial optimization, we are interested in heuristics to choose heuristics invoked to solve the addressed problem. In this thesis, we focus on hyperheuristic optimization in logistic problems. We focus on proposing a hyperheuristic framework that carries out a search in the space of heuristic algorithms and learns how to change the incumbent heuristic in a systematic way along the process in such a way that a good sequence of heuristics produces high quality solutions. We propose HHs for two problems in logistics: the workover rig scheduling problem and the hub location routing problem. Then, we compare the performances of several HHs described in the literature for the latter problem, which embed different heuristic selection methods such as a random selection, a choice function, a Q-Learning approach, and an ant colony based algorithm. The computational results prove the efficiency of HHs for the two problems in hand, and the relevance of including Lagrangian relaxation information for the second problem.