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.

Evolutionary multi-move path-relinking for transmission network expansion planning

This paper presents the application of a new metaheuristic algorithm to solve the transmission expansion planning problem. A simple heuristic, using a relaxed network model associated with cost perturbation, is applied to generate a set of high quality initial solutions with different topologies. The population is evolved using a multi-move path-relinking with the objective of finding minimum investment cost for the transmission expansion planning problem employing the DC representation. The algorithm is tested on the southern Brazilian system, obtaining the optimal solution for the system with better performance than similar metaheuristics algorithms applied to the same problem. ©2010 IEEE.

Aplicaçaõ das técnicas Path-relinking e Vocabulary buiding na melhoria de performance do algoritmo memético para o problema do caixeiro viajante assimétrico

The present essay shows strategies of improvement in a well succeded evolutionary metaheuristic to solve the Asymmetric Traveling Salesman Problem. Such steps consist in a Memetic Algorithm projected mainly to this problem. Basically this improvement applied optimizing techniques known as Path-Relinking and Vocabulary Building. Furthermore, this last one has being used in two different ways, in order to evaluate the effects of the improvement on the evolutionary metaheuristic. These methods were implemented in C++ code and the experiments were done under instances at TSPLIB library, being possible to observe that the procedures purposed reached success on the tests done

GRASP with Hybrid Path Relinking for Bi-Objective Winner Determination in Combinatorial Transportation Auctions

The procurement of transportation services via large-scale combinatorial auctions involves a couple of complex decisions whose outcome highly influences the performance of the tender process. This paper examines the shipper's task of selecting a subset of the submitted bids which efficiently trades off total procurement cost against expected carrier performance. To solve this bi-objective winner determination problem, we propose a Pareto-based greedy randomized adaptive search procedure (GRASP). As a post-optimizer we use a path relinking procedure which is hybridized with branch-and-bound. Several variants of this algorithm are evaluated by means of artificial test instances which comply with important real-world characteristics. The two best variants prove superior to a previously published Pareto-based evolutionary algorithm.

GRASP heuristic with path-relinking for the multi-plant capacitated lot sizing problem

This paper addresses the independent multi-plant, multi-period, and multi-item capacitated lot sizing problem where transfers between the plants are allowed. This is an NP-hard combinatorial optimization problem and few solution methods have been proposed to solve it. We develop a GRASP (Greedy Randomized Adaptive Search Procedure) heuristic as well as a path-relinking intensification procedure to find cost-effective solutions for this problem. In addition, the proposed heuristics is used to solve some instances of the capacitated lot sizing problem with parallel machines. The results of the computational tests show that the proposed heuristics outperform other heuristics previously described in the literature. The results are confirmed by statistical tests. (C) 2009 Elsevier B.V. All rights reserved.

An iterated sample construction with path relinking method: Application to switch allocation in electrical distribution networks

We present a metaheuristic approach which combines constructive heuristics and local searches based on sampling with path relinking. Its effectiveness is demonstrated by an application to the problem of allocating switches in electrical distribution networks to improve their reliability. Our approach also treats the service restoration problem, which has to be solved as a subproblem, to evaluate the reliability benefit of a given switch allocation proposal. Comparisons with other metaheuristics and with a branch-and-bound procedure evaluate its performance. © 2012 Published by Elsevier Ltd.

Path relinking for the fixed spectrum frequency assignment problem

International audience

Algorítmo evolucionário para a distribuição de produtos de petróleo por redes de polidutos

The distribution of petroleum products through pipeline networks is an important problem that arises in production planning of refineries. It consists in determining what will be done in each production stage given a time horizon, concerning the distribution of products from source nodes to demand nodes, passing through intermediate nodes. Constraints concerning storage limits, delivering time, sources availability, limits on sending or receiving, among others, have to be satisfied. This problem can be viewed as a biobjective problem that aims at minimizing the time needed to for transporting the set of packages through the network and the successive transmission of different products in the same pipe is called fragmentation. This work are developed three algorithms that are applied to this problem: the first algorithm is discrete and is based on Particle Swarm Optimization (PSO), with local search procedures and path-relinking proposed as velocity operators, the second and the third algorithms deal of two versions based on the Non-dominated Sorting Genetic Algorithm II (NSGA-II). The proposed algorithms are compared to other approaches for the same problem, in terms of the solution quality and computational time spent, so that the efficiency of the developed methods can be evaluated

EVOLUTIONARY TRAJECTORIES OF ULTRACOMPACT "BLACK WIDOW" PULSARS WITH VERY LOW MASS COMPANIONS

