In rechnergestutzten Routenplanungssystemen gilt es, zwischen einem vorgebbaren Startpunkt, d. h. einem Ausgangsort, an dem ein Benutzer des Routenplanungssystems eine Reise beginnen moche und einem Zielpunkt, zu dem der Benutzer reisen mach- te, 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 far 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 ei- nem 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 zugefuhrt, die jeweils min- destens 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 ermit- telt; -aus den Teilrouten wird die Route gebildet.

Die Anordnung weist eine Prozessoreinheit auf, die derart eingerichtet ist, daß in einem iterativen Verfahren eine Rou- te 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 min- destens 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 ermit- telt; -aus den Teilrouten wird die Route gebildet.

Durch die Erfindung wird eine schnelle, flexible Ermittlung einer Route far einen Benutzer von einem vorgebbaren Start- punkt 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 Teilrou- tenkarten in Form von Teilroutengraphen mit Knoten und Kanten gespeichert sind und zur Ermittlung der Teilroute jeweils 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 Optimie- rungskriterien zu bilden. Der Einsatz von Verfahren zur Er- mittlung 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 Op- timierungskriterium entsprechen.

Vorgebbare Optimierungskriterien können neben der Wegldnge oder der Dauer einer Route beispielsweise auch die Minimie- rung von Abbiegevorgangen, insbesondere von Linksabbiegevor- gangen in Städten sein.

Ferner kann der Zeitpunkt, fUr den die Route geplant werden soll, bei der Erfindung berucksichtigt werden. So kann beispielsweise die Zeit der Rei- se durchaus von Bedeutung sein, da die Entscheidung, fUr die Route den Individualverkehr oder den öffentlichen Verkehr zu wahlen, vom gewählten Zeitpunkt abhangen kann (wahrend der Berufsverkehrszeit wird man von in einer Innenstadt mit dem Auto vermutlich langer brauchen, als unter Ver- wendung des öffentlichen Verkehrs ; nachts mag die Situation umgekehrt sein).

Ein Ausführungsbeispiel der Erfindung ist in den Figuren dar- gestellt 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 far eine Datenverarbeitungsanlage zu verstehen, das aufgrund interner Zielvorgaben in der Lage ist, ohne wei- tere 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 Fahrplane eines öffentlichen Verkehrsnetzes sein. Diese sind ebenfalls in digitaler Form gespeichert.

In der Anordnung 101 sind mehrere Teilmodule vorgesehen. Je- dem Teilmodul ist eine Teilroutenkarte zugeordnet. Eine Teil-

routenkarte ist beispielsweise ein Verkehrsnetz, das minde- stens einen Teil des gesamten, durch die Anordnung berück- sichtigten geographischen Gebiets umfaßt.

Die Teilroutenkarten können unterschiedliche geographische Gebiete, oder auch sich überschneidende geographische Gebiete enthalten, wobei in diesem Fall unterschiedliche Verkehrsnet- ze (Straßenbahnnetz, Busnetz, Eisenbahnnetz) in den Teilrou- tenkarten enthalten sein können.

Jedes Teilmodul, das durch einen Software-Agenten realisiert ist, ist derart eingerichtet, daß unter Verwendung von Ver- fahren 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 Teil- routenkarte, 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 TUS zugeordnet ist, das ein Straßennetz für den Individualverkehr in der Stadt Muon- chen enthalt.

Unter Individualverkehr ist im weiteren der Verkehr unter Verwendung von Kraftfahrzeugen oder auch Fahrrädern zu ver- stehen.

Ein zweites Teilmodul UV 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 UR ist einer dritten Teilroutenkarte TUR zugeordnet, die ein Straßennetz für den Individualverkehr des beschreibt.Nürnberg-Erlangen-Fürth Ein viertes Teilmodul UE ist einer vierten Teilroutenkarte TUE zugeordnet, die ein Netz enthält, in dem der gesamte öf- fentliche 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 Abfahrts- oder Ankunftszeitpunkt) enthalt, eine möglichst optimierte Route, d. h. eine Menge zusammenhangender 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 an- gegeben, 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 moche.

Der Benutzer muß spätestens um 10.00 Uhr am Zielpunkt Z ein- getroffen sein (Nebenbedingung far die Routenermittlung).

Einschränkungen bei der Wahl des Verkehrsmittels gibt es in diesem Ausführungsbeispiel nicht. Das Optimierungskriterium ist die far die Reise benötigte Zeit.

In einem ersten Schritt wird von einem zentralen Agenten I far den Startpunkt S und den Zielpunkt Z eine Menge von Agen- ten, d. h. Teilmodulen Us, Uv, UR, UE, ermittelt, die far die Ermittlung einer Route zwischen dem Startpunkt S und dem Zielpunkt Z in Frage kommen.

