We propose a large neighborhood search (LNS) algorithm to solve the periodic location routing problem (PLRP). The PLRP combines location and routing decisions over a planning horizon in which customers require visits according to a given frequency and the specific visit days can be chosen. We use parallelization strategies that can exploit the availability of multiple processors. The computational results show that the algorithms obtain better results than previous solution methods on a set of standard benchmark instances from the literature.

Orientador: Daniela Renata Cantane / Resumo: Originadas na década de 1970, as Infecções Hospitalares vêm cada vez mais tomando proporções colossais, acarretando óbito em cerca de 30% dos pacientes em Unidades de Terapia Intensiva (UTI). Os pacientes diagnosticados com a infecções permanecem muito tempo internados, gerando um custo muito alto para os hospitais. No ambiente hospitalar a bactéria Acinetobacter baumannii a principal responsável por tais infecções, devido a sua facilidade de sobreviver em ambientes secos e úmidos, podendo sobreviver tanto no organismo humano, quanto nos ambientes que os profissionais da saúde entram em contato (computadores, equipamentos médicos, etc). Os principais vetores desta bactéria são os próprios agentes de saúde, visto que os pacientes na UTI estão todos acamados. No entanto, medidas de higienização extremamente necessárias para conter surtos da infecções o. Por outro lado, devido as emergências nestas unidades, muitas vezes não há tempo hábil para tais procedimentos. Visto que impossível uma medida total de higienização e uma taxa nula de contato da equipe de trabalho com o ambiente em UTIs, importante conhecer quais são as mínimas medidas necessárias para a diminuição de infecções hospitalares. Neste contexto, o objetivo deste trabalho propor e analisar um modelo que descreva a dinâmica de transmissão da infecção dentro de uma UTI, considerando pacientes e profissionais da saúde, assim como, propor um modelo de otimização visando determinar quais as mínimas medidas de higienização... (Resumo completo, clicar acesso eletrônico abaixo) / Abstract: Originated in the 1970s, Hospital Infections come every time more taking colossal proportions, causing death in about 30% of patients in Intensive Care Units (ICU). Patients diagnosed with infections remain long hospitalized, generating a very high cost for hospitals. In the hospital environment, Acinetobacter baumannii is the main responsible for such infections due to their ease of survival in dry and humid, and can survive both in the human body and in the environments that health workers contact (computers, medical equipment, etc.). The main vectors of this bacterium are the health agents themselves, since the patients in the ICU are all bedridden. However, hygiene measures are extremely necessary to contain outbreaks of infection. On the other hand, due to emergencies in these units, there is often no time for such procedures. Since a total sanitation measure and it is important to know the minimum measures necessary for the decrease of infections. In this context, the objective xiii of this work is to propose and analyze a model that describes the dynamics of transmission of infection within an ICU, considering patients and health professionals, as well as to propose an optimization model aiming to determine the minimum hygienic measures are needed to minimize the number of infected patients. A Variable Neighborhood Search Metaheuristic was proposed to solve the optimization model. For validation of the models were carried out computational simulations. These simulation... (Complete abstract click electronic access below) / Mestre

The Weapon Target Assignment (WTA) problem is a fundamental problem arising in defense-related applications of operations research. This problem consists of optimally assigning n weapons to m targets so that the total expected survival value of the targets after all the engagements is minimum. The WTA problem can be formulated as a nonlinear integer programming problem and is known to be NP-complete. There do not exist any exact methods for the WTA problem which can solve even small size problems (for example, with 20 weapons and 20 targets). Though several heuristic methods have been proposed to solve the WTA problem, due to the absence of exact methods, no estimates are available on the quality of solutions produced by such heuristics. In this paper, we suggest linear programming, integer programming, and network flow based lower bounding methods using which we obtain several branch and bound algorithms for the WTA problem. We also propose a network flow based construction heuristic and a very large-scale neighborhood (VLSN) search algorithm. We present computational results of our algorithms which indicate that we can solve moderately large size instances (up to 80 weapons and 80 targets) of the WTA problem optimally and obtain almost optimal solutions of fairly large instances (up to 200 weapons and 200 targets) within a few seconds

