Made available in DSpace on 2014-06-12T16:00:14Z (GMT). No. of bitstreams: 2 arquivo6093_1.pdf: 741570 bytes, checksum: fdadc967604851f84c712755a38b8051 (MD5) license.txt: 1748 bytes, checksum: 8a4605be74aa9ea9d79846c1fba20a33 (MD5) Previous issue date: 2007 / A alocação de veículos para uma determinada demanda de consumidores, espalhados geograficamente, está sujeita a uma explosão combinatória de possibilidades, devido às infinitas alternativas de escalonamento. Esta característica impossibilita, para grandes demandas, o tratamento deste problema por algoritmos exatos, ou seja, aqueles que buscam com garantia a solução ótima do problema. Em contrapartida, existem os métodos heurísticos, que são capazes de resolver tais problemas de forma satisfatória, mas não garantindo que a solução alcançada seja a melhor possível. Esta dissertação apresenta, como principal contribuição, um Sistema Híbrido (SH) para o conhecido Problema de Roteamento de Veículos com Janela de Tempo (PRVJT). Este SH é composto dos métodos (i) Recozimento Simulado Não Monotônico (RSNM), (ii) Subida na Encosta (SE) e (iii) Reinício Aleatório (RA). Os métodos foram combinados visando promover a diversificação e a intensificação na busca por soluções do PRVJT. Como contribuição secundária, este trabalho apresenta um arcabouço de métodos estatísticos que é capaz de ajustar parâmetros de sistemas estocásticos para otimização de desempenho. Os resultados dos experimentos realizados com o modelo proposto foram comparados com cada um dos melhores resultados individuais, alcançados anteriormente, pelos diferentes algoritmos conhecidos, para toda a base de dados de Solomon. Os resultados obtidos pelo SH se mostraram relevantes, tendo o método superado ou igualado 37 das 56 instâncias testadas, caracterizando o SH como um método eficaz e robusto no tratamento do PRVJT

[pt] Nesta tese são propostos diversos algoritmos para resolver as versões estática e dinâmica de roteirização de veículos com janelas de tempo. Estes problemas têm como objetivo determinar rotas de custo mínimo para uma frota homogênea, atendendo a demanda de um conjunto de clientes dentro de intervalos de tempo determinados, chamados de janelas de tempos. Além disto, na versão dinâmica no problema, novos clientes podem ser atendidos durante a execução das rotas pelos veículos. Para a versão estática do problema propôs-se um algoritmo híbrido utilizando otimização por colônias de formigas e o método de descida em vizinhança variável aleatória. Os resultados computacionais mostram que o algoritmo foi capaz de encontrar soluções muito boas ou mesmo as melhores soluções conhecidas de instâncias usadas como benchmarking na literatura. Para a versão dinâmica do problema foram propostos seis algoritmos, baseados em métodos de inserção, de otimização por colônia de formigas e das versões sequencial e aleatória do método de busca em vizinhança variável. Os resultados computacionais mostram que a maior parte dos algoritmos propostos é competitiva com os algoritmos propostos na literatura, pois produzem soluções de boa qualidade e com esforço computacional reduzido. / [en] This thesis proposes several algorithms to solve the vehicle routing with time windows static and dynamic versions. These problems involve determining minimum cost routes for a homogeneous fleet in order to meet the demand of a set of customers within specified time intervals popularly called time windows. In addition, in the dynamic version of the problem, new customers can be assigned to vehicles during the execution of the routes. For the static version it was proposed a hybrid algorithm using ant colony optimization and the random variable neighborhood search method. The computational results show that the algorithm was able to find very good or even the best known solutions to benchmark instances. For the dynamic version it was proposed six algorithms, based on an insertion procedure, ant colony optimization and random and sequential versions of variable neighborhood search methods. Computational results show that most of the proposed algorithms are competitive regarding the state of the art, providing solutions of good quality with low computational effort.

