DE10194720T5 - Eisenbahnkorridor-Fahrplansteuerungsprozeß einschließlich einer ausgeglichenen durchführbaren Kostenfuktion - Google Patents

Abstract

Verfahren zur fahrplanmäßigen Steuerung der Bewegung einer Vielzahl von in einem Eisenbahnkorridor betriebenen Zügen, wobei die den Eisenbahnkorridor durchquerenden Züge auf demselben Gleis kreuzen können, wobei jeder Zug zumindest einen veränderbaren Fahrparameter aufweist, wobei der Eisenbahnkorridor zumindest eine Hauptstrecke und eine Vielzahl von Sekundärgleisen aufweist, auf die ein Zug übergeleitet werden kann zur Vermeidung einer Kreuzung mit einem anderen Zug, wobei das Verfahren die folgenden Schritte umfasst:
(a) Herleiten einer Lokalisierungsfunktion zur Darstellung der Eisenbahnkorridors, wobei die Lokalisierungsfunktion einen Wert innerhalb eines ersten Bereichs zwischen Sekundärgleisen aufweist und einen Wert innerhalb eines zweiten Bereichs in der Nähe jedes Sekundärgleises aufweist, wobei die Lokalisierungsfunktion jedes Sekundärgleis mit einer gleichen Länge repräsentiert,
(b) Auswählen eines Werts für zumindest einen Fahrparameter für jeden der Vielzahl der Züge, (c) Auffinden der Kreuzungspunkte für die Vielzahl der Züge,
(d) Bestimmen des Werts der Lokalisierungsfunktion für jeden Kreuzungspunkt,
(e) Aufsummieren der Lokalisierungsfunktionswerte...

Description

• BEREICH DER ERFINDUNG
• Die Erfindung betrifft einen Ablauf zur fahrplanmäßigen Steuerung der Bewegung von Zügen über einen Schienenkorridor mit einer Vielzahl von Ausweichgleisen und Parallelgleisen mit Übergangsstellen.
• GRUNDLAGEN DER ERFINDUNG
• Ein Eisenbahnkorridor (Eisenbahnstreckenbereich, Streckenabschnitt) ist eine Anzahl von Gleisen (Strecken) und Ausweichgleisen, die zwei Bahnhofsbereiche miteinander verbinden. Ein Beispiel eines Eisenbahnkorridors 8 ist in 1 gezeigt, wobei eine eingleisige Hauptstrecke 10 mit drei Ausweich- bzw. Überholgleisen angegeben ist. Das westliche Ende des Eisenbahnkorridors ist auf der linken Seite von 1 gezeigt, während das östliche Ende auf der rechten Seite angegeben ist.
• Die fahrplanmäßige Ausgestaltung von Eisenbahntransporten in einem Eisenbahnkorridor ist in gleicher Weise kompliziert wie die Steuerung einer Autobahn, einer Wasserversorgung oder des Luftverkehrs. Benutzen Züge eine eingleisige Strecke in entgegengesetzten (in wechselnden) Richtungen (d. h. Begegnung bzw. Zusammentreffen) oder fahren Züge in derselben Richtung (d. h. Durchlauf, Vorbeifahrt), dann müssen sich die Züge in der Nähe eines Ausweichgleises treffen, so dass ein Zug die Ausweiche bzw. ein Ausweichgleis befahren und den anderen Zug vorbeilassen kann. Liegt alternativ eine zweigleisige Hauptstrecke mit Übergangsstellen (Weichenverbindungen) vor, dann kann ein Zug auf die zweite Hauptstrecke übergehen, so dass der andere Zug vorbeifahren kann (Gleiswechselbetrieb). Treten derartige Begegnungen oder Vorbeifahrten (Überholungen) bei Ausweichgleisen auf, dann muss das ausgewählte Ausweichgleis zum Aufnehmen des auf das Ausweichgleis zu leitenden Zugs eine für diesen ausreichende Länge aufweisen, und der auf das Ausweichgleis zu leitende Zug muss am Ausweichgleis ankommen und eine ausreichende Zeit zur Verfügung haben, um auf das Ausweichgleis überzugehen, bevor der Zug, dessen Vorbeifahrt erwartet wird, am Ausweichgleis ankommt.
• Die Eisenbahn macht Gewinne durch den Verkauf von Transportleistungen, wobei jedoch ein Teil des Gewinns einem Risiko unterliegt, falls der Zug die Fracht nicht rechtzeitig anliefern kann. Die Ankunftszeit der Züge muss soweit wie möglich gesteuert werden zur Verhinderung von durch die Eisenbahn verursachten Verspätungsstrafen. Die fahrplanmäßige Führung von Zügen über einen Eisenbahnkorridor erfordert daher die Anordnung von Begegnungen und Vorbeifahrten (Überholungen) entsprechend den Erfordernissen sämtlicher Züge, wobei jedoch auch der Fahrplan für jeden Zug zu beachten ist, so dass sämtliche Züge rechtzeitig (fahrplanmäßig) am Ende des Korridors ankommen.
• Kommerziell anwendbare Fahrplanabläufe, wie sie derzeit entwickelt sind, wurden auf der Basis von Paradigmen gebildet, die zum Auffinden eines konfliktfreien Fahrplans einer Simulation mit einem "Branch-and-Bound-Verfahren" umfassen. Da bei einem Branch-and-Bound-Verfahren ein Sortieren erfolgt durch viele binäre Auswahlvorgänge in dem Ablauf bis zur Lösung sind diese Verfahren langsam und gewinnen keinen Vorteil aus quantitativen Beziehungen, die aus dem Fahrplanzusammenhang gewonnen werden können.
• Ferner werden die aus dem Stand der Technik bekannten Suchabläufe tatsächlich mehr und mehr kompliziert und benötigen eine längere Zeit zum Erreichen einer Lösung, wenn die Anzahl der Ausweichgleise (Überholgleise) in einem Eisenbahnkorridor ansteigt. Dies ist durch den Suchalgorithmus bedingt, der die Basis bildet für diese bekannten Verfahren. Eine größere Anzahl von Ausweichgleisen erfordert für den Suchalgorithmus das Durchsuchen und Berücksichtigen mehrerer Auswahlvorgänge vor dem Erreichen einer optimalen Lösung. Wie es nachstehend noch gezeigt ist, beseitigt das Verfahren der vorliegenden Erfindung diesen Nachteil. Da die vorliegende Erfindung eine Kostenfunktion berechnet, in welcher jedes Überholgleis niedrigere Kosten repräsentiert, wird es für die Algorithmus bei vorliegen mehrere Ausweichgleise leichter, die optimalen (d. h. die minimalen) Kosten zu ermitteln.
• Ein Verfahren gemäß dem Stand der Technik verwendet quantitative Information wie die Zuggeschwindigkeit, den Bestimmungsgrad und die Abfahrtszeit als diskrete Variablen in einem System auf der Basis künstlicher Intelligenz. Der Künstliche-Intelligenz-Ablauf umfasst Regeln, die verwendet werden zum Durchsuchen der Versuchsfälle (Experimente) bis der beste Fall gefunden wird. Zusätzlich zu der erheblichen Zeit, die das Künstliche-Intelligenz-System zum optimieren der Lösung benötigt ist ebenfalls bekannt, dass eine geringe Änderung der Anfangsbedingungen ein erheblich unterschiedliches Endergebnis bewirken kann. In jedem Fall erfordert eine geringe Änderung der Anfangsbedingungen eine neue und langandauernde Berechnung zum Auffinden der optimalen Lösung. Ein kommerzielles Produkt, das als "The Movement Planer" bezeichnet ist und das von GE-Harris Railway Electronics L.L.C. of Melbourne, Florida angeboten wird, verwendet eine derartige Künstliche-Intelligenz-Lösung.
• Wie es erkennbar ist kann die Gesamtzahl der Parameter zur fahrplanmäßigen Ausgestaltung eines Korridors groß sein, und sowohl diskrete als auch kontinuierliche Parameter aufweisen. Im Allgemeinen kann eine Kostenfunktion auf der Basis dieser Parameter formuliert werden, und es wird dann ein Verfahren zum Suchen durchgeführt, das die Kosten vermindert und/oder einen für den betroffenen Zug brauchbaren bzw. akzeptablen Fahrplan findet. Das Vorliegen von diskreten Variablen in dem durchzusuchenden Raum verhindert jedoch die Anwendung eines Gradientenverfahrens (Optimierungsverfahren, "hill-climbing-Verfahren") als Suchverfahren auf der Basis der Verwendung von Gradienten, oder macht die Anwendung erheblich komplizierter.
• KURZZUSAMMENFASSUNG DER ERFINDUNG
• Überall differenzierbare Kostenfunktionen haben den Vorteil gegenüber den Künstliche-Intelligenz-Lösungen gemäß dem Stand der Technik, da sie Gradienten basierten Minimierungsalgorithmen zugänglich sind, die nicht die Schwierigkeiten aufnehmen müssen, die bei diskreten oder teilweise diskreten Suchräumen auftreten. Die vorliegende Erfindung betrifft einen Ablauf, in welchem ein Eisenbahnkorridor und ein Zugfahrplan entlang dieses Korridors als eine differenzierbare (d. h. kontinuierliche, stetige) Kostenfunktion dargestellt werden kann, so dass der Suchablauf auf der Basis einer Differentiation verwendet werden kann zur fahrplanmäßigen Aktivitäten eines Zugs in dem Korridor.
• Die vorliegende Erfindung betrifft einen Analyseablauf zum fahrplanmäßigen Führen eines Zugs durch einen Korridor auf der Basis einer zu minimierenden Kostenfunktion, wobei die Kostenfunktion eine kontinuierliche und differenzierbare Funktion der Fahrplanvariablen ist. Die vorliegende Erfindung ist eine Verbesserung gegenüber den bekannten Kostenfunktionen gemäß dem Stand der Technik, da diese diskrete Variablen aufweisen und somit nicht überall differenzierbar sind. Die vorliegende Erfindung erlaubt die Verwendung von Suchabläufen auf der Basis von Gradienten, und wird daher schneller gegen Lösungen konvergieren als die Fahrplanabläufe gemäß dem Stand der Technik, die eine Simulation aufweisen oder die Suche durch diskrete Bedingungen.
• Der Korridorfahrplanablauf gemäß der vorliegenden Erfindung umfasst drei Schritte zur Identifikation (Bestimmung) des optimalen Fahrplans. Nachdem eine akzeptable differenzierbare Kostenfunktion hergeleitet wurde, betrifft der erste Schritt den Gradientensuchablauf, in welchem der Gradient der differenzierbaren Kostenfunktion bestimmt wird. Die Kostenfunktion ist eine Summe von individuellen Lokalisierungsfunktionen. Für jedes Zugpaar in dem Korridor, das sich kreuzen kann wird der Kreuzungspunkt unter Verwendung der Lokalisierungsfunktion mit einem hohen Wert bestimmt, falls die Zugfahrstrecken nicht in der Nähe eines Ausweichgleises kreuzen, und wird mit niedrigen Werten bestimmt, wenn sich der Kreuzungspunkt in Richtung eines Ausweichgleises bewegt. Der Gradientenablauf kann nicht alle Kreuzungspunkte präzise zur Mitte eines Ausweichgleises in Abhängigkeit von dem ausgewählten Schwellenwert und den Parameterwerten der Lokalisierungsfunktion bewegen. Vielmehr verändert der Gradientenablauf die Zugabfahrtszeiten, so dass die Gesamtheit sämtlicher Kreuzungspunkte der Züge näher an die Ausweichgleise verschoben werden. Die zweite Phase des Ablaufs bewegt einfach die Punkte in präziser Weise zur Mitte der Ausweichgleise, wählt den auf das Ausweichgleis zu leitenden Zug aus und berechnet eine exakte Ankunfts- und Abfahrtszeit für die Züge an dem Ausweichgleis, so dass die physikalischen Rahmenbedingungen dieser Begegnung berücksichtigt werden. Zum Erreichen der Mitte der Kreuzungspunkte bei den Ausweichgleisen und zum Ausleiten eines bestimmten Zugs auf das Ausweichgleis müssen die Geschwindigkeiten der einzelnen Züge entsprechend verändert werden. Dies wird erreicht durch den zweiten Schritt des Fahrplanablaufs (fahrplanmäßiger Steuerungsablauf).
• Der dritte Schritt hält die geeigneten Abzweigbeziehungen aufrecht zwischen zwei sich begegnenden Zügen, wie es in Schritt 2 bestimmt wurde, wobei jedoch erlaubt wird, dass sich die Begegnungszeit im Hinblick darauf ändert, dass sichergestellt ist, dass kein Zug eine obere Geschwindigkeitsbeschränkung überschreitet. Diese letzte Phase ist ebenfalls erneut ein Gradientensuchablauf, der angewendet wird für sämtliche Begegnungspunkte, die in dem zweiten Schritt bestimmt wurden.
• KURZE BESCHREIBUNG DER FIGUREN
• Die vorliegende Erfindung wird auf einfache Weise verständlich und die weiteren Vorteile und Anwendungsmöglichkeiten werden erkennbar in Verbindung mit der Beschreibung der bevorzugten Ausführungsbeispiele und den nachfolgenden Figuren. Gleiche Bezugszeichen in den Figuren bezeichnen identische Bauteile bzw. Komponenten der Erfindung.
• 1 veranschaulicht einen einfachen Eisenbahnkorridor,
• 2 ist ein Liniendiagramm zur Veranschaulichung der Korridorfahrplanprobleme als sich kreuzende Linien,
• 3 ist ein Ablaufdiagramm des Korridorfahrplanablaufs der vorliegenden Erfindung,
• 4 zeigt die Grundgeometrie von Zugfahrstrecken,
• 5 ist eine graphische Darstellung einer Grundsigmoid-Funktion,
• 6 veranschaulicht die Verwendung von Sigmoid-Summen zum Diskriminieren von Intervallen,
• 7 veranschaulicht den Aufbau einer Lokalisierungsfunktion aus Sigmoid-Funktionen,
• 8 veranschaulicht ein Beispiel einer Lokalisierungsfunktion für zwei Ausweichgleise,
• 9A und 9B veranschaulichen die Änderung der Lokalisierungsfunktion zur Berücksichtigung von Korridorendpunkten,
• 10 veranschaulicht die erforderliche Geometrie zum Erzielen einer ausgeglichen Lokalisierungsfunktion,
• 11A, 11B und 11C veranschaulichen ein Verfahren zum Approximieren von Wirtschaftstraffunktionen,
• 12 zeigt eine Strafwertfunktion für frühes Abfahren eines Zugs,
• 13 ist ein anfänglicher nicht durchführbarer Linienfahrplan für zwölf Züge,
• 14 ist ein Linienfahrplan für Züge gemäß 13 nach einer Gradientensuche gemäß der vorliegenden Erfindung,
• 15 zeigt den Ablauf, mittels dessen Kreuzungspunkte zur Mitte eines Ausweichgleises bewegt werden,
• 16 zeigt die Bewegung des ersten Kreuzungspunkts zur Mitte eines Ausweichgleises,
• 17 veranschaulicht den Ablauf der Geschwindigkeitsanpassungen zum Zentrieren sämtlicher Begegnungen,
• 18A und 18B bis 24A und 24B veranschaulichen verschiedene Unmöglichkeiten, die erzeugt wurden durch Zentrieren von Begegnungen auf Ausweichgleisen, und die jeweilige Lösung derselben,
• 19A und 19B veranschaulichen zwei Typen von Ausweichkonflikten,
• 20A und 20B veranschaulichen die Auflösung bestimmter Ausweichkonflikte,
• 21A und 21B veranschaulichen einen "nicht lösbaren" Ausweichkonflikt,
• 22A bis 22D veranschaulichen Lösungen von beiden Typen von Ausweichkonflikten,
• 23A bis 23E veranschaulichen die Fälle abwärts lösbarer Ausweichkonflikte,
• 24A und 24B veranschaulichen die Lösung von aufwärts lösbaren Ausweichkonflikten,
• 25 veranschaulicht Zugfahrstrecken, die als gestrichelte Liniensegmente dargestellt sind,
• 26 ist eine Verarbeitung des Zugfahrstreckenvektors,
• 27 zeigt eine Anpassung der Zugfahrstrecke zur Berücksichtigung der Ausweichverzögerungen,
• 28 zeigt Ausweicheinzelheiten eines nach Westen fahrenden und ausweichenden Zugs,
• 29 veranschaulicht Ausweicheinzelheiten eines nach Osten fahrenden und überholenden (vorbeifahrenden) Zugs,
• 30 ist ein vollständiges Liniendiagramm, das angepasst ist für zentrierte Begegnungen und Zugsausweichvorgänge, und
• 31 und 32 sind Ablaufdiagramme zur Veranschaulichung von in der vorliegenden Erfindung implementierten Algorithmen.
• DETAILLIERTE BESCHREIBUNG DER BEVORZUGTEN AUSFÜHRUNGSBEISPIELE
• Das traditionelle Verfahren der graphischen Auflösung eines Zugfahrplans für einen Eisenbahnkorridor wird gemäß der Darstellung in 2 als Liniendiagramm oder Liniengraph (Bildfahrplan) bezeichnet. Das Liniendiagramm bezeichnet ein Zeit-Entfernungs-Diagramm der Zugbewegungen in dem in 1 gezeigten Korridor. Die horizontale Achse bezeichnet die Zeit (d. h. ein festgelegtes Zeitfenster), und die vertikale Achse bezeichnet die Entfernung, wobei der Punkt im Ursprung des Diagramms (graphische Darstellung) das westliche Ende des Korridors darstellt, während der oberste Punkt das östliche Ende des Korridors darstellt. Die Breite des Diagramms (Bildfahrplan) bezeichnet die interessierende Zeitdauer, in welcher die Züge fahrplanmäßig gesteuert wer den. Linien in dem Bildfahrplan mit einer Neigung in einer Richtung bezeichnen einen Verkehr in einer Richtung durch den Korridor, während Linien mit einer dazu entgegengesetzt gerichteten Neigung den in der entgegengesetzten Richtung laufenden Verkehr bezeichnen. Es wird dabei lediglich die Position der Lokomotive angegeben. Die horizontalen Linien über dem Bildfahrplan beziehen sich auf Bezugszeichen 20 und entsprechen den Ausweichorten (den Orten bzw. den Bereichen) der Ausweichgleise oder Nebengleise.
• Gemäß der nachfolgenden Darstellung wird die Erfindung in Verbindung mit einem eingleisigen Korridor mit zwei Ausweichgleisen (Nebengleisen) beschrieben. Der Fachmann auf diesem Gebiet wird jedoch erkennen, dass ein Übergang zu mehrgleisigen Hauptstrecken mit Übergangsstellen zwischen den Hauptstrecken (Hauptgleisen) möglich ist.
• Das wichtige Kriterium für einen akzeptablen, d. h. durchführbaren Fahrplan, wie er anhand des Liniendiagramms (Bildfahrplan) von 2 gezeigt ist, ist, dass zwei beliebige Zugfahrstrecken (Linien) im Bildfahrplan sich bei einem Ausweichgleis 20 kreuzen. Liegt die Begegnung bei Ausweichgleisen, dann ist eine Wahl erforderlich, welcher Zug auf das Ausweichgleis zu leiten ist.
• Dabei ist zu beachten, dass der Fahrplan undurchführbar bzw. unmöglich ist, sofern nicht sämtliche sich kreuzende Linien sich tatsächlich innerhalb der Ausweichgleise 20 kreuzen. Wird für den gerade vorliegenden Fall angenommen, dass sämtliche Zuggeschwindigkeiten feste Werte aufweisen, dann können die Abfahrtszeiten der Züge angepasst werden zum Hin- und Herbewegen der Zuglinien und für den Versuch, sämtliche Kreuzungspunkte über die Ausweichgleise 20 (d. h. in die Bereiche der Ausweichgleise) zu legen. In einem weiteren Ausführungsbeispiel der vorliegenden Erfindung wird es in gleicher Weise möglich sein, die Zuggeschwindigkeiten zu verändern, wobei sich die Neigung der Zugfahrstreckenlinien verändert, so dass die Kreuzungspunkte über die Ausweichgleise 20 gelegt werden können. In einem weiteren Ausführungsbeispiel können sowohl die Geschwindigkeiten als auch die Abfahrtszeiten der Züge gleichzeitig geändert werden, um einen geeigneten und durchführbaren Begegnungs/Überholungs-Fahrplan für die Züge zu finden.
• Der hier beschriebene Ablauf behandelt die Korridorfahrplangestaltungsprobleme als ein geometrisches Problem und weniger als ein direktes Fahrplanproblem, wie dies durch den Stand der Technik vorgeschlagen wird. Dies wird erreicht durch eine Vorgehensweise, bei welcher die Zugfahrstreckenlinien entsprechend einer Steuerung eines Gradientensuchprozesses auf der Basis einer differenzierbaren Kostenfunktion in einer Weise bewegt werden, bei der die Kreuzungspunkte zu oder in die Nähe von vorgesehenen Ausweichgleisen bewegt werden.
• Der Suchprozess gemäß der vorliegenden Erfindung ermöglicht die Änderung der Geschwindigkeiten und der Abfahrtszeiten, getrennt oder in Verbindung miteinander, und verwendet eine überall differenzierbare Kostenfunktion, die niedrigere Werte annimmt, wenn der Fahrplan sich der Durchführbarkeit nähert. Da die Kostenfunktion überall differenzierbar ist, kann ein iteratives Gradientensuchverfahren angewendet werden, mit dem sichergestellt ist, dass die sukzessive gefundenen Fahrplanausgestaltungen mittels des Suchablaufs tatsächlich gegen ein konfliktfreies Ergebnis konvergieren.
• In einem weiteren Ausführungsbeispiel der vorliegenden Erfindung ist es ferner möglich, die zwingende Bedingung zu berücksichtigen, dass ein Ausweichgleis länger sein muss als der Zug, der auf das betreffende Ausweichgleis umgelei tet wird. Es ist ferner möglich, in einem weiteren Ausführungsbeispiel die ökonomischen Kosten zum Anpassen der Zugfahrpläne einzubeziehen. In anderen Ausführungsbeispielen werden ebenfalls Sachzwänge (Restriktionen) bezüglich der maximalen Zuggeschwindigkeit und des frühen Abfahrens der Züge berücksichtigt.
• Es ist für den Fachmann auf diesem Gebiet klar, dass das Verfahren gemäß der vorliegenden Erfindung auf einfache Weise auf eine beliebige Anzahl von in jeder Richtung fahrenden Zügen und eine beliebige Anzahl von Ausweichgleisen jedes Eisenbahnkorridors erweitert werden kann, obwohl gemäß 2 lediglich drei Ausweichgleise und drei in jeder Richtung fahrende Züge dargestellt sind. Die Konzepte der vorliegenden Erfindung können ebenfalls erweitert werden auf einen Eisenbahnkorridor mit mehr als einer Hauptstrecke und Übergangsverbindungen (Kreuzungsverbindungen) zwischen den Hauptstreckengleisen. Die vorliegende Erfindung kann Verwendung finden bei jedem Eisenbahnkorridor, in welchem ein Zug auf ein anderes Gleis umgeleitet werden kann, wenn eine Begegnung oder eine Überholung (Gleiswechselbetrieb) mit anderen Zügen auftritt.
• Die fahrplanmäßige Steuerung der Züge muss zuerst durchführbar sein, wobei jedoch auch die Wahl bestehen kann, welcher Zug auf das Ausweichgleis umgeleitet wird, oder bezüglich der Reihenfolge der Fahrt der Züge, wobei dies dazu führt sicherzustellen, dass keine ökonomischen Strafen entstehen oder dass, falls dies nicht gelingt, diese zumindest vermindert werden.
• Ein Ablauf 30 zum Erhalten sowohl der Fahrplandurchführbarkeit als auch der ökonomischen Akzeptanz kann aus einer Anzahl von Schritten bestehen, wie dies in 3 gezeigt ist. Zuerst wird in Schritt 31 eine anfängliche Vorsortie rung bzw. Voranordnung der Züge vorgenommen, wobei ihre jeweilige Reihenfolge zum Einfahren in den Korridor bestimmt wird. An diesem Punkt stützt sich die Zugreihenfolge lediglich auf feste Zeiten (dargestellt als eine Eingabe in Schritt 31 von dem ersten Block 32) ohne eine Analyse bezüglich der Kapazität des Korridors oder der speziellen Abfahrtszeiten. In Schritt 33 wird ein Anfangsfahrplan für die Züge bestimmt; hierbei können verschiedene numerische Optimierungstechniken angewendet werden. Es wird hierbei auf die Veröffentlichung "Numerical Optimization" by Jorge Nacedad and Stephen J. Wright; Springer, New York 1999; ISBN 0-387-98793-2 verwiesen.
• Dieser Anfangsfahrplan wird in den Gradientensuchablauf gemäß Schritt 34 eingegeben, der nachstehend noch beschrieben wird, der die Fahrplanungsmöglichkeiten minimiert. In einem weiteren Ausführungsbeispiel kann der Gradientensuchablauf ebenfalls bei der Eisenbahn auftretende ökonomische Strafen für spätes Ankommen der Züge minimieren und unter Berücksichtigung der maximalen Zuggeschwindigkeiten, früherer Abfahrtszeiten und Ausweichlängen vorgeben. Die Gradientensuche passt die Zugabfahrtszeiten (d. h. die Zeit, zu der der Zug in den Korridor einfährt) und/oder die Geschwindigkeiten in der Weise an, dass Begegnungen in der Nähe von Ausweichgleisen auftreten. Der Ablauf 30 durchläuft den Ausweichgleisauswählschritt 38 und den Konfliktbestimmungsschritt 36 so lange, bis sämtliche Zugkreuzungen bei oder in der Nähe von Ausweichgleisen des Eisenbahnkorridors angeordnet sind durch Anpassen der Geschwindigkeit und/oder der Abfahrtszeit (d. h. der Zeit, zu der der Zug in den Korridor einfährt) für die den Korridor durchquerenden Züge.
• Die in Schritt 38 getroffene Entscheidung, welcher Zug eines sich begegnenden Zugpaars auf das Ausweichgleis umgeleitet wird, kann gestützt werden durch Berücksichtigung relativer ökonomischer Kosten infolge der Verzögerung, die auftritt, wenn ein Zug gegenüber einem anderen Zug auf ein Ausweichgleis geführt wird. Dieser Ausweichgleisentscheidungsablauf bezeichnet ein weiteres Ausführungsbeispiel der vorliegenden Erfindung und wird nachstehend noch beschrieben.
• Wurde die Ausweichentscheidung durchgeführt, dann werden einige der Fahrstrecken (diejenige für die ausweichenden Züge) in dem Liniendiagramm (2) zu gestrichelten Linien (zur Darstellung nicht durchführbarer Begegnungen), die neue Fahrplanunmöglichkeiten für einige Zugfahrstrecken verursachen können. An diesem Punkt kann die Gradientensuche erneut angewendet werden, wobei die Anwendung jedoch lediglich für eine Untermenge von Unterfahrstrecken vorgenommen wird, die zu undurchführbaren Begegnungen (Zugkreuzungen) gebracht wurden. Mehrfache Durchläufe durch den Gradientensuchschritt 34 und den Ausweichentscheidungsablaufschritt 38 führen den Fahrplan zur vollständigen Durchführbarkeit.
• 4 bezeichnet die Zugfahrstrecken als Linien auf der Basis der Anfangsabfahrtszeiten (Zeitpunkt der Einfahrt in den Korridor) und der Zuggeschwindigkeit. In 4 bezeichnet das untere Ende der vertikalen Achse das westliche Ende des Korridors, und die positive Richtung entlang dieser Achse entspricht einer Fahrt in östlicher Richtung. Das für die Fahrt im Korridor interessierende Zeitfenster beginnt mit der Zeit d₀ und der mit L bezeichneten Länge des Korridors.
• Hierbei bezeichnet 4 jeweils einen in östlicher und in westlicher Richtung fahrenden Zug T_i und T_j, die den Fahrstrecken L_i und L_j entsprechen. Mit s_i und s_j sind Geschwindigkeiten bezeichnet und mit d_i und d_j sind jeweils Ab fahrtszeiten der Züge T_i und T_j bezeichnet. Die Abfahrtszeit eines Zugs ist die Zeit, zu der der Zug in den Korridor einfährt: für den in östlicher Richtung fahrenden Zug entspricht dieser Punkt einem auf der horizontalen Achse von 4 liegenden Punkt (d. h. t = 0), und für einen in westlicher Richtung fahrenden Zug ist dies ein Punkt auf der horizontalen Linie y = L.
• Die Beziehung zwischen den Koordinaten für jeden Punkt auf der Linie kann für die Zugfahrstrecke L_i (in Ostrichtung) dargestellt werden in der Form

  
• In gleicher Weise kann für den Zug T_j (in Westrichtung) die Form der Fahrstrecke L_j ausgedrückt werden als

  
• Diese Gleichungen können in identischer Form für den in westlicher und, den in östlicher Richtung fahrenden Zug angegeben werden als

  

  wobei die Geschwindigkeit des in westlicher Richtung fahrenden Zugs durch Vereinbarung die negative Zuggeschwindigkeit ist, und ferner gilt

  
