PatentDe  


Dokumentenidentifikation DE102005023742B4 05.08.2010
Titel Verfahren zur Koordination von vernetzten Abfertigungsprozessen oder zur Steuerung des Transports von mobilen Einheiten innerhalb eines Netzwerkes
Anmelder Eidgenössische Technische Hochschule (ETH), Zürich, CH
Erfinder Helbing, Dirk, Prof. Dr., 01309 Dresden, DE;
Lämmer, Stefan, Dipl.-Ing., 01067 Dresden, DE
Vertreter Sperling, Fischer & Heyner Patentanwälte, 01277 Dresden
DE-Anmeldedatum 17.05.2005
DE-Aktenzeichen 102005023742
Offenlegungstag 23.11.2006
Veröffentlichungstag der Patenterteilung 05.08.2010
Veröffentlichungstag im Patentblatt 05.08.2010
IPC-Hauptklasse G05B 13/04  (2006.01)  A,  F,  I,  20051017,  B,  H,  DE
IPC-Nebenklasse G08G 1/01  (2006.01)  A,  L,  I,  20051017,  B,  H,  DE
H04L 12/28  (2006.01)  A,  L,  I,  20051017,  B,  H,  DE
G08G 1/07  (2006.01)  A,  L,  I,  20051017,  B,  H,  DE

Beschreibung[de]

Die Erfindung betrifft ein Verfahren zur Koordination von vernetzten Abfertigungsprozessen oder zur Steuerung des Transports von mobilen Einheiten innerhalb eines Netzwerkes, insbesondere zur Steuerung eines Verkehrsnetzes oder zur Steuerung eines komplexen Produktionsprozesses. Die Erfindung ist weiterhin anwendbar zur Steuerung von Logistikprozessen und im weiteren Sinne auch für die Steuerung von Informationsübertragungsprozessen oder die Koordination von ineinander greifenden Organisations- bzw. Programmabläufen.

Derartige Verfahren werden eingesetzt, um beispielsweise innerhalb von Verkehrsnetzen einen optimierten Verkehrsfluss der Fahrzeuge und Fußgänger zu ermöglichen. Adaptive Steuerungsverfahren sind auch zur Steuerung von Produktionsprozessen oder in der chemischen Prozess- und Verfahrenstechnik im Einsatz. Generell ist jedoch anzumerken, dass die Abhängigkeit der Dynamik komplexer Systeme mit nichtlinearem Verhalten von der Netzwerkstruktur bis heute nur unvollständig verstanden wird und entsprechende Optimierungsverfahren daher heuristischer Natur oder Best-Practice-Ansätze sind. Dies ist bei großen Systemen auch mit dem überbordenden Rechenaufwand begründet, der mit einer wachsenden Anzahl von Netzwerkknoten „explodiert”. Die verwendeten Verfahren haben folglich zahlreiche Unzulänglichkeiten. Ein gängiger Ansatz ist zum Beispiel die ereignisorientierte Simulationstechnik. Sie neigt jedoch zu „Aktionismus”, während eine Minimierung der durchschnittlichen Wartezeiten im System paradoxerweise oft Zeitverzögerungen erfordert, um konkurrierende Prozesse besser zu koordinieren. Die Liste der eingesetzten Verfahren und ihrer jeweils unterschiedlichen Defizite ließe sich beliebig verlängern. Obwohl viele Verfahren Lösungsansätze für Teilprobleme liefern, fehlt bisher ein genereller Ansatz zur systematischen Koordination von konkurrierenden (Abfertigungs-)Prozessen in großen Netzwerken bei unregelmäßiger zeitlicher Variation von Nachfrage- und Kapazitätsgrößen.

Verfahren zur Verkehrsregelung in Verkehrsnetzwerken sind in verschiedenster Ausgestaltung im Stand der Technik bekannt. Verwandte Probleme treten auch beim Routing von Datenströmen in Netzwerken auf, beispielsweise dem Internet. Allerdings sind die bestehenden Unterschiede erheblich: Während die mobilen Einheiten in Verkehrsnetzen überwiegend von den Kanten (Straßen) aufgenommen werden, dort die größten Zeitverzögerungen erfahren und nicht verloren gehen, werden Daten überwiegend in den Netzwerkknoten (Servern) zwischengespeichert und verlieren dort Zeit bzw. gehen verloren, wenn die Speicherkapazität erreicht ist. Weiterhin sind in Datennetzen Umschaltzeiten vernachlässigbar und Nutzungskonflikte von anderer Art. Daher sind die Verfahren zum adaptiven Datenrouting zur Lichtsignalsteuerung nicht geeignet.

Die bekanntesten und verbreitetsten Strategien zur Verkehrsregelung in Verkehrsnetzwerken befassen sich mit der Synchronisation des Verkehrs entlang von Verkehrsadern mit dem Ziel der Erzeugung von Grünen Wellen, deren Eigenschaft es ist, dass der Verkehr entlang der Verkehrsader fließt, und dass dadurch der Kraftstoffverbrauch reduziert und die Reisezeiten verkürzt werden können. Auf Beispiele für die verschiedenen Realisierungsmöglichkeiten wird nachfolgend kurz verwiesen.

Nach der DE 44 36 339 A1 ist ein Verfahren zur verkehrsadaptiven Steuerung einer Verkehrsampelanlage bekannt, wobei Sensoren zur Verkehrserfassung im Kreuzungsbereich zyklisch Daten liefern, welche in konkrete Steuersequenzen für die Verkehrsampel umgewandelt werden. Bei dem Verfahren wird neben den für die Verkehrssicherheit erforderlichen Prinzipien kein vorgefertigtes Modell benötigt. Die Grünphasen werden in Abhängigkeit von zeitlichen Schwankungen des Verkehrsaufkommens dem Verkehrsstrom angepasst.

Nach der DE 198 41 457 A1 ist ein Verfahren zur Ermittlung eines verkehrsabhängigen Signalprogrammes für Signalgruppen von Lichtsignal-Anlagen bekannt, bei dem die Signalfolgen von Signalgruppen durch Signalprogramme bestimmt werden. Die Signalprogramme werden unter Berücksichtigung von aktuellen, durch Verkehrsdetektoren ermittelten Daten an den aktuellen Verkehrsablauf angepasst. Dabei werden Signalprogramme verschiedener Ordnung erzeugt, die mit einer Qualitätsfunktion bewertet werden und aus deren Kombination weitere Signalprogramme erzeugt werden. Das als optimal ermittelte Signalprogramm wird schließlich zur Steuerung der Lichtsignalanlage verwendet.

Nach der DE 196 47 127 A1 ist ein Verfahren zur automatischen Verkehrsüberwachung mit Staudynamikanalyse bekannt, bei der erfindungsgemäß laufend eine Schätzung der zeitabhängigen Positionen der stromaufwärtigen Stauflanke und der stromabwärtigen Stauflanke nach charakteristischen Beziehungen vorgenommen wird, welche den Fluss und die Dichte des Verkehrs und des Staus, den Zeitpunkt, zu dem die stromaufwärtige Stauflanke eine jeweils erste Messstelle passiert, den Zeitpunkt, zu dem die stromabwärtige Stauflanke diese Messstelle passiert, sowie den Fluss und die mittlere Fahrzeuggeschwindigkeit an dieser ersten sowie an einer stromaufwärts der stromaufwärtigen Stauflanke gelegenen zweiten Messstelle berücksichtigt.

Die EP 1 057 155 B1 offenbart ein Verfahren zur Verkehrsleitung in einem Straßennetz, wobei auch die Gefahr einer Blockierung einer stromabwärts liegenden Verbindung bei einer Zuteilungsbestimmung beurteilt und in einem Zentralrechner verarbeitet wird.

Den Verfahren nach dem Stand der Technik ist der Nachteil zu Eigen, dass die Steuerkonzepte entweder keine gute Koordination benachbarter Ampeln gewährleisten oder von zentral gesteuerten Steuereinheiten ausgehen, welche eine Vernetzung der einzelnen Ampelanlagen mit einem Zentralrechner voraussetzen. Die zentralrechnergestützten Verkehrsleit- und Regelsysteme sind aufgrund der erforderlichen Datenverbindungsleitungen kostenaufwändig und leiden tendenziell unter einer Überlastung der Steuer- oder Entscheidungszentrale. Weiterhin sind die Programme und Steuerroutinen zu wenig adaptiv, um auf plötzliche und zufällige Änderungen der Verkehrssituation zu reagieren.

Verallgemeinernd kann gesagt werden, dass die Grüne-Welle-Methode, die im Voraus berechnete Kontrollschemata enthält, zwanghaft den Verkehrsfluss in vorberechnete Muster, wie feste Signalfolgen oder Programmabläufe, zu fügen versucht. Da die Verkehrsbelastung in der Realität jedoch variiert, wurde der Bedarf an Reaktionsfunktionen der Signalsteuerung bald offensichtlich, was zur Weiterentwicklung der traditionellen Systeme führte. Allerdings funktionieren die daraus entstandenen Systeme nur unter idealisierten Bedingungen optimal oder die zugrunde gelegten Näherungsverfahren wirken sich nachteilig aus.

Neuere Entwicklungen integrieren eine größere Adaptabilität, wobei die lokale Steuerung auf der Vorhersage des Verkehrsaufkommens eines globalen Netzwerkes von Verkehrsadern beruht, in die lokale Schnittpunktsteuerungen integriert werden. Diese im Stand der Wissenschaft bekannten Modelle und Methoden erfordern große Datensammlungen und einen sehr hohen Prozessaufwand. Dazu erfordert die globale Koordination ständig Daten, die schwer zu erhalten oder online auszuwerten sind. Weiterhin impliziert eine globale Optimierung eine große Sensitivität auf weit entfernte Abläufe, welche die Flexibilität bei der Anpassung an lokale Abläufe unnötig einschränkt.

Die DE 699 13 944 T2 beschreibt ein Verfahren zur Verkehrsoptimierung im übersättigten Verkehrszustand, in dem die Blockade des Abflusses durch zugestaute Straßenabschnitte im Mittelpunkt steht. Im Unterschied zu herkömmlichen Ampelsteuerungsverfahren reagiert dieses Verfahren nicht auf strom-aufwärtigen Verkehr, sondern konzentriert sich auf den strom-abwärtigen Verkehr. Die in der DE 699 13 944 T2 vorgeschlagene Lösung besteht in der Reduktion des Zufahrtsverkehrs durch Festlegung geeigneter Zuteilungen/Kontigentierungen für einzelne Straßen und kurzfristige Variationen zur Reaktion auf statistische Schwankungen im Verkehrsfluss. Es wird aber keine Lösung für die Frage offenbart, wie von der Steuerung für den Bereich unterhalb der Kapazität des Verkehrsnetzes (mit Reaktion auf die strom-aufwärtige Verkehrssituation) in den Bereich oberhalb seiner Kapazität (mit Fokus auf die strom-abwärtige Verkehrssituation) gewechselt wird und wie ein Betrieb erfolgen soll, in dem beide Fälle vermischt sind.

Aus FRIEDRICH, B.; SCHÜTTE, C.: A NEW APPROACH FOR INTEGRATED TRAFFIC CONTROL IN METROPOLITAN AREAS. In: 7-th World Congress an Intelligent Transport Systems, Torino, 6.–9. Nov. 2000, geht ein Konzept für ein Verkehrssteuerungssystem in Großstadtgebieten hervor. Dieses Konzept beinhaltet das Vorhandensein lokaler Steuerungen, zu deren Koordination jedoch ein hierarchischer Ansatz erforderlich ist. Dabei werden auf der höchsten, der strategischen Ebene, Entscheidungen durch Verkehrsexperten beziehungsweise Verkehrsoperatoren getroffen, um eine Konsistenz der Ziele für verschiedene Kontrollsysteme zu erreichen.

