Beschreibung

Die Erfindung bezieht sich die Planung von Touren, insbesondere von Touren von Postzustellern. Dabei betrifft die Erfindung ein Verfahren und ein System zum Planen von Touren die jeweils entlang einer Mehrzahl von Orten führen und für die jeweils eine Reihenfolge der Orte nach Maßgabe von Distanzen zwischen den Orten ermittelt wird.

Eine Tourenplanung wird in einer Vielzahl von Bereichen vorgenommen, die mit der Auslieferung von Waren und/oder dem Besuch einer Mehrzahl von Standorten verbunden sind, und umfasst die Bestimmung einer optimalen Reihenfolge, in der Standorte bedient werden, an denen bestimmte Aufträge zu erledigen sind. Ein Beispiel für einen Bereich, in dem die Tourenplanung von großer Bedeutung ist, ist die Zustellung und Abholung von Paketen und anderen Postsendungen, für die Zusteller ein- oder mehrmals täglich Touren durchführen, die wechselnde Adressen enthalten.

Die Tourenplanung wird insbesondere unter Berücksichtigung der auf den Touren zu bedienenden Adressen vorgenommen. Eingangsgrößen der Tourenplanung sind insbesondere die Distanzen zwischen den Standorten, die beispielsweise in einer Distanzmatrix angegeben und vor Durchführung der eigentlichen Tourenplanung berechnet werden können.

Aus der DE 10 2004 019 232 B4 geht ein Verfahren zur Touren- und Routenplanung hervor, bei dem insbesondere die Ermittlung der Reihenfolge von Adressen, an denen Objekte zuzustellen und/oder abzuholen sind, für die zu planenden Touren jeweils nach Maßgabe von geographischen Daten vorgenommen wird.

Um anhand der geographischen Daten die Tourenplanung vornehmen zu können, sind aus den Daten die Distanzen zwischen den zu bedienenden Adressen zu ermitteln. Für Anzahlen von Adressen, die typischerweise bei der Tourenplanung für die Zustellung von Paketen und/oder anderen Postsendungen zu berücksichtigen sind, ist hiermit jedoch jeweils ein hoher rechentechnischer und zeitlicher Aufwand verbunden.

Es ist eine Aufgabe der vorliegenden Erfindung, den Aufwand der Tourenplanung, insbesondere den Aufwand für die Ermittlung der Distanzen zwischen den zu berücksichtigenden Orten, zu verringern.

Die Aufgabe wird gelöst durch ein Verfahren mit den Merkmalen des Anspruchs 1 und eine Vorrichtung mit den Merkmalen des Anspruchs 14. Ausgestaltungen des Verfahrens und der Vorrichtung sind in den abhängigen Ansprüche angegeben.

Gemäß einem ersten Aspekt schlägt die Erfindung ein Verfahren zur Planung von Touren vor, die jeweils entlang einer Mehrzahl von Orten führen, und für die jeweils eine Reihenfolge von Orten nach Maßgabe von Distanzen zwischen den Orten ermittelt wird. Die Distanzen zwischen ersten Orten einer ersten Tour werden im Zusammenhang mit der Bestimmung der ersten Tour in einem Speicher gespeichert. Eine nachfolgende zweite Tour wird nach Maßgabe von in dem Speicher hinterlegten Distanzen zwischen Orten der zweiten Tour und nach Maßgabe von weiteren Distanzen zwischen Orten der zweiten Tour ermittelt, wobei die weiteren Distanzen im Speicher ergänzt werden.

Gemäß einem weiteren Aspekt wird eine Vorrichtung zum Planen von Touren bereitgestellt, die jeweils entlang einer Mehrzahl von Orten führen. Die Vorrichtung umfasst eine Tourenplanungseinrichtung, die dazu ausgestaltet ist, für die Touren jeweils eine Reihenfolge der Orte nach Maßgabe von Distanzen zwischen den Orten zu ermitteln, und die mit einer Speichereinrichtung verbunden ist. Die Tourenplanungseinrichtung ist dazu ausgestaltet, Distanzen zwischen ersten Orten einer ersten Tour im Zusammenhang mit der Bestimmung der ersten Tour in der Speichereinheit zu speichern und eine nachfolgende zweite Tour nach Maßgabe von in der Speichereinheit gespeicherten Distanzen zwischen Orten der zweiten Tour und nach Maßgabe von Distanzen zwischen weiteren Orten zu bestimmen. Die Tourenplanungseinrichtung ist ferner dazu ausgestaltet, die Distanzen zu den weiteren Orten in der Speichereinheit zu ergänzen. Die Distanzen zwischen Orten der zweiten Tour, die im Speicher bzw. der Speichereinheit hinterlegt sind, wurden vorteilhaft bereits im Zusammenhang mit der Planung der ersten Tour bestimmt, d.h., es handelt sich im Orte der zweiten Tour, die auch Bestandteil der ersten Tour sind.

Durch den Rückgriff auf Distanzen, die nach ihrer Bestimmung im Zusammenhang mit einer Tour für die Planung weiterer Touren in dem Speicher bzw. der Speichereinheit gespeichert bleiben, wird der Aufwand für die Planung von Touren, insbesondere der Aufwand für die Ermittlung von Distanzen zwischen den Orten der Touren, verringert. Zur Planung einer neuen Tour müssen lediglich die Distanzen in Bezug auf die Orte ermittelt werden, die im Speicher nicht berücksichtigt sind, weil sie kein Bestandteil vorangegangener Touren gewesen sind. Auf diese Weise füllt sich der Speicher kontinuierlich mit Adressen, so dass immer weniger Distanzen für die Tourenplanung neu bestimmt werden müssen.

