JPH08310399A - How to make a train schedule - Google Patents

Abstract

(57) [Summary] [Purpose] To provide an operation schedule creation method that enables generation of an optimum schedule schedule with a small amount of labor when creating a schedule schedule from mountain schedules. [Structure] Priorities are given to the diagonal lines forming the mountain diamond. A sequence of priority is set as a chromosome, and a first population that is a set of the chromosomes is generated. Crossover and mutation are performed on each chromosome of the first population based on predetermined criteria to generate a second population of new chromosomes. Based on each chromosome of the first group and the second group, each horizontal line corresponding to each diagonal line is divided into a predetermined number of rows and arranged to generate a work schedule. The generated work schedule is evaluated based on a predetermined standard, and a third group consisting of chromosomes corresponding to each work schedule that satisfies the evaluation standard is generated. The above processing is repeated with the third group as the first group to generate a work schedule.

Description

Detailed Description of the Invention

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a method for automatically creating a bus schedule for a bus, train, etc., and in particular, for each crew member or each vehicle based on a mountain schedule showing the operating status of the entire bus or train. The present invention relates to a method for creating an operation schedule that automatically generates a schedule for operations that represents the details of the schedule.

[0002]

2. Description of the Related Art In the transportation business for operating route buses and trains, a diagram called a mountain diagram is usually used in order to grasp at a glance all the operating conditions in a predetermined business line area. On the other hand, in order to grasp at a glance which work is assigned to each crew member or each vehicle in what order, a diagram called a work schedule is used.

As shown in FIG. 4, a mountain diagram means that each stop in a business line section is arranged in order along the vertical axis based on the distance (actual distance or temporal distance), and the horizontal axis indicates the time axis. , Are arranged on the coordinate plane, the diagonal lines 401, 402, ...
The operation status of each vehicle (bus in this example) represented by 406 is described. Also, diagonal lines 401, 402,
.., 406 indicates the state of one operation (one operation) from the start point to the end point by the same crew member and the same vehicle. One diagonal line is uniquely determined by the position (stop name) of each of the start point and the end point and the departure (or arrival) time. The intersection of the horizontal line indicating the position of each stop and the diagonal lines 401, 402, ..., 406 represents the time when the vehicle arrives at (or departs from) that stop. For example, the bus indicated by diagonal line 402 is "B
Intersection 4 is the time to arrive at (or depart from) the City Hall
It is "7 o'clock" indicated by 07.

As shown in FIG. 6, the work schedule means that numbers or names (001 and 002 in the figure) for identifying crew members in the vertical direction are arranged by the number of crew members (two in this case), and the horizontal axis direction. The time axis is located at the diagonal line 401, 402,
, 406 are arranged such that the respective line segments such as horizontal lines 601, 602, ..., 606 in which the starting point of each line corresponds to the left end and the ending point corresponds to the right end do not overlap each other by the number of diagonal lines. The work schedule can be regarded as one in which all the daily operations represented by the mountain schedule are assigned to each crew member in consideration of working conditions. The length of each horizontal line represents the time the vehicle is operating, and the stop name at the starting point on the left end (only the initial letters are shown in the figure)
The departure time and departure time (only minutes are shown in the figure) are accompanied by the stop name at the end and the arrival time there. The horizontal lines 601, 602, ..., 606 in FIG. 6 correspond to the diagonal lines 401, 402 ,. Looking at FIG. 6, the crew member 001 shows the horizontal lines 601 and 60.
It can be seen that the jobs represented by Nos. 4, 605, and 606 are in charge in this order, and the crew member 002 is in charge of each job represented by the horizontal lines 602 and 603 in this order. Flight attendant 001
By looking at the horizontal line 601, it is possible to confirm that this work, which he is in charge of, departs from City Hall B at 6:30 and arrives at Station A at 6:50 from City Hall B to Station A.

