JP2818080B2 - Train diagram making method and device - Google Patents

Description

DETAILED DESCRIPTION OF THE INVENTION

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a method for creating a train diagram (hereinafter abbreviated as "train diagram"), and more particularly to an optimal solution for a complex problem such as a case where the number of trains to be planned is large and the constraints are large. And a method and apparatus for obtaining the same at extremely high speed.

[0002]

2. Description of the Related Art With the progress of social life such as the expansion and diversification of the living area of large cities, the role of mass transportation by electric railways has dramatically increased, and train schedules have become more safe and serve passengers. There is a demand for a highly viscous and meticulous response. In addition, with the development of public and industrial sectors, there is an urgent need for high-speed mass transit between major cities to achieve even higher speed, safety, and accurate and prompt response in the event of an abnormal event. In response to the above situation, the current main train equipment is
Since it was not built in anticipation of today's situation, it has become difficult to sufficiently respond to improvements in vehicle performance, increase in passengers, and the like. In particular, trying to achieve the full effect of improving the performance of the vehicle will sacrifice safety, so it will not be possible to exhibit sufficient performance, or conversely, in an emergency, safety will not be sacrificed. I can't say it. Avoid this situation,
In order to make a safe and high-speed operation plan, it is essential to arrange trains optimally in equipment for a limited time, that is, to create an optimal train schedule. When creating a train schedule, we do not simply arrange the lines indicating the train position and time at the station from the first train to the last train according to the transportation plan, but also the train performance required for train operation, the work schedule of crew,
It is necessary to consider various conditions such as the station track layout, the passenger getting on and off, the breakdown and repair schedule of each facility, the operation and characteristics of the automatic control device, etc. In addition, after satisfying the above conditions, it is necessary to determine the one that most satisfies the purpose of creating a train schedule. For example, when a train arrives and departs at 3-minute intervals and operates on a route that operates 16 hours a day, the number of trains to be planned is at least 320. A train schedule is created for each train while taking into account the various conditions described above. If the purpose of the plan is, for example, to minimize the time from departure of the first station of each train to arrival at the final station (hereinafter referred to as "travel time"), calculate the sum of travel times of all trains, The train schedule having the shortest sum may be found from all possible combinations. However, the number of possible combinations is enormous. For example, even if it is assumed that the assignment method of one train is determined in one way, the number of combinations of train assignments is 320! = 320 × 319 × 318 ×... × 3 × 2 × 1 >> ¹⁰³¹⁰ . Therefore, one diamond creation, ie, 320
If it takes 1 second to assign a train, 10 ³¹⁰ (seconds)
> 10 ³⁰⁵ (days)> 10 ³⁰⁰ (years) is the time to calculate all combinations. In reality, using the fastest computer you can imagine is practically impossible. On the other hand, for example, “Sapporo City Transportation Bureau Delivered Train Diagram Creation Support System” (Hitachi Review, Vol. 71, pp41)
As described in literatures such as 〜 46, August 1989), there has been proposed a method for creating a train diagram that can be put to practical use in a short time using empirical information and in cooperation with a planner.

[0003]

