UNIVERSIDADE FEDERAL DE OURO PRETO
Uma Abordagem Hı́brida para Resolver
o Problema da Escala de Motoristas de
Ônibus Urbano
Danilo Santos Souza
Universidade Federal de Ouro Preto
Orientador: Gustavo Peixoto Silva
Coorientador: Haroldo Gambini Santos
Dissertação submetida ao Instituto de Ciências
Exatas e Biológicas da Universidade Federal de
Ouro Preto para obtenção do tı́tulo de Mestre
em Ciência da Computação
Ouro Preto, Julho de 2014
Uma Abordagem Hı́brida para Resolver
o Problema da Escala de Motoristas de
Ônibus Urbano
Danilo Santos Souza
Universidade Federal de Ouro Preto
Orientador: Gustavo Peixoto Silva
Coorientador: Haroldo Gambini Santos
S729a
Souza, Danilo Santos.
Uma abordagem híbrida para resolver o problema da escala de motoristas de
ônibus urbano [manuscrito] / Danilo Santos Souza. – 2014.
83 f.: il. color., grafs., tabs.
Orientadores: Prof. Dr. Gustavo Peixoto Silva e Haroldo Gambini Santos.
Dissertação (Mestrado) - Universidade Federal de Ouro Preto. Instituto de
Ciências Exatas e Biológicas. Departamento de Computação.
Área de concentração: Otimização e inteligência computacional.
1. Metaheurísticas - Teses. 2. Inteligência artificial - Teses. I. Silva, Gustavo
Peixoto. II. Santos, Haroldo Gambini. III. Universidade Federal de Ouro Preto.
IV. Título.
CDU: 681.3.091
Catalogação: [email protected]
CDU: 669.162.16
Dedico este trabalho a você que sempre me fez acreditar na realização dos meus sonhos
e trabalhou muito para que eu pudesse realizá-los, Mãe. A minha famı́lia e amigos que
sempre me apoiaram nas horas difı́ceis. Ao meu pai, que mesmo distante influenciou
para que pudesse chegar até aqui.
ii
iii
Uma Abordagem Hı́brida para Resolver o Problema da
Escala de Motoristas de Ônibus Urbano
Resumo
A alocação da tripulação (motoristas e cobradores) é uma etapa muito importante no
planejamento operacional do Sistema de Transporte Público visto que custo operacional
representado pelas escalas de trabalho compõe uma parcela significativa nos custos totais
de uma empresa de transporte público. A redução dos custos das escalas de trabalho
afetam não só as empresas operadoras, mas também os usuários deste serviço, pois com
esta redução há a possibilidade de um maior investimento na qualidade do transporte
público e a redução dos preços dos bilhetes. Estes custos, estão estritamente relacionados
as normas operacionais impostas pelas empresas e legislações trabalhistas que se refletem
na definição das jornadas de trabalho dos motoristas e cobradores.
Esse trabalho tem a finalidade de propor um novo método computacional capaz de
auxiliar o processo da programação da tripulação em empresas de transporte público
de ônibus urbano. Os métodos apresentados nesta pesquisa são baseados no uso de
um modelo de programação linear inteira, ainda inédito na literatura, se diferindo dos
demais pelo fato de que cada jornada é gerada diretamente a partir das tarefas a serem alocadas. Uma metaheurı́stica Late Acceptance Hill Climbing (LAHC) também
foi utilizada com o objetivo de resolver problemas de maiores dimensões. Um método
hı́brido, utilizando o método exato e a metaheurı́stica LAHC, é proposto com o objetivo
de obter um refinamento das soluções obtidas pela metaheurı́stica, de modo a reduzir os
custos das jornadas geradas. Para avaliar as abordagens apresentadas foram utilizadas
instâncias geradas a partir de dados reais de uma empresa do setor de transporte público
da cidade de Belo Horizonte/MG. Os modelos computacionais propostos apresentaram
resultados satisfatórios, sendo que os custos finais foram reduzidos para a maioria dos
testes realizados. Por outro lado, há a necessidade de novos estudos sobre os métodos
apresentados, a fim de que os mesmos se tornem mais eficientes.
Palavras-chave: Matheurı́stica, Problema de Programação de Tripulações, Metaheurı́stica.
iv
A Hybrid Approach to Solve the Problem of Scale for
Urban Bus Drivers
Abstract
The allocation of crew (drivers and collectors) is a quite important stage of operational planning of Public Transit System once the operational cost represented by the
work schedules consist in a significant portion of total costs in a public transit company.
Cost reduction of work schedules affects not only the operating company but also the
users of this service since there is chance of higher investments in transit quality and
reduction of ticket prices because of this cost-cutting. These costs are strictly related to
the operational rules established by companies and work laws which reflects themselves
in the transit drivers and collectors work schedule definition.
The goal of this work is to propose a new computational method able to assist the
crew planning process in urban bus public transit companies. The methods presented in
this work are based on use of an integer linear programming method even unpublished in
literature, being different from others due the fact that each schedule is created directly
from tasks to be allocated. A metaheuristic Late Acceptance Hill Climbing (LAHC) was
also utilized with the purpose of solving bigger problems. A hybrid method using the
exact method and the metaheuristic LAHC is proposed with the goal of refining solutions
gotten through metaheuristic, reducing created schedule costs. To evaluate the presented
approaches, problems generated from real data from a public transit company from
Belo Horizonte/MG city were used. The proposed computational methods presented
satisfactory results and final costs were reduced for most tests performed. On the other
hand, other researches about the presented methods are necessary in order that they
become more efficient.
Keywords: Matheuristic, Crew Scheduling Problem, Metaheuristic.
v
Declaração
Esta dissertação é resultado de meu próprio trabalho, exceto onde referência explı́cita é
feita ao trabalho de outros, e não foi submetida para outra qualificação nesta nem em
outra universidade.
Danilo Santos Souza
vi
Agradecimentos
Primeiramente agradeço à Deus por me amparar nos momentos difı́ceis e me dar
força para superar as dificuldades.
Aos meus pais, Gilsa e Denildo, e a meu irmão Diego, pelo incentivo, apoio e afeto.
A minha avó Carmelita, pelo exemplo de dedicação e por ser uma mãe pra mim.
Ao meu Tio Denilson, por sempre acreditar em mim quando alguns não acreditavam,
e por ser um exemplo de pai e homem.
À toda minha famı́lia, pelo carinho e força.
Agradeço ao meu orientador Gustavo Peixoto Silva pela oportunidade concedida, pela
impecável orientação e pelo apoio no desenvolvimento do trabalho. Agradeço ainda ao
meu Coorientador Haroldo Gambini Santos pelas valiosas contribuições para o presente
trabalho.
Aos meus amigos Bruna, Priscilla, Gabriela, Thayane, Lorran, Aristides, Alisson,
Pereira, Lucas, Marco, Emilia, Danielle e Flavio pela ajuda, pelas longas horas de
estudo, amizade, carinho e força, fundamentais para que eu conseguisse chegar até aqui.
À República Navio Pirata, Moradores e Ex-alunos, por me acolherem, pelo companheirismo e amizade, tornando esta minha segunda casa.
Ao CNPq, à FAPEMIG, à CAPES e à UFOP pelo apoio recebido no desenvolvimento
deste trabalho.
Ao PPGCC - UFOP, professores e técnicos, em especial aos professores Fabrı́cio,
Gustavo e Haroldo, e a Mariana pela ajuda sempre que fez-se necessário.
Enfim, agradeço a todos que, de alguma forma, acreditaram e torceram por mim,
participaram de minha vida e ajudaram na realização deste trabalho.
Sumário
Lista de Figuras
ix
Lista de Tabelas
x
Lista de Algoritmos
xiii
Nomenclatura
1
1 Introdução
2
1.1
Objetivo Geral . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5
1.2
Objetivos Especı́ficos . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5
1.3
Organização do Trabalho . . . . . . . . . . . . . . . . . . . . . . . . . . .
5
2 Revisão Bibliográfica
6
2.1
Métodos Exatos para Resolver o PPT . . . . . . . . . . . . . . . . . . . .
7
2.2
Metaheurı́sticas para Resolver o PPT . . . . . . . . . . . . . . . . . . . .
9
2.3
Métodos Hı́bridos para resolver o PPT . . . . . . . . . . . . . . . . . . .
12
3 Problema de Programação da Tripulação de Ônibus Urbano
3.1
Restrições do Problema . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4 Métodos Propostos
14
15
17
4.1
Estruturas para a Representação do Problema . . . . . . . . . . . . . . .
17
4.2
Modelo Matemático Proposto . . . . . . . . . . . . . . . . . . . . . . . .
19
4.2.1
19
Parâmetros e Conjuntos . . . . . . . . . . . . . . . . . . . . . . .
vii
viii
4.3
4.4
SUMÁRIO
4.2.2
Variáveis de Decisão . . . . . . . . . . . . . . . . . . . . . . . . .
20
4.2.3
Função Objetivo . . . . . . . . . . . . . . . . . . . . . . . . . . .
21
4.2.4
Conjunto de Restrições . . . . . . . . . . . . . . . . . . . . . . . .
21
A Metaheurı́stica LAHC . . . . . . . . . . . . . . . . . . . . . . . . . . .
25
4.3.1
Função Objetivo . . . . . . . . . . . . . . . . . . . . . . . . . . .
26
4.3.2
Geração da Solução Inicial . . . . . . . . . . . . . . . . . . . . . .
26
4.3.3
Estrutura de Vizinhança Realoca-Troca . . . . . . . . . . . . . . .
27
Matheurı́stica . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
28
4.4.1
29
Particionamento da Solução . . . . . . . . . . . . . . . . . . . . .
5 Resultados e Discussão
31
5.1
Resultados Obtidos pelo Modelo Exato . . . . . . . . . . . . . . . . . . .
31
5.2
Resultados Obtidos pelo LAHC e a Matheurı́stica . . . . . . . . . . . . .
37
5.2.1
Calibração da Metaheurı́stica . . . . . . . . . . . . . . . . . . . .
37
5.2.2
Comparação entre a Matheurı́stica, LAHC e demais Metaheurı́sticas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
40
6 Conclusões e Trabalhos Futuros
59
A Apêndices
62
A.1 Publicações . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Referências Bibliográficas
62
63
Lista de Figuras
4.1
4.2
Movimentos de realocação e troca de uma tarefa da jornada j para a
jornada k . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
28
Representação da Matheurı́stica implementada para o Problema de Programação da Tripulação . . . . . . . . . . . . . . . . . . . . . . . . . . .
29
ix
Lista de Tabelas
4.1
Estrutura de uma tarefa . . . . . . . . . . . . . . . . . . . . . . . . . . .
17
4.2
Estrutura de uma jornada . . . . . . . . . . . . . . . . . . . . . . . . . .
18
5.1
Caracterı́sticas dos problemas gerados para o caso 1 . . . . . . . . . . . .
33
5.2
Resultados do modelo exato para os problemas para o caso 1 . . . . . . .
33
5.3
Caracterı́sticas dos problemas gerados para o caso 2 . . . . . . . . . . . .
34
5.4
Resultados do modelo exato para os problemas do caso 2 . . . . . . . . .
34
5.5
Caracterı́sticas dos problemas gerados para o caso 3 . . . . . . . . . . . .
35
5.6
Resultados do modelo exato para os problemas para o caso 3 . . . . . . .
35
5.7
Caracterı́sticas dos problemas gerados para o caso 4 . . . . . . . . . . . .
36
5.8
Resultados do modelo exato para os problemas para o caso 4 . . . . . . .
36
5.9
Tabela com as informações de cada instância, contendo a quantidade de
tarefas a serem realizadas e quantos veı́culos são utilizados. . . . . . . . .
37
5.10 Resultados do primeiro teste de calibração da Metaheurı́stica LAHC para
os valores de tamanho de lista: 10, 20, 30, 40, 50, 100 e 150 . . . . . . . .
38
5.11 Resultados do primeiro teste de calibração da Metaheurı́stica LAHC para
os valores de tamanho de lista: 200, 250, 300, 350, 400, 450 e 500 . . . .
39
5.12 Resultados do segundo teste de calibração da Metaheurı́stica LAHC para
os valores de tamanho de lista: 40, 50, 100 e 300 . . . . . . . . . . . . . .
40
5.13 Caracterı́sticas dos melhores resultados para a instância 01 com custo 600
para jornadas do tipo dupla pegada . . . . . . . . . . . . . . . . . . . . .
42
5.14 Melhorias da Matheurı́stica em relação aos métodos LAHC, VNS, VNSVLNS, ILS e ILS - VLNS para a instância 01 com custo 600 para jornadas
do tipo dupla . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
43
x
LISTA DE TABELAS
xi
5.15 Caracterı́sticas dos melhores resultados para a instância 02 com custo 600
para jornadas do tipo dupla pegada . . . . . . . . . . . . . . . . . . . . .
43
5.16 Melhorias da Matheurı́stica em relação aos métodos LAHC, VNS, VNSVLNS, ILS e ILS-VLNS para a instância 02 com custo 600 para jornadas
do tipo dupla pegada . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
44
5.17 Caracterı́sticas dos melhores resultados para a instância 03 com custo 600
para jornadas do tipo dupla pegada . . . . . . . . . . . . . . . . . . . . .
44
5.18 Melhorias da Matheurı́stica em relação aos métodos LAHC, VNS, VNSVLNS, ILS e ILS-VLNS para a instância 03 com custo 600 para jornadas
do tipo dupla pegada . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
45
5.19 Caracterı́sticas dos melhores resultados para a instância 04 com custo 600
para jornadas do tipo dupla pegada . . . . . . . . . . . . . . . . . . . . .
45
5.20 Melhorias da Matheurı́stica em relação aos métodos LAHC, VNS, VNSVLNS, ILS e ILS-VLNS para a instância 04 com custo 600 para jornadas
do tipo dupla pegada . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
46
5.21 Caracterı́sticas dos melhores resultados para a instância 05 com custo 600
para jornadas do tipo dupla pegada . . . . . . . . . . . . . . . . . . . . .
46
5.22 Melhorias da Matheurı́stica em relação aos métodos LAHC, VNS, VNSVLNS, ILS e ILS-VLNS para a instância 05 com custo 600 para jornadas
do tipo dupla pegada . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
47
5.23 Caracterı́sticas dos melhores resultados para a instância 06 com custo 600
para jornadas do tipo dupla pegada . . . . . . . . . . . . . . . . . . . . .
47
5.24 Melhorias da Matheurı́stica em relação aos métodos LAHC, VNS, VNSVLNS, ILS e ILS-VLNS para a instância 06 com custo 600 para jornadas
do tipo dupla pegada . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
48
5.25 Caracterı́sticas dos melhores resultados para a instância 07 com custo 600
para jornadas do tipo dupla pegada . . . . . . . . . . . . . . . . . . . . .
48
5.26 Melhorias da Matheurı́stica em relação aos métodos LAHC, VNS, VNSVLNS, ILS e ILS-VLNS para a instância 07 com custo 600 para jornadas
do tipo dupla pegada . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
49
5.27 Valores da função objetivo para os melhores resultados obtidos para todas
as instâncias e com peso 600 para as jornadas do tipo dupla pegada . . .
49
5.28 Caracterı́sticas dos melhores resultados para a instância 01 com custo
5.000 para jornadas do tipo dupla pegada . . . . . . . . . . . . . . . . . .
50
xii
LISTA DE TABELAS
5.29 Melhorias da Matheurı́stica em relação aos métodos LAHC, VNS e VNSVLNS para a instância 01 com custo 5.000 para jornadas do tipo dupla
pegada . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
51
5.30 Caracterı́sticas dos melhores resultados para a instância 02 com custo
5.000 para jornadas do tipo dupla pegada . . . . . . . . . . . . . . . . . .
51
5.31 Melhorias da Matheurı́stica em relação aos métodos LAHC, VNS e VNSVLNS para a instância 02 com custo 5.000 para jornadas do tipo dupla
pegada . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
52
5.32 Caracterı́sticas dos melhores resultados para a instância 03 com custo
5.000 para jornadas do tipo dupla pegada . . . . . . . . . . . . . . . . . .
53
5.33 Melhorias da Matheurı́stica em relação aos métodos LAHC, VNS e VNSVLNS para a instância 03 com custo 5.000 para jornadas do tipo dupla .
53
5.34 Caracterı́sticas dos melhores resultados para a instância 04 com custo
5.000 para jornadas do tipo dupla pegada . . . . . . . . . . . . . . . . . .
54
5.35 Melhorias da Matheurı́stica em relação aos métodos LAHC, VNS e VNSVLNS para a instância 04 com custo 5.000 para jornadas do tipo dupla
pegada . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
54
5.36 Caracterı́sticas dos melhores resultados para a instância 05 com custo
5.000 para jornadas do tipo dupla pegada . . . . . . . . . . . . . . . . . .
55
5.37 Melhorias da Matheurı́stica em relação aos métodos LAHC, VNS e VNSVLNS para a instância 05 com custo 5.000 para jornadas do tipo dupla
pegada . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
55
5.38 Caracterı́sticas dos melhores resultados para a instância 06 com custo
5.000 para jornadas do tipo dupla pegada . . . . . . . . . . . . . . . . . .
56
5.39 Melhorias da Matheurı́stica em relação aos métodos LAHC, VNS e VNSVLNS para a instância 06 com custo 5.000 para jornadas do tipo dupla
pegada . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
56
5.40 Caracterı́sticas dos melhores resultados para a instância 07 com custo
5.000 para jornadas do tipo dupla pegada . . . . . . . . . . . . . . . . . .
57
5.41 Melhorias da Matheurı́stica em relação aos métodos LAHC, VNS e VNSVLNS para a instância 07 com custo 5.000 para jornadas do tipo dupla
pegada . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
57
5.42 Melhores resultados obtidos da função objetivo para todas as instâncias
com peso 5.000 para as jornadas do tipo dupla pegada . . . . . . . . . .
58
Lista de Algoritmos
4.1
Implementação do LAHC para um problema de minimização
. . . . . . .
26
4.2
Particionamento da solução . . . . . . . . . . . . . . . . . . . . . . . . . .
30
xiii
“Talvez não tenha conseguido fazer o melhor, mas lutei para que o melhor fosse feito.
Não sou o que deveria ser, mas Graças a Deus, não sou o que era antes.”
— Marthin Luther King
xiv
Nomenclatura
GRASP Greedy Randomized Adaptive Search Procedure
ILS
Iterated Local Search
LAHC
Late Acceptance Hill Climbing
MPL
Mathematical Programming Language
PPT
Problema de Programação de Tripulações
VND
Variable Neighborhood Descent
VNS
Variable Neighborhood Search
VLNS
Very Large-Scale Neighborhood Search
1
Capı́tulo 1
Introdução
Atualmente no ramo empresarial há uma necessidade cada vez maior pela utilização
de ferramentas computacionais para auxiliar no processo de tomada de decisões. Tal
fato acontece devido à possibilidade de redução nos custos da empresa, seja no nı́vel
estratégico, tático ou operacional. No setor de logı́stica, são exemplos de decisões operacionais: i ) a definição de rotas de transporte para entrega de cargas, ii ) a quantidade
de matéria prima a ser utilizada no processo de produção, iii ) a alocação e programação
das máquinas no processo de produção, entre outros (Novaes 2001). Nas empresas de
transporte publı́co, a utilização de ferramentas computacionais para dimensionar suas
frotas ainda é pequena, assim como para alocar seus motoristas e cobradores de maneira
econômica e equilibrada (Silva 2001). Desta forma, surge a importância de estudar e
aplicar métodos de otimização, nesta fase do processo de planejamento das empresas de
transporte público, para permitir a redução dos seus custos operacionais.
O ônibus ainda é o meio de transporte público de passageiros mais utilizado nas
cidades, sendo que em algumas delas ele é o único meio de transporte público. Assim, o
planejamento da operação das empresas deste ramo deve ser muito preciso para que a demanda dos usuários seja atendida prontamente e com o menor custo possı́vel. A redução
dos custos, decorrente de um melhor planejamento, é de fundamental importância para
as empresas. Além de um fator de sobrevivência, essa economia pode ser reinvestida em
outras áreas, como na qualificação dos seus funcionários, na manutenção da frota, entre
outros. Desta forma, a qualidade do serviço pode ser melhorada, assim como o retorno
à empresa. Logo, a utilização de técnicas e ferramentas computacionais podem trazer
benefı́cios para as empresas deste setor (Wren 2004).
2
Introdução
3
O desenvolvimento e a utilização de sof twares para auxiliar o processo de tomada
de decisão, em empresas de transporte público brasileiro, tem um histórico de pouca
utilização (Silva 2001). Isso ocorre por que tais métodos requerem a obtenção de dados
precisos da operação das frotas, o cumprimento de regras especı́ficas, o treinamento do
pessoal, entre outros outros fatores que geram custos adicionais e requerem a mudança
na forma de operação das empresas. Mesmo com essas dificuldades, é importante que
métodos de otimização adequados à realidade brasileira sejam elaborados e sua utilização
disseminada entre as empresas de transportes público, propiciando benefı́cios tanto para
as empresas como para os usuários do sistema.
O planejamento de transporte público urbano é uma tarefa muito delicada pois o
mesmo envolve tanto o poder público quanto as empresas de prestação de serviço. Uma
série de decisões operacionais devem ser tomadas neste planejamento. Primeiramente,
deve-se definir quais as linhas de transporte que irão operar, ou seja, definir quais serão
as rotas das linhas necessárias para cobrir todas as regiões desejadas de uma determinada cidade, definindo também os pontos de parada de cada rota. Com a definição da
trajetória das linhas a serem operadas, deve-se então definir o horário de partida de
cada viagem em cada linha sob a responsabilidade da empresa. Isto é, deve-se definir o
quadro de horários das linhas para os dias úteis, os sábados e os domingos/feriados. A
variação no quadro de horários se deve pela variação na demanda nos diferentes dias da
semana.
Numa segunda etapa deve-se fazer a alocação dos veı́culos que realizarão as viagens
de cada linha. Este problema é conhecido na literatura como Problema de Programação
dos Veı́culos. Nesta etapa procura-se definir a quantidade mı́nima de veı́culos necessários
para realizar todas as viagens previstas no quadro de horários de cada linha, gerado na
etapa anterior, e especificar o veı́culo que realizará cada viagem. A resolução deste
problema procura minimizar não apenas o número de veı́culos, mas também as viagens
ociosas e o tempo ocioso dos veı́culos nos terminais.
Na etapa seguinte deve ser definida a quantidade mı́nima de tripulantes (motorista e
cobrador) e como estes serão alocados de modo a cobrir todas as viagens dos veı́culos em
operação. Desta forma são definidas as jornadas que cada tripulação da empresa deverá
cumprir em um dia de trabalho. Este problema é denominado Problema de Programação
da Tripulação e tem como objetivo minimizar o total de tripulantes e o custo com horas
extras e ociosas contidas na escala diária.
A última etapa consiste em definir o rodı́zio das tripulações. Esta etapa tem como
4
Introdução
objetivo gerar as escalas mensais das tripulações de modo a cobrir todas as jornadas
respeitando as regras especificas para a atividade, como por exemplo as folgas da tripulação, o número máximo de dias trabalhados consecutivamente, entre outras. Este
problema é conhecido na literatura como Problema do Rodı́zio das Tripulações. Nesta
etapa é possı́vel realizar a compensação de horas extras com horas ociosas, realizadas
no mesmo mês, por uma determinada tripulação.
A definição das linhas e do quadro de horários é de responsabilidade do poder público,
enquanto a programação dos veı́culos e tripulações e o rodı́zio das tripulações ficam a
cargo das empresas de transporte público. O processo de planejamento operacional
descrito acima é geralmente realizado na ordem apresentada e a solução de cada etapa
é usada como dado de entrada da etapa seguinte.
A abordagem de todos os problemas do sistema de transporte em um único modelo
pode ser uma tarefa computacionalmente impossı́vel. Logo, este trabalho dedica-se exclusivamente ao tratamento do Problema de Programação da Tripulação (PPT). Devido
às restrições operacionais vigentes, restrições das empresas e das leis trabalhistas, este
problema especificamente torna-se de grande complexidade. O problema pode ser modelado como um problema de particionamento ou de recobrimento com variáveis binárias,
o que o torna NP-hard, para o qual não existe algoritmo de complexidade polinomial
que obtenha a solução ótima (Fischetti et al. 1987). Este problema vem sendo estudado
desde a década de 60, tendo Elias (1964) como trabalho pioneiro. Devido às constantes
mudanças no sistema de transporte público, várias pesquisas são realizadas ainda hoje
para representar e resolver o problema de forma mais precisa e eficiente.
Devido à complexidade deste problema, a utilização de métodos exatos fica restrita,
impossibilitando a resolução de problemas reais, que normalmente são de grandes dimensões. Assim, os métodos heurı́sticos se tornam uma alternativa e são amplamente
utilizados para resolver o problema (Ernst et al. 2004b).
O presente trabalho apresenta um modelo de programação linear inteira ainda inédito
na literatura. Para agilizar a resolução de problemas de grande porte, foi utilizada uma
abordagem hı́brida que combina a heurı́stica Late Acceptance Hill Climbing (LAHC)
com o modelo exato proposto. O modelo exato consiste em gerar jornadas de trabalho a
partir das viagens a serem realizadas. Desta forma, o modelo não utiliza a formulação de
particionamento de conjuntos. Este modelo é inédito e não necessita gerar as jornadas
previamente, como acontece no modelo de particionamento.
Introdução
1.1
5
Objetivo Geral
Este trabalho tem como objetivo resolver o Problema da Programação de Tripulação
de Ônibus Urbano de modo a reduzir o máximo possı́vel os custos operacionais na
atribuição das viagens às tripulações, utilizando técnicas exatas e heurı́sticas. Assim foi
implementado um modelo exato de programação linear inteira, uma metaheurı́stica e a
combinação de ambos, resultando em um modelo do tipo Matheurı́stica. Os métodos
foram avaliados quanto às vantagens e desvantagens destas abordagens na resolução de
problemas reais.
1.2
Objetivos Especı́ficos
• Resolver o PPT utilizando um modelo exato e verificar a dimensão máxima do
problema que o método é capaz de resolver;
• Resolver o PPT utilizando a metaheurı́stica Late Acceptance Hill Climbing LAHC;
• Resolver o PPT utilizando uma abordagem hı́brida, que é a combinação da metaheurı́stica LAHC e do modelo exato;
• Avaliar os resultados obtidos com resultados da literatura e das soluções apresentadas pela empresa.
1.3
Organização do Trabalho
Os demais capı́tulos deste trabalho estão organizados da seguinte forma: No Capı́tulo
2 é apresentada uma revisão bibliográfica do problema, abordando alguns métodos de
fundamental importância para este trabalho. No Capı́tulo 3 é descrito o Problema de
Programação da Tripulação para Ônibus de Transporte Público Urbano. No Capı́tulo 4
são apresentadas as metodologias implementadas para resolver o problema trabalhado.
No Capı́tulo 5 são apresentados os resultados e suas considerações para o problema. No
Capı́tulo 6 são apresentadas as conclusões finais e propostas de trabalhos futuros.
Capı́tulo 2
Revisão Bibliográfica
O PPT é um problema clássico, sobre o qual existem diversos trabalhos que exploram
diferentes técnicas de programação linear inteira para resolvê-lo. Entre estas técnicas são
destacadas o Branch-and-Bound (Fores et al. 1999, Smith and Wren 1988), Branch-andPrice (Barnhart et al. 1998, Desrochers and Soumis 1989) e Branch-and-Cut (Friberg
and Haase 1999). Por outro lado, diversas metaheurı́sticas foram implementadas para resolver problemas de grande porte. Dentre essas pode-se destacar: Algoritmos Genéticos,
GRASP, Busca Tabu, Simulated Annealing, entre outros (Lourenço et al. 2001, Shen
and Kwan 2001, Silva and da Cunha 2010, Souza et al. 2004). Com o emprego destas meta-heurı́sticas foi possı́vel obter resultados muito satisfatórios para o problema,
embora a otimalidade das soluções não sejam garantidas.
O trabalho de Ernst et al. (2004a) apresenta uma série de problemas relacionados à
alocação de pessoal em diversas áreas, incluindo motoristas e cobradores de sistemas de
transportes. Neste contexto, os autores descrevem problemas de alocação de funcionários
em seus diferentes modais de transportes, ou seja, no aeroviário, ferroviário, transporte
urbano e no transporte interurbano. No trabalho é apresentada uma revisão sobre
as principais pesquisas tanto para o problema de programação da tripulação, como
para o problema do rodı́zio das tripulações. No trabalho é mencionado também que a
complexidade dos problemas dependem do tipo de transporte, da categoria da tripulação,
dos tipos de frotas, das regras e regulamentações, da regularidade das viagens e dos custos
a serem considerados. Segundo Ernst et al. (2004a), uma das abordagens mais utilizadas
para resolver os problemas de programação das tripulações é aquela que o decompõe nas
seguintes etapas: geração das jornadas, otimização das jornadas e definição do rodizio
da tripulação. Desta forma, a complexidade do problema é reduzida, permitindo sua
6
Revisão Bibliográfica
7
resolução de forma satisfatória.
Algumas destas técnicas de otimização são utilizadas em pacotes comerciais voltadas
para a área de programação de veı́culos e tripulações. Uma metaheurı́stica do tipo runcutting foi utilizada para resolver o problema no pacote RUCUS (Luedtke 1985, Wilhelm
1975), desenvolvido nos Estados Unidos da América a partir da década de 70, e um algoritmo desenvolvido por Parker and e Smith (1981) foi utilizado no sistema TRACS,
o qual simulava o processo manual de alocação da tripulação. A formulação de recobrimento de conjuntos foi usada no pacote IMPACS do sistema BUSMAN e no pacote
Crew-opt, que posteriormente foi utilizado na versão inicial do HASTUS que substituiu
o TRACS (Wren 2004). A empresa brasileira Wplex, desenvolvedora de sistemas no
âmbito de transporte, desenvolveu um sistema WplexON (Fournier 2009) para tratar
problemas de alocação de tripulação. Neste trabalho a empresa utiliza a abordagem de
Branch-and-Price para solucionar o problema modelado como particionamento de conjuntos, sendo que o conjunto de Jornada de Trabalho é gerada a partir do movimento
de inserção de tarefas. Estas soluções obtidas pela Wplex são utilizadas em empresas
no estado de Santa Catarina.
Nas subseções a seguir são apresentados alguns trabalhos que utilizam abordagens
Exatas, Metaheurı́sticas e Heurı́sticas Hı́bridas.
2.1
Métodos Exatos para Resolver o PPT
Os métodos exatos se mostram mais eficiente quando utilizados para resolução de problemas de otimização combinatória quando os problema são de pequena dimensão ou
não são NP-Completo. No entanto, estes métodos podem ser ineficientes para problemas NP-Completos de grande dimensão, uma vez que o tempo de execução aumenta
exponencialmente à medida que as instâncias aumentam. Ainda assim, existem várias
abordagens exatas descritas na literatura para resolver o problema. Entre elas podemos
citar a Programação Dinâmica, a Programação Linear e Inteira, Relaxação Lagrangeana, Programação por Restrições, entre outros. Muitas destas técnicas são flexı́veis
e independentes de domı́nio, e podem ser aplicadas à maioria dos problemas práticos
(Stefanello 2011).
Em Desrochers and Soumis (1989) é proposta uma abordagem de geração de colunas
para resolver o Problema de Programação da Tripulação. Nesta abordagem o problema
8
Revisão Bibliográfica
é dividido em dois: um problema de cobertura de conjunto e um problema de caminho
mı́nimo com limitação de recurso. O problema de cobertura de conjuntos escolhe uma
escala de trabalho viável já conhecida. O problema de caminho mı́nimo é usado para
propor novas escalas de trabalho para melhorar a solução obtida pelo problema de cobertura de conjuntos. Para o problema de cobertura de conjuntos, o método de geração
de colunas é representado por linhas e colunas, onde as colunas representam uma escala
viável e as linhas as tarefas a serem realizadas. O modelo deve selecionar as melhores
escalas de modo que todas as tarefas de um dia de trabalho sejam cobertas. Porém as
novas escalas são geradas usando um algoritmo de caminho mı́nimo com restrição de
recursos. Cada caminho viável, da origem ao consumidor, representa uma jornada de
trabalho viável, ou seja, uma nova coluna para o problema de cobertura de conjuntos. O
método proposto apresenta resultados satisfatório para resolver problemas considerados
pequenos, compostos de 167 e 235 tarefas.
Fores et al. (1999) apresentam um sistema baseado em programação linear inteira,
como melhoria do sistema TRACS II desenvolvido pela Universidade de Leeds, Inglaterra. Diferente da abordagem utilizada no TRACS II, que utilizava duas funções objetivos para calcular as penalidades impostas na solução, o modelo proposto por Fores
et al. (1999) utiliza uma função objetivo composta, e o método de geração de colunas
para obter a sua solução final. Os testes computacionais mostram que o modelo proposto consegue resultados melhores do que o modelo utilizado pelo sistema TRACS II, e
obteve uma redução média de 41% no tempo de processamento para o mesmo conjunto
de dados.
A abordagem branch-and-price é utilizada por Freling et al. (2004) para resolver
tanto o problema de alocação quando o problema do rodı́zio de tripulação. Para resolver o problema, os autores utilizaram uma abordagem do tipo Geração de Colunas
onde inicialmente é escolhido um conjunto de jornadas (colunas) e então é resolvido o
problema relaxando a condição de integralidade da solução. Em seguida são geradas
novas colunas que podem ser inseridas no conjunto, substituindo outra, caso esta inserção consiga reduzir o custo da solução. Esta operação se repete até que nenhuma
jornada que reduza o custo seja encontrada. Se na etapa de geração de novas colunas
não for encontrada nenhuma jornada que reduza o custo, a operação branch-and-bound
é realizada. No inicio, uma solução (nó) é gerada para realizar o branch, calculando
novos limites inferiores das duas soluções, a primeira gerada na resolução do problema
com conjunto de jornadas e a outra após o processo de geração de colunas. Logo após,
verifica-se se o novo custo é menor do que o melhor custo. Então o método verifica se
Revisão Bibliográfica
9
todas as restrições estão sendo atendidas e o processo de branch-and-bound é iniciado
novamente até que a condição de parada seja atendida. Os testes foram realizado em
problemas de alocação de tripulações de aeronaves para instâncias pequenas. O modelo
teve como objetivo minimizar o número de tarefas descobertas e o número de tripulantes.
Santos and Mateus (2007) utilizam uma abordagem exata de Geração de Colunas
combinada com a metaheurı́stica populacional Algoritmos Genéticos para resolver o
PPT. Na geração de colunas, o problema é subdividido em dois: problema mestre e subproblema. O problema mestre seleciona as jornadas que serão realizadas pela tripulação
em um conjunto de jornadas viáveis, de modo a conseguir cobrir todas as viagens necessárias. Já o subproblema é responsável por gerar novas jornadas (colunas). Estas
jornadas são adicionadas ao problema mestre se possibilitarem a melhoria da solução.
Para a resolução do subproblema é utilizado um Algoritmo Genético. Os resultados
obtidos mostram que a utilização do Algoritmo Genético, em comparação com outras
metaheurı́sticas, destaca-se pelo fato da possibilidade de geração de um conjunto maior
de jornadas viáveis para a inclusão no problema mestre e consequentemente possibilita
reduzir o tempo de processamento quando lida com grandes instâncias.
2.2
Metaheurı́sticas para Resolver o PPT
Lourenço et al. (2001) utilizam duas metaheurı́sticas multiobjetivos para solucionar o
PPT, a Busca Tabu e um Algoritmo Genético. Na abordagem apresentada, são consideradas duas funções objetivo, uma com os custos operacionais do problema ao que se
refere a quantidade de tripulantes e tempo operacional, e custos por quebra de restrições
operacionais, por exemplo exceder o máximo de trocas de veı́culos. Na Busca Tabu, os
autores consideram duas listas tabu, uma de inserção e outra de remoção de jornadas.
A primeira contém a lista de jornadas que foram removidas e não podem ser inseridas
e a segunda lista contém as jornadas incluı́das que não podem ser removidas. A Busca
Tabu é realizada para cada função objetivo e posteriormente é aplicada com a função
de soma ponderada das duas funções objetivos. Um processo para otimizar a solução é
proposto, onde a Busca Tabu é realizada com varias iterações com objetivo de encontrar
soluções viáveis, utilizando somente de inserção de tarefas, e a metaheurı́stica GRASP é
utilizada para selecionar as melhores jornadas geradas no processo de Busca Tabu. No
algoritmo genético, a criação de novas populações se baseia na escolha aleatória de uma
das funções objetivo para conseguir uma diversificação maior da população. A utilização
10
Revisão Bibliográfica
de um método de cruzamento entre duas populações é proposto, utilizando GRASP para
tentar resolver este cruzamento como um subproblema e encontrar uma população dita
perfeita. Os teste foram comparados com dados utilizados em uma empresa de Portugal
e um método de programação linear proposto por Beasley (1987).
Um Algoritmo Genético Hı́brido para resolver o problema de programação da tripulação foi proposto por Li and Kwan (2003). Em sua abordagem os testes foram realizados tanto com instâncias de problemas de ônibus urbano quanto de linhas de trem,
com dados reais de empresas inglesas. Uma heurı́stica gulosa é utilizada para construir
uma escala, onde as jornadas são selecionados sequencialmente de um conjunto grande
de potenciais jornadas viáveis geradas previamente. As jornadas individuais e a escala
devem ser avaliadas como um único processo. A teoria do conjunto fuzzy é aplicada sobre
tais avaliações. Para jornadas individuais a sua viabilidade é avaliada por critérios identificados a partir do conhecimento prático do problema. O Algoritmo Genético é usado
para gerar uma distribuição de pesos quase ótimos entre os critérios, onde uma avaliação
ponderada de um único valor pode ser computada para cada jornada. A programação
construı́da a partir da distribuição dos pesos gerados é avaliada pela função de aptidão
do Algoritmo Genético. Para essa função, são utilizados os objetivos de minimizar jornadas e minimizar o custo total formulados como uma meta fuzzy. Este apresentou um
algoritmo inédito baseado na teoria dos conjuntos fuzzy para resolver o Problema de
Programação da Tripulação. A partir dos resultados apresentados o algoritmo proposto
consegue resolver problemas de tamanho reais.
Uma utilização da metaheurı́stica Busca Tabu para resolver o PPT da realidade brasileira foi apresentada em Marinho et al. (2004). Nesta implementação foram utilizadas
duas estruturada de vizinhança, uma de realocação e outra de troca de tarefas entre
jornadas. Esta mesma estrutura foi adotada no presente trabalho. A Lista Tabu tem
como finalidade evitar que a heurı́stica entre em um ciclo durante a busca do melhor
vizinho. A lista é utilizada para armazenar as últimas soluções avaliadas, de modo a
não permitir que o método volte para uma solução anteriormente avaliada. Três implementação da Busca Tabu foram abordadas no trabalho: a Busca Tabu com o primeiro
vizinho de melhora em uma porcentagem da vizinhança; a Busca Tabu com o melhor
vizinho em uma vizinhança variável e a Busca Tabu com o primeiro vizinho de melhora
em uma porcentagem da vizinhança com diversificação, onde após executar um certo
número de iterações sem encontrar uma solução viável, o procedimento é reiniciado. Os
testes realizados com os três tipos de busca obtiveram resultados relevantes ao serem
comparados com outra heurı́stica abordada na literatura e com dados de um empresa.
Revisão Bibliográfica
11
Em Silva and da Cunha (2010) o PPT é resolvido pela combinação da metaheurı́stica
GRASP (Greedy Randomized Adaptive Search Procedure) com o método de busca em
vizinhança de grande porte, o VLNS (Very Large-Scale Neighborhood Search). Esta
abordagem permite que sejam resolvidos problemas reais em empresas de grande porte,
em um tempo considerável e com bom resultados, devido a possibilidade de explorar vizinhanças com um número muito grande de soluções adjacentes. Os resultados apresentados referem-se à resolução de problemas reais de uma empresa de Belo Horizonte-MG.
Para todos os testes realizados, a abordagem utilizada consegue melhorias significativas
na programação da tripulação em relação à solução adotada pela empresa.
Gonçalves (2010) propõe um estudo comparativo entre as metaheurı́sticas Busca
Tabu e Iterated Local Search (ILS) e uma metodologia exata de programação matemática. Para a utilização das metaheurı́sticas foi necessário a geração de uma solução
inicial, onde esta foi gerada de forma sequencial. A cada iteração, uma tarefa é escolhida
sequencialmente e alocada à jornada existente, desde que a jornada permaneça viável.
Como estrutura de vizinhança foram utilizados os movimentos de troca e realocação de
tarefas, os mesmo utilizados no presente trabalho. Na Buca Tabu, a lista tabu é definida
como uma fila circular, onde os vizinhos mais antigos são eliminados à medida em que
os novos são adicionados e a fila está cheia. A metaheurı́stica ILS é combinada com a
metaheurı́stica Variable Neighborhood Descent (VND), onde o VND é utilizado como
método de busca local do ILS. Na utilização do ILS um processo de pertubação é apresentado, onde sucessivos movimentos aleatórios baseados na estrutura de vizinhança são
empregados. Como critério de aceitação, uma nova solução é aceita se ela for melhor
do que a melhor solução encontrada. Para as metaheurı́sticas a função de avaliação
proposta leva em consideração soluções viáveis e inviáveis. As soluções inviáveis são
penalizadas de forma a privilegiar a eliminação destas da solução final. A metodologia
exata proposta utiliza a abordagem de geração de colunas onde as colunas são geradas a
partir de Enumeração Exaustiva. No modelo exato só são aceitas soluções que atendam
todas as restrições, ou seja soluções viáveis. Os resultados apresentados mostram que os
métodos propostos obtêm soluções muito próximas e provou-se otimalidade em 93, 75%
dos casos de teste considerados.
No trabalho de Reis and Silva (2011) é apresentada a utilização da metaheurı́stica
VNS (Variable Neighborhood Search) combinada com dois métodos de busca distintos, o método clássico VND (Variable Neighborhood Descent) e o método de busca
em vizinhança de grande porte VLNS (Very Large-scale Neighborhood Search). A metaheurı́stica VNS é iniciada com uma solução factı́vel (solução corrente) e um conjunto
12
Revisão Bibliográfica
de estruturas de vizinhança é definido sequencialmente. Com a primeira estrutura de
vizinhança, é gerado um vizinho da solução corrente. Em seguida é realizada uma busca
local a partir deste vizinho. Se ao final da busca local for encontrado um valor melhor do
que o da solução corrente então a solução é atualizada e o procedimento se repete considerando a estrutura de vizinhança inicial. Caso o valor da solução encontrada na busca
local seja pior do que o valor atual, um novo vizinho é gerado considerando a próxima
estrutura de vizinhança, e o procedimento de busca local é novamente realizado. O procedimento se repete até que a condição de parada seja atingida. Como procedimento de
busca local foram utilizados o VND e o VLNS. Ambas as implementações foram testadas
considerando que as tripulações podem realizar no máximo uma troca e duas trocas de
veı́culos durante a jornada. Os custos para jornadas do tipo dupla pegada também foram
variados na realização dos testes, assumindo os valores de 500 e 6000. Os mesmos pesos
também foram utilizados no presente trabalho. Ambos os métodos utilizados obtiveram
melhores resultados quando comparados com os custos adotados pela empresa da cidade
de Belo Horizonte-MG que forneceu os dados. Estes resultados serão utilizados como
base de comparação para os métodos propostos neste trabalho.
2.3
Métodos Hı́bridos para resolver o PPT
Uma abordagem hı́brida é apresentada em Yunes et al. (2005) para resolver tanto o
problema de programação da tripulação como o problema de rodı́zio das tripulações. Os
autores utilizam as seguintes técnicas para resolver os problemas: programação inteira,
programação por restrição e geração de colunas, utilizando a abordagem de caminho
mı́nimo com restrição em um grafo acı́clico dirigido. Este subproblema é resolvido com
um algoritmo de programação dinâmica. Devido ao tamanho das instâncias abordadas,
a utilização destas técnicas, de forma única, se torna inviável. Logo, a combinação entre elas é considerada para resolver instâncias de grande porte. Para resolver o PPT,
inicialmente foi utilizada a técnica de relaxação linear para encontrar bons limites inferiores. Esses limites são utilizados na geração de colunas com o objetivo de gerar novas
jornadas viáveis com custo reduzido negativo. Ao encontrar um novo conjunto de jornadas o problema de escalonamento é resolvido por programação linear. Este processo
é repetido até que uma condição de parada seja alcançada ou o processo de geração
de colunas não encontre nenhuma jornada com custo reduzido negativo. Neste último
caso, a otimalidade da solução está provada. Os resultados apresentados mostram que
foi possı́vel encontrar a otimalidade em um tempo razoável com instâncias de até 100
Revisão Bibliográfica
13
viagens.
Mauri and Lorena (2007) apresentam um método hı́brido utilizando algoritmo de
treinamento populacional e programação linear para gerar os horários dos motoristas
em um sistema de transporte público. O método utiliza o modelo clássico de particionamento, onde os custos que compõem a função objetivo levam em consideração o total de
condutores, de horas extras e de horas ociosas. No algoritmo de treinamento foi utilizada
uma busca local, de modo a avaliar vários tamanhos de vizinhança, gerando assim um
grande número de jornadas de modo a cobrir todas as tarefas. Em seguida é utilizado
um modelo de programação linear para reduzir os custos das jornadas de modo que
todas as tarefas sejam realizadas. De acordo com os autores os resultados apresentados
são considerados bons e em tempo de execução razoável se comparado com Simulated
Annealing apresentados em Mauri and Souza (2003).
No trabalho de Gonçalves et al. (2008) é proposta uma metodologia para resolver o
PPT utilizando a metaheurı́stica Busca Tabu combinada com Programação Matemática.
Nesta implementação uma solução inicial é gerada utilizando um algoritmo guloso, de
modo a criar jornadas que operem sempre com os mesmos veı́culos. Após essa fase,
é definida uma estrutura de vizinhança onde o conjunto de vizinhos são jornadas que
possam ter suas tarefas realocadas ou trocadas entre elas. Após a geração da vizinhança,
com tamanho predeterminado, a Busca Tabu é executada para melhorar a solução atual.
Se esta melhora não acontecer em um número predeterminado de iterações um procedimento remove algumas tarefas alocadas de modo a gerar um subproblema que é resolvido
de forma exata. As tarefas são removidas das jornadas que possuem os maiores tempos
de trabalho. Os resultados apresentados mostram que o método hı́brido consegue reduzir
os custos das horas extras consideravelmente quando comparando com outros métodos
que utilizam somente a abordagem heurı́stica.
Capı́tulo 3
Problema de Programação da
Tripulação de Ônibus Urbano
Neste trabalho é abordado o Problema de Programação das Tripulações de Ônibus Urbano (PPT), também conhecido na literatura como Crew Scheduling Problem. O PPT
tem como dados de entrada a solução do Problema de Programação dos Veı́culos, que corresponde ao sequenciamento das viagens a serem realizadas por cada ônibus em operação,
de uma empresa, num determinado dia da semana. Cada viagem a ser realizada apresenta um horário de inı́cio e de fim, além do seu ponto inicial e ponto final. O conjunto
de todas as viagens realizadas por um veı́culo constitui seu bloco de viagens. Desta forma
é possı́vel prever o horário de partida do veı́culo da garagem e o seu retorno ao final
do dia, assim como o detalhamento de todas as viagens e eventuais pausas realizadas
pelo veı́culo ao longo da operação. As viagens de cada veı́culo são agrupadas em tarefas.
Uma tarefa é a sequência de viagens consecutivas que deve ser executada por um único
condutor, uma vez que entre estas viagens não existe tempo suficiente para que ocorra
a troca da tripulação. Cada jornada corresponde a um conjunto de tarefas que serão
realizadas por uma tripulação ao longo de um dia. As jornadas são formadas a partir da
atribuição das tarefas, a composição destas jornadas devem respeitar o pontos de trocas, a utilização dos veı́culos, o tempo máximo de trabalho,entre outros. Desta forma,
podemos identificar uma jornada como uma tripulação e vice-versa, pois cada tripulante
receberá uma jornada a ser realizada durante um dia útil de trabalho. As jornadas
também devem respeitar as restrições impostas pela empresa, pelas leis trabalhistas e
convenções coletivas.
No problema abordado, são considerados dois tipos de jornadas. A dupla pegada
14
Problema de Programação da Tripulação de Ônibus Urbano
15
é uma jornada caracterizada por um conjunto de tarefas que têm um intervalo, entre
duas tarefas, maior ou igual a um valor estipulado, no caso de duas horas. Este tipo de
jornada é utilizado para a condução dos veı́culos que só operam durante os horários de
pico, o que ocorre principalmente no inı́cio da manhã e no final da tarde. O intervalo
entre os dois pedaços de jornada não é contabilizado como hora trabalhada. Em uma
jornada do tipo pegada simples os intervalos entre as tarefas são menores do que o valor
estipulado para a dupla pegada. Independentemente do tipo de jornada, as horas extras
correspondem ao tempo trabalhado além do tempo normal, que no caso é de seis horas e
quarenta minutos. Por outro lado, se uma jornada durar menos do que o tempo normal
de trabalho, então a diferença entre o tempo normal de trabalho e a duração da jornada
é o tempo ocioso ou a ociosidade da jornada.
A resolução do PPT tem como objetivo atribuir as tarefas às tripulações de modo
que cada tarefa seja realizada por uma única tripulação, as restrições do problema sejam
atendidas e que o custo total composto pelo número de tripulações e a quantidade de
horas extras seja minimizado.
Além das restrições mencionadas, as jornadas devem obedecer as restrições impostas
pelas empresas, as leis trabalhistas e os acordos contidos nas convenções coletivas de
trabalho. Entre essas regras podem se citadas: a carga horária máxima de trabalho
de cada tripulante, o tempo mı́nimo de descanso de cada tripulação, o tempo mı́nimo
para a realização da troca da tripulação, a possibilidade de troca de veı́culos durante a
jornada, entre outras.
Nas subseções seguintes são apresentadas as restrições consideradas neste trabalho
e uma abordagem matemática clássica de particionamento de conjuntos normalmente
utilizada para resolver o problema.
3.1
Restrições do Problema
Para a construção das jornadas de trabalho foram levadas em consideração as seguintes
restrições operacionais e trabalhistas:
• Sobreposição: Dada duas tarefas, i e j realizadas consecutivamente por uma
mesma tripulação, então o horário de inı́cio do tarefa j deve ser posterior ao final
da tarefa i ;
16
Problema de Programação da Tripulação de Ônibus Urbano
• Hora Extra: A duração de uma jornada deve conter no máximo 2 horas a mais da
duração de trabalho regular, sendo este tempo de excesso contabilizado como hora
extra;
• Intervalo de Descanso: Cada tripulação tem direito a no mı́nimo 30 minutos particionado ou não de folga (descanso, almoço, etc.). Esse tempo não é aplicado
quando a jornada for do tipo dupla pegada;
• Troca de Terminal: Dada duas tarefas, i e j realizadas consecutivamente por uma
tripulação, então o ponto final da tarefa i deve ser igual ao ponto inicial da tarefa
j. Para as jornadas do tipo dupla pegada esta troca é permitida se o intervalo de
tempo entre o término da tarefa i e o inı́cio da tarefa j for superior a 2 horas;
• Intervalo de Descanso Diário: Considerando que uma jornada pode ser executada
pela mesma tripulação em dias consecutivos, então o intervalo entre o fim da
jornada e o seu inı́cio no dia seguinte deve ser superior a 11 horas.
• Troca de Veı́culo: Em uma jornada de trabalho, dependendo das regras empresariais, pode ter como restrição um número limitado de troca de veı́culos;
• Minimização de Hora Extra: O tempo excedente da hora de trabalho normal será
contabilizado em horas extras e o mesmo deve ser minimizado;
• Minimização do Número de Duplas Pegadas: Deve ser minimizado o número de
jornadas do tipo dupla pegada o tanto quanto possı́vel;
• Número de Jornadas: A quantidade de jornadas de trabalho deve ser mı́nimo,
cobrindo todas as tarefas as diárias;
• Tempo Ocioso: Deve ser minimizado, tanto quanto possı́vel, o tempo total ocioso
das tripulações;
Capı́tulo 4
Métodos Propostos
Neste capı́tulo são apresentados os métodos utilizados para a resolução do PPT. A
resolução do PPT consiste em encontrar um conjunto de jornadas de tal forma que
todas as tarefas sejam realizadas com o menor custo possı́vel e que sejam atendidas
todas as restrições consideradas para o problema (3.1). Inicialmente é apresentado o
Modelo de Programação Inteira proposto neste trabalho, o qual modela o problema
por meio de uma série de restrições lineares. Posteriormente é apresentado como a
metaheurı́stica LAHC foi implementada para resolver o problema, e finalmente segue
a descrição da implementação da Matheurı́stica que combina a LAHC com o modelo
exato. Para tanto, a seguir são descritas as estruturas utilizadas para representar os
principais elementos que compõem uma solução do PPT.
4.1
Estruturas para a Representação do Problema
Tarefa
Identificador
Horário de Inı́cio
Horário de Fim
Terminal de Inı́cio
Terminal de Fim
Número do Veı́culo
Tabela 4.1: Estrutura de uma tarefa
A Tabela 4.1 apresenta os dados de cada tarefa a ser alocada. O campo Identificador
17
18
Métodos Propostos
recebe um inteiro que identifica unicamente cada tarefa. Os campos Horário de Inı́cio
e Horário de Fim correspondem ao instante estimado em que a tarefa se inicia e se
encerra, respectivamente. No campo Terminal de Inı́cio é atribuı́do um número inteiro
para identificar o terminal onde a tarefa se inicia, e no campo Terminal de Fim um
número inteiro para identificar o terminal onde a tarefa se encerra. O campo Veı́culo
recebe um número inteiro que identifica qual veı́culo realiza a tarefa. Estes campos são
as caracterı́sticas relevantes de uma tarefa para a resolução do PPT.
Jornada
Identificador
Horário de Inı́cio
Horário de Fim
Horas Extras
Horas Ociosas
Dupla Pegada
Troca de Veı́culos
Lista das Tarefas
Tabela 4.2: Estrutura de uma jornada
Na Tabela 4.2 é apresentada a estrutura de uma jornada, sendo que para cada jornada
é atribuı́do um número inteiro único ao campo Identificador. Os campos Horário de
Inı́cio e Horário de Fim recebem o instante estimado em que a jornada se inicia e
instante que ele termina, respectivamente. No campo Horas Ociosas é atribuı́da a soma
do tempo de Ociosidade Interna e Ociosidade Externa. Onde a ociosidade interna é
a soma das ociosidade entre duas tarefas consecutivas. A ociosidade externa contém a
ociosidade que ocorre quando uma jornada tem duração inferior ao tempo normal de
trabalho. Portanto, a ociosidade externa é igual ao tempo normal de trabalho menos a
duração da jornada. No campo Hora Extra é atribuı́do o valor do tempo de trabalho
superior ao tempo normal de trabalho, ou seja, a duração da jornada menos o tempo
normal de trabalho, quando houver. No campo Dupla Pegada é indicado se a jornada é
do tipo dupla pegada ou não. A Troca de Veı́culos corresponde ao número de vezes que
a tripulação deve trocar de veı́culo durante a jornada. O conjunto das tarefas a serem
realizadas na jornada é armazenado na Lista de Tarefas.
Métodos Propostos
4.2
19
Modelo Matemático Proposto
Nesta seção é apresentado o modelo matemático proposto para a resolução do Problema
de Programação da Tripulação. Este modelo, ainda inédito na literatura, difere dos
demais pelo fato de que as jornadas são geradas a partir das tarefas a serem alocadas.
Nos modelos matemáticos apresentados na literatura, a solução do problema é alcançada
selecionando as melhores jornadas dentro de um conjunto de jornadas previamente geradas, sendo que as jornadas selecionadas devem cobrir todas as tarefas. No método
proposto neste trabalho, as jornadas são geradas durante a resolução do modelo, a partir do conjunto de tarefas a ser designado e o conjunto de restrições que devem ser
atendidas. Desta forma não é necessário gerar jornadas previamente.
Para modelar o problema de forma exata foi utilizada a linguagem Mathematical
Programming Language (Fourer et al. 1990) no ambiente de desenvolvimento Gusek. O
modelo final foi resolvido pelo Cplex 12.5. A modelagem é apresentada nas subseções
4.2.1 a 4.2.4, onde são descritos os parâmetros e conjuntos utilizados, as variáveis de
decisão, as restrições e as duas funções objetivo consideradas.
4.2.1
Parâmetros e Conjuntos
Seja qt o parâmetro de entrada que corresponde à quantidade de tarefas do problema,
logo tem-se o conjunto de tarefas T , onde |T | = qt. O parâmetro qj se refere ao
número máximo de jornadas na solução, que gera o conjunto de possı́veis jornadas J,
com |J| ≤ qj. O número máximo de tarefas alocadas a uma jornada é dado pelo valor
M ax T ar. Uma constante suficientemente grande M (Big M ) é utilizada na modelagem
de algumas restrições. Os parâmetros T emp M ax J e T emp M ax HE correspondem
respectivamente à duração máxima de uma jornada de trabalho e ao tempo máximo
de horas extras que uma jornada pode conter. Os parâmetros Custo J, Custo HE,
Custo OC e Custo DP representam o custo fixo de uma jornada e os custos variávies
devido às horas extras, ao tempo ocioso e ao fato da jornada ser do tipo dupla pegada,
respectivamente. Quant M ax DP e Quant M ax T V são parâmetros que correspondem
à quantidade máxima de duplas pegadas contidas na solução e de trocas de veı́culos realizadas em cada jornada. O parâmetro Inter M in DP é o tempo de intervalo mı́nimo
entre duas tarefas que caracterizam uma jornada do tipo dupla pegada, e Inter M in T
corresponde ao tempo mı́nimo de descanso/alimentação da tripulação durante a realização da jornada. Este tempo só é necessário para jornadas do tipo pegada simples.
20
Métodos Propostos
Vale ressaltar que os parâmetros acima são valores inteiros e positivos.
Para cada tarefa t ∈ T , temos stt o horário de inı́cio da tarefa, ett o horário de
término, slt o terminal de saı́da, elt o terminal de chegada e vct o veı́culo que realiza
a tarefa. Dadas duas tarefas t1 e t2 ∈ T , P os T Vt1 t2 identifica se entre as duas tarefas
existe a possibilidade da tripulação realizar a troca entre os respectivos veı́culos, ou seja,
P os T Vt1 t2 = 1 se vct1 6= vct2 , elt1 = slt2 e stt2 − ett1 > 0, caso contrário P os T Vt1 t2 = 0.
E P os DPt1 t2 identifica se entre as duas tarefas existe um intervalo que possibilita a
ocorrência de uma jornada do tipo dupla pegada. Desta forma P os DPt1 t2 = 1 se
stt2 − ett1 > Inter M in DP , caso contrário P os DPt1 t2 = 0.
4.2.2
Variáveis de Decisão
Para modelar o PPT, além das variáveis de alocação das tarefas às jornadas, são necessárias algumas variáveis auxiliares para que sejam geradas soluções viáveis para o
problema. As soluções viáveis devem satisfazer ao conjunto das restrições implementas
que serão apresentadas nas próximas subseções. Tais restrições matemáticas são utilizadas para modelar as regras impostas para que uma jornada de trabalho seja viável.
Seja j ∈ J ,onde |J| é aproximadamente 30% do total de tarefas , t ∈ T e p ∈ P ,
|P | = 8 , onde J, T e P são os conjuntos de jornadas, tarefas e posições (corresponde
a ordem que cada tarefa esta alocada, onde para cada jornada, uma tarefa será alocada
a uma posição, sempre em ordem crescente) das tarefas nas jornadas respectivamente,
então a variável binária xjtp assume valor 1 se a tarefa t for alocada à jornada j na
posição p. Vale ressaltar que esta é a variável que apresentará a solução do problema.
A variável yj é utilizada para identificar se a jornada j tem alguma tarefa alocada a ela,
recebendo o valor 1, caso contrário seu valor será 0. A variável inij receberá o valor do
horário de inı́cio da jornada j, f imj receberá o valor do horário de término da jornada j e
OC intj terá o valor do tempo total de ociosidade interna, ou seja, a soma dos intervalos
ociosos entre as tarefas atribuı́das à jornada j. A variável auxiliar OC extj receberá o
tempo de ociosidade externa quando houver, que é dado pelo intervalo que falta para
concluir a carga horária normal de uma jornada de trabalho, e Qnt HEj receberá a
quantidade de horas extras da jornada, quando houver.
Considerando j ∈ J, t1 , t2 ∈ T e p1 , p2 ∈ P , então a variável T roca Vjt1 t2 p1 p2 tem
como objetivo verificar se existe uma troca de veı́culo entre as tarefas t1 e t2 localizadas
nas posições p1 e p2 da jornada j. As variáveis DPjt1 t2 p1 p2 e Duplaj são utilizadas,
Métodos Propostos
21
respectivamente, para verificar as posições e marcar se uma jornada é do tipo dupla
pegada ou não. A variável Desc DPj contém a amplitude do intervalo não remunerado
para as jornadas do tipo dupla pegada. Esse valor é descontado da remuneração da
jornada.
4.2.3
Função Objetivo
Duas funções objetivo são propostas neste trabalho, sendo que a primeira, dada pela
expressão (4.1), minimiza o número de duplas pegadas e não utilizando a restrição (4.15)
para limitar o número máximo de jornadas do tipo dupla pegada. A segunda função
objetivo, expressa em (4.2), não minimiza o número de duplas pegadas, porém limita o
número de jornadas deste tipo considerando a restrição (4.15). Ambas são apresentadas
abaixo e foram testadas separadamente.
f o1 =
X
(Custo J ∗ yj + Custo OC ∗ (OC extj + OC intj )
(4.1)
j∈J
+Custo HE ∗ Qnt HEj + Custo DP ∗ Duplaj )
f o2 =
X
(Custo J ∗ yj + Custo OC ∗ (OC extj + OC intj )
(4.2)
j∈J
+Custo HE ∗ Qnt HEj )
Nas expressões (4.1) e (4.2) o Custo J se refere ao custo fixo de cada jornada,
Custo OC é o custo de cada hora ociosa, Custo HE é o custo de cada hora extra e
Custo DP é o custo associado a cada jornada do tipo dupla pegada, quando esta componente fizer parte da função objetivo. Desta forma são minimizados os custos fixos, as
horas extras, as horas ociosas e as duplas pegadas, quando considerada, de uma solução.
4.2.4
Conjunto de Restrições
As restrições foram consideradas e implementadas de acordo com as caracterı́sticas descritas anteriormente para o PPT estudado. Devido ao grande número de restrições, estas
são apresentadas em blocos, respeitando suas similaridades.
22
Métodos Propostos
X
xjtp ≤ 1, ∀j ∈ J, p ∈ P
(4.3)
xjtp = 1, ∀t ∈ T
(4.4)
t∈T
X
j∈J,p∈P
X
xjt1 (p+1) ≤
t1 ∈T
X
xjt2 p , ∀j ∈ J, p ∈ P − {1}
(4.5)
t2 ∈T
yj ≥ xjtp , ∀j ∈ J, t ∈ T, p ∈ P
(4.6)
A restrição (4.3) garante que em cada posição de cada jornada só sera alocada uma
única tarefa; (4.4) garante que cada tarefa seja alocada somente a uma jornada. A
restrição (4.5) garante que as tarefas sejam alocadas às jornadas em posições contı́guas,
salvo a primeira posição. A restrição (4.6) verifica se a jornada esta sendo utilizada ou
não, fazendo com que o valor da variável yj assuma o valor 1 se alguma tarefa for alocada
à jornada j, e 0 caso contrário. As cinco restrições apresentadas estão relacionadas à
alocação das tarefas, garantindo assim que estas sejam designadas de forma coerente,
gerando soluções factı́veis e que cobrem todas as tarefas informadas.
inij =
X
stt xjt1 , ∀j ∈ J
(4.7)
t∈T
f imj ≥ ett − M (1 − xjtp ), ∀j ∈ J, t ∈ T, p ∈ P
P os DPt1 t2 + xjt1 p
(4.8)
(4.9)
+xjt2 (p+1) − DPj t1 t2 p(p+1) ≤ 2, ∀j ∈ J, t1 , t2 ∈ T, p ∈ P − 1
DPj t1 t2 p(p+1) ≤ xjt1 p , ∀j ∈ J, t1 , t2 ∈ T, p ∈ P − 1, t2 > t1
(4.10)
DPj t1 t2 p(p+1) ≤ xjt2 (p+1) , ∀j ∈ J, t1 , t2 ∈ T, p ∈ P − 1, t2 > t1
(4.11)
Métodos Propostos
23
DPj t1 t2 p(p+1) = 0, ∀j ∈ J, t1 , t2 ∈ T, p ∈ P − 1, P os DPt1 t2 = 0 (4.12)
X
DPj t1 t2 p(p+1) ≤ 1, ∀j ∈ J
(4.13)
t1 ,t2 ∈T,p∈P −1
Duplaj =
X
DPj t1 t2 p(p+1) , ∀j ∈ J
(4.14)
t1 ,t2 ∈T,p∈P −1
X
Duplaj ≤ Qnt M ax DP
(4.15)
j∈J
Desc DPj =
X
DPj t1 t2 p(p+1) ∗ (stt2 − ett1 ), ∀j ∈ J (4.16)
t1 ,t2 ∈T,p∈P −1
f imj − inij − Desc DPj ≤ T emp M ax J + T emp M ax HE, ∀j ∈ J
f imj − inij ≤ 780, ∀j ∈ J
(4.17)
(4.18)
As restrições (4.7) e (4.8) são responsáveis por atribuir os valores de inij , inı́cio da
jornada e f imj , fim da jornada, para cada jornada j. Estas informações são utilizados
nas outras restrições para garantir a consistência temporal das soluções. As restrições
apresentadas de (4.9) a (4.16) são utilizadas para identificar e calcular o intervalo das
jornadas do tipo dupla pegada, sendo que em (4.9) é verificado se duas tarefas são
executadas em ordem consecutiva, e se entre elas ocorre uma dupla pegada. Em caso
afirmativo, a variável DPj t1 t2 p(p+1) recebe o valor 1, indicando assim que naquela jornada
haverá dupla pegada entre as tarefas t1 e t2 , que se localizam entre as posições p e p + 1.
As restrições (4.10) e (4.11) garantem que a variável DP receba valor um se as duas
tarefas t1 e t2 foram alocadas àquela jornada . O conjunto de restrições em (4.12)
garante que se duas tarefas t1 e t2 não forem candidatas a dupla pegada então a variável
DPj t1 t2 p(p+1) nunca receberá valor 1 para estas tarefas. As restrições em (4.13) garantem
que cada jornada pode ter no máximo um intervalo de tempo do tipo dupla pegada. As
restrições em (4.14) verificam se existe dupla pegada em uma jornada, atribuindo o
valor 1 à variável Duplaj e 0 caso contrário. Em (4.15) é limitado o número total de
duplas pegadas pelo parâmetro Qnt M ax DP , e em (4.16) é atribuı́do, como desconto
de tempo, o valor do intervalo da dupla pegada à variável Desc DPj para que possa
ser descontado no cálculo da remuneração da jornada. As restrições em (4.17) garantem
que nenhuma jornada pode ultrapassar o tempo máximo de trabalho acrescido das horas
extras. Em (4.18) é garantido que o tempo entre o final da jornada e seu inı́cio no dia
seguinte seja superior a 11 horas. As tarefas que são terminadas em um dia posterior, é
considerado o tempo posterior o dia na constagem das horas de descanso diário.
24
Métodos Propostos
OC extj ≥ yj ∗ T emp M ax J − (f imj − inij − Desc DPj ), ∀j ∈ J
(4.19)
X
(ett − stt )xjtp , ∀j ∈ J (4.20)
OC intj ≥ (f imj − inij − Desc DPj ) −
t∈T,p∈P
OC intj ≥ (1 − Duplaj ) ∗ Inter M in T, ∀j ∈ J
Qnt HEj ≥ (f imj − inij − Desc DPj ) − T emp M ax J, ∀j ∈ J
(4.21)
(4.22)
As restrições (4.19) e (4.20) calculam a ociosidade externa e interna de uma jornada.
O intervalo de descanso da tripulação durante a realização das tarefas é garantido pela
restrição (4.21). O cálculo da quantidade de horas extras é realizado em (4.22).
xjt1 p + xjt2 (p+1) ≤ 1, ∀j ∈ J, t1 , t2 ∈ T, p ∈ P − {1}
(4.23)
xjt1 p + xjt2 (p+1)
(4.24)
−DPj t1 t2 p(p+1) ≤ 1, ∀j ∈ J, t1 , t2 ∈ T, p ∈ P − {1}, slt2 6= elt1
xjt1 p + xjt2 (p+1)
(4.25)
−T Vj t1 t2 p(p+1) ≤ 1, ∀j ∈ J, t1 , t2 ∈ T, p ∈ P − {1}, P os T Vt1 t2
T Vj t1 t2 p(p+1) ≤ xjt1 p , ∀j ∈ J, t1 , t2 ∈ T, p ∈ P − {1}, t2 > t1
(4.26)
T Vj t1 t2 p(p+1) ≤ xjt2 (p+1) , ∀j ∈ J, t1 , t2 ∈ T, p ∈ P − {1}, t2 > t1 (4.27)
X
T Vj t1 t2 p(p+1) ≤ Qnt M ax T V, ∀j ∈ J
(4.28)
t1 ,t2 ∈T,p∈P −1
A (4.23) é responsável por garantir que nenhuma tarefa possa ser iniciada antes que
a anterior tenha terminado, em uma mesma jornada. Para permitir que haja troca
de terminal somente em jornadas do tipo dupla pegada, foi implementada a restrição
(4.24). As restrições (4.25), (4.26), (4.27) e (4.28) são responsáveis por garantir as regras
de possı́veis trocas de veı́culos.
Este modelo tem como caracterı́stica um grande número de restrições pois é por
meio delas que as soluções são montadas de acordo com as caracterı́sticas desejadas.
Portanto, quanto maior for o problema a ser resolvido, maior será o número de restrições
e variáveis, tornando assim ineficiente computacionalmente para problemas práticos de
grande porte. Para superar esta limitação foi considerada a implementação de uma
metaheurı́stica e sua combinação com o modelo proposto acima.
Métodos Propostos
4.3
25
A Metaheurı́stica LAHC
A metaheurı́stica Late Acceptance Hill Climbing-LAHC, proposta por Burke and Bykov
(2008), trata-se de uma adequação do método Hill Climbing Clássico (Russell and Norvig 2002). Segundo Burke and Bykov (2012), essa metaheurı́stica foi criada tendo em
mente três objetivos: ser um procedimento de busca local que não exige um processo de
resfriamento artificial, como acontece no Simulated Annealing; usar eficientemente a informação coletada durante iterações anteriores da busca, e; aplicar um novo mecanismo
simplificado de aceitação de soluções candidatas.
O objetivo desta metaheurı́stica é comparar o valor da função objetivo (fitness) de
uma solução candidata com o fitness de uma solução armazenada em uma lista de
soluções encontradas em iterações anteriores. Desta forma, a solução não é comparada
necessariamente com a melhor solução conhecida, mas com uma solução que foi armazenada em uma certa posição da lista em uma determinada iteração anterior. Vale ressaltar
que existe a possibilidade de uma solução candidata ser aceita mesmo não sendo a melhor solução encontrada até a sua iteração. Isto pode ocorrer uma vez que a comparação
não é feita com a melhor solução conhecida, e sim com a solução armazenada numa
determinada posição da lista.
Esta metaheurı́stica tem como único parâmetro o tamanho da lista onde serão armazenados os valores de função objetivo de diferentes soluções encontradas. Esta lista,
denotada por f , tem comprimento Lf a. Seja a lista f = {f1 , f2 , ..., fLf a }, onde, inicialmente, todas as suas posições são preenchidas com o custo da solução inicial C(s), ou
seja, fk ← C(s), ∀k ∈ {1, 2,..., Lf a}. A cada iteração i, uma solução candidata s0 é
gerada na vizinhança de s. Uma solução candidata é aceita se o seu fitness for melhor
ou igual ao fitness armazenado na posição v da lista f , onde v = i mod Lf a. Em caso
0
afirmativo, a posição v da lista f é atualizada: fv ← f (s ). Além disso, se essa solução
0
for melhor do que a melhor solução encontrada s∗ , s∗ é atualizada, ou seja, s∗ ← s .
Esse procedimento continua até que a condição de parada seja alcançada.
Como pode ser visto no Algoritmo 4.1, o LAHC é de fácil implementação, porém
algumas fases do algoritmo são de fundamental importância para o bom desempenho do
mesmo. Estas fases são apresentadas nas próximas seções.
26
Métodos Propostos
Algoritmo 4.1: Implementação do LAHC para um problema de minimização
Entrada: Solução inicial s e o parâmetro Lf a.
Saı́da: Melhor solução s∗ encontrada.
1 fk ← C(s) ∀k ∈ {1, 2,..., Lf a};
∗
2 s ← s;
3 i ← 0;
4 enquanto Condição de parada não atendida faça
0
5
Gere um candidato s na vizinhança de s;
6
v ← i mod Lf a;
0
7
se f (s ) ≤ fv então
0
8
s←s;
9
se f (s) < f (s∗ ) então
10
s∗ ← s;
fv ← f (s);
i ← i + 1;
11
12
13
retorna s∗ ;
4.3.1
Função Objetivo
Como função objetivo da metaheurı́stica LAHC, foi utilizada a mesma função objetivo
apresentada em 4.2.3 que minimiza o número de duplas pegadas. Esta é apresentada
abaixo.
f olahc =
X
(Custo J ∗ yj + Custo OC ∗ (OC extj + OC intj )+
(4.29)
j∈J
Custo HE ∗ Qnt HEj + Custo DP ∗ Duplaj )
Na expressão (4.29) o Custo J se refere ao custo fixo de cada jornada, Custo OC é
o custo de cada hora ociosa, Custo HE é o custo de cada hora extra e Custo DP é o
custo associado a cada jornada do tipo dupla pegada. Desta forma são minimizados os
custos fixos, as horas extras, as horas ociosas e as duplas pegadas.
4.3.2
Geração da Solução Inicial
Conforme exposto na seção 4.3, um fase importante da metaheurı́stica LAHC é a geração
da solução inicial. Para se obter uma solução inicial, foi utilizado um método construtivo
Métodos Propostos
27
guloso, onde o critério adotado é a ordem das tarefas, estas ordenadas a partir do tempo
de inicio. Os dados de entrada, ou seja, as tarefas a serem programadas, são armazenadas
na ordem crescente de seus horários de inı́cio, e em caso de empate, pelo horário de fim.
A construção da solução é iniciada com uma jornada vazia, dita jornada corrente. A
primeira tarefa k ainda não alocada é inserida nessa jornada. A partir de então, enquanto
for possı́vel, são inseridas as próximas tarefas ainda não alocadas, que pertencem ao
mesmo veı́culo da tarefa k e que não geram inviabilidade na jornada corrente. Quando
não for possı́vel inserir qualquer tarefa na jornada corrente, uma nova jornada vazia
é inicializada e o processo se repete até que todas as tarefas tenham sido alocadas a
alguma jornada.
4.3.3
Estrutura de Vizinhança Realoca-Troca
Os dois tipos de movimentos que caracterizam a estrutura de vizinhança adotada foram
a realocação ou a troca de uma tarefa entre duas jornadas, sem gerar inviabilidade. Estes
movimentos são realizados para encontrar um vizinho de uma solução corrente. Exemplificando, considere duas jornadas i e j, escolhidas aleatoriamente. Então é sorteada
uma tarefa a ser retirada da jornada i e introduzida na jornada j. Logo, pode ocorrer
uma das seguintes situações:
1. A tarefa retirada de i pode ser introduzida em j sem a necessidade de remover
qualquer tarefa da jornada j. Neste caso é realizado um movimento de realocação,
e a nova solução será avaliada.
2. A introdução da tarefa em j exige a retirada de uma ou mais tarefas desta jornada.
Neste caso, se a(s) tarefa(s) removida(s) de j puder(em) ser inserida(s) na jornada
i, sem haver qualquer sobreposição com as tarefas remanescentes em i, então o
movimento é aceito, caso contrário ele é descartado. Este é um movimento de
troca.
Em ambos os casos, as modificações são aceitas se e somente se as jornadas resultantes
respeitarem todas as restrições do problema. Uma representação gráfica do movimento
é apresentada na figura 4.1.
28
Métodos Propostos
Figura 4.1: Movimentos de realocação e troca de uma tarefa da jornada j para a jornada
k
4.4
Matheurı́stica
A utilização de métodos exatos em conjuntos com as heurı́sticas vem sendo uma crescente
tendência em otimização. Este processo de hibridização de métodos é também conhecido
como Matheurı́stica (Maniezzo et al. 2009). Os modelos apresentados nas seções 4.2 e
4.3 fazem parte da abordagem do tipo Matheurı́stica proposta neste trabalho para a
resolução do PPT.
A Matheurı́stica desenvolvida neste trabalho parte de uma solução viável gerada
pela metaheurı́stica LAHC e particiona os componentes da solução em subconjuntos
menores de tal forma que gera subproblemas de dimensões menores do que o probema
original. Assim, cada partição está associada a um problema menor e apresenta uma
solução inicial, a qual pode ser melhorada utilizando o modelo exato. Devido ao tamanho
reduzido dos subproblemas, é possı́vel encontrar a solução ótima para cada partição.
Neste trabalho, a solução otimizada inicial é produzida a partir da execução da metaheurı́stica LAHC apresentada na seção 4.3. Esta solução é particionada em problemas
com no máximo seis jornadas de trabalho. O procedimento adotado para realizar o par-
Métodos Propostos
29
ticionamento da solução é apresentado com maiores detalhes na próxima seção. Após o
particionamento, cada partição ou subproblema é resolvido pelo modelo exato descrito
na seção 4.2, onde tenta-se melhorar a solução inicial para cada partição ou demonstrar
a sua otimilidade.
Na Figura 4.2 é apresentado um diagrama com os métodos que compõe a abordagem
proposta neste trabalho.
Figura 4.2: Representação da Matheurı́stica implementada para o Problema de Programação da Tripulação
4.4.1
Particionamento da Solução
A seguir é apresentado o procedimento adotado para realizar o particionamento da
solução em subproblemas, de tal forma que seja possı́vel empregar o modelo exato e
obter a solução ótima. Para escolher as jornadas pertencentes a cada partição foram
utilizadas como atributos a quantidade de horas extras, quantidade de horas ociosas e
os veı́culos utilizados nas jornadas envolvidas.
Para cada partição do problema, foram selecionadas no máximo seis jornadas. Uma
primeira partição vazia é criada, e esta partição recebe a jornada com maior número de
horas extras e que ainda não foi incluı́da em nenhuma partição. Em seguida, é verificado
qual é o veı́culo utilizado na primeira tarefa da jornada inserida. Assim, será inserida
na partição a jornada com o maior número de horas ociosas que inicie com o mesmo
30
Métodos Propostos
veı́culo da jornada já inserida na partição. Quando não houver nenhuma jornada que
utilize o mesmo veı́culo, será inserida a jornada com o maior número de horas ociosas
independente do veı́culo utilizado na primeira jornada. Esse processo é realizado até que
cada partição receba no máximo seis jornadas e que todas as jornadas sejam alocadas
em uma única partição. O fato de escolher jornadas que conduzem o mesmo veı́culo se
deve à possibilidade de realocação das tarefas, visto que desta forma as tarefas estarão
associadas aos mesmos terminais.
Algoritmo 4.2: Particionamento da solução
Entrada: Lista de Jornadas Ordenadas por Horas Extras LHe
Entrada: Lista de Jornadas Ordenadas por Horas Ociosas LHo
Saı́da: Conjunto de partições P
1 Pk ← ∀k;
2 i ← 0;
3 n ← 1;
4 enquanto LHe 6= e LHo 6= faça
5
enquanto (n <= 6)&&(n <= Tamanho de LHe + Tamanho de LHo) faça
6
Pi ← LHe1 ;
7
n ← n + 1;
8
remove a jornada LHe1 das Listas LHe e LHo;
9
se V eı́culoLHe1 = V eı́culoLhok ∀k então
10
Pi ← LHok ;
11
n ← n + 1;
12
remove a jornada LHok das Listas LHe e LHo;
13
14
15
16
17
18
senão
Pi ← LHo1 ;
n ← n + 1;
remove a jornada LHo1 das Listas LHe e LHo;
i ← i + 1;
retorna s∗ ;
Capı́tulo 5
Resultados e Discussão
Inicialmente foram realizados testes com o Modelo Exato para medir a dimensão dos
problemas que este pode resolver. Para estes testes, foram geradas instâncias a partir
de dados reais de uma empresa de transporte público que opera na região metropolitana
de Belo Horizonte MG. As caracterı́sticas destes problemas e os resultados obtidos são
apresentados na seção 5.1. Cada problema foi resolvido pelo solver do pacote computacional CPLEX 12.5.
Na segunda fase de experimentos, a metaheurı́stica LAHC e a Matheurı́stica foram
testada em um conjunto de sete instâncias referentes a uma semana de operação de
uma empresa que atua na cidade de Belo Horizonte-MG. A metaheurı́stica LAHC e o
processo de particionamento das jornadas foram implementados na linguagem C/C++.
Após o particionamento das jornadas, cada subproblema foi resolvido pelo solver do
pacote computacional CPLEX 12.5.
Todos os testes foram executados em um microcomputador com processador Intel(R)
Core(TM) i7-2600, com clock de 3.40GHz, 8 GB de memória RAM, sob plataforma
Windows Seven Professional.
Neste Capı́tulo são apresentados os resultados obtido pelo modelo exato, pela metaheurı́stica LAHC e pela Matheurı́stica. Na seção 5.1 são apresentadas os resultados
obtidos pelo método exato. Em 5.2 é mostrado os resultados do LAHC, incluindo a
fase de calibração, os resultados da matheurı́stica e uma comparação com outras metaheurı́sticas abordadas na literatura.
5.1
Resultados Obtidos pelo Modelo Exato
Para testar o modelo foram gerados 4 casos com caracterı́sticas particulares. Os problemas resolvidos têm as seguintes caracterı́sticas:
• Caso 1: modelo completo com todas as restrições e a função objetivo 4.1. Dados
31
32
Resultados e Discussão
de entrada: veı́culos com e sem dupla pegada;
• Caso 2: modelo sem restrições de dupla pegada e a função objetivo 4.2. Dados de
entrada: veı́culos com e sem dupla pegada;
• Caso 3: modelo sem restrições de dupla pegada e de troca de terminal e função
objetivo 4.2. Dados de entrada: veı́culos com e sem dupla pegada e que operam
no mesmo terminal;
• Caso 4: modelo completo com todas as restrições e a função objetivo 4.1. Dados de
entrada: veı́culos somente do tipo dupla pegada e que operam no mesmo terminal.
Nos experimentos com o Modelo Exato, foram utilizados, devido dos resultados encontrados na maioria das literatura, os seguintes valores para seus parâmetros:
• Custo por jornada de trabalho: 10.000
• Custo da dupla pegada: 600
• Custo da hora extra expressa em minutos: 4
• Custo da hora ociosa expressa em minutos: 1
Para cada caso foram gerados 5 problemas. Estes foram resolvidos pelo CPLEX
por um tempo limite de 8 horas. Porém, para os casos nos quais foram encontradas
as soluções ótimas, esse tempo foi inferior. As tabelas abaixo apresentam os problemas e os resultados obtidos. É importante ressaltar que para melhor análise, foram
tomadas linhas de ônibus com o mesmo número de tarefas, porém estas tarefas não são
coincidentes.
As Tabelas 5.1, 5.3, 5.5 e 5.7 contêm as caracterı́sticas dos problemas testes gerados
em cada caso. Na coluna “Número de tarefas” é apresentado o valor total de tarefas a serem alocadas em cada problema. A coluna “Número de veı́culos” apresenta a
quantidade de veı́culos utilizados para cumprir todas as tarefas. Na coluna “Número
de variáveis” é apresentada a quantidade de variáveis geradas pelo modelo exato para
resolver o problema. A coluna “Número de restrições” mostra a quantidade de restrições
geradas pelo modelo para a representação do problema.
Os dados que caracterizam estes problemas gerados para o caso 1 são apresentados
na Tabela 5.1.
Resultados e Discussão
Problema
33
Número
Número
Número
Número
de tarefas
de veı́culos
de variáveis
de restrições
1
24
2
41.320
69.355
2
33
3
124.144
224.074
3
40
4
227.280
422.331
4
45
5
344.616
658.278
5
52
6
765.600
1.462.053
Tabela 5.1: Caracterı́sticas dos problemas gerados para o caso 1
Os valores apresentados para cada problema refere-se à melhor solução obtida pelo
CPLEX até o tempo limite. Nas Tabelas 5.2, 5.4, 5.6 e 5.8, que contém as caracterı́sticas
das soluções, a coluna “Total de jornadas” representa a quantidade de jornadas contidas
na solução. As coluna “Total de horas extras” e “Total de horas ociosas” mostram a
quantidade de horas extras e quantidade de horas ociosas da solução, expressas em horas
e minutos no formato hh:mm. Na coluna “Gap em %” é apresentada uma estimativa
da diferença para solução ótima em porcentagem. Quando o Gap é igual a zero, então
a solução é ótima, caso contrário, a otimalidade não foi provada pelo solver. Esta estimativa é calculada automaticamente pelo CPLEX. Na coluna “Total de duplas pegada”
é apresentada a quantidade de jornadas do tipo dupla pegada nas soluções encontradas.
Esta coluna não figura nas Tabelas 5.4 e 5.6 pois as restrições utilizadas não considera
jornadas do tipo dupla pegada ou ela não faz parte da função objetivo. A coluna “Fo”
apresenta o valor da função objetivo da melhor solução encontrada para cada problema.
A Tabela 5.2 apresenta os resultados dos cinco problemas para o caso 1. No problema
1 foi encontrada a solução ótima em aproximadamente 101 minutos. Porém só com cerca
de 305 minutos ele foi capaz de provar a otimalidade da solução.
Problema
1
2
3
4
5
Total de
jornadas
Total de
horas extras
Total de
horas ociosas
Gap
em %
Total de
dupla pegada
Fo
Tempo de
processamento
5
7
10
13
16
146
151
98
454
257
225
403
451
1046
1989
0
38,84
54,87
52,62
67,78
1
1
2
2
3
51.409
71.607
102.043
134.062
164.817
305
480
480
480
480
Tabela 5.2: Resultados do modelo exato para os problemas para o caso 1
34
Resultados e Discussão
Na Tabela 5.3 são apresentados os dados que caracterizam os problemas referentes
ao caso 2.
Problema
Número
Número
Número
Número
de tarefas
de veı́culos
de variáveis
de restrições
1
24
2
32.580
71.076
2
33
3
71.037
172.914
3
40
4
138.312
353.692
4
45
5
218.115
572.535
5
52
6
348.300
932.236
Tabela 5.3: Caracterı́sticas dos problemas gerados para o caso 2
Os resultado relativos aos cinco problemas de caso 2, apresentados na Tabela 5.4,
mostram que para o problema 1, foram gastos 293 minutos para provar a otimalidade da
solução,porém a solução ótima foi encontrada em aproximadamente 39 minutos. Para
esse caso a coluna quantidade de duplas pegadas foi omitida, pois esta caracterı́stica não
é considerada na função objetivo.
Problema
Total de
Total de
Total de
Gap
Fo
Tempo de
jornadas
horas extras
horas ociosas
em %
1
6
37
377
0
60.525
293
2
7
231
364
30,79
71.288
480
3
10
101
472
50,22
100.876
480
4
12
198
1016
51,12
121.808
480
5
13
290
917
45,79
132.077
480
processamento
Tabela 5.4: Resultados do modelo exato para os problemas do caso 2
Resultados e Discussão
35
Os dados que caracterizam os 5 problemas do caso 3 são apresentados na Tabela 5.5.
Problema
Número
Número
Número
Número
de tarefas
de veı́culos
de variáveis
de restrições
1
24
2
25.380
43.800
2
33
3
71.037
139.650
3
40
4
138.312
288.172
4
45
5
218.115
468.585
5
52
6
348.300
768.184
Tabela 5.5: Caracterı́sticas dos problemas gerados para o caso 3
Na Tabela 5.6 são apresentados os resultados para os cinco problemas de caso 3.
Novamente, para o problema 1, que é o de menor dimensão, foi encontrada a solução
ótima. Isto se deu em aproximadamente 2 minutos. Após 18 minutos foi provada a
otimalidade da solução. Para este caso o número de restrições foi reduzido, o que levou
o CPLEX a encontrar as soluções mais rapidamente.
Problema
Total
Total de
Total de
Gap
Fo
Tempo de
de jornadas
horas extras
horas ociosas
em %
1
4
354
251
0
41.667
18
2
6
369
444
18,28
61.920
480
3
9
155
530
44,96
91.150
480
4
11
251
928
49,62
111.932
480
5
15
199
1547
45,82
152.343
480
processamento
Tabela 5.6: Resultados do modelo exato para os problemas para o caso 3
Os dados que caracterizam os problemas gerados para o caso 4 são apresentados na
Tabela 5.7.
36
Resultados e Discussão
Problema
Número
Número
Número
Número
de tarefas
de veı́culos
de variáveis
de restrições
1
24
3
57.848
104.002
2
33
4
232.770
435.978
3
40
5
363.648
694.200
4
45
6
631.796
1.219.109
5
52
7
842.160
1.640.768
Tabela 5.7: Caracterı́sticas dos problemas gerados para o caso 4
Conforme pode ser observado na Tabela 5.8, que apresenta os resultados para os cinco
problemas do caso 4, não foi possı́vel provar a otimalidade para nenhum dos problemas,
pois existem veı́culos caracterı́sticos de dupla pegada e foram consideradas todas as
restrições. Desta forma, torna-se um caso mais difı́cil de ser resolvido. O custo de dupla
pegada foi incluı́do neste problema. Assim, a solução tentar diminuir ao máximo o total
de jornadas deste tipo. Também se observa que o número de veı́culos para cada problema
é maior.
Problema
1
2
3
4
5
Total
de jornadas
Total de
horas extras
Total de
horas ociosas
Gap
em %
Total de
dupla pegada
Fo
Tempo de
processamento
6
8
10
12
16
23
32
33
70
41
392
513
657
988
1535
26,83
48,83
50,36
52,62
59,39
4
3
6
4
7
62.884
82.441
104.389
123.668
165.899
480
480
480
480
480
Tabela 5.8: Resultados do modelo exato para os problemas para o caso 4
Realizando a análise dos resultados apresentados, percebe-se que o modelo exato
consegue encontrar e provar a ótimalidade somente para os problemas com 24 tarefas,
com exceção no caso 4. Nestas soluções, o total de jornadas varia entre 4 e 6. Além do
número de tarefas, quando essas possuem caracteristica de dupla pegada, é perceptivel
o aumento no tempo de processamento e no gap encontrada. Na Matheurı́stica apresentada em 4.4, a definição do método de particionamento e do número de jornadas contidas
em cada partição da solução foi baseada na conclusão destes testes. Desta forma, cada
partição recebeu no máximo 6 jornadas.
Resultados e Discussão
5.2
37
Resultados Obtidos pelo LAHC e a Matheurı́stica
Os resultados apresentados nessa seção foram divididos em duas categorias: Calibração
da Metaheurı́stica LAHC e Comparação da Matheurı́stica, LAHC e demais metaheurı́sticas. A calibração de uma metaheurı́stica serve para encontrar os melhores valores dos
parâmetros de entrada do algoritmo. A comparação é apresentada para avaliar os resultados gerados pelo LAHC e pela Matheurı́stica em relação a algumas metaheurı́sticas
apresentadas na literatura. Vale ressaltar que o tempo de execução da Matheurı́stica é
limitado a 60 minutos por partição da solução inicial encontrada pelo LAHC.
5.2.1
Calibração da Metaheurı́stica
A metaheurı́stica LAHC conta com apenas um parâmetro a ser calibrado. Entretanto,
esta definição pode não ser simples pela amplitude do intervalo a ser considerado para
este parâmetro. Para a realização dessa fase foram utilizadas 7 instâncias. Para cada
instância foram realizadas 10 execuções com um determinado tamanho da lista Lf a,
tendo como condição de parada o tempo de processamento limitado a 60 minutos. Foram
considerados os seguintes valores para o tamanho da lista: 10, 20, 30, 40, 50, 100, 150,
200, 250, 300, 350, 400, 450 e 500. O custo para cada jornada do tipo dupla pegada foi
fixado em 5.000 para essa etapa, este valor foi determinado empirı́camente. Na Tabela
5.9 são apresentadas as informações de cada instância utilizada para a realização dos
testes da calibragem.
Instancia
Total de tarefas
Total de veı́culos
1 - Segunda
705
61
2 - Terça
674
58
3 - Quarta
814
68
4 - Quinta
872
76
5 - Sexta
787
71
6 - Sábado
644
56
7 - Domingo
345
34
Tabela 5.9: Tabela com as informações de cada instância, contendo a quantidade de tarefas a serem realizadas e quantos veı́culos são utilizados.
620.547,20
Média:
598.932
1.192.748
1.207.988,80
Média:
Menor:
1.566.860
Menor:
1.658.044
1.674.716,80
1.532.864
1.543.342,80
1.312.836
1.329.808,40
1.363.352
1.374.668,40
615.856
624.715,20
1.193.200
1.207.491,20
1.571.112
1.581.490,00 1.579.223,20
Menor:
Média:
1.659.352
1.673.385,20
Média:
Menor:
1.531.316
1.547.521,60
Média:
Menor:
1.307.848
1.330.962,80
Média:
Menor:
1.348.068
1.372.661,20
Menor:
Média:
LFA 20
610.148
625.411,20
1.194.484
1.207.802,00
1.575.488
1.583.796,40
1.664.144
1.677.892,40
1.527.984
1.549.053,20
1.321.140
1.331.471,20
1.354.596
1.367.260,00
LFA 30
618.640
626.914,80
1.189.000
1.208.764,40
1.582.796
1.589.783,20
1.664.272
1.678.872,40
1.527.728
1.539.884,80
1.313.488
1.333.684,80
1.367.996
1.374.164,40
LFA 40
608.140
619.630,40
1.185.520
1.207.836,80
1.566.184
1.582.949,20
1.668.412
1.675.436,40
1.538.384
1.549.700,40
1.316.984
1.331.575,20
1.368.040
1.374.804,80
LFA 50
610.568
627.802,00
1.198.840
1.210.340,00
1.576.628
1.588.925,20
1.664.136
1.681.080,80
1.522.508
1.543.948,80
1.317.616
1.331.466,00
1.354.396
1.373.267,20
LFA 100
LFA 150
606.920
624.246,00
1.197.400
1.212.529,60
1.568.576
1.587.460,40
1.663.208
1.678.390,80
1.528.200
1.546.897,60
1.299.280
1.326.621,60
1.367.392
1.376.253,20
Tabela 5.10: Resultados do primeiro teste de calibração da Metaheurı́stica LAHC para os valores de tamanho de lista:
10, 20, 30, 40, 50, 100 e 150
Instância 7
Instância 6
Instância 5
Instância 4
Instância 3
Instância 2
Instância 1
LFA 10
38
Resultados e Discussão
624.256,40
Média:
612.664
1.184.476
Menor:
1.571.484
1.584.374,80
1.660.896
1.676.116,80
1.533.400
1.543.274,00
1.321.468
1.332.518,40
1.350.404
1.368.108,00
606.908
624.612,00
1.193.084
1.203.968,40 1.207.675,20
Menor:
Média:
1.575.884
1.586.724,40
Média:
Menor:
1.650.620
1.677.325,20
Média:
Menor:
1.538.456
1.549.056,80
Média:
Menor:
1.317.992
1.333.122,80
Média:
Menor:
1.360.972
1.376.335,20
Menor:
Média:
LFA 250
603.216
623.655,60
1.195.844
1.212.913,20
1.566.896
1.585.825,20
1.659.656
1.678.506,40
1.523.152
1.543.625,60
1.326.272
1.334.909,60
1.364.032
1.378.724,80
LFA 300
602.360
624.960,80
1.198.352
1.209.876,40
1.576.128
1.585.695,60
1.663.976
1.680.278,40
1.528.732
1.546.080,40
1.321.076
1.336.621,20
1.368.112
1.377.102,00
LFA 350
617.908
626.255,60
1.194.208
1.207.131,60
1.570.756
1.585.237,20
1.664.572
1.675.226,40
1.538.352
1.551.978,80
1.317.044
1.329.849,60
1.354.328
1.369.679,60
LFA 400
613.220
629.812,40
1.188.964
1.208.432,00
1.575.296
1.587.726,80
1.673.156
1.681.326,40
1.532.436
1.543.576,00
1.319.448
1.334.827,60
1.362.484
1.373.172,00
LFA 450
611.516
625.364,80
1.199.276
1.211.213,20
1.572.108
1.583.106,00
1.658.980
1.674.926,40
1.528.172
1.545.206,80
1.317.112
1.334.266,80
1.362.144
1.373.014,40
LFA 500
Tabela 5.11: Resultados do primeiro teste de calibração da Metaheurı́stica LAHC para os valores de tamanho de lista:
200, 250, 300, 350, 400, 450 e 500
Instância 7
Instância 6
Instância 5
Instância 4
Instância 3
Instância 2
Instância 1
LFA 200
Resultados e Discussão
39
40
Resultados e Discussão
Os resultados da primeira calibração são apresentados nas Tabelas 5.10 e 5.11, onde
verificou-se que as melhores soluções foram obtidas para os seguintes tamanhos da lista:
40, 50, 100 e 300. Assim, foi necessário realizar novos testes de calibração, levando
em conta somente os quatro tamanhos de lista com as melhores soluções. Cada uma
das 7 instâncias foram utilizadas, porém foram realizadas apenas três execuções para
cada valor atribuı́do ao tamanho da lista Lf a. Os resultados para a segunda etapa de
testes de calibração são apresentados na Tabela 5.12, onde os testes com tamanho de
lista 50 obtiveram os melhores resultado em 3 instâncias. Para as outras instâncias,
foram obtidos resultados muito próximos às melhores soluções encontradas. Logo, como
resultado de calibração, foi considerado o tamanho de lista ideal igual a 50. Assim, para
os experimentos restantes foi adotado o parâmetro Lf a = 50.
Instância 1
Instância 2
Instância 3
Instância 4
Instância 5
Instância 6
Instância 7
Lfa 40
Lfa 50
Lfa 100
Lfa 300
Média:
1.344.330,67
1.336.676,00
1.352.716,00
1.346.317,33
Menor:
1.336.704
1.331.732
1.332.692
1.337.192
Média:
1.290.684,00
1.299.412,00
1.300.594,67
1.303.334,67
Menor:
1.277.220
1.288.016
1.295.488
1.295.492
Média:
1.513.765,33
1.508.077,33
1.525.436,00
1.520.089,33
Menor:
1.504.524
1.488.040
1.507.424
1.509.720
Média:
1.649.356,00
1.640.852,00
1.662.602,67
1.651.034,67
Menor:
1.639.844
1.620.672
1.660.384
1.642.584
Média:
1.568.070,67
1.561.241,33 1.553.341,33
1.560.121,33
Menor:
1.562.696
Média:
1.192.054,67
Menor:
1.182.216
1.181.472
1.180.640
1.180.540
Média:
611.296,00
615.502,67
618.793,33
618.522,67
Menor:
606.068,00
607.196,00
612.184,00
615.512,00
1.551.600
1.545.056
1.186.600,00 1.183.202,67
1.543.392
1.184.726,67
Tabela 5.12: Resultados do segundo teste de calibração da Metaheurı́stica
LAHC para os valores de tamanho de lista: 40, 50, 100 e 300
5.2.2
Comparação entre a Matheurı́stica, LAHC e demais Metaheurı́sticas
Nos experimentos, foram adotados os seguintes valores para os respectivos parâmetros:
Resultados e Discussão
41
• Custo por jornada de trabalho: 10.000
• Custo da dupla pegada: 5.000 e 600
• Custo da hora extra expressa em minutos: 4
• Máximo de trocas de veı́culos por jornada: 1
Para cada instância, foram realizadas 10 execuções da metaheurı́stica tendo como
condição de parada o tempo em execução limitado a 60 minutos. Em relação à Matheurı́stica, cada subproblema foi executado em um tempo máximo de 60 minutos no CPLEX,
em busca da solução ótima.
As instâncias de testes foram as mesmas instâncias utilizadas na fase de calibração da
metaheurı́stica LAHC. As caracterı́sticas destas instâncias estão apresentadas na Tabela
5.9. As Tabelas apresentadas a seguir mostram uma comparação dos resultados obtidos
pela LAHC, pela matheurı́stica e aqueles produzidos pelas metaheurı́sticas VNS clássico,
VNS combinado com VLNS e ILS clássico e ILS combinado com VLNS, do trabalho de
Silva and Reis (2014). Também são apresentadas as soluções adotadas pela empresa
para os problemas.
Os resultados apresentados nesta seção estão divididos em dois grupos, considerando
os diferentes valores para o custo das jornadas do tipo dupla pegada. Dado que as empresas geralmente operam com no máximo 20% de jornadas com dupla pegada é importante
avaliar o impacto resultante da variação no custo destas jornadas e a consequencia no
número de jornadas deste tipo nas soluções finais.
Na primeira etapa dos testes, foram comparados os resultados gerados pela Matheurı́stica e as metaheurı́sticas LAHC, VNS Clássico (VNS), VNS combinado com VLNS
(VNS-VLNS), ILS Clássico (ILS), ILS combinado com VLNS (ILS-VLNS), considerando
o custo da dupla pegada igual a 600. Na segunda etapa foram avaliados os resultados da
Matheurı́stica e das metaheurı́sticas LAHC, VNS, VNS-VLNS considerando um custo
de 5.000 para as jornadas do tipo dupla pegada.
5.2.2.1
Resultados com Custo 600 para as Jornadas do Tipo Dupla Pegada
A Tabela 5.13 contêm as caracterı́sticas das melhores soluções obtidos pela Matheurı́stica,
LAHC, VNS, VNS-VLNS, ILS e ILS-VLNS para a primeira instância, que se refere à
operação de uma segunda-feira na empresa. A coluna “Fo” apresenta o valor da função
objetivo da melhor solução encontrada por cada método. A coluna “Total de jornadas” apresenta a quantidade de jornadas contidas na solução de cada método. A coluna
“Total de horas extras” mostra a quantidade de horas extras das soluções, expressa em
horas e minutos no formato hh:mm. Na coluna “Total de duplas pegadas” é apresentada
a quantidade de jornadas do tipo dupla pegada nas soluções. Esta mesma estrutura é
utilizada para apresentar os resultados das outras instâncias contidos nas Tabelas 5.15,
5.17, 5.19, 5.21, 5.23 e 5.25.
42
Resultados e Discussão
Métodos
Fo
Total de
Total de
Total de
jornadas
horas extras
duplas pegadas
Matheurı́stica
1.163.884
108
112:01
95
LAHC
1.163.904
108
109:36
96
VNS Clássico
1.218.316
120
54:46
23
VNS-VLNS
1.217.024
119
67:36
18
ILS Clássico
1.234.612
121
52:33
20
ILS - VLNS
1.216.256
119
64:24
18
Tabela 5.13: Caracterı́sticas dos melhores resultados para a instância 01 com
custo 600 para jornadas do tipo dupla pegada
A Tabela 5.14 apresenta uma comparação entre o melhor resultado obtido pela
Matheurı́stica e os melhores resultados encontrados pelas metaheurı́stica LAHC, VNS,
VNS-VLNS, ILS e ILS-VNLS para a instância 01. As porcentagens desta tabela foram obtidas utilizando a seguinte expressão: Pij = (V alorij − V alorM ath )/V alorij ,
∀i ∈ I, j ∈ J, onde I é o conjunto de atributos da solução (Fo, Total de jornadas,
Total de horas extras e Total de duplas pegadas) e J é o conjunto das metaheurı́sticas
(LAHC, VNS, VNS-VLNS, ILS e ILS-VNLS). Para cada i ∈ I e j ∈ J, se Pij > 0
então a Matheurı́stica obteve uma redução sobre o V alorij obtido pela metaheurı́stica
j, ou seja, há uma vantagem da Matheurı́stica sobre a metaheurı́stica j. Se Pij < 0 a
Matheurı́stica obteve um acréscimo sobre o valor de V alorij da metaheurı́stica j, ou seja,
ocorre uma desvantagem da Matheurı́stica em relação à metaheurı́stica j. E se Pij = 0 a
Matheurı́stica obteve o mesmo V alorji da metaheurı́stica j, então não houve modificação
para o atributo i. A mesma estrutura é utilizada para comparar os resultados obtidos
pela Matheurı́stica para as outras instâncias. Estas comparações são apresentadas nas
Tabelas 5.16, 5.18, 5.20, 5.22, 5.24 e 5.26.
Resultados e Discussão
Métodos
43
Total de
Total de
Total de
jornadas
horas extras
duplas pegadas
0,0017%
0,00%
-2,20%
1,04%
VNS Clássico
4,47%
10,00%
-104,53%
-313,04%
VNS-VLNS
4,37%
9,24%
-65,71%
-427,78%
ILS Clássico
5,73%
10,74%
-113,16%
-375,00%
ILS -VLNS
4,31%
9,24%
-73,94%
-427,78%
LAHC
Fo
Tabela 5.14: Melhorias da Matheurı́stica em relação aos métodos LAHC, VNS,
VNS-VLNS, ILS e ILS - VLNS para a instância 01 com custo 600 para jornadas
do tipo dupla
Analisando as Tabelas 5.13 e 5.14 é possı́vel concluir que a combinação do modelo
exato com o LAHC (Matheuristica), produziu, para a instância 1, soluções com menores
custo de F o, conseguindo reduzir o número de jornadas em torno de 10%, exceto quando
comparado com a metaheurı́stica LAHC. Por outro lado, percebe-se um aumento significativo no total de horas extras e no total de duplas pegadas. Comparando o número de
duplas pegadas da Matheurı́stica com a metaheurı́stica VNS-VLSNS, este valor chega a
aumentar em cerca de 427%, tornando a solução indesejável para a empresa, uma vez que
é adotado em média 20% de jornadas do tipo duplas pegadas na prática. Comparando a
Matheurı́stica com o LAHC, o ganho é mı́nimo, considerando o tempo de processamento
de 1080 minutos (18 partições com limite de 60 minutos) levado para obter a redução
de somente 0, 0017%.
Métodos
Fo
Total de
Total de
Total de
jornadas
horas extras
duplas pegadas
Matheurı́stica
1.110.504
104
111:16
74
LAHC
1.112.008
104
110:02
76
VNS Clássico
1.167.748
116
60:24
15
VNS-VLNS
1.183.108
116
63:47
13
ILS Clássico
1.187.020
116
62:35
20
ILS - VLNS
1.177.048
115
65:12
19
Tabela 5.15: Caracterı́sticas dos melhores resultados para a instância 02 com
custo 600 para jornadas do tipo dupla pegada
44
Resultados e Discussão
Métodos
Fo
Total de
Total de
Total de
jornadas
horas extras
duplas pegadas
LAHC
0,14%
0,00%
-1,12%
2,63%
VNS Clássico
4,90%
10,34%
-84,22%
-393,33%
VNS-VLNS
6,14%
10,34%
-74,44%
-469,23%
ILS Clássico
6,45%
10,34%
-77,79%
-270,00%
ILS-VLNS
5,65%
9,57%
-70,65%
-289,47%
Tabela 5.16: Melhorias da Matheurı́stica em relação aos métodos LAHC, VNS,
VNS-VLNS, ILS e ILS-VLNS para a instância 02 com custo 600 para jornadas
do tipo dupla pegada
Para a segunda instância é possı́vel perceber, a partir das Tabelas 5.15 e 5.16, que a
combinação do modelo exato com o LAHC , produz soluções com menores valores para
a F o e o número de jornadas. O número total de horas extras e total de duplas pegadas
aumenta bruscamente, chegando a cerca de 469% de acréscimo quando comparado com
a solução obtida pela metaheurı́stica VNS-VLNS. Porém o ganho da Matheurı́stica em
relação às metaheurı́sticas, variando entre 0, 14% e 6, 45% para a função objetivo e entre
0, 0% e 10, 34% para o total de jornadas. Comparando a Matheurı́stica e o LAHC, houve
uma redução de 0, 14% na F o e de 76 para 74 no número de duplas pegadas. Entretanto,
esta quantidade de duplas pegadas ainda ultrapassa o número aceitável para a empresa.
Métodos
Fo
Total de
Total de
Total de
jornadas
horas extras
duplas pegadas
Matheurı́stica
1.331.296
124
130:22
100
LAHC
1.331.872
124
127:48
102
VNS Clássico
1.396.164
137
63:57
22
VNS-VLNS
1.409.336
138
64:44
23
ILS Clássico
1.408.672
138
61:58
23
ILS-VLNS
1.406.892
138
62:03
20
Tabela 5.17: Caracterı́sticas dos melhores resultados para a instância 03 com
custo 600 para jornadas do tipo dupla pegada
Resultados e Discussão
Métodos
45
Fo
Total de
Total de
Total de
jornadas
horas extras
duplas pegadas
LAHC
0,04%
0,00%
-2,01%
1,96%
VNS Clássico
4,65%
9,49%
-103,86%
-354,55%
VNS-VLNS
5,54%
10,14%
-101,39%
-334,78%
ILS Clássico
5,49%
10,14%
-110,38%
-334,78%
ILS-VLNS
5,37%
10,14%
-110,10%
-400,00%
Tabela 5.18: Melhorias da Matheurı́stica em relação aos métodos LAHC, VNS,
VNS-VLNS, ILS e ILS-VLNS para a instância 03 com custo 600 para jornadas
do tipo dupla pegada
Os resultados para a instância 03 são apresentados nas Tabelas 5.17 e 5.18. Como
nas instâncias anteriores, o modelo exato combinado com a metaheurı́stica LACH reduz
os custo de F o e o número de jornadas, e conta com um aumento no total de horas
extras e de duplas pegadas. O total de duplas pegadas passou de 20 para 100, quando
comparado com a metaheurı́stica ILS-VLNS, caracterizando assim um aumento de cerca
de 400%. A Matheurı́stica comparada com LAHC apresenta, para a terceira instância,
uma redução de 0, 04% na função objetivo e cerca de 2% no número de duplas pegadas.
Métodos
Fo
Total de
Total de
Total de
jornadas
horas extras
duplas pegadas
Matheurı́stica
1.429.740
133
148:05
107
LAHC
1.429.868
133
148:37
107
VNS Clássico
1.515.728
150
61:09
34
VNS-VLNS
1.522.524
149
73:01
25
ILS Clássico
1.538.640
151
59:20
24
ILS-VLNS
1.534.792
151
60:48
17
Tabela 5.19: Caracterı́sticas dos melhores resultados para a instância 04 com
custo 600 para jornadas do tipo dupla pegada
46
Resultados e Discussão
Métodos
Fo
Total de
Total de
Total de
jornadas
horas extras
duplas pegadas
LAHC
0,01%
0,00%
0,36%
0,00%
VNS Clássico
5,67%
11,33%
-142,16%
-214,71%
VNS-VLNS
6,09%
10,74%
-102,81%
-328,00%
ILS Clássico
7,08%
11,92%
-149,58%
-345,83%
ILS-VLNS
6,84%
11,92%
-143,56%
-529,41%
Tabela 5.20: Melhorias da Matheurı́stica em relação aos métodos LAHC, VNS,
VNS-VLNS, ILS e ILS-VLNS para a instância 04 com custo 600 para jornadas
do tipo dupla pegada
Nas Tabelas 5.19 e 5.20 são apresentados os resultados obtidos para o quarto dia
operacional. Os custos de F o são reduzidos pela Matheurı́stica em até 7, 08% e o número
de jornadas é reduzido, chegando em até 11, 92% quando comparado com ILS e o ILSVNLS. Porém o número de duplas pegadas, quando comparado com Matheurı́stica, tem
um acréscimo de até 529, 41%, com um total de 107 jornadas do tipo dupla pegada
de um total de 133 jornadas, o que corresponde a cerca 80% do total de jornadas. A
Matheurı́stica consegue reduzir o custo da função objetivo da metaheurı́stica LAHC em
0, 01%, custo este relacionado à redução no número de horas extras.
Métodos
Fo
Total de
Total de
Total de
jornadas
horas extras
duplas pegadas
Matheurı́stica
1.368.232
127
144:18
106
LAHC
1.368.232
127
144:18
106
VNS Clássico
1.426.732
140
74:55
30
VNS-VLNS
1.446.964
142
69:05
17
ILS Clássico
1.447.112
142
67:58
18
ILS-VLNS
1.437.300
141
73:45
16
Tabela 5.21: Caracterı́sticas dos melhores resultados para a instância 05 com
custo 600 para jornadas do tipo dupla pegada
Resultados e Discussão
Métodos
47
Fo
Total de
Total de
Total de
jornadas
horas extras
duplas pegadas
LAHC
0,00%
0,00%
0,00%
0,00%
VNS Clássico
4,10%
9,29%
-92,61%
-253,33%
VNS-VLNS
5,44%
10,56%
-108,88%
-523,53%
ILS Clássico
5,45%
10,56%
-112,31%
-488,89%
ILS-VLNS
4,81%
9,93%
-95,66%
-562,50%
Tabela 5.22: Melhorias da Matheurı́stica em relação aos métodos LAHC, VNS,
VNS-VLNS, ILS e ILS-VLNS para a instância 05 com custo 600 para jornadas
do tipo dupla pegada
A instância 05 tem seus resultados apresentados na Tabela 5.21 e 5.22. A Matheurı́stica se mostra ineficiente ao tentar melhorar a solução obtida pelo LAHC para esta
instância. Porém a metaheurı́stica LAHC obtém melhores resultados de F o e número
total de jornadas quando comparada às outras metaheurı́sticas, conseguindo reduções do
custo total que variam entre 4, 10% e 5, 45%. O número de duplas pegadas na solução
encontrada pela metaheurı́stica LAHC é muito alto, sendo que das 127 jornadas totais,
106 são jornadas do tipo dupla pegada. Se for comparada com a solução que gera o
menor número de jornadas deste tipo, tem-se um aumento de 562, 5%.
Métodos
Fo
Total de
Total de
Total de
jornadas
horas extras
duplas pegadas
Matheurı́stica
996.912
92
127:58
73
LAHC
997.460
92
127:45
78
VNS Clássico
1.063.544
106
60:22
17
VNS-VLNS
1.101.428
108
51:47
15
ILS Clássico
1.084.620
106
62:35
16
ILS-VLNS
1.099.440
108
58:30
9
Tabela 5.23: Caracterı́sticas dos melhores resultados para a instância 06 com
custo 600 para jornadas do tipo dupla pegada
48
Resultados e Discussão
Métodos
Fo
Total de
Total de
Total de
jornadas
horas extras
duplas pegadas
LAHC
0,05%
0,00%
-0,17%
6,41%
VNS Clássico
6,27%
13,21%
-111,98%
-329,41%
VNS-VLNS
9,49%
14,81%
-147,12%
-386,67%
ILS Clássico
8,09%
13,21%
-104,47%
-356,25%
Tabela 5.24: Melhorias da Matheurı́stica em relação aos métodos LAHC, VNS,
VNS-VLNS, ILS e ILS-VLNS para a instância 06 com custo 600 para jornadas
do tipo dupla pegada
Para a sexta instância, referente a um dia de sábado, caracterizado por um número
reduzido de tarefas, os resultados obtidos são apresentados nas Tabelas 5.23 e 5.24. A
Matheurı́stica consegue melhorar a solução encontrada pela metaheurı́stica LAHC para
esta instância, com uma redução de 0, 05% no custo total e uma redução de 6, 41% no
número de duplas pegadas. Apesar da Matheurı́stica reduzir o número de jornadas do
tipo dupla pegada em relação ao LAHC, este número ainda é indesejável para utilização
das empresas, pois das 92 jornadas na solução, 73 são deste tipo. Quando comparada
a Matheurı́stica com o VNS -VLSN, o aumento no número do total de duplas pegadas
chega a 386, 67%.
Métodos
Fo
Total de
Total de
Total de
jornadas
horas extras
duplas pegadas
Matheurı́stica
528.308
49
64:37
38
LAHC
528.308
49
64:37
38
VNS Clássico
563.512
55
33:24
10
VNS-VLNS
563.472
55
36:08
8
ILS Clássico
580.548
57
23:57
8
ILS-VLNS
579.728
57
23:02
7
Tabela 5.25: Caracterı́sticas dos melhores resultados para a instância 07 com
custo 600 para jornadas do tipo dupla pegada
Resultados e Discussão
Métodos
49
Fo
Total de
Total de
Total de
jornadas
horas extras
duplas pegadas
LAHC
0,00%
0,00%
0,00%
0,00%
VNS Clássico
6,25%
10,91%
-93,46%
-280,00%
VNS-VLNS
6,24%
10,91%
-78,83%
-375,00%
ILS Clássico
9,00%
14,04%
-169,80%
-375,00%
ILS-VLNS
8,87%
14,04%
-180,54%
-442,86%
Tabela 5.26: Melhorias da Matheurı́stica em relação aos métodos LAHC, VNS,
VNS-VLNS, ILS e ILS-VLNS para a instância 07 com custo 600 para jornadas
do tipo dupla pegada
Os resultados para última instância, correspondente a um dia de domingo, são apresentados nas Tabelas 5.25 e 5.26. Como para a instância 05, a Matheurı́stica se mostrou
ineficiente ao tentar melhorar a solução encontrada pela metaheurı́stica LAHC. Comparando as heurı́sticas apresentadas, é possı́vel perceber que o LAHC consegue obter uma
solução com melhor custo final. Porém, como nas outras, o aumento de jornadas do tipo
dupla pegada chega a 443, 86%, quando comparado com a solução que gerou o menor
número de duplas pegadas. Sendo que a metaheurı́stica LAHC obteve em sua melhor
solução 49 jornadas, com 38 do tipo dupla pegada.
Métodos
Matheurı́stica
LAHC
VNS Clássico
VNS-VLNS
ILS Clássico
ILS-VLNS
Segunda
Terça
Quarta
Quinta
Sexta
Sábado
Domingo
1.163.884
1.163.904
1.218.316
1.217.024
1.234.612
1.216.256
1.110.504
1.112.008
1.167.748
1.183.108
1.187.020
1.177.048
1.331.296
1.331.872
1.396.164
1.409.336
1.408.672
1.406.892
1.429.740
1.429.868
1.515.728
1.522.524
1.538.640
1.543.792
1.368.232
1.368.232
1.426.732
1.446.964
1.447.112
1.437.300
996.912
997.460
1.093.544
1.101.428
1.084.620
1.099.440
528.308
528.308
563.512
563.472
580.548
570.728
Tabela 5.27: Valores da função objetivo para os melhores resultados obtidos
para todas as instâncias e com peso 600 para as jornadas do tipo dupla pegada
Na Tabela 5.27 são apresentados os valores da função objetivo da melhor solução
encontrada para cada um dos métodos e cada instância. Os valores apresentam o custo
final da F o da melhor solução obtida pelas metaheurı́sticas. Os resultados destacados
em negrito correspondem aos melhores resultados para cada instância. A partir desta
tabela pode-se concluir que a Matheurı́stica obteve os melhores resultados em 5 das 7
instâncias testadas. Somente em 2 instâncias a Matheurı́stica não conseguiu melhorar a
solução encontrada pela metaheurı́stica LAHC, finalizando sua execução com o mesmo
resultado obtido no LAHC.
50
Resultados e Discussão
5.2.2.2
Resultados com Custo 5.000 para as jornadas do tipo Dupla Pegada
Para realizar os testes apresentados nessa seção, foi utilizado o mesmo conjunto de
instâncias dos testes apresentados na seção 5.2.2.1. A diferença está no custo adotado na
função objetivo para as jornadas do tipo dupla pegada, que neste caso foi de 5.000. Para
esse conjunto de teste, devido o custo da dupla pegada ser maior, espera-se que o número
de jornadas deste tipo seja reduzido consideravelmente, atendendo às caracterı́sticas
desejadas na prática.
A Tabela 5.28 contêm as caracterı́sticas das melhores soluções obtidas pela Matheurı́stica, LAHC, VNS e VNS-VLNS para a primeira instância. A coluna “Fo” mostra o
valor da função objetivo, da melhor solução encontrada por cada método. A coluna
“Total de jornadas” apresenta a quantidade de jornadas contidas na solução de cada
método. A coluna “Total de horas extras” mostra a quantidade de horas extras da
solução, expressa em horas e minutos no formato hh:mm. Na coluna “Total de duplas
pegadas” é apresentada a quantidade de jornadas deste tipo nas soluções encontradas.
Esta mesma estrutura é utilizada para apresentar os resultados das outras instâncias
contidos nas Tabelas 5.30, 5.32, 5.34, 5.36, 5.38 e 5.40.
Métodos
Fo
Total de
Total de
Total de
jornadas
horas extras
duplas pegadas
Matheurı́stica
1.332.316
118
92:59
26
LAHC
1.332.408
118
93:22
26
VNS Clássico
1.368.520
120
98:00
29
VNS-VLNS
1.270.628
120
65:07
11
Tabela 5.28: Caracterı́sticas dos melhores resultados para a instância 01 com
custo 5.000 para jornadas do tipo dupla pegada
Uma comparação entre o melhor resultado obtido pela Matheurı́stica e os melhores resultados encontrados pelas metaheurı́sticas LAHC, VNS e VNS-VLNS, para a instância
01, são apresentados na Tabela 5.29. As porcentagens desta tabela foram obtidas utilizando a seguinte expressão: Pij = (V alorij − V alorM ath )/V alorij , ∀i ∈ I, j ∈ J. Onde
I é o conjunto de atributos da solução (Fo, Total de jornadas, Total de horas extras e
Total de duplas pegadas) e J é o conjunto das metaheurı́sticas avaliadas (LAHC, VNS
e VNS-VLNS). Para cada i ∈ I e j ∈ J, se Pij > 0 então a Matheurı́stica obteve
uma redução sobre o V alorij da metaheurı́stica j, ou seja, há uma vantagem sobre a
metaheurı́stica j. Se Pij < 0, então a Matheurı́stica apresenta o valor da F o maior do
que o V alorij da metaheurı́stica j, ou seja, ocorre uma desvantagem da Matheurı́stica
em relação à metaheurı́stica j. E se Pij = 0 a Matheurı́stica obteve o mesmo V alorji
da metaheurı́stica j, então não houve modificação para o atributo i. Esta estrutura é
Resultados e Discussão
51
utilizada para mostrar as melhorias obtidas das outras intâncias, estas apresentadas nas
Tabelas 5.31, 5.33, 5.35, 5.37, 5.39 e 5.41.
Métodos
Fo
Total de
Total de
Total de
jornadas
horas extras
duplas pegadas
LAHC
0,01%
0,00%
0,41%
0,00%
VNS Clássico
2,65%
1,67%
5,12%
10,34%
VNS-VLNS
-4,85%
1,67%
-42,79%
-136,36%
Tabela 5.29: Melhorias da Matheurı́stica em relação aos métodos LAHC, VNS
e VNS-VLNS para a instância 01 com custo 5.000 para jornadas do tipo dupla
pegada
Analisando os dados apresentados nas Tabelas 5.28 e 5.29 pode-se concluir que a
Matheurı́stica produziu uma solução mais aceitável em relação à quantidade de duplas
pegadas, gerando em média 22% do total de jornadas da solução encontrada. Porém, em
sua melhor solução, há um acréscimo de 4, 85% no custo final, quando comparado com
a melhor solução encontrada pela metaheurı́stica VNS-VLNS. A Matheurı́stica reduz o
custo total, o número de jornadas e o número de duplas pegadas quando comparado
com o VNS Clássico, conseguindo uma redução de 2, 65% no valor da função objetivo.
Métodos
Fo
Total de
Total de
Total de
jornadas
horas extras
duplas pegadas
Matheurı́stica
1.267.380
114
93:15
21
LAHC
1.267.380
114
93:15
21
VNS Clássico
1.318.200
114
96:40
31
VNS-VLNS
1.213.176
114
75:44
11
Tabela 5.30: Caracterı́sticas dos melhores resultados para a instância 02 com
custo 5.000 para jornadas do tipo dupla pegada
Os resultados para a instância 02 são apresentados nas Tabelas 5.30 e 5.31. A
Matheurı́stica não consegue reduzir o custo final encontrado pela metaheurı́stica LAHC.
A metaheurı́stica LAHC encontrou uma solução melhor do que a solução encontrada
pelo VNS clássico, reduzindo tanto o número de duplas pegadas quanto a quantidade de
horas extras. Esta redução foi de 3, 53% para a total de horas extras e 32, 26% para a
quantidade de duplas pegadas. Por outro lado, o VNS-VLNS apresenta a melhor solução
52
Resultados e Discussão
Métodos
Fo
Total
Total de
Total de
de jornadas
horas extras
duplas pegadas
LAHC
0,00%
0,00%
0,00%
0,00%
VNS Clássico
3,86%
0,00%
3,53%
32,26%
VNS-VLNS
-4,47%
0,00%
-23,13%
-90,91%
Tabela 5.31: Melhorias da Matheurı́stica em relação aos métodos LAHC, VNS
e VNS-VLNS para a instância 02 com custo 5.000 para jornadas do tipo dupla
pegada
entre os métodos, tendo uma diferença de função objetivo de 4, 47% comparando com
a solução do LAHC. A solução encontrada pela metaheurı́stica LAHC possui 21 duplas
pegada das 114 jornadas, se enquadrando nas métricas aceitas pelas empresas para este
tipo de jornada.
Resultados e Discussão
Métodos
53
Fo
Total de
Total de
Total de
jornadas
horas extras
duplas pegadas
Matheurı́stica
1.497.240
133
113:30
28
LAHC
1.497.536
133
114:44
28
VNS Clássico
1.527.904
135
116:16
30
VNS VLNS
1.471.176
140
67:24
11
Tabela 5.32: Caracterı́sticas dos melhores resultados para a instância 03 com
custo 5.000 para jornadas do tipo dupla pegada
Métodos
Fo
Total
Total de
Total de
de jornadas
horas extras
duplas pegadas
LAHC
0,02%
0,00%
1,07%
0,00%
VNS Clássico
2,01%
1,48%
2,38%
6,67%
VNS-VLNS
-1,77%
5,00%
-68,40%
-154,55%
Tabela 5.33: Melhorias da Matheurı́stica em relação aos métodos LAHC, VNS
e VNS-VLNS para a instância 03 com custo 5.000 para jornadas do tipo dupla
As Tabelas 5.32 e 5.33 apresentam os resultados obtidos para a terceira instância,
uma quarta-feira. Os custos de F o são reduzidos pela Matheurı́stica quando comparados
com as metaheurı́sticas LAHC e VNS clássico, sendo que esta redução chega a 2, 01%.
O número de jornadas com duplas pegadas na solução obtida pela Matheurı́stica é de
28, de um total de 133 jornadas, representando 21, 05% da solução. Pode-se perceber
também que a metaheurı́stica VNS-VLNS apresenta os melhores resultados tendo um
custo final de 1.471.176, enquanto a Matheurı́stica obteve um custo de 1.497.240.
54
Resultados e Discussão
Métodos
Fo
Total de
Total de
Total de
jornadas
horas extras
duplas pegadas
Matheurı́stica
1.612.644
146
115:11
25
LAHC
1.612.912
146
116:18
25
VNS Clássico
1.684.272
152
121:58
27
VNS-VLNS
1.583.644
148
77:41
17
Tabela 5.34: Caracterı́sticas dos melhores resultados para a instância 04 com
custo 5.000 para jornadas do tipo dupla pegada
Métodos
Fo
Total de
Total de
Total de
jornadas
horas extras
duplas pegadas
LAHC
0,02%
0,00%
0,96%
0,00%
VNS Clássico
4,25%
3,95%
5,56%
7,41%
VNS-VLNS
-1,83%
1,35%
-48,27%
-47,06%
Tabela 5.35: Melhorias da Matheurı́stica em relação aos métodos LAHC, VNS
e VNS-VLNS para a instância 04 com custo 5.000 para jornadas do tipo dupla
pegada
Os resultados para a quarta instância são apresentados nas Tabelas 5.34 e 5.35. A
solução com o menor custo final foi encontrada pela metaheurı́stica VNS-VLNS. Porém a
Matheurı́stica obteve melhores resultados que as metaheurı́sticas LAHC e VNS clássico,
conseguindo reduzir o custo da F o em 4, 25%. Além disso, a Matheurı́stica apresenta a
solução com menor número de jornadas, esta igual a do LAHC, e com um número de
jornadas do tipo dupla pegada aceitável pelas empresas.
Resultados e Discussão
Métodos
55
Fo
Total de
Total de
Total de
jornadas
horas extras
duplas pegadas
Matheurı́stica
1.535.660
140
106:55
22
LAHC
1.535.876
140
107:49
22
VNS Clássico
1.562.864
142
116:06
23
VNS-VLNS
1.471.100
139
87:55
12
Tabela 5.36: Caracterı́sticas dos melhores resultados para a instância 05 com
custo 5.000 para jornadas do tipo dupla pegada
Métodos
Fo
Total de
Total de
Total de
jornadas
horas extras
duplas pegadas
LAHC
0,01%
0,00%
0,83%
0,00%
VNS Clássico
1,74%
1,41%
7,91%
4,35%
VNS-VLNS
-4,39%
-0,72%
-21,61%
-83,33%
Tabela 5.37: Melhorias da Matheurı́stica em relação aos métodos LAHC, VNS
e VNS-VLNS para a instância 05 com custo 5.000 para jornadas do tipo dupla
pegada
Para a quinto instância, os resultados obtidos com o maior custo de duplas pegadas
são apresentados nas tabelas 5.36 e 5.37. Pode-se concluir que a Matheurı́stica obteve
melhor solução que as metaheurı́sticas LAHC e VNS Clássico. Porém, quando comparado com o VNS-VLNS, a solução obtida apresenta um aumento em todos os atributos
avaliados. Entretanto, Pode-se concluir também que a Matheurı́stica obteve um número
de jornadas do tipo dupla pegada aceitável pelas empresas de transporte publico, sendo
que, das 140 jornadas, somente 22 são do tipo dupla pegada.
56
Resultados e Discussão
Métodos
Fo
Total de
Total de
Total de
jornadas
horas extras
duplas pegadas
Matheurı́stica
1.156.484
99
110:21
28
LAHC
1.156.672
98
111:08
30
VNS Clássico
1.182.808
104
95:02
24
VNS-VLNS
1.152.552
109
52:18
10
Tabela 5.38: Caracterı́sticas dos melhores resultados para a instância 06 com
custo 5.000 para jornadas do tipo dupla pegada
Métodos
Fo
Total de
Total de
Total de
jornadas
horas extras
duplas pegadas
LAHC
0,02%
-1,02%
0,70%
6,67%
VNS Clássico
2,23%
4,81%
-16,12%
-16,67%
VNS-VLNS
-0,34%
9,17%
-110,99%
-180,00%
Tabela 5.39: Melhorias da Matheurı́stica em relação aos métodos LAHC, VNS
e VNS-VLNS para a instância 06 com custo 5.000 para jornadas do tipo dupla
pegada
Nas Tabelas 5.38 e 5.39 são apresentados os resultados das melhores soluções obtidas para a instância 6, correspondente a um dia de sábado. Para este problema, a
Matheurı́stica, apesar de não apresentar a melhor solução, é perceptı́vel que ela reduz
o número de jornadas, exceto quando comparado com o LAHC, que para reduzir o
número de duplas pegadas foi necessário aumentar o número de jornadas. Novamente,
a metaheurı́stica VNS-VLNS apresenta a solução com o menor custo de “Fo”, porém
a diferença entre esta metaheurı́stica e a Matheurı́stica é de aproximadamente 0, 34%.
Também pode-se concluir que, para a instância 6, com o menos número de tarefas, a
Matheurı́tica gerou um número elevado de duplas pegada chegando a cerca de 28% do
total de jornadas.
Resultados e Discussão
Métodos
57
Fo
Total de
Total de
Total de
jornadas
horas extras
duplas pegadas
Matheurı́stica
605.312
54
42:58
11
LAHC
605.312
54
42:58
11
VNS Clássico
596.088
54
46:12
9
VNS-VLNS
601.296
57
27:35
5
Tabela 5.40: Caracterı́sticas dos melhores resultados para a instância 07 com
custo 5.000 para jornadas do tipo dupla pegada
Métodos
Fo
Total de
Total de
Total de
jornadas
horas extras
duplas pegadas
LAHC
0,00%
0,00%
0,00%
0,00%
VNS Clássico
-1,55%
0,00%
7,00%
-22,22%
VNS-VLNS
-0,67%
5,26%
-55,77%
-120,00%
Tabela 5.41: Melhorias da Matheurı́stica em relação aos métodos LAHC, VNS
e VNS-VLNS para a instância 07 com custo 5.000 para jornadas do tipo dupla
pegada
Para a última instância, as melhores soluções encontradas por cada método são apresentadas nas Tabelas 5.40 e 5.41. Mais uma vez, a Matheurı́stica não conseguiu melhorar o resultado obtido pela metaheurı́stica LAHC. Por outro, o LAHC obteve uma
solução com o valor da “Fo” próximo ao resultados obtidos pelas outras metaheurı́sticas,
chegando a um aumento de somente 1, 55% sobre a melhor solução encontrada. Vale
também ressaltar que a metaheurı́stica LAHC obteve a solução o número de jornadas
igual ao VNS Clássico que possui a melhor solução.
Uma visão geral dos custos finais, obtidos por cada método para cada instância, é
apresentada na Tabela 5.42. Através dos dados apresentados, pode-se verificar que a
metaheurı́stica VNS-VLNS obteve a melhor solução para a maior parte das instâncias
testadas, exceto para a última. Porém, a Matheurı́stica apresenta um bom desempenho
chegando a obter melhores resultados que o VNS clássico, se mostrando uma abordagem
bastante competitiva.
58
Resultados e Discussão
Segunda
Métodos
Matheurı́stica
LAHC
VNS Clássico
VNS-VLNS
Terça
Quarta
Quinta
Sexta
Sábado
Domingo
Fo
Fo
Fo
Fo
Fo
Fo
Fo
1.332.316
1.332.408
1.368.520
1.270.628
1.267.380
1.267.380
1.318.200
1.213.176
1.497.240
1.497.536
1.527.904
1.471.176
1.612.644
1.612.912
1.684.272
1.583.644
1.535.660
1.535.876
1.562.864
1.471.100
1.156.484
1.156.672
1.182.808
1.152.552
605.312
605.312
596.088
601.296
Tabela 5.42: Melhores resultados obtidos da função objetivo para todas as
instâncias com peso 5.000 para as jornadas do tipo dupla pegada
Capı́tulo 6
Conclusões e Trabalhos Futuros
A resolução do Problema de Programação da Tripulação (PPT) é de grande importância
para o planejamento operacional de empresas de transporte público por consumir uma
porcentagem significativa dos seus recursos. Algumas empresas do setor de transporte
ainda utilizam meios manuais para gerar as jornadas de trabalho de suas tripulações.
Devido a esse fato existe a necessidade de se desenvolver ferramentas computacionais
que facilitem a geração das escalas diárias (jornadas), como abordada nesse trabalho,
especificamente para tripulação de ônibus urbano.
Neste trabalho foram propostas as seguintes técnicas para resolver o Problema de
Programação da Tripulação: um Modelo de Programação Linear Inteira, uma versão
da metaheurı́stica LAHC e uma Matheurı́stica composta pelo modelo exato e a metaheurı́stica. A utilização desta abordagem é justificada uma vez que o modelo exato só
é capaz de resolver problemas pequenos, e a solução de uma metaheurı́stica pode ser melhorada com a utilização de modelos exatos. Além disso, a utilização de métodos hı́bridos
em diversos problemas tem produzido resultados promissores. A escolha do método exato
abordado vem a ser justificada pela necessidade de se estudar novas técnicas exatas para
resolver este problema. Neste sentido, o modelo apresentado neste trabalho, apesar de
suas limitações, é inédito na literatura. A metaheurı́stica LAHC foi escolhida por ser
uma abordagem nova e que apresentou resultados satisfatórios quando utilizadas em
outros problemas de difı́cil resolução, além do fato de possuir um único parâmetro de
calibração o que facilita sua utilização.
Os testes realizados para a abordagem exata tiveram como objetivo verificar a dimensão dos problemas que este modelo é capaz de resolver. A partir destes testes foi
possı́vel observar que os modelo exato tem um melhor desempenho com problemas que
geram até 6 jornadas, visto que para essa quantidade de jornadas o modelo consegue
geralmente obter e provar a solução ótima. Também foi possı́vel concluir que problemas com mais que 50 jornadas são impossı́veies de serem resolvidos pelo método exato,
devido à necessidade de gerar um número muito elevado de variáveis e restrições pelo
modelo.
59
60
Conclusões e Trabalhos Futuros
Os resultados obtidos pela Matheurı́stica apresentam soluções sempre melhores ou
iguais às soluções encontradas pela metaheurı́stica LAHC. Isto se deve pelo fato da
solução do LAHC ser o dado de entrada para a Matheurı́stica. Também, pode-se concluir que a redução dos custos da Matheurı́stica em relação aos resultados da LAHC é
pequena, chegando a no máximo 0, 14% no melhor caso. O que pode ser explicado pelo
fato das partições utilizadas serem pequenas e restritas. O tamanho das partições foi
escolhido devido ao fato de que o modelo matématico so conseguia resolver problemas
desta dimensão em um tempo inferior as 8 horas. Foi observado que em quatro dos
testes realizados, a Matheurı́stica se mostrou ineficiente na tentativa de reduzir o custo
da solução obtida pelo LAHC.
Para os testes realizados com a Matheurı́stica e a metaheurı́stica LAHC, foram utilizados 2 valores diferentes para o custo das jornadas com dupla pegada, com o objetivo
de reduzir o total de jornadas deste tipo. Isto se deve pelo fato de que a adoção de
jornadas do tipo dupla pegada deve ser limitada na utilização prática. Geralmente, as
empresas atuam com uma quantidade máxima de cerca de 20% de jornadas deste tipo.
Logo, o controle desta caracterı́stica foi realizado, na metaheurı́sica, aumentando o seu
custo e verificando o impacto nas soluções obtidas.
Empregando um custo menor para as jornadas do tipo dupla pegada, no caso igual
a 600, a metaheurı́stica LAHC e a Matheurı́stica apresentaram soluções com menores
custos finais do que todos os resultados apresentados por (Silva and Reis 2014), na
mesmas condições. No melhor dos casos, a Matheurı́stica conseguiu uma redução de
até 9, 49% no custo da função objetivo quando comparado com o VNS-VLNS. Porém, o
número de jornadas do tipo dupla pegada nas soluções obtidas é muito alto, chegando
a contar com 87% deste tipo do total de jornadas, para a primeira instância. Logo, as
soluções obtidas tanto pela metaheurı́stica LAHC como para Matheurı́stica, apresentam
soluções não aceitas na prática. A geração deste número elevado de duplas pegadas se
deve ao baixo custo para jornadas deste tipo e nenhuma restrição foi implementada para
que as soluções não ultrapassassem a margem desejada.
Nos resultados obtidos considerando um custo de 5.000 para cada dupla pegada, as
melhores soluções encontradas pela Matheurı́stica e metaheurı́stica LAHC apresentaram
uma quantidade de duplas pegadas dentro das limitações práticas da solução. Comparando os resultados obtidos nestes testes, observa-se que a Matheurı́stica obteve resultados melhores em 6 das 7 solução obtida pelo VNS clássico, chegando a uma redução de
custo de função objetivo de até 4, 25% no melhor caso. Por outro lado, a Matheurı́stica
não obteve resultados melhores que as soluções encontradas pela metaheurı́stica VNSVLNS. Pode-se concluir também que tanto a Matheurı́stica como o LAHC obtém, na
maioria dos testes realizados, soluções com um menor número de jornadas, ou seja,
necessitando de um número menor de tripulações para a realização das tarefas.
De modo geral, pode-se concluir que a utilização de métodos hı́bridos para resolução
do Problema de Programação da Tripulação é uma abordagem nova, que mostrou resultados satisfatórios quando comparados com os melhores resultados obtidos anteriormente
por métodos heurı́sticos. A utilização da metaheurı́stica LAHC se mostrou eficiente, de
Conclusões e Trabalhos Futuros
61
modo a gerar soluções muito boas. Para o custo menor das duplas pegadas, suas soluções
são as melhores. O modelo exato proposto, apesar de resolver problemas pequenos, foi
uma abordagem inédita, por considerar as restrições das jornadas a partir das tarefas,
que são os dados de entrada. Desta maneira não é necessário gerar as jornadas previamente ou durante o processo de otimização, como ocorre nos modelos de geração de
colunas.
Como possı́veis trabalhos futuros, pode-se apontar a utilização de novas estratégias
de particionamento da solução na Matheurı́stica. Desta forma podem ser utilizados
critérios diferentes para o particionamento, criando maiores possibilidades de otimização
da solução produzida pela metaheurı́stica. Como critérios de particionamento, pode-se
utilizar do número de duplas pegadas, partições por estado temporal, manhã, tarde e
noite ou ainda utilizar mais de uma combinação, ou mais de uma fase de particionamento.
Apêndice A
Apêndices
A.1
Publicações
Neste apêndice são listados os trabalhos publicados em eventos cientı́ficos desenvolvidos
durante o perı́odo de realização da presente pesquisa.
1. SOUZA, D. S. ; SILVA, G. P. . UM MODELO EXATO PARA RESOLVER O PROBLEMA DA ESCALA DE MOTORISTAS DE ÔNIBUS
URBANO. In: XLV Simpósio Brasileiro de Pesquisa Operacional, 2013, Natal,
Brazil.
2. SOUZA, D. S. ; SILVA, G. P. ; SANTOS, H. G. . UMA ABORDAGEM
EXATA PARA RESOLVER O PROBLEMA DA ESCALA DE MOTORISTAS DE ÔNIBUS URBANO. In: XXVII ANPET - Congresso de
Pesquisa e Ensino em Transportes, 2013, Belém, Brazil.
O trabalho a seguir foi submetido e aceito para publicação em eventos cientı́fico.
1. SILVA, G. P. ; SOUZA, D. S. . A MATHEURISTIC APPROACH TO
SOLVE THE CREW SCHEDULING PROBLEM FOR MASS TRANSIT SYSTEMS. In: XVIII Pan-American Conference of Traffic and Transportation Engeneering and Logistics, 2014, Santander, Spain.
62
Referências Bibliográficas
Barnhart, C., Johnson, E. L., Nemhauser, G. L., Savelsbergh, M. W. e Vance, P. H.:
1998, Branch-and-price: Column generation for solving huge integer programs, Operations research 46(3), 316–329.
Beasley, J. E.: 1987, An algorithm for set covering problem, European Journal of Operational Research 31(1), 85–93.
Burke, E. K. e Bykov, Y.: 2008, A Late Acceptance Strategy in Hill-Climbing for Exam
Timetabling Problems, PATAT ’08 Proceedings of the 7th International Conference
on the Practice and Theory of Automated Timetabling, Montreal, Canadá.
Burke, E. K. e Bykov, Y.: 2012, The late acceptance hill-climbing heuristic, Department
of Computing Science and Mathematics, University of Stirling, number CSM-192.
Desrochers, M. e Soumis, F.: 1989, A column generation approach to the urban transit
crew scheduling problem, Transportation Science 23(1), 1–13.
Elias, S.: 1964, The use of digital computers in the economic scheduling for both man
and machine in public transport, Kansas, EUA: Technical Report 49.
Ernst, A. T., Jiang, H., Krishnamoorthy, M., Owens, B. e Sier, D.: 2004b, An annotated
bibliography of personnel scheduling and rostering, Annals of Operations Research
127(1-4), 21–144.
Ernst, A. T., Jiang, H., Krishnamoorthy, M. e Sier, D.: 2004a, Staff scheduling and rostering: A review of applications, methods and models, European journal of operational
research 153(1), 3–27.
Fischetti, M., Martello, S. e Toth, P.: 1987, The fixed job schedule problem with spreadtime constraints, Operations Research 35(6), 849–858.
63
64
REFERÊNCIAS BIBLIOGRÁFICAS
Fores, S., Proll, L. e Wren, A.: 1999, An improved ilp system for driver scheduling, in
N. H. M. Wilson (ed.), Computer-Aided Transit Scheduling, Springer, pp. 43–61.
Fourer, R., Gay, D. M. e Kernighan, B. W.: 1990, A modeling language for mathematical
programming, Management Science 36(5), 519–554.
Fournier, S.: 2009, Branch-and-price algorithm for a real-life bus crew scheduling problem, ERPOSul .
Freling, R., Lentink, R. M. e Wagelmans, A. P.: 2004, A decision support system for
crew planning in passenger transportation using a flexible branch-and-price algorithm,
Annals of Operations Research 127(1-4), 203–222.
Friberg, C. e Haase, K.: 1999, An exact branch and cut algorithm for the vehicle and crew
scheduling problem, in N. H. M. Wilson (ed.), Computer-Aided Transit Scheduling,
Springer, pp. 63–80.
Gonçalves, T. L.: 2010, Meta-heurı́sticas para o problema de programação de tripulações,
Master’s thesis, Programa de Engenharia de Sistemas e Computação, Universidade
Federal do Rio de Janeiro.
Gonçalves, T. L., Fampa, M. H. C., dos Santos, A. G. e Ochi, L. S.: 2008, Metaheurıstica
busca tabu e programaçao matemática uma abordagem hıbrida aplicada ao problema
de programaçao de tripulaçoes, Anais XXXI CNMAC-Congresso Nacional de Matemática Aplicada e Computacional.
Li, J. e Kwan, R. S.: 2003, A fuzzy genetic algorithm for driver scheduling, European
Journal of Operational Research 147(2), 334–344.
Lourenço, H. R., Paixão, J. P. e Portugal, R.: 2001, Multiobjective metaheuristics for
the bus driver scheduling problem, Transportation Science 35(3), 331–343.
Luedtke, L. K.: 1985, Rucus ii: a review of system capabilities, Computer Scheduling of
Public Transport 2, 61–116.
Maniezzo, V., Stützle, T. e Voß, S.: 2009, Hybridizing metaheuristics and mathematical
programming, Annals of information systems pp. 19–21.
Marinho, E. H., Ochi, L. S., Drummond, L. M., Souza, M. J. F. e Silva, G. P.: 2004,
Busca tabu aplicada ao problema de programação de tripulações de ônibus urbano,
Simpósio Brasileiro de Pesquisa Operacional, XXXVI pp. 1471–1482.
REFERÊNCIAS BIBLIOGRÁFICAS
65
Mauri, G. R. e Lorena, L. A. N.: 2007, A new hybrid heuristic for driver scheduling,
International Journal of Hybrid Intelligent Systems 4(1), 39–47.
Mauri, G. e Souza, M.: 2003, Resolução do problema de programação de tripulações de
um sistema de transporte público via simulated annealing, Relatório Técnico 02/2003,
Departamento de Ciência da Computação-Universidade Federal de Ouro Preto .
Novaes, A.: 2001, Logı́stica e gerenciamento da cadeia de distribuição, Vol. 3, Elsevier
Brasil.
Parker, M. e e Smith, B. M.: 1981, Two approaches to computer crew scheduling,
Computer Scheduling of Public Transport. Amsterdam: North-Holland pp. 193–222.
Reis, A. F. d. S. e Silva, G. P.: 2011, Um estudo de diferentes métodos de busca
ea metaheurı́stica vns para otimizar a escala de motoristas de ônibus urbano, XXV
ANPET - Congresso de Pesquisa e Ensino em Transportes 1, 2374–2385.
Russell, S. J. e Norvig, P.: 2002, Artificial Intelligence: A Modern Approach (2nd Edition), Prentice Hall, pp. 111–114.
Santos, A. G. e Mateus, G. R.: 2007, Crew scheduling urban problem: an exact column
generation approach improved by a genetic algorithm, Evolutionary Computation,
2007. CEC 2007. IEEE Congress on, IEEE, pp. 1725–1731.
Shen, Y. e Kwan, R. S.: 2001, Tabu search for driver scheduling, in S. Voß e J. R.
Daduna (eds), Computer-Aided Transit Scheduling, Springer, pp. 121–135.
Silva, G.: 2001, Uma metodologia baseada na técnica de geração de arcos para o problema
de programação de veı́culos, PhD thesis, Tese de doutorado. Escola Politécnica da USP,
São Paulo.
Silva, G. P. e da Cunha, C. B.: 2010, Uso da técnica de busca em vizinhança de grande
porte para a programação da escala de motoristas de ônibus urbano, Transportes
18(2), 37–45.
Silva, G. P. e Reis, A. F. d. S.: 2014, A study of different metaheuristics to solve the
urban transit crew scheduling problem, Journal of Transport Literature 8, 227–251.
Smith, B. M. e Wren, A.: 1988, A bus crew scheduling system using a set covering
formulation, Transportation Research Part A: General 22(2), 97–108.
66
REFERÊNCIAS BIBLIOGRÁFICAS
Souza, M. J. F., Cardoso, L. X. T., Silva, G. P., Rodrigues, M. M. S. e Mapa, S.
M. S.: 2004, Metaheurı́sticas aplicadas ao problema de programação de tripulações
no sistema de transporte público.
Stefanello, F.: 2011, Hibridização de métodos exatos e heurı́sticos para resolução de
problemas de otimização combinatória, Master’s thesis, Programa de Pós-Graduação
em Informática, Universidade Federal de Santa Maria, Santa Catarina.
Wilhelm, E.: 1975, Overview of the rucus package driver run cutting program
(runs), Transportation Science Section, Operations Research Society of America, etc.,
Workshop on Automated Techniques for Scheduling of Vehicle Operators for Urban
Public Transportation Services. Preprints, Chicago.
Wren, A.: 2004, Scheduling vehicles and their drivers-forty yearsâ experience, 9th International Conference on Computer-Aided Scheduling of Public Transport (CASPT),
San Diego, California.
Yunes, T. H., Moura, A. V. e De Souza, C. C.: 2005, Hybrid column generation approaches for urban transit crew management problems, Transportation Science 39(2), 273–
288.