Fornecedores necessitam atender a demanda de seus clientes da forma mais adequada possível e mantendo a qualidade de seu serviço, porém em muitos casos essa demanda é desconhecida. Esse problema pode ser modelado como um problema de roteirização e estoque com demanda estocástica o qual inclui o controle de estoque, transporte do produto e decisões de agendamento da entrega. Existem vários trabalhos na literatura para resolver esse problema, porém nenhum deles lida com janela de tempo de atendimento, capacidade máxima de estoque tanto no cliente quanto no depósito e o nível de confiança de atendimento individualizado para cada cliente. O objetivo principal deste trabalho é propor um novo algoritmo baseado em otimização matemática para lidar com esse problema mais realista. Além disso, este trabalho tem como objetivo secundário melhorar o algoritmo de estado da arte baseado em otimização matemática, visando encontrar soluções com um menor tempo computacional e custo. Foram realizados experimentos com instâncias sintéticas com 15 até 50 clientes, as quais são geradas aleatoriamente, e com uma instância real, baseada na experiência profissional no mercado empresarial e em cenários reais de distribuição na cidade de São Paulo / Providers need to supply the demand of their clients as optimally as possible and maintaining the quality of their service, however in many cases this demand is unknown. This problem can be modeled as a inventory routing problem with stochastic demand, which includes inventory control, product transportation and delivery scheduling decisions. There are several papers in the literature to solve this problem, but none of them deals with service time window, maximum stock capacity for both the customer and the depot and individualized confidence level for each costumer. The main objective of this work is to propose a new algorithm based on mathematical optimization to deal with this more realistic problem. In addition, this work has as secondary objective to improve the state of the art algorithm based on mathematical optimization, aiming to find solutions with a lower computational time and cost. Experiments were performed with synthetic instances with 15 to 50 clients, which are randomly generated, and with a real instance, based on professional experience in the business market and in real distribution scenarios in the city of São Paulo

Fornecedores necessitam atender a demanda de seus clientes da forma mais adequada possível e mantendo a qualidade de seu serviço, porém em muitos casos essa demanda é desconhecida. Esse problema pode ser modelado como um problema de roteirização e estoque com demanda estocástica o qual inclui o controle de estoque, transporte do produto e decisões de agendamento da entrega. Existem vários trabalhos na literatura para resolver esse problema, porém nenhum deles lida com janela de tempo de atendimento, capacidade máxima de estoque tanto no cliente quanto no depósito e o nível de confiança de atendimento individualizado para cada cliente. O objetivo principal deste trabalho é propor um novo algoritmo baseado em otimização matemática para lidar com esse problema mais realista. Além disso, este trabalho tem como objetivo secundário melhorar o algoritmo de estado da arte baseado em otimização matemática, visando encontrar soluções com um menor tempo computacional e custo. Foram realizados experimentos com instâncias sintéticas com 15 até 50 clientes, as quais são geradas aleatoriamente, e com uma instância real, baseada na experiência profissional no mercado empresarial e em cenários reais de distribuição na cidade de São Paulo / Providers need to supply the demand of their clients as optimally as possible and maintaining the quality of their service, however in many cases this demand is unknown. This problem can be modeled as a inventory routing problem with stochastic demand, which includes inventory control, product transportation and delivery scheduling decisions. There are several papers in the literature to solve this problem, but none of them deals with service time window, maximum stock capacity for both the customer and the depot and individualized confidence level for each costumer. The main objective of this work is to propose a new algorithm based on mathematical optimization to deal with this more realistic problem. In addition, this work has as secondary objective to improve the state of the art algorithm based on mathematical optimization, aiming to find solutions with a lower computational time and cost. Experiments were performed with synthetic instances with 15 to 50 clients, which are randomly generated, and with a real instance, based on professional experience in the business market and in real distribution scenarios in the city of São Paulo