• Diese Form einer linearen Gleichung (3-3) ist nicht die übliche Form direkt in Ausdrücken einer Neigung und eines Linienschnitts, sondern es werden in dieser Analyse Zuggeschwindigkeiten und Abfahrtszeiten verändert und die Form der Gleichung 3-3 weist den Vorteil auf, dass die Zugfahrstrecken explizit in Ausdrücken der Geschwindigkeit und der Abfahrtszeiten dargestellt sind.
• Die Aufgabe der vorliegenden Erfindung ist die Bestimmung der Koordinaten der Schnittpunkte (t_ij, y_ij) für Paare von Zugfahrstrecken, und die Bewegung dieser Schnittpunkte zu den Ausweichgleisen. Für Züge T_i und T_j ist die Lösung des Fahrwegschnittpunkts (t_ij, y_ij), wobei gilt

  

  die Werte (t_ij, y_ij) werden aus dem Gleichsetzen der Gleichung (3-1) und (3-2) hergeleitet (nach Durchführung einer Bezeichnungsänderung gemäß dem Vorschlag durch Gleichung (3-3)).
• Diese Bestimmung der Schnittpunkte trifft zu auf Kreuzungen von in gleicher Richtung fahrenden und in entgegengesetzten Richtungen fahrenden Zügen, so dass die zu entwickelnde Analyse bezüglich der Schnittpunkte (Kreuzungspunkte) Zugfahrstrecken anpassen kann bezüglich sowohl Zugbegegnungen als auch Überholungen.
• Bis zu diesem Punkt wurde das Zugfahrplangestaltungsproblem auf einen Kontext abstrahiert zum Bewegen der sich schneidenden Linien in dem Umfang, bis sämtliche Schnittpunkte innerhalb vorbestimmter Bereiche (den die Ausweichgleise darstellenden Balken 20 in 2) liegen. Liegen sämtliche Schnittpunkte, die innerhalb des Rechtecks (das den Korridor 8 bezeichnet) liegen, innerhalb der Ausweichgleise 20, dann wurde ein durchführbarer Fahrplan erhalten.
• Eine Aufgabe besteht in der Bereitstellung eines durchführbaren Fahrplans unter Verwendung eines Suchablaufs, der eine Kostenfunktion minimiert, und in einem bevorzugten Ausführungsbeispiel wird die bevorzugte Kostenfunktion einen hohen Wert annehmen, falls ein beliebiger Schnittpunkt (Kreuzungspunkt) außerhalb des Ausweichgleisbalkens 20 (Ausweichgleisbereich in 2) liegt, und wird einen niedrigen Wert nur dann annehmen, wenn sämtliche Schnittpunkte innerhalb der Ausweichgleisbalken liegen. Schnittpunkte, die völlig außerhalb des Diagramms (Bildfahrplan) liegen, werden nicht berücksichtigte es wird angenommen, dass der Korridor und die entsprechende Fahrplanperiode im Zusammenhang mit dem Diagramm stehen.
• Eine Funktion eines Einzelwerts y_ij mit dieser Kostenfunktionseigenschaft sei eine Lokalisierungsfunktion, und eine derartige Lokalisierungsfunktion wird unter Verwendung einer Sigmoid-Funktion als Basis aufgebaut. Die bevorzugte Funktion ist abhängig von der Grundsigmoidfunktion entsprechend der Gleichung

  

  und weist einen Graphen in der in 5 gezeigten Form auf.
• Der Parameter β der Sigmoidfunktion bestimmt eine horizontale Asymptote für die Kurve, und der Parameter α bestimmt die Stärke des Anstiegs der Funktion beim Schneiden der y-Achse. Nähert sich α dem Wert "unendlich" (∞), dann nähert sich die Sigmoidkurve einer Schrittfunktion (Sprungfunktion). In dem bevorzugten Ausführungsbeispiel gilt β = 1.0 und α = 0.5.
• Da die Sigmoidfunktion mit großer Steilheit von einem niedrigen zu einem hohen Wert ansteigen kann, bildet sie eine gute Annäherung für diskrete Abläufe. Summen von Sigmoiden können ebenfalls verwendet werden zur Bestimmung, ob eine Variable einen Wert innerhalb eines Intervalls aufweist oder nicht. Insbesondere gilt für das Intervall [a, b] die Funktion D(x;a,b) = σ(x – a;α,β) - σ(x – b;a,β) (4-2)
• Auf der Basis des Graphen der Sigmoidfunktion gemäß der Darstellung in 5 nimmt der Graph von D(x; a, b) die in 6 gezeigte Form an, die die Funktion D(x; a, b) zeigt (Bezugszeichen 60), die abgeleitet ist als eine Summe der zwei Sigmoidfunktionen 62 und 64.
• Da jede der Sigmoide 62 und 64 vorgesehen sein können zur Annäherung einer Sprungfunktion soweit wie gewünscht, kann die Funktion D(x; a, b) in der Weise definiert werden, dass sehr genau unterschieden werden kann, ob x innerhalb des Intervalls [a, b] liegt, und kann vorgesehen sein zum Annähern eines Pulses der Breite b – a soweit wie gewünscht.
• Da ferner die Funktion D(x; a, b) (Bezugszeichen 60) sich 0 annähert, wenn x weiter vom Intervall [a, b] liegt, ist es möglich, derartige Intervallunterschiede (für sich nicht überlappende Intervalle) aufzusummieren und auf diese Weise eine Funktion zu erhalten, die einen hohen Wert annimmt, wenn sich x in einem der interessierenden Intervalle befindet, und in anderen Fällen einen niedrigen Wert annimmt. Dies ist in 7 für die Intervalle [a₁, b₁] und [a₂, b₂] gezeigt, und es ist für den Fachmann auf diesem Gebiet offensichtlich, dass dieser Aufbau für jede begrenzte Anzahl von Intervallen verallgemeinert werden kann.
• Die Lokalisierungsfunktion 70 gemäß der Darstellung in 7 (die erzeugt wird durch Aufsummieren von Sigmoid-Funktionen 72, 74, 76 und 78) kann erweitert werden zu jeder beliebigen endlichen Anzahl von Intervallen, so dass eine derartige Lokalisierungsfunktion erstellt werden kann für jeden beliebigen Korridor von dem in 1 dargestellten Typ (eine Hauptstrecke, eine oder mehrere Ausweichgleise). Die Ausweichgleise werden entlang der x-Achse zwischen den Punkten ai und bi dargestellt.
• Die Lokalisierungsfunktion 70 weist daher die Form auf

  
• Die Kostenfunktion des Fahrplangestaltungsproblems gemäß 2 wird nachstehend unter Verwendung des Lokalisierungsfunktionskonzepts und der Annahme, dass n_s Ausweichgleise vorliegen, hergeleitet. In dem bevorzugten Ausführungsbeispiel wird die Kostenfunktion niedrige Werte lediglich dann annehmen, falls die y-Koordinate y_ij für eine Kreuzung von Zugfahrstrecken innerhalb des Bereichs eines Ausweichgleises liegt, wobei die Lokalisierungsfunktion 70 gemäß 7 tatsächlich die gegenteilige Wirkung zeigt. Daher wird zuerst die Lokalisierungsfunktion bestimmt zu

  

  die somit die gewünschte Eigenschaft aufweist, dass sie einen niedrigen Wert dann und nur dann annimmt, wenn x innerhalb der Intervalle

  

  liegt, und in anderen Fällen einen hohen Wert annimmt. Somit definiert die Gleichung 4-3 eine Lokalisierungsfunktion, die die invertierte Lokalisierungsfunktion 70 ist. Es wird auf die Lokalisierungsfunktion 80 in 8 verwiesen.
• Die mittels der Gleichung 4-3 definierte Lokalisierungsfunktion (die die invertierte Form der Lokalisierungsfunktion 70 in 7 annimmt) wird nachstehend zur Bestimmung eine Kostenfunktion verwendet, die einen niedrigen Wert annimmt, wenn sich die Kreuzungspunkte (Schnittpunkte) der Zugfahrstrecken den Ausweichgleisen nähern. Nachstehend werden zwei Versionen der Kostenfunktion getrennt voneinander beschrieben.
• Eine vereinfachte Kostenfunktion für einen durchführbaren Fahrplan
• Mit n_T wird nun die Gesamtheit sämtlicher in dem Korridor fahrender Züge bezeichnet, und L_i bezeichnet die Zugfahrstreckenlinie für den Zug T_i (wie es 2 dargestellt ist). Eine Gesamtheit I sämtlicher möglicher y-Koordinaten der Kreuzungspunkte zwischen den Zugfahrstrecken wird angegeben mittels der Gleichung

  
• Dabei ist unter Bezugnahme auf 2 zu beachten, dass diese Menge sämtliche mögliche Kreuzungspunkte zwischen Zugfahrstrecken beinhaltet, obwohl einige dieser Punkte nicht innerhalb des Korridors 8 und/oder des interessierenden Zeitfensters liegen können. Es ist erforderlich, derartige außerhalb des Korridors liegende Kreuzungspunkte zu berücksichtigen, da der Suchablauf die Zugfahrstrecken bewegen (verschieben) wird, und auf diese Weise einen Kreuzungspunkt in dem Korridor 8 einbringen kann, der ursprünglich außerhalb des Korridors 8 lag.
• Zur Erstellung einer Kostenfunktion, die einen niedrigen Wert dann und nur dann annimmt, wenn sämtliche Kreuzungspunkte innerhalb eines der Ausweichgleise 20 liegen, werden Lokalisierungsfunktionswerte aufsummiert, die aus der Gleichung 4-3 abgeleitet wurden. Insbesondere wird ein Vektor definiert, der sämtliche Kreuzungspunkte in der Nähe darstellt.

  
• Und es wird die Kostenfunktion C'(y →) bestimmt zu

  
• Die Kostenfunktion ist eine mehrdimensionale Funktion des Vektors y, wobei jeder Vektor auf der Basis von Lokalisierungsfunktionswerten eine unterschiedliche Summe ergibt. Jede die Summe umfassende Lokalisierungsfunktion gibt an, ob ein Kreuzungspunkt innerhalb eines durchführbaren bzw. möglichen Bereichs (d. h. innerhalb der Ausweichgleisbalken 20 gemäß 2) liegt oder nicht. Es wird auf die Kostenfunktion 80 von 8 hingewiesen, in welcher die x-Achse die Entfernungen und Abstände entlang des Korridors bezeichnet. Sind sämtliche Kreuzungspunkte relativ zu einem speziellen Ausweichgleis möglich bzw. durchführbar, dann sollte der Wert C'(y →) einen niedrigen Wert in der Nähe von dieses Ausweichgleis repräsentierenden Punkten annehmen; in anderen Fällen wird ein Wert in der Nähe des Werts β angenommen. Sind viele Kreuzungspunkte betroffen, dann muss β derart ausgewählt werden, dass die Summen in der Nähe von Null einer großen Anzahl von möglichen Kreuzungspunkten nicht einen Wert im Bereich von β ergeben, wodurch die Durchführbarkeit maskiert würde, obwohl diese mittels der Funktion bestimmt (diskriminiert) werden soll.
• C'(y →) ist eine differenzierbare Funktion des Vektors y → (der Kreuzungspunkte) und daher in jeder der Variablen, die die verschiedenen Kreuzungspunkte definieren, d.h. den Abfahrtszeiten und/oder den Geschwindigkeiten der Züge. Daher kann die Kostenfunktion mit einem Gradientensuchverfahren oder einem anderen Suchverfahren auf der Basis der partiellen Ableitungen, zur Minimierung der Kostenfunktionswerte bei den Ausweichgleisen verwendet werden. Ein derartiges Verfahren wird nachstehend beschrieben. Da jeder als eine Komponente von y → auftretender Kreuzungspunkt (Schnittpunkt) eine Funktion der Zugabfahrtszeit und der Geschwindigkeiten der entsprechenden Züge ist, kann die Kostenfunktion als eine Funktion behandelt werden, die optimiert werden kann durch Anpassung entweder der Geschwindigkeiten oder der Ursprungszeiten der Züge, oder durch beides.
• Berücksichtigung der Korridorendpunkte
• Die Tatsache, dass die Kreuzungspunkte in I nicht immer Kreuzungen der Fahrstrecken innerhalb des Korridors 8 bezeichnen, führt zu einer Schwierigkeit für die Kostenfunktion, wie sie in Gleichung 5-3 definiert ist, in der Weise, dass jeder Kreuzungspunkt außerhalb des Korridors ein "Nichtbeachtungs"-Punkt für den Suchprozess ist (solange er außerhalb des Korridors verbleibt), wobei jedoch die Kostenfunktion gemäß der Definition in der Gleichung 5-3 einem derartigen Punkt einen hohen Wert zuordnen wird. Es wird daran erinnert, dass die Kostenfunktion der Gleichung 5-3 auf der Lokalisierungsfunktion von Gleichung 4-3 basiert, die in 9A mit Bezugszeichen 90 veranschaulicht ist. Da die Gleichung 5-3 gegenwärtig formuliert ist, könnte eine andere mögliche Lösung durch einen "Nichtbeachtungs"-Punkt maskiert werden.
• In einem weiteren Ausführungsbeispiel der vorliegenden Erfindung umfasst die Lösung die Änderung der Lokalisierungsfunktion 90. 9A zeigt die Lokalisierungsfunktion 90, wie sie mittels der Gleichung 4-3 definiert ist, sowie eine modifizierte Lokalisierungsfunktion 92, die durch Addieren zweier weiterer Sigmoid-Funktionen 94 und 96 zur Berücksichtigung der Endpunkte des Korridors 8 erzeugt wird.
• Im Einzelnen gilt:
  e = y-Koordinate des östlichen Endes des Korridors 8 , w = y-Koordinate des westlichen Endes des Korridors 8 , (5-4)woraus sich die Änderung der Definition der Lokalisierungsfunktion durch Einbeziehen der Sigmoid-Funktionen 74 und 96 in der folgenden Weise ergibt.
