No / This paper presents a new class of heuristics which embed an exact algorithm within the framework of a local search heuristic. This approach was inspired by related heuristics which we developed for a practical problem arising in electronics manufacture. The basic idea of this heuristic is to break the original problem into small subproblems having similar properties to the original problem. These subproblems are then solved using time intensive heuristic approaches or exact algorithms and the solution is re-embedded into the original problem. The electronics manufacturing problem where we originally used the embedded local search approach, contains the Travelling Salesman Problem (TSP) as a major subproblem. In this paper we further develop our embedded search heuristic, HyperOpt, and investigate its performance for the TSP in comparison to other local search based approaches. We introduce an interesting hybrid of HyperOpt and 3-opt for asymmetric TSPs which proves more efficient than HyperOpt or 3-opt alone. Since pure local search seldom yields solutions of high quality we also investigate the performance of the approaches in an iterated local search framework. We examine iterated approaches of Large-Step Markov Chain and Variable Neighbourhood Search type and investigate their performance when used in combination with HyperOpt. We report extensive computational results to investigate the performance of our heuristic approaches for asymmetric and Euclidean Travelling Salesman Problems. While for the symmetric TSP our approaches yield solutions of comparable quality to 2-opt heuristic, the hybrid methods proposed for asymmetric problems seem capable of compensating for the time intensive embedded heuristic by finding tours of better average quality than iterated 3-opt in many less iterations and providing the best heuristic solutions known, for some instance classes.

Detta arbete syftar till att undersöka om det är möjligt att med en heuristisk metod skapa giltiga lösningar till ett problem vid planering av stränggjutningsproduktion på SSAB. Planeringsproblemet uppstår när stål av olika sorter ska gjutas under samma dag. Beroende på i vilken ordning olika kundordrar av stål gjuts uppstår spill av olika storlek. Detta spill ska minimeras och tidigare arbete har genomförts på detta problem och resulterat i en matematisk modell för att skapa lösningar till problemet. Det tar i praktiken lång tid att hitta bra lösningar med modellen och frågeställningen är om det går att göra detta med en heuristisk metod för att kunna generera bra lösningar snabbare. Med inspiration från Variable Neighbourhood Search, Simulated Annealing och tabusökning har heuristiker skapats, implementerats och utvärderats mot den matematiska modellen. En av heuristikerna presterar bättre än den matematiska modellen gör på 10 minuter. Matematiska modellens resultat efter 60 minuter körtid är bättre än den utvecklade heuristiken, men resultaten är nära varandra. Körtiden för heuristiken tar signifikant mindre tid än 10 minuter. / This study aims to investigate if it is possible to use a heuristic method to create feasible solution in a Cast Batching Problem at SSAB. The problem occurs when different kinds of steel should be cast during the same day. Depending on which order the groups of different steel is placed different amounts of waste is produced, the goal is to minimize this waste. Earlier work has been done on this problem and resulted in a mathematical model to create feasible solutions to this problem. In practice the time it takes to create good solutions are long and the question is if it is possible to use a heuristic method to generate good solutions in a shorter amount of time. Drawing upon inspiration from metaheuristics such as Variable Neighbourhood Search, Simualted Annealing and Tabu Search multiple heuristics have been created, implemented and evaluated against the mathematical model. One of the heuristics perform better than the mathematical model does in 10 minutes. The result from the mathematical model after 60 minutes is slightly better than the heuristic, but the results are similar. With regards to running time the heuristic takes considerably less time than 10 minutes.

In this thesis there is a set of waste disposal facilities, a set of customers at which waste is collected and an unlimited number of homogeneous vehicles based at a single depot. Empty vehicles leave the depot and collect waste from customers, emptying themselves at the waste disposal facilities as and when necessary. Vehicles return to the depot empty. We take into consideration time windows associated with customers, disposal facilities and the depot. We also have a driver rest period. The problem is solved heuristically. A neighbour set is defined for each customer as the set of customers that are close, but with compatible time windows. This thesis uses six different procedures to obtain initial solutions for the problem. Then, the initial solutions from these procedures are improved in terms of the distance travelled using our phase 1 and phase 2 procedures, whereas we reduce the number of vehicles used using our vehicle reduction (VR) procedure. In a further attempt to improve the solutions three metaheuristic algorithms are presented, namely tabu search (TS), variable neighbourhood search (VNS) and variable neighbourhood tabu search (VNTS). Moreover, we present a modified disposal facility positioning (DFP), reverse order and change tracking procedures. Using all these procedures presented in the thesis, four solution procedures are reported for the two benchmark problem sets, namely waste collection vehicle routing problems with time windows (VRPTW) and multi-depot vehicle routing problem with inter-depot routes (MDVRPI). Our solutions for the waste collection VRPTW problems are compared with the solutions from Kim et al (2006), and our solutions for the MDVRPI problems are compared with Crevier et al (2007). Computational results for the waste collection VRPTW problems indicate that our algorithms produce better quality solutions than Kim et al (2006) in terms of both distance travelled and number of vehicles used. However for the MDVRPI problems, solutions from Crevier et al (2007) outperform our solutions.

