Submitted by Livia Mello (liviacmello@yahoo.com.br) on 2016-09-16T12:55:52Z No. of bitstreams: 1 DissAAAD.pdf: 1563807 bytes, checksum: cd9db1180896a8d853b8d7cd4c694860 (MD5) / Approved for entry into archive by Marina Freitas (marinapf@ufscar.br) on 2016-09-21T18:31:23Z (GMT) No. of bitstreams: 1 DissAAAD.pdf: 1563807 bytes, checksum: cd9db1180896a8d853b8d7cd4c694860 (MD5) / Approved for entry into archive by Marina Freitas (marinapf@ufscar.br) on 2016-09-21T18:31:28Z (GMT) No. of bitstreams: 1 DissAAAD.pdf: 1563807 bytes, checksum: cd9db1180896a8d853b8d7cd4c694860 (MD5) / Made available in DSpace on 2016-09-21T18:31:33Z (GMT). No. of bitstreams: 1 DissAAAD.pdf: 1563807 bytes, checksum: cd9db1180896a8d853b8d7cd4c694860 (MD5) Previous issue date: 2016-02-29 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES) / In this dissertation we address the vehicle routing problem with time windows and multiple deliverymen, a variant of the vehicle routing problem that involves the additional decision of the crew size definition of the vehicles, besides scheduling and routing decisions. This problem arises in the distribution of goods in highly congested urban areas, where due to the relatively long service times, it may be difficult to serve all clients during regular working hours. Given this difficulty, an alternative consists in including the deliverymen assignment decision, which leads to extra costs in addition to travel and vehicle costs. The objective is to define routes to serve customer clusters minimizing the number of vehicles used, the number of allocated deliverymen and the traveled distance. In this study, we develop different solution methods to solve this problem. Initially, we present two metaheuristic approaches, which are based on Iterated Local Search and Large Neighborhood Search. Then we propose hybrid methods, combining these metaheuristics with a branch-price-and-cut method. Computational experiments using instances from the literature confirm the efficiency of the solution methods developed for the problem. / Nesta dissertação aborda-se o problema de roteamento de veículos com janelas de tempo e múltiplos entregadores, uma variante do problema de roteamento de veículos recentemente proposta na literatura que, além das decisões de programação e roteamento, envolve a determinação do tamanho da tripulação de cada veículo. Esse problema surge na distribuição de bens em centros urbanos congestionados em que, devido aos tempos de serviço relativamente longos, pode ser difícil atender a todos os clientes durante o horário normal de trabalho. Diante dessa dificuldade, uma alternativa consiste em incluir a designação de entregadores extras, o que gera custos adicionais aos custos tradicionais de deslocamento e utilização de veículos. Neste problema, o objetivo é definir rotas para atender grupos de clientes minimizando o número de veículos usados, o número total de entregadores designados e a distância total percorrida. Para tratar o problema, são desenvolvidos diferentes métodos de solução. Inicialmente, são apresentadas duas abordagens metaheurísticas baseadas em Busca Local Iterada e Busca em Vizinhança Grande. Posteriormente, são propostos métodos híbridos de solução a partir da combinação dessas metaheurísticas com um método branch-price-and-cut. Experimentos computacionais usando instâncias encontradas na literatura confirmam a eficiência dos métodos de solução desenvolvidos para o problema.