Die im Speicher berücksichtigten Orte sind zudem für die Planung von Touren relevant, da sie zumindest einmal bei einer Tour berücksichtigt werden. Distanzen für irrelevante Orte, die auf den zu planenden Touren nicht besucht werden, müssen hingegen nicht bestimmt werden. Dies ist ein weiterer Vorteil der bei dem Verfahren und in der Vorrichtung vorgesehen bedarfsabhängigen Bestimmung von Distanzen.

Um den für die Distanzermittlung erforderlichen Aufwand in einem möglichst hohen Maße zu reduzieren, werden zur Bestimmung der zweiten Tour gespeicherte Distanzen zwischen den Orten der zweiten Tour herangezogen, soweit sie in dem Speicher vorhanden sind. In dieser Ausgestaltung werden lediglich Distanzen, die nicht bereits in dem Speicher hinterlegt sind, neu bestimmt, um die Planung der zweiten Tour durchzuführen.

Um dies zu erreichen, sieht eine Ausgestaltung des Verfahrens und der Vorrichtung vor, dass im Zusammenhang mit der Bestimmung der zweiten Tour die weiteren Orte der zweiten Tour ermittelt werden, für die im Speicher keine zugehörigen Distanzen enthalten sind, und Distanzen bezüglich dieser weiteren Orte ermittelt und im Speicher ergänzt werden. Die Ermittlung der weiteren Orte der zweiten Tour, für die im Speicher keine zugehörigen Distanzen enthalten sind, kann anhand eines Vergleichs der Orte der zweiten Tour mit den Orten vorgenommen werden, für die im Speicher Distanzen hinterlegt sind. Diese Prüfung kann beispielsweise dann vorgenommen werden, wenn die Orte der zweiten Tour an die Tourenplanungseinrichtung gemeldet werden.

Bei einer weitere Ausgestaltung des Verfahrens und der Vorrichtung sind die Distanzen, die ermittelt und im Speicher ergänzt werden, Distanzen zwischen den weiteren Orten und/oder Distanzen zwischen den weiteren Orten und den bereits im Speicher berücksichtigten Orten. Hierbei kann es sich um Orte handeln, die ebenfalls Bestandteil der zweiten Tour sind. Gleichfalls können auch zusätzlich die Distanzen zu weiteren Orten bestimmt werden, die im Speicher berücksichtigt sind. Infolgedessen können auch Distanzen ermittelt und ergänzt, die in Bezug zu Orten stehen, die nicht bei der zweiten Tour besucht werden. Die Ergänzung wird jedoch im Hinblick auf mögliche nachfolgende Tourenplanungen vorgenommen, in denen diese Distanzen verwendet werden können.

Die im Speicher hinterlegten Distanzen können verschiedene Größen repräsentieren. Vorzugsweise werden die Touren so geplant, dass eine vorgegebene Größe, wie beispielsweise die zurückzulegende Entfernung und/oder die Zeit für die Durchführung einer oder mehrerer (gleichzeitig geplanter) Touren, nach Möglichkeit minimiert wird. Die im Speicher hinterlegten Distanzen können an die zu optimierende Größe angepasst sein. In einer Ausgestaltung des Verfahrens und der Vorrichtung handelt es sich bei den Distanzen um zeitliche Distanzen zwischen den Orten. Das heißt, dass die Distanz zwischen einem ersten und einem zweiten Ort eine Zeit angibt, die benötigt wird, um von dem ersten zu dem zweiten Ort zu gelangen. Die zeitlichen Distanzen können insbesondere dazu verwendet werden, Touren zu planen, bei denen die benötigte Zeit minimiert ist.

Zur Ermittlung von zeitlichen Distanzen zwischen den Orten sieht eine Ausgestaltung des Verfahrens und der Vorrichtung vor, dass die Distanzen zwischen den Orten in Abhängigkeit von ermittelten Routen zwischen den Orten bestimmt werden. Die Routen können so ermittelt werden, dass sie ein Optimierungskriterium zumindest nach Möglichkeit erfüllen. Insbesondere kann es sich um die kürzesten oder schnellsten Routen handeln.

Einen Einfluss auf die tatsächlich zurückzulegenden Distanzen hat die Verkehrslage, da sich Distanzen durch Verkehrsbeeinträchtigungen, wie beispielsweise Staus oder Sperrungen, vergrößern können. Zur Berücksichtigung der Verkehrslage beinhaltet eine Weiterbildung des Verfahrens und der Vorrichtung, dass die im Speicher hinterlegten Distanzen in Abhängigkeit von Verkehrsinformationen ermittelt und/oder aktualisiert werden. Durch eine Aktualisierung bereits im Speicher hinterlegter Distanzen lassen sich insbesondere Änderungen der Verkehrslage und daraus resultierende Änderungen der Distanzen berücksichtigen.

Ergänzend oder alternativ ist in einer Ausführungsform des Verfahrens und der Vorrichtung vorgesehen, dass die Distanzen anhand von während der Durchführung der Tour erfassten Messwerten bestimmt und im Speicher aktualisiert werden. Hierdurch können im Speicher die tatsächlich zurückgelegten Distanzen gespeichert werden. Dies geschieht vorzugsweise durch eine Aktualisierung von Distanzen, die beispielsweise vor der Durchführung der Tour berechnet worden sind. Bei den Messwerten kann es sich beispielsweise um erfasste Positionen und Zeiten handeln, aus denen zeitliche Distanzen zwischen den Orten der Tour ermittelt werden können.

Darüber hinaus ist eine Ausgestaltung des Verfahrens und der Vorrichtung dadurch gekennzeichnet, dass für wenigstens zwei Orte mehrere Distanzen zwischen den Orten im Speicher hinterlegt werden und die Distanzen für unterschiedliche Zeiträume gültig sind. Bei den Zeiträumen kann es sich insbesondere um Tageszeitintervalle und/oder Wochentage handeln. Durch die Hinterlegung mehrerer Distanzen für unterschiedliche Zeiten können unterschiedliche Verkehrslagen berücksichtigt werden, wie sie in der Regel in verschiedenen Zeiträumen eines Tages bzw. einer Woche vorliegen.

