Fallstudie 3: Diskrete Standortplanung und Transportplanung

SushiFresh-Übungen und Batterielogistik für die Automobilindustrie in Norddeutschland und Benelux

Autor:in

Supply Chain Management – Gruppenarbeit

Steckbrief

Thema	Netzwerkdesign mit dem Warehouse Location Problem (WLP), Belieferung als Transportproblem
Vorlesungsbezug	Block 2 „Strategische Gestaltung von Supply Chains“: Diskrete Netzwerkplanung · Transportplanung
Teil 1	Klausurvorbereitung: Aufgaben mit Stift und Papier zu einer neuen SushiFresh-Entscheidungssituation (25–30 Min.)
Teil 2	Datenbasierte Fallstudie NordCell: realistische Werks- und Standortkoordinaten, Mengen und Kosten realitätsnah geschätzt
Gruppengröße	3–6 Personen (Teil 2)
Ergebnis	Präsentation (20 Min.) + Diskussion (10 Min.), Foliensatz (PDF) und reproduzierbarer R-/Quarto-Code

1 Lernziele

Nach Bearbeitung der Übungen und der Fallstudie können Sie

ein unkapazitiertes WLP mit Add- und Drop-Heuristik sowie exakt als MILP lösen,
die Lösungsqualität einer Heuristik gegenüber dem Optimum bewerten,
ein Transportproblem mit Nordwestecken-Regel, Vogel’scher Approximation und als LP lösen und
unbalancierte Transportprobleme mit einem Dummy-Knoten behandeln.

2 Teil 1 – Klausurvorbereitung: Küchen und Belieferung im Rhein-Neckar-Gebiet

Hinweise

Bearbeitungszeit ca. 30 Minuten · Hilfsmittel: nicht programmierbarer Taschenrechner · 30 Punkte

Für die Belieferung von vier Supermärkten im Rhein-Neckar-Gebiet kommen drei Küchenstandorte infrage. Die jährliche Nachfrage, die Fixkosten der Küchen und die Transportkosten sind bekannt:

Transportkosten [€/Box]	Mannheim	Ludwigshafen	Heidelberg	Weinheim	Fixkosten [T€/Jahr]
K1 Mannheim-Hafen	0,10	0,20	0,50	0,60	20
K2 Schwetzingen	0,40	0,50	0,15	0,45	18
K3 Ladenburg	0,30	0,45	0,25	0,20	25
Nachfrage [T Boxen/Jahr]	70	30	50	20

Aufgabe 1 (5 Punkte) – Kostenmatrix. Berechnen Sie die jährlichen Transportkosten (T€) für die Belieferung jedes Markts aus jeder Küche.

Musterlösung Aufgabe 1

Transportkosten = Kostensatz × Nachfrage (T€/Jahr):

	MA	LU	HD	WH	Summe
K1	7,0	6,0	25,0	12,0	50,0
K2	28,0	15,0	7,5	9,0	59,5
K3	21,0	13,5	12,5	4,0	51,0

Bewertung: 5 Punkte (je Zeile 1–2 Punkte).

Aufgabe 2 (8 Punkte) – Add- und Drop-Heuristik. Lösen Sie das unkapazitierte Warehouse Location Problem mit der Add-Heuristik und mit der Drop-Heuristik. Dokumentieren Sie jede Iteration mit den Gesamtkosten.

Musterlösung Aufgabe 2

Add-Heuristik (jeder Markt wird von der günstigsten offenen Küche beliefert):

Iteration	Kandidat	Fixkosten	Transport	Gesamt
1	{K1}	20	50,0	70,0
	{K2}	18	59,5	77,5
	{K3}	25	51,0	76,0
2	{K1, K2}	38	7 + 6 + 7,5 + 9 = 29,5	67,5
	{K1, K3}	45	7 + 6 + 12,5 + 4 = 29,5	74,5
3	{K1, K2, K3}	63	7 + 6 + 7,5 + 4 = 24,5	87,5 → keine Verbesserung, Stopp

Drop-Heuristik (Start mit allen Küchen, 87,5):

Iteration	Kandidat	Gesamt
1	ohne K1: {K2, K3}	89,0
	ohne K2: {K1, K3}	74,5
	ohne K3: {K1, K2}	67,5
2	ohne K1: {K2}	77,5
	ohne K2: {K1}	70,0 → keine Verbesserung, Stopp

Beide Heuristiken eröffnen K1 und K2 mit Gesamtkosten von 67,5 T€/Jahr (K1 beliefert Mannheim und Ludwigshafen, K2 Heidelberg und Weinheim).

Bewertung: Add 4 Punkte, Drop 4 Punkte.