Made available in DSpace on 2014-06-11T19:22:36Z (GMT). No. of bitstreams: 0 Previous issue date: 2006-08-25Bitstream added on 2014-06-13T20:27:15Z : No. of bitstreams: 1 zviecovich_wg_me_ilha.pdf: 671253 bytes, checksum: fa917bf3d6aa15db73057717470be218 (MD5) / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES) / Fundação de Ensino Pesquisa e Extensão de Ilha Solteira (FEPISA) / A reconfiguração de sistemas de distribuição de energia elétrica consiste em alterar a topologia das redes através da abertura/fechamento das chaves de interconexão. Normalmente este procedimento é feito para fins de isolamento de faltas, minimização de perdas ativas, balanceamento de cargas entre alimentadores ou para melhoria dos níveis de tensão. Atingir estes objetivos é difícil, devido ao grande número de variáveis envolvidas e das restrições impostas, sendo a radialidade uma restrição de difícil representação matemática. Este problema pode ser classificado dentro dos problemas de programação não linear inteiro misto (PNLIM) e apresenta o fenômeno da explosão combinatória. Neste trabalho tem-se como principal objetivo o desenvolvimento de uma metaheurística chamada Busca em Vizinhança Variável para a reconfiguração de sistemas de distribuição de energia elétrica com respostas no planejamento da operação em função da razonalidade da carga. Verificamos que este método mostrou ser eficiente, pois através de uma metodologia simples, obteve-se resultados melhores em relação aos apresentados na literatura. / The network reconfiguration of electric power distribution consists of changing the topology of networks through the opening/closing of interconnection switches. This pro- cedure is usually done to isolate faught, reduction real power losses, balance the load among feeders or for improvement of tension levels. To reach these objectives is diffi- cult, due to the great number of involved variables and the imposed constraints, being the constraint of radial structure of difficult mathematical representation. This problem can be classified as nonlinar mixed integer programming problems and it presents the phenomenon of combinatorial explosion. The main objective og this work is to develop a metaheuristic called Variable Neighbourhood Search for network reconfiguration of elec- tric power distribution for operation planning based on rationality of load. This method showed to be efficient using a simple methodology, getting better results in relation to the presented in Literature.

Orientador: Rubén Augusto Romero Lázaro / Banca: José Roberto Sanches Mantovani / Banca: Luiz Carlos Pereira da Silva / Resumo: A reconfiguração de sistemas de distribuição de energia elétrica consiste em alterar a topologia das redes através da abertura/fechamento das chaves de interconexão. Normalmente este procedimento é feito para fins de isolamento de faltas, minimização de perdas ativas, balanceamento de cargas entre alimentadores ou para melhoria dos níveis de tensão. Atingir estes objetivos é difícil, devido ao grande número de variáveis envolvidas e das restrições impostas, sendo a radialidade uma restrição de difícil representação matemática. Este problema pode ser classificado dentro dos problemas de programação não linear inteiro misto (PNLIM) e apresenta o fenômeno da explosão combinatória. Neste trabalho tem-se como principal objetivo o desenvolvimento de uma metaheurística chamada Busca em Vizinhança Variável para a reconfiguração de sistemas de distribuição de energia elétrica com respostas no planejamento da operação em função da razonalidade da carga. Verificamos que este método mostrou ser eficiente, pois através de uma metodologia simples, obteve-se resultados melhores em relação aos apresentados na literatura. / Abstract: The network reconfiguration of electric power distribution consists of changing the topology of networks through the opening/closing of interconnection switches. This pro- cedure is usually done to isolate faught, reduction real power losses, balance the load among feeders or for improvement of tension levels. To reach these objectives is diffi- cult, due to the great number of involved variables and the imposed constraints, being the constraint of radial structure of difficult mathematical representation. This problem can be classified as nonlinar mixed integer programming problems and it presents the phenomenon of combinatorial explosion. The main objective og this work is to develop a metaheuristic called Variable Neighbourhood Search for network reconfiguration of elec- tric power distribution for operation planning based on rationality of load. This method showed to be efficient using a simple methodology, getting better results in relation to the presented in Literature. / Mestre