However, the knowledge engineering and the OR (operations research) method as described above are
It was not always a satisfactory technique in the following points. First, the optimal solution is not always obtained. Second, there is a lack of flexibility in changing the target problem. Third, the structure of the train timetable creation system is complicated and requires a huge number of manufacturing steps and cost. Fourth, a very long processing time is required. Each of the above problems will be briefly described below. Regarding the first point, it has conventionally been considered that there is only one method for finding one kind of optimal solution from among such a huge number of combinations. This is a method called “enumeration method” in which all order combinations are examined and evaluated to find an optimal solution. However, with this method, it is not possible to solve the problem in an acceptable and realistic time. On the other hand, stop considering all combinations, and based on empirical information,
Knowledge engineering, OR, etc. are researching to find a solution that does not have any problem even when actually used. Therefore, it can be said that the optimum solution is not always obtained. The second “lack of flexibility” is emphasized as the speed, the optimum, and the like are pursued in view of the characteristics inherent in knowledge engineering and the like. In other words, in an expert system based on knowledge engineering, a good planning system is a phenomenon that is unique to the target problem.
It is nothing but knowing in more detail.
Therefore, if the target is different or the target changes,
The system will not work at all. For example, train schedules that cannot be overtaken (hereinafter referred to as “parallel schedules”
) Is a train schedule that allows passing (this is
(Hereinafter referred to as "non-parallel diamond"). For example, an expert system for creating subway train schedules with overcrowded trains,
It is generally considered impossible to apply it to the creation of train schedules for high-speed mass transit routes. Regarding the third point,
As is clear from the second explanation, in order to create a good system, it is necessary to sufficiently study and investigate the target problem, and to express it requires a great deal of man-hour and cost. The fourth problem of low processing power occurs in the case of an expert system because it decreases as the amount of included knowledge increases.
Such a problem of the current technology is, for example, “FAreport
t, September 1992, Special Issue (Scheduling System) "and the like. Due to the many problems described above, it has been strongly desired to provide a train schedule creation system that can obtain a train schedule that is high-speed and that satisfies a desired purpose without being greatly affected by the subject in question. Therefore, an object of the present invention is to solve the above-mentioned problems and to provide a planning method and an apparatus capable of obtaining an optimal solution within an allowable finite time in creating a train schedule.

[0004]

In order to solve the above problems, the following means are conceivable. Stop stations of each of a plurality of trains which are the targets of the train schedule creation plan, desired departure time of each train, arrival time of each train, and running patterns corresponding to each train
No. of trains, stopping conditions indicating whether or not to stop at each station of each train, priority information which is added to a predetermined train and indicates an operation plan is given priority, and the running pattern of each train Information, station information including the number of tracks at each station and distance data from the preceding station, automatic driving control information relating to automatic driving control for decelerating when each train is shorter than a predetermined distance from other trains, and a station or train. Train schedule information input means for inputting train schedule information including failure / maintenance information of facilities and trains, parallel / non-parallel schedule information indicating whether passing is possible, and physical quantities to be optimized in train schedule creation. Planning condition setting means for inputting planning conditions including information for creating an objective function to be represented, and creating an objective function from given train schedule information and planning conditions Function creation means, a train diagram plan creation means for finding the minimum value of the objective function F (x) with a train combination vector being x, and an output means for outputting a train diagram plan creation result by the train diagram plan creation means. This is a train schedule creation device. Further, in the above-mentioned apparatus, a train diagram creating apparatus having a function of registering a plurality of objective functions in advance and selecting the objective function may be considered. In this case, the plurality of objective functions registered in advance include the minimum travel time,
Uniform train arrival intervals at each station, maximum safety, strict adherence to arrival times,
And when the travel load minimum is used as the objective function, the total time required from the first station to the last station of all trains is minimized, and the train arrival interval at each station is uniform. When the objective function is, aim at minimizing the standard deviation value of the arrival time interval of each train stopped at each station, and when the safety maximum is the objective function, certain trains and other trains In the case of a train provided with an automatic operation control device that performs deceleration when the distance of the train is equal to or less than a predetermined value, the number of decelerations by the device is minimized, and when the arrival time strict observance is used as an objective function, each train A function for minimizing the error between the scheduled arrival time at the terminal station and the actual arrival time, and minimizing the standard deviation value of the stop time at each station of each train when the objective function is to make the riding load uniform. Train diagram making device with It may be. In the above device,
It is preferable that the output unit includes at least one of a printing device and a display device. In this case, the display device may have a function of displaying, as a trend graph, the number of times the train schedule has been created and the objective function value for the created schedule. In addition, in the above description, a train diagram creation device having a function of terminating train diagram creation is also conceivable. Further, as the train schedule information, the train name, the departure time of the first station, the arrival time of the last station, the arrival time of the middle station, the passing time of the middle station, the station where the train is scheduled to depart preferentially when the timetable is created The information including the layout direction when creating the train schedule, travel pattern, first station, last station, stop station, transit station, standard stop time at each station, minimum stop time at each station, and maximum stop time at each station. Further, the station information may be information including the number of tracks for each traveling direction, the distance to the preceding station, and the minimum time for point switching. Further, in the above-described apparatus, the train diagram creating means sets each train as an element of the Gibbs matrix, and simulates a Markov chain, thereby bringing the state probability distribution of the Markov chain closer to the optimal state probability distribution,
It is a means for obtaining a train combination that gives the minimum value of the objective function, and the means may further include a means for lowering the temperature T, which is a parameter at the time of search, as the number of searches increases. Further, when the number of trains to be subjected to the train schedule creation plan is n, the search may be configured to have a function of terminating by the cube of n. In addition, the following means can be considered as application examples of the above device. In the device, there is only one type of line between stations, and the trains facing each other using the evacuation line in the station premises are subject to a train non-parallel diagram that is characterized by an operation that must cross each other. , Minimum travel time, uniform train arrival interval for each station, and maximum safety are determined, and when the minimum travel time is used as the objective function, the required time from the first station to the last station of all trains is calculated. If the objective function is to minimize the total sum and the train arrival interval uniformity for each station, the standard deviation value of the arrival time interval of each train stopping at each station is minimized, and the safety maximum is increased. When the objective function is used, a function for minimizing the number of times of deceleration by a train equipped with an automatic operation control device that performs deceleration when the distance between a certain train and another train is equal to or less than a predetermined value. Have There is the train schedule creation device. Also,
There is only one type of line between stations, and the non-parallel timetable, which is characterized by an operation in which the opposing trains must cross each other using the evacuation line in the station premises, is planned, and a certain train is delayed for more than a predetermined time If this is the case, enter the train schedule information at the time of occurrence of the delay, and use the function with the objective function of strict adherence to the arrival time to minimize the standard deviation from the estimated arrival time of each train when the delay does not occur. It is also conceivable to have a configuration. In addition, the tracks between stations are installed in each traveling direction, and the station premises have at least one evacuation line and at least one passing line in each traveling direction. If at least one of the minimum travel time, the uniform train arrival interval at each station, and the maximum safety is determined as the objective function, and the minimum travel time is used as the objective function, the required time from the first station to the final station of all trains If the objective function is to minimize the sum of time and the train arrival intervals at each station are the same, the standard deviation of the arrival time intervals of each train stopped at each station is minimized, and the safety When the maximum is used as the objective function, minimizing the number of times of deceleration by a train equipped with an automatic operation control device that performs deceleration when the distance between a certain train and another train is equal to or less than a predetermined value. Configuration with functions Conceivable. In addition, tracks between stations are set up for each direction of travel, and single-sided parallel trains with no evacuation tracks in the station premises are subject to train schedule planning. The transition information for each station is input as train schedule information, and at least one of a train arrival interval uniformity, a safety maximum, and a boarding load uniformity for each station is determined as an objective function. In the case, the standard deviation of the arrival time interval of each train stopping at each station is minimized, and when the safety maximum is used as the objective function, the distance between a certain train and another train is reduced. In the case of a train equipped with an automatic operation control device that performs deceleration when the speed is equal to or less than a predetermined value, if the number of decelerations by the device is minimized, and the riding load uniformity is used as an objective function, the train must be installed at each station of each train , Configurations are contemplated having a function to improve the minimization of the standard deviation of the parking time. Further, when a certain train in the train schedule creation plan is delayed by a predetermined time or more, the train schedule information at the time of occurrence of the delay, and the transition information for each station of the amount of boarding or transportation with respect to time are provided. A configuration is also conceivable which has a function of inputting and determining a uniform boarding load as an objective function, and minimizing the standard deviation value of the stop time at each station of each train. The following means can be considered as a method for solving the above problem. In order to create the optimal train schedule, given train schedule information for the given plan, travel pattern information for each train, station information including the number of tracks at each station, decelerate when each train is less than a predetermined distance from other trains Automatic operation control information on automatic operation control, failure maintenance information of trains, transition information of the number of passengers with respect to the time of each station, and state variables representing train assignment order candidates that can occur in these information are input. , A search for rearranging state variables is performed, a temperature T for determining the energy of the random system is set so as to decrease as the number of searches increases, and a first uniform random number is generated. The rearrangement of the state variables (trains) is performed based on the random number of 1, the next plan candidate Y is created from the current plan candidate X, and the objective function value f of the current plan candidate is calculated according to a predetermined objective function. x), and the objective function value f of the next plan candidate
(Y), the f (x) and f (y), the temperature T, and the newly generated second uniform random number a are expressed as a <exp (-(f (y) -f (X)) / T) (where exp represents a power of the base of the natural logarithm) When the inequality is satisfied, the next plan candidate y is set as the optimal train schedule candidate a predetermined number of times.

[0005]

The operation will be described below. In the present invention, the points of the processing are the following three points. First, the train schedule is created not only once but repeatedly until an optimal solution is obtained. In other words, since the entire possible plan combination set of the target train is observed and the optimal solution is obtained, the obtained result is always stable with respect to the objective function and becomes the most satisfactory. I have. Second, after creating a train schedule, when creating the next train schedule, the order combination of trains in the previously created train schedule is changed little by little using a stochastic process, and the purpose of the train schedule before the change is changed. Compare with the function value. Thirdly, the objective function value of the train diagram before the change is compared with the objective function value of the train diagram after the change, and even if the objective function value has not been improved (including the case where it has deteriorated), the optimal If it is determined that the search process reaches a solution, the train diagram after the change is adopted as a better candidate on the optimum solution search route. The above processing is repeated, the transition of the objective function value is observed, and when the optimal solution is reached, the creation of the train schedule is terminated. In the conventional knowledge engineering method, OR method, etc., the evaluation does not go in the direction of decreasing once in the planning process, so it is not possible to stop at the minimum value and reach the optimal solution. Since it is possible to accurately determine that the search process is to arrive at the optimal train schedule, it is possible to reliably detect the optimal solution which has been difficult in the past. Also, since it is possible to simulate the actual train assignment faithfully, it is possible to strictly calculate conditions such as failure, maintenance, fine speed change, etc.
A very realistic study is undertaken. Further, when the number of trains to be planned is n in the conventional enumeration method, the number of repetitions of the processing is n! Although it is necessary to consider (factorial) times, in the present invention, in consideration of experimental statistical considerations, it has been confirmed that n to the third power is sufficient. This means that, for example, if n = 100, 100! (≫1
0 ⁹⁰ ) is required, whereas the optimal train schedule is obtained in 100 ³ = 10 ⁶ times or less. Assuming that one search requires 1 (msec), the enumeration method requires at least 10 ⁸⁷ (seconds)> 10 ⁷⁹ years, but in the present invention, it should be terminated at 10 ³ (seconds) ≒ 17 (minutes). Becomes Furthermore, in the temperature (the amount representing energy) control method according to the present invention, the temperature is set large in the initial stage of the search, and then the temperature is rapidly decreased. Therefore, there is an important effect that a solution very close to the optimal solution can be obtained. This has sufficient performance for actual use. In this case, since n = 100, only 100
(Ms) shows that an optimal train diagram for practical use can be obtained. In the present invention, the objective function value in the planning process is converted into a trend graph and is displayed in real time, so that the user can quantitatively know the quality of the train schedule that has already been planned, and furthermore, any arbitrary Since the creation of the plan can be terminated at the time, the best one can be provided within the allowable time required for creating the train schedule under various circumstances. This is an important operation when, for example, a train schedule is arranged after a sudden train delay occurs. Further, according to the present invention, the purpose of preparing a train schedule can be quantitatively determined, so that fine adjustment of the prepared train schedule is hardly required unlike the conventional method.