In der Druckschrift PORCHE, I. ET AL.: A decentralized scheme for real-time optimization of traffic signals. In: Proceedings of the 1996 IEEE International Conference an Control Applications. 1996, S. 582 bis 589, wird ein Optimierungsverfahren zur dezentralen verkehrsabhängigen Steuerung von Lichtsignalanlagen beschrieben. Dabei erfolgt eine dezentrale Optimierung des Verkehrsdurchsatzes an den einzelnen Verkehrsknoten, was jedoch in der Regel zu „egoistischem”, unkoordinierten Verhalten der Steuerungen an den einzelnen Verkehrsknoten führt. In der Konsequenz ist die Optimierung an den einzelnen Verkehrsknoten für das gesamte Verkehrsnetz eher schädlich, weil es zu einer Verringerung von dessen Performance führt.

Insgesamt ist den Verfahren nach dem Stand der Technik nachteilig gemeinsam, dass die Systeme nur schwerfällig oder nicht angemessen auf Ausnahmeereignisse, wie im Falle von Verkehrsnetzwerken auf Unfälle, Baustellen oder andere temporäre Änderungen im Straßennetz, Ausfälle von Datenleitungen, Steuerungsanlagen oder Zentralrechnern, natürliche oder industrielle Störfaktoren, Katastrophen oder auch terroristische Angriffe reagieren.

Aufgabe der Erfindung ist es somit, ein adaptives Verfahren zur Koordination konkurrierender Prozesse oder zur Steuerung des Transports von mobilen Einheiten in Netzwerken zur Verfügung zu stellen, welches einen hohen Grad an Flexibilität bei großer Robustheit gegenüber lokalen Ausfällen oder Störungen aufweist.

Die Aufgabe der Erfindung wird einerseits durch ein Verfahren zur Steuerung des Transports von mobilen Einheiten innerhalb eines Netzwerkes gelöst, welches Knoten und Kanten aufweist. Dabei wird das Netzwerk in Kernbereiche n unterteilt, denen jeweils ein Randbereich zugeordnet wird, so dass der Kernbereich und der dazugehörige Randbereich jeweils ein zusammenhängendes Subnetzwerk von Knoten und Kanten definieren, wobei die Kanten eine begrenzte Pufferkapazität an aufnehmbaren mobilen Einheiten besitzen und die Knoten und/oder Kanten mit Datenerfassungselementen, zum Beispiel Sensoren, zur Erfassung von Daten ausgestattet sind und die Knoten eine begrenzte Abfertigungskapazität an zu bedienenden mobilen Einheiten haben. Die Knoten sind mit Steuereinheiten ausgestattet, für die ein Schaltzustand der Abfertigung von mobilen Einheiten, ein Schaltzustand der Nichtabfertigung und jeweils zwischen diesen ein Umschaltzustand vorgesehen sind. Das Verfahren ist dadurch gekennzeichnet, dass

  • a die echtzeitfähige Steuerung dezentral und selbstorganisierend in den Steuereinheiten der Knoten oder den Steuereinheiten lokal begrenzter Subnetzwerke erfolgt, wobei die Steuereinheiten benachbarter Knoten oder Subnetzwerke miteinander zum Datenaustausch in Verbindung stehen und wenigstens zwei Knoten die kleinstmögliche Variante von Subnetzwerken darstellen,
  • b1 Daten aus Voraussagemodellen der lokalen Abfertigungsprozesse aller Knoten des jeweiligen Subnetzwerkes und/oder
  • b2 Daten von Datenerfassungselementen aller Knoten und der mit ihnen verbundenen Kanten des Subnetzwerkes
  • c für die lokale Simulation und Optimierung von Schaltzuständen der Steuereinheit zur Ermittlung der Leistungsfähigkeit (Performance) der Knoten oder Subnetzwerke unter Berücksichtigung der Pufferkapazität der Kanten auf der Basis von Modellen für Kurzzeitprognosen bei fest angenommenen Schaltzuständen benachbarter Knoten eingesetzt werden, wobei
  • c1 aus mehreren alternativen Steuerungsstrategien hoher Performance für die einzelnen Knoten durch Kombination dieser Steuerungsstrategien eine Auswahl von Steuerungsstrategien für Subnetzwerke generiert werden, die unter dem Gesichtspunkt der Performance besonders vielversprechend sind, wobei
  • c2 die Kombination der jeweils besten Steuerungsstrategie jedes Einzelknotens des Subnetzwerkes nicht notwendigerweise die beste Steuerungsstrategie für das Subnetzwerk selber darstellt und daher durch einen geeigneten Test, aus der Menge der generierten alternativen Steuerungsstrategien für Subnetzwerke jene identifiziert wird, welche dort die beste Koordination im Sinne der besten Performance im Subnetzwerk zeigt und anschließend
  • c3 im jeweiligen Kernbereich des Subnetzwerkes die Steuerungsstrategie mit der besten Koordination ausgewählt und in entsprechende Schaltzustände für die betroffenen Knoten umgesetzt wird.

Die Aufgabe der Erfindung wird andererseits durch ein Verfahren zur Koordination von vernetzten Abfertigungsprozessen, die um knappe Ressourcen, insbesondere eine frühere Abfertigungszeit innerhalb eines Netzwerkes konkurrieren, welches Knoten und Kanten aufweist, gelöst. Dabei wird das Netzwerk in Kernbereiche n unterteilt, denen jeweils ein Randbereich zugeordnet wird, so dass der Kernbereich und der dazugehörige Randbereich jeweils ein zusammenhängendes Subnetzwerk von Knoten und Kanten definieren, wobei die Kanten eine begrenzte Pufferkapazität für zu bedienende Einheiten besitzen und die Knoten und/oder Kanten mit Datenerfassungselementen, zum Beispiel Sensoren, zur Erfassung von Daten ausgestattet sind und die Knoten eine begrenzte Abfertigungskapazität von zu bedienenden Einheiten haben. Die Knoten besitzen Steuereinheiten, für die ein Zustand der Abfertigung zu bedienender Einheiten, ein Zustand der Nichtabfertigung und jeweils zwischen diesen ein Umschalt- oder Übergangszustand auftritt. Das Verfahren ist dadurch gekennzeichnet, dass

  • a die echtszeitfähige Koordination der konkurrierenden Abfertigungsprozesse dezentral und selbstorganisierend in den Steuereinheiten der Knoten oder den Steuereinheiten lokal begrenzter Subnetzwerke erfolgt, wobei die Steuereinheiten benachbarter Knoten oder Subnetzwerke miteinander zum Datenaustausch in Verbindung stehen und wenigstens zwei Knoten die kleinstmögliche Variante von Subnetzwerken darstellen,
  • b1 Daten aus Voraussagemodellen der lokalen Abfertigungsprozesse aller Knoten des jeweiligen Subnetzwerkes und/oder
  • b2 Daten von Datenerfassungselementen aller Knoten und der mit ihnen verbundenen Kanten des Subnetzwerkes
  • c für die lokale Simulation und Optimierung von Schaltzuständen der Steuereinheit zur Ermittlung der Leistungsfähigkeit (Performance) der Knoten oder Subnetzwerke unter Berücksichtigung der Pufferkapazität der Kanten auf der Basis von Modellen für Kurzzeitprognosen bei fest angenommenen Zuständen benachbarter Knoten eingesetzt werden, wobei
  • c1 aus mehreren alternativen Steuerungsstrategien hoher Performance für die einzelnen Knoten durch Kombination dieser Steuerungsstrategien eine Auswahl von Steuerungsstrategien für Subnetzwerke generiert werden, die unter dem Gesichtspunkt der Performance besonders vielversprechend sind, wobei
  • c2 die Kombination der jeweils besten Steuerungsstrategie jedes Einzelknotens des Subnetzwerkes nicht notwendigerweise die beste Steuerungsstrategie für das Subnetzwerk selber darstellt und daher durch einen geeigneten Test, aus der Menge der generierten alternativen Steuerungsstrategien für Subnetzwerke jene identifiziert wird, welche dort die beste Koordination im Sinne der besten Performance im Subnetzwerk zeigt und anschließend
  • c3 im jeweiligen Kernbereich des Subnetzwerkes die Steuerungsstrategie mit der besten Koordination ausgewählt und in entsprechende Zustände für die betroffenen Knoten umgesetzt wird.

Das Verfahren ist bevorzugt dadurch gekennzeichnet, dass die in die lokale Simulation und Optimierung in Verfahrensschritt c einbezogenen Ziel- beziehungsweise Optimierungskriterien benachbarter Knoten in Abhängigkeit ihrer Entfernung zu den Grenzen des Subnetzwerks gewichtet werden. Vor allem im Randbereich des jeweils optimierten Subsystems werden die Knoten geringer gewichtet.

Die Wichtung im dezentralen Steuerungsverfahren kann beispielsweise durch den Ausdruck

erfolgen, der bei der Optimierung der Steuerung maximiert wird. Hierbei steht w nij für das Gewicht, das die Abfertigung von Kante i nach j am Knoten n auf die Optimierung haben soll, und fnij(t) für eine Ziel- bzw. Bewertungsfunktion. Das erfindungsgemäße Verfahren weist für die Simulation und Optimierung in Verfahrensschritt c bevorzugt folgende Eigenschaften auf:
  • d1 bei geringer Nachfrage von den mobilen Einheiten erfolgt an den Knoten eine einzelne Abfertigung der Einheiten ohne Wartezeiten, so dass die Anzahl der abgefertigten Einheiten proportional zu den durchschnittlich ankommenden Einheiten ist, wobei
  • d2 bei hoher Nachfrage mit unvermeidbaren Wartezeiten eine gruppenweise Abfertigung der Einheiten durch längere Schaltphasen zur Minimierung der Umschaltverluste erfolgt, wobei
  • d3 die Minimierung der Umschaltverluste bei Bedarf mit der priorisierten Abfertigung von zielnahen mobilen Einheiten kombiniert wird, um diese schnell aus dem Netzwerk zu entfernen,
  • d4 Schaltzeitverluste durch vorzeitiges Umschalten zugunsten einer Synchronisation von benachbarten Abfertigungsschaltzuständen durch eine prognostizierte höhere Abfertigungskapazität an benachbarten Knoten überkompensiert werden,
  • d5 Pufferkapazität bei hoher Nachfrage in den dem Knoten nachfolgenden Kanten reserviert wird, wobei die pro Kante zugestandene Pufferkapazität adaptiv angepasst wird,
  • d6 eine Priorisierung, nach der die Einheiten an den Knoten abgefertigt werden, auf der Grundlage individueller Eigenschaften der Einheiten möglich ist und dass
  • d7 eine Beschränkung der maximalen Dauer der Nichtabfertigung bei extrem hoher Nachfrage durch Kontingentierung gewährleistet wird.

Vorzugsweise verwendet die lokale (dezentrale) Optimierung ein datenbankgestütztes Verfahren, in dem eine Anzahl von Steuerungsstrategien hoher Performance in Abhängigkeit von Parametern hinterlegt werden, welche die Situation im jeweiligen Subnetzwerk charakterisieren und verfahrensbegleitend erhoben werden.

Nach einer vorteilhaften Ausgestaltung der Erfindung ist vorgesehen, dass die erforderlichen Modellparameter durch eine Kombination mehrerer alternativer Simulations- und Messdaten ermittelt werden und dass bei Fehlen oder Unplausibilität von (Mess-)Daten gemäß Verfahrensschritt b2 die fehlenden bzw. unbrauchbaren Daten durch ein Prognosemodell geschätzt werden und/oder dass bei Fehlen oder Unplausibilität von Simulations- oder Messdaten gemäß Verfahrensschritt b1 nach einer fest vorgegebenen Steuerungsstrategie (Festzeitsteuerung) gesteuert wird.