Made available in DSpace on 2016-06-02T19:51:37Z (GMT). No. of bitstreams: 1 2212.pdf: 1886443 bytes, checksum: bddd5428751623f23f36b7a2f2f3442c (MD5) Previous issue date: 2008-12-15 / Universidade Federal de Minas Gerais / In recent years, several studies have been revising static distribution models used by companies in order to incorporate intrinsic dynamic features of transport operations. Thanks to new technologies such as global positioning systems and wireless communications, vehicle routes elaborated in the beginning of the planning horizon can be altered in real time in order to serve new requests, avoid traffic jams, or find alternatives when some of the fleet vehicles are late or broke. In this way, realistic solutions of better quality are expected to be obtained from the company´s point of view (smaller costs) as well as from the customers´ (better service level). The main objective of this work is to analyze the impacts resulting from the incorporation of dynamic vehicle routing and scheduling in service production systems where the due dates for service is a prioritary issue. Specifically, we tackled the Dynamic Vehicle Routing Problem, where route plans are elaborated in a planning horizon. Initially, the definition and characteristics of dynamic problems are presented along with a review of some of the main contributions in the literature. We propose a heuristic based on Pureza and Laporte´s algorithm (2008) in order to obtain routes in real time. The relative impact of the heuristic application to other methods is analyzed by means of a set of generated instances from the data supplied by a drink company in São Paulo State. / Nos últimos anos, um crescente número de estudos científicos vem revisando modelos estáticos de distribuição adotados por empresas a fim de incorporar o dinamismo intrínseco às operações envolvidas. Esta tendência se deve principalmente aos avanços tecnológicos na área de geo-referenciamento, os quais permitem que rotas elaboradas no início do horizonte de planejamento sejam alteradas em tempo real a fim de atender novas requisições de clientes, evitar congestionamentos de tráfego, ou ainda, encontrar alternativas na ocorrência de veículos atrasados ou quebrados. Desta forma, espera-se obter soluções realistas de maior qualidade tanto do ponto de vista da empresa (menores custos) como dos clientes (melhor nível de serviço). Este trabalho tem como objetivo principal analisar o impacto decorrente da incorporação de métodos de roteamento dinâmico de veículos em ambientes de prestação de serviço onde o prazo de atendimento é o objetivo prioritário. Especificamente, é tratado o Problema de Roteamento de Veículos Dinâmico, onde planos de rotas são elaborados ao longo de um horizonte de planejamento. Inicialmente, a definição e características de problemas dinâmicos são apresentadas, juntamente com uma revisão de algumas das principais contribuições da literatura. É proposta, então, uma heurística baseada no algoritmo de Pureza e Laporte (2008) para elaboração de rotas em tempo real. O impacto da aplicação da heurística é analisado frente a outros métodos, utilizando-se um conjunto de instâncias geradas a partir de dados fornecidos por uma empresa do setor de bebidas do interior do estado de São Paulo.

Made available in DSpace on 2016-06-02T19:51:46Z (GMT). No. of bitstreams: 1 3393.pdf: 4478459 bytes, checksum: 69570a1820f1617b090f2e79453e5ec4 (MD5) Previous issue date: 2010-12-15 / Financiadora de Estudos e Projetos / The pursuit of excellence in customer service drives companies to investigate strategies that help to produce satisfactory solutions to the market, as is the case of beverage companies. One of the obstacles faced by this sector is the difficulty in distributing the demanded products within regular working hours due to long service times in each demand site. An alternative for reducing violations of route time consists in including the assignment of extra deliverymen to the usual routing and scheduling decisions. Such treatment is hardly often explored in the literature and it was not found any evidence of commercial softwares that consider it. In this sense, the current work addresses the Vehicle Routing Problem with the assignment of extra deliverymen, with the aim of generating routes in which the number of unserved clients in regular working hours is minimized. To this end, we propose an extension of Clarke and Wright heuristic. The proposed extension is applied to sets of examples generated based on classic instances of Solomon (1987) and Christofides et al. (1979). The results of the application are compared to those provided by the heuristic of Clarke and Wright according to a set of performance criteria. / A busca pela excelência no atendimento aos clientes faz com que empresas investiguem estratégias que auxiliem a obtenção de soluções satisfatórias no mercado, como é o caso das empresas do setor de bebidas. Um dos obstáculos enfrentados por este setor é a dificuldade em distribuir os produtos demandados dentro da jornada de trabalho estabelecida, em função dos altos tempos de serviço existentes em cada ponto de demanda. Uma alternativa para reduzir violações de tempo de rota consiste em incluir a designação de entregadores extras às decisões de roteamento e programação. Este tratamento é pouco explorado na literatura e não foi encontrada nenhuma evidência de softwares comerciais que o considerem. Neste sentido, o corrente trabalho aborda o Problema de Roteamento de Veículos com designação de entregadores extras, com o objetivo de gerar rotas em que o número de clientes não atendidos em uma dada jornada de trabalho seja minimizado. Para tal, é proposta uma extensão da heurística de Clarke e Wright. A extensão proposta é aplicada a conjuntos de exemplos gerados com base nas instâncias clássicas de Solomon (1987) e Christofides et al. (1979). Os resultados obtidos nestas aplicações são comparados aos fornecidos pela heurística de Clarke e Wright segundo um conjunto de critérios de desempenho.