After creating one mountain timetable, the business operator tries to obtain an optimum work timetable that allows the bus to be operated according to the mountain timetable and satisfying various conditions such as working conditions. . In the past, this series of work was performed manually. However, in general, the work schedule is not uniquely determined from the mountain schedule, and a plurality of ways can be considered, so the manual method is inefficient. Therefore, conventionally, an AI-like method has been proposed in which this work is performed by using a knowledge base in which knowledge of experts is accumulated. For example, JP-A-3-
There are 112769 and so on.

[0006]

There are as many production diamonds as can be generated from one mountain diamond, and the number of permutations / combinations of all the diagonal lines constituting the mountain diamond exists. Therefore, it is relatively easy to create a mountain diamond, but it is usually difficult to create a work diamond based on the mountain diamond thus created.

When this work is performed manually, it is basically a manual work relying on the knowledge and intuition based on the expert's many years of experience, and therefore it depends on the individual differences such as the experience, skill level, and habit of the expert who is the worker. However, there is a problem that the results obtained by different workers are different. Further, the number of types of work schedules that can be created from one mountain schedule is generally enormous due to the combination, and when the working conditions are taken into consideration, the schedule organization work becomes more complicated. For this reason, it takes a considerable amount of time and labor to manually obtain a work schedule suitable for the conditions, and furthermore, there is a problem that an optimal solution is not always obtained.

Further, in the AI-based method based on the knowledge base, it is necessary to draw out the expert knowledge for creating the work schedule from the expert, organize it, and accumulate it in the knowledge base. There is a problem that it takes an enormous amount of time and labor to acquire knowledge when constructing this knowledge base.

The present invention has been made in view of the above problems, and in the production of a work schedule, it is possible to obtain a uniform result regardless of which operator produces it, and to obtain an optimum solution with a small amount of time and labor. It is an object of the present invention to provide a method for creating an operation schedule that makes it possible to obtain an optimum work schedule without requiring the work of accumulating knowledge of experts.

[0010]

According to the present invention, a priority is assigned to each diagonal line forming a mountain diamond, and the priority is arranged.
One symbol string is regarded as one chromosome, and this is made to correspond to one work schedule, and a genetic algorithm is applied to the process of generating a work schedule from a mountain schedule.

In the system in which the mountain diamond is input, each element of the sequence symbol string consisting of the same number of elements as the number of the diagonal lines is set as 1 for each of the diagonal lines constituting the mountain diamond.
Randomly correspond and give each one. In this way, one symbol string configured by randomly assigning the priority becomes one chromosome. A plurality of chromosomes are generated by repeating the operation of randomly giving the priority a predetermined number of times. A set consisting of these chromosomes is referred to as a first group (initial group). Next, the second group of new chromosomes is generated by rearranging the priorities of the respective chromosomes constituting the first group based on a predetermined standard. As a method of rearranging the priority, crossovers in which subsequences formed by dividing a chromosome at one or more boundary lines are exchanged with each other over a plurality of chromosomes, and some of the priorities constituting the chromosomes are randomized. There is a mutation to change to another one, and these may be performed at a predetermined rate (mutation rate). Up to this point, so-called "generational change" has been performed, and when the first group is the "parent", the second group corresponds to the "child".

Next, for each chromosome forming the first group and the second group, by arranging each diagonal line corresponding to each priority forming one chromosome based on the priority, Generate a work schedule. Specifically, the work schedule can be generated by an assignment process in which each diagonal line is first converted into a horizontal line and the horizontal line is divided into a predetermined number of columns based on the priority. This allocation processing is performed, for example, by causing the horizontal line to be allocated to follow the horizontal line that has already been allocated and has the highest priority among the last allocated horizontal lines in each column.

