Otimizacao da Escala de Motoristas no Transporte Publico Urbano - Estudo com Metaheuristicas

UNIVERSIDADE FEDERAL DE OURO PRETO ESCOLA DE MINAS DEPARTAMENTO DE ENGENHARIA DE PRODUÇÃO ALLEXANDRE FORTES DA SILVA REIS UM ESTUDO DE DIFERENTES METAHEURÍSTICAS PARA OTIMIZAR A ESCALA DE MOTORISTAS DO TRANSPORTE PÚBLICO URBANO OURO PRETO MINAS GERAIS BRASIL ABRIL DE 2013 i UNIVERSIDADE FEDERAL DE OURO PRETO ESCOLA DE MINAS DEPARTAMENTO DE ENGENHARIA DE PRODUÇÃO ALLEXANDRE FORTES DA SILVA REIS UM ESTUDO DE DIFERENTES METAHEURÍSTICAS PARA OTIMIZAR A ESCALA DE MOTORISTAS DO TRANSPORTE PÚBLICO URBANO OURO PRETO MINAS GERAIS BRASIL ABRIL DE 2013 ii ALLEXANDRE FORTES DA SILVA REIS allexandrefsrgmailcom UM ESTUDO DE DIFERENTES METAHEURÍSTICAS PARA OTIMIZAR A ESCALA DE MOTORISTAS DO TRANSPORTE PÚBLICO URBANO Monografia apresentada ao Curso de Engenharia de Produção da Universidade Federal de Ouro Preto como parte dos requisitos para a obtenção de Grau em Engenharia de Produção Professor orientador Prof Dr Gustavo Peixoto Silva Área de concentração Pesquisa Operacional OURO PRETO MG 2013 iii Monografia defendida e aprovada em ABRIL de 2013 pela comissão avaliadora constituída pelos professores Prof Dr Gustavo Peixoto Silva Orientador Prof Me Magno Silvério Professor Convidado Prof Me André Luís Silva Professor Convidado iv Dedico esse trabalho a todos aqueles que me incentivaram familiares e amigos Mãe Pai Carol Anninha e Fê por todo apoio incessante A todos os mestres que contribuiram para minha formação v Agradecimentos Agradeço a minha mãe Cláudia por sempre estar presente e me mostrar o melhor caminho a ser seguido pelos conselhos e zelo constante Ao meu pai José pela sabedoria de que o conhecimento é a única coisa que ninguém pode retirar de nós Agradeço também as minhas amadas irmãs Carol e Anninha por toda amizade amor e carinho além da união e apoio em todos os momentos Agradeço imensamente a minha namorada amiga e confidente Fê por todo amor alegria apoio incessante e horas de estudos juntos do inicio ao fim Você foi essencial para essa conquista Aos meus tios as e primos as às famílias Fortes Cota Matos e Braga que me acompanharam apoiaram e torceram por mim durante esta caminhada Aos meus irmãos do handebol Arthur Gustavo Edson Felipe Túllio e Júlio Aos meus amigos as Vinícius Fortes Leila Amanda Vinícius Lage Tom Pepê Gabi Téis Victor Lydi Viviane Geisa Betinha Samuel Renato Aos amigos do curso e da turma de Produção 081 especialmente Hernando Guilherme Cêra Pé Elisa Jéssica Silvin Débora e Augusto por todos os desafios superados À UFOP Escola de Minas DEPRO e demais professores pelos conhecimentos transmitidos e pela minha formação acadêmica de qualidade Sou eternamente grato Ao professor Gustavo Peixoto Silva pelo ensino e dedicação durante orientação deste trabalho e da iniciação científica À Fundação Gorceix e ao CNPq pelas oportunidades e apoio concedidos vi Não existe triunfo sem perda não há vitória sem sacrifício Do filme O Senhor dos Anéis O Retorno do Rei vii viii RESUMO Este trabalho explora as metaheurísticas Variable Neighborhood Search VNS e Iterated Local Search ILS associadas a diferentes métodos de busca local para resolver o Problema de Programação de Tripulações do Sistema de Transporte Público Na implementação das metaheurísticas foi utilizada um método de busca clássica de descida e o método de busca local denominado Very Largescale Neighborhood Search VLNS que se baseia em algoritmos de rede Inicialmente as metaheurísticas foram implementadas nas suas formas Para o VNS normalmente utilizase o Variable Neighborhood Descent VND como procedimento de busca local e para o ILS a literatura deixa a critério dos pesquisadores a escolha da heurística de refinamento a ser empregada como busca local Dessa forma utilizouse inicialmente o Método Primeiro de Melhora First Improvement Method sendo obtidas as versões Clássicas das metaheurísticas Posteriormente para ambas metaheurísticas foi utilizada a técnica VLNS como procedimento de busca local A técnica VLNS realiza uma busca em um espaço maior do que as buscas clássicas permitindo a realocação de tarefas em uma série de diferentes tripulações Consequentemente esperase que as soluções ótimas locais sejam melhores do que aquelas obtidas pelos métodos clássicos As versões do VNS e ILS foram aplicadas a um conjunto de problemas de uma empresa que opera em Belo Horizonte produzindo resultados melhores do que as soluções adotadas pela empresa Os resultados mostram também que as soluções obtidas pelos métodos MetaheurísticaVLNS apresentam características mais apropriadas à realidade do que aquelas obtidas pelo método Clássico Palavras chave Problema da Programação de Tripulação Metaheurísticas Variable Neighborhood Search Iterated Local Search Very Largescale Neighborhood Search ix ABSTRACT This paper explores different methods associated with metaheuristics Variable Neighborhood Search VNS and Iterated Local Search ILS associated with different local search methods to solve the Crew Scheduling Problem from Public Transportation System Into implementation of metaheuristics a classical descent method and other one based in network algorithm called Very Largescale Neighborhood Search VLNS were used Initially the metaheuristics were implemented in their own forms For the VNS normally the classical Variable Neighborhood Descent VND as local search method and for ILS the literature allows the researchers choose the refinement heuristic Thereby firstly the First Improvement Method was used to reach the Classical forms of both metaheuristics and after also the VLNS The VLNS perform search into a larger space than the Classical allowing tasks reallocation in a sequence of different crews Consequently local optimal solutions must be better than those obtained by classical search methods Both versions of VNS and ILS have been applied to a set of problems from a company that operates in Belo Horizonte producing better results than the solutions adopted by the company The results also show that the solutions obtained by the VNSILS VLNS are more economical and present characteristics more appropriate to the operation than those obtained by the Classical methods Keyworks Crew Scheduling Problem Metaheuristics Variable Neighborhood Search Iterated Local Search Very Largescale Neighborhood Search x LISTA DE SIGLAS PPT Problema da Programação da Tripulação CSP Crew Scheduling Problem VNS Variable Neighborhood Search VND Variable Neighborhood Descent ILS Iterated Local Search VLNS Very Largescale Neighborhood Search BVGP Busca em Vizinhança de Grande Porte CLT Consolidação das Leis do Trabalho xi SUMÁRIO 1 INTRODUÇÃO 1 11 Formulação do problema 1 12 Justificativa 1 13 Objetivos 2 131 Geral 2 132 Específicos 2 14 Estrutura do trabalho 3 2 METODOLOGIA 4 3 REVISÃO BIBLIOGRÁFICA 4 4 MODELAGEM DO PROBLEMA 6 41 Função Objetivo 7 42 Solução Inicial 8 43 Métodos Clássicos de Busca Local 8 431 Estrutura de Vizinhança RealocaTroca 8 432 Método da Descida 9 433 Método da Primeira Solução de Melhora 9 434 Método de Descida em Vizinhança Variável VND 10 44 Método de Busca em Vizinhança de Grande Porte VLNS para resolver o PPT 11 441 Estrutura de Vizinhança de Troca Cíclica 11 442 Grafo de Melhoria para o PPT 12 443 Identificando um Ciclo Válido 13 45 Heurísticas para a Resolução do PPT 13 451 Busca em Vizinhança Variável VNS 13 452 A Metaheurística Iterated Local Search ILS 14 4521 Perturbação da Solução 15 4522 Critério de Aceitação 16 5 RESULTADOS COMPUTACIONAIS 16 51 Resultados da primeira etapa A metaheurística VNS 16 511 Soluções com menor peso para as duplas pegadas 17 4111 Resultados considerando no máximo uma troca de veículo por jornada 17 4112 Resultados considerando no máximo duas trocas de veículo por jornada 19 512 Soluções com maior peso para as duplas pegadas 20 5121 Resultados considerando no máximo uma troca de veículo por jornada 20 5122 Resultados considerando no máximo duas trocas de veículo por jornada 22 52 Resultados da segunda etapa As metaheurísticas VNS e ILS 23 xii 521 Soluções obtidas pelo VNS 23 522 Soluções obtidas pelo ILS 25 523 Comparando o desempenho VNS ILS 26 6 ANÁLISE DOS RESULTADOS 26 61 Análise dos Resultados da Primeira Etapa Metaheurística VNS 27 62 Análise dos Resultados da Segunda Etapa Metaheurísticas ILS e VNS 27 7 CONCLUSÕES 28 8 PRODUTOS OBTIDOS 29 81 Artigo completo publicado em congresso 29 82 Capítulo de livro 29 REFERÊNCIAS BIBLIOGRÁFICAS 30 1 1 INTRODUÇÃO 11 Formulação do problema O Problema da Programação das Tripulações PPT consiste em determinar o número mínimo de tripulações de forma a cobrir totalmente a programação de veículos realizada previamente também chamado de Problema da Programação de Veículos PPV A solução do PPT envolve o sequenciamento das atividades dos motoristas gerando um conjunto de jornadas de trabalho As jornadas devem satisfazer diversas restrições devido às leis trabalhistas acordos sindicais e ainda as regras operacionais das empresas Desta forma Fischetti et al 1987 mostraram que o problema se torna NPdifícil para o qual não existe algoritmo polinomial que obtenha a solução ótima A abordagem clássica para tratar esse problema formulao como um problema de programação linear inteira de recobrimento ou particionamento set covering ou set partitioning model Entretanto modelos exatos são limitados quando aplicados a problemas de grande porte Assim a utilização de métodos heurísticos para resolver problemas práticos os quais são normalmente de grande porte é uma interessante alternativa pois por menor que seja a melhora trará resultados tangíveis para um problema real Embora o Problema de Programação da Tripulação tenha sido largamente estudado e aplicado nos países mais desenvolvidos um exemplo é o Scheduling and Constraint Management Group da Universidade de Leeds no Reino Unido suas técnicas de resolução são pouco difundidas e modelos de otimização raramente são utilizados na realidade brasileira Isso se deve em parte pela falta de dados e organização necessária por parte das empresas do setor como também pela carência de modelos que representem a realidade operacional brasileira 12 Justificativa Atualmente muitas empresas buscam usar ao máximo as inovações tecnológicas para melhorar o desempenho de seus processos Porém as empresas do sistema de transporte público brasileiro ainda fazem pouco uso de softwares e modelos de otimização para alocar os seus equipamentos e a mão de obra necessária para a sua operação isto é os veículos e as suas tripulações motoristas e cobradores Isso se deve porque o uso de modelos de otimização requer o levantamento de dados precisos o cumprimento das regras especificadas a flexibilização da operação do sistema entre outras práticas ainda pouco 2 difundidas no setor Por outro lado em sistemas mais exigentes como no sistema de transporte aéreo a utilização de modelos de otimização para montar as escalas de suas tripulações é uma prática quase obrigatória Além de possibilitar a geração de escalas viáveis os modelos conseguem reduzir os custos com esta mão de obra que no caso do transporte aéreo são muito elevados De acordo com Ferraz e Torres 2004 a oferta de um transporte público urbano eficiente e de qualidade é de fundamental importância pois constitui uma forma de transporte de aspecto social e democrático sendo acessível a pessoas de baixa renda e que não podem dirigir Mantendose tanto a eficiência quanto a qualidade há também a melhoria na qualidade de vida da população mediante a redução de poluição ambiental congestionamentos e acidentes de trânsito quando ocorre a troca dos carros pelos ônibus Com a obtenção de menores custos na alocação dos tripulantes e programação estes podem ser repassados aos usuários Assim todos os atores do sistema obterão satisfação com o desenvolvimento de modelos e o seu uso na alocação das atividades dos condutores Dessa forma o estudo e a implementação de métodos eficientes para a resolução do problema de programação de tripulações do sistema de transporte público assim como a sua difusão no meio são tarefas importantes não somente para reduzir os custos operacionais mas também para disseminar a utilização de sistemas de apoio à decisão pela alta gerência das empresas que atuam neste setor 13 Objetivos 131 Geral Resolver o Problema da Programação de Tripulações do Transporte Urbano utilizando técnicas metaheurísticas apresentando as vantagens que o uso de métodos heurísticos de otimização propiciam na resolução problemas desta natureza oriundos de um caso real 132 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 3 Comparar os resultados obtidos com as diferentes metaheurísticas e suas duas versões e confrontálas com a solução adotada pela empresa 14 Estrutura do trabalho Neste capítulo introdutório é apresentado o assunto a ser estudado como forma de nortear o propósito da pesquisa A formulação do problema a justificativa e os objetivos gerais e específicos a serem alcançados pelo estudo foram apresentados Dessa forma o tema do trabalho bem como sua importância dentro contexto acadêmicosócioempresarial considerando os motivos de ordem teórica e prática que justificam a pesquisa são ilustrados nesse capítulo No capítulo 2 a metodologia científica utilizada no trabalho é classificada A seguir no capítulo 3 é apresentada a fundamentação teórica do trabalho a importância de uma programação da tripulação eficiente do transporte público as dificuldades enfrentadas para a realização das mesmas os tipos de métodos exatos que já foram utilizados e seus resultados a ideia central das metaheurísticas as vantagens que estas podem prover e quais métodos foram implementados no estudo O capítulo 4 apresenta de forma detalhada como o problema foi modelado a função de avaliação da solução como a solução inicial foi criada os métodos clássicos de busca local as metaheurísticas utilizadas e o método de busca em vizinhança de grande porte para otimização em redes No capítulo 5 é feita a apresentação dos resultados da primeira etapa da pesquisa que utiliza a metaheurística VNS e os resultados da segunda etapa onde a metaheurística ILS foi testada com a finalidade de comparar os resultados de ambas No capítulo 6 uma análise dos resultados de cada etapa é realizada separadamente seguindo os mesmos princípios da apresentação dos resultados O capítulo 7 apresenta as conclusões do presente estudo respondendo sobre a eficiência das metaheurísticas na solução do Problema da Programação das Tripulações e qual dos métodos apresenta soluções melhores dentro das práticas adotadas pela empresa Por fim no capítulo 8 os trabalhos obtidos deste estudo são enumerados 4 2 METODOLOGIA Para o início das atividades uma revisão bibliográfica foi realizada a qual se baseou na leitura e contextualização de alguns trabalhos publicados na utilização de metaheurísticas e resolução do Problema da Programação da Tripulação Dessa forma a pesquisa realizada é aplicada pois visa gerar conhecimentos para aplicação prática problemas específicos A abordagem é quantitativa e axiomática pois busca a resolução de um problema já idealizado Para isso o problema da programação das tripulações foi modelado relevando as variáveis e constantes pertinentes tornandoo mais próximo da realidade possível Com as informações bibliográficas e informações do problema quatro etapas metodológicas foram realizadas são elas a Definição do problema b Construção do Modelo c Solução do Modelo e d Validação do Modelo 3 REVISÃO BIBLIOGRÁFICA Realizar a programação de algum evento é uma atividade que se torna gradualmente mais difícil com o aumento da quantidade de itens a serem programados e também com o aumento das restrições do problema Desta forma a programação das tripulações do transporte urbano tornase um problema cada vez mais difícil de resolver devido às restrições trabalhistas e operacionais envolvidas Assim uma programação eficiente equivale à diminuição dos custos para a empresa ao aumento da produtividade e à satisfação dos funcionários e dos usuários do sistema Kwan e Li 2005 afirmam que o PPT é um problema mundial pois onde há o uso de ônibus há a necessidade de alocação de motoristas assim a aplicação de métodos computacionais robustos para uma melhor alocação dos motoristas fazse extremamente necessária O PPT é caracterizado pela busca em determinar o número mínimo de motoristas de forma a atender totalmente a uma programação de veículos ou seja frota operacional previamente estabelecida A solução do problema é obtida por meio do sequenciamento das atividades dos motoristas gerando um conjunto de jornadas de trabalho Estas jornadas devem satisfazer todas as diversas restrições que são as leis trabalhistas os acordos sindicais e também as regras operacionais das empresas Toda esta conjuntura caracteriza um problema do tipo NPdifícil para o qual não existe algoritmo polinomial que obtenha a solução ótima em um tempo de processamento razoável Fischetti et al 1987 5 A abordagem clássica para tratar esse problema formulao como um problema de programação linear inteira de recobrimento ou particionamento set covering ou set partitioning model Para resolver o problema normalmente é utiliza a estratégia de geração de colunas Smith e Wren 1988 Desrochers e Soumis 1989 Fores et al 1999 Barnhart et al 1998 Entretanto modelos exatos são limitados quando aplicados a problemas de grande porte Desta forma tornase fundamental a utilização de métodos heurísticos para resolver problemas práticos os quais são normalmente de grande porte Ferraz et al 2004 Neste ramo como grupo precursor temse o denominado Scheduling and Constraint Management Group da Universidade de Leeds que realizou uma série de implementações heurísticas utilizando Algoritmos Genéticos Kwan et al 1999 Li e Kwan 2003 Busca Tabu Shen e Kwan 2001 Colônia de Formigas Forsyth e Wren 1997 Algoritmo evolucionário autoajustável Kwan e Li 2005 entre outras Os modelos desenvolvidos por este grupo são largamente utilizados no Reino Unido tanto para realizar a programação das tripulações quanto da frota em operação Wren 2004 Dentre os estudos voltados para a resolução do PPT na realidade brasileira podemos destacar aqueles que utilizam as metaheurísticas Simulated Annealing Busca Tabu GRASP e VNS Silva et al 2002 Soares et al 2006 Souza et al 2004 Estas implementações foram testadas com dados de empresas que atuam no sistema brasileiro de transporte público e os resultados mostram que existem grandes possibilidades de redução dos custos em relação às soluções adotadas pelas empresas Entretanto como a operação do sistema é uma atividade dinâmica novos acordos e leis trabalhistas são aprovados transformando as restrições do problema Por outro lado modernas técnicas de busca surgem ao longo das pesquisas em curso e que podem ser utilizadas na resolução do problema Desta forma este trabalho explora a utilização de uma técnica recente de busca local baseada na representação em grafos e no uso de algoritmos de fluxo em redes para realizar buscas mais complexas do que aquelas inerentes aos procedimentos clássicos de busca local A técnica de busca denominada Very Largescale Neighborhood Search VLNS Ahuja 2000 foi empregada pela primeira vez para resolver o PPT por Silva e Cunha 2010 O modelo desenvolvido utiliza a técnica VLNS como o procedimento de busca da metaheurística GRASP Neste trabalho foi observado que o resultado de uma busca do tipo VLNS é fortemente dependente da solução inicial Sendo assim foi proposto adotar heurísticas construtivas que realizam perturbações periódicas na solução corrente através de 6 movimentos diversos Nesta classe podem ser destacadas as heurísticas Variable Neighborhood Search VNS que consiste em explorar o espaço de soluções através de trocas sistemáticas de estruturas de vizinhança e Iterated Local Search ILS que busca soluções melhores em sua estrutura de vizinhança através da realização de perturbações iterativas em sua solução corrente A maior vantagem das metaheurísticas é que elas são flexíveis para modelar o problema e muito eficientes em sua resolução retornando bons resultados mesmo dentro de um conjunto de soluções muito grande Kwan e Li 2005 Assim quando aplicadas a um problema real que já não alcança melhoras via modificações por humanos uma melhora por algum método computacional é de extrema valia Assim este trabalho tem como objetivo resolver o Problema de Programação da Tripulação utilizando as metaheurísticas ILS e VNS combinadas com diferentes técnicas de busca local Para verificar a eficiência das combinações propostas a metaheurística VNS foi implementada em sua versão clássica que usa o método Variable Neighborhood Descent VND tendo como procedimento de busca local subjacente o método da Primeira Solução de Melhora First Improvement Method Ao substituir o VND pelo VLNS foi obtida a versão VNSVNLS Para a ILS a sua versão clássica utilizou o método de busca local que aceitava o primeiro melhor vizinho do que a solução corrente encontrada pela busca local Em sua segunda versão foi utilizada a busca VLNS As duas versões da metaheurística foram testadas com dados de uma empresa nacional que opera em um sistema de transporte público e os diferentes resultados foram comparados permitindo uma avaliação quantitativa e qualitativa das soluções 4 MODELAGEM DO PROBLEMA A escala das tripulações é criada a partir de uma programação previamente definida para os veículos Sendo assim a programação dos veículos as regras operacionais e a legislação trabalhista são os dados de entrada do problema A maior parcela dos custos de uma empresa do setor é composta pela remuneração das tripulações dessa forma definir uma programação de tripulantes com custo mínimo leva a uma grande economia para a empresa A programação de uma tripulação é formada por um conjunto de tarefas e é denominada de jornada ou jornada diária da tripulação Neste contexto uma jornada se refere a uma tripulação e viceversa Uma tarefa é um conjunto de viagens de um mesmo veículo 7 que deve necessariamente ser realizado por uma mesma tripulação O conjunto de todas as jornadas constitui numa escala para as tripulações também dita programação das tripulações As jornadas são divididas em dois tipos Pegada Simples PS ou Dupla Pegada DP Na PS as tarefas são realizadas de uma única vez e os intervalos de tempo entre as tarefas são inferiores a duas horas Caso ocorra um intervalo maior do que duas horas a jornada é classificada como DP Este tipo de jornada está associado aos picos de demanda por viagens existentes nos dias úteis e o intervalo maior do que duas horas não é remunerado Para agrupar tarefas e formar uma jornada inúmeras restrições operacionais e normas trabalhistas devem ser levadas em conta Neste caso foram consideradas as seguintes restrições i As jornadas têm uma remuneração por 6 horas e 40 minutos de trabalho ii As jornadas do tipo PS devem ter uma pausa de pelo menos 20 minutos para descanso e refeição iii As jornadas não podem conter mais do que duas horasextras de trabalho iv O intervalo de tempo entre o final de uma jornada e o seu início no dia seguinte deve ser de pelo menos 11 horas v A troca de tripulações durante a operação só pode ocorrer em pontos e horas prédeterminados Os modelos heurísticos implementados neste trabalho procuram minimizar os custos fixos e variáveis da escala satisfazendo todas as restrições mencionadas acima Os custos fixos são representados pelo número de jornadas e os custos variáveis são computados em função do total de horas extras encontrado na escala Foram utilizadas as metaheurísticas Variable Neighborhood Search VNS proposta por Mladenović e Hansen 1997 e a Iterated Local Search ILS apresentada em Lourenço et al 2010 No VNS temse o VNS Clássico que utiliza como busca local a técnica Variable Neighborhood Descent VND e o VNS VLNS que utiliza a técnica Very Largescale Neighborhood Search Para o ILS além da técnica VLNS utilizouse uma busca local baseada no método primeiro de melhora As versões foram testadas resolvendo problemas de grande porte da realidade brasileira 41 Função Objetivo O custo associado a uma solução do PPT é computado por meio da combinação linear do custo fixo e dos custos variáveis que são i o total de horas extras e ii número de jornadas do tipo dupla pegada A expressão final para o custo de uma solução do PPT é trip tot i i i ppt peg dupla w extra hora w Fixo Custo C 1 2 1 1 8 Na expressão 1 temos que o CustoFixo representa a remuneração fixa de uma tripulação w1 é o peso por minutos de hora extra e horaextrai o total de horas extras da jornada i expresso em minutos Finalmente w2 é o peso por dupla pegada e duplapegi é igual a 1 se a tripulação i faz uma dupla pegada em sua jornada e 0 caso contrário 42 Solução Inicial A solução inicial dos métodos é gerada por um procedimento guloso que percorre as tarefas segundo a ordem crescente do horário de início das mesmas A tarefa de início mais cedo ainda não alocada inicializa uma jornada à qual são acrescidas as tarefas que apresentarem o menor custo de inserção à jornada Quando não for possível acrescentar novas tarefas à jornada corrente uma nova jornada é inicializada O procedimento se encerra quando todas as tarefas tiverem sido alocadas a uma jornada 43 Métodos Clássicos de Busca Local Os métodos de busca local constituem uma série de técnicas baseadas no conceito de vizinhança Para tanto seja S o espaço de todas as soluções de um problema de otimização e f a função objetivo a ser minimizada Definese um movimento como sendo a modificação m que transforma uma solução s em outra s dita vizinha de s pelo movimento m Assim podemos denotar tal operação da seguinte maneira ms s A função N que depende da estrutura do problema tratado associa a cada solução s em S sua vizinhança Ns contida em S Cada solução s em Ns é chamada de vizinho de s segundo um tipo de movimento ou estrutura de vizinhança que a define Para o caso do PPT uma solução representa uma escala ou programação para as tripulações e um movimento pode ser por exemplo a troca de uma tarefa entre duas tripulações Em linhas gerais esta classe de heurística parte de uma solução inicial qualquer obtida por uma heurística construtiva ou então gerada aleatoriamente e caminha a cada iteração de vizinho em vizinho de acordo com a definição da estrutura de vizinhança adotada 431 Estrutura de Vizinhança RealocaTroca Uma vez definida a quantidade máxima de tarefas movimentadas entre duas jornadas é necessário estabelecer os diferentes tipos de movimento que caracterizam cada uma das vizinhanças de uma solução Os dois tipos de movimentos adotados foram a 9 realocação ou a troca de tarefas entre duas jornadas sem haver sobreposição Estes movimentos são realizados para encontrar o melhor vizinho de uma solução corrente Exemplificando para um dado kmax maior do que zero e menor ou igual a três considere duas jornadas i e j escolhidas aleatoriamente Então são sorteadas k k kmax tarefas consecutivas da jornada i a serem introduzidas na jornada j Logo pode ocorrer uma das seguintes situações 1 As k tarefas de i podem ser introduzidas em j sem a necessidade de remover qualquer tarefa de j Neste caso o movimento é aceito e será avaliado sendo realizada uma alocação 2 A introdução das k tarefas em j exige a retirada de uma ou mais tarefas desta jornada Neste caso se as tarefas removidas de j puderem ser inseridas na jornada i sem haver qualquer sobreposição com as tarefas que permaneceram em i então o movimento é aceito caso contrário ele é descartado sendo o movimento denominado por troca Em ambos os casos as modificações são aceitas se e somente se as jornadas resultantes respeitarem todas as restrições do problema Para encontrar o melhor vizinho da solução corrente esta estrutura de vizinhança foi empregada no método de descida da primeira solução de melhora dentro do VND e no procedimento de busca local do ILS 432 Método da Descida A ideia desta técnica é partir de uma solução inicial qualquer e a cada passo analisar todos os seus possíveis vizinhos movendo para aquele que apresentar a maior melhoria no valor atual da função objetivo Pelo fato de analisar todos os vizinhos e escolher o melhor esta técnica é comumente identificada na literatura por Best Improvement Method O método é interrompido quando um ótimo local é encontrado Entretanto a utilização deste método de forma iterativa tornase inviável computacionalmente uma vez que ele avalia todos os possíveis vizinhos de uma solução para então escolher aquele que leva à maior melhoria 433 Método da Primeira Solução de Melhora Como o método de descida requer a exploração de toda a vizinhança uma alternativa que evita esta pesquisa exaustiva é o Método da Primeira Solução de Melhora First Improvement Method Neste caso a busca na vizinhança é interrompida assim que um vizinho melhor é encontrado Desta forma apenas no pior caso ou seja na última iteração 10 toda a vizinhança é explorada Assim como no método da descida este método fica preso no primeiro ótimo local encontrado Neste método é desejável que a ordem de exploração das soluções vizinhas seja alterada a cada passo do contrário privilegiase apenas um caminho determinístico no espaço de soluções Por exemplo para o PPT considere que um movimento consista em realocar uma tarefa de uma tripulação para outra tripulação Se a cada passo a ordem de exploração das soluções vizinhas começar com a movimentação da primeira tarefa do primeiro tripulante para o segundo tripulante depois para o terceiro e assim sucessivamente então os tripulantes iniciais serão privilegiados Para evitar isso uma alternativa é utilizar uma sequência diferente para percorrer as tripulações a cada iteração do método 434 Método de Descida em Vizinhança Variável VND O Método de Descida em Vizinhança Variável Variable Neighborhood Descent VND proposto por Mladenović e Hansen 1997 é uma técnica de busca local que consiste em explorar o espaço de soluções por meio de trocas sistemáticas de estruturas de vizinhança aceitando somente soluções que produzem uma melhora na solução corrente O procedimento retorna à primeira estrutura quando uma solução de melhora é encontrada O pseudocódigo deste método em que se considera o refinamento de uma solução s utilizando uma função de avaliação f a ser minimizada e um conjunto de r vizinhanças diferentes N N 1 N 2 N r é apresentado no Figura 1 Para encontrar o melhor vizinho da solução corrente foi utilizado o método clássico de descida com Primeira Solução de Melhora Mladenović e Hansen 1997 na linha 5 da Figura 1 percorrendo as jornadas em uma ordem aleatória Isso evita que as primeiras jornadas da escala apresentem qualidade superior em detrimento da qualidade das últimas jornadas Procedimento VND solução s vizinhança k Início 1 Seja s uma solução corrente dada 2 Seja k uma estrutura de vizinhança dada 3 r 1 4 Enquanto r k faça 5 Encontre o melhor vizinho s de s na vizinhança N r 6 Se fs fs 7 então s s e k 1 8 senão r r 1 11 9 Fim enquanto 10 Retorna a solução s Fim Figura 1 Pseudocódigo do Procedimento VND 44 Método de Busca em Vizinhança de Grande Porte VLNS para resolver o PPT A seguir são apresentadas as adaptações que possibilitaram utilizar o método de busca em vizinhança de grande porte para resolver o PPT Esse método de busca local foi incorporado às heurísticas VNS e ILS para resolver o PPT com as restrições legais e operacionais de problemas práticos 441 Estrutura de Vizinhança de Troca Cíclica Um aspecto crítico em algoritmos de busca em vizinhança diz respeito à escolha da estrutura da vizinhança isto é na maneira como ela é definida Essa escolha define em grande parte se a estratégia de busca permitirá obter soluções de boa qualidade ou não Em geral quanto maior a vizinhança melhor deverá ser a qualidade das soluções ótimas locais Porém vizinhanças de grande porte requerem um tempo elevado de pesquisa Por essa razão uma vizinhança maior não implica numa heurística melhor exceto se a vizinhança for explorada de maneira eficiente Ahuja et al 2000 Para uma exploração maior das estruturas de vizinhanças existem os algoritmos denominados Very Largescale Neighborhood Search Methods VLNS que são aplicáveis a problemas de particionamento Ahuja et al 2000 Estes algoritmos permitem explorar vizinhanças muito grandes mantendo o tempo de busca em níveis bem reduzidos Uma forma de alcançar tal eficiência é com a utilização de modelos de fluxo em rede para enumerar de forma implícita uma vizinhança com a finalidade de encontrar soluções melhores Os métodos clássicos de busca em vizinhança se baseiam em realocação e trocas aos pares de elementos entre os dois subconjuntos aos quais pertencem Diferentemente deles um método VLNS realiza trocas cíclicas Uma troca cíclica pode ser definida por uma sequência de tarefas t1t2t3trt1 pertencentes a diferentes tripulações que as executariam Considerando Dtk o subconjunto ao qual pertence a tarefa tk então a troca cíclica t1t2t3 trt1 representa a alteração onde a tarefa t1 é movida de Dt1 para Dt2 o elemento t2 de Dt2 para Dt3 e assim por diante Finalmente o elemento tr é movido de Dtr para Dt1 12 Note que a vizinhança de troca cíclica contempla a troca aos pares e ainda explora uma infinidade de outras soluções não alcançáveis pela troca aos pares Portanto para uma dada partição factível D definimos outra partição D como vizinha de D se i D é uma partição factível e ii D pode ser obtida a partir de D realizando um movimento de troca cíclica Definimos uma vizinhança ND como a coleção de todas as partições que são vizinhas de D Esta vizinhança cresce exponencialmente com o tamanho do ciclo r é de se esperar que soluções ótimas locais obtidas por meio de múltiplas trocas sejam em média superiores àquelas obtidas pela troca aos pares Entretanto uma vez que o tamanho da vizinhança em trocas múltiplas cresce exponencialmente com o tamanho do problema torna se necessário um método eficiente para encontrar um vizinho de menor custo na vizinhança Este problema pode ser contornado utilizando o conceito de grafo de melhoria descrito a seguir para explorar de forma eficiente uma dada vizinhança 442 Grafo de Melhoria para o PPT Um grafo de melhoria improvement graph para uma vizinhança com trocas cíclicas é definido para uma partição viável D do problema sendo representado por GD Seja Dtj a jornada que contém a tarefa tj O grafo GD é um grafo direcionado com n nós onde cada nó t corresponde a uma tarefa ti D Um arco direcionado i j em GD significa que a tarefa ti deixa a sua jornada atual e é movida para a jornada que contém a tarefa tj isto é a jornada Dtj Simultaneamente a tarefa tj deixa Dtj Para se construir GD são considerados todos os pares de tarefas ti e tj em D O arco i j é adicionado a GD se i as tarefas ti e tj pertencerem a diferentes jornadas ii a jornada tiDtjtj for viável O custo cij no arco i j é definido como ctiDtjtj cDtj Denominase um ciclo direcionado W no grafo de melhoria GD se as tarefas em D correspondentes aos nós em W pertencem a diferentes jornadas Definese um ciclo válido como um ciclo direcionado de custo negativo em GD Assim um ciclo válido em GD corresponde a uma troca cíclica que leva a uma melhoria no valor da função objetivo do problema Esta é uma forma eficiente de realizar buscas por soluções que melhoram o valor objetivo na vizinhança de D Portanto é necessário encontrar ciclos válidos no grafo de melhoramentos GD 13 443 Identificando um Ciclo Válido Nesse trabalho foi utilizado o algoritmo de rotulamento modificado com a disciplina de fila primeiro que entra primeiro que sai para identificar um ciclo válido Para implementar este algoritmo é armazenado o número de vezes que cada nó é examinado Se a rede não tiver ciclos válidos cada nó será examinado no máximo n 1 vezes onde n é o número de nós da rede Entretanto se algum nó for examinado mais do que n 1 vezes então a rede contém um ciclo Para reconstruir o ciclo basta partir do nó identificado e percorrer o vetor de nós predecessores até retornar ao nó Ahuja et al 1993 A ideia dos algoritmos do tipo VLNS consiste em construir um grafo GD para uma dada solução S e encontrar um ciclo direcionado em GD que forneça um vizinho melhor do que S Após efetuar a troca cíclica inerente ao ciclo válido o grafo é atualizado e é procurado um novo ciclo válido A busca termina quando o grafo de melhoria não apresentar qualquer ciclo válido O pseudocódigo apresentado na Figura 2 sintetiza a método Procedimento VLNS solução s Início 1 Seja s uma solução corrente dada 2 Construa o grafo de melhoria GD referente a s 3 Enquanto GD tiver ciclos negativos faça 4 Identifique um ciclo negativo em GD 5 Melhore a solução s devido às trocas do ciclo negativo 6 Atualize o grafo de melhoria GD 7 Fim enquanto 8 Retorna a solução s Fim Figura 2 Pseudocódigo do Procedimento VLNS 45 Heurísticas para a Resolução do PPT Nesta subseção serão apresentadas as heurísticas que foram utilizadas para a resolução do PPT e testadas tanto com os métodos clássicos de busca local quanto com o método VLNS 451 Busca em Vizinhança Variável VNS A metaheurística VNS Variable Neighborhood Search parte de uma solução inicial factível e de um conjunto de diferentes estruturas de vizinhança para realizar buscas locais A partir da solução inicial o procedimento gera um vizinho qualquer segundo uma 14 estrutura de vizinhança e realiza uma busca local a partir deste vizinho Se a busca local gerar uma solução melhor do que a solução corrente esta é atualizada e o processo se repete a partir da primeira estrutura de vizinhança Caso contrário um novo vizinho é gerado considerando a próxima estrutura de vizinhança e a busca local é aplicada neste vizinho Este processo se repete até que a condição de parada seja satisfeita A melhor solução encontrada neste processo é retornada pelo procedimento Para uma identificação mais fácil o uso do VND pelo VNS foi chamado de VNSClássico A Figura 3 sintetiza a metaheurística VNS Procedimento VNS solução s Início 1 Seja um conjunto de kmax estruturas de vizinhanças 2 Encontre uma solução inicial s e determine uma condição de parada 3 Enquanto a condição de parada não for satisfeita faça 4 k 1 5 Enquanto k kmax faça 6 Gere um vizinho qualquer s de s na késima vizinhança 7 Encontre o melhor vizinho s de s na vizinhança k 8 Se fs for melhor do que fs 9 então s s e k 1 10 senão k k 1 11 Fim enquanto 12 Fim enquanto 13 Retorna a solução s Fim Figura 3 Pseudocódigo da Metaheurística VNS 452 A Metaheurística Iterated Local Search ILS A metaheurística ILS apresentada em Lourenço et al 2010 é baseada na ideia de que um procedimento de busca local pode ser melhorado gerandose novas soluções de partida as quais são obtidas por meio de perturbações na solução ótima local Ele usa uma solução inicial gerada randomicamente ou através de uma solução gulosa para iniciar sua busca por soluções melhores em diferentes espaços Assim um método de busca local é aplicado a esta solução inicial gerando uma solução ótima local corrente Após isso uma perturbação é aplicada para que a solução se afaste da depressão de atração deste ótimo local e permita assim a realização de uma nova busca em um novo espaço Uma nova busca é realizada nesta solução intermediária Ao fim da iteração um critério de aceitação é aplicado para avaliação e possível aceitação da mesma decidindo qual será a próxima solução que sofrerá perturbação Através da Figura 4 é notável que a metaheurística está fundamentada em quatro procedimentos 1 Solução Inicial Gerada 2 Busca Local 3 Perturbação da 15 Solução e 4 Critério de Aceitação da Solução A função de busca local é tratada genericamente ou seja fica a critério do pesquisador definir que método será utilizado Neste trabalho o método de busca local é utilizado nas linhas 2 e 5 da Figura 4 sendo as técnicas utilizadas o VLNS e a heurística de refinamento do Primeiro vizinho de melhora na vizinhança para k igual a um Os procedimentos de Perturbação e Critério de Aceitação da Solução serão apresentados nas seções a seguir Procedimento ILS solução s Início 1 s0 Solução Inicial Gerada 2 s Busca Local s0 3 Repita até que a condição de parada seja encontrada 4 s Perturbação da Solução s histórico de busca 5 s Busca Local s 6 s Critério de Aceitação da Solução s s histórico de perturbação 7 Fim repita 8 Retorna a solução s Fim Procedimento ILS Figura 4 Pseudocódigo da Metaheurística ILS 4521 Perturbação da Solução Para escapar dos ótimos locais a metaheurística ILS aplica perturbações na solução corrente Assim a perturbação deve ser bastante efetiva mas não pequena demais ao ponto de não obter ganhos e deixar de explorar outros ótimos locais e nem tão grande ao ponto de desfazer os resultados da busca local e deixar de explorar bons ótimos locais Talbi 2009 A perturbação da solução corrente presente na metaheurística ILS foi implementada segundo a estrutura de vizinhança RealocaTroca apresentada anteriormente sendo que neste procedimento é utilizado o parâmetro k maior do que aquele passado para o método de Busca Local executado logo a seguir no algoritmo Esta estratégia é utilizada para evitar que o algoritmo entre em um ciclo e possa explorar outras regiões do espaço de soluções Lourenço et al 2010 O parâmetro k é incrementado assim que a busca local falhar na procura por uma solução melhor Ao atingir o valor máximo kmax definido em função do número de jornadas da solução corrente k recebe o valor dois e o procedimento continua até que a condição de parada seja atingida O valor de k utilizado na busca local é sempre igual a um 16 4522 Critério de Aceitação O critério de aceitação junto com o método de perturbação tem como função controlar o tradeoff entre intensificação seleção forte que aceita somente soluções de melhora e diversificação seleção fraca que aceita soluções sem dar atenção a qualidade Talbi 2009 O critério ao fim decide qual solução será perturbada na próxima iteração se será novamente a corrente ou a intermediária previamente gerada Para este trabalho a função de aceitação como sugerido por Lourenço et al 2010 foi divida nas partes de intensificação e diversificação Para que uma solução seja aceita ou seja tornese a próxima solução corrente é estritamente necessário que o seu custo seja menor do que o custo da melhor solução encontrada até o momento Caso não seja um elemento randômico é utilizado de forma a explorar novas depressões de atração em busca de uma solução melhor 5 RESULTADOS COMPUTACIONAIS As implementações foram testadas em duas etapas Na primeira etapa foi testada a metaheurística VNS variando o procedimento de busca local com as seguintes versões VNS Clássico e VNSVLNS Nesta etapa foram consideradas as variações dos parâmetros peso para a dupla pegada w2 da Expressão 1 e o número máximo de troca de veículos realizada durante uma jornada Foi também observado que mesmo considerando um peso maior para as duplas pegadas são produzidas soluções com um grande número de jornadas deste tipo o que não é desejável na prática Desta maneira a geração de duplas pegadas ficou restrita aos intervalos de pico levando a uma segunda etapa de testes Na segunda etapa foi implementada a nova regra de formação de duplaspegadas e empregado um equipamento computacional com maior capacidade de processamento e memória RAM Nesta etapa foram executados testes com as metaheurísticas VNS e ILS nas versões VNSClássico VNSVLNS ILSClássico e ILSVLNS Foram utilizados os parâmetros que produziram os melhores resultados segundo testes preliminares ou seja o peso para duplapegada igual a 600 e no máximo uma troca de veículos por jornada diária Os resultados são apresentados separadamente a seguir 51 Resultados da primeira etapa A metaheurística VNS Os algoritmos foram utilizados para resolver um 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 As duas heurísticas VNSClássico e VNSVLNS foram 17 implementadas na linguagem CC e os testes foram realizados em um computador pessoal com processador Core2 Duo e 3 GB de memória RAM As heurísticas foram executadas por uma hora e foram realizadas 10 execuções para cada problema da empresa Os resultados apresentados abaixo foram divididos em duas subseções em função dos pesos atribuídos ao total de duplas pegadas contido na solução Este tipo de análise é fundamental para o problema pois as empresas trabalham com o número de duplas pegadas variando entre 10 e 20 do total de duplas Por outro lado os dois métodos de busca implementados neste trabalho produziram soluções com características significativamente diferentes em relação ao número de duplas pegadas 511 Soluções com menor peso para as duplas pegadas A Tabela 1 contém as características das soluções adotadas pela empresa Nas tabelas a seguir a linha HE se refere o total de horas extras Jornadas ao total de jornadas DP o total de jornadas do tipo dupla pegada que estão contidas na solução e a FO se refere ao valor total da solução O primeiro conjunto de testes foi realizado considerando os seguintes pesos 10000 para o CustoFixo 4 para w1 tendo as horas extras expressas em minutos Ao peso w2 referente às duplas pegadas foi atribuído o valor 600 Estes pesos foram obtidos empiricamente para se produzir soluções com características desejáveis Eles foram aplicados às soluções da empresa para efeito de comparação com as soluções produzidas pelas heurísticas Tabela 1 Dados da escala de mão de obra operada pela empresa Segunda Terça Quarta Quinta Sexta Sábado Domingo HE 8641 8555 10605 12014 10811 5435 2657 Jornadas 134 130 149 162 155 124 68 DP 6 3 5 4 1 0 0 FO 1364404 1322420 1518460 1651256 1576564 1253100 686468 4111 Resultados considerando no máximo uma troca de veículo por jornada Para os pesos mencionados anteriormente foram realizados testes considerando que as jornadas pudessem realizar no máximo uma troca de veículo durante a operação A heurística VNSClássico produziu os resultados apresentados na Tabela 2 e na Tabela 3 estão os resultados do VNSVLNS As tabelas a seguir apresentam um resumo dos resultados obtidos nos quais os dados HE Jornadas e DP se referem à solução com menor FO 18 FO Melhor Além disso são apresentadas as médias de todas as soluções obtidas a FO Média assim como o desvio médio dado por FO Média FO MelhorFO Média Quanto menor for esta porcentagem mais robusto é o método Ou seja a diferença entre as diversas soluções encontradas que contam com um fator de aleatoriedade não é significativa e a heurística tem a capacidade de produzir soluções muito parecidas Tabela 2 Características das soluções obtidas pelo VNSClássico Segunda Terça Quarta Quinta Sexta Sábado Domingo HE 9658 9946 12237 13206 12556 9043 5351 Jornadas 117 111 133 141 134 101 52 DP 50 59 71 93 81 43 17 Melhor FO 1223272 1169344 1402028 1497504 1418824 1057572 543124 FO Média 1233332 1188202 1410726 1529976 1441757 1064657 556974 Desvio 082 159 062 212 159 067 249 Tabela 3 Características das soluções obtidas pelo VNSVLNS Segunda Terça Quarta Quinta Sexta Sábado Domingo HE 5039 5628 7730 7042 7033 5721 3421 Jornadas 120 117 135 149 141 107 55 DP 19 14 19 17 14 10 7 Melhor FO 1223556 1191952 1380000 1517168 1435332 1089764 562444 FO Média 1235435 1203345 1409582 1534114 1451791 1106525 572411 Desvio 096 095 210 110 113 151 174 Tabela 4 Melhorias alcançadas pelo VNS em relação à solução da empresa 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 Para comparar os resultados obtidos pelas metaheurísticas e a solução da empresa utilizouse a Expressão 2 mostrada a seguir 2 19 As melhorias apresentadas na Tabela 4 mostram uma redução de até 1355 e de 1045 no número de jornadas obtidas pelo VNSClássico e pelo VNSVLNS respectivamente para os dias úteis e de até 2353 e 1912 para o final de semana As reduções de jornadas mais significativas foram obtidas pelo VNSClássico Para tanto houve um aumento no número de horas extras que chega a 1641 nos dias úteis e até 9981 no final de semana Por outro lado o VNSVLNS conta com uma redução de até 4157 das horas extras nos dias úteis As soluções obtidas pelo VNSVLNS são de interesse prático pois estão dentro do limite de 20 do total de jornadas O mesmo não ocorre com as soluções produzidas pelo VNSClássico para a quantidade de jornadas de DP que alcançou valores tecnicamente inviáveis à realidade variando entre 73333 a 80000 nos dias úteis Como a empresa admite até duas trocas de veículo por motorista ao longo de sua jornada diária de trabalho foram realizados testes segundo esta condição o que representa uma flexibilização na operação da mão de obra 4112 Resultados considerando no máximo duas trocas de veículo por jornada Os resultados das Tabelas 5 e 6 consideram que as jornadas podem conter até duas trocas de veículo ao longo da operação Esta é mais uma variação nas diferentes possibilidades operacionais admitidas pela empresa Tabela 5 Características das soluções obtidas pelo VNS Clássico Segunda Terça Quarta Quinta Sexta Sábado Domingo HE 9658 9451 11345 12523 10551 8802 4335 Jornadas 117 111 132 144 136 101 52 DP 50 58 69 84 67 43 17 Melhor FO 1223272 1167564 1388144 1520492 1425068 1057572 543124 FO Média 1233332 1184599 1404902 1538868 1441251 1064102 556974 Desvio 082 146 121 121 114 062 255 Tabela 6 Características das soluções obtidas pelo VNSVLNS Segunda Terça Quarta Quinta Sexta Sábado Domingo HE 5039 5552 6210 5336 5618 4312 3621 Jornadas 120 117 137 149 141 107 55 DP 19 10 15 17 17 10 7 Melhor FO 1223556 1189408 1393920 1515196 1437060 1089764 562444 FO Média 1235435 1203465 1411193 1527566 1448626 1106525 572557 Desvio 097 118 124 082 081 154 180 20 Os resultados obtidos mostram que com a possibilidade de aumentar no número de trocas de veículos realizadas pelas tripulações levam em alguns casos a uma economia significativa no número de horas extras Este é o caso dos dados da quinta e da sextafeira observados no método VNSVLNS que chegam a 244 e 204 de redução entre o primeiro e o segundo cenário operacional Na Tabela 7 são apresentadas as melhorias em relação à solução da empresa Tabela 1 As melhorias foram calculadas utilizando a Expressão 2 Tabela 7 Melhorias alcançadas pelo VNS em relação à solução da empresa 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 Na tabela 7 é possível a predominância dos melhores valores da solução para o VNSClássico porém apresentando uma grande quantidade de jornadas do tipo DP e valores maiores para as horasextras 512 Soluções com maior peso para as duplas pegadas A seguir são apresentados os resultados para os pesos escolhidos com o intuito de produzir escalas com um número menor de duplas pegadas DP pela heurística VNS Clássico Nas tabelas a seguir foram considerando os seguintes pesos 10000 para o CustoFixo 4 para w1 tendo as horas extras expressas em minutos Ao peso w2 referente às duplas pegadas foi atribuído o valor 5000 Estes pesos são obtidos empiricamente com o objetivo de reduzir o número de duplas pegadas e manter o número de jornadas em um valor próximo dos níveis dos valores obtidos anteriormente 5121 Resultados considerando no máximo uma troca de veículo por jornada Considerando a possibilidade de cada tripulação realizar no máximo uma troca de veículo ao longo da operação e os novos pesos foram geradas escalas com as duas versões da heurística VNS Os resultados são apresentados nas Tabelas 8 e 9 21 Tabela 8 Características das soluções obtidas pelo VNS Clássico com novos pesos Segunda Terça Quarta Quinta Sexta Sábado Domingo HE 9800 9640 11616 12158 11606 9502 4612 Jornadas 120 114 135 152 142 104 54 DP 29 31 30 27 23 24 9 Melhor FO 1368520 1318200 1527904 1684272 1562864 1182808 596088 FO Média 1381195 1330934 1540384 1696964 1575031 1198170 609063 Desvio 093 097 082 075 078 130 218 Tabela 9 Características das soluções obtidas pelo VNSVLNS com novos pesos Segunda Terça Quarta Quinta Sexta Sábado Domingo HE 6507 7544 6724 7741 8755 5218 2735 Jornadas 120 114 140 148 139 109 57 DP 11 11 11 17 12 10 5 Melhor FO 1270628 1213176 1471176 1583644 1471100 1152552 601296 FO Média 1282988 1232681 1484256 1602478 1487842 1164025 606620 Desvio 097 161 089 119 114 100 088 Com os novos pesos fica clara a superioridade das soluções produzidas pela heurística VNSVLNS sobre o VNSClássico não somente por meio da comparação da FO como também pela comparação do número de jornadas número de jornadas com duplas pegadas mas principalmente pelo total de horas extras Na Tabela 10 são apresentadas as melhorias em relação à solução da empresa Tabela 1 Tabela 10 Melhorias alcançadas pelo VNS em relação à solução da empresa 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 Na tabela 10 é possível a predominância dos melhores valores da solução para o VNSVLNS com melhores valores para as horasextras e menor quantidade de duplas pegadas do que o VNSClássico 22 5122 Resultados considerando no máximo duas trocas de veículo por jornada Os resultados das Tabelas 11 e 12 consideram que as jornadas podem conter até duas trocas de veículo ao longo da operação Tabela 11 Características das soluções obtidas pelo VNS Clássico Segunda Terça Quarta Quinta Sexta Sábado Domingo HE 9336 8925 11157 11342 11020 9803 3406 Jornadas 120 115 139 151 143 102 54 DP 29 28 23 30 24 26 11 Melhor FO 1348720 1306088 1526608 1663964 1547540 1148672 595472 FO Média 1370574 1316318 1535872 1683994 1562788 1178420 612465 Desvio 162 078 061 120 098 259 285 Tabela 12 Características das soluções obtidas pelo VNSVLNS Segunda Terça Quarta Quinta Sexta Sábado Domingo HE 5134 5825 5819 5833 6605 4939 2712 Jornadas 121 118 139 150 139 110 58 DP 12 8 11 14 10 11 6 Melhor FO 1264724 1220112 1449952 1580160 1461288 1141916 597496 FO Média 1281180 1233742 1465691 1589927 1478001 1155537 605801 Desvio 130 112 109 062 114 119 139 Novamente foi verificada uma redução no valor da FO Melhor quando se permite que uma tripulação faça até duas trocas de veículo ao logo da operação Esta redução se deve principalmente à redução das horas extras e no número de jornadas do tipo dupla pegada Na Tabela 13 são apresentadas as melhorias em relação à solução da empresa Tabela 1 Tabela 13 Melhorias alcançadas pelo VNS em relação à solução da empresa 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 23 Na tabela 13 novamente existe a predominância dos melhores valores da solução para o VNSVLNS com melhores valores para as horasextras e menor quantidade de duplas pegadas do que o VNSClássico 52 Resultados da segunda etapa As metaheurísticas VNS e ILS Nesta etapa foi utilizado o mesmo conjunto de problemas da etapa anterior e a mesma linguagem de programação Os parâmetros utilizados na função objetivo Expressão 1 foram os mesmos adotados nos primeiros testes considerando o menor peso para as duplas pegadas e somente uma troca veículo da etapa anterior As tabelas a seguir apresentam o mesmo formato das tabelas da etapa anterior e os pesos utilizados foram 10000 para o CustoFixo 4 para w1 tendo as horas extras expressas em minutos e 600 para w2 ou seja para cada dupla pegada na solução Os testes foram realizados em um computador pessoal com processador Intel Core i7 e 8 GB de memória RAM As heurísticas foram executadas por uma hora e foram realizadas 10 execuções para cada problema do conjunto teste 521 Soluções obtidas pelo VNS Embora a heurística VNS tenha sido testada anteriormente nesta etapa houve uma pequena modificação em relação à etapa anterior produzindo resultados diferentes Na Tabela 11 são apresentados os detalhes da melhor solução obtida com a busca local clássica especificando o total de jornadas Jornadas de horasextras no formato hhmm HE o número de duplas pegadas DP e o valor da função objetivo FO Também são apresentados os valores médios da FO e o desvio médio Desvio para as 10 execuções conduzidas para cada dia da semana Tabela 14 Características das soluções obtidas pelo VNSClássico Segunda Terça Quarta Quinta Sexta Sábado Domingo HE 5446 6024 6357 6109 7455 6022 3324 Jornadas 120 116 137 150 140 106 55 DP 23 15 22 34 30 17 10 Melhor FO 1218316 1167748 1396164 1515728 1426732 1063544 563512 FO Média 1223408 1181297 1401548 1534773 1439857 1077809 570119 Desvio 042 115 038 124 091 132 116 24 Na Tabela 15 são apresentados os resultados obtidos pela metaheurística VNS associado à busca local de grande porte VLNS Tabela 15 Características das soluções obtidas pelo VNSVLNS Segunda Terça Quarta Quinta Sexta Sábado Domingo HE 6736 6347 6444 7301 6905 5147 3608 Jornadas 119 116 138 149 142 108 55 DP 18 13 23 25 17 15 8 Melhor FO 1217024 1183108 1409336 1522524 1446964 1101428 563472 FO Média 1233271 1203982 1422288 1539752 1455184 1120420 572689 Desvio 132 173 091 112 056 170 161 A Tabela 16 contém um resumo das melhorias alcançadas pelo VNS em relação à solução da empresa apresentada na Tabela 1 As melhorias são apresentadas para cada componente da função objetivo assim como para o seu valor final Observando o valor final é possível concluir que a combinação VNSClássico produziu soluções mais econômicas do que aquela que utiliza a busca em vizinhança de grande porte Isso se deve principalmente porque a combinação VNSClássico utiliza em média um número maior de duplas pegada e consegue reduzir o total de horas extras e o número de tripulações Tabela 16 Melhorias alcançadas pelo VNS em relação à solução da empresa 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 Na tabela 16 as soluções do VNSClássico têm os melhores valores para FO mas são consideravelmente pequenos mostra valores quase que dentro da realidade para a DP além de conseguir melhoria nas HE em relação à empresa o que não tinha obtido na primeira etapa de testes 25 522 Soluções obtidas pelo ILS A metaheurística ILS produziu resultados similares à VNS conforme pode ser observado nas Tabelas 17 e 18 Entretanto ao compara o ILSClássico com o ILSVLNS os melhores resultados foram obtidos pela combinação ILSVLNS segundo análise dos dados apresentados na Tabela 19 Tabela 17 Características das soluções obtidas pelo ILSClássico Segunda Terça Quarta Quinta Sexta Sábado Domingo HE 5233 6235 6158 5920 6758 6235 2357 Jornadas 121 116 138 151 142 106 57 DP 20 20 23 24 18 16 8 Melhor FO 1234612 1187020 1408672 1538640 1447112 1084620 580548 FO Média 1244630 1204278 1422502 1554936 1468522 1102346 589029 Desvio 080 143 097 105 146 161 144 Tabela 18 Características das soluções obtidas pelo ILSVLNS Segunda Terça Quarta Quinta Sexta Sábado Domingo HE 6424 6512 6203 6048 7345 5830 2302 Jornadas 119 115 138 151 141 108 57 DP 18 19 20 17 16 9 7 Melhor FO 1216256 1177048 1406892 1534792 1437300 1099440 579728 FO Média 1233277 1202322 1425890 1538452 1463668 1110343 580146 Desvio 138 210 133 024 180 098 007 Neste caso o ILSVLNS produziu soluções em geral com menor número de jornadas e de duplas pegadas mantendo ainda o total de horas extras no mesmo nível do ILSClássico Desta forma o valor do FO foi melhor para todas as soluções perdendo para o ILSClássico apenas no sábado Tabela 19 Melhorias alcançadas pelo ILS em relação à solução da empresa Heurística Segunda Terça Quarta Quinta Sexta Sábado Domingo 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 26 Na tabela 19 as soluções do ILSVLNS têm os melhores valores para FO em todos os dias além de melhores resultados para HE DP e número total de jornadas o que a torna bastante atrativa para a realidade do problema 523 Comparando o desempenho VNS ILS Apesar da metaheurística VNSClássico apresentar a maioria das soluções melhores do que o ILSVLNS a diferença entre elas é muito pequena chegando a ser insignificante em termos percentuais Na Tabela 20 são apresentadas as diferenças percentuais existentes entres os dois métodos Esta tabela foi construída utilizando os dados da melhor solução do VNSClássico e do ILSVLNS Os valores foram obtidos pela seguinte expressão VNSClássico ILSVLNSVNSClássico dos itens correspondentes às respectivas linhas Valores negativos mostram a superioridade do VNSClássico em relação ao ILS VLNS e viceversa Tabela 20 Diferença percentual entre o VNSClássico e o ILSVLNS 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 É possível verificar que a diferença da FO Melhor entre os dois métodos é de no máximo 126 para os dias úteis e 338 para o final de semana Desta forma fica claro que os dois métodos são competitivos e geram soluções muito próximas para este tipo de problema A diferença entre as horas extras variam entre os diferentes problemas dias da semana com vantagem menor valor para o VNSClássico Entretanto uma característica de grande interesse prático é o número de duplas pegadas Neste item o ILSVLNS é muito superior uma vez que além de ser menor em 6 dentre os 7 dias da semana o desvio padrão do número de duplas pegadas ocorridas nos dias úteis é de 158 para o ILSVLNS contra 74 para o VNSClássico Um número elevado de duplas pegadas dificulta sobremaneira a construção da programação mensal da tripulação 6 ANÁLISE DOS RESULTADOS Uma vez que os testes computacionais foram realizados em duas etapas distintas a análise dos resultados também deve seguir o mesmo princípio Desta forma 27 seguem abaixo as considerações de cada cenário estudado neste trabalho Uma característica comum a todos os cenários diz respeito ao desvio médio das 10 rodadas de cada problema Este valor variou entre 007 e 285 o que mostra que os algoritmos implementados são muito robustos produzindo soluções com custos e características muito próximas 61 Análise dos Resultados da Primeira Etapa Metaheurística VNS Os resultados obtidos mostram que a duas versões da metaheurística VNS produziram resultados melhores do que a solução da empresa em praticamente todos os testes efetuados Comparando os resultados do VNS com os pesos maiores para DP manteve um maior número de dias a quantidade de jornadas do tipo dupla pegada DP dentro dos limites aceitáveis do ponto de vista operacional que é de no máximo de 20 do total de jornadas e reduzindo ao máximo o total de horas extras Por outro lado em alguns casos o 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 Este tipo de análise e escolha da melhor solução depende das características mais valorizadas na prática 62 Análise dos Resultados da Segunda Etapa Metaheurísticas ILS e VNS As soluções produzidas na segunda etapa de testes tem um número consideravelmente menor de Duplas Pegadas do que na etapa anterior diferença esta observada principalmente nas versões que utilizam o método de busca Clássica O fato observado na etapa anterior de que o uso da busca local VLNS produz soluções com menor número de duplas pegadas se verifica nesta etapa também tanto para o VNS quanto para o ILS Os resultados obtidos mostram que a duas metaheurísticas estudadas produziram soluções melhores do que a empresa independentemente do método de busca local utilizado Comparando os resultados do VNS diferentemente da etapa anterior as melhores soluções foram obtidas pela versão VNSClássico Mas podese observar que a diferença entre os valores é de no máximo 14 para os dias úteis e 35 no final de semana Por outro lado o número de duplas pegadas é menor na maioria das soluções do VNSVLNS Para o ILS a versão ILSVLNS produziu soluções melhores segundo a função objetivo FO e ainda mantém o número de jornadas do tipo Dupla Pegada menor do que na versão ILSClássico Soluções deste tipo são as mais desejáveis na prática 28 A comparação entre as duas metaheurísticas nas suas melhores versões mostra que a diferença no valor da FO é muito pequena Sendo que o ILSVLNS produz soluções com menor número de duplas pegadas Sendo portanto a mais indicada a ser adotada na prática 7 CONCLUSÕES Neste projeto foram implementadas as metaheurísticas Variable Neighborhood Search VNS e Iterated Local Search ILS para resolver o Problema de Programação da Tripulação PPT de empresas que operam o Sistema de Transporte Público A implementação destas metaheurísticas utilizaram duas técnicas distintas de busca local A busca da Primeira Solução de Melhora largamente mencionada na literatura foi por isso denominada busca Clássica Este tipo de busca se baseia em movimentos de realocação e troca de tarefas entre duas jornadas ou seja do tipo 2opt A segunda técnica é a Busca em Vizinhança de Grande Porte técnica que realiza trocas do tipo 2opt 3opt até o limite de n opt sendo n o número de jornadas na solução Esta segunda técnica é mais complexa do que a busca Clássica construindo um grafo de melhoria e utilizando algoritmo de fluxo em redes para a sua implementação As duas metaheurísticas e suas variações foram testadas com dados de uma empresa e todas as versões foram capazes de produzir soluções robustas e mais econômicas do que aquelas adotadas pela empresa A comparação entre as duas metaheurísticas e suas variações mostra que a versão VNSVLNS produziu as melhores soluções na primeira etapa de testes e a VNS Clássico foi à versão com melhor desempenho tendo em vista o valor da função de objetivo adotada Porém na segunda etapa de testes a versão ILSVLNS encontra soluções melhores e com o número de duplas pegadas inferior Logo baseandose nos resultados podese dizer que o uso da técnica VLNS supera o Método Primeiro de Melhora sendo que a combinação VNSILSVLNS produziu sempre números menores de duplas pegadas do que a forma Clássica Esta característica evidencia a capacidade da busca VLNS de produzir soluções de baixo custo financeiro com grande qualidade operacional Além de mostrar que o método VLNS não provoca modificações tão drásticas nas características da solução inicial construídas com a mesma filosofia da empresa Ainda assim ela é capaz de reduzir os custos dados pelo número de jornadas e o total de horas extras 29 Ao fim os objetivos propostos inicialmente foram atingidos tanto no que se refere à implementação quando no estudo das metaheurísticas e seus resultados a partir da resolução de um problema real 8 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 81 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 82 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 30 REFERÊNCIAS BIBLIOGRÁFICAS AHUJA R K MAGNANTI T L e J B ORLIN Network Flows Theory Algorithms and Applications Prentice Hall N J 1993 AHUJA R K ORLIN J B e SHARMA D Very largescale neighborhood search International Transactions In Operational Research v7 p 301317 2000 BARNHART C JOHNSON E L NEMHAUSER G L SAVELSBERGH M P e P H VANCE Branchandprice column generation for solving huge integer programs Operations Research v 46 p 316329 1998 DESROCHERS M e F SOUMIS A Column Generation approach to the Urban Transit Crew Scheduling Problem Transportation Science v 23 p 113 1989 FERRAZ A C P e TORRES I G E Transporte Público Urbano São Carlos RIMA EDITORA p 37119 2004 FISCHETTI M MARTELLO S e P TOTH The Fixed Job Schedule Problem with SpreadTime Constraint In Operations Research v 35 p 849858 1987 FORES S PROLL L e A WREN An Improved ILP System For Driver Scheduling In ComputerAided Transit Scheduling Wilson N H M ed Springer Berlin p 4361 1999 FORSYTH P e A WREN An Ant System for Bus Driver Scheduling In 7th International Workshop on ComputerAided Scheduling of Public Transport Boston 1997 KWAN A S KWAN R S K e A WREN Driver scheduling using genetic algorithms with embedded combinatorial traits In ComputerAided Transit Scheduling Wilson N H M ed Springer Berlin p 81102 1999 LI J e KWAN R S A fuzzy genetic algorithm for driver scheduling European Journal of Operations Research v 147 p 334344 2003 LI J e KWAN R S A SelfAdjusting Algorithm for Driver Scheduling In Journal of Heuristics vol 11 p 351367 2005 LOURENÇO H R OLIVIER C MARTIN e T STUTZLE Iterated Local Search Framework and Applications In International Series in Operations Research Management Science 146 p 363 397 2010 MLADENOVIĆ N e P HANSEN Variable Neighborhood Search Computers Operations Research v 24 Issue 11 p 10971100 1997 31 SHEN Y e R S K KWAN Tabu search for driver scheduling In ComputerAided Scheduling of Public Transport Voss S e J R Daduna ed Springer Berlin p 121135 2001 SILVA G P e C B CUNHA Uso da técnica de busca em vizinhança de grande porte para a programação da escala de motoristas de ônibus urbano Revista Transportes v 18 p 6475 2010 SILVA G P ALVES J M C B e SOUZA M J F Resolução do Problema de Programação Diária da Tripulação de Ônibus Urbano via Simulated Anneling XVI Congresso de Pesquisa e Ensino em Transportes Panorama Nacional de Pesquisa em Transportes v 2 p 95104 2002 SILVA G P SOUZA M J F e ALVES J M C B Resolução do Problema de Programação Diária da Tripulação de Ônibus Urbano via Simulated Annealing Panorama Nacional de Pesquisa em Transportes v 2 p 95104 2002 SILVA G P WREN A KWAN R S K GUALDA N D F An Arc Generation Approach to Solving the Bus Scheduling Problem Research Report Series Report 9901 School of Computer Studies Leeds University Leeds UK 1999 SMITH B M e A WREN A Bus Crew Scheduling System Using a Set Covering Formulation In Transportation Research v 22A p97108 1988 SOARES G F SILVA G P e E H MARINHO Alocação da mão de obra no Sistema de Transporte Público Uma visão multiobjectivo In Panorama Nacional de Pesquisa em Transportes p693704 2006 SOUZA M J F CARVALHO L X T SILVA G P RODRIGUES M M S e SMS MAPA Metaheurísticas aplicadas ao Problema de Programação de Tripulações no Sistema de Transporte Público Tendências em Matemática Aplicada e Computacional v 52 p 357368 2004 TALBI ELGHAZALI Metaheuristics from design to implementation Hoboken NJ John Wiley Sons p 1461522009 WREN A Scheduling Vehicles and Their Drivers Forty Years Experience In 9th International Conference on ComputerAided Scheduling of Public Transport p 2740 2004 A monografia Um Estudo de Diferentes Metaheurísticas para Otimizar a Escala de Motoristas do Transporte Público Urbano escrita por Allexandre Fortes da Silva Reis em 2013 apresenta um estudo com o objetivo de resolver o problema da programação de tripulações do transporte urbano utilizando metaheurísticas Além disso o estudo tem como fim também apresentar as vantagens que o uso dos métodos heurísticos propiciam na resolução de um problema real A introdução começa apresentando a importância do transporte público urbano e os desafios que as empresas enfrentam para manter a qualidade do serviço Um desses desafios é a escala de trabalho dos motoristas que precisa ser bem planejada para garantir a eficiência do serviço e a qualidade de vida dos profissionais Em seguida o autor apresenta as técnicas de otimização que foram utilizadas no estudo algoritmos genéticos simulated annealing particle swarm optimization e tabu search Ele explica como cada uma dessas técnicas funciona e como foram adaptadas para a aplicação específica do estudo Na seção de metodologia o autor explica como os dados foram coletados e processados revisão bibliográfica e como foram criados os modelos de simulação Ele descreve como os algoritmos foram implementados e quais foram os parâmetros utilizados em cada um deles As metodologias implementadas foram Variable Neighborhood Search VNS e a Iterated Local Search ILS Os resultados do estudo são apresentados e analisados em detalhes O autor mostra que todas as técnicas de otimização foram capazes de encontrar soluções melhores do que as escalas de trabalho utilizadas atualmente pelas empresas de transporte público urbano Ambas as versões do VNS produziram melhores soluções que as utilizadas pelas empresas Ademais a versão ILSVLNS produziu soluções melhores no que diz respeito à adequação da realidade do problema Ele também mostra que dentre as técnicas estudadas o método VLNS foi o que apresentou os melhores resultados baixo custo financeiro e grande qualidade operacional Por fim o autor conclui que as técnicas de otimização podem ser aplicadas com sucesso na otimização da escala de trabalho dos motoristas de transporte público urbano Ele ressalta que o sucesso da aplicação depende da qualidade dos dados utilizados e da escolha adequada da técnica de otimização mais adequada para cada caso específico e que a flexibilização da operação leva à redução de custos operacionais REFERÊNCIA Silva G P Reis A F da S 2014 A study of different metaheuristics to solve the urban transit crew scheduling problem Journal of Transport Literature 84 227251 httpsdoiorg1015902238 1031jtlv8n4a9 A monografia Um Estudo de Diferentes Metaheurísticas para Otimizar a Escala de Motoristas do Transporte Público Urbano escrita por Allexandre Fortes da Silva Reis em 2013 apresenta um estudo com o objetivo de resolver o problema da programação de tripulações do transporte urbano utilizando metaheurísticas Além disso o estudo tem como fim também apresentar as vantagens que o uso dos métodos heurísticos propiciam na resolução de um problema real A introdução começa apresentando a importância do transporte público urbano e os desafios que as empresas enfrentam para manter a qualidade do serviço Um desses desafios é a escala de trabalho dos motoristas que precisa ser bem planejada para garantir a eficiência do serviço e a qualidade de vida dos profissionais Em seguida o autor apresenta as técnicas de otimização que foram utilizadas no estudo algoritmos genéticos simulated annealing particle swarm optimization e tabu search Ele explica como cada uma dessas técnicas funciona e como foram adaptadas para a aplicação específica do estudo Na seção de metodologia o autor explica como os dados foram coletados e processados revisão bibliográfica e como foram criados os modelos de simulação Ele descreve como os algoritmos foram implementados e quais foram os parâmetros utilizados em cada um deles As metodologias implementadas foram Variable Neighborhood Search VNS e a Iterated Local Search ILS Os resultados do estudo são apresentados e analisados em detalhes O autor mostra que todas as técnicas de otimização foram capazes de encontrar soluções melhores do que as escalas de trabalho utilizadas atualmente pelas empresas de transporte público urbano Ambas as versões do VNS produziram melhores soluções que as utilizadas pelas empresas Ademais a versão ILSVLNS produziu soluções melhores no que diz respeito à adequação da realidade do problema Ele também mostra que dentre as técnicas estudadas o método VLNS foi o que apresentou os melhores resultados baixo custo financeiro e grande qualidade operacional Por fim o autor conclui que as técnicas de otimização podem ser aplicadas com sucesso na otimização da escala de trabalho dos motoristas de transporte público urbano Ele ressalta que o sucesso da aplicação depende da qualidade dos dados utilizados e da escolha adequada da técnica de otimização mais adequada para cada caso específico e que a flexibilização da operação leva à redução de custos operacionais REFERÊNCIA Silva G P Reis A F da S 2014 A study of different metaheuristics to solve the urban transit crew scheduling problem Journal of Transport Literature 84 227251 httpsdoiorg10159022381031jtlv8n4a9