Task assignment optimization in SAP Extended WarehouseManagement

Nowadays in the world of mass consumption there is big demand for distributioncenters of bigger size. Managing such a center is a very complex and difficult taskregarding to the different processes and factors in a usual warehouse when we want tominimize the labor costs. Most of the workers’ working time is spent with travelingbetween source and destination points which cause deadheading. Even if a worker knowsthe structure of a warehouse well and because of that he or she can find the shortest pathbetween two points, it is still not guaranteed that there won’t be long traveling timebetween the locations of two consecutive tasks. We need optimal assignments betweentasks and workers.In the scientific literature Generalized Assignment Problem (GAP) is a wellknownproblem which deals with the assignment of m workers to n tasks consideringseveral constraints. The primary purpose of my thesis project was to choose a heuristics(genetic algorithm, tabu search or ant colony optimization) to be implemented into SAPExtended Warehouse Management (SAP EWM) by with task assignment will be moreeffective between tasks and resources.After system analysis I had to realize that due different constraints and businessdemands only 1:1 assingments are allowed in SAP EWM. Because of that I had to use adifferent and simpler approach – instead of the introduced heuristics – which could gainbetter assignments during the test phase in several cases. In the thesis I described indetails what ware the most important questions and problems which emerged during theplanning of my optimized assignment method.

Classification of petroleum well drilling operations with a hybrid particle swarm/ant colony algorithm

This paper describes an investigation of the hybrid PSO/ACO algorithm to classify automatically the well drilling operation stages. The method feasibility is demonstrated by its application to real mud-logging dataset. The results are compared with bio-inspired methods, and rule induction and decision tree algorithms for data mining. © 2009 Springer Berlin Heidelberg.

Architecture for peer-to-peer databases with routing queries using ant colony algorithm and semantic support

In a peer-to-peer network, the nodes interact with each other by sharing resources, services and information. Many applications have been developed using such networks, being a class of such applications are peer-to-peer databases. The peer-to-peer databases systems allow the sharing of unstructured data, being able to integrate data from several sources, without the need of large investments, because they are used existing repositories. However, the high flexibility and dynamicity of networks the network, as well as the absence of a centralized management of information, becomes complex the process of locating information among various participants in the network. In this context, this paper presents original contributions by a proposed architecture for a routing system that uses the Ant Colony algorithm to optimize the search for desired information supported by ontologies to add semantics to shared data, enabling integration among heterogeneous databases and the while seeking to reduce the message traffic on the network without causing losses in the amount of responses, confirmed by the improve of 22.5% in this amount. © 2011 IEEE.

Algoritmos de alinhamento múltiplo e técnicas de otimização para esses algoritmos utilizando Ant Colony

Pós-graduação em Ciência da Computação - IBILCE

An evolutionary approach to the design of experiments for combinatorial optimization with an application to enzyme engineering

In a large number of problems the high dimensionality of the search space, the vast number of variables and the economical constrains limit the ability of classical techniques to reach the optimum of a function, known or unknown. In this thesis we investigate the possibility to combine approaches from advanced statistics and optimization algorithms in such a way to better explore the combinatorial search space and to increase the performance of the approaches. To this purpose we propose two methods: (i) Model Based Ant Colony Design and (ii) Naïve Bayes Ant Colony Optimization. We test the performance of the two proposed solutions on a simulation study and we apply the novel techniques on an appplication in the field of Enzyme Engineering and Design.

An Ant Colony System adaptation to deal with accessibility issues after a disaster