Next, each of the generated operation schedules is evaluated based on a predetermined standard, and for each business schedule that satisfies the evaluation standard, a third group of corresponding chromosomes is generated and the evaluation standard is satisfied. For each operation schedule that does not exist, the corresponding chromosome is deleted. This is called selection. As an evaluation method, for example, among the operation timetables in which the rest time of each crew member and the transfer time of the vehicle are a predetermined number of hours or more, the smaller the total number of unassigned horizontal lines, the higher the evaluation value. Can be given and done. With such an evaluation, selection can be realized by leaving a predetermined number of chromosomes in order from the one with the highest evaluation value and configuring the third group with the remaining chromosomes. The third group is
It is a “sophisticated survivor” by selection and is eligible to become a “parent” in the next selective breeding.

In this way, each of the chromosomes constituting the third group is subjected to the above-mentioned crossover or mutation in the same manner as in the case of the first group, and the above-mentioned crossover / mutation, assignment, and selection are repeated. An optimal work schedule is generated by a genetic algorithm.

[0015]

The present invention focuses on the fact that a genetic algorithm can be applied to system construction without describing rules, and that it is possible to escape from a local solution, and a mountain that expresses the operating status of buses and trains. This algorithm is applied to the process of creating a work schedule representing the work content of each crew member from the schedule. By using the operation timetable creation method of the present invention, the operation timetable can be created without being caught by the rules created by the timetable creator, and the operation suitable for each operator operating a bus or train depending on the evaluation conditions. You can create a diamond. Furthermore, the system construction can be completed in a short time because the description of rules is unnecessary.

[0016]

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS An embodiment of the method for creating an operation timetable of the present invention will be shown below, and the present invention will be described with reference to the drawings. It should be noted that the present embodiment is an example in the case of creating a bus schedule for a route bus.

FIG. 3 shows the hardware configuration of this embodiment. The input unit 301 is for inputting information from an operator, and a known input unit such as a keyboard or a pointing device can be used. The control means 302 is a part that executes a genetic algorithm applied to the operation schedule creation method of the present invention, has a CPU and a temporary storage means, and creates or modifies a work schedule according to the input information. A known workstation, personal computer, or the like can be used as the control unit 302. The work area 303 is the control device 3
It is allocated on the temporary storage means included in No. 02, and is used as a work area when creating a mountain timetable and a work timetable in this embodiment. The basic data file 304 is a means for storing the information input to create a work schedule. The basic data file 304 includes, for example, working hours, restraint times, meal hours, handle times, etc. entered as working conditions, or departure / arrival place names entered as bus departure / arrival location information, presence / absence of garage, and meals. Whether or not it is stored is stored. The mountain diagram data file 305 is a unit for storing mountain diagram data created or modified by the control unit 302 based on the information of the basic data file 304. Work schedule data file 30
Reference numeral 6 is a means for storing the data of the work schedule created or modified by the control device 302 based on the information in the basic data file 304 and the mountain schedule data file 305.
The parameter data file 307 is means for storing / holding parameter information necessary for executing the genetic algorithm. The parameter data file 307 stores and holds parameter information such as the number of generations to be generated, the number of individuals to be generated, and the mutation occurrence rate. Each file 304-30
For example, a magnetic disk device or an arbitrary storage device can be used for 7. The display unit 308 visually displays the work schedule created by the control unit 302, and a CRT display device or the like can be used.
Although not shown in FIG. 3, it goes without saying that an output device such as a printer and other computer peripheral devices can be provided in addition to the above.

Next, a method of creating a work schedule in this embodiment will be described in detail along the flow of processing shown in FIGS.

The operator of the system firstly, in addition to the information regarding the bus operating time, the working conditions such as working hours, restraint time, meal time, handle time, etc., and the departure and arrival place name as the departure and arrival place information of the bus, The presence or absence of a garage, the availability of meals, etc. are input by the input means 301, and these information are stored in the basic data file 304. Control means 302
Creates a mountain diamond based on the operator's instruction and the input information stored in the basic data file 304, and stores it in the mountain diamond data file 305 (step 10).
1). A known method can be used to create the mountain diagram.

