Agrupando paradas em uma rota

Question

Trabalho em um projeto onde tenho que organizar rotas de atendimento para uma empresa de controle de pragas em nosso pacote de software.Discutimos diversas opções para organizar as paradas de cada dia da maneira mais eficiente possível.

Cada dia temos de 80 a 100 paradas, cerca de 10 paradas por técnico, e essas paradas podem, em sua maioria, ser movidas por até 7 dias em qualquer sentido do mês para acomodar a eficiência.

Ignorando as paradas que não podem ser deslocadas, qual seria um bom ponto de partida para organizar os clientes em dias onde as distâncias mais curtas são percorridas pelos técnicos?

Temos lat e long em cada parada.Por enquanto, não estamos preocupados com barreiras geográficas como pontes, rios, etc.Poderemos abordar isso mais tarde, mas em linha reta é bom o suficiente por enquanto.Alguma ideia?

EDITAR:

Também temos “grades de mapas” para cada cliente.Cada grade do mapa tem meia milha quadrada e está em uma grade perfeita em todo o nosso território de serviço.Eles podem ser usados ​​para agrupar e conter rotas.Normalmente nossas rotas contêm cerca de 100 grades em um agrupamento semi-apertado.

Answer 1

Igual a esse.

Você começa com uma ordem de viagem ingênua e depois começa a trocar entradas aleatoriamente.Cada vez que você troca, você mede a duração total da viagem, e se a nova duração for melhor você mantém, caso contrário você desfaz a troca.

Faça isso cerca de mil vezes e a viagem começará a ser razoável.