Eine weitere Ausgestaltung der Erfindung ergibt sich dadurch, dass bei hoher Nachfrage mit Wartezeiten an den Knoten parallel zur gruppenweisen Abfertigung von Einheiten zu passender Zeit eine Einzelabfertigung von Einheiten erfolgt, die ansonsten zu konfliktbehafteten Abfertigungsströmen gehören.

Soweit erforderlich, übermitteln die Einheiten Daten zu ihren Zielen an die Steuereinheiten der nächstgelegenen Knoten.

Das erfindungsgemäße Verfahren ist bevorzugt für die Steuerung eines Verkehrsnetzes verwendbar, wobei die Knoten des Netzwerkes die Kreuzungen und die Steuereinheiten die Ampeln und die Kanten die Straßenabschnitte und die mobilen Einheiten Fahrzeuge und/oder Fußgänger des Verkehrsnetzes darstellen.

Weiterhin ist das Verfahren verwendbar für die Steuerung von Produktionsprozessen. In diesem Fall stellen z. B. die Knoten Produktionsmaschinen, die Steuereinheiten die Maschinensteuerung, die Kanten die Transportwege und Puffer zwischen den Produktionsmaschinen sowie die mobilen zu bedienenden Einheiten die aus dem Produktionsprozess hervorgehenden Produkte dar. Verschiedene Ziele entsprechen verschiedenen Produktsorten (Artikeln) und unterschiedliche Routen unterschiedlichen Produktionsabläufen.

Nach einer weiteren Ausgestaltung der Erfindung ist das erfindungsgemäße Verfahren verwendbar für die Steuerung der Logistik eines Gütertransportes, wobei die Knoten die Umschlagplätze, die Kanten die Transportwege und die zu bedienenden Einheiten die Transportgüter darstellen.

Bei der Anwendung auf die Koordination von Organisationsabläufen entsprechen die zu bedienenden Einheiten den zu bearbeitenden Vorgängen und die Knoten den Bearbeitern, während die Kanten die Verwaltungs- oder Beförderungswege der Vorgänge beschreiben. Die Steuerung entspricht den vorgenommenen Priorisierungsentscheidungen. Entsprechend lassen sich Programmabläufe behandeln, bei denen die Knoten Programmmodulen entsprechen, die zu bedienenden Einheiten zu verarbeitende Daten sind. Die Weitergabe von Daten zwischen Programmmodulen definiert die Kanten des Netzwerks aufeinander folgender Verarbeitungsprozesse. Die Steuerung dient der Koordination und Harmonisierung der Verarbeitungsprozesse im Sinne eines besseren Einsatzes von Verarbeitungskapazitäten und einer schnelleren Abarbeitung.

Eine mögliche Erweiterung des Anwendungsbereiches des erfindungsgemäßen Steuerungsverfahrens ergibt sich auf dem Gebiet der Biotechnologie und Medizin. Letztendlich lässt sich auch die Verteilung von Substanzen oder Wirkstoffen in Zellen, Geweben oder Organismen als logistischer Vorgang beschreiben. So lässt sich das Verfahren zur Steuerung des Verteilungsprozesses von physikalischen, chemischen oder biologischen Substanzen verwenden, wobei diese Substanzen die mobilen Einheiten darstellen, die Knoten mögliche Ausgangs- und Zielorte dieser Substanzen sind und die Kanten Transportwegen der Substanzen entsprechen.

Ein Verkehrsnetz, welches zur Durchführung des erfindungsgemäßen Verfahrens geeignet ist, weist eine Vielzahl von Kreuzungen, Straßenabschnitten, Sensoren und Ampelanlagen mit computer- oder prozessorgestützten Steuereinrichtungen auf und ist weiterhin dadurch gekennzeichnet, dass den Kreuzungen Ampelanlagen und Kreuzungen oder Straßenabschnitten Sensoren zugeordnet sind, wobei die Steuereinrichtungen zum Empfang von Daten mit den Sensoren und die Steuereinrichtungen benachbarter Ampelanlagen zum Austausch von Daten in Verbindung stehen.

Gemäß einer Vorzugsausgestaltung der Erfindung sind die Datenverbindung zwischen den Sensoren und den Steuereinrichtungen der Ampelanlagen sowie zwischen den Steuereinrichtungen benachbarter Ampelanlagen drahtlos ausgebildet. Beispielsweise können die Datenverbindungen als wireless LAN (WLAN), als Bluetooth, als Infrarotverbindung, als Radarsignal, als Laserlink oder deren Weiterentwicklungen umgesetzt sein.

Unter einem Netzwerk im Sinne der beschriebenen Erfindung ist eine Vielzahl von Knoten und Kanten zu verstehen, die miteinander in Verbindung stehen. Unter einem Knoten wird gemäß dem dargelegten Hauptanwendungsgebiet der Erfindung eine Straßenkreuzung verstanden, jedoch ist die Anwendung des erfindungsgemäßen Prinzips auch auf komplexe Produktions- oder Organisationsprozesse sowie auf Organisationsprozesse oder Programmabläufe möglich, wobei ein Knoten dort beispielsweise einer Verarbeitungsmaschine, einem Bearbeiter oder einem Datenverarbeitungsprozess entsprechen würde.

Eine Kante entspricht in einem Verkehrsnetzwerk einem Straßenabschnitt, in einem Produktionsprozess einem Transportweg der Produkte von einem Verarbeitungsschritt zum nächsten oder einem (Zwischen-)Puffer, in einem Organisationsprozess oder Programmablauf beispielsweise der Weiterleitung bzw. dem Austausch von Daten.

Die Abfertigungskapazität eines Knotens entspricht seinem maximalen Durchsatz, wohingegen die Pufferkapazität einer Kante ihrer maximalen Aufnahmekapazität für zu bedienende Einheiten, d. h. der maximalen Warteschlange, entspricht. Weiterhin entspricht die Abfertigungsdauer der Zeitspanne, bis eine in Abfertigung befindliche Einheit den Knoten verlassen hat, also der Zeitspanne, welche zwischen dem Verlassen der vorhergehenden Kante durch eine Einheit und dem Erreichen der nachfolgenden Kante des Knotens verstreicht.

Unter einer Priorisierung wird ein optimiertes Abfertigungsschema verstanden, da es beim zeitnahen Eintreffen von Einheiten an einem Knoten zu einer Überschreitung der Abfertigungskapazität oder Abfertigungskonflikten an dem Knoten kommt und eine Priorisierung der abzufertigenden Einheiten gegenüber anderen Einheiten vorgenommen werden muss, um ein optimales Abfertigungsergebnis zu erreichen.

Eine Steuereinheit stellt ein Systemelement dar, das Priorisierungsentscheidungen für die Reihenfolge und/oder Parallelität von Bedienungs- bzw. Abfertigungsprozessen umsetzt. Eine Steuereinheit ist jeweils einem Knoten zugeordnet und nach dem Hauptanwendungsgebiet der Erfindung zum Beispiel als Ampelanlage ausgebildet.

Der Schaltzustand der Abfertigung von mobilen Einheiten am Knoten entspricht beim Verkehrsnetzwerk einer grün geschalteten Ampel und der Schaltzustand der Nicht-Abfertigung einer roten Ampel. Zwischen diesen Schaltzuständen ist ein Umschaltzustand vorgesehen, welcher einer gelb geschalteten Ampel entspricht.

Es wurde gefunden, dass ein erwünschtes Maß an Flexibilität durch die Unabhängigkeit der lokalen Steuerung von zentralen Steuer- oder Regelkontrollzentren ermöglicht wird. Um die gestellte Aufgabe zu lösen, wird konzeptionsgemäß ein autonomes, adaptives Steuerungsverfahren basierend auf einer bedarfssensitiven Selbstorganisation von Knoten vorgeschlagen, welches zu einem angemessenen Abfertigungsbetrieb führt und darüber hinaus sinnvollerweise Synchronisationsmuster, wie im Falle von Verkehrsnetzwerken eine Grüne Welle, selbständig erzeugt.

Besonders vorteilhaft schlägt sich dabei nieder, dass das erfindungsgemäße Verfahren nicht nur die mit einem Verkehrsstrom mobiler Einheiten verbundene nachgefragte Kapazität berücksichtigt, sondern darüber hinaus auch die verfügbare bzw. angebotene Kapazität der folgenden Netzwerkkanten.

Die verallgemeinerungsfähige Konzeption wird nachfolgend am Beispiel eines Verfahrens zur Steuerung eines Verkehrsnetzwerkes erläutert. Nach der Konzeption der Erfindung wird ein Prinzip zur Realisierung einer selbstorganisierten Steuerung von Knoten durch einen geeigneten Koordinationsmechanismus vorgeschlagen. Das Konzept wird in 1 veranschaulicht.

  • 1) Das aus Kanten (Richtungsfahrbahnen, Straßenabschnitten) und sie verbindenden Knoten (Verbindungsstücken, Kreuzungen) bestehende (Straßen-)Netzwerk wird zunächst in so genannte Kernbereiche n unterteilt. Diese können beispielsweise einzelnen Knoten entsprechen, aber auch den Knoten, die sich innerhalb eines quadratischen, sechseckigen oder anders definierten, zusammenhängenden Subsystems befinden. 2 illustriert beispielhaft quadratisch gewählte Subsysteme (dicke Linien).
  • 2) Zu jedem Kernbereich wird ein zugehöriger Randbereich bestimmt, der in 2 mit den dünnen durchgezogene Linien umrahmt ist. Er ist dadurch definiert, dass die in ihm befindlichen Einheiten (Fahrzeuge oder andere Verkehrsteilnehmer) innerhalb eines vorzugebenden Optimierungszeithorizonts T' den Kernbereich erreichen oder beeinflussen können bzw. dadurch, wie weit im Kernbereich befindliche Einheiten innerhalb dieser Zeit gelangen können. Der Kernbereich und sein Randbereich zusammen definieren ein Subnetzwerk, in dem die lokale Optimierung der (Lichtsignal-)Steuerung stattfindet. Besteht der Kernbereich aus einem einzigen Knoten, genügt es im Prinzip, sich auf das Subnetzwerk zu beschränken, in dem Fahrzeuge von der Ampelschaltung am Knoten n betroffen sein können und die Ampelschaltung somit beeinflussen können sollten. Daher erfolgt eine Beschränkung auf den Radius, der von Fahrzeugen während der maximalen Grünzeit T' durchmessen werden kann. Dieser Radius entspricht etwa einem Viertel bis zur Hälfte der maximalen, gesetzlich vorgeschriebenen Zykluszeit T. In dieser Zeit beeinflussen nur jene Fahrzeuge das für eine Lichtsignalanlage maßgebliche Geschehen, die sich in einem Radius V0T' um die Lichtsignalanlage befinden, wobei V0 die maximale, gesetzlich vorgeschriebene Geschwindigkeit ist. De facto kann man sich sogar auf den Radius V T' beschränken, wobei V ≈ V0/3 die mittlere Geschwindigkeit im behinderten Verkehr repräsentiert. Man beachte, dass bei geringem Verkehrsaufkommen mit hohen mittleren Geschwindigkeiten die optimalen Grünzeiten kurz sind, um die Wartezeiten der Fahrzeuge zu verkürzen. Für den Stadtverkehr ist es somit sinnvoll, einen Radius von etwa 300 bis 500 Metern bei der lokalen (dezentralen) Lichtsignaloptimierung zu berücksichtigen. Größere Radien können zu etwas besseren Ergebnissen führen, geringere Radien zu deutlich schlechteren Ergebnissen. Wegen der abnehmenden Vorhersagegenauigkeit einer Verkehrsprognose über längere Zeiträume macht es jedoch wenig Sinn, T' und damit den Radius viel größer als angegeben zu wählen. Infolgedessen kann eine dezentrale Steuerung nahe an das Systemoptimum gelangen; bei wesentlich größerer Flexibilität.
  • 3) Bei der Lichtsignaloptimierung handelt es sich um ein kombinatorisches so genanntes NP-hartes Optimierungsproblem, bei dem die erforderliche Rechenzeit mehr als polynomial mit der Systemgröße bzw. der Anzahl der Knoten wächst, so dass selbst Supercomputer überfordert sein können, die optimale Lösung in Echtzeit zu bestimmen. Die Optimierung in Subnetzwerken reduziert die Anzahl möglicher Lösungen und damit die Rechenzeit erheblich. Eine derartige dezentrale Optimierung kann dann und nur dann gute Gesamtlösungen liefern, wenn das Optimierungsverfahren die Steuerungen von benachbarten, d. h. über Kanten verbundene Bereiche koordiniert und aufeinander abstimmt, was durch die Erfindung erreicht wird. Hierbei müssen genügend und außerdem geeignete Parameter variiert werden, was man unter anderem durch Wahl der Größe der Subsysteme und des Optimierungszeithorizonts, aber auch durch die Optimierungstiefe, d. h. die Anzahl verglichener Alternativlösungen erreichen kann.

