DESCRIPTION
APPARATUS AND METHOD FOR AUTOMATIC PREPARATION OF OPERATION-RESCHEDULING-PLAN
Field
[0001] The present invention relates to an apparatus for automatic preparation of operation-rescheduling-plan and a method for automatic preparation of operation-rescheduling-plan, the operation-rescheduling-plan being a train-schedule change plan at a time of disruption of train schedule.
Background
[0002] Delay of a train due to accidents or vehicle failures is called disruption of train schedule. At a time of the disruption of train schedule, operation rescheduling is performed to change the train schedule for recovery from the train delay. The operation rescheduling is typically performed by combining separate methods for performing the operation-rescheduling such as changing the times at which trains arrive /depart, changing the platforms where trains arrive /depart, changing the train types, e.g., from rapid ones to local ones, changing the order of train operation, adding the extra trains, and bringing the trains out of service. Conventionally, most of operation-rescheduling work is performed manually by commanders. Performing the operation rescheduling requires selecting appropriate methods from among the vast combinations of the separate operation-rescheduling methods described above. In addition, the operation rescheduling needs to be performed in a short time so as to prevent the expansion of influence of the disruption of train schedule as the trains are

running even in the middle of the operation rescheduling. Furthermore, it is necessary to perform the operation rescheduling repeatedly until the recovery from the disruption of train schedule is achieved. As described above, the manually performed operation-rescheduling work is very difficult work, and thus computers are strongly required to assist such operation-rescheduling work. [0003] A method for assisting the operation-rescheduling work includes a technique of assisting preparation of an operation-rescheduling plan in consideration of quick recovery from the disruption of train schedule and passengers' convenience, as disclosed in Patent Literature 1. For the disclosed technique, wicket machine accumulates records of passenger's input/output in an operation-rescheduling server, such that on the basis of the input/output records and the train's arrival/departure times at each station, the operation-rescheduling server simulates the number of passengers staying at each station and the passenger load factors at each station at points of time from the current time, and displays a result of the simulation together with the train schedule on an operation-rescheduling terminal.
Citation List
Patent Literature
[0004] Patent Literature 1: Japanese Patent Application
Laid-Open No. 2007-118674
Summary
Technical Problem
[0005] However, to simulate the number of passengers
staying at each station and the passenger load factors at
each station, the conventional technique described above

requires information regarding stations where each passenger get on/off the trains. In addition, the conventional technique described above requires implementation of the simulation each time the operation-rescheduling plan is prepared on an as-needed basis. Consequently, the conventional technique poses the problem of difficulty in applying in an overcrowded line having the train run, the station, and the passenger in large number, because the conventional technique bears the increased burden of calculation in such an overcrowded line. [0006] The present invention has been made in view of the above, and an object of the present invention is to provide an apparatus for automatic preparation of operation-rescheduling-plan, the apparatus being capable of preparing the operation-rescheduling plan in a shorter time in consideration of both of the quick recovery from the disruption of train schedule and the passengers' convenience even in the overcrowded line.
Solution to Problem
[0007] To solve the above problem and achieve the object, the present invention provides an apparatus for automatic preparation of operation-rescheduling-plan, the apparatus comprising: a planned train-schedule storage unit to store a planned train schedule; an actual train-schedule storage unit to store an actual train schedule; a constraint condition storage unit to store constraint conditions to be imposed in preparing an operation-rescheduling plan; a convenience calculation unit to calculate convenience of the operation-rescheduling plan for each train type on a basis of the operation-rescheduling plan and scheduled departure times or scheduled arrival times of trains in the planned train schedule; a recovery degree calculation unit

to calculate a degree of recovery from disruption of train schedule on a basis of a difference between a current time and a train-schedule-disruption convergence time obtained from a comparison of the operation-rescheduling plan with the planned train schedule; a constraint violation amount calculation unit to calculate a constraint violation amount of the operation-rescheduling plan with respect to the constraint conditions on a basis of the constraint conditions and the operation-rescheduling plan; an operation-rescheduling-plan preparing unit to prepare the operation-rescheduling plan on a basis of an evaluation value defined using the convenience, the degree of recovery, and the constraint violation amount; and an operation-rescheduling-plan storage unit to store the operation-rescheduling plan, wherein the operation-rescheduling-plan preparing unit corrects an initial plan of the operation-rescheduling plan in accordance with a predetermined correction method to prepare a candidate operation-rescheduling plan, when an evaluation value of the candidate operation-rescheduling plan is improved in comparison with an evaluation value of the initial plan of the operation-rescheduling plan, the operation-rescheduling-plan preparing unit corrects the candidate operation-rescheduling plan in accordance with the correction method to prepare a next candidate operation-rescheduling plan, and repeats a process of correcting the next candidate operation-rescheduling plan in accordance with the correction method as far as an evaluation value of the next candidate operation-rescheduling plan is improved in comparison with the evaluation value of the candidate operation-rescheduling plan, and when the evaluation value of the next candidate operation-rescheduling plan is not improved in comparison with the evaluation value of the

candidate operation-rescheduling plan, the operation-rescheduling-plan preparing unit employs the candidate operation-rescheduling plan as the operation-rescheduling plan.
Advantageous Effects of Invention
[0008] The present invention achieves an effect of preparing the operation-rescheduling plan in the shorter time in consideration of both of the quick recovery from the disruption of train schedule and the passengers' convenience in the overcrowded line.
Brief Description of Drawings
[0009] FIG. 1 is a block diagram illustrating a configuration example of an apparatus for automatic preparation of operation-rescheduling-plan according to a first embodiment.
FIG. 2 is a diagram illustrating an example of a hardware configuration of the apparatus for automatic preparation of operation-rescheduling-plan according to the first embodiment.
FIG. 3 is a flowchart illustrating an example of a method for automatic preparation of operation-rescheduling-plan, the method being used in the apparatus for automatic preparation of operation-rescheduling-plan according to the first embodiment.
FIG. 4 is a block diagram illustrating a configuration example of an apparatus for automatic preparation of operation-rescheduling-plan according to a second embodiment.
FIG. 5 is a block diagram illustrating a configuration example of an apparatus for automatic preparation of operation-rescheduling-plan according to a third embodiment.

FIG. 6 is a block diagram illustrating a configuration example of an apparatus for automatic preparation of operation-rescheduling-plan according to a fourth embodiment.
FIG. 7 is a flowchart illustrating an example of a method for automatic preparation of operation-rescheduling-plan, the method being used in the operation-rescheduling-plan automatic preparation apparatus according to the fourth embodiment.
FIG. 8 is a block diagram illustrating a configuration example of an apparatus for automatic preparation of operation-rescheduling-plan according to a fifth embodiment.
FIG. 9 is a diagram illustrating an example of a change information setting screen which is a change information setting unit in the apparatus for automatic preparation of operation-rescheduling-plan according to the fifth embodiment.
FIG. 10 is a flowchart illustrating an example of a method for automatic preparation of operation-rescheduling-plan, the method being used in the apparatus for automatic preparation of operation-rescheduling-plan according to the fifth embodiment.
Description of Embodiments
[0010] Hereinbelow, an apparatus for automatic preparation of operation-rescheduling-plan (hereinafter referred to as "operation-rescheduling-plan automatic preparation apparatus") and a method for automatic preparation of operation-rescheduling-plan (hereinafter referred to as "an operation-rescheduling-plan automatic preparation method") according to each of embodiments of the present invention will be described in detail based on the drawings. The invention is not limited to the

embodiments.
[0011] First Embodiment.
FIG. 1 is a block diagram illustrating a configuration example of an operation-rescheduling-plan automatic preparation apparatus according to the present embodiment. As illustrated in FIG. 1, the operation-rescheduling-plan automatic preparation apparatus according to the present embodiment includes a planned train-schedule storage unit 1, an actual train-schedule storage unit 2, a constraint condition storage unit 3, a convenience calculation unit 4, a recovery degree calculation unit 5, a constraint violation amount calculation unit 6, an operation-rescheduling- plan preparing unit 7, and an operation-rescheduling- plan storage unit 8.
[0012] The planned train-schedule storage unit 1 stores a planned train schedule which is a train schedule planned in advance. Specifically, the planned train-schedule storage unit 1 stores a planned train-schedule which is operation data including: scheduled arrival/departure times at which each train is scheduled to arrive at /depart from each station; scheduled arrival/departure platforms of each station where each train is scheduled to arrive /depart; a train type of each train; a train number of each train; and a vehicle number of each vehicle of each train. The scheduled arrival/departure times used herein means a scheduled arrival time at which the train is scheduled to arrive and a scheduled departure time at which the train is scheduled to depart. In addition, the scheduled arrival/departure platforms mean a scheduled arrival platform where the train is scheduled to arrive and a scheduled departure platform where the train is scheduled to depart.
[0013] The actual train-schedule storage unit 2 stores