• 
• Die Verwendung der Lokalisierungsfunktion L der Gleichung 5-5 erfordert ebenfalls ein Umschreiben der Kostenfunktion in Gleichung 5-3 in der folgenden Weise.
• 
• Diese Kostenfunktion sollte nun einen hohen Wert annehmen, solange ein beliebiger Zugfahrstreckenkreuzungspunkt innerhalb des Korridors unmöglich (nicht durchführbar) ist, und sollte einen niedrigen Wert für alle möglichen Kreuzungspunkte annehmen, sowie für Kreuzungspunkte, die außerhalb des Korridors liegen.
• In gleicher Weise wie C'(y →) ist C(y →) eine differenzierbare Funktion in jeder Komponente des Vektors (y →). Jedes Gradientensuchverfahren oder die Verwendung einer anderen Information auf der Basis partieller Ableitungen kann zum Minimieren des Werts von C(y →) in den Regionen der Ausweichgleise verwendet werden.
• Ausgeglichene Kostenfunktion eines durchführbaren Fahrplans
• Wie es den Lokalisierungsfunktionen 70, 90 oder 92 entnehmbar ist, sind die Ausweichgleise (dargestellt durch die x-Achsenwerte a_I und b_I) mit unterschiedlichen Längen dargestellt. Tatsächliche weisen Eisenbahnkorridore typischerweise Ausweichgleise bzw Nebengleise mit unterschiedlichen Längen auf. Als Folge der unterschiedlichen Längen der Aus weichgleise tritt bezüglich der Kostenfunktion (siehe Gleichung (5-6)) auf, dass die Kostenfunktionsminima entsprechend den Ausweichgleisen nicht den gleichen y-Wert aufweisen. Es wird auf die Kostenfunktion 80 von 8 hingewiesen. Für das Ausweichgleis S1 ist der Kostenfunktions-y-Wert durch Bezugszeichen 82 dargestellt, und der y-Wert für das Ausweichgleis S2 ist dargestellt durch Bezugszeichen 84. Dabei ist zu beachten, dass das Minimum bei Bezugszeichen 82 einen größeren Wert aufweist als das Minimum bei Bezugszeichen 84. Infolge der Ausweichgleise mit unterschiedlichen Längen verwendet die Sigmoid-Summe, die das Minimum erzeugt, einen schmaleren Bereich der Sigmoid-Funktion für kürzere Ausweichgleise, so dass das zugehörige Minimum nicht soweit absinkt, wie dies für ein längeres (breiteres) Ausweichgleis auftritt. Dieser Effekt führt dazu, dass der Kostenfunktionsgradientenoptimierungsablauf längere Ausweichgleise mit einem tieferen Minimum bevorzugt, wenn es in unmittelbarer Nähe eines kurzen Ausweichgleises mit einem weniger ausgeprägten Minimum liegt. In dem nachstehend diskutierten Ausführungsbeispiel wird die Kostenfunktion zur Erzielung gleicher Minima für alle Ausweichgleise angepasst.
• Falls die Ableitung der Lokalisierungsfunktion 80 den Wert Null exakt bei dem Mittelpunkt zwischen Ausweichgleisen aufweist, beinhaltet der Suchablauf keine Tendenz zur Bevorzugung einer Seite vor der jeweils anderen. Eine derartige Lokalisierungsfunktion wird als "ausgeglichen" (balanciert) bezeichnet. Die in 8 dargestellte Situation gewährleistet nicht, dass die Kostenfunktionsableitung einen gut platzierten Nullpunkt aufweist; obwohl die Ableitung einen Nullwert zwischen den Ausweichgleisen annehmen kann, kann durch den Fachmann durch Veränderung der Gleichung nachgewiesen werden, dass Null üblicherweise außer mittig ist. 10 veranschaulicht eine Einrichtung zum Erzielen einer guten Annäherung an eine ausgeglichene Kostenfunktion. In 10 bezeichnen die Intervalle [a₁, b₁], [a₂, b₂] und [a₃, b₃] die Orte von Ausweichgleisen entlang dem Hauptkorridor. Die Abteilung der Lokalisierungsfunktion, wie sie für diesen Korridor definiert wurde, wird bei den Mittelpunkten m₁₂ und m₂₃ zwischen den Ausweichgleisen Null. Die Lokalisierungsfunktion, die die Kostenfunktion erzeugt, ist eine Summe von Sigmoiden, von denen jedes im Wesentlichen lediglich innerhalb der unmittelbaren Nachbarschaft zu den Ausweichgleisen beiträgt, für welches sie ein Minimum in der Lokalisierungsfunktion erzeugt. Wird angenommen, dass die Lokalisierungsfunktion bei dem Punkt m₁₂ nicht wesentlich von den Sigmoid-Termen abhängt, mit Ausnahme derjenigen, die zur Erzeugung der Minima für die beiden unmittelbar umgebenden Ausweichgleise verwendet werden, dann kann die Lokalisierungsfunktion in einer vereinfachten Form dargestellt werden. L ~(x;α1,b1,α2,b2) = β – σ(x – b1;α,β) + σ(x – α1;α,β) – σ(x – b2;α,β) + σ(x – α2;α,β) (5-7).
• Es ist zu beachten, dass die Sigmoid-Funktionen zur Verwendung bei der Erzeugung der Lokalisierungsfunktion lediglich diese Sigmoid-Funktionen sind, die Ausweichgleise zur Linken und Rechten des interessierenden Punkts auf der Lokalisierungsfunktion repräsentieren.
• Entsprechend der Berechnung gilt:

  

  vorausgesetzt, dass gilt: m12 – b1 = α2 – m12 & m12 – α1 = b2 – m12 , wie dies in 10 gezeigt ist. Dieses Erfordernis zwingt die beiden Ausweichgleise selbstverständlich zu derselben Länge, und es muss das nächste Ausweichgleis entsprechend dem Intervall [a₃, b₃] sodann dieselbe Länge wie das Ausweichgleis entsprechend dem Intervall [a₂, b₂] aufweisen. Mittels Induktion folgt hieraus, dass sämtliche Ausweichgleise entlang des Korridors für eine Ausgeglichenheit der Lokalisierungsfunktion des Korridors gleiche Längen aufweisen müssen.
• Wird ein derartiges Artefakt verwirklicht, dann führt dies zu zwei Auswirkungen:
• (1) die Suche kann zumindest geringfügig Kreuzungspunkte nicht korrekt lokalisieren, da in dem Modell die exakte Position der Ausweichgleise nicht wiedergegeben ist;
• (2) Ausweichgleislängen werden nicht in genauer Weise relativ zu den Zuglängen dargestellt.
• Bezüglich dieser Nachteile ist der letzte Nachteil tatsächlich ohne Folgen, da die Modifikation der Lokalisierungsfunktion zur Berücksichtigung der Ausweichgleislängen nicht den nachfolgenden Schritt der vorliegenden Erfindung (der nachstehend noch beschrieben wird) beeinträchtigen wird, in welchem die Zuglänge relativ zur Ausweichgleislänge betrachtet wird. Der vorherige Effekt hat eine geringe Auswirkung, da mit dem Bestreben, die Zugkreuzungspunkte in die Nähe der Ausweichgleise zu bringen, die Möglichkeit eröffnet wird für geringe Anpassungen der Zuggeschwindigkeit zur Sicherstellung, dass Kreuzungen bei den Ausweichgleisen auftreten. Dieser Schritt der vorliegenden Erfindung wird ebenfalls nachstehend noch beschrieben.
• In einem weiteren Ausführungsbeispiel, das insbesondere vorteilhaft ist, falls ein großer Unterschied zwischen dem kürzesten und längsten Ausweichgleis besteht, wird zu Anfang von Ausweichgleisen mit gleicher Länge ausgegangen, wodurch ein Versatz zwischen den Ausweichgleisen in einem frühen Stadium der Suche verhindert wird, worauf dann die Lokalisierung langsam auf korrigierte Ausweichgleislängen im Verlauf des Suchablaufs zurückgeführt wird.
• Insbesondere kann dies in einem weiteren Ausführungsbeispiel der vorliegenden Erfindung implementiert werden, wie es nachstehend angegeben ist. Vor Beginn des Ablaufs wird
• (1) die durchschnittliche Ausweichgleislänge s_avg berechnet zu
  
• (2) die Position jedes Ausweichgleises S_i (entsprechend dem Korridorintervall [a_i, b_i]) neu definiert entsprechend dem Intervall [a'_i(0), b'_i(0)], wobei gilt
  
• (3) wird für jede ganze Zahl n > 0 definiert
  
  wobei λ eine positive Realzahl ist. Dabei ist zu beachten, dass gilt
  
• Der Prozess beginnt mit n = 0 und n wird in Abhängigkeit von einer vorbestimmten Form im Verlauf der Suche vergrößert.
• Beispielsweise wäre eine bekannte Form die Beachtung, wenn aufeinanderfolgende Werte der Kostenfunktion (während des vorstehend beschriebenen Gradientensuchablaufs) eine Differenz kleiner als ein vorbestimmter Schwellenwert (siehe auch beispielsweise den Schwellenwert ε, auf den in Verbindung mit Gleichung 8-3 und den unmittelbar nachfolgenden Textteil Bezug genommen wird) aufweisen, worauf begonnen wird, n (relativ zu den Unterschieden in den Ausweichgleisen) zu vergrößern und die Lokalisierungsfunktion neu zu berechnen, bis die Ausweichgleislängen mit einer Genauigkeit von 5% erreicht sind. Dies ermöglicht der Anfangslokalisierungsfunktion der ausgeglichenen Lokalisierungsfunktion zu entsprechen, so dass Ausweichgleise nicht lediglich infolge ihrer Länge bevorzugt behandelt werden. Der anfängliche "Zuschlag" der Kreuzungen für das eine oder andere Ausweichgleis erfolgt unausgeglichen. Da n vergrößert wird, wird die Lokalisierungsfunktion in genauerer Weise den tatsächlichen Korridoraufbau wiedergeben, so dass schließlich ein genauer Fahrplan erhalten wird.
• Berücksichtigung der Zuglängen in Vergleich zu Ausweichgleislängen
• Die vorstehend beschriebene Kostenfunktion ermöglicht die Suche nach einem durchführbaren Fahrplan lediglich insoweit, als dass Züge in der Nähe von Ausweichgleisen einander begegnen werden. Eine Bezugnahme auf die Länge der Züge relativ zu den Ausweichgleisen ist bisher nicht erfolgt, und haben zwei Züge eine "durchführbare" Begegnung bei einem Ausweichgleis, das weder den einen noch den anderen Zug aufnehmen kann, dann ist die Situation (Begegnung) nicht tatsächlich durchführbar. Es gibt andere Gründe, nach denen Züge keine Ausweichgleise benutzen sollen, in Abhängigkeit von ihrer Einstufung, beim Transport von gefährlichen Materialien und dgl., so dass die nachfolgende Analyse zum Blockieren des Anwendens einer Umleitung auf ein Ausweichgleis für einen bestimmten Zug sich auf mehr Situationen bezieht als die Zuglänge im Vergleich zur Ausweichgleislänge.
• Die Kostenfunktion gemäß der Gleichung 5-6 wird nicht eine derartige Unmöglichkeit (Undurchführbarkeit) verhindern, wobei jedoch in einem anderen Ausführungsbeispiel eine einfache Änderung der Lokalisierungsfunktion (Gleichung 5-5), auf der die Kostenfunktion basiert, ausreichend ist, um derartige Unmöglichkeiten zu verhindern.
• Im Einzelnen umfasst die Kostenfunktion einen Term für jeden möglichen Zugfahrstreckenkreuzungspunkt. In dem vorhergehenden Ausführungsbeispiel sind sämtliche Terme von genau derselben Form. Es wird nun angenommen, dass die Lokalisierungsfunktion definiert wird, so dass sie speziell für jeden möglichen Kreuzungspunkt der Zugfahrstrecken ist, und dies ist im Folgenden angegeben. In diesem Fall wird ausgehend von dem Zusammenhang der 2 verallgemeinert, und es wird angenommen, dass eine Gesamtanzahl von n_s Ausweichgleisen S₁,..., S_ns entlang des Korridors besteht und n_T Züge T₁,..., T_n in dem Korridor fahren. Die folgenden Bezeichnungen sind erforderlich.
• Es sei Hi = die Länge des Ausweichgleises Si (i = 1,..., ns) (6-1) und Mi = die Länge des Zugs Ti (i = 1,..., nT) (6-2)
• Für zwei beliebige Züge T_i und T_j wird die nachfolgende Menge von Ausweichgleisen aus sämtlichen Ausweichgleisen des Korridors bestimmt. Sij = {Sk/k∈{1,..., N} & ((Mi ≤ Hk) ∨ (Mj ≤ Hk ))} (6-3)
• S_ij ist eine Untermenge der Ausweichgleise entlang des Korridors, auf welches zumindest einer der beiden Züge T_i und T_j übergeleitet werden kann. Falls die Lokalisierungsfunktion für den Kreuzungspunkt der Zugfahrstrecken der Züge T_i und Tj nicht die Sigmoid-Ausdrücke (siehe Gleichung 5-7) entsprechend den nicht in S_ij enthaltenen Ausweichgleisen umfasst, dann wird sie auf einem hohen Wert bleiben, obwohl y_ij; innerhalb eines Ausweichgleises liegt, wobei jedoch dieses Ausweichgleis zu kurz für jeden der Züge ist. Auf diese Weise bewirkt die Berücksichtigung der Ausweichgleislänge im Vergleich zur Zuglänge tatsächlich die Verminderung der Berechnungskomplexität der Kostenfunktion.
• Zum speziellen erneuten Definieren der Kostenfunktion in dieser Form wird zuerst die Lokalisierungsfunktion erneut definiert, so dass sie spezifisch für Zugpaare ist, wobei gilt

  
• Hierbei bezeichnet der Index "h" die Identifizierung eines Ausweichgleises.
• Schließlich wird die Kostenfunktion erneut definiert als

  

  wodurch die Definition der Durchführbarkeit erweitert wird, so dass nun der Wert C(y →) dann und nur dann niedrig wird, falls:
