Facility-Location-Problem über kontinuierlichen Raum
Ich überprüfe die Literatur zum Facility Location Problem (FLP). Hier stellten Daskin und Dean (2004) eine kurze Literatur zu diskreten Raum-FLPs bereit, die nützlich war, um verschiedene Arten von Modellen mit unterschiedlichen Zielen zu unterscheiden. Chopra und Meindl (2013) zeigten in dem Buch mit dem Titel „Supply Chain Management: Strategy, Planning, and Operation“ ein kleines Beispiel für ein FLP über kontinuierlichem Raum mit einer einzigen Anlagenauswahl, das sie Gravitationsstandortmodell nannten.
Ich bin auf der Suche nach einem Übersichtsartikel oder ausgewählten Artikeln, die FLP über einen kontinuierlichen Raum mit mehreren Auswahlmöglichkeiten formuliert haben. Außerdem wurde das Problem in Chopra und Meindl (2013) mit einem nichtlinearen Modell formuliert, da sie die euklidische Entfernung zwischen einem Bedarfsknoten und möglichen Einrichtungskoordinaten berücksichtigten. Sind Sie jemals auf ein Papier gestoßen, das das Problem mit einem linearen Modell formuliert? Ist das überhaupt möglich?
Um das Problem besser zu beschreiben, nehmen wir an, es gibt einen Satz von Nachfrageknoten mit polynomischer Größe, und wir möchten Einrichtungen lokalisieren, um die Nachfrage vollständig zu decken und gleichzeitig die Kosten für Einrichtungen und Dienste zu minimieren. Jede Einrichtung verfügt über einen kreisförmigen Servicebereich, und die Einrichtungskosten sind an allen Standorten gleich. Da die Kapazitäten der Einrichtungen nicht begrenzt sind und es keinen Anreiz gibt, einen Teil der Nachfrage durch eine andere Einrichtung zu decken, können wir davon ausgehen, dass jeder Bedarfsknoten vollständig von der nächstgelegenen Einrichtung bedient wird, und es ist nicht von Interesse, die Auswirkungen zu ermitteln. Wir können weiterhin davon ausgehen, dass die euklidische Distanz der vorherrschende Treiber der Servicekostenberechnung ist.
Ich interessiere mich auch für die diskret beabstandete Einrichtungsversion des oben beschriebenen Problems. Insbesondere suche ich nach Algorithmen, die in angemessener Rechenzeit, sagen wir weniger als einem Tag, bis zu 2 Millionen Bedarfsknoten abdecken können. Ansonsten bieten die in Daskin und Dean (2004) vorgestellten Modelle eine vernünftige Skizze, auf der aufgebaut werden kann.
Antworten
Die Art von Lokalisierungsproblemen, nach denen Sie suchen, sind planare Lokalisierungsprobleme , wobei das Weber - Problem und die Multi-Weber- Probleme zu den bekanntesten (und einfachsten) gehören. Drezner gibt einen schönen Überblick über das Problem und ein Lösungsverfahren namens "Weizfeld-Verfahren". Für das Multi-Weber-Problem gibt es eine einfache und ziemlich berühmte Heuristik namens " Coopers Location-Allocation-Heuristik " (oder so ähnlich).
Ich weiß, dass Sie das Multi-Weber-Problem sowohl als nichtlineares gemischtes ganzzahliges Programm als auch als Differenz eines konvexen Optimierungsproblems formulieren können. Aber man kann es nicht als lineares Programm formulieren (es sei denn$\mathcal{P=NP}$) wie es ist$\mathcal{NP}$-schweres Optimierungsproblem.
Wenn ich das richtig verstehe, erhalten Sie eine Reihe von Bedarfsknoten und möchten eine endliche Anzahl von Einrichtungen irgendwo in der Ebene lokalisieren, um die Summe der Entfernungen zwischen jedem Bedarfsknoten und der ihm zugewiesenen Einrichtung zu minimieren?
Neben der Literatur zu Standortproblemen von Einrichtungen finden Sie möglicherweise einige nützliche Werkzeuge in Clustering-Methoden (z. B. dem K-Means-Algorithmus und dergleichen) sowie Steiner-Baum-Problemen.
Der K-Means-Algorithmus berechnet Cluster, wobei der Schwerpunkt jedes Clusters so angeordnet ist, dass die Summe der quadrierten Abstände zu Punkten im Cluster minimiert wird. Eine ähnliche Version mit nicht quadrierten Abständen ist das p-Median-Problem. Für beide wurden einige spaltengenerierungsbasierte Ansätze vorgeschlagen, siehe z. B. dieses Papier .
Das Problem des euklidischen Steinerbaums ist nicht genau das Problem, das Sie erwähnen, aber es gibt möglicherweise einige nützliche Modellierungstricks aus dieser Literatur, zum Beispiel diesem Artikel .