By the way, there are the following objective functions. Of course, it is not limited to these. First
Is to minimize the required time from the first station to the last station of all target trains, that is, the sum of travel time.
This makes it possible to obtain a train schedule in which useless stop of the station, deceleration operation, and the like are eliminated while maintaining the determined traveling pattern. The train diagram created by this objective function is suitable for a train diagram for high-speed mass transportation.

The second is to make the arrival intervals of trains at each station uniform. Since the frequency of use of trains varies from station to station, various services need to be adjusted accordingly. By setting this function, optimal services can be provided for each station. This is important in creating a general train schedule that is frequently used on a daily basis, such as commuting to work or school. Third,
It maximizes safety. On a single-sided track, there is a possibility of a rear-end collision, and on a two-sided track, in addition to a rear-end collision, there is a possibility of a frontal collision. For this reason, it is necessary to ensure the interval from the preceding train as much as possible, and to secure a sufficient margin for evacuation in the station yard and switching of points. Therefore, the use of this objective function is important in the preparation of a congested timetable and in the operation control in an emergency. Fourth, strict adherence to the arrival time is required.
In the event of a natural disaster, vehicle breakdown, accident, etc., it is necessary to review the train schedule. At this time, various services can be maintained by setting the function so as to observe the arrival time of the last station of the train schedule before the change. of course,
It goes without saying that the arrival time at each station can be changed to be strictly adhered to. Fifth, the load of the ride is made uniform. On routes where the distance between stations is short and the number of trains passing per hour is large, the time at which the train stops at the station greatly affects the train schedule. Therefore, a good service is maintained by adding the train use degree with respect to the time for each station to the input information and planning to make the riding load (rate) of each train uniform. In addition, when a vehicle failure occurs at a certain station and the vehicle is delayed, the number of waiting passengers at the downstream station increases, so the time required for getting on and off the train increases one after another, and the delay of the train increases. Occurs. Even in such a case, if this objective function is selected, the preceding train is delayed little by little, and the following trains are arranged so as to be ahead of schedule. Therefore, the disturbance of the train schedule is recovered in a short time. Even if this method is to be realized by a program on a sequential execution type computer, the processing algorithm of the main part can be realized in only several tens of steps and does not need to be changed according to the target. Further, by operating with a mutual connection type neural computer, the speed can be further increased.

[0008]

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS Embodiments of the present invention will be described below in detail with reference to the drawings. FIG. 1 shows a configuration diagram of an embodiment of the present invention. The train schedule creation device 1 includes a train schedule information input unit 2, a train schedule information storage unit 3, a plan condition setting unit 4, a plan condition storage unit 5, a train schedule creation unit 6, a result storage unit 7, an output unit 8, a display device. 9 and printing device 1
0. The train schedule information input means 2
A means for inputting various types of train information, traveling patterns, station information, automatic operation control information, and failure / maintenance information, and is realized by, for example, a keyboard, a mouse, an electronic light pen, a touch panel, and the like. Train schedule storage means 3
Is a means for storing various information input by the train schedule information input means 2, and is realized by, for example, a RAM, a magnetic disk, an optical disk, or the like. The plan condition setting means 4 selects an objective function for creating a train diagram registered in advance, or creates an arbitrary objective function,
It is a means for setting the timetable to parallel or non-parallel and for instructing the start of a train timetable. The plan condition storage means 5 is a means for storing various information input from the plan condition setting means 4, and includes, for example, RA
M, a magnetic disk, an optical disk, and the like. The train schedule creation means 6 is provided with the train schedule information storage means 3
Means for planning the optimal train schedule based on the information stored in the plan condition storage means 5 and displaying the progress on the display device 9, for example, CPU, ROM, RA
M and the like. The result storage means 7 is a means for storing the created train schedule, for example, a RAM,
It is realized by a magnetic disk, an optical disk, or the like. The output unit 8 is a unit that displays the train schedule stored in the result storage unit 7 on the display device 9 and prints it on the printing device 10, and is realized by, for example, a CPU, a ROM, a RAM, and the like. The printing device 10 may be, for example, a printer, and the display device 9 may be a CR.
A T display, an EL display device, a liquid crystal display device and the like are conceivable. The apparatus according to the embodiment shown in FIG. 1 can be realized using one computer system. For example, the train schedule information input means 2 and the planning condition setting means 4 are provided with a keyboard for the user to perform an input operation and a C for displaying the input contents.
This can be realized by a configuration having a display device such as an RT. The train schedule creation means 6 and the output means 8 can be constituted by a central processing unit (CPU).
The plan condition storage means 5 and the result storage means 7 can be constituted by a memory device. The display device 9 is a display such as a CRT, which is a display screen of a computer, and the printing device 10 is a printer connected to the computer,
-Y plotter or the like. Hereinafter, specific embodiments will be described, but application examples are roughly classified into the following three. (1) Face-to-face non-parallel diamond (described with reference to FIGS. 5 to 27)

(2) Single-sided non-parallel diamond (FIGS. 28 to 3)
6 will be described).

(3) Single-sided parallel diamond (FIGS. 37 to 39)
To explain).

## EQU1 ## In addition, the above (1) and (3)
In the above, the present invention can solve a major problem conceivable when creating a train schedule, in detail, also describing the operation arrangement when a train delay or the like occurs. First, an example of application to a face-to-face non-parallel diamond will be described. First, the creation of a train schedule for normal operation will be described with reference to FIGS. FIG. 5 shows an example of the train information set by the train schedule information input means 2. In this example, 16 trains are arranged within about 6 hours.
1 to E4 are high-speed trains that run at a high speed and stop only at main stations. E5 to F6 are trains that run at high speed but stop at all stations. G1 to G4 are ordinary trains that stop at all stations. The following items can be set along the horizontal axis as train information for each train. “Scheduled time (start point)” indicates the scheduled departure time of the first station. “Scheduled time (end point)” indicates the estimated time of arrival at the terminal station. “Priority (start / end)” indicates that the station to which the symbol “○” is input is set as the planning start station. That is, "beginning"
At (first station), when "○", forward assignment toward the last station is instructed. At "last" (last station), when "○", assignment toward the first station going back from the last station is instructed. ing. In this example, only the first station and the last station can be selected, but depending on the route, from all stations,
It is also conceivable that the station can be selected according to the priority. In this case, the assignment from the corresponding station to the starting station and the assignment toward the terminal station may be performed. “Priority” indicates that a train to which a symbol “○” has been input is assigned with priority over other trains. These are excluded from the trains to be optimized. In the "stop station", the following symbols are set for all stations included in the line.

"□" indicates the first station, "●" indicates the last station, "○"
Indicates a stop station, and “◇” indicates a passed station. In the “stop time”, a standard stop time, a shortest stop time, and a maximum stop time of the train are set. If there is no restriction, the symbol “*” is set. If the riding amount changes depending on the time zone, the graph is a riding amount change graph with respect to time transition.

In the "direction", since the present example is a facing route, the direction is indicated by an arrow symbol.

The above is an example of a specific route direction,
All items can be changed according to the target route or the train schedule. For example, instead of the scheduled time, only the required number of trains may be set. In this case, trains are automatically arranged so as to satisfy the objective function. FIG. 6 shows a traveling pattern set by the train schedule information input means 2.