Eine weitere Ausführungsform des Verfahrens und der Vorrichtung beinhaltet, dass für wenigstens zwei Orte mehrere Distanzen zwischen den Orten im Speicher hinterlegt werden und die Distanzen für unterschiedliche Verkehrsmittel gültig sind. Hierdurch kann berücksichtigt werden, dass nicht alle Touren mit demselben Verkehrs- mittel durchgeführt werden und dass sich die Distanzen zwischen den Orten für unterschiedliche Verkehrsmittel beispielsweise aufgrund der erreichbaren Geschwindigkeit und/oder der benutzbaren Wege unterscheiden.

Eine mit den beiden zuvor genannten Ausgestaltungen verbundene Ausführungsform sieht vor, dass die erste und/oder zweite Tour nach Maßgabe der Distanz bestimmt wird, die für den Zeitraum gültig ist, in dem eine der Orte erreicht wird und/oder die für das zu benutzende Verkehrsmittel gültig ist.

Bei den geplanten Touren handelt es sich in einer Ausführungsform des Verfahrens und der Vorrichtung um Touren zur Zustellung und/oder Abholung von Postsendungen und bei den Adressen um Orte, an denen Postsendungen zuzustellen und/oder abzuholen sind. Die Tourenplanung umfasst vorzugsweise die Bestimmung der Reihenfolge, in der die Adressen von den Zustellern besucht werden und kann auch die Zuordnung von zuzustellenden Postsendungen und/oder Abholaufträgen zu den verfügbaren Zustellern umfassen.

Gemäß einem weiteren Aspekt schlägt die Erfindung ein Computerprogramm vor, das einen Softwarecode mit Befehlen zur Ausführung des Verfahrens und seiner Varianten auf einer Datenverarbeitungsanlage umfasst.

Die zuvor genannten und weitere Vorteile, Besonderheiten und zweckmäßige Weiterbildungen der Erfindung werden auch anhand der Ausführungsbeispiele deutlich, die nachfolgend unter Bezugnahme auf die Figuren beschrieben werden.

Von den Figuren zeigt:

Fig. 1 eine schematische Darstellung eines Zustelldepots mit zugehöriger Planungseinrichtung und einem dem Zustelldepot zugeordneten Zustellfahrzeug,

Fig. 2a eine schematische Veranschaulichung einer Distanzmatrix in einer ersten

Version und Fig. 2b eine schematische Veranschaulichung einer Distanzmatrix in einer weiteren Version.

Abgehend von dem in der Figur 1 schematisch gezeigten Zustelldepot 101 eines Postunternehmens erfolgt die Zustellung von Postsendungen in einem dem Zustelldepot 101 zugeordneten geographischen Gebiet 102. Zudem kann auch vorgesehen sein, dass die dem Zustelldepot 101 zugeordneten Zusteller Postsendungen von Absendern innerhalb des geographischen Gebiets 102 abholen, wenn die Absender entsprechende Abholaufträge an das Zustelldepot 101 oder eine andere Einrichtung des Postunternehmens übermitteln. Die Postsendungen können Pakete sein oder andere Postsendungen, wie beispielsweise Briefe.

Das Zustelldepot 101 verfügt über eine feste oder variable Anzahl von Zustellern, denen Zustellfahrzeuge 103 zugeordnet werden können, die von den Zustellern für die Zustellung und/oder Abholung von Postsendungen verwendet werden. Vorzugsweise werden mehrere Zusteller mit jeweils einem zugeordneten Zustellfahrzeug 103 eingesetzt (in Figur 1 ist beispielhaft jedoch lediglich ein Zustellfahrzeug 103 gezeigt). Die Zustellfahrzeuge 103 können als vier- oder mehrrädrige Personen- oder Lastkraftwagen ausgestaltet sein. Grundsätzlich können alle Zusteller des Zustelldepots 101 ein derartiges Zustellfahrzeug 103 verwenden. Es kann jedoch auch vorgesehen sein, dass zumindest ein Teil der Zusteller andere Verkehrsmittel für die Zustellung und/oder Abholung von Postsendungen nutzen, wie beispielsweise zweirädrige Kraftfahrzeuge, Fahrräder oder Rollwagen für die Zustellung zu Fuß.

Die in dem Zustelldepot 101 eingesetzten Zusteller bzw. Zustellfahrzeuge 103 führen täglich wenigstens eine Tour zur Zustellung und Abholung von Postsendungen durch. Gleichfalls kann wenigstens ein Teil der Zusteller auch mehrere Touren an einem Tag durchführen. Die Touren starten und enden jeweils an dem Zustelldepot 101 und beinhalten Besuche bei den dem Zusteller zugeordneten Adressen, an denen Postsendungen zuzustellen und/oder abzuholen sind. Diese Adressen werden nachfolgend auch als Stopps der Touren oder Routen der Zusteller bezeichnet.

Für die Planung der Touren ist eine Planungseinrichtung 105 vorgesehen, die im Zustelldepot 101 angeordnet sein kann oder separat, wie in Figur 1 beispielhaft gezeigt. Die Planungseinnchtung 105 ist als eine Datenverarbeitungsanlage mit einem Computerprogramm zur Ausführung der Tourenplanung ausgestattet. Die in der Planungseinrichtung 105 vorgenommene Tourenplanung umfasst vorzugsweise die Aufteilung der auszuliefernden Postsendungen auf die in dem Zustelldepot 101 zur Verfügung stehenden Zusteller bzw. die Zustellfahrzeuge 103. Gleichfalls erfolgt auch eine Aufteilung der vorliegenden Abholaufträge auf die Zusteller. Des Weiteren bestimmt die Planungseinrichtung 105 für die einzelnen Zusteller eine Reihenfolge, in der die Adressen bedient werden sollen, an denen Postsendungen zuzustellen und/oder abzuholen sind.

