Agrupar paradas en una ruta

Question

Trabajo en un proyecto en el que tengo que organizar rutas de servicio para una empresa de control de plagas en nuestro paquete de software. Discutimos varias opciones para organizar las paradas de cada día de la manera más eficiente posible.

Cada día tenemos de 80 a 100 paradas, 10 o más paradas por técnico, y estas paradas pueden, en su mayor parte, moverse hasta 7 días en cualquier sentido en el mes para adaptarse a la eficiencia.

Ignorando las paradas que no se pueden mover, ¿cuál sería un buen punto de partida para organizar a los clientes en días en los que los técnicos recorren las distancias más cortas?

Tenemos lat y long en cada parada. Por ahora, no nos preocupan las barreras geográficas como puentes, ríos, etc. Podríamos abordar eso más tarde, pero en línea recta es lo suficientemente bueno por ahora. ¿Alguna idea?

EDITAR:

También tenemos "cuadrículas de mapas" para cada cliente. Cada cuadrícula de mapa es de media milla cuadrada y está en una cuadrícula perfecta en todo nuestro territorio de servicio. Estos podrían usarse para agrupar y contener rutas. Por lo general, nuestras rutas contienen alrededor de 100 cuadrículas en un grupo semi-ajustado.

Answer 1

Similar a esto .

Comienzas con una orden de viaje ingenua y luego comienzas a intercambiar entradas al azar. Cada vez que intercambias, mides la duración total del viaje, y si la nueva longitud es mejor, la conservas; de lo contrario, deshaces el intercambio.

Hágalo unas mil veces y el viaje debería empezar a ser razonable.