Otimização de roteamento de veículo com múltiplas Frotas feito em Python

[wesley gabriel]

Boa Tarde Caros Colegas, 

Espero que se encontrem bem, estou tendo uma dúvida em relação ao desenvolvimento de um projeto em python. Será que alguém do grupo conseguiria me auxiliar nesta frente?

Estou tendo dificuldade em desenvolver essa aplicação de otimização para roteamento de veículos. 

Caso alguém consiga me auxiliar, entre em contato comigo. 

Desde já agradeço.

[Jonatas Almeida]

Fala Wesley, blz?

Pode especificar melhor o problema? Se puder, manda print e código no Gist pra gente dar uma olhada.

Nunca trabalhei diretamente com isso,  Está lidando com dados georreferenciados? Ouvi uma ou outra coisa a respeito.

att:

Jonatas Almeida

[Marcos Thomaz]

Opa Wesley, beleza?

O que você tem feito e como pensou na solução? Tipo, pensou no uso de alguma heurística, meta-heurística, uso de algum solver?

Tem uma lib do google que, em sua documentação, trata do problema (tem um exemplo simples): https://developers.google.com/optimization/routing/vrp?hl=pt-br#solving_the_vrp_example_with_or-tools

Quando precisei fazer algo nesse sentido, acabei usando um algoritmo genético (e no meu caso, modelei de forma semelhante ao VRP, mas era basicamente escalonamento de tarefas em máquinas distintas).

Jonatas, é um problema de otimização (VRP Vehicle Routing Problem).

--
--
------------------------------------
Grupo Python-Brasil
https://wiki.python.org.br/AntesDePerguntar
 
<*> Para visitar o site do grupo na web, acesse:
http://groups.google.com/group/python-brasil
 
<*> Para sair deste grupo, envie um e-mail para:
python-brasi...@googlegroups.com
---
Você recebeu essa mensagem porque está inscrito no grupo "Python Brasil" dos Grupos do Google.
Para cancelar inscrição nesse grupo e parar de receber e-mails dele, envie um e-mail para python-brasi...@googlegroups.com.
Para ver esta conversa, acesse https://groups.google.com/d/msgid/python-brasil/84bbf1c5-70c1-4064-9458-5030c327c570n%40googlegroups.com.

--

Marcos Thomaz da Silva

Analista de Tecnologia da Informação

[wesley gabriel]

Boa Tarde Jonatas e Marcos, tudo bem? Espero que sim.

Então o meu problema realmente envolve um case VRP heterogêneo com múltiplas frotas, no entanto, não estou conseguindo construir o meu algoritmo genético que explore todas essa frente com múltiplos veículos e as cidades. Caso vocês tenham alguma ideia e queiram compartilhar através de um vídeo ou uma reunião, ficarei grato. Mesmo usando CHATGPT passo a passo, o mesmo não retorna exatamente o que estou pensando.

Desde já agradeço.

Atenciosamente.  

Para ver esta conversa, acesse https://groups.google.com/d/msgid/python-brasil/CAEzgTQwozTi5DZBVaH%3Dp56FsNUcx0mXfuVtSjuz244PSb8fD0w%40mail.gmail.com.

--

Wesley Gabriel de Mendonça Pinto

Mestre em Engenharia de Produção - UNIFEI

Instituto de Engenharia de Produção e Gestão - IEPG

Endereço do Lattes:  http://lattes.cnpq.br/5071443901622811

[Guilherme Medeiros]

Wesley,

vc já buscou no google?

https://www.google.com/search?client=ubuntu-sn&channel=fs&q=VRP+heterog%C3%AAneo

Achei esse TCC que analisa esse seu problema e sugere alguns algoritmos: https://repositorio.ufc.br/bitstream/riufc/34016/1/2018_tcc_mandrade.pdf

Para ver esta conversa, acesse https://groups.google.com/d/msgid/python-brasil/CANH1oi6Sb_ies8pe_Mo%2B%3D4%2BXq5Zn2yUmb6CBZOtWHLx_DzXpjw%40mail.gmail.com.

[wesley gabriel]

Já sim, inclusive tentei usar o chat para me auxiliar. No entanto, não consegui respostas eficientes que me apoiam no desenvolvimento.

Para ver esta conversa, acesse https://groups.google.com/d/msgid/python-brasil/CAG2-K3yK1XXgmxR4qGQSWBSXzyyBXFYrQYN2jebS1vpjp3mhUg%40mail.gmail.com.

[Marcos Thomaz]

Wesley, no problema que você precisa modelar, fiquei com algumas dúvidas devido a características do problema.

- Os veículos da frota terão capacidade limitada de carga (peso máximo)?
- Os veículos da frota terão capacidades diferentes?

- Os produtos/entregas terão "peso" para considerar (pesos diferentes por produto/entrega)?
- Haverá priorização de entregas com base em alguma métrica temporal (duedate por exemplo) ou penalidade (exemplo do tardiness)?

Para ver esta conversa, acesse https://groups.google.com/d/msgid/python-brasil/CANH1oi4fvccrniaAJ%2BC99JGjfcXaV--kHMt0w_zqqR-w-0X5Aw%40mail.gmail.com.

[wesley gabriel]

- Os veículos da frota terão capacidade limitada de carga (peso máximo)? Sim, o peso deles, isto é, até encher tudo.
- Os veículos da frota terão capacidades diferentes?Sim, terei seis veículo com capacidades distintas.

- Os produtos/entregas terão "peso" para considerar (pesos diferentes por produto/entrega)? Não sei se entendi direito os pesos, mas não colocarei restrições de busca por prioridades nas cidades não. A ideia é que o GA retornasse a rota mais eficiente, minimizando custo, emissão do CO2 e maximizando a coleta. 
- Haverá priorização de entregas com base em alguma métrica temporal (duedate por exemplo) ou penalidade (exemplo do tardiness)? Não também.

Para ver esta conversa, acesse https://groups.google.com/d/msgid/python-brasil/CAEzgTQxKFe_kTqXd4j9yVQitfnvCokOqC8Bmkskphu8EyxZTxQ%40mail.gmail.com.

[Marcos Thomaz]

- Os produtos/entregas terão "peso" para considerar (pesos diferentes por produto/entrega)? Não sei se entendi direito os pesos, mas não colocarei restrições de busca por prioridades nas cidades não. A ideia é que o GA retornasse a rota mais eficiente, minimizando custo, emissão do CO2 e maximizando a coleta. 

No caso, como está definida sua função de fitness?

Outra coisa, você colocou "maximizando a coleta", seria uma variação aplicada a colega de lixo por exemplo? Pergunto porque aqui seria uma inversão, onde os caminhões saem vazios e vão sendo preenchidos.