Reconfiguração de sistemas de distribuição operando em vários níveis de demanda através de uma meta-heurística de busca em vizinhança variável

Pós-graduação em Engenharia Elétrica - FEIS

Locating control points in aerial images with a multi-scale approach based on terrestrial image patches

Fundação de Amparo à Pesquisa do Estado de São Paulo (FAPESP)

Comparison of metaheuristic strategies for peakbin selection in proteomic mass spectrometry data

Mass spectrometry (MS) data provide a promising strategy for biomarker discovery. For this purpose, the detection of relevant peakbins in MS data is currently under intense research. Data from mass spectrometry are challenging to analyze because of their high dimensionality and the generally low number of samples available. To tackle this problem, the scientific community is becoming increasingly interested in applying feature subset selection techniques based on specialized machine learning algorithms. In this paper, we present a performance comparison of some metaheuristics: best first (BF), genetic algorithm (GA), scatter search (SS) and variable neighborhood search (VNS). Up to now, all the algorithms, except for GA, have been first applied to detect relevant peakbins in MS data. All these metaheuristic searches are embedded in two different filter and wrapper schemes coupled with Naive Bayes and SVM classifiers.

Interference of parallel cylindrical Langmuir probes

Current to a cylindrical probe of arbitrary cross section is discussed. Previous results for circular cylinders at the high bias and moderate radius R of interest for electrodynamic bare tethers, for which space charge may be ignored over a large neighborhood of the probe, depend in separate ways on both R and perimeter p. These results are extended to a general convex cross section by introducing certain equivalent radius Req. For any concave cross section, results use a proper equivalent perimeter peq , in addition to Req. Finally, for the joint cross section of separate parallel probes, certain effective perimeter peff replaces peq. Rules to determine Req. peq. and peff are used to discuss collection interference among two or more parallel cylinders when brought from far away to contact

Formulações e algoritmos para o problema das p-medianas heterogêneo livre de penalidade

This work presents a new model for the Heterogeneous p-median Problem (HPM), proposed to recover the hidden category structures present in the data provided by a sorting task procedure, a popular approach to understand heterogeneous individual’s perception of products and brands. This new model is named as the Penalty-free Heterogeneous p-median Problem (PFHPM), a single-objective version of the original problem, the HPM. The main parameter in the HPM is also eliminated, the penalty factor. It is responsible for the weighting of the objective function terms. The adjusting of this parameter controls the way that the model recovers the hidden category structures present in data, and depends on a broad knowledge of the problem. Additionally, two complementary formulations for the PFHPM are shown, both mixed integer linear programming problems. From these additional formulations lower-bounds were obtained for the PFHPM. These values were used to validate a specialized Variable Neighborhood Search (VNS) algorithm, proposed to solve the PFHPM. This algorithm provided good quality solutions for the PFHPM, solving artificial generated instances from a Monte Carlo Simulation and real data instances, even with limited computational resources. Statistical analyses presented in this work suggest that the new algorithm and model, the PFHPM, can recover more accurately the original category structures related to heterogeneous individual’s perceptions than the original model and algorithm, the HPM. Finally, an illustrative application of the PFHPM is presented, as well as some insights about some new possibilities for it, extending the new model to fuzzy environments

A Decomposition, Construction and Post-Processing Approach for Nurse Rostering

This paper presents our work on decomposing a specific nurse rostering problem by cyclically assigning blocks of shifts, which are designed considering both hard and soft constraints, to groups of nurses. The rest of the shifts are then assigned to the nurses to construct a schedule based on the one cyclically generated by blocks. The schedules obtained by decomposition and construction can be further improved by a variable neighborhood search. Significant results are obtained and compared with a genetic algorithm and a variable neighborhood search approach on a problem that was presented to us by our collaborator, ORTEC bv, The Netherlands. We believe that the approach has the potential to be further extended to solve a wider range of nurse rostering problems.

Problema del agente viajero selectivo con restricciones adicionales