Pickup and Delivery Problems (PDPs) constitute a class of Vehicle Routing Problems (VRPs) consisting of finding the optimal routes for a fleet of vehicles to deliver requests from a set of origin locations to a corresponding set of destinations. PDPs are NP-hard and have a wide variety of variants and potential constraints. This thesis evaluates methods for solving a dynamic single- vehicle PDP restricted by multiple time-related constraints. The problem is dynamic in the sense that new requests arrive as time is simulated and inserted into the vehicle’s pickup and delivery plan as it is being executed. The time- related constraints include limited time windows during which the requests may be picked up or delivered, as well as maximum ride times that items may spend in the vehicle before being delivered. To solve the problem, we adapt insertion heuristics based on Large Neighborhood Search (LNS) and Heuristic Destroy and Repair (HDR) to the problem and evaluate them in a comparative study. Solution methods for the PDP are also applied on the problem of dynamically assigning incoming orders to vehicles in a delivery service with a short planning horizon. A PDP-based order assignment strategy is compared with assignment strategies based on proximity and workload. Due to the short planning horizon of the target application, the study is focused on finding well-performing methods for quickly solving small PDPs containing 10-15 requests. Our results indicate that LNS outperforms HDR for small problem instances. However, the quick convergence of HDR allows it to outperform LNS for larger problem instances. We also show that applying a PDP- based assignment strategy in the order assignment problem allows the service to accommodate more requests than the alternative assignment strategies while simultaneously providing a significant reduction in operational costs. Future work may improve the order assignment strategy by incorporating more anticipatory functionality and streamlining the PDP methods with more efficient tests for the feasibility of solutions. / Pickup and Delivery Problems (PDP:er) utgör en grupp av Vehicle Routing Problems (VRP:er) som består av att hitta de optimala rutterna för en fordonsflotta för att leverera beställningar från en uppsättning av upplockningsplatser till motsvarande uppsättning av avlämningsplatser. PDP:er är NP-svåra och har en stor mängd olika varianter och potentiella begränsningar. Denna avhandling utvärderar metoder för att lösa ett dynamiskt enkel-fordon PDP med flera tidsrelaterade begränsningar. Problemet är dynamiskt i den mening att nya beställnigar anländer i samband med att tiden simuleras och sätts in i fordonets leveransplan samtidigt som den utförs. De tidsrelaterade begränsningarna innefattar begränsade tidsfönstren under vilka beställningar kan plockas upp eller lämnas av, samt maximala tider som hämtade föremål får tillbringa i fordonet innan de lämnas av. För att lösa problemet anpassar vi insättningsheuristiker baserade på Large Neighborhood Search (LNS) och Heuristic Destroy and Repair (HDR) till problemet och utvärderar dem i en jämförande studie. Lösningsmetoder för PDP tillämpas också på problemet att dynamiskt tilldela inkommande beställningar till fordon i en leveransservice med en kort planeringshorisont. En PDP-baserad tilldelningsstrategi jämförs med strategier baserade på närhet och arbetsbelastning. På grund av målapplikationens korta planeringshorisont så fokuserar studien på att hitta väl presterande metoder för att snabbt lösa små PDP:er som innehåller 10-15 förfrågningar. Våra resultat indikerar att LNS överträffar HDR för små probleminstanser. Däremot leder den snabba konvergensen av HDR till att den överträffar LNS för större probleminstanser. Vi visar också att tillämpningen av en PDP-baserad tilldelningsstrategi i tilldelningsproblemet gör att tjänsten kan tillgodose fler beställningar än de alternativa tilldelningsstrategierna, samtidigt som det ger en betydlig minskning av driftskostnaderna. Framtida arbete kan förbättra tilldelningsstrategin genom att integrera mer förutseende funktionalitet och effektivisera PDP-metoderna med ett mer effektivt test av genomförbarhet för lösningar.