Ein solcher dezentraler Optimierungsansatz kann deshalb sehr gute Lösungen liefern, weil zwar in der Regel nur eine einzige optimale Lösung (Steuerung) existiert, aber die Anzahl nahezu optimaler Lösungen schon mit geringem Abstand zur optimalen Lösung schnell zunimmt. Die Optimierungsstrategie ist daher, bei drastisch gesteigerter numerischer Performance nahezu systemoptimale Lösungen durch dezentrale, aber koordinierte Optimierung zu erreichen. Unter den nahezu systemoptimalen Lösungen werden solche ausgewählt, die gleichzeitig den lokalen Gegebenheiten am besten gerecht werden. Hierdurch erreicht die vorgeschlagene Erfindung eine geringere Sensitivität gegenüber weit entfernten Abläufen zugunsten einer größeren Adaptivität und Flexibilität gegenüber dem lokalen Geschehen.

  • 4) Die Optimierung der Steuerung in den Kernbereichen findet in bestimmten Zeitschritten statt, beispielsweise in Zeitschritten, die vergleichbar mit der Umschaltzeit &tgr; sind.
  • 5) Bei der Optimierung im Inneren eines Kernbereichs wird die während des Planungshorizonts T' vorgesehene Steuerung im zugehörigen Randbereich normalerweise nicht geändert. Festzeitschaltungen oder anderweitig vorgegebene Steuerungen an einzelnen Knoten werden bei der Optimierung als zeitabhängige, aber nicht veränderbare Randbedingung berücksichtigt.
  • 6) Alle Knoten, im Bedarfsfall sogar die einzelnen Abfertigungseinheiten (Lichtsignalanlagen), bekommen vom Subsystem n abhängige Gewichte w nij zugewiesen, deren Größe in 2 durch die Länge der vertikalen Balken an den Knoten der gestrichelt dargestellten Straßen illustriert ist. Erfindungsgemäß spielt die Wahl der Gewichte eine entscheidende Rolle für die Performance bzw. Güte der Lösung im Gesamtsystem und allen Kernbereichen. Als Beispiel nehmen wir im Folgenden an, dass die Gewichte im Inneren des Kernbereichs gleich 1 und außerhalb des jeweils dezentral optimierten Kern- und Rand-Bereichs gleich 0 gesetzt werden. Letzteres macht das Optimierungsverfahren erheblich effizienter. Zur weiteren Erläuterung diskutieren wir nun drei beispielhafte Spezifikationen der Gewichte im Randbereich eines Kernbereichs:

    a) Werden die Gewichte im Randbereich gleich 0 gesetzt, dann gibt es bei der Optimierung keine Rücksichtnahme auf benachbarte Kernbereiche. Eine Koordination zwischen Nachbarbereichen ist damit unwahrscheinlich und die erwartete Lösung fernab vom Systemoptimum. Diese Optimierung könnte man als „egoistische lokale Kontrolle” bezeichnen und mit „Kleinstaaterei” vergleichen.

    b) Die Gewichte im Randbereich werden wie innerhalb des jeweils betrachteten Kernbereichs (gleich 1) gewählt, so wie dies bei konventionellen Parallelisierungsalgorithmen mit der Halomethode geschieht, wobei der Halo dem Randbereich entspricht: Für diesen Fall wird eine große Sensitivität gegenüber weit entfernten Geschehnissen erwartet, welche die Flexibilität der Reaktion auf lokale Ereignisse einschränkt. Darüber hinaus kann es geschehen, dass sich die Optimierung an eine Steuerung im Randbereich adaptiert, die unter Umständen bereits im nächsten Zeitschritt revidiert wird, was eine wirksame Koordination untergräbt. Derartige Probleme treten oft dann auf, wenn sich mehrere Prozesse auf der gleichen Zeitskala aneinander anzupassen versuchen.

    c) Wir schlagen daher vor, die Gewichte im Randbereich so zu wählen, dass sie in geeigneter Weise mit wachsendem Abstand vom jeweiligen Kernbereich auf 0 abfallen, also umso kleiner sind, je länger Einheiten benötigen, um in den Kernbereich zu gelangen. Dies führt zur Rücksichtnahme auf benachbarte Kernbereiche. Das heißt, suboptimale Lösungen (wie zusätzliche Wartezeiten) werden unter Umständen dann in Kauf genommen, wenn sie in den Randbereichen überkompensiert werden. Dieser Optimierungsansatz fördert die Koordination zwischen Nachbarbereichen und synchronisierte Steuerungen. Er kann als „altruistische dezentrale Steuerung” bezeichnet werden und führt erfindungsgemäß zu nahezu systemoptimalen Zuständen. Weit entfernte Geschehnisse haben dabei einen geringen Einfluss auf das lokale Geschehen, während die lokale Situation und die Situation in Nachbarbereichen berücksichtigt wird. Ein weiterer Vorteil ist, dass im Unterschied zu Variante b) eine leichte Verschiebung der Kernbereiche überwiegend zu ähnlichen Lösungen führt. Die Spezifikation der Kernbereiche wirkt sich also nicht so willkürlich wie bei der Vorgehensweise b) aus. Aus ähnlichen Gründen wird die Revidierungsproblematik des Verfahrens b) reduziert.
  • 7) Die lokale (dezentrale) Optimierung in den Kernbereichen erfolgt sinnvollerweise anhand eines datenbankgestützten Verfahrens. In der Datenbank sind (optional) eine Festzeitsteuerung sowie eine bestimmte Anzahl B der besten bisherigen Lichtsignalsteuerungen hinterlegt, und zwar in einer Vorzugsausführung in Abhängigkeit von Parametern, welche die Situation im jeweiligen Subnetzwerk charakterisieren, wie etwa dem Verkehrsaufkommen im Kern- oder Randbereich oder dem mittleren Füllgrad
    der Streckenabschnitte. Derartige Parameter können verfahrensbegleitend erhoben werden, beispielsweise durch exponentielle oder gleitende Mittelung von Simulations- oder Messwerten, durch in der Datenbank hinterlegte Erfahrungswerte über die Verkehrssituation an vergleichbaren Tagen oder als (Fit-)Funktion bestimmter Simulations- oder Messwerte.

Diese in der Datenbank hinterlegten Steuerungen stellen den Ausgangspunkt der Erzeugung alternativer Steuerungen durch Variation einzelner Steuerungsparameter dar. Fällt ihre Bewertung besser aus als die Bt-beste in der Datenbank hinterlegte Steuerung aus, so ersetzt sie diese, vorausgesetzt die Lösung ist vorschriftsgemäß oder technisch möglich. Andernfalls wird sie verworfen.

Mit einer solchen Verfahrensweise wird allmählich ein Lerneffekt erzielt, d. h. die vorgehaltene Ausgangsmenge guter Lösungen wird immer besser und stabilisiert sich schließlich, so dass sich eine gewisse Regelmäßigkeit in der Steuerung des Systems einstellt. Diese ist erwünscht, damit sich Fahrer in ihrem Routenwahlverhalten auf die Steuerung einstellen können. Weiterhin hat die Variation der besten Steuerungsvarianten den Vorteil, dass man bei der Optimierung nicht jedes Mal von vorne anfängt (wie etwa bei enumerativen Verfahren), sondern die knappe Optimierungszeit wesentlich besser nutzen kann, was die Optimierung größerer Kernbereiche und somit die Gewinnung besserer Lösungen erlaubt.

In der beschriebenen Weise lernt das Steuerungsverfahren immer bessere Steuerungsvarianten, die von der Netzwerktopologie und von den Zustandsvariablen des Systems abhängen, aber in jedem Zeitpunkt flexibel auf die jeweilige Verkehrslage vor Ort reagiert.

  • 8) Gestartet wird bei der Optimierung mit einer geeigneten Festzeitsteuerung, welche die Rückfallebene ist (falls Sensoren ausfallen). In jedem Zeittakt werden aber neue Varianten durchprobiert. Bei der Variation der Steuerung werden für die nicht mit einem festen Programm gesteuerten Knoten des Kernbereichs beispielsweise folgende Steuerungsparameter variiert: Umschaltzeitpunkt, nächste bediente Signalgruppe, etc., auf einer langsameren Zeitskala eventuell auch Parameter wie der Planungs- bzw. Optimierungszeithorizont usw.

Zur numerischen Effizienzsteigerung der Optimierung werden erfindungsgemäß Varianten, die besonders aussichtsreich sind, zuerst erzeugt und getestet, da die Anzahl der in jedem Zeitschritt testbaren Varianten durch die Rechenleistung beschränkt ist. Dies gilt beispielsweise a) für die Auswahl der Signalgruppen, b) für die Variation der Grünzeiten und c) für die Variation der Umschaltzeitpunkte:

  • a) Zunächst werden zur Reduktion der Komplexität die Kombinationen der Grünphasen an allen benachbarten Ampeln einer Kreuzung auf die kompatiblen, das heißt konflikt- bzw. garantiert unfallfreien Grünschaltungen eingeschränkt.