En esta tesis se introduce una variante del Problema del Agente Viajero Selectivo, también conocido en la literatura como Orienteering Problem (OP). En el OP se tiene un conjunto de clientes potenciales, a cada uno de los cuales se le asocia una puntuación o beneficio que recibe el agente al visitarlo, el objetivo es el de diseñar una ruta que comience y termine en el depósito y que maximice el puntaje colectado, tomando en cuenta que existe un límite máximo en la duración de la ruta. En este trabajo se consideran restricciones de conflictos entre clientes, es decir, si dos de ellos tienen conflicto, no pueden ser incluidos ambos en la ruta; por otra parte, existe un subconjunto de clientes que deben ser visitados de manera obligatoria. Se proponen dos modelos matemáticos del problema, cuya diferencia principal es la manera en que aborda la eliminación de ciclos. El primer modelo usa restricciones de tipo secuencial inspiradas en las propuestas por Miller et al. (1960) y el segundo utiliza restricciones basadas en flujo de múltiples productos y se basan en las restricciones propuestas por Wong (1980) y Claus (1984). Asimismo, se proponen dos algoritmos para la solución del problema planteado, el primero es de tipo heurístico y está basado en un esquema GRASP (Greedy Randomized Adaptive Search Procedure) reactivo, cuya fase de mejora es un método tipo VNS (Variable Neighborhood Search) general, el segundo es una estrategia de descomposición basada en generación de columnas. El desempeño de los algoritmos propuestos es evaluado a través de experimentos computacionales sobre un gran conjunto de instancias y los resultados obtenidos son comparados contra las soluciones ´optimas obtenidas al resolver los modelos matemáticos haciendo uso del solver Cplex 12.6.

Une heuristique de recherche à voisinage variable pour le problème du voyageur de commerce avec fenêtres de temps

Nous adaptons une heuristique de recherche à voisinage variable pour traiter le problème du voyageur de commerce avec fenêtres de temps (TSPTW) lorsque l'objectif est la minimisation du temps d'arrivée au dépôt de destination. Nous utilisons des méthodes efficientes pour la vérification de la réalisabilité et de la rentabilité d'un mouvement. Nous explorons les voisinages dans des ordres permettant de réduire l'espace de recherche. La méthode résultante est compétitive avec l'état de l'art. Nous améliorons les meilleures solutions connues pour deux classes d'instances et nous fournissons les résultats de plusieurs instances du TSPTW pour la première fois.

Une heuristique de recherche à voisinage variable pour le problème du voyageur de commerce avec fenêtres de temps

Nous adaptons une heuristique de recherche à voisinage variable pour traiter le problème du voyageur de commerce avec fenêtres de temps (TSPTW) lorsque l'objectif est la minimisation du temps d'arrivée au dépôt de destination. Nous utilisons des méthodes efficientes pour la vérification de la réalisabilité et de la rentabilité d'un mouvement. Nous explorons les voisinages dans des ordres permettant de réduire l'espace de recherche. La méthode résultante est compétitive avec l'état de l'art. Nous améliorons les meilleures solutions connues pour deux classes d'instances et nous fournissons les résultats de plusieurs instances du TSPTW pour la première fois.

Ordonnancement des opérations dans une unité d’extrusion

Les travaux de ce mémoire traitent du problème d’ordonnancement et d’optimisation de la production dans un environnement de plusieurs machines en présence de contraintes sur les ressources matérielles dans une usine d’extrusion plastique. La minimisation de la somme pondérée des retards est le critère économique autour duquel s’articule cette étude car il représente un critère très important pour le respect des délais. Dans ce mémoire, nous proposons une approche exacte via une formulation mathématique capable des donner des solutions optimales et une approche heuristique qui repose sur deux méthodes de construction de solution sérielle et parallèle et un ensemble de méthodes de recherche dans le voisinage (recuit-simulé, recherche avec tabous, GRASP et algorithme génétique) avec cinq variantes de voisinages. Pour être en totale conformité avec la réalité de l’industrie du plastique, nous avons pris en considération certaines caractéristiques très fréquentes telles que les temps de changement d’outils sur les machines lorsqu’un ordre de fabrication succède à un autre sur une machine donnée. La disponibilité des extrudeuses et des matrices d’extrusion représente le goulot d’étranglement dans ce problème d’ordonnancement. Des séries d’expérimentations basées sur des problèmes tests ont été effectuées pour évaluer la qualité de la solution obtenue avec les différents algorithmes proposés. L’analyse des résultats a démontré que les méthodes de construction de solution ne sont pas suffisantes pour assurer de bons résultats et que les méthodes de recherche dans le voisinage donnent des solutions de très bonne qualité. Le choix du voisinage est important pour raffiner la qualité de la solution obtenue. Mots-clés : ordonnancement, optimisation, extrusion, formulation mathématique, heuristique, recuit-simulé, recherche avec tabous, GRASP, algorithme génétique

Vehicle routing and location routing problems with minimum latency: algorithms and models

