|
|
Tourenplanung
I. Charakterisierung: 1. Begriff: Planung des Transportmitteleinsatzes zur Verteilung und/oder Sammlung von Sendungen im Flächenverkehr. - 2. Kernaufgabe: Wahl von Transportmitteln aus einem Fuhrpark, Zusammenstellung von Sendungen zu Ladungen der Transportmittel (Ladungsproblem) und Ermittlung der Reihenfolgen, in denen die einzelnen Transportmittel ihre Ent- und/oder Beladeorte anzufahren haben (Travelling-salesman-Problem), so daß die Transportaufträge einer bestimmten Planungsperiode unter Beachtung von Kapazitäts- und Zeitbegrenzungen mit minimalen Transportstrecken-, -zeiten- und/oder -kosten ausgeführt werden.
II. Grundproblem: 1. Es existiert eine Menge von Orten, die durch gewisse Straßenverbindungen untereinander verbunden sind (Straßennetz). Die Entfernungen zwischen den Orten sind bekannt. - 2. Über das Straßennetz sind Kunden verteilt, die mit gewissen Gütern beliefert werden sollen. - 3. Im Straßennetz existiert ein Depot, an dem die zu versendenden Güter vorhanden sind. Im Depot besteht ein Fuhrpark, der sich aus identischen Fahrzeugen zusammensetzt und der die Transporte zu den Kunden durchführen soll; die Anzahl der Fahrzeuge reicht aus, um jeden sich bei der Planung ergebenden Transportplan zu realisieren. - 4. Die Fahrzeuge weisen jeweils eine bestimmte identische Transportkapazität auf, die es aber tendenziell ermöglicht, mehrere Kunden hintereinander (d. h. ohne zwischenzeitliche Rückkehr vom Depot) anzufahren. - 5. Die zu versendenden Güter beanspruchen jeweils eine gewisse Transportkapazität. - 6. Sämtliche Fahrzeuge sollen am Ende wieder zum Depot zurückkehren. - 7. Gesucht ist ein Plan (Tourenplan), der angibt, wieviele Fahrzeuge eingesetzt und welche Kunden in welcher Reihenfolge von jedem Fahrzeug angefahren werden sollen (Tour). Die Transporte sollen so vorgenommen werden, daß die von allen Fahrzeugen zurückgelegte Entfernung minimal ist.
III. Modelle: Üblicherweise verwendet man zur Darstellung von Problemen der Tourenplanung graphentheoretische Methoden, wobei man naheliegende Orte als Knoten und die Straßenverbindungen als Kanten eines Graphen darstellt (Netzplantechnik).
IV. Varianten: 1. Sind die Kunden an den Orten konzentriert, liegt ein Problem knotenorientierter Tourenplanung (z. B. Vehicle-routing-Problem), sind sie an den Straßenverbindungen konzentriert, ein Problem kantenorientierter Tourenplanung (z. B. Chinese-postman-Problem) vor. - 2. Ein Ein-Depot-Problem liegt vor, wenn sämtliche Kunden von dem gleichen Depot aus beliefert werden sollen; ein Mehr-Depot-Problem, wenn mehrere Depots gegeben sind und insofern zusätzlich festzulegen ist, welche Kunden von welchem Depot aus zu beliefern sind. - 3. Ein Sammelproblem liegt vor, wenn Kunden nicht zu beliefern sind, sondern Güter bei ihnen einzusammeln und zum Depot zu transportieren sind. Entsprechend genauer müßte das Grundproblem als Auslieferungsproblem bezeichnet werden. - 4. Im Rahmen weiterer Varianten können unterschiedlich große bzw. unterschiedliche Kosten verursachende Transportfahrzeuge, Minimierung der gesamten Transportkosten, Minimierung der Anzahl der eingesetzten Fahrzeuge o. ä. sowie zusätzliche Nebenbedingungen (z. B. Einhaltung gewisser Besuchszeiten bei den Kunden, Einhaltung vorgegebener maximaler Fahrtzeiten) berücksichtigt werden.
V. Lösungsverfahren: Es existieren verschiedene exakte Lösungsverfahren, die sich jedoch in der Praxis bisher nicht durchgesetzt haben. Üblicherweise kommen heuristische Verfahren (z. B. Savingsverfahren oder Sweep-Verfahren) zur Anwendung. Diese Verfahren sind auch Grundlage für die meisten kommerziellen Softwaresysteme zur T.
VI. Ökonomische Bedeutung: Probleme der Tourenplanung treten z. B. bei der Belieferung von Tankstellen, Apotheken, Verkaufsfilialen von Bäckereien, Lebensmittelgeschäften, Buchgeschäften, aber auch bei der Einsammlung von Milch für Molkereien oder bei der Hausmüllentsorgung auf. Sie bilden ein weites, erfolgreiches Anwendungsfeld für Methoden des Operations Research (OR).
<< vorheriger Begriff |
|
nächster Begriff>> |
|
|
|
Diese Seite bookmarken :
|
|
