Skip to content

Instantly share code, notes, and snippets.

@henrydatei

henrydatei/Algorithmen Logistik.tex

Created April 7, 2021 15:04
Show Gist options
  • Save henrydatei/b581544f441f6e107205d119d3742619 to your computer and use it in GitHub Desktop.
Save henrydatei/b581544f441f6e107205d119d3742619 to your computer and use it in GitHub Desktop.
Download ZIP
Algorithmen für Logistik
Raw
Algorithmen Logistik.tex
\documentclass{article}
\usepackage{amsmath,amssymb}
\usepackage{tikz}
\usepackage{pgfplots}
\usepackage{xcolor}
\usepackage{colortbl}
\usepackage[left=2.1cm,right=3.1cm,bottom=3cm,footskip=0.75cm,headsep=0.5cm]{geometry}
\usepackage{enumerate}
\usepackage{enumitem}
\usepackage{marvosym}
\usepackage{tabularx}
\usepackage[colorlinks, linkcolor = blue, citecolor = blue, filecolor = blue, urlcolor = blue]{hyperref}
\usepackage{parskip}
\usepackage{multirow}
\usepackage{listings}
\definecolor{lightlightgray}{rgb}{0.95,0.95,0.95}
\definecolor{lila}{rgb}{0.8,0,0.8}
\definecolor{mygray}{rgb}{0.5,0.5,0.5}
\definecolor{mygreen}{rgb}{0,0.8,0.26}
%\lstdefinestyle{sh} {language=bash}
\lstset{language=bash,
basicstyle=\ttfamily,
keywordstyle=\color{lila},
commentstyle=\color{lightgray},
stringstyle=\color{mygreen}\ttfamily,
backgroundcolor=\color{white},
showstringspaces=false,
numbers=left,
numbersep=10pt,
numberstyle=\color{mygray}\ttfamily,
identifierstyle=\color{blue},
xleftmargin=.1\textwidth,
%xrightmargin=.1\textwidth,
escapechar=§,
}
\usepackage[utf8]{inputenc}
\renewcommand*{\arraystretch}{1.4}
\newcolumntype{L}[1]{>{\raggedright\arraybackslash}p{#1}}
\newcolumntype{R}[1]{>{\raggedleft\arraybackslash}p{#1}}
\newcolumntype{C}[1]{>{\centering\let\newline\\\arraybackslash\hspace{0pt}}m{#1}}
\newcommand{\E}{\mathbb{E}}
\DeclareMathOperator{\Var}{Var}
\DeclareMathOperator{\CDF}{CDF}
\newcommand*\circled[1]{\tikz[baseline=(char.base)]{
\node[shape=circle,draw,inner sep=2pt] (char) {#1};}}
\title{\textbf{Algorithmen für Logistik}}
\author{\textsc{Henry Haustein}}
\date{}
\begin{document}
\maketitle
\section*{Toplogische Sortierung}
\url{https://de.wikipedia.org/wiki/Topologische_Sortierung}
\textbf{Ziel:} Graphen topologisch sortieren, dass heißt für jeden Pfeil von Knoten $i$ nach Knoten $j$ muss gelten: $i<j$.
\textbf{Idee hinter dem Algorithmus:} Start bei einer Quelle, diese bekommt die kleinste Zahl. Dann entfernt man diese Quelle und mit ihr auch alle Pfeile zu nachfolgenden Knoten. In dem verbleibenden Knoten sucht man wieder eine Quelle und gibt ihr die nächstgrößere Zahl usw. Wenn der Graph einen Zyklus enthält, wird man irgendwann keine Quelle mehr finden, hat aber nicht alle Knoten neu nummeriert. In diesem Fall ist der Graph nicht topologisch sortierbar. Kann man alle Knoten neu nummerieren, so ist der Graph topologisch sortierbar.
\textbf{Beispiel:} Gegeben sei der Graph
\begin{center}
\begin{tikzpicture}
\node[circle,draw=black, fill=white] (1) at (0,0) {1};
\node[circle,draw=black, fill=white] (2) at (0,-2) {2};
\node[circle,draw=black, fill=white] (3) at (2,0) {3};
\node[circle,draw=black, fill=white] (4) at (2,-2) {4};
\node[circle,draw=black, fill=white] (5) at (4,-2) {5};
\draw[->] (1) -- (3);
\draw[->] (1) -- (2);
\draw[->] (1) -- (4);
\draw[->] (4) -- (2);
\draw[->] (4) -- (5);
\draw[->] (3) -- (4);
\end{tikzpicture}
\end{center}
\begin{center}
\begin{tabular}{c|c|C{4cm}|c|C{4cm}}
\textbf{Iteration $k$} & \textbf{Quelle $Q_k$} & \textbf{Kanten, die Quelle enthalten $\vec{E}_{Q_k}$} & \textbf{neue Nummer} & \textbf{restlicher Graph nach Entfernung der Quelle $V_{k+1}$, $\vec{E}_{k+1}$} \\
\hline
0 & \circled{1} & $\{(1,2),(1,3),(1,4)\}$ & 1 & $V_1=\{2,3,4,5\}$, $\vec{E}_1=\{(3,4),(4,2),(4,5)\}$ \\
\hline
1 & \circled{3} & $\{(3,4)\}$ & 2 & $V_2=\{2,4,5\}$, $\vec{E}_2=\{(4,2),(4,5)\}$ \\
\hline
2 & \circled{4} & $\{(4,2),(4,5)\}$ & 3 & $V_3=\{2,5\}$, $\vec{E}_3=\emptyset$ \\
\hline
3 & \circled{2} & $\emptyset$ & 4 & $V_4=\{5\}, \vec{E}_4=\emptyset$ \\
\hline
4 & \circled{5} & $\emptyset$ & 5 & $V_5=\emptyset$, $\vec{E}_5=\emptyset$
\end{tabular}
\end{center}
\textbf{Wissenswertes:} In frühen Zeiten der Programmierung war es notwendig, voneinander abhängige Quelltextdateien in der richtigen Reihenfolge zu kompilieren. Dafür wurde unter UNIX-artigen Systemen wie Linux und Mac das Kommandozeilenprogramm \texttt{tsort} entwickelt, das eine topologische Sortierung vornimmt. Die Abhängigkeiten werden in der Form \textit{von $\langle$Leerzeichen$\rangle$ nach} eingegeben. Für das obige Beispiel sähe die Eingabe wie folgt aus:
\begin{lstlisting}
tsort <<Ende
> 1 3
> 1 4
> 1 2
> 3 4
> 4 2
> 4 5
> Ende
\end{lstlisting}
und liefert als Ergebnis \texttt{1,3,4,5,2}, dass heißt in dieser Reihenfolge sollten die Knoten nummeriert werden.
\section*{Kruskal-Algorithmus}
\url{https://de.wikipedia.org/wiki/Algorithmus_von_Kruskal}
\textbf{Ziel:} Finden eines Minimalgerüstes
\textbf{Idee hinter dem Algorithmus:} Joseph Kruskal beschreibt seinen Algorithmus wie folgt: \textit{Führe den folgenden Schritt so oft wie möglich aus: Wähle unter den noch nicht ausgewählten Kanten von $G$ (dem Graphen) die kürzeste Kante, die mit den schon gewählten Kanten keinen Kreis bildet.} Das heißt man startet mit einem leeren Gerüst ohne Kanten und fügt aus dem Graphen die Kanten mit den kleinsten Gewichten hinzu, sodass kein Zyklus im Graph entsteht. Der Algorithmus stoppt genau dann, wenn man $n-1$ Kanten in seinem Gerüst hat.
\textbf{Beispiel:} Gegeben sei der Graph
\begin{center}
\begin{tikzpicture}
\node[circle,draw=black, fill=white] (1) at (0,0) {1};
\node[circle,draw=black, fill=white] (2) at (1.5,-1.5) {2};
\node[circle,draw=black, fill=white] (3) at (1.5,-3) {3};
\node[circle,draw=black, fill=white] (4) at (0,-4.5) {4};
\node[circle,draw=black, fill=white] (5) at (-1.5,-3) {5};
\node[circle,draw=black, fill=white] (6) at (-1.5,-1.5) {6};
\draw (1) to node[above right] {6} (2) to node[right] {4} (3) to node[below right] {1} (4) to node[below left] {2} (5) to node[left] {7} (6) to node[above left] {2} (1);
\draw (1) to node[below left] {5} (3) to node[below,xshift=15] {3} (5);
\draw (1) to node[left] {6} (4) to node[above right,xshift=-12,yshift=20] {4} (6);
\end{tikzpicture}
\end{center}
\begin{center}
\begin{tabular}{c|C{3cm}|C{2cm}|C{5cm}|C{2cm}}
\textbf{Iteration $k$} & \textbf{Kante mit kleinstem Kantengewicht $e^k$} & \textbf{Gewicht dieser Kante $c(e^k)$} & \textbf{Kanten im Gerüst $E^\ast$} & \textbf{Anzahl der Kanten im Gerüst $\vert E^\ast\vert$} \\
\hline
1 & $[3,4]$ & 1 & $\{[3,4]\}$ & 1 \\
\hline
2 & $[4,5]$ & 2 & $\{[3,4],[4,5]\}$ & 2 \\
\hline
3 & $[1,6]$ & 2 & $\{[3,4],[4,5],[1,6]\}$ & 3 \\
\hline
\rowcolor{gray!20}4 & $[3,5]$ & 2 & \multicolumn{2}{c}{Gerüst würde Zyklus enthalten} \\
\hline
5 & $[2,3]$ & 4 & $\{[3,4],[4,5],[1,6],[2,3]\}$ & 4 \\
\hline
6 & $[4,6]$ & 4 & $\{[3,4],[4,5],[1,6],[2,3],[4,6]\}$ & 5 \\
\hline
\multicolumn{2}{c|}{} & $\Sigma$ 13 & \multicolumn{2}{c}{}
\end{tabular}
\end{center}
\section*{Prim-Algorithmus}
\url{https://de.wikipedia.org/wiki/Algorithmus_von_Prim}
\textbf{Ziel:} Finden eines Minimalgerüstes
\textbf{Idee hinter dem Algorithmus:} selbe Idee wie beim Algorithmus von Kruskal, nur knoten- statt kantenorientiert. Man startet mit einem beliebigen Knoten im Gerüst und fügt nun solange Kanten mit kleinem Kantengewicht zum Gerüst hinzu, bis man alle Knoten im Gerüst hat. Logischerweise fügt man eine Kante nur dann hinzu, wenn sie einen neuen Knoten ins Gerüst bringt, sonst hätte man Zyklen im Gerüst.
\textbf{Beispiel:} Gegeben sei der Graph
\begin{center}
\begin{tikzpicture}
\node[circle,draw=black, fill=white] (1) at (0,0) {1};
\node[circle,draw=black, fill=white] (2) at (1.5,-1.5) {2};
\node[circle,draw=black, fill=white] (3) at (1.5,-3) {3};
\node[circle,draw=black, fill=white] (4) at (0,-4.5) {4};
\node[circle,draw=black, fill=white] (5) at (-1.5,-3) {5};
\node[circle,draw=black, fill=white] (6) at (-1.5,-1.5) {6};
\draw (1) to node[above right] {6} (2) to node[right] {4} (3) to node[below right] {1} (4) to node[below left] {2} (5) to node[left] {7} (6) to node[above left] {2} (1);
\draw (1) to node[below left] {5} (3) to node[below,xshift=15] {3} (5);
\draw (1) to node[left] {6} (4) to node[above right,xshift=-12,yshift=20] {4} (6);
\end{tikzpicture}
\end{center}
Wir wollen mit Knoten \circled{3} starten.
\begin{center}
\begin{tabular}{C{2cm}|C{2cm}|C{3cm}|C{2.25cm}|C{2cm}|C{4.5cm}}
\textbf{Knoten $W$ im Gerüst vorher} & \textbf{verfügbare Knoten $V$ vorher} & \textbf{Kante mit kleinstem Gewicht, die $W$ erweitern würde} & \textbf{Knoten $W$ im Gerüst nachher} & \textbf{verfügbare Knoten $V$ nachher} & \textbf{Kanten im Gerüst $E^\ast$} \\
\hline
$\{3\}$ & $\{1,2,4,5,6\}$ & $[3,4]$ & $\{3,4\}$ & $\{1,2,5,6\}$ & $\{[3,4]\}$ \\
\hline
$\{3,4\}$ & $\{1,2,5,6\}$ & $[4,5]$ & $\{3,4,5\}$ & $\{1,2,6\}$ & $\{[3,4],[4,5]\}$ \\
\hline
$\{3,4,5\}$ & $\{1,2,6\}$ & $[4,6]$ & $\{3,4,5,6\}$ & $\{1,2\}$ & $\{[3,4],[4,5],[4,6]\}$ \\
\hline
$\{3,4,5,6\}$ & $\{1,2\}$ & $[6,1]$ & $\{1,3,4,5,6\}$ & $\{2\}$ & $\{[3,4],[4,5],[4,6],[6,1]\}$ \\
\hline
$\{1,3,4,5,6\}$ & $\{2\}$ & $[3,2]$ & $\{1,2,3,4,5,6\}$ & $\emptyset$ & $\{[3,4],[4,5],[4,6],[6,1],[3,2]\}$
\end{tabular}
\end{center}
\section*{Dijkstra-Algorithmus}
\url{https://de.wikipedia.org/wiki/Dijkstra-Algorithmus}
\textbf{Ziel:} Finden des kürzesten Weges von einem Startknoten zu allen anderen Knoten
\textbf{Idee hinter dem Algorithmus:} Der Algorithmus hat eine Menge an Knoten $M$, zu denen er bereits den kürzesten Weg kennt. Der nächste Knoten, der zu dieser Menge hinzugefügt wird, ist der, der den kürzesten Weg zum Startknoten hat.
\textbf{Detailliertere Beschreibung:} Wir starten beim Startknoten und schauen uns dessen Nachfolger an und deren Kantengewicht an. Von diesen Nachfolgern fügen wir den Knoten zu $M$ hinzu, dessen Kantengewicht am kleinsten ist. Die Menge $M$ enthält jetzt 2 Knoten. Nun schauen wir uns alle Nachfolger (die noch nicht im $M$ sind) von den 2 Knoten in $M$ an und berechnen die Distanz zum Startknoten. Von diesen ganzen Nachfolgern fügen wir den zu $M$ hinzu, dessen Weg zum Startknoten am kürzesten ist usw.
\textbf{Beispiel:} Gegeben sei der Graph
\begin{center}
\begin{tikzpicture}
\node[circle,draw=black, fill=white] (1) at (0,0) {1};
\node[circle,draw=black, fill=white] (2) at (2,1) {2};
\node[circle,draw=black, fill=white] (3) at (2,-1) {3};
\node[circle,draw=black, fill=white] (4) at (4,1) {4};
\node[circle,draw=black, fill=white] (5) at (4,-1) {5};
\draw[->] (1) to node[above left] {5} (2);
\draw[->] (1) to node[below left] {4} (3);
\draw[->] (2) to[bend left = 30] node[right] {2} (3);
\draw[->] (3) to[bend left=30] node[left] {3} (2);
\draw[->] (2) to node[above right] {4} (5);
\draw[->] (2) to node[above] {5} (4);
\draw[->] (3) to node[below] {1} (5);
\end{tikzpicture}
\end{center}
Wir suchen die kürzeste Verbindung von Knoten \circled{1} zu allen anderen Knoten. $d_{ij}$ gibt den direkten Weg von $i$ nach $j$; $d_{ij}^{(k)}$ ist der Weg von $i$ über $k$ nach $j$.
\begin{center}
\begin{tabular}{c|C{2cm}|C{5cm}|C{5cm}}
\textbf{Iteration $k$} & \textbf{Menge an bekannten Knoten $M_k$} & \textbf{"unbekannte" Nachfolger aller Knoten in $M$} & \textbf{Distanz zu allen diesen Nachfolgern vom Startknoten} \\
\hline
1 & $\{1\}$ & $N(1)=\{2,3\}$ & $d_{12}=5$, \underline{$d_{13}=4$} \\
\hline
2 & $\{1,3\}$ & $N(1)=\{2\}$, $N(3)=\{2,5\}$ & \underline{$d_{12}=5$}, $d_{12}^{(3)}=7$, $d_{15}=5$ \\
\hline
3 & $\{1,2,3\}$ & $N(2)=\{4,5\}$, $N(3)={5}$ & $d_{14}^{(2)}=10$, $d_{15}^{(2)}=9$, \underline{$d_{15}^{(3)}=5$} \\
\hline
4 & $\{1,2,3,5\}$ & $N(2)=\{4\}$ & \underline{$d_{14}^{(2)}=10$} \\
\hline
5 & $\{1,2,3,4,5\}$ & $\emptyset$ &
\end{tabular}
\end{center}
Die kürzeste Distanz zu allen Knoten von Knoten \circled{1} sind die unterstrichenden Werte in der Tabelle, also $d_1=(0,5,4,10,5)$.
\section*{Verfahren von Bellmann}
\url{https://de.wikipedia.org/wiki/Bellman-Ford-Algorithmus}
\textbf{Ziel:} Finden des kürzesten Weges von einem Startknoten zu allen anderen Knoten, wenn der Graph zyklenfrei ist.
\textbf{Idee hinter dem Algorithmus:} Wenn ein Graph zyklenfrei ist, so kann er topologisch sortiert werden. Wir arbeiten die Knoten in aufsteigender Reihenfolge ab und schauen uns für jeden Knoten die Vorgänger an. Bei einer topologischen Sortierung haben wir uns bereits alle Vorgänger angeschaut und kennen den kürzesten Weg zu jedem dieser Vorgänger. Damit können wir nun auch den kürzesten Weg zum aktuell betrachteten Knoten ermitteln.
\textbf{Beispiel:} Gegeben sei der Graph
\begin{center}
\begin{tikzpicture}
\node[circle,draw=black, fill=white] (1) at (0,0) {1};
\node[circle,draw=black, fill=white] (2) at (2,0) {2};
\node[circle,draw=black, fill=white] (3) at (4,0) {3};
\node[circle,draw=black, fill=white] (4) at (6,0) {4};
\node[circle,draw=black, fill=white] (5) at (8,0) {5};
\draw[->] (1) to node[above] {3} (2);
\draw[->] (1) to[bend left=30] node[above] {2} (4);
\draw[->] (2) to node[above] {6} (3);
\draw[->] (3) to node[above] {1} (4);
\draw[->] (3) to[bend right=30] node[below] {5} (5);
\end{tikzpicture}
\end{center}
Wir suchen die kürzeste Verbindung von allen Knoten zu Knoten \circled{1}.
\begin{center}
\begin{tabular}{c|c|C{3cm}|C{3cm}}
\textbf{Knoten $j$} & \textbf{Vorgänger des Knotens $V(j)$} & \textbf{Distanz der Vorgänger zum Startknoten} & \textbf{Distanz von Knoten $j$ zum Startknoten} \\
\hline
\circled{1} & $\emptyset$ & & \underline{$d_{11}=0$} \\
\hline
\circled{2} & $\{1\}$ & $d_{11}=0$ & \underline{$d_{12}=3$} \\
\hline
\circled{3} & $\{2\}$ & $d_{12}=3$ & \underline{$d_{13}^{(2)}=9$} \\
\hline
\circled{4} & $\{1,3\}$ & $d_{11}=0$, $d_{13}^{(2)}=9$ & \underline{$d_{14}=2$}, $d_{14}^{(2,3)}=10$ \\
\hline
\circled{5} & $\{3\}$ & $d_{13}^{(2)}=9$ & \underline{$d_{15}^{(2,3)}=14$}
\end{tabular}
\end{center}
\section*{Tipelalgorithmus}
\url{https://de.wikipedia.org/wiki/Algorithmus_von_Floyd_und_Warshall}
\textbf{Ziel:} Finden des kürzesten Weges von jedem Knoten zu jedem Knoten.
\textbf{Idee hinter dem Algorithmus:} Iteration über alle Knoten im Graphen, die sowohl Vorgänger als auch Nachfolger haben (also weder Quellen noch Senken sind). Es wird zwischen jedem Vorgänger und jedem Nachfolger versucht einen Weg zu finden. Wenn es schon einen Weg zwischen einem Vorgänger und einem Nachfolger gibt, überprüft man, ob dieser Weg durch einen Umweg über den aktuell betrachteten Knoten kürzer ist. Wenn es diesen Weg noch nicht gibt, kann man ihn neu hinzufügen. Hier wird diese Idee an einem Beispiel in 16 Minuten erklärt: \url{https://www.youtube.com/watch?v=8qi06lDiU6I}.
\textbf{Beispiel:} Gegeben sei der Graph
\begin{center}
\begin{tikzpicture}
\node[circle,draw=black, fill=white] (1) at (0,0) {1};
\node[circle,draw=black, fill=white] (2) at (0,-2) {2};
\node[circle,draw=black, fill=white] (3) at (2,-2) {3};
\node[circle,draw=black, fill=white] (4) at (2,0) {4};
\draw[->] (1) to node[above] {4} (4);
\draw[->] (1) to node[above right] {2} (3);
\draw[->] (1) to node[left] {5} (2);
\draw[->] (3) to node[right] {1} (4);
\draw[->] (2) to[bend left=30] node[above] {3} (3);
\draw[->] (3) to[bend left=30] node[below] {2} (2);
\end{tikzpicture}
\end{center}
Umwege über Quelle \circled{1} und Senke \circled{4} können entfallen.
\begin{center}
\begin{tabular}{c|c|c|C{4cm}}
\textbf{betrachteter Knoten} & \textbf{Vorgänger} & \textbf{Nachfolger} & \textbf{Distanz zwischen Vor- und Nachgänger mit/ohne Umweg} \\
\hline
\multirow{2}{*}{\circled{2}} & \multirow{2}{*}{$\{1,3\}$} & \multirow{2}{*}{$\{3\}$} & \underline{$d_{13}=2$} vs. $d_{13}^{(2)}=8$ \\
& & & \underline{$d_{33}=0$} vs. $d_{33}^{(2)}=5$ \\
\hline
\multirow{4}{*}{\circled{3}} & \multirow{4}{*}{$\{1,2\}$} & \multirow{4}{*}{$\{2,4\}$} & $d_{12}=5$ vs. \underline{$d_{12}^{(3)}=4$} \\
& & & $d_{14}=4$ vs. \underline{$d_{14}^{(3)}=3$} \\
& & & \underline{$d_{22}=0$} vs. $d_{22}^{(3)}=5$ \\
& & & $d_{24}=\infty$ vs. \underline{$d_{24}^{(3)}=4$}
\end{tabular}
\end{center}
An den Stellen, wo der Umweg besser ist, muss man die Entfernungsmatrix $D$ des Ausgangsgraphen updaten. Selbiges gilt auch für die Vorgängermatrix $W$. So ergibt sich dann
\begin{center}
\begin{tabular}{c|cccc}
$D$ & 1 & 2 & 3 & 4 \\
\hline
1 & 0 & 4 & 2 & 3 \\
2 & $\infty$ & 0 & 3 & 4 \\
3 & $\infty$ & 2 & 0 & 1 \\
4 & $\infty$ & $\infty$ &$\infty$ & 0
\end{tabular}
\begin{tabular}{c|cccc}
$W$ & 1 & 2 & 3 & 4 \\
\hline
1 & 1 & 3 & 1 & 3 \\
2 & $\infty$ & 2 & 2 & 3 \\
3 & $\infty$ & 3 & 3 & 3 \\
4 & $\infty$ & $\infty$ & $\infty$ & 4
\end{tabular}
\end{center}
\section*{Vogel'sche Approximationsmethode}
\url{https://de.wikipedia.org/wiki/Vogelsche_Approximationsmethode}
\textbf{Ziel:} heuristische Lösung eines Transportproblems
\textbf{Idee hinter dem Algorithmus:} Für jede Produktionsstätte und jeden Abnehmer wird ein Einsparpotential als Differenz der zwei niedrigsten Transportkosten bestimmt. Die Produktionsstätte/der Abnehmer mit dem höchsten Einsparpotential wird angeschaut und dessen produzierte Waren/angeforderte Waren am billigsten transportiert. Anschließend werden die Bedarfe und produzierten Waren der anderen Abnehmer/Produktionsstätten neu berechnet und der Algorithmus beginnt von vorne, nur dass jetzt bei dem Einsparpotential die gerade behandelte Produktionsstätte/Abnehmer nicht mehr betrachtet wird.
\textbf{Beispiel:} Gegeben seiden zwei Produktionsstätten mit den Kapazitäten 11 und 13, sowie 3 Abnehmer mit den Bedarfen 6, 4 und 14.
\begin{center}
\begin{tabular}{c|ccc|cc}
& $A_1$ & $A_2$ & $A_3$ & Kapazität & Strafkosten \\
\cline{1-5}
$P_1$ & 60 & 40 & 30 & 11 & 10 \\
$P_2$ & 20 & 35 & 55 & 13 & 15 \\
\cline{1-5}
Bedarf & 6 & 4 & 14 & & \\
Strafkosten & \textcolor{red}{40} & 5 & 25
\end{tabular}
\end{center}
\begin{center}
\begin{tabular}{c|ccc|cc}
& \cellcolor{blue!20}$A_1$ & $A_2$ & $A_3$ & Kapazität & Strafkosten \\
\cline{1-5}
$P_1$ & \cellcolor{blue!20}60 & 40 & 30 & 11 & 10 \\
$P_2$ & \cellcolor{blue!20}20 \textbf{6} & 35 & 55 & 7 & 20 \\
\cline{1-5}
Bedarf & \cellcolor{blue!20}0 & 4 & 14 & & \\
Strafkosten & & 5 & \textcolor{red}{25}
\end{tabular}
\end{center}
\begin{center}
\begin{tabular}{c|ccc|c}
& \cellcolor{blue!20}$A_1$ & $A_2$ & $A_3$ & Kapazität \\
\hline
\cellcolor{blue!20}$P_1$ & \cellcolor{blue!20}60 & \cellcolor{blue!20}40 & \cellcolor{blue!20}30 \textbf{11} & \cellcolor{blue!20}0 \\
$P_2$ & \cellcolor{blue!20}20 \textbf{6} & 35 & 55 & 7 \\
\hline
Bedarf & \cellcolor{blue!20}0 & 4 & 3 &
\end{tabular}
\end{center}
\begin{center}
\begin{tabular}{c|ccc|c}
& \cellcolor{blue!20}$A_1$ & $A_2$ & $A_3$ & Kapazität \\
\hline
\cellcolor{blue!20}$P_1$ & \cellcolor{blue!20}60 & \cellcolor{blue!20}40 & \cellcolor{blue!20}30 \textbf{11} & \cellcolor{blue!20}0 \\
$P_2$ & \cellcolor{blue!20}20 \textbf{6} & 35 \textbf{4} & 55 & 3 \\
\hline
Bedarf & \cellcolor{blue!20}0 & 0 & 3 &
\end{tabular}
\end{center}
\begin{center}
\begin{tabular}{c|ccc|c}
& \cellcolor{blue!20}$A_1$ & $A_2$ & $A_3$ & Kapazität \\
\hline
\cellcolor{blue!20}$P_1$ & \cellcolor{blue!20}60 & \cellcolor{blue!20}40 & \cellcolor{blue!20}30 \textbf{11} & \cellcolor{blue!20}0 \\
$P_2$ & \cellcolor{blue!20}20 \textbf{6} & 35 \textbf{4} & 55 \textbf{3} & 0 \\
\hline
Bedarf & \cellcolor{blue!20}0 & 0 & 0 &
\end{tabular}
\end{center}
\section*{Verfahren des besten Nachfolgers für Traveling Salesman Problems}
\url{https://de.wikipedia.org/wiki/Problem_des_Handlungsreisenden} und insbesondere für den Algorithmus \url{https://de.wikipedia.org/wiki/Problem_des_Handlungsreisenden#Er%C3%B6ffnungsverfahren}
\textbf{Ziel:} Heuristik für das Finden eines kürzesten Weges, alle Knoten eines Graphen zu besuchen und wieder zum Ausgangsknoten zurückzukommen.
\textbf{Idee hinter dem Algorithmus:} Einfach zum nächsten Nachfolger laufen.
\section*{Sweep-Algorithmus}
Original-Paper: \url{https://www.jstor.org/stable/169591}, kurze Erklärung: \url{https://aktienundsweep.wordpress.com/2012/02/17/der-sweep-algorithmus-in-der-logistik/}
\textbf{Ziel:} Tourenplanung
\textbf{Idee hinter dem Algorithmus:} Die Kunden liegen um das Depot verstreut und müssen abgefahren werden. Dabei sortiert man die Kunden nach Polarwinkel, damit man in einer Tour möglichst nur Kunden hat, die ungefähr in der selben Richtung vom Depot aus liegen. Man fährt solange Kunden an, bis die Transportkapazität nicht mehr für den nächsten Kunden ausreicht. Die nächste Tour startet dann bei genau diesem Kunden.
\textbf{Beispiel:} Gegeben sei die Folgende Karte mit Depot in (0,0) und den Standorten der Kunden.
\begin{center}
\begin{tikzpicture}
\draw[->] (-5,0) -- (5,0);
\draw[->] (0,-5) -- (0,5);
\node[circle,draw=black, fill=white] (1) at (4,1) {1};
\node[circle,draw=black, fill=white] (2) at (3,2) {2};
\node[circle,draw=black, fill=white] (3) at (1,4) {3};
\node[circle,draw=black, fill=white] (4) at (-0.5,2) {4};
\node[circle,draw=black, fill=white] (5) at (-1,1) {5};
\node[circle,draw=black, fill=white] (6) at (-5,0.5) {6};
\node[circle,draw=black, fill=white] (7) at (-3,-1) {7};
\node[circle,draw=black, fill=white] (8) at (-3,-4) {8};
\node[circle,draw=black, fill=white] (9) at (2,-4) {9};
\node at (5,1) {70 ME};
\node at (4,2) {80 ME};
\node at (1,4.5) {30 ME};
\node at (-0.5,2.5) {50 ME};
\node at (-2,1) {60 ME};
\node at (-6,0.5) {100 ME};
\node at (-4,-1) {30 ME};
\node at (-3,-4.5) {70 ME};
\node at (2,-4.5) {60 ME};
\draw[->] (0,0) -- (1);
\draw[->] (1) -- (2);
\draw[->] (2) -- (0,0);
\draw[->] (0,0) -- (3);
\draw[->] (3) -- (4);
\draw[->] (4) -- (5);
\draw[->] (5) -- (0,0);
\draw[->] (0,0) -- (6);
\draw[->] (6) -- (7);
\draw[->] (7) -- (0,0);
\draw[->] (0,0) -- (8);
\draw[->] (8) -- (9);
\draw[->] (9) -- (0,0);
\end{tikzpicture}
\end{center}
Tourenplan mit einer maximalen Transportkapazität von 150 ME.
\begin{itemize}
\item 1. Tour: 0 - 1 - 2 - 0
\item 2. Tour: 0 - 3 - 4 - 5 - 0
\item 3. Tour: 0 - 6 - 7 - 0
\item 4. Tour: 0 - 8 - 9 - 0
\end{itemize}
\end{document}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment