Dissertations / Theses on the topic 'Local search heuristics'
To see the other types of publications on this topic, follow the link: Local search heuristics.
Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles
Consult the top 43 dissertations / theses for your research on the topic 'Local search heuristics.'
Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.
You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.
Browse dissertations / theses on a wide variety of disciplines and organise your bibliography correctly.
1
Shatabda, Swakkhar. "Local Search Heuristics for Protein Structure Prediction." Thesis, Griffith University, 2014. http://hdl.handle.net/10072/365446.
Full textAbstract:
This thesis presents our research on protein structure prediction on discrete lattices. Given a protein’s amino acid sequence, the protein structure prediction problem is to find its three dimensional native structure that has the minimum free energy. Knowledge about the native protein structures and their respective folding process is a key to understand protein functionalities and consequently the basics of life. Protein structure prediction problem is one of the most challenging problems in molecular biology.
In-vitro laboratory methods applied to this problem are very time-consuming, cost- expensive and failure-prone. Also, the search based optimization methods used are com- putationally very expensive. To tackle these, researchers have used various simplified models, such as low resolution energy functions and lattice-based structures, and applied incomplete local search methods on them. The simplified models help obtain back-bone structures first and then hierarchically work out the details. Local search methods can normally quickly find solutions although they suffer from re-visitation and stagnancy, and require good heuristics. In the literature, researchers have mostly used primitive ap- proaches based on random decisions at various choice points. Consequently, these methods are applicable to small-sized proteins only.
In this thesis, we present a number of techniques to improve the performance of lo- cal search methods applied to protein structure prediction problem using discrete lattices. Firstly, we propose a memory based local search framework that maintains a set of already explored solutions for avoiding re-visitation and stores previously unexplored but promi- nent solutions for restarting to handle stagnation. A novel encoding scheme for protein structures is proposed to handle symmetry present in the search space. We also propose an approximate matching strategy that results in reducing redundancy in the search space.Thesis (PhD Doctorate)
Doctor of Philosophy (PhD)
Institute for Integrated and Intelligent Systems
Science, Environment, Engineering and Technology
Full Text
2
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.
Full text
3
Magaji, Amina Sambo-Muhammad. "Combining search strategies for distributed constraint satisfaction." Thesis, Robert Gordon University, 2015. http://hdl.handle.net/10059/1374.
Full textAbstract:
Many real-life problems such as distributed meeting scheduling, mobile frequency allocation and resource allocation can be solved using multi-agent paradigms. Distributed constraint satisfaction problems (DisCSPs) is a framework for describing such problems in terms of related subproblems, called a complex local problem (CLP), which are dispersed over a number of locations, each with its own constraints on the values their variables can take. An agent knows the variables in its CLP plus the variables (and their current value) which are directly related to one of its own variables and the constraints relating them. It knows little about the rest of the problem. Thus, each CLP is solved by an agent which cooperates with other agents to solve the overall problem. Algorithms for solving DisCSPs can be classified as either systematic or local search with the former being complete and the latter incomplete. The algorithms generally assume that each agent has only one variable as they can solve DisCSP with CLPs using “virtual” agents. However, in large DisCSPs where it is appropriate to trade completeness off against timeliness, systematic search algorithms can be expensive when compared to local search algorithms which generally converge quicker to a solution (if a solution is found) when compared to systematic algorithms. A major drawback of local search algorithms is getting stuck at local optima. Significant researches have focused on heuristics which can be used in an attempt to either escape or avoid local optima. This thesis makes significant contributions to local search algorithms for DisCSPs. Firstly, we present a novel combination of heuristics in DynAPP (Dynamic Agent Prioritisation with Penalties), which is a distributed synchronous local search algorithm for solving DisCSPs having one variable per agent. DynAPP combines penalties on values and dynamic agent prioritisation heuristics to escape local optima. Secondly, we develop a divide and conquer approach that handles DisCSP with CLPs by exploiting the structure of the problem. The divide and conquer approach prioritises the finding of variable instantiations which satisfy the constraints between agents which are often more expensive to satisfy when compared to constraints within an agent. The approach also exploits concurrency and combines the following search strategies: (i) both systematic and local searches; (ii) both centralised and distributed searches; and (iii) a modified compilation strategy. We also present an algorithm that implements the divide and conquer approach in Multi-DCA (Divide and Conquer Algorithm for Agents with CLPs). DynAPP and Multi-DCA were evaluated on several benchmark problems and compared to the leading algorithms for DisCSPs and DisCSPs with CLPs respectively. The results show that at the region of difficult problems, combining search heuristics and exploiting problem structure in distributed constraint satisfaction achieve significant benefits (i.e. generally used less computational time and communication costs) over existing competing methods.
4
Henderson, Darrall. "Assessing the Finite-Time Performance of Local Search Algorithms." Diss., Virginia Tech, 2001. http://hdl.handle.net/10919/26926.
Full textAbstract:
Identifying a globally optimal solution for an intractable discrete optimization problem is often cost prohibitive. Therefore, solutions that are within a predetermined threshold are often acceptable in practice. This dissertation introduces the concept of B-acceptable solutions where B is a predetermined threshold for the objective function value.
It is difficult to assess a priori the effectiveness of local search algorithms, which makes the process of choosing parameters to improve their performance difficult. This dissertation introduces the B-acceptable solution probability in terms of B-acceptable solutions as a finite-time performance measure for local search algorithms. The B-acceptable solution probability reflects how effectively an algorithm has performed to date and how effectively an algorithm can be expected to perform in the future. The B-acceptable solution probability is also used to obtain necessary asymptotic convergence (with probability one) conditions. Upper and lower bounds for the B-acceptable solution probability are presented. These expressions assume particularly simple forms when applied to specific local search strategies such as Monte Carlo search and threshold accepting. Moreover, these expressions provide guidelines on how to manage the execution of local search algorithm runs. Computational experiments are reported to estimate the probability of reaching a B-acceptable solution for a fixed number of iterations. Logistic regression is applied as a tool to estimate the probability of reaching a B-acceptable solution for values of B close to the objective function value of a globally optimal solution as well as to estimate this objective function value. Computational experiments are reported with logistic regression for pure local search, simulated annealing and threshold accepting applied to instances of the TSP with known optimal solutions.Ph. D.
5
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.
Full textAbstract:
Modularity Density Maximization is a graph clustering problem which avoids the resolution limit degeneracy of the Modularity Maximization problem. This thesis aims at solving larger instances than current Modularity Density heuristics do, and show how close the obtained solutions are to the expected clustering. Three main contributions arise from this objective. The first one is about the theoretical contributions about properties of Modularity Density based prioritizers. The second one is the development of eight Modularity Density Maximization heuristics. Our heuristics are compared with optimal results from the literature, and with GAOD, iMeme-Net, HAIN, BMD- heuristics. Our results are also compared with CNM and Louvain which are heuristics for Modularity Maximization that solve instances with thousands of nodes. The tests were carried out by using graphs from the “Stanford Large Network Dataset Collection”. The experiments have shown that our eight heuristics found solutions for graphs with hundreds of thousands of nodes. Our results have also shown that five of our heuristics surpassed the current state-of-the-art Modularity Density Maximization heuristic solvers for large graphs. A third contribution is the proposal of six column generation methods. These methods use exact and heuristic auxiliary solvers and an initial variable generator. Comparisons among our proposed column generations and state-of-the-art algorithms were also carried out. The results showed that: (i) two of our methods surpassed the state-of-the-art algorithms in terms of time, and (ii) our methods proved the optimal value for larger instances than current approaches can tackle. Our results suggest clear improvements to the state-of-the-art results for the Modularity Density Maximization problem.
6
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.
Full textAbstract:
Agent-based computing has attracted much attention as a promising technique for application domains that are distributed, complex and heterogeneous. Current research on multi-agent systems (MAS) has become mature enough to be applied as a technology for solving problems in an increasingly wide range of complex applications. The main formal architectures used to describe the relationships between agents in MAS are centralised and distributed architectures. In computational complexity theory, researchers have classified the problems into the followings categories: (i) P problems, (ii) NP problems, (iii) NP-complete problems, and (iv) NP-hard problems. A method for computing the solution to NP-hard problems, using the algorithms and computational power available nowadays in reasonable time frame remains undiscovered. And unfortunately, many practical problems belong to this very class. On the other hand, it is essential that these problems are solved, and the only possibility of doing this is to use approximation techniques. Heuristic solution techniques are an alternative. A heuristic is a strategy that is powerful in general, but not absolutely guaranteed to provide the best (i.e. optimal) solutions or even find a solution. This demands adopting some optimisation techniques such as Evolutionary Algorithms (EA). This research has been undertaken to investigate the feasibility of running computationally intensive algorithms on multi-agent architectures while preserving the ability of small agents to run on small devices, including mobile devices. To achieve this, the present work proposes a new Hybrid Multi-Agent Architecture (HMAA) that generates new heuristics for solving NP-hard problems. This architecture is hybrid because it is "semi-distributed/semi-centralised" architecture where variables and constraints are distributed among small agents exactly as in distributed architectures, but when the small agents become stuck, a centralised control becomes active where the variables are transferred to a super agent, that has a central view of the whole system, and possesses much more computational power and intensive algorithms to generate new heuristics for the small agents, which find optimal solution for the specified problem. This research comes up with the followings: (1) Hybrid Multi-Agent Architecture (HMAA) that generates new heuristic for solving many NP-hard problems. (2) Two frameworks of HMAA have been implemented; search and optimisation frameworks. (3) New SMA meeting scheduling heuristic. (4) New SMA repair strategy for the scheduling process. (5) Small Agent (SMA) that is responsible for meeting scheduling has been developed. (6) “Local Search Programming” (LSP), a new concept for evolutionary approaches, has been introduced. (7) Two types of super-agent (LGP_SUA and LSP_SUA) have been implemented in the HMAA, and two SUAs (local and global optima) have been implemented for each type. (8) A prototype for HMAA has been implemented: this prototype employs the proposed meeting scheduling heuristic with the repair strategy on SMAs, and the four extensive algorithms on SUAs. The results reveal that this architecture is applicable to many different application domains because of its simplicity and efficiency. Its performance was better than many existing meeting scheduling architectures. HMAA can be modified and altered to other types of evolutionary approaches.
7
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/.
Full textAbstract:
A crescente necessidade de buscar operações mais eficientes, com menor custo e mais sustentáveis tem feito com que empresas passassem a procurar oportunidades pelas quais estes objetivos pudessem ser atingidos. Na área de transportes encontrou-se na colaboração uma oportunidade para tal. Este trabalho trata o problema de cobertura rotas com cardinalidade restrita (PCRCR), onde empresas que realizam viagens de carga cheia se unem com o objetivo de reduzir o deslocamento vazio de veículos através da formação de ciclos. É chamado de problema de cardinalidade restrita uma vez que limitamos o número de máximo de viagens no ciclo, o que torna este problema NP-Hard. Existem na literatura duas heurísticas (construtivas) e um modelo por programação linear inteira para a solução deste problema. Este trabalho apresenta uma heurística baseada em um método de busca local que reduziu em média 3,19% os melhores resultados apresentados na literatura. Também são apresentados os tempos de execução de cada um dos algoritmos e a importância de escolher de uma boa solução inicial quando se deseja implantar uma Heurística com Busca Local.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.
8
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.
Full textAbstract:
In this thesis the capacitated vehicle routing problem with time windows (VRPTW) is studied, where the objective is to serve a set of geographically dispersed customers with known demands and predefined time windows at the minimum cost. It is hard to find an optimal solution for the VRPTW even if the problem size is small. Therefore, many heuristic methods are developed to obtain near optimal solutions. In this study a local search algorithm is proposed for solving the VRPTW, which consist of route construction and route improvement phases. Computational experiments are conducted with Solomon (1987)&rsquos 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.
9
Sullivan, Kelly Ann. "A Convergence Analysis of Generalized Hill Climbing Algorithms." Diss., Virginia Tech, 1999. http://hdl.handle.net/10919/27027.
Full textAbstract:
Generalized hill climbing (GHC) algorithms provide a unifying framework for describing several discrete optimization problem local search heuristics, including simulated annealing and tabu search. A necessary and a sufficient convergence condition for GHC algorithms are presented.
The convergence conditions presented in this dissertation are based upon a new iteration classification scheme for GHC algorithms. The convergence theory for particular formulations of GHC algorithms is presented and the implications discussed. Examples are provided to illustrate the relationship between the new convergence conditions and previously existing convergence conditions in the literature. The contributions of the necessary and the sufficient convergence conditions for GHC algorithms are discussed and future research endeavors are suggested.Ph. D.
10
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/.
Full textAbstract:
Este trabalho aborda um problema ainda não explorado na literatura denominado 3L-FSMVRPTW (three-dimensional loading fleet sizing and mix vehicle routing problem with time windows), que compreende resolver simultaneamente o roteamento e carregamento tridimensional de veículos considerando frota heterogênea e janela de tempo. Foi desenvolvido um algoritmo específico para resolver o problema, denominado 3DC. Neste algoritmo foram introduzidas algumas inovações, entre elas, um novo operador de busca local (k-IntensiveSwap) e uma nova heurística de carregamento de contêiner. O algoritmo foi comparado aos melhores resultados disponíveis na literatura para problemas particulares ao apresentado. Houve bom desempenho no caso do CLP (container loading problem), bom resultado na redução do tamanho de frota no caso do 3L-VRP (threedimensional loading vehicle routing problem) e desempenho superior ao problema mais complexo estudado, o 3L-VRPTW (three-dimensional loading vehicle routing problem with time windows). Finalmente, apresentou-se um conjunto de avaliação, instâncias e soluções, para o problema completo com frota heterogênea e janela de tempo.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.
11
McInvale, Howard D. "Land Leveling Using Optimal Earthmoving Vehicle Routing." Thesis, Virginia Tech, 2002. http://hdl.handle.net/10919/42356.
Full textAbstract:
This thesis presents new solution approaches for land leveling, using optimal earthmoving vehicle routing. It addresses the Shortest Route Cut and Fill Problem (SRCFP) developed by Henderson, Vaughan, Wakefield and Jacobson [2000]. The SRCFP is a discrete optimization search problem, proven to be NP-hard. The SRCFP describes the process of reshaping terrain through a series of cuts and fills. This process is commonly done when leveling land for building homes, parking lots, etc. The model used to represent this natural system is a variation of the Traveling Salesman Problem. The model is designed to limit the time needed to operate expensive, earthmoving vehicles. The model finds a vehicle route that minimizes the total time required to travel between cut and fill locations while leveling the site. An optimal route is a route requiring the least amount of travel time for an individual earthmoving vehicle.
This research addresses the SRCFP by evaluating minimum function values across an unknown response surface. The result is a cost estimating strategy that provides construction planners a strategy for contouring terrain as cheaply as possible. Other applications of this research include rapid runway repair, and robotic vehicle routing.Master of Science
12
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.
Full textAbstract:
Made available in DSpace on 2016-06-02T19:53:31Z (GMT). No. of bitstreams: 1
LUGO_Pedro_2013.pdf: 2147400 bytes, checksum: a0c7948826b7f243c447b99fd96c3388 (MD5)
Previous issue date: 2013-09-12Financiadora 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.
13
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.
Full textAbstract:
In the last decades there has been a lot of interest in computational models and metaheuristics algorithms capable to solve combinatorial optimization problems. The recent trend is to define these algorithms taking inspiration by the observation of natural systems. In this thesis the Ant Colony System (ACS) is presented which has been inspired by the observation of real ant colonies. ACS is initially proposed to solve the symmetric and asymmetric travelling salesman problems where it is shown to be competitive with other metaheuristics. Although this is an interesting and promising result, it was immediately clear that ACS, as well as other metaheuristics, in many cases cannot compete with specialized local search methods. An interesting trend is therefore to couple metaheuristics with a local optimizer, giving birth to so-called hybrid methods. Along this line, the thesis investigates MACS-VRPTW (Multiple ACS for the Vehicle Routing Problem with Time Windows) and HAS-SOP: Hybrid Ant System for the Sequential Ordering Problem (SOP). In the second part the thesis introduces some modifications of the original ACS algorithm. These modifications are able to speed up the method and to make it more competitive in case of large problem instances. The resulting framework, called Enhanced Ant Colony System is tested for the SOP. Finally the thesis presents the application of ACS to solve real-life vehicle routing problems where additional constraints and stochastic information are included.Doctorat en Sciences de l'ingénieur
info:eu-repo/semantics/nonPublished
14
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.
Full textAbstract:
This study presents a comprehensive mathematical model for open pit mine block sequencing problem which considers technical aspects of real-life mine operations. As the open pit block sequencing problem is an NP-hard, state-of-the-art heuristics algorithms, including constructive heuristic, local search, simulated annealing, and tabu search are developed and coded using MATLAB programming language. Computational experiments show that the proposed algorithms are satisfactory to solve industrial-scale instances. Numerical investigation and sensitivity analysis based on real-world data are also conducted to provide insightful and quantitative recommendations for mine schedulers and planners.
15
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.
Full textAbstract:
De nombreux problèmes d'optimisation combinatoire considèrent plusieurs objectifs, souvent conflictuels. Cette thèse s'intéresse à l'utilisation de méthodes de recherche locale, de structures de données et de recherche Monte-Carlo pour la recherche de l'ensemble des solutions efficaces de tels problèmes, représentant l'ensemble des meilleurs compromis pouvant être réalisés en considération de tous les objectifs.Nous proposons une nouvelle méthode d'approximation appelée 2-Phase Iterated Pareto Local Search based on Decomposition (2PIPLS/D) combinant les concepts de recherche locale Pareto (PLS) et de décomposition. La PLS est une descente de recherche locale adaptée au multi-objectif, et la décomposition consiste en la subdivision du problème multi-objectif en plusieurs problèmes mono-objectif. Deux méthodes d'optimisation mono-objectif sont considérées: la recherche locale itérée et la recherche Monte-Carlo imbriquée. Deux modules principaux sont intégrés à 2PIPLS/D. Le premier généralise et améliore une méthode existante et génère un ensemble initial de solutions. Le second réduit efficacement l'espace de recherche et permet d'accélérer la PLS sans négliger la qualité de l'approximation générée. Nous introduisons aussi deux nouvelles structures de données gérant dynamiquement un ensemble de solutions incomparables, la première est spécialisée pour le cas bi-objectif et la seconde pour le cas général.2PIPLS/D est appliquée au Problème du Voyageur de Commerce bi-objectif et tri-objectif et surpasse ses concurrents sur les instances testées. Ensuite, 2PIPLS/D est appliquée à un nouveau problème avec cinq objectifs en lien avec la récente réforme territoriale d'agrandissement des régions françaisesMany 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
16
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.
Full textAbstract:
Cette thèse est le fruit d’une collaboration entre les laboratoires DAVID et Nokia Bell Labs France.L’idée originale est de trouver des solutions algorithmiques pour gérer des flux periodiques de manière déterministe dans les réseaux afin de contrôler et de minimiser le temps de transmission, appelé latence. L’un des objectifs de la 5G (le C-RAN, pour Cloud Radio Access Network) est de centraliser les unités de calculs des antennes radio des réseaux de télécommunications (appelé Radio Access Network) dans un même centre de calcul (le Cloud). Le réseau entre le centre de calcul et les antennes doit être capable de satisfaire les contraintes de latence imposées par les protocoles.Nous définissions le problème de trouver un ordonnancement periodique pour les messages de façon à ce qu'ils ne se disputent jamais la même ressource, et prouvons que les différentes variantes du problème étudiés sont NP-complets. Nous étudions dans un premier temps le problème pour une topologie particulière dans laquelle tous les flux partagent un même lien. Nous proposons dans un premier temps des algorithmes polynomiaux, de plus en plus évolués, ainsi que des algorithmes FPT permettant de trouver une solution quand le nombre de route est raisonnable, ce qui est le cas des réseaux C-RAN.Les algorithmes développés dans cette première partie n’étant pas applicables directement aux topologies plus générales, nous proposons ensuite une forme compacte au problème qui nous permet de définir une notion de voisinage efficace pour des heuristiques de recherches locales (descente, recherche tabou, recuit simulé). Nous utilisons cette forme compacte pour définir un algorithme Branch and Bound efficace quand le nombre de routes est modéré.Nous proposons aussi une évaluation de performance des solutions proposés par rapport aux solutions courantes de gestion des flux et montrons que notre modèle est réalisable en pratique grâce aux nouveaux équipements en cours de développementThis 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
17
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.
Full textAbstract:
Dans cette thèse nous nous sommes intéressés à l'extension du problème job-shop en ajoutant la contrainte du transport des jobs entre les différentes machines. Dans cette étude nous avons retenu l'existence de deux types de robots, les robots de capacité de chargement unitaire (capacité=1 veut dire qu'un robot ne peut transporter qu'un seul job à la fois) et les robots de capacité de chargement non unitaire (capacité>1 veut dire qu'un robot peut transporter plusieurs job à la fois). Nous avons traité cette extension en deux étapes. Ainsi, la première étape est consacrée au problème du job-shop avec plusieurs robots de capacité de chargement unitaire et en seconde étape en ajoutant la capacité de chargement non unitaire aux robots. Pour les deux problèmes étudiés nous avons proposé :* Une modélisation linéaire ;* Une modélisation sous forme de graphe disjonctif ;* Plusieurs heuristiques de construction de solutions ;* Plusieurs recherches locales qui améliorent les solutions obtenues ;* Utilisation des algorithmes génétiques / mémétiques comme schéma global d'optimisation ;* De nouveaux benchmarks, des résultats de test de nos approches sur nos benchmarks et ceux de la littérature et ces résultats sont commentés et comparés à ceux de la littérature. Les résultats obtenus montrent la pertinence de notre modélisation ainsi que sa qualité.
18
Guo, Yuhan. "Metaheuristics for solving large size long-term car pooling problem and an extension." Thesis, Artois, 2012. http://www.theses.fr/2012ARTO0206/document.
Full textAbstract:
La dispersion spatiale de l'habitat et des activités de ces dernières décennies a fortement contribué à un allongement des distances et des temps de trajets domicile-travail. Cela a pour conséquence un accroissement de l'utilisation des voitures particulières, notamment au sein et aux abords des grandes agglomérations. Afin de réduire les impacts dus à l'augmentation du trafic routier, des services de covoiturage, où des usagers ayant la même destination se regroupent en équipage pour se déplacer, ont été mis en place partout dans le monde. Nous présentons ici nos travaux sur le problème de covoiturage régulier. Dans cette thèse, le problème de covoiturage régulier a été modélisé et plusieurs métaheuristiques de résolution ont été implémentées, testées et comparées. La thèse est organisée de la façon suivante: tout d'abord, nous commençons par présenter la définition et la description du problème ainsi que le modèle mathématique associé. Ensuite, plusieurs métaheuristiques pour résoudre le problème sont présentées. Ces approches sont au nombre de quatre: un algorithme de recherche locale à voisinage variable, un algorithme à base de colonies de fourmis, un algorithme génétique guidée et un système multi-agents génétiques auto-adaptatif. Des expériences ont été menées pour démontrer l'efficacité de nos approches. Nous continuons ensuite avec la présentation et la résolution d'une extension du problème de covoiturage occasionel comportant plusieurs destinations. Pour terminer, une plate-forme de test et d'analyse pour évaluer nos approches et une plate-forme de covoiturage sont présentées dans l'annexeNowadays, 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
19
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.
Full textAbstract:
In this thesis we focus on Stochastic combinatorial Optimization Problems (SCOPs), a wide class of combinatorial optimization problems under uncertainty, where part of the information about the problem data is unknown at the planning stage, but some knowledge about its probability distribution is assumed.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
20
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.
Full textAbstract:
Nesta tese propõe-se um método heurístico para o problema de Projeto de Rede da Cadeia de Suprimentos (Supply Chain Network Design) considerando vários aspectos de relevância prática, tais como: fornecedores e matérias-primas, localização e operação de instalações, atribuição de Centros de Distribuição (CD), e grande número de clientes e produtos. Uma eficiente abordagem heurística de duas fases é proposta para a obtenção de soluções viáveis para os problemas, que inicialmente é modelado como um Programa Linear Inteiro Misto (PLIM) de grande escala. Na fase de construção, uma estratégia de Linear Programming Rounding é aplicada para se obter os valores iniciais para as variáveis de localização inteira do modelo. Simultaneamente, um método Multi-start foi desenvolvido para gerar soluções iniciais diversificadas para cada nova iteração da heurística de Rounding. Na segunda fase, dois procedimentos de Busca Local foram desenvolvidos no sentido de melhorar a solução fornecida pelo método de Rounding. Implementamos duas diferentes abordagens de Busca Local: remoção-inserção e troca. Uma técnica de Busca Tabu para orientar o procedimento de Busca Local para explorar os diferentes espaços de soluções foi desenvolvida. As formulações e algoritmos foram implementados na linguagem C++ utilizando ferramentas de otimização da COIN-OR. O método de solução foi experimentado em instâncias geradas aleatoriamente, com tamanhos diferentes em termos do número de parâmetros, tais como o número de produtos, zonas de clientes, CDs e fábricas considerando um sistema logístico de quatro níveis. As implementações computacionais mostram que o método de solução proposto obteve resultados satisfatórios quando comparados com a literatura. Para validar este método heurístico também foi usado em um caso realista, com base em dados de uma empresa de borracha que está reestruturando sua cadeia de suprimentos devido ao projeto de uma nova uma nova fábrica e produção de novos produtos. A abordagem heurística proposta revelou-se adequada para aplicação prática em um caso real de uma indústria multicommodity em um contexto determinístico.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.
21
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/.
Full textAbstract:
O ambiente de produção abordado neste trabalho é o Job Shop Flexível (JSF), uma generalização do Job Shop (JS). O problema de programação de tarefas, ou jobs, no ambiente JS é classificado por Garey; Johnson e Sethi (1976) como NP-Difícil e o JSF é, no mínimo, tão difícil quanto o JS. O JSF é composto por um conjunto de jobs, cada qual constituído por operações. Cada operação deve ser processada individualmente, sem interrupção, em uma única máquina de um subconjunto de máquinas habilitadas. O principal critério de desempenho considerado é a minimização dos atrasos dos jobs. São apresentados modelos de Programação Linear Inteira Mista (PLIM) para minimizar o atraso total e o instante de término da última operação, o makespan. São propostas novas regras de prioridade dos jobs, além de adaptações de regras da literatura. Tais regras são utilizadas por heurísticas construtivas e são aliadas a estratégias cujo objetivo é explorar características específicas do JSF. Visando aprimorar as soluções inicialmente obtidas, são propostas buscas locais e outros mecanismos de melhoria utilizados no desenvolvimento de três meta-heurísticas de diferentes categorias. Essas meta-heurísticas são: Iterated Local Search (ILS), classificada como meta-heurística de trajetória; Greedy Randomized Adaptive Search (GRASP), meta-heurística construtiva; e Artificial Bee Colony (ABC), meta-heurística populacional recentemente proposta. Esses métodos foram selecionados por alcançarem bons resultados para diversos problemas de otimização da literatura. São realizados experimentos computacionais com 600 instâncias do JSF, permitindo comparações entre os métodos de resolução. Os resultados mostram que explorar as características do problema permite que uma das regras de prioridade propostas supere a melhor regra da literatura em 81% das instâncias. As meta-heurísticas ILS, GRASP e ABC chegam a conseguir mais de 31% de melhoria sobre as soluções iniciais e a obter atrasos, em média, somente 2,24% superiores aos das soluções ótimas. Também são propostas modificações nas meta-heurísticas que permitem obter melhorias ainda mais expressivas sem aumento do tempo de execução. Adicionalmente é estudada uma versão do JSF com operações de Montagem e Desmontagem (JSFMD) e os experimentos realizados com um conjunto de 150 instâncias também indicam o bom desempenho dos métodos desenvolvidos.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.
22
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.
Full textAbstract:
La capacité à gagner du temps et à diminuer ses efforts est l'une des qualités de l'être humain, qui a conduit à exercer la pensée depuis l'Antiquité jusqu'à ces dernières décennies, caractérisées par l'émergence du mélange entre la rapidité des calculs et la précision des résultats, et ce dans plusieurs domaines. Le problème des tournées de véhicules et ses extensions sont, pour les théoriciens de ces utilités, d'une réelle importance quant aux applications du monde réel. Des recherches récentes dans ce domaine ont permis des avancées significatives dans la formulation des problèmes ainsi que dans la conception et l'analyse d'algorithmes. Dans cette étude, nous nous intéressons au problème de la logistique. Notre attention se porte en particulier sur un cas des réseaux de télécommunication, 2ECON-NDPR, et sur la façon de créer des designs d'une manière intelligente pour assurer la vitalité et la durabilité de la circulation de l'information. En outre. Nous choisissons les variantes problème de tournées de véhicules avec fenêtres de temps et problème de tournées de véhicules sélectives des familles VRP et OP respectivement. C'est dans ce cadre que s'inscrit cette thèse. La conception des solutions pour ces problèmes fait appel à la technique de programmation approchée connue pour sa rapidité de calcul. Il s’agit de Beam-search et de la recherche locale à grand voisinage. Nous présentons tout d’abord une étude détaillée des dernières problématiques précitées ainsi que différents types de méthodes de résolutions. Puis, nous exposons une méthode de recherche locale à grand voisinage adaptée pour la conception de réseau de survie avec relais, une proposition d’un algorithme de résolution approchée à trois phases pour le CVRPTW et, enfin, une proposition d'un algorithme de résolution approchée hybride pour le TOPThe 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
23
Š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.
Full textAbstract:
This thesis devote itself to use of information system for school agenda administration. Schools are forced to administer big amounts of informations, not only referred to their students. Broad issue is very extensive and disparate, so the most common types of data and demands on school information system operation are stated. The system for automatic generation of timetables is part of the school information system. At the first, basic conceptions of scheduling scope are defined and tied together with them are methods and algorithms for timetable creation problem solving. School timetabling is problem of scheduling lessons with certain limitative conditions. Further, thesis is engaged in design of school information system, data organization in such system and solving of system design problems. Designed information system accentuates on easy expandability and wide range of usage possibilities. Also suggested algorithm for solving of defined school timetabling is stated in this part of thesis.
24
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.
Full textAbstract:
Thesis deals with discrete optimization problems. It focusses on faster ways to find good solutions by means of heuristics and parallel processing. Based on ant colony optimization (ACO) algorithm coupled with k-optimization local search approach, it aims at massively parallel computing on graphics processors provided by Nvidia CUDA platform. Well-known travelling salesman problem (TSP) is used as a case study. Solution is based on dividing task into subproblems using tour-based partitioning, parallel processing of distinct parts and their consecutive recombination. Provided parallel code can perform computation more than seventeen times faster than the sequential version.
25
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.
Full text
26
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.
Full textAbstract:
Cette thèse présente un problème d'ordonnancement sur une ligne de production flexible. Dans une telle ligne, les postes de travail sont disposes séquentiellement, et chacun d'eux contient un certain nombre de machines parallèles identiques. Les pièces passent de poste en poste selon le même ordre et sont usinées par une des machines de chaque poste. Nos travaux portent sur l'étude de la minimisation de la date d'achèvement de la dernière pièce sur le dernier poste (makespan). Ce problème est np-difficile au sens fort. Nous étudions d'abord l'intérêt de ce type de ligne notamment en ce qui concerne la flexibilité, ensuite un état de l'art de ce domaine est présenté. Puis nous entamerons l'étude du flow shop flexible. Dans une première partie, nous proposons une borne inferieure pour le problème d'affectation (réduction à un seul poste). Ensuite nous développerons une heuristique pour ce cas particulier, en utilisant les algorithmes génétiques. Dans une seconde partie, nous présentons une heuristique pour un cas particulier du flow shop flexible à deux postes, puis on fera une étude théorique de sa performance. Nous proposons à la fin de cette thèse trois heuristiques pour le flow shop flexible, en utilisant trois méthodes différentes: l'amélioration locale, la méthode tabou et les algorithmes génétiques
27
Pandit, Vinayaka. "Local search heuristics for facility location problems." Thesis, 2004. http://localhost:8080/iit/handle/2074/2221.
Full text
28
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.
Full textAbstract:
碩士國立成功大學
工業與資訊管理學系碩博士班
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.
29
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.
Full textAbstract:
碩士國立中興大學
資訊科學研究所
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.
30
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.
Full textAbstract:
碩士國立交通大學
運輸工程與管理系
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.
31
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.
Full textAbstract:
Dissertação de mestrado em Engenharia de SistemasNesta 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.
32
Cheng, Chao-Jui, and 鄭朝瑞. "An Iterated Local Search Heuristic for Rotating Workforce Scheduling." Thesis, 2009. http://ndltd.ncl.edu.tw/handle/83920539579643610471.
Full textAbstract:
碩士華梵大學
工業工程與經營資訊學系碩士班
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
33
Dimova, Boryana Slavcheva. "Characterizing neighborhoods favorable to local search techniques." Thesis, 2004. http://repositories.lib.utexas.edu/bitstream/handle/2152/1308/dimovad16980.pdf.
Full text
34
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.
Full textAbstract:
This dissertation studies models for locating facilities in time varying demand
environments. We describe the characteristics of the time varying demand that motivate
the analysis of our location models in terms of total demand and the change
in value and location of the demand of each customer. The first part of the dissertation
is devoted to the dynamic location model, which determines the optimal
time and location for establishing capacitated facilities when demand and cost parameters
are time varying. This model minimizes the total cost over a discrete and
finite time horizon for establishing, operating, and closing facilities, including the
transportation costs for shipping demand from facilities to customers. The model
is solved using Lagrangian relaxation and Benders? decomposition. Computational
results from different time varying total demand structures demonstrate, empirically,
the performance of these solution methods.
The second part of the dissertation studies two location models where relocation
of facilities is not allowed and the objective is to determine the optimal location
of capacitated facilities that will have a good performance when demand and cost
parameters are time varying. The first model minimizes the total cost for opening
and operating facilities and the associated transportation costs when demand and
cost parameters are time varying. The model is solved using Benders? decomposition. We show that in the presence of high relocation costs of facilities (opening and closing
costs), this model can be solved as a special case by the dynamic location model. The
second model minimizes the maximum regret or opportunity loss between a robust
configuration of facilities and the optimal configuration for each time period. We
implement local search and simulated annealing metaheuristics to efficiently obtain
near optimal solutions for this model.
35
Lin, Chien-Chuan, and 林建權. "An Iterated Local Search Heuristic for the Periodic Location Routing Problem." Thesis, 2017. http://ndltd.ncl.edu.tw/handle/e89wzx.
Full textAbstract:
碩士國立交通大學
運輸與物流管理學系
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.
36
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.
Full text
37
Kinney, Gary W. "A group theoretic approach to metaheuristic local search for partitioning problems." Thesis, 2005. http://hdl.handle.net/2152/1594.
Full text
38
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.
Full textAbstract:
碩士國立交通大學
運輸與物流管理學系
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%.
39
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.
Full textAbstract:
碩士國立交通大學
運輸與物流管理學系
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%.
40
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.
Full textAbstract:
A generalized dynamic programming based algorithm and a local search heuristic
are used to solve the Two Runway Departure Scheduling Problem that arises at
an airport. The objective of this work is to assign the departing aircraft to one of the
runways and find a departing time for each aircraft so that the overall delay is minimized
subject to the timing, safety, and the ordering constraints. A reduction in the
overall delay of the departing aircraft at an airport can improve the airport surface
operations and aircraft scheduling. The generalized dynamic programming algorithm
is an exact algorithm, and it finds the optimal solution for the two runway scheduling
problem. The performance of the generalized dynamic programming algorithm
is assessed by comparing its running time with a published dynamic programming
algorithm for the two runway scheduling problem. The results from the generalized
dynamic programming algorithm show that this algorithm runs much faster than
the dynamic programming algorithm. The local search heuristic with k − exchange
neighborhoods has a short running time in the order of seconds, and it finds an approximate
solution. The performance of this heuristic is assessed based on the quality
of the solution found by the heuristic and its running time. The results show that
the solution found by the heuristic for a 25 aircraft problem has an average savings of
approximately 15 percent in delays with respect to a first come-first served solution. Also,
the solutions produced by a 3-opt heuristic for a 25 aircraft scheduling problem has an average quality of 8 percent with respect to the optimal solution found by the generalized
dynamic programming algorithm. The heuristic can be used for both real-time
and fast-time simulations of airport surface operations, and it can also provide an
upper limit for an exact algorithm. Aircraft arrival scheduling problems may also be
addressed using the generalized dynamic programming algorithm and the local search
heuristic with slight modification to the constraints.
41
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.
Full textAbstract:
碩士國立交通大學
運輸與物流管理學系
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%.
42
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.
Full textAbstract:
碩士國立臺灣大學
資訊工程學研究所
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.
43
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.
Full textAbstract:
碩士國立交通大學
運輸與物流管理學系
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