Problemacaixeiroviajante-Carvalho-2018

Prévia do material em texto

Universidade Federal do Rio Grande do Norte
Centro de Ciências Exatas e da Terra
Departmento de Informática e Matemática Aplicada
Programa de Pós-Graduação em Sistemas e Computação
Mestrado Acadêmico em Sistemas e Computação
O Problema do Caixeiro Viajante com
Múltiplos Passageiros e Quota
Allan Vilar de Carvalho
Natal-RN
Dezembro de 2018
Allan Vilar de Carvalho
O Problema do Caixeiro Viajante com Múltiplos
Passageiros e Quota
Dissertação de Mestrado apresentada ao
Programa de Pós-Graduação em Sistemas
e Computação do Departamento de Infor-
mática e Matemática Aplicada da Universi-
dade Federal do Rio Grande do Norte como
requisito parcial para a obtenção do grau
de Mestre em Sistemas e Computação.
Linha de pesquisa:
Algoritmos Experimentais
Orientador
Prof. Dr. Marco César Goldbarg
PPgSC – Programa de Pós-Graduação em Sistemas e Computação
DIMAp – Departamento de Informática e Matemática Aplicada
CCET – Centro de Ciências Exatas e da Terra
UFRN – Universidade Federal do Rio Grande do Norte
Natal-RN
Dezembro de 2018
Carvalho, Allan Vilar de.
 O problema do caixeiro viajante com múltiplos passageiros e
quota / Allan Vilar de Carvalho. - 2018.
 262f.: il.
 Dissertação (Mestrado) - Universidade Federal do Rio Grande
do Norte, Centro de Ciências Exatas e da Terra, Programa de Pós-
Graduação em Sistemas e Computação. Natal, 2018.
 Orientador: Marco César Goldbarg.
 1. Algoritmos - Dissertação. 2. Caixeiro viajante -