The control means 302 creates a mountain timetable list based on the mountain timetable data stored in the mountain timetable data file 305 (step 102). FIG. 5 is FIG.
It is a mountain diamond list created from the mountain diamond. In this example, the contents of each work represented by each diagonal line 401, 402, ..., 406 are the priority 502, the starting point stop name and departure time 503, and the ending point stop name and arrival time 5
The information is represented as a set of information 04, which is arranged in the order of departure time of the starting point to form a mountain timetable. FIG.
, 406 correspond to the order 501, 1, 2, ..., 6 on the list of FIG. 5, respectively. In this embodiment, when the mountain diamond list is created, the diagonal lines are arranged in order of the starting time of the starting point. However, the arrangement is not limited to this, and there is a certain rule in the arrangement so that the mountain diamond is unique from the mountain diamond list. It is arbitrary as long as it is determined by

A genetic algorithm (hereinafter referred to as "GA") is executed on the basis of the created mountain dialist. GA
The basic way of thinking is described in "Genetic Algorithms" edited by Hiroaki Kitano (Sangyo Tosho), pp. 3 to 16. The concepts necessary for applying GA include chromosomes, the number of individuals, the number of generations, mutation rate, selection, evaluation criteria, etc., and the meanings and roles of these are described in detail in the above-mentioned publicly known documents.

In the present invention, the diagonal lines 401 and 40 in FIG.
Each of the priorities 502 randomly assigned to 2, ..., 406 is set as an element gene, and a sequence in which these element genes are arranged is set as a chromosome. For example, the element gene 70 shown in FIG.
71 formed by arranging 1, 702, ..., 706 in an arbitrary order
A sequence such as 1, 712, ... Is a chromosome. Number 721
Represents the order 501 on the mountain dial list.

In this example, the element genes are integers from 1 to n. n is the number of horizontal lines, which is 6 here. A sequence of length n in which these are arranged in an arbitrary order becomes a chromosome.

The priority is information for determining to which of the already-assigned horizontal lines the horizontal line to be assigned will follow. The horizontal line to be assigned from now on is assigned after the horizontal line that has already been assigned and can be assigned subsequently to the horizontal line having the highest priority (minimum priority value).

For example, based on the chromosome 711 of FIG.
Consider assigning a mountain diamond list to a work schedule. The numbers used here are the numbers in the order 501 on the list. First, the number 1 data is the leading diagonal line 401.
Since there is no preceding assigned horizontal line, the line is converted into a horizontal line 601 and assigned unconditionally to the crew member 001.
The diagonal line 402 corresponding to the number 2 has a horizontal line 601 as a preceding horizontal line, but since the crew member 002 is empty, the horizontal line 6
Converted to 02 and unconditionally assigned to crew member 002. Next, the diagonal line 403 corresponding to the number 3 compares the priorities 2 and 1 of the two preceding horizontal lines 601 and 602, and assigns it as the horizontal line 603 following the horizontal line 602 having the smaller one as the priority. To be Furthermore, the diagonal line 404 corresponding to number 4 is the two leading horizontal lines 601 and 6
The priority levels 2 and 5 of 03 are compared with each other, and a horizontal line 601 having the smaller priority level 2 as a priority is followed by a horizontal line 604 and assigned as a horizontal line 604. Hereinafter, similar processing is repeated until the last number 6. The work schedule created by allocating is shown in Fig. 6.

When the assignment is performed in this way, the assignment pattern is uniquely determined from the chromosome that is the priority sequence. That is, one chromosome corresponds to one work schedule (however, a plurality of different chromosomes may correspond to the same work schedule). As described above, the chromosome 711 of FIG. 7 corresponds to the service schedule of FIG. 6, and does not correspond to other service schedules.

The execution of the GA in this embodiment will be described in detail below.