Die Zahl der Grünphasen bzw. Schaltkombinationen lässt sich deutlich reduzieren, wenn man lediglich diejenigen betrachtet, bei denen nur kompatible Flüsse gemeinsam abgefertigt werden, d. h. grün zugewiesen bekommen. Flüsse sind kompatibel, wenn sich ihre Fahrlinien nicht kreuzen. Diese ”sicheren” Kombinationen dürfen jedoch nicht mit den herkömmlichen Ampelphasen verwechselt werden, wo kompatible Flüsse zwangsweise gemeinsam bedient werden. Hier ist es beispielsweise auch möglich, nur einer einzigen rechts abbiegenden Spur grün zu geben, während alle anderen Ampeln rot zeigen. Dies ist dann sinnvoll, wenn Streckenkapazitäten für andere Verkehrsströme dringender erforderlich sind und somit besser freigehalten (reserviert) werden. Auch der Zustand ”alle Ampeln rot” ist sicher und damit erlaubt. Er kann sinnvoll sein, um ein schnelleres Freischalten für eintreffende Einzelfahrzeuge zu ermöglichen. Die Menge aller sicheren (kompatiblen) Schaltkombinationen findet man, indem man aus der Liste aller möglichen Kombinationen diejenigen eliminiert, bei denen inkompatible Flüsse gemeinsam grün haben.

  • b) Weiterhin kann ein guter Startwert für die Grünzeitdauer nach einem Nachfrage- und Angebotsprinzip festgelegt werden:

    Hierzu wird für einen einzelnen Knoten ein Optimierungs-Prinzip herangezogen, welches ermittelt, wie viele Fahrzeuge in einer bestimmten Grünzeit abgefertigt werden könnten. Dabei werden Wechselwirkungseffekte zwischen benachbarten Knoten zunächst vernachlässigt. Jedoch wird der verfügbare Platz in den Anschluss-Straßen durch zeitabhängige Spezifikation der Funktion Qdepi(t') berücksichtigt (s. Punkt 9). Die Anzahl N'i(t) der Fahrzeuge, die den Straßenabschnitt vom gegenwärtigen Zeitpunkt t0 bis zum Zeitpunkt t verlassen, lässt sich abschätzen als
    wobei Ii die Anzahl der Spuren ist, die in die gleiche Richtung führen, und Qdepi(t') der den Straßenabschnitt i zum Zeitpunkt t' verlassende Fahrzeugfluss. Qdepi(t') ist gleich 0, wenn in einem der stromabwärtigen Straßenabschnitte keine Kapazität verfügbar ist.

Im Vergleich dazu lässt sich die Anzahl Ni(t) der Fahrzeuge, die den Straßenabschnitt vom gegenwärtigen Zeitpunkt t0 bis zum Zeitpunkt t verlassen, wenn zum Zeitpunkt t0 auf gelb und zum Zeitpunkt t0 + &tgr; auf grün geschaltet würde, abschätzen als

wobei &tgr; die Schaltzeit bezeichnet. Die Formel
reflektiert den Schaltzeitverlust, d. h. die Anzahl der Fahrzeuge, die durch das Umschalten zwischen dem Abfertigen verschiedener Richtungen (die Gelbzeit/Verlustzeit &tgr;) weniger abgefertigt würden.

Es werden nun die Prognosewerte für die bis zum Zeitpunkt t abfertigbaren Fahrzeugzahlen über alle gleichzeitig abfertigbaren Verkehrsströme i ∊ I, d. h. alle kompatiblen Grünphasen, summiert:

Für eine einzelne Kreuzung ist dann Folgendes festzustellen: Wenn die Signalgruppe J (d. h. die entsprechende Kombination kompatibler Grünzeiten) zum gegenwärtigen Zeitpunkt t0 auf grün geschaltet würde, so würde sie bis zum Zeitpunkt t die größtmögliche Anzahl von Fahrzeugen abfertigen, wenn der Ausdruck NJ(t) – N'I(t) = NJ(t) – NI(t) – &Dgr;NI(t0)(5) unter allen möglichen Signalgruppen J den maximalen Wert annimmt. Solange der Ausdruck negativ ist, ist es am besten, die aktuell aktive (d. h. freigeschaltete) Signalgruppe weiterzubetreiben. Zum Umschalten von der Bedienung von Signalgruppe I auf Signalgruppe J muss also der Wert NJ(t) mindestens um den Schwellwert &Dgr;NI(t0) besser ausfallen als der Wert NI(t), um die Umschaltverluste auszugleichen. Die Umschaltverluste &Dgr;NI(t0) müssen daher überkompensiert werden, und die Signalgruppe muss überdies die meisten Fahrzeuge bis zum Zeitpunkt t abfertigen können.

Zur Koordination mit benachbarten Kreuzungen ist es unter Umständen sinnvoll, auch zweit- und drittbeste Lösungen mit zu berücksichtigen. Dies begründet sich auch dadurch, dass derzeit noch die Wahl des Zeithorizonts &Dgr;t = t – t0 offen ist, von dem die beste Wahl der Signalgruppe abhängen kann.

Es werden daher die Abfertigungsraten von Fahrzeugen pro Zeiteinheit bestimmt, d. h. die Durchsätze

Demgegenüber steht der Wert

für eine Fortsetzung der laufenden Grünphasen. Durch den Zusatzterm &Dgr;Ni(t0)/(t – t0) gibt es immer eine gewisse Tendenz zur Fortsetzung laufender Grünphasen, die aber nicht bedingungslos ist, sondern Umschaltverluste genau abwägt.

Die für verschiedene Signalgruppen J und Zeitpunkte t resultierenden Werte QJ(t) und Q'I(t) können in eine Rangfolge gebracht werden. Sie bestimmt die Präferenz für die Wahl verschiedener Signalgruppen, d. h. ihre Priorität aus Sicht eines einzelnen Knotens. Berücksichtigt werden beispielsweise alle Signalgruppen, deren Wert Q'I(t) bzw. QJ(t) zu einem der Zeitpunkte t um nicht mehr als einen bestimmten Prozentsatz &egr; unter der besten Lösung liegt. Es kann nämlich vernünftig sein, eine Signalgruppe mit hoher, aber nicht höchster Priorität zu wählen, wenn dadurch eine Koordination mit Ampelschaltungen an benachbarten Knoten erreicht werden kann. Dadurch wird die Synchronisation zwischen benachbarten Knoten erleichtert. Daher werden für eine Grünschaltung alle Signalgruppen hoher Priorität in Betracht gezogen. Sehr niedrige Werte von Q'i(t) = N'i(t)/(t – t0) geben dagegen Anlass, die Bedienung des Straßenabschnitts i abzubrechen, d. h. die entsprechende Ampel rot zu schalten.

Die Erfindung ist nicht beschränkt auf das hier ausgeführte Ausführungsbeispiel zur Identifikation besonders aussichtsreicher Steuerungen von Einzelknoten.

  • c) Nur dann, wenn eine kleine Verzögerung eines Umschaltzeitpunkts zu einer Verbesserung geführt hat, wird eine weitere Verzögerung getestet. Eine Variation des Endes der Grünzeitdauer beginnt sinnvollerweise mit der mittleren, verkehrszustandabhängigen Grünzeitdauer in der Vergangenheit.
  • 9) Zu gegebenen Randbedingungen und angenommenen Steuerungen wird die Verkehrsdynamik im Subsystem anhand eines geeigneten Verkehrsmodells unter Berücksichtigung der Abzweigewahrscheinlichkeiten der Fahrzeuge ermittelt, für deren Bestimmung Sensormessungen oder gängige Schätzmodelle herangezogen werden können. Wenn das Verkehrsaufkommen in den Randbereichen und Beziehungen für die Abzweigewahrscheinlichkeiten &agr;ij(t) bekannt sind bzw. geeignet vorausgesetzt werden, lassen sich die Verkehrsströme im Netz über kurze Zeiträume für jede beliebige Kombination und Schaltfolge von Lichtsignalen prognostizieren. Hierzu wurden in der Vergangenheit verschiedene Modelle entwickelt wie Fahrzeugfolgemodelle, zelluläre Automaten, fluiddynamische Verkehrsmodelle usw.

Beispielsweise kann man den zeitabhängigen Verkehrsfluss in Netzwerken mit folgenden Formeln (oder mit Formeln ähnlichen Inhalts oder ähnlicher Wirkung) näherungsweise beschreiben: Zunächst unterteilt man das Netzwerk in homogene Straßenabschnitte (Richtungsfahrbahnen) i mit einer konstanten Spurzahl Ii. Der Verkehrsfluss zum Zeitpunkt t einfahrender Fahrzeuge sei durch Qarri(t) bezeichnet und der Verkehrsfluss der den Streckenabschnitt verlassenden Fahrzeuge durch Qdepi(t) . Die Abzweigewahrscheinlichkeit (relative Abzweigehäufigkeit) zum Zeitpunkt t von Straßenabschnitt i in einen benachbarten Abschnitt j sei &agr;ij(t) ≥ 0. Dann gilt wegen der Erhaltung der Fahrzeugzahl:

Durch eine einfache Verallgemeinerung ist auch die Unterscheidung von Fahrzeugen mit verschiedenen Zielen d möglich.

Der tatsächliche Zufluss Qarri(t) ist durch die maximal verfügbare bzw. angebotene Kapazität Qarr,poti(t) begrenzt (das ”Angebot”), der tatsächliche Abfluss Qdepi(t) durch die maximal nachgefragte Kapazität Qdep,poti(t) (die ”Nachfrage”). Realisiert wird an einem Knoten bestenfalls das Minimum von ”Angebot” und ”Nachfrage”, d. h.

für alle j. Daraus kann man zusammen mit 0 ≤ Qarrj(t) ≤ Qarr,potj(t), 0 ≤ Qdepi(t) ≤ Qdep,poti(t) und Gleichung (8) geeignete Werte Qdepi(t) bestimmen, z. B. durch Lösung eines Gleichungssystems. Dabei ermittelt man die angebotene Kapazität pro Spur nach der Formel:
wobei sich die am weitesten vom stromabwärtigen Ende des Straßenabschnitts i entfernt stehenden Fahrzeuge am Ort li(t) befinden. Wenn auf dem Abschnitt i keine Fahrzeuge stehen, also freier Verkehr herrscht (li(t) = 0), dann ist der Ausfluss aus dem Streckenabschnitt i pro Spur durch den Zufluss Qarri von Fahrzeugen zum Zeitpunkt t – Li/V0i gegeben. Hierbei bezeichnet Li die Länge und V 0i die zulässige Höchstgeschwindigkeit sowie Li/V0i die freie (unbehinderte) Fahrtzeit auf Streckenabschnitt i. Falls es eine Warteschlange im Streckenabschnitt i gibt (li(t) > 0), bestimmt der maximale Ausfluss Q maxi aus dem Stau pro Spur den Verkehrsfluss von Fahrzeugen, die den Straßenabschnitt i verlassen. Für die angebotene Kapazität pro Spur gilt:

Demzufolge ist der potenzielle Zufluss gleich null, wenn die Ampel von Streckenabschnitt i zum Streckenabschnitt j nicht freigeschaltet ist (&ggr;ij(t) = 0). Bei Freischaltung/grüner Ampel (&ggr;ij(t) = 1) kann ein maximaler Verkehrsfluss Q maxi vom Streckenabschnitt j aufgenommen werden, wenn sich der Stau nicht bis zum Ende der Strecke ausdehnt (lj(t) < Lj). Wenn jedoch lj(t) = Lj ist, wird der maximale Zufluss durch den Abfluss Q depj aus dem Streckenstück j zur Zeit t – Lj/|c| bestimmt, wobei c ≈ –15 km/h die Ausbreitungsgeschwindigkeit von Störungen im behinderten Verkehr ist.

Die zeitliche Entwicklung der Lage des Stauendes kann mit folgender Formel berechnet werden:

Dabei ist li(t) ≤ Li die Entfernung zum stromabwärtigen Ende des Straßenabschnitts i, V 0i die zulässige Höchstgeschwindigkeit, &tgr;' = 1.8 s die sichere Folgezeit und &rgr;jam die Fahrzeugdichte pro Spur im gestauten Verkehr (z. B. vor einer roten Ampel).

Statt der oben genannten (Nährungs-)Formeln können auch Formeln ähnlichen Inhalts oder ähnlicher Wirkung verwendet werden. Schließlich ist die maximale Aufnahmekapazität des Streckenstücks i für Fahrzeuge bestimmt durch die Spurzahl Ii und die Länge Li eines Straßenabschnitts i. Sie wird berechnet durch die Formel IiLi&rgr;jam(13)

  • 10) Soweit zur Berechnung der zeitabhängigen Verkehrsströme in Abhängigkeit von den Ampelschaltungen, die durch die zeitabhängigen Werte von &ggr;ij(t) gegeben sind. Wir kommen nun zur Spezifikation des Bewertungs- und Auswahlverfahrens leistungsfähiger Lichtsignalsteuerungen im Rahmen des vorgeschlagenen lokalen Optimierungsansatzes, d. h. im Rahmen des dezentralen Steuerungsverfahrens.

Ist das Steuerungsziel die Optimierung des Durchsatzes der Fahrzeuge, die zwischen dem Zeitpunkt t0 und t0 + T' von Lichtsignalanlagen abgefertigt werden, dann maximiert man beispielsweise den Ausdruck:

