Riduce al minimo la distanza di viaggio di n persone in n posizioni

3

Il problema:

Viste le coordinate di N persone su un piano bidimensionale regolare e N punti di interesse bersaglio (POI) sullo stesso piano, determinare l'insieme di coppie di persone e POI che riducono al minimo la somma delle distanze in linea retta tra le posizioni in ciascuna coppia. Non è consentito a due persone di accedere allo stesso PDI e tutti i POI devono essere coperti.

In altre parole, se ho 5 camion che devono andare in 5 posizioni e camion sono intercambiabili, dove posso inviare i camion in modo che venga usata la minor quantità di carburante (supponendo che l'uso del carburante sia proporzionale alla distanza percorsa)?

Discussione:

La forza bruta richiederebbe N fattoriale. Esiste un modo migliore? Questo sembrerebbe essere un problema piuttosto comune di ricerca operativa, ma il mio google-fu è insufficiente.

    
posta Nic Watson 24.05.2014 - 22:56
fonte

1 risposta

1

Copia i commenti per far uscire il problema dai problemi senza risposta e renderlo wiki della comunità.

Sembra il problema del commesso viaggiatore. Vedi Algoritmo per una soluzione esatta all'acquirente in viaggio problema

Questo è noto come problema di assegnazione: en.wikipedia.org/wiki/Assignment_problem - Wikipedia elenca alcuni algoritmi per risolverlo in tempo polinomiale.

Hai ragione! Più specificamente, è esattamente il problema dei trasporti.

    
risposta data 12.04.2017 - 09:31
fonte