JPH0969122A - Method and system for creating operation plan of operating equipment - Google Patents

Abstract

(57) [Summary] [Purpose] To provide a method and system for creating an operation equipment operation plan that allows the user's intention to be easily reflected in solution search. [Structure] A storage area of a two-dimensional matrix consisting of operation numbers and dates of operating equipment and a storage area of a plurality of genes having the same matrix structure as this two-dimensional matrix are provided, and the operation equipment is provided with a plurality of operation numbers. The constraint condition to be considered when assigning to any of the two is set in the corresponding mesh of the two-dimensional matrix and stored, and different gene codes are randomly set in the storage regions of a plurality of genes, and the gene codes are different. After generating a plurality of genes, assigning operation equipment to any operation number based on the gene codes of the plurality of genes and the corresponding constraint conditions of the mesh, and assigning each gene obtained after this assigning process A plurality of corresponding operation plans are evaluated based on the degree of satisfaction with the constraint conditions, and an operation plan having a high evaluation value is output.

Description

Detailed Description of the Invention

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a method for preparing an operation plan for solving a problem of preparing an operation plan for operating equipment such as trains, buses, and aircrafts by a computer. The present invention relates to a method and system for creating an operation plan including the steps of displaying, the revision of the planning result, and the verification of the planning result.

[0002]

2. Description of the Related Art As a system for creating a vehicle operation plan by a computer, there is a system to which the AI technique is applied.

For example, "Takahashi, et al .: Computer use at vehicle depot, pp47-50, Mitsubishi Electric Technical Report vol.61, No.2,1"
As described in “987”, there is a system that supports operation management of vehicles using a personal computer. With this system, the expert's knowledge is used to create a plan one day at a time so that the number of kilometers traveled on all trains will be uniform, taking into consideration operation several days ahead.

Further, as described in "Vehicle operation plan expert system, pp224, Toshiba review vol.49, No.3, 1993", not only the vehicle operation plan is prepared,
There is a system that supports the automatic creation of a detention plan and the function of automatically searching for a vehicle that can be replaced when a failure occurs.

[0005]

However, in the conventional vehicle operation planning system to which the AI technique is applied, such as the expert system, the solution search logic depends considerably on the problem-specific solution knowledge (heuristics). ing. For this reason, once the planning conditions and the like change, the system often cannot follow them and a satisfactory solution cannot be obtained. In such cases, human intervention is required, such as changing the search rules and relaxing the constraints, but it is difficult to efficiently modify the search rules and constraints in conventional systems that rely heavily on heuristics. Therefore, there was a problem that the search logic had to be adjusted by trial and error.

An object of the present invention is to efficiently modify the search rules and constraint conditions in response to changes in the planning conditions, etc., and to easily reflect the user's intention in the search solution. It is to provide a creation method and system.

[0007]

In order to achieve the above object, the present invention basically has a storage area of a two-dimensional matrix consisting of operation numbers and dates of operating equipment, and this two-dimensional matrix. A storage area for a plurality of genes having the same matrix structure is provided, and constraint conditions to be considered when assigning operating equipment to any of a plurality of operation numbers are set and stored in the corresponding mesh of the two-dimensional matrix. Along with the generation of a plurality of genes having different gene codes by randomly setting different gene codes in the storage regions of the plurality of genes, respectively, the constraint conditions of the mesh corresponding to each gene code of the plurality of genes and Based on the above, assigning operation equipment to one of the operation numbers and assigning multiple operation plans for each gene obtained after this assignment process. Evaluated by the satisfaction degree for the serial constraints, and outputs a high operational plan of the evaluation value.

[0008]

According to the above means, the constraint conditions such as the operation schedule and the inspection plan are stored in each element of the two-dimensional matrix having the horizontal axis as the date and the vertical axis as the operation number for each constraint type. A plurality of genes having a structure corresponding to the two-dimensional matrix are generated, and the operation equipment is assigned to any operation number based on the gene codes of the plurality of genes and the corresponding mesh constraint conditions. Then, the plurality of operation plans corresponding to each gene obtained after the allocation processing are evaluated by the degree of satisfaction with the constraint condition, and the operation plan having a high evaluation value is output.

Therefore, by manipulating the constraints,
It is possible to efficiently search and output a solution (operation plan) that flexibly follows the constraint condition.

In this case, the operation plan of the operating equipment is displayed by using the connection graph between adjacent nodes in the operation connection matrix, and the nodes and arcs of the connection graph are designated by using a pointing device such as a mouse. You can modify constraints and plans as if you were modifying the graphic.

Furthermore, the operation plan is checked for each revision,
By blinking and coloring the nodes and arcs at the constraint violation points on the operational connection graph, the constraint check results can be presented to the user in an easy-to-understand manner.

Further, with respect to a part satisfying the constraint condition with respect to the addition or modification of the constraint, the allocation to that part is frozen so that the solution satisfying the constraint is efficiently processed so as not to break the current solution as much as possible. You can ask well.

[0013]

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS One embodiment of the present invention will be described below in detail with reference to the drawings.

First, an outline of the vehicle operation plan creation problem handled in this embodiment will be described.