an actual train schedule which is a train schedule prepared from results of actual operations of each train. Specifically, the actual train-schedule storage unit 2 stores an actual train-schedule which is actual operation data from the past to a current time. The actual operation data includes: arrival/departure times at which each train arrives at / departs from each station; arrival/departure platforms of each station where each train arrives / departs; a train type of each train, a train number of each train, and a vehicle number of each vehicle of each train. The arrival/departure times used herein means a time at which the train arrives and a time at which the train departs. In addition, the arrival/departure platforms mean a platform where the train arrives and a platform where the train departs.
[0014] The constraint condition storage unit 3 stores constraint conditions to be imposed in preparing an operation-rescheduling plan which is a train-schedule change plan at a time of disruption of train schedule. The constraint condition storage unit 3 stores the constraint conditions. The constraint conditions are: for example, minimum train-stop times for each train type and for each station; minimum turn-back times for each train type and for each terminal station; minimum train-running times for each direction and for each train type from each station to a next station thereof; a minimum departure time interval between a preceding train and a following train for each station, and a minimum arrival time interval between a preceding train and a following train for each station. In detail, the constraint conditions are as follows: a train of train type "e" should have a stop time Tst0p(e, s) at a station "s"; the train of train type "e" should have a turn-back time "Tretum(e, send) " at a terminal station "send";

the train of train type "e" bound for a direction "d" should have a running time "Trun(d, e, s, s')" required from the station "s" to a next station "s'" thereof; a departure time at which a preceding train departs from the station "s" and a departure time at which a next train following the preceding train departs from the station "s" should provide a departure time interval "Tdeparture (s) " therebetween; and an arrival time at which a preceding train arrives at the station "s" and an arrival time at which a next train following the preceding train arrives at the station "s" should provide an arrival time interval "Tarrlval (s) " therebetween. Here, the direction "d" indicates a direction of advancement of a train, for example, an inbound direction or an outbound direction. For each item indicating the constraint condition, a specific numerical value is given to a parameter of the constraint condition. For the stop time "Tstop(e, s)", for example, stop time data is given to the train type "e" and the station "s", which are parameters.
[0015] The convenience calculation unit 4 calculates convenience of an operation-rescheduling plan on the basis of the scheduled departure times or the scheduled arrival times of the trains in the planned train schedule and the operation-rescheduling plan. A known method for calculating convenience provided to passengers is a method for simulating a passenger load factor of the train and the number of passengers staying at each station, as disclosed in Patent Literature 1. However, since this known method requires implementation of the simulation each time a candidate of an operation-rescheduling plan is prepared on an as-needed basis, a burden of the calculation increases in the overcrowded line. On the other hand, an operation method for allowing passengers to readily feel convenient,

by other than the simulation of the passenger load factor of the train and the number of passengers staying at each station includes an equal-interval operation of allowing trains to depart at the same time intervals. The equal-interval operation has an advantage that the passenger load factor is uniformed. If departure intervals at which trains depart are too short, the train would stop between stations as the train can get too close to a preceding train. This can make passengers feel anxious. In contrast, the uniform departure interval makes it possible to suppress departures of trains at short intervals. It is known that passengers increasingly feel dissatisfied as a time during which the passengers wait for the train at a departure station increases. The uniform departure interval is advantageous because accumulation of the dissatisfaction of passengers is suppressed. When considering the equal-interval operation, it is more preferable to perform the equal-interval operation for each train type than to perform the equal-interval operation for all trains. This is because types of trains used by passengers are known beforehand in many cases. In addition, depending on a time of day, it may be preferable to shorten the departure interval because of many passengers, or to lengthen the departure interval because of few passengers. For example, usually, it is preferable to shorten the departure interval during rush hours in the morning or evening because there are many passengers, and it is preferable to lengthen the departure interval in the daytime because there are few passengers. As described above, it is preferable to adjust the departure interval depending the time of day. Accordingly, in the present embodiment, an average departure time interval of train for each of directions, train types, stations, and times of day,

is calculated on the basis of the scheduled departure times of trains in the planned train schedule, and then the convenience is defined as being the sum of amounts of shift by which the departure time intervals of the train for each of directions, train types, stations, and times of day in an operation-rescheduling plan are shifted from the average departure time interval.
[0016] A detailed description of the convenience is as follows. When an average departure time interval for a direction "d", a train type "e", a train station "s", and a time of day "p" in the planned train schedule is denoted by "Taverage (d, e, s, p)", a next train following a train "r" of the train type "e" at the station "s" in the operation-rescheduling plan is denoted by "Rnext(r, e, s)", a departure time of the train "r" of the train type "e" at the station "s" in the operation-rescheduling plan is denoted by "tdeparture (r, e, s)", a set of trains is denoted by "R", a set of train types is denoted by "E", a set of stations is denoted by "S", and a set of times of day is denoted by "P", convenience "Vconvenience" is defined as follows.
V convenience ^eeE,rGR,seS,pGP ^departure \ -t^-next \ r , e, S J , e, S ) ~ ^departure \^-f S, SJ - 1 average [Q-r S, S, PJI ... l-LJ
In other words, an absolute value of a difference between the departure time interval " (tdeparture (Rnext (r, e, s), e, s) - tdeparture (r, e, s))" in the operation-rescheduling plan and the average departure time interval "Taverage (d, e, s, p)" obtained from the planned train schedule is defined as an amount of shift by which the departure time interval in the operation-rescheduling plan is shifted from the average departure time interval. At that time, the difference between " (tdeparture (Rnext (r, e, s), e, s) -tdeparture (r, e, s))" and "TaVerage (d, e, s, p)" is executed for

"r" with which d(r) is the same as the argument "d" of Taverage, and "p" with which "tdeparture (r, e, s)" falls within a range of "p". The time of day "p" is indicated, for example, as "from 10 o'clock to 12 o'clock." As can be seen from formula (1) above, the larger the value of "Vconvenience" is, the lower the convenience is.
[0017] Although the convenience "Vconvenience" is defined by the departure time interval in the above formula (1), the convenience "Vconvenience" may be defined by the arrival time interval. In other words, an average arrival time interval of train for each of directions, train types, stations, and times of day, is calculated on the basis of the scheduled arrival times of trains in the planned train schedule, and then the convenience is defined as being the sum of amounts of shift by which the arrival time intervals of the train for each of directions, train types, stations, and times of day in the operation-rescheduling plan are shifted from the average arrival time interval.
[0018] The recovery degree calculation unit 5 calculates the degree of recovery from the disruption of train schedule on the basis of a train-schedule-disruption convergence time obtained from a comparison of the operation-rescheduling plan with the planned train schedule. The train-schedule-disruption convergence time "Tconverge" as used herein is defined as a point of time from which the planned train-schedule and the operation-rescheduling plan match. Specifically, from the train-schedule-disruption convergence time "TCOnverge", the planned train schedule matches the operation-rescheduling plan in terms of the scheduled arrival/departure time of each train at each station, the scheduled arrival/departure platform for each train at each station, the train type of each train, the train number of each train, and the vehicle number of each

vehicle of each train. The scheduled arrival/departure times in the operation-rescheduling plan and the scheduled arrival/departure times in the planned train schedule should be construed to match when a difference in scheduled arrival/departure time between the operation-rescheduling plan and the planned train schedule falls within a preset tolerance time period. The degree of recovery "VreCovery" is defined as follows using the train-schedule-disruption convergence time "Tconverge" and the current time "Tcurrent"-
''recovery -^ converge — -^ current ... \^j
According to the definition, the closer to the train-schedule-disruption convergence time "Tconverge" the current time "Tcurrent" is, the lower the degree of recovery "VreCovery" is.
[0019] On the basis of the constraint conditions stored in the constraint condition storage unit 3 and the operation-rescheduling plan prepared by the operation-rescheduling-plan preparing unit 7, the constraint violation amount calculation unit 6 calculates constraint violation amounts of the operation-rescheduling plan with respect to the constraint conditions. In other words, the constraint violation amount is an amount indicating a degree to which the operation-rescheduling plan violates the constraint conditions. The constraint violation amount is calculated as follows.
[0020] When the train type of the train "r" and a time at which the train "r" arrives at the station "s" in the operation-rescheduling plan are denoted by "e(r)" and "tarrivai (r, e(r), s)", respectively, a constraint violation amount of a minimum stop time is represented as follows. max(0, Tstop(e(r), s) - tdeparture (r, e(r), s) + tarrlvai (r, e(r), s) )
When "a" is equal to or more than "b" (a > b), "max(a,

b)" is equal to "a" ( max (a, b) = a), and when "a" is less than "b" (a < b), "max(a, b)" is equal to "b" ( "max (a, b) "= b) . In addition, "Tst0p (e (r) , s)" is a constraint condition regarding the minimum stop time stored in the constraint condition storage unit 3. Therefore, the sum "Vst0p" of the constraint violation amounts of the stop time is represented as follows.
Vstop = 2rGRfSGg max ( 0, Tstop (e (r) , s) - tdeparture (r, e (r) , s) + tarrivai(r, e(r), s)) ... (3)
[0021] Similarly, when a terminal station of the train "r" and a turn-back train which is the train "r" turned back at the terminal station in the operation-rescheduling plan are denoted by "Send(r)" and "Rreturn (r) ", respectively, the sum "Vreturn" of the constraint violation amounts of the minimum turn-back time is represented as follows.
^return = 2reR max ( 0 , Treturn ( S ( r ) , Send(r)) ~~
^departure l^return \^-) r S \ -t^-return \1-) ) , oend \^-)) ~*~ ^arrival \^-f S \S-) ,
Send(r))) ... (4)
where "Treturn (e (r) , Send(r))" is a constraint condition regarding the minimum turn-back time stored in the constraint condition storage unit 3.
[0022] Similarly, when the direction of the train "r" and a next stop at which the train "r" stops after the station "s" in the operation-rescheduling plan are denoted by "d(r)" and "Snext(r, s)", respectively, the sum "Vrun" of the constraint violation amounts of the required minimum running time is represented as follows.
Vrun = SrGRfSGS max(0, Trun(d(r), e(r), s, Snext(r, s)) -
t arrival (r/ e (r) , Snext (r/ S) ) + tdeparture (r/ e(r), S)) ... (5)
where "Trun (d (r) , e(r), s, Snext(r, s))" is a constraint condition regarding the required minimum running time stored in the constraint condition storage unit 3.