In einer Ausgestaltung sind die Zusteller dazu in der Lage, drahtlos dem Zustelldepot 101 zugeordneten Planungseinrichtung 105 zu kommunizieren. Dies geschieht beispielsweise über ein Mobilfunknetz 108, wie in der Figur 1 dargestellt. Zur Kommunikation können die Zustellfahrzeuge 103 eine in der Figur nicht gezeigte Kommunikationseinrichtung umfassen. Gleichfalls können die Zusteller jedoch auch tragbare Kommunikationseinrichtungen, wie beispielsweise Smartphones oder Notebook- Computer verwenden, um Datenverbindungen zu der Planungseinrichtung 105 aufzubauen. Über die Kommunikationsverbindung können insbesondere Tourendaten, wie Angaben über die zuzustellenden Sendungen, Abholaufträge und die in der Planungseinrichtung 105 ermittelte Reihenfolge der Stopps an die Zusteller bzw. Zustellfahrzeuge 105 übermittelt werden. Dies kann insbesondere auch bei der Neuplanung einer Tour vorgenommen werden, die durchgeführt werden kann, um Abholungen in die Tour zu integrieren, die nach Tourbeginn beauftragt werden.

Des Weiteren verfügen die Zusteller vorzugsweise über jeweils eine Ortungseinheit 107 zur Bestimmung ihrer Position, die in einem Zustellfahrzeug fest installiert sein oder von dem Zusteller als mobile Einrichtung mitgeführt werden kann. Die Ortungseinheit 107 kann als satellitengestützte Ortungseinheit 107 ausgebildet sein, welche die Position des Zustellfahrzeugs 103 in einer dem Fachmann an sich bekannten Weise anhand von Signalen eines Satellitennavigationssystems, beispielsweise des Global Positioning System (GPS), bestimmt. Die ermittelten Positionen des Zustellfahrzeugs 103 können an die Planungseinrichtung 105 übermittelt werden, so dass diese auch während einer Tour über die aktuelle Position des Zustellfahrzeugs 103 verfügt. In einer unten erläuterten Ausführungsform können diese Positionsdaten auch dazu verwendet werden, die Route des Zustellers nachzuverfolgen. Die Ortungseinheit 107 kann zudem Bestandteil einer tragbaren oder fest installierten Navigationseinrichtung sein, die dazu in der Lage ist, eine Route in einem Wegenetz des Gebiets 102 von einer Position des Zustellfahrzeugs 103 zu einem Zielpunkt zu ermitteln und den Fahrer des Zustellfahrzeugs 103 durch akustische und/oder optische Navigationshinweise entlang der Route zu dem Zielpunkt zu führen, bei dem es sich insbesondere um eine Stoppadresse handeln kann.

In dem geografischen Gebiet 102 zuzustellende Postsendungen werden über ein Logistiksystem 104 des Postunternehmens zu dem Zustelldepot 101 befördert. Dies kann beispielsweise ein- oder mehrmals täglich geschehen. Das Logistiksystem 104 umfasst in einer Ausgestaltung mehrere in der Figur nicht gezeigte Sortierzentren für Postsendungen, in denen Postsendungen auf dem Weg von ihrem Absender zum Empfänger sortiert und weitergeleitet werden (bei dem Zustelldepot 101 kann es sich gleichfalls um ein Sortierzentrum handeln oder um eines von mehreren separaten Zustelldepots, die gemeinsam einem Sortierzentrum des Logistiksystems 104 zugeordnet sind). Die Adressen der zuzustellenden Postsendungen können bereits in dem Logistiksystem 104 erfasst und an die Planungseinrichtung 105 übermittelt werden, oder die Adressen werden beim Eingang der Postsendungen in dem Zustelldepot 101 erfasst und an die Planungseinrichtung 105 gemeldet. Bei der Planung der Touren werden in einer Ausgestaltung die Zustelladressen der Postsendungen berücksichtigt, die das Zustelldepot 101 vor dem Beginn der Touren erreichen.

Abholaufträge werden von den Absendern an das Postunternehmen übermittelt und beispielsweise in einer zentralen Einrichtung erfasst. Die Übermittlung kann telefonisch, online, etwa über eine Webseite, oder anhand einer elektronisch übermittelten Nachricht, wie etwa einer E-Mail, erfolgen. Von der zentralen Einrichtung können die Abholaufträge für Adressen in dem geografischen Gebiet 102, das dem Zustelldepot 101 zugeordnet ist, an die Planungseinrichtung 105 übermittelt werden. In einer Ausgestaltung berücksichtigt die Planungseinrichtung 105 die Abholaufträge bei der Planung von Touren, die bis zu einem bestimmten Zeitpunkt vor dem Beginn der Touren eingegangen sind. Gleichfalls kann vorgesehen sein, auch später in der Planungseinrichtung 105 eingehende Abholaufträge zu berücksichtigen und in bereits geplante Touren zu integrieren. Dies kann auch nach dem Beginn einer Tour durchgeführt werden. In diesem Fall werden dem Zusteller der Auftrag sowie ggf. aufgrund des Auftrags geänderte Tourendaten, wie etwa eine aufgrund des Auftrags veränderte Reihenfolge der Stopps, über das Mobilfunknetz 108 übermittelt.

Die Tourenplanung in der Planungseinrichtung 105 wird auf der Grundlage der von den Zustellern zu bedienenden Adressen und der Distanzen zwischen den Adressen vorgenommen. Dabei wird die Zuordnung der Stopps zu den Zustellern nach einem oder mehrerer Optimierungskriterien vorgenommen, etwa so, dass eine gleichmäßige Auslastung der Zusteller erreicht wird, die Gesamtdauer oder -länge der Touren minimiert wird. Die Tourenplanung umfasst zudem die Ermittlung der Stoppreihenfolge für die Touren der einzelnen Zusteller. Zur Tourenplanung wird in der Planungseinrichtung 105 vorzugsweise ein heuristischer Algorithmus verwendet, der in einer dem Fachmann bekannten Weise ausgeführt werden kann.