La programmation par contraintes est souvent décrite, utopiquement, comme un paradigme déclaratif dans lequel l’utilisateur décrit son problème et le solveur le résout. Bien entendu, la réalité des solveurs de contraintes est plus complexe, et les besoins de personnalisation des techniques de modélisation et de résolution évoluent avec le degré d’expertise des utilisateurs. Cette thèse porte sur l’enrichissement de l’arsenal des techniques disponibles dans les solveurs de contraintes. D’une part, nous étudions la contribution d’un système d’explications à l’exploration de l’espace de recherche, dans le cadre spécifique d’une recherche locale. Deux heuristiques de voisinages génériques exploitant singulièrement les explications sont décrites. La première se base sur la difficulté de réparer une solution partiellement détruite, la seconde repose sur la nature non-optimale de la solution courante. Ces heuristiques mettent à jour la structure interne des problèmes traités pour construire des voisins de bonne qualité pour une recherche à voisinage large. Elles sont complémentaires d’autres heuristiques de voisinages génériques, avec lesquels elles peuvent être combinées efficacement. De plus, nous proposons de rendre le système d’explications paresseux afin d’en minimiser l’empreinte. D’autre part, nous effectuons un état des lieux des savoir-faire relatifs aux moteurs de propagation pour les solveurs de contraintes. Ces données sont exploitées opérationnellement à travers un langage dédié qui permet de personnaliser la propagation au sein d’un solveur, en fournissant des structures d’implémentation et en définissant des points de contrôle dans le solveur. Ce langage offre des concepts de haut niveau permettant à l’utilisateur d’ignorer les détails de mise en œuvre du solveur, tout en conservant un bon niveau de flexibilité et certaines garanties. Il permet l’expression de schémas de propagation spécifiques à la structure interne de chaque problème. La mise en œuvre et les expérimentations ont été effectués dans le solveur de contraintes Choco. Cette thèse a donné lieu à une nouvelle version de l’outil globalement plus efficace et nativement expliqué. / Constraint programming is often described, idealistically, as a declarative paradigm in which the user describes the problem and the solver solves it. Obviously, the reality of constraint solvers is more complex, and the needs in customization of modeling and solving techniques change with the level of expertise of users. This thesis focuses on enriching the arsenal of available techniques in constraint solvers. On the one hand, we study the contribution of an explanation system to the exploration of the search space in the specific context of a local search. Two generic neighborhood heuristics which exploit explanations singularly are described. The first one is based on the difficulty of repairing a partially destroyed solution, the second one is based on the non-optimal nature of the current solution. These heuristics discover the internal structure of the problems to build good neighbors for large neighborhood search. They are complementary to other generic neighborhood heuristics, with which they can be combined effectively. In addition, we propose to make the explanation system lazy in order to minimize its footprint. On the other hand, we undertake an inventory of know-how relative to propagation engines of constraint solvers. These data are used operationally through a domain specific language that allows users to customize the propagation schema, providing implementation structures and defining check points within the solver. This language offershigh-level concepts that allow the user to ignore the implementation details, while maintaining a good level of flexibility and some guarantees. It allows the expression of propagation schemas specific to the internal structure of each problem solved. Implementation and experiments were carried out in the Choco constraint solver, developed in this thesis. This has resulted in a new version of the overall effectiveness and natively explained tool.

Orientador: Rubén Augusto Romero Lázaro / Banca: José Roberto Sanches Mantovani / Banca: Antonio Padilha Feltrin / Banca: Luiz Carlos Pereira da Silva / Banca: Eduardo Nobuhiro Asada / Resumo: O Problema de Planejamento da Expansão de Sistemas de Transmissão de Energia Elétrica consiste em se escolher, entre um conjunto pré-definido de circuitos candidatos, aqueles que devem ser incorporados ao sistema de forma a minimizar os custos de investimento e operação ao e atender a demanda de energia futura ao longo de um horizonte de planejamento com confiabilidade, assumindo como conhecido o plano de geração. É considerado um problema muito complexo e difícil por se tratar de um problema não linear inteiro misto, não convexo, multimodal e altamente combinatório. Este problema tem sido solucionado usando técnicas clássicas como Decomposição ao de Benders e Branch and Bound, assim como também algoritmos heurísticos e metaheurísticas obtendo diversos resultados, mais com uma série de problemas como, por exemplo, alto esforço computacional e problemas de convergência. Neste trabalho apresentam-se duas novas técnicas de solução para o problema, a saber, as metaheurísticas Busca em Vizinhança Variável e a Busca Dispersa. A Busca em Vizinhança Variável é uma técnica baseada em trocas de estruturas de vizinhança dentro de um algoritmo de busca local, e a metaheurística Busca Dispersa, um método evolutivo que combina sistematicamente conjuntos de soluções para se obter solucões melhores. Essas técnicas de solução oferecem novas alternativas de solução que oferecem solução aos problemas encontrados com outros métodos, como é um baixo esforço computacional é uma melhor convergência, sendo este o principal aporte do trabalho. Os algoritmos são apresentados sistematicamente, explicando os seus algoritmos e a forma como são adaptados para resolver o problema do planejamento da expansão de sistemas de transmissão considerando-se a modelagem matemática conhecida com o modelo de transporte e o modelo DC. São realizados testes com os sistemas... (Resumo completo, clicar acesso eletrônico abaixo) / Abstract: Electric Energy Transmission Network Expansion Problem consist in choose among a set of pre-defined circuits candidates, who must be incorporated into the system so as to minimize the investment costs and operation and meet the future energy demand over a planning horizon with reliability, assuming the generation plan is known. It is a very complex and difficult problem because it is non linear, non convex, multimodal and highly combinatorial. This problem has been solved using traditional techniques such as Benders decomposition and Branch and Bound, as well as heuristic algorithms and metaheuristics getting different results, but with a series of problems such as high computational effort and convergence problems. This paper tests out two new techniques for solving the problem as are the metaheuristics Variable Neighborhood Search and Scatter Search. The Variable Neighborhood Search is a technique based on trading structures within a neighborhood of a local search algorithm, and the Scatter Search metaheuristic is a method which combines systematically sets of solutions in an evolutionary way to achieve better solutions. These solution techniques offer new alternatives to solve the problems encountered with other methods, such as a low computational effort and better convergence, which is the main contribution of this work. The techniques are presented systematically, explaining their algorithms and the way they are adapted to solve the network expansion planning problem based on the mathematical model known as the transportation model and the DC model. They are tested with the systems Southern Brazilian with 46 buses and the IEEE 24 buses system, results are compared with those obtained with other metaheuristics, obtaining excellent results with a best performance both in processing speed as in computational effort. / Doutor