Made available in DSpace on 2016-06-02T19:52:13Z (GMT). No. of bitstreams: 1 DissJMRB.pdf: 944400 bytes, checksum: b37a0f175baab577681e6785f305edee (MD5) Previous issue date: 2005-06-23 / This project consists in the refinement of the tabu search adaptive approach HTSA (PUREZA, 1996) and the analysis of its performance when applied to the classical Vehicle Routing Problem and to the Vehicle Routing Problem with Time Windows. HTSA promotes the integration of intensification and diversification strategies through the systematic variation of the values of selected tabu parameters, mostly based on the analysis of search trajectory patterns. The development of new implementations based on tabu search (GLOVER, 1989; GLOVER & LAGUNA, 1997) is an interesting avenue of research since tabu search has offered new marks on solution quality in routing problems, usually outperforming other methods. The results obtained with the application of HTSA approach to a set of classical routing instances and to a set of routing with times windows instances indicate quality solutions within reasonable computational times when compared to the results provided by competitive methods in the literature. / O corrente projeto tem como objetivo o refinamento da abordagem adaptativa de busca tabu HTSA (PUREZA, 1996) e a verificação de seu desempenho quando aplicada ao Problema de Roteirização de Veículos clássico e ao Problema de Roteirização com Janelas de Tempo. A abordagem HTSA tem como objetivo a integração de estratégias de intensificação e diversificação, consistindo na variação sistemática de valores de parâmetros tabu selecionados e apoiada principalmente na análise de padrões da trajetória da busca. O desenvolvimento de novas abordagens baseadas na meta-heurística busca tabu (GLOVER, 1989; GLOVER & LAGUNA, 1997) é uma linha de pesquisa interessante uma vez que a busca tabu tem oferecido novas marcas em qualidade da solução em problemas de Roteirização de veículos e suas variantes, geralmente superando outros métodos. Os resultados obtidos com a aplicação da abordagem HTSA a instâncias de roteirização de veículos clássicas e com janela de tempo indicam soluções de qualidade em tempos computacionais razoáveis quando comparadas aos resultados de métodos competitivos da literatura.

Made available in DSpace on 2015-05-08T14:53:38Z (GMT). No. of bitstreams: 1 arquivototal.pdf: 3056611 bytes, checksum: e73001b52f3f37e092e742b4d599ce04 (MD5) Previous issue date: 2014-02-14 / Conselho Nacional de Desenvolvimento Científico e Tecnológico / This dissertation deals with the Pollution-Routing Problem (PRP), a Vehicle Routing Problem (VRP) with environmental considerations, recently introduced in the literature by Bekta ¸s e Laporte (2011). The objective is to minimize operational and environmental costs while respecting route-load constraints and service time windows. Costs are based on driver wages and fuel consumption, which depends on many factors, such as travel distance and vehicle load. Vehicle speeds are additional decision variables of the problem which complement routing decisions. They impact the total cost, the travel times between the locations, and thus the set of feasible routes. We propose a hybrid method that combines a local search-based metaheuristic with an exact approach and a recursive speed-optimization algorithm. Moreover, two other green VRP variants, the Fuel Consumption VRP (FCVRP) and the Energy Minimizing VRP (EMVRP), are addressed. The results obtained compare very favorably with those found in the literature, and many new improved solutions are reported. / Esta dissertação lida com o Pollution-Routing Problem (PRP), i.e. um Problema de Roteamento de Veículos (PRV) com considerações ambientais, recentemente introduzido na literatura por Bekta¸s e Laporte (2011). O objetivo consiste na minimização dos custos operacionais e ambientais, respeitando as restrições de carga dos veículos e janelas de tempo dos clientes. O custo é baseado no salário dos motoristas e no consumo de combustível, que depende de diversos fatores, como distância percorrida e carga transportada. As velocidades dos veículos são variáveis de decisão adicionais que complementam as decisões de roteamento. Tais velocidades interferem diretamente no custo total, nos tempos de viagem, bem como no conjunto de rotas viáveis. Uma abordagem híbrida que combina uma metaheurística baseada em busca local com uma abordagem exata e um algoritmo recursivo para otimizar as velocidades é proposta para solucionar o problema. Além do PRP, outras duas variantes do PRV com considerações ambientais são tratadas: o PRV considerando consumo de combustível e o PRV com minimização de energia. Os resultados obtidos se mostraram bastante favoráveis quando comparados com os melhores da literatura, e diversas soluções melhoradas são reportadas.