Railway vehicles are required to undergo regular inspections. There are two types of tests, long-term tests and short-term tests. The long-term inspection requires several months to disassemble the vehicle and reassemble it. on the other hand,
In the short-term inspection, the inspection device automatically inspects predetermined check items, so the inspection is completed in a few days.

In general, all vehicles must undergo a long-term inspection once every 1-2 years and a short-term inspection once every 2-3 months. In addition, a vehicle ID is set for all vehicles, and an inspection plan for all vehicles for one year is manually created in advance using this. The inspection plan is carefully designed so that all vehicles can undergo short-term inspection in a well-balanced manner.

On the other hand, the vehicles assigned to the train operation schedule every day are changed every day, and the same vehicle is not operated every day at the same time. As for the general vehicle operation mode, the vehicle assigned to the operation "1" is the operation "2" on the next day,
On the day after the next day, it is considered that the work of the dispatcher of the vehicle becomes cyclic pattern (rotation operation) as much as possible such as operation "3", and that all vehicles can periodically return to the base for inspection and cleaning. .

In the vehicle operation plan creation problem, the inspection plan and the vehicle operation plan (train schedule) created by hand are used as indispensable constraint conditions, and the vehicle is included in the operation plan for one month so as not to disturb the rotation operation as much as possible. It is a problem of allocation without excess or deficiency.

FIG. 1 is a flow chart showing an embodiment of a railway vehicle operation plan preparation procedure according to the present invention.

In step 1010, basic information for determining the scale of the problem is input. FIG. 2 shows a basic information input screen 2010.

The user selects the X-axis and Y-axis names and ranges,
Enter the resource name and resource range (number) to be assigned.

In the vehicle allocation problem of this embodiment, the X axis is 1
Month date 2020, Y axis has, for example, 22 types of operation numbers 2030, and resources are assigned to each operation number 22
It corresponds to the book vehicle 2040.

Reference numeral 2050 denotes a set of nodes arranged in a two-dimensional matrix having the X-axis as the date and the Y-axis as the operation number created by the above basic information, and this is the basic type of the solution expression. A circle in the node set 2050 corresponds to one node.

For example, the vehicle A is assigned to the operation number "3" on the first day.
If the vehicle A is assigned to the operation number “1” on the next second day, the partial plan is node 206.
It is represented by a connecting arc 2060 between 1, 2062.

In this embodiment, the vehicle operation allocation problem is treated as a combination optimization problem of wiring paths in which a plurality of arcs corresponding to vehicle IDs are wired on a basic type of solution expression (a node set expressing operation numbers). It is a thing.

In step 1020, solution search parameters such as the number of generations of gene operation to be executed are input.
The solution search uses a genetic algorithm which is a probabilistic search method.

The genetic algorithm repeats the genetic operations such as (1) natural selection (2) multiplication (3) mutation in the generation cycle to obtain a gene having a higher fitness (evaluation value). It is one of the frameworks of the optimization method for searching the combination. In this example, a gene corresponds to a set of 0/1 codes given to each node.

In general, gene operations in a genetic algorithm are as follows: (1) Natural selection: Genes with poor fitness (evaluation value) are eliminated.

(2) Proliferation: crossing a plurality of gene sets,
Generate a new gene.

(3) Mutation: The gene code of a part of the gene is stochastically inverted.

Etc. are typical.

The specific optimization method and genetic operation in this embodiment will be described in detail in step 1060. The basic processing flow is (S1) The gene code (0 or 1) is randomly assigned to each node. Give (S2) Create a plurality of gene code sets (genes) as initial solution candidates (S3) Convert genes into solution expressions by a conversion algorithm (S4) Evaluate converted solution expressions by an evaluation algorithm (S5) Evaluation Genes are deleted in order from the lowest value according to the natural selection rate (S6) The surviving genes are crossed to generate a new gene (S7) The gene code of the generated gene is inverted according to the mutation rate ( S8) Process (S3) and process (S4) are performed on the generated gene (S9) From (S3) to (S ) Is processing the repeated execution number of generations.

The various parameters input in step 1020 are input using the parameter input screen of FIG. 3, and are as follows.

(1) Number of execution generations 3010 Parameter for designating the number of repetitions of the processes (S3) to (S8) (2) Number of population individuals 3020 Parameter for designating the number of genes created in the process (S2) (3 ) Natural selection rate 3030 Parameter specifying the ratio of genes to be deleted in the above process (S5) (4) Mutation rate 3040 Parameter specifying the probability of reversing the genetic code in the above process (S7) (5) Non-zero element ratio 3050 A parameter that specifies the proportion of non-zero elements among the genes generated in the above processing (S2).

In the example of FIG. 3, the number of execution generations 3010 = 10
00 (times), population individual number (gene number) 3020 = 30
(Pieces), natural selection rate 3030 = 25 (%), mutation rate 3040 = 5 (%), non-zero element rate 3050 = 50 (%)
Indicates that has been entered.

Next, in step 1030, the genetic information is initialized. FIG. 4 is a schematic explanatory diagram of the gene initialization process. The n genes 4010j (j) corresponding to the set 2050 of each node defined in the previous step 1010.
= 1 to n), 0/1 is randomly assigned to initialize n genes.

