Handlungsreisendenproblem auf Digraphen (asymmetric traveling salesman problem)
| \(\large (\text{TSP})~~\left\{~~ \begin{align*} & \text{Min.} && \sum_{(i, j) \in A} c_{ij} x_{ij} \\ & \text{u. d. N.} && \sum_{(i, j) \in A} x_{ij} = \sum_{(j, i) \in A} x_{ji} && (i \in V)\\ & && \sum_{(i, j) \in A} x_{ij} \ge 1 && (i \in V)\\ & && \pi_j-\pi_i \ge n(x_{ij}-1)+1 && ((i, j)\in A:j\neq j^\ast)\\ & && \pi_i \ge 0 && (i\in V)\\ & && x_{ij} \ge 0,~x_{ij}\in\mathbb{Z} && ((i, j)\in A) \end{align*}\right. \) |
| \(\ast\) | \(\pi_i\ge 0\) | Stufenindex von Knoten \(i\) auf der Rundreise bei Indizierung mit \(\pi_{j^\ast}=0\) |
| \(A\) | Menge der betrachteten Strecken \((i, j)\) im Verkehrsnetzwerk | |
| \(c_{ij}\) | Fahrzeit auf Strecke \((i, j)\) | |
| \(j^\ast\) | Beliebiger, aber fester ausgezeichneter Knoten | |
| \(n=|V|\) | Anzahl der Knoten | |
| \(V\) | Menge der zu bedienenden Knoten \(i\) im Verkehrsnetzwerk | |
| \(\ast\) | \(x_{ij}\in{}\mathbb{Z}_{\ge 0}\) | Häufigkeit, mit der Strecke \((i, j)\) auf der Rundreise durchfahren wird |