O nÃvel de serviÃo de uma empresa atacadista distribuidora pode ser medido pela frequÃncia e regularidade com que sua equipe de vendas atende os clientes. Mas como o sucesso no mercado tambÃm depende dos custos envolvidos, o planejamento adequado das sistemÃticas de atendimento à crÃtico. Aproveitando as similaridades entre essa situaÃÃo e o Problema de RoteirizaÃÃo PeriÃdica de VeÃculos (PRPV), foi proposta uma tÃcnica de resoluÃÃo deste problema. Para o PRPV, dado um horizonte de planejamento composto de vÃrios dias, clientes devem ter suas visitas alocadas aos dias conforme combinaÃÃes possÃveis ao mesmo tempo em que rotas sÃo geradas para cada dia, objetivando a reduÃÃo do custo total de atendimento nesse mesmo horizonte de planejamento. A tÃcnica proposta tambÃm foi adaptada para aplicaÃÃo no caso prÃtico de roteirizaÃÃo de uma equipe de vendas com horizonte de planejamento semanal e consiste em um algoritmo genÃtico para o qual foi desenvolvido um operador de cruzamento original. A tÃcnica foi validada com instÃncias da literatura para o PRPV e suas soluÃÃes para o caso prÃtico indicaram economias anuais significativas. / The service level of a wholesale distributor can be measured by the frequency and regularity with which its sales staff serves customers. But as the market success also depends on the costs involved, the proper planning of systematic servings is critical. Taking advantage of the similarities between this situation and the Periodic Vehicle Routing Problem (PVRP), a technique for solving the later was proposed. For the PVRP, given a planning horizon of several days, visits to customers must be assigned to possible days according to predefined schedule combinations at the same time as routes are generated for each day, aiming to reduce the total cost of serving in the same planning horizon. The proposed technique was also adapted to be applied to the practical case of routing a sales team within a weekly planning horizon and it consists of a genetic algorithm for which was developed an original crossover operator. The technique was validated with instances from the literature for the PVRP and its solutions for the case study indicated significant annual savings.

A presente pesquisa aborda um problema de roteirização e programação de veículos incorporando uma nova restrição operacional: a requisição simultânea de múltiplos veículos para atendimento da demanda. Trata-se de uma característica encontrada em operações de apoio à exploração de petróleo \"offshore\", em que mais de uma embarcação é requerida para executar tarefas de reboque e lançamento de linhas de ancoragem. Esta imposição, somada às restrições de janela de tempo, precedência entre tarefas, autonomia das embarcações e atendimento integral da demanda, configuram este problema. A programação é orientada pela minimização dos custos variáveis da operação e dos custos associados ao nível de serviço no atendimento. Este problema é uma variação do problema clássico de roteirização e programação de veículos com janela de tempo, de classe NP-Difícil. Nesta pesquisa, propõe-se modelar e resolver o problema em escala real por meio do algoritmo \"branch and cut\" acoplado às heurísticas de busca em vizinhança \"local branching\" e \"variable neighborhood search\". Para gerar as soluções iniciais será empregado o método \"feasibility pump\" e uma heurística construtiva. / This research focuses a fleet scheduling problem with new operational constraints: each task requiring multiple types of vehicles simultaneously. This kind of operation occurs in offshore exploitation and production sites, when more than one vessel is needed to accomplish the tugging and mooring of oil platforms. Other constraints are maintained such as time windows, precedence between tasks, route duration and the demand attendance. The solution schedules are cost oriented, which encompasses the routing variable costs and the customer service costs. This is a variation of the classical fleet routing and scheduling, which is an NP-Hard problem. This research aims to solve the real scale problem through a combined use of branch and cut strategy with local search algorithms such as local branching and variable neighborhood search. An efficient heuristic rule will be used in order to generate initial solutions using the feasibility pump method.

