Anzeige
Erschienen in:
1993 | OriginalPaper | Buchkapitel
Schranken für ein Kapazitätsbeschränktes Traveling Salesman Problem mit Quellen und Senken
verfasst von : Günther Schulz
Erschienen in: DGOR / ÖGOR
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
Die Arbeit befaßt sich mit der Berechnung unterer Schranken für ein kapazitätsbeschränktes Traveling Salesman Problem mit Quellen und Senken. Wir benutzen eine Relaxation durch minimale 1-Gerüste mit zusätzlichen Einschränkungen bzgl. der Auswahl der Kanten. Das Problem wird als minimal gewichtetes Matroid-Intersection- Problem auf dem Durchschnitt von zwei Matroiden gelöst. Ein polynomialer Algorithmus der Komplexität O(n4) wird angegeben.