Hierfur ubersendet der zentrale Agent I an alle ihm bekannten Teilmodule Ui (i = 1... m, m = Anzahl der Teilmodule Ui) ei- ne erste Nachricht 1. In der ersten Nachricht 1 ist eine An- frage enthalten, ob der Startpunkt S und/oder der Zielpunkt Z

in der Teilroutenkarte TUs, TUv, TUR, TUE des jeweiligen Teilmoduls Us, Uv, UR, UE enthalten ist.

Alle Teilmodule Us, Uv, 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, zuruck.

Dem ersten Teilmodul US 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 je- weiligen Teilroutenkarte TUR, TUE.

Die zweite Nachricht 2 von dem ersten Teilmodul Us, dem drit- ten Teilmodul UR sowie dem vierten Teilmodul UE, die jeweils zu dem zentralen Agenten I übertragen werden, enthalten die Information, daß das jeweilige Teilmodul US, UR, UE bei der Ermittlung der Route involviert ist.

Das zweite Teilmodul UV enthält in der ihm zugeordneten Teil- routenkarte weder den Startpunkt S noch den Zielpunkt Z. So- mit sendet das zweite Teilmodul UV sowie weitere Teilmodule Ui (nicht dargestellt), die in der Anordnung enthalten sind, eine zweite Nachricht 2 zuruck, in der angegeben ist, daß so- wohl der Startpunkt S als auch der Zielpunkt Z dem Teilmodul UV, Ui unbekannt sind, d. h. nicht in ihrer jeweiligen Teil- routenkarte TUV, TUi liegen.

In der zweiten Nachricht 2 ist für den Fall, daß der Start- punkt S oder der Zielpunkt Z in der jeweiligen Teilroutenkar- te 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 US, UR, UE jeweils far den Startpunkt S bzw. Zielpunkt Z"zuständig", da es sich bei dem ersten Teilmodul Us und dem dritten Teilmodul UR um Teilmodule zur Ermittlung von Routen far den Individualverkehr handelt, wäh- rend das vierte Teilmodul UE Routen far den öffentlichen Ver- kehr ermittelt.

In einem weiteren Schritt wird von dem zentralen Agenten I eine Menge von Folgen ermittelt, in denen angegeben ist, wel- che Folgen von Teilmodulen Us, UR, UE, Uv bei der Ermittlung der Route ausgehend von dem Startpunkt S zu dem Zielpunkt Z in Frage kommen. Hierzu wird eine lokale Wissensbasis KBI in Form einer Datenbank verwendet, die dem zentralen Agenten I zugänglich ist. In der Wissensbasis sind far 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 Ziel- punkt Z zu gelangen.

Auf Anfrage des zentralen Agenten I wird von der lokalen Wis- sensbasis KBI eine dritte Nachricht 3 an den zentralen Agen- ten I gesendet, der die ermittelten Sequenzen enthält, in diesem Fall : 1. US UV UR 2. US UV UE <BR> <BR> <BR> <BR> <BR> <BR> 3. UR#UE# <BR> <BR> <BR> <BR> <BR> <BR> <BR> <BR> 4. Ug Ug<BR> <BR> <BR> <BR> <BR> <BR> <BR> <BR> <BR> 5. UE Diese Sequenzen sind wie im folgenden far den Fall 1 (US UV- UR) beschrieben, zu verstehen. Die Route kann

als Sequenz der Teilroutenkarte TUS des ersten Teilmoduls Us, gefolgt von einer Teilroute der Teilroutenkarte TUV des zwei- ten Teilmoduls UV und abschließend einer Teilroute der Teil- routenkarte TUR des dritten Teilmoduls UR gebildet werden.

Entsprechendes gilt far die weiteren oben dargestellten Falle 2 bis 5.

In einem weiteren Schritt werden Teilstartpunkte und Teil- zielpunkte der Teilrouten, die von dem ersten Teilmodul Us, dem zweiten Teilmoduls UV und dem dritten Teilmoduls UR ge- bildet werden, ermittelt. Anschaulich bedeutet dies, daß mög- liche Übergangspunkte Üsv, ÜvR zwischen Teilroutenkarten TUS, TUV, TUR, die den einzelnen Teilmodulen US, UV, UR, zugeord- net sind, ermittelt werden.

