Spelling suggestions: "subject:"heuristic algorithms"" "subject:"heuristic a.lgorithms""
51 |
O problema do Hiker Dice em tabuleiro compacto: um estudo algor?tmicoPereira, Elder Gon?alves 21 March 2014 (has links)
Made available in DSpace on 2014-12-17T15:48:10Z (GMT). No. of bitstreams: 1
ElderGP_DISSERT.pdf: 2430148 bytes, checksum: e80c00c94f59463e3fe65b2466f0f400 (MD5)
Previous issue date: 2014-03-21 / Coordena??o de Aperfei?oamento de Pessoal de N?vel Superior / The Hiker Dice was a game recently proposed in a software designed by Mara Kuzmich and Leonardo Goldbarg. In the game a dice is responsible for building a trail on an n x m board. As the dice waits upon a cell on the board, it prints the side that touches the surface. The game shows the Hamiltonian Path Problem Simple Maximum Hiker Dice (Hidi-CHS) in trays Compact Nth , this problem is then characterized by looking for a Hamiltonian Path that maximize the sum of marked sides on the board. The research now related, models the problem through Graphs, and proposes two classes of solution algorithms. The first class, belonging to the exact algorithms, is formed by a backtracking algorithm planed with a return through logical rules and limiting the best found solution. The second class of algorithms is composed by metaheuristics type Evolutionary Computing, Local Ramdomized search and GRASP (Greed Randomized Adaptative Search). Three specific operators for the algorithms were created as follows: restructuring, recombination with two solutions and random greedy constructive.The exact algorithm was teste on 4x4 to 8x8 boards exhausting the possibility of higher computational treatment of cases due to the explosion in processing time. The heuristics algorithms were tested on 5x5 to 14x14 boards. According to the applied methodology for evaluation, the results acheived by the heuristics algorithms suggests a better performance for the GRASP algorithm / O Hiker Dice foi um jogo proposto recentemente em um software projetado por Mara Kuzmich e Leonardo Goldbarg. No jogo um dado ? respons?vel pela constru??o de uma trilha sobre um tabuleiro n x m. O dado ao visitar uma c?lula do tabuleiro imprime (marca) a face que entra em contato com a superf?cie. O jogo apresenta o Problema do Caminho Hamiltoniano Simples M?ximo Hiker Dice (CHS-HiDi) em Tabuleiros Compactos de ordem N , esse problema ? ent?o caracterizado por buscar um caminho hamiltoniano que maximize a soma dos faces do dado marcados no tabuleiro. A pesquisa presentemente relatada, modela o problema atrav?s de Grafos, e prop?e duas classes de algoritmos de solu??o. A primeira classe, pertencente aos algoritmos exatos, ? constitu?da por um algoritmo em backtracking aparelhado com um retorno realizado atrav?s de regras l?gicas e limite da melhor solu??o encontrada. A segunda classe de algoritmos ? constitu?da por metaheur?sticas do tipo Computa??o Evolucion?ria, Busca Local Aleatorizada e GRASP (Greed Randomized Adaptative Search). Para os algoritmos foram criados tr?s operadores espec?ficos da seguinte forma: de reestrutura??o, de recombina??o com duas solu??es e construtivo guloso aleat?rio. O algoritmo exato foi testado em tabuleiros 4x4 a 8x8 esgotando a possibilidade de tratamento computacional dos casos maiores em virtude da explos?o em tempo de processamento. Os algoritmos heur?sticos foram testados nos tabuleiros 5x5 at? 14x14. Segundo a metodologia de avalia??o utilizada, os resultados encontrados pelos algoritmos heur?sticos sugere um melhor potencial de desempenho para o algoritmo GRASP
|
52 |
Otimização multiobjetivo dos parâmetros do sistema de suspensão de um modelo de veículo completo através de um algoritmo meta-heurísticoFossati, Giovani Gaiardo January 2017 (has links)
O presente trabalho otimizou os parâmetros concentrados do sistema de suspensão de um modelo de veículo completo, representando um automóvel de passeio que trafega a uma velocidade constante por um determinado perfil de pista previsto na norma ISO 8608, 1995, através da utilização de um algoritmo meta-heurístico de otimização multiobjetivo. Duas rotinas numérico-computacionais foram desenvolvidas, visando realizar tal otimização tanto no domínio do tempo quanto no domínio da frequência. A utilização de algoritmos meta-heurísticos vem ganhando espaço na otimização de sistemas mecânicos, proporcionando rapidez e precisão na obtenção de resultados ótimos. Ao se combinar um algoritmo de otimização a um modelo que represente satisfatoriamente um sistema mecânico, obtém-se uma ferramenta indicadora dos parâmetros de máxima eficiência do sistema, que pode ser utilizada em inúmeras aplicações. Pretendeu-se, com a integração de rotinas de análise dinâmica nos domínios do tempo e da frequência ao algoritmo genético de otimização multiobjetivo NSGA-II, desenvolvido por Deb et al., 2002, a obtenção de duas fronteiras ótimas de Pareto. Estas fronteiras consistem no conjunto de soluções não dominadas que minimizam as seguintes funções objetivo: o valor RMS ponderado da aceleração vertical do assento do motorista, o valor RMS da média do fator de amplificação dinâmica das quatro rodas do modelo e o máximo deslocamento relativo entre cada roda e a carroceria. O método proposto por Shinozuka e Jan, 1972, é utilizado para a obtenção do perfil de irregularidades da pista no domínio do tempo a partir das equações de densidade espectral de potência (PSD) que representam as diferentes classes de pavimentos. O método de Newmark, 1959, é utilizado para resolver a equação diferencial de movimento no domínio do tempo e obter a resposta dinâmica do modelo a tais irregularidades. O comportamento dinâmico do modelo de veículo no domínio da frequência foi obtido através da utilização da função de resposta em frequência (FRF) do modelo de veículo analisado. Os resultados demonstraram a capacidade de ambas as rotinas de análise dinâmica desenvolvidas de produzir resultados consistentes com os encontrados na literatura, bem como a capacidade dos algoritmos de otimização implementados de fornecer fronteiras ótimas de Pareto para os problemas propostos. / The proposed work optimized the concentrated parameters of a full-vehicle model’s suspension system, being that model representative of a passenger car which travels at a constant speed on a certain road profile provided by the ISO 8608, 1995, standard, using a multi-objective meta-heuristic optimization algorithm. Two numerical-computational routines were developed, seeking to perform said optimization for both the time and frequency domains. The use of meta-heuristic algorithms has been increasing in mechanical systems optimization, providing speed and accuracy in obtaining an optimal result. Combining an optimization algorithm with a model that satisfactorily represents a mechanical system yields a tool that indicates the system’s maximum efficiency parameters, which can be used in numerous applications. It was intended, with the integration of the dynamic analysis routines to the multi-objective genetic optimization algorithm NSGA-II, developed by Deb et al., 2002, the obtainment of two Pareto-optimal fronts. These fronts consist in the set of non-dominated solutions that minimize the following objective functions: the weighted RMS value of the driver’s seat vertical acceleration, the mean RMS value of the model wheel’s dynamic amplification factor, and the maximum relative displacement between each wheel and the body of the vehicle model. The method proposed by Shinozuka and Jan, 1972, is used to obtain the road irregularity profile in the time domain from the power spectral density (PSD) equations that represent the different pavement classes. The Newmark’s method (1959) is used to solve the differential motion equation in the time domain, in order to obtain the vehicle model’s responses to these irregularities. The dynamic behavior of the vehicle model in the frequency domain was obtained through the use of the frequency response function (FRF) of the analyzed model. The results showed the capacity of both the dynamic analysis routines developed in generating results that are consistent with those found in literature, as well as the capacity of the optimization algorithms implemented in providing Pareto optimal fronts to the proposed problems.
|
53 |
Times assíncronos inicializadores para o planejamento da expansão da transmissão de energia elétrica baseados no modelo híbrido linear /Sanchez, Fernando Rodrigo Lopes. January 2008 (has links)
Orientador: Sérgio Azevedo de Oliveira / Banca: Rubén Augusto Romero Lazaro / Banca: Eduardo Nobuhiro Asada / Resumo: Neste trabalho foram implementados diversos agentes heuristicos construtivos, baseados no modelo híbrido linear, que fazem parte de um time assíncrono que tem como objetivo gerar configurações de boa qualidade para inicializar as metaheuríticas que resolvem o problema do planejamento da expansão da transmissão dos sistemas de energia elétrica. A teoria de times assíncronos foi aplicada para reunir as qualidades individuais dos métodos heurísticos, de uma maneira que, partindo de uma configuração base (sem adições) e utilizando um fluxo de dados cíclico, os agentes construtivos adicionassem circuitos a esta configuração de maneira sistemática e aleatória até que esta atenda as demandas de carga solicitadas pelo sistema elétrico em um horizonte futuro. Estas configurações foram então utilizadas por um algoritmo genético no intuito de validar a qualidade das mesmas. Os algoritmos foram implementados em Fortran, utilizando as rotinas de trocas de mensagens do LAM-MPI e simulados para sistemas teste de pequeno, médio e grande porte em ambiente de processamento distribuido. Os resultados comprovam que os times ass'ıncronos de vários metodos heurísticos são mais eficazes comparados com uma única heurística. / Abstract: In this study, it was implemented several constructive heuristic algorithms, based on hybrid linear model, which are part of a asynchronous team that aims to generate initial solutions with good quality for meta-heuristics that solve the transmission expansion planning problem of electric power systems. The theory of asynchronous team was applied to meet the individual qualities of each heuristic method, in a way that, starting from a base network configuration and using a cyclical flow of data, heuristic agents add circuits to is configuration in a systematic and random way until they meet the load demands requested by the electrical system on a future horizon. Then these configurations are utilized by a genetic algorithm in order to validate the quality of them. The algorithms were implemented in Fortran, using exchanging messages routines from LAM-MPI and simulated for small, medium and large size test-systems in distributed processing environment. The results show that the solutions obtained with asynchronous teams of several heuristic methods are more effective than the solutions with a single heuristic algorithm. / Mestre
|
54 |
Otimização multiobjetivo dos parâmetros do sistema de suspensão de um modelo de veículo completo através de um algoritmo meta-heurísticoFossati, Giovani Gaiardo January 2017 (has links)
O presente trabalho otimizou os parâmetros concentrados do sistema de suspensão de um modelo de veículo completo, representando um automóvel de passeio que trafega a uma velocidade constante por um determinado perfil de pista previsto na norma ISO 8608, 1995, através da utilização de um algoritmo meta-heurístico de otimização multiobjetivo. Duas rotinas numérico-computacionais foram desenvolvidas, visando realizar tal otimização tanto no domínio do tempo quanto no domínio da frequência. A utilização de algoritmos meta-heurísticos vem ganhando espaço na otimização de sistemas mecânicos, proporcionando rapidez e precisão na obtenção de resultados ótimos. Ao se combinar um algoritmo de otimização a um modelo que represente satisfatoriamente um sistema mecânico, obtém-se uma ferramenta indicadora dos parâmetros de máxima eficiência do sistema, que pode ser utilizada em inúmeras aplicações. Pretendeu-se, com a integração de rotinas de análise dinâmica nos domínios do tempo e da frequência ao algoritmo genético de otimização multiobjetivo NSGA-II, desenvolvido por Deb et al., 2002, a obtenção de duas fronteiras ótimas de Pareto. Estas fronteiras consistem no conjunto de soluções não dominadas que minimizam as seguintes funções objetivo: o valor RMS ponderado da aceleração vertical do assento do motorista, o valor RMS da média do fator de amplificação dinâmica das quatro rodas do modelo e o máximo deslocamento relativo entre cada roda e a carroceria. O método proposto por Shinozuka e Jan, 1972, é utilizado para a obtenção do perfil de irregularidades da pista no domínio do tempo a partir das equações de densidade espectral de potência (PSD) que representam as diferentes classes de pavimentos. O método de Newmark, 1959, é utilizado para resolver a equação diferencial de movimento no domínio do tempo e obter a resposta dinâmica do modelo a tais irregularidades. O comportamento dinâmico do modelo de veículo no domínio da frequência foi obtido através da utilização da função de resposta em frequência (FRF) do modelo de veículo analisado. Os resultados demonstraram a capacidade de ambas as rotinas de análise dinâmica desenvolvidas de produzir resultados consistentes com os encontrados na literatura, bem como a capacidade dos algoritmos de otimização implementados de fornecer fronteiras ótimas de Pareto para os problemas propostos. / The proposed work optimized the concentrated parameters of a full-vehicle model’s suspension system, being that model representative of a passenger car which travels at a constant speed on a certain road profile provided by the ISO 8608, 1995, standard, using a multi-objective meta-heuristic optimization algorithm. Two numerical-computational routines were developed, seeking to perform said optimization for both the time and frequency domains. The use of meta-heuristic algorithms has been increasing in mechanical systems optimization, providing speed and accuracy in obtaining an optimal result. Combining an optimization algorithm with a model that satisfactorily represents a mechanical system yields a tool that indicates the system’s maximum efficiency parameters, which can be used in numerous applications. It was intended, with the integration of the dynamic analysis routines to the multi-objective genetic optimization algorithm NSGA-II, developed by Deb et al., 2002, the obtainment of two Pareto-optimal fronts. These fronts consist in the set of non-dominated solutions that minimize the following objective functions: the weighted RMS value of the driver’s seat vertical acceleration, the mean RMS value of the model wheel’s dynamic amplification factor, and the maximum relative displacement between each wheel and the body of the vehicle model. The method proposed by Shinozuka and Jan, 1972, is used to obtain the road irregularity profile in the time domain from the power spectral density (PSD) equations that represent the different pavement classes. The Newmark’s method (1959) is used to solve the differential motion equation in the time domain, in order to obtain the vehicle model’s responses to these irregularities. The dynamic behavior of the vehicle model in the frequency domain was obtained through the use of the frequency response function (FRF) of the analyzed model. The results showed the capacity of both the dynamic analysis routines developed in generating results that are consistent with those found in literature, as well as the capacity of the optimization algorithms implemented in providing Pareto optimal fronts to the proposed problems.
|
55 |
Modelos de simulação e otimização para sistemas hidrotérmicos / Simulation and optimization models for hydrothermal systemsRamos, Edson da Silva 15 September 2016 (has links)
Submitted by JÚLIO HEBER SILVA (julioheber@yahoo.com.br) on 2017-08-31T17:54:58Z
No. of bitstreams: 2
Dissertação - Edson da Silva Ramos - 2017.pdf: 3997839 bytes, checksum: 46c0db17187cdc3a0d29e581ce8b11f0 (MD5)
license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) / Approved for entry into archive by Luciana Ferreira (lucgeral@gmail.com) on 2017-09-15T13:42:24Z (GMT) No. of bitstreams: 2
Dissertação - Edson da Silva Ramos - 2017.pdf: 3997839 bytes, checksum: 46c0db17187cdc3a0d29e581ce8b11f0 (MD5)
license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) / Made available in DSpace on 2017-09-15T13:42:24Z (GMT). No. of bitstreams: 2
Dissertação - Edson da Silva Ramos - 2017.pdf: 3997839 bytes, checksum: 46c0db17187cdc3a0d29e581ce8b11f0 (MD5)
license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5)
Previous issue date: 2016-09-15 / The problem of planning the hydrothermal systems is complex, dynamic, stochastic,
interconnected and nonlinear. In this work this problem is treated to meet one goal:
minimize the use of water tank during a scenario of natural river flows lean period. This
paper presents the application of meta-heuristics mono-objective of this problem, using a
set of eight real plants in the National Interconnected System during the period of five
years. The algorithms used were: PSO, ABeePSO, LSSPSO and KFPSO. The experiments
were compared to studies using Nonlinear Programming and it appears that this work
presents a simulation model and optimization for flexible hydrothermal system and highly
adaptable to the use of different meta-heuristics allowing the researcher to apply different
algorithms and compare the results between them. / O problema do planejamento da operação de sistemas hidrotérmicos é complexo, dinâmico,
estocástico, interconectado e não linear. Nesse trabalho esse problema é tratado de forma
a atender um objetivo: minimizar o uso do reservatório de água durante um cenário de
período de escassez de vazão natural dos rios. Este trabalho apresenta a aplicação de
meta-heurísticas mono-objetivo a esse problema, utilizando um conjunto de oito usinas
reais do Sistema Interligado Nacional durante o período de cinco anos. Os algoritmos
utilizados foram: PSO, ABeePSO, LSSPSO e KFPSO. Os experimentos realizados foram
comparados com estudos que utilizaram Programação Não Linear. E conclui-se que esse
trabalho apresenta um modelo de simulação e otimização para sistema hidrotérmicos
flexível e altamente adaptável para o uso de diversas meta-heurísticas possibilitando o
pesquisador aplicar diferentes algoritmos e comparar esses resultados entre os mesmos.
|
56 |
Algoritmo heurístico construtivo aplicado ao planejamento de redes aéreas de média tensão com a alocação de geração distribuída / Construtive heuristic algorithm applied to the planning of medium voltage networks carries with the allocation of distributed generationBenitez, Elias Emanuel 16 August 2017 (has links)
Submitted by Miriam Lucas (miriam.lucas@unioeste.br) on 2018-02-22T17:03:28Z
No. of bitstreams: 2
Elias_Emanuel_Benitez_2017.pdf: 4075070 bytes, checksum: ce09c54d8b2b9dd647b8166881114648 (MD5)
license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) / Made available in DSpace on 2018-02-22T17:03:28Z (GMT). No. of bitstreams: 2
Elias_Emanuel_Benitez_2017.pdf: 4075070 bytes, checksum: ce09c54d8b2b9dd647b8166881114648 (MD5)
license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5)
Previous issue date: 2017-08-16 / The solution to distribution networks expansion planning problem seeks to establish
updates in the system so that it is able to supply the future demand obeying important criteria
that represent the quality in the supply.
Considering that in recent years the number of distributed generation connected to the
system is increasing, contributing to the solution of some problems in the operation such as the
high losses, the poor quality in the energy supplied, the low reliability that can be a reality,
among others, this article presents a new algorithm to be applied to expansion planning of
medium voltage overhead lines and which also has the ability to establish a plan for the
connection of distributed generation in the network.
Thus, the algorithm operates in two steps. In the first step of operation, a new topology is
established for the network, which meets the future demand and respects the technical criteria
that are necessary for electricity to be delivered to consumers with quality. In this process, the
problem is represented by a nonlinear mathematical model whose objective function seeks to
minimize the cost of network expansion and the constraints represent the physical laws that
govern the power flow and ensure that future demand will be met with quality. In this operation
step, the solution to the problem is constructed in an iterative way, where in each iteration a
specialized sensitivity indicator uses the information obtained through the solution of the
mathematical model to aid in decision making. This step of the algorithm ends when a radial
topology for the system is determined.
In the second step, the algorithm performs an evaluation in the established topology to
indicate the capacity and the most interesting buses for connection of the Distributed
Generation, seeking the best benefit for the operation of the network. In this process, the
algorithm also takes advantage of the information obtained through the nonlinear mathematical
model for the evaluation.
Computacional tests with the new algorithm were performed considering data from
systems available in the specialized literature to evaluate their performance. The results
obtained through the simulations showed that the algorithm finds excellent solutions and a good
convergence time. / A solução para o problema de Planejamento da Expansão de Redes de Distribuição busca
por fazer atualizações no sistema para que este seja capaz de suprir a demanda futura
obedecendo a critérios importantes que representam a qualidade do suprimento.
Considerando que nos últimos anos o número de geração distribuída conectada ao sistema
está aumentando, contribuindo para a solução de problemas que envolvem a operação do
sistema, tais como, as perdas elétricas, a má qualidade da energia fornecida, a baixa
confiabilidade, entre outros, este trabalho apresenta um novo algoritmo para ser aplicado ao
problema de planejamento da expansão de linhas aéreas de média tensão e que também tem a
capacidade de estabelecer um plano para a conexão de geração distribuída na rede.
O algoritmo funciona em duas etapas. Na primeira etapa de execução, uma nova topologia
radial é estabelecida para a rede, que atende a demanda futura e respeita os critérios técnicos
necessários para que a eletricidade seja entregue aos consumidores com qualidade. Neste
processo, o problema é representado por um modelo matemático não linear cuja função objetivo
procura minimizar o custo de expansão da rede e as restrições representam as leis físicas que
regem o fluxo de potência elétrica e garantem que a demanda futura seja atendida com
qualidade, obedecendo aos limites de tensões estabelecidos para as barras e às capacidades de
carregamento das linhas. Nesta etapa de execução, a solução do problema é construída de forma
iterativa, onde em cada iteração um indicador de sensibilidade especializado usa a informação
obtida através da solução do modelo matemático para auxiliar na tomada de decisão. Esta etapa
do algoritmo termina quando uma topologia radial para o sistema é determinada.
Na segunda etapa de execução, o algoritmo realiza uma avaliação na topologia
estabelecida para indicar a capacidade da geração distribuída e a barra do sistema para sua
conexão, buscando o melhor benefício para a operação da rede. Neste processo, o algoritmo
também aproveita as informações obtidas através do modelo matemático não linear para esta
avaliação.
Testes computacionais com o novo algoritmo foram realizados considerando sistemas
testes disponíveis na literatura especializada para avaliar o seu desempenho. Os resultados
obtidos através das simulações mostraram que o algoritmo encontra excelentes soluções em
tempos de convergência satisfatórios.
|
57 |
Planejamento dinâmico da expansão de sistemas de transmissão de energia elétricaPoubel, Raphael Paulo Braga 04 July 2016 (has links)
Submitted by Renata Lopes (renatasil82@gmail.com) on 2017-01-06T17:13:56Z
No. of bitstreams: 1
raphaelpaulobragapoubel.pdf: 14885655 bytes, checksum: 55ce1d3cf1619213e5c2364f54de5a50 (MD5) / Approved for entry into archive by Diamantino Mayra (mayra.diamantino@ufjf.edu.br) on 2017-01-31T11:24:55Z (GMT) No. of bitstreams: 1
raphaelpaulobragapoubel.pdf: 14885655 bytes, checksum: 55ce1d3cf1619213e5c2364f54de5a50 (MD5) / Made available in DSpace on 2017-01-31T11:24:55Z (GMT). No. of bitstreams: 1
raphaelpaulobragapoubel.pdf: 14885655 bytes, checksum: 55ce1d3cf1619213e5c2364f54de5a50 (MD5)
Previous issue date: 2016-07-04 / O presente trabalho propõe um modelo não linear inteiro misto para o planejamento dinâmico da expansão da transmissão. Para a representação do modelo, se fez uso do fluxo de carga CC. As equações básicas do fluxo CC foram modificadas e expandidas de forma a incluir as variáveis de decisão e o acoplamento temporal entre os investimentos. Para a solução do modelo, de forma a mitigar as dificuldades inerentes à programação inteira, foram propostas técnicas de solução passo a passo. Em cada uma das técnicas as variáveis inteiras foram substituídas por uma função contínua de forma a se obter tempos computacionaisviáveis. Adiscretizaçãodasvariáveisinteirassedácomoauxíliodeíndices de sensibilidade apropriados, calculados a partir do modelo acoplado. O trabalho também investiga metodologias para o planejamento dinâmico de linhas de transmissão, buscando um equilíbrio entre a economia e a confiabilidade no processo de decisão dos investimentos. O critério determinístico N-1 foi escolhido para garantir maior confiabilidade ao sistema. / This work proposes a non-linear mixed integer model for dynamic transmission lines expansion planning. The DC load flow was used to represent the model. The basic equationsoftheDCloadflowweremodifiedandexpandedtoincludethedecisionvariables and the temporal coupling between investments. For the model solution, in order to mitigate the difficulties inherent of integer programming, step-by-step processes were proposed. In each of the techniques the integer variables have been replaced with a continuous function to obtain viable computational time. The discretization of the integer variables is made with the aid of appropriate sensitivity indexes, calculated from the coupled model. The work also suggests methods for dynamic transmission planning, seeking a balance between the economy and reliability in the investment decision process. The N-1 deterministic criteria was chosen to ensure system reliability.
|
58 |
Some PC-based Heuristics For Employee Pick-up Vehicle Routing Problem And Influence Of Spatial Demand DistributionMathirajan, M 03 1900 (has links) (PDF)
No description available.
|
59 |
Optimalizace tras při rozvozu europalet / Optimal routes for Euro pallet transportingJuříčková, Ivana January 2014 (has links)
This diploma thesis describes a logistic problem of the company JACER-CZ Ltd. The main focus is on identifying optimal routes about the Euro pallets distribution. The Euro pallets are standardized at length replaceable transport pallets which are in Europe. The aim of this thesis is to find a solution which will meet requirements of all thirteen customers and simultaneously a total route length of all vans will be minimalized. At first there is the mathematical model about the delivery assignment with the split delivery vehicle calculated by solvers CPLEX and Gurobi. Then the original and the modified example is solved manually by heuristic algorithms. It is concerned the nearest neighbour algorithm, savings algorithm, the insertion algorithm and the heuristic method for the split delivery vehicle routing problem.
|
60 |
Modification, development, application and computational experiments of some selected network, distribution and resource allocation models in operations researchNyamugure, Philimon January 2017 (has links)
Thesis (Ph.D. (Statistics)) -- University of Limpopo, 2017 / Operations Research (OR) is a scientific method for developing quantitatively
well-grounded recommendations for decision making. While it is true that it
uses a variety of mathematical techniques, OR has a much broader scope. It is
in fact a systematic approach to solving problems, which uses one or more analytical
tools in the process of analysis. Over the years, OR has evolved through
different stages. This study is motivated by new real-world challenges needed
for efficiency and innovation in line with the aims and objectives of OR – the
science of better, as classified by the OR Society of the United Kingdom. New
real-world challenges are encountered on a daily basis from problems arising
in the fields of water, energy, agriculture, mining, tourism, IT development,
natural phenomena, transport, climate change, economic and other societal requirements.
To counter all these challenges, new techniques ought to be developed.
The growth of global markets and the resulting increase in competition
have highlighted the need for OR techniques to be improved. These developments,
among other reasons, are an indication that new techniques are needed
to improve the day-to-day running of organisations, regardless of size, type and
location.
The principal aim of this study is to modify and develop new OR techniques
that can be used to solve emerging problems encountered in the areas of linear
programming, integer programming, mixed integer programming, network
routing and travelling salesman problems. Distribution models, resource allocation
models, travelling salesman problem, general linear mixed integer
ii
programming and other network problems that occur in real life, have been
modelled mathematically in this thesis. Most of these models belong to the
NP-hard (non-deterministic polynomial) class of difficult problems. In other
words, these types of problems cannot be solved in polynomial time (P). No general
purpose algorithm for these problems is known. The thesis is divided into
two major areas namely: (1) network models and (2) resource allocation and
distribution models. Under network models, five new techniques have been developed:
the minimum weight algorithm for a non-directed network, maximum
reliability route in both non-directed and directed acyclic network, minimum
spanning tree with index less than two, routing through 0k0 specified nodes,
and a new heuristic to the travelling salesman problem. Under the resource
allocation and distribution models section, four new models have been developed,
and these are: a unified approach to solve transportation and assignment
problems, a transportation branch and bound algorithm for the generalised assignment
problem, a new hybrid search method over the extreme points for
solving a large-scale LP model with non-negative coefficients, and a heuristic
for a mixed integer program using the characteristic equation approach. In
most of the nine approaches developed in the thesis, efforts were done to compare
the effectiveness of the new approaches to existing techniques. Improvements
in the new techniques in solving problems were noted. However, it was
difficult to compare some of the new techniques to the existing ones because
computational packages of the new techniques need to be developed first. This
aspect will be subject matter of future research on developing these techniques
further. It was concluded with strong evidence, that development of new OR
techniques is a must if we are to encounter the emerging problems faced by the
world today.
Key words: NP-hard problem, Network models, Reliability, Heuristic, Largescale
LP, Characteristic equation, Algorithm.
|
Page generated in 0.0612 seconds