Trabalho Prático de Otimização Combinatória

UNIVERSIDADE FEDERAL DE OUROPRETO CURSO DE GRADUAÇÃO EM ENGENHARIA DE PRODUÇÃO DISCIPLINA GESTÃO DA CADEIA DE SUPRIMENTOS 20242 TRABALHO FINAL MODELOS DE LOCALIZAÇÃO E ROTEAMENTO DATA DE ENTREGA 28032025 1 INSTRUÇÕES PARA A EXECUÇÃO DO TRABALHO a Leia com atenção o artigo técnico APM9346final1pdf Ele descreve a aplicação abordada assim como o modelo de Prog Linear InteiraMista proposto para abordar o problemaalvo b Leia com atenção a implementação do modelo completo dada nos códigosfonte m2mhlrpmvmd e m2mhlrpmvrun c Leia com atenção a implementação da técnica de Decomposição Benders disponível em bdm2mhlrpmvmd e bdm2mhlrpmvrun d Leia com atenção a implementação modificada que usa o famoso recurso de Seleção de Cortes ParetoÓtimos proposto por Magnanti Wong e aperfeiçoado por Papadakos em 2008 O artigo de Papadakos se encontra nos anexos 2 Com base no seu estudo sobre o problemaalvo sobre o modelo de PLIM proposto e sobre a técnica de Decomposição de Benders realize um estudo de esforçodesolução e de escalabilidade conforme descrito a seguir a Execute o modelo StandAlonepara o problemaalvo o modelo completo disponível em m2mhlrpmvmd e m2mhlrpmvrun para valores do nível de serviço T tais como 20 25 30 35 40 45 50 55 60 65 e 70 para a instância ap10ndat b Com base nos resultados obtidos e nos logs de execução do CPLEX trace curvas para o número de nós na árvore BranchAndBound o tempo de solução a evolução do gapdeintegralidade e número total de planos cortantes empregados c Repita os procedimentos do item b para a instância ap20ndat Limite o tempo de execução a 1800 segundos basta acrescentar à linha option cplexoptions a diretiva time 1800 como mostrado durante as aulas práticas d Execute os scripts que implementam o Método de Decomposição de Benders bdm2mhlrpmvmd e bdm2mhlrpmvrun para valores do nível de serviço T tais como 20 25 30 35 40 45 50 55 60 65 e 70 para a instância ap10ndat e Com base nos resultados obtidos e nos logs de execução do CPLEX trace curvas para o número de iterações do Método de Benders o tempo de solução e a evolução do gapdeotimalidade Repita o procedimento anterior para a instância ap20ndat limitando tempo de execução a 1800 segundos 3 Com base no seu estudo sobre a técnica de Seleção de Cortes Pareto Ótimos proposta por Magnanti Wong e aperfeiçoada por Papadakos em 2008 Papadakos2008pdf repita a experiência realizada em 2 agora considerando as implementações disponíveis em bdm2mhlrpmvpomd e bdm2mhlrpmvporun 4 Construa um relatório técnico colecionando seu aprendizado sobre o problemaalvo e seu esforço de solução a aplicação da técnica de Decomposição de Benders e o esquema numérico de seleção de cortes ParetoÓtimos de Papadakos 2008 Boa sorte e bom trabalho a todos Auf Wiedersehen Estudo Computacional com Decomposição de Benders e Cortes ParetoÓtimos Relatório Técnico Ayeska Gabriela da Silva Curso de Engenharia de Produção Universidade Federal de Ouro Preto UFOP Professora Gilberto Miranda Junior 1 Introdução Este relatório tem como objetivo apresentar um estudo computacional sobre um problema logístico que envolve tanto a localização de hubs quanto o roteamento de entregas Para isso foi utilizada a técnica de Programação Linear Inteira Mista PLIM que permite modelar decisões binárias como instalar ou não um hub e contínuas como a quantidade de carga transportada Durante o desenvolvimento do trabalho o foco foi entender como o modelo se comporta em diferentes situações e quais estratégias de resolução são mais eficientes Para isso foi aplicada a técnica de Decomposição de Benders que separa o problema em duas partes uma que cuida da localização dos hubs chamada de problema mestre e outra que trata do roteamento e en trega das cargas o subproblema Essa separação ajuda bastante na hora de resolver problemas grandes pois divide a complexidade em etapas menores Além disso também foi estudada uma versão aprimorada da Decomposição de Benders que utiliza uma técnica chamada de seleção de cortes ParetoÓtimos Essa abordagem pro posta inicialmente por Magnanti e Wong e aperfeiçoada por Papadakos 2008 busca acelerar o processo de resolução adicionando ao modelo apenas os cortes restrições mais relevantes para guiar a solução Os testes computacionais foram feitos variando o nível de serviço representado pelo pa râmetro T e utilizando diferentes conjuntos de dados instâncias menores e maiores do pro blema O objetivo foi comparar os tempos de execução e entender como o modelo responde a essas mudanças avaliando tanto o esforço computacional quanto a qualidade das soluções obtidas 2 Descrição do ProblemaAlvo O problema estudado neste trabalho é conhecido como M2MHLRP do inglês Multi Vehicle MultiCommodity Hub Location Routing Problem ou seja tratase de um problema logístico integrado que envolve ao mesmo tempo decisões estratégicas e operacionais Em outras palavras é preciso decidir onde instalar os hubs centros de distribuição como conectar os demais nós da rede a esses hubs e como organizar as rotas dos veículos que farão as entregas 1 A ideia principal é organizar melhor o transporte de mercadorias em uma rede de cidades ou centros logísticos buscando reduzir os custos totais Esses custos envolvem desde a instalação dos hubs até o deslocamento dos veículos que atendem às demandas entre os clientes O problema funciona da seguinte forma Existe um conjunto de pontos nós que representam cidades ou locais com demanda de transporte Algumas dessas cidades podem se tornar hubs que são como centros de redistribuição de mercadorias Cada cidade deve ser conectada a algum hub Os produtos precisam ser enviados entre pares de cidades passando quando necessário por hubs intermediários E por fim os veículos disponíveis devem fazer as entregas finais respeitando um limite de tempo T para cada rota O modelo considera que os veículos são todos iguais homogêneos e que há um número fixo deles disponível Também existem restrições que impedem que as rotas ultrapassem um certo tempo máximo justamente para manter a qualidade do serviço Os dados utilizados para representar a rede e as demandas vêm de dois arquivos forne cidos ap10ndat com uma instância menor e ap20ndat com uma instância maior Esses arquivos contêm informações como as distâncias entre os nós os custos de transporte e as demandas entre os pares de cidades Todos os dados foram normalizados para facilitar o processamento e a comparação entre os diferentes testes 3 Modelo Matemático Para representar o problema de roteirização com múltiplos hubs e veículos foi utilizado um modelo de Programação Linear Inteira Mista PLIM O objetivo principal do modelo é minimizar os custos totais envolvidos na operação da rede logística levando em conta desde a instalação de hubs até o uso de veículos para as entregas A seguir são apresentadas as variáveis e os parâmetros usados no modelo seguidos pela função objetivo e pelas principais restrições Variáveis de decisão zik 0 1 indica se o nó i está alocado ao hub k zkk 0 1 indica se o hub k foi instalado xijkm 0 1 fração da demanda entre os nós i e j que é roteada via os hubs k e m yuvkl 0 1 indica se a aresta u v é utilizada na rota do veículo l que parte do hub k qlk 0 1 indica se o veículo l está sendo utilizado no hub k 2 plik 01 indica se o nó i é atendido pelo veículo l alocado ao hub k θ ℝ variável auxiliar utilizada no método de Benders Parâmetros do modelo ak custo fixo para instalar o hub k wij demanda entre os nós i e j cuv custo de transporte entre os nós u e v cq l custo de uso do veículo l α β γ ω ex coeficientes de ponderação usados para diferentes custos no modelo T limite máximo de tempo que um veículo pode rodar em uma rota Função objetivo A função objetivo tem como foco minimizar o custo total TC que é formado pelos seguintes componentes Custo fixo de instalação de hubs FC Custo de transporte interhub IC Custo de alocação dos nós aos hubs AC Custo de uso de veículos VC Custo das rotas percorridas pelos veículos RC A equação completa fica assim min TC FC IC AC RC VC kN ex ak zkk ij km α wij ckm cmk xijkm i k β oi di cik zik l V k N ω cql qlk uv A k N l V γ cuv yuvkl Principais restrições do modelo As restrições mais importantes do modelo garantem que 1 Cada nó esteja alocado exatamente a um hub k N zik 1 i N 5 2 Um nó só pode ser alocado a um hub que tenha sido instalado zik zkk i k 3 O fluxo de demanda roteado pelos hubs respeite a alocação m N xijkm zik i jk k N xijkm zjm i jm 4 O tempo total de cada rota não ultrapasse o limite T uv A cuv yuvkl T k N l V 4 Decomposição de Benders Durante o desenvolvimento do trabalho foi estudada e aplicada a técnica de Decomposição de Benders que é muito útil para resolver modelos de Programação Linear InteiraMista PLIM que possuem variáveis de diferentes naturezas algumas contínuas e outras inteiras No caso do nosso problema logístico com hubs e veículos essa técnica faz bastante sentido porque conseguimos dividir o problema em duas partes Problema Mestre é responsável pelas decisões estratégicas como onde instalar os hubs zkk como alocar os clientes a esses hubs zik e como distribuir os veículos qlk Essas decisões são discretas variáveis binárias Subproblema para cada configuração gerada pelo mestre este subproblema cuida das operações de roteamento e entrega usando variáveis contínuas como os fluxos de entrega flktuv e as rotas dos veículos yuvkl A ideia da decomposição é resolver o problema em etapas Primeiro resolvemos o problema mestre depois usamos a solução encontrada para montar o subproblema Se a solução do subproblema não for viável ou puder ser melhorada geramos um corte de Benders uma restrição extra que melhora o problema mestre Esse processo é repetido até que os custos se estabilizem e o modelo encontre uma solução considerada ótima ou próxima disso Formulação do modelo com Benders O modelo mestre com Benders pode ser escrito assim min cT z θ sujeito a z Z θ αr βrT z r ℛ Onde z representa as variáveis inteiras do mestre θ é uma variável auxiliar que estima o custo do subproblema αr e βr são os coeficientes dos cortes de Benders gerados a cada iteração r R é o conjunto de todas as iterações realizadas Vantagens da decomposição Ao aplicar a técnica percebemos que o tempo de solução diminui em relação ao modelo ori ginal completo principalmente em instâncias maiores como a do arquivo ap20ndat Isso acontece porque o modelo mestre se mantém mais simples enquanto o subproblema é resolvido separadamente reduzindo a complexidade da árvore de BranchandBound Além disso a decomposição de Benders é especialmente útil quando se quer estudar dife rentes configurações de parâmetros como o nível de serviço T já que permite reusar parte do modelo e adaptar somente as partes necessárias 5 Cortes ParetoÓtimos Papadakos 2008 Durante a realização do trabalho também foi implementada uma variação do método de De composição de Benders chamada de seleção de cortes ParetoÓtimos proposta inicialmente por Magnanti e Wong 1981 e aperfeiçoada por Papadakos 2008 Essa técnica tem como objetivo acelerar a convergência do algoritmo de Benders adicionando cortes mais eficientes ao modelo mestre Motivação No método tradicional de Benders os cortes adicionados ao mestre são obtidos com base no dual do subproblema Apesar de válidos esses cortes nem sempre são os mais fortes e por isso o algoritmo pode demorar várias iterações para convergir A proposta de Papadakos consiste em melhorar essa etapa por meio da geração de cortes dominantes também chamados de ParetoÓtimos Eles são construídos de forma a eliminar a maior parte possível da região não ótima acelerando a aproximação da solução final Como funciona Para isso o subproblema dual é modificado Em vez de apenas buscar uma solução dual viável ele é reformulado para encontrar a que mais contribui com um corte informativo Isso é feito resolvendo um problema auxiliar que leva em consideração um ponto de referência z uma solução atual do mestre e tenta gerar um corte que corte o maior espaço possível sem excluir soluções ótimas Na prática esse novo corte é mais eficiente porque domina outros possíveis cortes por isso o nome ParetoÓtimo Esse processo reduz a quantidade de iterações necessárias no algo ritmo de Benders 5 Aplicação no presente estudo No contexto deste trabalho a técnica de Papadakos foi implementada com base nos arquivos bdm2mhlrpmvpomd e bdm2mhlrpmvporun adaptados para o ambiente Python Pyomo O subproblema foi modificado para gerar cortes mais eficientes a partir de uma formu lação auxiliar conforme sugerido no artigo de Papadakos 2008 Ao executar os experimentos com essa técnica tanto para a instância ap10ndat quanto para ap20ndat observouse que o algoritmo convergiu em apenas uma iteração para todos os valores do nível de serviço T Esse resultado demonstra claramente a efetividade dos cortes ParetoÓtimos uma vez que o tempo de processamento se manteve baixo mesmo em instâncias maiores Resumo da Contribuição Essa técnica mostrou ser extremamente vantajosa no contexto de problemas de roteirização e localização de hubs Ela não só melhorou a performance computacional como também facilitou a análise de diferentes cenários sem a necessidade de longos tempos de execução 6 Discussão dos Resultados A partir dos resultados computacionais obtidos com os scripts implementados em Python Pyomo foi possível comparar o desempenho de três estratégias distintas de solução para o problema M2MHLRP o modelo StandAlone completo a decomposição de Benders clássica e a decomposição com cortes ParetoÓtimos Todos os dados foram obtidos a partir da execução dos códigos em ambiente Google Colab com a leitura e tratamento prévio dos arquivos ap10ndat e ap20ndat Esses arquivos foram convertidos em dataframes utilizando a biblioteca Pandas e os parâmetros extraídos foram uti lizados diretamente nos modelos Resultados do Modelo StandAlone Para compreender o comportamento do modelo completo de Programação Linear Inteira Mista PLIM conhecido como modelo StandAlone realizamos uma série de experimentos utilizando as instâncias ap10ndat e ap20ndat Antes de rodar os experimentos foi necessário realizar um tratamento dos dados no Python pois os arquivos de entrada estavam em formato texto dat e não podiam ser utilizados direta mente no ambiente do Google Colab Os dados foram extraídos estruturados em DataFrames com o auxílio da biblioteca pandas e armazenados como dicionários para alimentar o modelo Pyomo Isso permitiu que o modelo fosse executado 100 em Python sem depender do GAMS A decisão de aplicar um tempo limite de execução de 200 segundos na instância ap10ndat foi baseada em testes preliminares nos quais verificouse que o solver CBC não encontrava so lução ótima em tempo razoável mesmo para uma instância pequena O objetivo dessa limitação era observar como o modelo reagiria a diferentes níveis de serviço T com restrição de tempo e 6 avaliar o crescimento do esforço computacional Já na instância ap20ndat optamos por executar o modelo sem limite de tempo para observar até que ponto o solver seria capaz de alcançar a otimalidade em problemas maiores Abaixo apresentamos os resultados obtidos para ambas as instâncias com base nas execu ções realizadas no Pyomo utilizando o solver CBC Tabela 1 Modelo StandAlone Instância ap10ndat tempo limitado a 200s Nível de Serviço T Tempo de Execução s Status da Solução 20 28185 maxTimeLimit 25 28348 maxTimeLimit 30 28263 maxTimeLimit 35 28193 maxTimeLimit 40 28260 maxTimeLimit 45 28068 maxTimeLimit 50 28308 maxTimeLimit 55 28124 maxTimeLimit 60 28576 maxTimeLimit 65 28368 maxTimeLimit 70 28183 maxTimeLimit Tabela 2 Modelo StandAlone Instância ap20ndat sem limite de tempo Nível de Serviço T Tempo de Execução s Status da Solução 20 80879 optimal 25 84662 optimal 30 79235 optimal 35 78428 optimal 40 83601 optimal 45 82568 optimal 50 86708 optimal 55 90784 optimal 60 97970 optimal 65 85350 optimal 70 80777 optimal 7 Figura 1 Modelo StandAlone Tempo de solução para a instância ap10ndat tempo limi tado Figura 2 Modelo StandAlone Tempo de solução para a instância ap20ndat sem limite 8 Tabela 3 Modelo StandAlone Instância ap20ndat limite 1800s T Tempo s Status 20 76314 optimal 25 76534 optimal 30 75459 optimal 35 75545 optimal 40 75962 optimal 45 75748 optimal 50 75456 optimal 55 74866 optimal 60 74451 optimal 65 74081 optimal 70 74311 optimal Na Tabela 3 apresentamos os resultados da execução do modelo completo sem decompo sição utilizando a instância ap20ndat com limite de tempo ampliado para 1800 segundos A mudança no tempo máximo de execução foi feita com o objetivo de observar se o solver conseguiria alcançar soluções ótimas em todos os cenários de nível de serviço Com esse tempo mais generoso todas as execuções resultaram em soluções ótimas No entanto os tempos de resolução ainda são consideravelmente altos todos acima de 740 segun dos Isso reforça a dificuldade computacional do modelo StandAlone para instâncias maiores mesmo com tempo suficiente Esse comportamento evidencia o impacto da escalabilidade no esforço computacional do modelo além de reforçar a necessidade do uso de técnicas de decomposição em aplicações prá ticas Ainda que a solução ótima tenha sido atingida o tempo elevado pode inviabilizar esse tipo de abordagem para problemas com mais nós demandas variáveis ou múltiplos períodos Os resultados mostram claramente que mesmo com apenas 10 nós o modelo StandAlone não conseguiu resolver nenhuma instância no tempo máximo de 200 segundos Isso demonstra a alta complexidade combinatória envolvida mesmo em problemas de pequeno porte Por outro lado quando o tempo de execução não é limitado instância com 20 nós o solver consegue encontrar soluções ótimas mas a um custo computacional bastante elevado O tempo médio ultrapassa 800 segundos chegando a quase 1000 segundos nos maiores valores de T Isso evidencia que o modelo embora eficaz em termos de formulação se torna computacional mente inviável sem técnicas de decomposição em instâncias reais Esses resultados motivaram a aplicação da Decomposição de Benders nas próximas etapas deste trabalho Diante dessas limitações observadas na abordagem direta com o modelo StandAlone parti mos para a aplicação da técnica de Decomposição de Benders conforme detalhado na próxima seção 9 Resultados com Decomposição de Benders Nesta etapa o modelo foi reestruturado com base na técnica de Decomposição de Benders dividindose o problema original em duas partes um problema mestre contendo as variáveis inteiras localização de hubs e alocação de veículos e um subproblema com as variáveis contí nuas roteamento e fluxo entre nós A implementação foi realizada em Python utilizando a biblioteca Pyomo Cada iteração resolve o problema mestre com base nos cortes acumulados resolve o subproblema com as va riáveis fixadas e em seguida adiciona um novo corte ao mestre até a convergência Optamos por utilizar o solver CBC e não impusemos limite de tempo buscando observar o comporta mento natural do algoritmo Antes da execução os dados extraídos do arquivo ap10ndat foram tratados e organi zados no Python convertendo os parâmetros de custo demanda e capacidade em estruturas dicionário Esse tratamento foi essencial para alimentar corretamente o modelo iterativo de Benders permitindo múltiplas chamadas ao subproblema com diferentes valores fixados da va riável z A tabela a seguir apresenta os resultados obtidos com a decomposição de Benders na ins tância ap10ndat Como o solver CBC não fornece diretamente estatísticas como número de nós na árvore de BranchandBound gap de otimalidade e número de planos cortantes cuts essas colunas foram deixadas em branco Tabela 4 Decomposição de Benders Instância ap10ndat Nível de Serviço T Tempo s Status Nós Gap Cortes 20 70697 optimal 25 71466 optimal 30 71212 optimal 35 72753 optimal 40 72961 optimal 45 72901 optimal 50 73453 optimal 55 72321 optimal 60 72337 optimal 65 73208 optimal 70 74263 optimal Os tempos registrados estão todos abaixo de 750 segundos o que representa uma melhora significativa em relação ao modelo StandAlone com tempo limitado a 200 segundos que se quer conseguiu obter solução ótima Isso mostra que a técnica de decomposição foi eficaz mesmo sem limitação explícita de tempo e sem ajustes finos adicionais no solver 10 Figura 3 Tempo de solução com Decomposição de Benders Instância ap10ndat A Figura 3 mostra que o tempo de execução se manteve relativamente estável à medida que o nível de serviço T aumentou Isso sugere que o algoritmo consegue lidar bem com variações no tempo máximo de rota ao contrário do modelo StandAlone que se tornava inviável com o aumento de T Os resultados reforçam a importância da separação estrutural entre decisões estratégicas e operacionais A decomposição de Benders permite lidar com instâncias maiores e mais comple xas mantendo a qualidade das soluções e reduzindo o esforço computacional necessário para encontrar soluções ótimas Resultados com Cortes ParetoÓtimos Nesta etapa foi aplicada a técnica de cortes ParetoÓtimos conforme proposta por Papa dakos 2008 na formulação com Decomposição de Benders A lógica desse aprimoramento é evitar a adição de cortes fracos ao modelo mestre buscando planos de corte que maximizem o ganho informativo em cada iteração A estratégia foi implementada a partir dos arquivos bdm2mhlrpmvpomd e bdm2mhlrpmvporun adaptados para o ambiente Pyomo em Python Diferente do Benders clássico que pode precisar de várias iterações para convergir a versão com ParetoÓtimos mostrou desempenho altamente eficiente o algoritmo convergiu em apenas uma iteração para todos os valores de T Isso significa que o corte gerado já foi suficiente para atingir a solução ótima do problema com a configuração inicial do mestre A tabela a seguir mostra os tempos e informações das execuções para a instância ap20ndat 11 Tabela 5 Benders com Cortes ParetoÓtimos Instância ap20ndat T Tempo s LB UB Gap Iterações 20 0156 909e10 909e10 00 1 25 0152 909e10 909e10 00 1 30 0064 909e10 909e10 00 1 35 0048 909e10 909e10 00 1 40 0045 909e10 909e10 00 1 45 0045 909e10 909e10 00 1 50 0046 909e10 909e10 00 1 55 0044 909e10 909e10 00 1 60 0047 909e10 909e10 00 1 65 0045 909e10 909e10 00 1 70 0044 909e10 909e10 00 1 É importante destacar que o valor da função objetivo LB UB 909 1010 permaneceu constante porque a configuração do modelo e os dados de entrada resultaram em uma solução robusta desde a primeira execução do mestre Isso evidencia o poder da técnica de corte Pareto Ótimo em encontrar o corte mais eficiente já na primeira tentativa Figura 4 Comparação de tempo Benders clássico vs ParetoÓtimos 12 Figura 5 Gap de otimalidade Benders com ParetoÓtimos ap20ndat Na Figura 4 observase que o tempo de execução foi drasticamente reduzido com o uso de cortes ParetoÓtimos em comparação ao Benders clássico Mesmo em instâncias maiores ou com valores mais altos de T a solução é encontrada quase instantaneamente A Figura 5 reforça esse comportamento com o gap de otimalidade zerado desde a primeira iteração Estes resultados demonstram o ganho computacional substancial proporcionado por estra tégias mais sofisticadas de geração de cortes sendo especialmente úteis em aplicações onde a escalabilidade do modelo é crucial Interpretação dos Resultados A análise dos resultados obtidos a partir das diferentes abordagens computacionais eviden cia a importância da escolha do método de solução para problemas de grande porte como o M2MHLRP A execução do modelo StandAlone embora conceitualmente simples mostrouse limitada Na instância com 10 nós mesmo após 200 segundos nenhuma solução ótima foi encontrada Já para a instância com 20 nós as soluções foram ótimas mas os tempos de execução foram excessivamente altos acima de 800 segundos Esses resultados reforçam que a complexidade do problema cresce rapidamente com o aumento do tamanho da instância e do parâmetro de nível de serviço T Diante disso a técnica de Decomposição de Benders foi implementada em Python utili zando a biblioteca Pyomo Essa técnica divide o problema em duas partes o problema mestre com variáveis inteiras e decisões estratégicas e o subproblema com variáveis contínuas e de cisões operacionais A resolução iterativa entre esses dois modelos permite reduzir o esforço 13 computacional direto facilitando o tratamento de instâncias maiores Ainda mais eficiente foi a versão com cortes ParetoÓtimos baseada na proposta de Pa padakos 2008 Com essa estratégia foi possível atingir a convergência do modelo logo na primeira iteração com tempos inferiores a 02 segundos em todos os testes Essa melhoria se deve à geração de cortes mais informativos que evitam a necessidade de múltiplas iterações O uso dessa abordagem é particularmente útil em contextos reais onde tempo e recursos compu tacionais são limitados Em resumo a modelagem e tratamento dos dados em Python permitiram controlar direta mente as variáveis iterar dinamicamente entre os modelos integrar com solvers como o CBC e gerar visualizações gráficos e tabelas que facilitam a análise de desempenho de cada aborda gem testada 7 Conclusão Este trabalho teve como objetivo analisar o esforço computacional necessário para resolver o problema MultiVehicle MultiCommodity Hub Location Routing Problem M2MHLRP através de técnicas de Programação Linear InteiraMista PLIM além de investigar os ganhos proporcionados pela aplicação da Decomposição de Benders e pela estratégia de cortes Pareto Ótimos Com base nas simulações realizadas observouse que O modelo StandAlone embora resolva o problema por completo tornase inviável em instâncias maiores devido ao elevado tempo de processamento A Decomposição de Benders é uma ferramenta poderosa para reduzir o número de variá veis binárias e facilitar a convergência do modelo A introdução dos cortes ParetoÓtimos acelerou ainda mais a resolução proporcionando convergência em apenas uma iteração e mantendo a solução ótima O uso do Python e da biblioteca Pyomo possibilitou a construção de modelos flexíveis reprodutíveis e com controle preciso sobre cada etapa da resolução Assim concluise que a combinação entre técnicas de decomposição e heurísticas inteligen tes de corte não apenas torna o modelo mais escalável como também viabiliza sua aplicação em cenários reais como cadeias logísticas urbanas centros de distribuição e redes de transporte multimodal 14 Referências 1 PAPADAKOS N Practical enhancements to the MagnantiWong method Operations Re search Letters v 36 n 4 p 444449 2008 2 HART W E et al Pyomo Optimization Modeling in Python Springer 2nd Edition 2017 15 Apêndices A Código Python Execução do Modelo StandAlone I m p o r t a o das bibliotecas import pyomoenviron as pyo from pyomoopt import SolverFactory Modelo StandAlone resumo model pyoConcreteModel D e f i n i e s de sets par metros vari veis R e s t r i e s e f u n o objetivo Solver solver SolverFactorycbc result solversolvemodel teeTrue B Código Python Decomposição de Benders Modelo mestre e subproblema separados Loop de i t e r a e s entre mestre e subproblema A d i o de cortes ao mestre Exemplo de i t e r a o for t in listadeT resolvemestre resolvesubproblema geracorte C Código Python Benders com Cortes ParetoÓtimos M o d i f i c a o do subproblema dual para gerar cortes dominantes Baseado em Papadakos 2008 Ajuste do subproblema para buscar corte Pareto timo M a x i m i z a o da v i o l a o do corte para uma s o l u o do mestre D Trecho de Tratamento dos Dados import pandas as pd Leitura e o r g a n i z a o dos dados do arquivo dat with openap10ndat as f linhas freadlines 16 E x t r a o de par metros como dist ncia demanda capacidade etc Convers o para dicion rios Python usados no Pyomo 17