Das Chinese Postman Problem handelt von einem Postboten, der Briefe austrägt. Dabei trägt er die Briefe auf beiden Straßenseiten gleichzeitig aus. Gesucht ist nun der kürzeste Zyklus, der alle Straßen mindestens einmal durchläuft.
Das Problem beschreibt informal die Suche nach dem kürzesten Eulerkreis.
Formulierung als Lineares Problem
Das Problem kann auch als Lineares Programm formuliert werden. Grundidee ist das Kürzeste-Wege-Problem als Lineares Programm:
Unter den Nebenbedingungen:
- Gehe jede Kante mindestens 1 mal ab
- Durchlaufe einen geschlossenen Weg
- Nichtnegativität von