For example, in the traveling pattern 1, the vehicle speed reaches 120 (km / h) in 6 minutes after the departure, and thereafter, 120 (k / h).
m / h), the vehicle gradually decelerates when approaching a stop, and stops in about 4 minutes. Running patterns 2 and 3 also define running patterns. The above is effective when there is a sufficient distance and time difference between the preceding train and the oncoming train, and it is not necessary to consider the danger of rear-end collision and collision. Therefore, when the vehicle is approaching the preceding train or the oncoming train, a more complicated operation pattern takes into account the automatic operation control information described later. In this example, pattern 1 for trains E1 to E4, pattern 2 for trains E5 to F6, and pattern 3 for trains G1 to G4.
Are set respectively. FIG. 7 shows station information set by the train schedule information input means 2. The following items can be set for all stations belonging to the planned route. The “number of tracks” indicates the number of tracks that can be entered in each train traveling direction. In this example, all the tracks have platforms that can get on and off. If there is a passage-only line or an evacuation-only line, it may be set separately from the number of lines. “Minimum point switching (minutes)” is an item that is set because a point operation for line switching is required in relation to a preceding or oncoming train. This is generally included in this information in the case of a route having automatic driving control described later. When creating a diagram, a minimum point switching (for example, in minutes) must be ensured. The distance to the adjacent station is set by “preceding station distance (km)”. If more realistic information is required, the configuration may be such that information can be input in consideration of the track layout, gradient, and the like. FIG. 8 illustrates the above information, and also describes the automatic operation control information set by the train schedule information input means 2. In recent years, in order to ensure the safety of many passengers, in recent years, each train has been equipped with an automatic operation control system,
In general, the traveling speed is controlled based on the relative relationship between the position of the vehicle and the vehicle. In FIG. 8, centering on station 4 (a)-
(G) Position detecting devices are installed at seven locations to control the traveling speed. For example, if the next train arrives at point g while the preceding train passes point a, it is necessary to reduce the traveling speed to 100 (km / h) or less in the sections g to f, and f
At the time of passing the point, the train is forcibly stopped unless it is less than 100 (km / h).

Therefore, when preparing a train schedule, it is necessary to strictly consider speed changes due to the positional relationship between the trains before and after. FIG. 23 shows the optimal train diagram created using the above various information on the display device 9 or the printing device 10.
This is an example of output to. In this figure, the vertical axis defines stations, platforms (tracks) within the station, and tracks between stations, and the horizontal axis defines time. The line in the figure shows the operation status of the train. For example, the train 7 has the train name F1, departs from the station 1 at 6:10, arrives at the station 2 at 6:17, and arrives at the station 2 at 6:17. 21
Minutes from the station 3 to station 9
And then arrives at station 10 which is the terminal station at 8:20. During this time, train 1 (E
It can be seen that the train has been overtaken in 1) and that it safely intersected the oncoming trains at stations 5, 6, 7, 8, and 9. Hereinafter, a situation in which the optimal train diagram is created by the apparatus according to the present invention will be described with reference to FIGS. 9 to 21 illustrate the operation of the train diagram creating means 6 in detail with reference to flowcharts for easy understanding. 9 to 11 show the flow of the entire processing of the train schedule creating means 6. First, the flow of the diagram planning process will be described with reference to FIG.
First, the train schedule information set by the train schedule information input means 2 and stored in the train schedule information storage means 3 is fetched. Further, the plan conditions set by the plan condition input means 4 and stored in the plan condition storage means 5 are fetched (step A).

Based on the taken-in failures, maintenance information, and the like, the availability status of the tracks, platforms, and the like is created (step B). Details of this processing will be described later in a specific application example. Next, in steps C to E, priority trains are allocated prior to the optimization processing. In this embodiment, a loop counter for 16 trains is set to refer to the train information shown in FIG. 5 (step C). Next, it is determined whether or not the train is a priority train (step D). If the train is a priority train, the corresponding train is allocated according to the train schedule information (step E). In this embodiment, as shown in FIG. 22, train 3 (E3), train 4
(E4), the train 9 (F3) is allocated prior to other trains. The “priority” is set, for example, when it is desired to predetermine the operation of a special express train or a train with a particularly large delay. Details of the allocation processing will be described later. The initial state of the diamond plan for optimization is created by the processing from step A to step E described above. Since this state is used repeatedly in the following processing, it is stored as the initial state A in step F. Next, in step G, a train table of only the trains excluding the above-mentioned priority train (hereinafter referred to as a “planned train table”) is created. FIG. 12 shows a detailed procedure of such processing. First, the set position pointer m of the train table to be planned is initialized (step G10), and then the loop counter P is set so as to repeat n times, which is the total number of trains (step G20). If the P-th train in the train table is not the priority train, it is registered as the m-th train in the planned train table (step G30), and the value of the set position pointer m is updated by 1 (step G35). By repeating the above-described processing n times, a planned train table in which 13 trains are registered as shown in the figure is created. Next, in steps H to L (see FIG. 9), a basic state for creating an optimal train diagram is created. First, a random one-dimensional vector と す る having a train to be planned as an element is generated as an initial state in the train assignment order (step H). In this embodiment, assuming that the arrangement order in FIG. 12 is an initial state, χ = (1,2,3,4,5,6,7,8,9,10,1
1, 12, 13). Here, since the train is indicated by the variable m, E1, E2, E5, E6, F1, F2, F4, F5
F6, G1, G2, G3, and G4 are arranged in this order. In accordance with the vector χ, trains are allocated according to train information or plan conditions (step I). Step I is the same processing as step E and step Q. FIG. 13 shows a detailed procedure of step E, and the description will be made based on this. First, a start / stop availability map is created that indicates whether trains can be started and stopped with respect to the time transition of each station (step E10). 14 and 15
The detailed example is shown in FIG. FIG. 14 shows an example in which there is no evacuation line at the target station. In this example, the stations 6 and 7 correspond to this. For example, as shown in the figure, when the operation of the train (1) to (4) has already been determined, it indicates that the allocation of a new train must be performed within the white blank area on the start / stop availability map. Here, the “assignment” means to determine the departure time at the station 6, the detailed traveling speed pattern from the stations 6 to 7, and the arrival time at the station 7. Train 1
Stop at line 1 (home) at station 6 for 5 to 10 minutes (hereinafter described as absolute time with the starting point being 0 minute), run from 10 to 20 minutes, and then stop at line 1 at station 7 for 5 minutes After that, departure in 25 minutes. The line between stations in this direction is 1
Overtaking between stations is impossible because there is only a book. Also,
Since there is only one track (home) in the station, it is impossible to stop or depart while the preceding train is stopped. Therefore,
The trains for which a steady running pattern is designated as in this example include a line connecting 5 minutes to 10 minutes at station 6, a line connecting 20 minutes to 25 minutes at station 7, 5 minutes at station 6, and station 7 Must not pass through the space and time indicated by the square (the hatched portion in the figure) enclosed by a straight line connecting the 20 minutes of the station 6 and the 10 minutes of the station 6 and the 25 minutes of the station 7. The train indicates a train passing without stopping at both the station 6 and the station 7. In this case, the train has a space-time line indicated by a straight line connecting the passage time 30 minutes at the station 6 and the passage time 40 minutes at the station 7. You cannot cross. However, this time and space does not specify that the vehicle arrives at the station 6 and departs from the station 7, but departs from the station 6, travels from the stations 6 to 7, and stops at the station 7.
It is important to note that it determines whether or not you can arrive. The train stops at the station 6 but passes through the station 7. In this case, the same concept as above is used, and the train at the station 6 from 43 minutes to 48 minutes, the station 6 at 43 minutes and the station 7 Of 56
A triangular area surrounded by a straight line connecting the minutes, the station 6 48 minutes, and the station 7 56 minutes indicates an impossible space-time. train,
Is an example of an oncoming train. The train stops at both station 7 and station 6, but the oncoming train is not affected by the stop. However, during the time period when the oncoming train departs from the station 7 and arrives at the station 6, the train between the stations 6 and 7 cannot use the line between the stations 6 and 7. Therefore, as shown in FIG.
The rectangular area having the vertices at the vertices of minutes, 80 minutes and 70 and 80 minutes of the station 7 is a time and space that cannot pass. The train is an on-coming train passing through stations 6 and 7, but, like the train, a rectangular area defined by a passing time of 88 minutes at station 7 and a passing time of 100 minutes at station 6 cannot be passed. Becomes A train is an example in which oncoming trains cross each other at a station 6.
The train arrives at station 6 at 123 minutes, but at that time the train is already running between station 7 and station 6, so waiting for the train to arrive at station 6 (130 minutes), and at 132 minutes Departs from station 6. As a result, the departure time 1 of the train at station 7
20 minutes, the train departure time at station 7 144 minutes, and station 6
Departure time of train at 132 minutes, and said 1 at station 6
A rectangular area created in 20 minutes becomes a time and space that cannot pass. In this case, the hatched portions in FIG. 14 are indirectly impassable space-time. FIG.
This is an example of a case where there is an evacuation track at a station. The difference from FIG. 14 is that trains in the same traveling direction can pass the preceding train in the station. In the example shown in FIG.
There are two tracks (home) in both directions, and one is
The other is used for "stop / evacuate" and the other is used for "stop / pass". The train 8 stops at the station 5 for 5 minutes from 5 minutes to 10 minutes. During this time, the following train can stop at the station 5 or pass through the station 5. Therefore, the operation pattern is the same as that of the train in FIG. 14, but is not a rectangular area as shown in FIG.
A triangular area as shown in FIG. 3 is a time space in which a train cannot pass. For trains 9 to 15, the time and space that cannot be passed are as shown in FIG. 15 for the same reason as described above. The above is the processing of Step E10 (see FIG. 13). Next, from step E20 to step E70
According to (see FIG. 13), the trains to be planned are allocated as follows in accordance with the preset train information and plan conditions. First, in step E20, the number of trains to be planned n
Is repeatedly set to the pointer P. Next, the traveling direction of the Pth train in the planned train table is determined (step E30). In step E40, the knitting direction of the diamond is similarly determined. In this embodiment, the “diamond composition direction” is determined by the priority designation of the first or last station.
For example, when the terminal station is prioritized, it gradually goes back to the upstream station using the estimated arrival time of the terminal station as reference information. Conversely, when the first station is prioritized, the assignment is made toward the downstream station using the first station departure time as reference information.
The method of allocation is not limited to the above method.
For example, the following methods ((a) to (c)) can be considered. (A) A method may be used in which a midway station is designated and allocated in both directions, upstream and downstream. (B) If the departure or arrival time for each station can be set in advance, a method may be used in which these are set as reference information and undecided information is determined. (C) A method is also conceivable in which only macro information such as the number of trains is given without determining the departure and arrival times, etc., thereby giving a degree of freedom in allocation. The method (a) is effective for, for example, emphasis on a main station, the method (b) is effective for, for example, a timetable arrangement in an emergency, and the method (c) is effective for, for example, a simulation at the initial stage of a diamond formation. is there. Next, the following processing is repeated for all the stations included between the first station and the last station designated for the train P (step E50).

