ROTEIRIZAÇÃO
Método do vizinho mais próximo
Este método consiste em, partindo de um ponto zero, procurar o ponto de
chegada ou entrega mais próximo (menor distância). Partindo do ponto
anterior, procurar em uma tabela ou possuir a informação com a distância
em quilometragens ou metros do destino mais próximo do atual.
A tabela usada relaciona as distâncias em quilômetros entre os destinos
que se deve passar, todos os pontos estão anotados na margem
superior e na lateral esquerda. Usamos somente uma das metades da
tabela, pois completá-la inteira seria repetir as informações entre as
distâncias.
Exemplo: Partindo do ponto zero, para qual dos pontos se deve partir com a
menor distância?
1
2
0
1
0
1
2
3
4
5
6
-
6
11
7
8
12
4
-
10
9
11
15
10
-
4
7
9
11
-
3
7
7
-
4
6
-
9
3
2
0
Fábrica
3
4
4
6
5
5
Repare que a menor distância é entre o ponto zero e o ponto seis, que
é de 4km.
Logo, vamos do ponto zero em direção ao ponto
seis.
1
2
3
0
0
1
2
3
4
5
0
1
2
3
4
5
6
-
6
11
7
8
12
4
-
10
9
11
15
10
-
4
7
9
11
-
3
7
7
-
4
6
-
9
4
6
Agora, estamos no ponto de entrega seis. Para qual o ponto devemos
partir? Qual o ponto com a menor distância do ponto seis (exceto,
obviamente o zero)?
5
1
Devemos certamente ir ao ponto quatro, que possui
a menor distância do ponto seis (6km).
2
3
0
0
1
2
3
4
5
0
1
2
3
4
5
6
-
6
11
7
8
12
4
-
10
9
11
15
10
-
4
7
9
11
-
3
7
7
-
4
6
-
9
4
6
Agora, estamos no ponto de entrega quatro. Para qual o ponto devemos
partir? Qual o ponto com a menor distância (exceto, obviamente os
pontos zero e seis)?
5
O ponto com a menor distância do ponto quatro é o ponto três: com 3km.
1
0
1
2
3
4
5
0
1
2
3
4
5
6
-
6
11
7
8
12
4
-
10
9
11
15
10
-
4
7
9
11
-
3
7
7
-
4
6
-
9
2
3
0
4
6
Agora, estamos no ponto de entrega três. Para onde vamos: para o
ponto um, dois ou cinco?
5
A distância entre três e um é de 9km, entre três e dois é de 4km,
entre três e cinco é de 7km. Logo, devemos partir para o ponto dois.
1
0
1
2
3
4
5
0
1
2
3
4
5
6
-
6
11
7
8
12
4
-
10
9
11
15
10
-
4
7
9
11
-
3
7
7
-
4
6
-
9
2
3
0
4
6
Agora, estamos no ponto de entrega dois. Para qual o ponto devemos
partir, 1 ou 5?
5
A distância entre dois e um é de 10km, entre dois e cinco é de 9km.
Logo, devemos partir para o ponto cinco.
1
0
1
2
3
4
5
0
1
2
3
4
5
6
-
6
11
7
8
12
4
-
10
9
11
15
10
-
4
7
9
11
-
3
7
7
-
4
6
-
9
De cinco, partimos para o ponto 1.
2
3
0
4
6
5
Chegando ao ponto 1, já cumprimos todas as entregas e retornamos ao
ponto de partida, o ponto zero.
1
0
1
2
3
4
5
0
1
2
3
4
5
6
-
6
11
7
8
12
4
-
10
9
11
15
10
-
4
7
9
11
-
3
7
7
-
4
6
-
9
2
3
0
4
6
5
1
2
3
4
5
6
-
6
11
7
8
12
4
-
10
9
11
15
10
-
4
7
9
11
-
3
7
7
-
4
6
-
9
4
5
2
3
0
1
m
4K
4
Método do Vizinho Mais Próximo
Rota = (0, 6, 4, 3, 2, 5, 1, 0)
5
9 Km
3
3 Km
3
6 m
K
15
2
4 4
Km
1
1
7
6 Km
0
0
6
2
6 Km
Distância = (4 + 6 + 3 + 4 + 9 + 15 + 6) = 47km
5
Observe que passamos duas vezes pelo ponto quatro. Neste método,
escolhemos o ponto vizinho mais próximo de onde estamos, entretanto
podem ocorrer problemas na otimização como ocorreu acima. Para evitar
este tipo de problema, podemos optar por outro método, como veremos.
ROTEIRIZAÇÃO
Método da inserção
Este método consiste em observar todos os pontos por onde se deve
passar e tentar formar uma figura poligonal, ligando-os, sem cruzar o
mesmo ponto mais de uma vez.
Você consegue imaginar a figura
poligonal que pode ser formada?
1
2
3
0
4
6
5
Se não conseguir, ligue três
pontos quaisquer e vá inserindo
os outros pontos um a um,
“abrindo” a figura formada (daí o
nome deste método ser método
da inserção).
ROTEIRIZAÇÃO
Método da inserção
1
0
1
0
1
2
3
4
5
6
-
6
11
7
8
12
4
-
10
9
11
15
10
-
4
7
9
11
-
3
7
7
-
4
6
-
9
2
3
4
5
1
2
3
0
4
6
5
3
2
1
1
2
2
3
3
0
0
4
4
6
6
5
5
ROTEIRIZAÇÃO
Método da inserção
4
1
5
1
2
2
3
3
0
0
4
4
6
6
5
1
6
2
3
0
4
6
5
5
ROTEIRIZAÇÃO
Método da inserção
1
2
3
0
4
6
5
Método da inserção mais próxima
Rota = (0, 6, 5, 4, 3, 2, 1, 0)
Distância = (4 + 9 + 4 + 3 + 4 + 10 + 6) = 40km
Observe que por este método, encurtamos a distância em 7 km.