[go: up one dir, main page]
More Web Proxy on the site http://driver.im/

WO1997009218A2 - Verfahren zur regelung von verkehrsmitteln - Google Patents

Verfahren zur regelung von verkehrsmitteln Download PDF

Info

Publication number
WO1997009218A2
WO1997009218A2 PCT/DE1996/001498 DE9601498W WO9709218A2 WO 1997009218 A2 WO1997009218 A2 WO 1997009218A2 DE 9601498 W DE9601498 W DE 9601498W WO 9709218 A2 WO9709218 A2 WO 9709218A2
Authority
WO
WIPO (PCT)
Prior art keywords
transport
line network
graph
occupancy plan
occupancy
Prior art date
Application number
PCT/DE1996/001498
Other languages
English (en)
French (fr)
Other versions
WO1997009218A3 (de
Inventor
Ulrich Lauther
Karl-Heinz Erhard
Original Assignee
Siemens Aktiengesellschaft
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by Siemens Aktiengesellschaft filed Critical Siemens Aktiengesellschaft
Priority to AU72774/96A priority Critical patent/AU7277496A/en
Publication of WO1997009218A2 publication Critical patent/WO1997009218A2/de
Publication of WO1997009218A3 publication Critical patent/WO1997009218A3/de

Links

Classifications

    • B—PERFORMING OPERATIONS; TRANSPORTING
    • B61—RAILWAYS
    • B61L—GUIDING RAILWAY TRAFFIC; ENSURING THE SAFETY OF RAILWAY TRAFFIC
    • B61L27/00—Central railway traffic control systems; Trackside control; Communication systems specially adapted therefor
    • B61L27/10—Operations, e.g. scheduling or time tables
    • B61L27/16—Trackside optimisation of vehicle or train operation

Definitions

  • the invention relates to a method with which it is possible to regulate means of transport, which are controlled in a given line network on given sequences of start and destination points, in a manner with the aid of a computer that deviations from given departure times and Arrival times of the means of transport are minimized as far as possible.
  • a disadvantage of this method is that this method was specifically designed for track sections and also only pursues local optimization strategies.
  • the fact that this method is based on conflict detection, that is to say that this method is only carried out when a conflict is detected, and not, for example, at periodic intervals, leads to the fact that there are possible chances of optimization in disposition without conflict situations occurring not be used in this case.
  • the invention is based on the problem of specifying a method for regulating means of transport with the aid of a computer which avoids the disadvantages described above.
  • the problem is solved by the method according to claim 1.
  • the method according to the invention pursues a fundamentally different objective.
  • An occupancy plan is drawn up on the basis of a predefined line network and on the basis of predefined arrival and departure times of the means of transport from various stops of the means of transport and of predefined sequences of start and destination points. This occupancy plan is completely deleted and regenerated before each new creation.
  • the individual means of transport are sequentially assigned in accordance with their priority when the occupancy plan is generated, by which parts of the line network are assigned to the individual means of transport for specific time intervals.
  • the still unoccupied time intervals are represented in the form of an interval graph and a so-called shortest path method, also referred to as a short-test path algorithm, is used on this interval graph in order to find an optimal route to be determined by the still unoccupied time intervals for the respective means of transport.
  • Adjusted parts of the line network which are now occupied by the means of transport at the respective time intervals.
  • the advantages of the method can be seen above all in the fact that a quick determination of permitted and optimized routes of the means of transport is made possible. Furthermore, this optimization is not restricted to local optimization strategies, but takes into account the global situation in the entire line network, in particular by completely deleting the old occupancy plan when generating a new occupancy plan.
  • the method is not a special solution for track sections, but can be used in general for any type of network, the parts of which are divided into sections. This broad applicability is also evident in the fact that the method can also be used in the regulation of aircraft.
  • the method according to the invention is further improved, since time gaps that are only slightly too small to be occupied by a means of transport on a route can be further optimized, so that time intervals already planned up to be shifted to a certain extent in order to enlarge free time intervals and thus quickly enable improved regulation of the means of transport.
  • FIG. 1 shows a flow diagram in which individual method steps of the method are shown
  • FIG. 2 shows a flow chart in which some additional procedural steps which serve to compact the occupancy plan are described
  • Figure 3 is a sketch in which a line network of a simple
  • Embodiment is shown with four parts;
  • FIG. 4 shows a time diagram (occupancy plan) for the four parts of the line network shown in FIG. 3, in which a possible occupancy of the line network by means of transport is shown;
  • FIGS. 5a and b show a sketch in which a target timetable of four trains in a line network of a second exemplary embodiment is shown and a state which arises if there is no regulation if a train is delayed;
  • FIGS. 6a and b show sketches in which, on the one hand, a regulation is shown which results when using known methods which are based on conflict detection and conflict resolution (FIG. 6a) and a solution which is obtained by using the ver - driving can result, for example ( Figure 6b);
  • FIG. 7 shows a time diagram (occupancy plan) for the four parts of the line network of the first exemplary embodiment, with an intuitive representation of the free time intervals of the occupancy plan in the form of an interval graph which has ten nodes and five edges;
  • Figure 8 shows an occupancy plan and a shift graph.
  • Means of transport Vi to be controlled are controlled in a line network LN.
  • An index i uniquely designates each means of transport Vi and is a natural number in the range from 1 to m, where a natural number m is the number of those located or to be controlled in the line network LN Transport Vi indicates.
  • Predetermined arrival times and predefined departure times are assigned to each means of transport Vi for each stopping point which the respective means of transport Vi is to approach.
  • each means of transport Vi are also given sequences of starting and destination points which each means of transport Vi has to travel through.
  • a second index j denotes a part TLNj of each Line network LN is unique and is a natural number in the range from 1 to n, the natural number n indicating the number of parts TLNj of the line network LN.
  • occupancy plan BP is iteratively regenerated in the following method steps. As long as not all means of transport Vi have been taken into account in the occupancy plan BP 03, the following steps are carried out sequentially for each means of transport Vi:
  • a means of transport Vi with the highest priority of the means of transport Vi not yet taken into account in the occupancy plan BP is selected and read 04 into a memory of the computer.
  • an interval graph IG uses an shortest route method (shortest path algorithm) to optimally route the means of transport Vi to be assigned to the occupancy plan, that is to say the parts TLNj of the line network LN and also to the respective time intervals len in which the means of transport Vi requires this part TLNj.
  • shortest route method shortest path algorithm
  • the interval graph IG is adjusted with respect to the parts TLNj of the line network LN which were "occupied" for the respective means of transport Vi in the previous step 05, by in each case a previously free time interval now either in two new ones , smaller, free time intervals are divided or if the free time interval has been completely "occupied" for the means of transport Vi, it is deleted.
  • a last step 07 which is carried out for all means of transport Vi, the parts TLNj of the line network LN required by the means of transport Vi are finally occupied at the required time intervals. If all means of transport Vi have been taken into account in the occupancy plan BP 03, all means of transport Vi are regulated in accordance with the newly created occupancy plan BP 08.
  • the line network LN is represented within the computer in the form of an undirected network graph consisting of nodes and edges.
  • a node of the undirected network graph represents, for example, a switch, if the means of transport Vi are possibly rail-bound vehicles, a signal, or a point at which a change in the maximum permissible speed of the means of transport Vi occurs.
  • An edge of the undirected network graph represents a part TLNj of the line network LN (see FIG. 3).
  • Two parts TLNj of the line network LN are in conflict with one another if they cannot be occupied at the same time, for example if they cross each other or if so-called edge protection is used.
  • Two parts TLNj of the line network LN of a rigid intersection also form a conflict pair. All conflicts are modeled by a directed conflict graph. The conflict graph is directed to too
  • a route is represented by the specification of a start node of the undirected network graph and a destination node of the undirected network graph.
  • the occupancy plan BP represents both the "target behavior” and "actual behavior” of the individual means of transport Vi.
  • the occupancy plan BP has a number of time intervals.
  • a certain time interval embodies the occupancy of a certain edge, ie a certain part TLNj of the line network LN in the non-directional network graph by a certain means of transport Vi.
  • the free time intervals of the occupancy plan BP are shown in the form of the interval graph IG.
  • the computer If there is conflict between one edge and another edge, so-called conflict edges, then the computer generates a conflict interval ki for each time interval for which there is a conflict.
  • This first exemplary embodiment serves only to clarify the method and limits the general usability to any number of parts TLNj of the line network LN, and any structure of the line network LN as well as any number of means of transport Vi which are located in the line network LN no way.
  • FIG. 4 For the first exemplary embodiment, a possible occupancy is shown in FIG. 4 in a diagram dependent on a time t, the occupancy plan BP.
  • a second means of transport V2 travels the parts TLN2, TLN3 and TLN4 of the line network LN in exactly this order. episode.
  • a first means of transport VI only crosses the first part TLN1 of the line network LN. Since the first part TLN1 and the third part TLN3 of the line network LN cross (see FIG. 3), these two parts TLN1, TLN3 of the line network LN conflict with one another.
  • TLNl is the conflicting edge of TLN3 and TLN3 is the conflicting edge of TLNl.
  • the occupancy for the third part TLN3 of the line network LN is assigned a conflict interval ki3 by the first means of transport VI by the computer.
  • the conflict interval ki3 has the same time values as the time interval which is assigned to the first part TLN1 in the occupancy for the first means of transport VI.
  • a waiting interval W describes a time interval during which the second means of transport V2 has to wait on the second part TLN2 of the line network LN until it is allowed to "enter” the third part TLN3, since the conflict that arises from the first means of transport VI by crossing the first part TLN1 with the third part TLN3 of the line network LN, has been dissolved again.
  • a first conflict interval kil is shown, since in this time interval the third part TLN3 of the line network LN is "occupied" by the first means of transport VI, and thus the first part TLN1, since the first part TLN1 represents a conflict edge of the third part TLN3 of the line network LN, a conflict interval must be assigned.
  • FIG. 7 shows the occupancy plan BP in the form of an interval graph IG.
  • Edges are introduced into the interval graph IG precisely when it is possible to travel between the two associated time intervals.
  • Time conditions for example the overlap of free time intervals and topological conditions, for example transition possibilities between the legs of a switch when using the method for rail-bound means of transport Vi, are taken into account and described in a uniform manner.
  • a shortest path method (short-path algorithm) is taken into account for the respective means of transport Vi to be assigned, taking into account the starting point of the means of transport Vi and the destination of the means of transport Vi and the stops of the transport Kehrsstoff ⁇ Vi applied.
  • a time-shortest, permissible route is determined for each means of transport Vi in accordance with its assigned priority.
  • the order of the means of transport Vi for assignment within the occupancy plan BP is according to the Priorities that are assigned to the means of transport Vi.
  • the interval graph IG After a means of transport Vi has been reassigned to the occupancy plan BP using the interval graph IG, the interval graph IG must of course also be adapted according to the new occupancy 06. This means that in the event that a means of transport Vi is part of a free time interval occupied, this free time interval is divided into either two new, smaller free time intervals which then "enclose" the time period occupied by the means of transport Vi, or, if the newly occupied time interval directly follows an already occupied time interval, only a new one If the assigned time interval completely covers the previously declared free time interval, no new free time interval is formed.
  • the means of transport Vi are regulated in a last step 08 in accordance with the requirements that result from the occupancy plan BP, which may have additional waiting times, for example, as indicated in FIG. 3 with the waiting interval W.
  • the regulation of the means of transport Vi can be carried out in several ways, for example it is provided that the means of transport Vi may, as shown in FIG. 3, be stopped at a stopping point for a certain time interval until they are allowed to continue again.
  • An advantage of this method is that different requirements of different line networks LN can be easily taken into account in the model of the different graphs.
  • a further simple variant, which can be taken into account in the method, is to regulate the traffic center Vi by changing the speeds on the individual parts TLNj of the line network LN.
  • the change in the speeds is then taken into account in the interval graph IG by appropriately adapting the free time intervals in the occupancy plan BP.
  • the means of transport Vi are assigned to the parts TLNj of the line network LN in the order of priority of the individual means of transport Vi.
  • the priority of the means of transport Vi is a value which is determined from at least one of the following criteria:
  • the means of transport as such can be assigned different meanings within the framework of the entire transport network; it can be, for example, that the meaning of a means of transport Vi that transports people is greater than the meaning of a means of transport Vi that is ter transported, or vice versa, depending on the application;
  • the start times of the individual means of transport Vi can also be taken into account when forming the priority of the means of transport Vi;
  • a desired arrival time can also be of great importance in a particular application, which then also influences the priority of the means of transport Vi;
  • a directed shift graph vg is first generated in order to formally describe which time intervals have to be shifted 22 if a specific time interval is shifted.
  • the safety distance is reset to the value fixed before the reduction.
  • the displacement graph vg is decompacted 23, that is to say the resulting occupancy plan is now consistent. Since time intervals here may be shifted too far into the future, the displacement graph vg is compacted in a further step 24. In this step, the time intervals are shifted to the left as far as possible.
  • the new time values for the time intervals are taken from the shift graph vg and the occupancy plan BP is adjusted accordingly 25.
  • the starting point for the generation of the shift graph vg is the occupancy plan BP.
  • Each node v of the shift graph vg represents the beginning of a time interval in the occupancy plan BP. This time value indicates the point in time at which the top of the means of transport Vi travels the part TLNj of the line network LN belonging to the time interval.
  • a directed edge e in the shift graph vg describes that the time value of the target node of the directed edge e must be at least as large as the time value of the start node of the directed edge e.
  • the index v and the index e are arbitrary natural numbers which uniquely identify a node v and an edge e, respectively.
  • the numbers lie in the range between 1 and the number of nodes v or edges e occurring in the shift graph vg.
  • movable (v) Specification as to whether or not the time value assigned to node v may be changed;
  • time value of the target node of the directed edge e must be at least as large as the time value of the starting node of the respective directed edge e plus cost (e).
  • the parameter mintime (v) is introduced in order to describe, for example, departure times of means of transport Vi in intermediate stops, that is, it should be taken into account that the means of transport Vi may not depart from the intermediate stop before a predetermined time.
  • the parameter movable (v) is introduced to e.g. B., when using the method for rail-bound means of transport Vi, to model track barriers. In this case, the time values of a track lock must not be changed.
  • the edges of the displacement graph vg are generated in the following way:
  • a specific time interval z which is contained in the predetermined route of the means of transport Vi and in the line network LN, is introduced for explanation.
  • the following sizes are also introduced:
  • the conflict interval belonging to the time interval z is designated kiz.
  • new edges are determined which have a target node t of the respective new edge and a start node u of the respective new edge.
  • cost (u, t) denotes the weight of the respective new edge.
  • va (z) denotes the node in the shift graph vg which represents the respective start of the time interval z.
  • a travel time tedge for a route length of the edge e and a travel time tlen for a route length which is equal to the length of the means of transport Vi are introduced.
  • edge parameter cost (u, t) is to be defined.
  • the large number of different cases is caused by the fact that the number of nodes in the shift graph vg has been minimized.
  • the elimination of the nodes, which represent the time values of the conflict intervals means that an edge must be generated from node va (z) to node va (gn (kiz)) in order to ensure that there is no overlap between the intervals kiz and gn (kiz ) to ensure (see equation 3).
  • Kir gn (zp (z)) applies.
  • Kir gn (kizp (z)) applies.
  • An index r denotes a further time interval not equal to the respective time interval z.
  • a special case leads to four further cases, namely if the means of transport Vi is on several edges, that is to say if the length of the means of transport Vi is greater than the length of the edge itself. These four cases are obtained from the
  • the shift graph vg to the occupancy plan BP from FIG. 4 is shown in FIG.
  • the edges of the displacement graph vg are indexed with the respective number of the case or the respective equation according to the overview shown above.
  • line network LN with a constriction Ver which is only from one means of transport Vi to one, is shown in FIGS. 5a and 5b can be occupied at a specific point in time, the predetermined travel times of three modes of transport with high priority VI, V2, V3 and one mode of transport with lower priority V4 are shown in a path-time diagram.
  • FIG. 5b shows a malfunction that occurs and a delay in the means of transport V2 associated therewith. This delay leads to an increase in a time interval ti2 / which lies between the first means of transport VI and the second means of transport V2. This time interval ti2 is increased by the delay to a new time interval t' ⁇ 2 .
  • the method is carried out when disturbances have occurred in the line network LN and / or in the means of transport Vi and / or other disturbances which are reported to influence the flow of traffic. These fault messages are received and saved.
  • a fault is understood to mean, for example, a case when a part TLNj of the line network LN fails or is blocked.
  • a new occupancy plan BP can be determined taking into account the reported malfunctions.
  • connection relationships between means of transport VI into account in the regulation and thus in the occupancy plan by simply generating dependent arrival and departure times of the means of transport Vi. This means that for a means of transport Vi this case that it has to wait for another means of transport must be taken into account in the occupancy plan BP.
  • a further development of the method also provides for at least one of the following secondary conditions to be taken into account when generating the occupancy plan (BP):
  • An optimal order sequence is that which has the lowest value in the target function of all possible order sequences.
  • the target function can also have other parameters, for example the weighting of delays which must exceed a predetermined threshold in order to be taken into account at all. Further aspects which, depending on the application, lead to a change in the target function can be taken into account in the method without restrictions.
  • the remaining orders o are planned individually, taking into account the already planned orders g.
  • the target function values of the o individual plans are added to the target function value of the g plans already carried out. If the lower bound calculated in this way is greater than or equal to the target function value of the earlier best order order Popt 'which is continuously updated during the process, then none of the o! (! in this context means fact, that is, all permutations of the o order sequences) o order sequences are better than the order sequence p opt • Consequently, these order sequences no longer need to be taken into account.
  • the order of the branching can be optimized. After the planning of g orders, the remaining o orders that are still to be planned are planned in order for trial purposes.
  • the order in which this trial planning takes place can be optimized by first planning the job that causes the smallest increase in the target function value among all the jobs. Accordingly, before the branching, all orders are sorted in ascending order with respect to this growth.
  • branch-and-bound algorithm described above can be accelerated using two parameters: - A branch barrier bs.
  • the calculated lower bound is multiplied by the stretching factor sf, the value of which is greater than 1. This is equivalent to imagining that you have a better lower bound.
  • the line network with the individual parts TLNj of the line network LN corresponds to the air corridors assigned to the individual aircraft on a flight route.
  • Another area of application of the method is in the disposition of collective stops.
  • the procedure is such that the means of transport Vi are first assigned to the respective stops of the collective stop, and then the optimal route is calculated for each means of transport Vi.
  • the method can also be used advantageously to create target timetables for the means of transport Vi.
  • the method can of course be used for any type of network disposition, since the method does not represent a special solution, but rather can be used for general network graphs.

Landscapes

  • Engineering & Computer Science (AREA)
  • Mechanical Engineering (AREA)
  • Control Of Conveyors (AREA)
  • Train Traffic Observation, Control, And Security (AREA)
  • Data Exchanges In Wide-Area Networks (AREA)

Abstract

Zur Regelung von Verkehrsmitteln (Vi) in einem vorgegebenen Liniennetz (LN) wird jeweils ein schon bestehender Belegungsplan (BP') vollständig gelöscht und komplett ein neuer Belegungsplan (BP) generiert. Die Generierung erfolgt in der Weise, daß jeweils ein Verkehrsmittel (Vi) sequentiell in einem Intervallgraphen (IG) bestimmten Zeitintervallen und Routen zugeordnet wird. Bei der Zuordnung optimaler Routen und Zeitintervalle für das jeweilige Verkehrsmittel (Vi) wird ein Kürzestes-Wege-Verfahren (Shortest Path Algorithm) verwendet. Durch diese Vorgehensweise wird eine globale optimierte Zuordnung und Regelung von Verkehrsmitteln (Vi) auf Teile (TLNj) des Liniennetzes (LN) erreicht.

Description

Beschreibung
Verfahren zur Regelung von Verkehrsmitteln.
Die Erfindung betrifft ein Verfahren, mit dem es möglich ist, Verkehrsmittel, die in einem vorgegebenen Liniennetz auf vor¬ gegebenen Sequenzen von Start- und Zielpunkten gesteuert wer¬ den, in einer Weise mit Hilfe eines Rechners zu regeln, daß Abweichungen von vorgegebenen Abfahrtszeiten und Ankunftszei¬ ten der Verkehrsmittel möglichst minimiert werden.
Besondere Bedeutung erlangt dieses Anwendungsgebiet bei auf¬ tretenden Störungen des Betriebs des Liniennetzes. Bei auf- tretenden Störungen müssen die Änderungen der Routen bzw. der Fahranweisungen für die einzelnen Verkehrsmittel in einer Weise erfolgen, daß die Auswirkungen der Störung auf den ge¬ samten Betrieb des Liniennetzes möglichst gering gehalten werden.
Es sind Verfahren zur Bestimmung kürzester Wege (Shortest Path Algorithms) in einem Netzwerkgraphen bekannt (E. Moore, The Shortest Path Through a Maze, In Proceedings Internatio¬ nal Symposium on the Theory of Switching, Part 2, April 2 - 5, S. 285 - 292, 1957; und E. Dijkstra, A Note on Two Pro¬ blems in Connexion with Graphε, Numerische Mathematik, Band 1, Springer Verlag, S. 269 bis 271, 1959).
Ein Verfahren zur automatischen Disposition von Zügen ist be- kannt (H. Schaefer et al, An Expert System for Real-Time
Train Dispatching, Railway Operations, Computers in Railways
4, Volume 2, COMPRAIL 94, T. Murthy et al (editors), Computa- tional Mechanics Publications, Southampton, ISBN 1-85312-359-
5, S. 27 biε 34, 1994) . Dieses Verfahren basiert auf Konflik- terkennung und Konfliktlösung. In diesem Zusammenhang liegt ein Konflikt vor, wenn die Fahrplanabweichungen so groß sind, daß die Abwicklung des Fahrbetriebs gemäß einem vorgegebenen Sollfahrplan nicht mehr möglich ist. Die Lösung der Konflikte erfolgt hier mit Hilfe einer Wissensbasis (Entscheidungsregeln) .
Nachteilig an diesem Verfahren ist, daß dieses Verfahren spe¬ ziell für Gleisstrecken konzipiert wurde und außerdem nur räumlich lokale OptimierungsStrategien verfolgt. Auch die Tatsache, daß dieses Verfahren auf einer Konflikterkennung basiert, das heißt daß dieses Verfahren nur durchgeführt wird, wenn ein Konflikt erkannt wird und nicht beispielsweise in periodischen Zeitabständen, führt dazu, daß mögliche Opti¬ mierungschancen bei der Disposition ohne auftretende Kon¬ fliktsituationen in diesem Fall nicht genutzt werden.
Ein weiteres konfliktbasiertes Verfahren ist aus (K. Komaya et al, Estrac-III: An Expert System for Train Traffic Control in Disturbed Situations, Control, Computers, Communications in Transportation - Selected Papers from the IFAC/IFIP/IFORS Symposium Programm, Oxford, UK, S. 147 bis 153, 1989) be- kannt. Das Verfahren verwendet zur Konfliktlosung ebenfalls lokale Entscheidungsregeln. Die Nachteile, die für das vorige Verfahren beschrieben wurden, gelten selbstverständlich eben¬ falls für dieses Verfahren, da dieses Verfahren auf denselben Grundprinzipien beruht, der Konflikterkennung und Konfliktlö- sung.
Ein Verfahren, welches ebenfalls auf Konflikterkennung und Konfliktlösung basiert, aber zur Lösung sogenannte Branch- and-Bound-Verfahren verwendet ist bekannt (R. Sauder, Compu- ter Aided Train Dispatching: Decision Support through Opti- mazation, INTERFACES 13, S. 24 bis 37, Dezember 1993). Das Verfahren weist die gleichen Nachteile auf wie die im vorigen beschriebenen Verfahren.
Der Erfindung liegt das Problem zugrunde, ein Verfahren zur Regelung von Verkehrsmitteln mit Hilfe eines Rechners anzuge¬ ben, das die im vorigen beschriebenen Nachteile vermeidet. Das Problem wird durch das Verfahren gemäß Patentanspruch 1 gelöst.
Im Gegensatz zu den Verfahren, die auf Konflikterkennung und Konfliktlösung das Verhalten des Disponenten in einem Exper¬ tensystem nachbilden, verfolgt das erfindungsgemäße Verfahren eine grundsätzlich andere Zielrichtung.
Durch das Verfahren wird eine weitgehend automatische und global optimierte Regelung von Verkehrsmitteln erreicht; IM Gegensatz zu den lokalen Entscheidungsregeln der bekannten Verfahren.
Anhand eines vorgegebenen Liniennetzes und anhand von vorge¬ gebenen Ankunfts- und Abfahrtszeiten der Verkehrsmittel von verschiedenen Haltestellen der Verkehrsmittel sowie von vor¬ gegebenen Sequenzen von Start- und Zielpunkten wird ein Bele¬ gungsplan erstellt. Dieser Belegungsplan wird vor jeder Neu- erstellung komplett gelöscht, und neu generiert.
Die einzelnen Verkehrsmittel werden bei der Generierung des Belegungsplans, durch den Teile des Liniennetzes für bestimm¬ te Zeitintervalle den einzelnen Verkehrsmitteln zugeordnet werden, sequentiell gemäß ihrer Priorität zugeordnet. Bei der Zuordnung der einzelnen Verkehrsmittel auf den Belegungsplan¬ werden die noch unbelegten Zeitintervalle in Form eines In- tervallgraphens dargestellt und auf diesen Intervallgraphen wird ein sogenanntes Kürzestes-Wege-Verfahren, auch als Shor- test Path Algorithm bezeichnet, angewendet, um eine optimale Route durch die noch unbelegten Zeitintervalle für das jewei¬ lige Verkehrsmittel zu ermitteln.
Wenn ein Verkehrsmittel einem Zeitintervall und einer Route zugeordnet wurde, wird der Belegungsplan für die einzelnen
Teile des Liniennetzes angepaßt, die nun von dem Verkehrsmit¬ tel zu den jeweiligen Zeitintervallen belegt werden. Die Vorteile des Verfahrens sind vor allem darin zu sehen, daß eine schnelle Ermittlung von zulässigen und optimierten Routen der Verkehrsmittel ermöglicht wird. Weiterhin ist die- se Optimierung nicht auf lokale Optimierungsstrategien be¬ schränkt, sondern berücksichtigt vor allem durch die voll¬ ständige Löschung des alten Belegungsplanes jeweils bei der Generierung eines neuen Belegungsplans die globale Situation in dem gesamten Liniennetz. Außerdem ist das Verfahren keine Speziallösung für Gleisstrecken, sondern kann ganz generell für jede Art von Netzen angewendet werden, deren Teile in Streckenabschnitte unterteilt sind. Diese breite Anwendbar¬ keit zeigt sich auch in der Tatsache, daß das Verfahren auch in der Regelung von Flugzeugen angewendet werden kann.
Durch die Weiterbildung des Verfahrens gemäß Patentanspruch 2 ist es möglich, eventuell auftretende Störungen in einem Li¬ niennetz sofort zu erkennen und in einer Neugenerierung des Belegungsplanes zu berücksichtigen, um die Auswirkungen der aufgetretenen Störungen auf das gesamte Liniennetz zu mini¬ mieren.
Durch die Weiterbildung des Verfahrens gemäß Patentanspruch 8 wird das erfindungsgemäße Verfahren weiter verbessert, da Zeitlücken, die nur geringfügig zu klein sind, um von einem Verkehrsmittel auf einer Route belegt werden zu können, noch weiter optimiert werden, so daß schon verplante Zeitinterval¬ le bis zu einem gewissen Grad verschoben werden, um freie Zeitintervalle zu vergrößern und somit schnell eine verbeε- serte Regelung der Verkehrsmittel zu ermöglichen.
Mit der Weiterbildung des Verfahrens gemäß Patentanspruch 13 werden unterschiedliche Nebenbedingungen bei der Generierung des Belegungsplans berücksichtigt, wodurch die Regelung wei- ter verbessert wird. Weiterbildungen der Erfindung ergeben sich aus den abhängigen Ansprüchen.
Ein bevorzugtes Ausführungsbeispiel der Erfindung ist in den Figuren dargestellt und wird im folgenden näher beschrieben.
Es zeigen
Figur 1 ein Ablaufdiagramm, in dem einzelne Verfahrensschrit- te des Verfahrens dargestellt sind;
Figur 2 ein Ablaufdiagramm, in dem einige zusätzliche Verfah¬ rensschritte, die zur Kompaktierung deε Belegungs¬ plans dienen, beschrieben sind;
Figur 3 eine Skizze, in der ein Liniennetz eines einfachen
Ausführungsbeispiels mit vier Teilen dargestellt ist;
Figur 4 ein Zeitdiagramm (Belegungsplan) für die vier Teile des in Figur 3 dargestellten Liniennetzes, in dem ei¬ ne mögliche Belegung des Liniennetzes durch Verkehrs¬ mittel dargestellt ist;
Figuren 5a und b eine Skizze, in dem ein Sollfahrplan von vier Zügen in einem Liniennetz eines zweiten Ausfüh¬ rungsbeispiels und ein Zustand dargestellt ist, der sich bei nicht vorhandener Regelung einstellt, wenn sich ein Zug verspätet;
Figuren 6a und b Skizzen, in denen zum einen eine Regelung, dargestellt ist, die sich ergibt bei Verwendung be¬ kannter Verfahren, die auf Konflikterkennung und Kon¬ fliktlösung basieren, (Figur 6a) sowie eine Lösung, die sich durch Anwendung des erfindungsgemäßen Ver- fahrens beispielsweise ergeben kann (Figur 6b) ; Figur 7 ein Zeitdiagramm (Belegungsplan) für die vier Teile des Liniennetzes des ersten Ausführungsbeispieis, mit einer intuitiven Darstellung der freien Zeitinterval¬ le des Belegungsplanε in Form eines Intervallgraphen, der zehn Knoten und fünf Kanten aufweist;
Figur 8 einen Belegungsplan und einen Verschiebegraphen.
Anhand der Figuren 1 bis 8 wird das Verfahren weiter erläu- tert.
In Figur 1 sind in Form eines Ablaufdiagramms einzelne Ver¬ fahrensschritte dargestellt.
Zu regelnde Verkehrsmittel Vi werden in einem Liniennetz LN gesteuert 01. Ein Index i bezeichnet jedes Verkehrsmittel Vi eindeutig und ist eine natürliche Zahl im Bereich von 1 bis m, wobei eine natürliche Zahl m die Anzahl der εich in dem Liniennetz LN befindenden bzw. zu εteuernden Verkehrsmittel Vi angibt.
Jedem Verkehrsmittel Vi sind vorgegebene Ankunftszeiten und vorgegebene Abfahrtszeiten für jede Halteεtelle, die das je¬ weilige Verkehrsmittel Vi anfahren soll, zugeordnet.
Außerdem sind jedem Verkehrsmittel Vi auch Sequenzen von Start- und Zielpunkten vorgegeben, die jedes Verkehrsmittel Vi jeweils zu befahren hat.
Eine eventuell schon existierende Zuordnung von Verkehrsmit¬ teln Vi auf Teile TLNj des Liniennetzes LN zu bestimmten Zei¬ tintervallen, die in einem Rechner gespeichert ist, also ein alter Belegungsplan BP', wird gelöscht 02. Ein zweiter Index j bezeichnet jeweils einen Teil TLNj des Liniennetzes LN ein- deutig und ist eine natürliche Zahl im Bereich von 1 bis n, wobei die natürliche Zahl n die Anzahl der Teile TLNj des Li¬ niennetzes LN angibt. Die Zuordnung, die im weiteren als Belegungsplan BP bezeich¬ net wird, wird in den folgenden Verfahrensschritten iterativ neu generiert. Solange noch nicht alle Verkehrsmittel Vi in dem Belegungsplan BP berücksichtigt wurden 03, werden jeweils εequentiell für ein Verkehrsmittel Vi folgende Schritte durchgeführt:
Ein Verkehrsmittel Vi mit der höchsten Priorität der noch nicht in dem Belegungsplan BP berücksichtigten Verkehrεmittel Vi wird ausgewählt und in einen Speicher deε Rechnerε einge¬ lesen 04.
In einem weiteren Schritt 05 wird auf einen Intervallgraphen IG mit Hilfe eines Kürzesten-Wege-Verfahren (Shortest Path Algorithm) eine optimale Route für das jeweils zuzuordnende Verkehrsmittel Vi zu dem Belegungsplan, also den Teilen TLNj des Liniennetzes LN als auch zu den jeweiligen Zeitinterval¬ len, in denen daε Verkehrsmittel Vi diesen Teil TLNj jeweilε benötigt, ermittelt.
In einem folgenden Schritt 06 wird der Intervallgraph IG in Bezug auf die Teile TLNj des Liniennetzes LN, die in dem vo¬ rigen Schritt 05 für das jeweiligen Verkehrsmittel Vi „belegt" wurden, angepaßt, indem jeweils ein bisher freies Zeitintervall nunmehr entweder in zwei neue, kleinere, freie Zeitintervalle aufgeteilt wird oder, wenn das freie Zeitin¬ tervall komplett für das Verkehrsmittel Vi „belegt" wurde, gelöεcht wird.
In einem letzten Schritt 07, der für alle Verkehrεmittel Vi durchgeführt wird, werden die von dem Verkehrεmittel Vi benö¬ tigten Teile TLNj deε Liniennetzes LN zu den benötigten Zei¬ tintervallen endgültig belegt. Wenn alle Verkehrsmittel Vi in dem Belegungsplan BP berück¬ sichtigt wurden 03, werden alle Verkehrsmittel Vi entspre¬ chend dem neu entstandenen Belegungsplan BP geregelt 08.
Das Liniennetz LN wird innerhalb des Rechners in Form eines ungerichteten Netzwerkgraphens, bestehend aus Knoten und Kan¬ ten, dargestellt.
Ein Knoten des ungerichteten Netzwerkgraphens repräsentiert in diesem Zusammenhang beispielsweise eine Weiche, falls es sich bei den Verkehrsmitteln Vi eventuell um schienengebunde¬ ne Fahrzeuge handelt, ein Signal, oder einen Punkt, an dem eine Änderung der maximal zulässigen Geschwindigkeit des Ver¬ kehrsmittels Vi auftritt.
Eine Kante des ungerichteten Netzwerkgraphenε repräεentiert jeweilε einen Teil TLNj deε Liniennetzeε LN (vgl. Figur 3).
Zwei Teile TLNj des Liniennetzes LN stehen zueinander in Kon- flikt, wenn sie nicht gleichzeitig belegt werden können, bei¬ spielεweise wenn sie εich kreuzen oder wenn ein εogenannter Flankenεchutz verwendet wird. Auch zwei Teile TLNj des Lini¬ ennetzes LN einer starren Kreuzung bilden ein Konfliktpaar. Alle Konflikte sind durch einen gerichteten Konfliktgraphen modelliert. Der Konfliktgraph ist gerichtet, um auch
Durchrutschwege und rückwärtige Auflösungen von Teilen TLNj des Liniennetzes LN beschreiben zu können.
Eine Route wird repräsentiert durch die Angabe eines Start- knotens des ungerichteten Netzwerkgraphens und eines Zielkno- tenε deε ungerichteten Netzwerkgraphenε.
Damit eε möglich ist, auch UmlaufbeZiehungen zu berücksichti¬ gen, bei der Verwendung des Verfahrens für schienengebundene Verkehrsmittel Vi bedeutet dies beispielsweise wendende Ver¬ kehrsmittel Vi, werden in diesem Fall für das jeweilige Ver¬ kehrsmittel Vi mehrere Routen definiert, welche voneinander abhängig gemacht werden. Die Routenabhängigkeiten werden an einem gerichteten Routengraphen beschrieben. In diesem Routengraphen können ebenso Anschlußbeziehungen zwischen den Verkehrsmitteln Vi, also Routenabhängigkeiten zwischen ver- schiedenen Verkehrsmitteln Vi, berücksichtigt werden.
Der Belegungsplan BP repräsentiert sowohl das „Sollverhalten" als auch „Istverhalten" der einzelnen Verkehrsmittel Vi. Der Belegungsplan BP weist eine Menge von Zeitintervallen auf. Dabei verkörpert ein bestimmtes Zeitintervall die zeitliche Belegung einer bestimmten Kante, also eines bestimmten Teils TLNj deε Liniennetzes LN im ungerichteten Netzwerkgraphen durch ein bestimmtes Verkehrεmittel Vi. Die freien Zeitinter¬ valle des Belegungsplans BP werden in Form des Intervallgra- phen IG dargestellt.
Besitzt eine Kante zu einer anderen Kante Konflikte, soge¬ nannte Konfliktkanten, dann wird durch den Rechner für jedes Zeitintervall, für das ein Konflikt besteht, ein Konfliktin- tervall ki generiert.
In Figur 3 ist ein einfaches Liniennetz LN mit vier Teilen TLNj, j = 1..4, dargeεtellt.
Dieεes erεte Ausführungsbeispiel dient nur zur Verdeutlichung des Verfahrens und schränkt die allgemeine Verwendbarkeit auf eine beliebige Anzahl von Teilen TLNj des Liniennetzes LN, sowie eine beliebige Struktur des Liniennetzeε LN alε auch eine beliebige Anzahl von Verkehrsmitteln Vi, die εich in dem Liniennetz LN befinden, in keinster Weise ein.
Für das erste Ausführungsbeispiel wird in Figur 4 eine mögli¬ che Belegung in einem von einer Zeit t abhängigen Diagramm, dem Belegungsplan BP, dargestellt.
Hierbei durchfährt ein zweites Verkehrsmittel V2 die Teile TLN2, TLN3 und TLN4 daε Liniennetz LN in genau dieser Reihen- folge. Ein erstes Verkehrsmittel VI durchquert ausschließlich den ersten Teil TLNl des Liniennetzes LN. Da sich der erste Teil TLNl und der dritte Teil TLN3 des Liniennetzes LN kreu¬ zen (vgl. Figur 3), stehen diese beiden Teile TLNl, TLN3 des Liniennetzes LN gegenseitig in Konflikt.
Dies bedeutet, TLNl ist Konfliktkante von TLN3 und TLN3 ist Konfliktkante von TLNl. Infolgedessen wird der Belegung für den dritten Teil TLN3 des Liniennetzes LN ein Konfliktinter- vall ki3 von dem ersten Verkehrsmittel VI durch den Rechner zugewiesen. Das Konfliktintervall ki3 weiεt dieεelben Zeit¬ werte wie das Zeitintervall auf, das dem ersten Teil TLNl in der Belegung für das erste Verkehrsmittel VI zugeordnet wird.
Ein Warteintervall W beschreibt ein Zeitintervall, während¬ dessen das zweite Verkehrεmittel V2 auf dem zweiten Teil TLN2 deε Liniennetzes LN warten muß, bis es in den dritten Teil TLN3 „einfahren" darf, da erεt dann der Konflikt, der sich aus dem ersten Verkehrsmittel VI durch Kreuzung des ersten Teils TLNl mit dem dritten Teil TLN3 des Liniennetzes LN er¬ geben hat, wieder aufgelöst wurde.
Weiterhin ist entsprechend der im vorigen beschriebenen Vor¬ gehensweise in Figur 4 ein erstes Konfliktintervall kil dar- gestellt, da in diesem Zeitintervall der dritte Teil TLN3 des Liniennetzes LN von dem ersten Verkehrsmittel VI „belegt" ist, und somit dem ersten Teil TLNl, da der erste Teil TLNl eine Konfliktkante des dritten Teilε TLN3 des Liniennetzeε LN darstellt, ein Konfliktintervall zugeordnet werden muß.
Wie im vorigen beschrieben wurde, wird ein alter, eventuell schon vorhandener Belegungsplan BP' bei Neugenerierung des Belegungsplans BP vollständig gelöscht 02.
In Figur 7 ist der Belegungsplan BP in Form eines Intervall¬ graphen IG dargestellt. Es werden allen verfügbaren, also freien Zeitintervallen in den Belegungsplan BP durch Knoten repräεentiert, denen die Angabe des jeweiligen Zeitintervalls als Attribut zugeordnet wird.
Kanten werden in dem Intervallgraphen IG genau dann einge- führt, wenn eine Fahrt zwischen den beiden zugehörigen Zei¬ tintervallen möglich ist.
Hierbei werden zeitliche Bedingungen, beispielsweise die Überlappung freier Zeitintervalle und topologische Bedingun- gen, beispielsweiεe Übergangεmöglichkeiten zwiεchen den Schenkeln einer Weiche bei Verwendung des Verfahrens für schienengebundene Verkehrsmittel Vi, berücksichtigt und in einheitlicher Weise beschrieben.
Auf den so entεtandenen Intervallgraphen IG wird für das je¬ weilε gerade zuzuordnende Verkehrεmittel Vi ein Kürzestes- Wege-Verfahren (Shorteεt Path Algorithm) unter Berückεichti- gung des Startpunktes des Verkehrεmittelε Vi und deε Ziel- punkteε deε Verkehrsmittels Vi und der Haltestellen des Ver- kehrsmittelε Vi angewendet.
Beispiele für Kürzeste-Wege-Verfahren sind bekannt (E. Moore, The Shortest Path Through a Maze, In Proceedings Internatio¬ nal Symposium on the Theory of Switching, Part 2, April 2 - 5, S. 285 bis 292, 1957; und E. Dijkstra, A Note on Two Pro- blemε in Connexion with Graphs, Numerische Mathematik, Band 1, S. 269 bis 271, 1959) .
Weitere Verfahren zur Bestimmung eines kürzesten Weges in ei- nem Netzwerkgraphen können ebenso ohne Einschränkung in die¬ εem Verfahren eingeεetzt werden.
Auf diese Weise wird für jedeε Verkehrsmittel Vi entsprechend seiner ihm zugeordneten Priorität eine zeitkürzeste, zulässi- ge Route ermittelt. Die Reihenfolge der Verkehrsmittel Vi zur Zuordnung innerhalb des Belegungsplanes BP wird gemäß den Prioritäten, die den Verkehrsmitteln Vi zugeordnet werden, festgelegt.
Die Prioritäten der Verkehrsmittel Vi dienen desweiteren als Gewichte im Rahmen einer im weiteren beschriebenen Zielfunk¬ tion.
Nachdem ein Verkehrsmittel Vi anhand des Intervallgraphen IG dem Belegungsplan BP neu zugeordnet wurde, muß natürlich auch der Intervallgraph IG entsprechend der neuen Belegung ange¬ paßt werden 06. Dies bedeutet, daß für den Fall, daß ein Ver¬ kehrsmittel Vi einen Teil eines freien Zeitintervalls belegt, dieseε freie Zeitintervall aufgeteilt wird in entweder zwei neue, kleinere freie Zeitintervalle, die dann den durch das Verkehrsmittel Vi belegten Zeitraum „umschließen", oder, wenn sich das neu belegte Zeitintervall direkt an ein schon beleg¬ tes Zeitintervall anschließt, nur ein neues freies Zeitinter¬ vall gebildet wird. Falls das zugeordnete Zeitintervall das bisher als frei deklarierte Zeitintervall vollständig über- deckt, wird kein neues freies Zeitintervall gebildet.
Im Anschluß daran werden die Teile TLNj mit den entεprechen- den Zeitintervallen für das jeweilige Verkehrsmittel Vi end¬ gültig belegt 07.
Wenn der Belegungsplan BP vollständig generiert wurde, werden die Verkehrsmittel Vi in einem letzten Schritt geregelt 08 entsprechend den Vorgaben, die sich aus dem Belegungsplan BP ergeben, welche beispielsweise zusätzliche Wartezeiten, wie in Figur 3 mit dem Warteintervall W angedeutet ist, aufweisen kann.
Die Regelung der Verkehrsmittel Vi kann auf mehrere Arten er¬ folgen, so ist es beispielsweiεe vorgeεehen, daß die Ver- kehrsmittel Vi unter Umständen wie in Figur 3 dargestellt, an einem Haltepunkt für ein bestimmtes Zeitintervall angehalten werden, bis sie wieder weiterfahren dürfen. Ein Vorteil deε Verfahrens liegt darin, daß unterschiedliche Anforderungen von verεchiedenen Liniennetzen LN ohne weiteres in daε Modell der verschiedenen Graphen berücksichtigt werden können.
Beispielsweise ist eε durch einfacheε Hinzufügen bzw. Ändern von Kanten möglich, einen eventuell vorgesehenen Gleiswech¬ selbetrieb für bestimmte Teile TLNj des Liniennetzes LN bei Verwendung des Verfahrens für schienengebundene Verkehrsmit¬ tel Vi, vorzusehen. Hierzu ist es lediglich notwendig, den vorgesehenen Teil TLNj, für den jeweils ein Gleiswechselbe¬ trieb, das heißt ein Auεweichen auf eine durch eine Kante mo¬ dellierte Schiene, die für eine andere Richtung derselben Strecke vorgeεehen ist, für ein bestimmtes Zeitintervall freizugeben.
Eine weitere einfache Variante, die in dem Verfahren berück¬ sichtigt werden kann, liegt in der Regelung der Verkehrsmit- tei Vi durch Veränderung der Geεchwindigkeiten auf den ein¬ zelnen Teilen TLNj deε Liniennetzes LN. Die Änderung der Ge¬ schwindigkeiten wird in dem Intervallgraphen IG dann berück¬ sichtigt durch entsprechende Anpassung der freien Zeitinter¬ valle in dem Belegungsplan BP.
Wie im vorigen beschrieben wurde, erfolgt die Zuordnung der Verkehrsmittel Vi zu den Teilen TLNj des Liniennetzes LN in der Reihenfolge der Priorität der einzelnen Verkehrsmittel Vi. Die Priorität der Verkehrsmittel Vi ist ein Wert, der aus mindestens einer der folgenden Kriterien ermittelt wird:
- die Verkehrsmittel als solche können unterschiedliche Be¬ deutung im Rahmen des gesamten Verkehrsnetzes zugeordnet bekommen; so kann eε beiεpielsweise sein, daß die Bedeutung eines Verkehrsmittelε Vi, das Perεonen transportiert, grö¬ ßer ist als die Bedeutung eines Verkehrsmittels Vi, das Gü- ter tranεportiert, oder eben auch umgekehrt, je nach Anwen¬ dung;
- die Geschwindigkeiten der einzelnen Verkehrsmittel Vi kön- nen ebenso in die Priorität des jeweiligen Verkehrεmittels
Vi einfließen;
- auch die Startzeiten der einzelnen Verkehrsmittel Vi können berücksichtigt werden bei der Bildung der Priorität der Verkehrsmittel Vi;
- ebenso wie die Startzeit, also die Abfahrtszeit des Ver- kehrεmittelε Vi kann auch eine gewünschte Ankunftszeit eine große Bedeutung in einer bestimmten Anwendung erlangen, die dann ebenso in die Priorität des Verkehrεmittelε Vi ein¬ fließt;
- allgemein kann ebenso von Bedeutung sein, daß eine sehr große Verspätung eines einzelnen Verkehrsmittels Vi sehr unerwünscht ist, was durch Berücksichtigung dieεeε Effektε in der Priorität einfließen kann.
Die biεher beεchriebene, εequentielle Zuordnung der Verkehrε¬ mittel Vi hat die charakteriεtiεche Eigenschaft, daß schon „vergebene" Zeitintervalle nicht mehr geändert, beispielswei¬ se verschoben, werden dürfen. Dies kann einen relativ großen Verschnitt im Belegungsplan BP zur Folge haben, weil freie Zeitintervalle, die nur geringfügig zu klein sind, um von ei¬ nem noch nicht in dem Belegungsplan BP berücksichtigten Ver- kehrsmittel Vi belegt zu werden, nicht ausgenutzt werden.
Die Weiterbildung deε Verfahrens, die im folgenden beschrie¬ ben wird, verbessert das Verfahren zusätzlich hinsichtlich dieseε Problemε, in dem zugelaεεen wird, daß εchon verplante Zeitintervalle biε zu einem gewiεεen Grad noch verεchoben werden dürfen. Ein eventuell vorgegebener zeitlicher Sicherheitεabstand zwi¬ schen zwei Verkehrεmitteln Vi auf einem Teil TLNj deε Linien- netzeε LN wird bei der Weiterbildung dieεeε Verfahrens zu¬ nächst reduziert 20 (vgl. Figur 2). Das Verfahren V wird nun komplett unter Berücksichtigung deε reduzierten Sicherheitε- abstands durchgeführt.
Aufgrund des zu geringen Sicherheitsabstandes ist der resul¬ tierende Belegungsplan BP inkonsistent. Um ihn wieder konsi- stent zu machen, werden Zeitintervalle verεchoben. Dazu wird zunächst ein gerichteter Verschiebegraph vg generiert, um formal zu beschreiben, welche Zeitintervalle verschoben wer¬ den müssen, wenn ein bestimmtes Zeitintervall verschoben wird 22.
In einem davor durchgeführten Schritt 21 wird der Sicher¬ heitsabstand wieder auf den vor der Reduzierung festgesetzten Wert zurückgesetzt.
Nun wird der Verschiebegraph vg dekompaktiert 23, das heißt der resultierende Belegungsplan ist nun konεiεtent. Da hier¬ bei Zeitintervalle möglicherweiεe zu weit in die Zukunft ver¬ εchoben werden, wird in einem weiteren Schritt eine Kompak- tierung deε Verεchiebegraphε vg durchgeführt 24. In diesem Schritt werden die Zeitintervalle soweit wie möglich nach linkε verεchoben.
Daε Ergebniε iεt ein konsistenter und optimaler Belegungs¬ plan, optimal unter der Vorausεetzung, daß die Route für je- deε Verkehrsmittel Vi sowie die Reihenfolge der Verkehrεmit¬ tel Vi für jede Kante bereits optimal festgelegt wurden.
In einem letzten Schritt werden nun noch die neuen Zeitwerte für die Zeitintervalle aus dem Verschiebegraph vg entnommen und der Belegungsplan BP entsprechend angepaßt 25. Ausgangspunkt für die Generierung des Verschiebegraphεn vg ist der Belegungsplan BP.
Jeder Knoten v des Verschiebegraphε vg repräsentiert den Be- ginn eines Zeitintervalls im Belegungsplan BP. Dieser Zeit¬ wert gibt den Zeitpunkt an, zu dem die Spitze des Verkehrs- mittelε Vi den zum Zeitintervall zugehörigen Teil TLNj deε Liniennetzeε LN befährt.
Eine gerichtete Kante e in dem Verεchiebegraphen vg be¬ schreibt jeweils, daß der Zeitwert des Zielknotenε der ge¬ richteten Kante e mindeεtens so groß sein muß wie der Zeit¬ wert des Anfangsknotens der gerichteten Kante e.
Es werden folgende Parameter für die Knoten v und die Kanten e verwendet. Der Index v und der Index e sind beliebige na¬ türliche Zahlen, die jeweils einen Knoten v bzw. eine Kante e eindeutig identifizieren. Die Zahlen liegen in dem Bereich zwischen 1 und jeweils der Anzahl der in dem Verschiebegra- phen vg vorkommenden Knoten v bzw. Kanten e.
Folgende Parameter werden für die Knoten v und die Kanten e verwendet:
- time(v): aktueller Zeitwert des Knotens v, beispielsweiεe in Sekunden;
- mintime(v) : untere Schranke für den Zeitwert deε Knotens v, beispielεweiεe in Sekunden;
- movable(v) : Angabe, ob der Zeitwert, der dem Knoten v zuge¬ ordnet ist, geändert werden darf oder nicht;
- cost(e): Zeitwert des Zielknotens der gerichteten Kante e muß mindestenε so groß sein wie der Zeitwert des Anfangs- knotens der jeweiligen gerichteten Kante e plus cost(e). Der Parameter mintime(v) wird eingeführt, um beispielsweiεe Abfahrtszeiten von Verkehrsmitteln Vi in Zwischenhalteεtellen zu beschreiben, das heißt es soll berücksichtigt werden, daß das Verkehrsmittel Vi nicht vor einer vorgegebenen Zeit von der Zwischenhaltestelle abfahren darf.
Der Parameter movable(v) wird eingeführt, um z. B., bei Ver¬ wendung des Verfahrenε für schienengebundene Verkehrsmittel Vi, Gleissperren zu modellieren. In diesem Fall dürfen die Zeitwerte einer Gleissperre nicht geändert werden.
Desweiteren dürfen Zeitintervalle, die in der Vergangenheit liegen, nicht verschoben werden.
Die Kanten deε Verεchiebungsgraphen vg werden auf folgende Weise generiert:
Zur Erläuterung wird ein bestimmteε Zeitintervall z, welches in der vorgegebenen Route des Verkehrsmittels Vi und im Lini- ennetz LN enthalten ist eingeführt. Eε werden weiterhin fol¬ gende Größen eingeführt:
- ein folgendes Zeitintervall gn(z), das dem Zeitintervall z in dem Liniennetz LN direkt folgt;
- ein weiteres folgendes Zeitintervall zn(z), welcheε das dem Zeitintervall z direkt folgende Zeitintervall in den vorge¬ gebenen Fahrzeiten des Verkehrsmittels Vi beschreibt sowie ein vorangegangenes Zeitintervall zp(z), welches das dem Zeitintervall z direkt vorangegangene Zeitintervall in den vorgegebenen Fahrzeiten des Verkehrsmittels Vi darstellt.
Hat eine Kante e eine Konfliktkante, dann wird das zum Zei¬ tintervall z gehörige Konfliktintervall mit kiz bezeichnet. Der Mindestabstand zwischen zwei Zeitintervallen, welche der¬ selben Kante e, aber verschiedenen Vekehrsmitteln Vi zugeord- net wird, beispielsweise also ein Sicherheitsabstand, wird mit zs bezeichnet.
Es werden jeweils neue Kanten ermittelt, die einen Zielknoten t der jeweilε neuen Kante und einen Anfangεknoten u der je¬ weilε neuen Kante aufweisen. cost(u,t) bezeichnet das Gewicht der jeweilε neuen Kante. Ferner wird mit va(z) derjenige Kno¬ ten in dem Verεchiebegraphen vg bezeichnet, welcher den je¬ weiligen Beginn deε Zeitintervalls z repräsentiert.
Weiterhin wird eine Fahrzeit tedge für eine Streckenlänge der Kante e und eine Fahrzeit tlen für eine Streckenlänge, welche gleich der Länge deε Verkehrεmittelε Vi ist, eingeführt.
Bei der Generierung der neuen Kanten werden im weiteren un¬ terschiedliche Fälle aufgeführt. Dabei wird jeweils angege¬ ben, wie der Kantenparameter cost(u, t) festzulegen ist. Die große Anzahl der unterschiedlichen Fälle wird dadurch verur¬ sacht, daß die Knotenzahl in dem Verschiebegraphen vg mini- miert wurde. Beispielsweise führt die Elimination der Knoten, welche die Zeitwerte der Konfliktintervalle repräsentieren, dazu, daß vom Knoten va(z) zum Knoten va(gn(kiz)) eine Kante generiert werden muß, um Überlappfreiheit zwiεchen den Inter¬ vallen kiz und gn(kiz) zu gewährleiεten (εiehe Gleichung 3) .
Ohne Elimination dieser Knoten würde man einfach eine Kante von va(kiz) nach va(gn(kiz)) generieren, was in Gleichung (2) dargestellt ist.
u = va(z) und t = va(zn(z) ) (1)
Hierbei gilt cost(u, t) = tedge
u = va(z) und t = va(gn(z) ) (2)
Hierbei gilt coεt(u, t) = tedge + tlen + zs
u = va(z) und t = va(z) (3) Es gilt kir = gn(r) Hierbei gilt cost(u, t) = tedge + tlen + zε
u = va(z) und t = va(gn(kiz)) (4)
Hierbei gilt coεt(u, t) = tedge + tlen + zε
u = va(z) und t = va(r) (5)
Eε gilt kir = gn(kiz)
Hierbei gilt coεt(u, t) = tedge + tlen + zε
u = va(z) und t = va(gn(zp(z) ) ) (6)
Hierbei gilt coεt(u, t) = tlen + zs
u = va(z) und t = va(r) (7)
Es gilt kir = gn(zp(z)) Hierbei gilt cost(u, t) = tlen + zε
u = va(z) und t = gn(kizp(z) ) (8)
Hierbei gilt cost(u, t) = + tlen + zs
u = va(z) und t - va(r) (9)
Es gilt kir = gn(kizp(z)) Hierbei gilt cost(u, t) = tlen + zs
Ein Index r bezeichnet jeweils ein weiteres Zeitintervall un- gleich dem jeweiligen Zeitintervall z.
Ein Sonderfall führt zu vier weiteren Fällen, nämlich wenn das Verkehrsmittel Vi auf mehreren Kanten steht, das heißt wenn die Länge deε Verkehrsmittels Vi größer ist als die Län- ge der Kante selbst. Diese vier Fälle erhält man aus den
Gleichungen (6), (7), (8) und (9), indem man u = va(z) durch u = va(zn(z)) ersetzt.
Zur Verdeutlichung dieεes im vorigen beschriebenen Vorgehens ist in Figur 8 der Verschiebegraph vg zum Belegungsplan BP aus Figur 4 dargestellt. Die Kanten des Verschiebegraphen vg sind indiziert mit der jeweiligen Nummer des Falles bzw. der jeweiligen Gleichung gemäß der oben dargestellten Übersicht.
Zur Verdeutlichung der Vorteile, die das Verfahren aufweist, ist in den Figuren 5a und 5b für die jeweilige Topologie ei¬ nes zweiten Auεführungεbeispiels in den Figuren 5a und 5b an¬ gegebenen Liniennetzeε LN mit einer Verengung Ver, die nur von einem Verkehrεmittel Vi zu einem beεtimmten Zeitpunkt be¬ legt werden kann, in einem Wegzeitdiagramm die vorgegebenen Fahrzeiten von drei Verkehrsmitteln mit hoher Priorität VI, V2, V3 und einem Verkehrsmittel mit niedrigerer Priorität V4 dargestellt.
In Figur 5b ist eine auftretende Störung und eine damit ver- bundene Verspätung des Verkehrsmittels V2 dargestellt. Diese Verspätung führt zu einer Vergrößerung eines Zeitintervalls ti2/ das zwischen dem ersten Verkehrsmittel VI und dem zwei¬ ten Verkehrsmittel V2 liegt. Dieses Zeitintervall ti2 wird durch die Verspätung vergrößert zu einem neuen Zeitintervall t'ι2.
Die bekannten Verfahren würden, wie in Figur 6a dargestellt, keine Umdisponierung des einzelnen Verkehrεmittels vornehmen, da kein Konflikt vorliegt.
Durch daε erfindungεgemäße Verfahren wird jedoch eine gesamte Neugenerierung deε Belegungεplans BP durchgeführt ohne daß eine Konflikterkennung dazu notwendig wäre. Dies führt dazu, daß wie in Figur 6b dargestellt ist, die entstandene Zeitlük- ke t'12 dazu genutzt wird, daß das vierte Verkehrsmittel V4 mit niedrigerer Priorität in diesem Zeitintervall t'12 aur einer Verengung Ver des Liniennetzes LN fahren zu lassen, oh¬ ne damit die vorgegebenen Fahrzeiten der Verkehrsmittel V2 und V3 zu beeinflussen. Damit wird eine globale Verbesserung des gesamten Fahrverhaltens erreicht. Das Verfahren kann beispielεweise in periodischen Zeitabstän¬ den, deren Größe je nach Anwendung unterschiedlich ist, oder auch in unregelmäßigen Zeitabständen durchgeführt werden.
Es ist in einer Weiterbildung des Verfahrens ebenso vorgese¬ hen, daß das Verfahren durchgeführt, wenn Störungen in dem Liniennetz LN und/oder bei den Verkehrsmitteln Vi und/oder sonstige Störungen aufgetreten sind, die den Verkehrsfluß be¬ einflussen gemeldet werden. Diese Störungsmeldungen werden empfangen und gespeichert.
Unter einer Störung ist in diesem Zusammenhang beispielsweise ein Fall zu verstehen, wenn ein Teil TLNj des Liniennetzes LN ausfällt oder blockiert ist. In diesem Fall kann ein neuer Belegungsplan BP unter Berücksichtigung der gemeldeten Stö¬ rungen ermittelt werden.
Desweiteren ist eε vorgeεehen, Anschlußbeziehungen zwischen Verkehrsmitteln VI bei der Regelung und somit in dem Bele- gungsplan zu berückεichtigen, indem einfach abhängige An- kunfts- und Abfahrtszeiten der Verkehrsmittel Vi generiert werden. Dies bedeutet, daß für ein Verkehrsmittel Vi dieser Fall, daß es auf ein anderes Verkehrsmittel warten muß, in dem Belegungsplan BP berücksichtigt werden muß.
Eε ist ebenso in einer Weiterbildung des Verfahrens vorgese¬ hen, bei der Generierung des Belegungsplans (BP) mindeεtens eine der folgenden Nebenbedingungen zu berücksichtigen:
- Art des Verkehrsmittelε (Vi) , - Gewicht deε Verkehrsmittels (Vi) ,
- Länge deε Verkehrεmittels (Vi),
- Höchstgeschwindigkeit des Verkehrsmittelε (Vi),
- vorgegebene Haltestellen des Verkehrsmittels (Vi) auf der Route, - Mindeεtaufenthaltεzeit deε Verkehrsmittels (Vi) an den vor¬ gegebenen Haltestellen, - frühestmögliche Abfahrtszeit deε Verkehrεmittelε (Vi) von den vorgegebenen Haltestellen,
- topologiεche Nebenbedingungen der einzelnen Teile deε Lini¬ ennetzes (LN) .
Für den möglichen Fall, daß nicht nur eine mögliche Reihen¬ folge der Verkehrsmittel Vi auf dem Liniennetz LN vorge¬ schrieben ist, sondern mehrere, iεt es vorgesehen, alle mög¬ lichen vorgegebenen Auftragsreihenfolgen für die Verkehrsmit- tei Vi zu verplanen, das heißt für jede mögliche Auftragsrei¬ henfolge das Verfahren durchzuführen, und das Ergebnis einer Zielfunktion, die beiεpielsweise in einer gewichteten Summe ermittelter Verspätungen der Verkehrsmittel Vi beschreibt, speichert.
Eine optimale Auftragsreihenfolge ist diejenige, die von al¬ len möglichen Auftragsreihenfolgen den geringεten Wert in der Zielfunktion aufweist.
Die Zielfunktion kann jeweils abhängig von dem Anwendungsge¬ biet und den Schwerpunkten der Optimierung auch andere Para¬ meter aufweisen, beispielsweise die Gewichtung von Verspätun¬ gen, die eine vorgegebene Schwelle überschreiten müssen, um überhaupt berücksichtigt zu werden. Weitere Aspekte, die an- wendungsabhängig zu einer Veränderung der Zielfunktion füh¬ ren, können ohne Einεchränkungen in dem Verfahren berückεich- tigt werden.
Zur weiteren Verbesserung des Verfahrens ist es möglich, je- weils nur den Ergebniswert der Zielfunktion bei Durchführung des Verfahrens für jede mögliche Auftragsreihenfolge zu spei¬ chern und nicht alle Parameter für die jeweilige Zuordnung. In diesem Fall muß, nachdem die optimale Auftragsreihenfolge gefunden wurde, für diese Auftragsreihenfolge das Verfahren noch einmal durchgeführt werden. Diese Vorgehensweise weist hinsichtlich der Nutzung deε Speicherbedarfε deε das Verfah¬ ren durchführenden Rechners erhebliche Vorteile auf. Das Verfahren des „Ausprobierens" aller möglichen Auftrags¬ reihenfolgen kann durch ein Beεchränken der auεzuprobierenden Möglichkeiten weitergebildet werden.
Zur Verdeutlichung wird eine Annahme getroffen, daß genau f Aufträge zu verplanen εind und g Aufträge bereits verplant wurden. In diesem Fall läßt sich folgende untere Schranke für den Zielfunktionεwert angeben, den man nach der Verplanung der restlichen o = f - g Aufträge erhält:
Es werden die Restaufträge o einzeln unter Berücksichtigung der schon verplanten Aufträge g verplant. Im folgenden werden die Zielfunktionswerte der o Einzelplanungen zum Zielfunkti- onswert der εchon durchgeführten g Planungen addiert. Iεt die dadurch berechnete untere Schranke größer oder gleich dem Zielfunktionswert der biεher beεten Auftragεreihenfolge Popt' welche während deε Verfahrenε laufend aktualisiert wird, dann kann keine der o! (! bedeutet in diesem Zusammenhang Fakul- tat, also alle Permutationen der o Auftragsreihenfolgen) o Auftragsreihenfolgen besεer εein als die Auftragsreihenfolge popt• Folglich brauchen diese Auftragsreihenfolgen nicht mehr berücksichtigt werden.
Weiterhin kann eine Optimierung der Reihenfolge der Verzwei¬ gung vorgenommen werden. Hierbei wird nach der Planung von g Aufträgen die restlichen o Aufträge, die noch zu verplanen sind, der Reihe nach probeweise verplant. Die Reihenfolge, in der diese probeweise Verplanung εtattfindet, kann optimiert werden, indem als ersteε derjenige Auftrag verplant wird, welcher unter allen o Aufträgen den geringsten Zuwachε am Zielfunktionεwert verursacht. Demgemäß werden noch vor dem Verzweigen alle o Aufträge in bezug auf diesen Zuwachs auf¬ steigend sortiert.
Der im vorigen beschriebene Branch-and-Bound-Algorithmus kann mit Hilfe zweier Parameter beεchleunigt werden: - Eine Branch-Schranke bs.
Wurden beim exakten Verfahren bereits g Aufträge bearbei¬ tet, dann εtanden alε nächstes genau o Aufträge zur Auswahl für die weitere Verplanung. Mit der Branch-Schranke bs, die kleiner ist als die Zahl der Aufträge f insgeεamt, wird die Anzahl der Aufträge, welche zur Auswahl εtehen, auf den Wert der Branch-Schranke bs beschränkt.
- Ein Streckungsfaktor sf.
Bei dieser Option wird die berechnete untere Schranke mit dem Streckungεfaktor sf, dessen Wert größer als 1 ist, mul¬ tipliziert. Dies ist äquivalent dazu, daß man εich vor¬ stellt, man hätte eine besεere untere Schranke. Der Strek- kungεfaktor sf wird gestaffelt festgelegt, und zwar propor¬ tional zu der Anzahl der noch zu verplanenden Aufträge o. Dabei gilt: sf = 1 für o = f.
Das erfindungsgemäße Verfahren sowie alle im vorigen be- schriebenen Weiterbildungen des Verfahrens können für unter¬ schiedliche Anwendungsgebiete eingeεetzt werden.
So ist es zum Beispiel vorgesehen, wie im vorigen beschrieben wurde, daε Verfahren für schienengebundene Verkehrεmittel Vi einzuεetzen.
Eε iεt ferner vorgesehen, das Verfahren einzusetzen zur Rege¬ lung von Flugzeugen. In diesem Fall entspricht das Liniennetz mit den einzelnen Teilen TLNj des Liniennetzes LN den den einzelnen Flugzeugen auf einer Flugroute zugeordneten Luft¬ korridoren.
Ein weiteres Anwendungsgebiet deε Verfahrenε liegt in der Disposition von Sammelhaltepunkten. Hierbei ist die Vorge- hensweise derart, daß zuerst die Verkehrsmittel Vi den jewei¬ ligen Haltepunkten deε Sammelhaltepunkts zugeordnet werden, und dann für jedes Verkehrsmittel Vi die optimale Route be¬ rechnet wird.
Das Verfahren kann außerdem vorteilhaft verwendet werden zur Erstellung von Sollfahrplänen für die Verkehrsmittel Vi.
Allgemein ist daε Verfahren εelbstverständlich für jede Art von Netzdispositionen einsetzbar, da das Verfahren keine Spe- ziallöεung darεtellt, εondern für allgemeine Netzwerkgraphen anwendbar iεt.

Claims

Patentansprüche
1. Verfahren zur Regelung von Verkehrsmitteln (Vi; i = 1 - m) ,
- bei dem die Verkehrsmittel (Vi) mit vorgegebenen Ankunfts¬ zeiten und vorgegebenen Abfahrtszeiten der Verkehrsmittel (Vi) und vorgegebenen Sequenzen von Start- und Zielpunkten der Verkehrsmittel (Vi) in einem Liniennetz (LN) in Form eines ungerichteten Netzwerkgraphen dargestellt wird,
- bei dem ein Belegungsplan (BP) , in dem freie Zeitintervalle des Belegungsplans (BP) in Form eines Intervallgraphen (IG) dargestellt werden, durch den Teile des Liniennetzes (TLNj; j = 1 - n) zu bestimmten Zeitintervallen bestimmten Ver- kehrεmitteln (Vi)zugeordnet werden, durch einen Rechner ge¬ neriert wird, indem alle Verkehrsmittel (Vi) sequentiell entsprechend wählbarer Prioritäten der Verkehrsmittel (Vi) und der Sequenzen von Start- und Zielpunkten der Verkehrs¬ mittel (Vi) den jeweils von den Verkehrsmitteln (Vi) benö- tigten Teilen (TLNj) des Liniennetzes (LN) zugeordnet wer¬ den, wobei
-- Knoten des Intervallgraphen (IG) Zeitintervalle zugeord¬ net werden, in denen der entsprechende Teil (TLNj) deε Liniennetzeε (LN) noch nicht belegt ist, -- Kanten des Intervallgraphen (IG) mögliche Routen für die Verkehrsmittel (Vi) unter Berücksichtigung örtlicher und zeitlicher Einschränkungen, die sich mindestens aus der Topologie des Liniennetzes und den vorgegebenen Ankunfts¬ zeiten und Abfahrtεzeiten der Verkehrεmittel (Vi) erge- ben, zugeordnet werden,
-- dem jeweiligen Verkehrsmittel (Vi) unter Verwendung ei¬ nes Kürzesten-Wege-Verfahrens (Shortest Path Algorithm) eine optimale Route in dem Intervallgraphen (IG) zugeord¬ net wird (05) , — freie Zeitintervalle der einzelnen Teile (TLNj) des Li¬ niennetzes (LN) angepaßt werden (06) an die Belegung des Liniennetzes (LN) durch das jeweilige Verkehrsmittel (Vi), und
- bei dem die Verkehrsmittel entsprechend den Anforderungen des Belegungεplanε (BP) geregelt werden (08) .
2. Verfahren nach Anspruch 1, bei dem ein alter Belegungsplan (BP') zu Beginn des Verfahrens vollständig gelöscht (02) wird.
3. Verfahren nach Anspruch 1 oder 2,
- bei dem empfangene gemeldete Störungen über das Liniennetz (LN) und/oder über die Verkehrsmittel (Vi) und/oder sonsti¬ ge Störungen, die den Verkehrsfluß beeinflussen , gespei¬ chert werden, und - bei dem daraufhin der Belegungsplan (BP) neu generiert wird unter Berücksichtigung der empfangenen Störungen.
4. Verfahren nach einem der Ansprüche 1 bis 3, bei dem auftretende Konfikte in dem Belegungsplan (BP) durch Wartezeiten, die den Verkehrsmitteln mit vergleichsweise niedrigerer Priorität zugeordnet werden, gelöst werden.
5. Verfahren nach einem der Ansprüche 1 bis 4, bei dem als Kürzesteε-Wege-Verfahren (Shorteεt Path Algo- rithm) ein Dijkεtra Algorithmuε vorgesehen wird.
6. Verfahren nach einem der Ansprüche 1 bis 4, bei dem alε Kürzeεteε-Wege-Verfahren (Shorteεt Path Algo¬ rithm) ein Moore Algorithmuε vorgesehen wird.
7. Verfahren nach einem der Ansprüche 1 bis 6, bei dem die Prioritäten der Verkehrsmittel (Vi) nach minde¬ stens einem der folgenden Kriterien ermittelt werden :
- eine vorgebbare Bedeutung der einzelnen Verkehrsmittel (Vi),
- Geschwindigkeiten der einzelnen Verkehrsmittel (Vi) , - vorgegebene Abfahrtszeiten der einzelnen Verkehrsmittel (Vi),
- vorgegebene Ankunftszeiten der einzelnen Verkehrsmittel (Vi), - Verspätungen der nach den einzelnen Verkehrεmittel (Vi) .
8. Verfahren nach einem der Anεprüche 1 biε 7, bei dem Anschlußbedingungen der Verkehrsmittel (Vi) bei der Generierung des Belegungsplans (BP) berücksichtigt werden.
9. Verfahren nach einem der Anprüche 1 bis 8,
- bei dem zu Beginn des Verfahrens ein vorgegebener Sicher¬ heitsabstand der Verkehrsmittel (Vi) auf mindestens einem Teil (TLNj) des Liniennetzes (LN) reduziert wird (20), - bei dem nach Beendigung deε Verfahrenε (V) der reduzierte Sicherheitsabstand wieder erhöht wird auf den vorgegebenen Sicherheitsabstand (21),
- bei dem ein Verschiebegraph (vg) generiert wird (22),
- bei dem der Verschiebegraph (vg) dekompaktiert wird (23), - bei dem der Verschiebegraph (vg) kompaktiert wird (24) , und
- bei dem der Belegungsplan (BP) entsprechend des kompaktier- ten Verschiebegraphens (vg) angepaßt wird.
10. Verfahren nach einem der Ansprüche 1 bis 9, - bei dem, wenn unterschiedliche Reihenfolgen der Verkehrs¬ mittel (Vi) in dem Liniennetz (LN) möglich sind, das Ver¬ fahren für mindestenε zwei mögliche Reihenfolgen durchge¬ führt wird, und
- bei dem die Regelung der Reihenfolge als eine optimale Re- gelung verwendet wird, die für eine vorgebbare Zielfunktion einen optimalen Wert ergibt.
11. Verfahren nach Anspruch 10, bei dem ein Branch-and-Bound-Verfahren zur Reduktion der An- zahl zu untersuchender Reihenfolgen der Verkehrsmittel in dem Liniennetz (LN) vorgeεehen wird.
12. Verfahren nach einem der Anprüche 1 bis 11, bei dem die Regelung der Verkehrsmittel (Vi) erfolgt durch Regelung der Haltezeiten der Verkehrsmittel (Vi) an Halte¬ punkten deε Liniennetzeε (LN) und/oder durch Regelung der Ge- εchwindigkeiten der Verkehrsmittel (Vi) .
13. Verfahren nach einem der Ansprüche 1 bis 12, bei dem ein möglicher Gleiswechεelbetrieb bei der Generierung deε Belegungεplans berücksichtigt (BP) wird.
14. Verfahren nach einem der Anεprüche 1 bis 13, bei dem bei der Generierung des Belegungsplans (BP) minde¬ stens eine der folgenden Nebenbedingungen berücksichtigt wer¬ den: - Art des Verkehrsmittelε (Vi) ,
- Gewicht des Verkehrεmittels (Vi) ,
- Länge des Verkehrsmittels (Vi) ,
- Höchstgeschwindigkeit des Verkehrsmittelε (Vi) ,
- vorgegebene Haltestellen des Verkehrεmittels (Vi) auf der Route,
- Mindestaufenthaltszeit des Verkehrsmittelε (Vi) an den vor¬ gegebenen Halteεtellen,
- früheεtmögliehe Abfahrtszeit des Verkehrsmittels (Vi) von den vorgegebenen Haltestellen, - topologische Nebenbedingungen der einzelnen Teile des Lini¬ ennetzes (LN) .
15. Verfahren nach einem der Ansprüche 1 bis 13,
- bei dem daε Verfahren eingeεetzt wird zur Regelung der Ver- kehrεmittel (Vi) an einem Sammelhaltepunkt mehrerer Ver¬ kehrεmi11e1, und
- bei dem zu Beginn des Verfahrens die Verkehrsmittel (Vi) beεtimmten vorgegebenen Teilen deε Liniennetzes (LN) zuge¬ ordnet werden.
16. Verfahren nach einem der Ansprüche 1 bis 13, - bei dem das Verfahren eingesetzt wird zu Regelung von Flug¬ zeugen, und
- bei dem die Teile (TLNj) des Liniennetzes (LN) durch Luft¬ korridore, die jeweils eindeutig in einem Zeitintervall den einzelnen Flugzeugen zugeordnet werden.
17. Verfahren nach einem der Ansprüche 1 bis 13, bei dem der Belegungsplan (BP) verwendet wird zur Erεtellung von Sollfahrplänen für die Verkehrεmittel (Vi) .
PCT/DE1996/001498 1995-09-07 1996-08-08 Verfahren zur regelung von verkehrsmitteln WO1997009218A2 (de)

Priority Applications (1)

Application Number Priority Date Filing Date Title
AU72774/96A AU7277496A (en) 1995-09-07 1996-08-08 Transport means control process

Applications Claiming Priority (2)

Application Number Priority Date Filing Date Title
DE19533127.3 1995-09-07
DE19533127 1995-09-07

Publications (2)

Publication Number Publication Date
WO1997009218A2 true WO1997009218A2 (de) 1997-03-13
WO1997009218A3 WO1997009218A3 (de) 1997-04-10

Family

ID=7771550

Family Applications (1)

Application Number Title Priority Date Filing Date
PCT/DE1996/001498 WO1997009218A2 (de) 1995-09-07 1996-08-08 Verfahren zur regelung von verkehrsmitteln

Country Status (3)

Country Link
AR (1) AR003516A1 (de)
AU (1) AU7277496A (de)
WO (1) WO1997009218A2 (de)

Cited By (9)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
EP0933280A2 (de) * 1998-01-26 1999-08-04 Alcatel Lösungsverfahren für Fahrplankonflikte in Transportnetzen und Datenverarbeitungseinrichtung dafür
US6016307A (en) * 1996-10-31 2000-01-18 Connect One, Inc. Multi-protocol telecommunications routing optimization
US6574547B2 (en) 2001-09-27 2003-06-03 International Business Machines Corporation Use of vehicle permissions to control individual operator parameters in a hierarchical traffic control system
US6580997B2 (en) 2001-09-27 2003-06-17 International Business Machines Corporation Hierarchical traffic control system which includes vehicle roles and permissions
US6609061B2 (en) 2001-09-27 2003-08-19 International Business Machines Corporation Method and system for allowing vehicles to negotiate roles and permission sets in a hierarchical traffic control system
US6611750B2 (en) 2001-09-27 2003-08-26 International Business Machines Corporation Hierarchical traffic control system
US6646568B2 (en) 2001-09-27 2003-11-11 International Business Machines Corporation System and method for automated parking
WO2009043770A1 (de) * 2007-09-27 2009-04-09 Siemens Aktiengesellschaft Verfahren zur fahrplangenerierung für verkehrssysteme mit berücksichtigung zeitlicher schranken
FR2955954A1 (fr) * 2010-02-04 2011-08-05 Ineo Systrans Systeme de gestion de services

Citations (2)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US5177684A (en) * 1990-12-18 1993-01-05 The Trustees Of The University Of Pennsylvania Method for analyzing and generating optimal transportation schedules for vehicles such as trains and controlling the movement of vehicles in response thereto
FR2692542A1 (fr) * 1992-06-23 1993-12-24 Mitsubishi Electric Corp Système de commande de trafic ferroviaire.

Patent Citations (2)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US5177684A (en) * 1990-12-18 1993-01-05 The Trustees Of The University Of Pennsylvania Method for analyzing and generating optimal transportation schedules for vehicles such as trains and controlling the movement of vehicles in response thereto
FR2692542A1 (fr) * 1992-06-23 1993-12-24 Mitsubishi Electric Corp Système de commande de trafic ferroviaire.

Non-Patent Citations (3)

* Cited by examiner, † Cited by third party
Title
DATABASE INSPEC INSTITUTE OF ELECTRICAL ENGINEERS, STEVENAGE, GB Inspec No. 3819895, KOMAYA K ET AL: "ESTRAC-III: an expert system for train traffic control in disturbed situations" XP002024513 in der Anmeldung erw{hnt & CONTROL, COMPUTERS, COMMUNICATIONS IN TRANSPORTATION. SELECTED PAPERS FROM THE IFAC/IFIP/IFORS SYMPOSIUM, PARIS, FRANCE, 19-21 SEPT. 1989, ISBN 0-08-037025-X, 1990, OXFORD, UK, PERGAMON, UK, Seiten 147-153, *
PROCEEDINGS OF THE IEEE/ASME JOINT RAILROAD CONFERENCE, ST. LOUIS, MAY 21 - 23, 1991, Nr. -, 21.Mai 1991, INSTITUTE OF ELECTRICAL AND ELECTRONICS ENGINEERS, Seiten 59-66, XP000289153 KIYOTOSHI KOMAYA: "A NEW SIMULATION METHOD AND ITS APPLICATION TO KNOWLEDGE-BASED SYSTEMS FOR RAILWAY SCHEDULING" *
SIGNAL + DRAHT, Bd. 85, Nr. 5, 1.Mai 1993, HAMBURG,DE, Seiten 166-169, XP000413530 DANNENBERG H ET AL: "ANWENDUNG VON SIMULATIONSMODELLEN FUR FLANUNGS- UND STEUERUNGSPROBLEME IM EISENBAHNBETRIEB" *

Cited By (13)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US6016307A (en) * 1996-10-31 2000-01-18 Connect One, Inc. Multi-protocol telecommunications routing optimization
US9806988B2 (en) 1996-10-31 2017-10-31 Patentmarks Communications, Llc Multi-protocol telecommunications routing optimization
EP0933280A2 (de) * 1998-01-26 1999-08-04 Alcatel Lösungsverfahren für Fahrplankonflikte in Transportnetzen und Datenverarbeitungseinrichtung dafür
EP0933280A3 (de) * 1998-01-26 2002-05-15 Alcatel Lösungsverfahren für Fahrplankonflikte in Transportnetzen und Datenverarbeitungseinrichtung dafür
US6611750B2 (en) 2001-09-27 2003-08-26 International Business Machines Corporation Hierarchical traffic control system
US6609061B2 (en) 2001-09-27 2003-08-19 International Business Machines Corporation Method and system for allowing vehicles to negotiate roles and permission sets in a hierarchical traffic control system
US6580997B2 (en) 2001-09-27 2003-06-17 International Business Machines Corporation Hierarchical traffic control system which includes vehicle roles and permissions
US6646568B2 (en) 2001-09-27 2003-11-11 International Business Machines Corporation System and method for automated parking
US6681175B2 (en) 2001-09-27 2004-01-20 International Business Machines Corporation Hierarchical traffic control system which includes vehicle roles and permissions
US6885935B2 (en) 2001-09-27 2005-04-26 International Business Machines Corporation Use of vehicle permissions to control individual operator parameters in a hierarchical traffic control system
US6574547B2 (en) 2001-09-27 2003-06-03 International Business Machines Corporation Use of vehicle permissions to control individual operator parameters in a hierarchical traffic control system
WO2009043770A1 (de) * 2007-09-27 2009-04-09 Siemens Aktiengesellschaft Verfahren zur fahrplangenerierung für verkehrssysteme mit berücksichtigung zeitlicher schranken
FR2955954A1 (fr) * 2010-02-04 2011-08-05 Ineo Systrans Systeme de gestion de services

Also Published As

Publication number Publication date
WO1997009218A3 (de) 1997-04-10
AU7277496A (en) 1997-03-27
AR003516A1 (es) 1998-08-05

Similar Documents

Publication Publication Date Title
DE60001915T2 (de) Dynamischer verkehrsführungsalgorithmus
DE69814276T2 (de) Rechnergestütztes Konfliktlösungsverfahren für Eisenbahnnetz
DE69514444T2 (de) Verfahren für die Ablauffolgeplanung von aufeinanderfolgenden Aufgaben mit Zeitzwangsbedingungen
DE102009024130B4 (de) Verfahren zur echtzeitfähigen Bahnplanung kontinuierlicher, rucksprungfreier Sollwerttrajektorien
EP1293948B1 (de) Verfahren und Anordnung zur Farhrplanoptimierung in Liniennetzen
DE69206917T2 (de) Hilfsverfahren für die Entwicklung einer miteinander kommunizierender Automatengruppe
DE19910311A1 (de) Automatisierungssystem mit wiederverwendbaren Automatisierungsobjekten und Verfahren zur Wiederverwendung von Automatisierungslösungen in Engineering-Werkzeugen
WO1997009218A2 (de) Verfahren zur regelung von verkehrsmitteln
DE3839675C2 (de) Optimierer für ein parameterabhängiges Steuerungssystem
EP2161698B1 (de) Verfahren zur Koordinierung von lichtsignalgesteuerten Knoten in einem Straßennetz
DE4409179A1 (de) System und Verfahren zur dynamischen Informationsverarbeitung
WO1997009217A2 (de) Verfahren zur regelung spurgebundener fahrzeuge
EP3937151A1 (de) Vorrichtung und verfahren zur steuerung eines verkehrsflusses in einem verkehrsnetz durch einen optimalen signalphasenplan
EP0671027B1 (de) Verfahren zum erstellen der anwendungsabhängigen logik eines freiprogrammierbaren schaltwerkes, einrichtung zur durchführung dieses verfahres und einrichtung zum betrieb eines steuerungssystems unter verwendung eines so erstellten programms
DE102023001698A1 (de) Verfahren zu einer automatisierten Generierung von Daten für rasterkartenbasierte Prädiktionsansätze
DE19510343C2 (de) Verfahren zur sequentiellen Vorsteuerung eines Prozesses
DE4403037A1 (de) Verfahren zum Betrieb eines Streckennetzes
EP0859988B1 (de) Verfahren zur zuordnung von ressourcen auf fahrzeuge, die eine vorgegebene strecke befahren, durch einen rechner
EP1500567B1 (de) Verfahren zur Auflösung von Konflikten in einem spurgebundenen Verkehrssystem
DE102013020582A1 (de) Verfahren zum computergestützten Nachbilden einer Produktionsanlage, Verfahren zur Inbetriebnahme einer Produktionsanlage, Konfigurationseinrichtung und Produktionsanlage
EP0796779B1 (de) Verfahren zur Steuerung und Sicherung eines spurgeführten Transportsystems
EP0284605B1 (de) Software-werkzeug zur automatischen erzeugung einer funktionsplangraphik
DE3784189T2 (de) Vorrichtung und verfahren zur steuerung der loeschung eines speicherbereichs.
WO2022254009A1 (de) Verfahren zum erzeugen eines steuerprogramms für ein automatisierungssystem und programmierwerkzeug
EP3991161A1 (de) Verfahren zur steuerung eines verkehrssystems, vorrichtung, computerprogramm, und computerlesbares speichermedium

Legal Events

Date Code Title Description
AK Designated states

Kind code of ref document: A2

Designated state(s): AU CN JP US

AL Designated countries for regional patents

Kind code of ref document: A2

Designated state(s): AT BE CH DE DK ES FI FR GB GR IE IT LU MC NL PT SE

AK Designated states

Kind code of ref document: A3

Designated state(s): AU CN JP US

AL Designated countries for regional patents

Kind code of ref document: A3

Designated state(s): AT BE CH DE DK ES FI FR GB GR IE IT LU MC NL PT SE

DFPE Request for preliminary examination filed prior to expiration of 19th month from priority date (pct application filed before 20040101)
121 Ep: the epo has been informed by wipo that ep was designated in this application
122 Ep: pct application non-entry in european phase