In der Planungseinrichtung 105 werden die zur Tourenplanung verwendeten Distanzen vor der Berechnung der Touren ermittelt und in einer nicht-flüchtigen Speichereinheit 109 der Planungseinrichtung 105 abgelegt. Um die Tourenberechnung durchzuführen, liest die Planungseinrichtung 105 die Distanzen zwischen den zu bedienenden Adressen aus der Speichereinheit 109 aus und verwendet sie als Eingangsgrößen für den Tourenplanungsalgorithmus. Dabei werden für jede zu bedienende und bei der Tourenplanung zu berücksichtigende Adresse jeweils Distanzen zu allen übrigen zu bedienenden Adressen bereitgestellt. In der Folge können für jede Adresse insbesondere auch Distanzen von den übrigen Adressen zu dieser Adresse berücksichtigt werden.

Bei den Distanzen handelt es sich vorzugsweise um zeitliche Distanzen, welche die Zeit angeben, die benötigt wird, um von einer Adresse zu einer anderen Adresse zu gelangen. Alternativ können die Distanzen jedoch auch die Entfernungen zwischen den Adressen oder anderen Größen angeben. Vorzugsweise wird die Größe, auf die sich die Distanzen beziehen, an das Optimierungskriterium angepasst, das der Tourenplanung zugrunde liegt. So können die Distanzen insbesondere Werte einer zu optimierenden Größe sein. In der Speichereinheit 109 werden die Distanzen in einer vorgegebenen Datenstruktur abgelegt, vorzugsweise in einer Distanzmatrix. Diese enthält Einträge d , die jeweils die Distanz von einer Adresse i zu einer Adresse j angeben. Die Einträge auf der Hauptdiagonalen der Distanzmatrix, d. h. die Einträge d,,, haben den Wert null. Die Distanzmatrix ist im Allgemeinen nicht symmetrisch, da die Distanz von einer Adresse i zu einer Adresse j jedenfalls nicht notwendig der Distanz von der Adresse j zu der Adresse i entspricht. Ein Grund für Unterschiede in diesen Distanzen kann beispielsweise sein, dass eine Route von der Adresse i zu der Adresse j aufgrund von Einbahnstraßen oder ähnlichem nicht in umgekehrter Richtung befahren werden kann.

Es ist vorgesehen, die Distanzmatrix nicht vor jedem in dem Planungsrechner 105 durchgeführten Tourenplanungsvorgang neu zu bestimmen. Stattdessen bleiben einmal berechnete Distanzen grundsätzlich in der Speichereinheit 109 gespeichert und können für mehrere Tourenberechnungsvorgänge verwendet werden (die Distanzen können in einer Ausgestaltung allerdings aktualisiert werden, wie noch beschrieben wird). Die Ermittlung der Distanzen wird vorzugsweise dann vorgenommen, wenn die zugehörigen Adressen erstmals zu bedienen sind. Wenn neue Adressen zu bedienen sind, die in der Distanzmatrix nicht berücksichtigt sind, ist vorgesehen, Distanzen zwischen den neuen Adressen sowie Distanzen zwischen den neuen und den übrigen Andressen der Distanzmatrix zu ermitteln und der Distanzmatrix hinzuzufügen.

Erstmalig kann die Distanzmatrix zur Vorbereitung eines bestimmten Tourenberechnungsprozesses auf der Grundlage der dabei zu berücksichtigenden Adressen ermittelt und daraufhin in der Speichereinheit 109 hinterlegt werden. In Figur 2a ist in einer schematischen Darstellung eine Distanzmatrix veranschaulicht, die sich infolge der erstmaligen Bestimmung ergeben kann. In der gezeigten Distanzmatrix werden N Adressen A-i, A _N berücksichtigt, auf deren Grundlage der Tourenplanungsprozess vorgenommen wird, für den die erstmalige Berechnung der Distanzmatrix vorgenommen wird. Die Distanzwerte beinhaltenden Einträge der Distanzmatrix sind in der Figur 2a schraffiert dargestellt. Wenn der Planungseinnchtung 105 eine oder mehrere weitere Adressen gemeldet werden, die bei nachfolgenden Tourenberechnungsprozessen zu berücksichtigen sind, prüft die Planungseinrichtung 105, ob diese Adressen bereits in der Version der Distanzmatrix berücksichtigt sind, in der Speichereinheit 109 hinterlegt ist. Ist dies für eine oder mehrere der empfangenen Adressen der Fall, werden die in der Speichereinheit 109 hinterlegten Distanzen in Bezug auf diese Adresse verwendet. Wenn die Planungseinrichtung 105 feststellt, dass eine oder mehrere der empfangenen Adressen nicht in der gespeicherten Version der Distanzmatrix berücksichtigt sind, werden Distanzen zwischen den betreffenden Adressen sowie zwischen den neuen Adressen und den bereits in der Distanzmatrix berücksichtigten Adressen ermittelt und in der Distanzmatrix hinterlegt. Hierdurch ergibt sich eine neue Version der Distanzmatrix, die in der Speichereinheit 109 hinterlegt wird.

Figur 2b zeigt in einer schematischen Darstellung eine Version der Distanzmatrix, die auf der Grundlage der in der Figur 2a gezeigten Version ermittelt worden ist, nachdem der Planungseinrichtung 105 weitere Adressen gemeldet worden sind. In der beispielhaft zugrunde gelegten Situation befinden sich unter den weiteren Adressen M Adressen Bi , ... , B _M , die keiner der Adressen Ai , ... , A _N entsprechen und daher in der vorangegangenen Version der Distanzmatrix nicht berücksichtigt worden sind. Wie in Figur 2b dargestellt, werden von der Planungseinrichtung 105 Distanzen zwischen den Adressen B-i, ... , B _M und zwischen den Adressen B-i, B _M und den Adressen A-i, ... A _N in der Distanzmatrix ergänzt. Die ergänzten Einträge sind in der Figur 2b durch eine gegenüber derjenigen der ursprünglichen Einträge geänderte Schraffur kenntlich gemacht.