[0023] Similarly, when a train following the train "r" in the operation-rescheduling plan is denoted by "Rnext(r)", the sum "Vdeparture" of the constraint violation amounts of the minimum departure time interval and the sum "Varrlvai" of the constraint violation amounts of the minimum arrival time interval are represented as follows, respectively.
"departure ^reR,seS lLiaX ^U, J-departure \SJ — ^departure \ J^-next \^-) r
e (Rnext (r) ) , S) + tdeparture (r, e(r), S)) ... (6)
^arrival = 2rGRfSGg ITISX (0, Tarrivai ( S) _ t arrival (Rnext ( r) I
e (Rnext (r) ) , s) + tarrivai(r, e(r), s)) ... (7)
where "Tdeparture (s) " is a constraint condition regarding the minimum departure time interval stored in the constraint condition storage unit 3 and "Tarrlvai (s) " is a constraint condition regarding the minimum arrival time interval stored in the constraint condition storage unit 3. [0024] Using these constraint violation amounts, the constraint violation amount calculation unit 6 calculates a constraint violation amount "VCOnstraint" as follows.
"constraint Vstop ~*~ "return ~*~ V run ~r Vc[eparture ~*~ ^arrival ...
(8)
[0025] The operation-rescheduling plan preparing unit 7 prepares an operation-rescheduling plan at the time of the disruption of train schedule on the basis of the planned train schedule stored in the planned train-schedule storage unit 1, the actual train schedule stored in the actual train-schedule storage unit 2, the convenience calculated by the convenience calculation unit 4, the degree of recovery calculated by the recovery degree calculation unit 5, and the constraint violation amount calculated by the constraint violation amount calculation unit 6. Details of the preparation of the operation-rescheduling plan will be described later.

[0026] The operation-rescheduling plan storage unit 8 stores the operation-rescheduling plan prepared by the operation-rescheduling plan preparing unit 7. The operation-rescheduling plan is post-rescheduling operation data which includes scheduled arrival/departure times at which each train arrives at/departs from each station, scheduled arrival/departure platforms of each station where each train arrives/departs, a train type of each train, a train number of each train, and a vehicle number of each vehicle of each train.
[0027] FIG. 2 is a diagram illustrating an example of a hardware configuration of the operation-rescheduling-plan automatic preparation apparatus according to the present embodiment. The operation-rescheduling-plan automatic preparation apparatus according to the present embodiment includes a processor 20, a memory 21, and an input/output device 22, and is implemented by a computer which operates in accordance with a control program stored in the memory 21. The control program is a program which causes the operation-rescheduling-plan automatic preparation apparatus to execute an operation-rescheduling-plan automatic preparation method described later. The functional configuration illustrated in FIG. 1 corresponds to the hardware configuration as follows. The convenience calculation unit 4, the recovery degree calculation unit 5, the constraint violation amount calculation unit 6, and the operation-rescheduling-plan preparing unit 7 are implemented by the processor 20 and the memory 21. The planned train-schedule storage unit 1, the actual train schedule storage unit 2, the constraint condition storage unit 3, and the operation-rescheduling-plan storage unit 8 are implemented by the memory 21. These storage units may be implemented by a storage device other than the memory 21.

The input/output device 22 is an input/output interface such as a keyboard, a mouse, and a display device.
[0028] Next, the operation-rescheduling-plan automatic preparation method used in the operation-rescheduling-plan automatic preparation apparatus according to the present embodiment will be described with reference to FIGS. 1 to 3. FIG. 3 is a flowchart illustrating an example of the operation-rescheduling-plan automatic preparation method used in the operation-rescheduling-plan automatic preparation apparatus according to the present embodiment.
[0029] The operation-rescheduling- plan preparing unit 7 acquires the planned timetable stored in the planned train-schedule storage unit 1 and the actual train-schedule stored in the actual train-schedule storage unit 2 (Step ST101), and prepares a candidate operation-rescheduling plan on the basis of the acquired planned train schedule and actual train schedule (Step ST102). In Step ST102, when the candidate operation-rescheduling plan is prepared for the first time, the operation-rescheduling-plan preparing unit 7 regards an initial plan of an operation-rescheduling plan as the candidate operation-rescheduling plan. The initial plan of the operation-rescheduling plan is prepared by the operation-rescheduling-plan preparing unit 7 in accordance with a predetermined preparation method. The preparation method may be any selected method. In Step ST102, when the candidate operation-rescheduling plan is prepared for the second or more time, the operation-rescheduling-plan preparing unit 7 corrects a current operation-rescheduling plan to thereby prepare the candidate operation-rescheduling plan. The current operation-rescheduling plan is one candidate operation-rescheduling plan which has been previously prepared and has an improved evaluation value. The operation-

rescheduling plan may be corrected in accordance with a predetermined correction method, but the correction method is not limited to a specific correction method. Examples of the correction method includes a method that shifts scheduled arrival/departure times by certain seconds, exchanges scheduled arrival/departure platforms between trains, or exchanges a turn-back train for another train. A plurality of the candidate operation-rescheduling plans may be prepared. The operation-rescheduling-plan preparing unit 7 transmits the prepared candidate operation-rescheduling plan to each of the convenience calculation unit 4, the recovery degree calculation unit 5, and the constraint violation amount calculation unit 6 (Step ST103). [0030] The convenience calculation unit 4 acquires the planned train schedule stored in the planned train-schedule storage unit 1 and the candidate operation-rescheduling plan transmitted from the operation-rescheduling-plan preparing unit 7 (Step ST104), calculates convenience on the basis of the acquired planned train schedule and candidate operation-rescheduling plan (Step ST105), and transmits the calculated convenience to the operation-rescheduling-plan preparing unit 7 (Step ST106). In Step ST105, the convenience calculation unit 4 calculates the average departure time interval of the train for each of directions, train types, stations, and times of day, on the basis of the scheduled departure times of trains in the planned train schedule, and calculates the convenience that is the sum of amounts of shift by which the departure time intervals of the train for each of directions, train types, stations, and times of day in the candidate operation-rescheduling plan are shifted from the average departure time interval. Alternatively, the convenience calculation unit 4 calculates the average arrival time interval of the

train for each of directions, train types, stations, and times of day, on the basis of the scheduled arrival times of trains in the planned train schedule, and calculates the convenience that is the sum of amounts of shift by which the arrival time intervals of the train for each of directions, train types, stations, and times of day in the candidate operation-rescheduling plan are shifted from the average arrival time interval.
[0031] The recovery degree calculation unit 5 acquires the planned train schedule stored in the planned train-schedule storage unit 1 and the candidate operation-rescheduling plan transmitted from the operation-rescheduling-plan preparing unit 7 (Step ST107), calculates the degree of recovery from the disruption of train schedule on the basis of the acquired planned train schedule and candidate operation-rescheduling plan (Step ST108), and transmits the calculated degree of recovery to the operation-rescheduling-plan preparing unit 7 (Step ST109). In Step ST108, the recovery degree calculation unit 5 calculates, in accordance with formula (2) above, the degree of recovery from the disruption of train schedule on the basis of the train-schedule-disruption convergence time obtained from comparison of the candidate operation-rescheduling plan with the planned train schedule. [0032] The constraint violation amount calculation unit 6 acquires the constraint conditions stored in the constraint condition storage unit 3 and the candidate operation-rescheduling plan transmitted from the operation-rescheduling-plan preparing unit 7 (Step ST110), calculates the constraint violation amount on the basis of the acquired constraint conditions and candidate operation-rescheduling plan (Step ST111), and transmits the calculated constraint violation amount to the operation-

rescheduling-plan preparing unit 7 (Step ST112). In Step ST111, the constraint violation amount calculation unit 6 calculates the constraint violation amount in accordance with formulae (3) to (8) above.
[0033] The operation-rescheduling-plan preparing unit 7 acquires the convenience transmitted from the convenience calculation unit 4, the degree of recovery transmitted from the recovery degree calculation unit 5, and the constraint violation amount transmitted from the constraint violation amount calculation unit 6 (Step ST113), and calculates an evaluation value of the candidate operation-rescheduling plan defined using the convenience, the degree of recovery, and the constraint violation amount (Step ST114). The evaluation value "VreScheduie" of the candidate operation-rescheduling plan is defined, for example, as a weighted sum of the convenience "Vconvenience"/ the degree of recovery "VreCovery"/ and the constraint violation amount "Vconstraint" and is given by the following formula.
^reschedule ^convenience v convenience ~*~ ^recovery v recovery ~*~ ^constraint "constraint ... \^j
where "wconvenience"/ "wreCovery"/ and "wconstraint" represent weights of the convenience, the degree of recovery, and the constraint violation amount, respectively, and are preset positive values. Since the convenience "Vconvenience" given by formula (1) includes an absolute value, and the constraint violation amount "Vconstraint" given by formulae (3) to (8) includes "max", the evaluation value "VreScheduie" given as the weighted sum as indicated by formula (9) is non-linear. However, it is known that a function defined by the sum of functions including an absolute value or "max" can be expressed as the sum of a linear objective function and a linear constraint condition through transformation. In other words, an optimization problem based on the

evaluation value "VreScheduie" given by formula (9) can be expressed as a linear programming problem. Consequently, it is possible to apply a high-speed technique such as an interior-point method when performing optimization in the linear programming problem.
[0034] Next, the operation-rescheduling-plan preparing unit 7 determines whether the evaluation value of the candidate operation-rescheduling plan has been improved
(Step ST115). When an evaluation value of the candidate operation-rescheduling plan is calculated for the first time, the operation-rescheduling-plan preparing unit 7 determines that the evaluation value of the candidate operation-rescheduling plan has been improved. When the evaluation value of the candidate operation-rescheduling plan is calculated for the second or more time, the operation-rescheduling-plan preparing unit 7 determines whether the evaluation value of the candidate operation-rescheduling plan has been improved by comparing an evaluation value of the current operation-rescheduling plan with the evaluation value of the candidate operation-rescheduling plan which has just been calculated. The evaluation value of the current operation-rescheduling plan is one candidate operation-rescheduling plan which has been previously prepared and has an improved evaluation value. In a case where the evaluation value of the candidate operation-rescheduling plan is calculated by using formula
(9) above, the operation-rescheduling-plan preparing unit 7 determines that the evaluation value of the candidate operation-rescheduling plan has been improved when the evaluation value of the candidate operation-rescheduling plan has been decreased. When there are multiple prepared candidate operation-rescheduling plans, the operation-rescheduling-plan preparing unit 7 determines that the

evaluation value has been improved when the evaluation value of one of the candidate operation-rescheduling plans has been improved. When the determination indicates that the evaluation value of the candidate operation-rescheduling plan is not improved (Step ST115, No), the operation-rescheduling-plan preparing unit 7 stores the current operation-rescheduling plan in the operation-rescheduling-plan storage unit 8 (Step ST117), and terminates the operation-rescheduling-plan automatic preparation process. When the determination indicates that the evaluation value of the candidate operation-rescheduling plan is improved (Step ST115, Yes), the operation-rescheduling plan-preparing unit 7 employs the candidate operation-rescheduling plan as a current operation-rescheduling plan (Step ST116), and the process returns to Step ST102. In ST102, the operation-rescheduling-plan preparing unit 7 prepares a next candidate operation-rescheduling plan. When there are multiple candidate operation-rescheduling plans having improved evaluation values, any one of them may be employed as a current operation-rescheduling plan, and, for example, a candidate operation-rescheduling plan having the most improved evaluation value may be employed as a current operation-rescheduling plan.
[0035] As described above, the operation-rescheduling-plan preparing unit 7 calculates the evaluation value of the candidate operation-rescheduling plan defined using the convenience, the degree of recovery, and the constraint violation amount, compares the calculated evaluation value of the candidate operation-rescheduling plan with the evaluation value of the current operation-rescheduling plan. Then, in a case where the calculated evaluation value of the candidate operation-rescheduling plan has been improved

in comparison with the evaluation value of the current operation-rescheduling plan, the operation-rescheduling-plan preparing unit 7 employs the candidate operation-rescheduling plan as a current operation-rescheduling plan. In a case where the calculated evaluation value of the candidate operation-rescheduling plan has not been improved in comparison with the evaluation value of the current operation-rescheduling plan, the operation-rescheduling-plan preparing unit 7 does not update the current operation-rescheduling plan.
[0036] In the present embodiment, as described above, the convenience calculation unit 4 calculates the average departure or arrival time interval of the train for each of directions, train types, stations, and times of day, on the basis of the scheduled departure times or scheduled arrival times of the trains in the planned train schedule, and then calculates the convenience as the sum of amounts of shift by which the departure time intervals or arrival time intervals of the train for each of directions, train types, stations, and times of day in the operation-rescheduling plan are shifted from the average departure time interval or the average arrival time interval. In addition, the operation-rescheduling-plan preparing unit 7 calculates the evaluation value of the candidate operation-rescheduling plan defined using the convenience, the degree of recovery, and the constraint violation amount, and, when the calculated evaluation value of the candidate operation-rescheduling plan is improved in comparison with the evaluation value of the current operation-rescheduling plan, the operation-rescheduling-plan preparing unit 7 employs the candidate operation-rescheduling plan as a current operation-rescheduling plan to thereby update the current operation-rescheduling plan, and when the calculated

evaluation value of the candidate operation-rescheduling plan is not improved in comparison with the evaluation value of the current operation-rescheduling plan, the operation-rescheduling-plan preparing unit 7 does not update the current operation-rescheduling plan. Since the convenience can be calculated without performing simulation of trains with passengers onboard each time an operation-rescheduling plan is prepared, it is possible to prepare an operation-rescheduling plan in a shorter time in consideration of both of quick recovery from the disruption of train schedule and the passengers' convenience even in the overcrowded line.
[0037] Although the convenience is defined by the sum of amounts of shift of the departure time intervals from the average departure time interval in the present embodiment, the convenience is not limited thereto. As one example, the convenience may be the square root of the sum of the squares of amounts of shift of the departure time intervals from the average departure time interval. As another example, the convenience may be a partial sum of amounts of shift of the departure time intervals from the average departure time interval. Specifically, the convenience can be defined as the partial sum of amounts of shift of the departure time intervals from the average departure time interval, the partial sum being obtained by adding up only the amounts of shift each of which is equal to or more than a predetermined value without adding up the amounts of shift each of which is less than the predetermined value. Alternatively, the convenience can also be defined without using the amounts of shift of the departure time intervals from the average departure time interval. In general, the convenience may be defined for each train type on the basis of the scheduled arrival times or scheduled departure times

of the trains in the planned train schedule and an operation-rescheduling plan. In that case, the operation-rescheduling plan is prepared for each train type in accordance with the flowchart in FIG. 3. Although, in the present embodiment, the current operation-rescheduling plan will be updated as far as the evaluation value is improved, the manner of updating the operation-rescheduling plan is not limited thereto. The update may be terminated when the number of times of the update reaches a predetermined number, and the current operation-rescheduling plan may be stored in the operation-rescheduling-plan storage unit 8. Alternatively, the update may be terminated when the evaluation value decreases to a predetermined value and the current operation-rescheduling plan may be stored in the operation-rescheduling-plan storage unit 8. The same holds for a case where the convenience is defined by the sum of the amounts of shift of the arrival time intervals from the average arrival time interval.
[0038] Second Embodiment.
FIG. 4 is a block diagram illustrating a configuration example of an operation-rescheduling-plan automatic preparation apparatus according to the present embodiment. In FIG. 4, the same reference signs are used to denote the same components as those in the first embodiment illustrated in FIG. 1, and detailed descriptions of the same components will be omitted.
[0039] The operation-rescheduling-plan automatic preparation apparatus according to the present embodiment has the same device configuration as the first embodiment illustrated in FIG. 1, except that the operation-rescheduling-plan preparing unit 7 acquires an operation-rescheduling plan from the operation-rescheduling-plan storage unit 8.

[0040] Next, an operation-rescheduling-plan automatic preparation method used in the operation-rescheduling-plan automatic preparation apparatus according to the present embodiment will be described with reference to FIGS. 4 and 3. Although FIG. 3 is the flowchart illustrating the example of the operation-rescheduling-plan automatic preparation method according to the first embodiment, the second embodiment is described with reference to FIG. 3 because the operation-rescheduling-plan automatic preparation method in the present embodiment is carried out in accordance with the flowchart illustrated in FIG. 3 except for the details of Step ST102.
[0041] In the flowchart in FIG. 3, Steps ST101 and ST103 to ST117 are performed in the same manner as that in the present embodiment and the first embodiment. However, Step ST102 in the present embodiment is performed in a different manner from that in the first embodiment.
[0042] In Step ST102 of the first embodiment, when the candidate operation-rescheduling plan is prepared for the first time, the operation-rescheduling-plan preparing unit 7 prepares the initial plan of the operation-rescheduling plan and regards the initial plan of the operation-rescheduling plan as the candidate operation-rescheduling plan, and when the candidate operation-rescheduling plan is prepared for the second or more time, the operation-rescheduling-plan preparing unit 7 employs a candidate operation-rescheduling plan previously prepared, as a current operation-rescheduling plan and then corrects the current operation-rescheduling plan to thereby prepare the candidate operation-rescheduling plan.
[0043] In contrast, in Step ST102 of the present embodiment, when a candidate operation-rescheduling plan is prepared for the first time, the operation-rescheduling-

plan preparing unit 7 acquires an operation-rescheduling plan whose preparation time is latest, stored in the operation-rescheduling-plan storage unit 8, and regards the operation-rescheduling plan as a candidate operation-rescheduling plan. On the other hand, when the candidate operation-rescheduling plan, the operation-rescheduling-plan preparing unit 7 corrects the current operation-rescheduling plan to thereby prepare the candidate operation-rescheduling plan in the same manner as that in the first embodiment.
[0044] After preparing an operation-rescheduling plan in accordance with the flowchart in FIG. 3, the operation-rescheduling-plan preparing unit 7 stores the prepared operation-rescheduling plan in the operation-rescheduling-plan storage unit 8. In storing the prepared operation-rescheduling plan in the operation-rescheduling-plan storage unit 8, the operation-rescheduling-plan preparing unit 7 attaches information regarding the preparation time at which the operation-rescheduling plan is prepared, to the prepared operation-rescheduling plan. In the present embodiment, one or more operation-rescheduling plans prepared in the past are stored in the operation-rescheduling plan storage unit 8 together with the corresponding preparation times. In a case where no operation-rescheduling plan is stored in the operation-rescheduling-plan storage unit 8, the operation-rescheduling-plan preparing unit 7 prepares an initial plan of the operation-rescheduling plan in the same manner as that in the first embodiment.
[0045] As described above, in addition to the configuration of the first embodiment, the present embodiment provides the configuration wherein, when the candidate operation-rescheduling plan is prepared for the

first time, the operation-rescheduling-plan preparing unit 7 acquires the operation-rescheduling plan prepared at the latest preparation time, from the operation-rescheduling-plan storage unit 8 and regards the operation-rescheduling plan as a candidate operation-rescheduling plan. Since the latest operation-rescheduling plan previously prepared can be used in repeatedly preparing the operation-rescheduling plan until recovery from the disruption of train schedule is achieved, it is possible to shorten the time required to prepare the initial plan of the operation-rescheduling plan. [0046] The other configurations, operations, and effects of the present embodiment are the same as those of the first embodiment. [0047] Third Embodiment.
FIG. 5 is a block diagram illustrating a configuration example of an operation-rescheduling-plan automatic preparation apparatus according to the present embodiment. In FIG. 5, the same reference signs are used to denote the same components as those in the first embodiment illustrated in FIG. 1, and detailed descriptions of the same components will be omitted.
[0048] The operation-rescheduling-plan automatic preparation apparatus according to the present embodiment includes, in addition to the configuration illustrated in FIG. 1, a train operation prediction unit 9 which predicts a condition of train-schedule disruption from a current time on the basis of the planned train schedule and the actual train schedule. The train operation prediction unit 9 is implemented by the processor 20 and the memory 21 illustrated in FIG. 2.
[0049] Next, an operation-rescheduling-plan automatic preparation method used in the operation-rescheduling-plan automatic preparation apparatus according to the present

embodiment will be described with reference to FIGS. 5 and 3. Although FIG. 3 is a flowchart illustrating an example of the operation-rescheduling-plan automatic preparation method according to the first embodiment, the third embodiment is described with reference to FIG. 3 because the operation-rescheduling-plan automatic preparation method of the present embodiment is carried out in accordance with the flowchart illustrated in FIG. 3 except for details in the process in Step ST102.
[0050] In the flowchart in FIG. 3, Steps ST101 and ST103 to ST117 in the third embodiment are performed in the same manner as that in the first embodiment. However, Step ST102 in the present embodiment is performed in a different manner from that in the first embodiment.
[0051] In Step ST102 of the first embodiment, when the candidate operation-rescheduling plan is prepared for the first time, the operation-rescheduling-plan preparing unit 7 prepares an initial plan of the operation-rescheduling plan and regards the initial plan of the operation-rescheduling plan as the candidate operation-rescheduling plan, and when the candidate operation-rescheduling plan is prepared for the second or more time, the operation-rescheduling-plan preparing unit 7 employs a candidate operation-rescheduling plan previously prepared, as a current operation-rescheduling plan and then corrects the current operation-rescheduling plan to thereby prepare the candidate operation-rescheduling plan.
[0052] In contrast, in Step ST102 of the present embodiment, when a candidate operation-rescheduling plan is prepared for the first time, the operation-rescheduling-plan preparing unit 7 regards a result of prediction performed by the train operation prediction unit 9 as an initial plan of the operation-rescheduling plan, and

regards the initial plan of the operation-rescheduling plan as the candidate operation-rescheduling plan. On the basis of the planned train schedule and the actual train schedule, the train operation prediction unit 9 predicts the condition of train-schedule disruption from the current time, that is, predicts arrival/departure times at which each train arrives at/departs from each station, arrival/departure platforms of each station where each train arrives / departs, a train type of each train, a train number of each train, and a vehicle number of each vehicle of each train.
[0053] The train operation prediction unit 9 predicts the condition of train-schedule disruption in accordance with a predetermined prediction method. The prediction method is, for example, a train operation simulation in which an equation of motion is set up for each train on the basis of the actual train schedule, gradients of railways, limited speeds on the railways, and
acceleration/deceleration of each train. On the other hand, when the candidate operation-rescheduling plan is prepared for the second or more time, the operation-rescheduling-plan preparing unit 7 corrects the current operation-rescheduling plan to thereby prepare the candidate operation-rescheduling plan in the same manner as that in the first embodiment.
[0054] As described above, in addition to the configuration of the first embodiment, the present embodiment provides the train operation prediction unit 9 which predicts the condition of train-schedule disruption from the current time on the basis of the planned train schedule and the actual train schedule. It is thus possible to prepare the initial plan of the operation-rescheduling plan with the less constraint violation amount

reflecting the running condition of the train at the time of the disruption of train schedule.
[0055] The other configurations, operations, and effects of the present embodiment are the same as those of the first embodiment.
[0056] Fourth Embodiment.
FIG. 6 is a block diagram illustrating a configuration example of an operation-rescheduling-plan automatic preparation apparatus according to the present embodiment. In FIG. 6, the same reference signs are used to denote the same components as those in the first embodiment illustrated in FIG. 1, and detailed descriptions of the same components will be omitted.
[0057] In addition to the configuration illustrated in FIG. 1, the operation-rescheduling-plan automatic preparation apparatus according to the present embodiment includes a passenger movement time storage unit 10. The passenger movement time storage unit 10 stores a passenger movement time which is a period of time during which passengers move when a train platform is changed at each station. The passenger movement time storage unit 10 is implemented by the memory 21 illustrated in FIG. 2. The passenger movement time storage unit 10 stores a passenger movement time "Tpiatform (s, p, qbefore, qafter) " when a platform for a train is changed from a platform "qbefore" to a platform "qafter" at a station "s" in a time of day "p". When "qbefore" and "qafter" are same, "Tpiatform (s, p, qbefore, qafter)" is 0. In a case where the change from the platform "qtefore" to the platform "qafter" is not available, for example, where the "qbefore" is a platform dedicated to a train in an inbound direction and the "qafter" is a platform dedicated to a train in an outbound direction, the "Tpiatform(s, p, qbefore, qafter) " is set to a sufficiently large

value.
[0058] The convenience calculation unit 4 calculates convenience defined by the sum of passenger movement times when the train platform is changed, in addition to the convenience defined by the sum of the mounts of shift by which the departure time intervals of the train for each of directions, train types, stations, and times of day in the operation-rescheduling plan are shifted from the average departure time interval.
[0059] Specifically, the convenience is defined as follows. When a platform for a train "r" at a station "s" in a planned train schedule is denoted by "qbefore(r, s)" and a platform for the train "r" at the station "s" in the operation-rescheduling plan is denoted by "qafter(r, s)", convenience "Vconvenience" is defined as follows.
V convenience ^eGE,reR,seS,pGP I ^departure \ -^next \ r , e, SJ, e, S )
~ "^departure \^ r S, S) ~ J-average \Qf S, S, pj | + ieeE,rER,seS,pe
pTplatform ( S, p, qbefore(r, S), qafter(r, S)) ... (10)
In other words, the convenience is defined by using the sum of an absolute value of a difference between the departure time interval " (tdeparture (Rnext (r, e, s), e, s) -tdeparture (r, e, s))" in the operation-rescheduling plan and the average departure time interval "Taverage (d, e, s, p) " obtained from the planned train schedule, and the passenger movement time "Tpiatform (s, p, qbefore(r, s), qafter(r, s))" when the platform is changed from "qbefore(r, s)" which is the train platform in the planned train schedule, to "qafter(r, s)" which is the train platform in the operation-rescheduling plan. Also in the present embodiment, the larger the value of "Vconvenience" is, the lower the convenience is. [0060] The operation-rescheduling-plan preparing unit 7

