Problemas de roteamento de veículos aplicados no planejamento logístico do transporte escolar da cidade de Coxim - MS

Prévia do material em texto

Fernando Silveira Alves
Problemas de roteamento de veículos aplicados no
planejamento logístico do transporte escolar da
cidade de Coxim - MS
CAMPINAS
2015
i
ii
Universidade Estadual de Campinas
Instituto de Matemática, Estatística
e Computação Científica
Fernando Silveira Alves
Problemas de roteamento de veículos aplicados no
planejamento logístico do transporte escolar da
cidade de Coxim - MS
Dissertação apresentada ao Instituto de Matemá-
tica, Estatística e Computação Científica da Uni-
versidade Estadual de Campinas como parte dos
requisitos exigidos para a obtenção do título de
Mestre em matemática aplicada e computacional.
Orientador: Cristiano Torezzan
Este exemplar corresponde à versão final da
dissertação defendida pelo aluno Fernando Sil-
veira Alves, e orientado pelo Prof. Dr. Cristi-
ano Torezzan.
Assinatura do Orientador
Campinas
2015
iii
Ficha catalográfica
Universidade Estadual de Campinas
Biblioteca do Instituto de Matemática, Estatística e Computação Científica
Ana Regina Machado - CRB 8/5467
 
 Alves, Fernando Silveira, 1987- 
 AL87p AlvProblemas de roteamento de veículos aplicados no planejamento logístico do
transporte escolar da cidade de Coxim - MS / Fernando Silveira Alves. –
Campinas, SP : [s.n.], 2015.
 
 
 AlvOrientador: Cristiano Torezzan.
 AlvDissertação (mestrado profissional) – Universidade Estadual de Campinas,
Instituto de Matemática, Estatística e Computação Científica.
 
 
 Alv1. Logística - Modelos matemáticos. 2. Transporte escolar - Planejamento -
Coxim (MS). I. Torezzan, Cristiano,1976-. II. Universidade Estadual de Campinas.
Instituto de Matemática, Estatística e Computação Científica. III. Título.
 
