6533b872fe1ef96bd12d2d45

RESEARCH PRODUCT

Das Chinese Postman’s Problem

subject

description

Ein Rundreiseproblem, das prima facie dem im Kapitel 6 behandelten Traveling Salesman Problem ahnelt, ist das Chinese Postman’s Problem. Wahrend beim Traveling Salesman Problem ein Rundweg durch einen Graphen gesucht ist, der jeden Knoten einmal beruhrt, ist beim Chinese Postman’s Problem nach einem Rundweg gefragt, der jede Kante eines Graphen mindestens einmal enthalt. Derartige Rundwege werden taglich von Brieftragern gegangen, die die Anlieger der durchschrittenen Strasen mit ihrer Post versorgen. Gesucht ist dabei jeweils der optimale, d.h. der z.B. kurzeste, schnellste oder kostenminimale Rundweg. Soweit man die entsprechenden Langen, Zeiten bzw. Kosten der einzelnen Strecken kennt, liegt also wieder ein Problem vom Typ AK vor. Es sei im folgenden aus Grunden der einheitlichen Terminologie unterstellt, das jeweils der kurzeste Weg gesucht ist. Bei anderen Zielsetzungen gelten die Ausfuhrungen dieses Kapitels analog.