Aufgabe 3 (3 Punkte) – Optimum. Wie viele Kombinationen offener Küchen gibt es? Prüfen Sie durch Vollenumeration, ob die Heuristiken das Optimum gefunden haben.

Musterlösung Aufgabe 3

Es gibt $2^3 - 1 = 7$ nichtleere Kombinationen: {K1} 70,0; {K2} 77,5; {K3} 76,0; {K1, K2} 67,5; {K1, K3} 74,5; {K2, K3} 89,0; {K1, K2, K3} 87,5. Beide Heuristiken haben das Optimum gefunden.

Bewertung: 1 Punkt Anzahl, 2 Punkte Enumeration.

Es werden K1 (Kapazität 250 Boxen/Tag) und K2 (Kapazität 200 Boxen/Tag) eröffnet. Die Tagesnachfrage beträgt Mannheim 160, Ludwigshafen 70, Heidelberg 110 und Weinheim 60 Boxen. Es gelten die Transportkosten der Tabelle oben.

Aufgabe 4 (2 Punkte) – Balance. Ist das Transportproblem balanciert? Führen Sie gegebenenfalls einen Dummy-Knoten ein und erläutern Sie, welche Kosten Sie für ihn ansetzen.

Musterlösung Aufgabe 4

Angebot 250 + 200 = 450 > Nachfrage 160 + 70 + 110 + 60 = 400. Das Problem ist nicht balanciert. Ein Dummy-Markt nimmt die Überkapazität von 50 Boxen auf. Seine Kosten sind 0, weil diese Menge gar nicht produziert und transportiert wird (oder, falls die Küche trotzdem produziert, ein entgangener bzw. verlorener Wert).

Bewertung: 2 Punkte.

Aufgabe 5 (10 Punkte) – Eröffnungsverfahren. Bestimmen Sie eine Lösung mit der Nordwestecken-Regel und mit der Vogel’schen Approximationsmethode und berechnen Sie jeweils die Transportkosten pro Tag. Ordnen Sie einen Dummy-Knoten als letzte Zeile bzw. Spalte an. Bei gleichen Differenzen wählen Sie die Zeile bzw. Spalte mit dem kleinsten Kostensatz.

Musterlösung Aufgabe 5

Nordwestecken-Regel (Dummy als letzte Spalte):

	MA	LU	HD	WH	Dummy	Angebot
K1	160	70	20			250
K2			90	60	50	200

Kosten: $160 10 + 70 20 + 20 50 + 90 15 + 60 45 = 16 + 14 + 10 + 13{,}5 + 27 = $ 80,50 €/Tag.

Vogel’sche Approximationsmethode:

Schritt	Differenzen (Zeilen; Spalten)	Größte Differenz	Zuordnung
1	K1 0,10; K2 0,15; MA 0,30; LU 0,30; HD 0,35; WH 0,15; Dummy 0	HD 0,35	K2 → HD 110
2	K1 0,10; K2 0,40; MA 0,30; LU 0,30; WH 0,15; Dummy 0	K2 0,40	K2 → Dummy 50
3	K1 0,10; K2 0,05; MA 0,30; LU 0,30; WH 0,15	MA/LU 0,30 (Gleichstand, kleinster Kostensatz: MA)	K1 → MA 160
4	K1 0,40; K2 0,05; LU 0,30; WH 0,15	K1 0,40	K1 → LU 70
5	nur noch WH		K1 → WH 20, K2 → WH 40

	MA	LU	HD	WH	Dummy
K1	160	70		20
K2			110	40	50

Kosten: $16 + 14 + 12 + 16{,}5 + 18 = $ 76,50 €/Tag.

Bewertung: Nordwestecke 3 Punkte, VAM 6 Punkte, Kostenvergleich 1 Punkt.

Aufgabe 6 (2 Punkte) – Verbesserung. Begründen Sie ohne Rechenverfahren, ob die VAM-Lösung optimal ist. Gibt es eine günstigere Zuordnung?

Musterlösung Aufgabe 6

Die VAM-Lösung ist nicht optimal. Der Dummy mit Kosten 0 erzeugt in Schritt 2 eine hohe Differenz bei K2, sodass die günstige Küche K2 ihre Kapazität an den Dummy „verliert“ und Weinheim teilweise aus K1 (0,60 €) beliefert wird. Besser: K2 beliefert Heidelberg (110) und Weinheim vollständig (60), K1 Mannheim und Ludwigshafen; der Dummy erhält 20 von K1 und 30 von K2. Kosten: $16 + 14 + 16{,}5 + 27 = $ 73,50 €/Tag. Das ist optimal, weil jeder Markt aus seiner jeweils günstigsten Küche beliefert wird.

Bewertung: 2 Punkte.

3 Teil 2 – Fallstudie: Batterielogistik in Norddeutschland und Benelux

3.1 Ausgangslage