Orientador: Fernando José Von Zuben / Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Engenharia Elétrica e de Computação / Made available in DSpace on 2018-08-17T20:59:25Z (GMT). No. of bitstreams: 1 Azuma_ReginaMitsue_M.pdf: 2321816 bytes, checksum: 44c4417bf2a4fad2a8241c7189e4d04a (MD5) Previous issue date: 2011 / Resumo: A classe de problemas de estoque e roteamento está presente em várias áreas, incluindo indústria automobilística e gerência de numerário no reabastecimento de caixas eletrônicos. Supondo que o fornecedor é responsável pela estocagem e distribuição dos produtos, sujeito a um conjunto de restrições, o desafio que se apresenta é a determinação de uma política ótima, mais especificamente quais clientes atender, qual quantidade a ser fornecida a cada cliente e qual rota empregar visando a minimização dos custos. Este trabalho apresenta uma proposta de solução para uma das mais comuns formulações do problema: um produto é distribuído a partir de um fornecedor para vários clientes em um horizonte de tempo definido. O transporte é realizado por um veículo de capacidade limitada. Para produzir a otimização simultânea de ambos os objetivos, minimização dos custos de transporte e estoque, a proposta segue uma abordagem multiobjetivo e se baseia no uso do algoritmo SPEA2 (do inglês, Strength Pareto Evolutionary Algorithm 2), incluindo inovações na representação de soluções-candidatas, nos operadores genéticos e de busca local. A fronteira de Pareto estimada é então composta de múltiplas soluções não-dominadas, representando compromissos distintos entre custos de transporte e estoque. Como casos de estudo, são tomadas instâncias de médio porte extraídas da literatura e são geradas instâncias de grande porte. Para as instâncias de médio porte, as fronteiras de Pareto estimadas em cada caso são comparadas com as respectivas soluções ótimas da versão mono-objetivo de cada problema, pois já existe um algoritmo exato de solução para a formulação mono-objetivo de instâncias de médio porte / Abstract: The class of inventory routing problems (IRP) is present in several areas, including automotive industry and cash management for ATM networks. Given that the supplier is responsible for managing the product inventory and replenishment, subject to a set of restrictions, the challenge here is to determine an optimal policy, more specifically which retailers to serve, the quantity to deliver to each retailer and which routes to employ in order to minimize the cost. This work presents a proposal to solve one version of the IRP usually found in the scientific literature: a product is distributed from a supplier to several retailers in a defined time horizon. Shipment is performed by a vehicle with limited capacity. To perform the simultaneous optimization of both objectives, minimization of transportation and inventory costs, the proposal follows a multi-objective approach based on SPEA2 (Strength Pareto Evolutionary Algorithm 2), including innovative aspects mainly associated with the representation of candidate solutions, genetic operators and local search. The Pareto front is then composed of multiple non-dominated solutions with distinct trade-offs between transportation and inventory costs. As case studies, medium size instances extracted from the literature are considered and large size instances are generated. For the medium size instances, the estimated Pareto fronts are compared, in each case, with the corresponding optimal solutions associated with the single-objective version of each problem, given that there is already an exact algorithm to solve such medium size single-objective instances / Mestrado / Engenharia de Computação / Mestre em Engenharia Elétrica

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

Orientador: Vinicius Amaral Armentano / Tese (doutorado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica e de Computação / Made available in DSpace on 2018-08-08T10:15:19Z (GMT). No. of bitstreams: 1 Araujo_OlintoCesarBasside_D.pdf: 1592360 bytes, checksum: 71dd5f2565cd93013aa027127157c442 (MD5) Previous issue date: 2006 / Resumo: A adoção de contêineres em grande escala tornou possível o desenvolvimento do transporte multimodal. Atualmente, carregamento de caixas em contêineres é uma importante atividade em empresas que têm no transporte de carga um fator logístico de alto custo. Este trabalho apresenta o desenvolvimento e aplicação de metaheurísticas com memória adaptativa para a resolução de problemas de corte e empacotamento tridimensional, bem como a integração destes com o problema de roteamento de veículos. Mais especificamente, são tratados os problemas de carregamento de contêiner, bin packing tridimensional e roteamento de veículos capacitados com restrições de empacotamento tridimensional. Uma nova abordagem, baseada em cubóides de tamanho variável, é utilizada para calcular os padrões de carregamento tridimensional em todos os métodos propostos. Restrições de orientação, estabilidade, centro de gravidade, projeção da base de apoio e múltiplos destinos são consideradas. Extensivos testes computacionais são realizados para demonstrar o desempenho das abordagenspropostas / Abstract: The wide-scale adoption of the containers made the development of the multimodal transport possible. Nowadays, shipment of boxes in containers is an important activity for companies that have in the load transport a logistic factor of high cost. This work presents the development and the application of metaheuristics with adaptive memory in order to solve three-dimensional cutting and packing problems, as well as their integration with the vehicle routing problem. In particular, problems of container loading, three-dimensional bin packing and vehicle routing with three-dimensional packing constraints are considered. Furthermore, a new approach based on maximal cuboids that fit in given empty spaces is used to calculate the packing patterns in the proposed methods. Constrains on orientation, stability, center of gravity, overhang and multiple destination are considered. Extensive computational experiments are carried out to demonstrate the performance of the proposed approaches / Doutorado / Automação / Doutor em Engenharia Elétrica