In this paper,we propose an adaptive large neighborhood search heuristic for the Two-Echelon Vehicle Routing Problem (2E-VRP) and the Location Routing Problem (LRP).The 2E-VRP arises in two-level transportation systems such as those encountered in the context of city logistics. In such systems, freight arrives at a major terminal and is shipped through intermediate satellite facilities to the final customers. The LRP can be seen as a special case of the 2E-VRP in which vehicle routing is performed only at the second level. We have developed new neighborhood search operators by exploiting the structure of the two problem classes considered and have also adapted existing operators from the literature. The operators are used in a hierarchical scheme reflecting the multi-level nature of the problem. Computational experiments conducted on several sets of instances from the literature show that our algorithm out performs existing solution methods for the 2E-VRP and achieves excellent results on the LRP.

This thesis introduces a Large Neighborhood Search (LNS) method to solve a multi-processor avionics scheduling problem. In a typical scheduling problem, tasks are scheduled with exact starting times. In this thesis however, tasks will instead be assigned to disjoint time segments, called buckets. For an assignment to be feasible, precedence relations and capacity constraints related to network and computing resources need to be fulfilled. The introduced LNS method relies on solving Mixed-Integer Programming (MIP)-models. To make progress in the search for a feasible assignment, we construct a MIP-model that allows violation of the problem constraints at a cost of increased objective value. The LNS method uses two operators, a destroy operator that chooses a set of tasks that are allowed to change buckets, and a repair operator that through solving the MIP-model creates a new schedule. This thesis develops 11 types of destroy operators and 30 (concrete) variants of them. The MIP-based LNS is evaluated on a set of 60 instances with up to 84 000 tasks and 21 processors. The instances belongs to six categories of varying difficulty. The MIP-based LNS solves 50 instances within our time limit, and the largest instance solved has 77 757 tasks. This is significantly better than solving the complete MIP-model in a single step. With this approach only 36 instances can be solved within our time limit and the largest instance solved has 48554 tasks.

In this paper we consider a rich vehicle routing problem where transportation requests are characterised by multiple pickup and delivery locations. The problem is a combined load acceptance and generalised vehicle routing problem incorporating a diversity of practical complexities. Among those are time window restrictions, a heterogeneous vehicle fleet with different travel times, travel costs and capacity, multi-dimensional capacity constraints, order/vehicle compatibility constraints, and different start and end locations for vehicles. We propose iterative improvement approaches based on Large Neighborhood Search and a relatedness measure for transportation requests with multiple pickup and delivery locations. Our algorithms are characterised by very fast response times and thus, can be used within dynamic routing systems where input data can change at any time.

A novel Ant Colony Optimization (ACO) framework for a dynamic environment has been proposed in this study. This algorithm was developed to solve Dynamic Traveling Salesman Problems more efficiently than the current algorithms. Adaptive Large Neighborhood Search based immigrant schemes have been developed and compared with existing ACO-based immigrant schemes in literature to maintain diversity via transferring knowledge to the pheromone trails from previous environments. Numerical results indicate that the proposed algorithm can handle dynamicity in the environment more efficiently compared to other immigrant-based ACOs available in the literature. A real-life case study for wildlife surveillance by unmanned aerial vehicles has also been developed and solved using the proposed algorithm.