Dissertação. 3. Problemas de Ridesharing - Dissertação. 4. Meta-
heurísticas - Dissertação. I. Goldbarg, Marco César. II. Título.
RN/UF/CCET CDU 004.021
Universidade Federal do Rio Grande do Norte - UFRN
Sistema de Bibliotecas - SISBI
Catalogação de Publicação na Fonte. UFRN - Biblioteca Setorial Prof. Ronaldo Xavier de Arruda - CCET
Elaborado por Joseneide Ferreira Dantas - CRB-15/324
Agradecimentos
Primeiramente agradeço a Deus por ser meu guia e protetor.
Agradeço também aos meus pais Adão Vilar de Carvalho e Acioneide Torres Vilar
de Carvalho por todo o amor e carinho.
Agradeço as minhas irmãs Arilania Vilar de Carvalho e Alânia Vilar de Carvalho
que sempre estão torcendo pelo meu sucesso.
Agradeço especialmente a Marco Cesar Goldbarg por toda orientação, pelo apren-
dizado e pelo empenho na construção deste trabalho.
Agradeço a Elizabeth Ferreira Gouveia Goldbarg, Sílvia Maria Diniz Monteiro Maia
e a Matheus da Silva Menezes por toda contribuição dada a este trabalho.
Agradeço a minha noiva Fiderlane Islane Gomes dos Santos pela ajuda dada em
momentos difíceis da minha vida de mestrando.
Por fim, agradeço aos meus colegas do mestrado por toda ajuda.
A melhor maneira de prever o futuro é inventá-lo.
Alan Kay
O Problema do Caixeiro Viajante com Múltiplos
Passageiros e Quota
Autor: Allan Vilar de Carvalho
Orientador(a): Prof. Dr. Marco César Goldbarg
Resumo
O presente trabalho apresenta o Problema do Caixeiro Viajante com Múltiplos Passa-
geiros e Quota, variante do Problema do Caixeiro Viajante com Quota. O problema
consiste em minimizar os custos de um caixeiro viajante que deve coletar uma cota
mínima de bônus nas localidades do problema, considerando a possibilidade de rateio
das despesas de rota com eventuais passageiros embarcados no veículo do caixeiro. Os
passageiros, se embarcados, devem ser transportados obrigatoriamente até seus desti-
nos previamente conhecidos. Os passageiros participam do rateio dos custos da rota
nos trechos em que estiverem embarcados. O trabalho propõe e valida um modelo de
Programação Matemática Linear para formalizar o problema. São propostos também
um banco de instâncias e métodos heurísticos para a solução do problema. Experimen-
tos computacionais validam os métodos propostos através da solução das instâncias do
banco proposto. Desenvolve-se um experimento computacional para obter conclusões
sobre a eficiência e eficácia dos métodos propostos.
Palavras-chave: Caixeiro Viajante, Problemas de Ridesharing, Meta-heurísticas.
The Traveling Salesman Problem with Multiple
Passengers and Quota
Author: Allan Vilar de Carvalho
Supervisor: Prof. Dr. Marco César Goldbarg
Abstract
The present work presents the Traveling Salesman Problem with Multiple Passengers
and Quota, variant of the Traveling Salesman Problem with Quota. The problem is to
minimize the costs of a salesman who must collect a minimum quota of bonuses in the
localities of the problem, considering the possibility of apportionment of expenses for
any passengers on the route with embedded vehicle traveling. Passengers, if shipped,
must be transported obligatorily to their destinations previously known. Passengers
participate in the apportionment of the costs of the route in excerpts in which you
sail. The paper proposes and validates a Linear Mathematical Programming model to
formalize the problem. Are proposed also a bank of instances and heuristics for sol-
ving the problem. Computational experiments validate the proposed methods through
the solution of the instances of the proposed bank. Developing a computational expe-
riment to obtain conclusions about the efficiency and effectiveness of the proposed
methods.
Keywords: Travelling Salesman, Ridesharing Problems, Meta-heuristics.
Lista de figuras
1 Exemplo de operação do BuscaLocalEH . . . . . . . . . . . . . . . . . . p. 56
2 Exemplos de caminhos PR . . . . . . . . . . . . . . . . . . . . . . . . . p. 65
3 Exemplos de operações das vizinhanças . . . . . . . . . . . . . . . . . p. 70
4 Conteúdo da instância a-10-21-4-1 . . . . . . . . . . . . . . . . . . . . p. 252
Lista de tabelas
1 Configuração do algoritmo G-LK para as instâncias simétricas . . . . p. 91
2 Configuração do algoritmo G-LK para as instâncias assimétricas . . . p. 91
3 Configuração do algoritmo G-PR . . . . . . . . . . . . . . . . . . . . . p. 91
4 Configuração do algoritmo G-VNDP . . . . . . . . . . . . . . . . . . . p. 91
5 Configuração do algoritmo ACO-OR . . . . . . . . . . . . . . . . . . . p. 91
6 Configuração do algoritmo ACO-AL . . . . . . . . . . . . . . . . . . . . p. 92
7 Configuração do algoritmo ACO-ORVNDP . . . . . . . . . . . . . . . . p. 92
8 Configuração do algoritmo ACO-ALVNDP . . . . . . . . . . . . . . . . p. 92
9 Configuração do algoritmo ACO-GALVNDP . . . . . . . . . . . . . . . p. 93
10 Configuração do algoritmo BA . . . . . . . . . . . . . . . . . . . . . . . p. 93
11 Quantidade de melhores soluções encontradas pelos algoritmos meta-
heurísticos nas instâncias simétricas . . . . . . . . . . . . . . . . . . . p. 102
12 Comparação das médias de solução dos algoritmos meta-heurísticos
por grupo de instâncias simétricas (vitórias x derrotas) . . . . . . . . . p. 103
13 Comparação das soluções mínimas dos algoritmos meta-heurísticos
por grupo de instâncias simétricas (vitórias x derrotas) . . . . . . . . . p. 105
14 Comparação das médias dos tempos médios de execução dos algo-
ritmos meta-heurísticos nas instâncias simétricas, por quantidade de
localidade da instância . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 107
15 Quantidade de maior desvio e quantidade de menor desvio dos algo-
ritmos meta-heurísticos nas instâncias simétricas . . . . . . . . . . . . p. 108
16 p-valores do teste de Friedman realizado utilizando as médias de so-
lução dos algoritmos meta-heurísticos nas instâncias simétricas . . . . p. 109
17 p-valores do teste de Friedman realizado utilizando as soluções míni-
mas dos algoritmos meta-heurísticos nas instâncias simétricas . . . . . p. 109
18 p-valores do teste de Conover realizado utilizando as médias de so-
lução dos algoritmos meta-heurísticos nas instâncias simétricas com
quantidade de localidade 10 . . . . . . . . . . . . . . . . . . . . . . . . p. 111
19 p-valores do teste de Conover realizado utilizando as médias de so-
lução dos algoritmos meta-heurísticos nas instâncias simétricas com
quantidade de localidade 20 . . . . . . . . . . . . .. . . . . . . . . . . p. 111
20 p-valores do teste de Conover realizado utilizando as médias de so-
lução dos algoritmos meta-heurísticos nas instâncias simétricas com
quantidade de localidade 30 . . . . . . . . . . . . . . . . . . . . . . . . p. 112
21 p-valores do teste de Conover realizado utilizando as médias de so-
lução dos algoritmos meta-heurísticos nas instâncias simétricas com
quantidade de localidade 40 . . . . . . . . . . . . . . . . . . . . . . . . p. 112
22 p-valores do teste de Conover realizado utilizando as médias de so-
lução dos algoritmos meta-heurísticos nas instâncias simétricas com
quantidade de localidade 50 . . . . . . . . . . . . . . . . . . . . . . . . p. 113
23 p-valores do teste de Conover realizado utilizando as médias de so-
lução dos algoritmos meta-heurísticos nas instâncias simétricas com
quantidade de localidade 100 . . . . . . . . . . . . . . . . . . . . . . . p. 113
24 p-valores do teste de Conover realizado utilizando as soluções mí-
nimas dos algoritmos meta-heurísticos nas instâncias simétricas com
quantidade de localidade 10 . . . . . . . . . . . . . . . . . . . . . . . . p. 115
25 p-valores do teste de Conover realizado utilizando as soluções mí-
nimas dos algoritmos meta-heurísticos nas instâncias simétricas com
quantidade de localidade 20 . . . . . . . . . . . . . . . . . . . . . . . . p. 115
26 p-valores do teste de Conover realizado utilizando as soluções mí-
nimas dos algoritmos meta-heurísticos nas instâncias simétricas com
quantidade de localidade 30 . . . . . . . . . . . . . . . . . . . . . . . . p. 116
27 p-valores do teste de Conover realizado utilizando as soluções mí-
nimas dos algoritmos meta-heurísticos nas instâncias simétricas com
quantidade de localidade 40 . . . . . . . . . . . . . . . . . . . . . . . . p. 116
28 p-valores do teste de Conover realizado utilizando as soluções mí-
nimas dos algoritmos meta-heurísticos nas instâncias simétricas com
quantidade de localidade 50 . . . . . . . . . . . . . . . . . . . . . . . . p. 117
29 p-valores do teste de Conover realizado utilizando as soluções mí-
nimas dos algoritmos meta-heurísticos nas instâncias simétricas com
quantidade de localidade 100 . . . . . . . . . . . . . . . . . . . . . . . p. 117
30 Quantidade de melhores soluções encontradas pelos algoritmos meta-
heurísticos nas instâncias assimétricas . . . . . . . . . . . . . . . . . . p. 119
31 Comparação das médias de solução dos algoritmos meta-heurísticos
por grupo de instâncias assimétricas (vitórias x derrotas) . . . . . . . . p. 120
32 Comparação das soluções mínimas dos algoritmos meta-heurísticos
por grupo de instâncias assimétricas (vitórias x derrotas) . . . . . . . . p. 122
33 Comparação das médias dos tempos médios de execução dos algorit-
mos meta-heurísticos nas instâncias assimétricas, por quantidade de
localidade da instância . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 124
34 Quantidade de maior desvio e quantidade de menor desvio dos algo-
ritmos meta-heurísticos nas instâncias assimétricas . . . . . . . . . . . p. 125
35 p-valores do teste de Friedman realizado utilizando as médias de so-
lução dos algoritmos meta-heurísticos nas instâncias assimétricas . . . p. 126
36 p-valores do teste de Friedman realizado utilizando as soluções míni-
mas dos algoritmos meta-heurísticos nas instâncias assimétricas . . . p. 126
37 p-valores do teste de Conover realizado utilizando as médias de solu-
ção dos algoritmos meta-heurísticos nas instâncias assimétricas com
quantidade de localidade 10 . . . . . . . . . . . . . . . . . . . . . . . . p. 127
38 p-valores do teste de Conover realizado utilizando as médias de solu-
ção dos algoritmos meta-heurísticos nas instâncias assimétricas com
quantidade de localidade 20 . . . . . . . . . . . . . . . . . . . . . . . . p. 127
39 p-valores do teste de Conover realizado utilizando as médias de solu-
ção dos algoritmos meta-heurísticos nas instâncias assimétricas com
quantidade de localidade 30 . . . . . . . . . . . . . . . . . . . . . . . . p. 128
40 p-valores do teste de Conover realizado utilizando as médias de solu-
ção dos algoritmos meta-heurísticos nas instâncias assimétricas com
quantidade de localidade 40 . . . . . . . . . . . . . . . . . . . . . . . . p. 128
41 p-valores do teste de Conover realizado utilizando as médias de solu-
ção dos algoritmos meta-heurísticos nas instâncias assimétricas com
quantidade de localidade 50 . . . . . . . . . . . . . . . . . . . . . . . . p. 129
42 p-valores do teste de Conover realizado utilizando as médias de solu-
ção dos algoritmos meta-heurísticos nas instâncias assimétricas com
quantidade de localidade 100 . . . . . . . . . . . . . . . . . . . . . . . p. 129
43 p-valores do teste de Conover realizado utilizando as soluções míni-
mas dos algoritmos meta-heurísticos nas instâncias assimétricas com
quantidade de localidade 10 . . . . . . . . . . . . . . . . . . . . . . . . p. 131
44 p-valores do teste de Conover realizado utilizando as soluções míni-
mas dos algoritmos meta-heurísticos nas instâncias assimétricas com
quantidade de localidade 20 . . . . . . . . . . . . . . . . . . . . . . . . p. 131
45 p-valores do teste de Conover realizado utilizando as soluções míni-
mas dos algoritmos meta-heurísticos nas instâncias assimétricas com
quantidade de localidade 30 . . . . . . . . . . . . . . . . . . . . . . . . p. 132
46 p-valores do teste de Conover realizado utilizando as soluções míni-
mas dos algoritmos meta-heurísticos nas instâncias assimétricas com
quantidade de localidade 40 . . . . . . . . . . . . . . . . . . . . . . . . p. 132
47 p-valores do teste de Conover realizado utilizando as soluções míni-
mas dos algoritmos meta-heurísticos nas instâncias assimétricas com
quantidade de localidade 50 . . . . . . . . . . . . . . . . . . . . . . . . p. 133
48 p-valores do teste de Conover realizado utilizando as soluções míni-
mas dos algoritmos meta-heurísticos nas instâncias assimétricas com
quantidade de localidade 100 . . . . . . . . . . . . . . . . . . . . . . . p. 133
49 Resultados do Solver e do algoritmo heurístico para o conjunto de ins-
tâncias com demanda 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 143
50 Resultados do Solver e do algoritmo heurístico para o conjunto de ins-
tâncias com demanda 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 144
51 Resultados do algoritmo G-LK para o conjunto de instâncias com de-
manda 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 145
52 Resultados do algoritmo G-LK para o conjunto de instâncias com de-
manda 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 150
53 Resultados do algoritmo G-PR para o conjunto de instâncias com de-
manda 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 155
54 Resultados do algoritmo G-PR para o conjunto de instâncias com de-
manda 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 160
55 Resultados do algoritmo G-VNDP para o conjunto de instâncias com
demanda 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 165
56 Resultados do algoritmo G-VNDP para o conjunto de instâncias com
demanda 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 170
57 Resultados do algoritmo ACO-OR para o conjunto de instâncias com
demanda 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 175
58 Resultados do algoritmo ACO-OR para o conjunto de instâncias com
demanda 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 180
59 Resultados do algoritmo ACO-AL para o conjunto de instâncias com
demanda 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 185
60 Resultados do algoritmo ACO-AL para o conjunto de instâncias com
demanda 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 190
61 Resultados do algoritmo ACO-ORVNDPpara o conjunto de instâncias
com demanda 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 195
62 Resultados do algoritmo ACO-ORVNDP para o conjunto de instâncias
com demanda 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 200
63 Resultados do algoritmo ACO-ALVNDP para o conjunto de instâncias
com demanda 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 205
64 Resultados do algoritmo ACO-ALVNDP para o conjunto de instâncias
com demanda 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 210
65 Resultados do algoritmo ACO-GALVNDP para o conjunto de instân-
cias com demanda 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 215
66 Resultados do algoritmo ACO-GALVNDP para o conjunto de instân-
cias com demanda 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 220
67 Resultados do algoritmo BA para o conjunto de instâncias com de-
manda 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 225
68 Resultados do algoritmo BA para o conjunto de instâncias com de-
manda 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 230
69 Melhores soluções encontradas pelos algoritmos meta-heurísticos para
o conjunto de instâncias com demanda 1 por grupo de instâncias si-
métricas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 235
70 Melhores soluções encontradas pelos algoritmos meta-heurísticos para
o conjunto de instâncias com demanda 2 por grupo de instâncias si-
métricas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 237
71 Desvio percentual dos algoritmos meta-heurísticos por grupo de ins-
tâncias simétricas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 240
72 Melhores soluções encontradas pelos algoritmos meta-heurísticos para
o conjunto de instâncias com demanda 1 por grupo de instâncias as-
simétricas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 243
73 Melhores soluções encontradas pelos algoritmos meta-heurísticos para
o conjunto de instâncias com demanda 2 por grupo de instâncias as-
simétricas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 246
74 Desvio percentual dos algoritmos meta-heurísticos por grupo de ins-
tâncias assimétricas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 248
75 Instâncias assimétricas dos experimentos . . . . . . . . . . . . . . . . . p. 253
76 Instâncias simétricas dos experimentos . . . . . . . . . . . . . . . . . . p. 256
77 Instâncias do irace . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 259
Lista de abreviaturas e siglas
PCV – Problema do Caixeiro Viajante
PCV-Q – Problema do Caixeiro Viajante com Quota
PCV-CP – Problema do Caixeiro Viajante com Coleta de Prêmios
PCV-P – Problema do Caixeiro Viajante com Passageiros
PCV-PQ – Problema do Caixeiro Viajante com Passageiros e Quota
PPL-PRTC – Problema do Passeio Lucrativo com Passageiros e Restrições de Tempo e
Custo
PCV-MPQ – Problema do Caixeiro Viajante com Múltiplos Passageiros e Quota
PCV-PL – Problema do Caixeiro Viajante com Passageiros e Lotação
PEP – Problema do Embarque de Passageiros
GRASP – Greedy Randomized Adaptive Search Procedure
LRC – Lista Restrita de Candidatos
PR – Path-Relinking
EH – Embarque Heurístico
VNS – Variable Neighborhood Search
VNDP – Variable Neighborhood Descending with Perturbation
ACO – Ant Colony Optimization
BA – Bees Algorithm
CA – Construtor Aleatório
BLA – Busca Local Aleatória
Lista de algoritmos
1 EH . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 54
2 BuscaLocalEH . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 55
3 AH . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 59
4 GRASP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 60
5 G-LK . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 62
6 PR . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 64
7 G-PR . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 67
8 VNDP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 68
9 G-VNDP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 71
10 ACO-OR . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 74
11 ACO-AL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 76
12 ACO-ORVNDP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 78
13 ACO-ALVNDP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 80
14 ACO-GALVNDP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 82
15 BA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 84
16 CA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 85
17 BLA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 86
Sumário
1 Introdução p. 20
1.1 Justificativa e Importância . . . . . . . . . . . . . . . . . . . . . . . . . p. 20
1.2 Metodologia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 22
1.3 Objetivos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 22
1.4 Contribuições . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 23
1.5 Organização do trabalho . . . . . . . . . . . . . . . . . . . . . . . . . . p. 24
2 PCV-MPQ p. 25
2.1 Contextualização do PCV-MPQ no estado da arte . . . . . . . . . . . . p. 25
2.1.1 O Problema do Caixeiro Viajante . . . . . . . . . . . . . . . . . p. 25
2.1.1.1 Modelo do PCV . . . . . . . . . . . . . . . . . . . . . . p. 26
2.1.2 O Problema do Caixeiro Viajante com Quota . . . . . . . . . . p. 26
2.1.3 O Problema do Caixeiro Viajante com Passageiros . . . . . . . p. 28
2.1.3.1 Modelo quadrático do PCV-P . . . . . . . . . . . . . . p. 29
2.1.4 O Problema do Caixeiro Viajante com Passageiros e Quota . . p. 30
2.1.4.1 Modelo quadrático do PCV-PQ . . . . . . . . . . . . . p. 32
2.1.5 O Problema do Caixeiro Viajante com Passageiros e Lotação . . p. 33
2.1.5.1 Modelo quadrático do PCV-PL . . . . . . . . . . . . . p. 34
2.1.6 O Problema do Passeio Lucrativo com Passageiros e Restrições
de Tempo e Custo . . . . . . . . . . . . . . . . . . . . . . . . . . p. 36
2.1.6.1 Modelo quadrático do PPL-PRTC . . . . . . . . . . . . p. 38
2.1.7 Conexões do PCV-MPQ com outros problemas de roteamento p. 40
2.1.7.1 Conexões do PCV-MPQ com o Ridesharing . . . . . . p. 40
2.1.7.2 Conexões do PCV-MPQ com o Carpooling . . . . . . p. 44
2.1.7.3 Conexões do PCV-MPQ com o Pickup and Delivery . p. 45
2.2 Descrição do PCV-MPQ . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 47
2.3 Formalização do PCV-MPQ . . . . . . . . . . . . . . . . . . . . . . . . p. 48
2.3.1 Linearização do modelo . . . . . . . . . . . . . . . . . . . . . . p. 48
2.3.1.1 Modelo linear do PCV-MPQ . . . . . . . . . . . . . . . p. 50
2.4 Conceitos do PCV-MPQ . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 52
3 O Problema do Embarque de Passageiros - PEP do PCV-MPQ p. 53
3.1 Subproblema do PCV-MPQ . . . . . . . . . . . . . . . . . . . . . . . . p. 53
3.2 Abordagem de solução do PEP . . . . . . . . . . . . . . . . . . . . . . . p. 53
3.2.1 Método heurístico . . . . . . . . . . . . . . . . . . . . . . . . . . p. 53
3.2.1.1 Busca local EH . . . . . . . . . . . . . . . . . . . . . . p. 54
3.3 Modelo matemático para o PEP . . . . . . . . . . . . . . . . . . . . . . p. 56
4 Abordagens de solução do PCV-MPQ p. 58
4.1 Método heurístico . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 58
4.1.1 Heurística ad hoc - AH . . . . . . . . . . . . . . . . . . . . . . . p. 58
4.2 Métodos meta-heurísticos . . . . . . . . . . . . . . . . . . . . . . . . . p. 59
4.2.1 Greedy Randomized Adaptive Search Procedure- GRASP . . . p. 59
4.2.1.1 GRASP com a heurística LKH . . . . . . . . . . . . . . p. 60
4.2.1.2 GRASP com o Path-Relinking - PR . . . . . . . . . . . p. 63
4.2.1.3 GRASP com o Variable Neighborhood Descending with
Perturbation - VNDP . . . . . . . . . . . . . . . . . . . p. 68
4.2.2 Ant Colony Optimization - ACO . . . . . . . . . . . . . . . . . p. 71
4.2.2.1 ACO-OR . . . . . . . . . . . . . . . . . . . . . . . . . . p. 72
4.2.2.2 ACO-AL . . . . . . . . . . . . . . . . . . . . . . . . . . p. 75
4.2.2.3 ACO-ORVNDP . . . . . . . . . . . . . . . . . . . . . . p. 77
4.2.2.4 ACO-ALVNDP . . . . . . . . . . . . . . . . . . . . . . p. 79
4.2.2.5 ACO com GRASP e VNDP . . . . . . . . . . . . . . . . p. 81
4.2.3 Bees Algorithm - BA . . . . . . . . . . . . . . . . . . . . . . . . p. 83
4.2.3.1 Algoritmo construtivo aleatório . . . . . . . . . . . . p. 85
4.2.3.2 Algoritmo busca local aleatória . . . . . . . . . . . . . p. 86
5 Experimentos computacionais p. 87
5.1 Definição das instâncias de teste do PCV-MPQ . . . . . . . . . . . . . p. 87
5.2 Metodologia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 89
5.2.1 Ajuste de parâmetros . . . . . . . . . . . . . . . . . . . . . . . . p. 90
5.3 Resultados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 93
5.3.1 Solver X Heurística AH . . . . . . . . . . . . . . . . . . . . . . . p. 93
5.3.2 GRASP X Heurística AH . . . . . . . . . . . . . . . . . . . . . . p. 94
5.3.2.1 G-LK X Heurística AH . . . . . . . . . . . . . . . . . . p. 94
5.3.2.2 G-PR X Heurística AH . . . . . . . . . . . . . . . . . . p. 95
5.3.2.3 G-VNDP X Heurística AH . . . . . . . . . . . . . . . . p. 95
5.3.3 ACO X Heurística AH . . . . . . . . . . . . . . . . . . . . . . . p. 96
5.3.3.1 ACO-OR X Heurística AH . . . . . . . . . . . . . . . . p. 96
5.3.3.2 ACO-AL X Heurística AH . . . . . . . . . . . . . . . . p. 97
5.3.3.3 ACO-ORVNDP X Heurística AH . . . . . . . . . . . . p. 98
5.3.3.4 ACO-ALVNDP X Heurística AH . . . . . . . . . . . . p. 98
5.3.3.5 ACO-GALVNDP X Heurística AH . . . . . . . . . . . p. 99
5.3.4 BA X Heurística AH . . . . . . . . . . . . . . . . . . . . . . . . . p. 100
5.3.5 Comparação das meta-heurísticas . . . . . . . . . . . . . . . . . p. 101
5.3.5.1 Instâncias simétricas . . . . . . . . . . . . . . . . . . . p. 101
5.3.5.2 Instâncias assimétricas . . . . . . . . . . . . . . . . . . p. 118
6 Considerações finais p. 134
6.1 Trabalhos futuros . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 135
Referências p. 137
Apêndice A -- Dados de experimentos computacionais p. 142
Apêndice B -- Dados de instância p. 252
20
1 Introdução
O presente trabalho relata pesquisas realizadas abordando um novo problema de
roteamento nomeado Problema do Caixeiro Viajante com Múltiplos Passageiros e Quota
(PCV-MPQ). Este capítulo tem por objetivo justificar a importância desse modelo de
aplicação e alvo da pesquisa. Na seção 1.1 discorre sobre a justificativa e importância
do problema de aplicação. Na seção 1.2, descreve a metodologia empregada no traba-
lho. Na seção 1.3, assenta os objetivos da pesquisa. Na seção 1.4, resume as contribui-
ções da pesquisa. Na seção 1.5 descreve como o texto do trabalho está organizado.
1.1 Justificativa e Importância
O problema alvo da pesquisa está contextualizado na área de problema de trans-
porte enriquecidos especificamente abordando a aplicação de transportes solidários.
O transporte solidário hoje, representa uma das soluções possíveis para promover a
mobilidade sustentável e a otimização dos sistemas de transporte, especialmente em
sistemas urbanos e suburbanos.
O transporte solidário é um meio de locomoção no qual diferentes pessoas se reú-
nem para compartilhar um veículo. A modalidade está difundindo em várias cidades
do mundo, por exemplo, por meio de aplicativos como Carona Direta, Me leva, BlaBla-
Car e outros. Em outros casos é o próprio poder público que fomenta o compartilha-
mento de veículos através de isenção de pedágios.
As vantagens do compartilhamento de veículos são múltiplas e impactam dife-
rentes áreas da economia, administração, ecologia e sociologia. Destacam-se: redução
da poluição ambiental, diminuição dos tempos de viagens, diminuição dos custos de
transporte, redução das áreas nobres destinadas à estacionamento de veículos, maior
conforto ao usuário, socialização e minimização dos engarrafamentos.
O uso do transporte em grupo ou solidário é impulsionada em países como os Esta-
21
dos Unidos, Canadá e alguns estados da União Europeia. Este tipo de transporte pode
ser feito seguindo várias estruturas como exemplo bike-sharing (SHAHEEN; GUZMAN;
ZHANG, 2010), definida pelo uso coletivo de bicicletas, carsharing (SHAHEEN; COHEN;
ROBERTS, 2006), em que carros são alugados, ridesharing (CHAN; SHAHEEN, 2012), que
realiza o compartilhamento de acentos de carros, personal vehicle sharing (SHAHEEN;
MALLERY; KINGSLEY, 2012), na qual carros pessoais são alugados, carpooling (GRUEBELE,
2008), que segue a ideia da lotação de veículos para redução de pedágio, slugging (MA;
WOLFSON, 2013), em que caronas que exigem carros com vários ocupantes são dadas em
locais próximos a localidades livres de pedágio e taxi-sharing (HOSNI; NAOUM-SAWAYA;
ARTAIL, 2014), que realiza o compartilhamento de viagens de taxi (NOURINEJAD, 2014).
Um exemplo de aplicação possível do problema alvo é o da empresa, como por
exemplo a iFast Courier, Rappi e outras, que contrata entregadores ou denominados
couriers para realizar viagens de coleta de mercadorias. A empresa neste caso, pode
exigir do courier coletar ou entregar uma quantidade mínima de mercadorias sobre
um conjunto de pontos de coleta ou entrega. Os pontos alvo podem estar localizados
em área urbana, suburbana ou mesmo em diferentes localidades fora da cidade. O
courier pode ser livre para organizar sua rota e eventual lotação de seu veículo, desde
que atenda a entrega ou recolhimento dos itens dentro do horizonte de trabalho fi-
xado pela empresa contratante. Consequentemente, nada impede que o courier utilize
o seu carro para compartilhar assentos com eventuais interessados e assim possa redu-
zir seus custos de rota. No caso abordado, considera-se que o courier só tem permissão
para embarcar um passageiro caso possa entrega-lo em seu destino. Adicionalmente,
considera-se que o passageiro é protegido por um acordo prévio que fixa o valor má-
ximo do rateio a ser cobrado. A restrição evita que o courier mantenha o passageiro
embarcado de forma abusiva ou desnecessária, visando prolongar a permanência do
passageiro no veículo e, consequentemente, o rateio dos custos.
Possivelmente outros exemplos de aplicação do modelo pesquisado são possíveis
na área de transporte ou, eventualmente, em outras áreas. Como o problema pesqui-
sado é uma variante do Caixeiro com Coleta de Prêmios (BALAS, 1989), é de solução
algorítmica pelo menos tão difícil quanto o problema de substrato, um conhecido pro-
blema NP-Difícil. Contudo, o modelo compartilha elementos em comum com vários
outros modelos de roteamento como o Pickup Delivery (PARRAGH; DOERNER; HARTL,
2008a) pela função de embarque e desembarque e Ridesharing (AMEY; ATTANUCCI;
MISHALANI, 2011) pela função de planejamento dos passageiros embarcados, repre-
senta uma aplicação real para os problemas de transporte solidário. Trata-se de uma
22
aplicação real de difícil solução e bastante importante para a classe dos problemas de
transporte solidário.
1.2 Metodologia
A metodologia de pesquisa abordou os seguintes passos:
1. Análise de modelos correlatos da literatura, para definir relações do problema
alvo com outros problemas;
2. Modelagem matemática linear do novo problema, para formalizar o modelo e
permitir sua solução ótima através do uso de software de solução - solvers;
3. Criação de bancos de casos testes que representassem situações típicas do pro-
blema e que não exibissem evidentes vieses estatísticos,para analisar a qualidade
de métodos de solução;
4. Alcançar a solução exata dos casos do banco de instâncias e, quando a solução
exata se mostrou inalcançável em tempo computacional razoável, alcançar limi-
tes inferiores de casos de testes;
5. Criação de algoritmo heurístico ad hoc de solução buscando solucionar, de forma
ótima ou aproximada, cada etapa de decisão do problema, a saber: primeira
etapa: rota com bônus. Segunda etapa: embarque de passageiros; como se as eta-
pas fossem independentes entre si. Com essa aproximação objetivou-se alcançar
boas soluções, principalmente para os problemas que deixaram de ser soluciona-
dos pela abordagem exata, e examinar o grau de acoplamento existente entre a
rota mais barata e os embarques ótimos.
6. Criação, parametrização e teste estatístico de algoritmos meta-heurísticos de so-
lução, para estabelecer melhores soluções aproximativas do problema;
7. Análise dos resultados, para avaliar a eficiência e a eficácia dos métodos de solu-
ção desenvolvidos.
1.3 Objetivos
O presente trabalho possui os seguintes objetivos:
23
• Objetivo geral
– Apresentar e formalizar a variante PCV-MPQ, desenvolvendo métodos de
solução para o modelo.
• Objetivos específicos
– Exibir um modelo de Programação Matemática Linear para formalizar o
PCV-MPQ;
– Construir o banco de casos de testes;
– Validar e avaliar a eficácia e a eficiência dos métodos de solução a partir de
análises quantitativas e qualitativas.
1.4 Contribuições
Dentre as contribuições do presente trabalho, destacam-se as que se segue:
1. A formalização do problema.
2. Uma linearização de modelo matemático quadrático.
3. Um banco de casos de testes com 216 instâncias para o problema.
4. A solução exata do modelo linear proposto.
5. Um método de solução heurístico ad hoc que decompõe a tomada de decisão do
problema, definindo a rota e depois o embarque do veículo.
6. Nove algoritmos meta-heurísticos de solução.
7. Um experimento estatístico de validação e aferição de eficiência e eficácia dos
algoritmos.
8. A publicação do seguinte artigo:
(a) CARVALHO, A. V.; GOLDBARG, M. C.; GOLDBARG, E. F. G. O PROBLEMA
DO CAIXEIRO VIAJANTE COM MÚLTIPLOS PASSAGEIROS E QUOTA. In:
L SBPO 2018 Simpósio Brasileiro de Pesquisa Operacional, 2018.
24
1.5 Organização do trabalho
O presente trabalho está estruturado da seguinte maneira. No capítulo 2 contextu-
aliza, descreve e formaliza o problema alvo. No capítulo 3 apresenta o subproblema do
PCV-MPQ e um método de solução para resolvê-lo. No capítulo 4 aborda um método
heurístico e nove métodos meta-heurísticos de solução para o PCV-MPQ. No capítulo
5 apresenta experimentos e análises computacionais. E por fim, no capítulo 6 aborda
as considerações finais e propõe trabalhos futuros.
25
2 PCV-MPQ
Este capítulo tem o objetivo de contextualizar o problema alvo na seção 2.1 a partir
de problemas relacionados, descrever o problema alvo na seção 2.2 mostrando sua
relação com outros problemas da literatura, e apresentar a formalização na seção 2.3 e
conceitos na seção 2.4.
2.1 Contextualização do PCV-MPQ no estado da arte
2.1.1 O Problema do Caixeiro Viajante
O problema abordado na presente pesquisa tem por base o conhecido modelo
do Problema do Caixeiro Viajante (PCV) (FLOOD, 1956), que possui significativa re-
lação com outros modelos (LAPORTE; ASEF-VAZIRI; SRISKANDARAJAH, 1996). O PCV é
NP-difícil (KARP, 1975) e um dos problemas de Otimização Combinatória mais citados
na literatura, tanto por sua extensa aplicação prática como no roteamento de veículos,
perfuração de placas de circuito (MATAI; SINGH; MITTAL, 2010) e outras, como por sua
dificuldade de solução algorítmica.
Dentre os métodos de solução aproximativos para o PCV, destacam-se a heurís-
tica 2-opt (CROES, 1958), heurística 3-opt, heurística Lin-Kernighan (LIN; KERNIGHAN,
1973), Otimizações por Colônia de Formiga, Algoritmos Genéticos, e entre outros. Va-
riantes principais do PCV são descritas em (GOLDBARG; GOLDBARG; LUNA, 2017).
Dado um grafo G = (N, M) onde N = {1, ...,n} é um conjunto de vértices ou lo-
calidades de uma rede e M = {1, ...,m} um conjunto de arestas ou estradas que ligam
as localidades da rede, o problema consiste em definir a rota de menor custo que li-
gue todas as localidades, considerando que o caixeiro motorista do veículo visite cada
localidade uma única vez. A cada aresta (i, j) ∈ M está associado um custo, cij , que
representa o custo do deslocamento da localidade i para a j, e uma variável binária xij ,
que representa a utilização da aresta (i, j) pelo caixeiro e terá valor 1 se a aresta (i, j)
26
é utilizada e 0, caso contrário. Com base nestas informações, temos na seção 2.1.1.1
o modelo matemático linear do PCV, proposto por (DANTZIG; FULKERSON; JOHNSON,
1954).
2.1.1.1 Modelo do PCV
Minimizar:
Z =
∑
i∈N
∑
j∈N\{i}
cijxij (2.1)
Sujeito à:
∑
j∈N\{i}
xij = 1 i = 1, . . . , n (2.2)
∑
i∈N\{j}
xij = 1 j = 1, . . . , n (2.3)
∑
i∈S
∑
j∈S\{i}
xij ≤ |S | − 1 ∀S ⊂N, S , ∅ (2.4)
xij ∈ {0, 1} i, j = 1, . . . , n, i , j (2.5)
A função objetivo expressa na equação (2.1) realiza o cálculo do custo do percurso
do caixeiro. As restrições (2.2) e (2.3) garantem que toda localidade da rede, o caixeiro
chega apenas uma vez na localidade e sai apenas uma vez da localidade. A restrição
(2.4) assegura a formação de uma única rota que visita todas as localidades da rede
uma única vez.
2.1.2 O Problema do Caixeiro Viajante com Quota
O modelo pesquisado neste trabalho também compartilha elementos com o conhe-
cido problema do Caixeiro Viajante com Coleta de Prêmios (PCV-CP), variante do PCV
(BALAS, 1989). Nesse tradicional problema o caixeiro não é obrigado a visitar todas as
localidades da rede.
Dado um grafo direcionado G = (N, M) onde N = {1, ...,n} é um conjunto de vérti-
27
ces ou localidades de uma rede e M = {1, ...,m} um conjunto de arestas ou estradas que
ligam as localidades da rede, o objetivo do problema é minimizar uma função objetivo
constituída pelo custo da rota afetado por penalidades associadas ao não atendimento
eventual de localidades. A cada aresta (i,j) ∈M está associado um custo, cij , que repre-
senta o custo do deslocamento da localidade i para a j, e uma variável binária xij , que
representa a utilização da aresta (i,j) pelo caixeiro e terá valor 1 se a aresta (i,j) é uti-
lizada e 0, caso contrário. A cada localidade i ∈ N está associado uma penalidade pi , e
uma variável binária yi , que representa a visita do caixeiro na localidade i, e terá valor
1 se a localidade i é visitada e 0, caso contrário. Com base nestas informações, temos a
seguir a formulação matemática do PCV-CP, proposta por (FEILLET; DEJAX; GENDREAU,
2005).
Minimizar:
Z =
∑
(i, j)∈M
cijxij −
∑
i∈N
piyi (2.6)
Sujeito à:
∑
j∈N\{i}
xij = yi (i ∈N ) (2.7)
∑
i∈N\{j}
xij = yj (j ∈N ) (2.8)
restrições de eliminação de subciclo (2.9)
y1 = 1 (2.10)
xij ∈ {0, 1} ((i, j) ∈M) (2.11)
yi ∈ {0, 1} (i ∈N ) (2.12)
A função objetivo expressa na equação (2.6) realiza o cálculo do custo do percurso
do caixeiro. As restrições (2.7) e (2.8) são as restrições de atribuição de localidade no
percurso do caixeiro. As restrições (2.9) asseguram a formação de um único ciclo na
solução. Diferentes restrições para as restrições (2.9) são apresentadas em (FEILLET;
DEJAX; GENDREAU, 2005).
O problema pode ou não conter uma restrição de coleta mínima de bônus. Quando
o modelo contém somente uma restrição de coleta de bônus distribuídos nos vértices
28
potencialmente visitáveis e não considera penalidades para os vértices não visitados,
o modelo é denominado Caixeiro Viajante com Cotas ( PCV-Q ), modelo introduzido
por (AWERBUCH et al., 1998). Sendo assim, para termos a formulação PCV-Q, precisa-
ríamos realizar na formulação PCV-CP apresentada, o que se segue, mudar a restrição
(2.6) pela restrição (2.13), e acrescentar a restrição (2.14), na qual q representa o valor
mínimo de bônus a ser coletado.
Z =
∑
(i,j)∈M
cijxij (2.13)
∑
i∈N
piyi ≥ q (j ∈N ) (2.14)
O modelo do PCV com Quota é pouco visitado na literatura, destacando-se os tra-
balhos de (AUSIELLO et al., 2004) que relatam um algoritmo para o On-Line Quota Tra-
veling Salesman Problem. Em (YU; LIU; BAO, 2014) é relatado algoritmos exatos para
variantes online desse problema.
Uma estruturação sistemática dos problemas de coleta de prêmios é encontrada
em (GOLDBARG; GOLDBARG, 2012) que propõem uma classificação dos problemas dessa
classe em cinco diferentes grupos. No trabalho (JOZEFOWIEZ; GLOVER; LAGUNA, 2008),
é apresentado uma versão multiobjetivo do problema, que trata da otimização de dois
objetivos conflitantes: a minimização do tamanho da rota e a maximização do bônus
coletado.
2.1.3 O Problema do Caixeiro Viajante com Passageiros
Uma variante do PCV já examinada na literatura e que possui similaridades com o
modelo da presente pesquisa, é o Problema do Caixeiro Viajante com Passageiros (PCV-
P) (CALHEIROS, 2017). O PCV-P tem por característica realizar um rateio dos custos da
rota entre o caixeiro e os passageiros embarcados. Trata-se de um modelo que aborda o
problema do transporte solidário. Além do rateio, o modelo caracteriza-se por atender
restrições de rota e de custos impostas pelos passageiros. O objetivo é minimizar as
despesas do caixeiro, através de embarques de passageiros. Em (CALHEIROS, 2017) são
apresentados algoritmos evolucionários (Genético e Memético) e construtivos (ACO e
GRASP) de solução para o PCV-P.
O PCV-P é definido por um grafo G = (N, M) e um conjunto de passageiros P =
{1, ...,n}, onde N = {1, ...,n} é um conjunto de vértices ou localidades de uma rede e
29
M = {1, ...,m} um conjunto de arestas ou estradas que ligam as localidades da rede. A
cada p ∈ P , estão associados uma origem, org(p), de modo que todo vértice possua exa-
tamente um único passageiro, um destino, dst(p), org(p) , dst(p), e um recurso máximo,
trf(p), que p está disposto a pagar para realizar sua viagem no veículo do caixeiro. A
cada aresta (i, j) ∈M está associado um custo, cij , que é dividido igualmente com todos
os ocupantes do veículo e representa o custo do deslocamento da localidade i para a j.
Com base nestas informações, temos na seção 2.1.3.1 o modelo matemático quadrático
do PCV-P, proposto por (CALHEIROS, 2017). O modelo é capacitado, de forma que o
veículo do caixeiro não pode embarcar mais passageiros que sua capacidade máxima
declarada.
Definição das variáveis e parâmetros do modelo do PCV-P:
• xij : variável binária que representa a utilização da aresta (i,j) pelo caixeiro e terá
valor 1 se a aresta (i,j) é utilizada e 0, caso contrário;
• vpij : variável binária que representa o transporte do passageiro p pela aresta (i,j)
e terá valor 1 se o passageiro p é transportado pela aresta (i,j) e 0, caso contrário;
• ui : variável inteira que representa a ordem do vértice i na rota do caixeiro;
• K : parâmetro inteiro que representa a capacidade máxima de passageiro no veí-
culo do caixeiro.
2.1.3.1 Modelo quadrático do PCV-P
Minimizar:
Z =
∑
1≤i, j≤n
cijxij
1 +
∑n
p=1 vpij
(2.15)
Sujeito à:
n∑
j=1
xij = 1 (1 ≤ i ≤ n) (2.16)
n∑
j=1
xji = 1 (1 ≤ i ≤ n) (2.17)
ui −uj + 1 ≤ n(1− xij) (2 ≤ i, j ≤ n) (2.18)
30
n∑
p=1
vpij ≤ Kxij (1 ≤ i, j ≤ n) (2.19)
n∑
i=1
vpir +
n∑
i=1
vp1i = 0 (1 ≤ p ≤ n | r = org (p) , r , 1) (2.20)
n∑
i=1
vpsi +
n∑
i=1
vpi1 = 0 (1 ≤ p ≤ n | s = dst (p) , s , 1) (2.21)
n∑
j=1
vpij =
n∑
j=1
vpji (1 ≤ i, p ≤ n | i , org (p) , i , dst(p)) (2.22)
∑
1≤i, j≤n
cijvpij
1 +
∑n
p=1 vlij
≤ t (1 ≤ p ≤ n | t = trf (p)) (2.23)
xij , vpij ∈ {0,1} (1 ≤ i, j, p ≤ n) (2.24)
ui ∈ R+ (2 ≤ i ≤ n) (2.25)
A função objetivo expressa na equação (2.15) realiza o cálculo do custo total da
rota, dividindo os custos com os ocupantes do veículo, incluindo o caixeiro. As restri-
ções (2.16) e (2.17) garantem que todo vértice visitado pelo caixeiro terá uma aresta de
entrada e uma aresta de saída. A restrição (2.18) é a contribuição de (MILLER; TUCKER;
ZEMLIN, 1960) para o PCV, utilizada para impedir a criação de subciclo na solução. A
restrição (2.19) estabelece que a capacidade máxima de passageiros do veículo não será
ultrapassada. A restrição (2.20) assegura que todo passageiro embarcado, com origem
diferente da localidade 1, não retornará a sua cidade de origem e não embarcará na
localidade 1. A restrição (2.21) garante que todo passageiro embarcado, com destino
diferente da localidade 1, não embarcará na sua localidade de destino e não desem-
barcará na localidade 1. A restrição (2.22) assegura que o passageiro embarcado será
desembarcado na sua localidade de destino. A restrição (2.23) garante que os passagei-
ros embarcados não pagaram mais que seu recurso máximo.
A linearização do modelo descrito nesta seção é apresentada em (CALHEIROS, 2017).
2.1.4 O Problema do Caixeiro Viajante com Passageiros e Quota
Um problema derivado da união do modelo do PCV-P ao PCV-Q, que possui se-
melhança com o problema alvo da pesquisa, é o Problema do Caixeiro Viajante com
Passageiros e Quota (PCV-PQ) (SILVA, 2017). O modelo do problema visa minimizar
o custo da rota considerando o ganho do compartilhamento de despesas proposto no
31
PCV-P, mas tendo que cumprir uma restrição de coleta do bônus mínimo conforme o
do PCV-Q. O PCV-PQ consiste em desenvolver uma solução do PCV-Q, levando em
consideração que o caixeiro pode compartilhar os assentos do veículo com passageiros
que podem embarcar e desembarcar em localidades da sua rota. Como um modelo de
coleta de bônus, o caixeiro não é obrigado a visitar todas as localidades. Como um mo-
delo de coleta de passageiros, o caixeiro não é obrigado a embarcar passageiros. O cai-
xeiro e os passageiros não levam em consideração o tempo de viagem, a permanência
nas localidades ou a quantidade de localidades visitadas. Em (SILVA, 2017) são apre-
sentados três algoritmos Genético, três algoritmos Memético, um algoritmo GRASP e
um algoritmo heurístico de solução para o problema.
O PCV-PQ é definido por um grafo G = (N, M, B) e um conjunto de passageiros
P = {1, ...,n}, onde N = {1, ...,n} é um conjunto de vértices ou localidades de uma rede,
M = {1, ...,m} um conjunto de arestas ou estradas que ligam as localidades da rede
e B = {b1, ...,bn} um conjunto de bônus associado à cada localidade, considerando-se
bs = 0, onde s é a localidade em que o caixeiro inicia e finaliza seu percurso. O bônus é
coletado no momento da visita. A cada p ∈ P , estão associados uma origem, op, de modo
que todo vértice possua exatamente um único passageiro, um destino, dp, op , dp, e um
recurso máximo,wp, que p está disposto a pagar para realizar sua viagem no veículo do
caixeiro. A cada aresta (i, j) ∈M está associado um custo, cij , que é dividido igualmente
com todos os ocupantes do veículo e representa o custo do deslocamento da localidade
i para a j. Com base nestas informações, temos na seção 2.1.4.1 o modelo matemático
quadrático do PCV-PQ proposto por (SILVA, 2017).
Definição das variáveis e parâmetros do modelo do PCV-PQ:
• xij : variável binária que representa a utilização da aresta (i,j) pelo caixeiro e terá
valor 1 se a aresta (i,j) é utilizada e 0, caso contrário;
• vpij : variável binária que representa o transporte do passageiro p pela aresta (i,j)
e terá valor 1 se o passageiro p é transportado pela aresta (i,j) e 0, caso contrário;
• ui : variável inteira que representa a ordem do vértice i na rota do caixeiro;
• Q : parâmetro real que representa a quota mínima de bônus, que o caixeiro pre-
cisa coletar.
• K : parâmetro inteiro que representa a capacidade máxima de passageiro no veí-
culo do caixeiro.
32
2.1.4.1 Modelo quadrático do PCV-PQ
Minimizar:
Z =
∑
(i,j)∈M
xijcij∑
p∈P v
p
ij + 1
(2.26)
Sujeito à:
∑
i∈N\{j}
xij ≤ 1 ∀j ∈N\{s} (2.27)
∑
i∈N\{j}
xji ≤ 1 ∀j ∈N\{s} (2.28)
∑
i∈N\{s}
xsi = 1 (2.29)
∑
i∈N\{s}
xis = 1 (2.30)
∑
i∈N\{j}
xij −
∑
i∈N\{j}
xji = 0 ∀j ∈N\{s} (2.31)
ui −uj+ (n− 1)xij ≤ n− 2 2 ≤ i, j ≤ n, i , j (2.32)∑
(i, j) ∈ M
i , j
bixij ≥Q (2.33)
∑
p∈P
v
p
ij ≤ Kxij ∀ (i, j) ∈M, i , j (2.34)
∑
(i,j)∈M
v
p
ijcij∑
p∈P v
p
ij + 1
−wp ≤ 0 ∀p ∈ P (2.35)
∑
j∈N\{i}
v
p
ji −
∑
j∈N\{i}
v
p
ij = 0 ∀p ∈ P , i ∈N\{op, dp} (2.36)∑
i∈N\{op}
v
p
iop
= 0 ∀p ∈ P (2.37)
∑
i∈N\{dp}
v
p
dpi
= 0 ∀p ∈ P (2.38)
∑
i∈N\{s}
v
p
si = 0 ∀p ∈ P , op , s (2.39)
33
1 ≤ ui ≤ n− 1 2 ≤ i ≤ n (2.40)
v
p
ij ∈ {0,1} ∀(i, j) ∈M (2.41)
xij ∈ {0,1} ∀(i, j) ∈M (2.42)
cij ∈ R+ ∀ (i, j) ∈M (2.43)
A função objetivo expressa em (2.26) realiza o cálculo do custo do percurso di-
vidindo igualmente com todos os ocupantes do veículo, visando minimizar o custo
total do caixeiro. As restrições (2.27) e (2.28) estabelecem as condições necessárias de
formação de uma única rota considerando um subconjunto de localidades de N. As
restrições (2.29) e (2.30) garantem o início e o término da rota no vértice origem. A
restrição (2.31) obriga que qualquer vértice visitado pelo caixeiro possua uma aresta
de entrada e uma de saída. A restrição (2.32) assegura a formação de um único ciclo
na solução (MILLER; TUCKER; ZEMLIN, 1960). A restrição (2.33) obriga a coleta da quota
mínima de bônus Q. A restrição (2.34) garante que a capacidade máxima do veículo,
K, não será ultrapassada. A restrição (2.35) assegura que a despesa total de cada pas-
sageiro p ∈ P não ultrapasse wp. A restrição (2.36) garante que os passageiros em fluxo
continuarão em fluxo exceto no destino e origem. As restrições (2.37) e (2.38) garantem
que os passageiros não são embarcados antes do vértice de embarque ou que perma-
neçam no veículo após o caixeiro visitar o vértice de destino do passageiro. A restrição
(2.39) proíbe o embarque de qualquer passageiro em s, se ele não tiver origem em s. As
restrições de (2.40) a (2.43) definem os limites e a natureza das variáveis de decisão.
2.1.5 O Problema do Caixeiro Viajante com Passageiros e Lotação
Outro problema que possui similaridade com o problema alvo da pesquisa é o
Problema do Caixeiro Viajante com Passageiros e Lotação (PCV-PL) (BASTOS, 2017). O
PCV-PL inclui na característica do compartilhamento dos assentos do veículo do PCV-
P, eventuais descontos decorrentes de high-occupancy toll lanes, ou hov, que são faixas
de transito, que isentam veículos com ocupação acima de um determinado limite, do
pagamento de pedágio. Trata-se de um problema que causa implicações diretas sobre o
uso do espaço urbano. As faixas hov são incentivos de governo para redução do trafego
de veículos em áreas com incidência de congestionamento. O caixeiro neste problema,
é beneficiado pela divisão das despesas com os passageiros e pelos descontos das faixas
hov. No trabalho (BASTOS, 2017), é apresentado para o PCV-PL, um algoritmo branch-
and-bound e cinco algoritmos baseados nas heurísticas, Simulated Annealing, Variable
34
Neighborhood Search, Colônia de Abelhas e Algoritmo Genético.
Dado um grafo G = (N,M) onde N = {1, ...,n} é um conjunto de vértices ou loca-
lidades de uma rede e M = {1, ...,m} um conjunto de arestas ou estradas que ligam as
localidades da rede, um grafo esparso W = (N,M ′), onde M ′ é o conjunto de arestas
ou estradas hov que possuem isenção de pagamento de pedágio, e um conjunto de pas-
sageiros L = {1, ...,n}, o objetivo do problema é encontrar a rota de custo mínimo PCV,
considerando que o caixeiro pode compartilhar os assentos do veículo com passagei-
ros, e adicionalmente, beneficie-se com as faixas de trânsito hov. A cada passageiro
l ∈ L, estão associados uma origem, Pl , de modo que todo vértice possua exatamente
um único passageiro, um destino, Ql , Pl , Ql , e um recurso máximo, tl , que l está dis-
posto a pagar para realizar sua viagem no veículo do caixeiro. A cada aresta (i, j) ∈M
está associado um custo, cij , que é dividido igualmente com todos os ocupantes do
veículo e representa o custo do deslocamento da localidade i para a j. A cada aresta
(i, j) ∈M ′ está associado um custo, wij , que será adicionado ao custo total do caixeiro
se o deslocamento da localidade i para a j for utilizado com o veículo não lotado e 0,
caso contrário. Com base nestas informações, temos na seção 2.1.5.1 o modelo mate-
mático quadrático do PCV-PL proposto por (BASTOS, 2017).
Definição das variáveis e parâmetros do modelo do PCV-PL:
• xij : variável binária que representa a utilização da aresta (i, j) pelo caixeiro e terá
valor 1 se a aresta (i, j) é utilizada e 0, caso contrário;
• φij : variável binária que representa a utilização da aresta (i, j) pelo caixeiro com
o veículo lotado e terá valor 1 se a aresta (i, j) é utilizada com o veículo lotado e
0, caso contrário;
• vlij : variável binária que representa o transporte do passageiro l pela aresta (i, j)
e terá valor 1 se o passageiro l é transportado pela aresta (i, j) e 0, caso contrário;
• ui : variável inteira que representa a ordem do vértice i na rota do caixeiro;
• C : parâmetro inteiro que representa a capacidade máxima de passageiro no veí-
culo do caixeiro.
2.1.5.1 Modelo quadrático do PCV-PL
Minimizar:
35
Z =
∑
i,j∈N
cijxij∑
l∈L v
l
ij + 1
+ϕijwijxij (2.44)
Sujeito à:
n∑
j=1
xij = 1 ∀i ∈N (2.45)
n∑
j=1
xji = 1 ∀i ∈N (2.46)
u1 = 1 (2.47)
ui −uj + 1 ≤ (n− 1)(1− xij) i , j, ∀i, j ∈N\{1} (2.48)
n∑
l=1
vlij − Cxij ≤ 0 i , j, ∀i, j ∈N (2.49)
n∑
i=1
n∑
j = 1
j , i
vlijcij∑n
k=1 v
k
ij + 1
− tl ≤ 0 ∀l ∈ L (2.50)
ϕij = 1−