In gleicher Weise wie bei der ersten Hinzufügung von Distanzen wird die Distanzmatrix immer dann ergänzt, wenn der Planungseinrichtung Adressen gemeldet werden, die von den Zustellern des Zustelldepots 101 zu bedienen und bei der Tourenplanung in der Planungseinrichtung 105 zu berücksichtigen sind. Auf diese Weise werden in der Distanzmatrix fortlaufend Distanzen in Bezug auf Adressen hinzugefügt, an denen Postsendungen zuzustellen und/oder abzuholen sind. Der Zuwachs an Distanzen wird dabei stetig geringer, da mit der Zeit immer weniger Adressen des dem Zustelldepot 101 zugeordneten geographischen Gebiets 102 verbleiben, die in der Distanzmatrix nicht berücksichtigt sind. Nach einer bestimmten Zeitdauer ist die Distanzmatrix auf diese Weise auf einen Umfang angewachsen, in dem im Wesentlichen alle bzw. eine Vielzahl von bei der Zustellung und/oder Abholung von Postsendungen zu berücksichtigenden Adressen Eingang in der Distanzmatrix gefunden haben. Adressen, an denen nie Postsendungen zugestellt und/oder abgeholt werden, beispielsweise weil die zugehörigen Grundstücke unbenutzt sind, werden in der Distanzmatrix hingegen nicht berücksichtigt. Dies ist ein Vorteil der vorgesehenen bedarfsabhängigen Ergänzung der Distanzmatrix, die dazu führt, dass nur Distanzen zwischen Adressen bestimmt werden müssen, die für die Zustellung und/oder Abholung von Postsendungen relevant sind.

Eine alternative Ausführungsform unterscheidet sich von der zuvor erläuterten Ausgestaltung dadurch, dass für neue Adressen, die für einen Tourenplanungsprozess übermittelt werden, nicht die Distanzen zu allen bereits in der Distanzmatrix berücksichtigten Adressen berechnet werden, sondern lediglich zu denjenigen in der Distanzmatrix bereits berücksichtigten Adressen, die auch in bei der Tourenplanung zu berücksichtigen sind. Die Distanzen zwischen einer neuen und einer weiteren Adresse die bereits in der Distanzmatrix berücksichtigt, bestimmt die Planungseinrichtung vorzugsweise dann, wenn die beide Adressen gemeinsam bei der Tourenplanung zu berücksichtigen sind.

In der alternativen Ausführungsform prüft die Planungseinrichtung 105 vor der Durchführung eines Tourenplanungsprozesses, ob in der Distanzmatrix Distanzen zwischen den zu berücksichtigen Adressen gespeichert sind. Die Distanzen, die nicht enthalten sind, werden von der Planungseinrichtung 105 ergänzt und bleiben auch nach dem Tourenplanungsprozess zur Durchführung weiterer Tourenplanungsprozesse in der Speichereinheit 109 gespeichert. Die Prüfung kann insbesondere dann vorgenommen, wenn eine Adresse gemeldet wird, die bei der Tourenplanung zu berücksichtigen ist. Dabei wird ermittelt, ob Distanzen zwischen der gemeldeten Adresse und den bereits erhaltenen, bei der Tourenplanung zu berücksichtigenden Adressen in der Speichereinheit 109 hinterlegt sind. Ist dies für eine oder mehrere bereits erhaltende Adresse nicht der Fall, werden die Distanzen ergänzt. Auch bei dieser Ausführungsform werden fortlaufend Distanzen in der Distanzmatrix hinzugefügt, die nicht enthalten sind, wobei der Zuwachs stetig kleiner wird. Die Rechenleistung, die in Bezug auf die Planung einer einzelnen Tour benötigt wird, ist bei der zuvor beschriebenen alternativen Ausführungsform geringer, da weniger Distanzen bestimmt werden müssen. Werden hingegen auch Distanzen zu Adressen bestimmt, die bei der aktuellen Tourenplanung nicht zu berücksichtigen sind, insbesondere zu allen anderen in der Distanzmatrix berücksichtigten Adressen, füllt sich die Distanzmatrix rascher mit Distanzen, die später ohne weitere Berechnungen verwendet werden können.

Zur Ermittlung der Distanz zwischen einer ersten und einer zweiten in der Distanzmatrix berücksichtigten Adresse berechnet die Planungseinrichtung 105 innerhalb des Wegenetzes der geographischen Region 102 in einer Ausgestaltung eine Route von der ersten zu der zweiten Adresse. Hierzu ist eine Routenberechnungseinrichtung 106 vorgesehen. In der Routenberechnungseinrichtung 106 wird die Route derart berechnet, dass sie einem oder mehreren vorgegebenen Optimierungskriterien genügt. Insbesondere kann die schnellste oder kürzeste Route berechnet. Vorzugsweise ist das Optimierungskriterium, das bei der Routenberechnung angewandt wird, an das Optimierungskriterium angepasst, das der in der Planungseinrichtung 105 durchgeführten Tourenplanung zugrunde liegt. Insbesondere kann dasselbe Optimierungskriterium verwendet werden. Die sich aus der optimalen Route ergebende Distanz wird von der Planungseinrichtung 105 in die Distanzmatrix eingetragen.

