GRASP with evolutionary path-relinking for the capacitated arc routing problem

The Capacitated Arc Routing Problem (CARP) is a well-known NP-hard combinatorial optimization problem where, given an undirected graph, the objective is to find a minimum cost set of tours servicing a subset of required edges under vehicle capacity constraints. There are numerous applications for the CARP, such as street sweeping, garbage collection, mail delivery, school bus routing, and meter reading. A Greedy Randomized Adaptive Search Procedure (GRASP) with Path-Relinking (PR) is proposed and compared with other successful CARP metaheuristics. Some features of this GRASP with PR are (i) reactive parameter tuning, where the parameter value is stochastically selected biased in favor of those values which historically produced the best solutions in average; (ii) a statistical filter, which discard initial solutions if they are unlikely to improve the incumbent best solution; (iii) infeasible local search, where high-quality solutions, though infeasible, are used to explore the feasible/infeasible boundaries of the solution space; (iv) evolutionary PR, a recent trend where the pool of elite solutions is progressively improved by successive relinking of pairs of elite solutions. Computational tests were conducted using a set of 81 instances, and results reveal that the GRASP is very competitive, achieving the best overall deviation from lower bounds and the highest number of best solutions found. © 2011 Elsevier Ltd. All rights reserved.

A hybrid multi-population genetic algorithm applied to solve the multi-level capacitated lot sizing problem with backlogging

The present paper proposes a new hybrid multi-population genetic algorithm (HMPGA) as an approach to solve the multi-level capacitated lot sizing problem with backlogging. This method combines a multi-population based metaheuristic using fix-and-optimize heuristic and mathematical programming techniques. A total of four test sets from the MULTILSB (Multi-Item Lot-Sizing with Backlogging) library are solved and the results are compared with those reached by two other methods recently published. The results have shown that HMPGA had a better performance for most of the test sets solved, specially when longer computing time is given. © 2012 Elsevier Ltd.

Cogeneration design problem Computational complexity analysis and solution through an expert system

Purpose - The purpose of this paper is twofold: to analyze the computational complexity of the cogeneration design problem; to present an expert system to solve the proposed problem, comparing such an approach with the traditional searching methods available.Design/methodology/approach - The complexity of the cogeneration problem is analyzed through the transformation of the well-known knapsack problem. Both problems are formulated as decision problems and it is proven that the cogeneration problem is np-complete. Thus, several searching approaches, such as population heuristics and dynamic programming, could be used to solve the problem. Alternatively, a knowledge-based approach is proposed by presenting an expert system and its knowledge representation scheme.Findings - The expert system is executed considering two case-studies. First, a cogeneration plant should meet power, steam, chilled water and hot water demands. The expert system presented two different solutions based on high complexity thermodynamic cycles. In the second case-study the plant should meet just power and steam demands. The system presents three different solutions, and one of them was never considered before by our consultant expert.Originality/value - The expert system approach is not a "blind" method, i.e. it generates solutions based on actual engineering knowledge instead of the searching strategies from traditional methods. It means that the system is able to explain its choices, making available the design rationale for each solution. This is the main advantage of the expert system approach over the traditional search methods. On the other hand, the expert system quite likely does not provide an actual optimal solution. All it can provide is one or more acceptable solutions.

A Chaotic Approach of Differential Evolution Optimization Applied to Loudspeaker Design Problem

Over the past few years, the field of global optimization has been very active, producing different kinds of deterministic and stochastic algorithms for optimization in the continuous domain. These days, the use of evolutionary algorithms (EAs) to solve optimization problems is a common practice due to their competitive performance on complex search spaces. EAs are well known for their ability to deal with nonlinear and complex optimization problems. Differential evolution (DE) algorithms are a family of evolutionary optimization techniques that use a rather greedy and less stochastic approach to problem solving, when compared to classical evolutionary algorithms. The main idea is to construct, at each generation, for each element of the population a mutant vector, which is constructed through a specific mutation operation based on adding differences between randomly selected elements of the population to another element. Due to its simple implementation, minimum mathematical processing and good optimization capability, DE has attracted attention. This paper proposes a new approach to solve electromagnetic design problems that combines the DE algorithm with a generator of chaos sequences. This approach is tested on the design of a loudspeaker model with 17 degrees of freedom, for showing its applicability to electromagnetic problems. The results show that the DE algorithm with chaotic sequences presents better, or at least similar, results when compared to the standard DE algorithm and other evolutionary algorithms available in the literature.