In der Wissensbasis KBI des zentralen Agenten I ist eine Li- ste aller theoretisch möglichen Teilzielpunkte und Teilstart- punkte, die im weiteren als Ubergangspunkte UgV, UVR bezeich- net werden, far die jeweiligen Teilroutenkarten TUS, TUV, TUR gespeichert. Aus der Menge aller möglichen Übergangspunkte Usv, UVR wird eine möglichst kleine Anzahl von Teilstartpunk- ten und Teilzielpunkten ausgewahlt, 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 Ubergangspunk- teneinflie#t.ÜVR Gemäß der Heuristik wird bei einer Gesamtentfernung von dem Startpunkt S zu dem Zielpunkt Z von tuber 100 km (die Luftli- nienentfernung von Manche nach Nürnberg ist griser 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 KBI nach Übergangs- punkte USV, UVR sucht, die einen Teil einer Autobahn reperd- sentieren, d. h. z. B. einen Autobahnanschluß repräsentieren.

Anschaulich bedeutet dies, daß zwischen der ersten Teilrou- tenkarte TUS und der zweiten Teilroutenkarte TUV bzw. der zweiten Teilroutenkarte TUV und der dritten Teilroutenkarte TUR Übergangspunkte ermittelt werden, deren Knoten Orte re- präsentieren, die in einer Autobahn enthalten sind oder di- rekt zu einer Autobahn führen.

In einer vierten Nachricht 4 wird der Wissensbasis KBI des zentralen Agenten I die Anforderung zur Ermittlung der tuber- gangspunkte Ugv, UVR ubergeben.

Von der Wissensbasis KBI wird in einer funften Nachricht 5 das Ergebnis, d. h. eine Menge von tbergangspunkten tsv zwi- schen den Teilroutenkarten TUS, TUV des ersten Teilmoduls US und des zweiten Teilmoduls UV und eine Menge von Übergangs- punkte ÜvR zwischen Teilroutenkarten TUV, TUR des zweiten Teilmoduls UV und des dritten Teilmoduls UR zurückgesendet.

Die Ubergangspunkte USV, UVR sind in Figur 2 durch Punkte ge- kennzeichnet.

Eine Menge von Übergangspunkte ÜXY (X, Y E N) zwischen Teil- routenkarten besteht im Fall des Übergangs von einem Netz far den Individualverkehr zu einem Netz far den öffentlichen Ver- <BR> <BR> <BR> <BR> <BR> kehr, in diesem Fall UR o UE, UV # UE und UR o UE aus einer Menge von Parkplatzen fur Kraftfahrzeuge, die sich in der NA- he einer Station far ein öffentliches Verkehrsmittel befin- den.

Im Fall des Übergangs von einem Netz far den öffentlichen Verkehr und einem Netz far den Individualverkehr besteht die Liste aus Taxistanden.

Im Fall des Übergamgs von einem Netz far den Individualver- kehr zu einem angrenzenden weiteren Netz far den Individual- verkehr besteht die Liste aus vorgegebenen Punkten, an denen

jeweils eine Strate von einem Netz zu dem anderen Netz aber- geht.

In einer sechsten Nachricht 6, die von dem zentralen Agen- ten I an das erste Teilmodul Us, das zweite Teilmodul Uv und das dritte Teilmodul UR gesendet werden, wird bei den Teilmo- dulen Us, Uv, UR angefragt, ob es durch Berücksichtigung lo- kaler Rahmenbedingungen, die jeweils in einer lokalen Wis- sensbasis KBS, KBV, KBR, die eindeutig dem jeweiligen Teilmo- dul US, UV, UR zugeordnet ist, andere Übergangspunkte ÜSV, fiVR gibt, die sich hinsichtlich des vorgegebenen Optimie- rungskriteriums eignen.

Ein solches lokales Wissen ist darin zu sehen, daß dem ersten Teilmodul Us unter Verwendung seiner ihm zugeordneten lokalen Wissensbasis KBS bekannt ist, daß-aufgrund von Heuristiken und domanenspezifischem Wissen aus der lokalen Wissensbasis KBS-für eine langer Reise Richtung Norden von dem vorgege- benen Startpunkt S, der sich relativ weit im Süden Münchens befindet, Übergangspunkte ÜSV im Südosten und im Norden der ersten Teilroutenkarte TUS zu berücksichtigen sind.

In der lokalen Wissensbasis KBV, die dem zweiten Teilmodul UV zugeordnet ist, ist angegeben, dans fur eine Reise von München nach Nürnberg die Übergangspunkte ÜvR der zweiten Teilrouten- karte TUV des zweiten Teilmoduls UV vorteilhaft sind, die im Norden der zweiten Teilroutenkarte TUV liegen.

Aus den zusatzlichen Vorschlagen, die von den einzelnen Teil- modulen Us, Uv, UR dem zentralen Agenten I zugefuhrt werden, wird von dem zentralen Agenten I eine Teilmenge Tus fur Übergänge von der ersten Teilroutenkarte TUS und der zweiten Teilroutenkarte TUV. Analog wird far die Ubergangspunkte UR, die Übergänge zwischen der zweiten Teilroutenkarte TUV und der dritten Teilroutenkarte TUR repräsentieren, eine zweite Teilmenge TÜvR von Ubergangspunkten UR ermittelt.