The occurrence probability of 0/1 is determined by the non-zero element ratio input in step 1020. For example, when the non-zero element ratio is N%, “1” to “100”
0/1 is determined by the uniform random value RAND up to and the non-zero element ratio magnitude relationship table 4020.

At step 1040, constraints are input.

The constraint conditions are conditions to be considered when allocating daily operation equipment (equipment such as buses, trains and aircrafts) to operation plans and inspection plans for railways, buses and aircrafts.

In this embodiment, a connection constraint and an allocation constraint are input as constraint conditions.

The connection constraint is a constraint relating to the connection between the specific operation number of the previous day and the operation number of the current day, and the allocation constraint is that the specific resource (operating equipment) is allocated to one of the operation numbers of the day. It is a constraint at the time.

The connection constraint and the assignment constraint are "priority = required" which means "must be assigned" or "must not be assigned" and "priority" which means "it is better to assign". = Goal. In addition to "essential" and "goal", there is "no restriction" as the priority regarding the constraint condition.

In the present embodiment, a graph screen as shown in FIG. 5 is used as an input interface of the constraint conditions in order to efficiently modify the constraint conditions with respect to changes in the planning conditions and the like. That is, the connection / disconnection operation of arcs between each node in the two-dimensional matrix in FIG. 2 and the resource allocation operation to a specific node are performed by a graph editing operation using pointing or the like, and connection constraints and allocation constraints are efficiently input. It is configured to be possible.

Reference numeral 5010 is a display example of connection restrictions. The strength of the constraint is determined by the priority, and when the priority is "essential", this constraint is interpreted as "a vehicle that has performed operation of 10B must be assigned to operation 11B the next day." . On the other hand, when the priority is “target”, it is interpreted that “a vehicle that has performed operation 10B should be assigned to operation 11B the next day”.

The strength of the connection constraint (that is, whether it is essential,
Target) is configured to be easily identifiable by changing the thickness and color of the arc. For example, for a connection constraint with a priority of “essential”, as shown in the display example 5030, a thick solid line is drawn between the nodes. As for the connection constraint whose priority is “target”, the nodes are displayed by thin solid lines as shown in a display example 5010.

On the other hand, reference numeral 5020 in FIG. 5 is a display example of allocation constraints. Like the connection constraint, the strength of the constraint is determined by the priority. When the priority of the constraint is "required", the vehicle with "vehicle ID = 5" must undergo a short-term inspection for "3 days from 29 to 31." Is interpreted as When the priority is “target”, “29 to 3
For three days a day, the vehicle with vehicle ID 5 should undergo a short-term inspection. Is interpreted as The strength of the allocation constraint can be easily identified by changing the size and color of the node, as in the case of the connection constraint.

FIG. 6 shows the data structure of the connection constraint. The "priority" 6010, "type" 6011,
The user can register / invalidate / change the constraint condition by designating the “adaptive target” 6012 or the like by the user. In the example of FIG. 6, since the priority 6010 is “target”, the type 6011 is “affirmative”, and the adaptation target 6012 is “node A” and “node B”, this connection constraint is “node A and node B”. B should be connected ".

When "No" is designated as the type 6011, it is interpreted to mean that "node A and node B should not be connected".

Further, "none" of the type 6011 is a default value and is synonymous with "affirmation".

FIG. 7 shows the data structure of the allocation constraint, which is also the "priority" 701, like the connection constraint.
The user can newly register / invalidate / change the constraint by designating 0, “type” 7011, “adaptive target” 7012, or the like. In the example of FIG. 7, since the priority 7010 is "required", the type 7011 is "negative", and the adaptation target 7012 is "node A" and "resource B", this allocation constraint is "node A Resource B must not be allocated. "

FIG. 8 is an explanatory diagram regarding the storage location of the connection constraint and the allocation constraint.

In this embodiment, the connection constraint and the assignment constraint are treated as specific examples. However, each mesh of the constraint storage matrices 8001 and 8002 has a mesh corresponding to the node of the solution expression for each constraint. Store the constraint conditions in.

For example, the arc 8010 shown in FIG.
The vehicles assigned to Operation 6B on "19th" are
It means a "required" connection constraint that it must be assigned to operation 7B on "0th day", but this means that node 8
The connection constraint A described in 020 is stored in the mesh 8030 of the connection constraint storage matrix 8001.

Similarly, the arc 8040 means a "target" connection constraint that a vehicle assigned to the operation 7B on "21st day" should be assigned to the operation 8B on the next "22nd day". , Which is stored in the mesh 8060 as the connection constraint B described in the node 8050.

On the other hand, the node 8070 means an “essential” allocation constraint that the vehicle with “vehicle ID = 5” must be allocated to the operation 10B on “21st day”, which is described in the node 8070. The allocation constraint C is stored in the mesh 8080 of the allocation constraint storage matrix 8002. Similarly, the node 8090 means an allocation constraint of “target” that it is better to allocate the vehicle of “vehicle ID = 9” to the operation 10B on “22nd”, which is described in the node 8090. Mesh 8 as allocation constraint D
It is stored in 100.

Next, the partial freezing process of the solution in step 1050 will be described.

