1994 | OriginalPaper | Buchkapitel
Die Einsatzplanung von Zementmischern und ein Traveling Salesman Problem
verfasst von : Eberhard Triesch, Walter Nolles, Jens Vygen
Erschienen in: Operations Research Reflexionen aus Theorie und Praxis
Verlag: Springer Berlin Heidelberg
Enthalten in: Professional Book Archive
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Wir betrachten das folgende Tourenplanungsproblem: Ein Zementmischer beliefert Kunden K1,…, Kn. Er startet (gefüllt) am Lager L1 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.