Latency can be defined as the sum of the arrival times at the customers. Minimum latency problems are specially relevant in applications related to humanitarian logistics. This thesis presents algorithms for solving a family of vehicle routing problems with minimum latency. First the latency location routing problem (LLRP) is considered. It consists of determining the subset of depots to be opened, and the routes that a set of homogeneous capacitated vehicles must perform in order to visit a set of customers such that the sum of the demands of the customers assigned to each vehicle does not exceed the capacity of the vehicle. For solving this problem three metaheuristic algorithms combining simulated annealing and variable neighborhood descent, and an iterated local search (ILS) algorithm, are proposed. Furthermore, the multi-depot cumulative capacitated vehicle routing problem (MDCCVRP) and the multi-depot k-traveling repairman problem (MDk-TRP) are solved with the proposed ILS algorithm. The MDCCVRP is a special case of the LLRP in which all the depots can be opened, and the MDk-TRP is a special case of the MDCCVRP in which the capacity constraints are relaxed. Finally, a LLRP with stochastic travel times is studied. A two-stage stochastic programming model and a variable neighborhood search algorithm are proposed for solving the problem. Furthermore a sampling method is developed for tackling instances with an infinite number of scenarios. Extensive computational experiments show that the proposed methods are effective for solving the problems under study.

Development of an Unmanned Capsule for large-scale maritime search and rescue

This paper describes the development and testing of a robotic capsule for search and rescue operations at sea. This capsule is able to operate autonomously or remotely controlled, is transported and deployed by a larger USV into a determined disaster area and is used to carry a life raft and inflate it close to survivors in large-scale maritime disasters. The ultimate goal of this development is to endow search and rescue teams with tools that extend their operational capability in scenarios with adverse atmospheric or maritime conditions.

Search for supersymmetry in events containing a same-flavour opposite-sign dilepton pair, jets, and large missing transverse momentum in s√=8 TeV pp collisions with the ATLAS detector

Two searches for supersymmetric particles in final states containing a same-flavour opposite-sign lepton pair, jets and large missing transverse momentum are presented. The proton--proton collision data used in these searches were collected at a centre-of-mass energy s√=8 TeV by the ATLAS detector at the Large Hadron Collider and corresponds to an integrated luminosity of 20.3 fb−1. Two leptonic production mechanisms are considered: decays of squarks and gluinos with Z bosons in the final state, resulting in a peak in the dilepton invariant mass distribution around the Z-boson mass; and decays of neutralinos (e.g. χ~02→ℓ+ℓ−χ~01), resulting in a kinematic endpoint in the dilepton invariant mass distribution. For the former, an excess of events above the expected Standard Model background is observed, with a significance of 3 standard deviations. In the latter case, the data are well-described by the expected Standard Model background. The results from each channel are interpreted in the context of several supersymmetric models involving the production of squarks and gluinos.

Search for new phenomena in final states with an energetic jet and large missing transverse momentum in pp collisions at s√=8 TeV with the ATLAS detector

Results of a search for new phenomena in final states with an energetic jet and large missing transverse momentum are reported. The search uses 20.3 fb−1 of s√=8 TeV data collected in 2012 with the ATLAS detector at the LHC. Events are required to have at least one jet with pT>120 GeV and no leptons. Nine signal regions are considered with increasing missing transverse momentum requirements between EmissT>150 GeV and EmissT>700 GeV. Good agreement is observed between the number of events in data and Standard Model expectations. The results are translated into exclusion limits on models with large extra spatial dimensions, pair production of weakly interacting dark matter candidates, and production of very light gravitinos in a gauge-mediated supersymmetric model. In addition, limits on the production of an invisibly decaying Higgs-like boson leading to similar topologies in the final state are presented.

Search for metastable heavy charged particles with large ionisation energy loss in pp collisions at root s=8 TeV using the ATLAS experiment

Many extensions of the Standard Model predict the existence of charged heavy long-lived particles, such as R-hadrons or charginos. These particles, if produced at the Large Hadron Collider, should be moving non-relativistically and are therefore identifiable through the measurement of an anomalously large specific energy loss in the ATLAS pixel detector. Measuring heavy long-lived particles through their track parameters in the vicinity of the interaction vertex provides sensitivity to metastable particles with lifetimes from 0.6 ns to 30 ns. A search for such particles with the ATLAS detector at the Large Hadron Collider is presented, based on a data sample corresponding to an integrated luminosity of 18.4 fb−1 of pp collisions at s√ = 8 TeV. No significant deviation from the Standard Model background expectation is observed, and lifetime-dependent upper limits on R-hadrons and chargino production are set. Gluino R-hadrons with 10 ns lifetime and masses up to 1185 GeV are excluded at 95% confidence level, and so are charginos with 15 ns lifetime and masses up to 482 GeV.