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.

A hybrid heuristic for the multi-plant capacitated lot sizing problem with setup carry-over

This paper addresses the capacitated lot sizing problem (CLSP) with a single stage composed of multiple plants, items and periods with setup carry-over among the periods. The CLSP is well studied and many heuristics have been proposed to solve it. Nevertheless, few researches explored the multi-plant capacitated lot sizing problem (MPCLSP), which means that few solution methods were proposed to solve it. Furthermore, to our knowledge, no study of the MPCLSP with setup carry-over was found in the literature. This paper presents a mathematical model and a GRASP (Greedy Randomized Adaptive Search Procedure) with path relinking to the MPCLSP with setup carry-over. This solution method is an extension and adaptation of a previously adopted methodology without the setup carry-over. Computational tests showed that the improvement of the setup carry-over is significant in terms of the solution value with a low increase in computational time.

Some heuristic algorithms for total tardiness minimization in a flowshop with blocking

The flowshop scheduling problem with blocking in-process is addressed in this paper. In this environment, there are no buffers between successive machines: therefore intermediate queues of jobs waiting in the system for their next operations are not allowed. Heuristic approaches are proposed to minimize the total tardiness criterion. A constructive heuristic that explores specific characteristics of the problem is presented. Moreover, a GRASP-based heuristic is proposed and Coupled with a path relinking strategy to search for better outcomes. Computational tests are presented and the comparisons made with an adaptation of the NEH algorithm and with a branch-and-bound algorithm indicate that the new approaches are promising. (c) 2007 Elsevier Ltd. All rights reserved.

Mapping the Contemporary Studies on Alliances and Strategic Networks

The competition among the companies depends on the velocity and efficience they can create and commercialize knowledge in a timely and cost-efficient manner. In this context, collaboration emerges as a reaction to the environmental changes. Although strategic alliances and networks have been exploited in the strategic literature for decades, the complexity and continuous usage of these cooperation structures, in a world of growing competition, justify the continuous interest in both themes. This article presents a scanning of the contemporary academic production in strategic alliances and networks, covering the period from January 1997 to august 2007, based on the top five journals accordingly to the journal of Citation Report 2006 in the business and management categories simultaneously. The results point to a retraction in publications about strategic alliances and a significant growth in the area of strategic. networks. The joint view of strategic alliances and networks, cited by some authors a the evolutionary path of study, still did not appear salient. The most cited topics found in the alliance literature are the governance structure, cooperation, knowledge transfer, culture, control, trust, alliance formation,,previous experience, resources, competition and partner selection. The theme network focuses mainly on structure, knowledge transfer and social network, while the joint vision is highly concentrated in: the subjects of alliance formation and the governance choice.

A CMMI-compliant requirements management and development process

Requirements Engineering has been acknowledged an essential discipline for Software Quality. Poorly-defined processes for eliciting, analyzing, specifying and validating requirements can lead to unclear issues or misunderstandings on business needs and project’s scope. These typically result in customers’ non-satisfaction with either the products’ quality or the increase of the project’s budget and duration. Maturity models allow an organization to measure the quality of its processes and improve them according to an evolutionary path based on levels. The Capability Maturity Model Integration (CMMI) addresses the aforementioned Requirements Engineering issues. CMMI defines a set of best practices for process improvement that are divided into several process areas. Requirements Management and Requirements Development are the process areas concerned with Requirements Engineering maturity. Altran Portugal is a consulting company concerned with the quality of its software. In 2012, the Solution Center department has developed and applied successfully a set of processes aligned with CMMI-DEV v1.3, what granted them a Level 2 maturity certification. For 2015, they defined an organizational goal of addressing CMMI-DEV maturity level 3. This MSc dissertation is part of this organization effort. In particular, it is concerned with the required process areas that address the activities of Requirements Engineering. Our main goal is to contribute for the development of Altran’s internal engineering processes to conform to the guidelines of the Requirements Development process area. Throughout this dissertation, we started with an evaluation method based on CMMI and conducted a compliance assessment of Altran’s current processes. This allowed demonstrating their alignment with the CMMI Requirements Management process area and to highlight the improvements needed to conform to the Requirements Development process area. Based on the study of alternative solutions for the gaps found, we proposed a new Requirements Management and Development process that was later validated using three different approaches. The main contribution of this dissertation is the new process developed for Altran Portugal. However, given that studies on these topics are not abundant in the literature, we also expect to contribute with useful evidences to the existing body of knowledge with a survey on CMMI and requirements engineering trends. Most importantly, we hope that the implementation of the proposed processes’ improvements will minimize the risks of mishandled requirements, increasing Altran’s performance and taking them one step further to the desired maturity level.

