·

Engenharia de Produção ·

Pesquisa Operacional 2

Send your question to AI and receive an answer instantly

Ask Question

Preview text

UM ESTUDO DE DIFERENTES METAHEURÍSTICAS PARA OTIMIZAR A ESCALA DE MOTORISTAS DO TRANSPORTE PÚBLICO URBANO Allexandre Fortes da Silva Reis Orientador Prof Dr Gustavo Peixoto Silva Sumário 2 Objetivos Metodologia Problema da Programação de Tripulações Características das Jornadas Diárias PPT como Problema de Particionamento Estrutura de Vizinhança Clássica Busca em Vizinhança de Grande Porte VLNS Vizinhança de Troca Cíclica Busca em Vizinhança Variável VNS Iterated Local Search ILS Resolvendo um Caso Real Resultados e Discussões Considerações finais Produtos obtidos Agradecimentos Objetivos 3 Resolver o Problema da Programação de Tripulações do Transporte Urbano utilizando metaheurísticas e apresentar as vantagens que o uso de métodos heurísticos propiciam na resolução de um problema caso real Específicos Otimizar o PPT utilizando a metaheurística Variable Neighborhood Search VNS com duas formas de busca local Variable Neighborhood Descent VND e Very Largescale Neighborhood Search VLNS Otimizar o PPT utilizando a metaheurística Iterated Local Search ILS com duas formas de busca local Método de Busca Primeiro de Melhora e VLNS Comparar os resultados obtidos com as diferentes metaheurísticas e suas duas versões e confrontálas com a solução adotada pela empresa Metodologia Revisão Bibliográfica Pesquisa aplicada Abordagem quantitativa axiomática Modelagem e Simulação Baseando nos dados e na bibliografia Definição do problema Construção do modelo Solução do Modelo Validação do Modelo Implementação da Solução Foi utilizada a linguagem CC no ambiente C Builder 5 4 Problema da Programação de Tripulações 5 Dada a programação da frota devese criar as Jornadas Diárias de Trabalho para os motoristas tal que Sejam minimizados os custos com salários horas extras A escala atenda às restrições legais e operacionais do problema Este problema é dito Problema de Programação da Tripulação ou PPT sigla que utilizaremos doravante Características das Jornadas Diárias 6 Jornadas Tarefas Viagens Jornada tipo pegada simples normal duração de 0640 com descanso mínimo de 20 minutos Jornada tipo dupla pegada horário de pico Existe um intervalo entre duas viagens 2 horas A folga 2 horas não é remunerada e não há folga descanso Tempo máximo de 2 horas extras por jornada diária Tempo mínimo de 11 horas entre o final da jornada e seu início no dia seguinte PPT como Problema de Particionamento 7 A conjunto de todas as tarefas viagens associadas à frota em operação Si o conjunto das tarefas executadas na jornada i CkSk custo fixo custo variável da jornada k Obs CkSk não depende das tarefas realizadas pelas outras jornadas J k Este é um problema NPDifícil para o qual não existe algoritmo polinomial Fischetti et al 1987 𝑀𝑖𝑛 𝐶𝑆 𝐾 𝑘1 𝐶𝑘ሺ𝑆𝑘ሻ 𝑆 ሺ𝑆1𝑆2𝑆𝑘ሻ é 𝑝𝑎𝑟𝑡𝑖çã𝑜 𝑑𝑒 𝐴 Estrutura de Vizinhança Clássica 8 Para k 1 troca uma única tarefa por vez Solução s A B C D E F G i j Vizinho de s A E B C D F G A E i j 9 Ainda para k 1 pode haver apenas a realocação da tarefa Solução s A B C D E F G i j B C D F G A E i j Estrutura de Vizinhança Clássica 10 Solução s A B C D E F G i j B C D F G A E i j A realocação ou troca é feita se e somente se for válida Ainda para k 1 pode haver apenas a realocação da tarefa Estrutura de Vizinhança Clássica 11 Para k 2 são selecionadas duas tarefas por vez Solução s A B C D E F G i j B C D F G A E i j Estrutura de Vizinhança Clássica 12 A B C D E F G i j B C D F G A E i j Solução s Vizinho de s Para k 2 são selecionadas duas tarefas por vez Estrutura de Vizinhança Clássica 13 Para k 3 são selecionadas três tarefas por vez Solução s A B C D E F G i j B C D F G A E i j Estrutura de Vizinhança Clássica 14 Solução s A B C D E F G i j B C D F G A E i j Vizinho de s Para k 3 são selecionadas três tarefas por vez Estrutura de Vizinhança Clássica Busca em Vizinhança de Grande Porte VLNS 15 Em inglês chamada Very Largescale Neighborhood Search Está baseada na construção de um Grafo de Melhorias GS construído para cada solução do problema Em GS cada nó i corresponde à tarefa ti ϵ S Um arco i j representa a realocação da tarefa ti da dupla Sti para a dupla Stj Simultaneamente a tarefa tj deixa a dupla Stj Um Ciclo Negativo em GS representa uma troca em cadeia cíclica entre jornadas que necessariamente melhora a solução corrente Portanto dado um GS procuramos por Ciclos Negativos em G Vizinhança de Troca Cíclica 16 Dupla 1 Dupla 1 Tarefa 1 Tarefa 2 Tarefa 3 Dupla 3 Dupla 3 Dupla 2 Dupla 2 Dupla 4 Dupla 4 Tarefa 10 Tarefa 11 Tarefa 12 Tarefa 7 Tarefa 8 Tarefa 9 Tarefa 4 Tarefa 5 Tarefa 6 Troca Cíclica sequência de tarefas t1t2 t3trt1 com t1 t2 t3 tr pertencente a veículos diferentes Exemplo t1t4 t10t7t1 Vizinhança de Troca Cíclica 17 Dupla 2 Dupla 2 Dupla 1 Dupla 1 Tarefa 1 Tarefa 2 Tarefa 3 Dupla 3 Dupla 3 Dupla 4 Dupla 4 Tarefa 10 Tarefa 11 Tarefa 12 Tarefa 7 Tarefa 8 Tarefa 9 Tarefa 4 Tarefa 5 Tarefa 6 Então a troca cíclica t1t4 t10t7t1 Vizinhança de Troca Cíclica 18 Dupla 2 Dupla 2 Dupla 1 Dupla 1 Tarefa 1 Tarefa 2 Tarefa 3 Dupla 3 Dupla 3 Dupla 4 Dupla 4 Tarefa 10 Tarefa 11 Tarefa 12 Tarefa 8 Tarefa 9 Tarefa 4 Tarefa 5 Tarefa 6 Troca em Caminho sequência de tarefas t1t2 t3tr com t1 t2 t3 tr pertencente a veículos diferentes Exemplo t1t4 t10Dupla 3 Vizinhança de Troca Cíclica 19 O Tamanho da vizinhança para K trocas é de OnK vizinhos On2 para K 2 Onde K varia de 2 até o total de duplas A VLNS que é Kopt realiza a busca do tipo 2opt e ainda muito mais Assim os ótimos locais obtidos devem ser superiores àqueles obtidos por trocas entre duas jornadas feitas tradicionalmente Busca em Vizinhança Variável VNS 20 Em inglês Variable Neighborhood Search Método de busca local que explora o espaço de soluções através de trocas sistemáticas de estruturas de vizinhança Explora vizinhanças gradativamente mais distantes do ótimo local Focaliza a busca em torno de uma nova solução somente se um movimento de melhora é realizado Método de Busca Clássico é o VND Método de Descida em Vizinhança Variável Variable Neighborhood Descent N1 s s s s será a nova solução ótima local se fs fs fazendo uma busca a partir de s é obtida s 21 Busca em Vizinhança Variável VNS N1 N2 s s s N1 22 Busca em Vizinhança Variável VNS N1 N2 Nr s s 23 Busca em Vizinhança Variável VNS Iterated Local Search ILS 24 Dividido em 4 partes centrais Solução Inicial Gerada Busca Local Perturbação da Solução Critério de Aceitação da Solução Sendo a Busca Local considerada uma caixa preta Para este trabalho foi utilizada o Método Primeiro de Melhora e a VLNS 25 Iterated Local Search ILS fs1 fs0 fs fs2 s1 Busca Local s0 s Busca Local s s2 Critério de Aceitação s s0 s Perturbação s1 fs s Perturbação s1 s Busca Local s s2 Critério de Aceitação s s fs Resolvendo um Caso Real 26 Conjunto de sete problemas referentes a uma semana de operação de uma empresa que atua no sistema de transporte público de Belo Horizonte Os resultados apresentados a seguir foram divididos em duas etapas em função dos pesos atribuídos ao total de duplas pegadas contido na solução Função objetivo utilizada trip tot i i i ppt peg dupla w extra hora w Fixo Custo C 1 2 1 Resultados e Discussões 27 Testes em duas etapas 1 VNSClássico e VNSVLNS considerando as variações dos parâmetros peso para a dupla pegada e o número máximo de troca de veículos realizada durante uma jornada até 2 trocas 2 VNSClássico e VNSVLNS ILSClássico e ILSVLNS Foram utilizados os parâmetros dos primeiros testes preliminares ou seja menor peso para dupla pegada e no máximo uma troca de veículos por jornada diária Resultados e Discussões 28 Heurísticas Segunda Terça Quarta Quinta Sexta Sábado Domingo HE VNS Clássico 1186 1612 1559 987 1641 6620 9981 VNSVLNS 4157 3428 2694 4120 3479 507 2746 Jornadas VNS Clássico 1269 1462 1074 1296 1355 1855 2353 VNSVLNS 1045 1000 940 802 903 1371 1912 DP VNS Clássico 73333 186667 132000 222500 800000 VNSVLNS 21667 36667 28000 32500 130000 FO VNS Clássico 1034 1158 767 931 1001 1560 2088 VNSVLNS 1032 987 912 812 896 1303 1807 Comparação das soluções considerando uma troca de veículo e menor peso para as Duplas Pegadas Empresa VNS Empresa Resultados e Discussões 29 Comparação das soluções considerando duas trocas de veículo e menor peso para as Duplas Pegadas Heurísticas Segunda Terça Quarta Quinta Sexta Sábado Domingo HE VNS Clássico 1186 1040 723 428 216 6128 6172 VNSVLNS 4157 3498 4140 5542 4796 2085 3488 Jornadas VNS Clássico 1269 1462 1141 1111 1226 1855 2353 VNSVLNS 1045 1000 805 802 903 1371 1912 DP VNS Clássico 73333 183333 128000 200000 660000 VNSVLNS 21667 23333 20000 32500 160000 FO VNS Clássico 1034 1171 858 792 961 1560 2088 VNSVLNS 1032 1006 820 824 885 1303 1807 Diminuição apenas nas Horas Extras Empresa VNS Empresa Resultados e Discussões 30 Heurísticas Segunda Terça Quarta Quinta Sexta Sábado Domingo HE VNS Clássico 1306 1251 960 144 732 7411 7143 VNSVLNS 2488 1185 3647 3539 1873 418 235 Jornadas VNS Clássico 1045 1231 940 617 839 1613 2059 VNSVLNS 1045 1231 604 864 1032 1210 1618 DP VNS Clássico 38333 93333 50000 57500 220000 VNSVLNS 8333 26667 12000 32500 110000 FO VNS Clássico 160 130 1372 092 114 561 1317 VNSVLNS 864 917 1692 511 695 802 1241 Comparação das soluções considerando uma troca de veículo e maior peso para as Duplas Pegadas Empresa VNS Empresa Resultados e Discussões 31 Heurísticas Segunda Terça Quarta Quinta Sexta Sábado Domingo HE VNS Clássico 798 407 553 543 199 7963 2653 VNSVLNS 4051 3201 4503 5130 3892 904 093 Jornadas VNS Clássico 1045 1154 671 679 774 1774 2059 VNSVLNS 970 923 671 741 1032 1129 1471 DP VNS Clássico 38333 83333 36000 65000 230000 VNSVLNS 10000 16667 12000 25000 90000 FO VNS Clássico 303 221 1379 029 211 833 1326 VNSVLNS 907 865 1812 531 757 887 1296 Comparação das soluções considerando duas trocas de veículo e maior peso para as Duplas Pegadas Empresa VNS Empresa Resultados e Discussões 32 Segunda etapa de testes Empresa VNS Somente uma troca de veículo e peso padrão para DP Heurística Segunda Terça Quarta Quinta Sexta Sábado Domingo Jornadas VNS Clássico 1045 1077 805 741 968 1452 1912 VNSVLNS 1119 1077 738 802 839 1290 1912 HE VNS Clássico 3682 2970 3972 4914 3075 1060 2393 VNSVLNS 2201 2576 3898 3927 3614 513 3408 DP VNS Clássico 28333 40000 34000 75000 290000 VNSVLNS 20000 53333 30000 32500 150000 FO VNS Clássico 1071 1170 805 821 950 1513 1791 VNSVLNS 1080 1053 719 780 822 1210 1792 Empresa VNS Empresa Resultados e Discussões 33 Segunda etapa de testes Empresa ILS Somente uma troca de veículo e peso padrão para DP Heurística Segunda Terça Quarta Quinta Sexta Sábado Doming o Jornadas ILS Clássico 970 1077 738 679 839 1452 1618 ILSVLNS 1119 1154 738 679 903 1290 1618 HE ILS Clássico 3938 2716 4159 5065 3717 1466 1113 ILSVLNS 2571 2411 4151 4943 3183 718 1453 DP ILS Clássico 23333 56667 36000 50000 170000 ILSVLNS 20000 53333 30000 32500 150000 FO ILS Clássico 951 1024 723 682 821 1345 1543 ILSVLNS 1086 1099 735 705 883 1226 1555 Empresa ILS Empresa Resultados e Discussões Segunda Terça Quarta Quinta Sexta Sábado Domingo HE 1759 795 297 057 156 309 3104 Jornadas 083 086 073 067 071 189 364 DP 2174 2667 909 5000 4667 4706 3000 FO 017 080 077 126 074 338 288 34 Segunda etapa de testes VNSClássico ILSVLNS VNSCl á ssico ILS VLNS VNSCl ássico Considerações finais 35 Primeira Etapa Metaheurística VNS Ambas versões do VNS produzem soluções melhores que as da empresa O VNS Clássico é eficiente para resolver o PPT mas modifica consideravelmente as características da solução inicial VNS Clássico produz escalas com um número menor de jornadas como nos problemas de quarta sábado e domingo Mas como estas soluções apresentam um número maior de horas extras e de duplas pegadas seus custos acabam sendo superiores A combinação VNSVLNS produziu soluções mais compatíveis com as soluções da empresa e ainda mais econômicas do que a Busca Clássica A flexibilização da operação leva à redução de custos operacionais Considerações finais Segunda Etapa Metaheurísticas ILS e VNS Número consideravelmente menor de Duplas Pegadas do que na etapa anterior em ambas versões Duas metaheurísticas estudadas produziram soluções melhores do que a empresa As melhores soluções foram obtidas pela versão VNSClássico mas diferença entre os resultados é muito pequena A versão ILSVLNS produziu soluções melhores no que diz respeito à adequação da realidade do problema 36 Considerações finais O uso da técnica VLNS supera o Método Primeiro de Melhora Capacidade da busca VLNS de produzir soluções de baixo custo financeiro com grande qualidade operacional O método VLNS não provoca modificações tão drásticas nas características da solução inicial empresa ainda capaz de reduzir os custos com jornadas e horasextras 37 Produtos Obtidos Durante o desenvolvimento deste trabalho e da iniciação científica que o impulsionou foram gerados os seguintes artigos científicos relacionados ao tema proposto ARTIGO COMPLETO PUBLICADO EM CONGRESSO 1 REIS Allexandre Fortes S SILVA Gustavo Peixoto 2011 Um Estudo de Diferentes Métodos de Busca e a Metaheurística VNS para Otimizar a Escala de Motoristas de Ônibus Urbano In XXV ANPET Congresso de Pesquisa e Ensino em Transportes Panorama Nacional da Pesquisa em Transportes 2011 p 23742385 Este trabalho recebeu o Prêmio CNT de Produção Acadêmica de 2011 2 SILVA Gustavo Peixoto REIS Allexandre Fortes S 2011 A VNS Heuristic with Different Search Methods to Solve the Crew Scheduling Problem from Urban Transit Companies In XXXII Iberian LatinAmerican Congress on Computational Methods in Engineering Proceedings p 154166 3 REIS Allexandre Fortes S SILVA Gustavo Peixoto 2013 A Study of Different Metaheuristics to solve the Urban Crew Scheduling Problem In 13th WCTR World Conference on Transport Research July 1518 2013 Rio de Janeiro Brazil CAPÍTULO DE LIVRO 1 REIS Allexandre Fortes S SILVA Gustavo Peixoto 2012 Um Estudo de Diferentes Métodos de Busca e a Metaheurística VNS para Otimizar a Escala de Motoristas de Ônibus Urbano Transporte em Transformação XVI Trabalhos vencedores do Prêmio CNT Produção Acadêmica 2011 p 4564 CNTANPET 38 Agradecimentos 39 CNPq Professor Gustavo Peixoto Professores Magno e André DEPRO e FG Mãe Fê Carol Anninha família e amigos Obrigado