Die berechnete optimale Routen, die der Distanzbestimmung zugrunde gelegt wird, wird in einer Ausgestaltung an die Zustellfahrzeuge 103 übertragen, die auf der Tour anhand der Routen geführt werden. Hierzu können die Routen beispielsweise in die Navigationssysteme der Zustellfahrzeuge 103 geladen werden, um die Zustellfahrzeuge anhand von Navigationshinweisen entlang der Routen zu navigieren. Gleichfalls kann jedoch auch vorgesehen sein, dass Routen zwischen den einzelnen Stopps in den Zustellfahrzeugen 103 unabhängig von der Routenbestimmung zur Ermittlung der Distanzen erfolgt. So können die Navigationseinrichtungen der Zusteller die Routen unabhängig von Vorgaben der Planungseinrichtung 105 bestimmen und/oder die Zusteller ermitteln die Routen zwischen den Stopps auf der Grundlage ihrer Ortskenntnis. Die Ermittlung der optimalen Route wird in der Planungseinrichtung 105 unter Heranziehung von gespeicherten Kartendaten des Wegenetzes des geographischen Gebiets 102 durchgeführt. Die Kartendaten können beispielsweise Wegeabschnitte des Wegenetzes enthalten, denen jeweils Distanzen zugeordnet sind oder für welche die Distanzen anhand von den Wegeabschnitten zugeordneten Daten berechnet werden können. Beispielsweise können für die Wegeabschnitte jeweils eine Länge und eine durchschnittliche Geschwindigkeit angegeben sein, woraus die Planungseinrichtung 105 eine durchschnittliche zeitliche Distanz zur Zurücklegung der Wegstrecke berechnen kann. Bei der Ermittlung einer Route von einer ersten zu einer zweiten Adresse werden einzelne Wegstücke des Wegenetzes derart miteinander verknüpft werden, dass sich eine optimale Route von der ersten zu der zweiten Adresse ergibt. Hierzu können Algorithmen verwendet werden, die dem Fachmann an sich bekannt sind.

In einer Ausgestaltung werden zudem Verkehrsinformationen herangezogen, um die Routen zu berechnen, aus denen die in die Distanzmatrix eingetragenen Distanzen bestimmt werden. Hierbei können langfristig bestehende Verkehrsbeeinträchtigungen berücksichtigt werden, wie beispielsweise Sperrungen und/oder Umleitungen, sowie vergleichsweise kurzzeitig bestehende Beeinträchtigungen, wie beispielsweise Staus. Aufgrund der genannten längerfristig bestehenden Verkehrsbeeinträchtigungen können beispielsweise bestimmte Wegstrecken bei der Routenberechnung ausgenommen werden. Die genannten kurzfristig bestehenden Verkehrsbeeinträchtigungen führen zu einer Vergrößerung der Distanz für die Fortbewegung auf den Wegstücken und werden daher bei der Distanzermittlung berücksichtigt. Beispielsweise können bei der Routenberechnung, die der Distanzermittlung zugrunde liegt, größere Distanzen für einzelne Wegstrecken verwendet werden, wenn für diese Wegstrecken ein Stau gemeldet worden ist.

Da sich die Verkehrsverhältnisse in dem Wegenetz des geographischen Gebiets 102 mit der Zeit verändern, ist vorgesehen, dass die auf der Grundlage der Verkehrsinformationen berechneten Distanzen in der Distanzmatrix aktualisiert werden. Die Aktualisierung kann beispielsweise bei einer Veränderung der Verkehrslage vorgenommen werden, die der Planungseinrichtung 105 innerhalb der Verkehrsinformationen gemeldet werden kann. In einer Ausgestaltung ist vorgesehen, dass die Distan- zen aktualisiert werden, sobald die Planungseinrichtung 105 eine Veränderung der Verkehrslage anhand der erhaltenen Verkehrsinformationen festgestellt hat. Zur Aktualisierung einer Distanz zwischen einer ersten und zweiten Adresse wird vorzugsweise eine Neuberechnung der Route zwischen den Adressen auf Grundlage der veränderten Verkehrsinformationen bzw. Verkehrslage vorgenommen.

Alternativ oder ergänzend zu der Berücksichtigung von Verkehrsinformationen und sich daraus ergebender Aktualisierungen der Distanzen in der Distanzmatrix kann vorgesehen sein, dass die Distanzen durch eine Erfassung und Auswertung der Fortbewegung der Zusteller auf den durchgeführten Touren ermittelt werden. Anhand von erfassten Positionsinformationen und erfassten Zeiten, an denen die Positionen erreicht werden kann bestimmt werden, wann der Zusteller die Stopps seiner Tour erreicht und welche zeitlichen Distanzen zwischen den Stoppadressen zurückgelegt worden sind. Sofern die Distanzwerte andere Größe repräsentieren, können zusätzliche bzw. andere Messwerte berücksichtigt werden, die bei der Durchführung der Touren erfasst werden, wie beispielsweise die zwischen den Stopps zurückgelegten Entfernungen.

Die Positionsinformationen und ggf. weitere Daten können von den Zustellern bzw. den Zustellfahrzeugen 103 an die Planungseinrichtung 105 übermittelt werden, so dass diese die Zusteller verfolgen und die zurückgelegte Route auswerten kann. Gleichfalls kann vorgesehen sein, dass die Positionen des Zustellfahrzeug 103 sowie zugehörige Zeitung und ggf. weitere Informationen in den Ortungseinheiten protokolliert und beispielsweise jeweils nach Beendigung einer Tour an die Planungseinrichtung 105 übermittelt werden.

Durch die Berücksichtigung der von dem Zustellern bzw. in den Zustellfahrzeugen 103 erfassten Daten Distanzen zwischen einer ersten und zweiten Adresse eingetragen werden, die von den Zustellern tatsächlich auf einer zurückgelegten Route von der ersten zur zweiten Adresse zurückgelegt worden sind. Hierdurch können in der Matrix sehr realistische Werte bereitgestellt werden. Wird dieselbe Route mehrmals zurückgelegt, kann es auch vorgesehen sein, Mittelwerte der tatsächlich zurückgelegten Distanzen zu berechnen und als Distanzwerte in die Distanzmatrix aufzuneh- men, um den Einfluss spezieller Gegebenheiten auf einzelnen Zustelltouren zu reduzieren.