prepares the operation-rescheduling plan at the time of the disruption of train schedule on the basis of the planned train schedule stored in the planned train-schedule storage unit 1, the actual train schedule stored in the actual train-schedule storage unit 2, the convenience calculated by the convenience calculation unit 4, the degree of recovery calculated by the recovery degree calculation unit 5, and the constraint violation amount calculated by the constraint violation amount calculation unit 6. [0061] Next, an operation-rescheduling-plan automatic preparation method used in the operation-rescheduling-plan automatic preparation apparatus according to the present embodiment will be described with reference to FIGS. 6 and 7. FIG. 7 is a flowchart illustrating an example of the operation-rescheduling-plan automatic preparation method used in the operation-rescheduling-plan automatic preparation apparatus according to the present embodiment. [0062] The operation-rescheduling-plan preparing unit 7 acquires the planned train schedule stored in the planned train-schedule storage unit 1 and the actual train schedule stored in the actual train-schedule storage unit 2 (Step ST201), prepares the candidate operation-rescheduling plan on the basis of the acquired planned train schedule and actual train schedule (Step ST202), and transmits the prepared candidate operation-rescheduling plan to each of the convenience calculation unit 4, the recovery degree calculation unit 5, and the constraint violation amount calculation unit 6 (Step ST203). The candidate operation-rescheduling plan is prepared in the manner as described in the first embodiment.
[0063] The convenience calculation unit 4 acquires the planned train schedule stored in the planned train-schedule storage unit 1, the candidate operation-rescheduling plan