Informações para Biblioteca Digital
Título em outro idioma: Routing problems of applied vehicles in the logistical planning of
school transport in the city of Coxim - MS
Palavras-chave em inglês:
Logistics - Mathematical models
School children - Transportation - Planning - Coxim (MS)
Área de concentração: Matemática Aplicada e Computacional
Titulação: Mestre em Matemática Aplicada e Computacional
Banca examinadora:
Cristiano Torezzan [Orientador]
Celso Cavellucci
Washington Alves de Oliveira
Data de defesa: 28-05-2015
Programa de Pós-Graduação: Matemática Aplicada e Computacional
Powered by TCPDF (www.tcpdf.org)
iv
Tese de Doutorado defendida em 28 de maio de 2015 e aprovada 
Pela Banca Examinadora composta pelos Profs. Drs. 
Prof(a). Dr(a). WASHINGTON LIVEIRA 
v 
·- - · - --~------~-
vi
Resumo
Nesta dissertação apresentamos um estudo sobre problemas de roteamento de veículos com o
interesse especial de investigar o planejamento logístico do transporte escolar público. Além dos
algoritmos clássicos para roteamento, são apresentadas estratégias de coleta de dados, seleção de
pontos de ônibus, desenho das rotas e definição de frotas para dimensionar transporte escolar em
sincronia com os horários das escolas. Como aplicação dos conceitos estudados, apresenta-se um
estudo de caso sobre o transporte escolar na cidade de Coxim-MS.
Palavras-chave: Problemas de roteamento de veículos, Planejamento logístico, Transporte
escolar.
Abstract
We present in this work a study on vehicle routing problems with special interest in investigate
the logistic planning for public school bus trasportation. Besides some classical models for vehicle
routing we present policies for data collection, bus point selection, design of routes and fleets
management. As an application we present a case study on the school bus transportation in the
city of Coxim-MS.
Keywords: Vehicle routing problems, Logistics planning, School bus.
vii
viii
Sumário
Introdução 1
1 O problema de roteamento de ônibus escolar: uma revisão 5
1.1 Planejamento do sistema . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.1.1 Preparação dos dados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.1.2 Seleção de pontos de ônibus . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.1.3 Planejamento e desenho das rotas de ônibus . . . . . . . . . . . . . . . . . . 7
1.1.4 Sincronização com os horários da escola . . . . . . . . . . . . . . . . . . . . . 8
1.1.5 Refinamento das rotas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.2 Classificação dos problemas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.2.1 Número de escolas: única ou múltiplas . . . . . . . . . . . . . . . . . . . . . 9
1.2.2 Área rural × área urbana . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.2.3 Problemas: manhã × tarde . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.2.4 Carregamento misto . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.2.5 Transporte de estudantes de necessidades especiais . . . . . . . . . . . . . . 12
1.2.6 Ônibus: homogêneo ou heterogêneo . . . . . . . . . . . . . . . . . . . . . . . 13
1.2.7 Objetivos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
1.2.8 Restrições . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
1.3 Classificação baseada nos métodos de solução . . . . . . . . . . . . . . . . . . . . . 14
1.3.1 Configurações de formulações matemáticas para um PROE . . . . . . . . . . 15
1.3.2 Métodos de solução . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
2 Problemas de roteamento de veículos e técnicas de solução 17
2.1 Alguns problemas de roteamento e seus modelos matemáticos . . . . . . . . . . . . 20
2.1.1 O problema de roteamento de veículos capacitado PRVC . . . . . . . . . . . 20
2.1.1.1 Formulação matemática do PRVC . . . . . . . . . . . . . . . . . . 21
2.1.2 Problemas de roteamento de veículos com janela de tempo PRVJT . . . . . 22
2.1.2.1 Formulação matemática de um PRVJT . . . . . . . . . . . . . . . . 23
2.1.3 Problema de roteamento de veículos com backhauls PRVB . . . . . . . . . . 23
2.1.3.1 Formulação matemática de um PRVB . . . . . . . . . . . . . . . . 24
2.1.4 Problema de roteamento de veículos com coleta e entrega PRVCE . . . . . . 25
2.1.4.1 Formulação matemática de um PRVCE . . . . . . . . . . . . . . . 26
2.1.5 Problema de roteamento de veículos com múltiplos depósitos PRVMD . . . . 27
ix
2.1.5.1 Formulação matemática do PRVMD . . . . . . . . . . . . . . . . . 28
2.1.6 Problema de roteamento de veículos com múltiplo uso de veículos PRVMUV 30
2.1.6.1 Formulação matemática do PRVMUV . . . . . . . . . . . . . . . . 30
2.1.7 Problema de roteamento de veículos com frota heterogênea PRVFH . . . . . 32
2.1.7.1 Formulação matemática PRVFH . . . . . . . . . . . . . . . . . . . 33
2.1.8 Problema de roteamento de veículos com entregas fracionadas PRVEF . . . . 34
2.1.8.1 Formulação matemática PRVEF . . . . . . . . . . . . . . . . . . . 34
2.1.9 Problemas de roteamento de veículos com janela de tempo e frota heterogê-
nea PRVJTFH . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
2.1.9.1 Formulação matemática do PRVJTFH . . . . . . . . . . . . . . . . 36
3 Métodos de resolução 37
3.1 Métodos exatos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
3.1.1 Branch-and-bound . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
3.1.2 Branch-and-cut . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
3.1.3 Branch-and-price . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
3.2 Heurísticas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
3.2.1 Heurísticas construtivas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
3.2.1.1 Heurística de Clarke e Wright CW . . . . . . . . . . . . . . . . . . 39
3.2.1.2 Heurística de Mole e Jameson MJ . . . . . . . . . . . . . . .. . . . 40
3.2.2 Heurísticas duas fases . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
3.2.2.1 Heurística de Gillet e Miller GM . . . . . . . . . . . . . . . . . . . 41
3.2.2.2 Algoritmo de Fisher e Jaikumar FJ . . . . . . . . . . . . . . . . . . 42
3.2.2.3 Algoritmo de Bramel e Simchi-Levi BS . . . . . . . . . . . . . . . . 42
3.2.2.4 Branch-and-bound truncado B&B-T . . . . . . . . . . . . . . . . . 43
3.2.2.5 Algoritmos petal . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
3.2.3 Heurísticas de melhoramento . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
3.2.3.1 𝑘-opt . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
3.2.3.2 Troca-𝜆 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
3.2.3.3 Transferência cíclica . . . . . . . . . . . . . . . . . . . . . . . . . . 47
3.2.3.4 Cadeias de ejeções (Ejection chain) . . . . . . . . . . . . . . . . . . 48
3.2.3.5 GENIUS (Generalized insertion procedure + unstringing stringing) 49
3.2.3.6 Troca cruzada (CROSS exchange) . . . . . . . . . . . . . . . . . . 50
3.2.3.7 Busca em uma vizinhança grande BVG . . . . . . . . . . . . . . . . 51
3.3 Metaheurísticas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
3.3.1 Arrefecimento simulado AS . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
3.3.2 Arrefecimento determinístico AD . . . . . . . . . . . . . . . . . . . . . . . . 53
3.3.3 Busca tabu BT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
3.3.4 Algoritmos genéticos AG . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
3.3.5 Colônias de formigas CF . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
3.3.6 Redes neurais RN . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
x
4 O estudo de caso 59
4.1 A cidade de Coxim - MS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
4.1.1 Transporte escolar em Coxim - MS . . . . . . . . . . . . . . . . . . . . . . . 60
4.2 Instituto Federal de Educação, Ciência e Tecnologia de Mato Grosso do Sul - Cam-
pus Coxim . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
4.3 Problema 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
4.3.1 Modelo matemático . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
4.3.1.1 Variável de decisão . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
4.3.1.2 Parâmetros . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
4.4 Problema 2: planejamento logístico . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
4.4.1 Preparação dos dados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
4.4.2 Problema 2.1 - seleção dos pontos de ônibus . . . . . . . . . . . . . . . . . . 65
4.4.3 Problema 2.2 - planejamento e desenho das rotas de ônibus . . . . . . . . . . 66
4.4.3.1 Variáveis de decisão . . . . . . . . . . . . . . . . . . . . . . . . . . 66
4.4.3.2 Parâmetros . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66
4.4.3.3 Conjuntos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66
4.4.3.4 Formulação do modelo . . . . . . . . . . . . . . . . . . . . . . . . . 67
4.5 Implementação e resultados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
4.5.1 Problema 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68
4.5.2 Problema 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
4.5.3 Problema 2.2 - planejamento e desenho das rotas de ônibus . . . . . . . . . . 70
5 Considerações finais 77
Referências Bibliográficas 81
Apêndices 86
A Algoritmos implementados e dados utilizados 87
A.1 Implementação 4.5.1 - Problema da quantidade mínima de ônibus . . . . . . . . . . 87
A.2 Implementação 4.5.2 - Seleção dos pontos de ônibus . . . . . . . . . . . . . . . . . . 88
A.3 Implementação 4.5 - Planejamento e desenho das rotas de ônibus - minimização de
ônibus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89
A.4 Implementação 4.5.3 - Planejamento e desenho das rotas de ônibus . . . . . . . . . . 90
A.5 Coordenadas geográficas das localizações dos 165 estudantes do IFMS . . . . . . . . 91
xi
xii
A Deus . . . .
Aos meus avós . . . .
Aos meus pais . . . .
A minha esposa . . . .
E a todos que me apoiaram . . . .
xiii
xiv
Agradecimentos
Agradeço em especial ao meu orientador Cristiano Torezzan, muitas vezes sendo meu orientador
e também amigo, com ótimos conselhos em como trabalhar e como conquistar os desafios.
Agradeço também a todo apoio técnico administrativo que tive no Instituto Federal de Educa-
ção, Ciência e Tecnologia de Mato Grosso do Sul, com a coleta dos dados para o estudo de caso, em
especial a Soray Mesquita Rodovalho Gonçalves sempre atenciosa e prestativa. Sem ela as coisas
teriam sido mais complicadas.
Aos meus diretores Marcela Rubim Schwab Leite Rodrigues e Carlos Vinicíus da Silva Figuei-
redo que sempre na medida do possível me apoiaram no âmbito institucional para conclusão deste
mestrado.
Ao apoio de meu amigo o Professor Alexandre Fornaro com grandes contribuições na revisão
ortográfica do texto.
E aos meus colegas de área sempre quando tinha necessidade assumiam meus trabalhos para
dedicação do mestrado.
E finalmente a minha esposa Talina Meirely Nery dos Santos, por ser essa pessoa gentil e
amorosa e todo apoio que me deu.
xv
xvi
Lista de Ilustrações
1.1 Esquema da estratégia LAR Park e Kim [1] . . . . . . . . . . . . . . . . . . . . . . 7
1.2 Esquema da estratégia ARL Park e Kim [1] . . . . . . . . . . . . . . . . . . . . . . 7
3.1 Esquema heurística 2-opt . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
3.2 Esquema heurística 3-opt . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
3.3 Esquema procedimento 1-troca . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
3.4 Esquema procedimento 1-permutação . . . . . . . . . . . . . . . . . . . . . . . . . . 46
3.5 Transferência cíclica - solução inicial sem refinamento . . . . . . . . . . . . . . . . . 47
3.6 Transferência cíclica - solução refinada . . . . . . . . . . . . . . . . . . . . . . . . . 48
3.7 GENI: tipo 1 - Inserção de um vértice 𝑣 entre os vértice 𝑣𝑖 e 𝑣𝑗 . . . . . . . . . . . 49
3.8 GENI: tipo 2 - Inserção de um vértice 𝑣 entre os vértice 𝑣𝑖 e 𝑣𝑗 . . . . . . . . . . . 50
3.9 Troca cruzada . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
3.10 Solução AG para PRV . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
3.11 Evolução de um modelo deformável em a), b), c) e solução final em d) . . . . . . . 56
4.1 Cidade de Coxim - MS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
4.2 IFMS - Campus Coxim . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
4.3 Questionário . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
4.4 Mapa de localização dos estudantes do IFMS . . . . . . . . . . . . . . . . . . . . . . 64
4.5 Pontos de ônibus - Google Earth . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70
4.6 Pontos de ônibus e estudantes - Google Earth . . . . . . . . . . . . . . . . . . . . . 70
4.7 Pontos de ônibus, estudantes e escola - Google Earth . . . . . . . . . . . . . . . . . 71
4.8 Sistema de rotas - Busca branch-and-cut - Google Earth . . . . . . . . . . . . . . . 74
4.9 Sistema de rotas - Busca heurística - Google Earth . . . . . . . . . . . . . . . . . . 74
xvii
xviii
Lista de Tabelas
4.1 Tipos e quantidade de veículos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
4.2 Tipos e quantidade de veículos - zona urbana . . . . . . . . . . . . . . . . . . . . . 68
4.3 Tipose quantidade de veículos - zona urbana . . . . . . . . . . . . . . . . . . . . . 68
4.4 Localização dos pontos de ônibus . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
4.5 Resultados de veículos para 165 estudantes . . . . . . . . . . . . . . . . . . . . . . . 71
4.6 Coordenadas Escola Artificial e Depósito . . . . . . . . . . . . . . . . . . . . . . . . 72
4.7 Rota 1 - branch-and-cut . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72
4.8 Rota 1 - Busca heurística . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72
4.9 Rota 2 - Busca branch-and-cut . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73
4.10 Rota 2 - Busca heurística . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73
4.11 Rota 3 - Busca branch-and-cut . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73
4.12 Rota 3 - Busca heurística . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73
4.13 Distância total percorrida em 𝑘𝑚 - Busca branch-and-cut . . . . . . . . . . . . . . . 75
4.14 Distância total percorrida em 𝑘𝑚 - Busca Heurística . . . . . . . . . . . . . . . . . 75
A.1 Coordenadas dos 165 estudantes do IFMS . . . . . . . . . . . . . . . . . . . . . . . 92
xix
xx
Introdução
O desenvolvimento de métodos eficazes que têm o objetivo de planejar e desenhar rotas de veí-
culos é uma área interdisciplinar de pesquisa bastante ativa. Nas últimas décadas, novos problemas
e métodos têm sido propostos na literatura. A atenção dada a estes problemas é, em grande parte,
motivada pela necessidade constante de redução de gastos nos processos de logística de entrega de
produtos ou na prestação de serviços à população.
O Problema de Roteamento de Veículos (PRV) é uma extensão natural do Problema do Caixeiro
Viajante (PCV), ao adicionar diversas restrições. Como o PRV pode ser reduzido a um PCV,
ele pertence à classe de problemas NP-Difícil. O PRV clássico consiste em encontrar a melhor
maneira de atender um conjunto de clientes 𝐶, cada cliente com uma demanda 𝑞𝑖 por um produto
(ou serviço) e, um depósito com veículos de capacidade 𝑄, de maneira que o somatório de todas
as demandas dos clientes não ultrapasse a capacidade 𝑄 dos veículos.
Os modelos e algoritmos propostos para resolução de PRV, podem ser aplicados de forma eficaz
em diversos problemas do mundo real que derivam de sistemas de transportes. As aplicações mais
típicas desse tipo de problema são:
• coleta de lixo;
• limpeza de ruas;
• planejamento de transporte escolar;
• sistemas dial-a-ride;
• transporte de pessoas portadoras de necessidades específicas (PNE);
• roteamento de vendedores e de unidades de manutenção.
A rede de estradas utilizada para um sistema de transporte pode ser descrita através de um
grafo, na qual os arcos representam partes da estrada e os vértices representam os cruzamentos,
depósitos e localização dos clientes. Cada arco está associado a um custo, que normalmente
representa a distância à percorrer ou o tempo de percurso, que irá depender do tipo de veículo
usado ou o período em que o percurso acontece, podendo ser em horários de picos com grande
congestionamento de veículos.
Os percursos realizados pelos veículos para atender os clientes começam e terminam em um
ou mais depósitos, localizados em um ou mais vértices do grafo que representa a rede de estradas.
Cada depósito é caracterizado pela demanda total de mercadorias, pela quantidade e tipo de
1
veículos que suporta. Em algumas aplicações do mundo real os clientes são divididos entre os
depósitos, os veículos devem retornar ao depósito de partida ao final de cada percurso. Quando
isso ocorre, o PRV pode ser decomposto em subproblemas independentes, cada um associado a
um depósito distinto.
Umas das muitas aplicações de PRV, é o transporte escolar, conhecido também como Problema
de Roteamento de Ônibus Escolar (PROE), que visa planejar eficientemente um cronograma para
uma frota de ônibus escolares no qual veículos recolhem estudantes em vários pontos de ônibus e
os entregam em escolas designadas, satisfazendo várias restrições como a capacidade máxima dos
veículos, o tempo máximo de permanência do estudante no veículo e a janela de tempo de uma
escola (período de inicio ou fim do período diário letivo).
Conforme é descrito em Park e Kim [1], a resolução de um PROE envolve geralmente 5 passos:
preparação dos dados, seleção de pontos de ônibus, planejamento e desenho das rotas de ônibus,
sincronização com os horários da escola e refinamento das rotas.
Nesta dissertação apresentamos uma revisão sobre PROE, que foi baseada em Park e Kim [1].
Este trabalho motivado por uma questão prática, surgida na disciplina de Pesquisa Operacional,
que envolve uma situação vivenciada pelo autor na cidade de Coxim-MS.
O município de Coxim está localizado na região norte do Estado de Mato Grosso do Sul, sendo
cortado pelos rios Coxim e Taquari. De acordo com o Censo do IBGE de 2010, o município
tem 32.159 habitantes com área territorial de 6.409,224 km2. O município é composto por vários
distritos em que os principais são: Jauru, São Ramão, Taquari e Silviolândia. A cidade de Coxim
não conta com transporte coletivo público ou privado, tendo somente o serviço de táxi ou moto-
táxi. Para atender a rede pública de ensino a prefeitura municipal conta com um serviço gratuito
para o transporte escolar dos estudantes no períodos matutino, vespertino e noturno.
Desde o ano 2010 Coxim, conta com o Instituto Federal de Educação, Ciência e Tecnologia
de Mato Grosso do Sul (IFMS). A partir do ano 2011 o IFMS passa a ofertar cursos de nível
médio com técnico integrado na área de informática e alimentos, e o curso de licenciatura plena
em química, que atendem estudantes de toda a região norte do estado. Com a maior demanda de
cursos e projetos do governo federal, existe a necessidade, por parte do poder público, de ofertar
transporte escolar de qualidade com o objetivo de ampliar o desenvolvimento da instituição de
ensino. Nas diversas reuniões pedagógicas do corpo docente da instituição, um dos principais
assuntos discutidos é o quanto a metodologia do transporte escolar pode afetar o rendimento e a
participação dos estudantes nas atividade de ensino da instituição. A motivação deste trabalho
parte dessas discussões.
O restante desta dissertação está organizada da seguinte forma: No Capítulo 1, apresentamos
uma revisão sobre o PROE. Em seguida descrevemos de forma geral o PRV e algumas de suas
extensões, incluindo algumas sugestões encontradas na literatura sobre formulações matemáticas
baseadas em Programação Linear Inteira Mista. No Capítulo 3, apresentamos de um modo geral
alguns métodos de resolução para o PRV: métodos exatos e os métodos aproximados. No Capítulo
4, apresentamos o nosso estudo de caso, que está dividido em 2 problemas:
1. No primeiro caso estudamos o problema de encontrar o menor número possível de veículos
para efetivação do transporte escolar na cidade de Coxim - MS nos períodos matutino e
vespertino. Neste caso não é considerado as rotas que os veículos utilizam e nem a quantidade
2
de pontos de ônibus ou suas localizações. Uma boa solução deste problema pode ter impactos
importantes nos gastos com a contratação de ônibus extras.
2. No segundo caso é feito um planejamento logístico para o transporte dos estudantes do IFMS
do campus Coxim do período matutino, em que definiremos a quantidade mínima de ônibus,
a localização dos pontos de ônibus e suas rotas, utilizando os algoritmos apresentados nos
Capítulos 1, 2, 3.
As nossas considerações finais são apresentadas no Capítulo 5.
3
4
Capítulo 1
O problema de roteamento de ônibus
escolar: uma revisão
Neste capítulo apresentaremos uma revisão sobre os principais conceitos envolvidos no pro-
blema de planejamento e roteamento de veículos para o transporte escolar a seremutilizados nessa
dissertação. Este capítulo é, em grande parte, baseado no artigo Park e Kim [1], que servirá de
referência para o estudo de caso que será apresentado no Capítulo 4.
O objetivo é fornecer uma análise abrangente do Problema de Roteamento de Ônibus Escolar
(PROE), que visa planejar eficientemente um cronograma para uma frota de ônibus escolares no
qual veículos recolhem estudantes em vários pontos de ônibus e os entregam em escolas designa-
das, satisfazendo várias restrições como a capacidade máxima dos veículos, o tempo máximo de
permanência do estudante no veículo e a janela de tempo de uma escola (horário de início ou fim
do período letivo).
1.1 Planejamento do sistema
A solução de um PROE envolve, em geral, 5 passos (sub-problemas) conforme descrito em Park
e Kim [1]: preparação dos dados, seleção de pontos de ônibus, planejamento e desenho das rotas
de ônibus, sincronização com os horários da escola e refinamento das rotas. A seguir detalhamos
cada um destes 5 passos.
1.1.1 Preparação dos dados
O sub-problema Preparação dos dados tem como objetivo preparar os dados para os outros
sub-problemas. A rede de possíveis rotas é especificada e quatro conjunto de dados para o PROE
são preparados: estudantes, escolas, veículos e matriz origem-destino (OD).
Os dados referentes aos estudantes contam com localização (endereços) de suas residências, a
escola de destino de cada estudante e o tipo de estudante é uma variável que indica se o estudante
é ou não Portador de Necessidade Específica (PNE).
Os dados referente a cada escola contém informações sobre a localização das escolas, o tempo
de início e término das aulas para chegada dos ônibus, o tempo máximo de condução do estudante
5
no ônibus. Na maioria dos estudos o tempo de início e término das aulas são apresentados, no
entanto, vários estudos disponíveis assumem que os tempos inicial e final podem ser determinados
pela variável ajuste de tempo do sino da escola (horário de início e término das aulas).
Os dados referentes aos veículos contém informações sobre o local de origem e os tipos de
ônibus disponíveis para o transporte escolar. Cada tipo de ônibus pode ter capacidades distintas
para estudantes em geral e veículos próprios ou compartilhados para PNE ou educação especial.
A matriz OD armazena os menores tempos de viagem entre os pares de nós (escolas, localização
dos estudantes e local de origem dos ônibus). A matriz OD pode ser calculada usando um sistema
de informação geográfica (GIS - sigla em inglês), como o Google Earth usado no Capítulo 4 para o
estudo de caso deste trabalho. Em Kim e Jeong [2] é apresentado uma comparação de desempenho
de vários algoritmos resolução do problema do caminho mínimo e é desenvolvida uma abordagem
para a geração aproximada da matriz OD.
1.1.2 Seleção de pontos de ônibus
Este sub-problema procura selecionar um conjunto de pontos de ônibus e atribuir estudantes
para estes pontos. Para estudantes que residem na zona rural, assume-se que em cada residência há
um ponto de ônibus. Entretanto, na zona urbana é planejado que os estudantes devem caminhar
até um ponto de ônibus a partir de suas casas e pegar o ônibus para a sua escola.
Na maioria dos casos os pontos de ônibus são assumidos como fixos e o problema se resume a
designar os estudantes a tais pontos. Por isso, em vários trabalhos que estudam PROE, a etapa
de seleção dos pontos chega a ser omitida.
Quando é necessária a solução deste sub-problema, as técnicas mais utilizadas são heurísticas
para variantes do problema de alocação e também métodos do tipo 𝑝-medianas (𝑝-facilidades) para
escolha dos pontos. Em Park e Kim [1] é apresentada uma lista de trabalhos que consideram este
sub-problema.
De maneira geral, as soluções heurísticas para este caso se classificam em dois tipos: Location-
Allocation-Routing (LAR) e Allocation-Routing-Location (ARL). A primeira determina inicial-
mente um conjunto de pontos de ônibus para cada escola e depois atribui os estudantes aos pontos
de ônibus. Por fim as rotas são definidas a partir destes pontos. No entanto, uma vez que os pontos
de ônibus são atribuídos e os estudantes são determinados sem levar em consideração os efeitos
sobre a geração das rotas, este método tende a gerar rotas excessivas, ou seja, rotas que tendem a
não serem usadas ou pouco usadas. A Figura 1.1 ilustra um esquema da estratégia LAR. Por outro
lado, a segunda estratégia divide os estudantes em grupos (clusters) satisfazendo a restrição de
capacidade dos veículos e, em seguida, são selecionados os pontos de ônibus e, só então, é gerada
uma rota para cada cluster. Finalmente, os estudantes em cada cluster são atribuídos a um ponto
de ônibus satisfazendo todas as restrições apresentadas no problema, como a distância máxima de
caminhada a partir da residência, número máximo de estudantes atribuídos por pontos de ônibus,
a distância mínima que separa os pontos de ônibus. A Figura 1.2 ilustra um esquema da estratégia
ARL.
6
Figura 1.1: Esquema da estratégia LAR Park e Kim [1]
Figura 1.2: Esquema da estratégia ARL Park e Kim [1]
1.1.3 Planejamento e desenho das rotas de ônibus
Neste sub-problema são construídas as rotas até as escolas. Os algoritmos para este sub-
problema são classificados em dois modelos “route-first, cluster-second” e “cluster-first, route-
second” que foram abordados por Bodin e Berman [3].
Em “route-first, cluster-second” com um algoritmo baseado no PCV desenvolve-se um grande
percurso que considera todos os pontos de ônibus, em seguida esse percurso é particionado em
rotas menores considerando as restrições do problema. Em Newton e Thomas [4], Bodin e Berman
[3] há uma implementação desse método.
No método “cluster-first, route-second” os estudantes são agrupados em clusters de modo que
cada um seja um percurso que satisfaça as restrições. Em Dulac, Ferland e Forgues [5], Chapleau,
7
Ferland e Rousseau [6] e Bowerman, Hall e Calamai [7] existem aplicações desse método para um
PROE.
Podemos destacar quatro modelos de planejamento:
1. ônibus dedicado para o cluster : cada ônibus é designado para pegar todos os estudantes de
um cluster e posteriormente passar por todas as escolas deixando os estudantes. Na volta, o
ônibus passa em todas as escolas e se dirige ao cluster.
2. ônibus dedicado para a escola: os ônibus são designados para as escolas e devem passar nos
pontos pegando apenas os estudantes da referida escola.
3. conexão com terminal: nesse modelo temos uma combinação dos dois primeiros, onde, os
ônibus serão distribuídos aos clusters e então será determinada uma rota até um terminal,
deste terminal, serão determinadas rotas até as escolas.
4. estratégias híbridas: são estratégias que combinam, de alguma forma, as três estratégias bá-
sicas relacionadas anteriormente. Esta política geralmente é adotada em grandes metrópoles
ou conglomerados urbanos complexos.
Após o planejamento das rotas até a escola, heurísticas de melhoramento podem ser aplicadas.
Há um enorme número de heurísticas de melhorias e métodos metaheurísticos. O método heurístico
sugerido por Lin [8], chamado de 𝑘-opt, é amplamente adotado em estudos de PRV. O algoritmo
apaga 𝑘 caminhos da rota e adiciona 𝑘 caminhos factíveis. A idéia do algoritmo 𝑘-opt é adotado
em vários estudos de PROE. Em Newton e Thomas [4], Dulac, Ferland e Forgues [5], Chapleau,
Ferland e Rousseau [6] e Desrosiers et al. [9] aplicaram o algoritmo 2-opt para melhorarem sua
solução. Em Bennett e Gazis [10], Bodin e Berman [3] adotaram algoritmos 3-opt.
1.1.4 Sincronização com os horários da escola
De acordo com Park e Kim [1], em muitos estudos o inicio e término dos horários escolares
são tratados como restrições. Entretanto, há uma série de trabalhos que consideram os horários
como variáveis de decisão com o objetivo de encontrar um tempo de inicio e término ótimo a fim
de maximizar o númerode rotas para um mesmo ônibus, assim, reduzindo o número de ônibus
utilizados. Em Desrosiers [11], Desrosiers et al. [9] determina-se o inicio e término dos horários
escolares utilizando um método de geração de colunas. Em Bodin [12] adaptou-se o método
de Desrosiers [11], Desrosiers et al. [9], afirmando que para problemas de pequeno porte podem
ser resolvidos manualmente e Fügenschuh [13] considerou o problema permitindo ao estudante a
mudança de rota e um modelo de Programação Inteira Mista (PIM) foi desenvolvido utilizando
um método branch-and-cut com vários mecanismos de pré-processamento com cortes válidos.
1.1.5 Refinamento das rotas
Neste sub-problema especifica-se a hora exata do início e término de cada rota, e define-se uma
cadeia de rotas executadas pelo mesmo ônibus.
8
Foi desenvolvido por Newton e Thomas [14] um modelo multi-escola para determinar todas
as rotas de ônibus escolar para um distrito escolar, na qual assumiram que existem períodos de
tempos distintos e as escolas tem horários distintos para inicio término dos períodos. Em Bodin
[15], Bodin e Berman [3], os autores assumem também que as janelas de tempo das escolas podem
ser divididas em períodos distintos, então o problema de roteamento de ônibus escolar pode ser
resolvido por período e posteriormente o percurso total é agrupado. No entanto, essa abordagem
pode não funcionar quando os tempos de horários das escolas se sobrepõem, ou seja, o horário de
término de um período anterior pode ser maior que o início do próximo período.
Foi utilizado por Desrosiers [11], Desrosiers et al. [9] um método heurístico para a solução de
uma série de problemas de transporte e, referência Graham e Nuttle [16] mostra comparações para
diversas heurísticas produzidas para o refinamento de rotas escolares. O trabalho de Desrosiers
et al. [17] apresenta três algoritmos que foram testados em oito problemas de transporte escolar
em várias configurações, considerando distintos os período da manhã ou tarde e a janela de tempo
entre os períodos.
Em Braca et al. [18] foi descrito um problema de roteamento de ônibus escolar para a cidade
Nova York, na qual resolveram para todas as escolas em uma única etapa, sendo que na maior parte
da literatura o problema é resolvido individualmente para cada escola e em seguida é determinado
um cronograma de rota para cada ônibus. Já Li e Fu [19] aplicou o algoritmo 𝑘th de caminho
mínimo de Lawler [20] para gerar uma rota inicial e um esquema de refinamento em que os pontos
de ônibus das rotas maiores são movidos para as rotas menores. Para os ônibus que tem a mesma
capacidade o problema de atribuição é formulado com o objetivo de minimizar os espaços vazios nos
ônibus. A abordagem do PROE para múltiplas escolas é feita em Spada, Bierlaire e Liebling [21],
e propôs um método heurístico, considerando as escolas pela ordem crescente de seus horários de
início e as rotas são construídas para cada escola por meio de uma estratégia gananciosa1. Depois
disso se possível as rotas são unidas e então essas rotas são refinadas por Simulated Annealing ou
Busca Tabu.
1.2 Classificação dos problemas
Os problemas de PROE é classificado em diversas categorias. Nesta seção detalhamos as
categorias propostas por Park e Kim [1].
1.2.1 Número de escolas: única ou múltiplas
A estrutura para um problema envolvendo uma única escola é semelhante ao problema clássico
de PRV, ou seja, a rota começa a partir de um depósito, visita uma série de clientes e retorna ao
depósito de origem. Entretanto em um PROE o depósito de origem normalmente é diferente da
localização da escola. Além disso, em um PROE, o tempo de duração ou distância do depósito até
o primeiro ponto de ônibus e a distância da escola até o depósito de partida não são considerados.
Assim, as estruturas de rotas para os veículos de um PROE são semelhantes a um Problema de
1Algoritmo ganancioso: a cada iteração o algoritmo escolhe a ação mais favorável, na qual a definição de favorável
é estabelecido inicialmente.
9
Roteamento de Veículos Aberto (PRVA) Fu, Eglese e Li [22]. Uma característica importante de
um PRVA é que o veículo não retorna ao depósito de origem depois de visitar o último cliente em
uma rota Li, Golden e Wasil [23].
Para a estrutura multi-escolar, existem duas abordagens diferentes para definição de rotas Park
e Kim [1], Spada, Bierlaire e Liebling [21]:
1. baseada na escola: é planejado um conjunto de rotas para cada escola e uma frota de ônibus é
designada para a rota. Feito isto, procede-se um refinamento em relação as janelas de tempo
da escola. Nesta abordagem não é permitido que estudantes de diferentes escolas tomem
o mesmo ônibus ao mesmo tempo. Em Braca et al. [18] apresenta-se um método baseado
nessa abordagem que insere um ponto de ônibus por vez em cada rota. Quando o ponto é
inserido em uma rota determinada a escola correspondente a esse ponto também deve estar
nessa rota. Se a escola não estiver na rota o algoritmo procura o melhor local para inserir
o ponto da escola levando em consideração o custo para inserir tal ponto, também deve ser
observado a relação de prioridade entre o estudante e a escola Bredström e Rönnqvist [24]
2. baseada no endereço do estudante: ao contrário da anterior, essa abordagem permite que
alunos de várias escolas sejam transportados pelos ônibus nos mesmos horários. Esta é a
abordagem mais comum nas cidades brasileiras.
1.2.2 Área rural × área urbana
O método de solução de um PROE pode variar se o tipo de serviço é para área rural ou
urbana. Supõe-se que nas áreas urbanas os estudantes podem caminhar de suas casas até os
pontos de ônibus. Já nas áreas rurais o número de estudantes é pequeno e normalmente os pontos
são definidos em suas próprias casas. Portanto, não é necessário a designação de pontos de ônibus
nas áreas rurais. Como é observado em Park e Kim [1], que geralmente a lotação máxima dos
ônibus são alcançadas antes do final do percurso de transporte de um estudantes devido a alta
concentração de estudantes nas áreas urbanas.
Foi apontado em Chen et al. [25] que um sistema de escola rural é diferente de um sistema
de escola urbana, devido aos seguintes fatos: menor densidade populacional, maior distância per-
corrida por rota, menor número de estudantes por pontos de ônibus, maior número de pontos de
ônibus por rota, poucas ou praticamente nenhuma rua de sentido único, maior número de ônibus
devem passar a noite nas casas do motoristas, menor número de estradas alternativas para os
pontos distantes da escola. Em Howley, Howley e Shamblen [26] foi estudado a diferença entre
o transporte de estudantes de áreas rurais e de áreas sub-urbanas2 por meio de uma pesquisa de
opinião, na qual, verificaram várias hipóteses de sua pesquisa como longos tempos de viagem e
ampliação de atendimento em áreas rurais. A singularidade da área rural, foi discutida em Rip-
plinger [27], ressalta-se que a solução ótima poderia ser gerada manualmente, pois, o tamanho do
problema é relativamente pequeno.
2Áreas sub-urbanas são regiões com grande concentração da população que se organizam em centro urbanos
secundários
10
Mas podemos também considerar um problema híbrido dos casos anteriores, que há rotas rurais,
sub-urbanas e urbanas percorrida por um mesmo ônibus para estudantes residentes nas áreas rurais
e que estudam em escolas urbanas.
1.2.3 Problemas: manhã × tarde
Durante a manhã os estudantes são apanhados em seus pontos de ônibus e levados até suas
escolas. Já no período da tarde os estudantes são apanhados em suas escolas e levados até seus
respectivos pontos de partida. Em Braca et al. [18] afirmou que os problemas da manhã tem maior
dificuldade em solução por dois motivos:
1. janela de tempo das escolas mal distribuídas;
2. trafego de veículos mais pesados.
De acordo com Park e Kim [1] os problemas da tarde recebem menor atenção do que os
problemas da manhã,em que muitos estudos são dedicados aos problemas da manhã e o problema
da tarde é brevemente mencionados. De acordo com Li e Fu [19] que os PROE para tarde podem
ser convertidos em PROE para manhã com poucas modificações.
Em Bodin e Berman [3] apresenta-se uma abordagem simples para o problema da tarde,
considera-se a mesma rota utilizada no problema da manhã, ou, inverte-se a sequência de ponto
de ônibus a fim de se obter o menor tempo de viagem. Seria mais intuitivo a sequência invertida,
entretanto, repetir a sequência é preferível do ponto de vista em equilibrar a isonomia do tempo de
viagem entre todos os estudantes, logo em seguida usando as rotas para cada escola são planejadas
as cadeia de rotas.
Nos trabalhos Desrosiers [11], Desrosiers et al. [17] produziram todas as possíveis combinações
de horários para uma rota considerando suas restrições, como limite superior o tempo de espera
dos estudantes entre sua chegada na escola e o horário de inicio das aulas. Em uma combinação
de horário há informações sobre o tempo total de percurso e quando é executado, se de manhã ou
de tarde. Ao selecionar um conjunto ideal de combinações para as rotas, os horários para manhã
e tarde são definidos simultaneamente.
Em outros problemas envolvendo manhã e tarde Bookbinder e Edwards [28] abordaram como
um tipo diferente de PROE, chamado de programa de programação. Neste programa procura-se,
definir o melhor plano de transporte para estudantes em várias escolas com atividades especiais,
como natação e arte industrial.
1.2.4 Carregamento misto
O problema de carregamento misto pode acontecer na zona rural, na qual o carregamento misto
de estudantes é permitido, estudantes de diferentes escolas podem ser alocados nos mesmos ônibus
ao mesmo tempo, gerando um aumento na flexibilidade e redução de custos é apontado em Braca
et al. [18]. Quando não são permitidas carga mista, o problema torna-se problemas de cargas
únicas na qual cada escola tem ônibus exclusivos para seus estudantes Bodin [12]. A suposição
11
de carga única é excessivamente restritiva e poderia usar um número excessivo de ônibus para
estudantes em localidades mais distantes Chen, Kallsen e Snider [29].
Embora o problema de carregamento misto seja discutidos em vários trabalhos Bodin e Berman
[3], Bodin [12], Chen, Kallsen e Snider [29], Spada, Bierlaire e Liebling [21], apenas Braca et al.
[18] propôs realmente um algoritmo para carregamento misto. Como foi desenvolvido por Chen,
Kallsen e Snider [29] um sistema especializado para um distrito escolar rural permitindo cargas
mistas nas rotas, entretanto as rotas foram geradas manualmente. Com uma ferramenta interativa
para o usuário manipularam cargas mistas Spada, Bierlaire e Liebling [21].
Uma heurística de localização baseado em Bramel e Simchi-Levi [30], foi proposta em Braca
et al. [18] que originalmente foi desenvolvida para Problemas de Roteamento de Veículos Capaci-
tados (PRVC). Sua abordagem foi baseada em um regra simples, o algoritmo verifica dois vértices
consecutivos em um percurso e verifica se um ponto de ônibus pode ser inserido entre eles, se a
escola de destino desse ponto não está na rota então o algoritmo também determina a melhor
posição de inserção para a escola. Subsequentemente, um conjunto de rotas é atualizado através
da inserção de um ponto para a rota que resulta na menor distância total do percurso, com esse
procedimento notaram que há uma dificuldade de verificação de viabilidade quando o ponto de
ônibus é adicionado a uma rota. Enquanto em um PRVC há apenas uma parcela fora do ponto
(depósito final), em percursos escolares múltiplos há mais de uma parcela fora das rotas dos pontos,
então é necessário determinar quando e onde o estudante entra e saí do ônibus.
1.2.5 Transporte de estudantes de necessidades especiais
O problema de planejamento de transporte de estudantes de necessidades específicas é funda-
mentalmente diferente em muitos aspectos do problema de roteamento de estudantes mais gerais.
Primeiramente, esses estudantes são apanhados diretamente em suas casas e não em pontos de
ônibus pré-determinados. Em segundo lugar, não há uma restrição muito rígida para o tempo
máximo de permanência do estudante no ônibus como no transporte de estudantes de forma mais
geral. Em terceiro lugar cada estudante deve ser atendido de modo diferente dependendo da ca-
racterística de sua necessidade específica. Uma vez que alguns estudantes necessitam de ajuda e
equipamentos especiais eles devem ser atribuídos a um ônibus especializado capaz de atende-los.
Como observado em Park e Kim [1] existem poucos trabalhos que consideram o transporte de es-
tudantes de educação especial. Foi abordado em Russell e Morrel [31] o problema de planejamento
de ônibus para educação especial, construíram uma solução inicial, utilizando uma modificação
no algoritmo de economia apresentado em Clarke e Wright [32], melhorando a solução por meio
de um algoritmo 3-opt e utilizando um algoritmo de melhoramento proposto em Russell e Mor-
rel [31]. Entretanto, uma vez que essas rotas muitas vezes tem várias escolas de destino, devido
a diversidade de estudantes, o número de escolas a serem visitados por um ônibus tende a ser
muito excessivo. Os autores desenvolveram um sistema de transporte a fim de reduzir o tempo
de permanência dos estudante nos ônibus e o número de escolas de destino. Em Braca et al. [18]
foi discutido brevemente o transporte de estudante de necessidades específicas e apresentaram o
sistema de transporte escolar da cidade de Nova York, onde cerca de 125.000 estudantes utilizam
o transporte escolar e 40.000 desses são classificados como estudantes de necessidades específicas.
O trabalho de Ripplinger [27] tratando estudantes com necessidades específicas nas áreas rurais
12
foi abordado de duas maneiras. A primeira faz a diferenciação de estudantes com e sem necessidades
específicas, em seguida, estes problemas são resolvidos separadamente. A segunda maneira gera
um plano de rotas de forma única para os dois tipos de estudantes.
1.2.6 Ônibus: homogêneo ou heterogêneo
O problema pode ser tratado de tal forma que sua frota seja heterogênea assim podemos assumir
que cada ônibus tem características distintas, tais como capacidade, tempo máximo de percurso,
custo fixo e custo variável por unidade de distância. O problema é semelhante ao um PRV com
veículos heterogêneos.
Foi assumido em Newton e Thomas [14] a hipótese de ônibus com capacidade única. Entretanto,
há alterações nas capacidades para cada escola, pois cada escola tem sua própria política de
capacidade máxima e se são permitidos estudantes de não sentados.
No trabalho deBowerman, Hall e Calamai [7] foi estudado o problema de roteamento de ônibus
de mesma capacidade. Na maioria dos estudos é considerado que um estudante ocupa um espaço
no ônibus, mas em Bowerman, Hall e Calamai [7] consideraram que um estudante das séries iniciais
ocupa 23 de espaço de um estudante regular, assim, neste caso dois ônibus de mesma capacidade
tem diferentes números de estudantes.
1.2.7 Objetivos
Em Park e Kim [1], Savas [33] propõem-se três medidas para avaliar o desempenho do serviço
público, utilizando estes critérios, Bowerman, Hall e Calamai [7], Fu, Eglese e Li [22] classificaram
esses objetivos como segue:
1. Eficiência: é definido como a razão entre a qualidade do serviço e o custo dos recursos
necessários para proporcionar esse serviço. Para uma determinada qualidade de serviço, a
eficiência é determinada pelo seu custo. De acordo com os autores Bowerman, Hall e Calamai
[7] existem dois componentes principais para o custo de um sistema de transporte escolar.
(a) Custo de capital necessário para adquirir um sistema de ônibus escolar.
(b) Custo por unidade de distância percorrida.
Portanto, uma solução que exige menos ônibus e tem menor tempo de viagem é preferível do
ponto de vista da eficiência.2. A eficácia de um serviço é medido pela maneira de como o público está satisfeito. Um
sistema de transporte de ônibus escolar deve estar disponível a todos os estudantes regular-
mente matriculados e deve ter um nível aceitável de satisfação. A eficácia de um sistema
de transporte de ônibus escolar pode ser medida através do tempo total de viagem e pela
distância que um estudante precisa caminhar.
3. A equidade avalia a justiça e a imparcialidade da prestação de um serviço. Uma solução
com boa medida de eficiência de baixo custo e com melhores perspectivas de custo e tempo,
13
mas seria inaceitável devido a falta de equidade do serviço aos estudantes. Eqüidade tem
sido negligenciada na avaliação de desempenho de um serviço de ônibus escolar, bem como
os serviços públicos. Para melhorar a equiedade de um serviço de transporte de ônibus
escolar deve ser considerado o balanceamento entre a quantidade de passageiros e o tempo
de percurso.
1.2.8 Restrições
Várias restrições são consideradas em um PROE, as restrições a seguir são listadas em Braca
et al. [18], Spada, Bierlaire e Liebling [21]:
• Restrição de capacidade do veículo - limitante superior sobre o número de estudantes em um
ônibus;
• Tempo máximo de percurso - limitante superior para o tempo de viagem para cada estudante;
• Distância máxima de caminhada - distância máxima permitida do ponto de ônibus até a casa
do estudante para o mesmo percorrer a pé;
• Janela de tempo da escola - janela de tempo para chegada e partida dos ônibus nas escolas;
• Limites máximos para o número de estudantes nos pontos;
• Tempo de recolhimento mais tarde para crianças
• Número mínimo de crianças para criação das rotas
Em alguns trabalhos essas restrições são consideradas como funções objetivo. Por exemplo o
tempo máximo de percurso como objetivo que visou minimizar o tempo de percurso para todas as
crianças é considerando em Bennett e Gazis [10], Li e Fu [19].
1.3 Classificação baseada nos métodos de solução
A combinação do problema de seleção de pontos de ônibus e planejamento e desenho das rotas
de ônibus de uma única escola é da classe NP-Difícil como mostrado em Bowerman, Hall e Calamai
[7]. Mesmo um único sub-problema, como seleção de pontos de ônibus ou planejamento e desenho
das rotas de ônibus pode ser mostrado ser um problema NP-Difícil. Na seleção de ponto de
ônibus, cada estudante deve ser atribuído a um ponto de ônibus e cada parada tem sua capacidade
máxima. Usando essas restrições, o problema de seleção de ponto de ônibus pode ser transformado
no problema de atribuição generalizada que também é conhecido como um problema NP-Difícil
Fisher, Jaikumar e Van Wassenhove [34]. O problema de planejamento e desenho das rotas de
ônibus com a capacidade máxima e as restrições de tempo máximo de percurso corresponde a uma
distância máxima restrita é um PRV Aberto que é conhecido como um problema NP-Difícil de
acordo com Bektaş [35]. Como é comentado em Park e Kim [1], devido a sua grande dificuldade
de solução a maioria dos estudos preferem métodos heurísticos em vez de métodos exatos. Apenas
alguns artigos utilizam métodos exatos para resolver partes de PROE.
14
1.3.1 Configurações de formulações matemáticas para um PROE
Os modelos matemáticos para um PROE são desenvolvidos utilizando várias configurações.
Usualmente os modelos são formulados utilizando Programação Inteira Mista (PIM) ou Progra-
mação Inteira Mista não Linear (PIMNL). Entretanto na maioria das vezes os modelos não são
utilizados para resolver todo o problema mas sim partes deles. Em Gavish e Shlifer [36] considera-se
o problema de desenho de linha de ônibus para uma única escola utilizando um modelo PIMNL. Os
autores propuseram limites superiores para o problema e utilizando o método branch-and-bound
resolvem uma sequência de problemas determinando a solução ótima. O algoritmo de Gavish e
Shlifer [36] foi melhorado por White [37] substituindo o problema de desenho de linha de linha
de ônibus para um problema de correspondente máximo. Os problemas de seleção de ponto de
ônibus e planejamento e desenho das rotas de ônibus foram considerados simultaneamente em
Bowerman, Hall e Calamai [7], na qual desenvolveram um modelo de PIMNL que não foi usado
para resolver o problema. Para o problema de planejamento e desenho de rotas de ônibus Li e
Fu [19] desenvolveram um modelo de PIMNL multi-objetivo e expressaram explicitamente várias
funções objetivo, sendo a formulação matemática não usada para resolver o problema. Ripplinger
[27] desenvolve um modelo PIM para o PROE da zona rural, o problema foi resolvido por um al-
goritmo heurístico. Um modelo para escola única como um problema múltiplo do caixeiro viajante
com múltiplos depósitos e um único destino foi modelado por Kara [38].
Modelos para uma única escola foram apresentados em Schittekat, Sevaux e Sorensen [39], Bek-
taş [35] e utilizado para a solução do problema. Foi considerado em Schittekat, Sevaux e Sorensen
[39] que uma escola é idêntica a um depósito e uma rota começa e termina na escola. Além disso,
considerou-se que a frota de veículos é homogênea e que a escolha de um estudante caminhar até
certo ponto de ônibus pode ser realizada ou não. Com base nessas hipóteses desenvolveram um
modelo PIM e resolveram um exemplo com 10 pontos e 50 estudantes. Observando-se que seu
modelo era simples e que não foi considerado restrições práticas tais como o tempo máximo de
percurso. Por outro lado em Bektaş [35] é proposto um modelo para o problema de planejamento
e desenho de rotas de ônibus, eles incluíram não só a capacidade dos veículo mas também um limi-
tante superior para o tempo de percurso de cada passageiro em um ônibus. Com essa formulação
encontraram uma solução ótima para uma escola primária de Ankara, Turquia com 29 pontos de
ônibus. Já em Desrosiers et al. [9], Fügenschuh [13] foi desenvolvido modelos PIM de multi-escola.
Com um modelo PIMNL Swersey e Ballard [40] foi transformado em dois modelos de programação
inteira discreta para o problema de planejamento e desenho de rotas para múltiplas escolas.
Nos trabalhos de Braca et al. [18], Spada, Bierlaire e Liebling [21] foram propostos modelos de
PIMNL que não foram utilizados para solucionar o problema, sendo que em Braca et al. [18] foi
formulado o modelo para o problema de planejamento e desenho de rotas de ônibus e o problema
de programação de horários de ônibus como um conjunto de problemas particionado. Entretanto,
foi considerado que o conjunto de rotas viáveis é dado. Em contrapartida em Spada, Bierlaire e
Liebling [21] foi apresentado uma formulação para o mesmo problema em um modelo PIMNL.
15
1.3.2 Métodos de solução
Problemas relativamente de pequenos porte normalmente são resolvidos por métodos exatos,
preferencialmente na maioria das vezes são utilizados métodos heurísticos na maioria dos estudos.
Aqui descreveremos a explicação detalhada dos métodos de solução utilizados para cada sub-
problema. E também serão apresentados as metaheurísticas aplicadas na solução de um PROE.
Nos últimos anos estão sendo propostas várias metaheurísticas para solução de problemas
de otimização combinatória: Arrefecimento Simulado (SA), Arrefecimento Determinístico (AD),
Busca Tabu (BT), Algoritmos Genéticos (AG), Otimização por Colônia de Formigas (OCF) e
Redes Neurais (RN). Essas metaheurísticas tem sido amplamente utilizadas em PRV (Gendreau,
Laporte e Potvin [41], Cordeau et al. [42], Yu, Yang e Yao [43], Belfiore, Yoshida Yoshizaki et al.
[44]) mas apenas alguns trabalhos tem aplicado metaheurísticas para um PROE conforme Park e
Kim [1].
Thangiah e Nygard [45] proporam um sistema automatizado de planejamento de ônibus es-
colares chamado GENROUTER. GENROUTER utiliza uma abordagem em duas fases com uma
variação dos métodos cluster-first e route-second. Na primeira fase é utilizado um método chamado
de setorização genética baseadaem um (AG) com a função de criar os cluster das residências dos
estudantes. Para o melhor conjunto de cluster obtidos na primeira fase, a segunda fase melhora
as rotas utilizando métodos de localização ótima.
Como citado por Park e Kim [1], em Corberán et al. [46] foi usado um método evolutivo
para melhorar a dispersão de soluções iniciais geradas por duas heurísticas que se baseiam em
mecanismos de clusters. Utilizando um método SA e um BT, em Spada, Bierlaire e Liebling
[21] foi melhorada uma solução inicial baseada em uma heurística de inserção. Utilizando um
algoritmo para gerar clusters, em Ripplinger [27] mostrado uma solução factível, para o PROE e
usado um algoritmo BT a solução inicial foi melhorada. Com quatro heurísticas diferentes, sendo
duas apresentadas em Corberán et al. [46], Pacheco e Martí [47] construiu um conjunto de soluções
factíveis a partir do algoritmo proposto em Fisher [48] e estudado um mecanismo de inserção. As
soluções encontradas por essas quatro heurísticas foram melhoradas através de uma BT.
16
Capítulo 2
Problemas de roteamento de veículos e
técnicas de solução
Neste capítulo apresentamos uma revisão da literatura sobre os problemas de distribuição de
mercadorias entre depósitos e clientes. Estes problemas são conhecidos como Problemas de Rote-
amento de Veículos (PRV) 1. Os modelos e algoritmos propostos para solução desses problemas,
podem ser aplicados de forma eficaz não somente a problemas destinados a entrega e coleta de bens,
mas para a solução de diversos problemas do mundo real que derivam em sistemas de transportes.
As aplicações mais típicas desse tipo de problema são:
• coleta de lixo;
• limpeza de ruas;
• planejamento de transporte escolar;
• sistemas dial-a-ride;
• transporte de pessoas portadoras de necessidades específicas (PNE);
• roteamento de vendedores e de unidades de manutenção.
A distribuição de bens se refere ao serviço feito, em um determinado período de tempo, para um
conjunto de clientes por um conjunto de veículos que são operados por um conjunto de operadores
(motoristas para o caso de caminhões, ônibus, etc.), a qual é executado em uma rede de estradas ou
caminhos convenientes. Em particular, a solução de um PRV visa a determinação de um conjunto
de rotas (caminhos, linhas, etc) cada uma realizada por um único veículo iniciando e terminando em
seu próprio depósito, de maneira que todos os requisitos de seus clientes sejam cumpridos e todas as
limitações operacionais sejam satisfeitas e o custo de transporte seja minimizado. Descrevemos as
características típicas dos problemas de roteamento e programação considerando seus componentes
principais (rede de estradas, veículos e motoristas), as principais restrições a serem impostas na
construção das rotas e os possíveis objetivos a serem minimizados.
1A principal referência que utilizamos neste capítulo é o livro Toth e Vigo [49]
17
A rede de estradas utilizada para o transporte de mercadorias geralmente é descrita através de
um grafo, no qual os arcos representam partes da estrada e os vértices representam os cruzamentos,
depósitos e localização dos clientes. Os arcos e consequentemente os grafos correspondentes podem
ser direcionados ou não, ou seja, eles podem ser percorridos por apenas uma direção (vias de único
sentido, geralmente de cidades ou rodovias) ou em ambas as direções. A cada arco é atribuído
um custo que normalmente representa a distância à percorrer ou o tempo de percurso, que irá
depender do tipo de veículo usado ou o período em que o percurso acontece. Podendo ser em
horários de picos e com grande congestionamento de veículos.
Como observado em Toth e Vigo [49], normalmente os clientes são caracterizados da seguinte
forma:
• vértice do grafo da rede de estradas em que um cliente está localizado;
• quantidade de bens (demanda), possivelmente de diferentes tipos que devem ser entregues
ou coletados nos clientes;
• períodos do dia (janela de tempo) em que um cliente pode ser atendido, possivelmente por
motivos em que o cliente se encontra aberto ou por limitações de transito. Por exemplo, nos
centros de algumas cidades brasileiras só pode ocorrer carga e descarga de mercadorias das
18:00 às 06:00.
• tempo necessário para carga e descarga de mercadorias que depende do tipo de veículo;
• subconjunto de veículos disponíveis que podem ser destinados ao cliente, por razão de limi-
tações de acesso ou restrições do cliente para carga e descarga.
As vezes não há possibilidade de atender os clientes. Nestes casos as quantidades a serem
entregues ou coletadas podem ser reduzidas ou não, podendo ocorrer a possibilidade de não aten-
dimento de um grupo de clientes. Deste modo, podem ser atribuídos prioridades ou penalizações
para a falta total ou parcial do serviço.
Os percursos realizados pelos veículos para os clientes serem atendidos começam e terminam
em um ou mais depósito, localizados nos vértices do grafo que representam as estradas. Cada
depósito é caracterizado pelo número, tipo de veículos e quantidade total de bens que suporta.
Em algumas aplicações do mundo real os clientes são divididos entre os depósitos e os veículos
devem retornar ao depósito de partida ao fim de cada percurso. Quando isso ocorre, o PRV pode
ser decomposto em problemas independentes cada um associado a um depósito distinto.
Por outro lado, o transporte de mercadorias é realizado usando uma frota de veículos compostos
por tamanhos fixos ou definidos de acordo com a exigências de cada cliente. Normalmente os
veículos são caracterizados como segue.
• Depósito de saída do veículo, com a possibilidade de que o depósito ao final do percurso seja
diferente do depósito de partida;
• Capacidade do veículo expressa pela quantidade máxima, ou o volume, ou o número de caixas
que o veículo pode transportar;
18
• Possibilidade do veículo ser dividido em subcompartimentos, cada um caracterizado pela sua
capacidade e tipo de produtos que podem ser transportados;
• dispositivos disponíveis para a operação de carga de descarga, por exemplo máquinas empi-
lhadeiras ou material humano.
• subconjunto de arcos da estrada que podem ser percorridos pelos veículos;
• custo associado pela utilização do veículo que podem ser por unidade de distância, por
unidade de tempo, por rota, etc.
Os operadores dos veículos devem satisfazer várias condições ajustadas por contratos sindicais
ou normas das empresas como período máximo de trabalho diário, número de intervalos durante
o serviço, duração máxima de períodos de condução, horas extras máxima permitida por dia, etc.
Existem também restrições impostas aos condutores associados aos veículos correspondentes.
As vias devem satisfazer várias limitações operacionais que dependem da natureza dos veículos
e dos bens transportados, refletindo na qualidade do serviço executado e as características de cada
cliente. Algumas restrições operacionais são:
• ao longo da rota a demanda de carga do veículo não pode ser maior que a capacidade do
mesmo;
• os clientes atendidos em uma rota pode exigir a entrega, coleta ou ambos de bens;
• os clientes podem ser atendidos somente dentro de sua janela de tempo ou dentro do período
de trabalho dos operadores.
Pode ser imposta uma ordem em que os clientes devem ser atendidos na rota, esse tipo de
restrição determina que um cliente deve ser atendido antes ou depois de um conjunto de clientes
da mesma rota, este tipo de situação é conhecido como o problema da coleta e entrega, em que
em uma mesma rota um mesmo veículo deve coletar mercadorias e entregar em outro cliente.
Outro tipo de restrição de procedência impõem que clientes de diferentes tipos são atendidos na
mesma rota. Neste caso, os clientes tem ordem fixa de atendimento, essa situação aparece para os
PRV com Backhauls, que é um problema de coleta e entrega, mas pela dificuldade de organização
dos produtos nosveículos, esse problema restringe-se as entregas que devem ser feitas antes das
coletas.
A avaliação do custo total do transporte e a verificação das restrições operacionais requerrm
um conhecimento do custo e do tempo de viagem entre cada par de clientes e entre o depósito
e os clientes. Para isso, o grafo da estrada original, que as vezes é muito escasso, é geralmente
transformado em um grafo completo, cujo os vértices do grafo representam os clientes e os depósitos.
Para cada par de vértices 𝑖 e 𝑗 do grafo completo é associado um custo 𝑐𝑖𝑗 ao arco (𝑖, 𝑗) do
caminho mínimo que liga o vértice 𝑖 ao vértice 𝑗. O tempo de percurso 𝑡𝑖𝑗 é associado ao arco
(𝑖, 𝑗) do grafo completo que representa a soma de todos o tempos do caminho mais curto que liga
o vértice 𝑖 ao vértice 𝑗, ou seja, consideramos um grafo completo em vez de considerar o grafo
original da estrada, que pode ser um grafo direcionado ou não, dependendo das matrizes de custo
e tempo de viagem correspondentes que podem ser assimétricas ou simétricas respectivamente.
19
Vários objetivos para os Problemas de Roteamento de Veículos podem ser considerados, alguns
deles são:
• minimizar o custo total do transporte, dependendo da distância ou tempo total da rota e
custos fixos associados aos veículos e seus operadores correspondentes;
• minimizar o número de veículos ou operadores para atender todos os clientes;
• balanceamento das rotas para o tempo de viagem e carregamento dos veículos;
• minimizar as punições relativas aos clientes não atendidos ou atendidos parcialmente.
É possível ainda considerar uma combinação desses objetivos.
Em algumas aplicações os veículos podem operar em mais de uma rota e por um tempo maior,
onde alguns percursos podem durar mais de um dia. Algumas vezes temos que levar em con-
sideração versões estocásticas do problema que dependem de tempos dinâmicos, ou seja, alguns
problemas a priori há apenas um conhecimento parcial de demandas dos clientes, dos custos e do
tempo total de viagem. Já em alguns casos, não há nenhum conhecimento associados aos arcos
das redes de estradas.
2.1 Alguns problemas de roteamento e seus modelos ma-
temáticos
Nesta seção apresentaremos alguns tipos de PRV encontrados na literatura e esboçaremos seu
modelo matemático de modo mais geral.
2.1.1 O problema de roteamento de veículos capacitado PRVC
Em um Problema de Roteamento de Veículos Capacitado (PRVC) todas as entregas e demandas
dos clientes são determinísticas (conhecidas antecipadamente) e não podem ser divididas, sendo
todos os veículos são iguais e existe apenas uma restrição de capacidade. O objetivo é minimizar
o custo total para atender todos os clientes.
Semelhante ao apresentado em Toth e Vigo [49], podemos descrever um PRVC como um pro-
blema teórico da seguinte maneira. Seja 𝐺 = (𝑉,𝐴) um grafo completo, com 𝑉 = {0, . . . , 𝑛} o
conjunto de todos os vértices e 𝐴 o conjunto arcos. Os vértices 𝑖 = 1, . . . , 𝑛, correspondem a todos
os clientes e o vértice 0 representa o depósito. Algumas vezes o depósito também representado
pelo vértice 𝑛+ 1.
O custo de transporte de um vértice 𝑖 ao vértice 𝑗 para todo (𝑖, 𝑗) ∈ 𝐴 é representado pela
constante não negativa 𝑐𝑖𝑗. Geralmente não é permitido um laço no arco (𝑖, 𝑖), então tomamos
𝑐𝑖𝑖 = +∞ para todo 𝑖 ∈ 𝑉 . Se 𝐺 é um grafo direcionado então a matriz de custo 𝐶 é assimétrica
e o problema correspondente é chamado de Problema de Roteamento de Veículos Capacitado
Assimétrico (PRVCAS), caso contrário, 𝑐𝑖𝑗 = 𝑐𝑗𝑖 para todo (𝑖, 𝑗) ∈ 𝐴, o problema é chamado de
Problema de Roteamento de Veículos Capacitado Simétrico (PRVCS).
20
Na maioria dos casos a matriz que representa o custo satisfaz a desigualdade triangular,
𝑐𝑖𝑘 + 𝑐𝑘𝑗 ≥ 𝑐𝑖𝑗 ∀ 𝑖, 𝑗, 𝑘 ∈ 𝑉. (2.1.1)
Note que quando o custo de cada arco do grafo é igual ao custo do caminho mínimo entre suas
extremidades, a matriz custo correspondente satisfaz a desigualdade triangular.
Em algumas aplicações os vértices são associados as coordenadas do plano e o custo 𝑐𝑖𝑗 para
cada arco (𝑖, 𝑗) ∈ 𝐴 é definido como a distância Euclidiana entre dois pontos correspondentes
aos vértices 𝑖 e 𝑗. Neste caso a matriz é simétrica, satisfaz a desigualdade triangular e resulta
em um conjuntos de problemas chamados de Problemas de Roteamento de Veículos Capacitados
Euclidianos (PRVCE).
Associamos a cada cliente 𝑖 (1, . . . , 𝑛) uma demanda 𝑑𝑖 não negativa e tomamos 𝑑0 = 0. Dado
um conjunto de vértices 𝑆 ⊆ 𝑉 , denotamos por:
𝑑 (𝑆) =
∑︁
𝑖∈𝑆
𝑑𝑖
a soma de todas as demandas dos clientes 𝑖 ∈ 𝑆. Consideremos que está associado ao depósito
um conjunto 𝐾 de veículos idênticos de capacidade 𝐶, assumimos também que a demanda 𝑑𝑖 ≤ 𝐶
para cada 𝑖 = 1, . . . , 𝑛, na qual cada veículo pode executar no máximo uma rota.
O PRVC baseia-se em encontrar um número 𝐾 de rotas, cada uma para cada veículo com o
objetivo de minimizar o custo total do transporte e atender as seguintes restrições:
• cada rota deve iniciar e terminar no depósito;
• cada cliente é visitado exatamente uma vez por apenas um veículo;
• a soma da demanda de uma rota não pode ser maior que a capacidade do veículo.
2.1.1.1 Formulação matemática do PRVC
A formulação matemática dada abaixo para PRVC, que mais tarde foi adaptado para PRVCS
utiliza 𝑂(𝑛2) variáveis binárias:
𝑥𝑖𝑗𝑘 =
⎧⎨⎩1 se o veículo 𝑘 percorre a aresta (𝑖, 𝑗)0 caso contrário
em que 𝑖, 𝑗 ∈ {0, . . . , 𝑛}, 𝑖 ̸= 𝑗 e 𝑘 ∈ {1, . . . , 𝐾}.
min
𝑛∑︁
𝑖=0
𝑛∑︁
𝑗=0
𝐾∑︁
𝑘=1
𝑐𝑖𝑗𝑥𝑖𝑗𝑘 (2.1.2)
sujeito a
𝐾∑︁
𝑘=1
𝑛∑︁
𝑗=1
𝑥0𝑗𝑘 = 𝐾 (2.1.3)
𝑛∑︁
𝑗=1
𝑥0𝑗𝑘 =
𝑛∑︁
𝑗=1
𝑥𝑗0𝑘 = 1, ∀ 𝑘 = 1, . . . , 𝐾 (2.1.4)
21
𝐾∑︁
𝑘=1
𝑛∑︁
𝑗=0
𝑥𝑖𝑗𝑘 = 1, ∀ 𝑖 = 1, . . . , 𝑛 (2.1.5)
𝑛∑︁
𝑗=0
𝑥𝑖𝑗𝑘 =
𝑛∑︁
𝑗=0
𝑥𝑗𝑖𝑘 ∀ 𝑘 = 1, . . . , 𝐾, ∀ 𝑖 = 1, . . . , 𝑛 (2.1.6)
𝐾∑︁
𝑘=1
∑︁
𝑖∈𝑆
∑︁
𝑗∈𝑆
𝑥𝑖𝑗𝑘 ≤ |𝑆| − 𝑟 (𝑆) , ∀ 𝑆 ⊆ 𝑉 ∖{0} , |𝑆| ≥ 2 (2.1.7)
𝑛∑︁
𝑖=1
𝑑𝑖
𝑛∑︁
𝑗=0
𝑥𝑖𝑗𝑘 ≤ 𝐶, ∀ 𝑖 ̸= 𝑗 e ∀ 𝑘 = 1, . . . , 𝐾 (2.1.8)
𝑥𝑖𝑗𝑘 ∈ {0, 1} , ∀ 𝑖 = 0, . . . , 𝑛, ∀ 𝑗 = 0, . . . 𝑛, ∀ 𝑘 = 1, . . . , 𝐾 (2.1.9)
A restrição (2.1.3) determina que a quantidade exata de veículos que deixa do depósito seja 𝐾,
já as restrições (2.1.4) que todas as rotas se iniciam e terminam no depósito, as restrições (2.1.5)
e (2.1.6) determinam que existe apenas uma única rota para um veículo 𝑘 percorrer o arco (𝑖, 𝑗).
A restrição (2.1.7) é também chamada de restrição de eliminação de sub-rotas, na qual impõe ao
modelo que as rotas que não se inicie e termine no depósito não estejam na solução, nessa restrição,
temos 𝑟 (𝑆) que representa o número mínimo de veículos necessários para que todos os clientes em
𝑆 sejam atendidos. Em (2.1.8) temos a restrição da capacidade dos veículos explicitamente, ou
seja, que a soma de todas as demandas do percurso para cada veículo 𝑘 não pode ser superior que
sua capacidade 𝐶 e por último temos as restrições de integralidade do problema em 𝑥𝑖𝑗𝑘 ∈ {0, 1}.
2.1.2 Problemas de roteamento de veículos com janela de tempo PRVJT
O PRVJT é uma extensão do PRVC em que cada cliente 𝑖 é associado ao intervalo de tempo
[𝑒𝑖, 𝑙𝑖] onde ele deve ser atendido, denominado de janela de tempo. Para cada cliente 𝑖 é considerado
um tempo de viagem 𝑡𝑖𝑗 para cada arco (𝑖, 𝑗) ∈ 𝐴 e um tempo adicional de serviço 𝑠𝑖 (carga e
descarga ou coleta e entrega). Sendo que o serviço de cada cliente deve iniciar dentro de sua
janela de tempo associada e o veículo deve permanecer no cliente durante todo o tempo de serviço
𝑠𝑖. Além disso, na maioria dos casos em que há antecipação de chegada o veículo é autorizado a
esperar um tempo 𝑎𝑖 até que o serviço possa ser iniciado.
Normalmente as matrizes de custo e tempo de viagem são coincidentes e assume-se que todos
os veículosdeixam o depósito no instante 0. Note que a restrição de janela de tempo impõe
implicitamente uma orientação para cada rota mesmo que as matrizes iniciais sejam simétricas.
Portanto, normalmente um PRVJT é modelado como um problema assimétrico.
Um PRVJT consiste em encontrar um conjunto com exatamente 𝐾 rotas minimizando o custo
total tal que:
• cada rota deve iniciar e terminar do depósito;
• cada cliente é visitado uma única vez;
• a soma das demandas dos cliente da rota não pode ser maior que a capacidade 𝐶 dos veículos;
• para cada cliente 𝑖 o serviço se inicia em uma janela de tempo [𝑒𝑖, 𝑙𝑖] e o veículo fica parado
no cliente por um tempo de serviço 𝑠𝑖.
22
2.1.2.1 Formulação matemática de um PRVJT
A formulação matemática de um PRVJT trabalha com 𝑂 (𝑛2) variáveis binárias e 𝑛 variáveis
reais. Como no PRVC a variável binária 𝑥𝑖𝑗𝑘, representa se um veículo 𝑘 percorre o arco (𝑖, 𝑗) e a
variável real 𝑏𝑖, 𝑖 = 1, . . . , 𝑛 representa o instante inicial do atendimento de um cliente 𝑖.
Segue abaixo a formulação do modelo matemático para um PRVJT:
min
𝑛∑︁
𝑖=0
𝑛∑︁
𝑗=0
𝐾∑︁
𝑘=1
𝑐𝑖𝑗𝑥𝑖𝑗𝑘 𝑖 ̸= 𝑗 (2.1.10)
sujeito a
𝐾∑︁
𝑘=1
𝑛∑︁
𝑗=1
𝑥0𝑗𝑘 = 𝐾 (2.1.11)
𝑛∑︁
𝑗=1
𝑥0𝑗𝑘 =
𝑛∑︁
𝑗=1
𝑥𝑗0𝑘 = 1, ∀ 𝑘 = 1, . . . , 𝐾 (2.1.12)
𝐾∑︁
𝑘=1
𝑛∑︁
𝑗=0
𝑥𝑖𝑗𝑘 = 1, ∀ 𝑖 = 1, . . . , 𝑛 (2.1.13)
𝑛∑︁
𝑗=0
𝑥𝑖𝑗𝑘 =
𝑛∑︁
𝑗=0
𝑥𝑗𝑖𝑘 ∀ 𝑘 = 1, . . . , 𝐾, ∀ 𝑖 = 1, . . . , 𝑛 (2.1.14)
𝐾∑︁
𝑘=1
∑︁
𝑖∈𝑆
∑︁
𝑗∈𝑆
𝑥𝑖𝑗𝑘 ≤ |𝑆| − 𝑟 (𝑆) , ∀ 𝑆 ⊆ 𝑉 ∖{0} , |𝑆| ≥ 2 (2.1.15)
𝑛∑︁
𝑖=1
𝑑𝑖
𝑛∑︁
𝑗=0
𝑥𝑖𝑗𝑘 ≤ 𝐶, 𝑖 ̸= 𝑗 e ∀ 𝑘 = 1, . . . , 𝐾 (2.1.16)
𝐾∑︁
𝑘=1
𝑛∑︁
𝑖=0
𝑥𝑖𝑗𝑘 (𝑏𝑖 + 𝑠𝑖 + 𝑡𝑖𝑗) ≤ 𝑏𝑗, 𝑖 ̸= 𝑗, ∀ 𝑗 = 1, . . . , 𝑛 (2.1.17)
𝑒𝑖 ≤ 𝑏𝑖 ≤ 𝑙𝑖 ∀ 𝑖 = 0, . . . , 𝑛 (2.1.18)
𝑥𝑖𝑗𝑘 ∈ {0, 1} , ∀ 𝑖 = 1, . . . , 𝑛, ∀ 𝑗 = 1, . . . 𝑛, ∀ 𝑘 = 1, . . . , 𝐾 (2.1.19)
Observe que a função objetivo (2.1.10) e as restrições (2.1.11)-(2.1.16) são as mesmas do PRVC.
A restrição (2.1.17) representa que a soma do instante da janela de tempo do cliente 𝑖 mais o tempo
de serviço 𝑠𝑖 que o veículo fica parado no vértice 𝑖 para coleta ou entrega das mercadorias somado
com o tempo 𝑡𝑖𝑗 de percurso entre os vértices 𝑖 e 𝑗 não pode ser maior que o inicio da janela de
tempo do cliente localizado no vértice 𝑗. E por fim a restrição (2.1.18) restringe que o atendimento
do cliente 𝑖 seja feito somente em sua janela de tempo.
2.1.3 Problema de roteamento de veículos com backhauls PRVB
O PRVB ou como definido por Vieira [50] Problema de Roteamento de Veículos com Prioridade
de Entrega (PRVPE) é uma extensão do PRVC em que o conjunto de clientes é particionado em dois
subconjuntos. O primeiro subconjunto contém todos os clientes que é preciso entregar os produtos,
em inglês são chamados de Linehaul customers contendo 𝑛 elementos que vamos representar por
23
𝐿. O segundo subconjunto contém todos os clientes que desejam enviar produtos ao depósito, em
inglês chamamos de Backhaul customers contendo 𝑚 elementos que vamos representar por 𝐵, na
qual há uma restrição de prioridade de atendimento a todos os clientes que tem produtos a receber.
Os clientes são numerados da seguinte maneira 𝐿 = {1, . . . , 𝑛} e 𝐵 = {𝑛+ 1, . . . , 𝑛+𝑚}.
Sempre que uma rota tiver clientes Linehaul e Backhaul todos os clientes Linehaul serão os
primeiros a serem atendidos. Para todos os clientes é atribuído uma demanda não negativa 𝑑𝑖
para ser coletado ou entregue dependendo de seu tipo e para o depósito é associado uma demanda
fictícia 𝑑0 = 0. A matriz custo de um PRVB é assimétrica, consiste em determinar o número exato
𝐾 de rotas com o objetivo de minimizar o custo de transporte atendendo as seguintes restrições:
• cada rota deve iniciar e terminar do depósito;
• cada cliente em uma rota é visitado uma única vez;
• a demanda total dos clientes visitados na rota para linehaul e backhaul não pode exercer
separadamente a capacidade 𝐶 do veículo;
• cada rota, todos os clientes linehaul são atendidos antes de todos clientes backhaul se houver.
2.1.3.1 Formulação matemática de um PRVB
O modelo proposto por Toth e Vigo [49] é baseado em uma reformulação do problema, na
qual é considerado como um problema assimétrico, portanto também é válido para um PRVBA.
Inicialmente vamos supor que são permitidas rotas para um único cliente linehaul.
Agora definimos 𝐿0 := 𝐿 ∪ {0} e 𝐵0 := 𝐵 ∪ {0}, considere 𝐺 =
(︁
𝑉 ,𝐴
)︁
um grafo direcionado
obtido de 𝐺 definindo 𝑉 = 𝑉 e 𝐴 = 𝐴1 ∪ 𝐴2 ∪ 𝐴3, em que:
𝐴1 := {(𝑖, 𝑗) ∈ 𝐴 : 𝑖 ∈ 𝐿0, 𝑗 ∈ 𝐿} ,
𝐴2 := {(𝑖, 𝑗) ∈ 𝐴 : 𝑖 ∈ 𝐵, 𝑗 ∈ 𝐵0} ,
𝐴3 := {(𝑖, 𝑗) ∈ 𝐴 : 𝑖 ∈ 𝐿, 𝑗 ∈ 𝐵0} .
Aqui particionamos o conjunto de arcos 𝐴 em três subconjuntos disjuntos. O Primeiro subcon-
junto 𝐴1 contém todos os arcos que ligam o depósito com os clientes linehaul e todos os vértices de
clientes linehaul. O segundo subconjunto 𝐴2 contém todos os arcos que ligam o depósito com os
clientes backhaul e todos os vértices de clientes backhaul, finalmente, 𝐴3 contém todos os arcos que
conectam os clientes linehaul com os clientes backhaul ou com o depósito. Esse último subconjunto
é denominado de arcos de interface. Observe que 𝐴 não contém arcos que não pertencem a uma
solução factível do problema, ou seja, não há arcos que partam dos clientes backhaul até os clientes
linehaul ou que partam do depósito aos clientes backhaul, pelo motivo da restrição de procedência
de que todos os clientes linehaul devem ser atendidos antes dos clientes backhaul. Note que 𝐴 é
um subconjunto próprio do conjunto 𝐴, para para arco (𝑖, 𝑗) ∈ 𝐴 temos um custo 𝑐𝑖𝑗 que é igual
ao custo de cada arco (𝑖, 𝑗) ∈ 𝐴 correspondente.
Seja ℒ (respectivamente ℬ) a família de todos os subconjuntos que contém os vértices de 𝐿
(respectivamente B) e ℱ = ℒ ∪ ℬ. Para cada 𝑆 ∈ ℱ , seja 𝑟 (𝑆) o número mínimo necessário para
24
atender todos os clientes em 𝑆. Para cada 𝑖 ∈ 𝑉 é definido △+𝑖 =
{︁
𝑗 : (𝑖, 𝑗) ∈ 𝐴
}︁
e △+𝑗 ={︁
𝑖 : (𝑗, 𝑖) ∈ 𝐴
}︁
, assim, a formulação do modelo de programação linear inteira é dado abaixo:
min
∑︁
(𝑖,𝑗)∈𝐴
𝑐𝑖𝑗𝑥𝑖𝑗 (2.1.20)
sujeito a:
∑︁
𝑖∈△−𝑗
𝑥𝑖𝑗 = 1 ∀ 𝑗 ∈ 𝑉 ∖{0} (2.1.21)
∑︁
𝑗∈△+𝑖
𝑥𝑖𝑗 = 1 ∀ 𝑖 ∈ 𝑉 ∖{0} (2.1.22)
∑︁
𝑖∈△−0
𝑥𝑖0 = 𝐾 (2.1.23)
∑︁
𝑗∈△+0
𝑥0𝑗 = 𝐾 (2.1.24)
∑︁
𝑗∈𝑆
∑︁
𝑖∈△−𝑗 ∖𝑆
𝑥𝑖𝑗 ≥ 𝑟 (𝑆) ∀ 𝑆 ∈ ℱ , (2.1.25)
∑︁
𝑖∈𝑆
∑︁
𝑗∈△+𝑖 ∖𝑆
𝑥𝑖𝑗 ≥ 𝑟 (𝑆) ∀ 𝑆 ∈ ℱ , (2.1.26)
𝑥𝑖𝑗 ∈ {0, 1} ∀ (𝑖, 𝑗) ∈ 𝐴 (2.1.27)
Seja 𝑥𝑖𝑗 = 1 se, e somente se, o arco (𝑖, 𝑗) pertence a solução ótima. As equações (2.1.21),
(2.1.23) e (2.1.22), (2.1.24) impõe respectivamente restrições de entrada e saída aos clientes e ao
depósito. O chamado Restrição de Corte de Capacidade (RCC) de (2.1.25) e (2.1.26) a continuidade
entre as rotas e que a capacidade dos veículos não seja violada. Note que as restrições (2.1.21)-
(2.1.24) implicam que o lado esquerdo das equações (2.1.25) e (2.1.26) para qualquer conjunto 𝑆
dado, sejam iguais, isto é, que o número de arcos que entram no conjunto 𝑆 é igual ao número de
arcos que saem.
E por último note que a familia de restrições (2.1.25) e (2.1.26) tem cardinalidade crescendo
exponencialmente com max {𝑛,𝑚}, mesmo com a forma relaxada definida em (2.1.20)-(2.1.26) e
0 ≤ 𝑥𝑖𝑗 ≤ 1, (𝑖, 𝑗) ∈ 𝐴 (2.1.28)
não há solução direta, mesmo para problemas de tamanhos moderados.
2.1.4 Problema de roteamento de veículos com coleta e entrega PRVCE
Na versão básica PRVCE cada cliente 𝑖 é associado a duas quantidades 𝑑𝑖 e 𝑝𝑖, representando
a demanda homogênea de mercadorias que serão entregues e coletados em cada cliente 𝑖. As vezes
é usado para para cada cliente 𝑖 uma quantidade de demanda 𝑑𝑗 = 𝑑𝑖 − 𝑝𝑖 indicando a demanda
líquida entre das demandas de entrega e coleta