When a user adds a new constraint to the constraint-satisfying solution proposed by the system or modifies a part of the solution, the influence on other schedules spreads, and a portion violating the constraint appears. In such a case, it is possible to return the solution to “blank paper” once and search for a solution that satisfies all the new constraints. However, in the present embodiment, new constraints are appropriately set without breaking the current solution as much as possible. It has a function to efficiently search for a feasible solution while absorbing it.

FIG. 9 is a main process flow of the partial solution freezing process. First, in step 9010, the date is initialized and the date is set to "1", and then in step 90
At 20, the processing end judgment is made as to whether it is the "end of the month",
If the date is the end of the month, the process ends.

In step 9030, the operation number is initialized and the operation number is set to "1". Step 9
At 040, the end determination is made based on the operation number. If the operation number is the last, the date is updated at step 9050, and the process returns to step 9020.

Next, in step 9060, it is determined whether the constraint registered in the corresponding node is satisfied. The system reconciles each node of the constraint satisfaction solution created previously by the system with the connection constraint or allocation constraint before modification and the modified connection constraint or allocation constraint, and each node of the constraint satisfaction solution created previously is modified. It is determined whether the connection constraint and the allocation constraint are satisfied. In this decision,
When each node of the constraint satisfaction solution created previously conforms to the modified connection constraint or allocation constraint, it is considered to be satisfied.

If the constraint is satisfied or no constraint is described, the priority of the constraint registered in the designated node is maximized in step 9070 to freeze the solution. That is, the solution is frozen by setting the constraint of "essential".

If the constraint is not satisfied,
The operation number is updated in step 9080 while the constraint remains unchanged, and the process returns to step 9040.

The partial freezing of the solution can be equivalently realized by freezing the genetic code corresponding to the mesh satisfying the constraints.

FIG. 10 is a schematic explanatory view of a partial solution freezing process, and 10010 is an example in which a constraint violation portion appears in the current solution due to addition of constraint conditions or the like. A shaded node indicates that the connection constraint is violated, and a thick line node indicates that the allocation constraint is violated. In this case, the constraint violation area of the matrix storing the connection constraint is 10020, and the constraint satisfaction area is 10030. At this time, the priority of the connection constraint registered in the constraint satisfaction area is stochastically changed to the maximum, that is, "required".
The solution of this area is stochastically frozen by changing to the connection constraint of.

Similarly, the constraint violation area of the allocation constraint storage matrix is 10040, and the constraint satisfaction area is 10.
It is 050. At this time, the priority of the allocation constraint registered in the constraint satisfaction area 10050 is stochastically changed to the maximum, that is, the allocation constraint is changed to “essential”, so that the solution in this area is stochastically frozen.

By this solution freezing process, a new solution is searched only for the nodes that have not been frozen.

Next, the optimization processing in step 1060 will be described.

FIG. 11 is a main processing flow of optimization.

In step 11010, the number of generations i is initialized and set to "number of generations = 1", and the following step 1
At 1020, the gene pointer j is initialized and set to “j = 1”.

At step 11030, the end judgment is made,
When the number of generations i has reached the preset number of execution generations, the process ends. In step 11040, conversion processing (decoding) to the solution expression of the gene is performed.

In the decoding process, a gene is converted into 1
This is a process of generating a vehicle operation plan for a month, and connects each node with the node of the previous day in order from the beginning of the month every day.

FIG. 12 is a detailed decoding processing flow.

After the date is initialized to "date = 1" at step 12010, it is determined at the end of the process at the end of the month at step 12020 that the process ends if the date is at the end of the month.

Next, at step 12030, the "maximum priority" (essential constraint in this embodiment) is set as the priority. In step 12040, the end determination for one day is performed based on the priority, and when the decoding of all the priorities for one day is completed, the date is updated in step 12050, and the process returns to step 12020.

At step 12060, the operation number is initialized to "operation number = 1". Next, step 1
In step 2070, the end determination is made based on the operation number. If the operation number is the final one, the priority is updated in step 12080 and the process returns to step 12040.

Next, in step 12090, it is judged whether or not a constraint having the same priority as the priority set in step 12030 or the priority exercised in step 12080 is registered in the corresponding mesh of the constraint storage matrices 8001 and 8002. If it is registered, the decoding rule is executed in step 12100.

The decoding process is performed by copying the constraints stored in the constraint storage matrices 8001 and 8002 to the work area. The reason is that the constraints stored in the constraint storage matrices 8001 and 8002 are commonly used by all genes. Therefore, the gene pointer j
Every time is updated, the constraint storing matrices 8001, 80
The constraint stored in 02 is copied to the work area, and the decoding process is performed using the copied constraint.

FIG. 13 is an explanatory diagram showing the definition screen of the decoding rule.

The decoding rule is described in the if-then format, and the if part indicates the constraint priority, type, and gene 0.
It is described using the / 1 code, and the then part is described using the object to which the constraint is applied and the processing code shown in FIG.

With this if-then format decoding rule, the priority indicated by the processing code is updated for the subject to which the constraint is applied, and the random allocation processing of unconnected nodes is performed.

