Die Einsatzplanung von Zementmischern und ein Traveling Salesman Problem

Wir betrachten das folgende Tourenplanungsproblem: Ein Zementmischer beliefert Kunden K₁,…, K_n. Er startet (gefüllt) am Lager L₁ und muß zwischen zwei Kunden stets eines von m Lagern anfahren, in denen er wieder aufgefüllt wird. Was ist die kürzeste Tour zur Belieferung aller Kunden? Wir zeigen, daß das allgemeine Problem NP-schwer ist. Im Falle der Beschränktheit von m ist das Problem aber polynomial lösbar. Der Beweis dieser Tatsache führt uns auf eine neue Klasse von polynomial lösbaren Traveling Salesman Problemen.