EP0933280A2 - Procédé de résolution des conflits de table horaire d'un réseau de transport et agencement de traitement correspondant - Google Patents

Procédé de résolution des conflits de table horaire d'un réseau de transport et agencement de traitement correspondant Download PDF

Info

Publication number
EP0933280A2
EP0933280A2 EP98403116A EP98403116A EP0933280A2 EP 0933280 A2 EP0933280 A2 EP 0933280A2 EP 98403116 A EP98403116 A EP 98403116A EP 98403116 A EP98403116 A EP 98403116A EP 0933280 A2 EP0933280 A2 EP 0933280A2
Authority
EP
European Patent Office
Prior art keywords
time table
level
corrected
conflicting
solution
Prior art date
Legal status (The legal status 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 status listed.)
Withdrawn
Application number
EP98403116A
Other languages
German (de)
English (en)
Other versions
EP0933280A3 (fr
Inventor
Stéphane Betge Brezetz
Serge Benoliel
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
Alcatel Lucent SAS
Nokia Inc
Original Assignee
Alcatel SA
Nokia Inc
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 Alcatel SA, Nokia Inc filed Critical Alcatel SA
Publication of EP0933280A2 publication Critical patent/EP0933280A2/fr
Publication of EP0933280A3 publication Critical patent/EP0933280A3/fr
Withdrawn legal-status Critical Current

Links

Images

Classifications

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

Definitions

  • the invention relates to a computer method for ensuring resolution, at level of a time table, conflicts that are likely to occur in a transport network, in particular in a rail-type transport network.
  • Such a method and such an arrangement are intended to be implemented in networks where the successions of operations relating to the transport to be carried out, such than planned in a given environment, with given material means and in a given time frame, are more particularly synthesized under the form of time tables. They are especially designed to be able to be used with different network configurations and to allow implementation of different heuristics.
  • Some of these known methods exploit for example an approach of the type decision tree and take into account a cost function, corresponding by example to a weighted sum of delays, others take into account a set of rules, for example in the context of an expert system, or a specific heuristic for reordering.
  • the invention therefore proposes a computer resolution method, at the level of a timetable, conflicts of a transport network, in particular of the type rail, which is managed through an IT system and which includes lines, tracks and / or roads, connecting stations between which vehicles circulate whose movements are organized according to a table of data, constituting the time table.
  • This is stored at a system level data processing and where the different movements of vehicles scheduled between stations for a specified period of time, with information characteristic of these movements, such as the different possible journeys between stations and the expected transit times at the stations.
  • tolerances in particular are associated with the corrected time table frame and are taken into account account when establishing a non-conflicting time table from this corrected time table frame.
  • the method further provides for minus a step of applying an optimization algorithm, possibly repeated, with different optimization criteria to produce at least one other non-conflicting time table from a determined time table, via a corrected time table frame, and possibly to produce at least one other table frame corrected from this determined time table.
  • the method provides that the implementation application of the non-conflicting hourly table obtained is at least partially achieved by action of the data processing set, where is implemented the process, at the IT unit level by through which the transport network is managed.
  • the various stages, carried out according to a decision tree and with the possible intervention of an operator, are memorized through each of the command sets respectively exploited for the transition from a non-conflicting time table to another table non-conflicting timetable in a possible chain of corrected table frames and non-conflicting time tables established from a starting situation conflictual memorized in a specific way, to allow a journey in both directions of the decision tree and a re-identification of the situation of departure.
  • the invention also proposes an arrangement for processing table conflicts. timetable in a network by applying the process mentioned above, in part of an associated or possibly included data processing system in a network management computer system.
  • the schematic representation illustrated in Figure 1 relates to a small part time table relating to a portion of railway line L supposed to connect three stations 1, 2 and 3 by a single channel as illustrated in figure 2, channel L is dividing in half at each station where two platforms are provided, such as A1 and B1 for station 1, A2 and B2 for station 2, A3 and B3 for station 3.
  • the track divisions made at each station allow two trains to cross or overtake, when one of the trains is stopped at this station.
  • train T1 is assumed come to a stop along a platform, for example A1 at station 1, at a instant t1 and until instant t3 from which it sets out on the path for a non-stop route to station 3, via station 2.
  • Train T3 is supposed to come to a stop at station 3, at time t2, until an instant t5 from which he sets off on the track for a journey without stopping to station 2. It is expected by the time table that it will arrive at station 2 at a instant t6, for example along platform A2, before train T1 running in opposite direction does not pass along platform B2.
  • Train T2 is expected to come come to a stop along one of the platforms of station 1, for example platform B1, at a instant t7 until instant t8 from which he too commits to a non-stop route to station 3.
  • the table predicts that the T2 train will pass by station 2, during the time during which train T3 is immobilized in this station.
  • Train T2 then passes along platform B2 if, as expected higher, train T3 is immobilized along platform A2. It is provided by the table that train T3 leaves for station 1 at time t9, that train T1 arrives at the station 3 at an instant t10 to stop along a platform, for example the platform A3, and train T2 arrives at station 3 at time t11.
  • the resolution process does not only apply to simple conflicts such as the one mentioned above. It is more particularly intended to intervene within the framework of networks and in particular mesh networks, where are likely develop conflict situations involving a number of parameters and / or an interaction of these parameters which practically prohibit the use a resolution procedure other than IT. It is expected that the process according to the invention is implemented by means of an arrangement provided for level of an associated or possibly included data processing system in the IT system by which the transport network is managed by the personnel responsible for ensuring its operation and management in particular. The exact structures of the data processing system and the whole network management IT is not developed here, as far as they have only an indirect relationship with the subject of the invention.
  • this system and this set are conventionally constituted by means of units programmed logic, organized around processors, memories and various interfaces allowing the units to communicate with each other and on the other hand with at least some of the equipment of the transport network and at least some of the network's operating personnel, via man-machine type for this staff.
  • These communications may take very diverse forms and are used in particular for ordering purposes equipment, transmission of activity reports, exchange of information between units and / or between units and operating personnel.
  • the computer resolution method according to the invention involves a representation, in a hierarchical form, of the transport network to which it is intended to be applied. This representation is here assumed to be stored at the level of data processing system where the resolution method is implemented.
  • the network is assumed to include a plurality of lines, tracks and / or roads, which connect stations between which vehicles circulate, these can be airplanes or boats in the case of air or maritime networks, in the example of a rail network envisaged here these vehicles are made up of trains or train components, such as power cars when they circulate in isolation. Vehicle movements are organized according to a time table, here assumed to be stored as a data table at data center level.
  • a computer process is planned to ensure automatic resolution conflicts likely to arise in a network, these conflicts being represented at the level of a time table where the different displacements of vehicles that are scheduled between stations in a network for a period of time determined.
  • This time table contains characteristic information relating to journeys, such as for example journeys between stations and expected transit times at stations. At least some of data stored in the time table and therefore by the processing system data can in particular be entered at the level of this system by the operating personnel. They are also likely to come from units, including equipment-machine and / or man-machine interface, the network management IT system.
  • a first level of modeling is used to express a set of traffic management constraints at the network level or higher precisely of its infrastructure. This is represented by the stations and by the lines or paths connecting these stations.
  • a rail network we designates by places the stations and the depots of rolling stock and by inter-places the network elements which are provided between the places.
  • the movements of vehicles are defined as missions.
  • a mission for a vehicle contains information specifying the places where it passes and the timetables of arrival, departure and passage for each place passed.
  • a second level of modeling is intended to express a set of constraints relating to the topology of lines and their equipment, such as for example the number and the arrangement of the passageways comprised by a line, the equipment in lights or other signaling devices on this line.
  • the constraints taken into account at the second level also concern the quays and service routes, as well that the journeys or successions of parts of the journey that the vehicles are likely to borrow.
  • Each vehicle movement is defined by a path, that is to say by the succession of paths or portions of path, that it will borrow and by the arrival, departure and / or passage times at the different places along the way to go for a given route.
  • the search for a solution to a time table conflict is triggered in the event of non-compliance with the constraints defined at the level of the transport, modeled on two levels according to the indications given above.
  • This triggering takes place following the reception of information inducing time table modification requests from all IT for network management and / or operating staff.
  • an application to the modeled network of the time table, where these requests are taken into account is then automatically launched and it triggers a search for a solution in the event of non-compliance, by the time table applied, of constraints defined at the level of the modeled network.
  • the search for a solution according to the invention essentially comprises two stages, repeated if necessary, to arrive at an optimized solution, that is to say a non-conflictual table, even to an optimal solution chosen from several possible non-conflicting tables.
  • the first step in finding a solution involves implementing a first optimization algorithm to modify the time table considered as conflictual.
  • the purpose of this first algorithm is to produce a draft solution, known as the corrected timetable table, which is in correspond to the functional level constraints defined for the network transport.
  • This research step is carried out on the basis of a first heuristic.
  • the research aims to allow to move from the conflict situation, noted at the level of a part of the table hourly, to at least one first corrected time table frame, for which are defined tolerances within which at least one complete solution is wanted.
  • tolerances are in particular tolerances with regard to passage time or parking and / or distance between vehicles on the same lane.
  • the data processing system automatically triggers a search step to obtain a solution complete, corresponding to a non-conflicting time table, from the frame corrected time table that was found.
  • This step is done by application of a second optimization algorithm taking as input the table frame corrected timetable and taking into account the constraints specific to the modeled network which relate to the topology of the lines and their equipment.
  • the data taken into account at the level of a subset 6 correspond in particular the departure and arrival times for the vehicles concerned on the portion of the route concerned, as well as the planned connections, for example the planned connections for the benefit of passengers and any couplings between vehicles at the seating level.
  • Mission definition data include, for example, departure, crossing and arrival times as well as the expected speeds for a given vehicle on a given route.
  • Restrictions correspond for example to any speed limits linked to work carried out along a route.
  • the search is therefore carried out step by step and can, depending on the case, make it possible to define either a corrected solution framework, or possibly several, when this can be envisaged in particular in terms of processing time.
  • the first step of applying the optimization algorithm taking into account the constraints defined at the functional level of the network, is repeated. This allows a selection of a non-conflicting time table, considered optimal, among several possible tables respectively obtained from competing corrected solution frameworks.
  • the resolution method according to the invention is implemented as part of a decision tree.
  • Storage of information defining the chain of solutions leading from the time table where a conflict situation with the non-conflict solution is noted, complete and ultimately retained, is carried out specifically at the level of data processing system.
  • a specific storage is planned data, relating to the part of the time table where a conflict is noted, of so that we can find the conflicting conditions which are generally transient.
  • the portion of railway line L serving stations 1, 2, 3 is a two-track line normally operated each in a different direction, which therefore allow a maximum flow of vehicles determined. If, as a result of an incident, one of the channels is no longer available between stations 1 and 2 and that the other channel must be used to ensure all traffic in both directions, it is no longer possible to obtain the same maximum flow level between these stations and vehicle traffic between stations 2 and 3 may be affected.
  • the data processing system is informed of such an incident, either by a unit of the IT group of management of the transport network which is responsible for supervising one of the equipment lane affected by the incident and for example the equipment out of order, by a member of the network operator who is informed of this incident.
  • the information received is here taken into account by the processing system. data to the extent that it may affect vehicle traffic at the level of the network for vehicles passing through the portion of line L.
  • a search for a solution, via the conflict resolution arrangement is then automatically launched by the duly programmed data processing system.
  • This should allow to establish a corrected timetable table framework which will define for example the number of trains in each direction that it is possible to maintain on the line portion L using the one of the two channels which remained exploitable. Tolerances here are assumed to be associated with the corrected time table frame for set the limits for alternating vehicles during the period during which it is estimated that the unavailability of one of the routes of the portion L will remain.
  • a search for complete solution can be initiated in order to obtain a non-conflicting table, adapted to the new conditions brought about by the unavailability of one of the tracks of the portion of line L, taking into account the constraints related to the network topology.
  • a table will a priori contain modifications train schedule and possibly route changes.
  • the data processing system sends the information necessary for the implementation of this table by equipment, particularly track, which is affected. To this end, these information is sent to the units of the IT management unit which control the equipment concerned and the operating personnel concerned. At least some of the information is likely to be taken into account by this personnel for information, supervision and / or execution.
  • the method is implemented in the context a schedule table conflict handling arrangement which is provided in which is shown schematically in Figure 4. As already indicated this arrangement is assumed performed at the level of a data processing system associated or included in the IT system for managing the transport network in question.
  • This software-type arrangement essentially comprises a unit of resolution 10 including a solution determination module 11, intended for search for a solution framework, i.e. a timetable corrected, by applying a first optimization algorithm to the network realized at functional level.
  • This determination module 11 is here provided to be able to be used with different heuristics for frame search corrected solution, here assumed grouped in a heuristic subset 15 where two of these heuristics are shown diagrammatically with references 12 and 13. These heuristics are provided here in order to be able to be used during stages of determination made as part of the same resolution operation for offer different options for solution selection.
  • the module determination is here supposed to have possibilities of creation and elimination which allow it respectively to generate new displacements for vehicles and delete them.
  • the resolution unit 10 also includes a refined search module 16 capable of provide at least one non-conflicting time table corresponding to a solution complete from a corrected solution framework developed by the module determination 11.
  • This refined research module 16 is responsible for ensuring the application of an optimization algorithm to the network model carried out at topological level. It is also designed to be able to be operated with different non-conflicting timetable search heuristics which are schematized with the references 17 and 18 in a sub-assembly referenced 19 in FIG. 4.
  • the search module 16 is here supposed to have possibilities of modification of timetable and modifiable constraints, in particular to allow compliance with the tolerances imposed by the determination module for a frame of determined solution. It receives as input a framework of solution corrected from of which it provides at least one solution for the part of the time table previously in conflict after having possibly carried out modifications as stated above using the strategy and at least one of the heuristics planned for him.
  • the determination 11 and refined search modules 16 of the resolution 10 communicate with each other, as shown schematically in Figure 4 and with a decision tree module 20.
  • This tree allows them to use the same algorithm for exploring solutions with the different heuristics that these two modules are likely to accept.
  • the decision tree module 20 provides the treatments relating to the tree structure and provides the latter, from nodes and connections stored online with the progress of the steps conflict resolution method according to the invention.
  • a solution manager module 21 is associated with the resolution unit 10 for memorize the time table solutions that this resolution unit provides to the during a research stage triggered from a time table conflictual and to allow the entire IT network management and accredited operating personnel to communicate with the processing via an interface 22.
  • FIG. 5 The operating principle of the resolution unit of the layout conflict treatment according to the invention is shown diagrammatically in FIG. 5.
  • This layout is implemented from a conflict situation affecting a timetable of the transport network for which it is implemented.
  • the disturbance P of the time table which leads to a conflict situation is transmitted to the determination module 11 responsible for establishing the solution frameworks corrected online with a conflict detection mechanism at the level functional, the information of which is symbolized by the letter F, and with a corrected solution framework evaluation mechanism, the information of which is symbolized by the letter E.
  • This is done according to the parameters of command referenced C and requests referenced R coming from the set IT for network management and / or an accredited operator, via the interface 22 not shown in this figure 5.
  • Each product solution framework is transmitted by the determination module 11 to the refined research module 16 in order to obtain a complete and non-conflicting solution with the assistance of a conflict detection mechanism of occupation of service lines and tracks, the information of which is symbolized by the letter O, and a complete solution evaluation mechanism, whose information is symbolized by the letter V.
  • the refined search module 16 is capable of reacting in a loop on the determination module 11, when a satisfactory complete solution is not found, so as to allow a new stage within the framework of an operation time table conflict resolution, in order to obtain a solution framework different from the one that did not succeed.
  • This module provides the information relating to the complete solutions found, via interface 22, for information and control by an accredited operator and for application to means, not shown, which are responsible for applying the non-conflict solution at the level of the network equipment concerned, via the whole IT management of this network.
  • the automatic implementation of the method according to the invention allows to quickly reach a solution in real time conditions.

Landscapes

  • Engineering & Computer Science (AREA)
  • Mechanical Engineering (AREA)
  • Traffic Control Systems (AREA)
  • Management, Administration, Business Operations System, And Electronic Commerce (AREA)
  • Train Traffic Observation, Control, And Security (AREA)

Abstract

Le procédé prévoit notamment les étapes suivantes :
  • modélisation du réseau de transport à deux niveaux, l'un fonctionnel où est exprimé un ensemble de contraintes relatives aux flux de véhicules entre les stations et l'autre topologique où est exprimé un ensemble de contraintes relatives à la topologie des lignes, voies et/ou routes, et à leur équipement ;
  • application d'un algorithme d'optimisation pour produire un cadre de table corrigée éliminant les conflits d'une table horaire conflictuelle, au niveau fonctionnel ;
  • application d'un algorithme d'optimisation prenant comme entrée le cadre de table corrigée et produisant une table non-conflictuelle en tenant compte des contraintes topologiques ;
  • mise en application de la table horaire non-conflictuelle obtenue.
L'agencement comporte un module de détermination de cadre de solution (11) et un module de recherche de solution complète (16) associés à un module gestionnaire de solutions (21) et un module d'arbre de décision.

Description

L'invention concerne un procédé informatique destiné à assurer la résolution, au niveau d'une table horaire, des conflits qui sont susceptibles d'intervenir dans un réseau de transport, en particulier dans un réseau de transport de type ferroviaire.
Elle concerne aussi un agencement de traitement conçu pour permettre la mise en oeuvre de ce procédé.
Un tel procédé et un tel agencement sont destinés à être mis en oeuvre dans les réseaux où les successions d'opérations relatives aux transports à réaliser, telles que planifiées dans un environnement donné, avec des moyens matériels donnés et dans un cadre temporel donné, sont plus particulièrement synthétisées sous la forme de tables horaires. Ils sont notamment prévus pour pouvoir être exploités avec différentes configurations de réseau et pour permettre la mise en oeuvre d'heuristiques différentes.
Les procédés et agencements connus ont généralement été conçus au cas par cas pour des réseaux déterminés, en tenant compte des particularités propres à ces réseaux ce qui les rend peu transportables du réseau pour lequel ils ont été conçus à un réseau différent.
Certains de ces procédés connus exploitent par exemple une approche de type arbre de décision et prennent en compte une fonction de coût, correspondant par exemple à une somme pondérée de retards, d'autres prennent en compte un ensemble de règles, par exemple dans le cadre d'un système expert, ou d'une heuristique spécifique de remise en ordre.
De plus ils exploitent souvent une représentation linéaire des réseaux fondée sur les infrastructures réelles des réseaux pris en compte. Ceci peut conduire à l'apparition de problèmes de convergence dans le cas d'événements graves conduisant à une exigence de traitements d'un nombre élevé de conflits de manière pratiquement simultanée.
Il existe aussi des procédés exploitant une approche de type programme de satisfaction de contraintes qui sont utilisés pour modifier les horaires des trains dans le cas de réseaux de transport ferroviaire. Toutefois ces procédés ne sont pas pleinement satisfaisants en matière de résolution des conflits de tables horaires dans la mesure où ils ne sont pas prévus pour assurer des changements d'itinéraires en plus des changements d'horaires en cas de conflits. Leur adaptation en vue d'offrir ces possibilités de changement d'itinéraire conduit à l'utilisation de temps prohibitifs de traitement des données.
L'invention propose donc un procédé de résolution informatique, au niveau d'une table horaire, des conflits d'un réseau de transport, notamment de type ferroviaire, qui est géré par l'intermédiaire d'un ensemble informatique et qui comporte des lignes, voies et/ou routes, reliant des stations entre lesquelles circulent des véhicules dont les déplacements sont organisés selon une table de données, constituant la table horaire. Celle-ci est stockée au niveau d'un système de traitement de données et où sont répertoriés les différents déplacements de véhicules prévus entre les stations pour une période de temps déterminée, avec des informations caractéristiques de ces déplacements, tels que les différents trajets possibles entre les stations et les temps de passage prévus au niveau des stations.
Selon une caractéristique de l'invention, le procédé prévoit la réalisation des étapes suivantes par le système de traitement de données :
  • modélisation du réseau de transport selon une hiérarchie à deux niveaux ;
  • un niveau, dit fonctionnel, où est exprimé un ensemble de contraintes qui sont relatives aux flux de véhicules entre les stations du réseau ;
  • un niveau, hiérarchiquement inférieur et dit topologique, où est exprimé un ensemble de contraintes relatives à la topologie des lignes, voies et/ou routes, et à leur équipement ;
  • déclenchement automatique d'une recherche de solution, en cas de réception par le système de traitement de données d'une information, susceptible de conduire à une modification de table horaire, en provenance de l'ensemble informatique de gestion du réseau et/ou d'un exploitant accrédité;
  • application d'un algorithme d'optimisation à la table horaire afin de produire un cadre de table horaire corrigée éliminant les conflits correspondant aux contraintes du niveau fonctionnel ;
  • application d'un second algorithme d'optimisation prenant comme entrée le cadre de table horaire corrigée et produisant une table horaire non-conflictuelle tenant compte des contraintes du niveau topologique ;
  • mise en application de la table horaire non-conflictuelle obtenue en tenant compte des contraintes du niveau fonctionnel et du niveau topologique, lorsque les contraintes sont respectées.
Selon une autre caractéristique de l'invention, des tolérances, notamment temporelles, sont associées au cadre de table horaire corrigée et sont prises en compte lors de l'établissement d'une table horaire non-conflictuelle à partir de ce cadre de table horaire corrigée.
Selon une autre caractéristique de l'invention, le procédé prévoit de plus au moins une étape d'application d'algorithme d'optimisation, éventuellement réitérée, avec des critères d'optimisation différents pour produire au moins une autre table horaire non-conflictuelle à partir d'une table horaire déterminée, via un cadre de table horaire corrigée, et éventuellement pour produire au moins un autre cadre de table corrigée à partir de cette table horaire déterminée.
Selon une autre caractéristique de l'invention, le procédé prévoit que la mise en application de la table horaire non-conflictuelle obtenue est au moins partiellement réalisée par action de l'ensemble de traitement de données, où est mis en oeuvre le procédé, au niveau de l'ensemble informatique par l'intermédiaire duquel le réseau de transport est géré.
Selon une autre caractéristique de l'invention, les diverses étapes, réalisées selon un arbre de décision et avec intervention éventuelle d'un exploitant, sont mémorisées par l'intermédiaire de chacun des jeux de commande respectivement exploités pour le passage d'une table horaire non-conflictuelle à une autre table horaire non-conflictuelle dans une éventuelle chaíne de cadres de table corrigées et de tables horaires non-conflictuelles établis à partir d'une situation de départ conflictuelle mémorisée de manière spécifique, afin de permettre un parcours dans les deux sens de l'arbre de décision et une ré-identification de la situation de départ.
L'invention propose aussi un agencement de traitement des conflits de table horaire dans un réseau par mise en application du procédé évoqué ci-dessus, dans le cadre d'un système de traitement de données associé ou éventuellement inclus dans un ensemble informatique de gestion du réseau.
Selon une caractéristique de l'invention, cet agencement comporte :
  • une unité de résolution comportant au moins un module de détermination de solution pour procéder à des recherches de cadre de table horaire corrigée selon une heuristique de recherche choisie par application d'un algorithme d'optimisation à un modèle de réseau réalisé à un niveau hiérarchique dit fonctionnel en vue de fournir un cadre de table horaire corrigée à partir d'une table horaire conflictuelle et un module de recherche de solution complète qui procède à des recherches de table horaire non-conflictuelle selon une heuristique de raffinement choisie par application d'un algorithme d'optimisation à un modèle de réseau réalisé à un niveau, dit topologique hiérarchiquement inférieur au précédent, à partir d'un cadre de table horaire corrigée fourni par le module de détermination en vue d'obtenir une table horaire non-conflictuelle, optimisée, respectant les contraintes de niveau fonctionnel et topologique et les tolérances associées au cadre de table horaire corrigée dont elle découle;
  • un module d'arbre de décision permettant aux modules de détermination et de recherche de solutions de l'unité de résolution d'exploiter un même algorithme d'exploration des solutions avec des stratégies différentes selon les heuristiques exploitées;
  • un module gestionnaire de solutions exploité pour un stockage des solutions obtenues aux différentes étapes d'obtention d'une table horaire non-conflictuelle optimale à partir d'une situation conflictuelle relative à une table horaire déterminée et pour une restitution des solutions en fonction des besoins de l'unité de résolution et de l'exploitant;
  • une interface de communication avec l'ensemble informatique de gestion du réseau de transport et avec le personnel exploitant.
L'invention, ses caractéristiques et ses avantages sont précisés dans la description qui suit en liaison avec les figures évoquées ci-dessous.
  • La figure 1 est une représentation schématique relative à un exemple simple de table horaire pour une ligne ferroviaire schématisée en figure 2.
  • La figure 2 est une représentation schématique d'une ligne ferroviaire.
  • La figure 3 présente un schéma de définition d'un exemple de cadre de solution.
  • La figure 4 présente un schéma synoptique d'un agencement de traitement pour la mise en oeuvre du procédé de résolution selon l'invention.
  • La figure 5 présente un schéma de principe relatif au fonctionnement de l'unité de résolution d'un agencement de traitement selon l'invention.
    • La représentation schématique illustrée en figure 1 est relative à une petite partie de table horaire relative à une portion de ligne ferroviaire L supposée relier trois stations 1, 2 et 3 par une voie unique comme illustré sur la figure 2, la voie L se divisant en deux au niveau de chaque station où deux quais sont ménagés, tels A1 et B1 pour la station 1, A2 et B2 pour la station 2, A3 et B3 pour la station 3. Les divisions de voie réalisées dans chaque station permettent à deux trains de se croiser ou de se dépasser, lorsque l'un des trains est à l'arrêt dans cette station.
    La situation illustrée en figure 1 est supposée impliquer trois trains T1, T2, T3 simultanément présents sur la ligne ferroviaire L au cours d'un même laps de temps. Selon une table horaire prévue pour ces trains, le train T1 est supposé venir s'immobiliser au long d'un quai, par exemple A1 de la station 1, à un instant t1 et jusqu'à un instant t3 à partir duquel il s'engage sur la voie pour un parcours sans arrêt jusqu'à la station 3, via la station 2.
    Le train T3 est supposé venir s'immobiliser à la station 3, à un instant t2, jusqu'à un instant t5 à partir duquel il s'engage sur la voie pour un parcours sans arrêt vers la station 2. Il est prévu par la table horaire qu'il arrive à la station 2 à un instant t6, par exemple au long du quai A2, avant que le train T1 circulant en sens inverse ne passe au long du quai B2. Le train T2 est supposé venir s'immobiliser au long d'un des quais de la station 1, par exemple le quai B1, à un instant t7 jusqu'à un instant t8 à partir duquel il s'engage lui aussi pour un parcours sans arrêt jusqu'à la station 3. La table prévoit que le train T2 passe par la station 2, pendant le laps de temps au cours duquel le train T3 est immobilisé dans cette station. Le train T2 passe alors au long du quai B2 si, comme prévu plus haut, le train T3 est immobilisé au long du quai A2. Il est prévu par la table que le train T3 reparte vers la station 1 à un instant t9, que le train T1 arrive à la station 3 à un instant t10 pour s'immobiliser au long d'un quai, par exemple le quai A3, et que le train T2 arrive à la station 3 à un instant t11.
    Il est ici envisagé un retard du train T1 au départ de la station 1, par exemple jusqu'à un instant t4, compris entre t3 et t5, sur le diagramme de type espace/temps de la figure 1 où ledit retard est symbolisé en trait épais. Ce retard conduit à une situation conflictuelle dans la mesure où le train T2 plus rapide que le train T1 va rattraper ce dernier entre les stations 2 et 3, comme le montre le croisement du tracé en pointillé correspondant au train T1 retardé avec le tracé en trait continu correspondant au train T2. Ce dernier ne sera plus susceptible d'arriver à la station 3 à l'instant t11 initialement prévu pour lui par la table.
    Bien entendu, le procédé de résolution ne s'applique pas qu'aux conflits simples tels que celui évoqué ci-dessus. Il est plus particulièrement prévu pour intervenir dans le cadre de réseaux et notamment de réseaux maillés, où sont susceptibles de développer des situations conflictuelles impliquant un nombre de paramètres et/ou une interaction de ces paramètres qui interdisent pratiquement l'emploi d'une procédure de résolution autre qu'informatique. Il est prévu que le procédé selon l'invention est mis en oeuvre par l'intermédiaire d'un agencement prévu au niveau d'un système de traitement de données associé ou éventuellement inclus dans l'ensemble informatique au moyen duquel le réseau de transport est géré par le personnel chargé d'en assurer notamment le fonctionnement et la gestion. Les structures exactes du système de traitement de données et de l'ensemble informatique de gestion du réseau ne sont pas développées ici, dans la mesure où elles n'ont qu'un rapport indirect avec l'objet de l'invention. Comme il est connu ce système et cet ensemble sont classiquement constitués au moyen d'unités logiques programmées, organisées autour de processeurs, de mémoires et d'interfaces diverses permettant aux unités de communiquer d'une part entre elles et d'autre part avec au moins certains des équipements du réseau de transport et au moins une partie du personnel d'exploitation du réseau, via des interfaces de type homme-machine pour ce personnel. Ces communications peuvent prendre des formes très diverses et sont notamment utilisées à des fins de commande d'équipement, de transmission de compte-rendu d'activités, d'échange d'informations entre unités et/ou entre unités et personnel exploitant.
    Le procédé de résolution informatique selon l'invention implique une représentation, sous forme hiérarchisée, du réseau de transport auquel il est destiné à être appliqué. Cette représentation est ici supposée stockée au niveau du système de traitement de données où le procédé de résolution est mis en oeuvre.
    Le réseau est supposé comporter une pluralité de lignes, voies et/ou routes, qui relient des stations entre lesquelles circulent des véhicules, ceux-ci peuvent être des avions ou des bateaux dans le cas de réseaux aériens ou maritimes, dans l'exemple de réseau ferroviaire envisagé ici ces véhicules sont constitués par des trains ou des éléments de train, telles que notamment les motrices lorsqu'elles circulent isolément. Les déplacements des véhicules sont organisés selon une table horaire, ici supposée stockée sous la forme d'une table de données au niveau du centre de traitement de données.
    Il est prévu un procédé informatique visant à assurer une résolution automatique des conflits susceptibles de survenir dans un réseau, ces conflits étant représentés au niveau d'une table horaire où sont répertoriés les différents déplacements de véhicules qui sont prévus entre les stations d'un réseau pour une période de temps déterminée. Cette table horaire contient des informations caractéristiques relatives aux déplacements, tels que par exemple les trajets entre les stations et les temps de passage prévus au niveau des stations. Au moins certaines des données stockées dans la table horaire et donc par le système de traitement de données peuvent notamment être introduites au niveau de ce système par le personnel exploitant. Elles sont également susceptibles de parvenir d'unités, notamment dotées d'interface équipement-machine et/ou homme-machine, de l'ensemble informatique de gestion du réseau.
    Il est prévu de réaliser une modélisation du réseau de transport, à deux niveaux hiérarchiquement différents, préalablement à toute tentative de résolution de conflit.
    Un premier niveau de modélisation, dit fonctionnel, est exploité pour exprimer un ensemble de contraintes de gestion de trafic au niveau du réseau ou plus précisément de son infrastructure. Celle-ci est représentée par les stations et par les lignes ou trajets reliant ces stations. Dans le cas d'un réseau ferroviaire on désigne par places les stations et les dépôts de matériel roulant et par inter-places les éléments de réseau qui sont prévus entre les places. Les mouvements des véhicules sont définis en tant que missions. Une mission pour un véhicule comporte des informations précisant les places où il passe et les horaires d'arrivée, de départ et de passage pour chaque place passée.
    Les contraintes de gestion de trafic qui sont prises en compte, sont ici supposées relatives aux flux de véhicules entre stations, étant entendu que chaque station ne peut accepter qu'un flux maximal déterminé de véhicules entrants et/ou sortants par une portion de ligne la reliant directement à une autre station.
    Un second niveau de modélisation, dit topologique et hiérarchiquement inférieur au premier, est prévu pour exprimer un ensemble de contraintes relatives à la topologie des lignes et à leur équipement, tels que par exemple le nombre et la disposition des voies de passage comportées par une ligne, l'équipement en feux ou autres dispositifs de signalisation de cette ligne.
    Dans le cas d'un réseau ferroviaire tel que défini ci-dessus, les contraintes prises en compte au second niveau concernent aussi les quais et voies de service, ainsi que les trajets ou successions de portions de trajet que les véhicules sont susceptibles d'emprunter. Chaque mouvement de véhicule est défini par un chemin, c'est-à-dire par la succession de trajets ou portions de trajet, qu'il va emprunter et par les horaires d'arrivée, de départ et/ou de passage au différentes places de passage au long du chemin à parcourir pour un trajet donné.
    Selon l'invention, la recherche d'une solution à un conflit de table horaire est déclenchée en cas de non respect des contraintes définies au niveau du réseau de transport, modélisé à deux niveaux selon les indications données ci-dessus.
    Ce déclenchement s'effectue suite à la réception d'informations induisant des demandes de modification de table horaire, en provenance de l'ensemble informatique de gestion du réseau et/ou du personnel exploitant. Selon une forme préférée de réalisation, une application au réseau modélisé de la table horaire, où sont prises en compte ces demandes, est alors automatiquement lancée et elle déclenche une recherche de solution en cas de non-respect, par la table horaire appliquée, de contraintes définies au niveau du réseau modélisé.
    La recherche de solution selon l'invention comporte essentiellement deux étapes, réitérées si besoin est, pour arriver à une solution optimisée, c'est-à-dire à une table non-conflictuelle, voire à une solution optimale choisie parmi plusieurs tables non-conflictuelles possibles.
    La première étape de recherche de solution implique la mise en oeuvre d'un premier algorithme d'optimisation pour modifier la table horaire considérée comme conflictuelle. Ce premier algorithme a pour objet de produire une ébauche de solution, dite cadre de table horaire corrigée, qui soit en correspondance avec les contraintes de niveau fonctionnel définies pour le réseau de transport. Cette étape de recherche est effectuée sur la base d'une première heuristique. Dans une forme préférée de réalisation, la recherche vise à permettre de passer de la situation conflictuelle, constatée au niveau d'une partie de table horaire, à au moins une premier cadre de table horaire corrigée, pour lequel sont définies des tolérances à l'intérieur desquelles au moins une solution complète est recherchée.
    Ces tolérances sont notamment des tolérances en matière de temps de passage ou de stationnement et/ou de distance entre véhicules sur une même voie.
    Si cette première étape de recherche est infructueuse, une nouvelle étape de recherche est automatiquement répétée, à l'aide d'un autre algorithme d'optimisation correspondant à une heuristique de recherche différente, pour tenter de trouver un premier cadre de table horaire corrigée.
    Lorsqu'un tel cadre de table est obtenu, le système de traitement de données déclenche automatiquement une étape de recherche en vue d'obtenir une solution complète, correspondant à une table horaire non-conflictuelle, à partir du cadre de table horaire corrigée qui a été trouvé. Cette étape s'effectue par application d'un second algorithme d'optimisation prenant comme entrée le cadre de table horaire corrigée et tenant compte des contraintes propres au réseau modélisé qui sont relatives à la topologie des lignes et à leur équipement.
    Dans la réalisation envisagée, l'ensemble des données correspondant à une solution est supposé résumé par un cadre de solution corrigée 4, tel que schématisé sur la figure 3. Ce cadre regroupe une table de temps hiérarchisée 5 où sont rassemblés :
    • un sous-ensemble 6 de données relatives à un cadre de solution corrigé obtenu en respectant les contraintes définies pour le réseau modélisé au niveau fonctionnel;
    • une table de tolérances 8 regroupant les données relatives aux tolérances admises pour le cadre de solution corrigée défini;
    • un sous-ensemble 7 de données, dites de second niveau, qui sont relatives à une table horaire non-conflictuelle obtenue à partir du cadre de solution corrigée, en tenant compte des contraintes définies pour le réseau modélisé au niveau topologique.
    Les données prises en compte au niveau d'un sous-ensemble 6 correspondent notamment aux heures de départ et d'arrivée pour les véhicules concernés sur la portion de trajet concernée, ainsi que les connexions prévues, par exemple les correspondances prévues au profit des passagers et les éventuels couplages entre véhicules au niveau des places.
    Les données prises en compte au niveau d'un sous-ensemble 7 correspondent notamment aux données de définition de mission et aux éventuelles restrictions susceptibles d'intervenir pour une mission. Les données de définition de mission comprennent par exemple les heures de départ, de passage et d'arrivée ainsi que les vitesses prévues pour un véhicule donné sur un trajet donné. Les restrictions correspondent par exemple aux éventuelles limitations de vitesse liées aux travaux effectués au long d'un trajet.
    La recherche s'effectue donc pas à pas et peut, suivant les cas, permettre de définir soit un cadre de solution corrigée, soit éventuellement plusieurs, lorsque ceci est envisageable notamment en matière de temps de traitement.
    La répétition des étapes de recherche en vue d'obtenir une table horaire non-conflictuelle optimale est susceptible d'être réalisée soit à partir d'un même cadre de solution corrigée, soit à partir de cadres de solution corrigée différents.
    Dans ce dernier cas, la première étape d'application d'algorithme d'optimisation, tenant compte des contraintes définies au niveau fonctionnel du réseau, est répétée. Ceci permet une sélection d'une table horaire non-conflictuelle, considérée comme optimale, parmi plusieurs tables possibles respectivement obtenues à partir de cadres de solution corrigée concurrents.
    Ces répétitions qui sont susceptibles d'être réalisées, tant pour la première étape en vue de trouver des cadres de table horaire corrigée différents que pour la seconde étape en vue de trouver des tables horaires non-conflictuelles différentes. Elles sont réalisées en mettant en oeuvre des algorithmes d'optimisation différents, prévus de manière connue par l'homme de métier en ce domaine, pour permettre à l'exploitant de sélectionner la solution optimisée à appliquer en fonction de critères différents, par exemple en fonction de critères de coût, de temps, de régularité, etc.
    Dans une forme préférée de réalisation, le procédé de résolution selon l'invention est mis en oeuvre dans le cadre d'un arbre de décision. Le stockage des informations qui définissent la chaíne de solutions conduisant de la table horaire où est constatée une situation conflictuelle à la solution non-conflictuelle, complète et finalement retenue, est effectué de manière spécifique au niveau du système de traitement de données. Il est prévu une mise en mémoire spécifique des données, relatives à la partie de table horaire où un conflit est constaté, de manière à pouvoir retrouver les conditions conflictuelles qui sont généralement transitoires. Il est aussi prévu une mémorisation du jeu de commandes correspondant aux solutions obtenues au cours des différentes étapes de mise en oeuvre du procédé, à la fin desquelles une table horaire non-conflictuelle est retenue. Ceci permet à l'exploitant de parcourir l'arbre de décision correspondant dans les deux sens, en particulier pour revenir à une solution intermédiaire, à partir d'une solution qui lui est postérieure, en phase de recherche, par une inversion du jeu de commandes ayant conduit de l'une à l'autre. Une réduction notable du volume de données à stocker est ainsi obtenue, puisque seul est nécessaire le stockage des données relatives aux commandes effectuées, à partir d'une partie de table horaire conflictuelle spécifiquement mémorisée, pour parvenir à une solution optimale correspondant à une partie de table horaire équivalente, non-conflictuelle.
    A titre d'exemple, il est supposé ici que la portion de ligne ferroviaire L desservant les stations 1, 2, 3 est une ligne à deux voies normalement exploitées chacune dans un sens différent, qui permettent donc un flux maximal de véhicules déterminé. Si par suite d'un incident, l'une des voies n'est plus disponible entre les stations 1 et 2 et que l'autre voie doit être utilisée pour assurer l'ensemble du trafic dans les deux sens, il n'est plus possible d'obtenir le même niveau de flux maximal entre ces stations et le trafic de véhicules entre stations 2 et 3 risque d'en être affecté. Le système de traitement de données est informé d'un tel incident, soit par une unité de l'ensemble informatique de gestion du réseau de transport qui est chargée de superviser un des équipements de voie affecté par l'incident et par exemple l'équipement en panne, soit encore par un membre du personnel exploitant du réseau qui est informé de cet incident.
    L'information reçue est ici prise en compte par le système de traitement de données dans la mesure où elle risque d'affecter le trafic des véhicules au niveau du réseau pour les véhicules qui transitent par la portion de ligne L.
    Un déclenchement d'une recherche de solution, par l'intermédiaire de l'agencement de résolution de conflits, est alors automatiquement lancé par le système de traitement de données dûment programmé. Ceci doit permettre d'établir un cadre de table horaire corrigée qui définira par exemple le nombre de trains dans chaque sens qu'il est possible de faire subsister sur la portion de ligne L en utilisant celle des deux voies qui est restée exploitable. Des tolérances temporelles sont ici supposées associées au cadre de table horaire corrigée pour fixer les limites de passage des véhicules en alternance au cours de la période pendant laquelle il est estimé que l'indisponibilité d'une des voies de la portion de liaison L va subsister.
    A partir du moment où un cadre de solution a été trouvé, une recherche de solution complète peut être initiée en vue d'obtenir une table non conflictuelle, adaptée aux nouvelles conditions entraínées par l'indisponibilité de l'une des voies de la portion de ligne L, en tenant compte des contraintes liées à la topologie du réseau. Une telle table va a priori contenir des modifications d'horaire de trains et éventuellement des changements de trajet. Lorsque la table non-conflictuelle à appliquer a été déterminée dans le cadre de temps imparti pour l'obtention de cette table, le système de traitement de données envoie les informations nécessaires à la mise en application de cette table par les équipements, notamment de voie, qui sont concernés. A cet effet, ces informations sont envoyées aux unités de l'ensemble informatique de gestion qui contrôlent les équipements concernés et au personnel exploitant concerné. Au moins certaines des informations sont susceptibles d'être prises en compte par ce personnel pour information, supervision et/ou exécution.
    Dans une forme préférée de réalisation, le procédé est mis en oeuvre dans le cadre d'un agencement de traitement de conflits de table horaire qui est prévu dans qui est schématisé sur la figure 4. Comme déjà indiqué cet agencement est supposé réalisé au niveau d'un système de traitement de données associé ou inclus dans l'ensemble informatique de gestion du réseau de transport considéré.
    Cet agencement, de type logiciel, comporte essentiellement une unité de résolution 10 incluant un module de détermination de solution 11, destiné à procéder aux recherches de cadre de solution, c'est-à-dire de table horaire corrigée, par application d'un premier algorithme d'optimisation au modèle de réseau réalisé au niveau fonctionnel. Ce module de détermination 11 est ici prévu pour pouvoir être exploité avec différentes heuristiques de recherche de cadre de solution corrigée, ici supposées regroupées dans un sous-ensemble heuristique 15 où deux de ces heuristiques sont schématisées avec les références 12 et 13. Ces heuristiques sont ici prévues pour pouvoir être exploitées au cours d'étapes de détermination réalisées dans le cadre d'une même opération de résolution pour offrir différentes possibilités de sélection de solution. Le module de détermination est ici supposé disposer de possibilités de création et d'élimination qui lui permettent respectivement d'engendrer de nouveaux déplacements pour des véhicules ainsi que d'en supprimer. Il est aussi prévu qu'il dispose de possibilités de création, modification et/ou suppression de contraintes modifiables. Il permet d'assurer les modifications les plus importantes, telles qu'indiquées ci-dessus, en utilisant la stratégie et au moins l'une des heuristiques prévues pour lui, et ceci usuellement sous la supervision d'un exploitant accrédité. Il reçoit en entrée les données relatives à une partie de table horaire conflictuelle et doit fournir un cadre de solution corrigée correspondant à une partie de table horaire modifiée, accompagnée de tolérances.
    L'unité de résolution 10 comporte aussi un module de recherche affinée 16 apte à fournir au moins une table horaire non-conflictuelle correspondant à une solution complète à partir d'un cadre de solution corrigée élaboré par le module de détermination 11. Ce module de recherche affinée 16 est chargé d'assurer l'application d'un algorithme d'optimisation au modèle de réseau réalisé au niveau topologique. Il est aussi prévu pour pouvoir être exploité avec différentes heuristiques de recherche de table horaire non-conflictuelle qui sont schématisées avec les références 17 et 18 dans un sous-ensemble référencé 19 de la figure 4.
    Le module de recherche 16 est ici supposé disposer de possibilités de modification d'horaire et de contraintes modifiables, notamment pour permettre un respect des tolérances imposées par le module de détermination pour un cadre de solution déterminé. Il reçoit en entrée un cadre de solution corrigée à partir duquel il fournit au moins une solution pour la partie de table horaire précédemment conflictuelle après avoir éventuellement effectué des modifications telles qu'indiquées ci-dessus en utilisant la stratégie et au moins l'une des heuristiques prévues pour lui.
    Les modules de détermination 11 et de recherche affinée 16 de l'unité de résolution 10 communiquent entre eux, comme schématisé sur la figure 4 et avec un module d'arbre de décision 20. Cet arbre leur permet d'exploiter un même algorithme d'exploration des solutions avec les différentes heuristiques que ces deux modules sont susceptibles d'accepter. Le module d'arbre de décision 20 assure les traitements relatifs à la structure d'arbre et fournit ce dernier, à partir des noeuds et branchements stockés en ligne avec le déroulement des étapes du procédé de résolution de conflit selon l'invention.
    Un module gestionnaire de solutions 21 est associé à l'unité de résolution 10 pour mémoriser les solutions de table horaire que fournit cette unité de résolution au cours d'une étape de recherche déclenchée à partir d'une table horaire conflictuelle et pour permettre à l'ensemble informatique de gestion du réseau et au personnel exploitant accrédité de communiquer avec l'agencement de traitement par l'intermédiaire d'une interface 22.
    Ceci permet notamment à l'ensemble de gestion du réseau de transport et plus particulièrement à un exploitant accrédité d'être informé sur le déroulement des étapes de recherche et d'agir éventuellement sur l'agencement. Ces actions se traduisent, par exemple par une sélection d'heuristique à mettre en oeuvre et par le choix d'une solution optimale parmi plusieurs solutions non-conflictuelles optimisées, lorsque les conditions notamment en matière de délai rendent ceci possible.
    Le principe de fonctionnement de l'unité de résolution de l'agencement de traitement de conflits selon l'invention est schématisé sur la figure 5. Cet agencement est mis en oeuvre à partir d'une situation conflictuelle affectant une table horaire du réseau de transport pour lequel il est mis en oeuvre. La perturbation P de table horaire qui amène à une situation conflictuelle est transmise au module de détermination 11 chargé d'établir les cadres de solution corrigée en ligne avec un mécanisme de détection de conflit au niveau fonctionnel, dont les informations sont symbolisées par la lettre F, et avec un mécanisme d'évaluation de cadre de solution corrigée, dont les informations sont symbolisées par la lettre E. Ceci s'effectue en fonction des paramètres de commande référencés C et des demandes référencées R provenant de l'ensemble informatique de gestion du réseau et/ou d'un exploitant accrédité, via l'interface 22 non représentée sur cette figure 5.
    Chaque cadre de solution produit est transmis par le module de détermination 11 au module de recherche affinée 16 en vue d'obtenir une solution complète et non-conflictuelle avec l'assistance d'un mécanisme de détection de conflits d'occupation des lignes et voies de service, dont les informations sont symbolisées par la lettre O, et d'un mécanisme d'évaluation de solution complète, dont les informations sont symbolisées par la lettre V.
    Le module de recherche affinée 16 est susceptible de réagir en boucle sur le module de détermination 11, lorsqu'une solution complète satisfaisante n'est pas trouvée, de manière à permettre une nouvelle étape dans le cadre d'une opération de résolution de conflit de table horaire, en vue d'obtenir un cadre de solution différent de celui qui n'a pas permis d'aboutir. Ce module fournit les informations relatives aux solutions complètes trouvées, via l'interface 22, à des fins d'information et de contrôle par un exploitant accrédité et pour application aux moyens, non représentés, qui sont chargés de l'application de la solution non-conflictuelle au niveau des équipements concernés du réseau, via l'ensemble informatique de gestion de ce réseau.
    La mise en oeuvre automatique du procédé selon l'invention, comme préférablement prévu, permet d'arriver rapidement à une solution dans des conditions de temps réel.

    Claims (6)

    1. Procédé de résolution informatique, au niveau d'une table horaire, des conflits intervenant dans un réseau de transport, notamment de type ferroviaire, géré par l'intermédiaire d'un ensemble informatique et comportant des lignes, voies et/ou routes, reliant des stations entre lesquelles circulent des véhicules dont les déplacements sont organisés selon une table de données, constituant la table horaire, qui est stockée au niveau d'un système de traitement de données et où sont répertoriés les différents déplacements de véhicules prévus entre les stations pour une période de temps déterminée, avec des informations caractéristiques de ces déplacements, tels que les différents trajets possibles entre les stations et les temps de passage prévus au niveau des stations, ledit procédé étant caractérisé en ce qu'il prévoit la réalisation des étapes suivantes par le système de traitement de données :
      modélisation du réseau de transport selon une hiérarchie à deux niveaux ;
      un niveau, dit fonctionnel, où est exprimé un ensemble de contraintes qui sont relatives aux flux de véhicules entre les stations du réseau ;
      un niveau, hiérarchiquement inférieur et dit topologique, où est exprimé un ensemble de contraintes relatives à la topologie des lignes, voies et/ou routes, et à leur équipement ;
      déclenchement automatique d'une recherche de solution, en cas de réception par le système de traitement de données d'une information, susceptible de conduire à une modification de table horaire, en provenance de l'ensemble informatique de gestion du réseau et/ou d'un exploitant accrédité;
      application d'un algorithme d'optimisation à la table horaire afin de produire un cadre de table horaire corrigée éliminant les conflits correspondant aux contraintes du niveau fonctionnel ;
      application d'un second algorithme d'optimisation prenant comme entrée le cadre de table horaire corrigée et produisant une table horaire non-conflictuelle tenant compte des contraintes du niveau topologique ;
      mise en application de la table horaire non-conflictuelle obtenue en tenant compte des contraintes du niveau fonctionnel et du niveau topologique, lorsque les contraintes sont respectées.
    2. Procédé selon la revendication 1, dans lequel des tolérances, notamment temporelles, sont associées au cadre de table horaire corrigée et sont prises en compte lors de l'établissement d'une table horaire non-conflictuelle à partir de ce cadre de table horaire corrigée.
    3. Procédé selon l'une des revendications 1, 2, dans lequel est prévu au moins une application d'algorithme d'optimisation avec des critères d'optimisation différents pour produire au moins une table horaire non-conflictuelle à partir d'une table horaire déterminée, via un cadre de table horaire corrigée, et éventuellement pour produire au moins un autre cadre de table horaire corrigée à partir de cette table horaire déterminée.
    4. Procédé selon l'une des revendications 1 à 4, dans lequel la mise en application de la table horaire non-conflictuelle obtenue est au moins partiellement réalisée par action de l'ensemble de traitement de données, où est mis en oeuvre le procédé, au niveau de l'ensemble informatique par l'intermédiaire duquel le réseau de transport est géré.
    5. Procédé selon l'une des revendications 1 à 3, dans lequel les diverses étapes, réalisées selon un arbre de décision et avec intervention éventuelle d'un exploitant, sont mémorisées par l'intermédiaire de chacun des jeux de commande respectivement exploités pour le passage d'une table horaire non-conflictuelle à une autre table horaire non-conflictuelle dans une éventuelle chaíne de cadres de table corrigées et de tables horaires non-conflictuelles établis à partir d'une situation de départ conflictuelle mémorisée de manière spécifique, afin de permettre un parcours dans les deux sens de l'arbre de décision et une ré-identification de la situation de départ.
    6. Agencement de traitement des conflits de table horaire dans un réseau de transport par mise en application du procédé selon l'une des revendications 1 à 5, réalisé dans le cadre d'un système de traitement de données associé ou éventuellement inclus dans un ensemble informatique de gestion du réseau, caractérisé en ce qu'il comporte :
      une unité de résolution (10) comportant au moins un module de détermination de solution (11) pour procéder à des recherches de cadre de table horaire corrigée selon une heuristique de recherche choisie (12, 13) par application d'un algorithme d'optimisation à un modèle de réseau réalisé à un niveau hiérarchique dit fonctionnel en vue de fournir un cadre de table horaire corrigée à partir d'une table horaire conflictuelle et un module de recherche de solution complète (16) qui procède à des recherches de table horaire non-conflictuelle selon une heuristique de raffinement choisie (17, 18) par application d'un algorithme d'optimisation à un modèle de réseau réalisé à un niveau, dit topologique hiérarchiquement inférieur au précédent, à partir d'un cadre de table horaire corrigée fourni par le module de détermination en vue d'obtenir une table horaire non-conflictuelle, optimisée, respectant les contraintes de niveau fonctionnel et topologique et les tolérances associées au cadre de table horaire corrigée dont elle découle;
      un module d'arbre de décision (20) permettant aux modules de détermination et de recherche de solutions de l'unité de résolution d'exploiter un même algorithme d'exploration des solutions avec des stratégies différentes selon les heuristiques exploitées;
      un module gestionnaire de solutions (21) exploité pour un stockage des solutions obtenues aux différentes étapes d'obtention d'une table horaire non-conflictuelle optimale à partir d'une situation conflictuelle relative à une table horaire déterminée et pour une restitution des solutions en fonction des besoins de l'unité de résolution et de l'exploitant;
      une interface (22) de communication avec l'ensemble ou le reste de l'ensemble informatique de gestion du réseau de transport et avec le personnel exploitant.
    EP98403116A 1998-01-26 1998-12-10 Procédé de résolution des conflits de table horaire d'un réseau de transport et agencement de traitement correspondant Withdrawn EP0933280A3 (fr)

    Applications Claiming Priority (2)

    Application Number Priority Date Filing Date Title
    FR9800767 1998-01-26
    FR9800767 1998-01-26

    Publications (2)

    Publication Number Publication Date
    EP0933280A2 true EP0933280A2 (fr) 1999-08-04
    EP0933280A3 EP0933280A3 (fr) 2002-05-15

    Family

    ID=9522133

    Family Applications (1)

    Application Number Title Priority Date Filing Date
    EP98403116A Withdrawn EP0933280A3 (fr) 1998-01-26 1998-12-10 Procédé de résolution des conflits de table horaire d'un réseau de transport et agencement de traitement correspondant

    Country Status (1)

    Country Link
    EP (1) EP0933280A3 (fr)

    Cited By (7)

    * Cited by examiner, † Cited by third party
    Publication number Priority date Publication date Assignee Title
    WO2001049549A1 (fr) * 1999-12-30 2001-07-12 Ge Harris Railway Electronics, L.L.C. Procede de planification pour couloir ferroviaire comprenant diverses fonctions de cout associees a des operations ferroviaires
    WO2001049547A1 (fr) * 1999-12-30 2001-07-12 Ge Harris Railway Electronics, L.L.C. Procede de programmation de couloir ferroviaire comprenant une fonction economique de programme, realisable et equilibre
    WO2009043770A1 (fr) * 2007-09-27 2009-04-09 Siemens Aktiengesellschaft Procédé d'établissement d'horaires de circulation de systèmes de transport avec prise en compte de limites temporelles
    CN102236828A (zh) * 2010-04-21 2011-11-09 北京交通大学 列车运行计划调整过程的建模方法
    WO2012038262A3 (fr) * 2010-09-20 2012-05-18 Siemens Aktiengesellschaft Procédé pour commander automatiquement une pluralité de véhicules guidés
    CN111814420A (zh) * 2020-06-18 2020-10-23 福州大学 基于拓扑优化和启发式搜索的总体布线方法
    CN112381277A (zh) * 2020-11-03 2021-02-19 北京交通大学 衔接多线路的方向别高速铁路枢纽站的到发线分配方法

    Family Cites Families (4)

    * Cited by examiner, † Cited by third party
    Publication number Priority date Publication date Assignee Title
    US4122523A (en) * 1976-12-17 1978-10-24 General Signal Corporation Route conflict analysis system for control of railroads
    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
    US5623413A (en) * 1994-09-01 1997-04-22 Harris Corporation Scheduling system and method
    WO1997009218A2 (fr) * 1995-09-07 1997-03-13 Siemens Aktiengesellschaft Procede de regulation de moyens de transport

    Cited By (12)

    * Cited by examiner, † Cited by third party
    Publication number Priority date Publication date Assignee Title
    WO2001049549A1 (fr) * 1999-12-30 2001-07-12 Ge Harris Railway Electronics, L.L.C. Procede de planification pour couloir ferroviaire comprenant diverses fonctions de cout associees a des operations ferroviaires
    WO2001049547A1 (fr) * 1999-12-30 2001-07-12 Ge Harris Railway Electronics, L.L.C. Procede de programmation de couloir ferroviaire comprenant une fonction economique de programme, realisable et equilibre
    US6304801B1 (en) 1999-12-30 2001-10-16 Ge-Harris Railway Electronics, L.L.C. Train corridor scheduling process including a balanced feasible schedule cost function
    US6546371B1 (en) 1999-12-30 2003-04-08 Ge-Harris Railway Electronics, L.L.C. Train corridor scheduling process including various cost functions associated with railway operations
    AU781542B2 (en) * 1999-12-30 2005-05-26 Ge Transportation Systems Global Signaling, Llc A train corridor scheduling process including a balanced feasible schedule cost function
    WO2009043770A1 (fr) * 2007-09-27 2009-04-09 Siemens Aktiengesellschaft Procédé d'établissement d'horaires de circulation de systèmes de transport avec prise en compte de limites temporelles
    CN102236828A (zh) * 2010-04-21 2011-11-09 北京交通大学 列车运行计划调整过程的建模方法
    WO2012038262A3 (fr) * 2010-09-20 2012-05-18 Siemens Aktiengesellschaft Procédé pour commander automatiquement une pluralité de véhicules guidés
    CN111814420A (zh) * 2020-06-18 2020-10-23 福州大学 基于拓扑优化和启发式搜索的总体布线方法
    CN111814420B (zh) * 2020-06-18 2022-07-08 福州大学 基于拓扑优化和启发式搜索的总体布线方法
    CN112381277A (zh) * 2020-11-03 2021-02-19 北京交通大学 衔接多线路的方向别高速铁路枢纽站的到发线分配方法
    CN112381277B (zh) * 2020-11-03 2023-09-26 北京交通大学 衔接多线路的方向别高速铁路枢纽站的到发线分配方法

    Also Published As

    Publication number Publication date
    EP0933280A3 (fr) 2002-05-15

    Similar Documents

    Publication Publication Date Title
    Wood Multiple temporalities of policy circulation: Gradual, repetitive and delayed processes of BRT adoption in South African cities
    Altazin et al. Rescheduling through stop-skipping in dense railway systems
    Dorfman et al. Scheduling trains on a railway network using a discrete event model of railway traffic
    EP0905003B1 (fr) Procédé de résolution de conflits dans un réseau ferroviaire à l'aide d'un moyen informatique
    MXPA02006579A (es) Modelo de actuacion de una estacion de ferrocarriles basado en modelaje de flujo de tareas.
    Canca et al. A rolling stock circulation model for railway rapid transit systems
    Van Den Broek Train Shunting and Service Scheduling: an integrated local search approach
    EP0933280A2 (fr) Procédé de résolution des conflits de table horaire d'un réseau de transport et agencement de traitement correspondant
    CA2526152A1 (fr) Procede de programmation et systeme de reseau ferroviaire
    Dixon et al. The 2019 deloitte city mobility index
    Lee et al. A smart city transportation system of systems governance framework: a case study of Singapore
    Umney et al. Designing frames: The use of precedents in parliamentary debate
    Xu et al. Solving a large‐scale multi‐depot vehicle scheduling problem in urban bus systems
    Abbink Crew management in passenger rail transport
    Dotoli et al. A real time traffic management model for regional railway networks under disturbances
    Salsingikar et al. Reinforcement learning for train movement planning at railway stations
    Bai et al. Optimization of Skip‐Stop Train Schedule in Urban Rail Transit Under Virtual Coupling
    Jiang et al. Scheduling additional train unit services on rail transit lines
    Kwan Co-ordination of joint headways
    Yi et al. Coordinated train rerouting and rescheduling in large infrastructures
    Polinder Resolving infeasibilities in the PESP model of the Dutch railway timetabling problem
    FR2663599A1 (fr) Systeme de transport automatique et rapide a trafic optimise.
    Artigues et al. Trains do not vanish: the ROADEF/EURO challenge 2014
    Kiciński Periodic Timetable Nonlinear Optimization in Public Transport Network
    Lorin et al. Transport digitalization: Business analytics results from Shift2Rail CONNECTIVE Project

    Legal Events

    Date Code Title Description
    PUAI Public reference made under article 153(3) epc to a published international application that has entered the european phase

    Free format text: ORIGINAL CODE: 0009012

    AK Designated contracting states

    Kind code of ref document: A2

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

    AX Request for extension of the european patent

    Free format text: AL;LT;LV;MK;RO;SI

    PUAL Search report despatched

    Free format text: ORIGINAL CODE: 0009013

    AK Designated contracting states

    Kind code of ref document: A3

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

    AX Request for extension of the european patent

    Free format text: AL;LT;LV;MK;RO;SI

    17P Request for examination filed

    Effective date: 20021115

    AKX Designation fees paid

    Designated state(s): AT DE ES FR GB

    STAA Information on the status of an ep patent application or granted ep patent

    Free format text: STATUS: THE APPLICATION IS DEEMED TO BE WITHDRAWN

    18D Application deemed to be withdrawn

    Effective date: 20060207