Raggruppamento delle soste su un percorso

Question

Lavoro a un progetto in cui devo organizzare percorsi di servizio per un'azienda di disinfestazione nel nostro pacchetto software. Abbiamo discusso diverse opzioni per organizzare le soste per ogni giorno nel modo più efficiente possibile.

Ogni giorno abbiamo 80-100 fermate, circa 10 fermate per tecnologia, e queste fermate possono, per la maggior parte, essere spostate fino a 7 giorni in entrambi i modi nel mese per garantire l'efficienza.

Ignorando le fermate che non possono essere spostate, quale sarebbe un buon punto di partenza per organizzare i clienti in giorni in cui i tecnici percorrono le distanze più brevi?

Abbiamo latitudine e longitudine su ogni tappa. Per ora, non ci preoccupiamo delle barriere geografiche come ponti, fiumi, ecc. Potremmo affrontarlo più tardi, ma in linea d'aria per ora è abbastanza buono. Qualche idea?

MODIFICA:

Abbiamo anche "griglie di mappe" per ogni cliente. Ogni griglia della mappa è un mezzo miglio quadrato e si trova in una griglia perfetta in tutto il nostro territorio di servizio. Questi potrebbero essere usati per raggruppare e contenere rotte. Di solito le nostre rotte contengono circa 100 griglie in un raggruppamento semi-stretto.

Answer 1

Simile a questo .

Inizi con un ordine di viaggio ingenuo, quindi inizi a scambiare le voci in modo casuale. Ogni volta che effettui uno scambio, misuri la lunghezza totale del viaggio e, se la nuova lunghezza è migliore, la mantieni, altrimenti annulli lo scambio.

Fallo un migliaio di volte e il viaggio dovrebbe iniziare a essere ragionevole.