wobei sich die Summe über alle durch Lichtsignalanlagen abgefertigten Wechsel von einem Streckenabschnitt i in einen Streckenabschnitt j erstreckt. Wenn der Streckenabschnitt i nicht in den Streckenabschnitt j führt, gilt &agr;ij = 0.

Statt einer globalen, d. h. systemweiten Optimierung, die rechentechnisch nicht zu bewältigen ist, wird erfindungsgemäß mit dem dezentralen Steuerungsverfahren die Maximierung des Performancemaßes

im Subnetzwerk n verfolgt. Dabei bezeichnet wnij ≥ 0 das Gewicht, wie stark die Ampelsteuerung für den Wechsel von Streckenabschnitt i in den Streckenabschnitt j bewertet wird (s. Punkt 6). Wählt man w nij abfallend, wie dies unter Punkt 6c) ausgeführt und in 2 symbolisch dargestellt ist, so wird Rücksicht auf den Durchsatz an benachbarten Knoten genommen, und es kann in der Nachbarschaft eine Durchsatz-steigernde Kooperation entstehen. Das Performancemaß (15) lässt sich auf beliebige Optimierungskriterien verallgemeinern:

Hierbei bezeichnet fnij(t) eine beliebige Bewertungs- bzw. Zielfunktion von Simulations- oder Messgrößen der Kanten i und j oder des sie verbindenden Knotens zum Zeitpunkt t. Berücksichtigt werden können beispielsweise

  • a) die Anzahl der wartenden Einheiten (Warteschlangenlänge),
  • b) die Bedien- und/oder Wartezeiten,
  • c) die Anzahl der eintreffenden Einheiten,
  • d) die Anzahl der abgefertigten Einheiten,
  • e) die potenzielle Abfertigungskapazität,
  • f) die Pufferkapazität,
  • g) die Priorität der Einheiten (z. B. Rettungsfahrzeuge, ÖPNV),
  • h) eine bevorzugte Abfertigungsmenge,
  • i) der Energieverbrauch oder die Kosten der Abfertigung,
  • k) die Nähe zum Ziel.

Zur priorisierten Entfernung zielnaher Fahrzeuge aus dem System (siehe Punkt k) können beispielsweise zielnahe Fahrzeuge stärker gewichtet werden (sofern der Lichtsignalsteuerung entsprechende Informationen zur Verfügung gestellt werden, z. B. durch Informationsaustausch mit Zielführungssystemen von Fahrzeugen). Zu diesem Zweck könnte Formel (2) ersetzt werden durch:

Dabei meint D die mittlere Fahrtstrecke der Fahrzeuge im Streckenabschnitt i zu ihrem Ziel und Dd die Fahrtstrecke der Fahrzeuge in Streckenabschnitt i mit dem Ziel d. Qdepid(t) ist der Fahrzeugfluss von Fahrzeugen mit Ziel d, die den Streckenabschnitt i zum Zeitpunkt t verlassen. Alternativ zur mittleren Fahrtstrecke kann auch die erwartete Fahrtzeit gewählt werden. Es kommen aber auch andere Formeln mit vergleichbarer Wirkung in Frage.

  • 11) Das vorgeschlagene Steuerungsverfahren sieht vor, viele Größen auf mehrere Weisen zu berechnen, um eine zuverlässigere Gesamtschätzung x zu erreichen. Beispielsweise können die Abzweigewahrscheinlichkeiten aus benachbarten Sensordaten (den relativen Abzweigehäufigkeiten), aus Verkehrssimulationen und aus Routenwahlmodellen auf der Basis von Daten über die Ziele der Fahrer ermittelt werden. Weiterhin wird vorgeschlagen, bei der Schätzung der Abfertigungszeiten einer Einheit an nahe gelegenen Kanten Messwerte und/oder Kurzzeitprognosen, an entfernten Kanten dagegen historische Messwerte für vergleichbare Situationen stärker zu gewichten.

Zur redundanten Gesamtschätzung x einer Größe x werden die einzelnen Simulations- oder Messwerte xk verschiedener Verfahren k mit ihrer Zuverlässigkeit zk (z. B. dem Inversen der Standardabweichung) gewichtet:

Die Nichtverfügbarkeit einer dieser Datenquellen gefährdet die Funktionsfähigkeit der Steuerung nicht, was sie robust gegenüber Störungen macht. Fällt beispielsweise die n-te Messung oder Datenquelle aus, erfolgt die Bestimmung über:

entsprechend der Zuverlässigkeit zn = 0 des n-ten Werts.
  • 12) Die Beschränkung der maximalen Grün- und Zykluszeit bei extrem hohem Verkehrsaufkommen erfolgt erforderlichenfalls durch Kontingentierung. Im Prinzip wird hierzu die Grünzeit künstlich beendet, wenn sie einen bestimmten Bruchteil u 0i einer maximalen Zykluszeit T innerhalb eines Zeitintervalls T überschreitet. Der Bruchteil u 0i kann beispielsweise proportional zum relativen Verkehrsaufkommen oder entsprechend Nutzer- oder systemoptimaler Gesichtspunkte spezifiziert gewählt werden.
  • 13) Besonders vorteilhaft ist das Betreiben der Anlage zusammen mit einem grünen Pfeil für Rechtsabbieger, um eine parallele Einzelabfertigung von Fahrzeugen in geeigneten Zeitlücken auch während des Bündelbetriebs bei starkem Verkehrsaufkommen zuzulassen. Dies ist vor allem für Nebenstraßen mit einer kleinen Spurzahl von Bedeutung.
  • 14) Eine stärke Berücksichtigung von Nebenstraßen i mit kleiner Spurzahl Ii kann erreicht werden, indem der Parameter Ii in den Optimierungsformeln künstlich erhöht wird. Insbesondere wird die Bedeutung der Spurzahl ignoriert, indem man in den Optimierungsformeln generell Ii = 1 setzt. Dies führt zu einer gleichrangigen Behandlung von Haupt- und Nebenstraßen, wobei sich jedoch die durchschnittlichen Fahrtzeiten erhöhen.
  • 15) Nachdem die optimale Netzwerksteuerung bestimmt wurde, kann zusätzlich auch die Dynamik der einzelnen Einheiten entlang der Kanten optimiert werden, um beispielsweise einen vermeidbaren Kraftstoffverbrauch durch überflüssiges Abbremsen und Beschleunigen zu vermeiden. Dies setzt voraus, dass die Einheiten Informationen und/oder Anweisungen seitens der Signalsteuerung entgegennehmen, etwa mittels Fahrzeug-Infrastruktur-Kommunikation.
  • 16) Das unter Punkt 1) bis 14) skizzierte Optimierungsverfahren kann so modifiziert werden, dass es sich zur Optimierung der Netzwerkstruktur eignet. Dazu ergänzt oder entfernt man Kanten oder Knoten im System und/oder ihre Spurzahl bzw. Kapazität, eventuell auch Abbiegeverbote. Eine derartige Optimierung hat vor allem verkehrsplanerische Anwendungen und kann auch offline durchgeführt werden.

Die Eigenschaften der erfindungsgemäß vorgeschlagenen Verkehrssteuerung lassen sich wie folgt beschreiben:

Das Schema und die Reihenfolge der Bedienung von mobilen Einheiten (Fahrzeugen oder Fußgängern) wird auf der Basis einer Kurzzeitverkehrsprognose unter angenommenen Schaltzuständen der benachbarten Ampeln in einem bestimmten ”Einflussbereich” (Subnetzwerk = Kern- und Randbereich) ermittelt, d. h. das Optimierungsprinzip wird nur lokal angewandt und definiert damit ein dezentrales Steuerungsprinzip.

Dadurch erfordert nur dieser Schritt eine kombinatorische Optimierung, und zwar nur für kurze Zeiträume und für wenige benachbarte Lichtsignalanlagen. Die Entkopplung weit entfernter Steuerungsbereiche und die Koordination von Nachbarbereichen erfolgt durch geringere Gewichtung der weiter entfernten Knoten im Randbereich. Ansonsten könnte eine lokale Variation einer Ampelschaltung bei globaler Optimierung eine Lichtsignalanlage am anderen Ende der Stadt beeinflussen. Dies würde eine extreme Sensitivität der Lichtsignalsteuerung gegenüber kleinen Störungen mit sich bringen, welche zulasten der Vorhersagbarkeit des Systemverhaltens (z. B. der Abzweigewahrscheinlichkeiten) ginge und damit zu chaotischen Reaktionen von Fahrern auf die unvorhersagbar variierende Schaltungsdynamik führen könnte. Dies hätte wiederum eine schlechte Gesamtperformance des Systems zur Folge. Ein lokales Steuerungsprinzip erreicht also eine geringere Sensitivität (größere Robustheit) gegenüber weit entfernten Abläufen zugunsten einer größeren Flexibilität, auf die Situation und Abläufe vor Ort zu reagieren.

Die Vorgehensweise bei der dezentralen Steuerung ist so, dass in regelmäßigen Zeitschritten, zum Beispiel alle 2 Sekunden, parallele Schaltentscheidungen in allen Bereichen n getroffen werden, in denen ein vorzugsweise drahtloser Informationsaustausch zwischen benachbarten Ampelsteuerungen erfolgt. Die Schaltentscheidungen basieren auf dem Vergleich alternativer Steuerungsszenarien während eines Zeithorizonts der maximalen Länge t – t0 = T', der situationsabhängig gewählt werden kann. Ein sinnvoller Zeithorizont entspricht etwa der mittleren Grünzeit plus dem 2- bis 3-fachen der Standardabweichung der Grünzeit. Dieser Wert kann als exponentieller oder gleitender Mittelwert über ein Zeitfenster, als Erfahrungswert oder als Funktion anderer Messgrößen, wie dem Verkehrsaufkommen oder mittleren Füllgrad der Streckenabschnitte i des Bereichs n, gewählt werden.

An den benachbarten Knotenpunkten eines Optimierungsbereichs werden nicht alle denkbaren Kombinationen von Grünschaltungen miteinander kombiniert, sondern nur Schaltungen hoher Priorität, da unwahrscheinlich ist, dass eine sehr ungünstige Schaltung an einem Knoten durch eine sehr viel günstigere Schaltung an einem Nachbarknoten kompensiert werden kann. Dies macht das Optimierungsverfahren effizient, zusammen mit der Beschränkung auf kleine Subsysteme (Bereiche) von benachbarten Lichtsignalanlagen. Die Überschneidung der Randbereiche mit benachbarten Kernbereichen und die abfallende Gewichtung zum Rand dieser Bereiche hin macht es wahrscheinlich, dass die für benachbarte Knoten ermittelten Schaltprogramme meistens gut miteinander kompatibel sind, die Ampeln sich also kooperativ verhalten. Beim Vergleich alternativer Steuerungsprogramme werden mögliche Umschaltverluste entsprechend Formel (3) berücksichtigt. Dadurch ist ein häufiges Schalten nur bei geringen Verkehrsflüssen wahrscheinlich, wo Umschaltverluste unbedeutend sind. Bei größeren Verkehrsaufkommen sorgen sie für eine Tendenz zur Fortsetzung einer bestehenden Grünzeit, solange Fahrzeuge effizient abgefertigt werden.

Wenn das Verkehrsaufkommen gering ist, entspricht ein Einzelfahrzeug bereits der längsten ”Warteschlange” und kann daher allein die Grünfreigabe erwirken. Bei geringem Verkehrsaufkommen werden die Einheiten also direkt bei ihrer Ankunft einzeln abgefertigt. Zugunsten einer Verringerung der Reaktions- bzw. Umschaltzeiten ist es sinnvoll, den Grundzustand der Ampeln rot zu wählen, wenn für ein Zeitintervall, das größer als die Umschaltzeit &tgr; ist, kein weiteres Fahrzeug folgt.