In the present embodiment, (1) When the priority of the constraint is “essential constraint”, the constraint matrix 8001, 800 in which the constraint is registered
The processing code is A regardless of the genetic code corresponding to the mesh position of 2, and the constraint is unconditionally satisfied regardless of 0/1 of the genetic code.

(2) When the priority of the constraint is "target constraint" The constraint matrix 8001, 800 in which the constraint is registered
When the gene code corresponding to the mesh position of 2 is “0”, the processing code is A and the target constraint is satisfied.
When the corresponding gene code is "1", the processing code is D, the priority of the constraint is lowered by one rank, and the satisfaction of the constraint is suspended.

(3) When the priority of the constraint is "none" or the constraint is not registered The processing code is Z regardless of the genetic code corresponding to the mesh position of the constraint map in which the constraint is registered, and it is not connected. Search for new nodes and randomly connect to the previous day's nodes.

If there is no constraint having the corresponding priority, the operation number is updated in step 12110, and the process returns to step 12070.

Returning to the optimization main flow of FIG. 11, in the next step 11050, the solution obtained as the decoding result is evaluated.

FIG. 14 is a detailed evaluation processing flow.
Evaluation is performed by the deduction method according to the constraint violation.

First, in step 14010, the penalty and the date are initialized, and "penalty = 0" and "date = 1" are set. Then, in step 14020, it is determined whether or not the processing ends at the end of the month. , The evaluation process of drafting the gene designated by the gene pointer j of the number of generations i ends.

In step 14030, the "maximum priority" (indispensable constraint in this embodiment) is set as the priority, and in step 14040, the end determination for one day is made by the priority, and the penalty is calculated for all the priorities. If is completed, the date is updated in step 14050, and the process returns to step 14020.

At step 14060, the operation number is initialized to "operation number = 1". Step 1407
When the operation number is 0, the end determination is made. When the operation number is the last, the priority is updated in step 14080 and the process returns to step 14040.

Next, at step 14090, it is judged whether or not the constraint having the same priority as the priority set at step 14030 or the priority updated at step 14080 is registered in the corresponding mesh of the constraint map, and the mesh is registered. In that case, it is checked in step 14100 whether the constraint is satisfied.

Whether or not the constraint is satisfied is determined by the constraint satisfaction solution decoded by the decoding process of FIG. 12 and the connection constraint and the allocation constraint stored in the connection constraint storage matrix 8001 and the allocation constraint storage matrix 8002. The constraint satisfaction solution decoded by the decoding process of FIG. 12 is compared with the connection constraint storage matrix 800.
1 and the allocation constraint storage matrix 8002 determines whether or not the connection constraint and the allocation constraint stored in the matrix 8002 are satisfied.

If the constraint is not satisfied, the penalty of the gene is updated by the deduction method in step 14110, the operation number is updated in step 14120, and the process returns to step 14070.

On the other hand, when the constraint is satisfied, the operation number is updated in step 14120, and the process returns to step 14070.

Returning to the optimization main flow of FIG. 11, in step 11060, it is judged whether or not there is a gene to be decoded. If there is, the gene pointer j is updated by 1 in step 11070, and the process returns to step 11040. , The following genes are decoded and evaluated.

If there is no gene to be decoded, in step 11080, natural selection processing, which is one of gene operations, is performed.

FIG. 15 is a schematic explanatory view of the natural selection process. In the natural selection process, the number of genes according to the natural selection rate is selected (deleted) in order from the lowest evaluation value among all the genes.

For example, the case where there are genes from A to Z and two genes are selected by natural selection will be described.
15010 is the end state of decoding and evaluation of the genes Y and Z newly generated in the previous step.
Shows the state in which all genes are rearranged in the order of high evaluation value. At this time, 150-1 is a state in which the evaluation values of the two genes are set to "-1" in order from the gene having the lowest evaluation value, and the genes are selected.

By this processing, the gene W with a low evaluation value,
X is eliminated.

Subsequently, in step 11090 of FIG. 11, a gene crossover operation is performed to generate and supplement new genes by the number of genes reduced in the previous natural selection.

FIG. 16 is a schematic illustration of the crossover process.

Gene 1601 of parent A shown in FIG. 16 (a)
The crossover process will be described by taking as an example the case where 0 and the gene 16020 of the parent B shown in FIG. 11B are crossed to generate the gene 16030 of the child shown in FIG.

Generally, in the crossover treatment, a gene is cut at a certain position and the genes of both parents are combined, but in this embodiment, a new gene is generated by a method of synthesizing a gene code.

Specifically, the gene codes in the same mesh of two parents are synthesized based on the synthesis rule, and the synthesized codes are set in the same mesh of the child genes. The composition rule is AND, OR, EOR of two codes.
Although there are various methods such as the above, in the present embodiment, as a mechanism for the non-zero element ratio of the genetic code to converge to the optimum value, the synthesis rule 16 as shown in FIG.
040 is applied.

This is because when the two parent gene codes to be synthesized have the same genetic code, the same genetic code is inherited by the offspring, and when they have different genetic codes, the probability is 0 depending on the probability P.
Determine / 1. Here, the probability P is dynamically determined so that the expected value of the non-zero element ratio of the genetic code of the child is the same as the non-zero element ratio of the parent with a high evaluation value.