Accelerating benders decomposition with heuristicmaster problem solutions

In this paper, a general scheme for generating extra cuts during the execution of a Benders decomposition algorithm is presented. These cuts are based on feasible and infeasible master problem solutions generated by means of a heuristic. This article includes general guidelines and a case study with a fixed charge network design problem. Computational tests with instances of this problem show the efficiency of the strategy. The most important aspect of the proposed ideas is their generality, which allows them to be used in virtually any Benders decomposition implementation.

Models for capacitated lot-sizing problem with backlogging, setup carryover and crossover

Setup operations are significant in some production environments. It is mandatory that their production plans consider some features, as setup state conservation across periods through setup carryover and crossover. The modelling of setup crossover allows more flexible decisions and is essential for problems with long setup times. This paper proposes two models for the capacitated lot-sizing problem with backlogging and setup carryover and crossover. The first is in line with other models from the literature, whereas the second considers a disaggregated setup variable, which tracks the starting and completion times of the setup operation. This innovative approach permits a more compact formulation. Computational results show that the proposed models have outperformed other state-of-the-art formulation.

Heuristic algorithms for the Capacitated Location-Routing Problem and the Multi-Depot Vehicle Routing Problem

The Capacitated Location-Routing Problem (CLRP) is a NP-hard problem since it generalizes two well known NP-hard problems: the Capacitated Facility Location Problem (CFLP) and the Capacitated Vehicle Routing Problem (CVRP). The Multi-Depot Vehicle Routing Problem (MDVRP) is known to be a NP-hard since it is a generalization of the well known Vehicle Routing Problem (VRP), arising with one depot. This thesis addresses heuristics algorithms based on the well-know granular search idea introduced by Toth and Vigo (2003) to solve the CLRP and the MDVRP. Extensive computational experiments on benchmark instances for both problems have been performed to determine the effectiveness of the proposed algorithms. This work is organized as follows: Chapter 1 describes a detailed overview and a methodological review of the literature for the the Capacitated Location-Routing Problem (CLRP) and the Multi-Depot Vehicle Routing Problem (MDVRP). Chapter 2 describes a two-phase hybrid heuristic algorithm to solve the CLRP. Chapter 3 shows a computational comparison of heuristic algorithms for the CLRP. Chapter 4 presents a hybrid granular tabu search approach for solving the MDVRP.

Cut-first branch-and-price-second for the capacitated arc-routing problem

This paper presents the first full-fledged branch-and-price (bap) algorithm for the capacitated arc-routing problem (CARP). Prior exact solution techniques either rely on cutting planes or the transformation of the CARP into a node-routing problem. The drawbacks are either models with inherent symmetry, dense underlying networks, or a formulation where edge flows in a potential solution do not allow the reconstruction of unique CARP tours. The proposed algorithm circumvents all these drawbacks by taking the beneficial ingredients from existing CARP methods and combining them in a new way. The first step is the solution of the one-index formulation of the CARP in order to produce strong cuts and an excellent lower bound. It is known that this bound is typically stronger than relaxations of a pure set-partitioning CARP model.rnSuch a set-partitioning master program results from a Dantzig-Wolfe decomposition. In the second phase, the master program is initialized with the strong cuts, CARP tours are iteratively generated by a pricing procedure, and branching is required to produce integer solutions. This is a cut-first bap-second algorithm and its main function is, in fact, the splitting of edge flows into unique CARP tours.

Multibeam Network Design and Measurement for Triangular Array of Three Radiating Elements