transmitted from the operation-rescheduling-plan preparing unit 7, and the passenger movement time stored in the passenger movement time storage unit 10 (Step ST204), calculates the convenience on the basis of the acquired planned train schedule, the candidate operation-rescheduling plan, and the passenger movement time (Step ST205), and transmits the calculated convenience to the operation-rescheduling-plan preparing unit 7 (Step ST206). In Step ST205, the convenience calculation unit 4 calculates the convenience in accordance with formula (10) above.
[0064] The recovery degree calculation unit 5 acquires the planned train schedule stored in the planned train-schedule storage unit 1 and the candidate operation-rescheduling plan transmitted from the operation-rescheduling-plan preparing unit 7 (Step ST207), calculates the degree of recovery from the disruption of train schedule on the basis of the acquired planned train schedule and candidate operation-rescheduling plan (Step ST208), and transmits the calculated degree of recovery to the operation-rescheduling plan-preparing unit 7 (Step ST209). The degree of recovery is calculated in the manner as described in the first embodiment.
[0065] The constraint violation amount calculation unit 6 acquires the constraint conditions stored in the constraint condition storage unit 3 and the candidate operation-rescheduling plan transmitted from the operation-rescheduling-plan preparing unit 7 (Step ST210), calculates the constraint violation amount on the basis of the acquired constraint conditions and candidate operation-rescheduling plan (Step ST211), and transmits the calculated constraint violation amount to the operation-rescheduling-plan preparing unit 7 (Step ST212). The

