Qual o Caminho mais rápido com R? O Problema do Delivery de Sushi – Pizza. parte 1 de 3

November 23, 2016 no comments Posted in R para não Programadores

Iremos explorar um assunto interessante, como calcular o caminho que leva menos tempo saindo de local passando por outros e retornando ao local de origem.

Esse problema esta relacionado ao nosso capítulo sobre mapas de uma forma indireta, não só porque podemos representar rotas entre dois ou mais pontos em um mapa Leaflet, como podemos com R acessar serviços como o Google Maps ou OpenStreetMap e desenvolver uma aplicação “nossa” envolvendo caminhos, tempos e mapas.

Interessou?

Para ser didático o caminho será longo, talvez 3 publicações para não cansar os leitores.

Esse problema me ocorreu a pensar em estratégias para tentar reduzir o tempo de entrega em sistemas de delivery. Em geral as rotas são traçadas em conhecimento da região e muito sentimento, mas como seria um modo “algorítmico” de resolver o problema?

Aviso que esse é tema muito estudado por cientistas da computação e que envolve a busca de caminhos mínimos e otmização, mas como somos “não-programadores“, vamos nos permitir uma solução simples, usaremos de “força-bruta”.

Força-bruta

porque iremos coletar todas as rotas possíveis, somar os seus tempos, e escolher a que for menor. Existem soluções sofisticadas que estão no escopo da Teoria dos Grafos e envolvem os chamados Circuitos Hamiltonianos. Você verá que esse exercício irá oferecer oportunidades interessantes de aprendizado de R e estruturas básicas de programação.

Primeiro vamos explorar as rotas possíveis e relembrar  noções de permutação.

No caso mais simples um entregador sai da loja, vai apenas a um cliente e retorna a loja, certo?

Se usarmos letras para representar os pontos do trajeto podemos usar L(oja) > C(liente)  > L(oja) , ou L > C > L, ou um sistema numerado 1 > 2 > 1. Nesse caso fica claro que não existem variações possíveis, só existe essa sequência  1 > 2 > 1.

Adicionando 2 clientes agora temos mais de um rota possível, vejamos:

  • Rota 1 : Loja > Cliente 1 > Cliente 2 > Loja  ou
  • Rota 2: Loja > Cliente 2 > Cliente 1 > Loja

Supondo que eu sei o tempo de deslocamento entre Loja e Cliente 1 , Cliente 1 e Cliente 2, Cliente 2 e Loja, já podemos pensar em com contabilizar e escolher o que demora menos, mas precisamos organizar melhor esses conceitos para facilitar as nossas contas, uma tabela talvez?

Origem Destino Tempo (minutos)
Loja Cliente 1 10
Cliente 1 Cliente 2 5
Cliente 2 Loja 8

 

E como ficariam as nossas contas?

Tempo 100 + 50 + 80 = 23

Na forma como está colocado as 2 rotas são indiferentes porque assumimos silenciosamente que os tempos de ir de A para B é igual ao de B para A, algo que no trânsito não é verdade.

A nossa tabela deve ter tambem os tempos de volta em cada trecho possível.

Origem Destino Tempo
Loja Cliente 1 10
Cliente 1 Cliente 2 5
Cliente 2 Loja 8
Cliente 1 Loja 8
Cliente 2 Cliente 1 7
Loja Cliente 2 6

Uma situação que pode ser visualizada na figura a seguir.

Diagrama de Rotas Possíveis entre 3 locais

Opa

E agora temos algo mais realista e uma conta simples irá revelar qual a rota é a mais rápida, vejamos:

Rota 1 Tempo Rota 2 Tempo
Loja > Cliente 1 10 Loja > Cliente 2 6
Cliente 1 > Cliente 2 5 Cliente 2 > Cliente 1 7
Cliente 2 > Loja 8 Cliente 1 > Loja 8
23

21

Uma representação bem condensada para todas as distâncias possíveis entre um conjunto de locais quaisquer é uma matriz de adjacências, nela as linhas e colunas são os locais e nas células as distâncias, tempos ou outras grandezas que as relacionem.

Loja

Cliente 1

Cliente 2

Loja

10 8

Cliente 1

8

5

CLiente 2

8 7

A loja de onde partem as entregas é o nosso ponto fixo e as rotas possíveis são todas as permutações entres os destinos das entregas.

Para estimar as possibilidades de rotas em uma entrega para 4 clientes temos que calcular as permutações entre os 4, ou 4! = 4 x 3 x 2 x 1 -> 24 rotas possíveis. Duvida? Vamos verificar.

Análise Combinarória

Esse capítulo não é sobre contagens ou análise combinatória, estamos querendo resolver o problema de nossa loja de delivery, mas estamos vendo que quem odiou esse item na escola agora pode ver um exemplo real da sua utilidade. Outro detalhe importante é que mesmo que o R ou qualquer outro programa ou o Excel realize a conta, sem estudarmos os conceitos e analisar as possibilidades não saberíamos qual a formulação correta a aplicar. Logo se o assunto lhe está parecendo espinhoso ou esquecido nas brumas do passado, que tal recordar um pouqinho sobre análise combinatória?

