• Refine Query
  • Source
  • Publication year
  • to
  • Language
  • 75
  • 2
  • Tagged with
  • 80
  • 70
  • 34
  • 25
  • 21
  • 19
  • 17
  • 17
  • 16
  • 14
  • 14
  • 14
  • 13
  • 13
  • 13
  • About
  • The Global ETD Search service is a free service for researchers to find electronic theses and dissertations. This service is provided by the Networked Digital Library of Theses and Dissertations.
    Our metadata is collected from universities around the world. If you manage a university/consortium/country archive and want to be added, details can be found on the NDLTD website.
21

Um sistema de roteirização via internet para o campus da USP de Ribeirão Preto / A system of internet routing service for addresing at campus of University of São Paulo in Ribeirão Preto

Airton Manoel Romero Costa 26 March 2004 (has links)
Neste trabalho uma metodologia é proposta para disponibilizar, via internet, um serviço de roteirização de endereços para o campus da USP de Ribeirão Preto, com a determinação do menor caminho entre duas localidades. Esta metodologia pode ser aplicada não apenas ao campus da USP de Ribeirão Preto, mas ela poderá ser estendida às cidades e/ou regiões que possuam um mapa digital correspondente. Um sistema, denominado SIGRIB, foi desenvolvido para implementar a metodologia proposta. Utiliza o software ARCVIEW como suporte na manipulação de dados geográficos e cadastrais. Para facilitar a interação do usuário com o sistema SIGRIB, uma interface foi desenvolvida para que se possa fornecer duas localidades para as quais se deseja obter o menor caminho. O resultado desta consulta é uma figura ou conjunto de figuras contendo o menor caminho correspondente destacado. O sistema SIGRIB está disponível na internet (http://143.107.231.188/sigrib/pagina.asp) e vários testes são apresentados neste trabalho que demonstram o seu bom desempenho. / In this work a methodology is proposal to turn available, through internet, a routing service for addressing at campus of University of São Paulo, in Ribeirão Preto, including the determination of shortest way between two localities. This methodology can be applied not only to this campus but it can be extended to various cities and/or regions that have a corresponding digital map. A system, called SIGRIB, has been developed for implementing the proposed methodology. It utilizes ARCVIEW software as support for manipulation of geographical and cadastral data. To turn easy the interaction of user with SIGRIB system, a interface has been also implemented for that can provide two localities for which it desires to obtain the shortest path. The result of this search is a figure or set of figures containing the corresponding shortest path highlighted. The system SIGRIB is available in the internet (http://143.107.231.188/sigrib/pagina.asp) and several tests are presented in this work that demonstrate its good performance.
22

Algoritmos genéticos híbridos sem delimitadores de rotas para problemas de roteirização de veículos. / Hybrid genetic algorithms without trip delimeters for vehicle routing problems.

Araújo, Carlos Eduardo Di Giacomo 07 December 2007 (has links)
Apesar de serem utilizados com sucesso em problemas de roteirização clássicos como o do caixeiro-viajante e o de roteirização de veículos com janelas de tempo, os algoritmos genéticos não apresentavam bons resultados nos problemas de roteirização de veículos sem janelas de tempo. Utilizando-se de uma tendência recente de hibridização de algoritmos genéticos, Prins (2004) elaborou um algoritmo para o problema de roteirização de veículos sem janelas de tempo, monoperíodo, e que obrigatoriamente atenda a todos os clientes cujos resultados, quando aplicado a instâncias de Christofides et al. (1979) e de Golden et al. (1998), são comparáveis aos melhores códigos elaborados com base na busca tabu. Diferentemente da maioria dos algoritmos genéticos apresentados para solução de problemas de roteirização de veículos, no método desenvolvido por Prins (2004) o cromossomo é composto apenas pelos pontos a serem atendidos, não contendo delimitadores de rotas. Estas são definidas a partir de um método de particionamento do cromossomo. Este trabalho implementa o algoritmo descrito por Prins (2004) e propõe a este melhorias em diversas de suas etapas, como inicialização, operação de crossover, operação de mutação, reinicialização e particionamento do cromossomo. As alterações implantadas são aplicadas às instâncias de Christofides et al. (1979) e comparadas com o algoritmo inicial em termos de qualidade de solução e tempo de processamento. Finalmente, é elaborado um algoritmo genético que contempla as alterações que obtiveram resultados positivos. / In the Vehicle Routing Problem (VRP) we seek for a set of minimum-cost vehicle routes for a fleet of identical vehicles, each starting and ending at a depot, such that each customer is visited exactly once and the total demand of any route does not exceed the vehicle capacity. Several families of heuristics have been proposed for the VRP. They can be broadly classified into two main classes: classical heuristics developed between 1960 and 1990, and, more recently, metaheuristics. Among them, tabu search plays an key role, being acknowledged by most authors as the most successful approach for the VRP. In the literature some successful implementations of metaheuristic Genetic Algorithm (GA) can be found for classic routing problems such as the traveling salesman and vehicle routing problems with time windows. However, until recently, the same did not apply for the VRP. In this thesis we develop a genetic algorithm without trip delimiters, and hybridized with a local search procedure, for the solving the VRP, which is based on the work of Prins (2004). At any time, a chromosome can be converted into an optimal VRP solution (subject to chromosome sequence) by means of a splitting procedure, in which the chromosome sequence, representing a giant tour, is partitioned into feasible routes in terms of vehicle capacities. Starting with the procedure originally proposed Prins (2004), we then introduce new improvements in terms of the different components of the GA, aiming to obtain improved solutions. These include how we determine the initial population, different partitioning approaches, alternative reproduction (crossover) processes, a granular tabu mechanism similar to the one proposed by Toth and Vigo (2003 and, finally, in changes in the reinitialization process, aiming to reestablish diversity. Computational experiments are presented, based on the 14 classical Christofides instances for the VRP. The results show that the proposed improved versions of the GA allow us to obtain better solutions when compared to the original approach by Prins (2004).
23

Modelo de Alocação de Mamógrafos Móveis: Um estudo para a Região Serrana do Estado do Rio de Janeiro. / Allocation model of mobile mammography: a study for the mountain region of the State of Rio de Janeiro.

Gerson Nunes da Cunha 28 April 2015 (has links)
O Estado do Rio de Janeiro possui indicadores de produção muito baixos na realização de exames de câncer de mama. Na tentativa de melhorar o acesso aos exames, principalmente em regiões com baixa densidade populacional onde a aquisição de mamógrafos não é custo-efetiva, o uso da mamografia móvel é uma alternativa para aumentar a execução de exames de rastreamento de câncer de mama. O objetivo desta pesquisa é a construção de um modelo computacional para definir a alocação de mamógrafos móveis. O Modelo considera as variáveis associadas com os custos e prazos, indicando quando, onde e por quanto tempo, as unidades móveis de mamografia devem permanecer em cada cidade. O modelo foi construído no software de modelagem e simulação Anylogic, usando técnicas de modelagem baseada em agentes. O principal resultado é determinar o percurso de cada veículo disponível, para oferecer a cobertura desejada em cada cidade. Todas as entradas são parametrizadas, permitindo simular diferentes cenários e fornecer informações importantes para o processo de tomada de decisão. O horizonte de tempo, número de mamógrafos (fixos e móveis), a cobertura desejada da população, a capacidade de produção de cada dispositivo, a adesão da população urbana e rural, entre outras variáveis, foram consideradas no modelo. Os dados da Região Serrana do Rio de Janeiro foram usados nas simulações, onde menos de metade das cidades possuem mamógrafos fixos. Com o modelo proposto foi possível determinar a distribuição de cada dispositivo físico e o número ótimo de unidades móveis de mamografia para oferecer cobertura à totalidade da população no ciclo de dois anos. O número de mamógrafos para oferecer cobertura de toda a população da região poderia ser reduzido pela metade com o modelo de alocação proposto neste trabalho. A utilização de mamografia móvel, em conjunto com a rede existente de mamógrafos fixos, procura maximizar a disponibilização de exames de testes de diagnóstico de câncer de mama no estado do Rio de Janeiro. O desenvolvimento de um modelo de roteamento que aperfeiçoa a cobertura de rastreio do câncer de mama é apresentado como um complemento importante na tentativa de melhorar o acesso à população residente em áreas urbanas e rurais dos municípios. / The Rio de Janeiro State has low indicators in screening exams of breast cancer. As an attempt to improve access to exams, particularly in regions with low population density, where the acquisition of mammography is not cost- effective, the use of mobile mammography is an alternative to increase screening tests for breast cancer. The objective of this research is to build a computer model to define the allocation of mobile mammography. The model considers the variables associated with the costs and deadlines, indicating when, where and how long, the mobile mammography units must remain in each city. The model was built in the modeling and simulation software AnyLogic, using Agent-Based modelling techniques. The main result is to determine the route of each vehicle available, to offer the desired coverage for each city. All inputs are parameterized, enabling simulate different scenarios and providing important information for decision-making. The time horizon, number of mammography devices (fixed and mobile) available, desired coverage of the population, production capacity of each device, adherence of urban and rural population, among others variables, were considered into the model. The tests data came from Mountain Region of the Rio de Janeiro State, where less than half of cities have fixed mammography units. Women need to move to other cities for the examination, which leads to decreased adherence to mammographic screening programs. With the proposed model was possible to determine the distribution of each physical device and the optimum number of mobile mammography units to cover to the entire population in the 2-year cycle. The number of mammography devices to provide coverage to the entire population of the region could be reduced by half with the routing proposed in the model. The use of mobile mammography, together with the existing network of fixed mammography, indicated a possibility to optimize the uptake of breast cancer diagnostic tests in the Rio de Janeiro State. The development of a routing model that optimized the breast cancer screening coverage represent an important complement in an attempt to improve access to mammography exams.
24

Heurísticas para o problema de distribuição com estoques geridos pelo fornecedor. / Heuristics for the vendor managed inventory problem.

Andrei Znamensky 20 October 2006 (has links)
O presente trabalho aborda o sistema logístico usualmente denominado Vendor Managed Inventory (VMI), no qual o fornecedor controla e coordena as decisões de reabastecimento, sendo responsável por manter os estoques de seus clientes dentro de limites fixados de antemão. O modelo proposto incorpora ainda as decisões relativas à produção e manutenção de estoque por parte do fornecedor, além da utilização de frota heterogênea na distribuição, e busca a minimização dos custos totais do sistema. Quatro heurísticas de duas etapas são propostas para a resolução do problema abordado. A primeira etapa, comum a todas as heurísticas, baseia-se em uma heurística recentemente publicada na literatura e fornece uma solução inicial viável, utilizada como ponto de partida para a etapa de melhoria subsequente, na qual é utilizada a metaheurística busca tabu ou busca em vizinhança variável. As heurísticas propostas foram avaliadas em um conjunto de teste, sendo obtidos resultados melhores que os reportados na literatura em todas as instâncias testadas. Dentre as estratégias de solução avaliadas, destaca-se a heurística baseada em busca tabu com diversificação, que demonstrou ser superior às demais heurísticas propostas. Os resultados obtidos indicam ainda que, no caso da frota disponível ser heterogênea, é vantajosa a utilização de uma adaptação do procedimento de obtenção da solução inicial, como forma de privilegiar a utilização de veículos de maior eficiência. / This thesis deals with the logistic system usually called Vendor Managed Inventory (VMI). In this system the supplier controls and coordinates the supply decisions and is responsible for keeping the inventory of each of his clients within predetermined minimum and maximum levels. Heterogeneous fleet and production/stocking decisions at the supplier are considered as well, and the proposed model seeks to minimize the total system cost. Four two-stage heuristics are proposed for this problem. The first stage consists in an adaptation of a heuristic found in the bibliography, which provides an initial viable solution that will be improved in the second stage by means of the metaheuristics tabu search or variable neighborhood search. The proposed heuristics were tested on a set of benchmark instances with improvements found on the best known results in all of the tested instances. The obtained results indicate that the tabu search based heuristic with diversification strategy is clearly superior to the other proposed heuristics and that a better fleet utilization can be obtained in the case of heterogeneous fleet by a simple improvement in the first stage, that favors the selection of more efficient vehicles.
25

Análise de uso de SIG no sistema de coleta de resíduos sólidos domiciliares em uma cidade de pequeno porte

Lacerda, Márcio Gonçalves [UNESP] 21 February 2003 (has links) (PDF)
Made available in DSpace on 2014-06-11T19:29:14Z (GMT). No. of bitstreams: 0 Previous issue date: 2003-02-21Bitstream added on 2014-06-13T19:59:02Z : No. of bitstreams: 1 lacerda_mg_me_ilha.pdf: 2855408 bytes, checksum: 5e5e118488fcf8f01763b2f3ee45d02f (MD5) / Relata-se neste trabalho, a análise do uso de um Sistema de Informação Geográfica - SIG como ferramenta para roteirização de veículos de coleta de resíduos sólidos domiciliares. O software utilizado foi o TransCAD, versão 3.2, que é um SIG específico para profissionais de transportes, permitindo desenvolver rotas utilizando-se algoritmos que incluem um procedimento de roteirização em arco (Rotina Arc Routing). O objetivo dessa rotina é minimizar a extensão total a ser percorrida pelos veículos coletores. O estudo de caso foi realizado na cidade de Ilha Solteira - SP, localizada na região noroeste do estado. A cidade possui uma população de aproximadamente 24.000 habitantes, sendo considerada uma cidade de pequeno porte. O serviço de coleta de lixo domiciliar na cidade de Ilha Solteira é executado pelo Poder Público Municipal, sendo realizado por uma frota de três veículos que trabalham de segunda-feira a sábado cobrindo toda a cidade. Os resultados obtidos pelo TransCAD e os dados fornecidos pelo Setor de Obras e Serviços da Prefeitura Municipal foram processados no software Microsoft EXCEL, for Windows versão 2000, para a obtenção dos parâmetros operacionais. Os resultados obtidos com a rotina demonstraram reduções percentuais de até 41%, em termos de distância total percorrida, e, de 68% no tempo total de percurso, em relação ao serviço atual. Com relação às características dos sistemas de coleta dos municípios brasileiros de pequeno porte, observou-se que esses municípios não apresentam recursos humanos e materiais para lidarem com a problemática dos resíduos sólidos. / The use of Geographical Information System - GIS as tool for the routing of the collecting vehicles of domestic solid waste was analyzed. The software TransCAD, version 3.2, was used. This GIS serves to develop routes by algorithm that includes a procedure of arc routing (Routine Arc Routing). The objective of this routine is minimizing the total distance travelled by the collection vehicles. The case study it was carried in the city of Ilha Solteira/SP, Brazil, located in region the northwest of the state. The city has a population of approximately 24,000 inhabitants, being considered a city of little postage. The domestic solid waste collection in the city is execute of the municipal public power municipal, being carried for a fleet of three vehicles that work of monday the saturday, covering all the city. The results obtained by TransCAD and the data provided by the Sector of Works and Service of the City Hall Municipal, had been processed in software Microsoft EXCEL, for Windows 2000, for the obtaining of operational parameters. The results obtained with the routine showed reduce percentual of the until 41% in the distance total e, of the 68% in the time total, in comparison service current. Concerning the characteristics from the systems of collection from the counties Brazilians of little postage was observed that those counties no present resources human and material to get with the problematic from the solid waste.
26

Modelo de Alocação de Mamógrafos Móveis: Um estudo para a Região Serrana do Estado do Rio de Janeiro. / Allocation model of mobile mammography: a study for the mountain region of the State of Rio de Janeiro.

Gerson Nunes da Cunha 28 April 2015 (has links)
O Estado do Rio de Janeiro possui indicadores de produção muito baixos na realização de exames de câncer de mama. Na tentativa de melhorar o acesso aos exames, principalmente em regiões com baixa densidade populacional onde a aquisição de mamógrafos não é custo-efetiva, o uso da mamografia móvel é uma alternativa para aumentar a execução de exames de rastreamento de câncer de mama. O objetivo desta pesquisa é a construção de um modelo computacional para definir a alocação de mamógrafos móveis. O Modelo considera as variáveis associadas com os custos e prazos, indicando quando, onde e por quanto tempo, as unidades móveis de mamografia devem permanecer em cada cidade. O modelo foi construído no software de modelagem e simulação Anylogic, usando técnicas de modelagem baseada em agentes. O principal resultado é determinar o percurso de cada veículo disponível, para oferecer a cobertura desejada em cada cidade. Todas as entradas são parametrizadas, permitindo simular diferentes cenários e fornecer informações importantes para o processo de tomada de decisão. O horizonte de tempo, número de mamógrafos (fixos e móveis), a cobertura desejada da população, a capacidade de produção de cada dispositivo, a adesão da população urbana e rural, entre outras variáveis, foram consideradas no modelo. Os dados da Região Serrana do Rio de Janeiro foram usados nas simulações, onde menos de metade das cidades possuem mamógrafos fixos. Com o modelo proposto foi possível determinar a distribuição de cada dispositivo físico e o número ótimo de unidades móveis de mamografia para oferecer cobertura à totalidade da população no ciclo de dois anos. O número de mamógrafos para oferecer cobertura de toda a população da região poderia ser reduzido pela metade com o modelo de alocação proposto neste trabalho. A utilização de mamografia móvel, em conjunto com a rede existente de mamógrafos fixos, procura maximizar a disponibilização de exames de testes de diagnóstico de câncer de mama no estado do Rio de Janeiro. O desenvolvimento de um modelo de roteamento que aperfeiçoa a cobertura de rastreio do câncer de mama é apresentado como um complemento importante na tentativa de melhorar o acesso à população residente em áreas urbanas e rurais dos municípios. / The Rio de Janeiro State has low indicators in screening exams of breast cancer. As an attempt to improve access to exams, particularly in regions with low population density, where the acquisition of mammography is not cost- effective, the use of mobile mammography is an alternative to increase screening tests for breast cancer. The objective of this research is to build a computer model to define the allocation of mobile mammography. The model considers the variables associated with the costs and deadlines, indicating when, where and how long, the mobile mammography units must remain in each city. The model was built in the modeling and simulation software AnyLogic, using Agent-Based modelling techniques. The main result is to determine the route of each vehicle available, to offer the desired coverage for each city. All inputs are parameterized, enabling simulate different scenarios and providing important information for decision-making. The time horizon, number of mammography devices (fixed and mobile) available, desired coverage of the population, production capacity of each device, adherence of urban and rural population, among others variables, were considered into the model. The tests data came from Mountain Region of the Rio de Janeiro State, where less than half of cities have fixed mammography units. Women need to move to other cities for the examination, which leads to decreased adherence to mammographic screening programs. With the proposed model was possible to determine the distribution of each physical device and the optimum number of mobile mammography units to cover to the entire population in the 2-year cycle. The number of mammography devices to provide coverage to the entire population of the region could be reduced by half with the routing proposed in the model. The use of mobile mammography, together with the existing network of fixed mammography, indicated a possibility to optimize the uptake of breast cancer diagnostic tests in the Rio de Janeiro State. The development of a routing model that optimized the breast cancer screening coverage represent an important complement in an attempt to improve access to mammography exams.
27

Otimização do uso de recursos críticos no desenvolvimento de campos de petróleo offshore. / Optimization of the use of critical resources in the development of offshore fields.

Sérgio Bassi 23 August 2018 (has links)
O presente trabalho aborda a questão da interligação de poços de petróleo às plataformas de produção com a utilização de embarcações do tipo Pipe Laying Support Vessels (PLSVs). O objetivo do estudo é a maximização da curva de produção de óleo no período analisado, o que passa pelo melhor aproveitamento da frota de PLSVs contratada. São consideradas as especificidades da situação como, por exemplo, as restrições técnicas de cada embarcação para as atividades necessárias, a disponibilidade dos PLSVs, materiais para interligação e a já ocorrência da fase precedente, denominada completação. Considerando todo este conjunto de características do problema, desenvolveu-se uma formulação de Programação Linear Inteira Mista com pontos inovadores em relação à literatura, especialmente no que diz respeito ao incremento da curva de produção por conta da operação de poços injetores e ao declínio natural de poços produtores com o passar do tempo. Como os resultados obtidos nos testes da formulação matemática mostraram-se satisfatórios para pequenas instâncias, mas de alta complexidade computacional para um número grande de atividades, foram elaboradas duas versões de uma heurística construtiva adequada para a resolução de problemas de maior porte. Levando em consideração as mesmas características do problema que foram usadas na etapa de formulação matemática, puderam ser elaborados os algoritmos e suas devidas programações computacionais. A partir disso, foram realizados testes de pequeno porte para verificar a robustez dos algoritmos quanto aos seus comportamentos. Por fim, houve a comparação do caso completo, onde foram aplicadas as heurísticas, com o que ocorreu na situação real, tendo o resultado deste presente estudo apresentado um relevante ganho. / This research presents a real case of connection of oil wells in subsea environment to the production platforms with the use of ships of the type PLSV - Pipe Laying Support Vessels. The objective of this study is to maximize the oil production curve in the horizon considered, which is due to the best exploitation of the outsourced fleet. Specificities of the situation are considered like, for example, technical constraints of each vessel for the required activities, the availability of the PLSVs, materials for connection and the end of the previous phase, called completion. Considering all this set of the problem characteristics, it was developed a Mixed-Integer Linear Programming (MILP) formulation with innovative aspects in relation to the literature, especially with respect to the increase of the production curve due to the operation of injector wells and to the natural decline of producer wells during their operation, in the course of time. As the results obtained in the tests of the mathematical formulation were satisfactory for small instances, but with a high computational time for a great number of activities, two suitable constructive heuristics were elaborated for the resolution of larger problems. Numerical experiments were conducted, in small scale, to verify the robustness of the algorithms. Next, the proposed methods were applied to a real case of an oil company and relevant gains were observed.
28

Roteirização de veículos para o abastecimento de linhas de produção. / Routing of vehicles for material delivery to assembly lines.

Luiz Caccalano 07 May 2012 (has links)
Este trabalho trata do problema de roteirização de veículos para o abastecimento de linhas de produção, o qual pode ser entendido como uma particularização do problema clássico de roteirização de veículos (VRP Vehicle Routing Problem). Neste problema, peças estão armazenadas em um estoque central, chamado de supermercado, de onde são transferidas para pontos de uso localizados ao longo da linha de produção. O ritmo de fabricação na linha de produção é suposto constante, o que torna periódica a necessidade de reposição das embalagens com peças. Uma frota de rebocadores transporta as embalagens, dispostas sobre plataformas com rodas puxadas pelo mesmo e configurando um comboio. O objetivo do problema é roteirizar a frota de rebocadores, maximizando sua utilização e garantindo o atendimento da demanda gerada pela linha de produção. O problema é comum a muitas empresas de manufatura de bens de consumo e possui impacto direto nos custos operacionais. A literatura sobre o tema é escassa e as soluções empregadas na indústria habitualmente se baseiam na experiência prática de operadores ou responsáveis pela movimentação de materiais. Este trabalho propõe uma heurística para obtenção de uma solução para o problema, baseada em métodos de inserção. A heurística proposta foi aplicada a um caso na indústria automobilística e a comparação entre a solução obtida e aquela formulada por operadores demonstrou ganho no número de rotas. / This work studies the routing of vehicles for material delivery to assembly lines, which consists of a generalization of the classic Vehicle Routing Problem (VRP). In this problem, parts are stored in central depot called supermarket and from where they are distributed to points of use placed along the production line. Production rate in the assembly line is considered constant, which means that parts are delivered to points of use periodically. A fleet of tow cars transfers the boxes or containers of parts using wheeled towed carts. The objective of this problem is to route the fleet of the tow cars maximizing their utilization and fulfilling the assembly line demand for parts. This problem is common to several companies and has direct impacts in material handling costs. The theme is poorly explored in routing studies and many companies use operator experience to configure tow cars routes. This work proposes a heuristic based on insertion methods to find a solution for the problem. The heuristic was applied to a real problem and resulted in the reduction of the number of routes when compared to former operator solution.
29

O problema de roteirização periódica de veículos. / The period vehicle routing problem.

Luciele Wu 10 May 2007 (has links)
O problema de roteirização periódica de veículos pode ser considerado como uma generalização do problema clássico de roteirização devido a duas características próprias: um período de planejamento maior que um dia, em que os veículos fazem diversas viagens, e freqüências de visitas associadas a pontos a serem servidos. Esse tipo de problema pode ter muitas aplicações práticas. Atualmente, algumas indústrias automobilísticas brasileiras já utilizam um sistema de coleta que se baseia na idéia de roteirização periódica, com a finalidade de reduzir o estoque de peças. Assim como os problemas originais de roteirização de veículos, o problema aqui tratado é também difícil de ser resolvido, sendo impossível o uso de algoritmos exatos para a obtenção de uma solução ótima para o tamanho de problemas encontrados na prática. Isso motivou o estudo, que direcionou seus esforços na exploração de novas estratégias de solução para esse problema através de novas abordagens, de modo que houvesse um aumento na qualidade de soluções e uma diminuição do tempo de processamento computacional. Dois procedimentos diferentes foram propostos para a alocação dos clientes aos dias de visitas: uma heurística de inserção seqüencial que visa equilibrar os esforços dos diferentes dias do período de planejamento, e uma heurística baseada em algoritmos genéticos. As rotas diárias são construídas através da utilização do algoritmo de economias de Clarke e Wright, que permite a obtenção de boas soluções em tempos de processamento curtos. Experimentos computacionais são realizados para a avaliação da eficiência de cada uma das heurísticas propostas através da utilização de benchmarks retirados da literatura e problemas-teste gerados aleatoriamente, e os resultados são também comparados aos anteriormente mostrados na literatura. / The period vehicle routing problem can be viewed as a generalization of the classic vehicle routing problem due to two singular features: a planning period longer than one day in which vehicles make several trips and frequencies of visit associated to points to be serviced. This type of problem may arise in different practical applications. Nowadays, some Brazilian automaker industries are already utilizing a collect system based on the idea of the period routing in order to reduce parts inventory. Similarly to the original vehicle routing problem, the period vehicle routing problem is also hard to solve, making it impossible to use exact in order to obtain an optimal solution for problem sizes found in practice. This motivated this research study, which directed its efforts to the exploration of new strategies of solution through new reasoning, leading to an increase in the quality of the solution and a decrease in the computational processing time. The proposed heuristics are composed of three consecutive stages: (i) assigning customers to days of visit while respecting their given frequencies, (ii) building routes that serve all customers assigned to each day of the planning horizon, and (iii) improving the obtained solution. Despite the distinction between the stages, we managed to take into consideration the integration among the three decisions. Two different procedures were proposed to the assignment of customers to days of visit: a sequential insertion heuristic that aims to balance the workload among different days in the time horizon, and a heuristic based on genetic algorithms. The daily routes are then constructed by using the Clarke and Wright\'s savings algorithm, which allows good solutions to be obtained in short processing times. Computational experiments are made in order to evaluate the efficiency of each proposed heuristic using both benchmark problem sets from the literature and randomly generated problems as well, and the results are compared to the previously reported in the literature.
30

A meta-heurística busca dispersa em problemas de roteirização com coleta e entrega simultâneas: aplicação na Força Aérea Brasileira. / The scatter search metaheuristic in vehicle routing problems with simultaneous delivery and pickup: application in the brazilian air force.

Antônio Célio Pereira de Mesquita 08 April 2010 (has links)
O presente trabalho trata da solução para o problema da elaboração de programações de transporte do sistema de distribuição de materiais da Força Aérea Brasileira (FAB). Essas programações de transporte consistem em definir os roteiros de entrega e coleta de materiais a serem realizadas simultaneamente em cada local de entrega/coleta a partir de um centro de distribuição, considerando-se a frota de veículos homogênea. Isto é característico de um Problema de Roteirização de Veículos com Coletas e Entregas Simultâneas (PRVCES). A gestão do sistema de distribuição física da FAB considera a complexidade desse sistema e os dados relativos às demandas de transporte de carga em cada um desses locais para elaborar as programações de transporte. Essas programações são elaboradas tendo em vista os limites de capacidade dos veículos, as características físicas das cargas e as prioridades de embarque. O gestor desse sistema possui boa visibilidade das demandas de transporte, porém, devido à grande quantidade de informações disponíveis e à elevada complexidade desse sistema, é impossível elaborarem-se manualmente programações de transporte que resultem em viagens de distribuição eficientes. O PRVCES foi resolvido por meio da meta-heurística Busca Dispersa (do inglês Scatter Search) integrada com a meta-heurística Descida em Vizinhança Variável (do inglês Variable Neighborhood Descent) utilizada como método de melhoria das soluções. Os resultados superaram ou se igualaram a alguns dos obtidos por outros autores para os mesmos problemas de teste com as mesmas restrições, o que demonstra que a Busca Dispersa implementada é competitiva para solucionar o PRVCES. Quanto à aplicação na FAB, os resultados mostraram que a utilização do método de solução desenvolvido resultará em programações de transporte elaboradas em curto tempo de processamento e que estas incidirão positivamente sobre a eficiência do sistema de distribuição de materiais da FAB. / This work deals with the solution to the problem of drawing up transport schedules in the material distribution system of the Brazilian Air Force (BAF). These transport schedules consist in defining the routes for material pickup and delivery to be accomplished simultaneously in each delivery/pickup location from a distribution center, considering a homogeneous fleet of vehicles. This is characteristic of a Vehicle Routing Problem with Simultaneous Delivery and Pick-up (VRPSDP). The management of the physical distribution of BAF considers the complexity of this system and the data regarding the cargo transport demands in each one of those locations to draw up transport schedules. These schedules are drawn up regarding the capacity limits of the vehicles, the physical characteristics of the cargoes and the shipping priorities. A good visibility of transport demands in each location is available to the manager of this system, but due to the great quantity of data to deal with and the high complexity of the physical distribution system of BAF, it is impossible to draw up transport schedules that result in efficient distribution trips. The VRPSDP was solved by means of the Scatter Search meta-heuristic integrated with the Variable Neighborhood Descent meta-heuristic as the solution improvement method. The results exceeded or equaled some of those obtained by other authors using the same test problems with the same restrictions, what indicates that the implemented Scatter Search is competitive to solve the VRPSDP. As for the application in the BAF, the results showed that using the solution method developed will result in schedules drawn up in short processing time and focused on the efficiency of the material distribution system of the BAF.

Page generated in 0.0581 seconds