constraint violation amount is calculated in the manner as described in the first embodiment.
[0066] The operation-rescheduling-plan preparing unit 7 acquires the convenience transmitted from the convenience calculation unit 4, the degree of recovery transmitted from the recovery degree calculation unit 5, and the constraint violation amount transmitted from the constraint violation amount calculation unit 6 (Step ST213), and calculates the evaluation value of the candidate operation-rescheduling plan (Step ST214). The evaluation value of the candidate operation-rescheduling plan is calculated in the manner as described in the first embodiment.
[0067] Next, the operation-rescheduling- plan preparing unit 7 determines whether the evaluation value of the candidate operation-rescheduling plan has been improved (Step ST215). When the evaluation value of the candidate operation-rescheduling plan is calculated for the first time, the operation-rescheduling-plan preparing unit 7 determines that the evaluation value of the candidate operation-rescheduling plan has been improved, and when the evaluation value of the candidate operation-rescheduling plan is calculated for the second or more time, the operation-rescheduling-plan preparing unit 7 determines whether the evaluation value of the candidate operation-rescheduling plan has been improved by comparing the evaluation value of the current operation-rescheduling plan with the evaluation value of the candidate operation-rescheduling plan which has just been calculated. When the determination indicates that the evaluation value of the candidate operation-rescheduling plan is not improved (Step ST215, No), the operation-rescheduling-plan preparing unit 7 stores the current operation-rescheduling plan in the operation-rescheduling-plan storage unit 8 (Step ST217),