Eine siebte Nachricht 7 wird von dem zentralen Agenten I an das erste Teilmodul Us, das zweite Teilmodul UV und das drit- te Teilmodul UR gesendet. Die siebte Nachricht 7 enthalt je- weils eine Anfrage zur Ermittlung einer oder mehrerer Teil- routen, die hinsichtlich des vorgegebenen Optimierungskrite- riums Zeit optimal sind.

In diesem Beispiel wird in der siebten Nachricht 7, die dem ersten Teilmodul US zugefuhrt wird, die Ermittlung von Teil- routen von dem Startpunkt S zu den funf Ubergangspunkten USV der ersten Teilmenge TÜSv, angefragt.

Die siebte Nachricht 7, die dem zweiten Teilmodul UV zuge- führt wird, enthält eine Anfrage zur Ermittlung von Teilrou- ten aller Kombinationen zwischen den Übergangspunkten ÜSV der ersten Teilmenge TTSV und den Ubergangspunkten UR der zwei- ten Teilmenge TÜVR- Die siebte Nachricht 7, die dem dritten Teilmodul UR zuge- fuhrt wird, enthält eine Anfrage zur Ermittlung von Teilrou- ten von den zwei Übergangspunkten ÜvR der zweiten Teilmenge TUVR 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 Üvs, ÜvR der Teilroutenkarten wäre im vorliegenden Fall eine Größenordnung von 2000 bis 3000 Ermittlungen erfor- derlich (ausgehend von einer Gesamtzahl möglicher Übergangs- punkte in der Größenordnung von 50).

Die Ermittlung der Teilrouten in den Teilmodulen erfolgt un- ter Verwendung von Verfahren zur Ermittlung kürzester Pfade, beispielsweise dem Verfahren nach Dijkstra. Den jeweiligen Knoten und/oder Kanten der Teilroutenkarte sind jeweils Ko- stenwerte zugeordnet, die im Rahmen der Optimierung zur Er- mittlung der Teilroute innerhalb der Teilroutenkarte in einer

Kostenfunktion berucksichtigt werden. Die Kostenwerte und die Art der Berücksichtigung hängen ab von der Art des Optimie- rungskriteriums. Mögliche Optimierungskriterien sind die far die Reise insgesamt benötigte Zeit, die zu minimierende ge- samte Routenlänge, oder weiteren Rahmenbedingungen. So wird far den Fall, daß ein bestimmtes Verkehrsmittel nicht verwen- det werden soll, das jeweilige Teilmodul, das far das Ver- kehrsmittel"zustandig"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än- gender Knoten und Kanten, ausgehend von dem Startpunkt S hin zu dem Zielknoten Z, ist. Die hinsichtlich des Optimierungs- kriteriums, #Zeit" beste Route wird von dem zentralen Agen- ten I ausgewahlt.

Das far die erste Sequenz Ug UR oben beschriebene Verfahren wird far alle weiteren Sequenzen entsprechend durchgeführt.

Es ist jedoch zu beachten, daß bei Übergängen zwischen einem Netz far den Individualverkehr und einem Netz far den offrent- lichen Verkehr jeweils noch Übergangszeiten für den Wechsel des Verkehrsmittels und diskrete Abfahrtszeiten des jeweili- gen öffentlichen Verkehrsmittels zu berücksichtigen sind.

Dies ist bei dem Übergang zwischen Netzen far den Individual- verkehr 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 beschrie- benen Ausführungsbeispiel aufgezeigt.

In dem Ausführungsbeispiel sind dem zentralen Agenten I alle erheblichen Teilmodule, die far die Ermittlung der Route er- forderlich sind, bekannt. In einer Variante ist jedoch vorge- sehen, daß die Information tuber 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 Wis- sensbasis KBI des zentralen Agenten I, sondern in einem wei- teren Agenten gespeichert ist. In diesem Fall wurde auch die- se Information von dem weiteren Agenten durch den zentralen Agenten I abgefragt.

Far die Sequenzen 2 bis 5 kann in einer Variante der Fall eintreten, daß der letzte Abschnitt der Reise mit einem Taxi zuruckgelegt wird. Dies bedeutet, daß die Folge um das weite- re Teilmodul UR (Ergänzung der Folgen um das Postfix"o UR") ergänzt werden matte, da zwar das letzte Teilmodul UR nicht den genauen Weg zu dem Zielpunkt Z, jedoch die far das letzte Teilstuck benotigte 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