The assignment is performed by the following simple procedure using the start / stop map. FIG. 16 shows a train (a) and a train (b) between the stations with one line in the station.
It is explanatory drawing in the case of assigning. By considering the assignment between the station 5 and the station 6, the arrival time of the train (a) at the station 6 is set to 12 minutes. The standard stop time is 2 minutes, and the train arrives at the station 7 in 27 minutes in consideration of the distance between the stations 6 and 7 and the traveling pattern. In addition, a standard stop time of 2 minutes was added, 29
Departs from Station 7 in minutes. Since the above operation is determined to be possible from the start / stop map, the assignment processing ends. On the other hand, the train (b) arrives at the station 6 in 92 minutes, but the start / stop map shows that the train (b) cannot depart after the standard stop time. For this reason, an operation that can change the departure time from the minimum stop time to the maximum stop time will be examined. In this example, since the train passes through the station 6 for 100 minutes, the train (b) is assigned to depart the station 6 at 102 minutes in consideration of the point switching time. In this case, the degree of freedom is only perturbation of the stop time since the traveling pattern is fixed, but when the traveling pattern can be selected, the change in the traveling speed can be added as the degree of freedom. The allocation within this degree of freedom may be defined for each objective function. For example,
In the above description, the earliest departure time is adopted, but this assignment is considered effective when an objective function is given so as to minimize the travel time. On the other hand, if the maximum safety is used as the objective function, it is conceivable that the automatic operation control is not performed and the start and stop times at which point switching can be performed with a sufficient margin. FIG. 17 shows an example in the case where an escape line exists. The train arrives on the first track of Station 5 in 6 minutes, stops for 4 minutes, and departs in 10 minutes. The train (c) arrives at the second track of the station 5 in 8 minutes, and leaves the station 6 18 minutes after the train departs. The equipment is used more densely than in the case shown in FIG. Next, the train (d) arrives at the station 6 at 63 minutes, but cannot be departed immediately because there are already allocated trains (11) and (12), and departs at 81 minutes. Assigned.
This indicates that when the assignment order is earlier for the train (d), the schedule is completely different.

After performing the above processing for all the stations in the train P (FIG. 13, steps E50 to E60),
The start / stop impossible time space determined by the assignment is registered in the start / stop availability map (FIG. 13, step E7).
0), branch to the processing of the next train. By repeating the above process for all the elements of the vector in the order of the trains to be planned, one possible train schedule is created. Next, in step J in FIG. 9, an objective function calculation is performed, and the possible train schedule generated above is quantitatively evaluated. The description here is shown in FIG.
For the objective function of FIG. 18 shows a detailed procedure of step J when the minimum travel time is used as the objective function. Step J is the same process as step R. The objective function for the already created possible diagram i is f (i), and “0” is set as an initial value (step J10). Next, a pointer P for repeating the process for the number of trains to be planned is set (step J2).
0). The travel time tt (p) is obtained as follows from the departure time ts (p) of the train P at the first station and the arrival time te (p) of the last station. tt (p) = te (p) -ts (p) Next, the objective function is updated. That is, f (i) = f
(I) + tt (p). The above is the processing of Step J30. F (i) after repeating this processing n times, which is the number of all trains to be planned, is the sum of travel times of all trains to be planned included in the possible timetable i.
Therefore, the minimum value of f (i) indicates a train schedule in which all trains operate most efficiently. next,
FIG. 19 is an explanatory diagram in a case where the arrival function of trains at each station is uniform as an objective function. First, in step J10, the objective function value f (i) is set to “0”. Next, the pointer s (=) that is repeated for all the stations included in the planned route
1 to smax). Here, smax is the total number of stations. Next, as shown on the right side of FIG. 19, differences t ₁ , t ₂ ,... Tw (w
Is the total number of stopped trains). A value H (s) obtained by dividing the standard deviation by w from these values is obtained, for example, as follows (step J30). H (s) = (√ (Σ (xa−xk) ² )) / w where xa is the average value of the difference between the arrival times of all the trains, and xk is the k-th difference between the arrival times of the trains. And Σ represents w sums. Next, in step J40, the objective function f (i) is updated. That is, f (i) = f
(I) + H (s) (step J40). f (i)
Is the sum of the train arrival interval deviations for each station, so f (i)
The minimum value indicates that the arrival time intervals of the stopped trains at each station are nearly constant, that is, the train schedule is preferable for the user. FIG. 20 shows a process when the maximum security is set as the objective function. There are various indicators for safety, but here we will focus on reducing the risk of collision and collision. In this example, the equipment and the train are provided with an automatic operation control device, and the device operates when the distance between the preceding train and the oncoming train is shorter than a preset value under a predetermined condition. Make restrictions. Therefore, reducing the number of occurrences of the traveling speed restriction reduces the danger in operation and also reduces the load on the automatic control device. In addition, an operation without a speed limit minimizes the travel time between stations, and contributes to a reduction in travel time by accurately determining a stop. In FIG. 20, first, "0" is set as the objective function value for diamond i (step J10). Next, 1 to smax is set in the pointer s for repeating the process for all stations. Here, smax is the total number of stations included in the line. The number of times the speed limit occurs for all trains entering the station s is calculated.
In the example of the figure, when the preceding train is at the point c and the point b, the speed is limited, and the number of times is two. At the station s, the sum of the numbers is set to H (s), and the objective function value f (i) is updated (step J40). That is, f (i) = f (i) +
H (s). FIG. 21 shows a procedure when the arrival time is strictly adhered to the objective function. This function may be used, for example, when scheduling a diagram after a delay has occurred.
In step J10, "0" is set to the objective function f (i). Next, 1 to n are set to the pointer p for repeating the process by the number of trains to be planned (n) (step J).
20). Next, the arrival time te of the terminal station after arrangement of the train P
(P) is calculated and estimated arrival time te 'before the schedule is arranged
When the absolute value th (p) of the difference from (p) is obtained, the following expression is obtained.