Generate an initial population (step 10)
3). Here, the group means a set of a plurality of chromosomes. The generation of the initial population is performed by randomly determining the order of arrangement of integers, which are element genes, and repeating this to generate a plurality of chromosomes.

Selective mating is performed on the generated initial population (step 104). As for the method of mating, in the present embodiment, it is assumed that a simple crossover in which a sequence of numbers is cut at a certain point and recombined with each other is applied.

Each chromosome obtained by the selective crossing is regarded as a mountain diamond list, and an allocation process is performed for each mountain diamond list (step 107). Note that step 107
The details of the above are shown in FIG.

One element gene representing the priority of the leading horizontal line is extracted from the extracted mountain diamond list (step 202). For example, horizontal line 501 and line 50
When the process for 2 has been completed, the head of the mountain diamond list is the gene representing the horizontal line 503, so this is taken out. A horizontal line corresponding to the extracted gene is assigned to the crew member (driver) (step 204). If there is a horizontal line that has already been assigned, it is checked whether the horizontal line to be assigned will overlap with it (step 20).
5). For example, when the horizontal line 503 is to be assigned, it is checked whether the horizontal lines 601 and 602 already exist in the work schedule and they do not overlap with each other in time. In this case, they do not overlap. It is checked whether the horizontal line to be assigned matches the work style of the assigned driver (step 206). The priority of the horizontal line adjacent to the horizontal line to be assigned is checked, and the horizontal line having the lowest priority is assigned (steps 207, 208,
209). For example, when the horizontal line 501 and the horizontal line 502 are compared in priority, the horizontal line 502 is smaller, so the line 403 is assigned after the horizontal line 502. Note that steps 205 and 20
The horizontal lines that are not allocated by the check of 6 and 208 are stored in the unallocated area (step 2
13).

It is checked whether allocation processing has been completed for all horizontal lines (step 215), and if not completed, the next horizontal line in the mountain dial list is taken out and the above operation is repeated. This is done for all the horizontal lines in the mountain timetable list to create one work timetable (step 216).

The above allocation process (step 107) is performed for all mountain dialys.

The work schedule created is evaluated (step 110). As the evaluation criteria, the total number of unassigned horizontal lines, rest time of each driver, meal time, forwarding time, etc. can be considered. The evaluation value is determined based on these. Needless to say, the evaluation standard can be changed or added by the operator of the system as needed. When an evaluation value is given to each work timetable, the work timetable with a low evaluation is removed by the determined number and selection (step 111). The selection is to remove a chromosome representing a work diamond having a low evaluation from the next mating target, and leave only a chromosome representing a work diamond having a high evaluation as a parent in the next selective mating.

FIG. 8 shows the state from selective mating to selection in this embodiment. Two chromosomes 801 and 802 in the initial group or the group that survived the previous selection are parents, and the chromosomes 803 and 804 generated by crossing each other with the boundary line 811 as a child are children. next,
Chromosome 80 satisfying the criteria by evaluating the work schedule corresponding to each of the chromosomes 801, 802, 803, 804
2 and 803 are left as parents 805 and 806 in the next selective cross, and chromosomes 801 and 804 that do not meet the criteria are removed.

As described above, from step 104 to step 111
Repeat the above process until the number of generations is reached (Step 1
12). The work diagram corresponding to the chromosomes remaining at the stage when the repetition is completed is the solution to be obtained (step 1).
13).

The embodiment described above makes it possible to generate an optimum work schedule.

The present invention is not limited to the embodiment, and various applications and modifications are possible. For example, although the present embodiment relates to bus operation schedule creation, the present invention is not limited to this, and can be applied to various transportation services such as railroad, aviation, and ships. Further, in the present embodiment, the attribute arranged in the vertical direction of the work schedule is the crew, but the attribute is not limited to this, and the vehicle may be used. Furthermore, in the present example, the simple crossover was applied at the time of selective mating, but the present invention is not limited to this, and mutation is carried out at a predetermined rate based on a preset mutation rate (some of the element genes are excluded). Changing to another one intentionally) may occur.

