Дисертації з теми "Local search heuristics"
Оформте джерело за APA, MLA, Chicago, Harvard та іншими стилями
Ознайомтеся з топ-43 дисертацій для дослідження на тему "Local search heuristics".
Біля кожної праці в переліку літератури доступна кнопка «Додати до бібліографії». Скористайтеся нею – і ми автоматично оформимо бібліографічне посилання на обрану працю в потрібному вам стилі цитування: APA, MLA, «Гарвард», «Чикаго», «Ванкувер» тощо.
Також ви можете завантажити повний текст наукової публікації у форматі «.pdf» та прочитати онлайн анотацію до роботи, якщо відповідні параметри наявні в метаданих.
Переглядайте дисертації для різних дисциплін та оформлюйте правильно вашу бібліографію.
Shatabda, Swakkhar. "Local Search Heuristics for Protein Structure Prediction." Thesis, Griffith University, 2014. http://hdl.handle.net/10072/365446.
Повний текст джерелаThesis (PhD Doctorate)
Doctor of Philosophy (PhD)
Institute for Integrated and Intelligent Systems
Science, Environment, Engineering and Technology
Full Text
Carson, Ted. "Empirical and analytic approaches to understanding local search heuristics /." Diss., Connect to a 24 p. preview or request complete full text in PDF format. Access restricted to UC campuses, 2001. http://wwwlib.umi.com/cr/ucsd/fullcit?p9995987.
Повний текст джерелаMagaji, Amina Sambo-Muhammad. "Combining search strategies for distributed constraint satisfaction." Thesis, Robert Gordon University, 2015. http://hdl.handle.net/10059/1374.
Повний текст джерелаHenderson, Darrall. "Assessing the Finite-Time Performance of Local Search Algorithms." Diss., Virginia Tech, 2001. http://hdl.handle.net/10919/26926.
Повний текст джерелаPh. D.
Santiago, Rafael de. "Efficient modularity density heuristics in graph clustering and their applications." reponame:Biblioteca Digital de Teses e Dissertações da UFRGS, 2017. http://hdl.handle.net/10183/164066.
Повний текст джерелаAlratrout, Serein Abdelmonam. "A hybrid multi-agent architecture and heuristics generation for solving meeting scheduling problem." Thesis, De Montfort University, 2009. http://hdl.handle.net/2086/2409.
Повний текст джерелаRosin, Rafael Alzuguir. "Heurística com busca local para solução do problema de cobertura de rotas com cardinalidade restrita." Universidade de São Paulo, 2011. http://www.teses.usp.br/teses/disponiveis/3/3148/tde-30032012-122542/.
Повний текст джерелаThe growing need to seek more efficient, lower cost and more sustainable operations has caused industries to seek opportunities in which these objectives could be achieved. In the area of transportation, collaboration is an opportunity for that. This work deals with the cardinality constrained lane covering problem (CCLCP), where companies who uses full truck loads join efforts in order to reduce empty vehicle travel through closed cycle formation. It is known as cardinality constraint problem as the maximum number of trips in the cycle is limited to an integer number, which makes this problem NP-Hard. There are two heuristics in the literature (constructive) and an integer linear programming model for solving this problem. This work presents a heuristic based on a local search method that reduced an average of 3.19% the better results in the literature. It also presents the execution times of each algorithm and the importance of choosing a good initial solution when you want to create a Local Search Heuristic.
Pehlivanoglu, Osman. "An Algorithm For The Capacitated Vehicle Routing Problem With Time Windows." Master's thesis, METU, 2005. http://etd.lib.metu.edu.tr/upload/2/12606657/index.pdf.
Повний текст джерелаs and Homberger and Gehring (1999)&rsquo
s problem sets in order to test the performance of the proposed algorithm. From the computational results encouraging results are obtained in terms of solution quality.
Sullivan, Kelly Ann. "A Convergence Analysis of Generalized Hill Climbing Algorithms." Diss., Virginia Tech, 1999. http://hdl.handle.net/10919/27027.
Повний текст джерелаPh. D.
Campos, Danilo da Silva. "Integração dos problemas de carregamento e roteamento de veículos com janela de tempo e frota heterogênea." Universidade de São Paulo, 2008. http://www.teses.usp.br/teses/disponiveis/3/3136/tde-30052008-111539/.
Повний текст джерелаThis work presents a problem not treated yet on the literature referenced as 3L-FSMVRPTW (three-dimensional loading fleet sizing and mix vehicle routing problem with time windows), which deals simultaneously with vehicle routing and its three-dimensional loading considering heterogeneous fleet and time windows. The algorithm developed for the specific problem is called 3DC. This algorithm introduces a new local search operator called k-IntensiveSwap and a new container loading heuristic. The results are compared with the best-known results from literature for particular problems embeeded on the general problem presented. The quality of solution was good in comparison other methods for CLP (container loading problem), it has good results in terms of reduction fleet sizing in the case of 3L-VRP (three-dimensional loading vehicle routing problem) and as for 3L-VRPTW (threedimensional loading vehicle routing problem with time windows) the performance was very superior. Finally, it is presented a solution set as benchmark for future comparison with the general problem, with heterogeneous fleet.
McInvale, Howard D. "Land Leveling Using Optimal Earthmoving Vehicle Routing." Thesis, Virginia Tech, 2002. http://hdl.handle.net/10919/42356.
Повний текст джерелаMaster of Science
Lugo, Pedro Luis Miranda. "Programação da produção em sistemas flowshop híbrido com buffers limitados." Universidade Federal de São Carlos, 2013. https://repositorio.ufscar.br/handle/ufscar/3825.
Повний текст джерелаFinanciadora de Estudos e Projetos
This research studies the hybrid flowshop scheduling problem. In this production configuration, we have a set of jobs that has to be processed in a set of stages. At every stage we have a set of parallel machines available to process the jobs. All jobs have to be processed following the same production flow, from the first to the last stage. Every job has to be processed on one machine at each stage and each machine can process at most one job at a time. Some constraints commonly found in real production systems as unrelated parallel machines, limited buffers, sequence-dependent setup times (both anticipatory and non-anticipatory), machine eligibility, transportation times and release times for machines are also taken into account. The optimization criterion is the makespan, whose minimization is related to the efficient use of production resources. A mixed integer programming model is proposed and solved by the commercial solver CPLEX. The computational evaluation results indicate that the model is suitable just to solve instances up to nine jobs and five stages. Therefore, to solve larger instances (50-100 jobs), several heuristics and an iterated local search (ILS) algorithm are proposed and evaluated computationally. The results indicate that the ILS is able to obtain good quality solutions in short computation times.
Este trabalho estuda o problema de programação da produção em sistemas Flowshop híbrido. Nesta configuração de produção há um conjunto de tarefas que deve ser processado em um conjunto de estações, nas quais um determinado número de máquinas paralelas encontra-se disponível para o processamento das tarefas. Todas as tarefas devem ser processadas seguindo o mesmo fluxo de produção, desde a primeira até a última estação. Cada tarefa deve ser processada em uma máquina de cada estação e cada máquina pode processar, no máximo, uma tarefa por vez. Algumas restrições comumente encontradas em sistemas de produção reais, como máquinas paralelas não relacionadas, buffers limitados, tempos de preparação dependentes da sequência (antecipatórios e não antecipatórios), elegibilidade de máquinas, tempos de transporte e tempos de liberação das máquinas, também são consideradas. O critério de otimização é o makespan, cuja minimização está diretamente relacionada com a utilização eficiente dos recursos de produção. Um modelo de programação inteira mista é proposto e resolvido através do solver comercial CPLEX. Os resultados da avaliação computacional indicam que o modelo é viável somente para resolver instâncias de até nove tarefas e cinco estações. Desta forma, para resolver instâncias de maior tamanho (50-100 tarefas), várias heurísticas e uma meta-heurística de busca local iterada (ILS, Iterated Local Search) são propostas e avaliadas computacionalmente. Os resultados indicam que o ILS é capaz de obter soluções de boa qualidade em curtos tempos computacionais.
Gambardella, Luca Maria. "Coupling ant colony system with local search." Doctoral thesis, Universite Libre de Bruxelles, 2015. http://hdl.handle.net/2013/ULB-DIPOT:oai:dipot.ulb.ac.be:2013/209045.
Повний текст джерелаDoctorat en Sciences de l'ingénieur
info:eu-repo/semantics/nonPublished
Mousavi, Nogholi Amin Alah. "Optimisation of open pit mine block sequencing." Thesis, Queensland University of Technology, 2015. https://eprints.qut.edu.au/86697/1/Amin%20Alah_Mousavi%20Nogholi_Thesis.pdf.
Повний текст джерелаCornu, Marek. "Local Search, data structures and Monte Carlo Search for Multi-Objective Combinatorial Optimization Problems." Thesis, Paris Sciences et Lettres (ComUE), 2017. http://www.theses.fr/2017PSLED043/document.
Повний текст джерелаMany Combinatorial Optimization problems consider several, often conflicting, objectives. This thesis deals with Local Search, data structures and Monte Carlo Search methods for finding the set of efficient solutions of such problems, which is the set of all best possible trade-offs given all the objectives.We propose a new approximation method called 2-Phase Iterated Pareto Local Search based on Decomposition (2PIPLS/D) combining the notions of Pareto Local Search (PLS) and Decomposition. PLS is a local search descent adapted to Multi-Objective spaces, and Decomposition consists in the subdivision of the Multi-Objective problem into a number of Single-Objective problems. Two Single-Objective methods are considered: Iterated Local Search and Nested Monte Carlo Search. Two main components are embedded within the 2PIPLS/D framework. The first one generalizes and improves an existing method generating an initial set of solutions. The second one reduces efficiently the search space and accelerates PLS without notable impact on the quality of the generated approximation. We also introduce two new data structures for dynamically managing a set of incomparable solutions. The first one is specialized for the bi-objective case, while the second one is general.2PIPLS/D is applied to the bi-objective and tri-objective Traveling Salesman Problem and outperforms its competitors on tested instances. Then, 2PIPLS/D is instantiated on a new five-objective problem related to the recent territorial reform of French regions which resulted in the reassignment of departments to new larger regions
Guiraud, Maël. "Ordonnancement periodiques de messages pour minimiser la latence dans les réseaux dans un contexte 5G et au delà." Electronic Thesis or Diss., université Paris-Saclay, 2021. http://www.theses.fr/2021UPASG034.
Повний текст джерелаThis thesis is the result of a collaboration between DAVID Laboratory and Nokia Bell Labs France.The original idea is to find algorithmic solutions to deterministically manage periodic flows in networks in order to control and minimize the transmission time, called latency. One of the objectives of 5G (C-RAN, for Cloud Radio Access Network) is to centralize the calculation units of the radio antennas of telecommunications networks (called Radio Access Network) in the same computer center (the Cloud). The network between the computing center and the antennas must be able to satisfy the latency constraints imposed by the protocols.We define the problem of finding a periodic scheduling for messages so that they never compete for the same resource, and prove that the different variants of the problem studied are NP-complete. We first study the problem for a particular topology in which all the streams share the same link. We first propose polynomial algorithms of increased sophistication, and FPT algorithms that allow us to find a solution when the number of routes is reasonable, which is the case for C-RAN networks.Since the algorithms developed in this first part are not directly adaptable to more general topologies, we then propose a canonical form to the problem which allows us to define an efficient neighborhood notion for local search heuristics (hill climbing, tabu search, simulated annealing). We use this canonical form to define an efficient Branch and Bound algorithm when the number of routes is moderate.We also propose a performance evaluation of the proposed solutions compared to current flow management solutions, and show that our model is feasible in practice thanks to new equipment under development
Larabi, Mohand. "Le problème de job-shop avec transport : modélisation et optimisation." Phd thesis, Université Blaise Pascal - Clermont-Ferrand II, 2010. http://tel.archives-ouvertes.fr/tel-00625528.
Повний текст джерелаGuo, Yuhan. "Metaheuristics for solving large size long-term car pooling problem and an extension." Thesis, Artois, 2012. http://www.theses.fr/2012ARTO0206/document.
Повний текст джерелаNowadays, the increased human mobility combined with high use of private cars increases the load on environment and raises issues about quality of life. The extensive use of private cars lends to high levels of air pollution, parking problem, traffic congestion and low transfer velocity. In order to ease these shortcomings, the car pooling program, where sets of car owners having the same travel destination share their vehicles, has emerged all around the world. We present here our research on the long-term car pooling problem. In this thesis, the long-term car pooling problem is modeled and metaheuristics for solving the problem are investigated. The thesis is organized as follows. First, the definition and description of the problem as well as its mathematical model are introduced. Then, several metaheuristics to effectively and efficiently solve the problem are presented. These approaches include a Variable Neighborhood Search Algorithm, a Clustering Ant Colony Algorithm, a Guided Genetic Algorithm and a Multi-agent Self-adaptive Genetic Algorithm. Experiments have been conducted to demonstrate the effectiveness of these approaches on solving the long-term car pooling problem. Afterwards, we extend our research to a multi-destination daily car pooling problem, which is introduced in detail manner along with its resolution method. At last, an algorithm test and analysis platform for evaluating the algorithms and a car pooling platform are presented in the appendix
Bianchi, Leonora. "Ant colony optimization and local search for the probabilistic traveling salesman problem: a case study in stochastic combinatorial optimization." Doctoral thesis, Universite Libre de Bruxelles, 2006. http://hdl.handle.net/2013/ULB-DIPOT:oai:dipot.ulb.ac.be:2013/210877.
Повний текст джерелаOptimization problems under uncertainty are complex and difficult, and often classical algorithmic approaches based on mathematical and dynamic programming are able to solve only very small problem instances. For this reason, in recent years metaheuristic algorithms such as Ant Colony Optimization, Evolutionary Computation, Simulated Annealing, Tabu Search and others, are emerging as successful alternatives to classical approaches.
In this thesis, metaheuristics that have been applied so far to SCOPs are introduced and the related literature is thoroughly reviewed. In particular, two properties of metaheuristics emerge from the survey: they are a valid alternative to exact classical methods for addressing real-sized SCOPs, and they are flexible, since they can be quite easily adapted to solve different SCOPs formulations, both static and dynamic. On the base of the current literature, we identify the following as the key open issues in solving SCOPs via metaheuristics:
(1) the design and integration of ad hoc, fast and effective objective function approximations inside the optimization algorithm;
(2) the estimation of the objective function by sampling when no closed-form expression for the objective function is available, and the study of methods to reduce the time complexity and noise inherent to this type of estimation;
(3) the characterization of the efficiency of metaheuristic variants with respect to different levels of stochasticity in the problem instances.
We investigate the above issues by focusing in particular on a SCOP belonging to the class of vehicle routing problems: the Probabilistic Traveling Salesman Problem (PTSP). For the PTSP, we consider the Ant Colony Optimization metaheuristic and we design efficient local search algorithms that can enhance its performance. We obtain state-of-the-art algorithms, but we show that they are effective only for instances above a certain level of stochasticity, otherwise it is more convenient to solve the problem as if it were deterministic.
The algorithmic variants based on an estimation of the objective function by sampling obtain worse results, but qualitatively have the same behavior of the algorithms based on the exact objective function, with respect to the level of stochasticity. Moreover, we show that the performance of algorithmic variants based on ad hoc approximations is strongly correlated with the absolute error of the approximation, and that the effect on local search of ad hoc approximations can be very degrading.
Finally, we briefly address another SCOP belonging to the class of vehicle routing problems: the Vehicle Routing Problem with Stochastic Demands (VRPSD). For this problem, we have implemented and tested several metaheuristics, and we have studied the impact of integrating in them different ad hoc approximations.
Doctorat en sciences appliquées
info:eu-repo/semantics/nonPublished
Farias, Everton da Silveira. "A heuristic approach to supply chain network design in a multi-commodity four-echelon logistics system." reponame:Biblioteca Digital de Teses e Dissertações da UFRGS, 2016. http://hdl.handle.net/10183/140332.
Повний текст джерелаIn this thesis we propose a heuristic method for the Supply Chain Network Design (SCND) problem considering several aspects of practical relevance: suppliers and raw materials, location and operation facilities, distribution center (DC) assignments, and large numbers of customers and products. An efficient two-phase heuristic approach is proposed for obtaining feasible solutions to the problems, which is initially modeled as a large-scale Mixed Integer Linear Program (MILP). In the construction phase, a linear programming rounding strategy is applied to obtain initial values for the integer location variables in the model. Simultaneously, a Multi-start method was developed to generate diversified initial solutions from each new iteration in the rounding heuristic. In the second phase, two Local Search procedures were developed towards to improve the solution provided by the rounding method. We implemented two different Local Search approaches: removal-insertion and exchange. A Tabu Search technique was developed to guide the Local Search procedure to explore the different spaces of solutions. The formulations and algorithms were implemented in C++ code language using the optimization engine COIN-OR. The solution method was experimented in randomly generated instances, with different sizes in terms of the number of parameters, such as number of products, customer zones, DCs, and factories considering a four-echelon logistic system. The computational implementations show that the solution method proposed obtained satisfactory results when compared to the literature review. To validate this heuristic method was also used in a realistic case, based on data from a rubber company that is restructuring its supply chain due to the overture of a new factory, producing new products. The proposed heuristic approach proved appropriate to practical application in a realistic case of a multi commodity industry in a deterministic context.
Melo, Everton Luiz de. "Meta-heurísticas Iterated Local Search, GRASP e Artificial Bee Colony aplicadas ao Job Shop Flexível para minimização do atraso total." Universidade de São Paulo, 2014. http://www.teses.usp.br/teses/disponiveis/3/3136/tde-15122014-002717/.
Повний текст джерелаThe production environment addressed herein is the Flexible Job Shop (FJS), a generalization of the Job Shop (JS). In the JS environment, the jobs scheduling problem is classified by Garey; Johnson and Sethi (1976) as NP-Hard and the FJS is at least as difficult as the JS. FJS is composed of a set of jobs, each consisting of operations. Each operation must be processed individually, without interruption, in a single machine of a subset of enabled machines. The main performance criterion is minimizing the jobs tardiness. Mixed Integer Linear Programming (MILP) models are presented. These models minimize the total tardiness and the completion time of the last operation, makespan. New priority rules of jobs are proposed, as well as adaptations of rules from the literature. These rules are used by constructive heuristics and are combined with strategies aimed at exploiting specific characteristics of FSJ. In order to improve the solutions initially obtained, local searches and other improvement mechanisms are proposed and used in the development of metaheuristics of three different categories. These metaheuristics are: Iterated Local Search (ILS), classified as trajectory metaheuristic; Greedy Randomized Adaptive Search (GRASP), constructive metaheuristic, and Artificial Bee Colony (ABC), recently proposed population metaheuristic. These methods were selected owing to their good results for various optimization problems in the literature. Computational experiments using 600 FJS instances are carried out to allow comparisons between the resolution methods. The results show that exploiting the characteristics of the problem allows one of the proposed priority rules to exceed the best literature rule in about 81% of instances. Metaheuristics ILS, GRASP and ABC achieve more than 31% improvement over the initial solutions and obtain an average tardiness only 2.24% higher than the optimal solutions. Modifications in metaheuristics are proposed to obtain even more significant improvements without increased execution time. Additionally, a version called Disassembly and Assembly FSJ (DAFJS) is studied and the experiments performed with a set of 150 instances also indicate good performance of the methods developed.
Bouchakhchoukha, Adel. "Modèles de résolution approchée et efficace pour les problèmes des réseaux de transport et de télécommunication." Thesis, Paris 1, 2015. http://www.theses.fr/2015PA010046.
Повний текст джерелаThe need to save time as well as minimize effort is part of the human condition and it has driven our though s from antiquity until these last few decades, now characterized by the emergence of a mix in all fields between rapidity of calculation and precision in the result. The vehicle routing problem and its extensions are an important field for theorists of these utilities for real-world applications. Recent research in the field has led to significant advantages in problem formulation and designing algorithm analyses. This study considers logistics problems. A particular locus was given to a certain case of telecommunications networks 2ECONNDPR, as well as the method of intelligently creating designs to ensure vitality and durability in information circulation. Furthermore, the study considered vehicle routing problems, with time windows and orienteering problems from the VRP and OP families, respectively. This is the framework for this thesis. Solutions to these problems use programming techniques known for their calculation speed, i .e ., Beam-search and very large-scale neighborhood searching. First, a detailed study is presented of these above mentioned problems, along with the various types or resolution methods. Next, a very large-scale neighborhood search method is presented, suited to the design of a survivable network with relay, a proposition for a three-stage heuristic for the capacitated vehicle routing problem with time windows and, finally, a proposition for a hybrid heuristic for the team orienteering problem
Švadlenka, Jiří. "Informační systém pro školy s automatickou tvorbou rozvrhů." Master's thesis, Vysoké učení technické v Brně. Fakulta informačních technologií, 2008. http://www.nusl.cz/ntk/nusl-235924.
Повний текст джерелаPecháček, Václav. "Akcelerace heuristických metod diskrétní optimalizace na GPU." Master's thesis, Vysoké učení technické v Brně. Fakulta informačních technologií, 2012. http://www.nusl.cz/ntk/nusl-236550.
Повний текст джерелаSainathuni, Bhanuteja. "The Warehouse-Inventory-Transportation Problem for Multi-Echelon Supply Chains." Wright State University / OhioLINK, 2013. http://rave.ohiolink.edu/etdc/view?acc_num=wright1389657641.
Повний текст джерелаHail, Nourredine. "Méthodes algorithmiques pour les lignes de production avec des machines parallèles." Université Joseph Fourier (Grenoble), 1995. http://www.theses.fr/1995GRE10019.
Повний текст джерелаPandit, Vinayaka. "Local search heuristics for facility location problems." Thesis, 2004. http://localhost:8080/iit/handle/2074/2221.
Повний текст джерелаChen, Chih-wei, and 陳志偉. "Scheduling Unrelated Parallel Machines in Semiconductor Manufacturing by Problem Reduction and Local Search Heuristics." Thesis, 2009. http://ndltd.ncl.edu.tw/handle/44925428830632330575.
Повний текст джерела國立成功大學
工業與資訊管理學系碩博士班
97
We investigate a difficult scheduling problem in a semiconductor manufacturing process that seeks to minimize the number of tardy jobs and makespan with sequence-dependent setup time, release time, due dates and tool constraints. We propose a mixed integer programming (MIP) formulation which treats tardy jobs as soft constraints so that our objective seeks the minimum weighted sum of makespan and heavily penalized tardy jobs. Although our polynomial-sized MIP formulation can correctly model this scheduling problem, it is so difficult that even a feasible solution can not be solved efficiently for small-scale problems. We then propose a technique to estimate the upper bound for the number of jobs processed by a machine, and use it to largely reduce the size of the MIP formulation. In order to effectively handle real-world large-scale scheduling problems, we propose an efficient dispatching rule that assigns a job with the earliest due date to a machine with least recipe changeover (EDDLC) and try to reoptimize the solution by some local search heuristics which involve interchange, translocation and transposition between assigned jobs. Our computational experiments indicate that EDDLC and our proposed reoptimization techniques are very efficient and effective. In particular, our method usually give solutions very close to the exact optimum for smaller scheduling problems, and can also produce good solutions for scheduling up to 200 jobs on 40 machines within 10 minutes.
Liu, Dongyu, and 劉東育. "A Genetic Local Search Algorithm with Lagrangean Heuristics for the Simple Plant Location Problem." Thesis, 2004. http://ndltd.ncl.edu.tw/handle/04209446293718199478.
Повний текст джерела國立中興大學
資訊科學研究所
92
The simple plant location problem is one of the important combinatorial optimization problems and has attracted much attention for many years. It aims to locate a set of plants so that a set of clients can be supplied by them at the minimum cost. In this thesis, we proposed a hybrid metaheuristics for this problem. We first use a Lagrangean heuristic applies the subgradient optimization method to find the solution for the dual problem obtained by Lagrangean relaxation. After the reduction of the solution space, we then apply a genetic local search algorithm to search for the optimal solution. The experimental results of our method on the standard OR Library benchmarks reveal that our method has very good performance.
Chen, Chien-Wei, and 陳建緯. "Applications of Local Search Engines and Meta-heuristics for Solving Large-Scale Traveling Salesman Problem." Thesis, 2001. http://ndltd.ncl.edu.tw/handle/49907207813481133331.
Повний текст джерела國立交通大學
運輸工程與管理系
89
This thesis applies various meta-heuristics methods to solve the Large-scale Traveling Salesman Problem (LTSP). We have applied generic meta-heuristics including the Threshold Accepting (TA), Great Deluge Algorithm (GDA), and Flip-Flop (FF). A bank of 22 benchmark TSP instances form the TSPLIB is selected to evaluate the performance of different solution methods. The problem size of the test problems ranges from 1,002 to 4,461. We have developed various hybrid meta-heuristics and coded the programs in C. All the programs are tested on Dual Pentium III 550 PC (Windows 2000 Server). In the research, we modified parameter settings of TA, GDA, and created a new framework of TA -- Bounded TA. The average accuracy deviation from the best known solutions of the 22 tested problems are: 2.176% for TA, 2.508% for GDA(I), and 2.076% for GDA(II). The research also adopts the GIDS (Generic Intensification and Diversification Search) concept, to design two-stage meta-heuristics. We use flip-flop algorithm for diversification search in addition to the TA and GDA generic search engines. Considering different strategies, we developed six implementation procedures for TA-FF-TA, TA-FF-GDA(I), GDA(I)-FF-TA, GDA(II)-FF-TA, GDA(I)-FF-GDA(I), and GDA(II)-FF-GDA(I). Among different two-stage solution methods, TA-FF-TA seems to yield better average performance than others. Results show that the average accuracy deviations of the 22 tested problems are all lower than 2.2%, and the best is merely 1.4%. This also implies that these GIDS meta-heuristics methods are robust.
Silva, Anaís Veloso. "Algoritmos heurísticos para problemas de escalonamento integrado de pessoal e tarefas." Master's thesis, 2021. http://hdl.handle.net/1822/76357.
Повний текст джерелаNesta dissertação considera-se um problema de escalonamento de pessoal numa empresa de serviços de call center. Esta empresa opera 24 horas por dia, 7 dias por semana, e o processo de escalonamento de pessoal é atualmente realizado manualmente. Neste sentido, o objetivo principal deste trabalho é o desenvolvimento e implementação de métodos heurísticos, de forma a obter soluções para este problema num tempo menor do que aquele que é despendido até ao momento com o escalonamento manual. A abordagem proposta consiste na construção de uma solução inicial através de uma heurística construtiva e posterior melhoria desta solução através de um método de pesquisa local. O que se pretende com esta abordagem é alocar funcionários a turnos de trabalho, procurando maximizar o número de horários invariáveis para cada funcionário em cada período. Depois de se ter desenvolvido um método de pesquisa local que melhora as soluções iniciais obtidas, foi ainda implementado um outro método de pesquisa local que minimiza as diferenças relativamente ao número de dias em que cada funcionário não é alocado a nenhum turno. A heurística construtiva e os dois métodos de pesquisa local foram implementados no Visual Studio v.16.8.2., utilizando a linguagem C#, e testados num conjunto de instâncias, incluindo instâncias com dados reais e instâncias geradas aleatoriamente. Esta abordagem foi analisada através da comparação entre as soluções iniciais e as soluções geradas pelos métodos de pesquisa local implementados.
The considered problem is a personnel scheduling problem in a call center company. This company operates 24 hours per day, 7days a week, and in which the personnel scheduling process is done manually. In this sense, the main purpose of this dissertation is the development and implementation of heuristic methods to obtain optimized solutions to this problem in a shorter amount of time than the one spent until this moment with manually built scales. The proposed approach consists of building an initial solution through a constructive heuristic and posterior improvement of this solution through a local search method. This approach intends to allocate employees to a work shift, maximizing the number of equal shifts to which an employee is allocated in each period. After developing a local search method that improved the initial solutions, we implemented another local search method that minimized the deviation relative to the number of days in which each employee is not allocated to any shift. The constructive heuristic and the two local search methods are implemented in Visual Studio v.16.8.2., using the language C#, and teste in several instances, including real instances and randomly generated instances. The approach was analyzed through the comparison between the initial solutions and the ones obtained by the local search methods implemented.
Cheng, Chao-Jui, and 鄭朝瑞. "An Iterated Local Search Heuristic for Rotating Workforce Scheduling." Thesis, 2009. http://ndltd.ncl.edu.tw/handle/83920539579643610471.
Повний текст джерела華梵大學
工業工程與經營資訊學系碩士班
97
Rotating workforce scheduling (RWS) has been generally applied in different firms and organizations. RWS is highly practical relevance to find solutions of workforce schedules. In this paper, an iterated local search (ILS) heuristic was proposed to get optimal solutions under different various constraints. This approach is proved to meet nurse workforce scheduling, computer room workforce scheduling, market workforce scheduling, and manufacturing factory workforce scheduling to generate workforce scheduling quickly and efficiently under the fulfill constraints. The computational results verified that the proposed ILS heuristc is an effective and efficient approach for solving the RWS problem. Keywords:Rotating workforce scheduling、Iterated Local Search Heuristic、workforce matrix
Dimova, Boryana Slavcheva. "Characterizing neighborhoods favorable to local search techniques." Thesis, 2004. http://repositories.lib.utexas.edu/bitstream/handle/2152/1308/dimovad16980.pdf.
Повний текст джерелаTorres, Soto Joaquin. "Dynamic and Robust Capacitated Facility Location in Time Varying Demand Environments." 2009. http://hdl.handle.net/1969.1/ETD-TAMU-2009-05-620.
Повний текст джерелаLin, Chien-Chuan, and 林建權. "An Iterated Local Search Heuristic for the Periodic Location Routing Problem." Thesis, 2017. http://ndltd.ncl.edu.tw/handle/e89wzx.
Повний текст джерела國立交通大學
運輸與物流管理學系
105
The Periodic Location Routing Problem (PLRP) is an extension of the conventional Vehicle Routing Problem (VRP). The PLRP combines the Location Routing Problem (LRP) and the Periodic Vehicle Routing Problem (PVRP) into a more realistic yet more complicated problem to solve than the conventional VRP. In this thesis, we develop a metaheuristic approach based on the Iterated Local Search (ILS) metaheuristic framework to solve the PLRP. Using bin packing and k-median concepts, we first generate five different depot combinations to construct multiple initial solutions. These solutions are then improved by a Randomized Variable Neighborhood Descent (RVND) module. This module includes eight conventional exchange operators and two new operators, i.e., D-shift and route_reduction that we have designed specifically for the PLRP. Finally, two perturbation mechanisms, i.e., route_pertubation and day_pertubation are applied in each iterated procedure to further diversify the search of solution. We have coded our proposed algorithms in C# and tested on a set of 30 benchmark instances described by Prodhon [18]. The result show that the average deviation from BKS is 6.15%. The performance gap, when compared to the best solution method in literature, i.e., Large Neighborhood Search (Hemmelmayr [5]), is only 2.03%. This implies that our algorithm is a quite competitive heuristic method for solving the PLRP.
Kinney, Gary W. Barnes J. Wesley. "A group theoretic approach to metaheuristic local search for partitioning problems." 2005. http://repositories.lib.utexas.edu/bitstream/handle/2152/1594/kinneyg73946.pdf.
Повний текст джерелаKinney, Gary W. "A group theoretic approach to metaheuristic local search for partitioning problems." Thesis, 2005. http://hdl.handle.net/2152/1594.
Повний текст джерелаLiu, Yi-Ching, and 劉依晴. "Using Iterated Local Search Heuristic to Solve the Green Vehicle Routing Problem." Thesis, 2016. http://ndltd.ncl.edu.tw/handle/14625866066059481193.
Повний текст джерела國立交通大學
運輸與物流管理學系
104
Green vehicle routing problem (G-VRP) is an extension of the classical Vehicle Routing Problem. G-VRP is developed to aid organizations with alternative fuel-powered vehicle fleets in overcoming difficulties that exist as a result of limited vehicle driving range in conjunction with limited traveling time and limited Alternative Fuel Station (AFS). We apply the Iterated Local Search (ILS) metaheuristic approach for solving G-VRP. First, we use parallel farthest cheapest insertion to build initial solution, then use a Randomized Variable Neighborhood Descent (RVND) module for solution improvement. The RVND module includes seven conventional exchange operators and two innovative operators which we have designed for improving the use of AFS in the G-VRP, i.e., 1-0_AFS and AFS_relocation. Finally, the search repeats itself with a perturbation mechanism for diversification. We have tested our algorithms, and compared with the best known solutions (BKS) of G-VRP. The results show that, out of 52 benchmark instances tested, our proposed approach has found 51 best solutions including 7 new BKS. The average deviation is -0.02%.
Teng, Chuan-Pin, and 鄧全斌. "An Iterated Local Search heuristic for the Close-Open Mixed Vehicle Routing Problem." Thesis, 2015. http://ndltd.ncl.edu.tw/handle/52078168528778481418.
Повний текст джерела國立交通大學
運輸與物流管理學系
103
The Close-Open Mixed Vehicle Routing Problem (COMVRP) is a variant of the conventional Vehicle Routing Problem (VRP). Consider the case when the private car of company is insufficient. In order to meet the demand of customer, the company can use external collaborative carrier to serve its customer. COMVRP is more suitable for the work of logistics distribution, but there was just a little study on COMVRP. Therefore, we are going to develop an Iterated Local Search (ILS) Metaheuristic to solve COMVRP. First, we use Node Insertion Route Addition (NIRA) to build multi-start solution. And then use Randomized Variable Neighborhood Descent (RVND), which includes seven traditional operators and the Open to Close (O2C) which we were aimed at the characteristic of COMVRP to improve the solution. Finally, it repeats search with perturbation mechanism to improve the breadth of solution space. Our proposed algorithm was tested on two sets of 42 benchmark instances. Results showed that our proposed algorithm on benchmark instances can generate 24 best known solutions (BKS) and 16 new BKS. The average deviation is -0.86%.
Ravidas, Amrish Deep. "An Exact Algorithm and a Local Search Heuristic for a Two Runway Scheduling Problem." 2010. http://hdl.handle.net/1969.1/ETD-TAMU-2010-12-8787.
Повний текст джерелаYi, Nai-En, and 易鼐恩. "An Iterated Local Search Heuristic for the Vehicle Routing Problem with Intermediate Replenishment Facilities." Thesis, 2017. http://ndltd.ncl.edu.tw/handle/cd9922.
Повний текст джерела國立交通大學
運輸與物流管理學系
105
Vehicle Routing Problem with intermediate replenishment facilities (VRPIRF) is an extension of the classical Vehicle Routing Problem. Unlike the VRP which considers a single depot, the VRPIRF considers multiple replenishment depots (RD) with unlimited capacity, capacity of vehicles and limitation of total duration. The best decisions of vehicle routing and the use of those intermediate RDs in the VRPIRF would help the business to further reduce the logistics cost and gain more competitive advantage. In this thesis, we propose a heuristic approach called RD_ILS for solving the VRPIRF. This RD_ILS approach is based on the Iterated Local Search (ILS) metaheuristic framework. The proposed RD_ILS approach consists of three modules. First, we build and split giant tours to construct multiple initial solutions. Then, a Randomized Variable Neighborhood Descent (RVND) module is applied for solution improvement. This RVND module includes eight conventional exchange operators each is conducted with a novel operator RD_ReAssignment to enhance the intensification of search. Finally, we implement three types of perturbations for customers, segments and routes to enrich the diversification of search. We have tested the RD_ILS algorithms with three VRPIRF benchmark problem sets. The results show that, out of 76 instances tested, our proposed approach has found 18 best known solutions (BKS) and 33 new best solutions; the average deviation from the BKS is -0.52%.
Li, Meng-Han, and 李孟韓. "A Linear-time Heuristic for The Gene Duplication Problem Based on NNI Local Searches." Thesis, 2009. http://ndltd.ncl.edu.tw/handle/81884604518459622987.
Повний текст джерела國立臺灣大學
資訊工程學研究所
97
Contradictory phylogenies may result from several effects, such as gene loss, recombination, and duplication. The gene duplication problem is to deduce a most likely phylogenetic supertree from a large set of gene trees with gene duplication information. This problem has been proved to be NP-complete, and more efficient heuristics are required to deal with large-scale phylogenetic analysis. A naive heuristic which performs a step-by-step search on the tree and recalculate the reconciliation cost on each node is extremely time consuming and requiring enormous computational power. The k-NNI search problem, based on at most k times nearest neighbor interchange operations, has been largely put into use for solving the gene duplication problem. In this work, we provide a linear-time solution for the 1-NNI local search problem and an O(p(r + log n))-time heuristic based on 1-NNI local search problem, where p denotes the number of iterations. The result of this work provides a feasible approach for the vast phylogenetic data analysis.
Ou, Jhe-Yu, and 歐哲瑜. "A Particle Swarm Optimization Solution Approach and an Iterated Local Search Heuristic for the Multi-Compartment Vehicle Routing Problem." Thesis, 2017. http://ndltd.ncl.edu.tw/handle/h59p72.
Повний текст джерела國立交通大學
運輸與物流管理學系
105
Multi-compartment vehicle routing problem (MCVRP) is an extension of the classical Vehicle Routing Problem (VRP) with multiple products that must be stored in the given compartments in the vehicle. The main difference between MCVRP and VRP is the compartment capacity limit for various products. Depending on if the different products of a customer can be shipped by different vehicles, the MCVRP can be classified into the split and non-split type of problems respectively. In this thesis, we apply the particle swarm optimization (PSO) method and a multi-start iterated local search (MS_ILS) approach for solving the MCVRP respectively. In the PSO part, we propose an n-dimension decoding method for solving both the non-split and split type of the MCVRP. In our MS_ILS, we first use the n-dimension decoding method to construct multiple initial solutions. Then, we apply a randomized variable neighborhood decent (RVND) module with the local search operators of 2-opt, Or-opt, λ-interchanges and 2-opt* to improve the solution. A p-point perturbation is also applied in the MS_ILS to increase the diversification of search. Our proposed algorithms were tested on four problem instance sets proposed by Fallahi et al. [9] and Reed et al. [24]. The results show that the MS_ ILS performs better than PSO. On the other hand, our proposed n-dimension decoding method of PSO can save about half computer time than the original 2n-dimension decoding method in solving the MCVRP for the split type of problems. Out of 136 instances tested, our MS_ILS has found 23 best known solutions (BKS) and 38 new best solutions. The average deviation from BKS is 0.18%. Key Words: Multi-Compartment Vehicle Routing Problem (MCVRP), Particle Swarm Optimization (PSO), Iterated Local Search (ILS), Multi-start