Formulação Matemática para Otimização de Itinerários Turísticos: uma aplicação em Alagoas
Aluno: Cássio Aquino Rocha Orientador: Prof. Dr. Bruno Costa e Silva Nogueira
CassioNovo.pdf
Documento PDF (9.9MB)
Documento PDF (9.9MB)
Dissertação de Mestrado
Formulação Matemática para Otimização de
Itinerários Turísticos: uma aplicação em Alagoas
Cássio Aquino Rocha
car@ic.ufal.br
Orientadores:
Dr. Bruno Costa e Silva Nogueira
Dr. Rian Gabriel Santos Pinheiro
Maceió
Agosto 30, 2022
Cássio Aquino Rocha
Formulação Matemática para Otimização de
Itinerários Turísticos: uma aplicação em Alagoas
Dissertação apresentada por Cássio Aquino Rocha
em cumprimento parcial dos requisitos para o grau
de Mestre em Informática da Universidade Federal de
Alagoas, Instituto de computação.
Orientadores:
Dr. Bruno Costa e Silva Nogueira
Dr. Rian Gabriel Santos Pinheiro
Maceió
Agosto 30, 2022
Catalogação na Fonte
Universidade Federal de Alagoas
Biblioteca Central
Divisão de Tratamento Técnico
Bibliotecário: Marcelino de Carvalho Freitas Neto – CRB-4 - 1767
R672f
Rocha, Cássio Aquino.
Formulação matemática para otimização de itinerários turísticos :
uma aplicação em Alagoas / Cássio Aquino Rocha. – 2022.
59. : il.
Orientador: Bruno Costa e Silva Nogueira.
Co-orientador: Rian Gabriel Santos Pinheiro.
Dissertação (mestrado em informática) - Universidade Federal de
Alagoas. Instituto de Computação. Maceió, 2022.
Texto em inglês.
Bibliografia: f. 36-39.
Apêndices: f. 40-59.
1. Janelas de tempo. 2. Turismo - Design. 3. Rotas turísticas. I. Título.
CDU: 519.6:379.85
UNIVERSIDADE FEDERAL DE ALAGOAS/UFAL
Programa de Pós-Graduação em Informática – PPGI
Instituto de Computação/UFAL
Campus A. C. Simões BR 104-Norte Km 14 BL 12 Tabuleiro do Martins
Maceió/AL - Brasil CEP: 57.072-970 | Telefone: (082) 3214-1401
Folha de Aprovação
CÁSSIO AQUINO ROCHA
FORMULAÇÃO MATEMÁTICA PARA OTIMIZAÇÃO DE ITINERÁRIOS TURÍSTICOS:
UMA APLICAÇÃO EM ALAGOAS
Dissertação submetida ao corpo docente do Programa
de Pós-Graduação em Informática da Universidade
Federal de Alagoas e aprovada em 30 de agosto de
2022.
Banca Examinadora:
________________________________________
Prof. Dr. BRUNO COSTA E SILVA NOGUEIRA
UFAL – Instituto de Computação
Orientador
__________________________________________
Prof. Dr. RIAN GABRIEL SANTOS PINHEIRO
UFAL – Instituto de Computação
Coorientador
__________________________________________
Prof. Dr. BRUNO ALMEIDA PIMENTEL
UFAL – Instituto de Computação
Examinador Interno
________________________________________
Prof. Dr. EDUARDO VIEIRA QUEIROGA
Centre de Recherche Inria Bordeaux - Sud-Ouest
Examinador Externo
Agradecimentos
Gostaria de Agradecer,
À minha família, especialmente a minha mãe que me incentivou ir em frente nos estudos e
que me permitiu conhecer a área de tecnologia da informação, onde me encontrei.
À minha esposa, Elaine, por ter dado todo apoio necessário nesse período de estudo.
Aos meus orientadores, Dr. Bruno Nogueira e Dr. Rian Pinheiro por terem me apresentado um ambiente de trabalho compenetrado. Pelos ensinamentos, dedicação, pelo apoio, pela
paciência, pelos puxões de orelha merecidos, pelo o tempo em mim investido para orientação,
pela experiência completa.
A todos os colegas, amigos e parceiros discentes do PPGI pelas parcerias e aprendizados
coletivos e em especialmente Flávio Vasconcelos, Alfredo Lima, Flávio Hahn e João Luiz.
A todos os funcionários assistentes de serviços gerais, administrativos, técnicos e gestores
da Universidade Federal de Alagoas.
A todos professores que direta ou indiretamente contribuíram para este trabalho.
A todos os servidores do Instituto Federal de Alagoas que possibilitaram meu afastamento
para desenvolver as atividades em tempo Integral.
Por fim a Deus, por ter me concedido vida, saúde e sapiência, proporcionando-me alcançar
conquistas e superar obstáculos.
–
iii
Resumo
Este trabalho propõe um método exato para o Problema de Orientação com Seleção de Hotéis
e Janelas de Tempo (OPHS-TW). Neste problema, são dados um conjunto de hotéis e um conjunto de pontos de interesse (atrações turísticas) com suas respectivas pontuações e janelas
de tempo. O objetivo do problema é determinar um número fixo de viagens conectadas que
visitam alguns vértices (atrações e hotéis) e maximizar a soma das pontuações coletadas. Até
onde sabemos, este é o primeiro método exato para o OPHS-TW. Nosso método exato foi desenvolvido usando Programação Linear Inteira (ILP). Experimentos computacionais realizados
em instâncias do OPHS-TW encontradas na literatura mostram que o método exato consegue
provar vários ótimos anteriormente desconhecidos. Em particular, o algoritmo encontrou 38 soluções desconhecidas da literatura. Dessas soluções desconhecidas, todas foram comprovadas
como ótimas. No total, 361 das 373 instâncias foram provadas. Além disso, o método proposto
foi aplicado para a criação de itinerário turístico no contexto de Alagoas, considerandos pontos
turísticos, hotéis e janela de tempo e tempo de visitação. Nesses testes computacionais, o algorítimo exato obteve uma média de execução de 4,36 segundos para executar 10 instâncias
com 20 vértices.
Palavras Chave: Problema de Orientação de Equipe com Janelas de Tempo - Problema de
Design de Viagem Turística - Problema de Orientação - Rotas turísticas.
iv
Abstract
This work proposes an exact method for the Orientation Problem with Hotel Selection and Time
Windows (OPHS-TW). In this problem, a set of hotels and a set of points of interest (tourist attractions) are given with their respective scores and time windows. The objective of the problem
is to determine a fixed number of connected trips that visit some vertices (attractions and hotels)
and maximize the sum of the collected scores. As far as we know, this is the first exact method
for OPHS-TW. Our exact method was developed using Integer Linear Programming (ILP). Computational experiments performed on OPHS-TW instances found in the literature show that the
exact method can prove several previously unknown optima. In particular, the algorithm found
38 solutions unknown to the literature. Of these unknown solutions, all have been proven to be
optimal. In total, 361 of the 373 instances were proven. In addition, the proposed method was
applied to create a tourist itinerary in the context of Alagoas, considering tourist spots, hotels
and time window and visitation time. In these computational tests, the exact algorithm obtained
an average execution of 4.36 seconds to execute 10 instances with 20 vertices.
Palavras Chave: Team orienteering problem with time windows - Tourist trip design problem
- Orienteering Problem - Tourist routes.
v
Sumário
Lista de figuras . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Lista de Tabelas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
vii
viii
1
Introdução
1.1 Definição do Problema . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.2 Exemplo de instância para o OPHS-TW . . . . . . . . . . . . . . . . . . . . . .
1.3 Objetivos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.3.1 Objetivo geral . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.3.2 Objetivos específicos . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.4 Estrutura do trabalho . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1
3
4
6
7
7
7
2
Fundamentação Teórica
2.1 Meta-heurística . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.2 Métodos exatos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.3 Problema de design de viagem turística (TTDP) . . . . . . . . . . . . . . . . . .
2.4 Turismo em Alagoas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
8
8
10
11
12
3
Revisão da Literatura
15
4
Formulação proposta
19
5
Resultados
5.1 Ambiente de execução . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.2 Experimentos computacionais . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.3 Protótipo de Aplicação do OPHSTW no contexto Alagoas . . . . . . . . . . . . .
24
24
24
27
6
Conclusão e Trabalhos Futuros
35
Referências
36
Apêndice
40
A Resultado de 16 Conjuntos de instâncias
40
B Coordenadas
56
C Matriz de distância Google
58
vi
Lista de Figuras
1.1
1.2
2.1
2.2
2.3
2.4
2.5
3.1
3.2
4.1
4.2
4.3
5.1
5.2
5.3
5.4
5.5
Solução . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Linha do tempo do primeiro trip . . . . . . . . . . . . . . . . . . . . . . . . .
Intensificação x diversificação. . . . . . . . . . . . . . . . . . . . . . . . . .
Dados de entrada e roteiros recomendados no TTDP. . . . . . . . . . . . . .
Mapa com a localização dos principais pontos turísticos em Alagoas. . . .
Mapa ilustrativo com pontos turísticos em várias cidades de Alagoas. . . .
Gráfico com os principais segmentos. . . . . . . . . . . . . . . . . . . . . .
Competição de Orientação. . . . . . . . . . . . . . . . . . . . . . . . . . . .
Variantes do TSP e OP. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Descrição da variável de decisão xidj . . . . . . . . . . . . . . . . . . . . . . .
Entrada. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Solução. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Protótipo da Aplicação. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Primeiro dia (Tour Maceió). . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Segundo dia (Tour Maceió). . . . . . . . . . . . . . . . . . . . . . . . . . . .
Terceiro dia (Tour Maceió). . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Quarto dia (Tour Maceió) . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
vii
6
6
9
11
12
13
14
15
18
20
22
23
28
31
32
33
34
Lista de Tabelas
Tempo disponível para o passeio . . . . . . . . . . . . . . . . . . . . . . . .
Descrição das atrações utilizadas do Sertão . . . . . . . . . . . . . . . . . .
Descrição dos Hotéis utilizados do Sertão . . . . . . . . . . . . . . . . . . .
Solução Sertão com 2 dias (Trip) . . . . . . . . . . . . . . . . . . . . . . . .
Publicação inicial do OP e variantes com seleção de hotéis . . . . . . . . .
Descrição do conjunto de instâncias de Divsalar et al. (2014b). . . . . . . .
Resumo da comparação do algoritmo exato versus GA-VND. . . . . . . . .
Descrição das atrações utilizadas na simulação de Maceió . . . . . . . . . .
Descrição dos hotéis utilizados na simulação de Maceió. . . . . . . . . . . .
Solução Maceió com 4 dias. . . . . . . . . . . . . . . . . . . . . . . . . . . .
Teste Maceió . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4
5
5
5
16
25
26
28
29
29
30
A.1 Conjunto 1 (1-2) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
A.2 Conjunto 2 (2-3) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
A.3 Conjunto 3 (5-3) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
A.4 Conjunto 4 (3-4) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
A.5 Conjunto 5 (6-4) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
A.6 Conjunto 6 (10-4) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
A.7 Conjunto 7 (10-5) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
A.8 Conjunto 8 (10-6) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
A.9 Conjunto 9 (12-4) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
A.10 Conjunto 10 (12-5) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
A.11 Conjunto 11 (12-6) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
A.12 Conjunto 12 (15-4) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
A.13 Conjunto 13 (15-5) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
A.14 Conjunto 14 (15-6) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
A.15 Conjunto 15 (15-8) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
A.16 Conjunto 16 (15-10) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
B.1 Coordenadas Sertão . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
B.2 Coordenadas Maceió . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
56
57
C.1 Matriz Sertão . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
C.2 Matriz Maceió . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
58
59
1.1
1.2
1.3
1.4
3.1
5.1
5.2
5.3
5.4
5.5
5.6
viii
1
Introdução
A atividade turística vem ganhando cada vez mais importância e é uma alternativa ao desenvolvimento econômico de várias regiões. No Brasil, em 2019, o turismo obteve um crescimento
recorde, com rendimento de R$ 136,7 bilhões, o que representou o maior rendimento registrado
nos últimos quatro anos. Além disso, o setor criou mais de 25 mil vagas de julho de 2018 a
julho 2019 (GOV, 2019). Conforme o secretário de turismo do estado de Alagoas, Brito (2019),
o crescimento do turismo no estado impulsiona a expansão hoteleira na capital e no interior,
fazendo com que a média de ocupação hoteleira anual seja superada a cada ano. Em 2018,
a média anual de ocupação hoteleira do estado foi de 72%, a expectativa para o fim de 2019
era de 74%. Esses dados revelam não só o aumento da ocupação hoteleira, mas também o
crescimento do número de turistas que visitam o estado.
Diversas tecnologias vêm contribuindo para o desenvolvimento do setor. Os sistemas de
reserva online, como Booking, Trivago e Decolar facilitam o planejamento de uma viagem turística. A utilização de sistemas de reserva online facilita buscar disponibilidade de quartos vagos
em hotéis ou assentos em voos. Assim, é muito mais fácil para empresas e agentes de viagens
criarem um tour com os desejos do cliente, receber confirmações instantâneas, além de permanecer competitivo. Com o crescimento constante do setor no período referido e as contribuições
das tecnologias, torna-se de grande relevância realizar um estudo que una o conceito de cidades inteligentes ao turismo em Alagoas, pois, isso pode contribuir ainda mais na satisfação do
turista ao visitar o estado.
Os precursores nos estudos de criação de itinerários turísticos, unindo a ideia de cidade
inteligente ao turismo, foram Vansteenwegen and Van Oudheusden (2007). Em seus estudos,
eles verificaram que o problema de roteamento de ‘nós’ com prêmio pode contribuir na satisfação dos turistas em aplicações de geração de roteiros. Implementações desse problema foram
realizadas em Singapura por Gunawan and Lau (2016) e Atenas, na Grécia, por Gunawan et al.
(2017).
1
Introdução
2
Os problemas de roteamento com prêmio, segundo Archetti et al. (2017), têm como decisão
crucial a identificação de um subconjunto de clientes “convenientes” para servir, ao contrário do
que acontece no roteamento clássico, em que todos os clientes devem ser atendidos. Esses
problemas são tradicionalmente classificados em duas categorias: (i) problemas de roteamento
de nó com prêmio, nos quais os clientes estão localizados nos vértices de um grafo, e (ii) problemas de roteamento de arco com prêmio, nos quais os clientes correspondem aos arcos. De
acordo com Archetti et al. (2017), o problema de roteamento com prêmio é dividido em 3 classes
principais:
1. Coleta de prêmios (Prize-Collecting): A função objetivo é a minimização do custo total da
viagem. O principal problema estudado é o Salesman Problem, onde os clientes estão
localizados nos vértices com um único veículo disponível. Nesse caso, uma restrição
estabelece coletar uma quantia mínima de lucro.
2. Passeio Rentável (Profitable Tour ) : A função objetivo é a maximização da diferença entre
o lucro total arrecadado e o custo de viagem.
3. Orientação (Orienteering): A função objetivo é a maximização da pontuação total coletada. Nesse caso, uma duração máxima com restrição é imposta nas rotas e os pontos
disponíveis para visitar são localizados nos vértices do grafo. Esse problema foi iniciamento introduzido por Tsiligirides (1984), em que está relacionado a um caixeiro viajante
sem tempo suficiente para visitar todos os clientes importantes.
Esta dissertação aborda a categoria Orientação (Orienteering) acrescentada de restrições de
janela de tempo com disponibilidade de gerar mais de uma rota e seleção de hotéis. Essa
variante com essas restrições impostas é conhecida na literatura como Orienteering Problem
with Hotel Selection and Time Windows (OPHS-TW) proposto por Divsalar et al. (2014b), que é
o problema de Orientação com Seleção de Hotel e Janelas de Tempo para a criação de roteiros
turísticos.
Gavalas et al. (2014) afirmam que quando os turistas visitam um destino por vários dias
perdem muito tempo planejando um roteiro turístico levando em consideração os POIs (pontos
de interesse, do inglês points of interest), o tempo de visita a cada ponto turístico,
o horário de funcionamento dos POIs, o horário ideal de visita e a ordem de visita a cada
ponto turístico. Vansteenwegen and Van Oudheusden (2007) pensando nesses problemas de
planejamento, propuseram em 2007, a utilização da variante Team Orienteering Problem (TOP),
que permite a geração de roteiros turísticos por vários dias.
O TOP tem como função objetivo a maximização da pontuação de um conjunto de vértices,
cada vértice possui um certo valor (pontuação) e a distância entre os pontos é conhecida. No
entanto, nem todos os pontos precisam ser selecionados, pois o tempo é limitado. O TOP trata
de determinar rotas, limitadas em tempo, entre alguns dos pontos para maximizar a pontuação
Introdução
3
total. Uma nova variante do TOP voltada para o turismo foi proposta em 2009 por Vansteenwegen et al. (2009a), conhecida como Team Orienteering Problem with Time Windows (TOPTW).
Essa variante, além de acrescentar a geração de várias rotas, adicionou a restrição de janela de
tempo, onde a visita em um nó particular deve iniciar dentro de uma janela de tempo predefinida
(ou seja, inicia no horário de abertura do ponto e antes do fechamento).
Divsalar et al. (2014b) propuseram o OPHS-TW que é similar ao TOPTW. No entanto, além
das caraterísticas de janela de tempo e roteiros para vários dias, essa variante também possui
a seleção de hotel. O OPHS-TW pode ser formulado como um problema de planejamento de
viagem turística.
Os problemas de planejamento de viagens turísticas são conhecidos na literatura como
Tourist Trip Design Problem (TTDP), que segundo Vansteenwegen and Van Oudheusden (2007)
consideram três conjuntos de informações: informações sobre os atrativos (dias de abertura
e horas, momentos ideais para visitar, expectativa de tempo necessário para uma visita etc);
perfil do turista (valorização do turista para certas categorias de interesse, como esculturas,
natureza, ciência, restaurantes, etc.); informação de viagem (quantos dias os turistas querem
passar em uma determinada região ou cidade, etc.).
Pensando na difícil tarefa de criar roteiros turísticos por vários dias e também na contribuição
da aplicação para o estado de Alagoas, tendo em vista que o turismo contribui economicamente
para o estado, propomos uma formulação matemática do OPHS-TW para otimização de itinerários turísticos no contexto de Alagoas. A presente formulação matemática é o primeiro método
exato para OPHS-TW. Experimentos computacionais realizados em instâncias do OPHS-TW
encontrados na literatura mostram que nosso método exato consegue provar vários ótimos anteriormente desconhecidos. O algoritmo encontrou 38 soluções desconhecidas da literatura.
Dessas soluções desconhecidas, todas foram comprovadas como ótimas. No total, 361 soluções provaram ser ótimas.
1.1
Definição do Problema
O OPHS-TW pode ser formalmente definido da seguinte forma. Seja N um conjunto de POIs,
H um conjunto de hotéis, NH a união de N e H (NH = N ∪ H ) sendo que n = |N|, h = |H|,
nh = |NH|, e m o número de dias do passeio. Além disso, considere que Si é uma função da
pontuação, Oi é uma função que indica o horário de abertura e Ci é uma função que indica o
horário de fechamento para cada POI, onde i ∈ N . Ti é uma função que indica o tempo serviço
para cada POI, Td é uma função que indica um orçamento de tempo para cada dia, onde d ∈ m,
E é um conjunto de links (E ⊂ NH × NH ), Ci j é uma função que indica o tempo de viagem de
i a j, onde (i, j) ∈ E . Com base nessas definições, o objetivo do OPHS-TW é encontrar um
subconjunto de N , um subconjunto de H e um passeio com m viagens conectadas, de modo que
cada dia comece e termine em um hotel e a pontuação do passeio seja maximizada. Note que
Introdução
4
como é um passeio com m viagens conectadas, a viagem seguinte deve começar no mesmo
hotel que a viagem atual terminou. É possível chegar antes da abertura da janela de tempo e
esperar. Para o entendimento deste trabalho é importante distinguir trip de Tour. Cada plano
diário de visita é chamado de trip e um conjunto de trip conectados é chamado de Tour. Neste
trabalho também utilizamos termos como rota e dia para indicar um trip.
1.2
Exemplo de instância para o OPHS-TW
Na Tabela 1.1 é definido o tempo de passeio por trip. A Tabela 1.2 apresenta as entradas dos
POIs (Atrações turísticas), a coluna ‘Código’ identifica cada Points Of Interest (POI), a coluna
‘Atração’ é o nome da atração, a coluna ‘Visita (Ti )’ é o tempo de visitação da atração (ou tempo
de serviço), a coluna ‘Pontuação’ define o tanto que um turista deseja visitar o POI e as colunas
‘Aberto’ e ‘Fechado’ são a janela de tempo, período que inicia o serviço. Note que se um serviço
é iniciado, é garantido o tempo de serviço (Ti ) integral. A Tabela 1.3 possui os hotéis utilizados,
a coluna ‘Código’ identifica o hotel, já a coluna ‘Hotel’ possui o nome do hotel. O Apêndice B
possui as coordenadas e O Apêndice C contém a matriz de distância real entre POIs e Hotéis
das Tabelas 1.2 e 1.3.
Tabela 1.1 – Tempo disponível para o passeio
Tour
Trip T (min)
1º
180
2º
210
1
Para uma melhor compreensão do problema é reproduzida uma simulação com esses dados
apresentados, perceba que as Tabelas 1.1, 1.2 e 1.3 apresentam as entradas para o problema.
Uma solução ótima para a instância é representada nas Figuras 1.1, 1.2 e na Tabela 1.4. O
resultado da saída foi obtido pelo método exato do OPHSTW. A Figura 1.2 exemplifica a linha
do tempo do primeiro trip gerado, que somados o tempo de permanência e o tempo de deslocamento no primeiro trip obtemos o tempo que o turista realizou o passeio (174 minutos) e
possuía uma restrição de 180 minutos. Veja que o POI 1 foi programado para permanecer 90
minutos e sair às 12:37 com a janela fechada às 12:00 não tendo nenhuma restrição, já que a
janela restringe somente o período em que é iniciado o serviço. Como pode ser visto na Tabela
1.4, a pontuação do tour foi 19. O tempo de execução foi de 0, 9 segundos.
Introdução
5
Tabela 1.2 – Descrição das atrações utilizadas do Sertão
Código Atração
Cidade
Visita (Ti ) Pontuação Aberto Fechado
1
Hidrelétrica Xingó Piranhas
90 min
5
09:00
12:00
2
Mirante da CHESF Piranhas
60 min
4
10:00
14:00
3
Mirante Secular
Piranhas
120 min
5
07:00
19:00
4
Bordado S.F
Piranhas
60 min
1
8:00
17:00
5
Museu
Piranhas
60 min
5
10:00
16:00
6
Rota do Cangaço
Piranhas
90 min
3
08:00
10:00
7
Cânions do Rio SF Olho d’agua
180 min
2
10:00
16:00
8
Angiquinho
Delmiro
120 min
1
07:00
12:00
9
Cristo Redentor
Pão de Açúcar
60 min
1
07:00
18:00
Tabela 1.3 – Descrição dos Hotéis utilizados do Sertão
Código Hotel
10
Pousada São Paulo
11
Dunen Hotel
12
Porta do Sol Pousada
13
Bristol Aline Hotel
14
Macambira Café Pousada
15
Hotel Virgulino
16
Pousada Paraiso dos Cânions
Tabela 1.4 – Solução Sertão com 2 dias (Trip)
Dia
Trip
Pontuação
1º
10 → 2 → 1 → 11
9
2º
11 → 3 → 5 → 10
10
Total
19
Introdução
6
Figura 1.1 – Solução
Fonte: Figura do Google Maps e editada pelo autor.
Figura 1.2 – Linha do tempo do primeiro trip
1.3
Objetivos
A seguir, serão descritos os objetivos gerais e específicos deste trabalho.
Introdução
1.3.1
7
Objetivo geral
Propor uma nova formulação matemática baseada em ILP para o problema de otimização do
OPHS-TW.
1.3.2
Objetivos específicos
• Desenvolver uma formulação do OPHS-TW;
• Testar a formulação em instâncias da literatura e no estado de Alagoas;
• Comparar o método proposto com os métodos estado da arte.
1.4
Estrutura do trabalho
Este documento está dividido em 6 capítulos.
• O Capítulo 2 apresenta métodos de otimização e informações do turismo em Alagoas;
• O Capítulo 3 são apresentados os trabalhos relacionados;
• O Capítulo 4 é apresentada a formulação matemática do problema;
• O Capítulo 5 os resultados obtidos nos testes são expostos e analisados;
• O Capítulo 6 apresenta a conclusão do trabalho e trabalhos futuros.
2
Fundamentação Teórica
Este capítulo apresenta um resumo sobre métodos de otimização começando com metaheurística e métodos exatos, na sequência é discorrido sobre problema de design de viagem
turística (TTDP) e turismo em Alagoas.
2.1
Meta-heurística
Na década de 70, surgiu um novo tipo de algoritmo de aproximação que tenta combinar métodos
heurísticos básicos em frameworks de alto nível visando explorar eficiente e efetivamente um
espaço de busca (Blum and Roli, 2008). Atualmente esses métodos são chamados de metaheurísticas, termo difundido por Glover (1986). Essa expressão é resultado da combinação
do prefixo grego metá (no sentido de alto nível, além) com heurística (do grego heuriskein ou
euriskein, descobrir) (Sörensen and Glover, 2013).
As meta-heurísticas são desenvolvidas especificamente para encontrar uma solução que
seja “boa o suficiente” no menor período computacional possível. Elas podem ser definidas
como métodos de solução que orquestram uma interação entre procedimentos de melhoria
local e estratégias de nível superior (Glover and Kochenberger, 2006). Esses métodos criam
um processo capaz de escapar de ótimos locais. As meta-heurísticas são geralmente utilizadas
para resolver vários tipos de problemas e não necessariamente um problema específico. Elas
não garantem a solução exata do problema, logo são bastantes utilizadas quando os problemas
são considerados N P -difíceis e sua resolução não pode ser feita em um tempo viável.
Segundo Blum and Roli (2003) dois conceitos muito importantes nas meta-heurística são
intensificação e diversificação. Essas são as duas forças que determinam amplamente o comportamento de uma meta-heurística. Eles são de alguma forma opostos, mas também complementares mutualmente. A intensificação tem em vista explorar o mínimo ou máximo em um local
já encontrado, já a diversificação tem em vista encontrar locais ainda não explorados. Na Figura
8
Fundamentação Teórica
9
2.1 pode ser visto um exemplo com vários vales com o objetivo de encontrar o mínimo global.
Veja que utilizando somente o procedimento de intensificação o primeiro ponto (à esquerda da
figura) iria ficar preso ao mínimo local, já que esse método geralmente utiliza movimentos curtos
e um passo curto antes ou depois não iria sair do mínimo local. Em contrapartida, utilizando a
pertubação (sendo um procedimento para diversificação), a solução pode escapar desses mínimos locais e assim encontrar o ótimo global do problema, como pode ser visto nos pontos a
direita. É notável, que nesses dois precedimentos, um completa a necessidade do outro.
Figura 2.1 – Intensificação x diversificação.
Na literatura existem diversas meta-heurísticas, algumas populares são:
• Ant Colony Optimization (ACO) que sua construção é baseada no comportamento das
formigas, que foi proposto por Dorigo et al. (1996);
• Iterated Local Search (ILS) foi introduzido por Lourenço et al. (2010) que se constrói
iterativamente uma sequência de soluções;
• Greedy Randomized Adaptive Search Procedures (GRASP) foi proposto inicialmente por
Feo and Resende (1995), existem duas fases dentro de cada iteração do GRASP: a primeira constrói uma solução através de uma função gulosa aleatória adaptativa; o segundo
aplica um procedimento de busca local na tentativa de encontrar uma melhoria.
• Em 1975, Holland introduziu um mecanismo que é semelhante ao Processo de evolução
conhecido como Genetic Algorithm (GA) (Holland, 1975).
Fundamentação Teórica
2.2
10
Métodos exatos
Muitos problemas práticos e teóricos em engenharia, ciência da computação, pesquisa operacional e outras áreas podem ser formuladas como um problema de programação matemática
ou, simplesmente, um problema de otimização. Rao (2009) define otimização como o ato de
encontrar a melhor solução nas circunstâncias dadas. Na resolução desse problema, deve-se
maximizar ou minimizar uma determinada função. Problema de otimização utiliza uma ou mais
variáveis de forma que todas as restrições se satisfaçam. Esses problemas são denominados
de métodos exatos, modelados sob a forma de equações ou desigualdades. Os métodos exatos são mais utilizados em problemas de pequena ordem e os heurísticos em problemas mais
complexos.
Diferentes modelos de Programação Matemática podem ser usados para modelar e resolver diferentes problemas de otimização. Eles podem ser divididos em linear e não linear, este
trabalho foca no modelo linear. Na Programação Linear Inteira é um problema em que todas ou
alguma(s) das suas variáveis são discretas (têm de assumir valores inteiros). Existem alguns
tipos como a Programação Linear Inteira Pura e a Programação Linear Inteira Mista, a primeira
é um problema em que todas as variáveis são discretas, já a segunda se apenas algumas variáveis precisarem ser inteiras. Existe um caso especial de variáveis inteiras: as variáveis binárias
que apenas podem tomar os valores 0 (zero) ou 1 (um). Assim, quando todas as variáveis
de um modelo são binárias é um modelo de Programação Inteira Binária. Um Problema de
Programação Linear Inteira (PPLI) pode ser definido sob a seguinte forma:
n
max
∑ Sixi
(2.1)
i=1
n
s.t
∑ Ti j xi ≤ B j
∀ j ∈ {1, . . . , n}
(2.2)
x∈Z
(2.3)
i=1
xi ≥ 0
Em que Si , Ti j e B j são dados (números reais) e xi representam as variáveis de decisão.
A função linear a ser maximizada (2.1) é denominada função objetivo. Já as Restrições (2.2)
determinam o domínio do problema. E Restrições (2.3) são conhecidas como restrições de
integralidade.
Para obter a solução ótima de um problema, a maioria dos métodos exatos baseiam-se
em técnicas de enumeração exaustiva. Eles são denominados por métodos de pesquisa em
árvore, conhecidos por branch-and-bound (B&B). O primeiro algoritmo B&B para Programação
Inteira (PI) foi proposto por Land and Doig (1960). Esses métodos consideram uma separação
do conjunto de soluções aceitáveis do problema inicial e, seguidamente, resolvem cada um
dos problemas parciais obtidos. Cada nó da árvore corresponde a um atributo do problema e
as ramificações correspondem a partições do conjunto de soluções aceitáveis. As folhas da
Fundamentação Teórica
11
árvore, ou ‘nós’ terminais, irão corresponder às soluções completas.
Os algoritmos exatos garantem a solução ótima. No entanto, estão associados a um grande
esforço computacional, dado o elevado número de soluções a analisar (Cavique, 2020). Algumas meta-heurísticas, às vezes, são combinadas com os algoritmos exatos com intuito de
alcançarem melhores desempenhos e solução cada vez melhores. Essa combinação é definida
como uma matheristic.
2.3
Problema de design de viagem turística (TTDP)
Algumas das entradas para o problema de planejamento do roteiro turístico (TTDP) foram organizadas por Gavalas et al. (2014), ilustradas na Figura 2.2. Elas podem ser utilizadas para
implementar um sistema de criação de roteiros turísticos. As entradas ilustradas na Figura 2.2
são detalhadas abaixo:
Figura 2.2 – Dados de entrada e roteiros recomendados no TTDP.
Fonte: (Gavalas et al., 2014).
• Dados de POIs (dados sobre os pontos de interesse): Algumas informações de cada POIs
como tipo (praia, museu), localização, horário de funcionamento e score (pontuação) são
importantes para geração de um roteiro turístico;
Fundamentação Teórica
12
• Dados de sensor: Os sensores também podem ser um forte aliado para criação de um
roteiro turístico, visto que alguns pontos turísticos têm seu clima mais ideal para visita, em
um dia chuvoso, por exemplo, ir à praia não é atraente para a maioria dos turistas;
• Tempo real multimodal: Uma viagem turística podendo envolver vários tipos de transporte;
• Preferências do usuário: A preferência do usuário é o principal foco dos algoritmos para
TTDP, essa preferencia é realizada por pontuação aos POIs, sendo uma forte aliado para
geração de um roteiro turístico.
• Lógica de otimização de itinerários turísticos: Todas essas entradas e restrições podem
ser utilizadas para geração de um itinerário turístico utilizando algoritmos de otimização.
• Itinerários turísticos personalizados diários: Por meio desse conjunto de restrições e entradas, os turistas podem utilizar um roteiro personalizado por vários dias.
2.4
Turismo em Alagoas
O turismo é um setor bastante explorado pelo estado de Alagoas. Segundo Mourão (2021), que
é a titular da Secretaria Municipal de Turismo, Esporte e Lazer de Maceió, o turismo representa
grande parte de todos os empregos do Estado e responde por 8,1% do PIB (Produto Interno
Bruto) do país, uma atividade que cresce ano após ano.
Figura 2.3 – Mapa com a localização dos principais pontos turísticos em Alagoas.
Fonte: Dados abertos Alagoas.
O governo do estado de Alagoas disponibiliza no site https://dados.al.gov.br as principais
cidades turísticas do estado de Alagoas, bem como a localização dos atrativos e informação
Fundamentação Teórica
13
dos segmentos. Essas informações foram utilizadas para a simulação de roteiro turístico em
Alagoas utilizando OPHS-TW.
Figura 2.4 – Mapa ilustrativo com pontos turísticos em várias cidades de Alagoas.
Fonte: Dados abertos de Alagoas.
Os Mapas de Alagoas apresentados nas Figuras 2.3 e 2.4 são do site Dados abertos do
governo do estado de Alagoas. Esses mapas contêm os principais pontos turísticos definidos
pelo governo de Alagoas, bem como a localização dos atrativos. A Figura 2.4 mostra o mapa de
Alagoas com desenhos que representam características das atrações (cultural, aventuras, ecológicas) encontradas em determinados pontos do mapa. Na figura citada anteriormente também
é mostrado uma tabela com as cidades que possuem os principais atrativos que também foram
utilizadas na simulação do modelo proposto.
Na Figura 2.5 são apresentados os principais segmentos encontrados no estado de Alagoas
disponível no site dados abertos. Como pode ser observado no gráfico citado anteriormente,
O estado tem uma alta predominância de atrações de sol e praia. Essa categoria de atração
muitas vezes depende de uma embarcação aquática para ir até à atração turística e o período
de embarque é bastante limitado. No decorrer desse trabalho será visto o funcionamento da
janela de tempo do nosso problema que pode viabilizar a criação de itinerários com período
específico para iniciar o serviço.
Fundamentação Teórica
Figura 2.5 – Gráfico com os principais segmentos.
14
3
Revisão da Literatura
Este capítulo apresenta trabalhos relacionados ao OPHS-TW, que é o problema tratado neste
trabalho, começando pelo Orienteering Problem (OP). OP foi publicado inicialmente por Tsiligirides (1984). A sua construção baseou-se numa orientação desportiva que mistura corrida e
navegação na floresta, cada competidor utiliza um mapa e bússola. Os competidores começam
Figura 3.1 – Competição de Orientação.
Fonte: https://orienteeringusa.org.
em intervalos de tempo e procuram encontrar vários ‘pontos de controle’ que foram colocados
na floresta e cujas localizações estão marcadas nos mapas dos competidores. Eles não precisam visitar todos os pontos. Cada ponto de controle tem uma pontuação, e o objetivo do
competidor é maximizar sua pontuação total no limite de tempo da competição. Portanto, cada
competidor deve planejar sua rota para acumular a maior pontuação com tempo suficiente para
retornar à linha de chegada. Na Figura 3.1 é ilustrada uma competição de orienteering acessada no site americano orienteeringusa.org, nesse site pode encontrar mais informações sobre
15
Revisão da Literatura
16
o esporte. De acordo com Chao et al. (1996b), OP pode ser modelado como um problema de
otimização multinível. No primeiro nível, é preciso escolher um subconjunto de pontos de controle para visitar. No segundo nível, é resolvido um Traveling Salesman Problem (TSP) sobre o
subconjunto selecionado de pontos de controle. A Tabela 3.1 mostra os autores precursores do
OP e de algumas variantes com seleção de hotéis.
Tabela 3.1 – Publicação inicial do OP e variantes com seleção de hotéis
Nome
Autor
Descrição
OP
Tsiligirides (1984) A função objetivo é maximizar a
pontuação total no período da competição.
OPHS
Divsalar
(2013a)
et
al. Além da função objetivo do OP, há
também restrição de seleção de hotéis por um ou vários dias.
OPHS-TW
Divsalar
(2014a)
et
al. Além de ter as descrições do
OPHS, há também uma restrição de
janela de tempo, restringindo a visitação a um POI só deve ser iniciada
no horário de funcionamento e antes de ser fechado.
De acordo com Chao et al. (1996a), o OP é conhecido como problema de orientação de
concorrente único. Eles propuseram uma variante do OP com equipe, conhecida como TOP. A
orientação por equipes estende a versão de competidor único do esporte. Uma equipe composta por vários competidores (digamos, 2, 3 ou 4 membros) começa no mesmo ponto. Cada
membro da equipe tenta visitar o maior número possível de pontos de controle dentro de um
limite de tempo prescrito e termina no ponto de chegada. A equipe com a maior pontuação
vence.
Diversas aplicações e variantes surgiram do OP após sua publicação inicial, como o problema de entrega de combustível domiciliar (Golden et al., 1987), recrutamento de atletas em
escolas secundárias (Butt and Cavalier, 1994), encaminhamento de técnicos para atendimento
aos clientes (Tang and Miller-Hooks, 2005), criação de roteiros turísticos (Vansteenwegen and
Van Oudheusden, 2007).
Vansteenwegen et al. (2009b) propõem um modelo matemático e uma meta-heurística de
busca local guiada para resolver o TOP. Neste modelo, os membros de cada equipe TOP são
considerados como dias ou rotas. Vansteenwegen et al. (2009c) criarão a variante TOPTW para
gerar itinerários. No TOPTW, você recebe um conjunto de locais, cada um com uma pontuação,
um tempo de serviço e uma janela de tempo. O objetivo é maximizar a soma das pontuações
coletadas por um número fixo de rotas. Cada rota pode ser interpretada como uma viagem de
um dia com o tempo de visitação limitado.
Revisão da Literatura
17
Divsalar et al. (2013a) desenvolveram o Orienteering Problem with Hotel Selection (OPHS)
que é uma variante do problema de orientação. No OPHS, são dados um conjunto de vértices
(pontos de interesse) com uma pontuação e um conjunto de hotéis. O objetivo é determinar
um número fixo de viagens conectadas que visitam alguns vértices e maximizar a soma das
pontuações coletadas. Cada viagem tem duração limitada e deve começar e terminar em um
dos hotéis. Os hotéis não têm pontuação. O hotel inicial e final de chegada do passeio são
fornecidos. Divsalar et al. (2014c) também implementaram um algoritmo Memetic para OPHS
que consiste em dois níveis: no primeiro nível, um componente genético foca em encontrar uma
boa sequência de hotéis intermediários, enquanto no segundo nível seis movimentos de busca
local embutidos em uma estrutura de vizinhança variável que trata da seleção e sequenciamento
de vértices entre os hotéis.
OPHS-TW foi inicialmente proposto por Divsalar et al. (2014a). Cada POI é atribuído a uma
janela de tempo. Na prática, o POI tem horários de visita limitados. Portanto, eles adicionaram
um horário de abertura e fechamento para cada POI. Na formulação deles não é considerado o
tempo gasto (tempo de serviço) em cada POI, isso é considerado uma desvantagem para o modelo, pois um problema real deve considerar o tempo gasto em cada atrativo turístico. A metaheurística proposta foi o Genetic Algorithm with a Variable Neighborhood Descent (GA-VND).
Como foi uma publicação inicial do OPHS-TW não existia um método exato, então os autores
criaram uma adaptação nas instâncias do OPHS para adicionar a janela de tempo. Desta forma,
eles consideraram que uma solução ótima da instância OPHS permanece ótima também para a
instância OPHS-TW. Isso resulta do fato de que adicionar restrições extras (tempo janelas neste
caso) para um problema de otimização nunca pode resultar em uma solução melhor.
O Problema do Caixeiro Viajante (TSP) e o OP têm variantes semelhantes.
Como pode ser visto na Figura 3.2, eles carregam siglas comuns como TW indicando que o
modelo possui uma janela de tempo e HS indicando haver uma seleção de hotel no modelo. No
OP, o incremento da sigla T informa que o modelo possui equipes competindo entre si. Para o
TOP na criação de itinerários, cada membro de uma equipe é considerado uma rota (ou uma
TRIP), e a equipe é considerada um conjunto de rotas (TOUR). Em um OP, a diferença entre
um modelo com HS e um modelo com T é que o primeiro possui várias rotas e seleção de
hotéis, enquanto o último indica apenas que o modelo possui várias rotas. Segundo Divsalar
et al. (2013a) a principal diferença entre o TOP e o OPHS é que no TOP todas as viagens têm
que começar e terminar no mesmo vértice e nenhum hotel precisa ser selecionado.
Como foi visto, os modelos TSP e OP possuem variantes semelhantes (TW e HS). No
entanto, os modelos têm funções objetivo diferente. Golden et al. (1987) denominam o OP de
Generalized Traveling Salesman Problem (GTSP). Segundo ele, o GTSP se enquadra na classe
de problemas N P -difíceis, pois contém o conhecido problema do caixeiro viajante como um
caso especial. De acordo com Divsalar et al. (2013b), algumas diferenças óbvias do travelling
salesperson problem with hotel selection (TSPHS) em relação ao OPHS são que no TSPHS
todos os vértices devem ser visitados e a função objetivo é minimizar o número de viagens e
Revisão da Literatura
18
Figura 3.2 – Variantes do TSP e OP.
Variantes
TSP
OP
TOP
OPHS
TOPTW OPHS-TW
OPTW
TSPHS
TSPTW
TSPTWHS
o tempo total de viagem. No entanto, no OPHS nem todos os vértices devem ser visitados e
a função objetivo é maximalizar a pontuação dos vértices. Segundo Sousa et al. (2021), esse
problema considera um vendedor que tem que atender todos os clientes, mas, em alguns casos,
não consegue visitar todos eles em apenas um dia útil. Assim, é necessário dividir a rota em
viagens de um dia viáveis, considerando um limite de tempo de viagem por dia. Um pernoite
em um dos hotéis indicados separa viagens consecutivas.
Como pode ser observado nesse capítulo, os problemas que mais se assemelham ao problema tratado nesta dissertação, OPHS-TW, são os problemas OPHS (Divsalar et al., 2013a),
TOPTW (Vansteenwegen et al., 2009c), TSPTWHS (Baltz et al., 2015). No entanto, OPHS considera que os pontos turísticos não têm janela, e o TOPTW não considera hotéis, já TSPTWHS
a função objetivo não considera a seleção de vértices por pontuação. Em relação aos métodos para o OPHS-TW, existem poucas meta-heurísticas, entre elas three-component heuristic
(I3CH) (Cheung, 2016) e GA-VND (Divsalar et al., 2014a) e o presente trabalho é o primeiro a
propor um método exato.
4
Formulação proposta
Este capítulo apresenta a formulação proposta para o OPHS-TW. Na nossa formulação, algumas restrições foram aproveitadas do modelo TOPTW desenvolvido por Vansteenwegen et al.
(2009c). As variáveis de decisão são:
• xidj = 1 se, no trip d , uma visita ao local i for seguida por uma visita para a localização j e
0 caso contrário. ∀ i, j ∈ {1, . . . , nh + 1}, d ∈ {1, . . . , m};
• yid = 1 se o local i for visitado no trip d , caso contrário 0. ∀ i ∈ {1, . . . , nh + 1}, d ∈
{1, . . . , m};
• sid é o início do serviço no local i no trip d , ∀ i ∈ {1, . . . , nh + 1}, d ∈ {1, . . . , m}.
Os parâmetros utilizados são:
• Si → pontuação do POI i;
• Ti → tempo de visita (ou tempo de serviço) do POI i;
• Td → tempo do passeio do dia d .
• Ci j → tempo para viajar do local i para o j;
• Oi → hora que inicia o serviço i;
• Ci → hora que fecha o serviço i;
A Figura 4.1 exemplifica os índices i, j usados na variável de decisão xidj , que possui dummy
node, POIs e hotéis. No total são utilizados dois dummy nodes que estão nos índices 0 e nh + 1
(igual a f ). Eles são utilizados apenas para facilitar a construção da seleção do hotel. M
uma grande constante. Os POIs são obtidos nos índices 1 . . . n. Os hotéis estão nos índices
n + 1 . . . nh (igual a n + h).
19
Formulação proposta
20
Figura 4.1 – Descrição da variável de decisão xidj .
0
1
...
POIs
Dummy node
n
n+1
nh
...
f
Hotéis
Dummy node
As Equações (4.1 à 4.19) apresentam a formulação proposta, a Função Objetivo (4.1) maximiza a pontuação total coletada. As Restrições (4.2) garantem que um ponto turístico (ou POI)
seja visitado no máximo uma vez. As Restrições (4.3) e (4.4) determinam a conectividade e a
linha do tempo de cada tour. As Restrições (4.5) garantem que exista uma aresta do dummy
para um hotel, e (4.6) garantem que exista uma aresta do hotel para um dummy. As Restrições
(4.7) limitam o tempo de viagem por dia (ou rota), e as Restrições (4.8) garantem que o hotel
que o turista dormir seja o mesmo hotel que acordar. Restrições (4.9) e (4.10) garantem que
todos os dias um turista saia de um hotel e retorne a um hotel. A Restrição (4.11) fixa o hotel
inicial como o primeiro do conjunto. Já a Restrição (4.12) fixa o hotel final como o segundo do
conjunto e essas restrições podem ser removidas caso os hotéis inicial e final não sejam fixos.
As Restrições (4.13) e (4.14) garantem que uma visita a uma atração só seja iniciada dentro
da janela de tempo. Restrições (4.15) e (4.16) garantem que não exista uma aresta do dummy
para uma atração.
m
max
n
∑ ∑ Siyid
(4.1)
d=1 i=1
m
s.t
∑ ykd ≤ 1
∀ k ∈ {1, . . . , n}
(4.2)
∀ i, j ∈ {0, . . . , nh}, d ∈ {1, . . . , m}
(4.3)
∀k ∈ {1, . . . , nh}, d ∈ {1, . . . , m}
(4.4)
∀ d ∈ {1, . . . , m}
(4.5)
∀ d ∈ {1, . . . , m}
(4.6)
∀ d ∈ {1, . . . , m}
(4.7)
∀ d ∈ {1, . . . , m − 1}, i ∈ {n + 1, . . . , nh}
(4.8)
d=1
sid + Ti +Ci j − s jd ≤ M(1 − xidj )
nh
nh
∑
d
=
xik
i=0
∑ xkd j + xkd f = ykd
j=1
nh
∑ x0d j = 1
j=n+1
nh
∑ xdj f = 1
j=n+1
nh
f
∑ Tiyid + ∑ Ci j xidj
i=0
(d+1)
xidf = x0i
!
≤ Td
j=1
Formulação proposta
n
21
nh
∑ ∑ xidj = 1
∀ d ∈ {1, . . . , m}
(4.9)
∀ d ∈ {1, . . . , m}
(4.10)
i=1 j=n+1
n
nh
∑ ∑ xdji = 1
i=1 j=n+1
1
x0(n+1)
=1
(4.11)
m
x(n+2)
f =1
(4.12)
Oi ≤ sid
∀ i ∈ {1, . . . , n}, d ∈ {1, . . . , m}
(4.13)
sid ≤ Ci
∀ i ∈ {1, . . . , n}, d ∈ {1, . . . , m}
(4.14)
xidf = 0
∀ d ∈ {1, . . . , m}, i ∈ {1, . . . , n}
(4.15)
d
x0i
=0
∀ d ∈ {1, . . . , m}, i ∈ {1, . . . , n}
(4.16)
xidj ∈ {0, 1}
∀ i, j ∈ {1, . . . , nh + 1}, d ∈ {1, . . . , m}
(4.17)
0 ≤ yid ≤ 1
∀ i ∈ {1, . . . , nh + 1}, d ∈ {1, . . . , m}
(4.18)
sid ≥ 0
∀ i ∈ {1, . . . , nh + 1}, d ∈ {1, . . . , m}
(4.19)
Para compreender melhor o funcionamento do modelo OPHS-TW, a Figura 4.2 ilustra a
entrada do modelo, onde os POIs formam um subgrafo completo e todo hotel é ligado a todos
POIs, representado pelo traço de maior espessura. Os hotéis dummies são utilizados para
facilitar a seleção dos hotéis.
Na Figura 4.3 é ilustrada uma solução, onde as arestas em vermelho representam a primeira
rota e as arestas em azuis a segunda rota. Note que o hotel final de uma rota (ou seja, o hotel
da dormida) é o mesmo que inicia a próxima rota (ou seja, o hotel de acordar). Cada POI possui
uma janela de tempo que é o período que o serviço pode ser iniciado. A distância entre os POIs
e hotéis é conhecida e todo POI possui uma pontuação.
Para deixar o modelo mais robusto, em cada uma das Restrições (4.3), a constante M foi
definida da seguinte forma:
1 +C + T +C − O , se i ∈ {1, . . . , n} e j ∈ {1, . . . , n}
i
i
ij
j
Mi j =
T +C ,
caso contrário.
max
(4.20)
ij
Em que no primeiro caso, (i ∈ {1, . . . , n} e j ∈ {1, . . . , n}), i e j correspondem a dois POIs. Já
no segundo caso, i ou j é um hotel.
Por meio desta definição, é possível remover as variáveis em que Mi j < 0 do modelo, pois
isso indica que o ponto j não pode ser visitado após o ponto i. Dessa forma, quando Mi j < 0,
é adicionada a restrição xidj = 0, ∀d ∈ {1, . . . , m}.
Formulação proposta
22
Figura 4.2 – Entrada.
n+1
n+1
n
n+2
n+3
.
.
.
n+4
n+5
n+3
n+2
0
f
Dumies
..
.
nh
n+4
Hotéis
POIs
Formulação proposta
23
Figura 4.3 – Solução.
n+1
n+1
n
n+2
n+3
.
.
.
n+4
n+5
n+3
n+2
0
f
Dumies
..
.
nh
n+4
Hotéis
POIs
Primeiro dia (Rota 1)
Segundo dia (Rota 2)
5
Resultados
Este capítulo apresenta os resultados computacionais, que foram feitos para avaliar o método
proposto.
5.1
Ambiente de execução
O método exato foi desenvolvido utilizando a linguagem de programação C++ e executado utilizando o pacote Cplex (software de otimização da IBM) versão 12.9, abaixo é ilustrado uma lista
com as especificações completas do ambiente de execução:
• Processador: CPU Intel® Xeon(R) E5-2670 0 @ 2,60GHz × 24
• Sistema Operacional: Linux Mint 20.3 Una 64-bit
• Kernel: Kernel Linux 5.4.0-94-generic x86_64
• Memória: 100 GiB.
5.2
Experimentos computacionais
Nesta seção, avaliamos os resultados do nosso método exato e comparamos com os resultados
do GA-VND proposto por Divsalar et al. (2014b).
Como foi visto, na formulação do OPHS-TW deste trabalho, Ti (tempo de vista em cada
POI) é considerado. No entanto, nas instâncias propostas por Divsalar et al. (2014b) (utilizadas
na comparação) Ti é definido como zero, além disso foram consideradas as restrições (4.11),
(4.12) com o proposito de deixar semelhante ao estudo de Divsalar et al. (2014b).
Os resultados foram obtidos a partir de 16 conjuntos de instâncias do OPHS-TW com base
no número de hotéis e no número de viagens no passeio. Como não foi obtido o acesso ao
24
Resultados
25
código do GA-VND, reportamos os resultados como estão no artigo dos autores. As instâncias foram baixadas do site http://www.mech.kuleuven.be/en/cib/op sendo disponibilizadas por
Divsalar et al. (2014b).
Para melhor compreensão e organização, os dados estão separados em duas tabelas: a
Tabela 5.1 descreve cada conjunto de instância e a Tabela 5.2 mostra os resultados computacionais. Essas tabelas são resumidas do Apêndice A que possuem 16 conjuntos de instâncias,
cada conjunto é listado em uma tabela. Nesse apêndice as soluções em negrito são soluções
ótimas desconhecidas e as linhas representadas por ‘−−’ são soluções que apresentaram inconsistências.
Experimentos computacionais foram realizados em 395 instâncias. No entanto, algumas
dessas instâncias estavam inconsistentes. Portanto, foram excluídas da base de testes. No
total, 22 instâncias estavam inconsistentes, já que na janela de tempo o tempo de abertura
estava maior que o tempo de fechamento.
Tabela 5.1 – Descrição do conjunto de instâncias de Divsalar et al. (2014b).
POIs
Conjunto Menor Maior Hotéis intermediários Trip Total de instâncias Inconsistentes
1
31
101
1
2
35
2
2
31
101
2
3
35
0
3
31
101
5
3
35
1
4
31
101
3
4
35
1
5
31
101
6
4
35
0
6
63
99
10
4
22
2
7
63
99
10
5
22
2
8
63
99
10
6
22
3
9
63
99
12
4
22
2
10
63
99
12
5
22
0
11
63
99
12
6
22
1
12
63
99
15
4
22
0
13
63
99
15
5
22
0
14
63
99
15
6
22
2
15
99
99
15
8
13
5
16
99
99
15
10
9
1
395
22
Total
A Tabela 5.1 contém uma descrição detalhada de 16 conjuntos de instâncias. Os conjuntos de instâncias são separadas por características comuns, como o mesmo número de hotel
intermediário e trip. A coluna ‘Conjunto’ lista os conjuntos de instâncias, As colunas ‘Menor’ e
‘Maior’ indicam, respectivamente, a quantidade mínima e máxima de POIs no conjunto, a coluna
Resultados
26
‘Hotéis intermediários’ é o número de hotéis que fazem conexões entre os dias da viagem (excluindo o hotel inicial e final). A coluna ‘Trip’ contém o número total de viagens (ou rotas). Note
que, um conjunto de ‘Trip’ conectados é chamado de Tour. A coluna ‘Total de instâncias’ descreve o número total de instâncias por conjunto. A coluna ‘inconsistentes’ descreve o número
total de instâncias que tiveram alguma inconsistência por conjunto. Por fim, é apresentado um
sumário com o total. Os testes foram realizados apenas nas instâncias corretas, o que equivale
ao número total de instâncias menos as instâncias incorretas, igual a 373 instâncias.
A Tabela 5.2 compara o método proposto com o algoritmo GA-VND de Divsalar et al.
(2014b). A coluna ‘Conjunto’ lista os 16 conjuntos de instâncias que também correspondem
à Tabela 5.1. A coluna ‘Total’ corresponde ao número total de instâncias corretas usadas nos
testes por cada conjunto. As colunas ‘T(s)’ representam o tempo médio de execução de cada
conjunto de instância. As colunas ‘GAP’ representam o gap médio de execução de cada conjunto de instâncias.
Tabela 5.2 – Resumo da comparação do algoritmo exato versus GA-VND.
Conjunto
Total
Exato
GA-VND
T(s)
GAP
Ótimo
Melhor
T (s)
GAP
Ótimo
1
33
10,45
0,00
33
5
0,31
0,43
28
2
35
9,92
0,00
35
3
0,44
0,18
32
3
34
22,19
0,00
34
4
0,87
0,26
30
4
34
3443,12
0,00
34
1
0,69
0,18
33
5
35
144,51
0,00
35
4
2,16
0,80
31
6
20
3794,72
0,96
19
1
46,15
0,13
19
7
20
3975,06
0,67
19
4
115,95
0,28
16
8
19
3208,86
0,57
18
3
148,59
0,50
16
9
20
2382,84
0,00
20
2
71,04
0,06
18
10
22
5021,39
0,52
21
3
196,95
0,37
19
11
21
4911,53
1,18
19
3
265,02
0,45
18
12
22
3998,65
0,21
21
2
179,91
0,11
20
13
22
3994,75
0,18
21
0
396,36
0,00
22
14
20
1896,81
0,00
20
2
471,98
0,49
18
15
8
6238,27
1,38
7
1
975,92
0,01
7
16
8
13681,86
4,28
5
0
900,11
0,00
8
3545,93
0,62
235,78
0,27
Média
Total
373
361
38
335
Resultados
27
O GAP é definido na Equação 5.1, onde best é a melhor solução encontrada e x é a melhor
solução obtida pelo método. Note que o GAP é o percentual que mede o quão próximo a melhor
solução obtida está da melhor solução encontrada.
GAP =
best − x
∗ 100
best
(5.1)
Ainda na Tabela 5.2, as colunas ‘Ótimo’ representam o número total de soluções ótima para
cada conjunto de instâncias. A coluna ‘Melhor’ representa o número total de soluções melhores
que GA-VND, para cada conjunto de instâncias. Por fim, é apresentado um sumário com o total
e a média em relação a todos os conjuntos apresentados na tabela.
O método exato não conseguiu resolver algumas instâncias devido à complexidade delas.
Nesse caso, finalizou a execução por conta da restrição de tempo ou de memória. No entanto,
algoritmo conseguiu provar o ótimo de várias instâncias. As instâncias que apresentaram maior
dificuldade para resolver foram as instâncias 100-200 e 100-210 dos conjuntos 6 à 16. Abordagem exata encontrou 361 soluções ótimas de 373 instâncias utilizadas, o que corresponde
ao percentual de 96.78%. Foram Estabelecidas 38 novas melhores soluções, das quais todas
foram comprovadas como ótimas. Os resultados são promissores e uma vez que as soluções
ótimas para essas instâncias são conhecidas, elas podem ser usadas como referência para
pesquisas futuras.
5.3
Protótipo de Aplicação do OPHSTW no contexto Alagoas
Este trabalho também simulou a criação de itinerários turísticos no contexto de Alagoas. Na
simulação foi utilizado o tempo das viagens real. O tempo de viagem foi coletado por meio da
Application Programming Interface (API) distance matrix do Google, que também é fornecida a
distância. Para calcular o tempo de viagem foi preciso fornecer as coordenadas dos POIs que
foram coletas no site https://dados.al.gov.br do governo de Alagoas e as coordenadas dos hotéis
que foram coletas no Google maps. Nos Apêndices B e C são apresentados, respectivamente:
• Matriz de distância (sendo utilizado somente o tempo de deslocamento). Note que para
saber o tempo de deslocamento de um ponto a outro na matriz é verificado o índice de
origem com o de destino, onde a primeira coluna da matriz é a origem e o destino é a
primeira linha da matriz. O tempo de viagem de um ponto a ele mesmo não é considerado;
• Coordenadas que foram utilizadas para gerar a matriz.
Na Figura 5.1 há um exemplo de um protótipo para uma aplicação real. Esse protótipo
possui exemplo da coleta dos dados entrada para o modelo. Os dados principais que precisam
do preenchimento pelo usuário são: a pontuação de cada atrativo (que define o tanto que
o turista deseja visitar o POI); a data de ida e volta, na simulação de Alagoas os hotéis de
Resultados
28
Figura 5.1 – Protótipo da Aplicação.
início e fim não são definidos pelo usuário, no entanto, eles são selecionados pelo modelo de
otimização, para isso as Restrições 4.11 e 4.12 do modelo não foram utilizadas na simulação; o
tempo do passeio em cada dia e o tempo de visitação em cada POI também são definidos.
Tabela 5.3 – Descrição das atrações utilizadas na simulação de Maceió
Código Atração
Cidade Visita (Ti ) Pontuação Aberto Fechado
1
Pontal da Barra
Maceió
60 min
5
09:00
15:30
2
Passeio das 9 ilha
Maceió
360 min
5
08:00
09:00
3
Praia da Pajuçara
Maceió
180 min
2
08:00
12:30
4
Praia Ponta Verde
Maceió
180 min
3
10:00
15:00
5
Praia da Jatiúca
Maceió
240 min
4
10:00
13:30
6
Praia de Cruz das Almas
Maceió
180 min
3
07:00
15:00
7
Praia de Jacarecica
Maceió
180 min
2
08:00
13:00
8
Praia da Guaxuma
Maceió
180 min
2
08:00
12:30
9
Praia da Garça Torta
Maceió
360 min
4
08:00
09:00
10
Praia de Riacho Doce
Maceió
180 min
2
08:00
12:30
11
Praia Mirante da Sereia
Maceió
180 min
3
08:00
14:00
12
Praia de Ipioca
Maceió
180 min
1
10:00
13:30
13
Praia da Ponta do Mangue
Maceió
180 min
3
08:00
14:00
14
Centro Histórico de Jaraguá Maceió
90 min
5
08:00
13:00
Na simulação foram utilizados 14 POIs e 6 hotéis. Na Tabela 5.3 são descritos os dados dos
POIs, a coluna ‘Código’ possui a identificação de cada POI. A coluna ‘Atração’ possui o nome
Resultados
29
de cada atração. A coluna ‘Cidade’ possui as cidades utilizadas na simulação. A coluna ‘Visita
(Ti )’ tem o tempo estimado de visita a cada POI. A coluna ‘Pontuação’ é definido um valor 1 a
5 que mede o tanto que um turista deseja visitar o POI. As colunas ‘Aberto’ e ‘Fechado’ são
definidos o período para iniciar o serviço. Note que se o serviço é iniciado na janela é garantido
o tempo de visita (Ti ) integral sem depender do tempo de fechamento da janela.
Na Tabela 5.4 apresenta a lista de hotéis utilizados, para que a simulação do problema ficasse mais realista foram realizadas as consultas dos hotéis (nomes e coordenadas) utilizando
os sites Booking (é um site que possibilita a busca de hotéis e reserva de hospedagem) e Google maps. Assim como os POIs da Tabela 5.3, cada hotel também possui um índice, ilustrado
na coluna ‘Código’. A coluna ‘Hotel’ possui o nome de cada hotel.
Tabela 5.4 – Descrição dos hotéis utilizados na simulação de Maceió.
Código Hotel
15
Hotel Bomfim
16
Sun Paradise - JTR
17
Pousada das Araras
18
Poutur Pousada
19
Hotel Ponta Verde Maceió
20
Brisa do Mar
Na Tabela 5.5 é disponibilizada a solução para Maceió utilizando o método exato. Nessa
solução foi definido que o tempo do passeio é 1º dia: 9h30min; 2º dia: 9h00min; 3º dia: 5h30min;
4º dia: 8h30min. Na coluna ‘Dia’ numera os passeios utilizados. Na coluna Trip descreve a
conexão dos passeios. A coluna ‘Pontuação’ informa a pontuação obtida por dia de viagem.
Nas Figuras 5.2 à 5.5 representam a solução gráfica da simulação do estado de Maceió.
Tabela 5.5 – Solução Maceió com 4 dias.
Dia
Trip
Pontuação
1º
18 → 2 → 4 → 19
8
2º
19 → 14 → 8 → 11 → 17
10
3º
17 → 10 → 1 → 19
7
4º
19 → 5 → 6 → 17
7
Total
32
Resultados
30
A Tabela 5.6 possui 11 colunas, onde a primeira é o código correspondente aos dados da
Tabela 5.3 (com exceção a pontuação) e os dados dos hotéis da Tabela 5.4. As colunas S(1)
a S(10) são as pontuações das instâncias geradas aleatórias de 1 a 5. As soluções exatas
são obtidas no sumário ‘FO’ que é a função objetivo e ‘T(s)’ é o tempo de execução por cada
solução. O algorítimo exato obteve uma média de execução de 4,36 segundos para executar 10
instâncias com 20 vértices.
Tabela 5.6 – Teste Maceió
Código S(1) S(2) S(3) S(4) S(5) S(6) S(7) S(8) S(9) S(10)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
5
4
5
5
2
1
2
2
2
2
3
2
4
2
3
1
1
3
4
3
2
3
2
4
2
4
3
2
5
4
1
4
1
2
2
5
5
5
4
2
3
5
3
3
3
4
1
5
1
1
2
5
4
3
3
3
1
3
3
4
3
4
4
4
3
2
3
2
5
3
5
2
2
1
1
5
5
4
3
5
5
5
5
4
2
4
1
5
5
1
3
5
3
1
3
5
3
4
3
5
1
5
3
2
2
4
4
2
1
1
2
1
3
4
5
2
1
2
5
2
3
5
3
1
1
1
2
4
5
4
2
1
1
5
1
1
1
1
2
2
FO
T(s)
30 30 37 33 31 41 36 27 30
26
2,64 8,24 4,45 1,67 8,38 8,82 2,44 2,59 2,44 1,88
Percebe-se que na elaboração de um roteiro é considerada: a preferência do atrativo; o
tempo de visita por dia, por atração; total de dias; seleção de hotéis; tempo deslocamento de
um ponto ao outro; horário de início da visita. Então nota-se que a elaboração de roteiros turísticos não é uma tarefa fácil. No entanto, a utilização de métodos de otimização como o OPHSTW
pode facilitar a criação itinerário turístico de forma satisfatório. A preferência do usuário (pontuação) foi definida por cada atrativo, no entanto, dificilmente um turista conseguiria avaliar um
atrativo que nunca visitou, mas essa preferencia poderia se dar pelo segmento (cultural, praia,
histórico). Após pontuar a preferência do segmento, o algorítimo poderia escolher o POI mais
bem avaliado por turistas que já visitaram o atrativo.
Resultados
31
Figura 5.2 – Primeiro dia (Tour Maceió).
Fonte: Figura do Apple Maps e editada pelo autor.
Resultados
32
Figura 5.3 – Segundo dia (Tour Maceió).
Fonte: Figura do Google Maps e editada pelo autor.
Resultados
33
Figura 5.4 – Terceiro dia (Tour Maceió).
Fonte: Figura do Apple Maps e editada pelo autor.
Resultados
34
Figura 5.5 – Quarto dia (Tour Maceió)
.
Fonte: Figura do Apple Maps e editada pelo autor.
6
Conclusão e Trabalhos Futuros
Neste trabalho, foi proposto o primeiro método exato para o proeminente problema de geração de rotas turísticas OPHS-TW. Experimentos computacionais realizados em instâncias do
OPHS-TW encontrados na literatura mostram que nosso método exato para o OPHS-TW consegue provar vários ótimos anteriormente desconhecidos. Uma vez que as soluções ótimas
para essas instâncias são conhecidas, elas podem ser usadas como referência para pesquisas
futuras. Das 373 instâncias usadas, apenas 12 não puderam ser resolvidas devido à exceção
do limite de memória de 80 GB ou a exceção do tempo de 10 horas de execução. O algoritmo
encontrou 38 soluções desconhecidas da literatura. Dessas soluções desconhecidas, todas foram comprovadas como ótimas. No total, 361 das 373 instâncias foram comprovadas, o que
corresponde ao percentual de 96.78% do total de instâncias utilizadas.
A criação de itinerário turístico no contexto de Alagoas também foi simulado, utilizando pontos turísticos, hotéis e matriz de distância real. Nesses testes computacionais, o algorítimo exato
obteve uma média de execução de 4,36 segundos para executar 10 instâncias com 20 vértices.
Para trabalhos futuros, serão desenvolvidos uma meta-heurística para OPHS-TW com restrições de custos e a implementação do tempo de serviço (que define o tempo de visitação a um
POI). Essas contribuições podem cooperar ainda mais para a satisfação dos turistas na geração
de roteiros turísticos, uma vez que um roteiro gerado nem sempre é acessível ao orçamento do
turista, e o tempo de visitação em cada POI é fundamental para que o turista planeje o tempo
ideal de visitação em cada POI. Para que o problema seja mais realista, também é planejado
desenvolver um modelo com múltiplas janelas de tempo, já que alguns POIs possuem vários
horários de abertura e fechamento.
35
Referências
Claudia Archetti, Luca Bertazzi, Demetrio Laganà, and Francesca Vocaturo. The undirected
capacitated general routing problem with profits. European Journal of Operational Research,
257(3):822–833, 2017.
Andreas Baltz, Mourad El Ouali, Gerold Jäger, Volkmar Sauerland, and Anand Srivastav. Exact
and heuristic algorithms for the travelling salesman problem with multiple time windows and
hotel selection. Journal of the Operational Research Society, 66(4):615–626, 2015.
Christian Blum and Andrea Roli. Metaheuristics in combinatorial optimization: Overview and
conceptual comparison. ACM computing surveys (CSUR), 35(3):268–308, 2003.
Christian Blum and Andrea Roli. Hybrid metaheuristics: an introduction. In Hybrid
Metaheuristics, pages 1–30. Springer, 2008.
Rafael Brito. Crescimento do turismo em alagoas impulsiona expansão hoteleira na capital e
interior, Disponível em:. http://www.sedetur.al.gov.br/noticia/item/2552-crescimento-doturismo-em-alagoas-impulsiona-expansao-hoteleira-na-capital-e-interior, 2019. acesso em
20 de maio 2021.
Steven E Butt and Tom M Cavalier. A heuristic for the multiple tour maximum collection
problem. Computers & Operations Research, 21(1):101–111, 1994.
Luís Cavique. Otimização inteira: taxonomia das meta-heurísticas. 2020.
I-Ming Chao, Bruce L. Golden, and Edward A. Wasil. The team orienteering problem.
European Journal of Operational Research, 88(3):464–474, 1996a. ISSN 0377-2217.
DOI https://doi.org/10.1016/0377-2217(94)00289-4. URL
https://www.sciencedirect.com/science/article/pii/0377221794002894.
I-Ming Chao, Bruce L. Golden, and Edward A. Wasil. A fast and effective heuristic for the
orienteering problem. European Journal of Operational Research, 88(3):475 – 489, 1996b.
ISSN 0377-2217. DOI https://doi.org/10.1016/0377-2217(95)00035-6. URL
http://www.sciencedirect.com/science/article/pii/0377221795000356.
36
Referências
37
YK Cheung. Implementation of the iterative three-component heuristic for the team orienteering
problem with time windows. 2016.
A. Divsalar, P. Vansteenwegen, and D. Cattrysse. A variable neighborhood search method for
the orienteering problem with hotel selection. International Journal of Production Economics,
145(1):150–160, 2013a. ISSN 0925-5273. DOI https://doi.org/10.1016/j.ijpe.2013.01.010.
URL https://www.sciencedirect.com/science/article/pii/S0925527313000285.
Ali Divsalar, Pieter Vansteenwegen, and Dirk Cattrysse. A variable neighborhood search
method for the orienteering problem with hotel selection. International Journal of Production
Economics, 145(1):150–160, 2013b.
Ali Divsalar, Pieter Vansteenwegen, Masoud Chitsaz, Kenneth Sörensen, and Dirk Cattrysse.
Personalized multi-day trips to touristic regions: A hybrid ga-vnd approach. In Christian Blum
and Gabriela Ochoa, editors, Evolutionary Computation in Combinatorial Optimisation, pages
194–205, Berlin, Heidelberg, 2014a. Springer Berlin Heidelberg. ISBN 978-3-662-44320-0.
Ali Divsalar, Pieter Vansteenwegen, Masoud Chitsaz, Kenneth Sörensen, and Dirk Cattrysse.
Personalized multi-day trips to touristic regions: A hybrid ga-vnd approach. In European
Conference on Evolutionary Computation in Combinatorial Optimization, pages 194–205.
Springer, 2014b.
Ali Divsalar, Pieter Vansteenwegen, Kenneth Sörensen, and Dirk Cattrysse. A memetic
algorithm for the orienteering problem with hotel selection. European Journal of Operational
Research, 237(1):29–49, 2014c.
M. Dorigo, V. Maniezzo, and A. Colorni. Ant system: optimization by a colony of cooperating
agents. IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics), 26(1):
29–41, 1996. DOI 10.1109/3477.484436.
Thomas A Feo and Mauricio GC Resende. Greedy randomized adaptive search procedures.
Journal of global optimization, 6(2):109–133, 1995.
Damianos Gavalas, Charalampos Konstantopoulos, Konstantinos Mastakas, and Grammati
Pantziou. A survey on algorithmic approaches for solving tourist trip design problems.
Journal of Heuristics, 20(3):291–328, 2014.
Fred Glover. Future paths for integer programming and links to artificial intelligence. Computers
& operations research, 13(5):533–549, 1986.
Fred W Glover and Gary A Kochenberger. Handbook of metaheuristics, volume 57. Springer
Science & Business Media, 2006.
Referências
38
Bruce L Golden, Larry Levy, and Rakesh Vohra. The orienteering problem. Naval Research
Logistics (NRL), 34(3):307–318, 1987.
GOV. Turismo tem faturamento recorde de R$ 136,7 bilhões em 2019, Disponível em.
https://www.gov.br/pt-br/noticias/viagens-e-turismo/2019/10/
turismo-tem-faturamento-recorde-de-r-136-7-bilhoes-em-2019, 2019. acesso
em 11 de fevereiro 2021.
Aldy Gunawan and Hoong Chuin Lau. A fast algorithm for personalized travel planning
recommendation. PATAT, 2016.
Aldy Gunawan, Hoong Chuin Lau, Pieter Vansteenwegen, and Kun Lu. Well-tuned algorithms
for the team orienteering problem with time windows. Journal of the Operational Research
Society, 68(8):861–876, 2017.
John H. Holland. Adaptation in Natural and Artificial Systems: An Introductory Analysis with
Applications to Biology, Control and Artificial Intelligence. University of Michigan Press, Ann
Arbor, MI, 1975.
AH Land and AG Doig. An automatic method of solving discrete programming problems.
econometrica. v28. 1960.
Helena R. Lourenço, Olivier C. Martin, and Thomas Stützle. Iterated Local Search: Framework
and Applications, pages 363–397. Springer US, Boston, MA, 2010. ISBN
978-1-4419-1665-5. DOI 10.1007/978-1-4419-1665-51 2. URL
https://doi.org/10.1007/978-1-4419-1665-5_12.
Patrícia Mourão. Prefeitura inicia construção do primeiro Plano Municipal de Turismo de
Maceió, Disponível em. https://maceio.al.gov.br/noticias/semtel/prefeitura-inicia-construcaodo-primeiro-plano-municipal-de-turismo-de-maceio, 2021. acesso em 01 de agosto 2022.
Singiresu S Rao. Engineering optimization: Theory and practice, by john wiley & sons. Inc.,
New Jersey, 2009.
Kenneth Sörensen and Fred Glover. Metaheuristics. Encyclopedia of operations research and
management science, 62:960–970, 2013.
Marques Moreira Sousa, Pedro Henrique González, Luiz Satoru Ochi, and Simone
de Lima Martins. A hybrid iterated local search heuristic for the traveling salesperson
problem with hotel selection. Computers Operations Research, 129:105229, 2021. ISSN
0305-0548. DOI https://doi.org/10.1016/j.cor.2021.105229. URL
https://www.sciencedirect.com/science/article/pii/S0305054821000216.
Referências
39
Hao Tang and Elise Miller-Hooks. A tabu search heuristic for the team orienteering problem.
Computers & Operations Research, 32(6):1379–1407, 2005.
Theodore Tsiligirides. Heuristic methods applied to orienteering. Journal of the Operational
Research Society, 35(9):797–809, 1984.
Pieter Vansteenwegen and Dirk Van Oudheusden. The mobile tourist guide: an or opportunity.
OR insight, 20(3):21–27, 2007.
Pieter Vansteenwegen, Wouter Souffriau, Greet Vanden Berghe, and Dirk Van Oudheusden.
Metaheuristics for Tourist Trip Planning, pages 15–31. Springer Berlin Heidelberg, Berlin,
Heidelberg, 2009a. ISBN 978-3-642-00939-6. DOI 10.1007/978-3-642-00939-62 . URL
https://doi.org/10.1007/978-3-642-00939-6_2.
Pieter Vansteenwegen, Wouter Souffriau, Greet Vanden Berghe, and Dirk Van Oudheusden. A
guided local search metaheuristic for the team orienteering problem. European journal of
operational research, 196(1):118–127, 2009b.
Pieter Vansteenwegen, Wouter Souffriau, Greet Vanden Berghe, and Dirk Van Oudheusden.
Iterated local search for the team orienteering problem with time windows. Computers &
Operations Research, 36(12):3281 – 3290, 2009c. ISSN 0305-0548.
DOI https://doi.org/10.1016/j.cor.2009.03.008. URL
http://www.sciencedirect.com/science/article/pii/S030505480900080X. New
developments on hub location.
Apêndice A
Resultado de 16 Conjuntos de instâncias
Tabela A.1 – Conjunto 1 (1-2)
Nome POIs
32-65
32-70
32-73
32-75
32-80
32-85
33-65
33-75
33-80
33-85
33-90
33-95
33-100
33-105
64-45
64-50
64-55
64-60
64-65
64-70
64-75
64-80
66-40
66-45
66-50
66-55
66-60
66-125
66-130
100-30
100-35
100-40
100-45
102-50
102-60
31
31
31
31
31
31
32
32
EXATO
T(s) GAP Ótimo
0,82
0
240
0,77
0
260
0,67
0
265
0,82
0
270
0,57
0
280
1,87
0
285
0,64
0
610
1,13
0
670
GA-VND
T(s) GAP Solução
0,13 0,00
240
0,12 0,00
260
0,1 0,00
265
0,12 0,00
270
0,09 0,00
280
0,12 0,00
285
0,1 0,00
610
0,13 0,00
670
−−
−−
−−
−−
−− −−
−−
32
32
32
32
32
63
63
63
63
63
63
63
63
65
65
65
65
65
65
65
0,89
0,85
0,55
0,93
1,21
1,02
22,16
8,86
25,36
4,47
22,13
39,53
38,24
1,9
1,63
2,75
1,67
2,2
44,86
109,46
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
740
770
790
800
800
816
876
960
1062
1116
1170
1224
1284
570
645
715
825
910
1665
1675
0,14 0,00
0,14 0,00
0,15 0,00
0,11 0,00
0,11 0,00
0,34 0,00
0,57 0,00
0,49 0,00
0,58 0,00
0,68 2,15
0,79 0,00
0,74 8,33
0,76 1,87
0,28 0,00
0,29 0,00
0,32 0,00
0,34 0,00
0,37 0,00
0,74 0,60
0,9 1,19
740
770
790
800
800
816
876
960
1062
1092
1170
1122
1260
570
645
715
825
910
1655
1655
−−
−−
−−
−−
−− −−
−−
99
99
99
101
101
1,04
1,65
2,8
0,57
0,87
0
0
0
0
0
241
299
367
181
243
0,11 0,00
0,14 0,00
0,1 0,00
0,07 0,00
0,08 0,00
241
299
367
181
243
40
Apêndice
41
Tabela A.2 – Conjunto 2 (2-3)
Nome POIs
EXATO
GA-VND
T(s) GAP ótimo
T(s) GAP Solução
32-65
31
0,61
0
240
0,18 0,00
240
32-70
31
1,08
0
260
0,21 0,00
260
32-73
31
1,28
0
265
0,19 0,00
265
32-75
31
1,5
0
270
0,2 0,00
270
32-80
31
0,86
0
280
0,22 0,00
280
32-85
31
1,53
0
285
0,18 0,00
285
33-65
32
0,82
0
610
0,2 0,00
610
33-75
32
1,24
0
670
0,18 0,00
670
33-80
32
2,84
0
710
0,19 0,00
710
33-85
32
0,95
0
740
0,21 0,00
740
33-90
32
0,77
0
770
0,2 0,00
770
33-95
32
0,84
0
790
0,22 0,00
790
33-100
32
2,74
0
800
0,19 0,00
800
33-105
32
1,07
0
800
0,23 0,00
800
64-45
63
2,46
0
816
0,35 0,00
816
64-50
63
4,9
0
870
0,4 0,00
870
64-55
63
8,25
0
960
0,69 2,50
936
64-60
63
4,6
0
1062
0,67 1,69
1044
64-65
63
9,05
0
1116
1,12 2,15
1092
64-70
63
66,42
0
1170
1,24 0,00
1170
64-75
63
11,91
0
1218
1,09 0,00
1218
64-80
63
58,03
0
1284
1,3 0,00
1284
66-40
65
1,19
0
570
0,23 0,00
570
66-45
65
1,49
0
645
0,31 0,00
645
66-50
65
1,57
0
715
0,36 0,00
715
66-55
65
1,73
0
825
0,49 0,00
825
66-60
65
3,08
0
910
0,58 0,00
910
66-125
65
82,02
0
1665
1,34 0,00
1665
66-130
65
68,03
0
1675
1,36 0,00
1675
100-30
99
0,6
0
173
0,21 0,00
173
100-35
99
0,86
0
241
0,22 0,00
241
100-40
99
0,8
0
299
0,22 0,00
299
100-45
99
1,26
0
367
0,25 0,00
367
102-50 101
0,37
0
181
0,16 0,00
181
102-60 101
0,47
0
243
0,18 0,00
243
Apêndice
42
Tabela A.3 – Conjunto 3 (5-3)
Nome POIs
EXATO
T(s)
GA-VND
GAP ótimo
T(s) GAP Solução
32-65
31
1,3
0
240
0,33 0,00
240
32-70
31
1,66
0
260
0,33 0,00
260
32-73
31
1,3
0
265
0,36 0,00
265
32-75
31
0,89
0
270
0,37 0,00
270
32-80
31
1,47
0
280
0,37 0,00
280
32-85
31
1,74
0
285
0,44 0,00
285
33-65
32
2,11
0
610
0,37 0,00
610
33-75
32
1,36
0
670
0,39 0,00
670
33-80
−−
−−
−−
−−
−− −−
−−
33-85
32
0,88
0
740
0,41 0,00
740
33-90
32
2,17
0
770
0,46 0,00
770
33-95
32
2,35
0
790
0,44 0,00
790
33-100
32
4,71
0
800
0,45 0,00
800
33-105
32
1,18
0
800
0,47 0,00
800
64-45
63
2,39
0
816
0,66 0,00
816
64-50
63
7,56
0
870
0,8 0,00
870
64-55
63
21,82
0
960
1,25 0,00
960
64-60
63
3,98
0
1062
1,73 0,00
1062
64-65
63
11,75
0
1116
1,85 2,15
1092
64-70
63
183,81
0
1170
1,89 0,00
1170
64-75
63
7,16
0
1218
2,06 0,00
1218
64-80
63
161,62
0
1284
2,4 3,27
1242
66-40
65
2,06
0
570
0,45 0,00
570
66-45
65
3,16
0
645
0,56 0,00
645
66-50
65
3,92
0
715
0,78 0,00
715
66-55
65
5,83
0
825
1,04 0,00
825
66-60
65
3,98
0
910
1,04 0,00
910
66-125
65
144,12
0
1665
2,83 0,60
1655
66-130
65
163,06
0
1675
2,81 2,99
1625
100-30
99
0,56
0
173
0,35 0,00
173
100-35
99
1,14
0
241
0,4 0,00
241
100-40
99
0,95
0
299
0,38 0,00
299
100-45
99
1,45
0
367
0,47 0,00
367
102-50
101
0,35
0
181
0,27 0,00
181
102-60
101
0,61
0
243
0,29 0,00
243
Apêndice
43
Tabela A.4 – Conjunto 4 (3-4)
Nome POIs
EXATO
T(s)
GA-VND
GAP Ótimo
T(s) GAP Solução
32-65
31
1,05
0
240
0,24 0,00
240
32-70
31
0,52
0
260
0,29 0,00
260
32-73
31
1,32
0
265
0,31 0,00
265
32-75
31
0,98
0
270
0,3 0,00
270
32-80
31
2,23
0
280
0,36 0,00
280
32-85
31
1,61
0
285
0,35 0,00
285
33-65
32
1,18
0
610
0,31 0,00
610
33-75
32
0,92
0
670
0,33 0,00
670
33-80
32
0,75
0
710
0,29 0,00
710
33-85
32
0,92
0
740
0,36 0,00
740
33-90
32
1,11
0
770
0,42 0,00
770
33-95
32
1,2
0
790
0,39 0,00
790
33-100
32
2,05
0
800
0,46 0,00
800
33-105
32
1,43
0
800
0,42 0,00
800
64-45
63
2,65
0
816
0,5 0,00
816
64-50
63
9,48
0
858
0,68 0,00
858
64-55
63
4,57
0
954
0,65 0,00
954
64-60
63
13,03
0
1062
0,86 0,00
1062
64-65
63
9,16
0
1116
1,15 0,00
1116
64-70
63
23,57
0
1170
1,27 0,00
1170
64-75
63
15,25
0
1218
1,67 0,00
1218
64-80
63
9,25
0
1284
1,73 0,00
1284
66-40
65
1,02
0
570
0,44 0,00
570
66-45
65
1,53
0
645
0,48 0,00
645
66-50
65
2,58
0
715
0,54 0,00
715
66-55
65
3,3
0
825
0,6 0,00
825
66-60
65
4,86
0
910
0,62 0,00
910
66-125
65
200,55
0
1665
2,44 0,00
1665
66-130
65
6545,62
0
1675
2,82 5,97
1575
100-30
99
−−
−−
−−
−− −−
−−
100-35
99
0,83
0
241
0,44 0,00
241
100-40
99
0,94
0
299
0,46 0,00
299
100-45
99
1,09
0
367
0,48 0,00
367
102-50
101
0,65
0
181
0,34 0,00
181
102-60
101
0,75
0
243
0,39 0,00
243
Apêndice
44
Tabela A.5 – Conjunto 5 (6-4)
Nome POIs
EXATO
T(s)
GA-VND
GAP Ótimo
T(s) GAP Solução
32-65
31
1,31
0
240
0,92 0,00
240
32-70
31
1,05
0
260
1,05 0,00
260
32-73
31
1,7
0
265
1,11 0,00
265
32-75
31
15,69
0
270
1,09 0,00
270
32-80
31
0,92
0
280
1,24 0,00
280
32-85
31
1,91
0
285
1,33 0,00
285
33-65
32
1,16
0
610
0,9
0,00
610
33-75
32
1,06
0
670
1,34 0,00
670
33-80
32
1,45
0
710
1,14 0,00
710
33-85
32
1,09
0
740
1,31 0,00
740
33-90
32
1,65
0
770
1,19 0,00
770
33-95
32
29,86
0
790
1,37 0,00
790
33-100
32
2,68
0
800
1,67 0,00
800
33-105
32
2,73
0
800
1,58 0,00
800
64-45
63
4,52
0
816
1,37 0,00
816
64-50
63
22,11
0
858
2,12 0,00
858
64-55
63
17,98
0
954
3,14 0,00
954
64-60
63
5,08
0
1062
3,29 0,00
1062
64-65
63
5,28
0
1116
4,39 0,00
1116
64-70
63
193,87
0
1170
6,15 0,00
1170
64-75
63
82,21
0
1218
5,7
0,00
1218
64-80
63
56,25
0
1284
5,43 0,00
1284
66-40
65
1,21
0
570
0,89 0,00
570
66-45
65
2,46
0
645
0,9
0,00
645
66-50
65
1,94
0
715
1,29 0,00
715
66-55
65
6,17
0
825
1,64 0,00
825
66-60
65
5,05
0
910
1,84 0,00
910
66-125
65
154,77
0
1665
7,38 1,50
1640
66-130
65
4429,88
0
1675
8,75 0,60
1665
100-30
99
0,58
0
200
0,71 13,50
173
100-35
99
0,73
0
241
0,70 0,00
241
100-40
99
0,87
0
299
0,75 0,00
299
100-45
99
1,25
0
367
0,72 0,00
367
102-50
101
0,59
0
207
0,56 12,56
181
102-60
101
0,69
0
243
0,64 0,00
243
Apêndice
45
Tabela A.6 – Conjunto 6 (10-4)
EXATO
GA-VND
Nome
POIs
64-75
63
179,74
0
64-80
63
223,81
66-125
65
66-130
T(s)
GAP Ótimo
T(s)
GAP Solução
1218
34,1
0,00
1218
0
1284
35,86 0,00
1284
212,97
0
1665
37,69 0,00
1665
65
12883,23
0
1675
45,89 3,69
1630
100-50
99
5,28
0
399
1,11
0,00
399
100-60
99
5,25
0
504
1,63
0,00
504
100-70
99
12,09
0
590
2,63
0,00
590
100-80
99
13,05
0
652
6,46
0,00
652
100-90
99
44,67
0
725
11,99 0,00
725
100-100 −−
−−
−−
−−
−−
−−
−−
100-110
99
85,44
0
835
26,06 0,00
835
100-120
99
506,92
0
886
34,94 0,00
886
100-130 −−
−−
−−
−−
−−
−−
−−
100-140
99
982,87
0
1013
36,17 0,00
1013
100-150
99
2042,93
0
1056
51,7
0,00
1056
100-160
99
3370,39
0
1114
55,98 0,00
1114
100-170
99
594,78
0
1164
66,46 0,00
1164
100-180
99
3081,12
0
1198
73,85 0,00
1198
100-190
99
2937,19
0
1229
77,66 0,00
1229
100-200
99
9137,17
0
1257
89,66 0,00
1257
100-210
99
12837,43 0,00
1281
107,05 0,00
1281
100-240
99
35780,86 19,22 1055
126,07 0,00
1306
Apêndice
46
Tabela A.7 – Conjunto 7 (10-5)
EXATO
GA-VND
Nome
POIs
64-75
63
1444,23
0
1218
58,59 0,00
1218
64-80
63
34,08
0
1284
65,44 0,00
1284
66-125
65
235,82
0
1665
95,45 0,00
1665
66-130
65
1066,1
0
1675
95,91 0,90
1660
100-50
99
3,58
0
393
1,56
0,00
393
100-60
99
5,82
0
504
1,91
0,00
504
100-70
−−
−−
−−
−−
−−
−−
−−
100-80
99
12
0
652
6,83
0,00
652
100-90
99
15,05
0
725
13,96 0,00
725
100-100
99
65,26
0
774
33,12 0,00
774
100-110
99
25,23
0
835
34,69 0,00
835
100-120
99
635,95
0
886
69,78 1,02
877
100-130 −−
−−
−−
−−
−−
−−
−−
100-140
99
592,88
0
1013
96,59 0,00
1013
100-150
99
3895,22
0
1049
136,28 0,00
1049
100-160
99
911,95
0
1114
157,63 0,00
1114
100-170
99
15902,8
0
1164
162,29 0,00
1164
100-180
99
1483,2
0
1193
265,13 3,52
1151
100-190
99
4855,93
0
1226
226,85 0,24
1223
100-200
99
3670,41
0
1253
234,8 0,00
1253
100-210
99
8613,88
0
1281
222,36 0,00
1281
100-240
99
36031,78 13,37 1121
339,73 0,00
1294
T(s)
GAP Ótimo
T(s)
GAP Solução
Apêndice
47
Tabela A.8 – Conjunto 8 (10-6)
EXATO
GA-VND
Nome
POIs
64-75
63
837,06
0
1218
80,62 0,00
1218
64-80
63
54,72
0
1284
86,49 0,00
1284
66-125
65
264,12
0
1660
135,71 3,01
1610
66-130
65
949,17
0
1670
140,18 0,90
1655
100-50
99
2,28
0
436
2,29
5,50
412
100-60
99
4,64
0
504
2,58
0,00
504
100-70
99
−−
−−
−−
−−
−−
−−
100-80
99
8,40
0
652
4,59
0,00
652
100-90
99
32,3
0
725
11,53 0,00
725
100-100 −−
−−
−−
−−
−−
−−
−−
100-110
99
53,51
0
835
40,81 0,00
835
100-120
99
201,83
0
886
72,95 0,00
886
100-130
99
399,39
0
943
82,22 0,00
943
100-140
99
686,93
0
1013
104,39 0,00
1013
100-150
99
1588,99
0
1048
136,46 0,00
1048
100-160
99
208,54
0
1114
185,45 0,00
1114
100-170
99
2180,91
0
1164
216,62 0,00
1164
100-180 −−
−−
−−
−−
−−
−−
−−
100-190
99
653,78
0
1226
345,18 0,00
1226
100-200
99
2479,8
0
1253
322,82 0,00
1253
100-210
99
14347,4
0
1281
322,36 0,00
1281
100-240
99
36,02
10,80 1165
529,87 0,00
1306
T(s)
GAP Ótimo
T(s)
GAP Solução
Apêndice
48
Tabela A.9 – Conjunto 9 (12-4)
EXATO
GA-VND
Nome
POIs
64-75
63
453,71
0
1218
59,27 0,49
1212
64-80
63
48,07
0
1284
58,06 0,00
1284
66-125
65
66,08
0
1665
74,7
0,00
1665
66-130
65
5563,48
0
1675
73,65 0,00
1675
100-50
99
5,4
0
399
1,63
0,00
399
100-60
99
6,94
0
504
2,48
0,00
504
100-70
99
22,94
0
590
4,44
0,00
590
100-80
99
51,94
0
652
10,29 0,00
652
100-90
99
158,14
0
725
19,91 0,00
725
100-100
99
159,35
0
774
25,92 0,00
774
100-110
99
683,71
0
835
54,91 0,00
835
100-120
99
688,41
0
886
58,47 0,00
886
100-130
99
336,11
0
953
72,47 0,00
953
100-140
99
371,52
0
1013
79,51 0,00
1013
100-150
99
695,24
0
1056
108,37 0,00
1056
100-160
99
4532,44
0
1114
104,44 0,00
1114
−−
−−
−−
−−
−−
−−
100-170 −−
T(s)
GAP Ótimo
T(s)
GAP Solução
100-180
99
2872,87
0
1198
138,27 0,00
1198
100-190
99
11846,16
0
1229
139,36 0,00
1229
100-200
99
1402,3
0
1257
156,36 0,00
1257
100-210
99
17691,89
0
1281
178,29 0,70
1272
100-240
99
−−
−−
−−
−−
−−
−−
Apêndice
49
Tabela A.10 – Conjunto 10 (12-5)
EXATO
GA-VND
Nome
POIs
64-75
63
379,1
0
1218
112,68 0,00
1218
64-80
63
59,12
0
1284
118,43 1,87
1260
66-125
65
263,27
0
1665
180,78 0,00
1665
66-130
65
3710,06
0
1675
167,6 0,00
1675
100-50
99
7,1
0
393
1,93
0,00
393
100-60
99
5,26
0
504
2,95
0,00
504
100-70
99
7,46
0
590
5,73
0,00
590
100-80
99
15,63
0
652
13,43 0,00
652
100-90
99
20,56
0
725
25,44 0,00
725
100-100
99
90,56
0
774
55,96 0,00
774
100-110
99
338,51
0
835
65,02 0,00
835
100-120
99
1250,23
0
886
96,74 0,00
886
100-130
99
1018,44
0
943
142,04 0,00
943
100-140
99
651,86
0
1013
198,91 0,00
1013
100-150
99
3406,3
0
1049
237,33 0,00
1049
100-160
99
1785,39
0
1114
239,54 0,00
1114
100-170
99
19622,96
0
1164
444,81 4,98
1106
100-180
99
5926,57
0
1193
350,97 0,00
1193
100-190
99
15746,72
0
1226
388,31 0,00
1226
100-200
99
8267,36
0
1253
416,15 1,36
1236
100-210
99
11869,06
0
1281
472,68 0,00
1281
100-240
99
36029,03 11,41 1157
595,57 0,00
1306
T(s)
GAP Ótimo
T(s)
GAP Solução
Apêndice
50
Tabela A.11 – Conjunto 11 (12-6)
EXATO
GA-VND
Nome
POIs
64-75
63
553,27
0
1218
145,40 0,00
1218
64-80
63
132,59
0
1284
146,98 0,00
1284
66-125
65
35,12
0
1665
223,71 3,00
1615
66-130
65
2522,58
0
1675
267,16 0,30
1670
100-50
99
2,18
0
439
2,74
6,15
412
100-60
99
3,94
0
504
2,94
0,00
504
100-70
−−
−−
−−
−−
−−
−−
−−
100-80
99
37,29
0
652
12,27 0,00
652
100-90
99
53,13
0
725
19,82 0,00
725
100-100
99
74,13
0
769
43,03 0,00
769
100-110
99
124,9
0
835
64,86 0,00
835
100-120
99
392,48
0
886
97,26 0,00
886
100-130
99
258,26
0
943
134,3 0,00
943
100-140
99
3439,55
0
1013
230,96 0,00
1013
100-150
99
2359,17
0
1049
239,76 0,00
1049
100-160
99
908,92
0
1114
290,62 0,00
1114
100-170
99
3564,71
0
1164
369,75 0,00
1164
100-180
99
9848,76
0
1193
435,61 0,00
1193
100-190
99
5354,33
0
1226
545,45 0,00
1226
100-200
99
1446,36
0
1253
738,76 0,00
1253
100-210
99
36018,37 5,78
1207
716,65 0,00
1281
100-240
99
36012,02 18,99 1058
837,44 0,00
1306
T(s)
GAP Ótimo
T(s)
GAP Solução
Apêndice
51
Tabela A.12 – Conjunto 12 (15-4)
EXATO
GA-VND
Nome
POIs
64-75
63
393,36
0
1218
130,66 0,00
1218
64-80
63
112,56
0
1284
147,38 0,00
1284
66-125
65
604,41
0
1665
166,24 1,80
1635
66-130
65
2687,39
0
1675
168,81 0,00
1675
100-50
99
3,98
0
399
1,72
0,00
399
100-60
99
6,26
0
504
1,94
0,00
504
100-70
99
15,75
0
590
3,30
0,00
590
100-80
99
17,41
0
652
9,92
0,00
652
100-90
99
133,82
0
725
39,66 0,00
725
100-100
99
68,94
0
774
30,86 0,00
774
100-110
99
185,57
0
835
108,03 0,00
835
100-120
99
967,24
0
886
134,57 0,00
886
100-130
99
896,34
0
953
155,06 0,00
953
100-140
99
1331,46
0
1013
177,92 0,00
1013
100-150
99
1761,93
0
1056
216,73 0,00
1056
100-160
99
3342,1
0
1114
222,68 0,00
1114
100-170
99
1110,76
0
1164
268,33 0,69
1156
100-180
99
1630,79
0
1198
299,16 0,00
1198
100-190
99
7029,65
0
1229
362,8 0,00
1229
100-200
99
3606,65
0
1257
377,75 0,00
1257
100-210
99
26045,61
0
1281
420,13 0,00
1281
100-240
99
36018,28 4,59 1246
514,43 0,00
1306
T(s)
GAP Ótimo
T(s)
GAP Solução
Apêndice
52
Tabela A.13 – Conjunto 13 (15-5)
EXATO
GA-VND
Nome
POIs
64-75
63
516,44
0
1218
246,08 0,00
1218
64-80
63
242,87
0
1284
275,67 0,00
1284
66-125
65
842,46
0
1665
331,59 0,00
1665
66-130
65
186,64
0
1675
348,04 0,00
1675
100-50
99
2,96
0
393
2,38
0,00
393
100-60
99
12,51
0
504
3,19
0,00
504
100-70
99
9,44
0
590
3,21
0,00
590
100-80
99
18,53
0
652
7,89
0,00
652
100-90
99
31,78
0
725
22,16
0,00
725
100-100
99
110,68
0
774
75,01
0,00
774
100-110
99
383,32
0
835
119,87 0,00
835
100-120
99
471,68
0
886
144,66 0,00
886
100-130
99
991,93
0
943
250,14 0,00
943
100-140
99
735,11
0
1013
369,1
0,00
1013
100-150
99
2106,06
0
1049
462,97 0,00
1049
100-160
99
1480,02
0
1114
523,83 0,00
1114
100-170
99
5486,97
0
1164
600,5
0,00
1164
100-180
99
8317,14
0
1193
1038,03 0,00
1193
100-190
99
15768,61
0
1226
978,51 0,00
1226
100-200
99
6892,62
0
1253
772,14 0,00
1253
100-210
99
7250,09
0
1281
855
0,00
1281
100-240
99
36026,57 3,91 1255
1290
0,00
1306
T(s)
GAP Ótimo
T(s)
GAP Solução
Apêndice
53
Tabela A.14 – Conjunto 14 (15-6)
EXATO
GA-VND
Nome
POIs
64-75
63
593,6
0
1218
272,96 0,00
1218
64-80
63
147,56
0
1284
295,01 0,00
1284
66-125
65
466,66
0
1665
420,96 4,50
1590
66-130
65
6636,75
0
1675
452,41 0,00
1675
100-50
99
3,87
0
435
3,31
5,29
412
100-60
99
8,26
0
504
3,49
0,00
504
100-70
−−
−−
−−
−−
−−
−−
−−
100-80
99
17,46
0
652
10,22
0,00
652
100-90
99
24,79
0
725
23,47
0,00
725
100-100
99
144,09
0
769
65,3
0,00
769
100-110
99
290,78
0
835
102,44 0,00
835
100-120
99
286,51
0
886
169,33 0,00
886
100-130
99
171,82
0
943
267,99 0,00
943
100-140
99
5360,33
0
1013
376,75 0,00
1013
100-150
99
2287,8
0
1049
559,24 0,00
1049
100-160
99
931,95
0
1114
653,23 0,00
1114
100-170
99
1540,08
0
1164
827,08 0,00
1164
100-180
99
5355,67
0
1193
1056,96 0,00
1193
100-190
99
765,78
0
1226
1348,25 0,00
1226
100-200
99
1249,43
0
1253
1259,27 0,00
1253
100-210
99
11653,07
0
1281
1272
0,00
1281
−−
−−
−−
−−
−−
−−
100-240 −−
T(s)
GAP Ótimo
T(s)
GAP Solução
Apêndice
54
Tabela A.15 – Conjunto 15 (15-8)
EXATO
Nome
GA-VND
POIs
T(s)
GAP
Ótimo
T(s)
GAP Solução
100-100
99
61,1
0
750
27,56
0,00
750
100-110
−−
−−
−−
−−
−−
−−
−−
100-120
−−
−−
−−
−−
−−
−−
−−
100-130
−−
−−
−−
−−
−−
−−
−−
100-140
−−
−−
−−
−−
−−
−−
−−
100-150
99
818,68
0
1044
308,78
0,00
1044
100-160
99
1022,16
0
1114
405,03
0,00
1114
100-170
99
1001,21
0
1164
567,23
0,00
1164
100-180
99
4498,03
0
1188
915,49
0,00
1188
100-190
−−
−−
−−
−−
−−
−−
−−
100-200
99
4783,1
0
1252
1282,62 0,08
1251
100-210
99
1705,98
0
1281
1585,05 0,00
1281
100-240
99
36015,91 11,017 1155
2715,62 0,00
1298
Apêndice
55
Tabela A.16 – Conjunto 16 (15-10)
EXATO
Nome
GA-VND
POIs
T(s)
GAP Ótimo
T(s)
GAP Solução
100-140
99
−−
−−
−−
−−
−−
−−
100-150
99
1379,33
0
1038
158,26
0,00
1038
100-160
99
473,13
0
1114
217,47
0,00
1114
100-170
99
411,64
0
1164
572,36
0,00
1164
100-180
99
3308,63
0
1182
691,8
0,00
1182
100-190
99
30492,63 10,29 1090
748,15
0,00
1215
100-200
99
1371,35
0,00
1251
922,21
0,00
1251
100-210
99
36016,07
9,44
1151
1636,09 0,00
1271
100-240
99
36002,1
14,55 1116
2254,52 0,00
1306
Apêndice B
Coordenadas
Tabela B.1 – Coordenadas Sertão
Código
Longitude
Latitude
1
-9.6218825445163
2
-9.63009767944081 -37.78477457681713
3
-9.623580555555556 -37.753575
4
-9.671161111111111 -37.65946388888889
5
-9.624969444444446 -37.75410277777777
6
-9.671443446395447 -37.66044506309587
7
-9.524379113521995 -37.880862433312075
8
-9.422923814281850 -38.18364442418620
9
-9.749994444444443 -37.44783055555556
10
-9.603938545397204 -37.768763344152475
11
-9.608838761838351 -37.76265044543369
12
-9.749476094042024 -37.432415258772345
13
-9.372027243841272 -37.99420413591547
14
-9.393643391461657 -38.00307691225499
15
-9.497524579831913 -37.829204026413564
16
-9.497664679739325 -37.82988557291119
56
-37.79669725119823
Apêndice
57
Tabela B.2 – Coordenadas Maceió
Código
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
Longitude
Latitude
-9.69605517159951 -35.78017068629510
-9.689629830288220 -35.7740021361158
-9.663804940803400 -35.70506599504110
-9.663231211607800 -35.69554174977270
-9.645197409785890 -35.69911006554310
-9.639008218137070 -35.69823170529150
-9.616385251873340 -35.6892400574223
-9.592104374645870 -35.6684891874493
-9.587708856914540 -35.66379677251350
-9.57586287770571 -35.65513227160370
-9.565450491957560 -35.64521684335300
-9.530799943419160 -35.60425662092510
-8.933294444444442 -35.165927777777775
-9.672125
-35.72384722222223
-9.661745366641126 -35.729240324268474
-9.652174154037438 -35.69825350608212
-9.630876729523333 -35.69777865579632
-9.667013736485316 -35.74357821503382
-9.66153611263287 -35.696510647792564
-9.670681602167221 -35.71816701723714
Apêndice C
Matriz de distância Google
De i (Primeira coluna), para j (primeira linha)
Tabela C.1 – Matriz Sertão
1
1
2
5
3
13
2
3
7
8
9
10
11
12
13
14 15 16
5
13 109 14 109 38
68
99
9
10
94
40
41 16 17
12 108 13 108 37
67
98
8
9
93
39
40 16 16
70
99
9
6
95
42
43 19 19
12
4
109
4 108 107 108
5
14
13
9
110
6 108 107 108
1
5
6
9
109 40
109
1
112 142 114 104 103 110 114 116 92 92
110 41
109
71 100 10
7
96
43
45 20 21
112 142 114 104 103 110 114 116 92 92
7
37
36
39 112 41 112
8
70
69
72 145 73 145 67
9
99
98
99 116 101 116 103 133
10
8
7
9
105 10 105 35
65
95
11
8
8
6
106
67
96
6
12 92
91
92 109 94 109 96 126
7
89
13 41
40
43 116 45 116 38
31 106 38
38 102
14 40
39
43 116 44 116 37
34 106 38
37 101
8
15 16
15
18
92
20
92
21
51
82
13
13
78
23
25
16 17
16
19
92
20
92
21
51
82
14
14
78
23
25
8
64 102 34
106 37
135 67
58
96
34
98
36
38 21 21
67 131 33
34 54 54
94
10 105 107 83 83
3
91
37
39 14 15
92
39
41 16 16
87
98 100 76 76
8
25 25
24 25
1
1
Apêndice
59
Tabela C.2 – Matriz Maceió
1
1
2
2
3
5
18 20 25 27 32 38 38 40 43 50 168 15 15 24 29 13 21 16
5
5
6
7
8
9
10 11 12 13 14 15 16 17 18 19 20
16 18 23 25 30 36 36 38 41 49 166 14 14 22 28 12 19 14
3 21 17
4 23 19
4
2
2
5 25 21 10
8
9
14 21 21 23 26 33 151 6
12
6
12 13
3
5
5
7
12 18 19 21 23 31 149 8
14
4
10 16
1
8
2
7
13 13 15 18 26 143 16 14
3
4
17
7
14
5
11 12 14 16 24 142 19 16
9
3
19 13 16
6
22 19 21
8
6 27 23 14 14
7
7 30 26 19 19 13 11
7
7
9
12 19 137 22 19 15
4
6
9
17 134 27 25 21 12 28 24 26
4
7
15 133 28 25 21 12 28 25 27
4
11 129 30 27 23 14 30 27 29
8 36 32 25 25 19 16
7
9 36 32 25 25 19 16
8
4
10 38 34 27 27 21 18 10
6
5
11 41 37 30 30 24 22 13
9
8
4
10 127 33 30 26 17 33 30 32
12 50 46 39 39 32 30 21 18 16 13 10
122 41 39 34 26 41 38 40
13 168 164 156 157 150 148 139 136 134 131 128 122
14 16 12
9
159 157 152 144 159 156 158
11 14 16 20 26 26 28 31 39 157
8
15 19 15 12 14 15 16 21 27 27 29 32 40 157 10
16 26 22
7
15 18
12
6
15 19 10 14
9
4
2
3
8
15 15 17 20 27 145 13 15
6
17 27 22 15 15
9
7
5
10 10 13 15 23 141 18 16 11
9
18
12
18 15 17
18 15 10 12 14 16 18 23 28 29 31 33 41 159 10
6
18 20
19 24 20
3
1
5
11 18 18 20 23 31 148 9
15
3
20 18 14
6
9
13 15 20 26 27 29 31 39 157 3
9
12 18 11
6
4
9
15 11
16
8
9