• (1) sämtliche Zugfahrstreckenkreuzungen an Ausweichgleisbalken (2) auftreten, und
• (2) zumindest einer der beiden Züge für eine derartige Kreuzung auf das betreffende Ausweichgleis umgeleitet werden kann.
• Dabei ist zu beachten, dass dieses Verfahren erweitert werden kann, über die Berücksichtigung der Zuglänge im Vergleich zur Ausweichgleislänge: falls keiner der beiden Züge T_i und T_j auf das Ausweichgleis S_k aus bestimmten Gründen übergeleitet werden kann, dann kann die Lokalisierungsfunktion für den Kreuzungspunkt y_ij den Ausdruck entsprechend S_k weglassen. Beispielsweise kann der Fall vorliegen, dass ein Kohlenzug auf S_k übergeleitet werden könnte, wobei er jedoch nicht erneut infolge einer Steigung anfahren könnte, und der überschneidende Zug, ein multimodaler Zug absolut nicht für einen Kohlenzug auf ein Ausweichgleis geführt wird. Obwohl in diesem Fall die Ausweichmöglichkeit für jeden der beiden Züge ausreichend wäre, wird diese Möglichkeit in jedem Fall von der Berücksichtigung ausgeschlossen. Wie es aus anderen Ausführungsbeispielen klar wird, kann die Definition von jedem Wert S_ij verkleinert werden zum Ausschließen von Fällen wie den vorhergehenden Fall, so dass die Möglichkeit verbessert wird, dass der Suchablauf nicht durchführbare (nicht akzeptable) Überleitungen auf ein Ausweichgleis verhindert.
• Ökonomische Kosten, frühe Abfahrt und Geschwindigkeitsbeschränkungen
• Die Kostenfunktion gemäß der Beschreibung in den Gleichungen 5-6 oder 6-6 vereinfacht das Auffinden von durchführbaren Zugfahrplänen, umfasst jedoch noch keine Kenntnis anderer Effekte zum Ändern der individuellen Zugfahrpläne zum Erzielen einer Durchführbarkeit. In einem anderen Ausführungsbeispiel wird die Kostenfunktion derart modifiziert, dass gemeinsam die Fahrplandurchführbarkeit und die ökonomischen Kosten einer späten Ankunft gemeinsam berücksichtigt werden.
• Ökonomische Kostenfunktion (späte Ankunft)
• Ein Eisenbahnfrachtservice umfasst unterschiedliche Arten von Leistungsanreizen für eine zeitgerechte (pünktliche) Anlieferung der Fracht. Im vorliegenden Fall werden zwei Arten von Verzögerungsstrafen berücksichtigt:
• (1) Schrittfunktionsstrafe – falls ein Zug T_i eine vorbestimmte Anlieferungszeit t_i versäumt, wird eine festgelegte Strafe H_i verhängt,
• (2) eine Schrittfunktion plus lineare Vergrößerung – falls die vorbestimmte Anlieferungszeit t_i versäumt wird, wird eine unmittelbare Strafe h_i (möglicherweise auch 0) verhängt, die danach linear mit einer Rate von m_i Dollar pro Stunde vergrößert wird.
• 11A veranschaulicht eine einzelne allgemeine Form für diese beiden Fälle, da sowohl h_i als auch m_i 0 oder positiv werden können. Somit veranschaulicht 11A eine kombinierte Strafenfunktion einschließlich sowohl einer Schrittfunktionsstrafe als auch einer linearen Strafe.
• Die vorgeschlagene Kostenfunktion ist keine differenzierbare Funktion, da sie zum Zeitpunkt t_i keine definierte Steigung aufweist. Diese Tatsache schließt die Verwendung jeglicher Gradientensuchverfahren zur Minimierung der ökonomischen Kosten aus oder macht es zumindest kompliziert, sofern nicht spezielle Toleranzen zum Zeitpunkt t_i oder in dessen Nähe ermöglicht werden. Aus diesem Grund zeigen die 11B und 11C zwei Annäherungen an die Kostenfunktion, eine Schritt-plus-Linear-Strafe und eine lediglich lineare Strafe. In beiden Figuren ist ein Liniensegment auf eine Sigmoid-Funktion in der Weise aufgesetzt, dass die resultierende Funktion in allen Punkten differenzierbar ist.
• Für die Schritt-plus-Linear-Strafe wird eine Sigmoid-Funktion verwendet, die die Kosten bis zu einer Zeit geringfügig über t_i darstellt, an welche dann eine Linie mit der Steigung m_i angehängt wird. Siehe in diesem Zusammenhang 11B. Wird der Übergangspunkt von der Sigmoid-Kurve zu dem Liniensegment bei dem Punkt der Sigmoid-Kurve gewählt, bei dem die Steigung exakt m_i ist (Bezugszeichen 110), dann ist die resultierende Annäherung differenzierbar in allen Punkten, und ist daher problemlos in einen Gradientensuchablauf integrierbar. Falls (t_c, y_c) den Übergangspunkt bezeichnet, dann kann die differenzierbare Version der Strafenfunktion definiert werden gemäß

  
• Die hierbei verwendeten Sigmoide weisen Werte β₁ von 1 auf, so dass die Bezeichnung für den Parameter β₁ in jedem Sigmoid unterdrückt wird. Diese Auswahl wird durchgeführt, so dass die Asymptote des Sigmoids in der Weise bestimmt wird, dass sie h_i annimmt, in Verbindung mit dem zu repräsentierenden Strafewert.
• Der Wert von α_i ist positiv und kann gewählt werden zum Annähern der Schrittkosten so genau wie gewünscht. In einem Ausführungsbeispiel wird die Suche gestartet mit "sanften" Sigmoiden, und es werden sodann die Werte von α_i im Verlauf des Suchablaufs vergrößert. Dies ermöglicht den schnellen Fortgang einer frühen Suche in Richtung korrekter ökonomischer Entscheidungen, und in einer späteren Stufe der Suche wird die Information bezüglich der ökonomischen Kosten weiter verfeinert zur Bereitstellung eines genaueren Ergebnisses.
• Zur Bestimmung des Übergangspunkts 110 ((t_c, y_c) in 11B) ist es nötig, die Gleichung für den Wert von t_c mit t_c > t_i zu lösen.
• 
• Das Verfahren zum Lösen dieser Gleichung ist für den Fachmann auf diesem Gebiet bekannt. Es ist anzumerken, dass die Steigung von σ(t – t_i; α_i) überall positiv ist und ein Maximum bei dem Punkt t = t_i annimmt. Das Maximum kann so hoch wie möglich angehoben werden durch Auswählen eines großen Werts für α_i, wobei die Lösung der Gleichung 7-2 immer positiv ist.
• Zu Zwecken der Darstellung des Gradienten, wie es nachstehend noch beschrieben wird, ist zu beachten, dass die unabhängige Variable t in der Gleichung 7-1 tatsächlich eine Funktion der Abfahrtszeit d_i und der Geschwindigkeit s_i des Zugs T_i ist, so dass die Gleichung wie folgt umgeformt werden kann.
• 
• l0C verwendet ferner einen Übergang von dem Sigmoid zu einem Liniensegment bei dem Punkt 112 auf dem Sigmoid, bei welchem die Steigung exakt diejenige der Linie ist: die Differenz besteht darin, dass in diesem Fall der Übergangspunkt t_c kleiner als t_i ist. Mit Ausnahme dieser Tatsache ist die Beschreibung der Annäherungsfunktion identisch zu derjenigen gemäß den Gleichungen 7-1 und 7-3.
• Es werden nun die Kostenfunktionen gemäß den Gleichungen 5-6 oder 6-6, wie folgt, erweitert. Die erweiterte Kostenfunktion zur Berücksichtigung sowohl der Fahrplandurchführbarkeit als auch der ökonomischen Kosten wird definiert durch

  

  wobei
  η∈[0,1] ein Gewichtungsfaktor zwischen 0 und 1 ist zur Verwendung einer Anpassung der relativen Wichtigkeit zwischen den Betrachtungen der ökonomischen und der Fahrplandurchführbarkeit.
• d → = (d₁, d₂,..., d_nT) ist ein Vektor der Zugabfahrtszeiten, und
• s → = (s₁, s₂,..., s_nT) ist der Vektor der Zuggeschwindigkeiten.
• Tatsächlich sind die Kreuzungspunkte y der Zugfahrtstrecken Funktionen der Zugabfahrtszeiten und der Geschwindigkeiten, so dass die Gleichung 7-4 entsprechend umgeformt werden kann.

  

  und es ist aus dieser letzten Form erkennbar, dass der Gradient gemäß der nachstehenden Beschreibung direkt berechnet werden kann.