and terminates the operation-rescheduling-plan automatic preparation process. When the determination indicates that the evaluation value of the candidate operation-rescheduling plan is improved (Step ST215, Yes), the operation-rescheduling-plan preparing unit 7 employs the candidate operation-rescheduling plan as a current operation-rescheduling plan (Step ST216), and the process returns to Step ST202.
[0068] As described above, in addition to the configuration of the first embodiment, the present embodiment provides the passenger movement time storage unit 10 which stores a passenger movement time when the platform for the train is changed at each station, and hence it is possible to prepare the operation-rescheduling plan in consideration of passengers' convenience when the platform for the train is changed.
[0069] The other configurations, operations, and effects of the present embodiment are the same as those of the first embodiment. [0070] Fifth Embodiment.
FIG. 8 is a block diagram illustrating a configuration example of an operation-rescheduling-plan automatic preparation apparatus according to the present embodiment. In FIG. 8, the same reference signs are used to denote the same components as those in the first embodiment illustrated in FIG. 1, and detailed descriptions of the same components will be omitted.
[0071] The operation-rescheduling-plan automatic preparation apparatus according to the present embodiment includes a change information setting unit 11 and a change information storage unit 12 in addition to the configuration illustrated in FIG. 1. The change information setting unit 11 is capable of setting operation

change information determined by, for example, a commander in advance. The change information storage unit 12 stores the operation change information set by the change information setting unit 11. The change information setting unit 11 is implemented by the input/output device 22 in FIG. 2, and the change information storage unit 12 is implemented by the memory 21 in FIG. 2.
[0072] The operation change information includes, for example, information regarding suspension of train service, addition of extra trains, and a train type change. A method for setting the operation change information includes, for example, a method using a change information setting screen 13 illustrated in FIG. 9. FIG. 9 is a diagram illustrating an example of the change information setting screen 13 which is the change information setting unit 11. The change information setting screen 13 is a screen which enables operation change information to be input and set. As illustrated in FIG. 9, the change information setting screen 13 includes text boxes 14a, 14b, 14c, 14d, 14e, 14f, and 14g, and a setting button 15. A train number of a train out of service can be input to the text box 14a. A vehicle number of an extra train can be input to the text box 14b. A train number of the extra train can be input to the text box 14c. A train type of the extra train can be input to the text box 14d. Departure stations from which the extra trains depart, departure times at which the extra trains depart, departure platforms from which the extra trains depart, arrival stations at which the extra trains arrive, arrival times at which the extra trains arrive, and arrival platforms at which the extra trains arrive can be input to the text box 14e. A train number of a train having its train type to be changed can be input to the text box 14f. A changed train

type of the train having its train type to be changed can be input to the text box 14g. Pushing the setting button 15 after inputting the operation change information causes the input operation change information to be stored in the change information storage unit 12.
[0073] Next, an operation-rescheduling-plan automatic preparation method used in the operation-rescheduling-plan automatic preparation apparatus according to the present embodiment will be described with reference to FIGS. 8 and 10. FIG. 10 is a flowchart illustrating an example of the operation-rescheduling-plan automatic preparation method used in the operation-rescheduling-plan automatic preparation apparatus according to the present embodiment. [0074] First, the change information setting unit 11 sets the operation change information. The operation change information is stored in the change information storage unit 12.
[0075] The operation-rescheduling-plan preparing unit 7 acquires the planned train schedule stored in the planned train-schedule storage unit 1, the actual timetable stored in the actual train-schedule storage unit 2, and the operation change information stored in the change information storage unit 12 (Step ST301), prepares the candidate operation-rescheduling plan on the basis of the acquired planned train schedule, actual train schedule, and operation change information (Step ST302), and transmits the prepared candidate operation-rescheduling plan to each of the convenience calculation unit 4, the recovery degree calculation unit 5, and the constraint violation amount calculation unit 6 (Step ST303). The candidate operation-rescheduling plan is prepared in the manner as described in the first embodiment. [0076] The convenience calculation unit 4 acquires the

planned train schedule stored in the planned train-schedule storage unit 1 and the candidate operation-rescheduling plan transmitted from the operation-rescheduling-plan preparing unit 7 (Step ST304), calculates the convenience on the basis of the acquired planned train schedule and candidate operation-rescheduling plan (Step ST305), and transmits the calculated convenience to the operation-rescheduling-plan preparing unit 7 (Step ST306). The convenience is calculated in the manner as described in the first embodiment.
[0077] The recovery degree calculation unit 5 acquires the planned train schedule stored in the planned train-schedule storage unit 1 and the candidate operation-rescheduling plan transmitted from the operation-rescheduling-plan preparing unit 7 (Step ST307), calculates the degree of recovery from the disruption of train schedule on the basis of the acquired planned train schedule and candidate operation-rescheduling plan (Step ST308), and transmits the calculated degree of recovery to the operation-rescheduling plan-preparing unit 7 (Step ST309). The degree of recovery is calculated in the manner as described in the first embodiment.
[0078] The constraint violation amount calculation unit 6 acquires the constraint conditions stored in the constraint condition storage unit 3 and the candidate operation-rescheduling plan transmitted from the operation-rescheduling-plan preparing unit 7 (Step ST310), calculates the constraint violation amount on the basis of the acquired constraint conditions and candidate operation-rescheduling plan (Step ST311), and transmits the calculated constraint violation amount to the operation-rescheduling- plan preparing unit 7 (Step ST312). The constraint violation amount is calculated in the manner as

described in the first embodiment.
[0079] The operation-rescheduling-plan preparing unit 7 acquires the convenience transmitted from the convenience calculation unit 4, the degree of recovery transmitted from the recovery degree calculation unit 5, and the constraint violation amount transmitted from the constraint violation amount calculation unit 6 (Step ST313), and calculates the evaluation value of the candidate operation-rescheduling plan (Step ST314). The evaluation value of the candidate operation-rescheduling plan is calculated in the manner as described in the first embodiment.
[0080] Next, the operation-rescheduling-plan preparing unit 7 determines whether the evaluation value of the candidate operation-rescheduling plan has been improved (Step ST315). When the evaluation value of the candidate operation-rescheduling plan is calculated for the first time, the operation-rescheduling-plan preparing unit 7 determines that the evaluation value of the candidate operation-rescheduling plan has been improved, and when the evaluation value of the candidate operation-rescheduling plan is calculated for the second or more time, the operation-rescheduling-plan preparing unit 7 determines whether the evaluation value of the candidate operation-rescheduling plan has been improved by comparing an evaluation value of the current operation-rescheduling plan with the evaluation value of the candidate operation-rescheduling plan which has just been calculated. When the determination indicates that the evaluation value of the candidate operation-rescheduling plan is not improved (Step ST315, No), the operation-rescheduling-plan preparing unit 7 stores the current operation-rescheduling plan in the operation-rescheduling-plan storage unit 8 (Step ST317), and terminates the operation-rescheduling-plan automatic

preparation process. On the other hand, when the determination indicates that the evaluation value of the candidate operation-rescheduling plan is improved (Step ST315, Yes), the operation-rescheduling-plan preparing unit 7 employs the candidate operation-rescheduling plan as a current operation-rescheduling plan (Step ST316), and the process returns to Step ST302.
[0081] As described above, in addition to the configuration of the first embodiment, the present embodiment provides the change information setting unit 11 capable of setting the operation change information determined by, for example, the commander in advance, and the change information storage unit 12 which stores the operation change information set by the change information setting unit 11, and therefore, the operation change information set by the commander in advance is taken into consideration in preparing the operation-rescheduling plan. [0082] Although the start of the process illustrated in FIG. 10 (Step ST301) is premised on the input of the operation change information, the operation-rescheduling plan may be once prepared without operation change information, and after confirming a result thereof, for example, the commander may input the operation change information to correct the operation-rescheduling plan. [0083] The other configurations, operations, and effects of the present embodiment are the same as those of the first embodiment.
[0084] The configurations described in the embodiments above indicate one example of the content of the present invention and can be combined with other known technology, and a part thereof can be omitted or modified without departing from the gist of the present invention.

Reference Signs List
[0085] 1 planned train-schedule storage unit, 2 actual train-schedule storage unit, 3 constraint condition storage unit, 4 convenience calculation unit, 5 recovery degree calculation unit, 6 constraint violation amount calculation unit, 7 operation-rescheduling-plan preparing unit, 8 operation-rescheduling-plan storage unit, 9 train operation prediction unit, 10 passenger movement time storage unit, 11 change information setting unit, 12 change information storage unit, 13 change information setting screen, 14a to 14g text box, 15 setting button, 20 processor, 21 memory, 22 input/output device.