The Energy metabolism of China and India between 1971-2010: studying the bifurcation

This paper presents a comparison of the changes in the energetic metabolic pattern of China and India, the two most populated countries in the world, with two economies undergoing an important economic transition. The comparison of the changes in the energetic metabolic pattern has the scope to characterize and explain a bifurcation in their evolutionary path in the recent years, using the Multi-Scale Integrated Analysis of Societal and Ecosystem Metabolism (MuSIASEM) approach. The analysis shows an impressive transformation of China’s energy metabolism determined by the joining of the WTO in 2001. Since then, China became the largest factory of the world with a generalized capitalization of all sectors ―especially the industrial sector― boosting economic labor productivity as well as total energy consumption. India, on the contrary, lags behind when considering these factors. Looking at changes in the household sector (energy metabolism associated with final consumption) in the case of China, the energetic metabolic rate (EMR) soared in the last decade, also thanks to a reduced growth of population, whereas in India it remained stagnant for the last 40 years. This analysis indicates a big challenge for India for the next decade. In the light of the data analyzed both countries will continue to require strong injections of technical capital requiring a continuous increase in their total energy consumption. When considering the size of these economies it is easy to guess that this may induce a dramatic increase in the price of energy, an event that at the moment will penalize much more the chance of a quick economic development of India.

Mineral zoning and geochemistry of epithermal polymetallic Zn-Pb-Ag-Cu-Bi mineralization at Cerro de Pasco, Peru