Next, in step 11100 of FIG.
Perform gene mutation operation. Generally, the purpose of the mutation operation in the genetic algorithm is to prevent the solution search from falling into a local solution, but in this embodiment, a mutation is applied to a new gene generated for the same purpose.

FIG. 17 is a schematic diagram of the mutation operation. For example, when the pre-mutation gene 17010 shown in FIG. 17 (a) is mutated to the gene 17020 shown in FIG. 17 (b), the gene code stored in the mesh A of the gene 17010 is code-converted by the mutation operation 17030. It is stored in the mesh B of 17020.

The mutation operation is a process of inverting the genetic code with a predetermined mutation rate P.

Subsequently, in step 11110 of FIG. 11, the generation number i is updated, and the process returns to step 11020. By repeating the above steps 11020 to 11110 for the number of execution generations, the search for the optimum solution is advanced.

Returning to the main flow of FIG. 1, step 10
The display of the plan content / user intervention process 70 will be described.

The gene having the highest evaluation value at the time when the optimization process is completed is decoded into the solution expression, and the result is shown in FIG.
It is displayed as a vehicle operation graph like.

As the decoding rule in this case, the same rule as described in FIG. 13 is used.

The planner judges the displayed vehicle operation graph and corrects the constraint 18010 and the alternative request 1802.
0, approval 18030, discard 18040, constraint check 1
Intervention such as 8050.

The modification of the constraint is the same as that described in step 1040. When a constraint change operation is input, the constraint storage matrices 8001 and 8002 are updated accordingly.

FIG. 19 is an example in which three connection constraints are newly input. The "constraint 1" is a mandatory connection constraint with a thick line arc, the "constraint 2" is a thick x mark with a mandatory connection constraint, and the "constraint 3" is a thin solid line arc with a "target" connection constraint. Taking “constraint 1” as an example, mapping is performed with the node to which the connection constraint is input, and the constraint storage matrix 80
The constraint 19010 is newly stored in the corresponding mesh of 01.

On the other hand, FIG. 20 shows an example in which three allocation constraints are newly input. The "constraint 6" is a target allocation constraint for a light-colored node, and the "constraint 4" and "constraint 5" are mandatory allocation constraints for a dark-colored node. Taking “constraint 6” as an example, mapping is performed with the node to which the assignment constraint is input, and the constraint 200 is assigned to the corresponding mesh of the constraint storage matrix 8002.
10 is newly stored.

If an alternative is requested, step 10
After performing the alternative plan generation process at 80, the process returns to step 1070.

FIG. 21 is a schematic explanatory diagram of the alternative plan generating process. The alternative is generated by decoding the gene B having the next highest evaluation value.

In FIG. 21, gene A having the next highest evaluation value is decoded with respect to gene A having the highest evaluation value,
This shows that “alternative 1” 21010 is generated.

When the planner requests the constraint check, the constraint check is performed for each of the connection constraint and the allocation constraint in step 1090, and the result is displayed.

The constraint check is performed by the connection constraint storage matrix 8001 and the allocation constraint storage matrix 800.
This is done by checking whether or not the connection constraint and the allocation constraint stored in 2 are violated.

FIG. 22 is an explanatory diagram showing a display example of a violation part of the connection constraint. The arc 22011 of the violation part is blinked and the content of the violation is displayed on the window 22010. In the window 22010, the “connection constraint 2” shown in FIG. 19 is violated, and it is displayed in the node B that connection is impossible.

FIG. 23 is an explanatory view showing a display example of a violation part of the allocation constraint. The node 23011 at the violation part is blinkingly displayed (blinking) and the violation content is displayed on the window 23010. In addition, instead of blinking display,
The line thickness or color of the corresponding arc or node may be changed.

When the discard of the plan is selected, the solution search parameter is corrected and the solution search is restarted from the beginning, and therefore the process returns to step 1020 of the main processing flow.

If you choose to approve the plan, step 1
Format conversion and printing at 100.

The approved plan is registered as a formal plan, and the operation plan table for all vehicles for January is converted into a practical format and then output from the printer.

FIG. 24 is a block diagram of a system for carrying out the above-described operation plan creating method. A keyboard 2401 for inputting basic information and a pointing device 240 used for inputting connection restrictions and the like on a graph screen.
2. A display 2403 for displaying constraint satisfaction solutions and the like, a printer 2405 for printing out constraint satisfaction solutions, a processing device 246 for performing the processing shown in the flowchart of FIG. 1, and a storage device 2407 for storing various information such as connection constraints. It is configured.

The processing device 2406 has a processing function corresponding to each step of the flowchart of FIG. That is, basic information input processing 2411, solution search parameter input processing 2412, gene information initialization processing 2413, constraint condition input processing 2414, partial solution freezing processing 2415, optimization processing 2416, alternative generation processing 2417, constraint check processing 2418, A format conversion / print processing 2419 is provided.

The storage device 2407 has a connection constraint storage matrix 8001 and an allocation constraint storage matrix 80.
02 is provided with storage areas 2420 and 2421 for storing 02, a gene storage area 2422, and an evaluation value storage area 2423 for storing evaluation values of each gene.

