Planeamento integrado da logística de inbound e outbound

FACULDADE DE ENGENHARIA DA UNIVERSIDADE DO PORTO Planeamento integrado da logística de inbound e outbound Rúben Gonçalo Pereira Brito Mestrado Integrado em Engenharia Eletrotécnica e de Computadores Orientador: Professor Doutor Jorge Pinho de Sousa Orientador Externo: Professora Doutora Alexandra Sofia da Fonseca Marques 22 de julho de 2016 c Rúben Brito, 2016 Resumo A otimização dos processos na prestação de serviços é, no ambiente competitivo que as empresas enfrentam, decisiva para o seu desempenho. Em particular, o planeamento da distribuição de produtos a partir das fábricas, com vista a uma redução dos custos, pode ser extremamente complexo e envolver vários clientes a visitar em cada dia, encomendas variáveis, múltiplas fábricas, frotas diversificadas, e um conjunto de restrições temporais. A presente dissertação trata de um problema de planeamento integrado da logística de inbound eoutbound, nas fábricas de uma empresa de derivados da madeira com expressão ibérica. Este problema consiste em determinar as rotas diárias que minimizam os custos de transportes associados às entregas de produtos aos clientes e, sempre que possível, ao retorno às fábricas com o transporte de matéria-prima. Trata-se, portanto, de um problema de planeamento de rotas de veículos, com janelas temporais, viagens de retorno com matéria-prima e múltiplos armazéns [Multiple Depot Vehicle Routing Problem with Backhauls and Time Windows (MDVRPTW)]. Numa primeira fase deste trabalho, foi desenvolvido um modelo integrado, de programação matemática, mas, dado o baixo desempenho computacional deste modelo, foi desenvolvido um novo algoritmo, resultado da decomposição do modelo anterior. Este método de resolução permitiu resolver instâncias de maior dimensão, tendo sido testado com um problema de uma semana de planeamento. Este problema foi inspirado no problema real, tendo por isso características idênticas (com valores semelhantes para a procura média, janelas temporais e distribuição da procura). Os resultados obtidos foram comparados positivamente com a situação atual, considerando as regras empíricas de planeamento atualmente em vigor na empresa. Finalmente, foram realizados alguns melhoramentos no método de decomposição, o que resultou num método iterativo que procura, em cada iteração, ajustar o parâmetro que determina a escolha de um fornecedor em cada rota. Os resultados mostram que a estratégia proposta conduz, no caso da semana representativa do caso de estudo, a melhorias significativas do planeamento da logística de inbound-oubound, com uma redução significativa dos custos de transporte e um aumento das receitas. No futuro, deverão ser desenvolvidas melhorias adicionais no método de resolução, com vista a reduzir os tempos de computação e permitir a resolução de problemas de maior dimensão. A integração do modelo desenvolvido num software de apoio à decisão, que permita, no dia-a-dia da empresa, uma forma de interação dos planeadores com o sistema, é também um desenvolvimento futuro natural. Palavras chave: planeamento da distribuição, logística, otimização, planeamento de rotas de transporte, programação matemática, backhauling,time windows, MDVRPBTW i ii Abstract The optimization of processes in the provision of services is in the competitive environment that companies face, decisive for its performance. In particular, the planning of the distribution of products from the factories with a view to reducing costs, can be extremely complex and involve multiple clients to visit each day, variable orders, multiple factories, diversified fleets, and a set of time constraints. This dissertation covers an integrated planning problem of inbound-outbound logistics, in factories of a wood-based company with Iberian expression. This problem is to determine the daily routes that minimize transport costs associated with the delivery of products to customers and, whenever possible, to return to the factory with transportation of raw materials. This is therefore a Multiple Depot Vehicle Routing Problem with Time Windows and backhaul (MDVRPTW). In the first phase of this work, an integrated model was developed based on mathematical programming. But given the low computing performance of this model, a new algorithm was developed, the result of the decomposition of the previous model. This resolution method has solved bigger instances, having been tested with a problem of planning a week. This problem was inspired by the real problem and therefore have identical characteristics (similar values for average demand, time windows and distribution of demand). The results were compared with the current situation, considering the empirical planning rules currently in force in the company. Finally, some improvements have been made in the decomposition method, resulting in an iterative method that seeks, at each iteration, to set the parameter that determines the choice of a supplier in each route. The results show that the proposed strategy exhibits significant improvements on the planning of inbound-outbound logistics, with a significant reduction in transport costs and increase in revenue. In the future, further improvements should be developed in the resolution method, to reduce the computing time and allow for solving of bigger problems. The integration of the model developed with a decision support system which allows, in day-to-day business, a form of interaction of the planners with the system, is also a natural future development. Keywords: distribution planning, logistics, optimization, planning transport routes, mathematical programming, backhauling, time windows, MDVRPBTW iii iv Agradecimentos Em primeiro lugar, devo começar por agradecer a um conjunto de elementos do INESC TEC - Instituto de Engenharia de Sistemas e Computadores, Tecnologia e Ciência, que incondicionalmente me apoiaram na realização da dissertação: Bruno Oliveira por toda a ajuda inicial na formulação e compreensão do problema; Samuel Carvalho por todo o tempo perdido comigo e conselhos dados na tarefa de desenho das rotas; ao Doutor Pedro Amorim, pela colaboração, interesse e contribuições no projeto, das quais resultou uma melhoria significativa do método de resolução; ao meu orientador, Doutor Jorge Pinho de Sousa por toda a ajuda e conhecimento partilhado ao longo do projeto; por último, à minha prestável co-orientadora, a Doutora Alexandra Marques por ter tido um papel determinante no sucesso do projeto, assim como por ter conseguido despender um pouco do seu preenchido tempo, para efetuar as reuniões semanais e assim conseguir manter o ritmo adequado do trabalho. Tenho ainda que agradecer aos meus pais por estarem sempre do meu lado e me oferecerem as condições ideais para alcançar este objetivo. À minha mana Sara Brito, por todo o apoio e compreensão que teve comigo, especialmente nalguns momentos mais complicados destes 5 meses de trabalho na dissertação. Por fim, tenho que acabar por agradecer a um grupo de amigos mais próximos que me ajudaram nestes últimos tempos: ao “grande” Morais, ao verdadeiro “Bru”, à Renata e à fantástica Cris-tina. Obviamente não posso esquecer todos os outros amigos que, de uma maneira ou outra, contribuíram para chegar até aqui. Rúben Brito v vi “The best preparation for tomorrow is doing your best today.” H. Jackson Brown, Jr. vii xiv LISTA DE TABELAS 7.2 Dados relativos aos pontos considerados na instância apresentada . . . . . . . . . 80 7.3 Resultados obtidos para a instância de teste com o modelo monolítico . . . . . . 81 7.4 Resultados obtidos para a instância de teste com a abordagem iterativa . . . . . . 82 7.5 Resultados obtidos com o método iterativo para a semana representativa . . . . . 84 Abreviaturas e Símbolos ACO Ant Colony Optimization ARP Arc Routing Problems CARP Capacitated Arc Routing Problems CVRP Capacitated Vehicle Routing Problem DVRP Dynamic Vehicle Routing Problem EC Evolutionary Computation GRASP Greedy Randomized Adaptive Search Procedure HVRP Heterogeneous Fleet Vehicle Routing Problem ILS Iterated Local Search IMP Papéis impregnados MDF Painéis de fibra de média densidade MDVRP Multiple Depot Vehicle Routing Problem MFC Painéis revestidos a melamina NRP Node Routing Problems OLS Oscillating Local Search PB Painéis de aglomerado de partículas SA Simulated Annealing SVRP Stochastic Vehicle Routing Problem TS Tabu Search VFB MDF e PB revestidos com folha de madeira VNS Variable Neighborhood Search VRP Vehicle Routing Problem VRPB Vehicle Routing Problem with Backhauls VRPBTW Vehicle Routing Problem with Backhauls and Time Windows VRPPD Vehicle Routing Problem with Pickups and Deliveries VRPSD Vehicle Routing Problem with Split Deliveries VRPTW Vehicle Routing Problem with Time Windows xv Capítulo 1 Introdução 1.1 Enquadramento O planeamento da distribuição de produtos das fábricas para os clientes é um problema complexo. Existem vários clientes a visitar em cada dia, com encomendas variáveis, várias fábricas e uma frota diversificada de veículos com capacidade de transporte limitada. Diariamente, vários responsáveis pelos transportes fazem o planeamento regional, tendo como objetivo definir o número mínimo de camiões a utilizar bem como determinar a melhor sequência de clientes a visitar por cada veículo (rota) de forma a minimizar os custos de transporte. Esta dissertação foca o caso particular do planeamento dos transportes de produtos derivados da madeira, na perspetiva de uma grande empresa, que detém fábricas em toda a Península Ibérica. Na situação atual, o planeamento é realizado de forma independente para cada fábrica. O dimensionamento da frota e respetivas rotas de entrega de produtos aos clientes (rotas de outbound) é feito de forma manual sem recurso a ferramentas de apoio à decisão. Na indústria dos derivados da madeira, um outro aspeto muito importante é o transporte de matéria-prima para as fábricas (rotas de inbound). As rotas de inbound representam uma parte significativa dos custos totais de aquisição destes materiais e tem por isso um grande impacto na eficiência de toda a cadeia de abastecimento. O planeamento destas rotas é feito de forma desintegrada do planeamento de rotas de outbound, embora muitas das vezes seja possível que o camião responsável pelas entregas das encomendas aos clientes, transporte matéria-prima no seu retorno à fábrica. A inexistência de um planeamento integrado e eficaz da logística de inbound-outbound ao nível ibérico poderá por isso, ser responsável pelo insucesso de uma empresa. Modelos e métodos de investigação operacional têm vindo a ser desenvolvidos em todo o mundo para melhorar o planeamento dos transportes e servir de suporte às tomadas de decisão a curto e médio prazo. Conforme se irá discutir em detalhe no capítulo da revisão bibliográfica, estas abordagens dependem do contexto da aplicação, de tal forma que se podem focar apenas nas decisões de logística de inbound, somente na logística de outbound, ou abranger toda a cadeia de 1 2Introdução abastecimento. Note-se que, o planeamento integrado da logística de inbound eoutbound é ainda pouco estudado, em especial na indústria de produtos derivados da madeira. 1.2 Objetivos e Motivação Esta dissertação tem como objetivo aplicar técnicas de investigação operacional para o planeamento integrado da logística de inbound eoutbound nas fábricas da empresa de derivados de madeira, com expressão ibérica. Em particular, será desenvolvido um modelo matemático para definir as rotas diárias de inbound-outbound, que minimizam os custos de transportes associados às entregas de produtos aos clientes e, sempre que possível, à recolha de matéria-prima no retorno às fábricas. Trata-se, portanto, de um modelo para o problema de planeamento de rotas de veículos (VRP) com determinadas particularidades: janelas temporais, viagens de retorno com matéria prima e múltiplos armazéns. Esta dissertação irá também desenvolver um método de resolução adequado a este problema. Todo este projeto é muito desafiante, uma vez que as particularidades do negócio e o contexto real do problema conduzem a um modelo inovador, diferente do que existe publicado na literatura. Adicionalmente, a abordagem proposta tem o potencial de vir a reduzir os custos de transporte e posicionar a empresa numa maior orientação do serviço ao cliente, resultando daí um potencial ganho da sua vantagem competitiva. 1.3 Estrutura da Dissertação Os capítulos seguintes desta dissertação detalham o trabalho realizado e os resultados obtidos. No capítulo 2 é realizada uma revisão bibliográfica de vários temas de interesse para a realização da dissertação, tal como, descrição do planeamento de rotas de veículos (VRP), variantes do VRP e os vários tipos de estratégias para resolução deste tipo de problemas. No capítulo 3 é apresentada uma caracterização pormenorizada do problema, incluindo a exposição de um exemplo ilustrativo, bem como uma solução admissível do mesmo. No capítulo 4 é efetuada uma descrição detalhada da primeira metodologia seguida para resolução do problema, assim como demonstrada a implementação e resolução de uma instância do problema de pequena dimensão (por exemplo, número reduzido de clientes, fornecedores e veículos). No capítulo 5 é apresentado um novo método de resolução com capacidade de encontrar soluções para instâncias maiores, mais próximas da realidade, que permitam retirar conclusões acerca da melhor estratégia de planeamento para a empresa. No capítulo 6 é demonstrada a aplicação do método ao caso de estudo. É apresentada a geração de um conjunto de instâncias que constituem uma semana representativa do problema. Posteriormente, são analisadas as vantagens da abordagem proposta, face ao que é atualmente posto em prática pela empresa. 1.3 Estrutura da Dissertação 3 No capítulo 7 é apresentada uma extensão do método que pretende aproximar os resultados obtidos à solução ótima. É demonstrada a aplicação da extensão do método de resolução numa pequena instância, assim como identificadas as melhorias nas soluções obtidas. O capítulo termina com a exposição dos resultados obtidos para a semana representativa criada, utilizando a extensão proposta. Por fim, no capítulo 8, são apresentadas as conclusões de todo o trabalho efetuado, assim como referenciado trabalho futuro, passível de ser executado no âmbito da presente dissertação. 4Introdução Capítulo 2 Revisão Bibliográfica Este capítulo apresenta os resultados da análise da literatura sobre o Vehicle Routing Problem. Foram analisados 38 artigos científicos, publicados em jornais científicos internacionais, 4 livros de interesse para este tema e ainda 1 dissertação de doutoramento. O estudo focou-se na descrição geral do VRP, formulação e métodos de resolução. Foram também analisadas as principais variantes do VRP com semelhanças com o problema estudado, nomeadamente o Capacitated Vehicle Routing Problem,Multiple Depot Vehicle Routing Problem,Vehicle Routing Problem with Time Windows eVehicle Routing Problem with Backahuls. 2.1 Vehicle Routing Problem: características e modelos OVehicle Routing Problem é um dos problemas de otimização combinatória mais estudados em todo o mundo. O problema foi inicialmente formulado por Dantzig e Ramser [3]. Conhecemse atualmente inúmeros exemplos da sua aplicação em casos reais da logística, distribuição e transporte [4] em diversos sectores de atividade como na distribuição e recolha de produtos florestais [5], entregas de encomendas [6], transporte de pessoas [7], recolha de lixo [8], entre muitos outros casos. Os problemas de determinação de rotas ótimas podem ser classificados em dois grandes grupos: problemas com procura nos vértices (Node Routing Problems – NRP) e problemas com procura nos arcos (Arc Routing Problems – ARP). Os problemas de procura nos arcos são por exemplo, situações de recolha de lixo em meio urbano, uma vez que a densidade de locais a visitar ao longo das ruas é suficientemente elevada para considerar os arcos (ruas) elementos chave da rede a ser servida. O VRP é considerado um problema com procura nos vértices, uma vez que os clientes são os vértices do grafo e é lá que está localizada a procura. 2.1.1 Rotas e rede de distribuição De uma forma geral, o VRP pretende encontrar rotas de custo mínimo para entregas ou recolhas de produtos ao longo da rede de distribuição, para um ou mais veículos. Desta forma, a 5 6Revisão Bibliográfica rede de distribuição assume um papel importante para o suporte da resolução de um problema de planeamento de rotas e é composta pelos seguintes elementos: •Vértice ou nós de origem (fábrica) onde existe disponibilidade de produto. •Vértice ou nós de destino (clientes ou fornecedores) onde existe procura do produto ou disponibilidade de matéria-prima (no caso dos fornecedores). •Arede de estradas normalmente representada pelos arcos de um grafo. Associado aos arcos do problema existe um custo que depende da distância real que o mesmo representa e ainda um tempo necessário para o percorrer. •Depósito ou vértice de início e de fim de uma rota. Tem associado a si um ou mais veículos que podem ser de diferentes tipos, assim como uma capacidade limitada para armazenamento de bens. Estes locais existem em problemas especiais onde são considerados locais específicos para estacionar os veículos, tais como sede de empresas de transportes, casa dos condutores, entre outros. No caso de problemas que não considerem este tipo de locais, as rotas têm início no vértice de origem. Os veículos são elementos com capacidade de realizar o transporte de bens a partir de uma origem até um destino, e naturalmente têm associadas algumas limitações relativas ao tipo e quantidade de carga transportada. Não se pode descurar o facto de um veículo estar associado a um condutor que tem limitado o número de horas de condução. Neste sentido, o veículo terá limitada a distância que pode percorrer, através do limite temporal imposto ao seu condutor. No caso do VRP tradicional, todas as rotas têm como ponto de partida um vértice de origem – fábrica - onde existe disponibilidade de produto, com posteriores passagens por um conjunto de nós de destino – clientes ou fornecedores – onde existe procura do produto ou oferta de matéria-prima, distribuídos numa certa zona geográfica. No final de executadas todas as entregas ou recolhas, o regresso do veículo ao vértice de origem é obrigatório. Numa abordagem clássica, as rotas têm todas o mesmo ponto de partida e a distribuição é realizada por uma frota com um número fixo de veículos. No entanto, existem múltiplas variantes do VRP decorrentes de casos de aplicação reais, que consideram por exemplo a existência de vários vértices de origem [Multiple Depot Vehicle Routing Problem (MDVRP)], janelas temporais para efetuar carregamentos dos produtos nas fábricas [Vehicle Routing Problem with Time Windows (VRPTW)], possibilidades de efetuar backhauls [Vehicle Routing Problem with Backhauls (VRPB)] e muitas outras. As questões associadas às restrições do problema serão revistas em pormenor na secção 2.1.4. 2.1.2 Variáveis de decisão As varáveis de decisão para o problema de planeamento de rotas de veículos dependem das restrições consideradas e de futuras abordagens pensadas para serem usadas como método de resolução. Num VRP “clássico” a variável de decisão mais utilizada indica se o veículo kvisita o cliente japós visitar o cliente i, geralmente representada por xi jk. No entanto, diferentes abordagens 2.1 Vehicle Routing Problem: características e modelos 7 ao problema ou modificações de algumas das restrições, fazem com que as variáveis de decisão sejam modificadas. Exemplo disso, é o caso retratado em [9], onde o problema é solucionado por uma abordagem iterativa, em que a principal variável de decisão é diferente da apresentada. Neste caso, como numa primeira fase é feito o agrupamento de clientes e só depois definida a rota pelo caminho mínimo, foi considerada a variável xk ique indica se a rota kvisita o vértice de destino i. Como a maioria das variantes do VRP considera restrições adicionais, são acrescentadas variáveis auxiliares, de forma a conseguir respeitar-se as novas restrições impostas. No caso do VRPTW, é muitas vezes criada uma variável suplementar ou acrescentado um parâmetro a xi jk, que permite controlar o horário em que o veículo kpode sair do armazém, efetuar uma visita a um cliente ou limitar a duração máxima da rota [10]. 2.1.3 Função objetivo De um modo geral, a função objetivo do VRP consiste em minimizar os custos totais da distribuição, incluindo os custos fixos e os variáveis. Os custos fixos são constituídos maioritariamente pelo custo de compra e manutenção de uma frota de veículos, por exemplo o imposto, seguro e revisão do veículo. Os custos variáveis variam de acordo com serviços realizados, e de um modo geral podem ser considerados diretamente proporcionais à distância percorrida. Outros objetivos frequentes na literatura incluem a minimização do número total de rotas, da distância total percorrida ou da duração das rotas. Tal como no caso do problema abordado em [9] e estudado neste trabalho, muitos problemas requerem que se considere mais que um objetivo em simultâneo, de tal forma que são geradas funções objetivo, em que dois ou mais termos são combinados. Nestes casos, é necessário atribuir pesos relativos a cada um dos objetivos, de forma a encontrar uma solução que vá de encontro aos interesses dos decisores [11]. 2.1.4 Restrições 2.1.4.1 Restrições associadas aos veículos As características dos veículos condicionam a forma como é efetuada uma abordagem ao problema. As principais restrições relacionadas com o tipo de veículos a utilizar, prende-se com o limite de capacidade quer em peso, volume ou número de artigos. A este tipo de problemas deu-se o nome de Capacitated Vehicle Routing Problem (CVRP) [12], variante apresentada na secção 2.2.1. Outras restrições associadas aos veículos incluem tipo de carga que têm aptidão para transportar, condições necessárias para efetuar cargas e descargas, número e tipos de veículos disponíveis (frota heterogénea ou homogénea) e ainda a possibilidade de transporte de múltiplos tipos de carga, com recurso à subdivisão do veículo em compartimentos. Associado a um veículo existe normalmente um condutor que terá limitado o número de horas consecutivas de condução, assim como definida a duração dos intervalos durante o serviço. Desta forma, o veículo poderá ter limitado a distância que pode percorrer, através do limite temporal imposto ao seu condutor. 14 Revisão Bibliográfica mantêm e melhoram várias soluções em simultâneo. Como exemplo de métodos baseados em populações tem-se as meta-heurísticas Ant Colony Optimization (ACO) e Evolutionary Computation (EC). As meta-heurísticas individuais ou de trajetória (trajectory methods) focam-se exclusivamente em modificar e melhorar uma única solução, isto é, visam encontrar uma solução individual. São classificadas como meta-heurísticas de trajetória, os seguintes exemplos: Simulated Annealing (SA), Tabu Search (TS), Greedy Randomized Adaptive Search Procedure (GRASP), Iterated Local Search (ILS) e Variable Neighborhood Search (VNS). A crescente exploração de meta-heurísticas para resolução de complexos problemas derivados do VRP, permite identificar na literatura diversas abordagens de resolução. Para resolução do VRPBTW, é apresentado em [42] um algoritmo Tabu Search. Em [43] foi apresentada uma metodologia de resolução de duas fases para o VRPB. Num primeiro momento é gerada uma solução inicial através de duas heurísticas construtivas e, posteriormente, a solução é melhorada com recurso a uma extensão do Tabu Search (reactive TS). Outro algoritmo baseado no TS foi proposto em [44]. O algoritmo proposto resulta da integração de TS com Adaptive Memory Programming, de modo a conduzir a pesquisa para regiões não exploradas. Em [45] foi apresentado também um algoritmo TS para melhorar uma solução inicial previamente criada a partir de duas diferentes metodologias. Em [46] foi proposta uma Ant Colony que faz uso de dois esquemas de busca local. Em [17] foi proposto uma Iterated Local Search (ILS) com capacidade de resolver problemas de planeamento de rotas de veículos com fornecedores. Através da introdução de uma técnica heurística de Oscillating Local Search (OLS), o algoritmo permite oscilar entre soluções possíveis e impossíveis. A simplicidade associada a este algoritmo, assim como os resultados obtidos em termos de tempo e custos das soluções, fazem deste método bastante competitivo em relação a outras técnicas descritas na literatura (por exemplo, [45], [44], [46], [16]). Em [10] foi apresentada uma meta-heurística híbrida para resolução do VRPBTW, que integra o Simulated Annealing e o Tabu Search, conseguindo obter na maioria das instâncias testadas os melhores resultados conhecidos, assim como um tempo computacional competitivo em relação a outras técnicas heurísticas. 2.3.2.3 Análise dos métodos de resolução Em situações reais, os problemas de planeamento de rotas tendem a considerar diversas situações (por exemplo, janelas temporais, múltiplos fábricas, fornecedores, entregas fracionadas, entre outras) e, por isso, tornam-se bastante complexos. Normalmente, quando a empresa procura um sistema de apoio à decisão para planeamento de rotas, verifica-se que a dimensão dos problemas a resolver é elevada. Consequentemente, estes dois fatores dificultam a utilização de um método de resolução exato, uma vez que seria necessário um tempo computacional muito elevado, isto é, um tempo em que não permita à empresa efetuar um planeamento atempado ou efetuar reajustes dos resultados obtidos. Note-se que, o tempo de resolução de um problema da classe NP-difícil cresce exponencialmente com o aumento da sua dimensão, pelo que, mesmo com o aumento da capacidade de processamento dos computadores, torna-se, por vezes, complicada a utilização de métodos exatos para a resolução de um problema de grande dimensão. No entanto, existem situações nas quais 2.4 Enquadramento do problema em estudo no referencial VRP 15 a dimensão reduzida e simplificações do problema real, permitem utilizar técnicas exatas para a resolução de um problema de planeamento de rotas. É interessante perceber que a dimensão dos problemas solucionados por métodos exatos tem vindo a aumentar, devido aos melhoramentos feitos, quer nas formulações matemáticas dos problemas, quer ao nível das capacidades dos solvers. 2.4 Enquadramento do problema em estudo no referencial VRP Na secção 2.2 da presente dissertação foram apresentadas as variantes do VRP, que seriam importantes conhecer face ao problema em estudo neste projeto. No entanto, são descritas na literatura muitas outras extensões ao problema do planeamento de rotas, como por exemplo: Heterogeneous Fleet VRP (HVRP), variante que considera uma frota heterogénea de veículos que podem possuir capacidades de carga e custos diferentes; VRP with Split Deliveries (VRPSD), onde é relaxada a restrição que obriga os clientes a serem visitados uma única vez, permitindo assim, em situações onde a procura dos clientes é próxima ou superior à capacidade do veículo, efetuar a entrega da encomenda divida por diversos veículos; Stochastic VRP (SVRP), onde um ou mais elementos do problema de planeamento de rotas têm natureza não determinística; Dynamic VRP (DVRP), na qual os parâmetros e a dimensão do problema sofrem alterações em tempo real; VRP with Pickups and Deliveries (VRPPD) onde existe a possibilidade de recolher bens nos clientes, ao mesmo tempo que se entrega produtos nesses locais; entre muitas outras que se ajustam a situações de casos reais. Uma comparação entre a caracterização do problema presente no capítulo 3 e a classificação das diversas variantes do VRP apresentadas na Tabela 2.1 permite verificar que o problema em estudo nesta dissertação tem grandes semelhanças com 3 das variantes do VRP, nomeadamente: MDVRP, VRPB e VRPTW. Pode-se por isso designar-se por MDVRPBTW (Multiple Depot Vehicle Routing Problem with Backhauls and Time Windows). Apesar de individualmente as extensões serem muito conhecidas e constantemente exploradas em casos de estudo, não foi possível encontrar nenhuma referência na literatura que trate em simultâneo as três variantes. No entanto, são tratados muitas vezes problemas que agrupam pelo menos duas das três variantes. Exemplo disso é o trabalho desenvolvido em [10] e em [47], onde é apresentada uma formulação matemática do problema de planeamento de rotas com backhauls e janelas temporais (VRPBTW), assim como os respetivos métodos de resolução. Já em [14] é apresentada uma formulação de um MDVRP que considera situações interessantes para o problema a modelar nesta dissertação (por exemplo, limite temporal de trabalho do veículo, nó de início e fim das rotas poderá não ser o mesmo - flexible assignment). 16 Revisão Bibliográfica CVRP HVRP MDVRP VRPTW VRPB VRPPD VRPSD SVRP DVRP Node vértices de origem Unitário 3 3 3 3 3 3 3 3 Múltiplos 3 Tipo de Procura Determinística 3 3 3 3 3 3 3 3 Estocástica 3 3 Restrições Capacidade do veículo limitada 3 3 3 3 3 3 3 3 3 Janelas temporais 3 Node entregas a clientes por rota Unitária 3 3 3 3 3 3 3 3 Múltiplas 3 Variáveis de decisão Rotas de entrega 3 3 3 3 3 3 3 3 3 Quantidade a entregar a cliente 3 Fornecedor a visitar numa rota 3 Tipo de Frota Homogénea e Limitada 3 3 3 3 3 3 3 3 Heterogénea e Limitada 3 Tabela 2.1: Classificação das principais variantes do VRP com interesse no projeto Legenda: CVRP: Capacitated VRP; HVRP: Heterogenous VRP; MDVRP: Multiple Depot VRP; VRPTW: VRP with Time Windows;VRPB: VRP with backhauls; VRPPD: VRP with Pickups and Deliveries; VRPSD: VRP with Split Deliveries; SVRP: Stochastic VRP; DVRP: Dynamic VRP; Capítulo 3 Caso de estudo Neste capítulo é efetuada uma caracterização pormenorizada do caso de estudo. São apresentados os elementos e as condições necessários à compreensão do problema, assim como representado um exemplo ilustrativo e a respetiva solução admissível. 3.1 Descrição geral do problema O problema em estudo na dissertação visa a integração da logística de outbound einbound no caso da distribuição de produtos e recolha de matéria-prima de uma empresa de grande dimensão no setor dos produtos derivados da madeira, detentora de inúmeras fábricas localizadas na Península Ibérica. Dado um grupo de fábricas, um grupo de clientes com determinada necessidade de produtos que deve ser satisfeita num certo dia, um grupo de fornecedores que podem ter disponível matériaprima necessária nas fábricas, o problema consiste em encontrar um conjunto de rotas constituídas por um conjunto de entregas de produtos derivados da madeira (outbound) e um possível retorno de matéria-prima para uma das fábricas (operações de backhauling, ou inbound). A construção das rotas é feita de forma a minimizar a distância total percorrida para servir todos os clientes, bem como o uso eficiente da frota através da realização de backhauling. É importante notar que os veículos nunca poderão transportar maior quantidade de produtos do que a sua capacidade, pelo que a carga total associada às entregas aos clientes e a quantidade de matéria-prima recolhida no fornecedor não poderá exceder, separadamente, a capacidade do veículo. Na situação atual, responsáveis pelos transportes em cada fábrica fazem o planeamento das rotas a realizar para cada período de planeamento, assim como avaliam o número necessário de veículos para a realização das respetivas rotas. A atribuição de rotas aos veículos é realizada de forma a que o tempo necessário para as completar, nunca ultrapasse o tempo máximo de trabalho do condutor do veículo. Desta forma, o processo de desenho das rotas e atribuição das mesmas a um determinado veículo é da inteira responsabilidade dos planeadores internos, localizados em cada fábrica. O serviço de transporte (incluindo o veículo e condutor) é contratualizado a empresas especializadas, na base de pagamento-por-serviço. 17 18 Caso de estudo Apesar do planeamento de rotas dos veículos ser feito diariamente, a distribuição dos clientes a um determinado dia é realizada semanalmente. Desta forma, no início de cada semana é estabelecido um plano que contém as encomendas que deverão ser satisfeitas em cada dia da mesma e a respetiva fábrica fornecedora de produtos. Consequentemente, este conjunto de informação (clientes, necessidades e fábrica fornecedora) serve de input para o planeamento diário em cada uma das fábricas. O facto de neste setor existir um grande desperdício em rework e a capacidade de armazenamento (stock) de produto acabado ser muito reduzida, justifica que seja adotado o principio de que tudo o que é produzido num dia, seja expedito nesse mesmo momento. Em suma, o problema pode ser definido nos seguintes pontos: •rotas iniciam e terminam numa fábrica, não necessariamente a mesma; •rotas planeadas diariamente de acordo com distribuição de clientes executados no inicio de cada semana; •as rotas outbound podem incluir a visita de 1, 2 ou mais clientes; •todas as encomendas devem ser satisfeitas (entenda-se por encomenda, um conjunto de produtos desejados por cliente); •cada cliente é visitado uma e uma só vez num período de planeamento (dia); •todas as combinações de entregas são possíveis; •rotas podem incluir a visita de um backhaul depois de visitados todos os clientes, isto é, após entrega de todas as encomendas (note-se que não existem rotas apenas com backhauls); •existe um número máximo de locais (clientes e fornecedores) que uma rota pode visitar, limitado pela capacidade do camião e pelo seu tempo de trabalho disponível durante o dia; •a disponibilidade de matéria-prima nos fornecedores é limitada e traduz-se, por isso num número máximo de visitas que poderão ser feitas a cada fornecedor, num determinado período de planeamento; •a frota de veículos utilizada para a operação de distribuição é considerada homogénea e com um número limitado de veículos com capacidade aproximada de 24 toneladas; •não é necessário considerar janelas temporais para os clientes, contudo no caso das fábricas e dos armazéns dos fornecedores é necessário respeitar os seus horários de funcionamento; •cada par veículo/condutor tem um limite máximo de horas de trabalho e em momento algum, a duração da rota atribuída a um veículo poderá ser superior ao alcance temporal do mesmo (entenda-se por duração da rota, o tempo de carregamento na fábrica, tempo de viagens entres clientes e fornecedor, o tempo de serviço em cada um desses locais, bem como o tempo necessário para regressar a uma fábrica). 3.2 Exemplo ilustrativo 19 3.2 Exemplo ilustrativo Na Figura 3.1 está representado um exemplo de uma solução admissível para um pequeno problema que segue as condições descritas na secção anterior. O problema esquematizado considera apenas duas fábricas, dois fornecedores (B1eB2), cinco clientes (A,B,C,DeE) e um total de três veículos disponíveis com capacidade de 24 toneladas. As linhas contínuas representam viagens onde o camião leva produtos ou matéria-prima e as linhas tracejadas situações onde o camião está completamente vazio. Já as cores associadas às linhas, representam as três diferentes rotas necessárias a percorrer para satisfazer a necessidade de todos os clientes. Figura 3.1: Solução admissível para um pequeno problema idêntico ao apresentado Na Tabela 3.1 são apresentados os dados relativos aos pontos presentes na instância utilizada como exemplo ilustrativo. Local Máximo de visitas Fábrica alocada Procura Fábrica 1 - - - Fábrica 2 - - - A - 1 20 B - 1 2 C - 1 2 D - 2 24 E - 2 22 S1 2 - - S2 2 - - Tabela 3.1: Dados relativos aos vértices considerados na instância apresentada 20 Caso de estudo Foi determinada como solução admissível para a instância apresentada um planeamento constituído por um total de três rotas. A rota R1satisfaz os clientes A,BeC, com a posterior visita do fornecedor B1e tem duração de 6 horas. A rota R2inclui visitas ao cliente De ao fornecedor B1, sendo necessárias 5 horas para a sua realização. Por fim, a terceira rota (R3) tem duração de 4 horas e passa pelo cliente Ee ainda pelo fornecedor B2. Note-se que, a duração das rotas é resultado das distâncias entre locais visitados e ainda pelo tempo de serviço em cada um desses lugares. Dado a duração das três rotas, é possível concluir que vai ser necessário utilizar os três veículos disponíveis, uma vez que não existe nenhuma combinação de duas rotas em que a duração total das mesmas seja inferior ao limite temporal do veículo (8 horas). 3.3 Caracterização do caso de estudo 3.3.1 Fábricas O estudo engloba as 4 fábricas da empresa localizadas na Península Ibérica. No total, as fábricas produzem 6 tipos de produtos derivados da madeira, incluindo: painéis de aglomerado de partículas (PB), painéis de fibra de média densidade (MDF), MDF e PB revestidos com folha de madeira (VFB), painéis revestidos a melamina (MFC) e papéis impregnados (IMP). Cada fábrica pode produzir um ou mais produtos apresentados e é nestes locais que os camiões irão proceder ao carregamento da mercadoria a ser entregue aos clientes, havendo necessidade de respeitar os horários de funcionamento das mesmas, o que neste problema em específico corresponde à janela temporal entre as 7 e 21 horas. 3.3.2 Clientes No problema em questão, o conjunto das fábricas da Península Ibérica necessita de dar resposta em média a 132 encomendas diárias para 57 clientes, o que se traduz num total de 3354 toneladas de produtos diversos a entregar por dia. Deste modo, os responsáveis pelo planeamento da logística, presentes em cada fábrica, terão de definir diariamente as rotas de entregas de aproximadamente 800 toneladas de produtos [9]. Neste caso, os clientes dão total liberdade aos condutores dos veículos, no que diz respeito ao momento em que se procede a entrega dos produtos. 3.3.3 Fornecedores Os fornecedores são os elementos que têm a seu dispor uma disponibilidade limitada de vários tipos de matéria-prima necessária para fabricar os produtos anteriormente referidos na secção 3.3.1. Depois de todas as entregas executadas, o veículo poderá deslocar-se até um fornecedor com objetivo de recolher matéria-prima e proceder ao seu transporte até uma fábrica (operação de backhauling). Deste modo, é assim possível aumentar a rentabilização do serviço de transporte contratado para entrega de produtos aos clientes. 3.4 Simplificações consideradas 21 A empresa tem à sua disposição cerca de 88 potenciais fornecedores que têm em média 36933 toneladas de produto bruto disponíveis por semana, garantido assim que as fábricas não têm falta de matéria-prima [9]. As visitas aos fornecedores por parte dos camiões terão que ser realizadas no horário do funcionamento dos mesmos, isto é, numa janela temporal entre as 7 horas e as 18 horas. 3.3.4 Veículos Neste tipo de problema, os veículos a serem utilizados terão de possuir características que permitam efetuar o transporte de produtos para os clientes, assim como recolher matéria-prima na fase final da rota. Desta forma, o grupo detentor das fábricas faz a terceirização deste serviço a uma empresa especializada, podendo contar com uma frota homogénea de 141 camiões com reboques de lona reforçada [9]. Esta particularidade permite o camião transportar os painéis para os clientes e também as lascas de madeira (matéria-prima) sem necessitar de efetuar grandes alterações na sua estrutura. Outra característica que condiciona o problema está relacionada com o facto de os camiões terem uma capacidade limitada a 24 toneladas. Normalmente o camião efetua uma entrega, o que corresponde à satisfação da necessidade de um só cliente. Isto acontece, uma vez que, a procura dos clientes é, na maioria das vezes, próxima da capacidade do veículo. No entanto, poderão também ser executadas duas ou mais entregas pelo mesmo veículo, no caso de as necessidades dos clientes serem inferiores a 24 toneladas e permitirem assim, ser agrupadas. 3.4 Simplificações consideradas A modelação proposta é uma simplificação do problema real. Melhorias futuras ao nível da modelação poderão incluir situações que acontecem no caso de estudo e não foram tratados nesta dissertação. Exemplo disso é o facto da existência de clientes onde a duração da viagem entre este e a fábrica fornecedora de produtos é superior ao alcance temporal do veículo. Numa situação real são considerados tempos de descanso do condutor, permitindo desta forma, satisfazer clientes que estão localizados a distâncias relativamente grandes das fábricas. No entanto, na modelação do problema apenas foi considerado o limite máximo de horas consecutivas de trabalho do veículo. Na situação real, existem também clientes localizados em locais inacessíveis por via terrestre. Mais uma vez, esta situação não foi coberta pela modelação presente nesta dissertação, uma vez que isso implicaria considerar diversos tipos de problemas e dificultar seriamente a resolução do problema. 22 Caso de estudo Capítulo 4 Modelação e resolução do problema Este capítulo apresenta uma formulação matemática para o problema em estudo na dissertação com base em formulações matemáticas presentes em 3 artigos científicos. Uma vez que a principal referência de base para o modelo monolítico é [14] e apresenta uma formulação de um problema diferente do tratado nesta dissertação, houve necessidade de estender o modelo, na medida em que este passou a ter em conta os fornecedores e respetivas operações de backhauling. São também apresentados os resultados obtidos com o modelo para uma pequena instância do problema. Tratando-se de um modelo integrado que posteriormente foi sujeito a um processo de decomposição, foi designado por modelo monolítico. 4.1 Representação da rede de distribuição Os problemas de planeamento de rotas de veículos são difíceis de caracterizar devido às especificações e limitações que cada um considera. Dadas as características particulares do problema, nomeadamente questões de precedência entre clientes e fornecedores, foi considerado representar a rede do problema com um grafo dirigido. Desta forma, é possível definir o caminho entre um vértice representativo de um cliente para um vértice representativo de um fornecedor, e não contemplar a ligação não permitida entre fornecedor e cliente. O problema foi formulado tendo por base a formulação existente para o Vehicle Routing Problem with flexible assignment of start and end depots presente em [14]. Naturalmente, houve necessidade de trabalhar a mesma, por forma a que a formulação criada fosse de encontro ao problema descrito no capítulo 3. Na presente formulação, foram usadas as transformações de grafos para representação da rede de distribuição, onde cada solução possível para o problema original corresponde a um ou mais ciclos hamiltonianos num subgrafo do grafo original. Entenda-se por ciclo hamiltoniano, um ciclo que contém todos os vértices do grafo exatamente uma vez, com exceção dos vértices inicial e final, que têm de coincidir. Cada solução possível num grafo transformado pode ser interpretada como uma solução para o problema no grafo original. Desta forma, foi usada uma transformação 23 30 Modelação e resolução do problema As restrições 4.23 e 4.24 são resultado da linearização da equação 4.43 que tem como objetivo atribuir valores à variável de carga do veículo zik, nos vértices dos clientes e dos fornecedores. ∑ i∈∆− j ∑ k∈K xi jk(zik +dj−zjk) = 0∀j∈ {L,B0}(4.43) Quando um veículo é utilizado, as restrições resultantes da linearização da equação anterior forçam o veículo a passar por uma fábrica pertencente a qualquer um dos subconjuntos de M0, ficando assim prevenida a formação de subtours em segmentos de rotas entre depósitos e não para toda a extensão da rota. Note-se que a variável zik é inicializada a zero para todos os veículos em todas as fábricas de M0aMFna restrição 4.38. Já a prevenção de subtours para toda a extensão da rota é garantida pelas restrições 4.25 e 4.26 que resultam da linearização da equação 4.44. ∑ i∈∆− j ∑ k∈K xi jk(wik +si+ti j −wjk) = 0∀j∈ {L,B0,M1,M2,...,MF}(4.44) Estas restrições para além de atribuírem valores às variáveis wik nos vértices dos clientes, dos fornecedores e das fábricas fictícias pertencentes aos conjuntos de M1aMF, obrigam também à passagem das rotas pelos vértices das fábricas originais em M0. Deste modo, fica assegurado a inexistência de subtours ao longo de todo o percurso das diversas rotas. De modo semelhante, os pares de restrições 4.27 e 4.28, 4.29 e 4.30 resultaram de linearizações de duas equações semelhantes e têm como objetivo atribuir valores às variáveis nik ebik, respetivamente. As restrições 4.31 e 4.32 asseguram que as janelas temporais dos fornecedores e das fábricas são cumpridas, isto é, que o veículo visite cada um destes elementos dentro do intervalo definido. A inequação 4.33 estabelece que um segmento de rota, isto é, o percurso de uma rota entre duas fábricas, apenas deve visitar no máximo um backhaul. Ainda relativamente às visitas dos fornecedores, a restrição 4.34 limita o número de rotas que visitam um certo backhaul, de acordo com o respetivo limite de visitas permitido para o mesmo. A imposição do limite de visitas a clientes e fornecedores numa dada rota é função da restrição 4.35. A restrição 4.36 assegura que a capacidade do veículo não é excedida, ou seja, que a totalidade de carga de produtos transportada para os clientes não é superior à capacidade do veículo. Importa referir que no caso de uma visita a um fornecedor é assumido que o veículo transportará a carga máxima, não havendo, portanto, necessidade de criar uma restrição para limitar a quantidade de matéria-prima para este troço da rota. Por último, a restrição 4.37 garante que o número de horas máximo de trabalho de um veículo não é ultrapassado. As restrições 4.39 e 4.40 estabelecem o domínio das variáveis xi jk eyk, enquanto que as restrições 4.41 e 4.42 definem a natureza das variáveis de decisão. 4.3 Implementação e avaliação do modelo 31 Note-se que o modelo apresentado foi baseado na formulação de um problema de planeamento de rotas de veículos que não incluía backhauls, janelas temporais e número máximo de locais por rota [14] e por isso, houve necessidade que a formulação apresentada incluísse variáveis de decisão adicionais (nik ebik), assim como um conjunto de restrições que garantissem que as rotas criadas respeitassem as condições impostas no caso de estudo (restrições 4.27 - 4.35). 4.3 Implementação e avaliação do modelo 4.3.1 Questões de implementação O modelo descrito para resolução de um MDVRPBTW foi implementado em Java e resolvido no Gurobi Optimizer versão 6.0.5 usando a sua capacidade de resolução de problemas através de programação linear inteira mista. Todos os testes do modelo foram executados num computador equipado com um processador Intel R CoreTM i7-2630QM CPU 2,00GHz, 6GB de memória RAM e sistema operativo Windows 10 Pro N. Tal como pode ser visto na secção 4.3.4, o presente modelo tem apenas capacidade para determinar, em tempos computacionais aceitáveis, a solução ótima de instâncias muito reduzidas. Esta situação levou a que fosse necessário desenvolver um novo método de resolução (apresentado em detalhe no capítulo 5) e, por isso, não fosse dada muita importância à melhoria do código deste modelo. Por esta razão, os dados relativos aos clientes, fornecedores e fábricas são inicializados diretamente no bloco de código principal, assim como todos os parâmetros do problema são inicializados em variáveis neste mesmo local. Caso seja necessário alterar algum dos parâmetros ou a localização dos clientes, fornecedores e fábricas da instância a resolver é necessário fazê-lo diretamente no código Java. A Figura 4.1 apresenta um fluxograma do algoritmo do modelo. É possível perceber que o algoritmo se encontra totalmente estruturado em Java e não existem trocas de informação com outros sistemas. Face ao tempo disponível para execução do projeto, o modelo criado com o auxílio das bibliotecas do solver Gurobi foi estruturado de uma forma que não poderá ser considerada a mais eficiente. Exemplo disso, é o caso de as variáveis de decisão serem criadas mesmo que estas não estejam definidas. No caso concreto da criação das variáveis xi jk é gerada uma matriz tridimensional de variáveis, e posteriormente se o arco (i1,j1)não estiver considerado no grafo da rede, o lower bound (lb) e upper bound (ub) de xi jk :i=i1,j=j1;∀k∈Kserão definidos a zero. Por esta razão, nas Tabelas 4.4, 5.2 e 5.5 a quantidade de variáveis de decisão é dividida no número de variáveis a definir e igualadas a zero. No entanto, sabe-se que se fossem utilizadas a técnicas de computação mais sofisticadas, seria possível obter resultados em tempos computacionais ligeiramente mais interessantes do que aqueles que foram obtidos. 32 Modelação e resolução do problema Figura 4.1: Fluxograma do algoritmo do modelo monolítico 4.3.2 Geração de instâncias de testes De forma a ser testada a abordagem monolítica, foi criado um ambiente simulado baseado nas condições reais do problema. Deste modo, para adequar este ambiente às capacidades disponíveis do modelo, foi considerada uma área de estudo de 200km×200km muito inferior à área da Península Ibérica. Foi assumido que os clientes presentes nesta área seriam servidos por duas fábricas localizadas em posições fixas em (50,50)e(150,150). Ao contrário destas posições, a localização dos vértices dos clientes e dos fornecedores são geradas aleatoriamente dentro do intervalo da área de estudo. Perante a sua localização é possível calcular a matriz de distâncias, onde cada elemento da matriz, isto é, o valor da distância entre dois nós que estabelecem ligação por um arco, é calculada como a distância euclidiana: di j =q(xi−xj)2+(yi−yj)2(4.45) A Tabela 4.1 apresenta os pressupostos para serem obtidos os valores dos parâmetros necessários para resolução do problema. Algumas destas conjeturas são baseadas em situações que 4.3 Implementação e avaliação do modelo 33 caracterizam o problema (por exemplo, necessidades dos clientes, tempo de serviço, janelas temporais, capacidade do veículo, tempo máximo de condução, Nmax). Por outro lado, o custo e tempo de viagem considerados, são sustentados por dados reais e recolhidos da literatura. Parâmetro Descrição Pressupostos Valor Un ci j Custo de viagem entre o nó iej Custo: 0,20AC/km 0,2×di j AC ti j Tempo de viagem entre o nó iej Velocidade média do veículo: 50km/h=0,02h/km 0,02×di j h diProcura do nó iCapacidade do veículo: 24 Ton; Necessidade nos vértices das fábricas e dos fornecedores, i∈ M,M0,...,Mf,B: 0 Ton; Procura nos vértices dos clientes i∈ L: 1−24Ton 0−24 Ton siTempo de serviço no nó iTempo de serviço nos vértices das fábricas i∈M,M0,...,MF: 0.3; Tempo de serviço nos vértices dos clientes i∈L:[0.1+0.0083∗di]; Tempo de serviço nos vértices dos fornecedores i∈B: 0.4; 0,14 - 0,4 h [a,b]Janela de tempo dos fornecedores -[7,18]h [c,d]Janela de tempo das fábricas -[7,21]h mCusto fixo de utilização de um veículo 40AC/turno 40 AC QCapacidade de um veículo - 24 Ton RTempo máximo de condução - alcance do veículo Tempo de duração de um turno de trabalho: 8h/turno 8 h Nmax Nomáximo de vértices (clientes e fornecedores) a visitar numa rota Segundo dados fornecidos uma rota tende a ter poucos clientes 4 Nós Tabela 4.1: Valores dos parâmetros calculados e assumidos para o estudo do problema 4.3.3 Instância de teste A validação do modelo monolítico foi realizada com recurso a uma pequena instância de teste inspirada nos testes realizados em [14]. Este problema considera 5 clientes, 3 fornecedores, 2 fábricas e um máximo de 6 veículos disponíveis para executarem todas as rotas. Em comparação com a dimensão real do caso de estudo descrita no capítulo 3, observa-se que esta instância considera um reduzido número de elementos: existência metade do número de fábricas reais, redução de 85 fornecedores e de 127 encomendas, assim como uma frota de veículos reduzida em 135 unidades. 34 Modelação e resolução do problema Para facilitar referências futuras, este problema será designado por sigla TP_A. Na Tabela 4.2 é possível consultar toda a informação relativa aos vértices considerados no TP_A (por exemplo, coordenadas de localização, número máximo de visitas dos fornecedores, procura e fábrica fornecedora de produtos para cada um dos clientes). Na Figura 4.2 é possível visualizar a dispersão dos elementos do problema na área de estudo considerada, considerando as coordenas apresentadas na Tabela 4.2. Veja-se, que os restantes parâmetros necessários para a execução do modelo, estão descritos na Tabela 4.1 Tipo Nome Posição X Posição Y Máximo de visitas Procura Fábrica alocada Fornecedor B1 48 165 10 - - Fornecedor B2 79 40 10 - - Fornecedor B3 169 119 10 - - Cliente L1 113 96 - 6 M1 Cliente L2 73 106 - 6 M1 Cliente L3 104 130 - 6 M2 Cliente L4 58 131 - 6 M2 Cliente L5 157 52 - 6 M1 Fábrica M1 50 50 - - - Fábrica M2 150 150 - - - Tabela 4.2: Dados relativos aos vértices considerados no TP_A Figura 4.2: Localização dos vértices considerados no TP_A Analisando os dados do problema, isto é, localização dos vértices e todos os parâmetros a estes pontos associados, foi possível obter com recurso à equação 4.11 a solução F=2. Desta forma, resultado das características do problema apresentadas, assim como o valor desta variável, 4.3 Implementação e avaliação do modelo 35 o modelo contará com os vértices apresentados na Tabela 4.3. Note-se que a quantidade total de vértices presentes na rede do problema é constituída pela soma dos nós reais e fictícios, tal como explicado na secção 4.1. Tipo Novértices reais Novértices falsos Quantidade Fábricas 2 4 6 Clientes 5 0 5 Fornecedores 3 6 9 Total 10 10 20 Tabela 4.3: Número de vértices presentes na rede de distribuição do TP_A A Tabela 4.4 e a Tabela 4.5 resumem, respetivamente, a totalidade de variáveis de decisão e restrições no modelo para esta instância. As variáveis de decisão dividem-se em dois grupos: aquelas que o modelo tem que encontrar uma solução (A definir) e as que já sabe à priori qual o valor a atribuir às mesmas (Igualadas a zero). O caso da existência das 1440 variáveis xi jk igualadas a zero foi na secção 4.3.1 justificada. No que diz respeito às variáveis zik,nik ebik, as 36 variáveis igualadas a zero, dizem respeito à inicialização das mesmas com valor nulo para todos os veículos, cada vez que visitam uma das fábricas pertencentes aos grupos de M0aMF. Variável Tipo Quantidade Igualadas a zero A definir xi jk Binária 2400 1440 960 ykBinária 6 0 6 zik Inteira 120 36 84 wik Continua 120 0 120 nik Inteira 120 36 84 bik Inteira 120 36 84 Total - 2886 1662 1254 Tabela 4.4: Variáveis de decisão existentes no modelo monolítico para o TP_A Pelos resultados apresentados na Tabela 4.5, verifica-se que para uma instância com 10 vértices reais e consequentemente um total de 20 vértices (reais e falsos), seriam necessárias 8900 restrições para modelar o problema. Finalizada a análise do modelo ao nível da quantidade das variáveis de decisão e do número de restrições, foi executado o modelo para o problema que tem vindo a ser analisado. A Tabela 4.6 apresenta os resultados obtidos para o TP_A. Tal como é possível verificar pelos dados presentes na Tabela 4.6, foram testadas seis combinações de valores para os pesos α,βeγ, obtendo-se sempre a mesma solução. O resultado obtido é constituído por duas rotas de inbound-outbound com duração de 5,4h e 6,52h. Cada uma das rotas é apenas constituída por um segmento de rota. De acordo com o que foi descrito para o 36 Modelação e resolução do problema Restrição Quantidade Restrição 4.18: cada cliente visitado apenas uma vez 5 Restrição 4.19: garantir fluxo para os clientes 84 Restrição 4.20: veículos saem dos depósitos apenas uma vez 6 Restrição 4.21: garantir que os veículos que saem de 12 Restrição 4.22: garantir fluxo para fábricas intermédias 12 Restrição 4.23 e 4.24: atribuir valores a 600 Restrição 4.25 e 4.26: atribuir valor a 4104 Restrição 4.27 e 4.28: atribuir valores a 3192 Restrição 4.29 e 4.30: atribuir valores a 540 Restrição 4.31: janelas temporais nos fornecedores 54 Restrição 4.32: janelas temporais nas fábricas 36 Restrição 4.33: limitar visita a um backhaul por rota 84 Restrição 4.34: limite de visitas a um determinado bakchaul 9 Restrição 4.35: limitar número de nós visitados por rota 84 Restrição 4.36: garantir que a capacidade do veículo não é excedida 30 Restrição 4.18: garantir que não é excedido o alcance temporal do veículo 48 Total 8900 Tabela 4.5: Restrições presentes no modelo monolítico para o TP_A modelo monolítico do problema, cada rota construída é executada por um veículo, pelo que, para a realização do planeamento apresentado serão necessários dois dos seis veículos disponíveis. A uniformidade das soluções obtidas poderá ser explicada pela localização favorável dos fornecedores, isto é, numa posição em que não é exigido percorrer grande distância adicional em relação à rota de outbound para ser realizada uma visita aos mesmos. Por exemplo na situação em que α=1,8 e γ=0,5, a visita de um backhaul traduz-se numa bonificação de 20AC na função objetivo, enquanto que o custo variável de transporte passa para 1,8×0,2AC/km. Deste modo, na Figura 4.3 podem ser vistas as duas possibilidades existentes no momento em que o veículo se encontra a visitar o último cliente (L4) da segunda rota criada: Situação (a) – regressar diretamente para a fábrica mais próxima; Situação (b) – visitar um fornecedor e posteriormente deslocar-se para a fábrica mais próxima. Note-se, que os valores associados aos arcos apresentados na Figura 4.3 representam os custos de deslocação entre os dois vértices. Nas equações 4.46 e 4.47, podem ser vistos os custos associados às duas situações sob efeito dos pesos considerados. Ca=16,27×1,8=29,29AC (4.46) Cb= (18,68+6,13)×1,8−20 =24,66AC (4.47) 4.3 Implementação e avaliação do modelo 37 Alfa Beta Gama Tempo (s) F. objetivo Rotas 1,2 1,8 1 197,26 181,28 M1->L2->L1->L5->B3->M2 M2->L3->L4->B2->M1 1,5 1,5 1 2,70 186,6 M1->L2->L1->L5->B3->M2 M2->L3->L4->B2->M1 1,8 1,2 1 1,31 191,91 M1->L2->L1->L5->B3->M2 M2->L3->L4->B2->M1 1,2 1,8 1,5 1585,06 141,28 M1->L2->L1->L5->B3->M2 M2->L3->L4->B2->M1 1,5 1,5 1,5 720,78 146,6 M1->L2->L1->L5->B3->M2 M2->L3->L4->B2->M1 1,8 1,2 1,5 3,19 151,92 M1->L2->L1->L5->B3->M2 M2->L3->L4->B2->M1 1,2 1,8 0,5 3,65 221,28 M1->L2->L1->L5->B3->M2 M2->L3->L4->B2->M1 1,5 1,5 0,5 2,61 226,6 M1->L2->L1->L5->B3->M2 M2->L3->L4->B2->M1 1,8 1,2 0,5 1,62 231,92 M1->L2->L1->L5->B3->M2 M2->L3->L4->B2->M1 Média - - 279,80 185,60 - Tabela 4.6: Resultados obtidos com o modelo monolítico para o TP_A Figura 4.3: Ilustração do fator de decisão da visita a um backhaul Desta forma, como Ca>Cbe se pretende minimizar os custos associados ao processo de entrega e recolha de bens, a visita ao fornecedor deverá ser realizada, pois, irá permitir minimizar a função objetivo. 38 Modelação e resolução do problema 4.3.4 Análise do desempenho do modelo O problema foi aplicado em instâncias de diversas dimensões, sendo estas baseadas nos requisitos computacionais necessários para algoritmos exatos descritos em [14]. Foram consideradas situações sem nenhum fornecedor e aumentado gradualmente o número de clientes de 2 até 8, sempre com uma procura homogénea de 6 toneladas. Em situações onde o número de clientes justificava a presença de um ou mais fornecedores, foram selecionados aleatoriamente um ou mais clientes e transformados esses nós em vértices representativos de fornecedores. À medida que o número de clientes era aumentado, eram gerados 3 conjuntos aleatórios de vértices representativos de clientes, com objetivo de serem testadas 3 instâncias sob efeito das mesmas condições. Note-se ainda, que dada a função objetivo 4.17, foi necessário considerar para cada instância três combinações diferentes para os pesos α,βeγ. Em função dos resultados obtidos para os diversos testes foi possível traçar o gráfico do tempo computacional exigido para a resolução do problema em função do número de vértices da rede (ver Figura 4.4). Tal como já tinha sido afirmado anteriormente, o MDVRPBTW é um problema da classe NP-difícil, pelo que, o tempo necessário para a sua resolução cresce exponencialmente com o aumento da sua dimensão. Na Figura 4.4 é possível identificar este comportamento para as três instâncias criadas. Desta forma, o modelo monolítico é capaz de determinar a solução ótima para instâncias de dimensões muito inferiores ao problema real apresentado no capítulo 3. Ainda assim, numa primeira fase da exploração do problema, o modelo poderá ser útil para a empresa perceber se a integração do planeamento da logística de inbound eoutbound, bem como se a flexibilização da fábrica de início e fim de rota, isto é, a possibilidade de as rotas terminarem em fábricas diferentes da qual partiram, será ou não vantajoso em relação ao atual modo de planeamento. Figura 4.4: Evolução do tempo computacional em função do número de vértices do problema Capítulo 5 Decomposição do modelo Neste capítulo é apresentado um método de resolução alternativo para o problema em estudo na dissertação que resulta da decomposição do modelo monolítico e designado, por isso, de método de decomposição. Desta forma, é possível resolver instâncias de dimensão superior à pequena instância de teste utilizada anteriormente. São ainda apresentados os resultados obtidos para o TP_A com recurso ao método de decomposição e comparados os dois métodos de resolução em relação à sua performance e qualidade dos resultados. 5.1 Descrição do método O modelo neste capítulo proposto é constituído por dois módulos integrados (consultar Figura 5.1): num primeiro módulo foi desenvolvido um modelo de programação linear inteira mista que efetua a modelação das rotas, isto é, determina os locais a visitar, bem como estabelece a sequência das visitas; num segundo módulo criado, mais uma vez com recurso a um modelo de programação linear inteira mista, é efetuada a alocação dos veículos às rotas previamente criadas no primeiro módulo, com objetivo de minimizar o número de veículos utilizados. Figura 5.1: Representação da abordagem segmentada para o problema 39 46 Decomposição do modelo visitado à fábrica mais próxima deste. Desta forma, conhecendo o custo necessário para percorrer a totalidade dos arcos das rotas de outbound (resultado da equação 5.33), é efetuada a divisão deste valor pelo número total de arcos das rotas outbound (equação 5.34 ). z|β=0=∑ i∈V ∑ j∈δ+ i ci j ∑ k∈K xi jk (5.33) p=z|β=0 Node arcos das rotas de outbound (5.34) Para o exemplo da Figura 5.3, é calculado numa primeira fase o valor da função objetivo (custo de transporte) quando β=0, isto é, o valor necessário para percorrer a rota que inicia e termina na fábrica M1, com passagens intermédias pelo cliente AeB. A rota da outbound está representada por linhas contínuas e tem um custo total dado pela equação 5.35. z|β=0=cM1A+cAB +cBM1=7+3+5=15 (5.35) Consequentemente, o custo médio por arco é dado pela seguinte equação: p=Custo médio por arco =15 3=5 (5.36) Desta forma, o custo aproximado do último arco, isto é, o caminho entre o ultimo cliente visitado (B) e a fábrica mais próxima (M1) e, neste caso única, possuiu um valor estimado de 5AC. Concluído o cálculo do prémio para a visita de um fornecedor, é agora necessário avaliar as diferentes possibilidades existentes. Deste modo, quando o veículo se encontra no último cliente da rota (vértice B) poderá regressar diretamente à fábrica mais próxima (equação 5.37) ou visitar um dos fornecedores existentes, B1ou B2, com custos calculados respetivamente na equação 5.38 e 5.39. z=cM1A+cAB +cBM1=7+3+5=15 (5.37) z0=cM1A+cAB +cBB1+cB1M1−p=7+3+2+6−5=13 (5.38) z00 =cM1A+cAB +cBB2+cB2M1−p=7+3+4+2−5=11 (5.39) Uma vez que é pretendido minimizar o valor da função objetivo, a solução irá contemplar a visita do fornecedor B2. Se for analisada esta solução ao nível do custo acrescentado, é possível concluir que a mesma irá aumentar o custo em apenas 1AC relativamente à rota de outbound. Na eventualidade de existir apenas o fornecedor B1, visitar este local implicaria aumentar o custo em 3AC. Sendo este valor menor que o custo médio por arco, a solução final continuaria a incluir a visita de um fornecedor, ao invés de regressar diretamente para a fábrica. Este método de cálculo do prémio pimplica, tal como o anterior, executar o modelo uma primeira vez com um peso β=0 na função objetivo (equação 5.3). Assim, o modelo irá determinar 5.1 Descrição do método 47 um conjunto de rotas constituídas apenas por clientes e é por isso possível, calcular o custo associada às mesmas, bem como analisar o número de arcos existentes. De forma a que o tempo computacional exigido para encontrar uma solução de uma dada instância não seja muito elevado, foi imposto um time limit de 600 segundos ou a obtenção de um intervalo de otimalidade inferior a 7% para a fase de cálculo do prémio. Ooutput deste módulo de desenho das rotas é a descrição das rotas a realizar, incluindo: duração, distância, percurso, vértices de início e fim de rota, volume de entregas entre outros dados de interesse para o módulo seguinte. 5.1.2 Alocação dos veículos A resolução do problema com recurso ao método de decomposição fica concluída com a execução do segundo módulo, onde será encontrado o número necessário de veículos para cada período de planeamento das rotas. O objetivo é alocar os veículos às rotas, de formar a minimizar o número de veículos utilizados, tendo em conta que cada veículo terá um período máximo de trabalho. Note-se, que o tempo de conclusão de cada uma das rotas diz respeito ao intervalo de tempo com início no momento em que o veículo sai de uma fábrica e fim na altura em que o mesmo regressa a um destes locais. Para referências futuras, o conjunto de rotas que um veículo terá que realizar num determinado período de planeamento será designado de serviço do veículo. Conhecendo o início e fim de cada rota, é gerada uma matriz de distância entre rotas, T0, onde cada elemento t0 i j indica o tempo associado à deslocação de um veículo do vértice de fim da rota Ripara o vértice de origem da rota Rj. Portanto, se o fim da rota Ricoincidir com o local de início da rota Rj, tem-se naturalmente um t0 i j =0h. De modo análogo, é gerada ainda a matriz de custos, C0, onde cada elemento c0 i j, indica o custo de deslocação de um veículo do vértice de fim da rota Ripara o local de início da rota Rj. Esta matriz é calculada com base na matriz T0. Considerando que a rota R1termina na fábrica M1e a rota R2tem início na fábrica M2, o custo associado à deslocação do fim da rota R1para a o local de início da rota R2, é dado por: c0 R1R2=1AC×t0 R1R2=1AC×tM1M2(5.40) Note-se na equação 5.40 que o custo de 1AC advém do pressuposto que a velocidade média é de aproximadamente de 50km/he que o custo de viagem por quilómetro é de cerca de 0,2AC. Por esta razão, a distância percorrida numa hora tem um custo total de 50×0,2=1AC. Para ser possível definir o sequenciamento das rotas executadas por cada veículo, foi criado um depósito de veículos falso e concebidas duas rotas fictícias que teriam início e fim no mesmo, com um tempo nulo de execução. Desta forma, o camião inicia sempre a sua sequência de rotas com a realização da rota fictícia R0, seguida de uma ou mais rotas reais previamente criadas no módulo anterior. No final da sequência de rotas, cada veículo realiza a segunda rota fictícia criada (R|K|), terminando assim no mesmo local de onde iniciou viagem, isto é, no depósito de veículos. Assim sendo, as possíveis ligações entre rotas estão bem definidas e resumem-se às seguintes situações: 48 Decomposição do modelo •R0para qualquer uma das rotas reais criadas na primeira fase de resolução; •qualquer rota real Ri, para uma outra rota real Rj, desde que o tempo necessário para percorrer as duas rotas mais o tempo necessário para ir do final da primeira rota para o início da segunda, não seja superior ao limite temporal do veículo; •qualquer rota real Ri, para a rota fictícia final R|K|. Desta forma, cada rota Ri:i∈Ktem um conjunto de rotas que poderá ser executado após esta (rotas consequentes), e um conjunto de rotas que poderá ser realizado anteriormente (rotas precedentes), representados respetivamente pelos conjuntos, δi+eδi−. O último módulo que constitui o método de decomposição procura determinar o conjunto de rotas que cada um irá executar e foi formulado com o seguinte modelo de programação linear inteira mista: Conjuntos K– Conjunto de rotas R– Conjunto de veículos Parâmetros ti– Tempo necessário para completar a rota i∈K Tmax – Máximo número de horas de trabalho c0 i j - Custo associado à deslocação do veículo do fim da rota iaté ao início da rota j:i,j∈K t0 i j - Tempo associado à deslocação do veículo do fim da rota iaté ao início da rota j:i,j∈K mCusto fixo de utilização de um veículo Variáveis de decisão yr i j =   1,se o veículo rexecuta a rota jdapois da rota i 0,caso contrário zr=   1,se o veículo restá ativo 0,caso contrário wr i– Variável que especifica a hora de início da rota ipelo veículo r.∀i∈K,r∈R O modelo min z =∑ i∈R zi×m+∑ i∈K ∑ j∈K c0 i j ∑ r∈R yr i j (5.41) 5.2 Implementação do modelo 49 Sujeito a: |k−2|zr≥∑ j∈K\{0,|K|} yr 0j∀r∈R(5.42) ∑ i∈δj− ∑ r∈R yr i j =1∀j∈K\{0,|K|} (5.43) ∑ i∈δj− yr i j −∑ i∈δj+ yr ji =0∀r∈R,j∈K\{0,|K|} (5.44) ∑ j∈K\{0,|K|} yr 0j−zr=0∀r∈R(5.45) ∑ j∈K\{0,|K|} ∑ r∈R yr 0j−∑ i∈K\{0,|K|} ∑ r∈R yr i|K|=0∀r∈R(5.46) wr i+ti+t0 i j −wr j≤M(1−yr i j)∀i∈δj−,∀j∈K\{0},r∈R(5.47) wr i+ti+t0 i j −wr j≥ −M(1−yr i j)∀i∈δj−,∀j∈K\{0},r∈R(5.48) wr i≤Tmax ∀r∈R,i∈K(5.49) yr i j ∈ {0,1} ∀i,j∈K,r∈R(5.50) wr i≥Tmax ∀r∈R,i∈K\{0}(5.51) wr i=0∀r∈R,i=0 (5.52) A função objetivo 5.41 do presente modelo pretende minimizar os custos associados à alocação dos veículos às rotas previamente definidas, procurando por isso reduzir o número de veículos utilizados, assim como minimizar os custos associadas à deslocação entre rotas feitas pelo mesmo veículo. A restrição 5.42 força os veículos a estarem ativos quando uma rota lhes é atribuída. A restrição 5.43 estabelece que todas as rotas reais, isto é, aquelas que foram criadas no módulo anterior devem ter alocado um veículo. O fluxo entre execução das rotas reais é garantido pela restrição 5.44, enquanto que a restrição 5.45 garante que cada veículo sai apenas uma vez da rota inicial (R0). Por outro, a restrição 5.46, obriga a que todos os veículos terminem a sequência de rotas em R|K|. Mais uma vez, também neste módulo as restrições 5.47 - 5.49 tratam o aspeto temporal associado à execução da sequência de rotas. Por último, as restrições 5.50 - 5.50, definem os valores possíveis para as variáveis presentes no problema. Ooutput deste módulo será um conjunto de serviços dos veículos, ou seja, uma lista sequenciada de rotas que cada veículo estará responsável por realizar. 5.2 Implementação do modelo O presente método de resolução foi implementado com recurso ao mesmo software ehardware descrito na secção 4.3. 50 Decomposição do modelo Uma vez que numa fase inicial o modelo tinha como principal objetivo comparar a eficácia do método para a instância testada com o modelo monolítico, foi seguida a mesma linha de pensamento para a estruturação do código do que a descrita na secção 4.3.1. Assim, todos os parâmetros do problema e todos os dados sobre os vértices da rede de distribuição do problema são declarados diretamente no código criado. No entanto, uma vez que este método vai ser aplicado ao caso de estudo, serão efetuadas atualizações à arquitetura do sistema, de forma a efetuar leitura e escrita de dados a partir de um ficheiro Excel (apresentado em detalhe na secção 6.1). O fluxograma do algoritmo do método de decomposição é apresentado na Figura 5.4. A primeira situação a avaliar neste método, consiste em perceber se o objetivo da execução do modelo será ou não calcular o valor prémio para uma dada instância. Caso este já seja conhecido, o planeamento das rotas poderá ser imediatamente determinado. Caso contrário, terá que ser numa primeira fase calculado o valor do prémio e só posteriormente realizado o planeamento. O código foi assim implementado, uma vez que inicialmente será necessário conhecer a bonificação para a visita de um fornecedor, contudo, quando se pretende ajustar os valores dos pesos da função objetivo (equação 5.3), não será necessário calcular constantemente o valor do prémio, dado que este é fixo para cada instância. 5.3 Resultados computacionais preliminares De forma a comparar a complexidade associada a este método de resolução com a do modelo monolítico, foi testado o modelo com o TP_A apresentado na secção 4.3.3 e realizada exatamente a mesma análise que tinha sido feita para o modelo monolítico, ou seja, calculado o total de vértices da rede do problema, o número de variáveis de decisão e a quantidade de restrições existentes para a instância em questão. Na Tabela 5.1, tal como se estava à espera, é possível verificar que o número total de vértices foi significativamente reduzido (cerca de 66%). Esta situação acontece uma vez que, nesta abordagem apenas é considerado um grupo de vértices falsos para as fábricas. Tipo Novértices reais Novértices falsos Quantidade Fábricas 2 2 4 Clientes 5 0 5 Fornecedores 3 0 3 Total 10 2 16 Tabela 5.1: Número de vértices presentes na rede do problema do TP_A no método de decomposição A partir do número de vértices presentes na rede de distribuição do problema, é possível calcular o número de variáveis de decisão e de restrições existentes para o TP_A nos dois módulos da abordagem neste capítulo apresentada. Desta forma, com recursos aos dados calculados para os 5.3 Resultados computacionais preliminares 51 Figura 5.4: Fluxograma do algoritmo do método de decomposição dois métodos criados, é possível perceber a qual das abordagens está associada uma maior complexidade, fruto do número de restrições e variáveis de decisão. Uma vez que o método em estudo é constituído por dois módulos, foi numa primeira fase analisado individualmente cada um deles e posteriormente estudado o modelo no seu global, a fim de o comparar com o modelo monolítico apresentado no capítulo 4. 52 Decomposição do modelo 5.3.1 Rotas para o TP_A A Tabela 5.2 apresenta as variáveis de decisão envolvidas no primeiro módulo do modelo de decomposição, bem como o tipo e quantidade existente para o problema apresentado e já testado com o modelo monolítico. Por outro lado, a Tabela 5.3 apresenta a quantidade de restrições necessárias para obter um conjunto de rotas que vá de encontro ao esperado, isto é, que sejam cumpridas todas as limitações descritas no capítulo 3. Variável Tipo Quantidade Igualadas a zero A definir xi jk Binária 864 498 366 wi j Contínua 72 0 72 Total - 936 498 438 Tabela 5.2: Variáveis de decisão existentes no primeiro módulo do método para o TP_A Restrição Quantidade Restrição 5.4: cada cliente visitado apenas uma vez 5 Restrição 5.5: garantir fluxo para os clientes e fornecedores 48 Restrição 5.6: rotas iniciam e terminam numa fábrica 6 Restrição 5.7: um veículo sai apenas uma vez de um nó inicial 6 Restrição 5.8 e 5.9: atribuir valores a 528 Restrição 5.10: Janelas temporais nos fornecedores 18 Restrição 5.11: Janelas temporais nas fábricas 24 Restrição 5.12: limite de visitas a um determinado backhaul 3 Restrição 5.13: limitar número de nós visitados por rota 6 Restrição 5.14: garantir que a capacidade do veículo não é excedida 6 Restrição 5.15: garantir que não é excedido o alcance temporal do veículo 24 Restrição 5.16: limite de um backhaul por rota 6 Total 680 Tabela 5.3: Restrições presentes no primeiro módulo do método de decomposição para o TP_A Para uma instância com 10 vértices reais, a rede de distribuição do problema é modelada por um grafo de 12 vértices (reias e falsos), resultando um total de 438 variáveis (a definir) para o módulo de modelação das rotas. Resultado das características do problema, assim como do número de variáveis de decisão, são necessárias um total de 680 restrições para efetuar a modelação das rotas. Para terminar a análise da primeira parte do modelo, na Tabela 5.4 são apresentados os resultados obtidos no final primeiro módulo para o TP_A, considerando as mesmas condições descritas na secção 4.3.3. Foram testadas três combinações de valores para os pesos αeβ, com 5.3 Resultados computacionais preliminares 53 objetivo de perceber que influência têm na solução obtida. O valor do prémio foi previamente calculado através da equação 5.53: p=z|β=0 Node arcos das rotas =87,96 7=12,57 (5.53) Alfa Beta Visitas a fornecedores Tempo (s) F. objetivo Rotas 1 0,5 1 0,21 82,91 R1:M1->L2->L1->L5->B3->M2 R2:M2->L3->L4->M1 1 1 2 0,13 72,59 R1:M1->L2->L1->L5->B3->M2 R2:M2->L3->L4->B2->M1 0,5 1 2 0,05 23,73 R1:M1->L2->L1->L5->B3->M2 R2:M2->L3->L4->B2->M1 Tabela 5.4: Resultados obtidos no final do primeiro módulo do método de decomposição para o TP_A A Tabela 5.4 demonstra que as combinações dos diferentes pesos dão origem a soluções distintas. Quando α=1 e β=0,5, é dado maior importância à minimização da distância percorrida do que à visita de um fornecedor. Nesta caso, na rota R2, o custo acrescentado para visitar um fornecedor é superior a 0,5×p, e consequentemente, a rota não inclui uma operação de backhauling. Já no caso do número de visitas a fornecedores ter igual ou mais importância na função objetivo que a minimização da distância, observa-se que são criadas duas rotas onde são visitados fornecedores. 5.3.2 Número de veículos para o TP_A O número de variáveis de decisão e restrições do segundo módulo depende do resultado obtido na primeira fase do método, mais concretamente do número de rotas geradas. Na instância de teste, o número de rotas geradas foi exatamente igual para as diferentes combinações dos valores de α eβ. Desta forma, o número total de rotas presentes no segundo módulo do problema corresponde ao tamanho do vetor routesDuration. Com base no número total de rotas, é possível calcular o número de variáveis presentes no segundo módulo para o TP_A (Tabela 5.5), bem como a quantidade de restrições existentes para esta instância (Tabela 5.6). No caso da variável yr i j, as 72 variáveis igualadas a zero, dizem respeito às ligações entre rotas não permitidas. Já no que diz respeito às 4 variáveis wr iigualadas a zero, estão relacionadas com a inicialização desta variável na rota fictícia inicial (R0). Concluído a análise do último módulo ao nível das variáveis de decisão e restrições presentes para o TP_A, são apresentados na Tabela 5.7 os resultados obtidos nesta última fase do método, nomeadamente, que veículo irá executar cada uma das rotas. 54 Decomposição do modelo Variável Tipo Quantidade Igualadas a zero A definir yr i j Binária 96 72 24 zrBinária 6 0 6 zrContínua 24 4 20 Total - 126 76 50 Tabela 5.5: Variáveis de decisão existentes no segundo módulo do método para o TP_A Restrição Quantidade Restrição 5.42: veículo ativo quando tem uma rota atribuída 6 Restrição 5.43: rotas reais criadas devem ter um veículo alocado 2 Restrição 5.44: garantir fluxo para as rotas reais 12 Restrição 5.45: garantir que um veículo sai apenas uma vez da rota inicial 6 Restrição 5.46: Término da sequência de rotas em R|k|6 Restrição 5.47 e 5.48: atribuir valores a wr i48 Restrição 5.49: Rotas percorridas pelo veículo 20 Total 100 Tabela 5.6: Restrições presentes no segundo módulo do método de decomposição para o TP_A Como pode ser visto pela Tabela 5.7, o serviço dos veículos é constituído apenas por uma rota, o que significa que nesta situação o segundo módulo do método nada acrescentou à solução final. Naturalmente, isto acontece uma vez que o limite de horas de operação contínua do par veículo/condutor é inferior à duração total das duas rotas, e por isso, não permite que estas sejam alocadas ao mesmo camião. Alfa Beta Noveículos Tempo (s) F. objetivo Serviço dos veículos 1 0,5 2 0,01 80 V1:R1; V2:R2; 1 1 2 0,01 80 V1:R1; V2:R2; 0,5 1 2 0,01 80 V1:R1; V2:R2; Média 2 0,01 80 - Tabela 5.7: Resultados obtidos no final do segundo módulo do método de decomposição para o TP_A 5.4 Análise global do método 55 5.4 Análise global do método De forma a ser comparado o modelo monolítico com o método de decomposição é necessário analisar este último no seu global, ou seja, é obrigatório somar a totalidade de variáveis de decisão e de restrições presentes nos dois módulos deste para a resolução da instância em estudo. A Tabela 5.8 apresenta os indicadores que permitem avaliar a complexidade dos dois métodos, sendo que no modelo de decomposição os valores destes parâmetros resultam da soma dos mesmo nos dois módulos. O novo método de resolução proposto permitiu não só reduzir em cerca de 61% o número de variáveis de decisão, como também diminuir em aproximadamente 89% o número de restrições necessários na definição do problema. A redução significativa destes elementos advém da diminuição do número de vértices que caracterizam a rede (redução de 8 vértices). A simplificação desta estrutura no método de decomposição permite aumentar a capacidade de resolução do modelo e, consequentemente conseguir trabalhar com problemas de maiores dimensões. Indicadores Modelo Monolítico Modelo de decomposição #Vértices da rede 20 12 #Variáveis de decisão a determinar 1224 476 #Restrições 8900 1008 Tabela 5.8: Comparação dos modelos apresentados ao nível da complexidade Analisando a Tabela 4.6 e a Tabela 5.4 verifica-se que existe apenas uma combinação dos pesos, para cada método, onde é dada igual importância aos diferentes termos da função objetivo: no modelo exato acontece quando α=β=γ=1,5 e no método de decomposição na situação onde α=β=1. Nestes casos, verifica-se que os resultados obtidos pelos dois métodos são exatamente iguais, pelo que o valor associado ao serviço de transporte contratualizado é igual para as soluções obtidas pelos dois modelos, apesar dos diferentes valores da função objetivo (consultar a Tabela 5.9). Esta diferença é justificada pelo facto das funções objetivo serem constituídas por diferentes termos e respetivos pesos, e ainda, pela desigualdade verificada nos valores dos prémios em cada um dos métodos. Modelo Alfa Beta Gama F. objetivo Custo variável Custo fixo Rotas Monolítico 1,5 1,5 1,5 135,6 90,5 80 V1:M2->L3->L4->L2->B2->M1; V2:M2->L1->L5->B3->M2 Decomposição 1 1 - 67,12 90,5 80 V1:M2->L3->L4->L2->B2->M11; V2:M2->L1->L5->B3->M2 Tabela 5.9: Comparação dos modelos apresentados relativamente aos resultados obtidos para o TP_A Através dos resultados obtidos fica comprovada tanta a eficácia, como a eficiência do segundo método de resolução para o TP_A. No entanto, uma vez que o método de decomposição divide 62 Aplicação do método de decomposição ao caso de estudo Figura 6.2: Gráfico do volume de entregas por cada dia dias, visualiza-se que a procura está concentrada num intervalo de valores mais reduzido. É ainda facilmente observado que continuam a existir situações pontuais de procura muito reduzida. Por exemplo, no terceiro dia de planeamento, a procura está maioritariamente distribuída no intervalo de 12 a 24 toneladas, no entanto são observadas duas situações com procura muito reduzida (3 e 5 toneladas). Figura 6.3: Caixa de bigodes da procura dos clientes nos diferentes dias 6.3 Resultados computacionais 63 6.3 Resultados computacionais Na Tabela 6.4 é apresentada uma síntese dos resultados obtidos com o método de resolução para o primeiro dia. São apresentadas algumas características das rotas criadas, tais como, duração, número de clientes (#Clientes), realização de backhauling, volume de entregas e a ainda distância total. As cores associadas às rotas servem para identificar a alocação dos veículos realizada numa segunda fase do planeamento. Tal como explicado na secção anterior o número de clientes de uma rota é limitado, na maioria das vezes, pela capacidade do veículo e não pelo tempo máximo de serviço do mesmo. Esta situação pode ser verificada pelos dados apresentados, uma vez que para este dia, as rotas visitam em média 1,17 clientes/rota, os veículos transportam em média 20,78 toneladas e a duração das rotas é em média de 5,11 horas, valor significativo mais baixo que o limite imposto para o serviço do veículo (8 horas). ID Rota Duração (h) #Clientes Backhauling Volume de entregas (Ton) Distância (km) 1 3,69 1 1 24 134,45 2 3,81 1 1 6 148,05 3 3,92 1 1 24 146,05 4 6,68 1 1 24 283,94 5 6,25 1 1 23 263,11 6 5,80 1 1 24 240,01 7 5,80 1 1 24 240,02 8 5,74 1 1 24 237,11 9 4,07 1 1 24 153,63 10 3,06 1 1 20 104,57 11 5,31 2 1 22 211,20 12 3,7 1 1 24 135,16 13 6,69 1 1 24 284,34 14 5,73 1 1 5 244,62 15 4,86 3 1 17 186,01 16 5,98 1 1 19 251,11 17 7,48 1 1 22 324,69 18 3,49 1 1 24 124,57 Tabela 6.4: Plano detalhado gerado pelo método de decomposição para o primeiro dia Na Tabela 6.5 é apresentado o número de veículos necessários utilizar para o primeiro dia de planeamento, assim como o respetivo serviço para cada um dos mesmos. A Figura 6.4 apresenta o percurso de todas as rotas encontradas para o primeiro dia de planeamento. Naturalmente, a ferramenta de display de rotas permite visualizar individualmente cada uma das rotas e, até consultar detalhes operacionais, tais como, cargas e descargas em cada local. O modelo para determinar a solução para a instância do primeiro dia de planeamento necessitou de cerca de 2 minutos. 64 Aplicação do método de decomposição ao caso de estudo Veículo Serviço do veículo ( ID de rotas) V1 6 V2 13 V3 8 V4 2->12 V5 5 V6 7 V7 18->3 V8 1->9 V9 14 V10 16 V11 15->10 V12 11 V13 4 V14 17 Tabela 6.5: Serviço dos veículos gerado pelo método de decomposição Figura 6.4: Conjunto de rotas criadas pelo método para o primeiro dia O método de resolução utilizado para encontrar o conjunto de rotas para o primeiro dia do planeamento, foi aplicado para as instâncias dos restantes dias. Repare-se, que o tempo computacional necessário para que o modelo encontre o sequenciamento de um conjunto de rotas, assim como determine o serviço de cada veículo, varia de acordo com o número de clientes necessários a satisfazer, bem como das suas necessidades. Por esta razão, foi considerado para todas instâncias que o primeiro e segundo módulos teriam individualmente um tempo máximo de execução (time limit) de 2000 segundos. Por esta razão, o modelo com capacidade de determinar as rotas para um dia de planeamento terá como tempo máximo de execução 1 hora e 10 minutos. A Tabela 6.6 expressa os resultados obtidos para um conjunto de indicadores em cada um dos planeamentos diários da semana representativa considerada. Os indicadores utilizados foram escolhidos tendo por base o trabalho desenvolvido em [9] e são os seguintes: número de rotas criado (#Rotas), número de veículos utilizados (#Veículos), média de clientes por rota (Média #Clientes/Rota), média de carga transportada pelos veículos (Carga Média), taxa de utilização da capacidade de transporte do veículo (Utilização), número de fornecedores integrados nas rotas de entregas de produtos a clientes (#Fornecedores), duração média das rotas (Duração média), o número de rotas com X clientes (# Rotas X clientes), total de custos fixos e variáveis associados ao processo de entrega e recolha de bens (T. custos fixos e T. custos variáveis) e, por fim, o total de valor a pagar, que considera a soma dos dois indicadores anteriores (Valor a pagar). Uma breve análise destes resultados permite verificar que está a ser feita uma boa integração das rotas outbound einbound pois, em todos os dias, se verifica que a totalidade das rotas cria- 6.4 Avaliação do método 65 Dia 1 Dia 2 Dia 3 Dia 4 Dia 5 #Rotas 18 20 19 22 20 #Veículos 14 16 16 17 17 Media #Clientes/Rota 1,17 1,10 1,11 1,05 1,15 Carga Média 20,78 19,45 20,26 18,50 21,05 Utilização 86,57% 81,04% 84,43% 77,08% 87,71% #Fornecedores 18 20 19 22 20 Média duração 5,11 4,76 5,09 4,80 4,95 #Rotas 1 cliente 16 18 17 21 20 #Rotas 2 clientes 1 2 2 1 3 #Rotas >2 clientes 1 0 0 0 0 Custo fixos 1442,00 AC 1648,00 AC 1648,00 AC 1751,00 AC 1751,00 AC Custos variáveis 742,52 AC 758,47 AC 783,16 AC 844,45 AC 792,41 AC Valor a pagar 2184,52 AC 2406,47 AC 2431,16 AC 2595,45 AC 2543,41 AC Tabela 6.6: Resultados obtidos pelo método proposto para a semana representativa das visita um fornecedor. É também importante notar que são necessários menos veículos que o número total de rotas para a realização do planeamento proposto. Portanto, é possível concluir que em cada dia de planeamento existe um ou mais veículos a realizar mais do que uma rota. Em relação ao número de clientes por rota, este valor é condicionado pela variação da procura apresentada anteriormente. Uma vez que a maioria dos clientes apresenta procura próxima da capacidade do veículo, tendem a existir muitas rotas constituídas apenas por um cliente e, consequentemente uma reduzida média de clientes por rota. Resultado ainda da variação da procura e da proximidade da mesma à capacidade do veículo, verifica-se uma taxa de utilização do veículo relativamente elevada (média de 83,37% para a semana considerada). 6.4 Avaliação do método 6.4.1 Método de planeamento atual Uma vez que as instâncias tratam uma situação que nunca foi planeada na empresa, houve necessidade de mimetizar o que é feito atualmente no planeamento diário das rotas. Só assim, é possível comparar os resultados propostos com o que é atualmente praticado. Desta forma, é importante perceber detalhadamente como se processa o planeamento diário das rotas. No início de cada dia, os responsáveis pelo planeamento analisam quais as encomendas necessitam ser expedidas nesse período. Uma vez que estes elementos só têm acesso à localização e necessidades dos clientes, numa primeira fase agrupam os clientes por distrito. Posteriormente, analisam a procura dos clientes pertencentes ao mesmo grupo e verificam se é possível que uma rota visite mais que um cliente do mesmo distrito. No final do processo de desenho das rotas de 66 Aplicação do método de decomposição ao caso de estudo outbound, não existe grande preocupação em fazer a integração de visitas a fornecedores nestas rotas. Contudo, na eventualidade de haver necessidade de matéria-prima na fábrica e ser economicamente vantajoso visitar um backhaul na rota já criada, os planeadores consideram esta opção. Note-se, que é necessário observar a viabilidade desta opção a nível temporal. Uma vez que no contexto desta dissertação e das instâncias criadas não é possível perceber quando existe necessidade de matéria-prima, a opção da visita de um fornecedor foi baseada num algoritmo de roulette wheel. Com base no estudo feito em [9] foi possível verificar que só 23,56% das vezes é realizada uma operação de backhauling em rotas planeadas de acordo com a situação atual. É importante também compreender a estrutura de custos que é atualmente utilizada no processo de transportes. A empresa faz a terceirização deste serviço a empresas especializadas e o custo de transporte está associado ao tipo de rotas executadas. No caso de ser uma rota de outbound, o custo é calculado em função da distância ao cliente mais distante visitado por essa rota e ainda por um custo adicional por cada cliente visitado (consultar equação 6.1). O custo extra/entrega é baseado na relação da localização entre o cliente adicional e o cliente mais distante de uma rota. A Tabela 6.7 apresenta os custos associados a esta relação. Por outro lado, no caso de ser uma rota inbound-outbound o custo é calculado com base na função da distância total percorrida (consultar equação 6.2). Custo Rinbound =0,7×dist.cliente mais distante +extra/entrega (6.1) Custo Rinbound_outbound =0,7×dist.total da rota (6.2) País cliente mais distante País clientes adicional Custo extra/entrega Portugal Portugal 10 AC Espanha Espanha 35 AC Portugal Espanha 65 AC 0 Espanha Portugal 65 AC Tabela 6.7: Relação do custo extra face à localização dos clientes O planeamento diário para cada uma das instâncias consideradas foi realizado de acordo com o método apresentado. De modo análogo ao que foi feito para análise dos resultados do método de decomposição, a Tabela 6.8 apresenta os indicadores que serão adequados para perceber que tipo de rotas foram criadas. Uma vez que na situação atual, o custo de uma solução engloba os custos fixos e variáveis, apenas foi possível apresentar o valor a pagar à empresa especializada de transportes. 6.4 Avaliação do método 67 Dia 1 Dia 2 Dia 3 Dia 4 Dia 5 #Rotas 19 21 19 22 22 #Veículos 16 18 16 17 17 Media #Clientes/Rota 1,11 1,05 1,11 1,05 1,05 Carga Média 19,68 18,48 20,42 18,50 19,14 Utilização 82,02% 76,98% 85,09% 77,08% 79,73% #Fornecedores 3 7 4 7 7 Média duração 3,10 1,05 3,61 3,37 3,18 #Rotas 1 cliente 18 20 17 21 21 #Rotas 2 clientes 0 1 2 1 1 #Rotas >2 clientes 1 0 0 0 0 Valor a pagar 2288,08 AC 2347,44 AC 2573,73 AC 2618,32 AC 2522,23 AC Tabela 6.8: Resultados obtidos para a semana representativa de acordo com mimetização da situação atual 6.4.2 Comparação de soluções A aplicação do método de resolução às instâncias permite desde logo agilizar o processo de planeamento de rotas que atualmente é feito de forma manual, assim como realizar a integração do planeamento das rotas de outbound com operações de bakchauling. Em relação a este último ponto, verifica-se que no total dos cinco dias de planeamento, o número de rotas inbound-outbound desenhadas com recurso ao método de resolução proposto aumentou de 28 para 99 (cerca de 3,5 vezes). No que diz respeito aos restantes indicadores apresentados na Tabela 6.6 e Tabela 6.8, é possível verificar que o número de veículos necessários utilizar para cada dia de planeamento na solução obtida no método de resolução proposto é inferior à solução obtida com o planeamento atual em cerca de 5%. Embora atualmente esta situação não seja preocupante, dado que a empresa tem uma estrutura de custos que depende exclusivamente da distância percorrida e do tipo de rotas, este parâmetro indica que o método de planeamento proposto é mais eficiente do que aquele que é atualmente posto em prática. Em cada um dos dias da semana considerada, a média da duração das rotas foi superior na solução obtida com recurso ao método de decomposição proposto. Esta situação a par do respetivo aumento da utilização das capacidades do veículo, denota que os serviços de transporte contratados pela empresa seriam significativamente melhor aproveitados. Relativamente aos custos totais das soluções criadas, foi apresentado na Figura 6.5 um gráfico dos valores a pagar em cada um dos dias da semana representativa, que pretende servir de base comparativa em termos financeiros das duas abordagens de planeamento. Os custos apresentados têm em conta unicamente o valor que a empresa terá que pagar à entidade contratada para realizar o serviço de transporte, ou seja, não é considerado o ganho associado à integração de um fornecedor numa rota de outbound. Por esta razão, surgem situações onde o planeamento realizado de acordo 68 Aplicação do método de decomposição ao caso de estudo com o que é atualmente praticado tem um custo associado inferior ao das soluções obtidas com o método de resolução proposto (caso do dia 2 e 5). Figura 6.5: Valor a pagar em cada dia de planeamento de acordo com os resultados obtidos pelas duas abordagens descritas No entanto, se for considerado um ganho para a visita de um backhaul, serão obtidos custos bastantes mais reduzidos para a nova abordagem de planeamento, uma vez que dela resultam um maior número de rotas de inbound-outbound. Dado que na estrutura de custos atual a utilização de um veículo não tem um custo fixo, o prémio não poderá ser igualado a este valor. Por outro lado, na estrutura de custos proposta é considerado um custo fixo, pelo que a visita de um fornecedor numa rota de outbound se traduz na redução da utilização de um veículo e, consequentemente na poupança de um valor igual a esse custo. Para a estrutura de custos utilizada no planeamento atual, foi estudado o custo da visita de cada um dos fornecedores considerados nas instâncias a partir da fábrica mais próxima do mesmo (consultar Anexo B). A Tabela 6.9 apresenta o valor do prémio calculado para cada uma das abordagens: no caso da situação atual representa o custo médio da visita de um fornecedor; no caso da abordagem proposta é equivalente ao custo fixo da utilização de um veículo. Prémio (estrutura de custos atual) Prémio (estrutura de custos proposta) 110,33 AC 103,00 AC Tabela 6.9: Redução de custos na visita de um fornecedor numa rota inbound-outbound Uma vez que se pretende comparar os custos efetivos das soluções obtidas com recurso aos dois métodos de planeamento, foi considerado que uma visita a um fornecedor estava associada a uma redução de custos igual à média dos valores apresentados (106,67 AC). A Figura 6.6 apresenta o gráfico dos custos reais das soluções obtidas para cada dia, após ser retirado a bonificação das 6.4 Avaliação do método 69 visitas dos fornecedores aos custos a pagar à empresa prestadora dos serviços de transporte. Uma vez que o valor do prémio é igual nas duas abordagens, poderá ser feita uma comparação realista dos resultados obtidos com as duas abordagens descritas. Tal como seria expectável, a abordagem proposta que visa a integração da logística de inboundoutbound, permite para a semana apresentada efetuar uma elevada redução de custos. É neste caso, verificado que em todos os dias existe uma diminuição relevante nos custos reais do plano de transportes. Figura 6.6: Custo real em cada dia de planeamento de acordo com os resultados obtidos pelas duas abordagens descritas 70 Aplicação do método de decomposição ao caso de estudo Capítulo 7 Extensão do método de decomposição Este capítulo apresenta um conjunto de extensões do método de decomposição que pretende melhorar a qualidade da solução obtida, aproximando-a da solução ótima obtida com o modelo monolítico. Numa primeira fase é apresentada uma simples modificação do método de decomposição apresentado no capítulo anterior. São detalhados os resultados obtidos com a extensão do método para uma pequena instância de validação. Logo de seguida, é possível encontrar a descrição de um método iterativo que pretende uma vez mais corrigir desvios detetados nos resultados em relação à solução ótima. Por último, são apresentadas as soluções encontradas pelo método iterativo para as cinco instâncias da semana representativa. 7.1 Modificação das rotas Nesta primeira fase de extensão do método de decomposição, a alteração do modelo acontece entre o primeiro e segundo módulo do método, através da modificação das rotas criadas (consultar Figura 7.1). No método de decomposição, tal como apresentado em detalhe na Figura 5.4, as rotas obtidas no primeiro módulo servem diretamente de input para o segundo módulo do método de decomposição. No entanto, nesta extensão do método de resolução, cada rota que constitui a lista routesOutput é modificada com objetivo de dar maior liberdade à alocação dos veículos às rotas. A modificação referida passa pela remoção do nó de fim da rota (fábrica) e pela consequente atualização dos campos que caracterizam a rota, isto é, duração, vértice final e trajetória. Posteriormente, é criado o vetor routesDuration, a matriz C0e ainda a matriz T0com base na nova lista de rotas, designada por routesOutputModify. Esta modificação no algoritmo do método de decomposição implicou a alteração das restrições 5.47 e 5.48 do segundo módulo. Sabendo que o serviço de um veículo inicia e termina com a execução de uma rota fictícia e que cada elemento t0 i j da matriz T0passou a ser a distância (em horas) entre o último cliente ou fornecedor visitado pela rota Rie o vértice de origem da rota Rj, no caso das restrições identificadas considerarem j=|K|(rota fictícia de fim de percurso), para além do tempo t0 i j já considerado na restrição, terá ainda que ser contemplado o tempo necessário 71 78 Extensão do método de decomposição Iteração 1: MP =  5 5×4,5 8 5 5×4,5 8 =  5 2,81 5 2,81  Solução s0: R1:M1−A−B−B1−M1; V1alocado à rota R1; R1duration: 7,65 horas; R1durationOutbound: 4,5 horas; Iteração 2: MP =  5×4,5 80 5×4,5 80 =  2,81 0 2,81 0  Solução s0: R1:M1−A−B−B1−M1; V1alocado à rota R1; R1duration: 7,65 horas; R1durationOutbound: 4,5 horas; Iteração 3: MP =  2,81×4,5 80 2,81×4,5 80 =  1,58 0 1,58 0  Solução s0: R1:M1−A−B−B1−M1; V1alocado à rota R1; R1duration: 7,65 horas; R1durationOutbound: 4,5 horas; Iteração 4: MP =  1,58×4,5 80 1,58×4,5 80 =  0,88 0 0,88 0  Solução s0: R1:M1−A−B−M1; V1alocado à rota R1; R1duration: 4,5 horas; R1durationOutbound: 4,5 horas; Uma vez que a solução inicial considera a visita do fornecedor B2e é constituída apenas por uma rota, no início da iteração 1 vai ser atualizado o prémio da visita deste fornecedor a partir 7.2 Método iterativo 79 dos clientes inseridos nesta rota (AeB). A atualização da matriz MP levou a que a solução criada nesta iteração visitasse o fornecedor B1. Desta forma, na iteração 2, na atualização da matriz MP verifica-se a modificação do prémio da visita do fornecedor B1e ainda a atribuição de valor nulo aos prémios da visita do fornecedor B2, de modo a não ser possível voltar a considerar a visita do mesmo numa futura iteração. Seguidamente, como existe apenas a possibilidade de visitar ou não o fornecedor B1, as iterações futuras (iteração 3 eiteração 4) continuam a atualizar o valor do prémio da visita deste fornecedor até ser alcançado um critério de paragem. 7.2.2 Critério de paragem A abordagem iterativa será terminada quando for alcançado um critério de paragem. Uma vez que o principal objetivo do trabalho é efetuar o planeamento integrado e eficaz da logística de inbound-outbound, o critério de paragem tem em conta o número de rotas de inbound-outbound. Assim, quando a quantidade destas rotas for inferior a 50% do número total de rotas, o algoritmo deixará de apresentar resultados interessantes face ao que seria pretendido. No entanto, uma vez que este requisito poderia requerer um número elevado de iterações, no caso das instâncias estudadas foi também definido um número máximo de iterações (Nite). Em suma, a abordagem iterativa terá paragem quando as rotas obtidas não consideraram na sua maioria a visita de um fornecedor ou for atingindo o número máximo de iterações estipulado. 7.2.3 Resultados computacionais preliminares Uma vez que é necessário comparar os resultados da abordagem iterativa com as soluções obtidas com o modelo monolítico, foi criada uma pequena instância do problema. Os clientes e fornecedores deste problema, foram estrategicamente localizados, de forma a perceber se a abordagem proposta seria capaz de lidar com determinados problemas encontrados no método de decomposição. A Figura 7.5 mostra a localização dos vértices do problema. Os pontos estão representados de cor amarelo, verde e azul, representando respetivamente as fábricas, clientes e fornecedores da instância. Por outro lado, a Tabela 7.2 apresenta os dados relativos aos diferentes pontos que constituem esta instância. Uma vez que era pretendido que os prémios atribuídos às visitas de um fornecedor fossem iguais nos dois métodos, foi inicialmente calculado com recurso ao método de decomposição o valor do prémio p, obtendo-se um valor de 6,909AC. Por esta razão, o valor de γa utilizar na função objetivo 4.17 foi calculado com base na equação 7.4. γ×Custo Veiculo =6,909 ⇔γ=6,909 103 =0,067 (7.4) Conhecido o valor do peso a atribuir ao termo da função objetivo referente à bonificação das visitas aos fornecedores, foi executado o modelo monolítico para a instância apresentada, obtendo-se o resultado apresentado na Tabela 7.3. A solução obtida permite a utilização de apenas um veículo para satisfazer as necessidades dos 5 clientes e ainda realizar duas operações de backhauling. A 80 Extensão do método de decomposição Figura 7.5: Localização dos pontos da instância de teste da abordagem iterativa Tipo Nome Máximo de visitas Procura Fábrica Fornecedora Fábrica M1 - - - Fábrica M2 - - - Cliente L1 - 12 M1 Cliente L2 - 12 M1 Cliente L3 - 6 M2 Cliente L4 - 6 M2 Cliente L5 - 6 M2 Fornecedor S1 5 - - Fornecedor S2 5 - - Fornecedor S3 5 - - Fornecedor S4 5 - Tabela 7.2: Dados relativos aos pontos considerados na instância apresentada rota terá duração de 7,79 horas e terá um custo total de 159,50 AC, correspondente a um custo fixo de 103,00 AC e 56,50 AC de custos variáveis. Em relação à resolução deste pequeno problema com recurso ao método iterativo, foram utilizados ambos os critérios de atualização de prémios apresentados. Os melhores resultados, isto é, aqueles que apresentavam menores custos, foram obtidos quando aplicado o critério B. Os resultados do modelo iterativo para a instância de teste, quando considerado esse critério de atualização 7.2 Método iterativo 81 Alfa Beta Gama Tempo F. objetivo Rota 1 1 0,067 2,55 91,44 M1->L2->L1->B2->M2->L3->L4->L5->B3->M2 Tabela 7.3: Resultados obtidos para a instância de teste com o modelo monolítico de prémios, são apresentados na Tabela 7.4 e encontram-se estruturados pelas diversas iterações. Desta forma, é possível identificar claramente as modificações existentes à medida que o modelo vai avançando. Na iteração 0 (solução inicial) apresentada na Tabela 7.4 é possível perceber a razão pela qual, quando considerado o critério A, o método iterativo apresentou piores resultados. Comparando as rotas desta solução, com os segmentos de rota (M1->L2->L1->B2->M2 e M2->L3->L4->L5- >B3->M2) que constituem a solução obtida pelo modelo monolítico, verifica-se que a primeira rota (M1->L2->L1->B4->M1) seria a única rota onde deveria ser alterado o fornecedor a visitar. No entanto, ao ser utilizado o critério A no método iterativo, constate-se que os prémios associados aos clientes desta rota nunca serão atualizados, dado que, a sua duração é em todas as iterações inferior à duração média das duas rotas. Os dados apresentados na Tabela 7.4, permitem verificar que a partir da quinta iteração deixou de ser proveitoso visitar um fornecedor em ambas as rotas, devido às atualizações dos prémios até aqui impostas. Uma vez que um dos critérios de paragem foi alcançado, o modelo poderia ter sido terminado. No entanto, para verificar que iterações futuras não acrescentariam qualquer valor ao método de resolução, foi considerado como único critério de paragem do algoritmo um número máximo de iterações igual a dez. Analisando em detalhe as diferentes soluções obtidas, verifica-se que entre a solução inicial e a solução obtida na primeira iteração foi alterado o fornecedor da primeira rota. Esta modificação está associada a um aumento da distância percorrida sem qualquer benefício associado e consequentemente pelo acréscimo dos custos. Já da primeira iteração para a segunda é possível verificar que a nova alteração do fornecedor da primeira rota também aumenta a distância total, contudo permite realizar o retorno para a fábrica na qual inicia a segunda rota. Desta forma, como a soma das durações das duas rotas não excede o limite máximo de horas de trabalho do par condutor/veículo, é possível que estas sejam realizadas pela mesma viatura. Por esta razão, apesar do aumento da distância total das rotas, consegue-se minimizar os custos associados ao processo de transportes. Na terceira iteração deixa de ser visitado um fornecedor na primeira rota e verifica-se a alteração da ordem das visitas dos dois clientes. Esta situação impossibilitou que as duas rotas fossem executadas pelo mesmo veículo, e, por isso, fosse aumentado o custo da solução criada. Na quarta iteração nota-se mais uma vez a influência da atualização dos prémios na segunda rota, nomeadamente na troca do fornecedor B3para a visita do fornecedor B2, o que se traduziu num aumento da duração e distância percorrida na mesma. É assim, mais uma vez verificado que são necessários dois veículos para realizar as duas rotas criadas. Na última iteração apresentada, nenhuma das rotas criadas integra a visita de um fornecedor. Observa-se a diminuição da distância e duração 82 Extensão do método de decomposição Iteração 0 (solução inicial) Veículo ID Rota Rotas Duração Distância V1 1 M1->L2->L1->B4->M1 4,12 151,26 V2 2 M2->L3->L4->L5->B3->M2 3,69 124,43 Iteração 1 Veículo ID Rota Rotas Duração Distância V1 2 M1->L2->L1->B1->M1 4,18 153,88 V2 1 M2->L3->L4->L5->B3->M2 3,69 124,43 Iteração 2 Veículo ID Rota Rotas Duração Distância V1 1 M1->L2->L1->B2->M1 4,26 158,09 V1 2 M2->L3->L4->L5->B3->M2 3,69 124,43 Iteração 3 Veículo ID Rota Rotas Duração Distância V1 2 M1->L1->L2->M1 3,62 145,93 V2 1 M2->L3->L4->L5->B3->M2 3,69 124,43 Iteração 4 Veículo ID Rota Rotas Duração Distância V1 1 M1->L1->L2->M1 3,62 145,93 V2 2 M2->L5->L4->L3->B2->M2 4,05 142,46 Iteração 5 Veículo ID Rota Rotas Duração Distância V1 2 M2->L5->L4->L3->M2 4,23 171,32 V1 1 M1->L1->L2->M1 3,62 145,93 Tabela 7.4: Resultados obtidos para a instância de teste com a abordagem iterativa das rotas, o que permite que seja alocado o mesmo veículo a ambas. Apesar da redução dos custos, esta solução não é a que está relacionada a mais vantagens para a empresa, visto que, não houve ganhos com retornos de matéria-prima para as fábricas. A solução criada na segunda iteração é igual ao resultado obtido pelo modelo monolítico. De 7.2 Método iterativo 83 forma a comprovar que esta solução era aquela que apresentava menor custo para a empresa, foi traçado o gráfico dos custos em função da iteração do modelo (consultar Figura 7.6). Neste gráfico, está incluindo o valor a pagar à empresa transportadora e ainda o custo real do planeamento (custo com o planeamento que tem em consideração o retorno financeiro associado às visitas dos fornecedores). Figura 7.6: Custos das soluções obtidas com a abordagem iterativa em função da iteração É possível confirmar que o melhor resultado obtido com recurso à abordagem iterativa é o obtido na segunda iteração, uma vez que é este que irá permitir à empresa diminuir os custos de transporte das rotas de outbound e, ainda, rentabilizar o investimento feito neste serviço com a realização de dois retornos à fábrica com matéria-prima. 7.2.4 Resultados computacionais Com recurso ao método iterativo descrito, foi mais uma vez efetuado o planeamento de cada umas das cinco instâncias geradas na secção 6.2. Foram considerados os dois critérios para atualização de rotas, sendo obtidos os melhores resultados com recurso ao critério B, onde se verificou a melhoria das soluções em dois dos cinco dias considerados (segundo e quarto dia), ao contrário do critério A, que não permitiu melhorar a solução obtida com o método de decomposição em nenhum dos dias. Tal como explicado no capítulo anterior, o tempo computacional necessário para que o método determine a solução para uma dada instância, depende do número e localização dos clientes, assim como das suas necessidades. Uma vez que nesta extensão do método é considerado um Nite = 10, foi considerado um tempo máximo de execução de 600 segundos para um dos módulos que constituem o método de resolução. Por conseguinte, a resolução de uma instância com recurso a esta extensão será resolvida num período máximo de 3 horas e 20 minutos. 84 Extensão do método de decomposição No Anexo C deste documento é possível visualizar em detalhe o conjunto de rotas criadas, assim com a respetiva alocação dos veículos gerado com recurso ao método iterativo. Por sua vez, a Tabela 7.5 apresenta a análise destes resultados, através do mesmo conjunto de indicadores já utilizado em momentos anteriores. Comparando estes resultados com os da Tabela 6.6, é possível compreender quais as modificações das soluções que conduziram à redução de custos no segundo e quarto dia. No dia 2, verifica-se que houve uma redução de 10% no número de fornecedores visitados, enquanto que no quarto dia a diminuição foi de cerca de 36,4%. É importante notar que as mesmas operações de entrega nos dois dias foram realizadas com menos uma rota do que tinha sido feito anteriormente, o que se traduziu num melhor aproveitamento da capacidade dos veículos e, no caso do segundo dia, uma maior duração média das rotas. Veja-se que, o número de rotas com 2 clientes aumentou nos dois dias, resultado da diminuição do número de fornecedores visitados e do consequente aumento do tempo disponível para integrar um novo cliente numa rota de inbound-outbounb, cuja visita do fornecedor foi desconsiderada devido à atualização dos prémios. A conjugação de todas estas alterações no conjunto de rotas criadas permitiu que, no caso do segundo dia, fosse necessário menos um veículo para executar todas as rotas e que, no caso do quarto dia fossem necessários menos dois veículos. Dia 1 Dia 2 Dia 3 Dia 4 Dia 5 #Rotas 18 19 19 21 20 #Veículos 14 15 16 15 17 Media #Clientes/Rota 1,17 1,16 1,11 1,10 1,15 Carga Média 20,78 20,47 20,26 19,38 21,05 Utilização 86,57% 85,31% 84,43% 80,75% 87,71% #Fornecedores 18 18 19 14 20 Média duração 5,11 4,84 5,10 4,75 4,95 #Rotas 1 cliente 16 16 17 19 17 #Rotas 2 clientes 1 3 2 2 3 #Rotas >2 clientes 1 0 0 0 0 Custo fixos 1442,00 AC 1545,00 AC 1648,00 AC 1545,00 AC 1751,00 AC Custos variáveis 742,52 AC 736,43 AC 783,16 AC 822,26 AC 792,41 AC Valor a pagar 2184,52 AC 2281,43 AC 2431,16 AC 2367,26 AC 2543,41 AC Tabela 7.5: Resultados obtidos com o método iterativo para a semana representativa Relativamente aos custos das soluções destes dois dias, a Figura 7.7 e a Figura 7.8 apresentam dois gráficos comparativos entre a situação obtida pelo método de decomposição e pelo resultado final da extensão deste método. É possível verificar que tanto o valor a pagar (Figura 7.7) para a realização do planeamento proposto, como o custo que considera o retorno financeira da prática de operações de backhauling (Figura 7.8) são significativamente inferiores nas soluções obtidas com o método iterativo. No caso do segundo dia o valor a pagar foi reduzido em 5,2%, enquanto que 7.2 Método iterativo 85 os custos reais foram diminuídos em cerca de 3,2%. Já no caso do dia 4 da semana considerada, houve uma redução de 8,8% e de 4,2%, respetivamente no valor a pagar e nos custos reais. Se for analisada a redução de custos ao nível semanal, conclui-se que o valor a pagar foi reduzido em cerca de 353,23 AC (3,0%), enquanto se forem considerados os ganhos da integração de fornecedores nas rotas de outbound o valor necessário despender para efetuar o planeamento foi diminuído em 187,07 AC (1,8%). Figura 7.7: Gráfico comparativo do valor a pagar das soluções obtidas pelos dois métodos Figura 7.8: Gráfico comparativo do custo real das soluções obtidas pelos dois métodos 86 Extensão do método de decomposição Capítulo 8 Conclusões e trabalho futuro 8.1 Conclusões e contribuições do trabalho desenvolvido Este trabalho permitiu simplificar e melhorar o processo de planeamento de transportes de uma empresa portuguesa de produção de painéis de madeira, com várias unidades de produção na Península Ibérica. O problema em estudo é classificado como um problema de planeamento de rotas de veículos com múltiplos vértices de origem, janelas temporais e bakchauls (MDVRPTWB –Multiple Depot Vehicle Routing Problem with Time Windows and Backhauls). Foi inicialmente proposto um modelo de programação matemática integrado para representar o problema. Esta abordagem permitiu entender até que dimensões do problema poderia uma abordagem monolítica apresentar resultados em tempos computacionais satisfatórios. Uma vez que o problema a resolver é da classe NP-difícil, observou-se que o modelo desenvolvido apenas tinha capacidade para resolver instâncias de dimensão muito reduzida (2 fábricas, 5 clientes, 3 fornecedores e 6 veículos) em tempo computacional aceitável (desde poucos segundos a alguns minutos, em função dos pesos atribuídos aos termos da função objetivo). Dadas as limitações do modelo monolítico, procurou-se decompor o modelo em duas fases: num primeiro momento seria executada a modelação de rotas e posteriormente realizada a alocação de veículos às rotas previamente criadas. Desta forma, foi possível resolver instâncias de maior dimensão, no entanto inferiores à grandeza do problema real, e perceber quais as vantagens introduzidas pela utilização de um modelo que pode servir de sistema de apoio à decisão. O algoritmo desenvolvido foi testado através da simulação de uma semana representativa de operações, tendo como base comparativa o plano elaborado da forma tradicional. As soluções obtidas mostram que o método proposto conduz a melhorias significativas tanto ao nível dos custos, como em relação ao número de rotas de inbound-outbound. Comparativamente aos resultados criados pela mimetização da situação atual, as soluções obtidas pelo método de decomposição permitiram reduzir o valor a pagar à empresa especializada em transportes na ordem dos 2% e ainda aumentar 3,5 vezes o número de rotas de inbound-outbound. Uma vez que o método de decomposição apresenta em algumas situações resultados divergentes aos obtidos pelo modelo monolítico, o processo de melhoria do método de resolução teve 87 94 Instâncias constituintes da semana representativa Clientes - Dia 2 Nome Cód. Postal Localidade Latitude Longitude Procura Fábrica L1 14550 Montilla 37,58772 -4,63729 22 M2 L3 18640 Padul 37,02509 -3,62297 20 M2 L6 3754-909 Agueda 40,57128 -8,45946 23 M1 L10 47155 Santovenia de Pisuerga 41,69378 -4,69026 6 M4 L12 47012 Valladolid 41,6303 -4,69155 18 M4 L20 4524-909 Santa Maria da Feira 40,91682 -8,49724 24 M1 L53 29006 Malaga 36,70387 -4,46453 24 M2 L63 4590-688 Raimonda 41,31819 -8,33465 22 M1 L99 05230 Avila 40,61441 -4,33596 20 M3 L105 41400 Ecija 37,54147 -5,08267 3 M2 L119 4770-861 Casteloes 41,4099 -8,42187 5 M3 L139 3105-292 Pelariga 39,97255 -8,63179 22 M3 L164 29006 Malaga 36,70387 -4,46453 24 M2 L181 10002 Caceres 39,46574 -6,37447 24 M4 L189 13440 Argamasilla de Calatrava 38,72739 -4,07849 5 M2 L208 2025-000 Alcanede 39,41534 -8,82161 12 M1 L209 4580-646 Vilela 41,24743 -8,38268 22 M3 L228 2400-000 Leiria 39,74953 -8,80768 6 M1 L230 29006 Malaga 36,70387 -4,46453 23 M2 L247 19004 Guadalajara 40,63249 -3,16017 20 M4 L269 23200 La Carolina 38,27426 -3,61418 20 M2 L276 3730-953 Vale de Cambra 40,84296 -8,39562 24 M3 Instâncias constituintes da semana representativa 95 Clientes - Dia 3 Nome Cód. Postal Localidade Latitude Longitude Procura Fábrica L10 47155 Santovenia de Pisuerga 41,69378 -4,69026 18 M4 L12 47012 Valladolid 41,6303 -4,69155 23 M3 L14 4535-472 Sao Paio De Oleiros 40,989 -8,59689 16 M3 L17 4905-222 Carvoeiro 41,64721 -8,65676 21 M1 L20 4524-909 Santa Maria da Feira 40,91682 -8,49724 3 M3 L30 2461-601 Alcobaca, Porugal 39,57169 -8,91851 24 M1 L52 4590-373 Freamunde 41,28656 -8,33896 24 M3 L54 28921 Alcorcon 40,34897 -3,82864 12 M4 L74 45210 Yuncos 40,08839 -3,87317 24 M3 L99 05230 avila 40,61441 -4,33596 12 M4 L111 4470-590 Maia 41,22789 -8,62105 24 M3 L128 41016 Sevilha 37,39419 -5,88024 17 M2 L147 28970 Humanes de Madrid 40,25962 -3,82096 12 M4 L152 45220 Yeles 40,1207 -3,80512 24 M4 L169 23640 Torre del Campo 37,76966 -3,8999 24 M2 L181 10002 Caceres 39,46574 -6,37447 24 M1 L194 28200 Madrid 40,59038 -4,16161 12 M4 L208 2025-000 Alcanede 39,41534 -8,82161 5 M1 L221 23100 Mancha Real 37,78681 -3,61038 24 M4 L224 29400 Malaga 36,78136 -5,08069 24 M2 L247 19004 Guadalajara 40,63249 -3,16017 18 M2 96 Instâncias constituintes da semana representativa Clientes - Dia 4 Nome Cód. Postal Localidade Latitude Longitude Procura Fábrica L1 14550 Montilla 37,58772 -4,63729 20 M2 L3 18640 Padul 37,02509 -3,62297 16 M2 L6 3754-909 Agueda 40,57128 -8,45946 24 M1 L14 4535-472 Sao Paio De Oleiros 40,989 -8,59689 6 M3 L30 2461-601 Alcobaca, Porugal 39,57169 -8,91851 20 M3 L63 4590-688 Raimonda 41,31819 -8,33465 6 M3 L105 41400 Ecija 37,54147 -5,08267 24 M2 L111 4470-590 Maia 41,22789 -8,62105 24 M1 L119 4770-861 Casteloes 41,4099 -8,42187 20 M3 L128 41016 Sevilha 37,39419 -5,88024 23 M2 L139 3105-292 Pelariga 39,97255 -8,63179 16 M1 L152 45220 Yeles 40,1207 -3,80512 24 M2 L154 28814 Madrid 40,55287 -3,44983 6 M4 L169 23640 Torre del Campo 37,76966 -3,8999 20 M4 L175 41500 Alcala de Guadaira 37,33968 -5,84181 22 M2 L181 10002 Caceres 39,46574 -6,37447 21 M4 L189 13440 Argamasilla de Calatrava 38,72739 -4,07849 8 M4 L198 18220 Albolote 37,22832 -3,65436 22 M2 L209 4580-646 Vilela 41,24743 -8,38268 22 M3 L228 2400-000 Leiria 39,74953 -8,80768 3 M1 L230 29006 Malaga 36,70387 -4,46453 12 M2 L269 23200 La Carolina 38,27426 -3,61418 24 M2 L276 3730-953 Vale de Cambra 40,84296 -8,39562 24 M1 Instâncias constituintes da semana representativa 97 Clientes - Dia 5 Nome Cód. Postal Localidade Latitude Longitude Procura Fábrica L1 14550 Montilla 37,58772 -4,63729 16 M2 L3 18640 Padul 37,02509 -3,62297 24 M2 L10 47155 Santovenia de Pisuerga 41,69378 -4,69026 24 M4 L12 47012 Valladolid 41,6303 -4,69155 24 M3 L17 4905-222 Carvoeiro 41,64721 -8,65676 24 M1 L20 4524-909 Santa Maria da Feira 40,91682 -8,49724 12 M3 L52 4590-373 Freamunde 41,28656 -8,33896 24 M3 L54 28921 Alcorcon 40,34897 -3,82864 4 M4 L74 45210 Yuncos 40,08839 -3,87317 16 M4 L99 05230 Avila 40,61441 -4,33596 13 M4 L119 4770-861 Casteloes 41,4099 -8,42187 22 M3 L132 28814 Madrid 40,55287 -3,44983 24 M2 L147 28970 Humanes de Madrid 40,25962 -3,82096 4 M4 L164 29006 Malaga 36,70387 -4,46453 16 M2 L181 10002 Caceres 39,46574 -6,37447 24 M4 L189 13440 Argamasilla de Calatrava 38,72739 -4,07849 18 M2 L194 28200 Madrid 40,59038 -4,16161 24 M2 L208 2025-000 Alcanede 39,41534 -8,82161 21 M1 L221 23100 Mancha Real 37,78681 -3,61038 24 M2 L228 2400-000 Leiria 39,74953 -8,80768 3 M1 L230 29006 Malaga 36,70387 -4,46453 24 M2 L247 19004 Guadalajara 40,63249 -3,16017 12 M4 L276 3730-953 Vale de Cambra 40,84296 -8,39562 24 M3 98 Instâncias constituintes da semana representativa Anexo B Custo da visita dos fornecedores Neste anexo é apresentado o custo da visita de todos os fornecedores considerados nas instâncias criadas com base no caso de estudo. Este valor foi calculado tendo em conta a distância à fábrica mais próxima e considerando a estrutura de custos atualmente adotada pela empresa. 99 100 Custo da visita dos fornecedores Nome Fábrica Dist. Fábrica-Fornecedor Dist. Fornecedor-Fábrica Custo da Visita B2 M1 54,22 53,68 75,53 AC B4 M2 198,70 199,69 278,87 AC B6 M1 54,93 54,47 76,58 AC B16 M2 197,96 195,13 275,16 AC B17 M1 15,77 16,76 22,77 AC B18 M1 38,42 38,26 53,67 AC B19 M1 200,41 200,96 280,96 AC B30 M2 112,78 115,36 159,70 AC B35 M3 75,55 75,99 106,08 AC B39 M2 82,09 82,69 115,35 AC B40 M2 46,21 46,79 65,10 AC B42 M1 32,75 33,17 46,15 AC B43 M4 13,21 13,08 18,40 AC B59 M3 11,60 11,59 16,23 AC B60 M2 74,65 74,80 104,61 AC B64 M2 144,02 141,53 199,88 AC B68 M2 82,09 82,69 115,35 AC B75 M2 196,10 195,90 274,40 AC B79 M3 37,46 37,50 52,47 AC B82 M4 79,83 80,18 112,01 AC B83 M1 61,87 62,00 86,71 AC B85 M3 56,49 56,50 79,10 AC B86 M4 67,32 68,32 94,94 AC B88 M2 48,08 50,97 69,33 AC B89 M4 80,73 80,38 112,77 AC B95 M2 16,27 19,39 24,96 AC B108 M4 55,67 55,58 77,88 AC B110 M3 24,24 24,93 34,42 AC B119 M4 80,43 80,55 112,69 AC B131 M2 68,31 71,59 97,93 AC B138 M1 128,69 128,85 180,27 AC Custo médio da visita de um fornecedor em rota isolada 110,33 AC Anexo C Soluções obtidas com o método iterativo Neste anexo são apresentadas as soluções obtidas para cada um dos dias de planeamento com recurso ao método iterativo (método de resolução que apresentou soluções mais interessantes). É detalhado o conjunto de rotas criados, assim como a alocação dos veículos, isto é, as rotas que constituem o serviço de cada veículo. De modo a completar estes dados, é ainda realizada a representação espacial da solução para cada dia de planeamento 101 102 Soluções obtidas com o método iterativo Planeamento do dia 1 Veículo ID Rota Rota Duração (h) #Clientes Backhauling Carga Distância V1 6 M2-Linehaul ID:164-Backhaul ID:95-M2 5,8 1 1 24 240,00 V2 13 M3-Linehaul ID:12-Backhaul ID:82-M4 6,69 1 1 24 284,34 V3 2 M1-Linehaul ID:30-Backhaul ID:17-M1 3,81 1 1 6 148,05 V3 1 M1-Linehaul ID:14-Backhaul ID:85-M3 3,69 1 1 24 134,45 V4 16 M2-Linehaul ID:152-Backhaul ID:43-M4 5,98 1 1 19 251,11 V5 5 M2-Linehaul ID:189-Backhaul ID:95-M2 6,25 1 1 23 263,11 V6 17 M2-Linehaul ID:224-Backhaul ID:95-M2 7,48 1 1 22 324,68 V7 14 M3-Linehaul ID:99-Backhaul ID:43-M4 5,73 1 1 5 244,62 V8 11 M4-Linehaul ID:247-Linehaul ID:132-Backhaul ID:108-M4 5,31 2 1 22 211,20 V9 3 M2-Linehaul ID:1-Backhaul ID:95-M2 3,92 1 1 24 146,05 V9 18 M2-Linehaul ID:198-Backhau ID:40-M2 3,49 1 1 24 124,57 V10 8 M1-Linehaul ID:17-Backhaul ID:85-M3 5,74 1 1 24 237,11 V11 15 M3-Linehaul ID:209-Linehaul ID:52-Linehaul ID:63-Backhaul ID:85-M3 4,86 3 1 17 186,01 V11 10 M3-Linehaul ID:6-Backhaul ID:18-M1 3,06 1 1 20 104,57 V12 12 M1-Linehaul ID:276-Backhaul ID:59-M3 3,7 1 1 24 135,16 V12 9 M3-Linehaul ID:111-Backhaul ID:35-M3 4,07 1 1 24 153,63 V13 7 M2-Linehaul ID:230-Backhaul ID:95-M2 5,8 1 1 24 240,01 V14 4 M2-Linehaul ID:175-Backhaul ID:95-M2 6,68 1 1 24 283,94 Soluções obtidas com o método iterativo 103 Conjunto de rotas geradas para o primeiro dia Fornecedores que servem as diferentes fábricas no primeiro dia 110 Soluções obtidas com o método iterativo Planeamento do dia 5 Veículo ID Rota Rota Duração (h) #Clientes Backhauling Carga Distância V1 17 M2->Linehaul ID:3->Backhaul ID:40->M2 4,16 1 1 24 158,18 V2 20 M3->Linehaul ID:12->Backhaul ID:82->M4 6,69 1 1 24 284,34 V3 8 M2->Linehaul ID:132->Backhaul ID:108->M4 6,89 1 1 24 294,34 V4 11 M2->Linehaul ID:164->Backhaul ID:95->M2 5,73 1 1 16 240,00 V5 5 M1->Linehaul ID:17->Backhaul ID:85->M3 5,74 1 1 24 237,11 V6 7 M4->Linehaul ID:10->Backhaul ID:82->M4 5,3 1 1 24 215,28 V7 9 M3->Linehaul ID:276->Backhaul ID:59->M3 3,34 1 1 24 117,06 V7 18 M3->Linehaul ID:20->Backhaul ID:85->M3 3,42 1 1 12 125,78 V8 1 M3->Linehaul ID:52->Backhaul ID:85->M3 4,57 1 1 24 178,64 V9 13 M2->Linehaul ID:189->Backhaul ID:95->M2 6,21 1 1 18 263,11 V10 14 M2->Linehaul ID:230->Backhaul ID:95->M2 5,8 1 1 24 240,00 V11 4 M4->Linehaul ID:54->Linehaul ID:247->Backhaul ID:43->M4 4,99 2 1 16 197,84 V12 6 M1->Linehaul ID:228->Linehaul ID:208->Backhaul ID:17->M1 4,6 2 1 24 175,03 V13 10 M4->Linehaul ID:147->Linehaul ID:74->Backhaul ID:43->M4 4,18 2 1 20 155,80 V13 2 M4->Linehaul ID:99->Backhaul ID:43->M4 2,74 1 1 13 91,56 V14 19 M2->Linehaul ID:194->Backhaul ID:43->M4 6,6 1 1 24 280,05 V15 12 M3->Linehaul ID:119->Backhaul ID:85->M3 4,87 1 1 22 194,34 V16 16 M2->Linehaul ID:1->Backhaul ID:95->M2 3,85 1 1 16 146,05 V16 3 M2->Linehaul ID:221->Backhaul ID:95->M2 2,32 1 1 24 66,21 V17 15 M4->Linehaul ID:181->Backhaul ID:43->M4 7,03 1 1 24 301,33 Soluções obtidas com o método iterativo 111 Conjunto de rotas geradas para o quinto dia Fornecedores que servem as diferentes fábricas no quinto dia 112 Soluções obtidas com o método iterativo Referências [1] P Toth e D Vigo. The Vehicle Routing Problem. Society for Industrial and Applied Mathematics, 2002. [2] S Sathyanarayanan, K S Joseph, e S K V Jayakumar. A hybrid population seeding technique based genetic algorithm for stochastic multiple depot vehicle routing problem. Em 2015 International Conference on Computing and Communications Technologies (ICCCT), 26-27 Feb. 2015, páginas 119–127. IEEE, 2015. [3] G B Dantzig e J H Ramser. The truck dispatching problem. Management Science, 6(1):80– 91, 1959. [4] Gilbert Laporte. Fifty years of vehicle routing. Transportation Science, 43(4):408–416, 2009. [5] Patrik Flisberg, Bertil Lidén, e Mikael Rönnqvist. A hybrid method based on linear programming and tabu search for routing of logging trucks. Computers & Operations Research, 36(4):1122–1144, 2009. [6] Xu Degang e Xiao Renbin. Modelling and intelligent solving of foodstuff distribution vrp based on disruption management. International Journal of Computer Applications in Technology, 44(2):80–87, 2012. [7] Yueqin Zhang, Shiying Chen, Jinfeng Liu, e Fu Duan. The application of genetic algorithm in vehicle routing problem. Em International Symposium on Electronic Commerce and Security, ISECS 2008, August 3, 2008 - August 5, 2008, páginas 3–6. Inst. of Elec. and Elec. Eng. Computer Society, 2008. [8] I von Poser e A R Awad. Optimal routing for solid waste collection in cities by using real genetic algorithm. Em International Conference on Information & Communication Technologies: from Theory to Applications, 24-28 April 2006, página 5 pp., Piscataway, NJ, USA, 2006. IEEE. [9] Pedro Amorim, Alexandra F. Marques, e Bruno Oliveira. Wood-based products distribution planning with wood returns in a iberian company, 5-7-2014 2014. [10] I Kucukoglu e N Ozturk. An advanced hybrid meta-heuristic algorithm for the vehicle routing problem with backhauls and time windows. Computers & Industrial Engineering, 86:60–68, 2015. [11] Carlos Manuel Chorro Simões Barrico. Optimização evolucionária multi-objectivo em ambientes incertos : pesquisa de soluções robustas. Tese de doutoramento, 2007. 113 114 REFERÊNCIAS [12] M Angelica Pinninghoff, Ricardo Contreras, e Carlos Pantoja. A comparison of methods for the vehicle routing problem. Em 2014 40th Latin American Computing Conference, CLEI 2014, September 15, 2014 - September 19, 2014. Institute of Electrical and Electronics Engineers Inc., 2014. [13] Luo Jianping e Chen Min-Rong. Multi-phase modified shuffled frog leaping algorithm with extremal optimization for the mdvrp and the mdvrptw. Computers & Industrial Engineering, 72:84–97, 2014. [14] Alvina G. H. Kek, Ruey Long Cheu, e Qiang Meng. Distance-constrained capacitated vehicle routing problems with flexible assignment of start and end depots. Mathematical and Computer Modelling, 47(1–2):140–152, 2008. [15] Haibing Li e Andrew Lim. Local search with annealing-like restarts to solve the vrptw. European Journal of Operational Research, 150(1):115–127, 2003. [16] Emmanouil E Zachariadis e Chris T Kiranoudis. An effective local search approach for the vehicle routing problem with backhauls. Expert Systems with Applications, 39(3):3174– 3184, 2012. [17] Daniel Palhazi Cuervo, Peter Goos, Kenneth Sörensen, e Emely Arráiz. An iterated local search algorithm for the vehicle routing problem with backhauls. European Journal of Operational Research, 237(2):454–464, 2014. [18] S Geetha, P T Vanathi, e G Poonthalir. Metaheuristic approach for the multi-depot vehicle routing problem. Applied Artificial Intelligence, 26(9):878–901, 2012. [19] Marshall L. Fisher. Optimal solution of vehicle routing problems using minimum k-trees. Operations Research, 42(4):626–642, 1994. [20] Laszlo Ladányi, Ted K. Ralphs, e Leslie E. Trotter. Branch, Cut, and Price: Sequential and Parallel, páginas 223–260. Springer Berlin Heidelberg, Berlin, Heidelberg, 2001. [21] Candace Arai Yano, Thomas J. Chan, Lori Kaplan Richter, Theodore Cutler, Katta G. Murty, e David McGettigan. Vehicle routing at quality stores. Interfaces, 17(2):52–63, 1987. [22] Sylvie Gélinas, Martin Desrochers, Jacques Desrosiers, e Marius M. Solomon. A new branching strategy for time constrained routing problems with application to backhauling. Annals of Operations Research, 61(1):91–109, 1995. [23] Paolo Toth e Daniele Vigo. An exact algorithm for the vehicle routing problem with backhauls. Transportation Science, 31(4):372–385, 1997. [24] Aristide Mingozzi, Simone Giorgi, e Roberto Baldacci. An exact method for the vehicle routing problem with backhauls. Transportation Science, 33(3):315–329, 1999. doi:10.1287/trsc.33.3.315. [25] Gilbert Laporte, Yves Nobert, e Serge Taillefer. Solving a family of multi-depot vehicle routing and location-routing problems. Transportation Science, 22(3):161–172, 1988. [26] G Laporte, M Gendreau, J Y Potvinb, e F Semet. Classical and modern heuristics for the vehicle routing problem. International Transactions in Operational Research, 7(4-5):285– 300, 2000. REFERÊNCIAS 115 [27] J K Lenstra e A H G Rinnooy Kan. Complexity of vehicle routing and scheduling problems. Networks, 11(2):221–227, 1981. [28] Claudia Archetti, Dominique Feillet, Michel Gendreau, e M Grazia Speranza. Complexity of the vrp and sdvrp. Transportation Research Part C: Emerging Technologies, 19(5):741–750, 2011. [29] L. Bodin, B. Golden, e A. Assad. Routing and Scheduling of Vehicles and Crews: The State of the Art., volume 10. Computers and Operations Research, 1983. [30] Éric Taillard, Philippe Badeau, Michel Gendreau, François Guertin, e Jean-Yves Potvin. A tabu search heuristic for the vehicle routing problem with soft time windows. Transportation Science, 31(2):170–186, may 1997. [31] Frank A. Tillman. The multiple terminal delivery problem with probabilistic demands. Transportation Science, 3(3):192–204, 1969. [32] Anthony Wren e Alan Holliday. Computer scheduling of vehicles from one or more depots to a number of delivery points. Operational Research Quarterly (1970-1977), 23(3):333–344, 1972. [33] Billy E. Gillett e Jerry G. Johnson. Multi-terminal vehicle-dispatch algorithm. Omega, 4(6):711–718, 1976. [34] B. L. Golden, T. L. Magnanti, e H. Q. Nguyen. Implementing vehicle routing algorithms. Networks, 7(2):113–148, 1977. [35] Ole M. Raft. Third euro iv special issuea modular algorithm for an extended vehicle scheduling problem. European Journal of Operational Research, 11(1):67–76, 1982. [36] M. O. Ball, B. L. Golden, A. A. Assad, e L. D. Bodin. Planning for truck fleet size in the presence of a common-carrier option. Decision Sciences, 14(1):103–120, 1983. [37] I. Ming Chao, Bruce L. Golden, e Edward Wasil. A new heuristic for the multi-depot vehicle routing problem that improves upon best-known solutions. American Journal of Mathematical and Management Sciences, 13(3-4):371–406, 1993. [38] I. Deif e L. Bodin. Extension of the Clarke and Wright Algorithm for Solving the Vehicle Routing Problem with Backhauls. 1984. [39] Marc Goetschalckx e Charlotte Jacobs-Blecha. The vehicle routing problem with backhauls. European Journal of Operational Research, 42(1):39–51, 1989. [40] Paolo Toth e Daniele Vigo. A Heuristic Algorithm for the Vehicle Routing Problem with Backhauls, páginas 585–608. Springer Berlin Heidelberg, Berlin, Heidelberg, 1996. [41] Paolo Toth e Daniele Vigo. A heuristic algorithm for the symmetric and asymmetric vehicle routing problems with backhauls. European Journal of Operational Research, 113(3):528– 543, 1999. [42] Christophe Duhamel, Jean-Yves Potvin, e Jean-Marc Rousseau. A tabu search heuristic for the vehicle routing problem with backhauls and time windows. Transportation Science, 31(1):49–59, 1997. 116 REFERÊNCIAS [43] Ibrahim H. Osman e Niaz A. Wassan. A reactive tabu search meta-heuristic for the vehicle routing problem with back-hauls. Journal of Scheduling, 5(4):263–285, 2002. [44] N. Wassan. Reactive tabu adaptive memory programming search for the vehicle routing problem with backhauls. The Journal of the Operational Research Society, 58(12):1630– 1641, 2007. [45] José Brandão. A new tabu search algorithm for the vehicle routing problem with backhauls. European Journal of Operational Research, 173(2):540–555, 2006. [46] Yuvraj Gajpal e P. L. Abad. Multi-ant colony system (macs) for a vehicle routing problem with backhauls. European Journal of Operational Research, 196(1):102–117, 2009. [47] Nabila Azi, Michel Gendreau, e Jean-Yves Potvin. An exact algorithm for a vehicle routing problem with time windows and multiple use of vehicles. European Journal of Operational Research, 202(3):756–763, 2010. [48] F. Hernandez, D. Feillet, R. Giroudeau, e O. Naud. A new exact algorithm to solve the multitrip vehicle routing problem with time windows and limited duration. 4OR, 12(3):235–259, 2014. [49] 16/05/2016. URL: https://developers.google.com/maps/documentation/ geocoding/intro#Viewports. [50] 30/04/2016 2016. URL: https://github.com/Project-OSRM/osrm-backend/ wiki/Server-API---v4,-old. [51] 2016. URL: http://fence2.focusnet.eu/.