Th (p) = | te (p) -te '(p)
The objective function value is updated with this deviation (step J30).
That is, f (i) = f (i) + th (p). In this manner, the sum of the absolute values of the differences between the scheduled arrival times of all the planned trains before the schedule and the scheduled arrival times after the schedule is set to f (i). In this example, the arrival time deviation with respect to the terminal station is evaluated, but the arrival time deviation may be evaluated with respect to all the stopping stations.
The above is the processing in step J shown in FIG. next,
In step K, the objective function value for χ obtained in step J is stored in the working storage variable area MOPT. That is, MOPT = f (χ). Next, the number N of optimization repetition processes is determined (FIG. 10, step L). That is, N = n ³ . In the present embodiment, n ³ is defined as the number of times of optimization repetition processing with respect to the number n of trains to be planned. This value is found experimentally and statistically, and is originally an order combination of n trains. Is n! What is present indicates that n ³ can provide satisfactory results, speeding up the processing. For validity of this value,
It will be described later. With the above processing, the preparation processing for optimization is completed, and the optimal train diagram is created as follows in steps M to W (FIG. 10). First, 1 to N are set in the loop counter i in order to perform the repetition processing for N times, which is a sufficient number of times to obtain the optimal solution (step M). Next, the initial state A stored in step F of FIG. With this operation, the initial train diagram in which the priority train, the failure / maintenance information, and the like are already set is reproduced for each loop i. Next, the already-assigned planned train number is used as an element.
The train allocation order vector 少 し is slightly changed in the following procedure (this is hereinafter referred to as “perturbation”). First, two types of uniform random numbers is and ie (is <
ie) is generated (step O). Next, the element i of χ
The contents of the sth and ieth ranges are rearranged in the reverse order (Step P). Step P will be specifically described with reference to the present embodiment. χ = (1,2,3,4,5,6,7,8,9,10,1
1,12,13), and if is = 3, ie = 8 is generated, the new train allocation vector y is y = (1,2,8,7,6,5,4,3, 9,10,1
1, 12, 13). If this is indicated by an actual train name, referring to FIG. 12, E1, E2, F5, F4, F2, F1, E6, E
5, F6, G1, G2, G3, and G4. The above operation is referred to as a perturbation, and such processing is performed every time a next study candidate is created in creating a train diagram. Next, train allocation is performed for the new planned train vector y (step Q), and an objective function value f (y) for the allocation result is calculated (step R). Where step Q and step R
Is the same process as Step I and Step J, respectively. In step S, the new plan y created in this way and the already created χ are examined as follows. First, a uniform real random number a in the range of 0.0 to 1.0 is generated. Next, the temperature T is determined by a function that decreases as the number of searches i increases. Further, the a, T, f
At (χ) and f (y), it is determined whether or not the train schedule based on the newly created y is an optimal solution candidate. Using the present embodiment, the processing in step S will be specifically described.
Now, the travel time of the objective function is minimized, and the objective function values in this case are f (χ) = 1255 (minutes) and f (y) = 1287 (minutes). Also, a = 0.6505, T = Δ / lo
In the case of g (i + 2) (Δ = 100.0 in this example), if i = 1, then a <exp (− (f (y) −f (χ)) / T) = exp
(-(1287-1255) /209.5) ≒ 0.85
Since 8 (exp represents a power of the base of the natural logarithm) is satisfied, the diamond y replaces χ as a candidate close to the optimal solution despite the travel time being longer than the diamond χ (step T). Next, when f (y) is smaller than the MOPT set in step K, the minimum value of the objective function value is stored as MOPT = f (y) (step V). Step W is a process of displaying on the display device 9 when the minimum value is updated in this way. This is shown in FIG.
Is displayed as shown. In this example, the horizontal axis indicates the number of searches i, and the vertical axis indicates the minimum value MOPT of the objective function as a trend graph. The user can sequentially observe this graph during the train diagram creation process, and can terminate the creation process at an arbitrary timing. The feature of this train schedule creation method is that it is very close to the optimal solution at the initial stage of the search. Therefore, when the train schedule creation time is not enough and an exact result is not required, it is very effective. As described above, the optimal solution can be obtained by repeating Step N to Step W at most N times. FIG. 4 illustrates the case where an optimal solution is obtained by performing the above-described processing, and shows the convergence state to the optimal solution based on the number of searches based on experimental statistical results. As described above, when the number of trains to be planned is n, the allocation order is n! There are only pieces. In the upper left diagram in FIG. 4, the horizontal axis represents the number of searches 1 to n! Is defined, and the corresponding objective function values are plotted. Since the number of searches is a natural number, the objective function is also discretely arranged on the secondary plane, but is shown by a continuous curve for explanation. From this figure, it can be seen that the objective function value has many minimum values and one type of minimum value. When a random search is performed as shown in this figure, n! It can be seen that the number of searches must be a guarantee condition for the optimal solution. For example, like a conventional Hopfield-type neural network, a method is used in which the energy of a system is defined as a continuous amount, and the search is performed with respect to the time axis as a temporal transition to search for a low energy state. And the minimum value can be determined in a relatively short time, but the probability of detecting the minimum value is extremely low.
On the other hand, in the present invention, in step O and step P,
The train assignment order combination is slightly changed, and random search is eliminated. Then, if the combination after the change is improved compared to the evaluation of the combination before the change, the combination after the change is adopted as a new candidate as an ordered combination closer to the optimal solution (step S). But,
With only this operation, when the minimum point is reached as described above, no new candidate is created thereafter, and the minimum value cannot be obtained. In the present invention, this is avoided as follows. In the enlarged view near the minimum value in the upper left diagram of FIG.
Now, it is assumed that the objective function has a value of LM at the L-th search. Since the true minimum value is OPT, LM
It is necessary to move to PT. For example, let the objective function value be a ball (sphere) (an analogy for explaining the principle) and consider the energy amount of the ball. At this time, the transition in the direction A in the drawing is performed,
What is necessary is just to consider a method for suppressing the reversal phenomenon in the B direction, that is, the return phenomenon. When this is replaced with potential energy, it can be understood that the above is achieved by applying a force larger than the energy difference a between LM and LMX (maximum value) and smaller than the energy difference b between OPT and LMX. If this force is temperature T (which is an amount that determines energy),
T may be set to a large value in the initial stage of the search, and may be controlled so as to decrease as the number of searches increases. More specifically, for example, T = Δ / (log (i + 2)) (where Δ is a positive number and i is the number of searches). Of course, other functions are conceivable, but in general this function is better. After determining T in this manner, whether or not the optimal solution is reached may be determined by performing a stochastic trial.
For example, a random number a uniformly distributed between 0.0 and 1.0 is generated, and escape from the minimum point is determined by the following equation. a <exp (− (f (y) −f (χ)) / T) When the above expression is satisfied, y obtained by perturbing the combination れ ば may be adopted as a new candidate. This formula always holds when f (χ)> f (y), so if y is better than χ, it is always a new candidate. Also, f (χ) <f (y)
Even in the case of, as (f (y) −f (χ)) / T approaches zero, the possibility that the condition is satisfied increases. Therefore, if a sufficient number of trials are performed, the minimum value will always be obtained. The lower left diagram in FIG. 4 uses the device according to the present invention,
It shows the process up to the optimal train schedule.
In the present example, it reached the minimum at approximately n ^2. The three types of diagrams on the right side in FIG. 4 show, in a frequency distribution table, the number of searches that arrived at the optimum solution when a train diagram was created for each of the three types of planned trains n. For example, if it is assumed that the train operates 16 hours a day, and the train operates only once an hour,
n = 16, 3 pieces per hour, that is, n every 20 minutes
= 50 every 10 minutes, n = 100. The most dense diamond in reality is considered to be every two minutes, in this case n =
In this case, the time required for getting on and off at the station and the connection with other routes increase, so in practice, it is considered that the creation of a train diagram of about n = 300 is the maximum load. The right side in FIG. 4 shows n = 16 and n = 5 among the above.
This shows the results of experiments performed for 0 and n = 100. Both have the optimal solution is obtained from the n ² in the n ³ times, also, it is understood that n is frequently optimal solution is obtained larger the n ² within is large. The above is, for example, 1
000 MIPS (“MIPS” indicates a unit capable of executing one million instructions per second), and a computer using a computer capable of performing the operation is required to create a train schedule.
Creation is completed within the following time under the following conditions. The first condition is that the number of processing steps required for assignment and evaluation of one train is 10,000 (I = step). The second condition is the number of searches = n ² required for optimization. In the case of n = 16 it is, (10,000 (I) × 16 ( train)) × 16 ^2/1000 /
(MIPS) $ 0.04 (second).