The existence of millisecond pulsars with planet-mass companions in close orbits is challenging from the stellar evolution point of view. We calculate in detail the evolution of binary systems self-consistently, including mass transfer, evaporation, and irradiation of the donor by X-ray feedback, demonstrating the existence of a new evolutionary path leading to short periods and compact donors as required by the observations of PSR J1719-1438. We also point out the alternative of an exotic nature of the companion planet-mass star.

Advertising education in Australia: Looking back to the future

In Australia, advertising is a $13 billion industry which needs a supply of suitably skilled employees. Over the years, advertising education has developed from vocational based courses to degree courses across the country. This paper uses diffusion theory and various secondary sources and interviews to observe the development of advertising education in Australia from its early past, to its current day tertiary offerings, to discussing the issues that are arising in the near future. Six critical issues are identified, along with observations about the challenges and opportunities within Australia advertising education. By looking back to the future, it is hoped that this historical review provides lessons for other countries of similar educational structure or background, or even other marketing communication disciplines on a similar evolutionary path.

Perspectives on the origin of microfilaments, microtubules, the relevant chaperonin system and cytoskeletal motors - a commentary on the spirochaete origin of flagella

The origin of cytoskeleton and the origin of relevant intracellular transportation system are big problems for understanding the emergence of eukaryotic cells. The present article summarized relevant information of evidences and molecular traces on the origin of actin, tubulin, the chaperonin system for folding them, myosins, kinesins, axonemal dyneins and cytoplasmic dyneins. On this basis the authors proposed a series of works, which should be done in the future, and indicated the ways for reaching the targets. These targets are mainly: 1) the reconstruction of evolutionary path from MreB protein of archaeal ancestor of eukaryotic cells to typical actin; 2) the finding of the MreB or MreB-related proteins in crenarchaea and using them to examine J. A. Lake's hypothesis on the origin of eukaryote from "eocytes" (crenarchaea); 3) the examinations of the existence and distribution of cytoskeleton made of MreB-related protein within coccoid archaea, especially in amoeboid archaeon Thermoplasm acidophilum; 4) using Thermoplasma as a model of archaeal ancestor of eukaryotic cells; 5) the searching for the homolog of ancestral dynein in present-day living archaea. During the writing of this article, Margulis' famous spirochaete hypothesis on the origin of flagella and cilia was unexpectedly involved and analyzed from aspects of tubulins, dyneins and spirochaetes. Actually, spirochaete cannot be reasonably assumed as the ectosymbiotic ancestor of eukaryotic flagella and cilia, since their swing depends upon large amount of bacterial flagella beneath the flexible outer wall, but not depends upon their intracellular tubules and the assumed dyneins. In this case, if they had "evolved" into cilia and lost their bacterial flagella, they would immediately become immobile! In fact, tubulin and dynein-like proteins have not been found in any spirochaete.

Figer: A Quadraphonic Electroacoustic Composition

Figer (to congeal, to solidify) is a quadraphonic electroacoustic composition. It was completed in the fall of 2003. Several software programs were used in creating and assembling the piece (C-Sound, Grain Mill, AL/Erwin (grain generator), Sound Forge and Acid Music). The sounds used in the piece are of two general types: synthesized and sampled, both of which were subjected to various processing techniques. The most important of these techniques, and one that formally defines large portions of the piece, is granular synthesis. Form The notion of time perception is of great importance in this piece. Figer addresses this question in several ways. In one sense, the form of Figer is simple. There are three layers of activity (see diagram). Layer 1 is continuous and non-sectional and supplies a backdrop (not necessarily a background) for the other two. The second and third layers overlap and interrupt one another. Each consists of two blocks of sound. The layers, and blocks within, relate to each other in various ways. Layer 1 is formally continuous. Layer 2 consists of well-defined columns of sound that evolve from soft and mild to loud and abrasive. The layer is, in reality, a whole that is simply cut into two parts (block 1 and block 2). In contrast, the blocks of layer 3 do not constitute a whole. Each is a complete unit and has its own self-contained evolutionary path. Those paths, however, do cross the paths of other units (layers, blocks), influencing them and absorbing some of their essence. At the heart of Figer lies a constant process of presenting materials or ideas and immediately, or, at times, simultaneously, commenting, reflecting on, or reinterpreting that material. All of the layers of this piece deal, both at local and global levels, with the problem of time and its perception relative to the materials, sonic or otherwise, that occupy it and the manner in which they unfold and relate to each other.