One of the main problems relief teams face after a natural or man-made disaster is how to plan rural road repair work tasks to take maximum advantage of the limited available financial and human resources. Previous research focused on speeding up repair work or on selecting the location of health centers to minimize transport times for injured citizens. In spite of the good results, this research does not take into account another key factor: survivor accessibility to resources. In this paper we account for the accessibility issue, that is, we maximize the number of survivors that reach the nearest regional center (cities where economic and social activity is concentrated) in a minimum time by planning which rural roads should be repaired given the available financial and human resources. This is a combinatorial problem since the number of connections between cities and regional centers grows exponentially with the problem size, and exact methods are no good for achieving an optimum solution. In order to solve the problem we propose using an Ant Colony System adaptation, which is based on ants? foraging behavior. Ants stochastically build minimal paths to regional centers and decide if damaged roads are repaired on the basis of pheromone levels, accessibility heuristic information and the available budget. The proposed algorithm is illustrated by means of an example regarding the 2010 Haiti earthquake, and its performance is compared with another metaheuristic, GRASP.

Exploring ant-based algorithms for gene expression data analysis

Objective: Recently, much research has been proposed using nature inspired algorithms to perform complex machine learning tasks. Ant colony optimization (ACO) is one such algorithm based on swarm intelligence and is derived from a model inspired by the collective foraging behavior of ants. Taking advantage of the ACO in traits such as self-organization and robustness, this paper investigates ant-based algorithms for gene expression data clustering and associative classification. Methods and material: An ant-based clustering (Ant-C) and an ant-based association rule mining (Ant-ARM) algorithms are proposed for gene expression data analysis. The proposed algorithms make use of the natural behavior of ants such as cooperation and adaptation to allow for a flexible robust search for a good candidate solution. Results: Ant-C has been tested on the three datasets selected from the Stanford Genomic Resource Database and achieved relatively high accuracy compared to other classical clustering methods. Ant-ARM has been tested on the acute lymphoblastic leukemia (ALL)/acute myeloid leukemia (AML) dataset and generated about 30 classification rules with high accuracy. Conclusions: Ant-C can generate optimal number of clusters without incorporating any other algorithms such as K-means or agglomerative hierarchical clustering. For associative classification, while a few of the well-known algorithms such as Apriori, FP-growth and Magnum Opus are unable to mine any association rules from the ALL/AML dataset within a reasonable period of time, Ant-ARM is able to extract associative classification rules.

A novel hybrid evolutionary algorithm based on ACO and SA for distribution feeder reconfiguration with regard to DGs

This paper presents an efficient hybrid evolutionary optimization algorithm based on combining Ant Colony Optimization (ACO) and Simulated Annealing (SA), called ACO-SA, for distribution feeder reconfiguration (DFR) considering Distributed Generators (DGs). Due to private ownership of DGs, a cost based compensation method is used to encourage DGs in active and reactive power generation. The objective function is summation of electrical energy generated by DGs and substation bus (main bus) in the next day. The approach is tested on a real distribution feeder. The simulation results show that the proposed evolutionary optimization algorithm is robust and suitable for solving DFR problem.

A hybrid evolutionary algorithm based on ACO and SA for distribution feeder reconfiguration

This paper deals with an efficient hybrid evolutionary optimization algorithm in accordance with combining the ant colony optimization (ACO) and the simulated annealing (SA), so called ACO-SA. The distribution feeder reconfiguration (DFR) is known as one of the most important control schemes in the distribution networks, which can be affected by distributed generations (DGs) for the multi-objective DFR. In such a case, DGs is used to minimize the real power loss, the deviation of nodes voltage and the number of switching operations. The approach is carried out on a real distribution feeder, where the simulation results show that the proposed evolutionary optimization algorithm is robust and suitable for solving the DFR problem.

Detection of multiple source locations using a glowworm metaphor with applications to collective robotics

This paper presents a glowworm swarm based algorithm that finds solutions to optimization of multiple optima continuous functions. The algorithm is a variant of a well known ant-colony optimization (ACO) technique, but with several significant modifications. Similar to how each moving region in the ACO technique is associated with a pheromone value, the agents in our algorithm carry a luminescence quantity along with them. Agents are thought of as glowworms that emit a light whose intensity is proportional to the associated luminescence and have a circular sensor range. The glowworms depend on a local-decision domain to compute their movements. Simulations demonstrate the efficacy of the proposed glowworm based algorithm in capturing multiple optima of a multimodal function. The above optimization scenario solves problems where a collection of autonomous robots is used to form a mobile sensor network. In particular, we address the problem of detecting multiple sources of a general nutrient profile that is distributed spatially on a two dimensional workspace using multiple robots.