[0021] In the case of n = 50 is, (10,000 (I) × 50 ( train)) × 50 ^2/1000 /
(MIPS) $ 1.2 (seconds). In the case of n = 100 is, (10,000 (I) × 100 ( ^{train)) × 100 2/1000 /} (M
IPS) $ 10 (seconds). The above is the time required to obtain the optimal solution, but it is known that a practically usable good solution can be obtained in the above time of 1/10 to 1/100. If the function is used, a solution can be obtained on the order of seconds even when n becomes about 300. Steps U to W in FIG. 10 are processes for obtaining the above-mentioned realistic sub-optimal solution in a very short time by indicating the train schedule creation status to the user. In step U,
The previous optimal value MOPT and the objective function value f of the new candidate
(Y), and when MOPT> f (y) holds,
The optimum value is updated as MOPT = f (y) (step V). In step W, the update of the optimum value is indicated by a graph as shown in FIG. 3, and information on whether or not the user terminates the process by his / her own judgment is provided. It should be noted that the termination can be realized by configuring the system so as to be performed by external input means such as a keyboard. The train diagram created in this way is displayed on the display device 9 (FIG. 11, step X) and printed on the printing device 10 (FIG. 11, step Y). The above is the detailed description of the main part of the operation of the present invention for the facing non-parallel diamond knitting. Next, the train diagram arrangement (re-creation) will be described. 24 to 27
1 shows an embodiment of the arrangement of train schedules according to the present invention. In a conventional expert system or the like, since train information is based on empirical information, it is generally necessary to consider that train diagram formation and train diagram arrangement are realized by different systems. However, in the present invention, the main logic does not need to be changed only by switching between the initial condition and the objective function. The reason for the difference between the diamond formation and the diamond arrangement is mainly that the purpose and the permissible time required for planning are different, and the assignment method based on the equipment and train information is the same. FIG. 24 shows a case where a failure occurs in the train 5 at 8:15, the departure schedule is greatly delayed, and the departure at 9:00 is expected. At this time,
As shown in the figure, the other trains are operated according to the schedule, so that it is necessary to appropriately operate the train 5 without changing the schedule of each train as much as possible. In this case, in the present embodiment, the train schedule is recreated, that is, rearranged as described below, using the objective function as the arrival time. FIG.
The operation status of the train at 8:15 is shown in the train table. E1, E2, E4, already operated
The scheduled time of the F1 train is deleted (indicated by the symbol "*"),
In addition, all stops are indicated by the symbol "◇" as stations that have already passed.

For the train running at 8:15, the scheduled time and the stop station are updated as follows.
For example, since the train 8 travels to the station 3 and departs the station 3 at 8:15 and heads for the terminal station 1 which is the terminal station, the first station becomes the station 3 (indicated by a symbol □), and The scheduled departure time has been updated at 8:15. Updates are being made on other running trains as well. In addition, the trains that have not left the starting station at 8:15 retain the initial information. Next, from FIG. 25, the trains that have already been operated are removed, and “arrangement (replanning) target train information” as shown in FIG. 26 is created. Here, 12 trains are targeted. The above processing is usually performed every hour in real time by the operation management system. The information in FIG. 26 is input information to the present system, and the subsequent processing is described in FIGS.
The processing may be exactly the same as that described in. The only difference from the train timetable is that all trains do not depart from the starting station, and only the point that the running train starts at an intermediate station and the objective function is switched.

FIG. 27 shows the result created (organized) as described above. It can be seen that the trains have been cleverly arranged so that the target train can arrive at a time close to the arrival time. Further, an example of application to a single-sided non-parallel diamond will be described. FIGS. 28 to 36 show a single-sided non-parallel schedule, that is, a route in which a line dedicated to two-way traffic is provided, and an ordinary train and an express train are mixed. FIG. 28 shows train information. This is a table similar to that of the embodiment shown in FIG. 5, but the direction is omitted because it is one-way. In this embodiment, A
Four trains 1 to A4 are the fastest trains, eight trains B1 to B8 are medium speed trains, and C1 to C8 are ordinary trains. 29 and FIG.
As shown in FIG. 0, it is assumed that seven types of running patterns are also finely defined. FIG. 31 shows a failure / maintenance information input example in which the description has been omitted in the above-described example. this is,
This is input by the train schedule information input means 2 and is set prior to train diagram creation. As shown in the figure, the horizontal axis is time, and the vertical axis is a station, a line (home) in the station yard, and a line between stations. The horizontal line in the figure is the setting information, and when it is set, it means that the corresponding station, the track (home), and the track between stations cannot be used for train operation. These pieces of information are fetched in step A in the processing flow of FIG. 9, and are set prior to the optimization processing as shown in FIG. Specifically, it is set as a start / stop availability space zone in the start / stop availability map for the station. FIG. 35 shows, in addition to the above, a priority train (2),
(4) and (12) show the allocated state (steps C to E). FIG. 36 shows a state in which the creation of the optimal train schedule has been completed. In the creation of the optimal train schedule, maximum safety is selected as an example of the objective function. The only difference from the non-facing diamond is that each train is traveling in the same direction.
This is the same as the embodiment described above. Finally, an application example to a single-sided parallel diamond will be described. 37 to 39 show the results of applying the present invention to the creation and arrangement of a single-sided parallel diamond. The two-way non-parallel and one-side non-parallel schedules allow trains in the same direction to pass, but this route is different from the former two in that they do not pass. Therefore, by removing and considering the algorithm that considers overtaking in the procedure at the time of train assignment, the train schedule can be created in exactly the same procedure as the others. FIG. 37 shows the result of selecting uniform arrival intervals as an example of the objective function, and it can be seen that the arrival intervals at each station are well aligned. FIG. 38 shows a situation in which a trouble has occurred in the train 6 at 7:10 with respect to the schedule in FIG. 37, and it is clear that the departure of the train 6 is expected to be at 7:29. If left unattended, the interval from departure of train 5 to arrival of train 6 at station 3 becomes very long, and the number of passengers waiting for the train increases. As a result, the time required for getting on and off the vehicle becomes longer, the delay gradually increases, and the train does not arrive at the station 10 for 1 hour and 20 minutes from the arrival of the train 5. On the other hand, FIG. 39 shows the result of train schedule arrangement performed by the present system, with the objective function set to the riding load uniformity.
This can be obtained by giving the amount of change in time such as the arrival density of passengers and the drop-off density with respect to time, and planning these to be uniformly distributed to each train. Specifically, it can be seen that the disorder of the train schedule is repaired in a relatively short time by delaying the operation of the train preceding the train 6 or speeding the operation of the subsequent train.