Novel hardware and software combination for automotive motorsport vehicles based on direct processing of graphical functions

The main motivation for the work presented here began with previously conducted experiments with a programming concept at the time named "Macro". These experiments led to the conviction that it would be possible to build a system of engine control from scratch, which could eliminate many of the current problems of engine management systems in a direct and intrinsic way. It was also hoped that it would minimize the full range of software and hardware needed to make a final and fully functional system. Initially, this paper proposes to make a comprehensive survey of the state of the art in the specific area of software and corresponding hardware of automotive tools and automotive ECUs. Problems arising from such software will be identified, and it will be clear that practically all of these problems stem directly or indirectly from the fact that we continue to make comprehensive use of extremely long and complex "tool chains". Similarly, in the hardware, it will be argued that the problems stem from the extreme complexity and inter-dependency inside processor architectures. The conclusions are presented through an extensive list of "pitfalls" which will be thoroughly enumerated, identified and characterized. Solutions will also be proposed for the various current issues and for the implementation of these same solutions. All this final work will be part of a "proof-of-concept" system called "ECU2010". The central element of this system is the before mentioned "Macro" concept, which is an graphical block representing one of many operations required in a automotive system having arithmetic, logic, filtering, integration, multiplexing functions among others. The end result of the proposed work is a single tool, fully integrated, enabling the development and management of the entire system in one simple visual interface. Part of the presented result relies on a hardware platform fully adapted to the software, as well as enabling high flexibility and scalability in addition to using exactly the same technology for ECU, data logger and peripherals alike. Current systems rely on a mostly evolutionary path, only allowing online calibration of parameters, but never the online alteration of their own automotive functionality algorithms. By contrast, the system developed and described in this thesis had the advantage of following a "clean-slate" approach, whereby everything could be rethought globally. In the end, out of all the system characteristics, "LIVE-Prototyping" is the most relevant feature, allowing the adjustment of automotive algorithms (eg. Injection, ignition, lambda control, etc.) 100% online, keeping the engine constantly working, without ever having to stop or reboot to make such changes. This consequently eliminates any "turnaround delay" typically present in current automotive systems, thereby enhancing the efficiency and handling of such systems.

Solution Methods for Service Network Design with Resource Management Consideration