Nowadays, more a more base stations are equipped with active conformal antennas. These antenna designs combine phase shift systems with multibeam networks providing multi-beam ability and interference rejection, which optimize multiple channel systems. GEODA is a conformal adaptive antenna system designed for satellite communications. Operating at 1.7 GHz with circular polarization, it is possible to track and communicate with several satellites at once thanks to its adaptive beam. The antenna is based on a set of similar triangular arrays that are divided in subarrays of three elements called `cells'. Transmission/Receiver (T/R) modules manage beam steering by shifting the phases. A more accurate steering of the antenna GEODA could be achieved by using a multibeam network. Several multibeam network designs based on Butler network will be presented

Designing Rapid Transit Network Design with Alternative routes

The aim of this paper is to propose a model for the design of a robust rapid transit network. In this paper, a network is said to be robust when the effect of disruption on total trip coverage is minimized. The proposed model is constrained by three different kinds of flow conditions. These constraints will yield a network that provides several alternative routes for given origin–destination pairs, therefore increasing robustness. The paper includes computational experiments which show how the introduction of robustness influences network design

Aspects of a phased array radar feed and bias network design

Radar technologies have been developed to improve the efficiency when detecting targets. Radar is a system composed by several devices connected and working together. Depending on the type of radar, the improvements are focused on different functionalities of the radar. One of the most important devices composing a radar is the antenna, that sends the radio-frequency signal to the space in order to detect targets. This project is focused on a specific type of radar called phased array radar. This type of radar is characterized by its antenna, which consist on a linear array of radiating elements, in this particular case, eight dipoles working at the frequency band S. The main advantage introduced by the phased array antenna is that using the fundamentals of arrays, the directivity of the antenna can change by shifting the phase of the signal at the input of each radiating element. This can be done using phase shifters. Phase shifter consists on a device which produces a phase shift in the radio-frequency input signal depending on a control DC voltage. Using a phased array antenna allows changing the directivity of the antenna without a mechanical rotating system. The objective of this project is to design the feed network and the bias network of the phased antenna. The feed network consists on a parallel-fed network composed by power dividers that sends the radio-frequency signal from the source to each radiating element of the antenna. The bias network consists on a system that generates the control DC voltages supplied to the phase shifters in order to change the directivity. The architecture of the bias network is composed by a software, implemented in Matlab and run in a laptop which is connected to a micro-controller by a serial communication port. The software calculates the control DC voltages needed to obtain a determined directivity or scan angle. These values are sent by the serial communication port to the micro-controller as data. Then the micro-controller generates the desired control DC voltages and supplies them to the phase shifters. In this project two solutions for bias network are designed. Each one is tested and final conclusions are obtained to determine the advantages and disadvantages. Finally a graphic user interface is developed in order to make the system easy to use. RESUMEN. Las tecnologías empleadas por lo dispositivos radar se han ido desarrollando para mejorar su eficiencia y usabilidad. Un radar es un sistema formado por varios subsistemas conectados entre sí. Por lo que dependiendo del tipo de radar las mejoras se centran en los subsistemas correspondientes. Uno de los elementos más importantes de un radar es la antena. Esta se emplea para enviar la señal de radiofrecuencia al espacio y así poder detectar los posibles obstáculos del entorno. Este proyecto se centra en un tipo específico de radar llamado phased array radar. Este tipo de radar se caracteriza por la antena que es un array de antenas, en concreto para este proyecto se trata de un array lineal de ocho dipolos en la banda de frequencia S. El uso de una antena de tipo phased array supone una ventaja importante. Empleando los fundamentos de radiación aplicado a array de antenas se obtiene que la directividad de la antena puede ser modificada. Esto se consigue aplicando distintos desfasajes a la señal de radiofrecuencia que alimenta a cada elemento del array. Para aplicar los desfasajes se emplea un desplazador de fase, este dispositivo aplica una diferencia de fase a su salida con respecto a la señal de entrada dependiendo de una tensión continua de control. Por tanto el empleo de una antena de tipo phased array supone una gran ventaja puesto que no se necesita un sistema de rotación para cambiar la directividad de la antena. El objetivo principal del proyecto consiste en el diseño de la red de alimentación y la red de polarización de la antena de tipo phased array. La red de alimentación consiste en un circuito pasivo que permite alimentar a cada elemento del array con la misma cantidad de señal. Dicha red estará formada por divisores de potencia pasivos y su configuración será en paralelo. Por otro lado la red de polarización consiste en el diseño de un sistema automático que permite cambiar la directividad de la antena. Este sistema consiste en un programa en Matlab que es ejecutado en un ordenador conectado a un micro-controlador mediante una comunicación serie. El funcionamiento se basa en calcular las tensiones continuas de control, que necesitan los desplazadores de fase, mediante un programa en Matlab y enviarlos como datos al micro-controlador. Dicho micro-controlador genera las tensiones de control deseadas y las proporciona a cada desplazador de fase, obteniendo así la directividad deseada. Debido al amplio abanico de posibilidades, se obtienen dos soluciones que son sometidas a pruebas. Se obtienen las ventajas y desventajas de cada una. Finalmente se implementa una interfaz gráfica de usuario con el objetivo de hacer dicho sistema manejable y entendible para cualquier usuario.

Topics in MOSFET network design /

Thesis--University of Illinois at Urbana-Champaign.

Optimum network design using NOR and NOR-AND gates by integer programming,

Bibliography: p. 44.