In this system configuration, the processing device 2
406 performs the same processing as described in FIGS.
A solution satisfying the connection constraint and the allocation constraint is searched for and displayed on the screen of the display 2403 or the printer 240.
Print out from 5. The detailed description is omitted because it overlaps with the description of FIGS.

In FIG. 24, the processing shown in each step of FIG. 1 is configured to be executed by one processing apparatus, but it may be configured to be distributed and executed by a plurality of processing apparatuses. Good.

As described above, according to the operation plan creating method and system of the present embodiment, (1) a two-dimensional matrix which is a solution expression of the constraint conditions for operating the vehicle in accordance with the train schedule and the inspection plan. By mapping the above, it becomes possible to link the operation of modifying the plan and the operation of adjusting the constraint conditions, and the search rules and constraint conditions can be efficiently modified in response to changes in the operation plan creation conditions, etc. Can be easily reflected in the vehicle operation plan.

(2) Since the vehicle operation plan can be displayed / corrected by the graph editing operation, the operation plan can be easily evaluated and the constraints can be checked, and the efficiency of the operation plan preparation work can be improved.

(3) When a new constraint is added or a constraint violation is resolved, partial freezing processing is performed so as not to break the solution at the present time. It is possible to efficiently search for a solution satisfying the constraint when operating the train.

(4) When the graph creating operation or the modifying operation is performed using the pointing device, the strength of the connection constraint or the allocation constraint is expressed by the thickness or the color of the arc connecting the two nodes. Therefore, it is possible to intuitively identify whether the constraint condition is a mandatory condition or a target condition, and the operability is improved.

(5) With respect to the portion that violates the connection constraint or the allocation constraint, the thickness or color of the line of the corresponding arc or node is changed or blinked. Can be grasped.

(6) Since the optimum solution is searched by the genetic algorithm, the optimum solution can be obtained without changing the search rule in response to a multidimensional combination of constraints or a change in the planning condition. It is possible to flexibly respond to changes in planning conditions.

In the above embodiments, the case of creating a train operation plan has been described, but the same can be applied to the case of creating an operation plan of operating equipment such as buses, aircraft, taxis, and ships. Needless to say.

[0138]

According to the present invention, the following effects can be obtained.

(1) By linking the constraint conditions for operating a vehicle according to the train schedule or the inspection plan on the two-dimensional matrix that is the solution expression, the plan correction operation and the constraint condition adjustment operation are linked. Therefore, it is possible to efficiently modify the search rule and the constraint condition in response to the change of the operation plan creation condition and the like, and easily reflect the user's intention in the vehicle operation plan.

(2) Since the vehicle operation plan can be displayed / corrected by the graph editing operation, the operation plan can be easily evaluated and the constraints can be checked, and the efficiency of the operation plan preparation work can be improved.

(3) When a new constraint is added or when a constraint violation is resolved, partial freeze processing is performed so as not to break the solution at the present time. It is possible to efficiently search for a solution satisfying the constraint when operating the train.

(4) Since the optimum solution is searched by the genetic algorithm, the optimum solution can be obtained without changing the search rule in response to a multidimensional combination of constraints or a change in the planning condition. It is possible to flexibly respond to changes in planning conditions.

[Brief description of drawings]

FIG. 1 is a main process flow chart showing an embodiment of a vehicle operation plan creation method of the present invention.

FIG. 2 is an explanatory diagram showing a basic information input screen.

FIG. 3 is an explanatory diagram showing an input screen for a solution search parameter.

FIG. 4 is an explanatory diagram of a method for initializing gene information.

FIG. 5 is an explanatory diagram showing a constraint condition input screen.

FIG. 6 is an explanatory diagram showing an example of definition of connection constraint.

FIG. 7 is an explanatory diagram showing an example of definition of an allocation constraint.

FIG. 8 is an explanatory diagram of a storage location of a constraint condition.

FIG. 9 is a flowchart of a partial freezing process of a solution.

FIG. 10 is an explanatory diagram of a solution partial freezing process.

FIG. 11 is a flowchart of optimization processing.

FIG. 12 is a flowchart of decoding processing.

FIG. 13 is an explanatory diagram of a decoding method.

FIG. 14 is a flowchart of evaluation processing.

FIG. 15 is a schematic explanatory diagram of a natural selection process.

FIG. 16 is a schematic explanatory diagram of a crossover process.

FIG. 17 is a schematic explanatory diagram of mutation processing.

FIG. 18 is an explanatory diagram showing an example of a vehicle operation graph.

FIG. 19 is an explanatory diagram showing an example of changing and inputting a connection constraint.

FIG. 20 is an explanatory diagram showing an example of changing and inputting an allocation constraint.

FIG. 21 is an explanatory diagram of alternative generation processing.

FIG. 22 is an explanatory diagram of a function of checking a violation part of a connection constraint.

FIG. 23 is an explanatory diagram of a check function of a violation part of an allocation constraint.

FIG. 24 is a block diagram showing an embodiment of an operation plan creation system.

[Explanation of symbols]