[0024]

According to the present invention, it is possible to create an optimal train in a short time with a simple configuration and logic for various train schedules and arrangements. Further, even if the plan object changes, the main logic does not need to be changed, so that the man-hours for system construction can be reduced, and a flexible system can be constructed that can easily take in various types of information.

In addition, the need for an abundant experienced person or an expert system, which has been conventionally required, is eliminated, and the maintainability is improved.

[Brief description of the drawings]

FIG. 1 is a configuration diagram of a train schedule creation system.

FIG. 2 is an explanatory diagram of planning condition setting means and the like.

FIG. 3 is a display example of a train schedule creation status.

FIG. 4 is an explanatory diagram of a minimum value search principle, a search frequency, and the like.

FIG. 5 is a diagram showing train information of an example of a non-parallel diamond diagram.

FIG. 6 is an explanatory diagram of a train running pattern.

FIG. 7 is an explanatory diagram of information on a station.

FIG. 8 is an explanatory diagram of station status and automatic operation control information.

FIG. 9 is a flowchart of a timetable planning process.

FIG. 10 is a flowchart of a timetable planning process.

FIG. 11 is a flowchart of a timetable planning process.

FIG. 12 is a flowchart of a train table creation process for a train other than a priority train.

FIG. 13 is a flowchart of a timetable planning process.

FIG. 14 is an explanatory diagram of a start / stop availability map when there is no evacuation line.

FIG. 15 is an explanatory diagram of a start / stop possibility map when there is an evacuation line.

FIG. 16 is an explanatory diagram of train assignment and registration in a start / stop availability map when there is no evacuation track;

FIG. 17 is an explanatory diagram of train assignment and registration in a start / stop availability map when there is an evacuation track;

FIG. 18 is a flowchart of a process using a travel time minimization as an objective function.

FIG. 19 is a flowchart of a process using train interval uniformity as an objective function.

FIG. 20 is a flowchart of a process using the maximum safety as an objective function.

FIG. 21 is a flowchart of a process in which adherence to arrival time is used as an objective function.

FIG. 22 is a table showing assignment of priority trains.

FIG. 23 is a diagram showing an operation state of an optimal train schedule.

FIG. 24 is a diagram illustrating an operation state when a failure occurs in the train 5 and a traffic control request is generated.

FIG. 25 is a diagram showing the train operation status at the current time.

FIG. 26 is a diagram showing rearrangement (replanning) target train information.

FIG. 27 is a diagram showing a diagram arrangement after driving arrangement.

FIG. 28 is a diagram showing train information of an example of a single-sided non-parallel diamond.

FIG. 29 is an explanatory diagram of a train running pattern.

FIG. 30 is an explanatory diagram of a train traveling pattern.

FIG. 31 is an explanatory diagram showing fault maintenance information.

FIG. 32 is an explanatory diagram of information on a station.

FIG. 33 is an explanatory diagram of a station situation.

FIG. 34 is an explanatory diagram showing assignment of failure and regular maintenance information.

FIG. 35 is a table showing assignment of priority trains.

FIG. 36 is a table showing an example of an optimal timetable;

FIG. 37 is a diagram showing train information of an example of a single-sided parallel diagram.

FIG. 38 is a diagram showing a train operation situation when a trouble of the train 6 occurs at the station 2.

FIG. 39 is a diagram showing a train operation situation when the traffic rescheduling is performed with a uniform loading load.

[Explanation of symbols]

DESCRIPTION OF SYMBOLS 1 ... Train schedule creation device, 2 ... Train schedule information input means, 3 ... Train schedule information storage means, 4 ... Plan condition setting means, 5 ... Plan condition storage means, 6 ... Train schedule creation means,
7 ... Result storage means, 8 ... Output means, 9 ... Display device, 10
… Printing device

──────────────────────────────────────────────────続 き Continuing on the front page (72) Inventor Masakazu Yahiro 5-2-1 Omika-cho, Hitachi City, Ibaraki Prefecture Inside the Hitachi, Ltd. Omika Plant (72) Inventor Yoshiyuki Sato 5-2-2 Omika-cho, Hitachi City, Ibaraki Prefecture No. 1 Hitachi, Ltd. Omika Plant (72) Inventor Isashi Tashiro 4026 Kuji-cho, Hitachi City, Ibaraki Prefecture Hitachi, Ltd. Hitachi Research Laboratory (56) References JP-A-4-135970 (JP, A) JP JP-A-3-82056 (JP, A) JP-A-63-34281 (JP, A) JP-A-59-176158 (JP, A) JP-A-55-39873 (JP, A) JP-A-4-57180 (JP, A) , A) (58) Fields investigated (Int. Cl. ⁶ , DB name) B61L 27/00 G06F 17/60

Claims (1)

(57) [Claims] 1. A plurality of trains which are subject to a train schedule creation plan, each stop station, a desired departure time of each train, an arrival time of each train, a running pattern number corresponding to each train, and a Stop conditions indicating whether to stop at each station,
Priority information, which is an identifier added to a predetermined train and indicates that an operation plan is preferentially made, travel pattern information of each train, station information including the number of tracks at each station and distance data from the preceding station, and each train Automatic driving control information and automatic driving control for automatic driving control to perform deceleration when the distance is less than a predetermined distance with other trains, equipment and trains provided in the station or train,
Train schedule information input means for inputting train schedule information including failure / maintenance information, parallel / non-parallel schedule indication information indicating whether passing is possible, and objective functions representing physical quantities to be optimized in train schedule creation Condition setting means for inputting plan conditions including information for the purpose, objective function creating means for creating an objective function from given train schedule information and planning conditions, x is a combination vector of trains, and an objective function F (x ) Which includes a train schedule creation means for obtaining a minimum value of the above , and an output means for outputting a train schedule creation result by the train schedule creation means, wherein the train schedule information input means is one type of line between stations.
Without fail, the trains that oppose each other using the evacuation line in the station premises
Face-to-face non-parallel diamond characterized by operation that must intersect
Station information for which planning is
If a delay occurs, the train at the time of the delay
Receiving an input of timetable information, the objective function creating means, the train timetable information input means
The station information for planning the non-parallel
And the train schedule information at the time of the delay
If entered, the arrival schedule of each train if there is no delay
Aiming to adhere to the arrival time to minimize the standard deviation from the fixed time
A train schedule creation device characterized by creating a function .