Glowworm-inspired robot swarm for simultaneous taxis towards multiple radiation sources

This paper presents a glowworm metaphor based distributed algorithm that enables a collection of minimalist mobile robots to split into subgroups, exhibit simultaneous taxis-behavior towards, and rendezvous at multiple radiation sources such as nuclear/hazardous chemical spills and fire-origins in a fire calamity. The algorithm is based on a glowworm swarm optimization (GSO) technique that finds multiple optima of multimodal functions. The algorithm is in the same spirit as the ant-colony optimization (ACO) algorithms, but with several significant differences. The agents in the glowworm algorithm carry a luminescence quantity called luciferin along with them. Agents are thought of as glowworms that emit a light whose intensity is proportional to the associated luciferin. The key feature that is responsible for the working of the algorithm is the use of an adaptive local-decision domain, which we use effectively to detect the multiple source locations of interest. The glowworms have a finite sensor range which defines a hard limit on the local-decision domain used to compute their movements. Extensive simulations validate the feasibility of applying the glowworm algorithm to the problem of multiple source localization. We build four wheeled robots called glowworms to conduct our experiments. We use a preliminary experiment to demonstrate the basic behavioral primitives that enable each glowworm to exhibit taxis behavior towards source locations and later demonstrate a sound localization task using a set of four glowworms.

Generating artificial chromosomes with probability control in genetic algorithm for machine scheduling problems

In this paper, a novel genetic algorithm is developed by generating artificial chromosomes with probability control to solve the machine scheduling problems. Generating artificial chromosomes for Genetic Algorithm (ACGA) is closely related to Evolutionary Algorithms Based on Probabilistic Models (EAPM). The artificial chromosomes are generated by a probability model that extracts the gene information from current population. ACGA is considered as a hybrid algorithm because both the conventional genetic operators and a probability model are integrated. The ACGA proposed in this paper, further employs the ``evaporation concept'' applied in Ant Colony Optimization (ACO) to solve the permutation flowshop problem. The ``evaporation concept'' is used to reduce the effect of past experience and to explore new alternative solutions. In this paper, we propose three different methods for the probability of evaporation. This probability of evaporation is applied as soon as a job is assigned to a position in the permutation flowshop problem. Experimental results show that our ACGA with the evaporation concept gives better performance than some algorithms in the literature.

Computational algorithms inspired by biological processes and evolution

In recent times computational algorithms inspired by biological processes and evolution are gaining much popularity for solving science and engineering problems. These algorithms are broadly classified into evolutionary computation and swarm intelligence algorithms, which are derived based on the analogy of natural evolution and biological activities. These include genetic algorithms, genetic programming, differential evolution, particle swarm optimization, ant colony optimization, artificial neural networks, etc. The algorithms being random-search techniques, use some heuristics to guide the search towards optimal solution and speed-up the convergence to obtain the global optimal solutions. The bio-inspired methods have several attractive features and advantages compared to conventional optimization solvers. They also facilitate the advantage of simulation and optimization environment simultaneously to solve hard-to-define (in simple expressions), real-world problems. These biologically inspired methods have provided novel ways of problem-solving for practical problems in traffic routing, networking, games, industry, robotics, economics, mechanical, chemical, electrical, civil, water resources and others fields. This article discusses the key features and development of bio-inspired computational algorithms, and their scope for application in science and engineering fields.

NEW METHODOLOGY FOR FEEDER RECONFIGURATION IN DISTRIBUTION NETWORKS WITH DISTRIBUTED ENERGY RESOURCES