2401 ... Keyboard, 2402 ... Pointing device, 2403 ... Display, 2405 ... Printer,
2406 ... Processing device, 2407 ... Storage device, 2411 ...
Basic information input processing, 2412 ... Solution search parameter input processing, 2413 ... Gene information initialization processing, 2414 ... Constraint condition input processing, 2415 ... Solution partial freezing processing, 2416
... optimization process, 2417 ... alternative generation process, 2418 ... constraint check process, 2419 ... format conversion / print process, 24
22 ... Gene storage area, 2423 ... Evaluation value storage area, 4
010j ... Gene, 8001 ... Connection constraint storage matrix, 8002 ... Allocation constraint storage matrix.

Claims (12)

[Claims] 1. The operation number and date of the operating equipment 2
After providing a storage area for a dimensional matrix and a storage area for a plurality of genes having the same matrix structure as this two-dimensional matrix, the constraint conditions to be considered when assigning operating equipment to any of a plurality of operation numbers are described above. After setting and storing in a corresponding mesh of a two-dimensional matrix, different gene codes are randomly set in the storage regions of the plurality of genes to generate a plurality of genes having different gene codes, and Allocation processing for allocating operation equipment to any operation number is performed based on each gene code and the constraint condition of the corresponding mesh, and a plurality of operation plans corresponding to each gene obtained after this allocation process are satisfied with the constraint condition. A method for creating an operation plan for operating equipment, characterized by outputting an operation plan with a high evaluation value. 2. A plurality of operation plans corresponding to each gene obtained after the allocation processing are evaluated by a degree of satisfaction with the constraint condition, and the gene codes of the plurality of genes are recombined based on the evaluation value, Based on each gene code of a plurality of genes after recombination and the constraint condition of the corresponding mesh, an allocation process for allocating operation equipment to any operation number is performed, and a plurality of operations corresponding to each gene obtained after this allocation process are performed. The process of evaluating the plan by the degree of satisfaction with the constraint condition is repeated for a predetermined number of generation alternations, and the evaluation value for the constraint condition is high among a plurality of operation plans corresponding to each gene obtained after the repetition process. The method for creating an operation plan for operating equipment according to claim 1, wherein the operation plan is output. 3. With respect to the change of the constraint condition which is the basis of the output operation plan, the allocation of the operating equipment that satisfies the changed constraint condition is frozen, and the allocation process is performed only for the constraint condition that is not satisfied. Claim 1 or 2 characterized
How to create an operation plan for any of the operating equipment listed. 4. The operation plan is edited and output as a connection graph between nodes arranged in each mesh on a two-dimensional matrix consisting of an operation number and a date, and output. How to create an operation plan for any of the operating equipment. 5. The change of the constraint condition is performed by changing the connection graph.
How to make an operation plan for the listed operating equipment. 6. The constraint condition comprises an assignment constraint when allocating an operating device to one of the operation numbers of the day and a connection constraint when connecting a specific operation number of the previous day and an operation number of the day. The method for creating an operation plan for operating equipment according to any one of claims 1 to 5. 7. The operation number and date of the operating equipment 2
Dimension matrix storage area, storage area for a plurality of genes having the same matrix structure as this two-dimensional matrix, and constraint conditions to be considered when assigning operation equipment to any of a plurality of operation numbers Means for setting and storing in a mesh to store, a means for generating a plurality of genes having different gene codes by randomly setting different gene codes respectively in the storage regions of the plurality of genes, and each gene code of the plurality of genes And a means for performing an allocation process for allocating the operating equipment to any operation number based on the constraint conditions of the corresponding mesh, and a plurality of operation plans corresponding to each gene obtained after the allocation process with a degree of satisfaction with the constraint conditions. Operational equipment comprising means for evaluating and means for outputting an operation plan with a high evaluation value Operational planning system. 8. An operation device based on a means for recombining gene codes of a plurality of genes based on the evaluation value of the evaluating means, and the constraint condition of mesh corresponding to each gene code of the plurality of genes after the recombination. Is assigned to any operation number, and means for repeatedly performing the process of evaluating the degree of sufficiency with respect to the constraint conditions by the number of generation alternations specified in advance is provided, and each gene correspondence obtained after the completion of the iterative process 8. The operation equipment operation plan creation system according to claim 7, wherein an operation plan having a high evaluation value for the constraint condition is output from the plurality of operation plans. 9. The method further comprises means for freezing the allocation of operating equipment that satisfies the changed constraint conditions in response to the change of the constraint conditions that are the basis of the output operation plan, and only for constraint conditions that do not satisfy the constraint conditions. 10. The operation equipment operation plan creation system according to claim 7, wherein the allocation processing is performed. 10. The method according to claim 7, further comprising means for editing and outputting the operation plan as a connection graph between nodes arranged in each mesh on a two-dimensional matrix consisting of operation numbers and dates. ~ An operation plan creation system for any of the operating equipment described in 9 above. 11. The operation equipment operation plan creation system according to claim 10, further comprising means for changing the constraint condition according to an operation of changing the connection graph. 12. The constraint condition comprises an assignment constraint when allocating an operating device to one of the operation numbers of the day and a connection constraint when connecting a specific operation number of the previous day and an operation number of the day. An operation plan creation system for operating equipment according to any one of claims 7 to 11.