von Dr. Hannah Bakker (Gewinnerin Dissertationspreis 2024)
Das Capacitated Facility Location Problem (CFLP) gehört zu den klassischen Problemen der Standortplanung. Hierbei werden aus einer Menge von Kandidaten Standorte für Einrichtungen mit fixer Kapazität ausgewählt, um Nachfragen einer bekannten Menge an Kunden zu erfüllen. Die Eröffnung von Standorten verursacht fixe Kosten, während die Bedienung von Kundennachfragen variable Kosten verursacht, die von der Menge und Entfernung abhängen. Der zentrale Trade-off besteht darin, dass mehr Standorte höhere Fixkosten mit sich bringen, aber gleichzeitig kürzere Transportwege die variablen Kosten senken. Es wird entschieden, welche Standorte eröffnet und welche Kunden welchen Standorten zugeordnet werden.
Das CFLP ist seit den 1960er Jahren ein intensiv erforschtes Problem. Trotz seiner Anschaulichkeit findet man jedoch kaum visuelle Darstellungen von Instanzen oder Lösungen. Dies liegt einerseits daran, dass reale Transportkosten oft nicht proportional zu Luftlinienentfernungen sind, was eine Darstellung gemäß Positionen auf der Landkarte wenig aussagekräftig macht. Andererseits fehlen bei synthetischen Daten oft Angaben zur Position von Kunden oder Standorten, da nur Transportkostenmatrizen angegeben sind. Mit Hilfe multidimensionale Skalierung (MDS), einem Verfahren, das häufig in der Vorverarbeitung von Daten im maschinellen Lernen verwendet wird, bietet sich die Möglichkeit, Instanzen und Lösungen transportkostengerecht zu visualisieren. Hierbei wird die Transportkostenmatrix auf zwei Dimensionen reduziert, die als Koordinaten in der Ebene interpretiert werden, sodass die relativen Positionen von Standorten und Kunden transportkostengerecht abgebildet werden [1].
Abbildung 1 zeigt die optimale Lösung des CFLP für eine der Benchmark-Instanzen aus der OR-Library, die auf einem realen Datensatz aus den USA basiert. Abbildung 2 zeigt eine gute, aber nicht optimale Lösung einer synthetisch generierten Instanz. Sie veranschaulicht, dass eine visuelle Darstellung eine intuitive Bewertung der Lösungen erlaubt. So ist es offensichtlich, dass die in Rot gezeichneten Zuordnungsentscheidungen suboptimal sind, da eine Zuordnung zu näher gelegenen, eröffneten Standorten die Kosten reduzieren würde.
Die visuelle Darstellung macht es auch möglich, Kunden und Standorte intuitiv zueinander in Beziehung zu setzen. Für die Eröffnungsentscheidung eines bestimmten Standorts ist es vor allem relevant, welche anderen Standorte in der Nähe eröffnet werden. Dies wird am Beispiel in Abbildung 3 deutlich. Die hellgrün dargestellten Standorte und Zuordnung in der oberen linken Ecke der Abbildung sind Teil der optimalen Lösung dar. Sobald jedoch einer der beiden eingekreisten Standorte nicht verfügbar ist, ist auch der andere eingekreiste Standort nicht länger Teil der optimalen Lösung. In diesem Fall ist es kostengünstiger, die Kunden in der Region von der nächstbesten Kombination an Standorten, in Orange dargestellt, zu bedienen. Die restlichen Standort- und Zuordnungsentscheidungen sind von dem Wegfall nicht betroffen. Vergleicht man die optimalen Lösungen zu abgeleiteten Instanzen, die daraus entstehen, dass einzelne Kandidaten entfernt werden, stellt man fest, dass sich die Menge der Kunden und Kandidaten in verschiedene interdependente Regionen unterteilen lässt. Die implizierten Regionen können so charakterisiert werden, dass Kunden in verschiedenen Lösungen zwar unterschiedlichen Standorten zugeordnet werden, diese Standorte aber immer in derselben Region liegen. Diese Regionen sind nicht nur durch Transportkosten geprägt, sondern auch durch Kapazitäten, Nachfragen und Fixkosten, die bestimmen, welche Kundengruppen ein Standort bedienen kann.
Wie lassen sich solche Regionen algorithmisch bestimmen, ohne eine approximative, visuelle Darstellung? Die Charakterisierung von Regionen basiert auf den Zuordnungsentscheidungen in einer Menge günstiger Lösungen. Aggregiert man die Matrizen der Zuordnungsentscheidungen in diesen Lösungen bspw. durch Aufsummieren, so lassen sich die Zeilen und Spalten der aggregierten Matrix so umsortieren, dass diese eine blockdiagonale Struktur aufweist, bei der jeder Block einer Region entspricht. Algorithmisch entspricht das Umsortieren von Zeilen und Spalten der Matrix zum Erhalt einer solchen Struktur zweidimensionalen Clustering, einer Form der Mustererkennung [2]. Mithilfe von Matrixfaktorisierung kann eine Aufteilung in eine festgelegte Anzahl von Regionen bestimmt werden.
Da Regionen nicht nur durch Transportkosten bestimmt werden, sondern auch durch Kapazitäts- und Nachfrageparameter, werden sie aus den Matrizen der Zuordnungsentscheidungen abgeleitet und nicht, wie man zunächst vermuten würde, von den Transportkostenmatrizen. Um von einer reinen ex-post-Analyse zu einem Informationsgewinn zu gelangen, der bereits beim Auffinden der optimalen Lösung genutzt werden kann, können Matrizen der Zuordnungsentscheidungen der optimalen Lösung des linear relaxierten Problems verwenden werden. Abbildung 4 zeigt die drei Regionen, die aus der linear relaxierten Lösung zu der Benchmark-Instanz abgeleitet wurden, sowie eine überlagerte Darstellung der optimalen Lösung für das gemischt-ganzzahlige Problem.
Die Möglichkeit, Kunden und Standorte in weitgehend unabhängige Regionen zu unterteilen, birgt viel Potenzial. In meiner Thesis [3] zeige ich, dass die Größe und Anzahl der Regionen, in die eine Instanz zerlegt werden kann, die Performanz von exakten als auch heuristischen Lösungsverfahren maßgeblich beeinflusst. Große Regionen bedeuten, dass eine Standortentscheidung viele andere beeinflusst, während kleinere Regionen weniger Abhängigkeiten aufweisen. Dieses Verständnis kann helfen, ein passendes Lösungsverfahren für eine bestimmte Instanz zu wählen. Beispielsweise findet ein einfaches Greedy-Verfahren in Instanzen, die sich in viele kleine Regionen unterteilen lassen, häufiger die optimale Lösung als Instanzen, die nur in wenige, große Regionen zerlegbar sind.
Regionen entstehen aus dem Zusammenspiel von Transportkosten, Fixkosten, Kapazitäten und Nachfrageparametern. Sie spiegeln Zuordnungsmuster wider, die unter den gegebenen Parametern besonders kostengünstig sind. Wenn zusätzliche Aspekte wie zeitliche Nachfrageentwicklungen oder stochastische Parameter in das Modell aufgenommen werden, bleiben diese Regionen oft stabil, da sich ein Großteil der Parameter nicht ändert und es weiterhin kostengünstig ist, Kunden von „nahegelegenen“ Standorten zu bedienen. Ein weiterer Aspekt, den ich in meiner Thesis analysiere ist, wann ein Wechsel zu einem komplexeren Modell sinnvoll ist und wie die Entscheidungen durch die implizierten Regionen beeinflusst werden [3].
Das Auffinden von Regionen basiert auf einem Verfahren der Musterkennung, mit Hilfe dessen eine Vielzahl günstiger Lösungen im Entscheidungsraum analysiert werden. Dies ist nur dank leistungsstarker moderner Solver und effizienter Datenanalysetools möglich. Die Thesis ist ein Beispiel dafür, dass stets besser werdenden Solver nicht nur das Lösen größerer und komplexerer Probleme ermöglichen, sondern auch neue Perspektiven auf seit Jahrzehnten untersuchte Probleme wie das CFLP eröffnen.
[1] Bakker, H., & Nickel, S. (2024). Spatial Patterns Underlying Facility Location Problems: Visualization and Classification (v1.1). Zenodo. https://github.com/hannah-bakker/FLP-spatialpattern
[2] Dhillon, I. S. (2001). Co-clustering documents and words using bipartite spectral graph partitioning. In Proceedings of the Seventh ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD ’01, page 269–274, New York, NY, USA.
[3] Bakker, H. (2024). On the interplay between data and decisions in discrete location problems. Karlsruher Institut für Technologie (KIT), PhD Thesis.
[4] Bakker, H., und Nickel, S. (2024). The Value of the Multi-period Solution revisited: When to model time in capacitated location problems. Computers & Operations Research, 161, 106428. Hannah Bakker, Kaiserstr. 89, 76133 Karlsruhe, hannah.bakker@kit.edu