Problema di localizzazione della struttura su spazio continuo
Sto rivedendo la letteratura sul problema di localizzazione della struttura (FLP). Qui, Daskin e Dean (2004) hanno fornito una breve letteratura sui FLP nello spazio discreto, utile per distinguere diversi tipi di modelli con obiettivi diversi. Chopra e Meindl (2013) hanno mostrato un piccolo esempio di un FLP su uno spazio continuo con una singola selezione di strutture, che hanno chiamato modello di localizzazione gravitazionale , nel libro intitolato: "Gestione della catena di approvvigionamento: strategia, pianificazione e operazione".
Sono alla ricerca di un articolo di revisione o di articoli selezionati che abbiano formulato FLP su uno spazio continuo con selezioni multiple di strutture. Inoltre, il problema è stato formulato con un modello non lineare in Chopra e Meindl (2013) perché hanno considerato la distanza euclidea tra un nodo di domanda e le possibili coordinate della struttura. Hai mai incontrato un documento che formula il problema con un modello lineare? È possibile?
Per descrivere meglio il problema, supponiamo che esista un insieme di nodi di domanda di dimensioni polinomiali e vorremmo individuare strutture per soddisfare completamente la domanda riducendo al minimo i costi di strutture e servizi. Ogni struttura ha una gamma di servizi circolari e il costo della struttura è lo stesso in tutte le sedi. Poiché le strutture non sono limitate in termini di capacità e non vi è alcun incentivo a soddisfare una parte della domanda da parte di un'altra struttura, possiamo presumere che ogni nodo di domanda sarà completamente servito dalla struttura più vicina e trovare le ramificazioni non è interessante. Possiamo inoltre supporre che la distanza euclidea sia il driver prevalente del calcolo del costo del servizio.
Sono anche interessato alla versione della struttura a spaziatura discreta del problema sopra descritto. In particolare, sto cercando algoritmi in grado di gestire fino a 2 milioni di nodi di domanda in una quantità ragionevole di tempo computazionale, diciamo meno di un giorno. Altrimenti, i modelli presentati in Daskin e Dean (2004) forniscono uno schizzo ragionevole su cui costruire.
Risposte
Il tipo di problemi di posizione che stai cercando sono problemi di posizione planari in cui il problema di Weber e i problemi multi-Weber sono tra i più noti (e più semplici). Drezner offre una bella panoramica del problema e una procedura di soluzione chiamata "procedura di Weizfeld". Per il problema multi-Weber esiste un'euristica semplice e piuttosto famosa chiamata " euristica di allocazione della posizione di Cooper " (o qualcosa del genere).
So che puoi formulare il problema multi-Weber sia come programma intero misto non lineare sia come differenza del problema di ottimizzazione convessa. Ma non puoi formularlo come un programma lineare (a meno che$\mathcal{P=NP}$) in quanto è un$\mathcal{NP}$-difficile problema di ottimizzazione.
Se ho capito bene, ti viene fornito un insieme di nodi di domanda e vuoi localizzare un numero finito di strutture, ovunque nel piano, in modo da ridurre al minimo la somma delle distanze tra ciascun nodo di domanda e la sua struttura assegnata?
Oltre alla letteratura sui problemi di localizzazione delle strutture, potresti trovare alcuni strumenti utili nei metodi di clustering (ad esempio, l'algoritmo K-means e simili), così come i problemi dell'albero di Steiner.
L'algoritmo K-mean calcola i cluster, in cui si trova il centroide di ciascun cluster in modo da ridurre al minimo la somma delle distanze al quadrato dei punti nel cluster. Una versione simile con distanze non quadrate è il problema p-mediano. Alcuni approcci basati sulla generazione di colonne sono stati proposti per entrambi, vedere, ad esempio, questo articolo .
Il problema dell'albero di Steiner euclideo non è esattamente il problema che stai menzionando, ma potrebbero esserci alcuni utili trucchi di modellazione da questa letteratura, ad esempio questo articolo .