Beschreibung
Verfahren und Anordnung zur Ermittlung einer Route von einem Startpunkt zu einem Zielpunkt
Die Erfindung betrifft die Ermittlung einer Route von einem Startpunkt zu einem Zielpunkt.
In rechnergestützten Routenplanungssystemen gilt es, zwischen einem vorgebbaren Startpunkt, d.h. einem Ausgangsort, an dem ein Benutzer des RoutenplanungsSystems eine Reise beginnen möchte und einem Zielpunkt, zu dem der Benutzer reisen möchte, eine Route zu ermitteln in einer Weise, daß sowohl die Ermittlung der Route selbst möglichst schnell erfolgt und die Route hinsichtlich verschiedener, vorgebbarer Anforderungen optimiert ist.
Anforderungen in diesem Sinne können beispielsweise sein eine für die gesamte Route benötigte Reisezeit, die Routenlänge oder auch bestimmte Vorgaben, daß bestimmte Verkehrsmittel bevorzugt benutzt werden sollen.
Unter einer Route ist im weiteren eine Wegbeschreibung, d.h. eine Menge von Knoten und Kanten, wenn der Weg durch einen Graphen repräsentiert wird, der Knoten und Kanten aufweist, von einem Startpunkt zu einem Zielpunkt, zu verstehen.
Die Ermittlung der Route soll möglichst schnell und flexibel durchgeführt werden.
Eine Übersicht über Verfahren zur Ermittlung kürzester Pfade ist in [1] zu finden.
Das Problem wird durch das Verfahren gemäß Patentanspruch 1 sowie durch die Anordnung gemäß Patentanspruch 9 gelöst.
Die Route wird von einem Startpunkt zu einem Zielpunkt in einem iterativen Verfahren ermittelt. Der Startpunkt und der Zielpunkt liegen in unterschiedlichen Teilroutenkarten, wobei die Teilroutenkarten in digitaler Form gespeichert sind. Das Verfahren umfaßt folgende Schritte :
- Teilmodulen, die jeweils einer Teilroutenkarte zugeordnet sind, werden digitale Nachrichten zugeführt, die jeweils mindestens einen Teilstartpunkt und mindestens einen Teilzielpunkt enthalten, die in der Teilroutenkarte des Teilmoduls liegen, das die jeweilige Nachricht empfängt;
- von jedem Teilmodul wird mindestens eine Teilroute zwischen dem jeweiligen Teilstartpunkt und dem Teilzielpunkt ermittelt;
- aus den Teilrouten wird die Route gebildet.
Die Anordnung weist eine Prozessoreinheit auf, die derart eingerichtet ist, daß in einem iterativen Verfahren eine Route von einem Startpunkt zu einem Zielpunkt, die jeweils in unterschiedlichen Teilroutenkarten liegen, ermittelt wird, wobei die Teilroutenkarten in digitaler Form gespeichert sind. Das Verfahren umfaßt folgende Schritte:
- Teilmodulen, die jeweils einer Teilroutenkarte zugeordnet sind, werden digitale Nachrichten zugeführt, die jeweils mindestens einen Teilstartpunkt und mindestens einen Teilziel- punkt enthalten, die in der Teilroutenkarte des Teilmoduls liegen, das die jeweilige Nachricht empfängt;
- von jedem Teilmodul wird mindestens eine Teilroute zwischen dem jeweiligen Teilstartpunkt und dem Teilzielpunkt ermittelt; - aus den Teilrouten wird die Route gebildet.
Durch die Erfindung wird eine schnelle, flexible Ermittlung einer Route für einen Benutzer von einem vorgebbaren Startpunkt zu einem vorgebbaren Zielpunkt (zu einem vorgebbaren Zeitpunkt) gewährleistet. Dabei wird das äußerst komplexe Problem der Routenermittlung in Teilprobleme aufgespaltet, welches jeweils unabhängig voneinander gelöst wird, wodurch
es möglich wird, sowohl zentrales als auch lokales Wissen in Nebenbedingungen der Ermittlung von Teilrouten bzw . der Route zu berücksichtigen .
Weiterbildungen der Erfindung ergeben sich aus den abhängigen Ansprüchen .
Es ist in einer Weiterbildung vorteilhaft , daß die Teilroutenkarten in Form von Teilroutengraphen mit Knoten und Kanten gespeichert sind und zur Ermittlung der Teilroute j eweils ein Verfahren zur Ermittlung kürzester Pfade eingesetzt wird .
Durch Einsatz der Verfahrensermittlung kürzester Pfade ist es in den einzelnen Teilmodulen auf einfache Weise möglich, op- timierte Teilrouten hinsichtlich der vorgebbaren Optimierungskriterien zu bilden . Der Einsatz von Verfahren zur Ermittlung kürzester Pfade ist derart zu verstehen, daß jeweils eine Teilroute hinsichtlich einer vorgegebenen Kostenfunktion (Optimierungskriterien) optimiert ermittelt wird . Den Kanten sind jeweils Kostenwerte zugeordnet , die dem vorgegebenen Optimierungskriterium entsprechen .
Vorgebbare Optimierungskriterien können neben der Weglänge oder der Dauer einer Route beispielsweise auch die Minimie- rung von Abbiegevorgängen, insbesondere von Linksabbiege orgängen in Städten sein .
Ferner kann der Zeitpunkt , für den die Route geplant werden soll , bei der Erf indung berücksichtigt werden . So kann beispielsweise die Zeit der Rei- se durchaus von Bedeutung sein, da die Entscheidung, für die Route den
Individualverkehr oder den öffentlichen Verkehr zu wählen, vom gewählten Zeitpunkt abhängen kann (während der Berufsverkehrszeit wird man von in einer Innenstadt mit dem Auto vermutlich länger brauchen, als unter Verwendung des öffentlichen Verkehrs ; nachts mag die Situation umgekehrt sein) .
Ein Ausführungsbeispiel der Erfindung ist in den Figuren dargestellt und wird im weiteren näher erläutert.
Es zeigen
Figur 1 ein Blockdiagramm, in dem die Anordnung sowie der Austausch von Nachrichten zwischen den Software- Agenten beschrieben ist;
Figur 2 eine Skizze von mehreren Teilroutenkarten, anhand welcher Skizze die Erfindung beschrieben wird.
Eine Anordnung 101 zur Ermittlung einer Route aufgrund einer Benutzeranfrage 102, die der Anordnung 101 zugeführt wird, weist folgende Komponenten auf:
Mehrere Software-Agenten. Unter einem Software-Agenten ist ein Programm für eine Datenverarbeitungsanlage zu verstehen, das aufgrund interner Zielvorgaben in der Lage ist, ohne weitere Beeinflussung von außen seine ihm gestellte Aufgabe ei- genständig zu lösen. Im weiteren wird ein Software-Agent als Agent bezeichnet.
In einem zentralen Agenten wird die Ermittlung von Routen durchgeführt und koordiniert.
In diesem Ausführungsbeispiel wird davon ausgegangen, daß in der Anordnung 101 verschiedene Landkarten und Verkehrsnetze in Form eines Graphen mit Knoten und Kanten gespeichert sind. Unter einem Verkehrsnetz ist beispielsweise ein Schienennetz zu verstehen.
Den Verkehrsnetzen zugeordnet können beispielsweise Fahrpläne eines öffentlichen Verkehrsnetzes sein. Diese sind ebenfalls in digitaler Form gespeichert .
In der Anordnung 101 sind mehrere Teilmodule vorgesehen. Jedem Teilmodul ist eine Teilroutenkarte zugeordnet. Eine Teil-
routenkarte ist beispielsweise ein Verkehrsnetz, das mindestens einen Teil des gesamten, durch die Anordnung berücksichtigten geographischen Gebiets umfaßt.
Die Teilroutenkarten können unterschiedliche geographische Gebiete, oder auch sich überschneidende geographische Gebiete enthalten, wobei in diesem Fall unterschiedliche Verkehrsnetze (Straßenbahnnetz, Busnetz, Eisenbahnnetz) in den Teilroutenkarten enthalten sein können.
Jedes Teilmodul, das durch einen Software-Agenten realisiert ist, ist derart eingerichtet, daß unter Verwendung von Verfahren zur Ermittlung kürzester Pfade in der Teilroutenkarte, die dem jeweiligen Teilmodul zugeordnet ist, mindestens eine Teilroute ermittelt wird. Ergebnis der Teilroute sind jeweils ein Teilzielpunkt und ein Teilstartpunkt, die am Rand der Teilroutenkarte liegen, sowie die Route innerhalb der Teilroutenkarte, die von dem Teilstartpunkt zu dem Teilzielpunkt führt .
Das Verfahren zur Ermittlung der Route aus den Teilrouten wird im weiteren detailliert beschrieben.
Es wird im weiteren davon ausgegangen, daß ein erstes Teilmo- dul Us einer ersten Teilroutenkarte TUg zugeordnet ist, das ein Straßennetz für den Individualverkehr in der Stadt München enthält .
Unter Individualverkehr ist im weiteren der Verkehr unter Verwendung von Kraftfahrzeugen oder auch Fahrrädern zu verstehen.
Ein zweites Teilmodul Uy ist einer zweiten Teilroutenkarte TUV zugeordnet, die in Form eines Graphen digital gespeichert das Straßennetz der Bayerischen Autobahnen und Fernstraßen enthält .
Ein drittes Teilmodul Up_ ist einer dritten Teilroutenkarte TUp zugeordnet, die ein Straßennetz für den Individualverkehr des Großraums Nürnberg-Erlangen-Fürth beschreibt.
Ein viertes Teilmodul Ug ist einer vierten Teilroutenkarte TUE zugeordnet, die ein Netz enthält, in dem der gesamte öffentliche Verkehr (Bus, Straßenbahn, Schienenverkehr) in dem Bundesland Bayern gespeichert ist .
Es gilt nun, aufgrund der Benutzeranfrage 102, die einen
Startpunkt S und einen Zielpunkt Z (sowie optional Abfahrtsoder Ankunftszeitpunkt) enthält, eine möglichst optimierte Route, d.h. eine Menge zusammenhängender Knoten und Kanten von dem Startpunkt S zu dem Zielpunkt Z, zu ermitteln, wobei die Nutzung unterschiedlicher Verkehrsmittel möglich ist.
In dem Ausführungsbeispiel ist in der Benutzeranfrage 102 angegeben, daß der Benutzer eine Reise vom Otto-Hahn-Ring 6 in München (Startpunkt S) nach Nürnberg, Flaschenhofstr. 55 (Zielpunkt Z) am Montag, den 06. Oktober 1997, machen möchte. Der Benutzer muß spätestens um 10.00 Uhr am Zielpunkt Z eingetroffen sein (Nebenbedingung für die Routenermittlung) . Einschränkungen bei der Wahl des Verkehrsmittels gibt es in diesem Ausführungsbeispiel nicht. Das Optimierungskriterium ist die für die Reise benötigte Zeit.
In einem ersten Schritt wird von einem zentralen Agenten I für den Startpunkt S und den Zielpunkt Z eine Menge von Agenten, d.h. Teilmodulen Ug, Uv, UR, Ug, ermittelt, die für die Ermittlung einer Route zwischen dem Startpunkt S und dem Zielpunkt Z in Frage kommen.
Hierfür übersendet der zentrale Agent I an alle ihm bekannten Teilmodule U-^ (i = 1 ... m, m = Anzahl der Teilmodule Uj_) ei- ne erste Nachricht 1. In der ersten Nachricht 1 ist eine Anfrage enthalten, ob der Startpunkt S und/oder der Zielpunkt Z
in der Teilroutenkarte TUg, TUy, TUR, TUE des jeweiligen Teilmoduls Us, Uy, UR, UE enthalten ist.
Alle Teilmodule Ug, Uy, UR, UE senden an den zentralen Agen- ten I eine zweite Nachricht 2, in der eine Antwort enthalten ist, d.h. eine positive oder eine negative Nachricht, zurück.
Dem ersten Teilmodul Ug und dem vierten Teilmodul UE ist der Startpunkt S bekannt, d.h. der Startpunkt S liegt in ihrer jeweiligen Teilroutenkarte TUS, TUE .
Dem dritten Teilmodul UR und dem vierten Teilmodul UE ist der Zielpunkt Z bekannt, d.h. der Zielpunkt Z liegt in ihrer jeweiligen Teilroutenkarte TUR, TUE .
Die zweite Nachricht 2 von dem ersten Teilmodul Ug, dem dritten Teilmodul U sowie dem vierten Teilmodul U , die jeweils zu dem zentralen Agenten I übertragen werden, enthalten die Information, daß das jeweilige Teilmodul Ug, UR, UE bei der Ermittlung der Route involviert ist.
Das zweite Teilmodul Uy enthält in der ihm zugeordneten Teilroutenkarte weder den Startpunkt S noch den Zielpunkt Z. Somit sendet das zweite Teilmodul Uy sowie weitere Teilmodule Uj_ (nicht dargestellt) , die in der Anordnung enthalten sind, eine zweite Nachricht 2 zurück, in der angegeben ist, daß sowohl der Startpunkt S als auch der Zielpunkt Z dem Teilmodul Uy, Uj_ unbekannt sind, d.h. nicht in ihrer jeweiligen Teilroutenkarte TUy, TUj_ liegen.
In der zweiten Nachricht 2 ist für den Fall, daß der Startpunkt S oder der Zielpunkt Z in der jeweiligen Teilroutenkarte enthalten ist, eine Identifikationsangabe enthalten, mit der der Startpunkt S bzw. der Zielpunkt Z in der Teilrouten- karte eindeutig identifiziert werden kann. In diesem Beispiel
sind mehrere Teilmodule Ug, UR, UE jeweils für den Startpunkt
S bzw. Zielpunkt Z "zuständig", da es sich bei dem ersten Teilmodul Ug und dem dritten Teilmodul UR um Teilmodule zur Ermittlung von Routen für den Individualverkehr handelt, wäh- rend das vierte Teilmodul UE Routen für den öffentlichen Verkehr ermittelt .
In einem weiteren Schritt wird von dem zentralen Agenten I eine Menge von Folgen ermittelt, in denen angegeben ist, wel- ehe Folgen von Teilmodulen Us, UR, UE , Uy bei der Ermittlung der Route ausgehend von dem Startpunkt S zu dem Zielpunkt Z in Frage kommen. Hierzu wird eine lokale Wissensbasis KBj in Form einer Datenbank verwendet, die dem zentralen Agenten I zugänglich ist. In der Wissensbasis sind für jede Kombination von Teilmodulen, in denen ein Start- oder Zielpunkt liegen kann, Folgen von Teilmodulen gespeichert, deren Teilrouten nacheinander verwendet werden, um vom Startpunkt S zum Zielpunkt Z zu gelangen.
Auf Anfrage des zentralen Agenten I wird von der lokalen Wissensbasis KBj eine dritte Nachricht 3 an den zentralen Agenten I gesendet, der die ermittelten Sequenzen enthält, in diesem Fall :
1. Us → Uy → UR
2. Ug → Uy → UE
3. Ug → UR → UE
4. Ug → UE
5. UE
Diese Sequenzen sind wie im folgenden für den Fall 1
(Ug -> Uy - U ) beschrieben, zu verstehen. Die Route kann
als Sequenz der Teilroutenkarte TUg des ersten Teilmoduls Ug, gefolgt von einer Teilroute der Teilroutenkarte TUy des zweiten Teilmoduls Uy und abschließend einer Teilroute der Teilroutenkarte TUR des dritten Teilmoduls U gebildet werden.
Entsprechendes gilt für die weiteren oben dargestellten Fälle 2 bis 5.
In einem weiteren Schritt werden Teilstartpunkte und Teil- Zielpunkte der Teilrouten, die von dem ersten Teilmodul Ug, dem zweiten Teilmoduls Uy und dem dritten Teilmoduls UR gebildet werden, ermittelt. Anschaulich bedeutet dies, daß mögliche Übergangspunkte ÜSy, Üyj^ zwischen Teilroutenkarten TUg, TUy, TUR, die den einzelnen Teilmodulen Ug, Uy, UR, zugeord- net sind, ermittelt werden.
In der Wissensbasis KBj des zentralen Agenten I ist eine Liste aller theoretisch möglichen Teilzielpunkte und Teilstartpunkte, die im weiteren als Übergangspunkte Ügy, ÜyR bezeich- net werden, für die jeweiligen Teilroutenkarten TUg, TUy, TUR gespeichert. Aus der Menge aller möglichen Übergangspunkte Ügy, ÜyR wird eine möglichst kleine Anzahl von Teilstartpunkten und Teilzielpunkten ausgewählt, um somit die Anzahl der zu ermittelnden Teilrouten so gering wie möglich zu halten.
Die Auswahl erfolgt unter Berücksichtigung lokalen Wissens, welches in einer Heuristik zur Ermittlung von Übergangspunkten Ügy, ÜyR einfließt.
Gemäß der Heuristik wird bei einer Gesamtentfernung von dem Startpunkt S zu dem Zielpunkt Z von über 100 km (die Luftlinienentfernung von München nach Nürnberg ist größer als 100 km) , versucht, einen möglichst großen Anteil der Route unter Verwendung von Autobahnen abzudecken. Dies bedeutet, daß der zentrale Agent I in seiner Wissensbasis KB nach Übergangs- punkte Ügy, Üy sucht, die einen Teil einer Autobahn repräsentieren, d.h. z.B. einen Autobahnanschluß repräsentieren.
Anschaulich bedeutet dies, daß zwischen der ersten Teilroutenkarte TUg und der zweiten Teilroutenkarte TUy bzw. der zweiten Teilroutenkarte TUy und der dritten Teilroutenkarte TUR Übergangspunkte ermittelt werden, deren Knoten Orte repräsentieren, die in einer Autobahn enthalten sind oder direkt zu einer Autobahn führen.
In einer vierten Nachricht 4 wird der Wissensbasis KB des zentralen Agenten I die Anforderung zur Ermittlung der Übergangspunkte Ügy, ÜyR übergeben.
Von der Wissensbasis KB wird in einer fünften Nachricht 5 das Ergebnis, d.h. eine Menge von Übergangspunkten Ügy zwi- sehen den Teilroutenkarten TUg, TUy des ersten Teilmoduls Ug und des zweiten Teilmoduls Uy und eine Menge von Übergangs- punkte Üy£ zwischen Teilroutenkarten TUy, TUR des zweiten Teilmoduls Uy und des dritten Teilmoduls U zurückgesendet. Die Übergangspunkte Ügy, ÜyR sind in Figur 2 durch Punkte ge- kennzeichnet.
Eine Menge von Übergangspunkte ÜXγ (X,Y e N) zwischen Teilroutenkarten besteht im Fall des Übergangs von einem Netz für den Individualverkehr zu einem Netz für den öffentlichen Ver- kehr, in diesem Fall U —• UE, Uy —► UE und UR —» UE aus einer Menge von Parkplätzen für Kraftfahrzeuge, die sich in der Nähe einer Station für ein öffentliches Verkehrsmittel befinden.
Im Fall des Übergangs von einem Netz für den öffentlichen
Verkehr und einem Netz für den Individualverkehr besteht die Liste aus Taxiständen.
Im Fall des Übergangs von einem Netz für den Individualver- kehr zu einem angrenzenden weiteren Netz für den Individualverkehr besteht die Liste aus vorgegebenen Punkten, an denen
jeweils eine Straße von einem Netz zu dem anderen Netz übergeht .
In einer sechsten Nachricht 6, die von dem zentralen Agen- ten I an das erste Teilmodul Ug, das zweite Teilmodul Uy und das dritte Teilmodul UR gesendet werden, wird bei den Teilmodulen Ug, Uy, UR angefragt, ob es durch Berücksichtigung lokaler Rahmenbedingungen, die jeweils in einer lokalen Wissensbasis KBg, KBy, KBR, die eindeutig dem jeweiligen Teilmo- dul Ug, Uy, UR zugeordnet ist, andere Übergangspunkte Ügy, ÜyR gibt, die sich hinsichtlich des vorgegebenen Optimierungskriteriums eignen.
Ein solches lokales Wissen ist darin zu sehen, daß dem ersten Teilmodul Ug unter Verwendung seiner ihm zugeordneten lokalen Wissensbasis KBg bekannt ist, daß - aufgrund von Heuristiken und domänenspezifischem Wissen aus der lokalen Wissensbasis KBg - für eine längere Reise Richtung Norden von dem vorgegebenen Startpunkt S, der sich relativ weit im Süden Münchens befindet, Übergangspunkte Ügy im Südosten und im Norden der ersten Teilroutenkarte TUg zu berücksichtigen sind.
In der lokalen Wissensbasis KBy, die dem zweiten Teilmodul Uy zugeordnet ist, ist angegeben, daß für eine Reise von München nach Nürnberg die Übergangspunkte Üyp_ der zweiten Teilroutenkarte TUy des zweiten Teilmoduls Uy vorteilhaft sind, die im Norden der zweiten Teilroutenkarte TUy liegen.
Aus den zusätzlichen Vorschlägen, die von den einzelnen Teil- modulen Ug, Uy, UR dem zentralen Agenten I zugeführt werden, wird von dem zentralen Agenten I eine Teilmenge TÜgy für Übergänge von der ersten Teilroutenkarte TUg und der zweiten Teilroutenkarte TUy. Analog wird für die Übergangspunkte Ü ^, die Übergänge zwischen der zweiten Teilroutenkarte TUy und der dritten Teilroutenkarte TU repräsentieren, eine zweite Teilmenge TÜyj^ von Übergangspunkten Ü^ ermittelt.
Eine siebte Nachricht 7 wird von dem zentralen Agenten I an das erste Teilmodul Ug, das zweite Teilmodul Uy und das dritte Teilmodul UR gesendet. Die siebte Nachricht 7 enthält jeweils eine Anfrage zur Ermittlung einer oder mehrerer Teil- routen, die hinsichtlich des vorgegebenen Optimierungskriteriums Zeit optimal sind.
In diesem Beispiel wird in der siebten Nachricht 7, die dem ersten Teilmodul Ug zugeführt wird, die Ermittlung von Teil- routen von dem Startpunkt S zu den fünf Übergangspunkten Ügy der ersten Teilmenge TÜgy, angefragt.
Die siebte Nachricht 7, die dem zweiten Teilmodul Uy zugeführt wird, enthält eine Anfrage zur Ermittlung von Teilrou- ten aller Kombinationen zwischen den Übergangspunkten Ügy der ersten Teilmenge TÜgy und den Übergangspunkten Üyj^ der zweiten Teilmenge Üyj^.
Die siebte Nachricht 7, die dem dritten Teilmodul UR zuge- führt wird, enthält eine Anfrage zur Ermittlung von Teilrouten von den zwei Übergangspunkten Üy^ der zweiten Teilmenge TÜy zum Zielpunkt Z.
Die Gesamtzahl der zu ermittelnden Teilrouten beträgt bei dieser Vorgehensweise 5 + 10 + 2 = 17. Bei Ermittlung aller möglichen Teilrouten für alle in Frage kommenden Übergangs- punkte Üyg, Üyj^ der Teilroutenkarten wäre im vorliegenden Fall eine Größenordnung von 2000 bis 3000 Ermittlungen erforderlich (ausgehend von einer Gesamtzahl möglicher Übergangs- punkte in der Größenordnung von 50) .
Die Ermittlung der Teilrouten in den Teilmodulen erfolgt unter Verwendung von Verfahren zur Ermittlung kürzester Pfade, beispielsweise dem Verfahren nach Dijkstra. Den jeweiligen Knoten und/oder Kanten der Teilroutenkarte sind jeweils Kostenwerte zugeordnet, die im Rahmen der Optimierung zur Ermittlung der Teilroute innerhalb der Teilroutenkarte in einer
Kostenfunktion berücksichtigt werden. Die Kostenwerte und die Art der Berücksichtigung hängen ab von der Art des Optimierungskriteriums. Mögliche Optimierungskriterien sind die für die Reise insgesamt benötigte Zeit, die zu minimierende gesamte Routenlänge, oder weiteren Rahmenbedingungen. So wird für den Fall, daß ein bestimmtes Verkehrsmittel nicht verwendet werden soll, das jeweilige Teilmodul, das für das Verkehrsmittel „zuständig" ist, nicht mit der Berechnung einer Teilroute beauftragt.
Nachdem alle Teilrouten von den Teilmodulen dem zentralen Agenten I zugeführt wurden, wird von dem zentralen Agenten I eine Route ermittelt, wobei die Route eine Menge zusammenhängender Knoten und Kanten, ausgehend von dem Startpunkt S hin zu dem Zielknoten Z, ist. Die hinsichtlich des Optimierungskriteriums „Zeit" beste Route wird von dem zentralen Agenten I ausgewählt .
Das für die erste Sequenz Ug —» Uy —>• UR oben beschriebene Verfahren wird für alle weiteren Sequenzen entsprechend durchgeführt .
Es ist jedoch zu beachten, daß bei Übergängen zwischen einem Netz für den Individualverkehr und einem Netz für den öffent- liehen Verkehr jeweils noch Übergangszeiten für den Wechsel des Verkehrsmittels und diskrete Abfahrtszeiten des jeweiligen öffentlichen Verkehrsmittels zu berücksichtigen sind. Dies ist bei dem Übergang zwischen Netzen für den Individualverkehr nicht erforderlich.
Als Route wird im Gesamtergebnis diejenige ausgewählt, die hinsichtlich des Optimierungskriteriums optimiert ist.
Die ausgewählte Route wird dem Benutzer als Antwort 103 sei- ner Benutzeranfrage 102 als Ergebnis zur Verfügung gestellt, beispielsweise auf einem Bildschirm angezeigt oder in anderer Form ausgegeben.
Im weiteren werden einige Alternativen zu dem oben beschriebenen Ausführungsbeispiel aufgezeigt.
In dem Ausführungsbeispiel sind dem zentralen Agenten I alle erheblichen Teilmodule, die für die Ermittlung der Route erforderlich sind, bekannt. In einer Variante ist jedoch vorgesehen, daß die Information über erforderliche Teilmodule in weiteren Agenten gespeichert ist. Die Information wird dann von dem zentralen Agenten I abgefragt.
In einer Variante der Erfindung ist es ferner vorgesehen, daß die möglichen Folgen von Teilroutenkarten nicht in der Wissensbasis KB des zentralen Agenten I, sondern in einem wei- teren Agenten gespeichert ist. In diesem Fall würde auch diese Information von dem weiteren Agenten durch den zentralen Agenten I abgefragt .
Für die Sequenzen 2 bis 5 kann in einer Variante der Fall eintreten, daß der letzte Abschnitt der Reise mit einem Taxi zurückgelegt wird. Dies bedeutet, daß die Folge um das weitere Teilmodul U (Ergänzung der Folgen um das Postfix „-» UR") ergänzt werden müßte, da zwar das letzte Teilmodul U nicht den genauen Weg zu dem Zielpunkt Z, jedoch die für das letzte Teilstück benötigte Zeit ermitteln müßte.
Im Rahmen dieses Dokuments wurden folgende Veröffentlichungen zitiert :
[1] B. V. Cherkassky et al , Shortest Path Algorithms, Theory and Experimental Evaluation Mathematical Programming, Vol. 73, Nr. 2, S. 129 - 174, 1996