Orientador: Francisco de Assis Magalhães Gomes Neto / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Matematica, Estatistica e Computação Cientifica / Made available in DSpace on 2018-08-12T23:12:18Z (GMT). No. of bitstreams: 1 Vieira_HeloisaPassarelli_M.pdf: 1211437 bytes, checksum: 312aded4a440d526d723ab88a2a23588 (MD5) Previous issue date: 2008 / Resumo: Nos últimos anos, diversas heurísticas e meta-heurísticas foram propostas para o Problema de Roteamento de Veículos com Janela de Tempo (PRVJT), cujo objetivo é determinar a rota a ser seguida por uma frota de veículos para servir um número de clientes em um dado intervalo de tempo, sem violar a capacidade dos veículos. Cada cliente é visitado por exatamente um veículo e somente uma vez. Esta disertação apresenta um estudo das técnicas utilizadas para o PRVJT, dando ênfase para os Algoritmos Genéticos. Diversos tipos de cruzamento e esquemas de mutação, além de outras técnicas avançadas, tal como o Hill-Climbing, são analisados. Para o algoritmo que implementamos, são apresentados vários resultados numéricos baseados em um conjunto de 56 problemas, cada qual com 100 clientes, proposto por Solomon. O desempenho do algoritmo que implementamos também é comparado aos melhores resultados publicados na literatura / Abstract: In recent years, several heuristic and metaheuristic methods were proposed for the Vehicle Routing Problem with Time Windows (VRPTW). The objective of the problem is to serve a set of customers within a given time interval, without violating the capacity of the vehicles. Each customer must be visited once and by only one vehicle. This dissertation presents a survey on the techniques used to solve the VRPTW, with emphasis on the genetic algorithms. Several crossover and mutation schemes, as well as other advanced techniques, such as the Hill-Climbing are analyzed. Numerical results based on Solomon's 56 VRPTW 100-customer instances are presented for the algorithm implemented here. The performance of our algorithm is also compared with the best results published in the specialized literature / Mestrado / Pesquisa Operacional / Mestre em Matemática Aplicada

Este trabalho apresenta um estudo teórico da Técnica de Geração de Colunas (GC) aplicada em alguns Problemas de Roteamento de Veículo (PRV). Essa técnica foi inicialmente utilizada para tratar problemas de otimização de grande porte com estruturas especiais[Dantzig & Wolfe, 1960]. Dentre as diversas classes de problemas de roteamento; revisamos a aplicação dessa técnica a dois casos particulares: O problema de roteamento de helicópteros em plataformas marítimas, cujo objetivo minimizar o custo total do transporte; O problema de roteamento com janela de tempo, onde a função objetivo é descrita pelo tamanho da frota e o custo do percurso. Revisamos e implementamos um algoritmo de caminho mínimo com janela de tempo (CMJT). Esse algoritmo surge como um sub-problema do algoritmo Primai Simplex para resolver o problema de partição de conjunto, utilizado para modelar o problema de roteamento com janela de tempo. / This work presents a study about the Column Generation Technique (CG) applied to some Vehicle Ftouting Problems. The technique was first used to deal with optimization problems having special structures. Among the vaa-ious classes of routing problems, we review the use of the technique in two specific cases: Ftouting helicopters for crew exchanges on off-shore locations, where the objective is to minimize the total transportation cost; Ftouting with time windows, where the objective function is composed by the size of the fleet and the cost of route. We review and implement a shortest path algorithm with time windows. This algorithm aa-ises as a sub-problem in the Primai Simplex algorithm to solve the linear relaxation of the set partitioning problem used to model the routing problem with time windows.