CLAIMS 1. An apparatus for automatic preparation of operation-rescheduling-plan, the apparatus comprising:
a planned train-schedule storage unit to store a planned train schedule;
an actual train-schedule storage unit to store an actual train schedule;
a constraint condition storage unit to store constraint conditions to be imposed in preparing an operation-rescheduling plan;
a convenience calculation unit to calculate convenience of the operation-rescheduling plan for each train type on a basis of the operation-rescheduling plan and scheduled departure times or scheduled arrival times of trains in the planned train schedule;
a recovery degree calculation unit to calculate a degree of recovery from disruption of train schedule on a basis of a difference between a current time and a train-schedule-disruption convergence time obtained from a comparison of the operation-rescheduling plan with the planned train schedule;
a constraint violation amount calculation unit to calculate a constraint violation amount of the operation-rescheduling plan with respect to the constraint conditions on a basis of the constraint conditions and the operation-rescheduling plan;
an operation-rescheduling-plan preparing unit to prepare the operation-rescheduling plan on a basis of an evaluation value defined using the convenience, the degree of recovery, and the constraint violation amount; and
an operation-rescheduling-plan storage unit to store the operation-rescheduling plan, wherein
the operation-rescheduling-plan preparing unit

corrects an initial plan of the operation-rescheduling plan in accordance with a predetermined correction method to prepare a candidate operation-rescheduling plan,
when an evaluation value of the candidate operation-rescheduling plan is improved in comparison with an evaluation value of the initial plan of the operation-rescheduling plan, the operation-rescheduling-plan preparing unit corrects the candidate operation-rescheduling plan in accordance with the correction method to prepare a next candidate operation-rescheduling plan, and repeats a process of correcting the next candidate operation-rescheduling plan in accordance with the correction method as far as an evaluation value of the next candidate operation-rescheduling plan is improved in comparison with the evaluation value of the candidate operation-rescheduling plan, and
when the evaluation value of the next candidate operation-rescheduling plan is not improved in comparison with the evaluation value of the candidate operation-rescheduling plan, the operation-rescheduling-plan preparing unit employs the candidate operation-rescheduling plan as the operation-rescheduling plan.
2. The apparatus for automatic preparation of operation-rescheduling-plan according to claim 1, wherein the evaluation value is defined as a weighted sum of the convenience, the degree of recovery, and the constraint violation amount.
3. The apparatus for automatic preparation of operation-rescheduling-plan according to claim 1 or 2, wherein in storing the operation-rescheduling plan in the operation-rescheduling-plan storage unit, the operation-rescheduling-

plan preparing unit attaches information regarding a preparation time at which the operation-rescheduling plan is prepared, to the operation-rescheduling plan, and stores the operation-rescheduling plan, and
the operation-rescheduling-plan preparing unit regards an operation-rescheduling plan prepared at a latest preparation time and stored in the operation-rescheduling-plan storage unit, as the initial plan of the operation-rescheduling plan.
4. The apparatus for automatic preparation of operation-
rescheduling-plan according to claim 1 or 2, comprising a
train operation prediction unit to predict a condition of
train-schedule disruption from the current time on a basis
of the planned train schedule and the actual train schedule,
wherein
the operation-rescheduling-plan preparing unit regards a result of prediction performed by the train operation prediction unit as the initial plan of the operation-rescheduling plan.
5. The apparatus for automatic preparation of operation-
rescheduling-plan according to any one of claims 1 to 4,
wherein the convenience calculation unit calculates an
average departure time interval of a train for each of
directions, train types, stations, and times of day, on a
basis of the scheduled departure times of trains in the
planned train schedule, and then calculates, as convenience,
the sum of amounts of shift by which departure time
intervals of a train for each of directions, train types,
stations, and times of day in the operation-rescheduling
plan are shifted from the average departure time interval,
or the convenience calculation unit calculates an average

arrival time interval of a train for each of directions, train types, stations, and times of day, on a basis of the scheduled arrival times of trains in the planned train schedule, and then calculates, as convenience, the sum of amounts of shift by which arrival time intervals of a train for each of directions, train types, stations, and times of day in the operation-rescheduling plan are shifted from the average arrival time interval.
6. The apparatus for automatic preparation of operation-
rescheduling-plan according to claim 5, comprising a
passenger movement time storage unit to store a passenger
movement time caused due to a train platform change for
each station, wherein
the convenience calculation unit calculates, as the convenience, a value obtained by calculating a passenger movement time due to the train platform change for each of stations and times of day on a basis of the planned train schedule, the actual train schedule, and the passenger movement time stored in the passenger movement time storage unit, and then adding the passenger movement time to the sum of amounts of shift of the departure time intervals or the sum of mounts of shift of the arrival time intervals.
7. The apparatus for automatic preparation of operation-
rescheduling-plan according to any one of claims 1 to 6,
wherein the constraint condition storage unit stores as the
constraint conditions:
minimum stop times for each train type and for each station;
minimum return times for each train type and for each terminal station;
minimum running times for each direction and for each

train type from each station to a next station thereof;
a minimum departure time interval between a preceding train and a following train for each station; and
a minimum arrival time interval between a preceding train and a following train for each station.
8. The apparatus for automatic preparation of operation-
rescheduling-plan according to any one of claims 1 to 7,
comprising:
a change information setting unit capable of setting operation change information from a change information setting screen; and
a change information storage unit to store change information set by the change information setting unit, wherein
when the evaluation value of the next candidate operation-rescheduling plan has been improved in comparison with the evaluation value of the candidate operation-rescheduling plan, the operation-rescheduling-plan preparing unit corrects the next candidate operation-rescheduling plan in accordance with the correction method on a basis of the convenience, the degree of recovery, the constraint violation amount, the planned train schedule, the actual train schedule, and the change information.
9. A method for automatic preparation of operation-
rescheduling-plan, the method being used in an apparatus
for automatic preparation of operation-rescheduling-plan,
the method comprising:
a step of, by the apparatus for automatic preparation of operation-rescheduling-plan, regarding an initial plan of an operation-rescheduling plan as a candidate operation-rescheduling plan when the operation-rescheduling plan is

prepared for a first time, and correcting a candidate operation-rescheduling plan previously prepared, in accordance with a predetermined correction method to prepare the candidate operation-rescheduling plan when the candidate operation-rescheduling plan is prepared for second or more time;
a step of, by the apparatus for automatic preparation of operation-rescheduling-plan, calculating convenience of the candidate operation-rescheduling plan for each train type on a basis of the candidate operation-rescheduling plan and scheduled departure times or scheduled arrival times of trains in a planned train schedule;
a step of, by the apparatus for automatic preparation of operation-rescheduling-plan, calculating a degree of recovery from disruption of train schedule on a basis of a difference between a current time and a train-schedule-disruption convergence time obtained from a comparison of the candidate operation-rescheduling plan with the planned train schedule;
a step of, by the apparatus for automatic preparation of operation-rescheduling-plan, calculating a constraint violation amount of the candidate operation-rescheduling plan with respect to constraint conditions on a basis of the constraint conditions and the candidate operation-rescheduling plan;
a step of, by the apparatus for automatic preparation of operation-rescheduling-plan, calculating an evaluation value of the candidate operation-rescheduling plan defined using the convenience, the degree of recovery, and the constraint violation amount; and
a step of, by the apparatus for automatic preparation of operation-rescheduling-plan, returning to a process of preparing the operation-rescheduling plan when the

evaluation value of the candidate operation-rescheduling plan is calculated for a first time, comparing the evaluation value of the candidate operation-rescheduling plan with an evaluation value of the candidate operation-rescheduling plan previously prepared, when the evaluation value of the candidate operation-rescheduling plan is calculated for second or more time, returning to the process of preparing the operation-rescheduling plan when the evaluation value of the candidate operation-rescheduling plan has been improved in comparison with the evaluation value of the candidate operation-rescheduling plan previously prepared, and employing the candidate operation-rescheduling plan previously prepared, as the operation-rescheduling plan when the evaluation value of the candidate operation-rescheduling plan has not been improved in comparison with the evaluation value of the candidate operation-rescheduling plan previously prepared.