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

WO1997009218A2 - Transport means control process - Google Patents

Transport means control process 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
German (de)
French (fr)
Other versions
WO1997009218A3 (en
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/en
Publication of WO1997009218A3 publication Critical patent/WO1997009218A3/en

Links

Classifications

    • BPERFORMING OPERATIONS; TRANSPORTING
    • B61RAILWAYS
    • B61LGUIDING RAILWAY TRAFFIC; ENSURING THE SAFETY OF RAILWAY TRAFFIC
    • B61L27/00Central railway traffic control systems; Trackside control; Communication systems specially adapted therefor
    • B61L27/10Operations, e.g. scheduling or time tables
    • B61L27/16Trackside 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

To control transport means (Vi) in a predetermined line system (LN) an existing occupation plan (BP') is completely erased and anew one (BP) fully generated so that a transport means (Vi) is allocated to certain time intervals and routes in an interval graph (IG). A shortest path algorithm is used in the allocation of optimum routes and time intervals for the transport means (Vi) concerned. It is thereby possible to attain an overall optimised allocation and control of transport means (Vi) on parts (ZTLNj) of the line system (LN).

Description

Beschreibungdescription
Verfahren zur Regelung von Verkehrsmitteln.Procedure for regulating means of transport.
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.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.
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.This area of application becomes particularly important in the event of malfunctions in the operation of the line network. In the event of disruptions, the changes to the routes or the driving instructions for the individual means of transport must be carried out in such a way that the effects of the disruption on the overall operation of the line network are kept as low as possible.
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).Methods for determining the shortest paths (shortest path algorithms) in a network graph are known (E. Moore, The Shortest Path Through a Maze, In Proceedings International Symposium on the Theory of Switching, Part 2, April 2 - 5, p. 285-292, 1957; and E. Dijkstra, A Note on Two Problems in Connexion with Graphε, Numerische Mathematik, Volume 1, Springer Verlag, pp. 269 to 271, 1959).
Ein Verfahren zur automatischen Disposition von Zügen ist be- kannt (H. Schaefer et al, An Expert System for Real-TimeA method for the automatic disposition of trains is known (H. Schaefer et al, An Expert System for Real-Time
Train Dispatching, Railway Operations, Computers in RailwaysTrain 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-4, Volume 2, COMPRAIL 94, T. Murthy et al (editors), Computational 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) .5, p. 27 to 34, 1994). This procedure is based on conflict detection and conflict resolution. In this context, there is a conflict if the schedule deviations are so large that the handling of the driving operation according to a predetermined one Target schedule is no longer possible. The conflicts are resolved here with the help of a knowledge base (decision rules).
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.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.
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.Another conflict-based method is from (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, pp. 147 to 153, 1989). The procedure also uses local decision rules to resolve the conflict. The disadvantages that have been described for the previous method naturally also apply to this method, since this method is based on the same basic principles of conflict detection and conflict resolution.
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.A method that is also based on conflict detection and conflict resolution, but uses so-called branch and bound methods to solve it (R. Sauder, Computer Aided Train Dispatching: Decision Support through Optimization, INTERFACES 13, p. 24) to December 37, 1993). The method has the same disadvantages as those described in the previous method.
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.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.
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.In contrast to the methods which simulate the behavior of the dispatcher in an expert system based on conflict detection and conflict resolution, the method according to the invention pursues a fundamentally different objective.
Durch das Verfahren wird eine weitgehend automatische und global optimierte Regelung von Verkehrsmitteln erreicht; IM Gegensatz zu den lokalen Entscheidungsregeln der bekannten Verfahren.A largely automatic and globally optimized regulation of means of transport is achieved by the method; Contrary to the local decision rules of the known procedures.
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.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.
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.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. When assigning the individual means of transport to the occupancy plan, 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.
Wenn ein Verkehrsmittel einem Zeitintervall und einer Route zugeordnet wurde, wird der Belegungsplan für die einzelnenIf a means of transport has been assigned to a time interval and a route, the occupancy plan for the individual
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.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. In addition, 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.
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.The further development of the method according to claim 2 makes it possible to immediately recognize any faults that may occur in a line network and to take them into account in a regeneration of the occupancy plan in order to minimize the effects of the faults that have occurred on the entire line network.
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.By developing the method according to claim 8, 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.
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.With the further development of the method according to claim 13, different secondary conditions are taken into account when generating the occupancy plan, as a result of which the regulation is further improved. Further developments of the invention result from the dependent claims.
Ein bevorzugtes Ausführungsbeispiel der Erfindung ist in den Figuren dargestellt und wird im folgenden näher beschrieben.A preferred embodiment of the invention is shown in the figures and is described in more detail below.
Es zeigenShow it
Figur 1 ein Ablaufdiagramm, in dem einzelne Verfahrensschrit- te des Verfahrens dargestellt sind;FIG. 1 shows a flow diagram in which individual method steps of the method are shown;
Figur 2 ein Ablaufdiagramm, in dem einige zusätzliche Verfah¬ rensschritte, die zur Kompaktierung deε Belegungs¬ plans dienen, beschrieben sind;FIG. 2 shows a flow chart in which some additional procedural steps which serve to compact the occupancy plan are described;
Figur 3 eine Skizze, in der ein Liniennetz eines einfachenFigure 3 is a sketch in which a line network of a simple
Ausführungsbeispiels mit vier Teilen dargestellt ist;Embodiment is shown with four parts;
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;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;
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;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;
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;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;
Figur 8 einen Belegungsplan und einen Verschiebegraphen.Figure 8 shows an occupancy plan and a shift graph.
Anhand der Figuren 1 bis 8 wird das Verfahren weiter erläu- tert.The method is explained further with reference to FIGS. 1 to 8.
In Figur 1 sind in Form eines Ablaufdiagramms einzelne Ver¬ fahrensschritte dargestellt.1 shows individual process steps in the form of a flow chart.
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.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.
Jedem Verkehrsmittel Vi sind vorgegebene Ankunftszeiten und vorgegebene Abfahrtszeiten für jede Halteεtelle, die das je¬ weilige Verkehrsmittel Vi anfahren soll, zugeordnet.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.
Außerdem sind jedem Verkehrsmittel Vi auch Sequenzen von Start- und Zielpunkten vorgegeben, die jedes Verkehrsmittel Vi jeweils zu befahren hat.In addition, each means of transport Vi are also given sequences of starting and destination points which each means of transport Vi has to travel through.
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:A possibly already existing assignment of means of transport Vi to parts TLNj of the line network LN at certain time intervals, which is stored in a computer, ie an old occupancy plan BP ', is deleted 02. 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. The assignment, which is hereinafter referred to as 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:
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.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.
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 a further step 05, 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.
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 a subsequent step 06, 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.
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.In 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.
Das Liniennetz LN wird innerhalb des Rechners in Form eines ungerichteten Netzwerkgraphens, bestehend aus Knoten und Kan¬ ten, dargestellt.The line network LN is represented within the computer in the form of an undirected network graph consisting of nodes and edges.
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.In this context, 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.
Eine Kante des ungerichteten Netzwerkgraphenε repräεentiert jeweilε einen Teil TLNj deε Liniennetzeε LN (vgl. Figur 3).An edge of the undirected network graph represents a part TLNj of the line network LN (see FIG. 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 auchTwo 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
Durchrutschwege und rückwärtige Auflösungen von Teilen TLNj des Liniennetzes LN beschreiben zu können.Slip routes and rearward resolutions of parts TLNj of the line network LN can be described.
Eine Route wird repräsentiert durch die Angabe eines Start- knotens des ungerichteten Netzwerkgraphens und eines Zielkno- tenε deε ungerichteten Netzwerkgraphenε.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.
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.So that it is possible to also take into account circular relationships, when using the method for rail-bound means of transport Vi this means, for example, turning means of transport Vi, in this case several routes are defined for the respective means of transport Vi, which differ from one another be made dependent. The route dependencies are described using a directional route graph. In this route graph, connection relationships between the means of transport Vi, that is, route dependencies between different means of transport Vi, can also be taken into account.
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.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.
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.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.
In Figur 3 ist ein einfaches Liniennetz LN mit vier Teilen TLNj, j = 1..4, dargeεtellt.FIG. 3 shows a simple line network LN with four parts TLNj, j = 1..4.
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.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.
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.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.
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.Here, 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.
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.This means that TLNl is the conflicting edge of TLN3 and TLN3 is the conflicting edge of TLNl. As a result, 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.
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.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.
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ß.Furthermore, in accordance with the procedure described in FIG. 4, 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.
Wie im vorigen beschrieben wurde, wird ein alter, eventuell schon vorhandener Belegungsplan BP' bei Neugenerierung des Belegungsplans BP vollständig gelöscht 02.As described in the previous, an old, possibly already existing occupancy plan BP 'is completely deleted when the occupancy plan BP is regenerated 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.FIG. 7 shows the occupancy plan BP in the form of an interval graph IG. There are all available, i.e. free time intervals in the occupancy plan BP through nodes represented, to which the specification of the respective time interval is assigned as an attribute.
Kanten werden in dem Intervallgraphen IG genau dann einge- führt, wenn eine Fahrt zwischen den beiden zugehörigen Zei¬ tintervallen möglich ist.Edges are introduced into the interval graph IG precisely when it is possible to travel between the two associated time intervals.
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.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.
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.On the interval graph IG thus created, 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 Kehrsmittelε Vi applied.
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) .Examples of shortest path methods are known (E. Moore, The Shortest Path Through a Maze, In Proceedings International Symposium on the Theory of Switching, Part 2, April 2-5, pp. 285 to 292, 1957; and E. Dijkstra, A Note on Two Problem in Connexion with Graphs, Numerische Mathematik, Band 1, pp. 269 to 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.Other methods for determining a shortest path in a network graph can also be used without restriction in this method.
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.In this way, 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.
Die Prioritäten der Verkehrsmittel Vi dienen desweiteren als Gewichte im Rahmen einer im weiteren beschriebenen Zielfunk¬ tion.The priorities of the means of transport Vi also serve as weights within the scope of a target function described below.
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.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.
Im Anschluß daran werden die Teile TLNj mit den entεprechen- den Zeitintervallen für das jeweilige Verkehrsmittel Vi end¬ gültig belegt 07.Subsequently, the parts TLNj are finally assigned 07 with the corresponding time intervals for the respective means of transport Vi.
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.When the occupancy plan BP has been generated completely, 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.
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.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.
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.For example, by simply adding or changing edges, it is possible to provide a possibly changing track operation for certain parts TLNj of the line network LN when using the method for rail-bound means of transport Vi. For this purpose, it is only necessary to release the intended part TLNj for which a track change operation, that is to say a change to a rail modeled by an edge, which is provided for another direction of the same route, for a certain time interval.
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.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.
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:As described in the previous section, 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:
- 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;- 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;
- die Geschwindigkeiten der einzelnen Verkehrsmittel Vi kön- nen ebenso in die Priorität des jeweiligen Verkehrεmittels- The speeds of the individual means of transport Vi can also be the priority of the respective means of transport
Vi einfließen;Inflow Vi;
- auch die Startzeiten der einzelnen Verkehrsmittel Vi können berücksichtigt werden bei der Bildung der Priorität der Verkehrsmittel Vi;- 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;
- 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;- just like the start time, ie the departure time 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;
- 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.- In general, it can also be important that a very long delay of an individual means of transport Vi is very undesirable, which can be given priority by taking this effect into account.
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.The previously described, sequential assignment of the means of transport Vi has the characteristic property that "allocated" time intervals may no longer be changed, for example shifted. This can result in a relatively large waste in the occupancy schedule BP, because free time intervals which are only slightly too small to be occupied by a means of transport Vi not yet taken into account in the occupancy plan BP are not used.
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.The further development of the method, which is described in the following, additionally improves the method with regard to this problem, in which it is permitted that already planned time intervals may still be shifted to a certain extent. A possibly specified time safety distance between two means of transport Vi on part TLNj of the line network LN is initially reduced 20 in the development of this method (see FIG. 2). The method V is now carried out completely taking into account the reduced safety distance.
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.Due to the safety margin being too small, the resulting occupancy plan BP is inconsistent. In order to make it consistent again, time intervals are shifted. For this purpose, 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.
In einem davor durchgeführten Schritt 21 wird der Sicher¬ heitsabstand wieder auf den vor der Reduzierung festgesetzten Wert zurückgesetzt.In a step 21 carried out beforehand, the safety distance is reset to the value fixed before the reduction.
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.Now 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.
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.The result is a consistent and optimal occupancy plan, optimal provided that the route for each means of transport Vi and the sequence of the means of transport Vi for each edge have already been optimally determined.
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.In a last step, 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.
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.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.
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.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.
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.The following parameters are used for the nodes v and the edges 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.
Folgende Parameter werden für die Knoten v und die Kanten e verwendet:The following parameters are used for nodes v and edges e:
- time(v): aktueller Zeitwert des Knotens v, beispielsweiεe in Sekunden;time (v): current time value of node v, for example in seconds;
- mintime(v) : untere Schranke für den Zeitwert deε Knotens v, beispielεweiεe in Sekunden;- mintime (v): lower bound for the time value of the node v, for example in seconds;
- movable(v) : Angabe, ob der Zeitwert, der dem Knoten v zuge¬ ordnet ist, geändert werden darf oder nicht;movable (v): Specification as to whether or not the time value assigned to node v may be changed;
- 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.- cost (e): 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.
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.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.
Desweiteren dürfen Zeitintervalle, die in der Vergangenheit liegen, nicht verschoben werden.Furthermore, time intervals that lie in the past must not be shifted.
Die Kanten deε Verεchiebungsgraphen vg werden auf folgende Weise generiert:The edges of the displacement graph vg are generated in the following way:
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: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:
- ein folgendes Zeitintervall gn(z), das dem Zeitintervall z in dem Liniennetz LN direkt folgt;- A following time interval gn (z) which directly follows the time interval z in the line network LN;
- 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.- Another following time interval zn (z), which describes the time interval directly following the time interval z in the specified travel times of the means of transport Vi, and a previous time interval zp (z) which describes the time interval directly preceding the time interval z in the specified travel times of the Represents means of transport Vi.
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.If an edge e has a conflict edge, then the conflict interval belonging to the time interval z is designated kiz. The minimum distance between two time intervals which are assigned to the same edge e but different means of transport Vi net, for example a safety distance, is denoted by zs.
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.In each case, 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. Furthermore, va (z) denotes the node in the shift graph vg which represents the respective start of the time interval z.
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.Furthermore, 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.
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) .Different cases are listed below when generating the new edges. In each case it is indicated how the 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. For example, 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).
Ohne Elimination dieser Knoten würde man einfach eine Kante von va(kiz) nach va(gn(kiz)) generieren, was in Gleichung (2) dargestellt ist.Without eliminating these nodes, one would simply generate an edge from va (kiz) to va (gn (kiz)), which is shown in equation (2).
u = va(z) und t = va(zn(z) ) (1)u = va (z) and t = va (zn (z)) (1)
Hierbei gilt cost(u, t) = tedgeHere, cost (u, t) = tedge applies
u = va(z) und t = va(gn(z) ) (2)u = va (z) and t = va (gn (z)) (2)
Hierbei gilt coεt(u, t) = tedge + tlen + zsHere 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) and t = va (z) (3) kir = gn (r) Here, cost (u, t) = tedge + tlen + zε applies
u = va(z) und t = va(gn(kiz)) (4)u = va (z) and t = va (gn (kiz)) (4)
Hierbei gilt coεt(u, t) = tedge + tlen + zεHere coεt (u, t) = tedge + tlen + zε
u = va(z) und t = va(r) (5)u = va (z) and t = va (r) (5)
Eε gilt kir = gn(kiz)Eε applies kir = gn (kiz)
Hierbei gilt coεt(u, t) = tedge + tlen + zεHere coεt (u, t) = tedge + tlen + zε
u = va(z) und t = va(gn(zp(z) ) ) (6)u = va (z) and t = va (gn (zp (z))) (6)
Hierbei gilt coεt(u, t) = tlen + zsHere coεt (u, t) = tlen + zs applies
u = va(z) und t = va(r) (7)u = va (z) and t = va (r) (7)
Es gilt kir = gn(zp(z)) Hierbei gilt cost(u, t) = tlen + zεKir = gn (zp (z)) applies. Here, cost (u, t) = tlen + zε applies
u = va(z) und t = gn(kizp(z) ) (8)u = va (z) and t = gn (kizp (z)) (8)
Hierbei gilt cost(u, t) = + tlen + zsHere, cost (u, t) = + tlen + zs applies
u = va(z) und t - va(r) (9)u = va (z) and t - va (r) (9)
Es gilt kir = gn(kizp(z)) Hierbei gilt cost(u, t) = tlen + zsKir = gn (kizp (z)) applies. Here, cost (u, t) = tlen + zs applies
Ein Index r bezeichnet jeweils ein weiteres Zeitintervall un- gleich dem jeweiligen Zeitintervall z.An index r denotes a further time interval not equal to the respective time interval 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 denA 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
Gleichungen (6), (7), (8) und (9), indem man u = va(z) durch u = va(zn(z)) ersetzt.Equations (6), (7), (8) and (9) by replacing u = va (z) with u = va (zn (z)).
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.To illustrate this in the procedure described above, 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.
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.5a and 5b for the respective topology of a second exemplary embodiment in FIGS. 5a and 5b, 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.
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.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 .
Die bekannten Verfahren würden, wie in Figur 6a dargestellt, keine Umdisponierung des einzelnen Verkehrεmittels vornehmen, da kein Konflikt vorliegt.As shown in FIG. 6a, the known methods would not reschedule the individual means of transport since there is no conflict.
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.Through the method according to the invention, however, an entire regeneration of the occupancy plan BP is carried out without a conflict detection being necessary for this. , This leads to that as shown in Figure 6b, the resulting Zeitlük- ke is used to t'12 that the fourth transport to have V4 drive with a lower priority in this time interval t'12 aur a narrowing Ver the line network LN, oh ¬ ne to influence the predetermined travel times of the means of transport V2 and V3. This leads to a global improvement in overall driving behavior. The method can be carried out, for example, at periodic time intervals, the size of which varies depending on the application, or also at irregular time intervals.
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.In a further development of the method it is also provided that 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.
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.In this context, a fault is understood to mean, for example, a case when a part TLNj of the line network LN fails or is blocked. In this case, a new occupancy plan BP can be determined taking into account the reported malfunctions.
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ß.Furthermore, provision is made to take 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.
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: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):
- Art des Verkehrsmittelε (Vi) , - Gewicht deε Verkehrsmittels (Vi) ,- type of means of transport (Vi), - weight of means of transport (Vi),
- Länge deε Verkehrεmittels (Vi),- length of the means of transport (Vi),
- Höchstgeschwindigkeit des Verkehrsmittelε (Vi),- maximum speed of the means of transport (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,- predetermined stops of the means of transport (Vi) on the route, - minimum stay of the means of transport (Vi) at the predetermined stops, - earliest possible departure time of the means of transport (Vi) from the predetermined stops,
- topologiεche Nebenbedingungen der einzelnen Teile deε Lini¬ ennetzes (LN) .- Topological constraints of the individual parts of the line network (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.In the possible case that not only one possible order of the means of transport Vi is prescribed on the line network LN, but several, it is provided to plan all possible order sequences for the means of transport Vi, that is to say for to carry out each possible order sequence for the method and stores the result of a target function, which describes, for example, a weighted sum of determined delays in the means of transport Vi.
Eine optimale Auftragsreihenfolge ist diejenige, die von al¬ len möglichen Auftragsreihenfolgen den geringεten Wert in der Zielfunktion aufweist.An optimal order sequence is that which has the lowest value in the target function of all possible order sequences.
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.Depending on the area of application and the focal points of the optimization, 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.
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.To further improve the method, it is possible in each case to save only the result value of the target function when the method is carried out for every possible order sequence and not all parameters for the respective assignment. In this case, after the optimal order sequence has been found, the procedure must be carried out again for this order sequence. This procedure has considerable advantages with regard to the use of the memory requirement of the computer performing the process. The method of "trying out" all possible order sequences can be further developed by limiting the possibilities to be tried out.
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:For the sake of clarity, an assumption is made that exactly f orders are to be scheduled and g orders have already been scheduled. In this case, the following lower bound can be specified for the target function value that is obtained after the planning of the remaining o = f - g orders:
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.The remaining orders o are planned individually, taking into account the already planned orders g. In the following, 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.
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.Furthermore, 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.
Der im vorigen beschriebene Branch-and-Bound-Algorithmus kann mit Hilfe zweier Parameter beεchleunigt werden: - Eine Branch-Schranke bs.The branch-and-bound algorithm described above can be accelerated using two parameters: - A branch barrier 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.If g orders have already been processed in the exact process, then exactly o orders were then available for selection for further planning. With the branch barrier bs, which is smaller than the total number of orders f, the number of orders that are available for selection is limited to the value of the branch barrier bs.
- Ein Streckungsfaktor sf.- A stretch factor 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.With this option, 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 stretching factor sf is staggered, in proportion to the number of orders o still to be scheduled. The following applies: sf = 1 for 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.The method according to the invention and all the further developments of the method described above can be used for different fields of application.
So ist es zum Beispiel vorgesehen, wie im vorigen beschrieben wurde, daε Verfahren für schienengebundene Verkehrεmittel Vi einzuεetzen.For example, as described in the previous section, it is intended to use methods for rail-bound means of transport Vi.
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.It is also provided to use the method for regulating aircraft. In this case, 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.
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.Another area of application of the method is in the disposition of collective stops. Here, 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.
Das Verfahren kann außerdem vorteilhaft verwendet werden zur Erstellung von Sollfahrplänen für die Verkehrsmittel Vi.The method can also be used advantageously to create target timetables for the means of transport 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. In general, 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.

Claims

Patentansprüche claims
1. Verfahren zur Regelung von Verkehrsmitteln (Vi; i = 1 - m) ,1. Procedure for regulating means of transport (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,in which the means of transport (Vi) with predetermined arrival times and predetermined departure times of the means of transport (Vi) and predetermined sequences of starting and destination points of the means of transport (Vi) are represented in a line network (LN) in the form of an undirected network graph,
- 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- in which an occupancy plan (BP), in which free time intervals of the occupancy plan (BP) are represented in the form of an interval graph (IG), through the parts of the line network (TLNj; j = 1 - n) certain means of transport at certain time intervals ( Vi) are assigned, generated by a computer, in that all means of transport (Vi) sequentially according to selectable priorities of the means of transport (Vi) and the sequences of start and destination points of the means of transport (Vi) are those of the means of transport (Vi ) required parts (TLNj) of the line network (LN) are assigned, where
-- 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,- nodes of the interval graph (IG) are assigned time intervals in which the corresponding part (TLNj) of the line network (LN) is not yet occupied, - edges of the interval graph (IG) take possible routes for the means of transport (Vi) into account local and time restrictions, which result from at least the topology of the route network and the predefined arrival and departure times of the means of transport (Vi),
-- 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- An optimal route in the interval graph (IG) is assigned (05) to the respective means of transport (Vi) using a shortest path algorithm (Shortest Path Algorithm), - Free time intervals of the individual parts (TLNj) of the Line network (LN) can be adapted (06) to the occupancy of the Line network (LN) through the respective means of transport (Vi), and
- bei dem die Verkehrsmittel entsprechend den Anforderungen des Belegungεplanε (BP) geregelt werden (08) .- in which the means of transport are regulated in accordance with the requirements of the occupancy plan (BP) (08).
2. Verfahren nach Anspruch 1, bei dem ein alter Belegungsplan (BP') zu Beginn des Verfahrens vollständig gelöscht (02) wird.2. The method according to claim 1, in which an old occupancy plan (BP ') is completely deleted (02) at the beginning of the method.
3. Verfahren nach Anspruch 1 oder 2,3. The method according to claim 1 or 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.- in the case of received reported disturbances via the line network (LN) and / or via the means of transport (Vi) and / or other disturbances which influence the flow of traffic, and - in which the occupancy plan (BP) is then new is generated taking into account the received interference.
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.4. The method according to any one of claims 1 to 3, in which occurring conflicts in the occupancy plan (BP) are resolved by waiting times which are assigned to the means of transport with a comparatively lower priority.
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.5. The method according to any one of claims 1 to 4, in which a Dijkεtra Algorithmuε is provided as the shortest path method (short path algorithm).
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.6. The method according to any one of claims 1 to 4, in which a Moore Algorithmuε is provided as the shortest path method (short path algorithm).
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 :7. The method according to any one of claims 1 to 6, in which the priorities of the means of transport (Vi) are determined according to at least one of the following criteria:
- eine vorgebbare Bedeutung der einzelnen Verkehrsmittel (Vi),- a definable meaning of the individual means of transport (Vi),
- Geschwindigkeiten der einzelnen Verkehrsmittel (Vi) , - vorgegebene Abfahrtszeiten der einzelnen Verkehrsmittel (Vi),- speeds of the individual means of transport (Vi), - predefined departure times for the individual means of transport (Vi),
- vorgegebene Ankunftszeiten der einzelnen Verkehrsmittel (Vi), - Verspätungen der nach den einzelnen Verkehrεmittel (Vi) .- predefined arrival times of the individual means of transport (Vi), - delays of the individual means of transport (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.8. The method according to one of claims 1 to 7, in which connection conditions of the means of transport (Vi) are taken into account when generating the occupancy plan (BP).
9. Verfahren nach einem der Anprüche 1 bis 8,9. Method according to one of claims 1 to 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),- in which, at the beginning of the method, a predetermined safety distance of the means of transport (Vi) is reduced (20) to at least a part (TLNj) of the line network (LN), - in which the reduced safety distance increases again after completion of the method (V) the specified safety distance (21),
- bei dem ein Verschiebegraph (vg) generiert wird (22),- in which a displacement graph (vg) is generated (22),
- bei dem der Verschiebegraph (vg) dekompaktiert wird (23), - bei dem der Verschiebegraph (vg) kompaktiert wird (24) , und- in which the displacement graph (vg) is decompacted (23), - in which the displacement graph (vg) is compacted (24), and
- bei dem der Belegungsplan (BP) entsprechend des kompaktier- ten Verschiebegraphens (vg) angepaßt wird.- in which the occupancy plan (BP) is adjusted according to the compacted shift graph (vg).
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, und10. The method according to any one of claims 1 to 9, - in which, if different sequences of the means of transport (Vi) in the line network (LN) are possible, the method is carried out for at least two possible sequences, and
- bei dem die Regelung der Reihenfolge als eine optimale Re- gelung verwendet wird, die für eine vorgebbare Zielfunktion einen optimalen Wert ergibt.- in which the regulation of the sequence is used as an optimal regulation which results in an optimal value for a predefinable objective function.
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. 11. The method according to claim 10, in which a branch-and-bound method for reducing the number of sequences of the means of transport to be examined is provided in the line network (LN).
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) .12. Method according to one of claims 1 to 11, in which the regulation of the means of transport (Vi) takes place by regulating the stopping times of the means of transport (Vi) at stops of the line network (LN) and / or by regulating the speeds of the means of transport (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.13. The method according to any one of claims 1 to 12, in which a possible Gleischchεelbetrieb is taken into account when generating the occupancy plan (BP).
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) ,14. Method according to one of claims 1 to 13, in which at least one of the following secondary conditions is taken into account when generating the occupancy plan (BP): type of means of transport (Vi),
- Gewicht des Verkehrεmittels (Vi) ,- weight of the means of transport (Vi),
- Länge des Verkehrsmittels (Vi) ,- length of transport (Vi),
- Höchstgeschwindigkeit des Verkehrsmittelε (Vi) ,- maximum speed of the means of transport (Vi),
- vorgegebene Haltestellen des Verkehrεmittels (Vi) auf der Route,predetermined stops of the means of transport (Vi) on the route,
- Mindestaufenthaltszeit des Verkehrsmittelε (Vi) an den vor¬ gegebenen Halteεtellen,- Minimum stay of the means of transport (Vi) at the given stops,
- früheεtmögliehe Abfahrtszeit des Verkehrsmittels (Vi) von den vorgegebenen Haltestellen, - topologische Nebenbedingungen der einzelnen Teile des Lini¬ ennetzes (LN) .- early departure time of the means of transport (Vi) from the predetermined stops, - topological secondary conditions of the individual parts of the line network (LN).
15. Verfahren nach einem der Ansprüche 1 bis 13,15. The method according to any one of claims 1 to 13,
- bei dem daε Verfahren eingeεetzt wird zur Regelung der Ver- kehrεmittel (Vi) an einem Sammelhaltepunkt mehrerer Ver¬ kehrεmi11e1, und- The method is used to regulate the means of transport (Vi) at a collective stopping point of several means of transport, and
- bei dem zu Beginn des Verfahrens die Verkehrsmittel (Vi) beεtimmten vorgegebenen Teilen deε Liniennetzes (LN) zuge¬ ordnet werden.- With which the means of transport (Vi) predetermined parts of the line network (LN) are assigned at the beginning of the method.
16. Verfahren nach einem der Ansprüche 1 bis 13, - bei dem das Verfahren eingesetzt wird zu Regelung von Flug¬ zeugen, und16. The method according to any one of claims 1 to 13, - In which the method is used to control aircraft, and
- bei dem die Teile (TLNj) des Liniennetzes (LN) durch Luft¬ korridore, die jeweils eindeutig in einem Zeitintervall den einzelnen Flugzeugen zugeordnet werden.- In which the parts (TLNj) of the line network (LN) by air corridors, each of which is clearly assigned to the individual aircraft in a time interval.
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) . 17. The method according to any one of claims 1 to 13, in which the occupancy plan (BP) is used to create target timetables for the means of transport (Vi).
PCT/DE1996/001498 1995-09-07 1996-08-08 Transport means control process WO1997009218A2 (en)

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 (en) 1997-03-13
WO1997009218A3 WO1997009218A3 (en) 1997-04-10

Family

ID=7771550

Family Applications (1)

Application Number Title Priority Date Filing Date
PCT/DE1996/001498 WO1997009218A2 (en) 1995-09-07 1996-08-08 Transport means control process

Country Status (3)

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

Cited By (9)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
EP0933280A2 (en) * 1998-01-26 1999-08-04 Alcatel Process for resolution of time conflicts in a transport network and processing arrangement therefore
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 (en) * 2007-09-27 2009-04-09 Siemens Aktiengesellschaft Method for creating timetables for transportation systems taking into account time limits
FR2955954A1 (en) * 2010-02-04 2011-08-05 Ineo Systrans SERVICE MANAGEMENT SYSTEM

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 (en) * 1992-06-23 1993-12-24 Mitsubishi Electric Corp System for control of railway traffic - uses details of train itinerary and time tables together with decision rules to aid preparation of route diagram

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 (en) * 1992-06-23 1993-12-24 Mitsubishi Electric Corp System for control of railway traffic - uses details of train itinerary and time tables together with decision rules to aid preparation of route diagram

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 (en) * 1998-01-26 1999-08-04 Alcatel Process for resolution of time conflicts in a transport network and processing arrangement therefore
EP0933280A3 (en) * 1998-01-26 2002-05-15 Alcatel Process for resolution of time conflicts in a transport network and processing arrangement therefore
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 (en) * 2007-09-27 2009-04-09 Siemens Aktiengesellschaft Method for creating timetables for transportation systems taking into account time limits
FR2955954A1 (en) * 2010-02-04 2011-08-05 Ineo Systrans SERVICE MANAGEMENT SYSTEM

Also Published As

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

Similar Documents

Publication Publication Date Title
DE60001915T2 (en) DYNAMIC TRANSPORT ALGORITHM
DE69814276T2 (en) Computer-based conflict resolution procedure for the railway network
DE69514444T2 (en) Procedure for scheduling sequential tasks with time constraints
DE102009024130B4 (en) Method for real-time capable path planning of continuous, jerk-free setpoint trajectories
EP1293948B1 (en) Method and device to optimize route plans on line networks
DE69206917T2 (en) Auxiliary procedures for the development of a group of communicating machines
DE19910311A1 (en) Automation system with reusable automation objects and process for reusing automation solutions in engineering tools
WO1997009218A2 (en) Transport means control process
DE3839675C2 (en) Optimizer for a parameter-dependent control system
EP2161698B1 (en) Method for coordinating light signal-controlled nodes in a street network
DE4409179A1 (en) System and method for dynamic information processing
WO1997009217A2 (en) Control process for track-bound vehicles
EP3937151A1 (en) Device and method for controlling a traffic flow in a traffic network by means of an optimal signal phase plan
EP0671027B1 (en) Process for defining the application-dependent logic of a freely programmable sequential logic system, device for implementing this process and device for operating a control system using a program thus defined
DE102023001698A1 (en) Method for an automated generation of data for raster map-based prediction approaches
DE19510343C2 (en) Process for sequential feedforward control of a process
DE4403037A1 (en) Process for operating a route network
EP0859988B1 (en) Method for the computerized allocation of resources to vehicles travelling over a predetermined section
EP1500567B1 (en) Method for resolving conflicts in a trackbound transportation system
DE102013020582A1 (en) Method for computer-aided replication of a production plant, method for commissioning a production plant, configuration device and production plant
EP0796779B1 (en) Method for the control and the safety of a guided transport system
EP0284605B1 (en) Software tool for automatic production of a logical function diagram
DE3784189T2 (en) DEVICE AND METHOD FOR CONTROLLING THE ERASE OF A STORAGE AREA.
WO2022254009A1 (en) Method for generating a control program for an automation system, and programming tool
EP3991161A1 (en) Method for controlling a traffic system, device, computer program, and computer-readable storage medium

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