Em um mercado global, tem sido observada a tendência para a dispersão geográfica das fabricas. Esta dispersão e motivada pela oportunidade de explorar as vantagens locais, sob diferentes pontos de vista. Essa estrutura também permite a interação mais intensa entre plantas de diferentes empresas produtivas. Neste sentido, o conceito de Empresa Virtual (EV) e fundamental para explorar novas estratégias de negócios, tais como foco nas competências essenciais, orientação máxima para o cliente e produção distribuída. No entanto, nesta nova estrutura produtiva, há novos requisitos para o planejamento e para o estabelecimento da data de entrega dos pedidos. Um sistema de Planejamento e Controle da Produção (PCP) convencional utiliza uma arquitetura hierárquica, o que não atende o requisito de autonomia das empresas parceiras. Para atender a essas novas exigências, este trabalho apresenta uma arquitetura de sistemas de planejamento e controle da produção no contexto de EV. Na proposta são utilizados os conceitos de janelas de tempo em conjunto com propagação de restrições para atender os requisitos de prazo de entrega de produtos. Estes dois conceitos tem sido amplamente utilizados na literatura relacionada a sistemas de planejamento convencionais, no entanto, não no contexto de EV. Nesta abordagem, as janelas de tempo delimitam o intervalo de alocação das tarefas nos sistemas de produção envolvidos, enquanto as restrição de capacidade identificam janelas de tempo factíveis considerando a importância da data de vencimento do pedido. E apresentado um exemplo da utilização da arquitetura e um exemplo de implementação. Este trabalho engloba EVs com empresas parceiras de diversos tipos de produção (produção em lotes e produção discreta). E utilizado o Production Flow Schema (PFS) para modelagem dos processos produtivos segundo uma abordagem hierárquica, com base em sucessivos renamentos para construir o modelo de forma progressiva e estruturada onde as propriedades do modelo ficam asseguradas por construção. Este refinamento gera sub-grafos em Rede de Petri, que são utilizados para a analise e o controle do processo produtivo. / In a global market, the trend for geographical dispersion of manufacturing plants has been observed. This dispersion is motivated by the opportunity to exploit local advantages under dierent viewpoints. This structure also allows for more intense interaction between plants of dierent productive enterprises. In this sense, the concept of Virtual Enterprise (VE) is fundamental to explore new business strategies such asfocus on core competencies,maximal customer orientationanddistributed production. However, in this new productive structure, there are new requirements for planning and for establishing the delivery date of the orders. A conventional Production Planning and Control system (PPC) uses a hierarchical architecture, which does not meet the requirement of autonomy of the partners companies. To address these new requirements, this work introduces a Production Planning and Control System Architecture in EV context. In the proposal are used the concepts oftime windowsandconstraint propagationto meet the deadline requirements of product delivery. These two concepts have been widely used in the literature relating to conventional planning systems, however, not in the EV context. In this approach, thetime windowsdelimit the allocation range of tasks in production systems involved, while the capacity constraint identify the feasible time window considering the importance of the ordes due date. An example of using the architecture and an implementation is presented. This work includes EVs with partner companies of various types of production (production batch and discrete manufacturing). Production Flow Schema (PFS) is used for modeling the processes according to a hierarchical approach based on successive renements to construct progressive and structured model where the properties of model are ensured by construction. This renement generates sub-graphs in Petri Net, which are used for the analysis and control of the production process.

Made available in DSpace on 2015-03-05T13:59:42Z (GMT). No. of bitstreams: 0 Previous issue date: 27 / Nenhuma / As escalas de tripulações em companhias aéreas é um fator importante na logística de operações dessas empresas e um problema interessante para a aplicação de Pesquisa operacional. Os custos com tripulantes no transporte aéreo são extremamente altos, superiores a 20% dos custos de operações das empresas. Diante desse contexto, este trabalho vem abordar o problema de rotações de tripulações em empresas aéreas. Uma rotação de tripulação – crew pairings – é uma seqüência de etapas ou segmentos de vôo que começam e terminam em uma base domiciliar de tripulantes. O objetivo deste planejamento é encontrar um subconjunto dessas rotações com custo mínimo e que cubra todas as etapas de vôo na programação da empresa atendendo as restrições inerentes ao problema. O trabalho desenvolveu uma solução para o problema com um modelo set covering/set partitioning, primeiramente, promovendo, uma solução inicial viável que foi aplicada, numa segunda etapa, a um processo de otimização utilizando a meta-heurística Busca Tabu e jan / The flight scheduling crews in airliners are an important factor in logistic of operations of a these companies and interesting problem for the application of Operational Research. The costs with crew members in the air transportation are extremely high, superior 20% of the costs of operations of the companies. So, this study presents an approach of the crew pairing problem in airlines. The objective of this planning is to find a subgroup of these pairings with minimum cost and that it covers all the flight legs in the programming of the airliners taking care of the inherent restrictions to the problem. The solution for the problem implemented a set covering/set partitioning model, first, promoting, a viable initial solution that was applied, in one second stage, to optimize process using the meta-heuristic Tabu Search and time windows. The results had disclosed values satisfactory, demonstrating solutions that, compared with the real solution, had promoted minimization indices superior 70%. The validation