Mas e o R?  Como ele pode nos ajudar, primeiro no pacote básico temos a função combm, que gera as combinações possíveis de M elementos N a N sem que esses r. Lembram?

Dados 4 elementos quantas combinações possíveis 2 a 2?

combn(1:4,2)
combn(c(“a”, “b”, “c”, “d”) , 2)
pessoas = c(“joão”, “maria”, “pedro”, “leonardo”)
combn( pessoas, 2)

Acima alguns exemplos de como podemos explorar combinações no R, uma sequência “1:4”, um vetor anônimo c(“a”, “b”, “c”, “d”) e um vetor chamado pessoas, o resultado é uma matriz com as combinações possíveis.

Teste no seu console. Eu espero. 🙂

Para mim o resultado é o que está na figura abaixo.

Screen Shot 2016-11-24 at 08.31.34.png

Felizmente, tudo de acordo com a Lei.  Combinações de M objetos N a N é calculado como M!/ ((M-N)! N!)  no caso acima 4! / 2! x 2! = ( 4 x 3 x 2 x 1) / (2 x 1) x (2x 1) = 6.

Se pretendemos usar esse resultado depois, precisamos armazenar o resultado em alguma varíavel, digamos “pares”, faremos assim

 

> pessoas = c(“joão”, “maria”, “pedro”, “leonardo”)
> pares = combn( pessoas, 2)
> pares
[,1] [,2] [,3] [,4] [,5] [,6]
[1,] “joão” “joão” “joão” “maria” “maria” “pedro”
[2,] “maria” “pedro” “leonardo” “pedro” “leonardo” “leonardo”

e porque essa preocupação com variáveis?  

Bem o nome sugere, é algo que esperemos que possa ser utilizado com valores diferentes. Já logo imagino que o vetor “pessoas” não será digitado no meio do nosso script, mas lido de arquivo ou resultado de uma seleção do usário em uma aplicação R/Shiny.

Disse ante que combm retorna um objeto do tipo “matrix” e como podemos verificar o tipo ou a classe de um objeto?  “class”.  Teste.

class(pares)
[1] “matrix”

Esse comando é importante porque a medida que avançamos em R você verá que para cada Classe de objetos existem operações que só podem ser realizadas em um determinado tipo de objeto e que eventualmente teremos que converter um objeto em outro.

Um objeto matriz é acessado por referências as linhas e as colunas assim matriz [ linha, coluna ]. A seguir algumas possibilidades, teste no seu console.

pares[1,1]
[1] “joão”
> pares[1,2:3]
[1] “joão” “joão”
> pares[1,]
[1] “joão” “joão” “joão” “maria” “maria” “pedro”
> pares[,1]
[1] “joão” “maria”
> pares[]
[,1] [,2] [,3] [,4] [,5] [,6]
[1,] “joão” “joão” “joão” “maria” “maria” “pedro”
[2,] “maria” “pedro” “leonardo” “pedro” “leonardo” “leonardo”

O combn retorna os pares formados como colunas, um possiblidade para impressão do resultado.

for ( i in 1:6)
{
cat(i, pares[,i], “\n”)
}
1 joão maria
2 joão pedro
3 joão leonardo
4 maria pedro
5 maria leonardo
6 pedro leonardo
>

Epa!!  Uau!

Aqui esbarramos com a nossa primeira estrutura de loop e de controle de um programa. Falaremos muito mais sobre loops posteriormente, mas veja que é tranquilo.

O comando FOR é uma instrução que automatiza a geração de valores e a execução do que está entre os colchetes { } .

No caso acima o FOR irá gerar valores para variável  “i” como 1, 2,3, 4, 5, 6 e para cada valor gerado, o que está dentro dos colchetes é executado.

Dentro do colchetes um comando para imprimir no console os valores que estão dentro dos parentênsis   cat(i, pares[,i], “\n”), ou seja, o valor do “i”, mais o valor de “pares[,i]”  e uma instrução para pular de linha “\n”.  Experimente retirar o  “,”\n”” e terás algo assim:

for ( i in 1:6)
{
cat(i, pares[,i])
}
1 joão maria2 joão pedro3 joão leonardo4 maria pedro5 maria leonardo6 pedro leonardo

Bem já dispersamos bastante, mas estamos construindo conceitos para programas cada vez mais poderosos.

Retornando ao nosso problema do entregador de sushi, precisamos de uma forma rápida de calcular permutações e para isso recorrer a um pacote extra, o “combinat“.

Nessa altura instalar pacotes não deve ser mais um problema, no RStudio, menu, Tools > Install Packages.

Pacote instalado vamos explorar as permutações.

Outra coisa do base do R para ajudar em nossos exercícios é o que alguns vetores pré-instalados já estão disponíveis, um deles o  “letters”, veja

letters
[1] “a” “b” “c” “d” “e” “f” “g” “h” “i” “j” “k” “l” “m” “n” “o” “p” “q” “r” “s” “t” “u” “v” “w” “x”
[25] “y” “z”

é um vetor, logo podemos referenciar  assim letters[1:3]