Die NordCell Logistics GmbH (fiktiv) ist ein auf Gefahrgut spezialisierter Kontraktlogistiker. Sie hat den Zuschlag erhalten, Lithium-Ionen-Batteriemodule für zehn Fahrzeugwerke in Norddeutschland, NRW, Hessen und Benelux zu lagern, zu sequenzieren und just in sequence anzuliefern. Die Module kommen zu 60 % als Importe über den Hafen Hamburg und zu 40 % aus der Zellfabrik Salzgitter.

Batterien sind Gefahrgut der Klasse 9. Die Lager benötigen Brandabschnitte, Sprinkler- und Löschwasserrückhaltesysteme und behördliche Genehmigungen, was die Fixkosten stark erhöht. NordCell hat acht potenzielle Lagerstandorte identifiziert und muss entscheiden,

welche Lager eröffnet werden (strategisch, Vertragslaufzeit 7–12 Jahre) und
welches Werk aus welchem Lager beliefert wird (taktisch, jährlich).

3.2 Daten

Die Werksstandorte orientieren sich an realen Fahrzeugwerken. Mengen und Kosten sind fiktiv, aber in ihrer Größenordnung realitätsnah.

Code

werke <- data.frame(
  id    = 1:10,
  werk  = c("VW Wolfsburg", "VW Hannover", "VW Emden", "VW Osnabrück",
            "Mercedes-Benz Bremen", "Ford Köln", "Opel Rüsselsheim",
            "Volvo Cars Gent", "Volvo Trucks Gent", "VDL Nedcar Born"),
  lat   = c(52.432, 52.380, 53.365, 52.279, 53.075, 50.950, 49.993, 51.054, 51.040, 51.030),
  lon   = c(10.787,  9.746,  7.213,  8.047,  8.808,  6.900,  8.422,  3.717,  3.730,  5.867),
  d2027 = c(28000, 22000, 18500, 12000, 25000, 20000, 15000, 30000, 14000, 11000),
  d2030 = c(42000, 26000, 28000, 12000, 31000, 27000, 21000, 36000, 17000,  6000)
)
quellen <- data.frame(
  quelle = c("Hafen Hamburg", "Zellfabrik Salzgitter"),
  lat    = c(53.540, 52.160),
  lon    = c( 9.970, 10.400),
  anteil = c(0.60, 0.40)
)
lager <- data.frame(
  id   = 1:8,
  ort  = c("Gütersloh", "Düren", "Dorsten/Marl", "Peine", "Langenhagen",
           "Venlo (NL)", "Bremen GVZ", "Gent Hafen (BE)"),
  lat  = c(51.906, 50.804, 51.660, 52.320, 52.438, 51.370, 53.050, 51.100),
  lon  = c( 8.383,  6.493,  6.965, 10.230,  9.737,  6.170,  8.700,  3.780),
  fix  = c(2400, 2600, 2500, 2300, 2700, 2800, 2600, 3000),   # T€/Jahr
  kap  = c(90, 110, 80, 70, 100, 120, 90, 80) * 1000           # MWh/Jahr
)
knitr::kable(werke, format.args = list(big.mark = ".", decimal.mark = ","),
             col.names = c("#", "Werk", "Breite", "Länge",
                           "Bedarf 2027 [MWh/a]", "Szenario 2030 [MWh/a]"))

#	Werk	Breite	Länge	Bedarf 2027 [MWh/a]	Szenario 2030 [MWh/a]
1	VW Wolfsburg	52,432	10,787	28.000	42.000
2	VW Hannover	52,380	9,746	22.000	26.000
3	VW Emden	53,365	7,213	18.500	28.000
4	VW Osnabrück	52,279	8,047	12.000	12.000
5	Mercedes-Benz Bremen	53,075	8,808	25.000	31.000
6	Ford Köln	50,950	6,900	20.000	27.000
7	Opel Rüsselsheim	49,993	8,422	15.000	21.000
8	Volvo Cars Gent	51,054	3,717	30.000	36.000
9	Volvo Trucks Gent	51,040	3,730	14.000	17.000
10	VDL Nedcar Born	51,030	5,867	11.000	6.000

Code

knitr::kable(lager, format.args = list(big.mark = ".", decimal.mark = ","),
             col.names = c("#", "Standort", "Breite", "Länge",
                           "Fixkosten [T€/a]", "Kapazität [MWh/a]"))

#	Standort	Breite	Länge	Fixkosten [T€/a]	Kapazität [MWh/a]
1	Gütersloh	51,906	8,383	2.400	90.000
2	Düren	50,804	6,493	2.600	110.000
3	Dorsten/Marl	51,660	6,965	2.500	80.000
4	Peine	52,320	10,230	2.300	70.000
5	Langenhagen	52,438	9,737	2.700	100.000
6	Venlo (NL)	51,370	6,170	2.800	120.000
7	Bremen GVZ	53,050	8,700	2.600	90.000
8	Gent Hafen (BE)	51,100	3,780	3.000	80.000