[0039]

As described above, by using the operation timetable creation method of the present invention in which the genetic algorithm is applied to the generation of the service timetable, it is possible to obtain the optimum solution which cannot be obtained by the local solution search. In addition, by selecting candidate solutions under the evaluation conditions, a better solution can be obtained and an optimal work schedule can be created.

[Brief description of drawings]

FIG. 1 is a flowchart showing the operation of an embodiment of the present invention.

FIG. 2 is a flowchart for assigning mountain diamonds to work diamonds in an embodiment of the present invention.

FIG. 3 is a diagram showing an example of a hardware configuration of the present invention.

FIG. 4 is a diagram showing a mountain diamond according to an embodiment of the present invention.

FIG. 5 is a diagram showing a mountain schedule according to an embodiment of the present invention.

FIG. 6 is a diagram showing a work schedule in one embodiment of the present invention.

FIG. 7 is a diagram showing chromosomes in an example of the present invention.

FIG. 8 is a diagram showing selective crossing and selection according to an example of the present invention.

[Explanation of symbols]

 101 Start 102 Mountain Dialist Creation 103 Initial Outbreak 104 Selective Mating 107 Assignment Process 110 Individual Evaluation 111 Selection 112 Conditional Branching by Number of Generations 113 End

Continuation of front page (51) Int.Cl. ⁶ Identification number Reference number within the agency FI Technical display location // G06F 17/60 G06F 15/21 C (72) Inventor Kenichiro Okada At 890 Kashimada, Kawasaki-shi, Kanagawa 12 Information Systems Division, Hitachi, Ltd.

Claims (6)

[Claims] 1. A system for generating a work schedule based on a mountain schedule, (a) assigning a priority corresponding to each of the slanting lines forming the mountain schedule, and (b) arranging the assigned priorities. To create a symbol string, and c) change the method of giving the priority and repeat steps a) to b) a predetermined number of times to generate a first group consisting of a plurality of symbol strings. D) A second group of new symbol strings is generated by rearranging the priorities of the respective symbol strings forming the first group, and e) the first group and the first group. For each symbol string forming the group of 2, the operation diamond is generated from each diagonal line corresponding to each priority forming one symbol string based on the priority, and (f) the generated operation diamond. By evaluating, satisfy the evaluation criteria. (3) For each work schedule, a third group consisting of the corresponding symbol strings is generated, and for each work schedule that does not meet the evaluation criteria, the corresponding symbol string is deleted. 2) as a group of 1) ~
A method for creating an operation timetable, characterized in that an operation timetable is generated by repeating the steps of (f). 2. The operation schedule creation method according to claim 1, wherein the symbol sequence corresponds to a chromosome, the rearrangement corresponds to a crossover, and the step of) is selected. A method for creating an operation schedule characterized by being equivalent to. 3. The rearrangement of the priority in the step (d) above according to claim 1,
A method for creating an operation timetable, characterized by comprising regular and non-regular sorting. 4. The method according to claim 1, wherein the step (e) corresponds to each priority that constitutes one symbol string for each symbol string that constitutes the first group and the second group. A method for creating an operation timetable, wherein each diagonal line is converted into a horizontal line which is a constituent element of the operation timetable, and the horizontal line is divided into a predetermined number of rows based on the priority to generate the operation timetable. 5. The method according to claim 4, wherein, in the step (e), a horizontal line to be arranged is a horizontal line that has already been arranged and is assigned the last priority in each column. A method for creating an operation timetable, which is characterized by arranging it following a high horizontal line. 6. The evaluation according to claim 4, wherein the evaluation in the step (f) is based on the transfer time of each vehicle corresponding to the horizontal line, the rest time of each crew member, and the total number of unaligned horizontal lines. A method for creating an operation schedule, which is characterized in that it is performed based on