La gestion des ressources, équipements, équipes de travail, et autres, devrait être prise en compte lors de la conception de tout plan réalisable pour le problème de conception de réseaux de services. Cependant, les travaux de recherche portant sur la gestion des ressources et la conception de réseaux de services restent limités. La présente thèse a pour objectif de combler cette lacune en faisant l’examen de problèmes de conception de réseaux de services prenant en compte la gestion des ressources. Pour ce faire, cette thèse se décline en trois études portant sur la conception de réseaux. La première étude considère le problème de capacitated multi-commodity fixed cost network design with design-balance constraints(DBCMND). La structure multi-produits avec capacité sur les arcs du DBCMND, de même que ses contraintes design-balance, font qu’il apparaît comme sous-problème dans de nombreux problèmes reliés à la conception de réseaux de services, d’où l’intérêt d’étudier le DBCMND dans le contexte de cette thèse. Nous proposons une nouvelle approche pour résoudre ce problème combinant la recherche tabou, la recomposition de chemin, et une procédure d’intensification de la recherche dans une région particulière de l’espace de solutions. Dans un premier temps la recherche tabou identifie de bonnes solutions réalisables. Ensuite la recomposition de chemin est utilisée pour augmenter le nombre de solutions réalisables. Les solutions trouvées par ces deux méta-heuristiques permettent d’identifier un sous-ensemble d’arcs qui ont de bonnes chances d’avoir un statut ouvert ou fermé dans une solution optimale. Le statut de ces arcs est alors fixé selon la valeur qui prédomine dans les solutions trouvées préalablement. Enfin, nous utilisons la puissance d’un solveur de programmation mixte en nombres entiers pour intensifier la recherche sur le problème restreint par le statut fixé ouvert/fermé de certains arcs. Les tests montrent que cette approche est capable de trouver de bonnes solutions aux problèmes de grandes tailles dans des temps raisonnables. Cette recherche est publiée dans la revue scientifique Journal of heuristics. La deuxième étude introduit la gestion des ressources au niveau de la conception de réseaux de services en prenant en compte explicitement le nombre fini de véhicules utilisés à chaque terminal pour le transport de produits. Une approche de solution faisant appel au slope-scaling, la génération de colonnes et des heuristiques basées sur une formulation en cycles est ainsi proposée. La génération de colonnes résout une relaxation linéaire du problème de conception de réseaux, générant des colonnes qui sont ensuite utilisées par le slope-scaling. Le slope-scaling résout une approximation linéaire du problème de conception de réseaux, d’où l’utilisation d’une heuristique pour convertir les solutions obtenues par le slope-scaling en solutions réalisables pour le problème original. L’algorithme se termine avec une procédure de perturbation qui améliore les solutions réalisables. Les tests montrent que l’algorithme proposé est capable de trouver de bonnes solutions au problème de conception de réseaux de services avec un nombre fixe des ressources à chaque terminal. Les résultats de cette recherche seront publiés dans la revue scientifique Transportation Science. La troisième étude élargie nos considérations sur la gestion des ressources en prenant en compte l’achat ou la location de nouvelles ressources de même que le repositionnement de ressources existantes. Nous faisons les hypothèses suivantes: une unité de ressource est nécessaire pour faire fonctionner un service, chaque ressource doit retourner à son terminal d’origine, il existe un nombre fixe de ressources à chaque terminal, et la longueur du circuit des ressources est limitée. Nous considérons les alternatives suivantes dans la gestion des ressources: 1) repositionnement de ressources entre les terminaux pour tenir compte des changements de la demande, 2) achat et/ou location de nouvelles ressources et leur distribution à différents terminaux, 3) externalisation de certains services. Nous présentons une formulation intégrée combinant les décisions reliées à la gestion des ressources avec les décisions reliées à la conception des réseaux de services. Nous présentons également une méthode de résolution matheuristique combinant le slope-scaling et la génération de colonnes. Nous discutons des performances de cette méthode de résolution, et nous faisons une analyse de l’impact de différentes décisions de gestion des ressources dans le contexte de la conception de réseaux de services. Cette étude sera présentée au XII International Symposium On Locational Decision, en conjonction avec XXI Meeting of EURO Working Group on Locational Analysis, Naples/Capri (Italy), 2014. En résumé, trois études différentes sont considérées dans la présente thèse. La première porte sur une nouvelle méthode de solution pour le "capacitated multi-commodity fixed cost network design with design-balance constraints". Nous y proposons une matheuristique comprenant la recherche tabou, la recomposition de chemin, et l’optimisation exacte. Dans la deuxième étude, nous présentons un nouveau modèle de conception de réseaux de services prenant en compte un nombre fini de ressources à chaque terminal. Nous y proposons une matheuristique avancée basée sur la formulation en cycles comprenant le slope-scaling, la génération de colonnes, des heuristiques et l’optimisation exacte. Enfin, nous étudions l’allocation des ressources dans la conception de réseaux de services en introduisant des formulations qui modèlent le repositionnement, l’acquisition et la location de ressources, et l’externalisation de certains services. À cet égard, un cadre de solution slope-scaling développé à partir d’une formulation en cycles est proposé. Ce dernier comporte la génération de colonnes et une heuristique. Les méthodes proposées dans ces trois études ont montré leur capacité à trouver de bonnes solutions.

El caso de perdurabilidad empresarial de Crepes & Waffles desde una perspectiva de responsabilidad social empresarial e innovación en valor en Colombia

La multinacional Crepes & Waffles posee una historia extraordinaria de emprendimiento y arte en la gestión, con la cual construye un valor agregado diferenciador en la industria gastronómica de Colombia, pues mediante el uso de una estrategia enfocada hacia la Responsabilidad Social Empresarial (RSE) genera Innovación en Valor y por consiguiente la satisfacción de cada uno de sus clientes tanto internos como externos (Stakeholders) estableciendo lazos de confianza y compromiso. El presente trabajo de grado busca incluir como ingrediente clave de la perdurabilidad a la RSE creadora de Innovación en Valor, ya que por medio del estudio del caso Crepes & Waffles, se concluye que una gerencia humana, holística y comprometida con la construcción de su entorno, puede lograr que una empresa sea legitimada por la sociedad en la que está inmersa. Una buena dosis de RSE estratégicamente aplicada se configura hoy por hoy como la receta innegable del éxito y aunque un sinnúmero de teorías organizacionales tratan de establecer las pautas para impulsar el crecimiento de las empresas, únicamente la entidad que logre ingresar al corazón de sus Stakeholders y crear fidelidad, se mantendrá en el tiempo y se sumergirá en un nicho de mercado carente de competidores, o en lo que los escritores W. Chan Kim y Renée Mauborgne (2005) describen en su libro “La estrategia del Océano Azul” como “Un espacio de mercado no disputado donde la competencia es irrelevante”.