Im Verkehrswesen bestehen zahlreiche Anwendungsmoglichkeiten fur Entscheidungs-und Optimierungsmethoden. Gerade im Hinblick auf den langfristigen Zeitho-rizont, fur den in der Regel Verkehrs- und Logistikprojekte angelegt sind, istdie Anwendung von zuverlassigen Hilfsmitteln zur Entscheidungsfindung una-blassig.Die Komplexitat des ”Systems Verkehr“ erfordert dabei eine klare und uber-schaubare Gliederung und Strukturierung, um den vielfaltigen Wechselwirkun-gen zwischen einzelnen Problemfeldern wahrend des Planungsprozesses gerechtzu werden. [FGSV 1982]Innerhalb dieses Planungsprozesses ist ein Entscheidungstrager mit einer Viel-zahl an notwendigen Entscheidungen konfrontiert, welche die Anwendung vonEntscheidungsmethoden erfordert. Einen dieser Bereiche stellt die Standortplan-ung dar.Im Verkehrswesen existiert eine Vielzahl an Standortentscheidungsproblemen,welche durch Optimierungsmethoden des Operations Research modelliert wer-den konnen. Es zeigt sich, dass diese auf sehr unterschiedliche Teilgebiete desVerkehrswesens - beispielsweise auf den Wirtschaftsverkehr oder den Offentli-chen Verkehr - angewendet werden konnen.Im Folgenden sind verschiedene Einsatzbereiche von Entscheidungsmodellen imVerkehrswesen dargestellt. Unterteilt sind diese nach der Verkehrsart, also nachWirtschaftsverkehr (hierzu zahlt neben dem Guterverkehr auch der Sonder-verkehr), Personenindividualverkehr und Offentlichem Verkehr.
3
1.2 Problembereiche
Wirtschafts-verkehr
Zum Wirtschaftsverkehr zahlen der Transport von Gutern (”Guterverkehr“)und der Sonderverkehr. Sonderverkehr umfasst beispielsweise Einsatzfahrtenvon Rettungsdiensten und Fahrten, die dem Straßenbetrieb und der Straßen-unterhaltung dienen.[FACHGEBIET VV der TUD 2004]Folgende Standortprobleme des Wirtschaftsverkehrs werden betrachtet:
• Guterverkehrszentren
• Straßenmeistereien
• Feuer- und Rettungswachen
Personen-individualver-
kehr
Zu betrachten sind im Rahmen des Personenindividualverkehrs Standortent-scheidungen fur Parkierungsanlagen. Neben Park + Ride Anlagen ist dieStandortbestimmung von Parkplatzen und Parkhausern in stadtischen Kern-gebieten von Interesse.
OffentlicherVerkehr
Schon seit vielen Jahren ist der offentliche Verkehr einer steigenden intermodalenKonkurrenz - vor allem durch den motorisierten Individualverkehr - ausgesetzt[LIEBCHEN 2005].Angesichts knapper finanzieller Ressourcen und einer fortschreitenden Privati-sierung der Markte sind Verkehrsunternehmen zunehmend auf einen hohen Gradan Effizienz im Einsatz ihrer Ressourcen, wie etwa Verkehrsmittel und Personal,angewiesen.Eine große Rolle spielen dabei computergestutzte Planungsmethoden. Hier kannmit Hilfe von mathematischen Planungs- und Optimierungsmethoden die pla-nerische Arbeit im OPNV unterstutzt werden [GENC 2003].Im Folgenden sollen die Depotplanung fur offentliche Verkehrsmittel sowiedie Standortplanung von Haltestellen im Rahmen eines Liniennetzes naherbetrachtet werden.
1.2.1 Nebenpfad:
Guterver-kehrszentren
und Lager
GVZ sind zentrale Umschlagplatze in der Nahe von Ballungszentren, in denenGuter gelagert, fur ihren Transport vorbereitet und zwischen verschiedenen Ver-kehrsmitteln umgeladen werden. Sie dienen vor allem als Schnittstelle zwischen
4
Straße und Schiene, wenn moglich auch der Binnen- und Seeschifffahrt sowiedem Luftverkehr. [ABERLE 2000]Kriterien fur die Standortoptimierung sind die Minimierung der Transportwegeund der Transportzeit sowie die Verknupfung verschiedener Logistikebenen.Die Standortplanung fur GVZ lasst sich den MINISUM-Modellen zuordnen. DieSumme der Distanzen zwischen Nachfragerknoten und potentiellen Standortensoll minimiert werden. Hub und Spoke Systeme bieten eine gute Moglichkeit.Die GVZ stellen dabei die Hubs dar, uber die die Ware zwischen den Quell- undZielorten transportiert werden.
1.2.2 Nebenpfad:
Straßen-meistereien
Straßenmeistereien sind Betriebe, die an Bundes-, Landes- und/oder Kreisstra-ßen gelegen sind und deren Instandhaltung dienen. Zu den betrieblichen Ein-richtungen der Meistereien konnen Verwaltungsraume, Aufenthaltsraume furArbeiter, Abstellhallen fur Gerate und Fahrzeuge, Werkstatten, Tankstellen undLager gehoren.Eine Straßenmeisterei soll moglichst im Schwerpunkt des zu versorgendenStraßennetzes liegen, damit dieses optimal erreicht werden kann. Ziel bei derStandortwahl ist es, die Kosten zu minimieren. Dies kann erreicht werden, indemdie Summe der Wege zwischen Meisterei und Einsatzort minimiert wird.Die Standortplanung fur Straßenmeistereien lasst sich den MINISUM-Modellenzuordnen. Die Summe der Distanzen zwischen zu versorgendem Straßenab-schnitten und potentiellen Standorten soll minimiert werden. Medianmodellein Netzwerken konnen diese Problematik darstellen. Ist die Anzahl der zu loka-lisierenden Meistereien nicht vorgegeben, so lasst sich das Optimierungsproblemin Form eines Warehouse Location Modells beschreiben.
1.2.3 Nebenpfad:
Feuer- undRettungswa-
chen
Feuerwehr und Rettungsdienste haben die Aufgabe, bei einem Notfall schnellstmoglichan dem Einsatzort einzutreffen, um Hilfe zu leisten. Die Zeit ist bei dem Einsatzdie kritische Komponente. Es muss gewahrleistet sein, dass ein hoher Prozent-satz der Bevolkerung rechtzeitige Hilfe erlangen kann.Das Ziel bei der Bestimmung der Standorte von Feuer- und Rettungswachenist zum einen die zentrale Lage im Zustandigkeitsbereich. Zum anderen mussenauch Randgebiete in einer vorgegebenen Zeit erreichbar sein. Die maximalenEntfernungen sind gering zu halten. Nicht die minimalen Kosten sind das Haupt-ziel, sondern ein bestimmter Grad an Versorgungssicherheit.
Eine 100-prozentige Abdeckung ist kaum moglich. Eine Kooperation zwischenden Feuerwehr und Rettungsdiensten existiert vielerorts. So kann die Feuerwehr
5
die Erstversorgung ubernehmen, bis der Rettungsdienst eingetroffen ist, wenndie Feuerwache naher am Einsatzort liegt.Die Standortbestimmung von Feuer- und Rettungswachen ist den MINIMAX-Modellen zuzuordnen. Es sind vor allem die Zentrenprobleme in Netzwerkenrelevant. Gesucht sind die Standorte, bei denen die maximalen Distanzen zwi-schen den Rettungswachen und den Nachfragern minimal sind.
1.2.4 Nebenpfad:
Park + RideAnlagen
Park + Ride (P+R) bezeichnet ein Prinzip der Verkehrsplanung, bei dem inder Nahe von Haltestellen des Offentlichen Nahverkehrs (OPNV) Abstellmoglich-keiten fur PKW, teilweise auch Motorrader und Busse, zur Verfugung gestelltwerden.P+R Anlagen stellen, gerade in Ballungsraumen mit regionalem Schienenver-kehr fur Pendler, die aus dem Umland in die Kernstadt fahren, eine sinnvolleAlternative zur ausschließlichen Nutzung des OPNV oder des Motorisierten In-dividualverkehrs (MIV) dar. Grunde fur eine Nutzung von P+R Anlagen sindvor allem: [HUMPFNER 2002]
• Stau
• Mangel an Stellplatzen oder eine Begrenzung der Parkdauer
• Hohe Nutzungsentgelte fur Parkierungsanlagen
• Schlechte Anbindung des Umlandes durch den OPNV bei guter Anbindungder Kernstadt
Primares Optimierungsziel ist es, den Anteil der mit dem PKW zuruckgelegtenWegelange an der Gesamtreise zu minimieren. Als weiteres Ziel soll der Anteilder Pendlerreisen maximiert werden, die von einer bisher ausschließlichen MIV-Nutzung auf P+R ubergehen. [HUMPFNER 2002]Zum einen konnen die Anlagen als kapazitierte Warenhauser angesehen werden.Die Modellierung als Warehouse Location Problem bietet sich folglich an. Au-ßerdem ist die Betrachtung von P+R Anlagen bzw. von Haltestellen an einerNahverkehrslinie als Hub denkbar. Die Modellierung als Hub Location Problemist ebenfalls moglich. Die Wege von den Nachfragern zu den P+R Platzen undvon der Zielhaltestelle zum endgultigen Ziel stellen die Speichen dar. Der Rei-seweg fuhrt demnach immer uber das Hubsystem.
6
1.2.5 Nebenpfad:
Parkplatzeund
Parkhauser
Des Weiteren ist die Standortplanung von Parkplatzen und Parkhausern instadtischen Kerngebieten von großer Wichtigkeit. Die Parkraumplanung beein-flusst nicht nur Art und Umfang des Verkehrs, sondern auch die Stadtstrukturund die Flachennutzung. Sie zahlt in Verbindung mit dem OPNV und demFußganger- und Radverkehr zu einem der bedeutendsten Steuerungsgroßen desStadtverkehrs. [TOPP 1994]Ziele der Parkraumplanung sind daher:
• Schaffung von Verkehrssicherheit
• Erhaltung und Ausbau der Leistungsfahigkeit des Straßenraumes
• Umweltschutz
• Wirtschaftlichkeit der Straßen und der Verkehrsmittel
Die Ziele und Kriterien richten sich im Allgemeinen auf die Minimierung derWege zwischen Nachfrager und Parkplatz sowie zwischen Parkplatz und Ziel.Somit ist die Zuordnung dieser Problemstellung zu den MINISUM-Modellenin Netzwerken sinnvoll. Die dort angesprochenen Optimierungsverfahren undLosungsmodelle sind fur diese Problemstellung anwendbar.
1.2.6 Nebenpfad:
Depots furoffentliche
Verkehrsmittel
Ein Depot dient als Lagerplatz fur eine Menge an Fahrzeugen. Gelagert werdenFahrzeuge, die auf Grund des Fahrplans nicht zum Einsatz kommen, Ersatz-fahrzeuge oder Fahrzeuge, die gewartet werden mussen.Der Verkehrsbetrieb hat die Aufgabe, die Fahrzeuge den Depots zuzuordnen,die moglichst nah an deren Anfangs- und Endhaltestellen liegen.Grundlage der Depotplanung sind der Einsatzplan und die Anzahl der Fahrzeu-ge, die je Haltestelle benotigt werden.
Entscheid-ungskriterien
Die im Rahmen einer Optimierung veranderlichen Entscheidungsvariablensind:
• die Zuordnung der Fahrzeuge zu den Depots
7
• die Anzahl der zu implementierenden Depots
Die Anzahl der Depots hat kaum Einfluss auf die Dauer der Reisezeit und dieQualitat des offentlichen Verkehrsnetzes. Eine Verschlechterung der Attrakti-vitat des OPNV trifft nur dann ein, wenn auf Grund eines unerwarteten Aus-falls eines Fahrzeugs Ersatz aus einem Depot benotigt wird. Die Behebung einesStorfalls dauert bei wenigen Depots langer.
Ziele Ziel ist es, die optimale Anzahl an Depots zu finden, durch die die Gesamtkostenminimiert werden. Zu viele Depots fuhren zu hohen Fixkosten der Investition,zu wenige Depots steigern die variablen Transportkosten.Die Depotplanung fur offentliche Verkehrsmittel lasst sich den MINISUM-Modellenin Netzwerken zuordnen. Die Summe der Fahrten von den Depots zu den An-fangshaltestellen sowie von den Endhaltestellen zuruck zu den Depots soll mi-nimiert werden.Weiterhin ist es realitatsnaher, die potentiellen Standorte auf die Punkte einesNetzwerks zu beschranken.Medianmodelle kommen zur Anwendung, falls die Anzahl der Depots fest vor-gegeben ist und fur diese die optimalen Standorte gesucht werden.Die Problemstellung lasst sich den Warehouse-Location-Problemen zuordnen,wenn die Anzahl der Depots variabel ist und die Summe der Distanzen mini-miert werden soll.Zudem ist davon auszugehen, dass die Kapazitaten der Depots nicht derart fle-xibel sind, dass alle Fahrzeuge einem Depot zugeordnet werden konnen. Dahermussen zusatzlich Kapazitatsbeschrankungen beachtet werden.
1.2.7 Nebenpfad:
Haltestellenim Rahmen
einesLiniennetzes
Ziel der Planung des Liniennetzes ist es, eine dem Verkehrsaufkommen gerechtwerdende Versorgung einer Region mit offentlichem Verkehr sicher zu stellen.Dazu zahlt neben dem Bau von Strecken und Verbindungen auch die Errichtungvon Haltestellen. Das Liniennetz ist dabei in der Regel historisch gewachsen. Ineiner uber Jahrhunderte gewachsenen Infrastruktur ist es kaum moglich, Ver-kehrsnetze von Grund auf neu zu errichten [BUSSIECK; WINTER; ZIMMERMANN 1997].Vielmehr befasst sich die Planung des Liniennetzes mit [SCHOBEL 2003]
• dem Finden neuer Haltestellen in einem bestehenden Liniennetz,
• dem Schließen von bestehenden Haltestellen,
• dem Bau von neuen Linien, Verbindungen und Anschlussen in einem be-stehenden Liniennetz,
8
• dem Schließen von Linien, Verbindungen und Anschlussen in einem beste-henden Liniennetz und
• dem Finden von Sub-Netzwerken.
Entscheid-ungskriterien
Entscheidungskriterien, die den Standort einer Haltestelle beeinflussen, sindim Rahmen der Standortsuche von Haltestellen sehr vielfaltig und orientierensich an der zugehorigen Zielsetzung.Als Optimierungskriterien sind dabei folgende von Interesse:
• Zugangsweiten von den Nachfragerknoten zu den Haltestellen
• Anzahl der Haltestellen
• Uberdeckung der Nachfrageknoten (Erschließungswirkung der Haltestel-len)
• Investitions- und Betriebskosten des Betreibers bzw. Opportunitatskostendes Nutzers durch lange Reisezeiten
• Tur-zu-Tur Reisezeit
Ziele Als primares Ziel kann bei der Standortplanung die Minimierung der Ge-samtkosten - also der Investitions- und Betriebskosten als auch der Zeitoppor-tunitatskosten des Nutzers durch lange Reisezeiten - betrachtet werden.Typische weitere Ziele bei der Haltestellenplanung stellen sich wie nachstehendaufgefuhrt dar [SCHOBEL 2003]:
• Maximierung der Uberdeckung der Nachfragerknoten durch Haltestellen
• Implementierung von Haltestellen, die nicht weiter entfernt sind als einbestimmter Radius r zu so vielen potentiellen Nachfragern wie moglich
• Minimierung der zusatzlichen Reisezeit im Verkehrsnetzwerk
• Minimierung der Anzahl an Haltestellen
9
• Minimierung der durchschnittlichen Tur-zu-Tur Reisezeit aller Nachfrager
• Maximierung des Erloses des Verkehrsbetriebs
10
2 Modelle zur Standortbestimmung
2.1 Modellcharakteristika
Standortplan-ung
Die Standortplanung ist Teilgebiet der Standorttheorie und gehort zu den Raum-wirtschafttheorien der Wirtschaftgeographie. Sie befasst sich mit der optimalenraumlichen Lokalisation von Wirtschaftstatigkeiten bzw. Unternehmungen unddem Einfluss von Absatz und Gewinn auf den Standort bzw. die Standortent-scheidung. Hierbei wird das Standortverhalten von Haushalten, Unternehmenund staatlichen Einrichtungen aufgezeigt. Durch Modelle wird weitergehend ver-sucht darzustellen, warum sich verschiedene Wirtschaftssubjekte an bestimmtenOrten ansiedeln. [http://www.wikipedia.de].Zu unterscheiden sind bei der Standortbestimmung die volkswirtschaftlicheStandortplanung, die betriebliche Standortplanung und die innerbe-triebliche Standortplanung bzw. Layoutplanung [DOMSCHKE; DREXL 1996].
Modelle Zur Modellierung der betrachteten Probleme im Rahmen normativer Ansatzekonnen zum einen die Methoden der Standortplanung in der Ebene, zumanderen die Standortbestimmung in Netzwerken herangezogen werden.
Standortplan-ung in der
Ebene
Bei der Standortbestimmung in der Ebene wird davon ausgegangen, dassdie Nachfragerorte (bspw. Kundenorte) auf einer homogenen Flache in der Ebe-ne verteilt sind. Jeder Punkt der Ebene kommt folglich als potentieller Standortin Frage.[DOMSCHKE; DREXL 1996] Diese Standortmodelle finden ihre An-wendung, wenn uber die moglichen Standorte nur wenige Informationen vorlie-gen, die Fixkosten standortunabhangig sind und die Bedingungen wie Platzan-gebot sowie strategisch gunstige Lage keine Entscheidungsfaktoren darstellen.[KLOSE 2001]
Entfernungen zwischen zwei Punkten werden gemaß bestimmter Metriken ge-messen. [DOMSCHKE; DREXL 1996] Die am haufigsten verwendeten Metrikenzur Entfernungsmessung sind die rechtwinklige Entfernungsmessung und die eu-klidische Entfernungsmessung.
Standortplan-ung in
Netzwerken
Im Gegensatz zur Standortbestimmung in der Ebene ist bei der Standortbe-stimmung in Netzwerken die Menge potentieller Standort auf die Menge derKnoten eines Graphen und die Menge der Punkte auf den Kanten beschrankt.Distanzen ergeben sich nicht durch bestimmte Metriken, vielmehr sind sie be-stimmt durch die Langen kurzester Wege im Netzwerk.
11
Kontinuierlicheund diskrete
Standortplan-ung
Eine weitere Differenzierung muss zwischen kontinuierlicher und diskreterStandortplanung getroffen werden.Ausgehend von der Annahme einer homogenen Flache, werden bei der konti-nuierlichen Standortplanung infinitesimal kleine Verschiebungen des Standorteszugelassen. Es existiert eine unendliche Menge moglicher Standorte. Im Gegen-satz dazu wird bei der diskreten Standortplanung nur eine begrenzte Mengepotentieller Standorte in die Betrachtung mit einbezogen. [LIEBMANN 1971]Ahnliches gilt fur Netzwerke. Durfen potentielle Standorte nur auf Knoten plat-ziert werden, wird von einem diskreten Modell gesprochen. Konnen dagegenpotentielle Standorte auch auf den Kanten eines Netzwerkes platziert werden,handelt es sich um kontinuierliche Probleme. [WEINBRECHT 2000]
WeitereMerkmale
Daruber hinaus konnen Standortprobleme und zugehorige Modelle der Stand-ortplanung anhand weiterer Merkmale unterschieden werden. Zu diesen zahlenunter anderen:
• die Form der Zielfunktion
• MINISUM-Lokationsprobleme: Ziel ist es, die Summe der Entfernungenzwischen Nachfragern und allen Standorten, bei vollstandiger Deckungdes Bedarfs, zu minimieren.
• Uberdeckungsprobleme: Ziel ist es, die Uberdeckung von Nachfragerkno-ten durch Standorte zu gewahrleisten. Ein Sonderfall stellt das MINIMAX- Kriterium dar. Gesucht ist die Lage der Standorte, bei denen die maxi-male Distanz zwischen Standort und Nachfrager minimal ist.
• Berucksichtigung einer Kapazitatsrestriktion: Unkapazitierte bzw. kapazi-tierte Modelle
• Modelle mit elastischer bzw. unelastischer Nachfrage
• statische Modelle bzw. dynamische Modelle
12
2.2 Ebene Modelle
Standortbe-stimmung in
der Ebene
Bei der Standortplanung in der Ebene kann zwischen MINISUM- und MINIMAX-Modellen unterschieden werden.Zum einen kann die Summe der gewichteten Distanzen zwischen Standorten undden Nachfragerknoten minimiert werden. Hierbei handelt es sich um WeberModelle.Des Weiteren kann mit Hilfe von Zentrenmodellen die maximale Distanz zwi-schen Nachfragern und Standorten minimiert werden. Hierbei handelt es sichum Zentrenprobleme.
2.2.1 Nebenpfad: Weber Probleme
Bestimmungeines
Standortes
Das Problem der Bestimmung eines neuen Standortes in der Ebene unter derBeachtung der MINISUM-Zielsetzung - auch Steiner-Weber-Problem genannt -kann wie folgt beschrieben werden
EinstufigesWeber Modell
Es ist ein Standort gesucht, so dass die Entfernung zwischen diesem Standortund allen Nachfragerknoten minimal ist. Die Transportkosten sind dabei pro-portional zu der Entfernung. Der Bedarf der Nachfrager stellt das Gewicht derKnoten dar.
Modellfor-mulierung
Mathematisch lasst sich das Modell wie folgt formulieren:Minimiere F (x, y) = c ∗
∑nj=1 bj
√(x− uj)2 + (y − vj)2
mitx, y = Koordinaten der Standorteu, v = Koordinaten der Nachfragerknotenbj = Nachfragergewichtec = Transportkosten
Losungsver-fahren
Das iterative Verfahren von Miehle beginnt mit vorgegebenen Startwertenfur x und y, die in Gleichungen eingesetzt werden, die man durch partielle Ab-leitungen der ursprunglichen Zielfunkton erhalt.Durch Berechung der Gleichungen ergeben sich neue Koordinaten (x1, y1), dieim folgenden Iterationsschritt wiederum in die Gleichungen eingesetzt werden.Nach einer endlichen Anzahl von Iterationsschritten, einer Anzahl vorgegebenerSchritte oder bei nur noch marginaler Veranderung der Ergebniswerte wird dasVerfahren schließlich abgebrochen.
13
Bestimmungmehrerer
Standorte
Gegeben seien n Kunden mit fest vorgegebenen Koordinaten. Es sollen Einrich-tungen oder Depots so bestimmt werden, dass die Transportkosten zwischen denDepots sowie zwischen Depots und Kunden minimiert werden. [DOMSCHKE; DREXL 1996]
Losungsver-fahren
Ahnlich zum einfachen Weber Modell existiert ein iteratives Verfahren, welchesdie Summe der Distanzen zwischen Nachfragern und Standorten minimiert.Das Hyperboloid-Approximationsverfahren berechnet fur eine vorgegebe-ne Anzahl an Standorten die Koordinaten.
2.2.2 Nebenpfad: Zentrenprobleme
Zentrenpro-bleme
Im Gegensatz zu den Weber-Modellen sind Zentrenprobleme in der Ebene MINIMAX-Lokationsprobleme. Ziel ist, wie bei Zentrenproblemen in Netzwerken, die Mini-mierung der maximalen resultierenden Distanz zwischen Standorten und Nach-fragerknoten.Im Falle p = 1 kann das Problem durch ein einfaches geometrisches Verfahrengelost werden. Es ist ein Kreis mit minimalem Radius gesucht, der alle Kunden-orte einschließt.Des Weiteren konnen Heuristiken und Methoden der Spaltengenerierung fur dasMulti-Weber Problem mit entsprechenden Modifikationen auch auf p-Zentren-probleme in der Ebene ubertragen werden. [KLOSE 2001]
14
2.3 Uberdeckungsprobleme
Uberdeckungs-probleme
Uberdeckungsprobleme lassen sich in Set Covering Probleme, Maximum Co-vering Probleme und Zentrenprobleme unterteilen (siehe folgende Abbildung[DASKIN 1995]).
Details Details zu den einzelnen Modellen finden sich auf folgenden Unterseiten.Set Covering ProblemMaximum Covering ProblemZentrenproblem
15
2.3.1 Nebenpfad: Set Covering
Set CoveringProblem
Aus einer gegebenen Menge potenzieller Standorte ist eine Teilmenge so zubestimmen, dass alle Nachfragerpunkte uberdeckt werden und die Summe derKosten cj aller Standorte minimal ist.
Modellfor-mulierung
Mathematisch formulieren lasst sich das Set Covering-Modell wie folgt:Minimiere
∑nj=1 cj ∗ xj
unter den Nebenbedingungen∑nj=1 aij ∗ xj ≥ 1 ∀i
xj ∈ (0, 1) ∀jmit
aij =(
1 falls Standort j Nachfragerknoten i uberdeckt0 sonst
)xj =
(1 falls Standort j implementiert wird
0 sonst
)cj = Kosten, um einen Standort j zu implementieren
Gegeben ist bei diesem Modell eine binare m x n Matrix A = (aij) sowie ein n-dimensionaler Kostenvektor c = cj . Ferner sind die Mengen I := (1, ...,m) und J :=(1, ..., n) gegeben. Das Element i ∈ I bezeichnet dabei die i-te Zeile der MatrixA, das Element j ∈ J die j-te Spalte der Matrix A. cj sind die Kosten furdie Spalte j ∈ J . Wenn die Matrixelemente aij den Wert 1 annehmen, wirddavon gesprochen, dass eine Zeile von einer Spalte uberdeckt wird. Ziel ist es,eine kostenminimale Teilmenge S ⊂ J mit Kosten
∑j∈ S cj zu bestimmen, so
dass alle Zeilen aus I von Spalten aus S uberdeckt werden. Die erste Nebenbe-dingung legt fest, dass jeder Nachfragerknoten von mindestens einem Standortuberdeckt werden muss [ANNEN 2003].
AufgabeWie sieht die Uberdeckungsmatrix zu folgendem Problem aus? [SCHOBEL 2003]
16
HOTSPOT Losung: 2
Losungsmog-lichkeit
Exakte Verfahren zur Losung von Set Covering Problemen lassen sich inCutting Plane Algorithmen, Branch & Bound Algorithmen und Branch & CutAlgorithmen untergliedern.Heuristische Verfahren finden bei der Losung sehr großer Set Covering Pro-bleme Anwendung, bei denen der Einsatz exakter Verfahren auf Grund einesunangemessenen Zeitbedarfs nicht sinnvoll ist. Mit Hilfe von Heuristiken konnenNaherungslosungen, teilweise auch Optimallosungen, gefunden werden.Ein einfacher Greedy Algorithmus[SCHOBEL 2003] wird im Rahmen desLosungsweges des bikriteriellen Standortproblems verwendet, um benotigte Zwi-schenlosungen zu finden. Gerade bei Uberdeckungsproblemen mit streng mono-toner Uberdeckungsmatrix mit Intervalleigenschaft ist dieser Algorithmus sehrgut geeignet, optimale Losungen fur das ungewichtete Set Covering Problem zufinden.
Anwendungs-gebiete
Die bedeutendsten Anwendungsgebiete von Set Covering Problemen sind diePersonaleinsatzplanung von Fluggesellschaften und des Schienenverkehrs sowiedie Standortplanung. Aufgrund hoher Relevanz fur die Praxis wurden zahl-reiche exakte und heuristische Ansatze zur Losung dieser Probleme entwickelt
17
[ANNEN 2003].
Infoseite Greedy Algorithmus fur ungewichtete Set Covering Probleme mit Intervallei-genschaft
mitS = Menge an Haltestellen sD = Menge an Nachfragerknoten dr = Radius der Uberdeckungfd = min(s ∈ S : ads = 1) ist das erste Element in einer Zeile der Uberdeckungsmatrixmit dem Wert 1ld = max(s ∈ S : ads = 1) ist das letzte Element in einer Zeile der Uberdeckungsmatrixmit dem Wert 1
Infoseite IntervalleigenschaftEine Matrix hat die Intervalleigenschaft oder Consecutive Ones Property (kurzC1P), falls durch Permutation der Spalten eine Form entstehen kann in der gilt:aik = 1 und ail = 1 und k < l ⇒ ∀k ≤ j ≤ l aij = 1Von starker C1P wird gesprochen, wenn die Matrix diese Form ohne vorherigePermutation der Spalten besitzt.Beispiel:
Fur eine Uberdeckungsmatrix eines Verkehrsnetzes bedeutet die Intervalleigen-schaft, dass sich die potentiellen Haltestellen auf dem Netzwerk in einer Reihen-folge befinden, so dass ein Nachfragerknoten immer nur von direkt aufeinanderfolgenden Haltestellen uberdeckt wird.
18
2.3.2 Nebenpfad: Maximum Covering
Problem-stellung
Eines der Probleme des Set Covering Modells ist, dass die Anzahl von Stand-orten, die eine vollstandige Erschließung ermoglichen, schnell die maximal mogli-che Anzahl an Standorten - beispielsweise aus Kostengrunden - uberschreitet.Außerdem unterscheidet das Set Covering Modell nicht nach der Gewichtungder Nachfrager. So ist es gleichsam wichtig, einen Nachfragerknoten mit zehnNachfragern bzw. mit einer niedrigen Bedarfsmenge zu uberdecken, als aucheinen Nachfragerknoten mit 1000 Nachfragern bzw. einer hohen Bedarfsmenge.Aus diesem Grund kann durch die Lockerung des Kriteriums, dass alle Nach-frager uberdeckt werden sollen und der Fixierung der Anzahl der Standorte aufeine bestimmte Große, das Maximum Covering Location Model wie folgtformuliert werden.
MaximumCoveringProblem
Mit einer gegebenen Anzahl von Standorten p soll eine maximale Bedarfsmengeb der Nachfragerknoten d uberdeckt werden.
Modellfor-mulierung
Mathematisch lasst sich das Modell wie folgt formulieren:Maximiere
∑mi=1 bi ∗ yi
unter den Nebenbedingungenyi ≤
∑nj=1 aij ∗ xj ∀i∑n
j=1 xj ≤ Pxj ∈ (0, 1) ∀jyi ∈ (0, 1) ∀imitbi = Nachfrage des Knoten iP = Anzahl der zu implementierenden Standorte
aij =(
1 falls Standort j Nachfragerknoten i uberdeckt0 sonst
)xj =
(1 falls Standort j implementiert wird
0 sonst
)yi =
(1 falls Nachfragerknoten i uberdeckt wird
0 sonst
)Die Zielfunktion maximiert die Hohe des uberdeckten Bedarfs der Nachfrager-knoten. Die erste Nebenbedingung besagt, dass ein Knoten von mindestens ei-nem Standort uberdeckt werden muss. Die Anzahl der zu implementierendenStandorte ist durch die zweite Nebenbedingung vorgegeben.
19
Anwendungs-gebiete
Praktische Anwendung fur das Maximum Covering Location Model stellen dieStandortoptimierung und Positionierung von Notfalleinrichtungen, offentlichenVersorgungssystemen oder finanzwirtschaftlichen Einrichtungen dar [ANNEN 2003].
2.3.3 Nebenpfad: Zentren
MINIMAX-Probleme
Bei einigen Standortmodellen ist die bloße Minimierung der Summe der Di-stanzen und der damit verbundenen Transportkosten nicht sinnvoll. Dies istdann der Fall, wenn Zeit die kritische Komponente darstellt. [KLOSE 2001] Eshandelt sich um eine MINIMAX - Problemmodellierung.Lokationsprobleme, die die Minimierung der maximalen Distanz zum Ziel haben,werden Zentrenprobleme genannt [KLOSE 2001]. Sie konnen wie folgt beschrie-ben werden:
p-Zentrenmodelle
Eine gegebene Anzahl an Standorten p ist so zu bestimmen, dass die maxima-le gewichtete Distanz zwischen den Nachfragerknoten und dem jeweils nachstgelegenen Standort p minimiert wird [DASKIN 1995].
Modellfor-mulierung
Mathematisch lasst sich das Modell wie folgt formulieren:Minimiere runter den Nebenbedingungen∑
j yij = 1 ∀i∑j xj = P
xj ≥ yij ∀i, jr ≥ bi ∗
∑j γij ∗ yij ∀i
xj ∈ (0, 1)yij ≥ 0mit
r = maximale Distanz zwischen einem Nachfragerknoten und dem nachstgele-genen Standort
γij = Distanz vom Nachfragerknoten i zum Depot j
bi = Nachfrage des Knoten i
P = Anzahl der zu implementierenden Standorte
xj =(
1 falls Standort j implementiert wird0 sonst
)
20
yij =(
1 falls Standort j Knoten i zugeordnet wird0 sonst
)Die Zielfunktion minimiert die maximalen Distanzen zwischen den Nachfrager-knoten und dem jeweils nachstgelegenen Standort p. Die erste Nebenbedingungstellt sicher, dass der Bedarf aller Nachfragerknoten gedeckt wird. Hierzu kannein Nachfrager von mehreren Depots beliefert werden. Die zweite Nebenbedin-gung fordert, dass genau P Standorte implementiert werden. Die dritte Neben-bedingung sagt aus, dass die Nachfragerknoten nur von Depots beliefert werdenkonnen, wenn diese implementiert sind. Bedingung vier verlangt, dass die ma-ximale gewichtete Distanz zwischen Nachfrager und Kunde großer sein muss alsjede andere Distanz zwischen Kunden und eben diesem Depot.
Losungsmog-lichkeiten
Zur Losung der Zentrenprobleme konnen verschiedene Verfahren zur Anwen-dung kommen. Kariv und Hakimi haben Algorithmen entwickelt, mit denensich absolute 1-Zentrenprobleme losen lassen. Hierbei wird zunachst von jederKante das Zentrum bestimmt. Im Anschluss kann mit diesen Punkten das ab-solute 1-Zentrum ermittelt werden. [DASKIN 1995]
Des Weiteren konnen Zentrenprobleme in eine Folge zu losender Uberdeckungs-probleme transformiert werden. Es lassen sich beispielsweise heuristische Ver-fahren fur Uberdeckungsprobleme zur Bestimmung suboptimaler Losungen furp-Zentrenprobleme anwenden. [KLOSE 2001]
Anwendungs-gebiete
MINIMAX - Modelle finden sich vorwiegend bei Lokationsproblemen der offent-lichen Hand und betreffen beispielsweise die Standortbestimmung fur Feuerwa-chen, Depots fur Rettungsdienste, Krankenhauser und Schulen. [KLOSE 2001]
21
2.4 MINISUM Probleme
MINISUM-Probleme
MINISUM-Modelle lassen sich in Medianmodelle, Warehouse Location Modelleund Hub & Spoke Modelle unterteilen.
Details Details zu den einzelnen Modellen finden sich auf folgenden Unterseiten.MedianproblemeWarehouse Location ProblemeHub & Spoke Systeme
2.4.1 Nebenpfad: Median
Mediane Es sind p Punkte auf einem Netzwerk so zu bestimmen, dass die Summe dergewichteten Distanzen der Knoten des Graphen zum jeweils nachstgelegenen derbestimmten Punkte minimal ist. Die so bestimmten p Punkte auf dem Graphenwerden als p-Median eines Graphen bezeichnet [KLOSE 2005].
1-Median Im einfachsten Fall wird ein ungerichteter Graph G betrachtet und der 1-Medianbestimmt.
22
Sei G = [S, E, c, b] ein ungerichteter Graph mit Knotenmenge S, KantenmengeE, nicht-negativen Knotengewichten bj und Kantenlangen ci, dann bezeichnetσ(i) :=
∑j∈S γij ∗ bj ∀i
die Summe der gewichteten kurzesten Entfernungen zwischen Knoten i undjedem Knoten j von G. Ein Knoten im mit den Eigenschaftenσ(im) = min(σ(i)|i ∈ S)wird als Median des Graphen G bezeichnet.
Aufgabe:Bestimmungdes Medians
Bestimmen Sie den 1-Median des dargestellten Graphen (die Knotengewichte bj
sind fur alle Knoten gleich 1)!
3
p-MedianProblem
Bei der Bestimmung mehrere Mediane bietet sich die Formulierung als binareslineares Optimierungsproblem an.
Modellfor-mulierung
Das p-Median Modell lautet:Minimiere F (x, y) =
∑mi=1
∑nj=1 bj ∗ γij ∗ xij
unter den Nebenbedingungen∑mi=1 xij = 1 ∀j
xij − yi ≤ 0 ∀i, j∑mi=1 yi = p ∀i
yi ∈ (0, 1) ∀i
xij ∈ (0, 1) ∀i, jmitbj=Bedarf des Knoten jγij=Distanz zwischen zwei Knoten i und j
xij =(
1 falls Knoten i Knoten j zugeordnet wird0 sonst
)yi =
(1 falls Knoten j zum p Median gehort
0 sonst
)
23
Die zweite Nebenbedingung legt die Anzahl der zum p-Median gehorenden Kno-ten auf p fest. Die dritte Nebenbedingung stellt sicher, dass ein Nachfrager j nureinem Knoten i zugeordnet wird, der zum p-Median gehort. Des Weiteren besagtdie erste Nebenbedingung, dass jeder Knoten nur einem Median zugeordnetwird [DOMSCHKE; DREXL 1996].
Losungsmog-lichkeiten
Da Medianprobleme von der Problemformulierung Ahnlichkeiten mit den imFolgenden beschriebenen Warehouse Location Problemen aufweisen, konnen diedort aufgezeigten Losungsverfahren auch fur Medianprobleme angewendet wer-den.
2.4.2 Nebenpfad: Warehouse
WarehouseLocationProbleme
Durch Warehouse Location Probleme lassen sich verschiedene Standortentschei-dungsprobleme abbilden. Grob unterscheiden lassen sich die folgenden Modelle:
• Unkapazitierte vs. Kapazitierte WLP
• Einstufige vs. Mehrstufige WLP
• Einprodukt-WLP vs. Mehrprodukt-WLP
Modellfor-mulierung
Mathematisch formulieren lasst sich das WLP wie folgt:Minimiere F (x, y) =
∑mi=1
∑nj=1 cij ∗ xij +
∑mi=1 fi ∗ yi
unter den Nebenbedingungen∑mi=1 xij = 1 ∀j
xij − yi ≤ 0 ∀i, jyi ∈ (0, 1) ∀ixij ≥ 0 ∀i, jmit cij=variable Transport- und Lagerhaltungskostenfi=fixe Depot- bzw. Standortkosten der Investition
xij =(
1 falls Nachfrager j von einem Lager am Standort i voll beliefert wird0 sonst
)yi =
(1 falls am potentiellen Standort i ein Depot errichtet wird
0 sonst
)Der erste Teil der Zielfunktion minimiert die variablen Kosten cij des Trans-ports und der Lagerhaltung, der zweite Summand minimiert die fixen Depot-bzw. Standortkosten fi der Investition. Ferner stellt die erste Restriktion dieNachfragebedingung dar, und die folgende Nebenbedingung garantiert, dass diefixen Standortkosten erfasst werden, sobald ein Transport von einem Standort jstattfindet. Ein Kunde wird zwingend vom nachstgelegenen Lager voll beliefert.
24
Losungsver-fahren
Zur Losung unkapazitierter WLP kommen exakte sowie heuristische Verfahrenin Frage.
• Exaktes Branch & Bound Verfahren von Erlenkotter
• Heuristische Eroffnungs- und Verbesserungsverfahren
• Heuristische Metastrategien
2.4.3 Nebenpfad: Hub&Spoke
Hub & SpokeNetzwerke
Ein Hub & Spoke Netz ist eine spezielle Art von Netzwerk. In diesem sind dieQuellen und die Ziele von Wegen nicht direkt miteinander verbunden, sondernindirekt uber einen oder mehrere Hubs. Die Verbindungen zwischen den Quellenbzw. den Zielen laufen strahlen- oder sternformig auf ein Hub zu, und die Hubssind innerhalb des Hub-Netzes miteinander verbunden. Die Hubs erfullen dabeidie Funktion von Drehkreuzen bzw. Umschlagpunkten. [MAYER 2001]
Abbildungeines
Hub&SpokeNetzes
Ziel Das am haufigsten angestrebte Ziel bei Hub Location Problemen ist, ahnlichwie bei den meisten Standortplanungsproblemen, die Minimierung von Kosten.Zu berucksichtigende Kosten konnen neben den fixen und variablen Kosten auchKosten der Verspatung aus Sicht der Nachfrager sein. Es wird davon ausgegan-gen, dass durch die Nutzung von Interhub-Verbindungen die Transportkostenpro Wegeinheit im Hubnetz durch einen bestimmten Faktor kleiner 1 abdis-kontiert werden. Der Transport uber Hubs soll dadurch gunstiger sein als eineDirektverbindung der Quelle mit dem Ziel, obwohl der zuruckgelegte Weg meistgroßer ist. [MAYER 2001]
25
Losungsver-fahren
Wird davon ausgegangen, dass die Transportkosten proportional zu der zuruck-gelegten Strecke sind, dann handelt es sich bei Hub Location Problemen umeine MINISUM-Zielsetzung.Zur Losung von Hub Location Problemen existieren eine Reihe exakter Losungs-verfahren sowie Heuristiken. Neben verschiedenen Branch & Bound Verfahrenkonnen heuristische Eroffnungsverfahren wie Add und Drop, Verbesserungsver-fahren sowie heuristische Metastrategien zur Anwendung kommen.
Anwendungs-bereiche
Anwendung finden Hub Location Probleme vor allem im Luft-, Schifffahrts- undStraßenguterverkehr, bei Speditionen, Paketdiensten oder der Post sowie beimDesign von Computer- und Kommunikationsnetzwerken [MAYER 2001].Im Offentlichen Verkehr konnen die Verbindungen zwischen den Hubs schnel-le Verbindungen zwischen zwei Zentren und die Speichen langsame Bus- oderStraßenbahnlinien zu zentralen Haltestellen bzw. fußlaufige Distanzen zwischenQuelle oder Ziel und Haltestelle darstellen.
26
2.5 Modelle zur Haltestellenoptimierung
Haltestellen inNetzwerken
Zur Darstellung von Standortproblemen von Haltestellen auf Netzwerken konnenverschiedene Modelle angewendet werden.Eine Moglichkeit ist die Modellierung als Medianproblem.Daruber hinaus konnen diese Probleme als Uberdeckungsprobleme modelliertwerden. Dabei existieren unterschiedliche Modellierungsansatze [SCHOBEL 2005]:
1. Door-to-Door Travel Time Stop Location Problem
2. Complete Cover Stop Location Problem
3. Bicriterial Stop Location Problem
2.5.1 Nebenpfad: Door-To-Door Travel Time Stop Location Pro-blem
Door-To-DoorTravel Time
Stop LocationProblem
Bei der Betrachtung der gesamten Reisezeit (Door-To-Door Travel Time) sinddie Zeiten enthalten, die ein Nachfrager benotigt, um von einem Ausgangs-punkt zu einer Haltestelle zu gelangen, die anschließende Reisezeit innerhalbdes offentlichen Verkehrsnetz und die Abgangszeit von der Zielhaltestelle zumgewunschten Zielort.
Abbildung 1:Beispiel fur die
Tur-zu-TurReisezeit
Optimierung Anstelle der Berechnung der gesamten Reisezeit wird in diesem Modell nur dieAnderung der Reisezeit berechnet, die sich durch die Anordnung und die Anzahlvon Haltestellen ergibt.
27
Anderungen ergeben sich zum einen durch eine geringere Zugangsdistanz zu denHaltestellen, bedingt durch eine hohe Anzahl vorgesehener Haltepunkte.Zum anderen erhoht sich die Reisezeit innerhalb des Verkehrsnetzes durch einehohe Anzahl Stopps. Zu minimieren ist die Differenz zwischen der Reisezeit imVerkehrsnetz und der Zugangszeit zu der Haltestelle, die dem Nachfrager amnachsten liegt.
2.5.2 Nebenpfad: Complete Cover Stop Location Problem
CompleteCover Stop
LocationProblem
Das Complete Cover Stop Location Problem kann wie folgt formuliert werden:
Modellfor-mulierung
Fur ein gegebenes Verkehrsnetz G, eine gegebene Anzahl an Reisenden auf denverschiedenen Relationen und eine endliche Menge an Nachfragerknoten mitNachfragern wd, die sich in einer bestimmten Entfernung γd < r zu der nachstenHaltestelle befinden, soll eine Menge S an Haltestellen gefunden werden, die alleNachfragerknoten uberdeckt, so dass die zusatzliche Reisezeit bzw. die Zeitop-portunitatskosten der Wartezeit fur die Nutzert+travel(S) =
∑s∈S cs
minimal ist.
Diese Problemformulierung entspricht einem Set Covering Problem. Als mogli-che Losungsmenge existiert eine endliche dominierende Menge potentieller Stoppsauf dem Verkehrsnetzwerk.
Losungsmog-lichkeit
Eine Moglichkeit ist, dieses unter zu Hilfenahme eineskurzesten-Wege Algo-rithmus zu losen. Dazu muss ein gerichteter Digraph bestimmt werden, dersich aus der Uberdeckungsmatrix der Problemformulierung ableiten lasst. DieKantengewichte entsprechen den cs- Werten. Die Verbindungen in diesem Di-graph entsprechen dabei allen Moglichkeiten, potentielle Haltestellen auf demNetzwerk zu implementieren, die eine vollstandige Uberdeckung aller Nachfra-gerknoten garantieren.Der Set-Covering Digraph GSC = (SSC , ASC) ist deshalb definiert alsSSC = S ∪ (s, t) undASC = ((i, j) : i < j und fj≤li+1) ∪ ((s, i) : fi = 1) ∪ ((i, t) : li = |D|)Die Gewichte der Kanten betragen cij = cs mitcij = cj falls j 6= t und 0 falls j = tDie Gewichte entsprechen der Anzahl der Reisenden, fur die sich auf einer Rela-tion, bedingt durch zusatzliche Stopps, die Reisezeit um eine vorgegebene Zeiterhoht. Ziel ist es nun, einen kurzesten Weg von s nach t zu bestimmen, der
28
genau die Haltestellen berucksichtigt, bei denen die Summe der Wartezeitenminimal ist und alle Nachfragerknoten uberdeckt werden.
Beispiel Das folgende kleine Beispiel soll die Vorgehensweise erlautern:
Problem Gegeben sei das Problem mit der Uberdeckungsmatrix Acov = (ads):
Acov =
1 1 1 00 1 1 10 0 1 1
und der Anzahl an Reisenden cs, fur die sich die Reisezeit im Verkehrsnetzbedingt durch zusatzliche Haltestellen erhoht:c1 = 4 c3 = 6c2 = 3 c4 = 2
AufgabeWelche Form hat der Digraph zu obenstehender Uberdeckungsmatrix?HOTSPOT Losung: 1
Dijkstra-Algorithmus
Mit Hilfe des Dijkstra Algorithmus kann nun ein kurzester Weg von s nach tbestimmt werden.Die Losung des Beispiels stellt sich wie folgt dar:
Kurzester Weg
Losung (bitte nur klicken, wenn Sie obenstehende Aufgabe schon gelosthaben!!!!)
2.5.3 Nebenpfad: Bicriterial Stop Location Problem
BicriterialStop Location
Problem
Unter bestimmten Bedingungen erscheint es als nicht sinnvoll, alle Nachfragerdurch Haltestellen zu uberdecken, sondern nur einen bestimmten Prozentsatz.Einerseits ist es unter realen Bedingungen unrealistisch, alle Nachfrager durchHaltestellen uberdecken zu konnen, andererseits konnte dies zu einer sehr ho-hen Anzahl an Haltestellen fuhren, was einen wirtschaftlichen und qualitativhochwertigen Betrieb in Bezug auf die Reisezeit nicht zuließe.Das bikriterielle Standortproblem fur Haltestellen kann wie folgt formuliert wer-den:
Modellfor-mulierung
Fur ein gegebenes Verkehrsnetz G, eine gegebene Anzahl an Reisenden auf denverschiedenen Relationen und eine endliche Menge an Nachfragerknoten mitNachfragern wd, die sich in einer bestimmten Entfernung γ < r zu der nachstenHaltestelle befinden, soll eine Menge S an Haltestellen gefunden werden, so dassdie zusatzliche Reisezeitt+travel(S) =
∑s∈S cs
und die Uberdeckung der Nachfrager−qcover = −
∑d∈cover(S) wd
minimal sind.
Unter der Minimierung beider Funktionen ist folglich zu verstehen, dass pareto-optimale Losungen fur t+travel und qcover so gefunden werden sollen, dass eineMenge moglicher Stopps S1 eine andere Menge moglicher Stopps S2 dominiert.S1 dominiert hierbei S2, wennt+tavel(S1) ≤ t+travel(S2) undqcover(S1) ≥ qcover(S2)und in mindestens einer Ungleichung nicht die Gleichheit auftritt. Unter Pareto-optimalen Losungen wird in der Okonomie eine Allokation verstanden, in der esnicht mehr moglich ist, ein Wirtschaftssubjekt besser zu stellen, ohne gleichzeitig(mindestens) ein Wirtschaftssubjekt schlechter zu stellen.Die Pareto-optimale Losung S* ist dann eine mogliche Menge an Stopps, dievon keiner anderen Menge moglicher Stopps dominiert wird.
Die Punkte(
t+travel(S∗)qcover(S∗)
)von Pareto-Losungen S* werden als effizient bezeich-
net.
30
Losungsmog-lichkeit
Zur Losung des bikriteriellen Standortproblems konnen eine Vielzahl an Losungs-verfahren angewendet werden.
Infoseite LosungsverfahrenWerden beide Zielfunktionen unter Verwendung eines gewichteten Mittelwertszu einer Ersatzzielfunktion zusammengefasst, wird von der Gewichtete Sum-men Skalarisierung bzw. der Zielgewichtung gesprochen. Die Einzelzielfunktio-nen werden vor der Optimierung mit reellen Zahlenλ1, λ2, ..., λt mit 0 ≤ λt ≤ 1 gewichtet und anschließend aufsummiert.Als Nebenbedingung soll dabei∑t
i=1 λi = 1 gelten [DOMSCHKE; DREXL 1998].Vorteil einer gewichteten Summenfunktion ist, dass die Ersatzzielfunktion in derRegel relativ einfach zu bestimmen ist. Nachteilig wirkt sich aber aus, dass dieLosungsmenge nur eine extremale optimale Losung beinhaltet. Auch ist die Wahlder Gewichte stark von den Praferenzen des Entscheidungstragers abhangig. DieWahl kann sehr stark subjektiv beeinflusst werden und oftmals sind die Zielebzw. die Einheiten der Ziele nicht vergleichbar.Daruber hinaus ist ein weiterer Nachteil dieser Methode, dass die optimaleLosung von sehr kleinen Veranderungen der Gewichtung stark beeinflusst wer-den kann.Dieses Problem lasst sich losen, indem fur die einzelnen Ziele obere bzw. un-tere Schranken vorgegeben werden, die dann im Rahmen einer Losung nichtuber- bzw. unterschritten werden durfen. Die Vorgehensweise wird in folgendemAbschnitt zur Zieldominanzmethode naher erlautert.Bei der Zieldominanz-Methode wird das bikriterielle Optimierungsproblemals einkriterielles Problem charakterisiert.Anfanglich wird ein Optimierungsziel nicht betrachtet und stattdessen eine Ne-benbedingung der Artfi(S) ≤ ε oder fi(S) ≥ ε eingefuhrt,die fur die Zielfunktion obere bzw. untere Schranken festsetzt. Unter den soentstehenden Losungen wird dann eine berechnet, die bezuglich der anderenZielfunktion und ihrem Optimierungsziel optimal ist.Problematisch bei dieser Methode ist, dass durch ungunstige Schranken fur einNebenziel der Zielerreichungsgrad des Hauptziels sehr stark einschrankt oder imExtremfall die Menge der zulassigen Losungen leer ist [DOMSCHKE; DREXL 1998].Unter der Berucksichtigung von Abstandsfunktionen wird die Minimie-rung der Abstande zwischen dem Zielfunktionswert eines gesondert betrachtetenZiels fi∗ und dem Zielfunktionswert einer kombinierten Losung mehrerer Zielefi(x) verstanden.Es wird also eine Losung des Gesamtproblems gesucht, welches einen moglichstgeringen Abstand zwischen der Losung der Einzelziele t und der Losung desGesamtziels, bei gleichzeitiger Betrachtung beider Zielfunktionen, aufweist.
31
Ahnlich wie bei der Zielgewichtung konnen zusatzliche Gewichte fur die einzel-nen Ziele eingefuhrt werden.EIne Sonderform der Bestimmung von Abstandfunktionen ist das Goal-Programming/Zielprogrammierung.Hierbei werden die Werte fur fi∗ vom Entscheidungstrager vorgegeben. Ziel istes auch, die Abstande zwischen vorgegebenem Zielfunktionswert und dem kom-binierten Zielfunktionswert aller Ziele zu minimieren.Eine weitere Losungsmoglichkeit ist, ahnlich wie bei gewichteten Set CoveringProblemen, unter zu Hilfenahme der Bestimmung kurzester Wege in einemgerichteten Digraphen, pareto-optimale Losungen zu bestimmen.Es werden jeder Kante zwei Gewichte zugeordnet.Zum einen soll die Summe der Wartezeiten cij minimiert, zum anderen dieUberdeckung der Nachfrager wd maximiert werden [SCHOBEL 2005].Eine weitere Moglichkeit zur Bestimmung optimaler Losungen fur mehrkri-terielle Problemstellungen stellt die lexikographische Optimierung dar. Hier-bei werden die einzelnen Zielfunktionen nach ihrer Wichtigkeit sortiert, unddas Problem wird anschließend sukzessive nach den einzelnen Zielfunktionenoptimiert. Die berechneten optimalen Losungen werden dann als Randbedin-gungen in die nachfolgende Optimierung der nachsten Zielfunktion eingefugt[DOMSCHKE; DREXL 1998].Fur Zielfunktionen, die als gleichwertig angesehen werden konnen, ist die lexiko-graphische Optimierung nicht anwendbar. So ergeben sich bei der Anwendungauf die bikriterielle Zielsetzung der Standortfindung bestimmte Schwierigkeiten.Beide Ziele sind zum einen als gleichwertig anzusehen. Des Weiteren stellen dieoptimalen Ziele der einzelnen Zielfunktionen Extrempunkte dar, die eine Op-timierung der anderen Zielfunktion nicht moglich machen. Wird zum Beispielnur nach dem Ziel, die Kosten zu minimieren, optimiert, dann ist die optimaleLosung, dass keine Stopps implementiert werden und die Kosten gleich Nullsind. Darauf aufbauend das zweite Ziel - die Maximierung der Uberdeckung -zu optimieren, ist nun nicht mehr moglich, da bei keiner errichteten Haltestellekeine Nachfrager uberdeckt werden konnen. Die lexikographische Optimierungscheidet also fur unsere Problemstellung aus.
32
3 Beispiel 1: Depots
3.1 Modellierung
Aufgabenstell-ung
Ein Netzwerk des offentlichen Nahverkehrs soll erweitert werden. Die Knotens stellen die Anfangs- und Endhaltestellen der Linien dar, die im Pendelbe-trieb verkehren. Die Gemeinde mochte ein Unternehmen beauftragen, Depotsfur Straßenbahnen zu errichten. Dafur stehen die potentiellen Standorte l zurVerfugung.Ein Planungsburo wird damit beauftragt zu untersuchen, wie viele der potenti-ellen Depotstandorte errichtet werden sollen und von welchem Depot aus welcheHaltestellen versorgt werden sollten. Ein Depot kann mehrere Haltestellen ver-sorgen, ebenso kann eine Haltestelle von mehreren Depots aus bedient werden.
Abbildung 1:Gemeindege-
biet
33
Die zuruckzulegenden Wege sind unter Beachtung des vorhandenen bzw. zu bau-enden Schienennetzes zu wahlen und konnen stets in beide Richtungen befahrenwerden. Die durchgezogenen Linien stehen fur die zu bedienenden Straßenbahn-linien, die gestrichelten Linien stellen die Gleisverbindungen dar, die die potenti-ellen Depots mit den Haltestellen verbinden. Sie mussen bei der Wahl eines jedenDepots ebenfalls neu errichtet werden. Um von einem Depot zu einer Haltestel-le zu gelangen, konnen sowohl die durchgezogenen wie auch die gestricheltenLinien verwendet werden. Maßgebend ist immer die kurzeste Verbindung.
Digraph
Kurzeste Wege Die Entfernungen γls zwischen potentiellem Depot und Haltestellen sind Grund-lage fur die Berechnung der Transportkosten. Eine Distanzeinheit entspricht 0,5Geldeinheiten. Damit ist berucksichtigt, dass ein Fahrzeug jeweils einmal am
34
Tag eine Ein- und Aussetzfahrt zurucklegen muss. Die minimalen Wege werdenmit Hilfe des kurzesten Wege Algorithmus von Dijkstra bestimmt. Sie sind inder Entfernungsmatrix in folgender Tabelle dargestellt.
35
3.2 Modellierung (2)
Optimierungs-ziel und
Optimierungs-kriterien
Ziel ist die Minimierung der Summe der variablen Transportkosten und derfixen Abschreibungskosten fur Depots und der dadurch notwendigen Trassen.
Eingangs-großen
Benotigte Eingangsgroßen zur Losung des Problems sind:
• Lage und Anzahl der zu bedienenden Haltestellen
• Lage und Anzahl der potentiellen Depots
• Anzahl der benotigten Straßenbahnen je Haltestelle
• Kapazitat und Fixkosten der potentiellen Depots
• bestehendes und potentielles Schienennetz
• Lange jeder Wegstrecke
• Entfernung der potentiellen Depots zu jeder Haltestelle (Entfernungsma-trix)
Entscheid-ungsvariablen
Als Entscheidungsvariablen mussen die
• Anzahl der Straßenbahnen, die je Depot zu einer bestimmten Haltestellebefordert werden, und die
• Anzahl der zu errichtenden Depots
beachtet werden.
Modellierung Aus der Problemstellung geht hervor, dass aus einer Menge potentieller Stand-orte eine Teilmenge identifiziert werden soll, damit das Verhaltnis zwischen fi-xen Standortkosten und variablen Transportkosten optimal ist. Aufgrund derzusatzlichen Kapazitatsbeschrankung der Depots, beschreibt unser Beispiel einkapazitiertes Warehouse Location Problem.
36
3.3 Losungsverfahren DROP-Algorithmus
Losungsver-fahren
Die Losung des Problems wird mit heuristischen Verfahren ermittelt. Als Eroff-nungsverfahren wird der Drop-Algorithmus verwendet, mit Hilfe von TabuSearch soll anschließend die Startlosung verbessert werden.
DROP-Algorithmus
Der Drop-Algorithmus geht von der Startsituation aus, dass alle potentiellenStandorte der Depots vorlaufig einbezogen sind. Zu Beginn entspricht der Ziel-funktionswert der Summe der Fixkosten aller Standorte und der minimalenTransportkosten. Letztere werden durch das Losen von Transportproblemenermittelt.Mit jeder Iteration wird nun derjenige Standort endgultig ausgeschlossen, durchdessen Schließung die großtmogliche Verringerung des Zielfunktionswertes er-langt wird. Der Algorithmus endet, sobald durch die Schließung eines weiterenStandortes keine zusatzliche Senkung des Zielfunktionswertes erreicht werdenkann. Alle Standorte, die nicht ausgeschlossen wurden, werden nun endgultigeinbezogen. [SCHILDT 1994]Der Drop-Algorithmus zahlt zu den Greedy-Verfahren. Bei jeder Iteration wirddemnach die großtmogliche Verbesserung des Zielfunktionswertes angestrebt.Bei dem Algorithmus kann nicht abgeschatzt werden, wie sich das Eliminieren ei-nes Standortes auf nachfolgende Verfahrensschritte auswirkt. [DOMSCHKE; KLEIN; SCHOLL 1996]Das bedeutet, dass eventuell suboptimale Losungen gefunden werden. Der Drop-Algorithmus liefert dennoch eine gute Startlosung, die anschließend mittels TabuSearch verbessert werden soll.
37
Infoseite TransportproblemTransportprobleme sind lineare Optimierungsprobleme und konnen mit Hilfedes Simplex-Algorithmus gelost werden.Bei großeren Optimierungsproblemen ist es sinnvoll, ein Computerprogrammzur Losung dieser in Anspruch zu nehmen, da sonst der Rechenaufwand zu großwird. Hiervon existieren zahlreiche, deren Losungsverfahren auf der Simplex-Methode basieren.
38
3.4 Losungsverfahren Tabu-Search
Tabu Search Mit Hilfe der Metaheuristik Tabu Search soll die Losung des Drop-Algorithmusauf mogliche Verbesserungen des Zielfunktionswertes untersucht werden.Der Aufbau des Tabu Search-Verfahrens sieht wie folgt aus:
1. Ermittle eine Starlosung x0 und berechne den zugehorigen Zielfunktions-wert F0.
2. Suche in der Nachbarschaft nach einer Losung, die die großte Verbesserungbzw. die geringste Verschlechterung des Zielfunktionswertes F ermoglichtund berechne diesen.
3. Vergleiche die Zielfunktionswerte F und F0 und speichere die beste Losung.
4. Aktualisiere die Tabu-Liste.
5. Wiederhole die Schritte 2 bis 4 so lange, bis ein Abbruchkriterium erfulltist.
6. Gib die beste Losung und ihren zugehorigen Zielfunktionswert an.
39
4 Beispiel 2: Haltestellen
4.1 Modellierung
Aufgabenstell-ung
Ein Verkehrsunternehmen betreibt ein offentliches Verkehrsnetz innerhalb einerGemeinde. Die drei Gemeindegebiete werden dabei von jeweils einer Linie imTourenbetrieb angedient. Ein zentraler Umsteigebahnhof auf dem Gemeindege-biet B ermoglicht die Anbindung aller drei Linien.Um das Angebot auch in Zukunft wettbewerbsfahig und attraktiv zu gestalten,mochte das Unternehmen die Standorte fur die Haltestellen optimieren, um dieAnzahl der Fahrgaste zu erhohen. Dies soll sukzessive fur jedes Gemeindegebietgeschehen. In einem ersten Schritt sind dabei die Planungen und die anschließen-de Optimierung fur das Gemeindegebiet A durchzufuhren. Dem Unternehmerbietet sich dafur die Moglichkeit, Haltestellen auf dem Netz im GemeindegebietA neu zu errichten und bestehende Haltestellen zu schließen.
Abbildung 1:Gemeindege-
biet
Nahverkehrs-linie
Das Netz im Gemeindegebiet A mit potentiellen Haltestellen und Knoten, indenen Nachfrage besteht, ist in Abbildung 1 dargestellt.Zur Vereinfachung wird davon ausgegangen, dass die Nachfrage nicht auf dergesamten Flache besteht, sondern dass Nachfragerknoten bereits durch Cluster-bildung gebildet worden sind. Diese stellen Schwerpunkte eines vorher bestimm-ten Bereichs dar, in dem die Nachfrage akkumuliert werden kann. Dies konnenbeispielsweise Wohngebiete, Industriegebiete, Einkaufszentren oder ahnliche Ag-glomerationen sein.
Die Einzugsbereiche der einzelnen Haltestellen sind mittels gestrichelter Ver-bindungslinien dargestellt. So sind zum Beispiel die Nachfragerknoten d2 undd3 von der Haltestelle s2 uberdeckt und eine bestimmte Anzahl potentiellerKunden nutzt diese Haltestelle.
40
Abbildung 2:Nahverkehrs-
linie mitHaltestellen
und Nachfra-gerknoten
Uberdeckungs-matrix und
Gewichte derNachfrager-
knoten
Die Uberdeckungsmatrix Acov = (ads) fur obiges Netz ergibt sich wie folgt:
Ferner wird angenommen, dass sich die Nachfragerknoten in einem bestimm-ten gegebenen Abstand zu den potentiellen Haltestellen befinden, und dassjeder Nachfragerknoten eine gleich hohe Anzahl an Nachfragern reprasentiert.Im Verhaltnis zu der Distanz zwischen Nachfragerknoten und Haltestelle er-geben sich folgende Werte, die die Anzahl Nutzer der einzelnen Halstestellenreprasentieren:
41
Infoseite Es wird davon ausgegangen, dass die maximale fußlaufige Distanz γd, die einNutzer bereit ist bis zu einer Haltestelle zuruckzulegen, 500 Meter nicht uber-schreitet. Diese Distanz entspricht in etwa der maximalen Fußweglangen, die alsBedienungsstandard im Offentlichen Verkehr vorgegeben werden (bspw. stadti-sche Kernzone: 300-400 Meter; Unterzentrum: 600 Meter).Die Gewichtung der Nachfragerknoten berechnet sich fur das Beispiel aus fol-gender Funktion:
Diese Funktion nimmt bei einem Abstand von 0 Metern zur Haltestelle denWert 1 an (was einem Nachfrageranteil des Knotens von 100% entspricht) undbei einer Entfernung des Nachfragerknotens von 500 Metern den Wert Null (waseinem Nachfrageranteil des Knotens von 0% entspricht).Bei bspw. 100 Einwohnern je Nachfragerknoten wurden demnach 21 Nachfrageraus Knoten 1 Haltestelle 1 in Anspruch nehmen. Analog dazu wurden Haltestelle3 drei Nachfrager aus Knoten 3 und 35 Nachfrager aus Knoten 4 in Anspruchnehmen.
42
4.2 Modellierung (2)
Vorbemerkung Die Standortplanung von Haltestellen ist einer der ersten Schritte bei der Pla-nung eines offentlichen Verkehrsnetzes.Die Planung ist dabei eng verbunden mit dem Fahrplan. Anschlusse verschiede-ner Linien werden durch Haltestellen raumlich und durch den Fahrplan zeitlichfestgelegt.Ziel dieses Beispiels ist die raumliche Optimierung der Haltestellenstandorte ineinem gegebenen Nahverkehrsnetz.
Aufgabe Jeder Linie muss eine bestimmte Anzahl an Haltestellen zugeordnet werden, andenen die Transportmittel halten, um einer bestimmten Anzahl an Nachfragerneine Anbindung an das Nahverkehrsangebot zu ermoglichen.
Optimierungs-ziele und
Optimierungs-kriterien
Ziele sind die Minimierung der Anzahl an Haltestellen und die Maxi-mierung der Uberdeckung der Nachfrager (Maximierung der Erschlie-ßungswirkung).Optimierungskriterien fur beide Ziele sind:
• Anzahl der zu implementierenden Haltestellen:
• Wartezeiten der Reisenden im Nahverkehrsnetz
• Zeitopportunitatskosten der Nutzer
• Betriebs- und Investitionskosten
• Anzahl uberdeckter Nachfrager:
• Erlose des Nahverkehrsunternehmens
Eingangs-großen
Zur Bearbeitung der Aufgabe werden folgende Daten und Eingangsgroßenbenotigt:
• Verlauf der Nahverkehrslinie
• Lage der Nachfragerknoten
43
• Anzahl potentieller Nachfrager pro Nachfragerknoten
• Zuordnung der Nachfragerknoten zu den Haltestellen
• Anzahl Reisender auf den verschiedenen Relationen (Quelle-Ziel Matrix)
Entscheid-ungsvariablen
Im Rahmen der Optimierung veranderlich sind die Entscheidungsvariablen:
• Anzahl der zu implementierenden Haltestellen
• Anzahl der zu uberdeckenden Nachfragerknoten
Modellierung Moglichkeiten der Modellierung sind bereits an vorangegangener Stelle erlautertworden. Wir werden im Folgenden die bikriterielle Modellierung [DOMSCHKE; DREXL 1998]detailliert betrachten und Losungsvorschlage aufzeigen.
44
4.3 Optimierungsverfahren
Optimierungs-verfahren
Zur Optimierung der bikriteriellen Standortprobleme werden (wie oben bereitsaufgezahlt) folgende Optimierungsverfahren eingesetzt:
• Zielgewichtung bzw. Gewichtete Summen Skalarisierung
• Zieldominanz bzw. e-constraint-Methode
• Berucksichtigung von Abstandsfunktionen bzw. Goal-Programming
• Bestimmung kurzester Wege
• Lexikographische Optimierung
Im Folgenden wird auf die Bestimmung kurzester Wege und die Zielgewichtungnaher eingehen. Diese werden zur Losung des Beispiels angewendet.
45
4.4 Losungsverfahren Bestimmung kurzester Wege
Bestimmungkurzester
Wege
Analog zur Bestimmung kurzester Wege bei der Losung von Set Covering Pro-blemen konnen bei der Losung von bikriteriellen Problemen ebenfalls Kurzeste-Wege-Algorithmen zur Anwendung kommen.Veranschaulichen lasst sich dies gut an einem leicht vereinfachten Beispiel.Es werden jeder Kante zwei Gewichte zugeordnet. Zum einen soll die Summeder Wartezeiten cij minimiert, zum anderen die Uberdeckung der Nachfragerwd maximiert werden.Als Vereinfachung werden die cij-Werte zu 1 normiert. Die wd-Werte stellen dieGewichte der Kanten dar.Der bikriterielle Set Covering Digraph GBSC = (SBSC , ABSC) ist - anders alsder Set-Covering Digraph - definiert durch:SBSC = S ∪ (s, t) undABSC = ((i, j) : i, j ∈ S und i < j) ∪ ((s, j) : j ∈ S) ∪ ((i, t) : i ∈ S) ∪ ((s, t))Die Gewichte der Kanten betragencij = 1wij =
∑d∈cover(j)/cover(i) wd falls i 6= s, j 6= t
wij =∑
d∈cover(j) wd falls i = s, j 6= t
wij = 0 falls j = t
Beispiel Fur das Beispiel stellt sich der Digraph wie folgt dar:
Im Gegensatz zum Digraphen des gewichteten Set Covering Problems sind hierder Knoten s und der Knoten t mit allen anderen Knoten und alle Knoten i ∈ smit allen folgenden Knoten j ∈ s fur i < j verbunden.Grund ist, dass zum einen auch hier die Verbindungen der Knoten allen Moglich-keiten entsprechen, potentielle Haltestellen auf dem Netzwerk zu implementie-ren, zum anderen aber nicht notgedrungen alle Nachfragerknoten uberdecktwerden mussen. Es konnen somit beliebige Konfigurationen an Haltestellen-standorten in Abhangigkeit der Anzahl zu errichtender Stopps implementiert
46
werden. Aus diesem Grund sind hier alle Knoten mit allen nachfolgenden Kno-ten verbunden.
Losung Mit folgenden Werten fur die Anzahl uberdeckter Nachfrager je Knoten ergebensich fur das Beispiel folgende pareto-optimale Losungen in Abhangigkeit derAnzahl implementierter Haltestellen.w1 = 5 w2 = 4w3 = 6 w4 = 2Fur
K=1 wird Haltestelle 3 implementiert,
K=2 werden Haltestellen 1 und 3 implementiert,
K=3 werden Haltestellen 1,2 und 3 implementiert und fur
K=4 werden alle Haltestellen implementiert.
EffizienteLosungen bei
mehrerenZielen
Wird davon ausgegangen, dass die cs-Werte nicht konstant gleich 1 sind, dannbesteht die Losung aus einer Menge an pareto-optimalen Elementen.
AufgabeAus wie vielen Elementen besteht die Losungsmenge des obigen kurzeste WegeProblems mit den Kantengewichten wd und cs?15
Gelten fur die Gewichte die oben stehenden Werte fur wd und die folgend auf-gefuhrten cs-Werte, stellt sich die Losungsmenge des Beispiels wie folgt dar:c1 = 3 c2 = 5c3 = 2 c4 = 6
47
AufgabeWelchs Element der Losungsmenge ist fur K=2 Haltestellen pareto-optimal? false {s,1,2,t}true {s,1,3,t}false {s,1,4,t}false {s,2,3,t}false {s,2,4,t}false {s,3,4,t}
WeitereeffizienteLosungen
Fur K=1 ist die effiziente Losung {s,3,t}Fur K=3 ist die effiziente Losung {s,1,2,3,t}Fur K =4 ist die effiziente Losung {s,1,2,3,4,t}
48
4.5 Losungsverfahren Zielgewichtung
Zielgewichtung Fur die Optimierung bei mehrfacher Zielsetzung ist die Zielgewichtung ein wei-teres mogliches Losungsverfahren.Das folgende kleine Beispiel soll die Vorgehensweise erlautern:
Beispiel Maximiere Gewinn G(x, y) = x + 2yMaximiere Absatz A(x, y) = x + yMaximiere Umsatz U(x, y) = 3x + 2yunter den Nebenbedingungenx + y ≤ 1006x + 9y ≤ 720y ≤ 60x, y ≥ 0Mit den Gewichten λ1 bis λ3 fur das Zieltripel (Gewinn, Absatz, Umsatz) mit(1/3, 1/2, 1/6) lautet die Zielfunktion:Maximiere Φ(x, y) = 1
3G(x, y) + 12A(x, y) + 1
6U(x, y) = 43x + 3
2yunter obenstehenden NebenbedingungenZur Losung dieses linearen Optimierungsproblems eignet sich der Simplex Al-gorithmusSimplex Algorithmus.Die optimale Losung dieses Problems lautet dann:x = 60; y = 40; G = 140; A = 100; U = 260
49
4.6 Losung
Vereinfachung Mit Hilfe eines einfachen Algorithmus werden pareto-optimale Losungen furverschiedene Anzahlen an zu implementierenden Haltestellen ermittelt. Als Son-derfall dient die Vereinfachung, dass die Anzahl an Reisenden, die eine Halte-stelle ”durchreisen“, fur alle Haltestellen gleich groß ist. Die Summe der Zeitop-portunitatskosten cs der einzelnen Haltestellen nimmt fur alle Stopps den Wert1 an.Die Vorgehensweise des Algorithmus fur das Nahverkehrsnetz der Gemeinde istin folgender Diashow dargestellt.
Zielgewichtung Im nachsten Schritt wird die Anzahl der Nachfrager in den einzelnen Relationenin die Zielfunktion mit aufgenommen. Die Variable cs nimmt damit fur dieunterschiedlichen potentiellen Haltepunkte die in folgender Tabelle aufgefuhrtenWerte an.
Die wd-Werte sind an fruherer Stelle bereits aufgefuhrt worden.Um nun in Abhangigkeit der Minimierung der Summe der Wartezeiten und derMaximierung der Uberdeckung der Nachfrager optimale Losungen zu finden,wenden wir die Methode der Zielgewichtung an.Als Gewichte werden fur λ1 = 0, 3 und fur λ2 dementsprechend 0,7 gewahlt. Da-mit wird die Uberdeckung hoher als die zusatzliche Wartezeit gewichtet. Darinspiegelt sich die Praferenz des Entscheidungstragers wieder, eine hohe Uber-deckung als wichtiger fur die Erhohung der Attraktivitat einzustufen als einewartzeitminimale Verbindung innerhalb des Verkehrsnetzes.
50
Modellierung
Es mussen nun - analog zu der Bestimmung kurzester Wege - fur K=1,..., 6 Hal-testellen effiziente Losungen bestimmt werden. Diese sind in folgender Diashowdargestellt.
51
Variieren derGewichte
Die Auswahl der Gewichte beeinflusst stark das Ergebnis des Optimierungspro-blems. Aus diesem Grund werden fur variierende Gewichte die verschiedenenErgebnisse dargestellt.
52
Es ist zu erkennen, dass sich durch verschiedene Gewichte die Losungsmengenfur die optimalen Standorte von Haltestellen und die jeweils uberdeckten Nach-fragerknoten andern. Die optimalen Losungen sind sehr stark von den Praferen-zen des Entscheidungstragers - also den Gewichten - abhangig.
Infoseite Algorithmus zur Losung des bikriteriellen Problems
”Das Particial Set Covering Problem und Erweiterungen: Modellierungund Losungsverfahren“Dissertation an der Fakultat fur Naturwissenschaften der UniversitatDuisburg-EssenDuisburg 2003
[BUSSIECK; WINTER; ZIMMERMANN 1997] Bussieck, M.; Winter, T.;Zimmermann, U.:
”Discrete optimization in public rail transport“In: Mathematical Programming 79(3), Seiten 415-444, 1997http://i11www.ilkd.unikarlsruhede/algo/teaching/SS 03/eisenbahn modelle/bussieck97discrete.pdf(letzter Zugriff, 16.09.2005)
[DASKIN 1995] Daskin, M.:
”Network and Discrete Location; Models, Algorithms, and Applications“John Wiley & SonsNew York 1995
”Tabu Search - eine intelligente Losungsstrategie fur komplexe Optimie-rungsprobleme“In: Schriften zur Quantitativen Betriebswirtschaftslehre an der TU Darm-stadtDarmstadt 1996
”Einfuhrung in Operations Research“Springer VerlagBerlin 1998
[DOMSCHKE; SCHOLL 2000] Domschke, W.; Scholl,A.:
”Grundlagen der Betriebswirtschaftslehre“
54
Springer VerlagBerlin 2000
[FACHGEBIET VV der TUD 2004] Fachgebiet Verkehrsplanung und Ver-kehrstechnik der TU Darmstadt:Umdruck zur Vorlesung ”Verkehrsplanung und Verkehrstechnik I“ an derTU DarmstadtDarmstadt 2004
[FGSV 1982] Forschungsgesellschaft fur Straßen- und Verkehrswesen, Arbeits-gruppe Verkehrsplanung:
”Hinweise fur die Anwendung von Entscheidungs- und Optimierungsme-thoden im Verkehrswesen“Koln 1982
[GENC 2003] Genc, Z.:
”Ein neuer Ansatz zur Fahrplanoptimierung im OPNV: Maximierung vonzeitlichen Sicherheitsabstanden“Dissertation am Fachbereich der mathematisch-naturwissenschaftlichenFakultat der Universitat zu KolnKoln 2003
[HUMPFNER 2002] Humpfner, S.:
”Entwicklung eines Verfahrens zur Standortoptimierung von Park-and-Ride-Anlagen“Lehrstuhl fur Verkehrs- und Stadtplanung der TU MunchenMunchen 2002
[KLOSE 2001] Klose, A.:
”Standortplanung in distributiven Systemen“Physica VerlagHeidelberg 2001
[KLOSE 2005] Klose, A.:
”OR-Modelle in der Standort- und Tourenplanung“Vorlesungsunterlagen zur Spezialvorlesung Operations Research am In-stitut fur Operations Research und mathematische Methoden der Wirt-schaftswissenschaften an der Universitat ZurichZurich 2005
[LIEBCHEN 2005] Liebchen C.:
”Der Berliner U-Bahn Fahrplan 2005 - Realisierung eines mathematischoptimierten Angebotskonzeptes“In: FGSV Verlag (Hrsg.): ”HEUREKA 2005: Optimierung in Transportund Verkehr - Tagungsbericht“ Seiten 483-500FGSV-Verlag2005
55
[LIEBMANN 1971] Liebmann, H.-P.:
”Die Standortwahl als Entscheidungsproblem“,Physica-Verlag,Wurzburg 1971
[MAYER 2001] Mayer, G.:
”Strategische Logistikplanung von Hub & Spoke-Systemen“Deutscher Universitats-VerlagWiesbaden 2001
”Hub Location Problems“In: Mathematical methods on Optimization in Transportation Systems,EURO-Working Group Meeting on Transportation Seiten 95-1072001
[SCHILDT 1994] Schildt, B.:
”Strategische Produktions- und Distributionsplanung, Betriebliche Stand-ortoptimierung bei degressiv verlaufenden Produktionskosten“DUVWiesbaden 1994
[SCHOBEL 2003] Schobel, A.:
”Optimization Models in Public Transportation“Vorlesungsunterlagen am Institut fur Numerische und Angewandte Ma-thematikGottingen 2003
[SCHOBEL 2005] Schobel, A.:
”Costumer-Oriented Optimization in Public Transportation“Habilitationsschrift an der Universitat GottingenGottingen 2005
[TOPP 1994] Topp, H.H:
”Parkraum als Steuerungsinstrument“In: Handbuch der kommunalen Verkehrsplanung Bd.2, (3.4.12.1)Bonn 1994 ff.
[WEINBRECHT 2000] Weinbrecht, K.:
”Kontinuierliche Standortprobleme in Polygonen“,Dissertation an der Mathematisch-Naturwissenschaftlichen Fakultat derUniversitat zu Koln,Koln 2000