∑n
l=1 v
l
ij + 1
C + 1
 i , j, ∀i, j ∈N (2.51)
n∑
j = 1
j , i
vlij −
n∑
j = 1
j , i
vlji = 0 i , l, i ,Ql ,∀i ∈N, ∀l ∈ L (2.52)
n∑
i = 1
i , l
vlil +
n∑
i = 1
i ,Ql
vlQl i = 0 ∀l ∈ L (2.53)
n∑
i=2
vl1i = 0 ∀l ∈ L\{1} (2.54)
xij ∈ {0,1} ∀i, j ∈N (2.55)
ui ∈N\{1} ∀i ∈N\{1} (2.56)
vlij ∈ {0,1} ∀i, j ∈N (2.57)
ϕij ∈ {0,1} ∀i, j ∈N (2.58)
36
A função objetivo expressa na equação (2.44) realiza o cálculo do custo total do per-
curso do caixeiro dividindo os custos com os ocupantes do carro. As restrições (2.45)
e (2.46) garantem que as cidades serão visitadas uma única vez. As restrições (2.47) e
(2.48) é a contribuição de (MILLER; TUCKER; ZEMLIN, 1960) para o PCV, utilizada para
impedir a criação de subciclo na solução. A restrição (2.49) assegura que a capacidade
máxima de passageiros no veículo não será ultrapassada. A restrição (2.50) garante
que os passageiros embarcado não irão pagar mais que seu recurso máximo. A restri-
ção (2.51) assegura que o pedágio das estradas utilizadas pelo caixeiro seja cobrado
sempre que o carro não esteja lotado. A restrição (2.52) garante que todos os passagei-
ros embarcados sejam desembarcados. A restrição (2.53) assegura que todo passageiro
embarcado será desembarcado em sua localidade de destino. A restrição (2.54) garante
que todo passageiro com origem diferente localidade 1, não será embarcado na locali-
dade 1.
2.1.6 O Problema do Passeio Lucrativo com Passageiros e Restrições
de Tempo e Custo
O Problema do Passeio Lucrativo com Passageiros e Restrições de Tempo e Custo
(PPL-PRTC) (PETCH, 2018) é um problema recente que possui características simila-
res as do problema alvo da pesquisa. O PPL-PRTC possui a característica da divisão
dos custos do motorista do veículo com passageiros vista no PCV-P e dos eventuais
descontos decorrentes da alta ocupação do veículo do motorista vista no PCV-PL. No
problema o motorista realiza serviços de entrega e coleta em uma cidade e aproveita
para compartilhar os assentos do veículo com passageiros que solicitam carona na sua
rota. Todo serviço de coleta ou entrega realizado pelo motorista resulta em um paga-
mento (bônus), e um gasto de tempo na entrega. O motorista é livre para escolher as
localidades a visitar, os passageiros a embarcar e os serviços a realizar, e é restrito em
realizar apenas uma entrega ou coleta em cada localidade visitada. O motorista pode
visitar uma localidade e não realizar serviço, no qual gastaria tempo. Para o moto-
rista realizar embarque de passageiro, primeiramente,o veículo terá que ter assento
livre, segundo, o passageiro terá que estar disponível para embarque, e terceiro, terá
de concordar com a localidade de desembarque e o recurso máximo a ser gasto com
o transporte definidos pelo passageiro. O custo total da rota do motorista é composto
pelo custo da rota dividido com os ocupantes do veículo e pelo custo do pedágio, am-
bos definidos para cada trecho da rota. O objetivo do problema é encontrar a melhor
rota, serviços e embarques que proporcionem o maior lucro possível para um moto-
37
rista. Algoritmo exato de solução, e algoritmos meta-heurísticos (VNS, GRASP, Gené-
tico, Memético, Transgenético, ACO e uma hibridização do Memético com VNS) de
aproximação de solução são propostos em (PETCH, 2018) para o PPL-PRTC.
O PPL-PRTC é definido por um grafo G = (V ,E), um conjunto de passageiros P =
{1, ...,p} e um conjunto de pedágios O = {1, ...,m}, onde V = {1, ...,n} é um conjunto
de vértices ou localidades de uma cidade e E = {1, ...,m} é um conjunto de arestas ou
estradas que ligam as localidades da cidade. A cada localidade i ∈ V , estão associados
um bônus, dv , que representa o ganho pelo serviço realizado na localidade e um tempo,
sv , que representa o tempo para realizar o serviço na localidade. A cada p ∈ P , estão
associados uma origem, sp, um destino, ep, sp , ep, um recurso máximo, rp, que p está
disposto a pagar para realizar sua viagem no veículo do motorista, e uma janela de
tempo, [lp,np], que representa o intervalo de tempo que p estar solicitando embarque.
A cada aresta (i, j) ∈ E estão associados um custo, cij , que é dividido igualmente com
todos os ocupantes do veículo e representa o custo do deslocamento da localidade i
para a j, um tempo, tij , que representa o tempo de travessia da localidade i para a
j, e um valor de pedágio, oijk, que será adicionado ao custo total do motorista se no
deslocamento da localidade i para a j o veículo tiver k passageiros. Com base nestas
informações, temos na seção 2.1.6.1 o modelo matemático quadrático do PPL-PRTC
proposto por (PETCH, 2018).
Definição das variáveis e parâmetros do modelo do PPL-PRTC:
• xij : variável binária que representa a utilização da aresta (i,j) pelo motorista e
terá valor 1 se a aresta (i,j) é utilizada e 0, caso contrário;
• yi : variável binária que representa a visita do motorista na localidade i e terá
valor 1 se a localidade i é visitada e 0, caso contrário;
• zi : variável binária que representa a coleta do bônus da localidade i e terá valor
1 se o bônus é coletado e 0, caso contrário;
• vijk : variável binária que representa o transporte do passageiro i pela aresta (j,k)
e terá valor 1 se o passageiro i é transportado pela aresta (j,k) e 0, caso contrário;
• fij : variável real que representa a quantidade de tempo gasto até a aresta (i,j)
desde o vértice inicial;
• bi : variável real que representa o instante de início do atendimento ao vértice i;
38
• qijk : variável binária que representa a utilização da aresta (i,j) pelo motorista
com o veículo contendo k passageiros e terá valor 1 se a aresta (i,j) é utilizada
com o veículo contendo k passageiros e 0, caso contrário;
• K : parâmetro inteiro que representa a capacidade máxima de passageiro no veí-
culo do motorista;
• C : constante grande o suficiente, que deve ser maior do que o maior tempo gasto
de todas as arestas do grafo.
2.1.6.1 Modelo quadrático do PPL-PRTC
Minimizar:
Z =
∑
i∈V
dizi −
∑
i∈V
∑
j∈V \{i}
xi,jci,j
1 +
∑
k∈P vk,i,j
−
∑
i∈V
∑
j∈V \{i}
∑
k∈K
qi,j,kxi,joi,j,k (2.59)
Sujeito à:
∑
j∈V \{i}
xi,j = yi ∀i ∈ V (2.60)
∑
j∈V \{i}
xj,i = yi ∀i ∈ V (2.61)
∑
j∈V \{1}
f1,i =
∑
j∈V \{1}
x1,jt1,j (2.62)
∑
j∈V \{1}
fj,1 =
∑
i∈V
∑
j∈V \{i}
xi,jti,j +
∑
i∈V \{1}
zisi (2.63)
∑
j∈V \{i}
fi,j =
∑
j∈V \{i}
fj,i +
∑
i∈V \{i}
xi,jti,j + zisi ∀i ∈ V \{1} (2.64)
Cxi,j ≥ fi,j ∀i, j ∈ V (2.65)∑
j ∈ V \{sp}
vp,j,sp +
∑
j ∈ V \{ep}
vp,ep,j = 0 ∀p ∈ P (2.66)
∑
j ∈ V \{i}
vp,j,i −
∑
j ∈ V \{i}
vp,i,j = 0 ∀p ∈ P , i ∈ V \{sp, ep} (2.67)
39∑
p ∈ P
vp,i,j ≤ Kxi,j ∀i, j ∈ V (2.68)
∑
j∈V \{1}
vp,1,i +
∑
j∈V \{1}
vp,j,1 = 0 ∀p ∈ P , sp , 1, ep , 1 (2.69)
∑
i∈V
∑
j∈V \{i}
ci,jvp,i,j
1 +
∑
k∈P vk,i,j
≤ rk ∀p ∈ P (2.70)
b1 = 0 (2.71)∑
i∈V \{j}
fi,j = bj ∀j ∈ V \{1} (2.72)
bsk ≥ lk
∑
j∈V \{sp}
vp,sp,j ∀p ∈ P (2.73)
bsk ≤ nk +C(1−
∑
j∈V {sp}
vp,sp,j) ∀p ∈ P (2.74)
z1 = 0 (2.75)
z1 ≤ y1 ∀i ∈ V \{1} (2.76)∑
k∈K=0
qi,j,k = 1 ∀i, j ∈ V (2.77)∑
k∈K
kqi,j,k =
∑
k∈P
vi,j,k ∀i, j ∈ V (2.78)
xi,j ∈ {0,1} ∀i, j ∈N (2.79)
yi ∈ {0,1} ∀i ∈N (2.80)
zi ∈ {0,1} ∀i ∈N (2.81)
wi,j ∈ {0,1} ∀i ∈ P , j ∈ V (2.82)
vi,j,k ∈ {0,1} ∀i ∈ P ,∀j,k ∈ V (2.83)
qi,j,k ∈ {0,1} ∀i, j ∈ V , ∀k ∈ K (2.84)
bi ≥ 0 ∀i ∈N (2.85)
fi,j ≥ 0 ∀i, j ∈N (2.86)
A função objetivo expressa na formula (2.59), realiza o cálculo do lucro do moto-
rista. As restrições (2.60) e (2.61) garantem que toda localidade visitada pelo motorista
será visitada uma única vez. As restrições (2.62), (2.63) e (2.64) asseguram o cálculo
do tempo gasto pelo motorista, e adicionalmente, proíbem a formação de múltiplas
40
rotas. A restrição (2.65) garante que só haverá fluxo passando por um vértice caso
esteja na solução. A restrição (2.66) proíbe o desembarque de passageiro na sua locali-
dade de origem. A restrição (2.67) assegura que todos os passageiros embarcados serão
desembarcados. A restrição (2.68) garante que a capacidade máxima de passageiros
do veículo não seja ultrapassada. A restrição (2.69) assegura que as arestas utilizadas
pelos passageiros serão utilizadas pelo motorista. A restrição (2.70) garante que todo
passageiro embarcado não pagará mais que seu recurso máximo. A restrição (2.71)
determina o tempo na localidade inicial da rota. A restrição (2.72) relaciona o tempo
percorrido vinculado às arestas para um vínculo relacionado aos vértices. As restrições
(2.73) e (2.74) proíbem que um passageiro seja embarcado fora da sua janela de tempo.
A restrição (2.75) garante que nenhum serviço será realizado na localidade 1. A restri-
ção (2.76) assegura que serviço é só realizado em localidade visitada. A restrição (2.77)
garante o pagamento de um único pedágio em cada aresta utilizada. A restrição (2.78)
define o valor de qijk a partir da quantidade de passageiros na aresta. A linearização
do modelo descrito nesta seção é apresentada em (PETCH, 2018).
2.1.7 Conexões do PCV-MPQ com outros problemas de roteamento
O PCV-MPQ possui características que são visíveis em problemas da classe de pro-
blemas denominada de Ridesharing (AMEY; ATTANUCCI; MISHALANI, 2011), em proble-
mas de Carpooling e em modelos denominados de Pickup and Delivery (PARRAGH;
DOERNER; HARTL, 2008a).
2.1.7.1 Conexões do PCV-MPQ com o Ridesharing
A classe de problemas Ridesharing pode ser definida de uma forma geral como o
problema de reunir duas ou mais pessoas para compartilhar uma única viagem em um
veículo, sem levar em conta um acordo prévio ou um histórico de cooperação (DAILEY;
LOSEFF; MEYERS, 1999). Nesse sentido geral, o PCV-MPQ poderia ser classificado como
um problema de Ridesharing.
O Ridesharing basicamente é um modelo de lotação de veículo para uma dada via-
gem previamente definida pelo motorista, no qual os viajantes compartilham os custos
da viajem, como combustível, pedágio e taxas de estacionamentos. Ridesharing é uma
viagem conjunta de pelo menos dois participantes que compartilham um veículo. Nor-
malmente o transporte é feito por veículos privados, os quais dão maior conforto e
segurança. Outras implicações são possíveis além da lotação de veículo, com impactos
41
em áreas como transportes, economia e ciências sociais (KLEINER; NEBEL; ZIPARO, 2011).
O Ridesharing, é omisso na literatura presente, nos casos onde o embarque e de-
sembarque de passageiros é muito constante. Mas ao passar do tempo, estar se tor-
nando mais flexível, chegando a considerar serviço de taxi ou transporte personalizado
que segue um trajeto com condições previamente definidas (CHAN;SHAHEEN, 2012).
O sistema Ridesharing pode combinar a flexibilidade e a velocidade dos carros
particulares com o custo reduzido dos sistemas de linha fixa (FURUHATA et al., 2013).
Vários incentivos podem ser oferecidos pelo setor público, como exemplo, desconto de
licenciamento e pedágio.
Os benefícios do Ridesharing incluem, custos reduzidos de viagem, menos conges-
tionamento de trânsito e menos poluição ambiental. A poluição dos veículos é uma
das principais fontes de emissões de gases, e uma das causas das alterações climáticas
globais.
Mesmo os Ridesharing podendo oferecer uma grande quantidade de benefícios,
há uma série de desafios que restringiram sua adoção generalizada. A privacidade e
a responsabilidade legal do serviço são umas das preocupações dos participantes dos
sistemas Ridesharing (FURUHATA et al., 2013). A segurança pessoal é também uma preo-
cupação quando compartilha uma viagem com estranhos. Em (LEIBSON; PENNER, 1994)
são identificados possíveis riscos nos programas tradicionais Ridesharing.
Para (AMEY; ATTANUCCI; MISHALANI, 2011), um sistema Ridesharing de sucesso, re-
duziria as emissões, o consumo de combustível, os custos de estacionamento, o conges-
tionamento durante os períodos de pico de viagem, forneceria um modo alternativo e
confiável para os viajantes e promoveria uma maior igualdade no transporte. Para os
viajantes, os principais benefícios incluem diminuição do tempo de viagem e diminui-
ção dos custos (combustível e estacionamento).
Algumas estratégias de adoção do Ridesharing: sistemas de Vanpooling, pistas
HOV (high-occupancy vehicle), Carpooling casuais e instalações de Park-and-Ride (CHAN;
SHAHEEN, 2012). Os telefones com GPS, as redes sociais e a internet, são também im-
portantes. Os telefones com GPS ajudam a rastrear a localização dos viajantes com o
objetivo de atender melhor a solicitação de novos viajantes no serviço. As redes sociais
ajudam a estabelecer confiança entre os viajantes.
O Ridesharing é promovido por muitas agências e empresas públicas. Um exem-
plo é o clube online NuRide, que recompensa com pontos, quando viajantes utilizam
42
o transporte público, andam de bicicleta ou trabalham remotamente. Estes pontos po-
dem ser utilizados para cupons de restaurante, descontos em compras, e ingressos para
atrações. Outro exemplo é o serviço PickupPal, promovido por uma empresa que uti-
liza redes sociais para combinar viagens. A utilização de redes sociais pode limitar o
compartilhamento de viagens, com viajantes menos experientes em tecnologia. Algu-
mas empresas não cobram pelo serviço e não compensam os que oferecem viagens,
já em outras empresas é realizado a cobrança pelo serviço e a compensação dos que
oferecem viagens. O Ridesharing também é promovido por operadores de serviço, que
normalmente utilizam seus carros próprios e motoristas, por exemplo, para disponibi-
lizar transporte para aeroportos (FURUHATA et al., 2013). Nestes Ridesharing oferecidos
por operadores de serviço, normalmente as decisões são tomadas pelos operadores e os
passageiros simplesmente decidem se aceitam ou não, mas normalmente os locais de
embarque e desembarque são ajustados para os passageiros.
O problema básico de Ridesharing é um problema de atribuição, em que cada pas-
sageiro só pode combinar com um motorista e vice e versa. Este problema é NP-hard,
e pode ser expandido para múltiplos passageiros e múltiplos motoristas (NOURINEJAD,
2014).
Alguns problemas Ridesharing são considerados problemas estáticos. Os estáticos
assumem que o serviço possui todas as informações de todos os pedidos de viagem
dos passageiros. Portanto estes problemas são, mais apropriados para serviços em que
todas as solicitações de viagens são conhecidas previamente.
Dentre as versões Ridesharing existentes, a conhecida como "real-time"(GRUEBELE,
2008) ou "dinâmica"(DEAKIN; FRICK; SHIVELY, 2010) está se destacando atualmente e
ganhando cada vez mais espaço.
O Ridesharing dinâmico é um novo tipo de problema Ridesharing originado com
o aumento do uso dos telefones inteligentes, que torna possível compartilhar viagens
em um curto prazo (DOERNER; SALAZAR-GONZÁLEZ, 2014). Neste tipo de problema os
passageiros buscam um veículo em tempo real, sem planejamento prévio. O uso de
tecnologia, por exemplo GPS e web, é fundamental para o estabelecimento das viagens
em um curto prazo, bem como para auxiliar nos valores e formas de pagamento.
Os sistemas Ridesharing dinâmicos, executam modelos dinâmicos várias vezes du-
rante seu funcionamento, diferentemente dos sistemas Ridesharing estáticos. A cada
execução do modelo o sistema considera os viajantes que estão no sistema e os que
estão aguardando confirmação de transporte pelo sistema. A todo momento de execu-
43
ção do sistema, novos viajantes estão sendo inseridos e removidos no sistema. Esses
sistemas são de natureza dinâmica, já que os usuários noticiam sua participação em
momentos de execução específicos do sistema (NOURINEJAD, 2014).
Muitos sistemas Ridesharing dinâmicos incluem recursos extras, como exemplo:
armazenamento do perfil do usuário, integração com redes sociais, avaliação dos vi-
ajantes, transações financeiras automatizadas, incentivos e recompensas (AMEY; ATTA-
NUCCI; MISHALANI, 2011). Em alguns sistemas há a integração com informações de ou-
tros sistemas não Ridesharing, como exemplo, informações de ônibus, que podem ser
utilizadas pelo viajante quando uma viagem Ridesharing não poder ser estabelecida.
Os serviços Ridesharing dinâmicos oferecem uma maior flexibilidade para os via-
jantes encontrarem ou disponibilizarem viagens compartilhadas, permitindo-lhes su-
perar muitos desafios encontrados nas versões clássicas do Ridesharing. Essa flexibi-
lidade elimina a necessidade dos viajantes se comprometerem antecipadamente com
um horário fixo de viagem. Normalmente o viajante precisa apenas enviar uma men-
sagem que solicita ou oferece uma viajem, utilizando um telefone ou um computador,
para um serviço Ridesharing dinâmico, e o sistema disponibilizará rapidamente uma
viagem compartilhada se existir uma disponível. Na América do Norte muitos destes
serviços utilizam softwares, por exemplo, GreenRidew e Jack Bell Ride-Share, vendidos
por empresas privadas para aproximar os viajantes. Em julho de 2011, existia aproxi-
madamente 12 empresas na América do Norte oferecendo este tipo de software (CHAN;
SHAHEEN, 2012). Diferentes softwares ou empresas oferecem diferentes níveis de fle-
xibilidade de viagem. Desvantagens do serviço incluem preocupações relacionadas à
segurança e proteção dos viajantes.
Existe também as versões Ridesharing centralizada (GHOSEIRI; HAGHANI; HAMEDI,
2011) e descentralizada (KLEINER; NEBEL; ZIPARO, 2011). O Ridesharing centralizado é
pouco flexível, em situações que necessitam de trocas constantes de passageiros em um
mesmo veículo.
Outra versão Ridesharing é a multiobjetivo, que tem como objetivo otimizar si-
multaneamente mais de um objetivo normalmente conflitantes entre se. Uma versão
Ridesharing multiobjetivo é apresentada em (HERBAWI; WEBER, 2012), nesta versão os
objetivos conflitantes incluem: custo, tempo e a quantidade de motoristas.
Uma revisão abrangente de problemas Ridesharing, é apresentada em (FURUHATA et
al., 2013). Este trabalho propõe padrões de problemas Ridesharing, definidos a partir
de características do percurso do motorista, capacidade do veículo e quantidade de
44
passageiros. Outro trabalho de Ridesharing também importante é o (AGATZ et al., 2012),
que oferece uma revisão abrangente de sistemas Ridesharing dinâmicos.
2.1.7.2 Conexões do PCV-MPQ com o Carpooling
Em problemas de Carpooling são visíveis conexões com o PCV-MPQ e com os pro-
blemas de Ridesharing. Ridesharing normalmente inclui Carpooling. Características
dos problemas Carpooling que diferencia dos problemas Ridesharing: demanda regu-
lar, destinos pouco variáveis para os participantes e longo horizonte de planejamento(MORENCY, 2007).
O Carpooling pode ser definido como transporte simultâneo de duas ou mais pes-
soas de um ponto de embarque comum ou nas proximidades para um ponto de de-
sembarque comum ou nas proximidades. Exemplo comum de Carpooling: pessoas que
trabalham em um mesmo local, moram próximas e concordam em compartilhar um
veículo para ir ao trabalho. Carpooling representa um compartilhamento de veículos
mais fácil e comum (CIASULLO et al., 2018). Muitos problemas do setor de viagem po-
dem ser resolvidos com o Carpooling (BEN-AKIVA; ATHERTON, 1977).
Os serviços de Carpooling são disponibilizados na web e/ou em aplicativos de te-
lefone para os usuários solicitarem ou disponibilizarem viagens de carro (CIASULLO
et al., 2017). Alguns aplicativos permitem os usuários deixarem um feedback após a
utilização do serviço, com o objetivo de reduzir a preocupação dos usuários em viajar
com pessoas não conhecidas. Estes serviços visam aumentar a ocupação dos veículos
de pessoas que estão partindo para o trabalho ou saindo do trabalho. O funcionamento
do serviço de Carpooling é melhor em locais de trabalho onde há um grande número
de pessoas chegando e saindo (DEAKIN; FRICK; SHIVELY, 2010).
Nos EUA para aumentar a utilização dos serviços de Carpooling, implantou-se
muitas faixas expressas de trânsito reservadas para veículos com uma quantidade mí-
nima de ocupantes (DOERNER; SALAZAR-GONZÁLEZ, 2014). Ao trafegar por essas faixas
o motorista é beneficiado, com por exemplo, isenção de pagamento de pedágio.
A redução dos carros na rua, poluição, congestionamento, e de custos relacionados
ao uso de veículos como por exemplo, combustível, estacionamento e pneus, são uns
dos benefícios do Carpooling. O Carpooling oferece solução para muitos problemas
de trânsito e ao mesmo tempo oferece muitos benefícios aos utilizadores e ao meio
ambiente.
45
O Carpooling começou a ser colocado em prática durante a crise do petróleo e es-
cassez de energia na década de 1970 nos EUA (ROSENBLOOM; SHELTON, 1974) (KENDALL
et al., 1975). Os estudos desta época se concentravam em incentivos para as pessoas
utilizarem o Carpooling. Ao passar do tempo o Carpooling foi referenciado de várias
formas, que são bastante semelhantes, mas diferentes por possuírem características
próprias (BENTO; HUGHES; KAFFINE, 2013).
O problema Carpooling pode ser tratado como dinâmico, informal e flexível (CIA-
SULLO et al., 2018). O caso dinâmico também conhecido por Carpooling casual, organiza
as viagens em um curto espaço de tempo. Uma viagem é organizada em troca de um
pagamento de dinheiro, realizado por um dispositivo móvel com GPS e conectado a
uma rede social (MALLUS et al., 2017). Uma revisão de literatura do Carpooling dinâ-
mico é apresentada em (GRAZIOTIN, 2013). O caso informal também conhecido por
slugging, é um tipo de Carpooling criado para atender solicitações diversas de viajan-
tes (CHAN; SHAHEEN, 2012). O serviço de Carpooling informal é operado por pessoas
que compartilham coisas em comum além do horário e local de viagem (MASOUD; JAYA-
KRISHNAN, 2017). Já o Carpooling flexível é um tipo de Carpooling iniciado na década
de 1980 (CHAN; SHAHEEN, 2012), em que os viajantes precisam caminhar para uma
determinada localidade de encontro para oferecer ou receber viagens. Uma das prin-
cipais características deste Carpooling flexível é a ausência de organização de viagens
com antecedência (MINETT, 2009). As viagens são organizadas em locais de encontro,
por exemplo, estacionamentos e pistas HOV (KELLY, 2007). O Carpooling flexível pode
ser considerado um sistema de viagem de emergência (MINETT; VILLAGE; PEARCE, 2008).
Muitos métodos de solução exato, heurístico e meta-heurístico foram desenvolvi-
dos para o problema Carpooling. Em (BALDACCI; MANIEZZO; MINGOZZI, 2004) é apre-
sentado um método exato e um método heurístico de solução. No trabalho (MANIEZZO;
CARBONARO; HILDMANN, 2004) é relatado um método de solução baseado na meta-
heurística colônia de formigas.
2.1.7.3 Conexões do PCV-MPQ com o Pickup and Delivery
O PCV-MPQ ainda possui visíveis conexões com problemas de Pickup and Deli-
very, em que cada solicitação de transporte tem um ponto de coleta e entrega.
Os problemas de Pickup and Delivery são uma classe de problemas onde objetos ou
pessoas precisam ser transportados de uma origem a um destino (BERBEGLIA; CORDEAU;
LAPORTE, 2010). Esta classe aborda situações da vida real relacionadas a logística e
46
robótica, e representa uma importante classe de problemas de roteamento.
O objetivo similar dos problemas de Pickup and Delivery é encontrar o caminho
mais curto para coletar e distribuir objetos ou pessoas. O problema consiste em um
conjunto de localidades classificadas em localidades de coleta e localidades de entrega
(TING; LIAO, 2013).
O problema de Pickup and Delivery pode ser estático ou dinâmico. O problema
é estático quando todas as informações de coleta e entrega são conhecidas antes da
construção da rota. Nos problemas estáticos o horizonte de tempo de planejamento
das viagens é longo. Agora os problemas dinâmicos, também chamados de problemas
dial-a-ride dinâmicos, as informações de coleta e entrega são atualizadas ou dispo-
nibilizadas ao longo da construção da rota, e os pedidos de transporte consistem em
passageiros. Diferentemente dos problemas estáticos, o horizonte de tempo de plane-
jamento nos problemas dinâmicos é bastante curto. Em problemas dinâmicos os passa-
geiros precisam ser coletados e entregues em tempo real. Dois exemplos de problema
dial-a-ride dinâmico: problema do transporte de deficientes e idosos (BERBEGLIA; COR-
DEAU; LAPORTE, 2010); e o problema do roteiro de ônibus escolar, em que alunos são
transportados de suas casas para a escola e vice e versa (PARK; KIM, 2010).
Um problema dial-a-ride dinâmico pode ser tratado como uma junção de dois pro-
blemas, primeiro problema, consiste em definir uma rota que satisfaça um conjunto
de passageiros, transportando-os de seus locais de origem a seus locais de destino, e
segundo problema, consiste em definir qual momento o veículo ira realiza o embarque
e desembarque dos passageiros (DOERNER; SALAZAR-GONZÁLEZ, 2014). Nos problemas
dial-a-ride dinâmico os passageiros solicitam embarque em uma localidade e desem-
barque em uma outra localidade diferente em um determinado horizonte de tempo.
A inconveniência dos passageiros e tempo máximo de viajem dos passageiros são ca-
racterísticas também consideradas. O trabalho (PSARAFTIS, 1980) apresenta um dos
primeiros estudos sobre o dial-a-ride dinâmico que considera a insatisfação dos passa-
geiros.
Ao longo de anos diversos métodos de solução para diferentes versões do problema
dial-a-ride foram desenvolvidos. Em (PARRAGH; DOERNER; HARTL, 2010) foi apresen-
tado uma meta-heurística Variable Neighborhood Search para uma versão dial-a-ride
clássica que aborda o transporte de pacientes na Austrália. Um algoritmo hibrido ba-
seado na meta-heurística busca tabu foi desenvolvida para um dial-a-ride dinâmico
e apresentado no trabalho (BERBEGLIA; CORDEAU; LAPORTE, 2012). Outra hibridização
47
mais recente, agora para o dial-a-ride clássico, é apresentada em (PARRAGH; SCHMID,
2013).
A literatura sobre problemas Pickup and Delivery é vasta, incluindo várias pes-
quisas. Um estudo abrangente dividido em duas partes é apresentado em (PARRAGH;
DOERNER; HARTL, 2008a) (PARRAGH; DOERNER; HARTL, 2008b). O trabalho (TING; LIAO,
2013), classifica formulações de problemas Pickup and Delivery de acordo com os atri-
butos de transporte, nó, veículo e mercadoria.
2.2 Descrição do PCV-MPQ
O problema alvo da presente pesquisa é uma variante do PCV-Q, denominado
de Problema do Caixeiro Viajante com Múltiplos Passageiros e Quota (PCV-MPQ). O
PCV-MPQ possui a característica do embarque de passageiros visto no PCV-P, PCV-
PL, PCV-PQ e PPL-PRTC, e a característica da coleta do bônus mínimo, visto no PCV-
Q e PCV-PQ. Diferentemente do PCV-P,