letters[1:3]
[1] “a” “b” “c”

Logo,

library(combinat)
permn(letters[1:2])
[[1]]
[1] “a” “b”

[[2]]

[1] “b” “a”

Recordando que usamos o library() para carregar para a memória a biblioteca antes de usar as funções que ela implementa.

Com 3 elementos começa a ficar interessante.

permn(letters[1:3])
[[1]]
[1] “a” “b” “c”

[[2]]
[1] “a” “c” “b”

[[3]]
[1] “c” “a” “b”

[[4]]
[1] “c” “b” “a”

[[5]]
[1] “b” “c” “a”

[[6]]
[1] “b” “a” “c”

Listas?

Pena que o resultado de “permn” é do tipo “list”, assunto que não queria tratar agora, pois são estruturas mais complexas. Listas podem armazenar listas de objetos de qualquer tipo e dependendo da complexidade da lista navegar por elas pode as vezes ser doloroso. 🙂  Sempre prefiro os data frames por sua equivalência com planilhas do Excel.

Ok, mas não precisamos arrancar os cabelos agora. A lista aqui é simples e podemos acessar os valores usando a notação dos colchetes duplos [[ ]] .

Vamos lá. Direto no console do RStudio.

Screen Shot 2016-11-24 at 09.26.58.png

Legal, não?

Usamos a função permn para gerar todas as permutações possíveis de 3 letras, armazenamos os resultados em uma lista chamada “p” e usamos os [[]] para extrair os resultados.

Mas quantas são as permutações possíveis?  Se você reviu a matéria, ja sabem que o número de permutações de 3 elementos é igual ao fatorial de 3, ou 3!, ou 3 x 2 x 1 = 6, mas temos outro meio de saber isso sem ter que fazer essa conta, basta verificar qual é o “tamanho” da lista “p”.

Se lá estão todas as combinações, logo está resolvido. E ai entra em jogo um eterno aliado em nossos scripts, a função “length”, de length em inglês, o comprimento ou tamanho.

Os exemplos abaixo deixam claro.

length(pessoas)
[1] 4
> length(1:5)
[1] 5
> length(letters[1:7])
[1] 7
> pessoas = c(“joão”, “maria”, “pedro”, “leonardo”)
> length(pessoas)
[1] 4

no caso das nossas permutações, quantas podem existir entre 3,4,5 elementos?

length(permn(3))
[1] 6
> length(permn(4))
[1] 24
> length(permn(5))
[1] 120

Em cima outro detalhe interessante, o uso de função dentro de função length( permn())  e podemos ir longe, como em length(permn(c(“joão”, “maria”, “pedro”, “leonardo”))).

Atenção, a função permn gera as combinações possíveis e a length conta o resultado, logo pode ser lenta para se o número de elementos for alto.

Se quiser apenas calcular o fatorial de um número use a função “factorial”, por exemplo para 10 elementos vemos rapidamente que existem 3.628.800 permutações possíveis.

factorial(10)
[1] 3628800

Pronto agora podemos finalmente retornar ao nosso problema original,

uma loja, x clientes, quantas rotas?

clientes <- c(“c1”, “c2”, “c3”)
rotas <- permn(clientes)
length(rotas)
rotas
“c1” “c2” “c3”
“c1” “c3” “c2”
“c3” “c1” “c2”
“c3” “c2” “c1”
“c2” “c3” “c1”
“c2” “c1” “c3”

mas falta ainda componente essencial, para determinar a rota mais rápida precisamos dos tempos de ida e de volta entre as lojas e os clientes. Ou seja as combinações 2 a 2 entre 4 locais, a loja e os 3 clientes.

> locais <- c(“loja”, “c1”, “c2”, “c3”)
> trechos <- combn(locais,2)
> trechos
[,1] [,2] [,3] [,4] [,5] [,6]
[1,] “loja” “loja” “loja” “c1” “c1” “c2”
[2,] “c1” “c2” “c3” “c2” “c3” “c3”

e claro as rotas opostas,

trechos[1:2,]
[,1] [,2] [,3] [,4] [,5] [,6]
[1,] “loja” “loja” “loja” “c1” “c1” “c2”
[2,] “c1” “c2” “c3” “c2” “c3” “c3”
> trechos[2:1,]
[,1] [,2] [,3] [,4] [,5] [,6]
[1,] “c1” “c2” “c3” “c2” “c3” “c3”
[2,] “loja” “loja” “loja” “c1” “c1” “c2”

Observe os índices da matriz trechos.

Nossa, avançamos bastante.

Agora já temos um modelo para trabalhar. Dado uma loja e N clientes, sabemos como calcular de forma genérica todas as rotas possíveis e temos um método de explicitar todas as distâncias que precisamos calcular para estimar a rota mais rápida.

Próximos passos?

  1. Usar a API do Google para obter os tempos em todos os trechos;
  2. Calcular a rota ótima;
  3. Exibir no mapa.

Vamos nessa?

Bye, não deixe de enviar o seu comentário em caso de dúvidas.

João Carlos

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Leave a Comment

Related Story
%d bloggers like this: