Tourenplanungsproblem (capacitated vehicle routing problem)

\(\large (\text{CVRP})~~\left\{~~ \begin{align*} & \text{Min.} && \sum_{\mu=1}^n\sum_{(i, j) \in A} c_{ij} x^\mu_{ij} \\ & \text{u. d. N.} && \sum_{\mu=1}^n y^\mu_i = 1 && (i \in V\setminus\{0\})\\ & && \sum_{i\in V} \hat{b}_i y^\mu_i \le u && (\mu=1, \ldots, n)\\ & && \sum_{(i, j) \in A} c_{ij} x^\mu_{ij} \le D && (\mu=1, \ldots, n)\\ & && \sum_{(i, j)\in A}x^\mu_{ij} \ge y^\mu_i && (i\in V;~\mu=1, \ldots, n)\\ & && \sum_{(i, j) \in A} x^\mu_{ij} = \sum_{(j, i) \in A} x^\mu_{ji} && (i \in V\setminus\{0\};~\mu=1, \ldots, n)\\ & && \pi_j-\pi_i \ge n(x^\mu_{ij}-1)+1 && ((i, j)\in A:j\neq 0;~\mu=1, \ldots, n)\\ & && x^\mu_{ij} \ge 0,~x^\mu_{ij}\in\mathbb{Z} && ((i, j)\in A;~\mu=1, \ldots, n)\\ & && y^\mu_i\in\{0, 1\} && (i\in V;~\mu=1, \ldots, n) \end{align*}\right. \)
\(\ast\)\(\pi_i\ge 0\)Stufenindex von Knoten \(i\) auf seiner Tour bei Indizierung mit \(\pi_0=0\)
\(A\)Menge der betrachteten Strecken \((i, j)\) im Verkehrsnetzwerk
\(\hat{b}_i\)Bedarf von Kunde \(i\)
\(c_{ij}\)Fahrzeit auf Strecke \((i, j)\)
\(D\)Maximale Dauer einer Tour
\(n=|V|\)Anzahl der Knoten
\(u\)Ladekapazität eines Fahrzeugs
\(V\)Menge der zu bedienenden Kunden \(i\) und Depot \(0\)
\(\ast\)\(x^\mu_{ij}\in\mathbb{Z}_{\ge 0}\)Häufigkeit, mit der Strecke \((i, j)\) auf Tour \(\mu\) durchfahren wird
\(\ast\)\(y^\mu_i\in\{0, 1\}\)\(=1\), falls Kunde \(i\) auf Tour \(\mu\) bedient wird, \(=0\), sonst