• Der Wert des Gewichtungsfaktors η muss ausgewählt werden, und die Auswahl ist von einiger Wichtigkeit. Es ist zu beachten, dass die gemäß Gleichung 7-5 definierte Kostenfunktion nach oben getrieben wird sowohl durch unmögliche Fahrplangestaltungsauswahlvorgänge als auch durch Auswahlvorgänge, die Züge verspätet werden lassen, und umgekehrt. Das Problem entsteht, wenn Änderungen der Abfahrtszeiten oder Geschwindigkeiten gegenseitig ausgleichende Effekte in den zwei Hälften der Kostenfunktion der Gleichung 7-5 bewirken. Wird der erste, die Durchführbarkeit betreffende Term um weniger hoch getrieben als der zweite, die Zeitbedingungen betreffende Term herabgesetzt wird, dann kann der Suchablauf die ökonomischen Kosten bis zu einem Grad verstärken, dass sie gegen nicht durchführbare Fahrpläne konvergieren.
• In einem Ausführungsbeispiel kann der Gewichtungsfaktor η während der Suche variiert werden. Wird beispielsweise mit einem niedrigen Wert von η gestartet, so ergibt sich die Tendenz zum Forcieren der niedrigen ökonomischen Kosten auf Kosten der Durchführbarkeit. Dies kann den Zug veranlassen, in der Abfolge Plätze auszulassen zur Verbesserung der gesamten Zeitbedingungen der Ankünfte, bevor die tatsächliche Verstärkung beginnt bei dem Auswählen von Geschwindigkeiten und Abfahrtszeiten, die einen durchführbaren Fahrplan ergeben. In jedem Fall wird die Entscheidung, in welcher Weise n während der Suche zu verändern ist, von tatsächlichen Prüfungen an Beispielen profitieren, und endgültige Mechanismen zum Ändern von n ergeben sich notwendigerweise für den Fachmann auf diesem Gebiet aus Experimenten.
• Bei einem angenäherten Prozess zur Bemessung des Gewichtungsfaktors n ist zu beachten, dass die Kostenkomponente

  

  unterschiedliche Anzahlen von Summanden umfassen und daher unterschiedliche Größen ungefähr proportional zur Anzahl der beteiligten Summanden haben. Liegt beispielsweise eine Gesamtanzahl von 20 Zügen vor, woraus sich 60 Kreuzungen in Liniendiagramm (Bildfahrplan) ergeben, dann umfasst der Ausdruck C(s →,d →) 60 Summanden und der Ausdruck

  

  umfasst 20 Summanden. Zum mehr oder weniger Ausgleichen der Effekte dieser beiden Beiträge zur Kostenfunktion wird man die Gewichtung η auf einen Wert von η = 20/(60 + 20) = 0,25 setzen, wodurch der Beitrag jeder Hälfte der Kostenfunktion (d. h. der beiden Terme

  

  zur gesamten Kostenfunktion ausglichen wird. Aus diesem Beispiel ist erkennbar, dass die Bildung eines bestimmten Werts von η sehr speziell für die betreffende Situation ist, wie es im Allgemeinen für Fachleute auf dem Gebiet einer komplexen Optimierung erkennbar ist.
• Frühabfahrtkostenfunktion
• Die aus ökonomischen Gründen verhängten Verspätungsstrafen sollen verhindern, dass der Zug beliebig spät abfährt. Die Formulierung der Kostenfunktionen, wie sie gegeben sind (Gleichungen 5-6, 6-6, 7-5) weisen keinen Term auf, der verhindert, dass die Zugfahrten beliebig früh durchgeführt werden. Eine Kostenfunktion zur Verhinderung einer frühen Abfahrt kann formuliert werden in Ausdrücken der gleichzeitigen Sigmoid-Funktion, wobei die Kosten wie folgt definiert werden.

  

  wobei
• e_i die frühest mögliche Abfahrtszeit für den Zug T_i ist und
• α'₁ ist mit einem Apostroph versehen, um diesen Wert von α₁ der Gleichung 7-3 zu unterscheiden.
• 12 bezeichnet einen Term dieser Kostenfunktion für den Zug T_i. Die Funktion nimmt schnell hohe Werte an, wenn der Zug T_i in Richtung einer nicht verwirklichbaren Abfahrtszeit verschoben wird, und fällt schnell ab, wenn die Abfahrtszeit in einem realisierbaren (durchführbaren) Bereich eintritt. Es bestehen tatsächlich keine ökonomischen Kosten in Verbindung mit einer frühen Abfahrt, sondern es handelt sich lediglich um eine Sache der Durchführbarkeit. Daher wird den Ausdrücken der Gleichung 7-6 zur Darstellung jedes Zugs beliebig eine Höhe von 1 (d. h. dem asymptotischen Sig moid-Wert von 1) gegeben, und diese Gleichung 7-6 kann ebenso kombiniert werden mit den Kostenfunktionen der Fahrplandurchführbarkeit und der ökonomischen Kosten. Im Einzelnen gilt:

  

  wobei ferner gilt η1 + η2 + η3 = 1 (7-8)
• In einem Ausführungsbeispiel kann die spezielle Gewichtung der Komponenten der Kosten in Gleichung 7-7 in der vorstehend beschriebenen Weise berechnet werden, insbesondere in dem Beispiel mit 20 Zügen und 60 Kreuzungspunkten innerhalb des Korridors. Die Ausdrücke bezüglich der Fahrplandurchführbarkeit und der frühen Abfahrt weisen jeweils 60 Summanden auf und der Term der ökonomischen Strafen wird 20 Ausdrücke aufweisen. Bei der Verwendung einer gleichartigen Gleichung, wie die vorstehend beschriebene Gleichung zur Berechnung von η, ergibt sich das Berechnungsergebnis n₁ = 1/7, η₂ = 3/7 und η₃ = 3/7. Andere Gewichtungswerte können auf der Basis spezieller Benutzerbedingungen gebildet werden.
• Maximalzuggeschwindigkeitskostenfunktion
• Wird es in dem Ausführungsbeispiel durch den Suchprozess ermöglicht, die Zuggeschwindigkeiten zur Erzielung einer Durchführbarkeit und zur Kostenminimierung zu variieren, dann muss eine Einrichtung vorgesehen sein, die verhindert, dass die Geschwindigkeiten die in der Praxis vorgegebenen Grenzen für die beteiligten Züge und befahrenen Strecken überschreiten. In diesem Ausführungsbeispiel wird eine zu sätzliche Komponente der Kostenfunktion gebildet, die derartige Geschwindigkeitsbeschränkungen absichert. Eine derartige Geschwindigkeitsbeschränkung kann in Analogie zu der Beschränkung einer frühen Abfahrt gemäß Gleichung 7-6 implementiert werden. Insbesondere wird eine Geschwindigkeitskostenfunktion definiert als

  

  wobei
  si (max) = maximal zulässige Geschwindigkeit für den Zug Ti.
• Wie bei den weiteren hier erläuterten Kostenfunktionen handelt es sich um eine differenzierbare Funktion bezüglich der Kreuzungspunkte der Züge innerhalb des Korridors, da die Maximalgeschwindigkeitskostenfunktion aus einer Summe von Sigmoid-Funktionen hergeleitet wurde. Daher kann ein Gradientensuchablauf zum Auffinden der Minima in den Kostenfunktionswerten verwendet werden.
• Die gesamte Kostenfunktion einschließlich der Durchführbarkeit der Begegnungen und Überholungen, der Beschränkungen bezüglich einer frühen Abfahrt und die Berücksichtigung einer späten Ankunft (d. h. ökonomische Strafen) sowie der Beschränkungen der maximalen Zuggeschwindigkeit ist eine Verallgemeinerung der Gleichung 7-7, wobei gilt

  

  und es gilt η1 + η2 + η3 + η4 = 1 (7-11).
• Die spezifischen Werte der Gewichtungsfaktoren für die Komponenten der Gleichung 7-10 können experimentell bestimmt werden. In einem Ausführungsbeispiel unter Verwendung der selben Form, wie sie in Verbindung mit Gleichung (7-8) erläutert wurde, gilt für zwanzig Züge und sechzig Kreuzungen η1 = 0,1 und η2 = η3 = η4 = 0,3.
• Der Gradientensuchablauf
• Der Gradient ∇f(x →) einer Funktion f(x →) ist ein Vektor in demselben Raum wie die unabhängige Variable x →, die in der Richtung der maximalen Änderung von f(x →) innerhalb eines kleinen lokalen Bereichs auf der Fläche der Funktion zeigt, so dass in die Richtung eines lokalen Minimums oder Maximums gezeigt wird. In dieser Form ist er vielfach in die Legenden und Sprache der Optimierungstheorie eingeführt. Eine Berechnung des Gradienten der unterschiedlichen, nachstehend diskutierten Kostenfunktionen erlaubt die Lokalisierung des lokalen Minimums zur Identifikation der Fahrplandurchführbarkeit.
• Im gegenwärtigen Kontext der fahrplanmäßigen Zugsteuerung, wie es vom Fachmann auf diesem Gebiet geschätzt wird, gibt es eine Anzahl möglicher Parameter zur Beschreibung einer Zugfahrstrecke, die zur Auflösung von Konflikten innerhalb eines Eisenbahnkorridors, d. h. zum Erreichen einer niedrigeren Kostenfunktion, verändert werden können. Die mathematischen Bedingungen für eine Gradientensuche, bei der lediglich die Abfahrtszeiten oder Geschwindigkeiten der Züge verändert werden, und bei der sodann sowohl die Abfahrtszeiten als auch die Geschwindigkeiten verändert werden, werden nachstehend erläutert. Zuerst wird lediglich die Kostenfunktion in Verbindung mit der Fahrplandurchführbarkeit (Gleichung 5-6) erläutert, und es erfolgt dann eine Ausdehnung der Kostenfunktion auf die Berücksichtigung der ökonomischen Kosten, der frühen Abfahrt und der maximalen Zuggeschwindigkeit, wie es vorstehend beschrieben worden und wie es durch die Kostenfunktion der Gleichung 7-10 dargestellt ist.
• Gradientensuche zum Optimieren der Fahrplandurchführbarkeit durch Verändern lediglich der Zugabfahrtszeiten
• Zuerst wird angenommen, dass n_T Züge vorliegen und dass der Vektor y → (wie er in Gleichung (5-2) dargestellt ist) sämtliche mögliche Kreuzungspunkte beinhaltet. Jeder Kreuzungspunkt y_ij weist die in der Gleichung 3-6 angegebene Charakterisierung auf, die hier zum allgemeinen Verständnis wiederholt wird.

  

  und y_ij ist direkt ausgedrückt in Ausdrücken der Abfahrtszeiten und der Geschwindigkeiten für sämtliche Züge innerhalb des Fahrplans. Zum schnellen Nachvollziehen werden ebenfalls die Begriffsbestimmungen für die Geschwindigkeiten und die Abfahrtszeiten nachstehend wiederholt, die bereits zuvor ursprünglich eingeführt wurden.
• L = die Länge des Korridors,
• s_i = die Geschwindigkeit des Zugs T_i (ein negativer Wert für den westwärts fahrenden Zug T_i),
• d_i = die Abfahrtszeit (Zeit der Einfahrt in den Kor ridor) des Zugs T_i, und
• 
• Sodann werden die Vektoren definiert: s = (s₁,..., s_nT) und d = (d_l,..., d_nT) . Die Kostenfunktion wird mit den folgenden Termen ausgedrückt. Zur Bezeichnungsvereinfachung wird die Abhängigkeit der Lokalisierungsfunktion und der Kostenfunktionen von α und β unterdrückt.
• 
• Die Aufgabe besteht darin, den Vektor d → (Zugabfahrtszeiten) zum Vermindern der Kostenfunktion zu verändern, und ein Verfahren, das zumindest ein lokales Minimum der Kostenfunktion lokalisieren kann, ist der gradientengerichtete Abfall, der in der folgenden Weise iterativ definiert wird.
• (1) Es wird gestartet mit einer Anfangsschätzung der Abfahrtszeit d₀ für jeden Zug n_T, einem Anhaltekriterium ε > 0 und einer Schrittgröße h.
• (2) Zum Schätzen von d →_n wird der Gradient
  
  der Kostenfunktion für d →_n berechnet zum Verändern von lediglich d →, und zum Normalisieren desselben, so dass er einen Absolutwert von 1 aufweist, wobei gilt
  
• Bei den Bezeichnungen wird die Abhängigkeit der Kostenfunktion von s unterdrückt, da für den vorliegenden Fall lediglich d verändert wird.
• (3) Berechnen des Werts C_n = C(d →_n), berechnen von d →_{n + 1} = d →_n – hg →, und berechnen von C_{n + 1} = C(d →_{n + 1}). (4) Falls |C_n – C_n+1| < ε, wird die Suche beendet und es wird d →_{n + 1} als endgültige Antwort akzeptiert. Andererseits wird d →_n mit d →_{n + 1} ersetzt und es erfolgt eine Rückkehr zu Schritt (2). In dem bevorzugten Ausführungsbeispiel wird die Suche beendet, wenn gilt |C_n – C_{n + 1}| ≤ (.001)C₀ – C₁|. Die Anhalteschwelle für derartige Probleme ist sehr situationsabhängig, wie es im Allgemeinen für den Praktiker auf dem Gebiet der Optimierung erkennbar ist.
• Es muss noch der Gradient

  

  explizit dargestellt werden, der bei der Iteration verwendet wird. Die Kostenfunktion gemäß der Darstellung in der Gleichung 5-6 ist eine Funktion des Vektors der Kreuzungspunkte y →, und die Komponenten von y → sind Funktionen der Komponenten der Vektoren s → und d →. Da an diesem Punkt lediglich d → veränder-1ich ist, ist der Gradient

  

  der Kostenfunktion ein Vektor in der Form

  

  und es wird jede Komponente des Gradienten

  

  durch Anwenden der Kettenregel für die Differentiation erhalten.
• 
• Unter Verwendung der Gleichung 8-6 und des Hilfssatzes (Lemma) A3 in dem Anhang A kann schließlich die k-te Komponente des Gradienten ausgedrückt werden als

  
• Gradientensuche zur Optimierung der Fahrplandurchführbarkeit durch Verändern lediglich der Zuggeschwindigkeiten
• Der überwiegende Teil des vorher erläuterten kann auch hier in gleicher Weise verwendet werden. Der primäre Unterschied besteht darin, dass nun verstärkt wird, dass C(y →) angesehen werden kann als eine Funktion des Vektors s, wobei d konstant gehalten ist, und es wird s verändert zum Auffinden eines lokalen Minimums der Kostenfunktion, wobei die Abhängigkeit von d unterdrückt wird. Dabei wird C(y →) wie folgt dargestellt C(y →) = C(s →) (8-8)
• Beginnend mit

  

  ist es nun noch erforderlich, die Komponenten der Form

  

  zu berechnen unter Verwendung der Differentiationskettenregel. Dabei ergibt sich

  

  und es wird ein expliziter Ausdruck für

  

  wie folgt erhalten.
• 
• Die Auswertungen der Gleichungen 8-10, 8-11 und des Hilfssatzes A3 des Anhangs A führen zu einer endgültigen Form für den Gradienten, wie es nachstehend dargestellt ist.
• 
• Die Suchregel, die den in Gleichung 8-12 berechneten Gradienten verwendet, ist ein exaktes Analogon zur Suchregel, wie sie durch Gleichung 8-7 angegeben ist, wobei jedes Auftreten eines der Vektoren d →, d →₀, d →_n, d →_{n + 1} jeweils durch einen der Vektoren s →, s →₀, s →_n, s →_{n + 1} ersetzt wird.
• Gradientensuche zum Optimieren der Fahrplandurchführbarkeit durch Verändern sowohl der Abfahrtszeit als auch der Zuggeschwindigkeiten
• Unter der Berücksichtigung, dass die Geschwindigkeiten und Abfahrtszeiten der Züge unabhängig voneinander geändert werden können, kann der Ausdruck der Kostenfunktion als eine Funktion sowohl von s → als auch d → ausgewertet werden, d. h. C(y →) = C(s →, d →), und es wird die gemeinsame Veränderung der Geschwindigkeit und der Abfahrtszeit zum Auffinden eines lokalen Minimums der Kostenfunktion betrachtet. In diesem Fall nimmt der Gradientenvektor die folgende Form an

  
• Da s → und d → nicht funktional voneinander abhängig sind, ergibt sich der folgende Ausdruck

  

  so dass die Komponenten des Gradienten der Gleichung 8-13 bereits durch die Gleichungen 8-7, 8-11 und 8-12 bestimmt sind.
• Die Suchregel ist in diesem Falle von gleicher Form wie 8-7, mit der Ausnahme, dass der vereinigte Vektor (Gesamtvektor) betrachtet wird. v → = (s →, d →) (8-15),wobei sämtliche Bezugnahmen auf die Vektoren d →, d →₀, d →_n, d →_{n + 1} in dieser Regel jeweils durch Bezugnahmen auf v →, v →₀, v →_n, v →_{n + 1} ersetzt werden.
• Einbeziehung der Auswirkung einer frühen Abfahrt auf die Gradientensuche
• Es wird nochmals auf die vorstehende Erläuterung hingewiesen, dass eine Kostenfunktion, die hohe Kosten für frühe Zugabfahrten bewirkt und niedrige Kosten in anderen Fällen, in Form von Termen der Sigmoid-Funktion dargestellt werden kann. Es wird Gleichung 6-7 wiederholt.

  

  wobei
• e_i die frühestmöglich Abfahrtszeit des Zugs T_i ist und
• a'_i die Schritte des Ansteigens der Kosten bei der Annäherung an eine frühe Abfahrt beeinträchtigt.
• Der Wert α' kann mittels Experimenten eingestellt werden, wobei das Ergebnis jedoch im Einzelnen nicht von diesem Wert direkt abhängig ist. Ein erster Vorschlag in einem Ausführungsbeispiel für einen Wert α'_i wäre 0,8, obwohl dieser Parameter auch kleiner gemacht werden kann, falls gewisse Freiheiten hinsichtlich frühester Abfahrtszeiten bestehen.
• Bei der Kombination der Frühabfahrtskosten mit den Fahrplandurchführbarkeitskosten ergibt sich eine gewichtete Summe der Terme wie folgt D(s →,d →) = ηC(s →,d →)+(1 – η)E(d →) η∈(0,1) (8-17)
• Dieses Konzept wurde vorstehend beschrieben. Es wird ferner auf Gleichung 7-7 verwiesen, bei der die vereinigte Kostenfunktion die Fahrplandurchführbarkeit, die ökonomischen Kosten und die Auswirkungen der frühen Abfahrt umfasst.
• Da die Gradientenoperation linear im Funktionsraum ist, für den sie angewendet wird, ergibt sich auch folgende Beziehung ∇(D(s →,d →)) = η∇(C(s →,d →)) + (1 – η)∇(E(d →)) (8-18)
• Für den ersten Term auf der rechten Seite der Gleichung 8-17 wird auf die vorherigen Gradientenberechnungen Bezug genommen. Siehe in diesem Zusammenhang auch Gleichung 8-7 mit den Ersetzungen gemäß Gleichung 8-15 und den folgenden Text.
• Bezüglich des zweiten Terms auf der rechten Seite der Gleichung 8-17 oder 8-18 wird angenommen, dass lediglich der Abfahrtszeitvektor d → in einer Suche für einen Fahrplan verändert wird, der sowohl durchführbar ist als auch frühe Abfahrten verhindert. Sodann wird der Gradient von E(d →) relativ zu dem Vektor d → bestimmt, und es ergibt sich der Ausdruck

  

  und es ergibt sich ferner (sie Gleichungen 8-6 und A-2)

  
• Es ist nun möglich, den Gradienten

  

  unter Verwendung der Gleichung 8-7, 8-18 und 8-20 zu bilden. Die Abfahrtszeiten sind unabhängig von den Zuggeschwindigkeiten, i so dass die Kostenkomponente E(d) nicht von den Geschwindigkeiten s abhängig ist. Die endgültige Form des Gradienten ergibt sich somit zu

  

  wobei sowohl die Zuggeschwindigkeiten als auch die Abfahrtszeiten variabel sind, und es ergibt sich

  

  wobei implizit Bezug genommen wird auf die Gleichungen 8-7, 8-12 und 8-15.
• Einbeziehen der ökonomischen Kosten in die Gradientensuche
• Die Kostenarten, die bei einer Eisenbahn für verspätetes Anliefern auftreten, wurden vorstehend diskutiert, und es wurde eine differenzierbare Annäherung zur Funktion der Verspätungskosten als eine Funktion der Zeit ausgedrückt. Bei der Verwendung einer derartigen Annäherung, die überall differenzierbar ist, kann die Vermeidung von Verspätungskosten in den Gradientensuchablauf einbezogen werden. Die Ankunftszeiten werden sowohl durch die Zuggeschwindigkeiten als auch durch die Zugabfahrtszeiten beeinflusst, obwohl entweder die Geschwindigkeit, die Abfahrtszeit oder beide Werte während der Suche veränderlich sein können.
• Die Form der Verspätungskostenannäherungsfunktion ist gegeben durch (siehe Gleichung 7-3)

  

  wobei gilt
• u_i = die tatsächliche Ankunftszeit des Zugs,
• t_i = die Zeit, zu der die Verspätungsstrafen aufzulaufen beginnen,
• h_i = die Größe der Schrittstrafe (in k$),
• m_i = die Rate des linearen Teils der Strafe (in k$/h), und
• t_c = der Übergangspunkt, bei dem die Kostenfunktion von ei ner Sigmoid-Funktion zu einem Liniensegment geändert wird.
• Wird für den derzeitigen Fall die Kostenfunktion auf die Form A_i (u_i) verkürzt, wobei u → = (u₁,..., u_nT), dann kann eine Kostenfunktion ausgedrückt werden, die die Ankunftszeiten sämtlicher Züge berücksichtigt, in der Form:

  
• Es liegt jedoch auch noch die Beziehung

  

  vor, so dass sich hieraus eine alternative Darstellung der Gleichung 8-24 ergibt zu

  
• Diese letzte Form der Kosten ist für den vorliegenden Suchablauf angemessen, da dieser Ablauf auf einer Veränderung der Komponenten der Vektoren s → und d → basiert.
• Zum Einbeziehen der Spätankunftskosten in die Suche wird die Kostenfunktion der Gleichung 8-18 erweitert auf die Form

  

  wobei η_i Gewichtungsfaktoren sind, die die folgende Beziehung erfüllen η1 + η2 + η3 = 1 (8-28).
• Die Auswahl für diese Gewichtungsfaktoren muss experimentell bestimmt werden, und in einem Ausführungsbeispiel der vorliegenden Erfindung ist es möglich, diese iterativ im Fortgang des Suchablaufs zu verändern. Individuelle Benutzer der vorliegenden Erfindung können diese Gewichtungen gemäß einer Bestimmung entsprechend den Eigenschaften des Korridors und den der Eisenbahn für verschiedene Effekte auferlegten Kosten, wie es in dem Suchalgorithmus vorgesehen ist, zuordnen. In dem bevorzugten Ausführungsbeispiel nehmen diese Gewichtungen Werte gemäß der Bestimmung in Verbindung mit der vorstehenden Diskussion der Gleichung (7-8) an.
• Gradientensuche zur Optimierung der Fahrplandurchführbarkeit, der frühen Abfahrten und der ökonomischen Kosten durch Verändern lediglich der Zugabfahrtszeiten
• Eine Suche mit der Verwendung der Spätankunftskostenfunktion der Gleichung 8-27 kann eine Veränderung lediglich der Abfahrtszeiten d beinhalten, wobei in diesem Fall der Gradient, mittels dessen die Suche ausgerichtet ist, von einer Form analog zu der in Gleichung 8-19 gezeigten Form ist. Eine Komponente des Gradientenvektors kann daher ausgedrückt werden in der Form

  
• Unter Berücksichtigung der Gleichung 8-6 und 8-20 kann die Gleichung 8-29 erweitert werden zu der Form

  

  wobei dieser Ausdruck unter Zuhilfenahme der Gleichung 8-7 eine explizite Darstellung der Komponenten des Gradienten von D(s →, d →) bereitstellt, wenn lediglich die Zugabfahrtszeiten verändert werden.
• Gradientensuche zur Optimierung der Fahrplandurchführbarkeit, der frühen Abfahrten und der ökonomischen Kosten durch Veränderung lediglich der Zuggeschwindigkeiten
• Werden die Abfahrtszeiten der Züge konstant gehalten und werden die Geschwindigkeiten verändert, dann nimmt der Gradient zur Verwendung bei der Änderung des Vektors s = (s →₁, ..., s_nT) während der Suche die folgende Form an

  

  hierbei ist E(d →) unabhängig von der Zuggeschwindigkeit. Die k-te Komponente dieses Gradienten kann daher erhalten werden zu

  

  wobei der erste Term auf der rechten Seite der Gleichung 8-32 ausgedrückt werden kann in einer vollständig expliziten Form unter Bezugnahme auf die Gleichung 8-12.
• Gradientensuche zur Optimierung der Fahrplandurchführbarkeit, der früheren Abfahrten und der ökonomischen Kosten durch Verändern sowohl der Zugabfahrtszeiten als auch der Zuggeschwindigkeiten.
• In diesem Fall werden sowohl d als auch s in der vollständigen Kostenfunktion gemäß Gleichung 8-25 verändert, so das der Gradient nunmehr ausgedrückt werden kann als

  
• Es wird erneut der Gradient in seiner Vektorform betrachtet, und die Komponenten des ersten Terms der Summe der linken Seite der Gleichung 8-33 können leicht erhalten werden unter Zuhilfenahme der Gleichung 8-14, die explizit dargestellt wird unter Verwendung der Gleichungen 8-7, 8-11 und 8-12. Die Komponenten des zweiten Ausdrucks können erhalten werden unter Verwendung der Gleichung 8-20, und die Komponenten des dritten Terms können erhalten werden und Verwendung der Gleichungen 8-30 und 8-32.
• Einbeziehen des Maximalgeschwindigkeitsbegrenzungseffekts
• Eine Komponente der Kostenfunktion, die in ihrem Wert stark ansteigt, wenn die Geschwindigkeit s_i eines Zugs T_i nahe an die Maximalgeschwindigkeit S_i ^(max) herankommt, die spezifisch ist für den Zug, wurde vorstehend entwickelt. Diese Komponente wies die Formulierung auf (siehe Gleichung 7-9)

  

  und trat auf als ein gewichteter Term der Kostenfunktion, d. h.

  

  wobei die Summe der Gewichtungen zu 1 in dem bevorzugten Ausführungsbeispiel gewählt wird. Da die Veränderung der Geschwindigkeit unabhängig von den Abfahrtszeiten der Züge ist, ergibt sich

  

  wobei die Beschränkung der Suche durch die Maximalzuggeschwindigkeiten nicht die Komponenten des Gradienten beeinflusst, die als partielle Ableitungen bezüglich der Abfahrtszeiten erhalten wurden. Relativ zu den Gradiententermen, die als partielle Ableitungen bezüglich der Zuggeschwindigkeiten erhalten wurden, gelten die Beziehungen

  

  

  wobei die explizite Form der Ableitung in Gleichung 8-38 entsprechend der Gleichung A-2 des Anhangs ist.
• Darstellen des gesamten Gradienten
• Im Sinne einer Vollständigkeit werden die vollständigen Ausdrücke dieser Komponenten der Gleichung 8-38 nachstehend angegeben. Zuerst gilt

  

  und es werden die Gewichtungsfaktoren η₁, η₂, η₃, η₄ in der Weise ausgewählt, dass die folgende Beziehung erfüllt wird η1, η2, η3, η4 = 1
• Dabei ist zu beachten, dass die Indexangaben des Vektors D → die partiellen Ableitungen zuerst bezüglich s_k platzieren und sodann zum zweiten die partiellen Ableitungen bezüglich d_k, wobei n_T Werte jedes Index vorliegen.

  

  
• Veranschaulichung des Gradientensuchablaufs
• Nachstehend wird ein Beispiel behandelt mit zwölf Zügen, von denen sechs Züge in jeder Richtung in einem Korridor mit 150 Meilen während eines 8-Stunden-Zeitfensters verkehren.
• 13 zeigt das Liniendiagramm (Bildfahrplan) des anfänglichen noch nicht verarbeiteten Fahrplans (d. h. Zugabfahrtszeiten wurden ohne Rücksicht auf die Durchführbarkeit gewählt), und die nachstehende Tabelle 1 zeigt die Information bezüglich jedes Zugs. Es befinden sich zwölf Züge innerhalb des Korridors und der interessierende Zeitrahmen beträgt 8 Stunden (12:00 bis 20:00 Uhr). Die Spalten der Tabelle geben folgendes an:
• (1) Zugidentifikationsnummer (in dem Liniendiagramm als ganze Zahl in der Mitte jeder zugeordneten Linie angegeben)
• (2) Fahrtrichtung (RICHTUNG),
• (3) früheste akzeptable Abfahrtszeit (FRÜHESTE ABFAHRT)
• (4) tatsächliche Abfahrtszeit (TATSÄCHLICHE ABFAHRT)
• (5) späteste Ankunftszeit vor Auferlegung einer Strafe (SPÄTESTE ANKUNFT)
• (6) Anfangsgeschwindigkeit (GESCHWINDIGKEIT)
• (7) Länge (LÄNGE)
• (8) Anfangsstrafe, auferlegt für Verspätung (STRAFE SCHRITT)
• (9) stundenbezogene Strafe für jede Verspätungsstunde (STRAFE STEIGUNG)
• (10) maximal zulässige Geschwindigkeit (MAXIMALGESCHWINDIGKEIT).
• Die Gradientensuche gemäß der vorstehenden Beschreibung wird eingeleitet mittels der Abfahrtszeiten, die verändert werden, mit den konstant gehaltenen Zuggeschwindigkeiten, sowie mit der Kostenfunktion einschließlich den Strafen für frühes Abfahren und der ökonomischen Strafen (d. h. für verspätetes Ankommen). Das sich ergebende Liniendiagramm (Bildfahrplan) ist in 14 gezeigt.
• Aus einem Vergleich der 14 mit 13 ist erkennbar, dass von den anfänglich 31 Punkten von Kreuzungen der Zugfahrstrecken gemäß 13 neun Kreuzungen nahe bei der Durchführbarkeit waren, wobei die Definition "nahe" eher in Termen der Kreuzungspunkte ausgedrückt wird, die zumindest ein Ausweichgleis (Ausweichgleisbalken) 20 berühren. Somit sind 23 Kreuzungspunkte nicht in der Nähe der Durchführbarkeit. In der endgültigen Version von 14 sind einige Kreuzungspunkte verschwunden, insbesondere aus dem Grund, dass die Züge 4 und 5 zu einem Konvoi (in 14 mittels der Nummer 5 auf der betreffenden Linie angegeben) vereinigt wurden, und einige Züge aus dem Liniendiagramm ausgeschlossen wurden. In 14 sind lediglich zwei Kreuzungspunkte erkennbar, die nicht die Definition der "Nähe" erfüllen.
• Tabelle 2 zeigt den endgültigen Fahrplan, der dem ursprünglichen Fahrplan mit Ausnahme der tatsächlichen Abfahrtszeiten der Züge entspricht. Dabei ist zu beachten, dass sämtliche Züge 7,5 Stunden von der tatsächlichen Abfahrtszeit bis zur Ankunft am Bestimmungsort benötigen, so dass lediglich Zug Nr. 6 verspätet ist, wobei jedoch Zug Nr. 6 lediglich um vier Minuten verspätet ist.
• Verbesserung des Gradientensuchergebnisses durch Geschwindigkeitsanpassungen
• In diesem Ausführungsbeispiel wird das Gradientensuchergebnis verändert durch Anpassen der Zuggeschwindigkeiten zwischen den Ausweichgleisen zur Erzielung verbesserter Begegnungen bei den Ausweichgleisen. Der Gradientensuchablauf brachte Zugkreuzungen näher, konnte sie jedoch nicht immer exakt zu dem Mittelpunkt der Ausweichgleise bringen. Dieses Ausführungsbeispiel umfasst ein Verfahren zum Berücksichtigen der tatsächlichen Ausweichverzögerung infolge einer Änderung der auf dem Ausweichgleis gefahrenen Geschwindigkeit der Züge, wie es erforderlich ist zum Aufrechterhalten der Positionen der Kreuzungspunkte bei den Ausweichgleisen. Zur Bereitstellung einer Standartbasis für diesen Ablauf wird gemäß diesem Ausführungsbeispiel zuerst das Ergebnis der Gradientensuche angepasst, so dass die Kreuzungspunkte der Zugfahrstrecken y-Koordinaten aufweisen, die präzise an den Mittelpunkten der Ausweichgleise liegen. Die Kreuzungspunkte müssen bewegt werden zur Vergrößerung der Zeitkoordinate zur Sicherstellung, dass sämtliche wichtigen Kreuzungspunkte bereits in angemessener Weise angepasst wurden.
• Zum Zentrieren der Kreuzungspunkte bei den Ausweichgleisen und zum Überleiten der speziellen Züge auf die Ausweichgleise ist es erforderlich, die Zuggeschwindigkeit der beteiligten Züge in gewissem Umfang zu verändern. Selbstverständlich wirkt sich eine Änderung der Zuggeschwindigkeit an einem beliebigen Punkt nachteilig auf die Fahrstreckenkennlinie aus, wodurch die Positionen ihrer jeweiligen zukünftigen Begegnungen mit anderen Zügen verschoben werden können. Dies wird vermieden durch eine Forderung, dass die zentrierten Kreuzungspunkte fest bleiben, und dass die Zuggeschwindigkeiten im erforderlichen Umfang verändert wer den, so dass diese Bedingung erfüllt wird. Insbesondere wird der Zug, der nicht an einem vorgegebenen Kreuzungspunkt auf das Ausweichgleis geleitet wird, beschränkt für einen Durchlauf durch den zentrierten Kreuzungspunkt, und der auf das Ausweichgleis zu leitende Zug wird einer Geschwindigkeitsanpassung im erforderlichen Umfang unterzogen im Hinblick auf eine Ankunft und ein Überleiten auf das Ausweichgleis, bevor sich der Gegenzug innerhalb eines Überschneidungsbereichs (d. h. einer minimalen Anhalteentfernung) bezüglich des ausweichenden Zugs befindet.
• Die Kreuzungspunkte werden in einer ansteigenden Zeitreihenfolge verarbeitet, so dass sämtliche Steigungsanpassungen der Linien der Zugfahrstrecken auch frühere Änderungen berücksichtigen können. Da jeder Kreuzungspunkt verarbeitet wird, kann die Entscheidung, welcher Zug auf das Ausweichgleis zu leiten ist, von verschiedenen Kriterien abhängig sein, die als Spezialregeln gebildet werden können als zusätzlichen Beitrag zu dem gesamten Algorithmus. Ist beispielsweise lediglich einer der beiden Züge zu lang für das Ausweichgleis, dann muss der andere Zug auf das Ausweichgleis umgeleitet werden. Ein anderer spezieller Fall ist denkbar für einen Zug, der nicht erneut anfahren könnte, falls er innerhalb des Korridors an einer Steigung auf das Ausweichgleis geleitet würde (d. h. es kann nicht ausreichend Antriebsleistung zur Verfügung gestellt werden für eine ansteigende Bewegung bzw. ein erneutes Anfahren in der Steigung).
• Gibt es keine speziellen Umstände, die erfordern, dass einer der beiden Züge auf das Ausweichgleis zu leiten ist, dann ist das Kriterium für die Entscheidung, welcher Zug umzuleiten ist, der Aspekt der Zuggeschwindigkeit: hierbei erfordert der Übergang auf ein Ausweichgleis, dass der Zug "früh" bei dem Ausweichgleis ankommt, relativ zu dem zentrierten Kreuzungspunkt, so dass der Zug abgebremst werden kann und ohne Überschneidung mit dem Gegenzug auf das Ausweichgleis übergeleitet werden kann. Eine frühe Ankunft impliziert, dass der Zug eine Geschwindigkeit größer als diejenige, die normalerweise im Gradientensuchablauf gemäß der vorliegenden Erfindung zugeordnet wird, aufweist, und es besteht selbstverständlich eine praktische obere Grenze bezüglich der Zuggeschwindigkeit, wie dies nachstehend noch beschrieben wird. Die Ausweichentscheidung ist zu treffen auf der Basis, welcher der beiden Züge weniger weit von der oberen Grenze betrieben wird, wobei vorausgesetzt wird, dass dieser Zug ausweichen muss. Ist die Entscheidung einmal getroffen, dann werden die Geschwindigkeit und Ankunftszeiten beider Züge entsprechend den tatsächlichen Erfordernissen des Überleitens auf ein Ausweichgleis des Zugs angepasst.
• 15 zeigt eine derartige Situation, bei der die Kreuzungspunkte (x_ij, y_ij) der Züge T_i und T_j zu der Mitte des Ausweichgleises S_h (bezeichnet durch Punkt (x_ij, (a_h + b_h)/2)) bewegt wurden, vorausgesetzt, dass vorherliegende Kreuzungspunkte, die die Züge T_i und T_j beeinflusst haben, bereits angepasst wurden. Insbesondere ist die erforderliche Geschwindigkeit für die Züge T_i (von S_{h – 1} bis S_h) und für T_j (von S_{h + 1} bis S_h) gegeben durch

  

  wobei

  

  und die Züge T_k, T_p sind die Züge, die jeweils die unmittelbar vorhergehende Begegnung mit den jeweiligen Zügen T_i und T_j repräsentieren.
• Es gibt ebenfalls den Fall, dass kein vorheriger Kreuzungspunkt vorliegt, d. h. wenn der Kreuzungspunkt (x_ij, y_ij) der erste Kreuzungspunkt für beide Züge T_i oder T_j ist, wie dies in 16 dargestellt ist. In diesem Fall wird die Geschwindigkeit, die erforderlich ist zur Sicherstellung einer Kreuzung in der Mitte des Ausweichgleises gegeben durch

  
• 17 veranschaulicht das Ergebnis des Zentrierens sämtlicher Begegnungen für die Gradientensuchergebnisse, wie sie in 14 dargestellt sind, bezüglich der Ausweichgleise 181 bis 188 durch Anpassung der Zuggeschwindigkeiten zwischen den Ausweichgleisen. Insgesamt sind sehr geringe Geschwindigkeitsanpassungen im Allgemeinen ausreichend zum Zentrieren sämtlicher Begegnungen.
• Lösung von Ausweichkonflikten
• Bei dem Zentrieren von Begegnungen oder Vorbeifahrten (Überholungen) treten mögliche unerwünschte Ausweicheffekte auf, die in den 18A und 18B veranschaulicht sind. Nach der Durchführung des Gradientensuchablaufs sind die anfänglichen Kreuzungspunkte in 18A dargestellt. Ein Zug T₁ kreuzt mit einem Zug T₃ bei dem Punkt 180, der Zug T₁ kreuzt mit einem Zug T₄ bei einem Punkt 181 und ein Zug T₂ kreuzt mit dem Zug T₄ bei dem Punkt 182. Das Ergebnis des Zentrierens sämtlicher Begegnungen, dargestellt durch die Punkte 180, 181 und 182 mittels entsprechender Geschwindigkeitsanpassungen gemäß der vorstehenden Beschreibung ist in 18B gezeigt. Der Zug T₁ wird auf das Ausweichgleis S_{n + 1} im Punkt 183 infolge einer Begegnung mit dem Zug T₃ übergeleitet, und der Zug T₄ wird auf das Ausweichgleis S_{n + 1} in Punkt 184 in Folge der Begegnung mit dem Zug T₂ geleitet.
• Das Problem besteht darin, dass die Züge T₁ und T₄ beide auf dasselbe Ausweichgleis S_{n + 1}geleitet werden sollen, obwohl beide in unterschiedlichen Richtungen fahren, da ein Zug auf dem Ausweichgleis wartet, das der anderen Zug belegen soll, bevor der frühere Zug ausgefahren ist. Dieser Forderung kann nicht entsprochen werden, so dass das Ergebnis des Zentrierens sämtlicher Begegnungen tatsächlich wie im vorliegenden Fall zu einem nicht durchführbaren Fahrplan führt. Diese Artefakte werden als Ausweichkonflikte bezeichnet.
• Der Begegnungszentrierungsablauf kann zwei Typen von Ausweichkonflikten bewirken, wie dies in den 19A und 19B gezeigt ist. 19A wiederholt das Ausweichproblem, das bereits in 18B veranschaulicht ist. 19B veranschaulicht eine weitere Ausweichkonfliktsituation, wobei wie in den Fällen der 18B und 19A das Problem erneut darin besteht, dass zwei in entgegengesetzte Richtungen fahrende Züge auf dasselbe Ausweichgleis geleitet werden sollen. Die Züge T₂ und T₃ kreuzen im Punkt 194, wobei der frühere Zug auf das Ausweichgleis geleitet wurde, während die Züge T₁ und T₄ im Punkt 196 kreuzen, wobei der frühere Zug ausweicht. Beide Arten der Ausweichkonflikte gemäß den 19A und 19B können gelöst werden durch Bewegen (Verschieben) der Begegnung der durch den Konflikt betroffenen Züge zu einem benachbarten Ausweichgleis, wie dies in den 20A und 20B dargestellt ist.
• 20A zeigt einen Ausweichkonflikt, der identische ist mit demjenigen von 19A. Der Konflikt am Begegnungspunkt 200 wird gelöst durch eine Aufwärtsbewegung desselben zu dem Punkt 201 in 20B. Dies wird erreicht durch Beschleunigen oder Verzögern der erforderlichen Züge zwischen benachbarten Ausweichgleisen. In gleicher Weise kann der Ausweichkonflikt gemäß 19B gelöst werden durch Abwärtsbewegen desselben.
• Der Ablauf zur Lösung gemäß der Darstellung in 20B (d. h. die Aufwärts- und Abwärtsbewegung der Begegnungen zur Lösung der Ausweichkonflikte) ist erfolgreich, falls die Züge innerhalb des Konflikts höchstens eine Begegnung bei dem Ausweichgleis aufweisen, zu welchem die Begegnung verschoben wird, und wird jedoch nicht zum Erfolg führen, falls beide Züge Begegnungen bei dem Ausweichgleis aufweisen, zu dem ihren Begegnung verschoben wird, wie dies in den 21A und 21B dargestellt ist. In diesem Fall bewirkt die Lösung des ursprünglichen Ausweichkonflikts bei dem Punkt 210 in 21A durch Bewegen desselben zu dem Punkt 211 in 21B schließlich einen weiteren Ausweichkonflikt.
• Es gibt jedoch einen induktiven Weg zur Lösung all dieser Ausweichkonflikte, die sich aus einem Begegnungszentrierungsablauf ergeben: wird der Ausweichkonflikt der 18B und 19A als ein aufwärts lösbarer Konflikt bezeichnet und wird der Ausweichkonflikt von 19B als ein abwärts lösbarer Konflikt bezeichnet, dann ergibt sich daraus, dass jeder Ausweichkonflikt, der an einem Ausweichgleis S₁ auftritt, in der Tat lösbar ist, da der Konfliktpunkt an das Ende des Korridors verschoben werden kann, wo jegliche Begegnungen mit den beiden beteiligten Zügen vermieden werden können durch geringfügiges Ändern der Abfahrts-Ankunftszeiten der beteiligten Züge im erforderlichen Umfang.
• Dies ist in den 22A bis 22D dargestellt, wobei die Darstellungen auf der rechten Seite Lösungen der Ausweichkonflikte auf der linken Seite bilden. Die Kreuzung bei Punkt 220 in 22A wird zu dem Punkt 212 in 22B bewegt durch Vermindern der Geschwindigkeit des Zugs T₁. In 22C wird der Ausweichkonflikt bei Punkt 224 beseitigt durch Bewegen des Kreuzungspunkts der Züge T₁ und T₂ zu dem Punkt 225. Es können nun durchführbare Ausweichvorgänge bei den Kreuzungspunkten 225 und 226 auftreten.
• Es wird nun mittels Induktion gezeigt, dass sämtliche Konflikte lösbar sind, wobei die Basis mittels des in 22 gezeigten Verfahrens bereitgestellt wird, und mit der induktiven Annahme, dass sämtliche, bei dem Ausweichgleis S_{n – 1}, für n ≥ 2, auftretenden Ausweichkonflikte lösbar sind durch Verschieben des Konfliktpunkts an das Ende des Korridors.
• Die 23A bis 23E veranschaulichen einen abwärts lösbaren Ausweichkonflikt auf dem Ausweichgleis S_n, und es wird gezeigt, dass für sämtliche mögliche Variationen dieses Konflikts eine Lösung gebildet werden kann zu einer Si tuation, in welcher sich im ungünstigsten Fall als Ergebnis ein neuer Ausweichkonflikt bezüglich des Ausweichgleises S_{n – 1} ergibt. Entsprechend der induktiven Annahme können sämtliche derartige Ausweichkonflikte gelöst werden. 23A zeigt die ursprüngliche Begegnungssituation. 23B (Fall 1) zeigt die Auslösung, falls der Zug T₁ eine Begegnung bei dem Punkt d aufweist, Zug T₂ keine Begegnung bei Punkt f aufweist und Zug T₅ nicht auf das Ausweichgleis geleitet wird. 23D (Fall 2b) zeigt die Lösung, wenn der Zug T¹ eine Begegnung bei dem Punkt d aufweist, der Zug T₂ keine Begegnung bei dem Punkt f aufweist und der Zug T₅ ausweicht. Die Lösung des (nicht gezeigt) Falls 3, in welcher der Zug T₁ keine Begegnung bei Punkt d aufweist, der Zug T₂ eine Begegnung bei Punkt f ausweist, ist identisch zu dem Fall 2a und 2b. Schließlich veranschaulicht 23E den Fall 4, in welchem Züge T₁ und T₂ beide eine Begegnung am Ausweichgleis S_{n – 1} aufweisen.
• 24 zeigt eine gleichartige Veranschaulichung für einen aufwärts lösbaren Ausweichkonflikt bezüglich S_n mit der Ausnahme, dass die Darstellung begrenzt ist auf einen ungünstigsten Fall, wobei es in Verbindung damit offensichtlich ist, dass Fälle mit weniger beschränkenden Begegnungen ebenfalls lösbar sind, im ungünstigsten Fall mit einem Ausweichkonflikt bei S_n–1. 24 veranschaulicht die ursprüngliche Begegnungssituation mit der Änderung in Verbindung mit der Bewegung der Begegnung bei einem Punkt c zu dem Punkt g, wie es in 24B veranschaulicht ist.
• Das vorstehende Verfahren wird nun wie folgt zusammengefasst: obwohl der Begegnunqszentrierungsablauf ein nicht durchführbares Liniendiagramm infolge von Ausweichkonflikten erzeugen kann, können sämtliche derartige Ausweichkonflikte gelöst werden zu durchführbaren Situation, die keinen Ausweichkonflikt mehr beinhalten. Wird ein Begegnungs punkt von einem Ausweichgleis zu dem nächsten niedrigeren bewegt, dann wird üblicherweise ein bestimmter horizontaler Spielraum entstehen, an welcher Stelle zu platzieren ist, und bis zu einem gewissen Grad können Zuggeschwindigkeitsbegrenzungen bevorzugt werden. Dabei ist zu beachten, dass die Lösung dieser Konflikte zu einigen Fällen führen kann, in welchen ein Zug mit nicht realisierbaren Geschwindigkeiten fahren muss. Dies wird berücksichtigt durch Einbeziehen eines neuen Gradientenoptimierungsablaufs in einem weiteren Ausführungsbeispiel der Erfindung gemäß der nachstehenden Beschreibung.
• Berücksichtigung der Ausweichzeit
• In der bisherigen Beschreibung erlaubt die Erfindung einen anfänglichen Zugfahrplan auf dem Korridor, der aufgebaut wird ungeachtet der Begegnungen und der Vorbeifahrten, und der in Richtung eines Fahrplans bewegt wird, der Begegnungen oder Vorbeifahrten an nicht durchführbaren Orten, d. h. abseits von Ausweichgleisen eliminiert oder minimiert.
• Nach der Anwendung von Abläufen zur Verbesserung der Gradientensuchergebnisse durch Geschwindigkeitsanpassungen und die Auflösung von Ausweichkonflikten gemäß der vorstehenden Beschreibung bezüglich des ursprünglichen Gradientensuchergebnisses wurde ein Liniendiagramm erzeugt, in welchem jede Zugfahrstrecke angegeben ist als eine Sequenz von geraden Liniensegmenten mit den Beschränkungen bezüglich Begegnungen mit anderen Zugfahrstrecken bei den Mittelpunkten der Ausweichgleise. Das Liniendiagramm (Bildfahrplan), das angepasst wurde nach der Gradientensuche im erforderlichen Umfang zur Bewegung sämtlicher Begegnungen zu den Mittelpunkten der Ausweichgleise wird als unvollständiges Liniendiagramm bezeichnet.
• Die Gradientensuche und die Geschwindigkeitsanpassungen erzeugen eine Begegnung zweier Züge bei einem Ausweichgleis, wobei in einem Ausführungsbeispiel nicht tatsächlich das Erfordernis des Ausweichens für einen Zug oder die Tatsache, dass der Zug eine bestimmte Länge aufweist, berücksichtigt wird. Zum tatsächlichen Ausweichen eines Zugs muss dieser bei dem Ausweichgleis weit im Voraus vor dem anderen Zug ankommen, um vollständig auf das Ausweichgleis überwechseln zu können, und es muss der Zug seine Abfahrt verzögern, bis der andere Zug (Gegenzug oder überholender Zug) den Bereich des Ausweichgleises verlassen hat.
• 25 veranschaulicht dieses Problem. Bisher wurde eine Zugfahrstrecke angenähert als ein einziges durchgezogenes Liniensegment (wie beispielsweise in 2), und es wird in Wirklichkeit die Form eines unterbrochenen Liniensegments verwendet, falls der betreffende Zug ausweichen muss. In 25 müssen die Züge T₂ und T₃ ausweichen, so dass die entsprechenden Fahrstrecken L₂ und L₃ die erforderliche Ausweichzeit mittels der horizontalen Liniensegmente 250 und 252 kennzeichnen, die in die Fahrstrecken eingesetzt sind. Die Minimumlänge des horizontalen Segments wird bestimmt durch die Länge und Geschwindigkeit des Gegenzugs. Daher muss der Grad der Auflösung bei der Zugfahrstreckenplanung in diesem Ausführungsbeispiel verbessert werden zum Erhalten eines verwirklichbaren Zugfahrplans auf der Basis der Ergebnisse der Gradientensuche. Es ist erforderlich, die mathematischen Bedingungen des auf ein Ausweichgleis zu leitenden Zugs zu entwickeln, wobei vorausgesetzt wird, dass ein Anfangsfahrplan erhalten wurde unter Verwendung des vorstehenden Gradientensuchablaufs.
• Definition des Zugfahrstreckenvektors
• Implizit sind in der lediglich geometrischen Darstellung, die bisher beschrieben wurde numerischen Größen erforderlich zur Definition des Zugfahrstreckenvektors der Gleichung 10-1. Insbesondere muss für den Zug T_i der Wert von b_i0 (T_i in östlicher Richtung) oder von b_{i,n,s + 1} (T_i in westlicher Richtung) gleich der Abfahrtszeit d_i des Zugs sein, die bestimmt wurde durch den Gradientensuchablauf mit einer möglichen Änderung bei der Auflösung von Ausweichkonflikten. Für einen in östlicher Richtung fahrenden Zug wird angenommen, dass die erste Begegnung mit einem weiteren Zug mit dem Zug T_j bei dem Ausweichgleis S_h, h ≥ 0, auftritt, dann muss insbesondere Ti bei dem Punkt (x_ij, c_h) auf dem Liniendiagramm sein, wie es in 26 gezeigt ist. Dann ergibt sich die Geschwindigkeit s_ih des Zugs Ti von seinem

  

  und es folgt, dass b_ik für k = 1,..., h und e_ik, für k = 1,...,h – 1 in der folgenden Weise bestimmt werden kann.
• 
• Es erfolgt nun ein Übergang zum nächsten Liniensegment (d. h. von Begegnung zu Begegnung), das die Fahrstrecke von T_i definiert, zum Erhalten einer Geschwindigkeit, die bestimmt wird durch die Kreuzungen von T_i mit anderen Zügen, woraus die Ankunftszeit von T_i für sämtliche dazwischenlie gende Ausweichgleisenden bestimmt werden kann, so dass sämtliche erforderliche Daten für den Zugfahrstreckenvektor von T_i mit Ausnahme der Ausweichentscheidungswerte T_ih verfügbar sind. Die Ausweichentscheidungen wurden noch nicht berücksichtigt, und diese Werte werden später definiert.
• Es ist ersichtlich, dass ein analoger Ablauf für nach Westen fahrende Züge bestimmt werden kann, so dass induktiv sämtliche Zugfahrstreckenvektoren unter Verwendung des unvollständigen Liniendiagramms bestimmt wurden.
• Erweiterung der Definition der Zugfahrstrecken
• Die Definition von Zugfahrstrecken als Gleichungen, die eine Entfernung entlang des Korridors auf die Zeit beziehen, wie dies angegeben ist durch Gleichung 3-3, beinhaltet noch nicht die Ausweichzeit und die Ausweichentscheidungen, die für manche Züge erforderlich sind. Vielmehr wurde eine Charakterisierung der Fahrstrecken als gerade Liniensegmente bereitgestellt zum Zwecke der Minimierung der für den Gradientensuchablauf erforderlichen Berechnungen. Zur Verallgemeinerung der Fahrstrecke wird in diesem Ausführungsbeispiel die einfache Definition einer Fahrstrecke verändert durch Addieren von Parametern zur Berücksichtigung der Zugverzögerungen in Verbindung mit den Ausweichgleisen. Weist ein Korridor n_s Ausweichgleise auf, dann kann hier die Definition des Zugfahrstreckenvektors beginnen, und im Hinblick auf eine bequeme Bezeichnung wird das westliche Ende des Korridors als Ausweichgleis So und das östliche Ende des Korridors als Ausweichgleis S_{ns + i} bezeichnet unter der Erkenntnis, dass diese "Ausweichgleise" die Länge von 0 aufweisen. Entsprechend dieser Vereinbarung kann der Zugfahrstreckenvektor für den Zug T_i bestimmt werden zu

  

  wobei
• θ_i = die Richtung des Zugs T_i ist (bereits definiert in der Gleichung 3-4),
• b_ih = die Zeit ist, zu der der Zug T_i das Ausweichgleis Sh (h = 0,..., ns + 1) erreicht,
• e_ih, = die Zeit, zu der der Zug T_i das Ausweichgleis S_h (h = 1,..., n_s) verlässt,
• 
• Die Zeiten, zu denen ein Zug ein Ausweichgleis erreicht oder verlässt ist die Zeit, zu der die Spitze des Zugs das stromauf- oder stromab liegende jeweilige Ende des Ausweichgleises erreicht ("stromab" oder "stromauf" ist definiert relativ zu der Fahrtrichtung des Zugs). Da das Ausweichgleis S_i die Endpunkte a_i und b_i gemessen vom westlichen Ende des Korridors aufweist, bezeichnet im Sinne einer konsistenten Bezeichnung b₀ den Beginn des Korridors, und a_{ns + 1} bezeichnet das Ende des Korridors.
• Einzelheiten des Ausweichablaufs
• 14 zeigt das Ergebnis des Gradientensuchablaufs und zeigt ferner, dass der Suchablauf die Fähigkeit aufweist, die Abfahrtszeiten anzupassen, sodass Zugfahrstrecken sich bei Ausweichgleisen kreuzen. Der Gradientensuchablauf kann üblicherweise nicht in perfekter Weise sämtliche Begegnungen bei den Ausweichgleisen mit diesen übereinstimmend anordnen, und daher wurde der Begegnungszentrierungsablauf vorstehend ebenfalls beschrieben. Wurden einmal tatsächlich sämtliche Begegnungen bei den Ausweichgleisen platziert, dann können Zuggeschwindigkeitsanpassungen verwendet werden zum Interpretieren der Ergebnisse des Liniendiagramms, wobei gezeigt ist, dass die Lokomotiven des Zugs exakt den Mittelpunkt der Ausweichgleise passieren.
• Das Folgende ist nun auf ein Verfahren gerichtet, mittels dessen ein Liniendiagramm (Bildfahrplan, Liniengraph) wie dasjenige von 14 mit bei den Ausweichgleisen zentrierten Begegnungen, wie es vorstehend beschrieben wurde, verändert werden kann zur Bereitstellung eines vollständigen durchführbaren Liniendiagramm-Fahrplans (Bildfahrplan) mit ausweichenden Zügen, sofern erforderlich. Die Betrachtung beginnt mit sämtlichen bei Ausweichgleisen zentrierten Zugbegegnungen, und wobei, soweit erforderlich, sämtliche mögliche Ausweichkonflikte gelöst sind. Der Ablauf wird induktiv sein: zuerst wird die Anzahl sämtlicher Kreuzungspunkte des unvollständigen Liniendiagramms entsprechend der Kreuzungszeit angeordnet, und diese werden sodann in zeitlicher Reihenfolge verändert, sodass jeder Kreuzungspunkt eine durchführbare Ausweichgleisanordnung kennzeichnet.
• 27 veranschaulicht das anwendbare Verfahren, wie es angewendet wird bei dem Kreuzungspunkt y₂₄. Es wird angenommen, dass sämtliche Kreuzungspunkte des Liniendiagramms, die in der Zeit vor y₂₄ liegen, mittels dieses Ablaufs bereits geändert wurden, sodass die erforderlichen Zeit- und Geschwindigkeitsdaten bezüglich der Züge T₂ und T₄, die zeitlich vor dem Punkt y₂₄ liegen, tatsächlich gültig sind. Aus den beiden Fahrstrecken, die durch y₂₄ laufen wird der Zug T₄ für ein Ausweichen ausgewählt, und die Änderung der Fahrstrecke für T₄ ist angegeben mittels der gestrichelten Sequenz der Liniensegmente. Es ist hierbei erforderlich, dass der Zug T₄ mit einer höheren Geschwindigkeit vom letzten Kreuzungspunkt auf der Fahrstrecke (relativ zu dem unvollständigen Liniendiagramm) betrieben wird im Hinblick auf eine Ankunft bei dem Ausweichgleis S_n, sodass der letzte Wagen des Zugs T₄ tatsächlich das Ausweichgleis befährt, bevor die Lokomotive des Zugs T₂ am westlichen Ende des Ausweichgleises S_n ankommt.
• Die 28 und 29 stellen mögliche Begegnungs-/Überholungssituationen zwischen Zügen dar. Hierbei gibt es gemäß der nachfolgenden Darstellung vier grundlegende Fälle:
• (1) ein ostwärts fahrender Zug weicht einem westwärts fahrenden Zug aus,
• (2) ein westwärts fahrender Zug weicht einem ostwärts fahrenden Zug aus,
• (3) ein ostwärts fahrender Zug weicht für eine Überholung einem ostwärts fahrenden Zug aus,
• (4) ein westwärts fahrender Zug weicht für eine Überholung einem westwärts fahrenden Zug aus.
• Es gibt ebenfalls vier Varianten für jeden Fall (und somit eine Gesamtanzahl von 16 Fällen) in Abhängigkeit davon, ob einer oder beide der beteiligten Züge bei dem vorherigen Kreuzungspunkt auf ihren Fahrwegen auf Ausweichgleise übergeleitet werden. Dies hat insofern Bedeutung, als dass ein ein Ausweichgleis verlassender Zug eine niedrigere Anfangsgeschwindigkeit (die (beschränkte) Ausfahrgeschwindigkeit aus dem Ausweichgleis) über ein Segment innerhalb des Ausweichgleises haben wird, als ein Zug, der nicht ausweichen muss.
• Wesentliche Parameter für den Ablauf werden bestimmt in Verbindung mit den 28 und 29. Relativ für jeden Zug T_i sind
• A_ih = die Ankunftszeit des letzten Wagens von T_i am stromauf liegenden Ende des Ausweichgleises S_h,
• D_ih = die Zeit, zu der die Spitze von T_i am stromab liegen den Ende des Ausweichgleises S_h ankommt,
• t_ih = die Zeit, zu der ein nicht umgeleiteter Zug T_i bei S_h den Mittelpunkt des Ausweichgleises S_h passiert,
• V_h = die Einfahr-/Ausfahrgeschwindigkeit jedes Zugs in/aus dem Ausweichgleis S_h,
• p(i,h) = das Ausweichgleis, bei dem T_i die jüngste Begeg nung vor der Begegnung bei S_h hatte.
• f_i(v) = die Minimumanhaltezeit für den Zug T_i bei der Geschwindigkeit v. Die für diese Funktion verwendete Annäherung ist im Anhang B erläutert.
• Obwohl die folgenden Bezeichnungen nicht neu sind, werden sie hier zur Erleichterung der Darstellung wiederholt:
• a_h = die Koordinate des westlichen Endes des Ausweichglei ses S_h,
• b_h = die Koordinate des östlichen Endes des Ausweichgleises S_h,
• M_i = die Länge des Zugs T_i,
• L = die Länge des Korridors (mit dem Ursprung am westlichen Ende), wobei sich schließlich für die Koordinaten des Mittelpunkts des Ausweichgleises S_h ergibt
  
• Relativ zu den früheren Beschreibungen des Zugfahrstreckenvektors für den Zug T_i (Gleichung 10-1) gilt ferner Dih = eih (10-10)und für einen nicht ausweichenden und das Ausweichgleis S_h passierenden Zug mit der Annahme der konstanten Geschwindigkeit über die Länge des Ausweichgleises ergibt sich

  

  wobei der Wert gebildet wurde durch Zentrieren sämtlicher Begegnungen bei den Ausweichgleisen.
• In den folgenden Herleitungen sind die Züge, die sich bei einem Ausweichgleis S_h treffen, die Züge T_i und T_j, und T_i wird immer der auf das Ausweichgleis überzuleitende Zug sein. Die erkennbaren Beschränkungen, die für den ausweichenden Zug T_i erfüllt sein müssen (siehe 28 und 29) sind Aih ≤ Djh (10-12)und Dih ≥ Ajh (10-13).
• Diese beiden Beschränkungen sind in gewissem Rahmen idealisiert, und beide erfordern Änderungen. Zuerst wäre es unsicher, die Ungleichung 10-12 wörtlich anzuwenden, da falls aus beliebigen Gründen der Zug T_i kurz vor seiner vollständigen Überleitung auf das Ausweichgleis angehalten wird, der Zug T_j tatsächlich zu nahe sein kann zum rechtzeitigen Anhalten zur Vermeidung eines Zusammenstoßes. Daher sollte die Bedingung 10-12 ersetzt werden durch die Bedingung Aih ≤ Djh – fj(vj) (10-14)wobei v_j die Geschwindigkeit des Zugs T_j ist, der sich dem Ausweichgleis S_h nähert.
• Die Bedingung 10-13 erfordert ebenfalls eine Änderung, da der Fall auftreten kann, dass T_j tatsächlich das stromab liegende Ende des Ausweichgleises (relativ zu T_i) freigibt bzw. räumt, bevor T_i dort ankommen kann, auch wenn der auf das Ausweichgleis übergeleitete Zug T_i seine Fahrt mit der maximalen Ausweichgeschwindigkeit fortsetzt und am stromab liegenden Ende des Ausweichgleises ankommt. In diesem Fall ist T_ih begrenzt auf die Geschwindigkeit von T_i und nicht auf die Position von T_j, und erreicht den Minimumwert

  

  so dass die nun korrigierte Version der Bedingung 10-14 lautet

  
• Die beschränkenden Bedingungen 10-14 und 10-16 ergeben praktische Sachzwänge (Beschränkungen), mittels denen Begegnungen und Vorbeifahrten (Überholungen) geplant werden können.
• Die Größen in den Ungleichungen sind Funktionen der Zuggeschwindigkeiten der früheren, zwischen den Ausweichgleisen liegenden Segmente und der Abfahrtszeiten von dem letzten Ausweichgleis: Induktiv wird angenommen, dass die Abfahrtszeiten für beide Züge von ihren vorherigen Begegnungen bekannt sind, und es müssen nun die Geschwindigkeiten hergeleitet werden, die erforderlich sind für beide Züge, um bei dem Ausweichgleis S_h anzukommen, sodass die Bedingungen 10-14 und 10-16 erfüllt sind. Die bekannten Größen für die Züge T_i und T_j zu Beginn des Induktionsschritts sind:
• (1) t_jh die Zeit, zu der sich T_j bei der Mitte von S_h befin den sollte (Gleichung 10-11),
• (2) D_i,p(i,h) für T_i,
• (3) D_i,p(j,h) für T_j.
• Zur Erfüllung der Bedingungen 10-14 und 10-16 müssen die Werte D_ih, D_jh, A_ih und A_jh in Ausdrücken von Geschwindigkeiten bestimmt werden, und es sind dann die Bedingungsungleichungen für die zur Erfüllung der Bedingungen erforderlichen Geschwindigkeit zu lösen.
• Die auf diese Weise erhaltenen Geschwindigkeiten gelten für T_i und T_j ausgehend von ihren letzten Begegnungen bis zu ihrer gemeinsamen Begegnung, und werden die Bedingungsungleichungen gelöst (werden sie der erfolgten Ausweichauswahl unterzogen) zum Erhalten dieser Zuggeschwindigkeiten, dann wird ebenfalls die Werte entsprechend den vorstehenden Punkten (1) bis (3) für die Züge T_i und T_j bei dem Ausweichgleis S_h bestimmt, sodass hierdurch der induktive Ablauf (Induktionsablauf) vollständig ist. Ruf die Basis für diese Induktion wird später noch eingegangen.
• Der induktive Schritt für den nicht ausweichenden Zug
• Zuerst werden die Geschwindigkeiten bestimmt aus den Erfordernissen, dass der nicht ausweichende Zug die Mitte des Ausweichgleises S_h zu dem Zeitpunkt t_jh passieren soll:

  
• Dabei ist zu beachten, dass es ebenfalls die beiden nachstehend angegebenen Spezialfälle der Gleichungen 10-17 gibt, tj0 = dj für Tj (östliche Richtung) (10-18) tj,ns + l = dj für Tj (westliche Richtung)und es wird für eine durchgehende Bezeichnung definiert: c0 = 0,und Cns + 1 = L (10-19)
• Zusätzlich erfordert die Gültigkeit der Gleichung 10-17, dass die Entfernung zwischen den Ausweichgleisen S_h und S_p(j,h) die Länge M_j des Zugs T_j überschreitet. Aus den Gleichungen 10-17 kann eine Lösung für die erforderlichen Geschwindigkeiten gebildet werden:

  
• Da nun die Geschwindigkeit für den nicht ausweichenden Zug bestimmt ist, kann nach D_jh und A_jh wie folgt aufgelöst werden:

  
• Für den nicht ausweichenden Zug vervollständigt die Bestimmung von D_jh, in der Gleichung 10-24 den induktiven Schritt des Ausweichsteuerungsalgorithmus. Dabei ist zu beachten, dass, falls Ausweichgleise zwischen S_h und S_p(j,h) vorliegen, die Zeiten der Ankunft und der Abfahrt von diesen Ausweichgleisen implizit in den in den Gleichungen 10-20 bis 10-23 berechneten Geschwindigkeiten enthalten sind. Sei nun k ein Index eines derartigen Ausweichgleises, dann ergeben sich die folgenden Beziehungen:

  
• Ferner ergeben sich folgende Beziehungen:

  
• Der induktive Schritt für den ausweichenden Zug
• Die Hälfte des induktiven Schritts für den ausweichenden Zug T_i (den auf das Ausweichgleis überzuleitenden Zug) ist bereits vollständig, indem der Wert D_ih auf einen beliebigen Wert zur Erfüllung der Bedingung 10-16 gesetzt wird, obwohl normalerweise der Wert so klein wie möglich eingestellt wird. Es muss jedoch ferner die erforderliche Geschwindigkeit für den Zug T_i von dem vorherigen Ausweichgleis S_p(i,h) bestimmt werden, wo T_i eine Begegnung mit S_h hatte, so dass die Bedingung 10-14 erfüllt wird. Dabei ergeben sich vier Fälle in Abhängigkeit davon, ob T_i in östlicher oder westlicher Richtung fährt und ob ein Ausweichen bei S_p(i,h) erfolgt ist oder nicht . Es wird nun A_ih ausgedrückt für jeden dieser Fälle, und es wird sodann die Bedingung 10-14 verwendet zur Bestimmung einer Minimumgeschwindigkeit für Ti.

  
• Da der Wert von D_jh im vorherigen Abschnitt bestimmt wurde, führen die Gleichung 10-28 und die Bedingung 10-12 zu Ungleichheiten für die Geschwindigkeit s_ih oder s_{i,h – 1} von T_i, wie es im Folgenden angegeben ist.

  

  für T_i in östlicher Richtung und ohne Ausweichen bei S_p(i,h),

  

  für T_i in östlicher Richtung und mit Ausweichen bei S_p(i,h),

  

  für T_i in westlicher Richtung und ohne Ausweichen bei S_p(i,h),

  

  für T_i in westlicher Richtung und mit Ausweichen bei S_p(i,h),
  wobei gilt

  
• Sämtliche der Größen auf den rechten Seiten der Ungleichungen 10-29 bis 10-32 sind bekannt, so dass die Geschwindigkeit S_ih oder S_{i,h – 1} für den Zug T_i bestimmt ist, und der induktive Schritt ist somit vollendet. Falls ein Ausweichgleis S_k zwischen den Ausweichgleisen S_h und S_p(i,h) besteht, dann bilden die Gleichungen 25 und 26 die Werte von e_ik und b_ik.
• Die Bildung einer induktiven Basis für den vorstehenden Sachverhalt hängt lediglich von der Beobachtung ab, dass der allerersten Begegnung von einem der Züge T_i oder T_j die Einfahrt in den Korridor aus westlicher oder östlicher Richtung vorausgeht. Alle sodann erforderlichen Berechnungen zum Erreichen des Ausweichgleises und für eine Begegnung bei dem Ausweichgleis Sh, die den zwingenden Bedingungen unterworfen sind, basieren auf der ursprünglichen Abfahrtszeit des relevanten Zugs, für welche D_p(i,h) oder D_p(j,h) gleich gesetzt werden, wie dies der Fall sein kann.
• Ferner bestimmt der vorstehend angegebene induktive Ablauf Geschwindigkeiten sowie die Zeiten der Ankunft und der Abfahrt für jeden Zug bei jedem Ausweichgleis auf der Basis der Begegnungen an dem Ausweichgleisen. Hatte ein Zug seine letzte Begegnung, dann wird die endgültige Geschwindigkeit angepasst zur Sicherstellung, dass der Zug fahrplanmäßig am Ende des Korridors ankommt. Hatte der Zug T_i seine letzte Begegnung bei dem Ausweichgleis S_h, dann ergeben sich die Geschwindigkeiten zwischen allen nachfolgenden Ausweichgleisen, die erforderlich sind zum fahrplanmäßigen Verlassen des Korridors, in der folgenden Weise
• 
• 30 zeigt ein endgültiges und vollständiges Liniendiagramm (Bildfahrplan), das angepasst wurde für zentrierte Begegnungen und für ein Ausweichen von Zügen.
• 31 ist ein Ablaufdiagramm zum Implementieren eines der Algorithmen gemäß der vorliegenden Erfindung. Das Ablaufdiagramm von 31 kann verarbeitet werden auf jedem spezialisierten oder zu allgemeinen Zwecken dienenden Computer. Der zugehörige Programmcode (Softwarecode), der erforderlich ist zum Implementieren des in 31 gezeigten Ablaufdiagramms, kann von jedem Fachmann auf dem Gebiet der Programmierung erstellt werden, wenn ihm die Information aus 31 und die vorstehend angegebene Beschreibung der vorliegenden Erfindung zur Verfügung steht.
• Der Ablauf beginnt mit einem Schritt 310, in welchem die Anfangsbedingungen gebildet werden. Es wird ein Anfangsvektor y →_n angenommen, der entweder die Anfangszuggeschwindigkeit oder die ursprünglichen Abfahrtszeiten der Züge des Korridors oder beides angibt. Der Vektor y →_n wird verwendet zur Berechnung der Kreuzungspunkte in einem Schritt 312, und es wird sodann der Wert der Lokalisierungsfunktion für jeden berechneten Kreuzungspunkt in einem Schritt 314 bestimmt. In einem Schritt 316 werden die Lokalisierungsfunktionswerte aufsummiert zur Erzeugung einer Fahrplandurchführbarkeitskostenfunktion mit einem Argument y →_n. Gemäß der vorstehenden Beschreibung gibt es viele unterschiedliche Kostenfunktionstypen in Verbindung mit unterschiedlichen Ausführungsbeispielen der vorliegenden Erfindung. Beispielsweise bezeichnet Gleichung 8-17 zwei Kostenfunktionen. Die Kostenfunktion der Fahrplandurchführbarkeit (C) und eine Kostenfunktion in Verbindung mit frühen Abfahrtswirkungen (E). Die ökonomische Kostenfunktion wird in Gleichung 8-26 definiert, und die Maximumgeschwindigkeitskostenfunktion wird in Gleichung 7-9 definiert. In Abhängigkeit von dem Ausführungsbeispiel der vorliegenden Erfindung werden eine oder mehrere dieser Kostenfunktionen verwendet zur Erzeugung der Kostenfunktion gemäß Schritt 316.
• In einem Schritt 318 wird der Gradient der Kostenfunktion bei y →_n berechnet. In einem Schritt 320 wird ein neues Argument für die Kostenfunktion erzeugt. Auf dieses Argument wird als y →_{n + 1} Bezug genommen und wird berechnet unter Verwendung des Gradientenwerts des Schritts 318 und einer vorbestimmten Schrittgröße. Diese Schrittgröße ist abhängig von dem Gradientenwert und muss in jeder Situation bestimmt werden im Hinblick auf eine Konvergenz gegen das Funktionsminimum. Es wird ferner Bezug genommen auf den vierstufigen Ablauf, wie er in Gleichung 8-3 angegeben ist. In einem Schritt 3-22 wird die Größe der Differenz zwischen der Kos tenfunktion bei y →_n und y →_{n + 1} berechnet. Bei dem Entscheidungsschritt 324 werden die Ergebnisse des Schritts 322 mit einem Schwellenwert verglichen. Wird der Schwellenwert nicht überschritten, dann wurde das Kostenfunktionsminimum lokalisiert und ein Fahrplan für den Korridor wird gebildet. Gemäß Schritt 325 wird dies in Form eines Diagramms veranschaulicht. Wird der Schwellenwert überschritten, dann können weitere Berechnungen durchgeführt werden zum Auffinden des Kostenfunktionsminimums. Bei diesem Punkt geht der Ablauf zu einem Schritt 326 über, in welchem der vorherige Wert von y →_n nun gleich dem Wert y →_{n + 1} gesetzt wird, und der Ablauf kehrt zu dem Schritt 312 zurück, bei welchem die Kreuzungspunkte erneut berechnet werden. Der Ablauf wird dann mittels der Schritte 314, 316, 318, 320 und 322 fortgesetzt, gefolgt von dem Entscheidungsschritt 324, in welchem die Größe erneut mit dem Schwellenwert verglichen wird.
• Gemäß der vorstehenden Beschreibung gibt es zusätzliche Verfeinerungen für den in dem Schritt 325 gebildeten Fahrplan. Diese Verfeinerungen kennzeichnen zusätzliche Ausführungsbeispiele der vorliegenden Erfindung und werden im Einzelnen vorstehend beschrieben. In der Form eines Ablaufdiagramms sind sie in 32 dargestellt. Anstelle des Übergangs des Ablaufs zu dem Schritt 325 in 31, wenn der Schwellenwert nicht überschritten ist, kann der Ablauf stattdessen mit einem Schritt 340 fortgesetzt werden, der in 32 veranschaulicht ist. Hierbei werden Anpassungen vorgenommen bezüglich Zuggeschwindigkeiten zwischen Ausweichgleisen, so dass die Kreuzungen präzise bei den Ausweichgleisen auftreten werden. Dieses Ausführungsbeispiel ist in Verbindung mit den 15, 16 und 17 beschrieben. In einem weiteren Ausführungsbeispiel können Ausweichkonflikte entsprechend einem Schritt 342 gelöst werden. Dieses Ausführungsbeispiel ist in Verbindung mit den vorstehenden
• 18 bis 24 beschrieben. Die Tatsache der Berücksichtigung der Zeit, während der die Züge das Ausweichgleis befahren (Durchführung des Ausweichvorgangs) wird durch den Ablaufschritt 344 dargestellt. Dieses Ausführungsbeispiel wird vorstehend in Verbindung mit den 25 bis 30 beschrieben. Schließlich bewirkt die Einbeziehung dieser zusätzlichen Ausführungsbeispiele die Erzeugung eines weiteren Zugfahrplans für den Eisenbahnkorridor, wie dies in einem Schritt 346 veranschaulicht ist.
• 
• 
• Anhang A Eigenschaften der Sigmoid- und Lokalisierungsfunktionen.

  
• Das folgende Ergebnis folgt aus der Herleitung der Lokalisierungsfunktion im Hauptteil des Dokuments (Beschreibung), und aus der Anwendung des Hilfssatzes (Lemma) 2.
• Hilfssatz (Lemma) 3: (– ∞,w), (a₁,b₁),... (a_N,b_N),(e,∞) kennzeichnet von einander unabhängige Intervalle, mit – ∞ < a₁ < b_l < a₂. . . < a_N < b_N < ∞. Der Ausdruck L (x, α,β,) wird dann und nur dann auf einen niedrigen Wert definiert, wenn x in einem der Intervalle (–∞, w), (a₁, b₁),...(a_N, b_N), (e,∞) oder in der Nähe des Intervalls liegt, wobei der Ausdruck dann die Form annimmt

  
• Anhang B Eine Zuganhaltezeitannäherung
• Die Grundformel für eine Beschleunigung/Verzögerung eines Körpers ist F = MA (B1),wobei
  F = die aufgebrachte Bremskraft ist,
  M = die Masse des Körpers, und
  A = die Beschleunigung des Körpers ist.
• Ein Zug weist Bremsen an jedem Wagen auf, und jeder Wagen umfasst eine Masse, so das angenommen werden kann, das die gesamte maximale Bremskraft und die Masse proportional zur Länge des Zugs ist. Daher kann die Gleichung B1 auch angegeben werden als A = k, (B2)d. h., die bei der maximalen Abbremsung verfügbare Verzögerung ist (angenähert) unabhängig von der Länge oder Masse des Zugs.
• Zur Auswertung von k wird angenommen, das ein sich mit 50 mph (Meilen pro Stunde) bewegender Zug innerhalb einer Meile anhalten kann, so dass seine durchschnittliche Geschwindigkeit während der (linearen) Verzögerung 25 mph beträgt, und die zum vollständigen Anhalt des Zugs erforderliche Zeit berechnet werden kann zu
  (1 mi./25 mph)(60 min/h) = 2.4 Minuten.
• Somit erhält die Gleichung der Zuggeschwindigkeit v zur Anhaltezeit f(v) die Form f (v) = v/A = v/k (B3)und 2.4 = 50/k, so dass sich ergibt k = 50/2.4 = 20.83 (mph/min).
• Die endgültige Form wird nun erhalten f(v) = V/20.83 (B4),wobei f(v) in Minuten und v in Meilen pro Stunde angegeben sind.
• Anhang C Liste der Variablen
• A_i(t) – die Verspätungsstrafefunktion, die für einen Zug T_i verhängt wurde (Gleichung 7-1)
• A_ih – die Ankunftszeit des Endes des Zugs T_i bei einem stromaufliegenden Ende des Ausweichgleises S_h
• A(s →,d →) – die Kostenfunktionskomponenten zum Bewirken ei ner rechtzeitigen Ankunft
• a_h – der Abstand zum westlichen Ende des Korridors, bei dem das Ausweichgleis S_h beginnt
• B_ih – die Entscheidungsvariable, ob ein Zug T_i bei dem Ausweichgleis S_h ausweicht oder nicht
• b_h – der Abstand zum westlichen Ende des Korridors, bei dem das Ausweichgleis S_i endet (a_i < b_i)
• c(s →,d →) – die Kostenfunktion zum Bewirken von Fahrstre ckenkreuzungen bei Ausweichgleisen
• c_h – der Mittelpunkt des Ausweichgleises S_h
• D_ih – die Abfahrtszeit des Zugs T_i vom stromabwärts liegenden Ende des Ausweichgleises S_h
• d_i – die Abfahrtszeit des Zugs T_i
• d → – der Vektor der Dimension n_T der Abfahrtszeit für sämtliche Züge
• E – der Name des Punktes am östlichen Ende des Korridors,
• E(d →) – die Kostenfunktionskomponente zur Verhinderung des frühen Abfahrens der Züge,
• f_i(v) – die minimale Anhaltezeit des Zugs T_i aus einer Geschwindigkeit v,
• G(s →,d) – die Gesamtfahrplankostenfunktion (Gleichung 7-10),
• H_i – die Länge des Ausweichgleises S_i,
• h_i – die Schrittstrafekosten, die dem verspätet ankommenden Zug T_i auferlegt werden,
• I – die Gesamtheit sämtlicher Kreuzungen der Zugfahrstrecken (auch wenn diese nicht im Liniendiagramm enthalten sind),
• L – die Länge des Korridors
• L_i – die Linie auf dem Liniendiagramm zur Darstellung der Fahrstrecke des Zugs T_i,
• L(y) – die Lokalisierungsfunktion mit Minima entsprechend jedem Ausweichgleis (Gleichung 5-5),
• L(y) – die ausgeglichene Lokalisierungsfunktion (Gleichung 5-7),
• L_ij(y_ij) – die modifizierte Lokalisierungsfunktion, so dass Züge T_i und T_j sich nicht treffen, wenn keiner der Züge dem jeweils anderen ausweichen kann,
• M_i – die Länge des Zugs T_i
• m_i – die Verspätungsstrafe pro Zeiteinheit bei verspäteter Ankunft des Zugs T_i
• n_s – die Anzahl der Ausweichgleise entlang des Korridors
• n_T – die Anzahl der bei der Optimierung einbezogenen Züge
• p(i, h) – das Ausweichgleis vor S_h, bei welchem der Zug T_i eine Begegnung hatte
• S_i – der Bezeichner für das i-te Ausweichgleis für eine Fahrt in östlicher Richtung auf dem Korridor
• s_i – die Geschwindigkeit des Zugs T_i,
• si^(max) – maximal zulässige Geschwindigkeit für den Zug Ti,
• S_ih – die Geschwindigkeit des Zugs T_i zwischen den stromaufliegenden Enden der Ausweichgleise S_h und Sh + 1,
• s → – der Vektor mit der Dimension n_T der Geschwindigkeiten sämtlicher Züge,
• T_i – der Bezeichner für den i-ten Zug,
• T_ij – die Gesamtheit sämtlicher Ausweichgleise, bei welchen zumindest einer der Züge T_i und T_j ausweichen kann,
• t_i – die Ankunftszeit, ab der für den Zug T_i Verspätungsstrafen auflaufen,
• t_jh, – die Zeit, zu der der Zug T_j den Ort c_h erreicht, falls er nicht bei Sh ausweicht,
• t_ij – die Zeitkoordinate in Verbindung mit den Fahrstreckenkreuzungspunkt yij,
• V(s →) – die Kostenfunktionskomponente zur Begrenzung der Zuggeschwindigkeiten,
• v_h – die Einfahr- und Ausfahrgeschwindigkeit für Züge bei dem Ausweichgleis S_h,
• W – der Name des Punkts am westlichen Ende des Korridors (Null auf der Entfernungsachse),
• y_ij – die Entfernung vom westlichen Ende des Korridors, wo die Züge T_i und T_j kreuzen,
• y → – der Vektor sämtlicher Fahrstreckenkreuzungspunkte y_ij,
• α – der Sigmoidfunktionsparameter zur Steuerung der Steilheit des Anstiegs (Gleichung 4-1),
• β – die horizontale Asymptote der Sigmoidfunktion (Gleichung 4-1),
• η₁ – die bei der Durchführbarkeitskomponente C(s →,d) der Kostenfunktion verwendete Gewichtung,
• η₂ – die bei der Spätankunftskomponente A(s →,d) der Kostenfunktion verwendete Gewichtung,
• η₃ – die bei der Frühabfahrtskomponente E(d) der Kostenfunktion verwendete Gewichtung,
• η₄ – die bei der Maximalgeschwindigkeitskomponente V(s →) der Kostenfunktion verwendete Gewichtung,
• θ_{i – eine Variable zur Bezeichnung der Richtung des} Zugs T_i mit dem Wert 0 für eine Fahrt in östlicher Richtung und dem Wert 1 für eine Fahrt in westlicher Richtung,
• σ(x) – die Sigmoidfunktion (Gleichung 4-1)
• Zusammenfassung
• Es wird ein Ablauf beschrieben zur fahrplanmäßigen Steuerung der Fahrt von Zügen in einem Eisenbahnkorridor. Der 5 Eisenbahnkorridor umfasst eine Vielzahl von Ausweichgleisen, auf welche Züge ausweichen können, wenn eine Begegnung oder eine Vorbeifahrt (Überholung) mit einem anderen Zug in dem Korridor auftritt. Ein Gradientensuchablauf wird verwendet in Verbindung mit einer Kostenfunktion zur Bestimmung des optimalen Fahrplans durch Bewegen jeder Begegnung und jeder Überholung zu einem Ausweichgleis. Die einzelnen Zugfahrpläne werden verändert durch Verändern der Zuggeschwindigkeit und/oder der Zugabfahrtszeit (d.h. der Zeit, zu der der Zug in den Korridor einfährt).
• 3

Claims (22)

1. Verfahren zur fahrplanmäßigen Steuerung der Bewegung einer Vielzahl von in einem Eisenbahnkorridor betriebenen Zügen, wobei die den Eisenbahnkorridor durchquerenden Züge auf demselben Gleis kreuzen können, wobei jeder Zug zumindest einen veränderbaren Fahrparameter aufweist, wobei der Eisenbahnkorridor zumindest eine Hauptstrecke und eine Vielzahl von Sekundärgleisen aufweist, auf die ein Zug übergeleitet werden kann zur Vermeidung einer Kreuzung mit einem anderen Zug, wobei das Verfahren die folgenden Schritte umfasst: (a) Herleiten einer Lokalisierungsfunktion zur Darstellung der Eisenbahnkorridors, wobei die Lokalisierungsfunktion einen Wert innerhalb eines ersten Bereichs zwischen Sekundärgleisen aufweist und einen Wert innerhalb eines zweiten Bereichs in der Nähe jedes Sekundärgleises aufweist, wobei die Lokalisierungsfunktion jedes Sekundärgleis mit einer gleichen Länge repräsentiert, (b) Auswählen eines Werts für zumindest einen Fahrparameter für jeden der Vielzahl der Züge, (c) Auffinden der Kreuzungspunkte für die Vielzahl der Züge, (d) Bestimmen des Werts der Lokalisierungsfunktion für jeden Kreuzungspunkt, (e) Aufsummieren der Lokalisierungsfunktionswerte zur Erzeugung einer Fahrplandurchführbarkeitskostenfunktionssumme, wobei die Fahrplandurchführbarkeitskostenfunktionssumme die Kostenfunktion in Verbindung mit der Kreuzung der Züge bei einem Sekundärgleis darstellt, und (f) Ändern eines oder mehrerer der in dem Schritt (b) ausgewählten Werte zum Auffinden des Minimums der Kostenfunktion.
2. Verfahren nach Anspruch 1, wobei der Schritt (a) ferner umfasst: (a1) Berechnen der durchschnittlichen Länge der Sekundärgleise in dem Eisenbahnkorridor, und (a2) Neudefinieren der Grenzen jedes Sekundärgleises entsprechend der Darstellung mittels der Lokalisierungsfunktion, so dass jedes Sekundärgleis eine Länge gleich der durchschnittlichen Länge aufweist.
3. Verfahren nach Anspruch 1, wobei der Schritt (f) ferner umfasst: (f1) Inkrementales Vergrößern der Länge jedes Sekundärgleises von dem Durchschnittswert zu seinem tatsächlichen Wert, und (f2) Ändern eines oder mehrerer der in dem Schritt (b) ausgewählten Werte zum Auffinden des Minimums der Kostenfunktion.
4. Verfahren nach Anspruch 1, wobei der Fahrparameter eine Zuggeschwindigkeit umfasst.
5. Verfahren nach Anspruch 4, ferner mit einem Schritt (g) der Anpassung der Zuggeschwindigkeiten zwischen Sekundärgleisen zur Sicherstellung, dass jede Kreuzung bei einem Sekundärgleis auftritt.
6. Verfahren nach Anspruch 4, ferner mit einem Schritt (g) des Modifizierens der Geschwindigkeit von zumindest einem der Vielzahl der Züge innerhalb des Ausweichgleises zur Berücksichtigung der Zeit, die ein Zug auf einem Sekundärgleis verbringt.
7. Verfahren nach Anspruch 1, wobei der Fahrparameter die Einfahrzeit des Zugs in den Eisenbahnkorridor umfasst.
8. Verfahren nach Anspruch 1, wobei der Fahrparameter die Zuggeschwindigkeit und die Einfahrzeit des Zugs in den Eisenbahnkorridor umfasst.
9. Verfahren nach Anspruch 1, wobei das Sekundärgleis ein Ausweichgleis umfasst.
10. Verfahren nach Anspruch 1, wobei das Sekundärgleis zwei parallele Gleise mit einer dazwischenliegenden Übergangsstelle aufweist.
11. Verfahren nach Anspruch 1, wobei die Lokalisierungsfunktion hergeleitet wird durch Aufsummieren einer Vielzahl von Sigmoidfunktionen, wobei die Sigmoidfunktionen angeordnet sind mit einer Beziehung zueinander und zu den Orten der Sekundärgleise derart, dass die Lokalisierungsfunktion einen Wert in dem ersten Bereich zwischen Sekundärgleisen und einen Wert in dem zweiten Bereich in der Nähe jedes Sekundärgleises annimmt.
12. Vorrichtung zur fahrplanmäßigen Steuerung der Bewegung einer Vielzahl von in einem Eisenbahnkorridor betriebenen Zügen, wobei die den Eisenbahnkorridor durchquerenden Züge kreuzen können, wobei jeder Zug zumindest einen veränderbaren Fahrparameter aufweist, wobei der Eisenbahnkorridor zumindest eine Hauptstrecke und eine Vielzahl von Sekundärgleisen aufweist, auf das ein Zug übergeleitet werden kann zur Vermeidung einer Kreuzung mit einem anderen Zug, wobei die Vorrichtung umfasst: eine Einrichtung zur Herleitung einer Lokalisierungsfunktion zur Darstellung des Eisenbahnkorridors, wobei die Lokalisierungsfunktion einen ersten Wert innerhalb eines ersten Bereichs zwischen Sekundärgleisen und einen Wert innerhalb eines zweiten Bereichs in der Nähe jedes Sekundärgleises aufweist, wobei die Lokalisierungsfunktion die Sekundärgleise mit gleicher Länge darstellt, eine Einrichtung zum Auswählen eines Werts für zumindest einen Fahrparameter für jeden der Vielzahl der Züge, eine Einrichtung zum Auffinden der Kreuzungspunkte für die Vielzahl der Züge, eine Einrichtung zur Bestimmung des Werts der Lokalisierungsfunktion für jeden Kreuzungspunkt, eine Einrichtung zum Aufsummieren der Lokalisierungsfunktionswerte zur Erzeugung einer Fahrplandurchführbarkeitskostenfunktionssumme, wobei die Fahrplandurchführbarkeitskostenfunktionssumme die Kostenfunktion in Verbindung mit der Kreuzung der Züge bei einem Sekundärgleis darstellt, und eine Einrichtung zum Ändern eines oder mehrerer der ausgewählten Werte zum Auffinden des Minimums der Kostenfunktion.
13. Vorrichtung nach Anspruch 12, wobei die Einrichtung zur Herleitung der Lokalisierungsfunktion umfasst: eine Einrichtung zur Berechnung der durchschnittlichen Länge der Sekundärgleise in dem Eisenbahnkorridor, und eine Einrichtung zum Definieren der Grenzen jedes Sekundärgleises entsprechend der Darstellung durch die Lokalisierungsfunktion, so dass jedes Sekundärgleis eine Länge gleich der durchschnittlichen Länge aufweist.
14. Vorrichtung nach Anspruch 12, mit einer Einrichtung zum inkrementalen Vergrößern der Länge jedes Sekundärgleise von dem Durchschnittswert zu seinem tatsächlichen Wert.
15. Vorrichtung nach Anspruch 12, wobei der Fahrparameter eine Zuggeschwindigkeit umfasst.
16. Vorrichtung nach Anspruch 15, mit einer Einrichtung zur Anpassung der Zuggeschwindigkeiten zwischen Sekundärgleisen zur Sicherstellung, dass jede Kreuzung bei einem Sekundärgleis auftritt.
17. Vorrichtung nach Anspruch 15, mit einer Einrichtung zum Ändern der Geschwindigkeit auf dem Sekundärgleis für zumindest einen der Vielzahl der Züge zur Berücksichtigung der Zeit, die ein Zug auf einem Sekundärgleis verbringt.
18. Vorrichtung nach Anspruch 12, wobei der Fahrparameter die Einfahrzeit des Zugs in den Eisenbahnkorridor umfasst.
19. Vorrichtung nach Anspruch 12, wobei der Fahrparameter einer Zuggeschwindigkeit und die Einfahrzeit des Zugs in den Eisenbahnkorridor umfasst.
20. Vorrichtung nach Anspruch 12, wobei das Sekundärgleis ein Ausweichgleis umfasst.
21. Vorrichtung nach Anspruch 12, wobei das Sekundärgleis 2 parallele Gleise mit einer dazwischen angeordneten Übergangsstelle aufweist.
22. Vorrichtung nach Anspruch 12, wobei die Lokalisierungsfunktion hergeleitet wird durch Aufsummieren einer Vielzahl von Sigmoidfunktionen, wobei die Sigmoidfunktionen vorgesehen sind mit einer Beziehung zueinander und zu dem Ort der Sekundärgleise derart, dass die Lokalisierungsfunktion einen Wert innerhalb des ersten Bereichs zwischen Sekundärgleisen und einen Wert innerhalb des zweiten Bereichs in der Nähe jedes Sekundärgleises annimmt.