This doctoral Thesis defines and develops a new methodology for feeder reconfiguration in distribution networks with Distributed Energy Resources (DER). The proposed methodology is based on metaheuristic Ant Colony Optimization (ACO) algorithms. The methodology is called Item Oriented Ant System (IOAS) and the doctoral Thesis also defines three variations of the original methodology, Item Oriented Ant Colony System (IOACS), Item Oriented Max-min Ant System (IOMMAS) y Item Oriented Max-min Ant Colony System (IOACS). All methodologies pursue a twofold objective, to minimize the power losses and maximize DER penetration in distribution networks. The aim of the variations is to find the algorithm that adapts better to the present optimization problem, solving it most efficiently. The main feature of the methodology lies in the fact that the heuristic information and the exploitation information (pheromone) are attached to the item not to the path. Besides, the doctoral Thesis proposes to use feeder reconfiguration in order to increase the distribution network capacity of accepting a major degree of DER. The proposed methodology and its three variations have been tested and verified in two distribution networks well documented in the existing bibliography. These networks have been modeled and used to test all proposed methodologies for different scenarios with various DER penetration degrees.

Determinação de uma fonte de contaminantes no estuário do Rio Macaé através da técnica de problemas inversos

Um grande desafio da atualidade é a preservação dos recursos hídricos, bem como o correto manejo dos mesmos, frente à expansão das cidades e às atividades humanas. A qualidade de um corpo hídrico é usualmente avaliada através da análise de parâmetros biológicos, físicos e químicos. O comportamento de tais parâmetros pode convenientemente ser simulado através de modelos matemáticos e computacionais, que surgem assim como uma ferramenta bastante útil, por sua capacidade de geração de cenários que possam embasar, por exemplo, tomadas de decisão. Nesta tese são discutidas técnicas de estimação da localização e intensidade de uma fonte de contaminante conservativo, hipoteticamente lançado na região predominantemente fluvial de um estuário. O lançamento aqui considerado se dá de forma pontual e contínua e a região enfocada compreendeu o estuário do Rio Macaé, localizado na costa norte do Rio de Janeiro. O trabalho compreende a solução de um problema direto, que consiste no transporte bidimensional (integrado na vertical) desse contaminante hipotético, bem como a aplicação de técnicas de problemas inversos. Para a solução do transporte do contaminante, aqui modelada pela versão 2D horizontal da equação de advecção-difusão, foram utilizados como métodos de discretização o Método de Elementos Finitos e o Método de Diferenças Finitas. Para o problema hidrodinâmico foram utilizados dados de uma solução já desenvolvida para estuário do Rio Macaé. Analisada a malha de acordo com o método de discretização, foram definidas a geometria do estuário e os parâmetros hidrodinâmicos e de transporte. Para a estimação dos parâmetros propostos foi utilizada a técnica de problemas inversos, com o uso dos métodos Luus-Jaakola, Algoritmo de Colisão de Partículas e Otimização por Colônia de Formigas para a estimação da localização e do método Seção Áurea para a estimação do parâmetro de intensidade da fonte. Para a definição de uma fonte, com o objetivo de propor um cenário experimental idealizado e de coleta de dados de amostragem, foi realizada a análise de sensibilidade quanto aos parâmetros a serem estimados. Como os dados de amostragem de concentração foram sintéticos, o problema inverso foi resolvido utilizando-os com e sem ruído, esse introduzido de forma artificial e aleatória. Sem o uso de ruído, os três métodos mostraram-se igualmente eficientes, com uma estimação precisa em 95% das execuções. Já com o uso de dados de amostragem com ruídos de 5%, o método Luus-Jaakola mostrou-se mais eficiente em esforço e custo computacional, embora todos tenham estimado precisamente a fonte em 80% das execuções. Considerando os resultados alcançados neste trabalho tem-se que é possível estimar uma fonte de constituintes, quanto à sua localização e intensidade, através da técnica de problemas inversos. Além disso, os métodos aplicados mostraram-se eficientes na estimação de tais parâmetros, com estimações precisas para a maioria de suas execuções. Sendo assim, o estudo do comportamento de contaminantes, e principalmente da identificação de fontes externas, torna-se uma importante ferramenta para a gestão dos recursos hídricos, possibilitando, inclusive, a identificação de possíveis responsáveis por passivos ambientais.