The large Cerro de Pasco Cordilleran base metal deposit in central Peru is located on the eastern margin of a middle Miocene diatreme-dome complex and comprises two mineralization stages. The first stage consists of a large pyrite-quartz body replacing Lower Mesozoic Pucara carbonate rocks and, to a lesser extent, diatreme breccia. This body is composed of pyrite with pyrrhotite inclusions, quartz, and black and red chalcedony (containing hypogene hematite). At the contact with the pyrite-quartz body, the diatreme breccia is altered to pyrite-quartz-sericite-pyrite. This body was, in part, replaced by pipelike pyrrhotite bodies zoned outward to carbonate-replacement Zn-Pb ores hearing Fe-rich sphalerite (up to 24 mol % Fes). The second mineralization stage is partly superimposed on the first and consists of zoned east-west-trending Cu-Ag-(Au-Zn-Pb) enargite-pyrite veins hosted in the diatreme breccia in the western part of the deposit and well-zoned Zn-Pb-(Bi-Ag-Cu) carbonate-replacement orebodies; in both cases, sphalerite is Fe poor and the inner parts of the orebodies show typically advanced argillic alteration assemblages, including aluminum phosphate Sulfate (APS) minerals. The zoned enargite-pyrite veins display mineral zoning, from a core of enargite-pyrite +/- alunite with traces of Au, through an intermediate zone of tennantite, chalcopyrite, and Bi minerals to a poorly developed Outer zone hearing sphalerite-galena +/- kaolinite. The carbonate-hosted replacement ores are controlled along N 35 degrees E, N 90 degrees E, N 120 degrees E, and N 170 degrees E faults. They form well-zoned upward-flaring pipelike orebodies with a core of famatinite-pyrite and alunite, an intermediate zone with tetrahedrite-pyrite, chalcopyrite, matildite, cuprobismutite, emplectite, and other Bi minerals accompanied by APS minerals, kaolinite, and dickite, and an outer zone composed of Fe-poor sphalerite (in the range of 0.05-3.5 mol % Fes) and galena. The outermost zone consists of hematite, magnetite, and Fe-Mn-Zn-Ca-Mg carbonates. Most of the second-stage carbonate-replacement orebodies plunge between 25 degrees and 60 degrees to the west, suggesting that the hydrothermal fluids ascended from deeper levels and that no lateral feeding from the veins to the carbonate-replacement orebodies took place. In the Venencocha and Santa Rosa areas, located 2.5 km northwest of the Cerro de Pasco open pit and in the southern part of the deposit, respectively, advanced argillic altered dacitic domes and oxidized veins with advanced argillic alteration halos occur. The latter veins are possibly the oxidized equivalent of the second-stage enargite-pyrite veins located in the western part of the deposit. The alteration assemblage quartz-muscovite-pyrite associated with the pyrite-quartz body suggests that the first stage precipitated at slightly, acidic fin. The sulfide mineral assemblages define an evolutionary path close to the pyrite-pyrrhotite boundary and are characteristic of low-sulfidation states; they suggest that the oxidizing slightly acidic hydrothermal fluid was buffered by phyllite, shale, and carbonate host rock. However, the presence in the pyrite-quartz body of hematite within quartz suggests that, locally, the fluids were less buffered by the host rock. The mineral assemblages of the second mineralization stage are characteristic of high- to intermediate-sulfidation states. High-sulfidation states and oxidizing conditions were achieved and maintained in the cores of the second-stage orebodies, even in those replacing carbonate rocks. The observation that, in places, second-stage mineral assemblages are found in the inner and outer zones is explained in terms of the hydrothermal fluid advancing and waning. Microthermometric data from fluid inclusions in quartz indicate that the different ores of the first mineralization stage formed at similar temperatures and moderate salinities (200 degrees-275 degrees C and 0.2-6.8 wt % NaCl equiv in the pyrite-quartz body; 192 degrees-250 degrees C and 1.1-4.3 wt % NaCl equiv in the pyrrhotite bodies; and 183 degrees-212 degrees C and 3.2-4.0 wt % NaCl equiv in the Zn-Pb ores). These values are similar to those obtained for fluid inclusions in quartz and sphalerite from the second-stage ores (187 degrees-293 degrees C and 0.2-5.2 wt % NaCl equiv in the enargite-pyrite veins: 178 degrees-265 degrees C and 0.2-7.5 wt % NaCl equiv in quartz of carbonate-replacement orebodies; 168 degrees-999 degrees C and 3-11.8 wt % NaCl equiv in sphalerite of carbonate-replacement orebodies; and 245 degrees-261 degrees C and 3.2-7.7 wt % NaCl equiv in quartz from Venencocha). Oxygen and hydrogen isotope compositions oil kaolinite from carbonate-replacement orebodies (delta(18)O = 5.3-11.5%o, delta D = -82 to -114%o) and on alunite from the Venencocha and Santa Rosa areas (delta(18)O = 1.9-6.9%o, delta D = -56 to -73%o). Oxygen isotope compositions of quartz from the first and second stages have 6180 values from 9.1 to 1.7.8 per mil. Calculated fluids in equilibrium with kaolinite have delta(18)O values of 2.0 to 8.2 and delta D values of -69 to -97 per mil; values in equilibrium with alunite are -1.4 to -6.4 and -62 to -79 per mil. Sulfur isotope compositions of sulfides from both stages have a narrow range of delta(34)S values, between -3.7 and +4.2 per mil; values for sulfates from the second stage are between 4.2 and 31.2 per mil. These results define two mixing trends for the ore-forming fluids. The first trend reflects mixing between a moderately saline (similar to 10 wt % NaCl equiv) magmatic end member that had degassed (as indicated by the low delta D values) and meteoric water. The second mixing indicates condensation of magmatic vapor with HCl and SO(2) into meteoric water, which formed alunite. The hydrothermal system at Cerro de Pasco was emplaced at a shallow depth (similar to 500 m) in the epithermal and upper part of a porphyry environment. The similar temperatures and salinities obtained for the first stage and second stages, together with the stable isotope data, indicate that both stages are linked and represent successive stages of epithermal polymetallic mineralization in the upper part of a porphyry system.