Este trabalho apresenta um estudo teórico da Técnica de Geração de Colunas (GC) aplicada em alguns Problemas de Roteamento de Veículo (PRV). Essa técnica foi inicialmente utilizada para tratar problemas de otimização de grande porte com estruturas especiais[Dantzig & Wolfe, 1960]. Dentre as diversas classes de problemas de roteamento; revisamos a aplicação dessa técnica a dois casos particulares: O problema de roteamento de helicópteros em plataformas marítimas, cujo objetivo minimizar o custo total do transporte; O problema de roteamento com janela de tempo, onde a função objetivo é descrita pelo tamanho da frota e o custo do percurso. Revisamos e implementamos um algoritmo de caminho mínimo com janela de tempo (CMJT). Esse algoritmo surge como um sub-problema do algoritmo Primai Simplex para resolver o problema de partição de conjunto, utilizado para modelar o problema de roteamento com janela de tempo. / This work presents a study about the Column Generation Technique (CG) applied to some Vehicle Ftouting Problems. The technique was first used to deal with optimization problems having special structures. Among the vaa-ious classes of routing problems, we review the use of the technique in two specific cases: Ftouting helicopters for crew exchanges on off-shore locations, where the objective is to minimize the total transportation cost; Ftouting with time windows, where the objective function is composed by the size of the fleet and the cost of route. We review and implement a shortest path algorithm with time windows. This algorithm aa-ises as a sub-problem in the Primai Simplex algorithm to solve the linear relaxation of the set partitioning problem used to model the routing problem with time windows.

Em um mercado global, tem sido observada a tendência para a dispersão geográfica das fabricas. Esta dispersão e motivada pela oportunidade de explorar as vantagens locais, sob diferentes pontos de vista. Essa estrutura também permite a interação mais intensa entre plantas de diferentes empresas produtivas. Neste sentido, o conceito de Empresa Virtual (EV) e fundamental para explorar novas estratégias de negócios, tais como foco nas competências essenciais, orientação máxima para o cliente e produção distribuída. No entanto, nesta nova estrutura produtiva, há novos requisitos para o planejamento e para o estabelecimento da data de entrega dos pedidos. Um sistema de Planejamento e Controle da Produção (PCP) convencional utiliza uma arquitetura hierárquica, o que não atende o requisito de autonomia das empresas parceiras. Para atender a essas novas exigências, este trabalho apresenta uma arquitetura de sistemas de planejamento e controle da produção no contexto de EV. Na proposta são utilizados os conceitos de janelas de tempo em conjunto com propagação de restrições para atender os requisitos de prazo de entrega de produtos. Estes dois conceitos tem sido amplamente utilizados na literatura relacionada a sistemas de planejamento convencionais, no entanto, não no contexto de EV. Nesta abordagem, as janelas de tempo delimitam o intervalo de alocação das tarefas nos sistemas de produção envolvidos, enquanto as restrição de capacidade identificam janelas de tempo factíveis considerando a importância da data de vencimento do pedido. E apresentado um exemplo da utilização da arquitetura e um exemplo de implementação. Este trabalho engloba EVs com empresas parceiras de diversos tipos de produção (produção em lotes e produção discreta). E utilizado o Production Flow Schema (PFS) para modelagem dos processos produtivos segundo uma abordagem hierárquica, com base em sucessivos renamentos para construir o modelo de forma progressiva e estruturada onde as propriedades do modelo ficam asseguradas por construção. Este refinamento gera sub-grafos em Rede de Petri, que são utilizados para a analise e o controle do processo produtivo. / In a global market, the trend for geographical dispersion of manufacturing plants has been observed. This dispersion is motivated by the opportunity to exploit local advantages under dierent viewpoints. This structure also allows for more intense interaction between plants of dierent productive enterprises. In this sense, the concept of Virtual Enterprise (VE) is fundamental to explore new business strategies such asfocus on core competencies,maximal customer orientationanddistributed production. However, in this new productive structure, there are new requirements for planning and for establishing the delivery date of the orders. A conventional Production Planning and Control system (PPC) uses a hierarchical architecture, which does not meet the requirement of autonomy of the partners companies. To address these new requirements, this work introduces a Production Planning and Control System Architecture in EV context. In the proposal are used the concepts oftime windowsandconstraint propagationto meet the deadline requirements of product delivery. These two concepts have been widely used in the literature relating to conventional planning systems, however, not in the EV context. In this approach, thetime windowsdelimit the allocation range of tasks in production systems involved, while the capacity constraint identify the feasible time window considering the importance of the ordes due date. An example of using the architecture and an implementation is presented. This work includes EVs with partner companies of various types of production (production batch and discrete manufacturing). Production Flow Schema (PFS) is used for modeling the processes according to a hierarchical approach based on successive renements to construct progressive and structured model where the properties of model are ensured by construction. This renement generates sub-graphs in Petri Net, which are used for the analysis and control of the production process.