Optimierte Standortbestimmung für Verbindungsknoten zur Kanalisierung von Transport- bzw. Materialflüssen
Final Report Abstract
Mit steigenden Energiekosten und knapper werdenden Ressourcen gewinnen gute Standortentscheidungen zunehmend an Bedeutung, sowohl aus ökonomischer als auch aus ökologischer Sicht; siehe z.B. (T3) für eine aktuelle, allgemeinverständliche Einführung. In diesem Projekt wurden Verbindungs-Standortprobleme betrachtet, bei denen die optimalen Standorte für Verbindungs- und Anschlussknoten wie z.B. Brücken, Ein-, Aus- und Übergängen, Bearbeitungszentren oder Steuerungsknoten in Flussnetzwerken gesucht werden. Zusammenhänge bestehen u.a. zu kontinuierlichen Mehrstandortproblemen wie dem Multi-Weber Problem (Location-Allocation Problem) und zu Hub-St andortproblemen. Verbindungs-Standortprobleme kombinieren eine kontinuierliche Standortentscheidung (d.h. die Platzierung von K neuen Standorten im R^2) mit einer diskreten Zuordnungsentscheidung (d.h. der Zuordnung von Transport-Flüssen zu neuen Standorten) und lassen sich entsprechend als nichtlineare, gemischt ganzzahlige Optimierungsprobleme schreiben. Im Rahmen dieses Projekts konnten zahlreiche theoretische wie auch algorithmische Ergebnisse erzielt werden: - Verbindungs-Standortprobleme sind NP-schwer. - Verbindungs-Standortprobleme sind bikonvex, d.h. sie lassen sich durch Fixierung der Standort- bzw. Zuordnungs variablen in konvexe Teilprobleme zerlegen, wobei die Gesamtprobleme i. A . hochgradig nichtkonvex bleiben. - Cluster-Eigenschaften für die Zuordnung der existierenden zu neuen Standorten gelten nur bei quadratischen euklidischen Abständen und verwandten Abstandsmaßen. - Die Suche nach der optimalen Lage der neuen Standorte kann, je nach Abstandsmaß, auf die konvexe oder metrische Hülle der existierenden Standorte beschränkt werden. - Für polyedrische Abstandsmaße gelten Diskretisierungsergebnisse. Außerdem lässt sich das Problem in diesem Fall als MILP umformulieren. - Als exakte Lösungs verfahren eignen sich besonders Branch & Bound und, im Fall polyedrischer Abstandsmaße, Konstruktionslinienalgorithmen. - Unter den heuristischen Lösungsverfahren ist insbesondere die bikonvexe Suche (Alternate Location AUocation Heuristik) in Verbindung mit Meta- Heuristiken zur Vermeidung lokaler Minima erfolgreich. - Einige der obigen Ergebnisse lassen sich auf Modellerweiterungen übertragen. Betrachtet wurden Probleme mit Kapazitätsbeschränkungen, als Warteschlangen operierende Verbindungsknoten und aUgemeine Abstandsfunktionen wie Barrierenabstände und gemischte Abstände, die kontinuierliche mit Netzwerk-basierten Abstandsmaßen kombinieren. Verbindungs-Standortprobleme sind damit umfassend analysiert und einer effizienten Lösung zugänglich gemacht worden. Die Auswirkungen auf verwandte ProblemsteUungen sind Gegenstand weiterer Forschungsarbeiten.
Publications
- (2006). Path Planning and Location Problems with Varying Environments. Dissertation, Fachbereich Mathematik, Universität Erlangen-Nürnberg, 2006. Shaker-Verlag, Aachen, 2006, ISBN 3-8322-4950-8
B. Pfeiffer
- (2007). An efficient solution method for Weber problems with barriers based on genetic algorithms. European Journal of Operational Research 177:22-41
M. Bischoff und K. Klamroth
- (2007): Biconvex sets and optimization with biconvex functions - A survey and extensions. Mathematical Methods of Operations Research 66:373-407
J. Gorski, F. Pfeuffer und K. Klamroth
- (2007): Two branch & bound methods for a generalized class of location-allocation problems. In: A. Paias und F. Saldanha da Gama (Hrsg.): Proceedings of the EURO Winter Institute on Location and Logistics. S. 45-61
M. Bischoff und K. Klamroth
- (2008). A unified model for Weber problems with continuous and network distances. Computers and Operations Research 35:312-326
B. Pfeiffer und K. Klamroth
- (2008). Construction Line Algorithms for the connection location-allocation problem. In: J. Kalcsics und S. Nickel (Hrsg.): Operations Research Proceedings 2007, S. 345-350, Springer-Verlag
M. Bischoff und Y. Bayer
- (2008). Location of Connection Fadlities. Dissertation, Fachbereich Mathematik, Universität Erlangen-Nürnberg, 2008. Erschienen im Shaker-Verlag, Aachen, 2008, ISBN 978-3-8322-7096-4
M. Bischoff
- (2008): Standortoptimierung. In: B. Luderer (Hrsg.): Die Kunst des Modellierens. Mathematisch - Ökonomische Modelle. S. 139-156, Teubner-Verlag
H.W. Hamacher, K. Klamroth und Chr. Tammer
- (2009): Allocation search methods for a generalized class of location-allocation problems. European Journal of Operational Research 192:793-807
M. Bischoff und K. Dächert
- (2009): The multifacility location-allocation problem with barriers. Computers and Operations Research 36:1376-1392
M. Bischoff, T. Fleischmann und K. Klamroth
