Briefträgerproblem auf Digraphen – kostenminimale Eulersche Vergrößerung
(chinese postman problem – minimum-cost Eulerian extension)
| \(\large (\text{MCEE})~~\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} = 0 && (i \in V)\\ & && x_{ij} \ge 1 && ((i,j) \in A) \end{align*}\right. \) |
| \(A\) | Menge der zu bedienenden Strecken \((i, j)\) im Verkehrsnetzwerk | |
| \(c_{ij}\) | Fahrzeit auf Strecke \((i, j)\) | |
| \(V\) | Menge der Knoten \(i\) im Verkehrsnetzwerk | |
| \(\ast\) | \(x_{ij}\ge 0\) | Häufigkeit, mit der Strecke \((i, j)\) auf der Briefträgertour durchfahren wird |