Transportkostensätze (Richtwerte): Zulauf Quelle → Lager 0,25 €/(MWh·km), Auslieferung Lager → Werk 0,45 €/(MWh·km), jeweils auf die Haversine-Distanz mit Umwegfaktor 1,2.

3.3 Aufgaben

3.3.1 Teil A – Datenaufbereitung

A1. Stellen Sie Quellen, Lagerkandidaten und Werke auf einer Karte dar und berechnen Sie die Kostenmatrix $c_{ij}$ in €/MWh (Zulauf und Auslieferung, siehe Startercode). Prüfen Sie für zwei Relationen, wie gut Haversine-Distanz × 1,2 die Straßendistanz eines Routenplaners trifft.

3.3.2 Teil B – Unkapazitiertes WLP (Bedarf 2027)

B1. Lösen Sie das WLP mit der Add- oder Drop-Heuristik und exakt mit ompr. Welche Lager werden eröffnet, wie hoch sind die Gesamtkosten, und wie weit liegt die Heuristik vom Optimum entfernt?

3.3.3 Teil C – Transportproblem

C1. Halten Sie die Standortentscheidung aus B1 fest und berücksichtigen Sie nun die Lagerkapazitäten. Lösen Sie die Zuordnung Lager → Werke als Transportproblem (VAM und LP). Reichen die Kapazitäten der eröffneten Lager aus? Welche Werke werden gegenüber B1 anders beliefert, und was kostet das?

3.3.4 Teil D – Szenario, Empfehlung und Reflexion

D1. Prüfen Sie Ihr Netz mit dem Bedarf des Szenarios 2030: Reichen die Kapazitäten noch, und wie stark steigen die Kosten? Formulieren Sie eine Netzempfehlung für NordCell mit Standorten, Kosten und Risiken.

D2. Reflexion. Beantworten Sie in der Präsentation:

Die Kostenfunktion ist in der Nähe des Optimums oft flach. Welche Rolle sollten qualitative Kriterien (vgl. Fallstudie 2) bei der endgültigen Auswahl spielen?
Welche Modellannahme halten Sie für die kritischste (Luftlinie × Umwegfaktor, lineare Transportkosten, deterministische Nachfrage)?
Wann würden Sie in der Praxis eine Heuristik statt eines exakten Verfahrens einsetzen?

4 Anhang: R-Startercode

Code

source("../R/scm_functions.R")   # haversine(), add_heuristic_wlp(), drop_heuristic_wlp(), vogels_approximation()
library(ompr); library(ompr.roi); library(ROI.plugin.glpk); library(dplyr)

uf <- 1.2
# Zulaufkosten je MWh für jedes Lager (gewichtet über die Quellen)
c_in <- sapply(seq_len(nrow(lager)), function(i)
  sum(quellen$anteil * 0.25 * uf *
        haversine(lager$lat[i], lager$lon[i], quellen$lat, quellen$lon)))

# Auslieferkosten je MWh (Lager x Werk)
c_out <- outer(seq_len(nrow(lager)), seq_len(nrow(werke)), Vectorize(function(i, j)
  0.45 * uf * haversine(lager$lat[i], lager$lon[i], werke$lat[j], werke$lon[j])))

C <- c_in + c_out                       # €/MWh, Matrix 8 x 10
dimnames(C) <- list(lager$ort, werke$werk)

# Unkapazitiertes WLP (Kosten in T€)
d  <- werke$d2027
f  <- lager$fix
nI <- nrow(lager); nJ <- nrow(werke)

m <- MIPModel() |>
  add_variable(y[i], i = 1:nI, type = "binary") |>
  add_variable(x[i, j], i = 1:nI, j = 1:nJ, type = "continuous", lb = 0, ub = 1) |>
  set_objective(sum_over(f[i] * y[i], i = 1:nI) +
                sum_over(C[i, j] * d[j] / 1000 * x[i, j], i = 1:nI, j = 1:nJ), "min") |>
  add_constraint(sum_over(x[i, j], i = 1:nI) == 1, j = 1:nJ) |>
  add_constraint(x[i, j] <= y[i], i = 1:nI, j = 1:nJ)

res <- solve_model(m, with_ROI(solver = "glpk"))
objective_value(res)
offen <- get_solution(res, y[i]) |> filter(value > 0.5) |> pull(i)

# Teil C: Transportproblem mit den Kapazitäten der eröffneten Lager
vogels_approximation(C[offen, , drop = FALSE],
                     supply = lager$kap[offen], demand = d)