In this paper we study a complex real-world workforce scheduling problem. We propose a method of splitting the problem into smaller parts and solving each part using exhaustive search. These smaller parts comprise a combination of choosing a method to select a task to be scheduled and a method to allocate resources, including time, to the selected task. We use reduced Variable Neighbourhood Search (rVNS) and hyperheuristic approaches to decide which sub problems to tackle. The resulting methods are compared to local search and Genetic Algorithm approaches. Parallelisation is used to perform nearly one CPU-year of experiments. The results show that the new methods can produce results fitter than the Genetic Algorithm in less time and that they are far superior to any of their component techniques. The method used to split up the problem is generalisable and could be applied to a wide range of optimisation problems.

In this paper, we study a rich vehicle routing problem incorporating various complexities found in real-life applications. The General Vehicle Routing Problem (GVRP) is a combined load acceptance and generalised vehicle routing problem. Among the real-life requirements are time window restrictions, a heterogeneous vehicle fleet with different travel times, travel costs and capacity, multi-dimensional capacity constraints, order/vehicle compatibility constraints, orders with multiple pickup, delivery and service locations, different start and end locations for vehicles, and route restrictions for vehicles. The GVRP is highly constrained and the search space is likely to contain many solutions such that it is impossible to go from one solution to another using a single neighbourhood structure. Therefore, we propose iterative improvement approaches based on the idea of changing the neighbourhood structure during the search.

Résumé indisponible. / A healthcare network or health system consists of all organizations, actions and people who participate to promote, restore or maintain people’s health. The health care systems in many developed countries are facing increasing costs. The major reason is the changing age distribution of the population with more elderly people in need of support. Increasing healthcare costs has created new alternatives to traditional hospitalization in which one is Home Health Care (HHC). Home health care or domiciliary care is the provision of health care and assistance to people in their own homes, according to a formal assessment of their needs. HHC has attained a specific place in healthcare network. HHC programs have now been successfully implemented in many countries. The purpose of HHC is to provide the care and support needed to assist patients to live independently in their own homes. HHC is primarily performed by means of personal visitations of healthcare workers to patients in their homes, where they provide care assistance according to patients’ needs. In this thesis we have considered different aspects of planning problems for home health care services. The efficient use of resources is necessary in continuous healthcare services. To meet the increased demand of HHC, operation research specialist can play an important role by solving the various combinatorial optimization problems arising in HHC. These problems can be tactical, strategic or operational with respect to planning horizon. Strategic problems are those which help in attaining long term goals or objectives, e.g. higher level of quality for HHC patients and efficient use of resources. These strategic objectives can be achieved through tactical i.e. medium term panning and operational planning i.e. short term planning. The main purpose of our thesis is to identify these potential optimization problems and solve them via recent metaheuristics. HHC is an alternative to traditional hospitalization and has got a significant share in the organization of healthcare in developed countries. The change in aging demographics, recent development in technology and the increase in the demand of healthcare services are major reasons for this rapid growth. Some studies show HHC as a tool to reduce costs of care, which is a major preoccupation in developed countries. Some others reveal that it leads to the improvement of patients’ satisfaction without increasing the resources. Home health care, i.e. visiting and nursing patients in their homes, is a flourishing realm in the medical industry. The number of companies has grown largely both in public and private sectors. The staffing needs for HHC companies have been expanded as well. Also they face the problem of assigning geographically dispersed patients to home healthcare workers and preparing daily schedules for these workers. The challenge of this problem is to combine aspects of vehicle routing and staff rostering. Both of them are well known NP- hard combinatorial optimization problems, it means the amount of computational time required to find solution increases exponentially with problem size. Home healthcare workers scheduling problem is difficult to solve optimally due to presence of large number of constraints. These are two types of constraints: hard constraints and soft constraints. The hard constraints are the restrictions to be fulfilled for the schedules to be applicable and soft constraints are preferences to improve the quality of these schedules. (...)