Die Eintragung von Distanzwerten, die auf der Grundlage von tatsächlich zurückgelegten Distanzen ermittelt worden sind, erfolgt vorzugsweise durch eine Aktualisierung von in der Distanzmatrix enthaltenen, berechneten Distanzen. D.h., bevor ein Zusteller eine Route zwischen zwei Adressen zurückgelegt hat und zugehörige Positionsdaten vorliegen, wird eine berechnete Distanz in die Distanzmatrix eingetragen. Diese wird dann durch die Distanz ersetzt, die auf der Grundlage von erfassten Daten bestimmt worden ist, nachdem eine Route zwischen den Adressen von einem Zusteller zurückgelegt worden ist.

Darüber hinaus verändern sich die Distanzen zwischen den in der Distanzmatrix berücksichtigten Adressen in der Regel mit der Tageszeit und/oder dem Wochentag, wenn Verkehrsinformationen in der Distanzmatrix Berücksichtigung finden. Grund hierfür ist die üblicherweise schwankende Verkehrsdichte, die beispielsweise in der so genannten Rushhour höher ist als zu den übrigen Zeiten. Um die Schwankungen der Distanzen zu berücksichtigen, kann vorgesehen sein, dass mehrere Distanzmatrizen in der Speichereinheit 109 hinterlegt werden, die jeweils (nur) für einen bestimmten Zeitraum, insbesondere für eine bestimmte Tageszeit und/oder einen bestimmten Wochentag gültig sind. Alternativ kann es auch vorgesehen sein, dass die einzelnen Einträge der Distanzmatrix jeweils mehrere Komponenten umfassen, die jeweils für unterschiedliche Zeiträume gültig sind. In dieser Ausführungsform kann die Distanzmatrix höherdimensional mit mehr als zwei Dimensionen ausgestaltet sein. Die den verschiedenen Zeiträumen zugeordneten Distanzen sind vorzugsweise durchschnittliche Distanzen, die in den Gültigkeitszeiträumen typischerweise für die Zurücklegung der Routen zwischen den betreffenden Adressen benötigt werden. Sie können in Abhängigkeit von Verkehrsinformationen und/oder erfassten Messwerten ermittelt werden.

In einer weiteren Ausgestaltung, in der die Zusteller unterschiedliche Verkehrsmittel für die Zustellung und/oder Abholung von Postsendungen verwenden, kann vorgesehen sein, dass in der Speichereinheit 109 mehrere Distanzmatrizen gespeichert werden, die jeweils einem Verkehrsmittel zugeordnet sind, oder alternativ die Einträ- ge der Distanzmatrix mehrere Komponenten umfassen, die jeweils einem Verkehrsmittel zugeordnet sind. Diese Ausgestaltungen können auch mit den zuvor beschriebenen Ausführungsformen kombiniert werden, bei denen unterschiedliche Distanzen für verschiedene Zeiträume angegeben werden.

Sofern, wie zuvor beschrieben, mehrere Distanzwerte für eine oder mehrere Distanzen vorgesehen sind, werden alle Distanzwerte vorzugsweise ergänzt, wenn der zugehörig Ort an die Planungseinrichtung 105 gemeldet wird. Gleichfalls kann es jedoch auch vorgesehen sein, dass die Bestimmung bedarfsweise erfolgt, d.h. dann, wenn die Distanzwerte für die Tourenplanung benötigt werden.

Innerhalb der in der zuvor beschriebenen Weise berechneten Distanzmatrix stehen in der Planungseinheit 105 stets realistische Distanzen zwischen einer Vielzahl von Adressen des dem Zustelldepot 101 zugeordneten geographischen Gebiets 102 für die Tourenplanung zur Verfügung. Die Distanzen müssen nicht bei jedem Tourenpla- nungsprozess neu berechnet werden, wodurch die Tourenplanung beschleunigt werden kann.

Zudem stehen die benötigten Distanzen auch dann zur Verfügung, wenn eine rasche Neuplanung einer oder mehrerer Touren vorgenommen werden soll.

Eine solche Neuplanung kann beispielsweise vorgesehen sein, um Abholaufträge, die nach dem Beginn einer Zustelltour in der Planungseinrichtung 105 eingehen, in die Zustelltour zu integrieren. Wenn die Adresse des Abholauftrags zuvor nicht in der Distanzmatrix berücksichtigt war, müssen für die Neuplanung der Tour lediglich die Distanzen zwischen dieser Adresse und den übrigen, in der Distanzmatrix berücksichtigten, Adressen bestimmt werden. Falls die Adresse bereits in der Distanzmatrix berücksichtigt war, ist überhaupt keine Distanzberechnung erforderlich, um die Neuplanung der Zustelltour vornehmen zu können.

Obwohl die Erfindung in den Zeichnungen und der vorausgegangenen Darstellung im Detail beschrieben wurde, sind die Darstellungen illustrativ bzw. beispielhaft und nicht einschränkend zu verstehen; insbesondere ist die Erfindung nicht auf die erläuterten Ausführungsbeispiele beschränkt. Weitere Varianten der Erfindung und ihre Ausführung ergeben sich für den Fachmann aus der vorangegangenen Offenbarung, den Figuren und den Patentansprüchen.

In den Patentansprüchen verwendete Begriffe wie "umfassen", "aufweisen", "beinhalten", "enthalten" und dergleichen schließen weitere Elemente oder Schritte nicht aus. Die Verwendung des unbestimmten Artikels schließt eine Mehrzahl nicht aus. Eine einzelne Einrichtung kann die Funktionen mehrerer in den Patentansprüchen genannter Einheiten beziehungsweise Einrichtungen ausführen. In den Patentansprüchen angegebene Bezugszeichen sind nicht als Beschränkungen der eingesetzten Mittel und Schritte anzusehen.