Das Zurückschalten auf eine rote Ampel nach dem Passieren eines Fahrzeugs erlaubt eine schnellere Bedienung eines Fahrzeugs aus einer anderen Richtung.

Damit ein Fahrzeug vor seiner Einzelabfertigung nicht genötigt ist, an der Ampel abzubremsen, muss das Fahrzeug so weit stromaufwärts der Ampel detektiert werden, dass genügend Zeit zum Umschalten bleibt. Beträgt die zulässige Höchstgeschwindigkeit des Fahrzeugs V0 und die Umschaltzeit (Gelbphase) &tgr;, so muss der Sensor die passierenden Fahrzeuge in einem Abstand l = V0&tgr; von der Lichtsignalanlage detektieren. Beim Passieren des Querschnitts im Abstand l müsste die Umschaltung sofort begonnen werden. Observiert der Sensor die Verkehrssituation sogar im Abstand l' > l, so muss spätestens nach einem Zeitintervall von (l' – l)/V0 umgeschaltet werden. Der Umschaltzeitpunkt könnte von der tatsächlich gemessenen Fahrzeuggeschwindigkeit &ngr; abhängig gemacht werden und wäre idealerweise (l' – l)/&ngr;, um ungenutzte Grünzeiten zu minimieren.

Bei größerem Verkehrsaufkommen, wenn eine Einzelabfertigung wegen nahezu gleichzeitiger bzw. zeitnaher Ankünfte von Fahrzeugen nicht mehr konfliktfrei möglich ist, bewirkt das vorgeschlagene Steuerungsverfahren eine Bündelung von Einheiten durch längere Grün- und Rotphasen nach dem Prinzip der Minimierung der Umschaltverluste. Das Bündelungsprinzip resultiert automatisch aus der größeren Abfertigungsrate, die sich bei größeren Verkehrsaufkommen durch ein Abfertigen gleichartiger Einheiten ergibt (im Vergleich zur Einzelabfertigung unterschiedlicher Einheiten, die mit Umschalt- und Verlustzeiten verbunden ist).

Bei Überlastung, d. h. wenn eine weitere Zunahme von Einheiten im System dessen Durchsatz reduziert, kann das Prinzip der Minimierung der Umschaltverluste mit der priorisierten Behandlung zielnaher Fahrzeuge kombiniert werden, um diese so schnell wie möglich aus dem System zu entfernen und somit Platz für andere Fahrzeuge zu schaffen, d. h. Staus und Warteschlangen zu reduzieren.

Die oben beispielhaft ausgeführte Lichtsignalsteuerung verfolgt primär das Ziel der Durchsatzmaximierung, um damit die Gesamtwartezeiten zu minimieren und die Gesamtfahrtzeiten zu minimieren. Als Ziel wurde also angenommen, dass möglichst viele Fahrzeuge möglichst schnell voran kommen. Das vorgeschlagene Verfahren zur Schaltung und Koordination der Lichtsignalanlagen löst durch Performancevergleich von Kurzzeit-Verkehrsprognosen für alternative Steuerungsszenarien unter anderem folgende Zielkonflikte:

  • • Einerseits möchte man längstmögliche Grünphasen zur Reduktion von Schaltzeitverlusten, andererseits eine ”sofortige” Reaktion auf Vorgänge an benachbarten Ampeln, wie sie zur Etablierung einer grünen Welle erforderlich ist.
  • • Trotz eines Mangels an Pufferkapazität in folgenden Strecken-Abschnitten müssen wichtige Ströme priorisiert abgefertigt werden, deren Nichtabfertigung zur Blockade anderer Ströme führen würde. Dies kann gegebenenfalls die vorzeitige Beendigung der Grünzeit erforderlich machen, zumal die Systemperformance ab einem bestimmten Füllgrad abnehmen kann.

Die erfindungsgemäße Steuerung, welche die typischen Merkmale einer Regelung aufweist, löst diese Zielkonflikte dadurch, dass Schaltzeitverluste durch ein vorzeitiges Umschalten zugunsten einer Synchronisation von benachbarten Grünphasen (Grüne Welle) durch eine prognostizierte höhere Abfertigung an den betroffenen Nachbarknoten überkompensiert werden. Eine derartige Koordination benachbarter Kreuzungen ergibt sich automatisch durch die Berücksichtigung der Verkehrsströme an benachbarten Kreuzungen. In gewisser Weise werden die Koordinationsgewinne in Form von zusätzlich abgefertigten Fahrzeugen anteilig den benachbarten Knoten gutgeschrieben, die bei einer Synchronisation gegenüber ihrer optimalen Steuerung Verluste hinnehmen müssen. Wenn diese ”Gutschrift” die Verluste übertrifft, beteiligt sich die betroffene Lichtsignalanlage an einer koordinierten Schaltung.

Ein weiterer Vorzug der erfindungsgemäßen Steuerung ist ihre Robustheit und Ausfallsicherheit durch Redundanz: Wenn beispielsweise der Sensorinput einer Lichtsignalsteuerung ausfällt, so würden die Steuereinheiten beispielsweise automatisch entsprechend einer Festzeitsteuerung gesteuert (Rückfallebene). Genauso können die Abzweigewahrscheinlichkeiten &agr;ij(t) und die prognostizierten Abfertigungszeiten auf redundante Weise bestimmt werden.

Redundanz wird weiterhin dadurch erreicht, dass bei lokalem Ausfall der Messungen der Verkehrssituation die Daten durch das der Verkehrsprognose zugrunde liegende Simulationsmodell automatisch geschätzt werden. (Nach dem Prinzip der Fahrzeugzahlerhaltung werden Fahrzeuge auf freier Strecke nicht produziert oder vernichtet, so dass Simulationsmodelle aus lokalen Messwerten das dazwischen liegende Verkehrsgeschehen rekonstruieren bzw. voraussagen können.)

Weitere erfindungsgemäße Vorteile bestehen in der selbstständigen Reaktion der Knoten auf unerwartete Vorkommnisse wie Unfälle, Baustellen oder andere nicht vorhersehbare Ereignisse, die den Transport der mobilen Einheiten behindern. Die höhere Flexibilität führt zu Kosteneinsparungen, zumal auf den Aufbau und die Erhaltung einer zentralen Infrastruktur und Datenleitungen im Vergleich mit Verkehrsleitsystemen mit zentralen Verkehrsrechnern verzichtet werden kann. Das dezentrale Steuerungsverfahren kann aber auch in einer eventuell vorhandenen zentralen Infrastruktur umgesetzt werden und bestehende Festzeitsteuerungen oder andere vorgegebene Steuerungsprogramme einzelner Knoten ohne Probleme integrieren. Es ist bei der Informationsgewinnung und dem Datenaustausch jedoch auf die vorteilhafte Nutzung moderner Sensortechnologien und drahtloser Kommunikationsmethoden zugeschnitten.

Schließlich ist hervorzuheben, dass das vorgeschlagene Verfahren besonders adaptiv, flexibel und robust gegenüber lokalen Variationen und Ausfällen im System ist. Außerdem erlaubt es eine einfache und harmonisch auf das Gesamtverkehrssystem abgestimmte, also rücksichtsvolle statt vorbehaltslose Priorisierung des öffentlichen Personennahverkehrs. Hierzu wird ein ÖPNV-Fahrzeug mit einem größeren Gewicht versehen wie ein PKW, z. B. entsprechend der durchschnittlichen Passagierzahl.


Anspruch[de]
Verfahren zur Steuerung des Transports von mobilen Einheiten innerhalb eines Netzwerkes, welches Knoten und Kanten aufweist, wobei das Netzwerk in Kernbereiche n unterteilt wird, denen jeweils ein Randbereich zugeordnet wird, so dass der Kernbereich und der dazugehörige Randbereich jeweils ein zusammenhängendes Subnetzwerk von Knoten und Kanten definieren, wobei die Kanten eine begrenzte Pufferkapazität an aufnehmbaren mobilen Einheiten besitzen und die Knoten oder Kanten mit Datenerfassungselementen ausgestattet sind und die Knoten eine begrenzte Abfertigungskapazität an zu bedienenden mobilen Einheiten haben sowie mit Steuereinheiten ausgestattet sind, für die ein Schaltzustand der Abfertigung von mobilen Einheiten, ein Schaltzustand der Nichtabfertigung und zwischen diesen ein Umschaltzustand vorgesehen sind,

dadurch gekennzeichnet, dass

a die echtzeitfähige Steuerung dezentral und selbstorganisierend in den Steuereinheiten der Knoten oder den Steuereinheiten lokal begrenzter Subnetzwerke erfolgt, wobei die Steuereinheiten benachbarter Knoten oder Subnetzwerke miteinander zum Datenaustausch in Verbindung stehen und wenigstens zwei Knoten die kleinstmögliche Variante von Subnetzwerken darstellen,

b1 Daten aus Voraussagemodellen der lokalen Abfertigungsprozesse aller Knoten des jeweiligen Subnetzwerkes und/oder

b2 Daten von Datenerfassungselementen aller Knoten und der mit ihnen verbundenen Kanten des Subnetzwerkes

c für die lokale Simulation und Optimierung von Schaltzuständen der Steuereinheit zur Ermittlung der Leistungsfähigkeit (Performance) der Knoten oder Subnetzwerke unter Berücksichtigung der Pufferkapazität der Kanten auf der Basis von Modellen für Kurzzeitprognosen bei angenommenen Schaltzuständen benachbarter Knoten eingesetzt werden, wobei

c1 aus mehreren alternativen Steuerungsstrategien hoher Performance für die einzelnen Knoten durch Kombination dieser Steuerungsstrategien eine Auswahl von Steuerungsstrategien für Subnetzwerke generiert werden, die unter dem Gesichtspunkt der Performance besonders vielversprechend sind, wobei

c2 die Kombination der jeweils besten Steuerungsstrategie jedes Einzelknotens des Subnetzwerkes nicht notwendigerweise die beste Steuerungsstrategie für das Subnetzwerk selber darstellt und daher durch einen geeigneten Test, aus der Menge der generierten alternativen Steuerungsstrategien für Subnetzwerke jene identifiziert wird, welche dort die beste Koordination im Sinne der besten Performance im Subnetzwerk zeigt und anschließend

c3 im jeweiligen Kernbereich des Subnetzwerks die Steuerungsstrategie mit der besten Koordination ausgewählt und in entsprechende Schaltzustände für die betroffenen Knoten umgesetzt wird.
Verfahren zur Koordination von vernetzten Abfertigungsprozessen, die um knappe Ressourcen, insbesondere eine frühere Abfertigungszeit innerhalb eines Netzwerkes konkurrieren, welches Knoten und Kanten aufweist und in Kernbereiche n unterteilt wird, denen jeweils ein Randbereich zugeordnet wird, so dass der Kernbereich und der dazugehörige Randbereich jeweils ein zusammenhängendes Subnetzwerk von Knoten und Kanten definieren, wobei die Kanten eine begrenzte Pufferkapazität für zu bedienende Einheiten besitzen und die Knoten oder Kanten mit Datenerfassungselementen ausgestattet sind und die Knoten eine begrenzte Abfertigungskapazität für die Abfertigung von zu bedienenden Einheiten haben sowie Steuereinheiten besitzen, für die ein Zustand der Abfertigung zu bedienender Einheiten, ein Zustand der Nichtabfertigung und zwischen diesen ein Umschalt- oder Übergangszustand auftritt,

dadurch gekennzeichnet, dass

a die echtzeitfähige Koordination der konkurrierenden Abfertigungsprozesse dezentral und selbstorganisierend in den Steuereinheiten der Knoten oder den Steuereinheiten lokal begrenzter Subnetzwerke erfolgt, wobei die Steuereinheiten benachbarter Knoten oder die Steuereinheiten benachbarter Subnetzwerke miteinander zum Datenaustausch in Verbindung stehen und wenigstens zwei Knoten die kleinstmögliche Variante von Subnetzwerken darstellen,

b1 Daten aus Voraussagemodellen der lokalen Prozessabläufe aller Knoten des jeweiligen Subnetzwerkes und/oder

b2 Daten von Datenerfassungselementen aller Knoten und der mit ihnen verbundenen Kanten des Subnetzwerkes

c für die lokale Simulation und Optimierung von Zuständen der Steuereinheit zur Ermittlung der Leistungsfähigkeit (Performance) der Knoten oder Subnetzwerke unter Berücksichtigung der Pufferkapazität der Kanten auf der Basis von Modellen für Kurzzeitprognosen bei angenommenen Zuständen benachbarter Knoten eingesetzt werden, wobei

c1 aus mehreren alternativen Steuerungsstrategien hoher Performance für die einzelnen Knoten durch Kombination dieser Steuerungsstrategien eine Auswahl von Steuerungsstrategien für Subnetzwerke generiert werden, die unter dem Gesichtspunkt der Performance besonders vielversprechend sind, wobei

c2 die Kombination der jeweils besten Steuerungsstrategie jedes Einzelknotens des Subnetzwerkes nicht notwendigerweise die beste Steuerungsstrategie für das Subnetzwerk selber darstellt und daher durch einen geeigneten Test, aus der Menge der generierten alternativen Steuerungsstrategien für Subnetzwerke jene identifiziert wird, welche dort die beste Koordination im Sinne der besten Performance im Subnetzwerk zeigt und anschließend

c3 im jeweiligen Kernbereich des Subnetzwerks die Steuerungsstrategie mit der besten Koordination ausgewählt und in entsprechende Zustände für die betroffenen Knoten umgesetzt wird.
Verfahren nach Anspruch 1 oder 2, dadurch gekennzeichnet, dass die in die lokale Optimierung in Verfahrensschritt c einbezogenen Ziel- bzw. Optimierungskriterien benachbarter Knoten in Abhängigkeit von der Lage im jeweiligen lokalen Optimierungsgebiet (Subnetzwerk) gewichtet werden. Verfahren nach Anspruch 3, dadurch gekennzeichnet, dass die Wichtung bei dem dezentralen Steuerungsverfahren durch die Maximierung des Ausdrucks
erfolgt, wobei fnij(t) eine beliebige Bewertungs- bzw. Zielfunktion von Simulations- oder Messgrößen der Kanten i und j oder des sie verbindenden Knotens zum Zeitpunkt t bezeichnet, w nij die Gewichtung, t0 den Startzeitpunkt der Optimierung und T' den Planungs- bzw. Optimierungszeithorizont.
Verfahren nach einem der Ansprüche 1 bis 4, dadurch gekennzeichnet, dass für die Simulation in Verfahrensschritt c gilt, dass

d1 bei geringer Nachfrage von den zu bedienenden Einheiten an den Knoten ohne Wartezeiten eine einzelne, gleichberechtigte Abfertigung der Einheiten erfolgt, wobei die Anzahl der abgefertigten Einheiten proportional zu den durchschnittlich ankommenden Einheiten ist,

d2 bei hoher Nachfrage mit unvermeidbaren Wartezeiten eine gruppenweise Abfertigung der Einheiten durch längere Schaltphasen nach dem Prinzip der Minimierung der Umschaltverluste erfolgt, wobei

d3 die Minimierung der Umschaltverluste bei Bedarf mit der priorisierten Abfertigung von zielnahen Einheiten kombiniert wird, um diese schnell aus dem Netzwerk zu entfernen,

d4 Schaltzeitverluste durch vorzeitiges Umschalten zugunsten einer Synchronisation von benachbarten Abfertigungsschaltzuständen durch eine prognostizierte höhere Abfertigungskapazität an benachbarten Knoten überkompensiert werden,

d5 Pufferkapazität bei Bedarf in den dem Knoten nachfolgenden Kanten reserviert wird, wobei die pro Kante zugestandene Pufferkapazität adaptiv angepasst wird,

d6 eine Priorisierung, nach der die Einheiten an den Knoten abgefertigt werden auf der Grundlage der Eigenschaften der Einheiten erfolgt und dass

d7 eine Beschränkung der maximalen Dauer der Nichtabfertigung durch Kontingentierung erfolgt.
Verfahren nach einem der Ansprüche 1 bis 5, dadurch gekennzeichnet, dass die lokale (dezentrale) Optimierung ein datenbankgestütztes Verfahren verwendet, in dem eine Anzahl von Steuerungsstrategien hoher Performance in Abhängigkeit von Parametern hinterlegt werden, welche die Situation im jeweiligen Subnetzwerk charakterisieren und verfahrensbegleitend erhoben werden. Verfahren nach einem der Ansprüche 1 bis 6, dadurch gekennzeichnet, dass die Kontingentierung nach nutzer- oder systemoptimalen Gesichtspunkten vorgenommen wird. Verfahren nach einem der Ansprüche 1 bis 7, dadurch gekennzeichnet, dass die erforderlichen Modellparameter durch eine Kombination mehrerer alternativer Simulations- und Messdaten ermittelt werden. Verfahren nach einem der Ansprüche 1 bis 8, dadurch gekennzeichnet, dass bei der Schätzung der voraussichtlichen Abfertigungszeiten einer Einheit an nahegelegenen Kanten Messwerte und/oder Kurzzeitprognosen, an entfernten Kanten dagegen historische Messwerte für vergleichbare Situationen stärker gewichtet werden. Verfahren nach einem der Ansprüche 1 bis 9, dadurch gekennzeichnet, dass bei Fehlen oder Unplausibilität von Messdaten gemäß Verfahrensschritt b2 die fehlenden bzw. unbrauchbaren Daten durch ein Simulations- oder Schätzmodell ersetzt werden und/oder dass bei Fehlen oder Unplausibilität von Simulations- oder Messdaten gemäß Verfahrensschritt b1 nach einer fest vorgegebenen Steuerungsstrategie gesteuert wird. Verfahren nach einem der Ansprüche 1 bis 10, dadurch gekennzeichnet, dass parallel zur gruppenweisen Abfertigung von Einheiten zu passenden Zeitpunkten eine Einzelabfertigung von Einheiten erfolgt, die zu inkompatiblen, d. h. konfliktbehafteten Abfertigungsprozessen gehören. Verfahren nach einem der Ansprüche 1 bis 11, dadurch gekennzeichnet, dass zielnahe Abfertigungsprozesse priorisiert erfolgen und dafür erforderliche Daten zusätzlich mit den Steuereinheiten ausgetauscht werden. Verfahren nach einem der Ansprüche 1 bis 12, dadurch gekennzeichnet, dass zur Koordination konkurrierender vernetzter Abfertigungsprozesse oder zur Steuerung des Transports mobiler Einheiten kontinuierliche Signale oder Steuereingriffe eingesetzt werden. Verfahren nach einem der Ansprüche 1 bis 13, dadurch gekennzeichnet, dass es zur Optimierung einer Netzwerkstruktur durch Variation von Knoten und Kanten verwendet wird. Verfahren nach einem der Ansprüche 1 bis 14, dadurch gekennzeichnet, dass es mit einem Verfahren zur Optimierung der Abzweigewahrscheinlichkeiten kombiniert wird. Verfahren nach einem der Ansprüche 1 bis 15, dadurch gekennzeichnet, dass es mit einem Verfahren zur Optimierung der Dynamik der einzelnen Einheiten entlang der Kanten kombiniert wird, wobei die Einheiten Informationen und/oder Anweisungen seitens der Steuereinheiten entgegennehmen. Verwendung eines Verfahrens nach einem der Ansprüche 1 bis 15 für die Steuerung eines Verkehrsnetzes, wobei die Knoten des Netzwerkes die Kreuzungen und die Steuereinheiten die Ampeln und die Kanten die Straßenabschnitte und die mobilen Einheiten Fahrzeuge und/oder andere Verkehrsteilnehmer des Verkehrsnetzes darstellen. Verkehrssystem mit einer Vielzahl von Kreuzungen, Straßenabschnitten, Datenerfassungselementen und Ampelanlagen mit Steuereinheiten, die zur Durchführung eines Verfahrens nach einem der Ansprüche 1 bis 17 geeignet sind, dadurch gekennzeichnet, dass den Kreuzungen Ampelanlagen und Sensoren zugeordnet sind, wobei die Steuereinheiten zum Empfang von Daten mit den Sensoren in Verbindung stehen und dass die Steuereinheiten benachbarter Ampelanlagen zum Austausch von Daten miteinander in Verbindung stehen. Verkehrssystem nach Anspruch 18, dadurch gekennzeichnet, dass die Datenverbindung zwischen den Sensoren und den Steuereinheiten der Ampelanlagen sowie zwischen den Steuereinheiten benachbarter Ampelanlagen drahtlos ausgebildet ist. Verkehrssystem nach Anspruch 18, dadurch gekennzeichnet, dass die Datenverbindung als WirelessLAN (WLAN), als Bluetooth, als Infrarotverbindung, als Radarsignal, als Laserlink oder Variante davon ausgebildet ist. Verwendung eines Verfahrens nach einem der Ansprüche 1 bis 16 für die Steuerung eines Produktionsprozesses, wobei die Knoten die Produktionsmaschinen oder produktiven Einheiten, die Kanten die Transportwege oder Zwischenlager zwischen ihnen und die mobilen zu bedienenden Einheiten die Produkte darstellen. Verwendung eines Verfahrens nach einem der Ansprüche 1 bis 16 für die Steuerung der Logistik eines Gütertransportes, wobei die Knoten die Umschlagplätze, die Kanten die Transportwege und die zu bedienenden Einheiten die Transportgüter darstellen. Verwendung eines Verfahrens nach einem der Ansprüche 1 bis 16 zur Koordination von Organisationsabläufen, wobei die zu bedienenden Einheiten den zu bearbeitenden Vorgängen und die Knoten den Bearbeitern entsprechen, während die Kanten den Verwaltungs- oder Beförderungsweg der zu bearbeitenden Vorgänge beschreiben, wobei die Steuerung den vorgenommenen Priorisierungsentscheidungen entspricht. Verwendung eines Verfahrens nach einem der Ansprüche 1 bis 16 für die Behandlung von Programmabläufen, wobei die Knoten den Programmmodulen entsprechen, die zu bedienenden Einheiten zu verarbeitende Daten sind, und die Weitergabe von Daten zwischen den Programmmodulen die Kanten des Netzwerkes aufeinander folgender Verarbeitungsprozesse definieren und die Steuerung der Koordination der Verarbeitungsprozesse dient. Verwendung eines Verfahrens nach einem der Ansprüche 1 bis 16 auf dem Gebiet der Biotechnologie zur Steuerung des Verteilungsprozesses von physikalischen, chemischen oder biologischen Substanzen, wobei diese Substanzen die mobilen Einheiten darstellen, die Knoten mögliche Ausgangs- und Zielorte dieser Substanzen sind und die Kanten Transportwegen der Substanzen entsprechen.






IPC
A Täglicher Lebensbedarf
B Arbeitsverfahren; Transportieren
C Chemie; Hüttenwesen
D Textilien; Papier
E Bauwesen; Erdbohren; Bergbau
F Maschinenbau; Beleuchtung; Heizung; Waffen; Sprengen
G Physik
H Elektrotechnik

Anmelder
Datum

Patentrecherche

Patent Zeichnungen (PDF)

Copyright © 2008 Patent-De Alle Rechte vorbehalten. eMail: info@patent-de.com