JP7744286B2 - Maintenance work schedule creation device and maintenance work schedule creation method - Google Patents

Description

The present invention relates to a maintenance work schedule creation device, etc.

On railways, maintenance work such as cleaning the interiors of return trains is performed at return stations. A maintenance schedule is a timetable that determines which return trains maintenance workers will perform maintenance on and in what order. Because the return train schedule varies from day to day, and the number of workers and working hours on a given day also vary, a maintenance schedule must be created for each day. However, there is no known technology for automatically creating a maintenance schedule using a computer. For ease of understanding, this specification will refer to creating a maintenance schedule, including the creation of a "proposed maintenance schedule."

Similar technologies include a technology for easily and efficiently determining staffing allocation for multiple tasks in home care and nursing services (see Patent Document 1), and a technology for rescheduling cleaning and other tasks when vehicle operations are changed due to train schedule rescheduling (see Patent Document 2).

JP 2019-082784 A JP 2017-81267 A

The technology of Patent Document 1 first sets tasks and assigns personnel capable of performing each task, without considering whether the assignment results in an unfair or unequal allocation for certain personnel. The technology of Patent Document 2 first sets vehicle operations and then creates a work plan by having workers select and specify tasks that they can perform within the time frame of the changed vehicle operations (see, for example, paragraph [0010]). Therefore, whether the work plan is appropriate for each worker's working conditions or is an inappropriate work plan for a specific worker is up to the discretion of the person selecting and specifying the tasks. Furthermore, the work plan cannot be created automatically. As described above, similar technologies are difficult to apply directly to creating maintenance work schedules. In particular, maintenance work schedules must be created based on predetermined factors such as the number of workers, each worker's working hours, break times, and fixed work times. Additionally, maintenance work schedules have specific requirements, such as leveling out the work assigned to each worker and minimizing the amount of time each worker spends working consecutively, and these must be taken into consideration when creating them.

The problem that this invention aims to solve is to provide technology for automatically creating maintenance work schedules.

The first invention for solving the above problem is:
A return train schedule acquisition means (for example, the acquisition unit 202 in FIG. 11 ) that acquires a return train schedule in which the track number and time of each return train that is the target of maintenance work at a given return station are specified;
a worker group setting unit (e.g., the worker group setting unit 204 in FIG. 11 ) for setting a plurality of worker groups each having a predetermined start time and end time;
a fixed task setting unit (for example, the fixed task setting unit 206 in FIG. 11 ) that sets a fixed task with a predetermined start time and end time for each of the set worker groups;
a candidate solution generating means (e.g., the candidate solution generating unit 208 in FIG. 11 ) that generates, for each of the set worker groups, a candidate solution for a maintenance work timetable in which maintenance work trains to be performed by the worker group among the return trains set in the return train timetable and the fixed work set for the worker group are assigned in chronological order between the start time and the end time of the work for the worker group, and the candidate solution satisfies a platform change required time condition when the platform platforms of the previous and next maintenance work trains assigned to the same worker group are different;
a selection means (e.g., the selection unit 212 in FIG. 11 ) for selecting a final solution from the generated candidate solutions based on a given evaluation index;
The maintenance work schedule creation device is provided with the above.

Other inventions include:
A maintenance work schedule creation method for creating a maintenance work schedule to which a worker group is assigned for each turn-back train that is the subject of maintenance work at a given turn-back station, comprising:
Obtaining a return train schedule that specifies the track number and time of each return train that is subject to maintenance work at the return station;
Setting a plurality of worker groups each having a predetermined start time and end time;
setting a fixed work having a predetermined start time and end time for each of the set worker groups;
Generate a plurality of candidate solutions for a maintenance work timetable that assigns, for each of the set worker groups, maintenance work trains to be performed by the worker group among the return trains set in the return train timetable and the fixed work set for the worker group in time series between the start time and the end time of the work for the worker group, and that satisfy a platform change required time condition when the platform platforms of the previous and next maintenance work trains assigned to the same worker group are different (for example, steps S1 to S21 in FIG. 3);
selecting a final solution from the generated candidate solutions based on a given evaluation index (e.g., step S23 of FIG. 3);
A maintenance work schedule creation method including the steps of:

According to the first invention, maintenance work schedules can be automatically created. That is, for each set worker group, multiple candidate solutions are generated that assign the maintenance work trains to be subjected to maintenance work and the fixed work set for that group between the start and end times of work, and that satisfy the platform change time conditions when the platform platforms of the previous and next maintenance work assigned to the same group are different. A final solution for the maintenance work schedule is then selected from the generated candidate solutions based on a given evaluation index. This makes it possible to create an appropriate maintenance work schedule based on a given evaluation index, without creating a maintenance work schedule that is too forceful for workers to change platform platforms.

A second invention is the first invention,
the selection means evaluates the candidate solutions using an evaluation index based on the platform movement time due to the difference in the platform platforms of the preceding and following maintenance work trains assigned to the same worker group in the candidate solutions, and selects the final solution.
This is a maintenance work schedule creation device.

According to the second invention, it is possible, for example, to select a candidate solution with the shortest track travel time for maintenance work assigned to the same worker group as the final solution for the maintenance work timetable.

A third invention is the first or second invention,
the candidate solution generating means generates a new candidate solution by switching the maintenance work trains between the worker groups for the previously generated candidate solution.
This is a maintenance work schedule creation device.

According to the third invention, a new candidate solution can be generated by swapping maintenance work trains between worker groups for a previously generated candidate solution. For example, a new candidate solution can be generated by swapping maintenance work trains operating in the same time slot. Furthermore, by swapping one of consecutive maintenance work tasks with a maintenance work task performed by a different worker group, a candidate solution can be generated that eliminates the consecutive maintenance work tasks.

A fourth invention is the first to third inventions,
A basic work time for the maintenance work for one return train is specified,
the candidate solution generating means generates the candidate solution for the same worker group such that an overlap time between a work period based on the basic work time for the maintenance work train and a fixed work period from the start time to the end time for the fixed work satisfies a given overlap time condition.
This is a maintenance work schedule creation device.

According to the fourth invention, it is possible to generate candidate solutions for maintenance work schedules that can be arbitrarily set to allow or disallow overlap between the work periods of maintenance work assigned to the same worker group and fixed work periods, depending on the number of minutes of overlap that constitutes the overlap time condition.

A fifth aspect of the present invention is the fourth aspect of the present invention,
The candidate solution generating means
a success/failure determination means for determining whether the candidate solution has been successfully generated based on whether all of the turn-back trains defined in the turn-back train timetable have been assigned as the maintenance work trains of any of the worker groups;
overlap time condition changing means for changing the overlap time condition;
having
This is a maintenance work schedule creation device.

According to the fifth invention, if it is determined that the generation of a candidate solution is not successful because all turn-back trains are not assigned as maintenance work trains for a worker group, the overlap time condition can be relaxed. As a result, the allowable overlap time between the work period of maintenance work assigned to the same worker group and the fixed work period increases, improving the possibility of generating a candidate solution in which all turn-back trains are assigned as maintenance work trains for a worker group.

A sixth invention is any one of the first to fifth inventions,
the candidate solution generating means generates a candidate solution that satisfies an upper limit number allocation condition related to the number of maintenance work trains to be allocated to the same worker group.
This is a maintenance work schedule creation device.

According to the sixth aspect of the present invention, for example, it is possible to generate a candidate solution in which the number of maintenance work trains assigned to the same worker group is equal to or less than the upper limit. This increases fairness and equality regarding work between worker groups.

A seventh invention is any one of the first to sixth inventions,
When the time interval between two maintenance work trains assigned to the same worker group satisfies a predetermined short time condition, the candidate solution generation means generates a candidate solution as a work time obtained by adding a given additional time to the work time for maintenance work of the latter of the two maintenance work trains.
This is a maintenance work schedule creation device.

According to the seventh aspect of the present invention, for example, when consecutive maintenance work tasks with short time intervals are assigned to the same worker group, a candidate solution can be generated in which a given additional time is added to the work time for the latter maintenance work. This makes it possible to create a maintenance work schedule that takes into account worker groups that perform multiple maintenance work tasks in succession with short time intervals.

An eighth invention is any one of the first to seventh inventions,
The selection means
an evaluation index based on the number of time intervals between maintenance work trains assigned to the same worker group in the candidate solution that satisfy a predetermined short time condition;
an evaluation index indicating the variation in the distribution of maintenance work train allocation times among each worker group in the candidate solution;
evaluating the candidate solutions using at least one of the following to select the final solution;
This is a maintenance work schedule creation device.

According to the eighth invention, for example, a candidate solution with a small number of consecutive maintenance work assignments with short time intervals between them when assigned to the same worker group, or a candidate solution with small variation in the distribution of maintenance work assignment times between each worker group, can be selected as the final solution for the maintenance work schedule.

A ninth invention is any one of the first to eighth inventions,
The worker group includes a plurality of divisions each having a different type of maintenance work,
For each of the categories, the worker group setting means sets a worker group, the fixed task setting means sets a fixed task, the candidate solution generation means generates candidate solutions, and the selection means selects a final solution.
This is a maintenance work schedule creation device.

According to the ninth invention, candidate solutions are generated for each category of multiple worker groups with different types of maintenance work, and a final solution is selected, and the set of final solutions for each selected category can be used as the final maintenance work schedule.

Overview of the creation of a maintenance work schedule. FIG. 10 is an explanatory diagram of a graph structure for creating a maintenance work schedule. 10 is a flowchart of a maintenance work schedule creation process. FIG. 10 is a flowchart of an initial solution generation process. An example of a graph structure with the current time initially set for a worker group. An example of a graph structure with the first and last maintenance tasks assigned. An example of a graph structure with additional work assigned. An example of a graph structure in which the current time exceeds the start time of a fixed task. An example of a graph structure after an initial solution is generated. 1 shows an example of the functional configuration of a maintenance work schedule creation device.

Preferred embodiments of the present invention will now be described with reference to the drawings. Note that the forms to which the present invention can be applied are not limited to the following embodiments. In addition, the same elements will be designated by the same reference numerals throughout the drawings.

[overview]
In this embodiment, a maintenance work schedule is created, which is a plan for maintenance work on turn-back trains at turn-back stations. Of course, the created maintenance work schedule may be a draft of the maintenance work schedule that will ultimately be used. Therefore, creating a draft maintenance work schedule is also included in creating the maintenance work schedule of this embodiment.

Figure 1 is a diagram showing an overview of this embodiment. As shown in Figure 1, the maintenance work diagram creation device 1 is provided with turn-back train schedule data 310 (see Figure 11), which is data on the turn-back train schedule 10 at turn-back stations, maintenance work data 320 related to maintenance work for each turn-back train defined in the turn-back train schedule 10, and worker group data 330 related to multiple worker groups performing maintenance work. The maintenance work diagram creation device 1 uses this data to create a maintenance work schedule 20 (more precisely, maintenance work schedule data 370 (see Figure 11) which is data on the maintenance work schedule 20).

The return train schedule 10 is a train schedule that specifies the train number, platform, and arrival/departure times (arrival and departure times) for each return train that operates at a return station.

For each maintenance task, the maintenance task data 320 includes a task number, which is the train number of the target return train, the task content, start time, and end time. Maintenance tasks include, for example, cleaning the interior of the train, checking for lost items inside the train, and providing water. The start and end times of maintenance tasks are determined based on the arrival and departure times of the return train. In other words, they are set so that they occur within the period between the arrival and departure times of the return train and are equal to or longer than the predetermined basic maintenance task time for one return train (e.g., 10 minutes).

For each worker group, worker group data 330 includes a group ID, category, start time, end time, and fixed task data 332. The category is the type of maintenance work performed, such as a cleaner responsible for cleaning the interior of the train, a cleaning manager responsible for managing the interior cleaning and checking for lost items, or a water supply manager. Fixed task data 332 is data related to fixed tasks that are defined as tasks that the corresponding worker group must perform, and includes the fixed task number, task content, start time, and end time. Fixed task content includes, for example, breaks, team meetings, and preparatory work required for maintenance work, and is work performed in a location separate from the station platform. The start and end times of fixed tasks are determined to ensure sufficient work time according to the content of the fixed task.

The maintenance work schedule 20 is schedule data that chronologically assigns to each worker group the maintenance work (maintenance work trains) that the group will perform and the fixed work assigned to that group during the work period from the start time to the end time.

In this embodiment, a maintenance work schedule is created using a graph structure. Figure 2 is a diagram explaining the graph structure used to create a maintenance work schedule. The graph structure used in this embodiment is a structure in which two nodes are connected by a directed arc that follows the passage of time. A node represents a task assigned to a worker group, and an arc represents the worker group's movement between tasks. In Figure 2, each node is arranged with time running horizontally. Furthermore, for maintenance work nodes, each node is arranged with the track number of the turnaround station running vertically. Furthermore, the start node, end node, and fixed work node are displayed with the group ID of the corresponding worker group, and the maintenance work node is displayed with the train number of the corresponding turnaround train.

Node types include start nodes and end nodes, which represent the start and end of work for each worker group; fixed nodes, which represent fixed work assigned to each worker group; maintenance work nodes, which represent maintenance work performed on each return train; and additional nodes, which represent additional work performed as needed.

A start time and an end time are set for each node, and the period from the start time to the end time is the work period for the corresponding task. In Figure 2, the position on the left side of the rectangle representing the node is the start time, and the position on the right side is the end time. A start time and an end time are set in advance for each node, except for additional nodes, according to their type. That is, for start nodes, the start time is set to the start time of the corresponding worker group, and a predetermined time after the start time is set to the end time. For end nodes, the end time is set to the end time of the corresponding worker group, and a predetermined time prior to the end time is set to the start time. For maintenance work nodes, the start time and end time of maintenance work on the corresponding train are set as the start time and end time.

The additional work represented by an additional node is work that is performed away from the station platform, such as a short break or preparation work for maintenance work, and is work that is added as one of the constraints described below. Additional nodes are not set before the maintenance work schedule is created, but are set during the creation of the schedule. Specifically, additional nodes are set by assigning start and end times to the relevant worker group so that the work time determined based on the content of the additional work is secured.

When creating a maintenance work schedule using this graph structure, first set the start and end nodes and fixed nodes for each worker group, as well as the maintenance work nodes for return trains. Then, for each worker group, connect the maintenance work nodes and fixed work nodes between the start node and end node with arcs so that they do not branch out in chronological order, creating a maintenance work schedule.

[Processing flow]
3 is a diagram illustrating the flow of the maintenance work diagram creation process for creating a maintenance work diagram performed by the maintenance work diagram creation device 1. In this embodiment, in order to create a more appropriate maintenance work diagram in a short time, the maintenance work diagram is created by applying tabu search, which is one of the metaheuristic methods.

The maintenance work schedule creation process first performs an initial solution generation process to generate an initial solution, which is the first candidate solution for the maintenance work schedule (step S1). Details of the initial solution generation process will be described later (see Figure 5). The initial solution for the maintenance work schedule is generated so as to satisfy specified constraints.

The constraints include: (A) a work assignment order constraint that assigns maintenance work to worker groups with the earliest start times or fixed work end times; (B) an assignment constraint that assigns only one worker group to maintenance work on all return trains; (C) an upper limit constraint on the difference in the number of work trains, which requires that the difference (variation) in the number of maintenance work trains (number of maintenance work trains) assigned to each worker group be within a specified number; (D) an upper limit constraint on the number of work trains, which requires that the number of maintenance work trains (number of maintenance work trains) assigned to one worker group must satisfy a specified upper limit condition on the number of work trains assigned; (E) a consecutive work number constraint that adds specified additional work when a specified number of maintenance work trains are assigned consecutively to one worker group; (F) a platform movement time constraint that does not assign maintenance work to a worker group if the movement time for the previous and next maintenance work trains does not satisfy a specified platform movement time condition when the platform platforms of the previous and next maintenance work trains are different; and (G) a task overlap constraint that requires that the overlap time between the work periods of the previous and next maintenance work trains assigned to one worker group and the fixed work trains must satisfy a specified overlap time condition. The required time condition for moving between track platforms may be set as one, or may be set for each combination of track platforms to be moved.

Once an initial solution for the maintenance work schedule is generated, it is determined whether all return trains are assigned as maintenance work trains for one worker group (whether constraint (B) is satisfied). If all return trains are not assigned (step S3: NO), the constraints are relaxed (step S5), and the initial solution generation process is performed again to generate an initial solution (step S7). Relaxing the constraints, for example, can be done by lengthening the allowable overlap time, which is the overlap time condition that allows partial overlap between maintenance work periods and fixed work periods (relaxing constraint (G)). Specifically, by changing the allowable overlap time from "0 minutes" to "1 minute," an initial solution can be generated that allows for minor violations of constraints, such as a worker group's break time (an example of fixed work) being "1 minute short." Furthermore, constraints can be relaxed by changing the parameters for the worker groups, which serve as input data, such as advancing the start time of a worker group by a predetermined amount, delaying the end time of a worker group by a predetermined amount, or increasing the number of worker groups.

If not all return trains have been assigned even in the regenerated initial solution (step S9: NO), the initial solution and the unassigned return trains (maintenance work) are output as processing results (step S11).

On the other hand, if all of the return trains for the generated initial solution are assigned as maintenance work trains for one of the worker groups (step S3: YES or step S9: YES), the initial solution is added to the tabu list and the tentative solution list as the first tentative solution (step S13). Further candidate solutions are then generated (step S15). Further candidate solutions are generated by partially modifying the tentative solution. A new solution (new candidate solution) is generated from a single solution (tentative solution), which can be considered a "seed." In the repetition of steps S15 to S21, this single original solution (tentative solution), which can be considered a "seed," is replaced; this replacement (i.e., performing a new repetition of steps S15 to S21) is referred to below as a "transition." Furthermore, the number of candidate solutions generated from the single original solution (tentative solution), which can be considered a "seed," can be one; however, in this embodiment, two or more candidate solutions are generated.

Figure 4 is a diagram illustrating a method for generating multiple new candidate solutions from a single tentative solution. In Figure 4, an example of a tentative solution for a maintenance work schedule is shown at the top, and examples of two new candidate solutions are shown at the bottom. In this embodiment, a new candidate solution is generated by swapping one or more maintenance work trains that satisfy all conditions for track movement time, continuous work time, number of work trains, and work sequence between two worker groups in the tentative solution.

The condition for track platform movement time is that, in the post-swap solution, the total time required to move between track platforms when the previous and next maintenance work tasks are on different track platforms is less than a predetermined time (equivalent to constraint (F)). The condition for continuous work time is that, in the post-swap solution, the total work time required for each maintenance work task that is consecutive to the previous or next maintenance work task is less than a predetermined time. "Continuous maintenance work tasks" means that the time interval between the maintenance work tasks is less than a predetermined time. The condition for the number of tasks is that, in the post-swap solution, the number of maintenance work tasks (number of maintenance work trains) assigned to one worker group is less than a predetermined number (equivalent to constraint (D)). The condition for work order is that, in the post-swap solution, the maintenance work tasks and work orders are not swapped.

In this way, for all combinations of one or more maintenance work trains in the tentative solution that satisfy all conditions of track travel time, continuous work time, number of work trains, and work sequence between two worker groups, new multiple candidate solutions are generated by swapping the maintenance work in that combination. The number of maintenance work tasks to be swapped (one or more) should be determined so that the difference (variation) in the number of maintenance work tasks (number of maintenance work trains) assigned to each worker group in the solution after the swap is within a specified number. This makes it possible to generate candidate solutions that satisfy constraint (C).

In addition, if, as a result of regenerating the initial solution, there are unassigned maintenance work trains to any of the worker groups, a candidate solution may be generated by adding those unassigned maintenance work trains to the regenerated initial solution. In other words, all candidate solutions are generated that assign unassigned maintenance work trains to any of the worker groups and satisfy all conditions regarding platform movement time, continuous work time, number of work trains, and work sequence.

In the example in Figure 4, the first new candidate solution is generated by swapping one maintenance work train between "worker groups A and D" in the tentative solution. Furthermore, the second new candidate solution is generated by swapping one maintenance task between "worker groups A and C" in the tentative solution.

In the second candidate solution, the maintenance work for "Worker Group C" was swapped in the tentative solution, eliminating the consecutive maintenance work for "Worker Group C" and making additional work unnecessary. This additional work for "Worker Group C" was added by assigning consecutive maintenance work to one worker group at a time interval that satisfies a specified short-time condition (constraint (E)). As described below, the lower the number of consecutive maintenance work tasks (= the number of consecutive maintenance work tasks at a time interval that satisfies a specified short-time condition), the higher the evaluation value for the candidate solution. Therefore, by generating a candidate solution by prioritizing the swapping of maintenance work tasks that have additional work added immediately after them, it is possible to eliminate consecutive maintenance work tasks and generate a candidate solution with a higher evaluation value.

Returning to Figure 3, once multiple candidate solutions have been generated, the candidate solution that is not included in the tabu list and has the best evaluation value is selected from the generated candidate solutions as a new tentative solution and added to the tentative solution list (step S17). This new tentative solution can be considered a "seed" solution that will serve as the basis for generating further solutions (further candidate solutions) in step S19 when the next transition is made. The tentative solution list is a list that stores past tentative solutions in association with their calculated evaluation values.

A new tentative solution is selected in step S17, and the immediately preceding tentative solution is added to the tabu list to update the tabu list (step S19). A tabu list is a list that stores a specified number of candidate solutions (tentative solutions in this case) using a FIFO (First In First Out) method. Therefore, if the tabu list contains a specified number of candidate solutions, the oldest candidate solution is deleted from the list, and the tentative solution immediately preceding the new tentative solution selected in step S17 is added to update the tabu list. The specified number is two or more. The reason the immediately preceding tentative solution is added to the tabu list instead of the new tentative solution selected in step S17 is because a new candidate solution is generated by partially modifying the tentative solution in the next transition (when steps S15 to S21 are newly performed). Partial modification means that a solution different from the tentative solution is necessarily generated, so there is no need to store the original solution that is the basis for the modification in the tabu list. Therefore, instead of the new tentative solution selected in step S17, the previous tentative solution is added to the taboo list.

The evaluation value of the candidate solution is calculated based on predetermined evaluation indices. The evaluation indices include (α) platform travel time, which is the total travel time between platform platforms when the previous and next maintenance work assigned to each worker group are on different platform platforms; (β) the number of consecutive maintenance work tasks, which is the total number of consecutive maintenance work tasks assigned to each worker group; (γ) the variation in the distribution of allocated time for maintenance work (maintenance work trains) between each worker group; and (δ) the difference in the number of work tasks, which is the difference in the number of maintenance work tasks (number of maintenance work trains) assigned to each worker group.

The variance of the distribution of assigned time, which is the evaluation index (γ), can be measured using either the variance or the sum of squared deviations. In the latter example, first, the average number of maintenance tasks assigned to each worker group is found for each time slot from the start time to the end time. Next, for each worker group, the square of the difference between the found average number and the number of maintenance tasks assigned to that worker group is found for each time slot and the sum is calculated, and this sum is used as the variance for that group. Note that the square root of the sum can also be used as the variance.

The difference in the number of tasks, an evaluation index (δ), can be, for example, the difference between the maximum and minimum number of maintenance tasks (number of maintenance work trains) assigned to each worker group. Alternatively, the average number of total maintenance tasks (number of maintenance work trains) assigned to each worker group can be calculated, and the difference in the number of tasks can be calculated by squaring the difference between this average number and the total number of maintenance tasks (number of maintenance work trains) assigned to each worker group.

Then, for each candidate solution, the values of these four evaluation indices (α) through (δ) are calculated, and the sum of the weighted values for each evaluation indices is calculated as the index value for that candidate solution. By changing the weighting, you can freely set which evaluation indices to emphasize.

Following step S19, it is determined whether a termination condition is met. The termination condition can be, for example, the number of times the generation of candidate solutions and selection of tentative solutions (steps S15 to S19) have been repeated, or the fact that a tentative solution has been obtained whose evaluation index value satisfies a predetermined high evaluation condition. If the termination condition is not met (step S21: NO), the process proceeds to step S15 to repeat steps S15 to S19, and multiple new candidate solutions are generated based on the tentative solution selected in step S17 (step S15). If the termination condition is met (step S21: YES), the solution with the best evaluation value among the past tentative solutions (candidate solutions) stored in the tentative solution list is output as the final solution for the maintenance work schedule (step S23). After the above processing is performed, this process ends.

Figure 5 is a flowchart explaining the flow of the initial solution generation process. The initial solution generation process will be explained with reference to the graph structures in Figures 6 to 10. To give an overview of the process, a maintenance work schedule is created by assigning maintenance work and fixed work assigned to each worker group in order of earliest start time, starting from the start time of the shift, as time passes.

Figures 6 to 10 show an example of a graph structure during the process of generating an initial solution using the initial solution generation process. Figures 6 to 10 show an example where there are four "worker groups A to D" for the same segment, each of which has one fixed task, resulting in 20 "maintenance tasks 1M, 3M, ..., 39M."

As shown in Figure 5, the initial solution generation process first selects the target worker group category (step S101). Then, steps S103 to S131 are performed for the worker groups in the selected category. First, for each worker group in the selected category, the current time is initially set based on the start node (step S103). Specifically, the end time of the start node is initially set as the current time.

Figure 6 shows an example of a graph structure in which the start node of each worker group has been selected and the current time of each worker group has been initialized. The end time of the start node is initially set as the current time for each of "worker groups A to D."

Returning to Figure 5, next, in order of earliest current time, the unassigned maintenance work with the earliest start time is assigned to each worker group as the first maintenance work, and the end time of the assigned maintenance work is updated as the current time of the group (step S105). Furthermore, in order of latest start time of the end node, the unassigned maintenance work with the latest end time is assigned to each worker group as the last maintenance work (step S107).

Figure 7 shows an example of a graph structure in which the first and last maintenance tasks have been assigned to each worker group. The initially set current time is earliest for worker groups A, B, C, and D, in that order, so the first maintenance tasks are assigned in that order. The end time of the assigned first maintenance task is then updated as the current time for each worker group. The start time of the end node is latest for worker groups D, C, B, and A, so the last maintenance tasks are assigned in that order.

Returning to Figure 5, next, from among the worker groups, one worker group with the earliest current time is selected as the target worker group, and the unassigned maintenance work with the earliest start time is assigned to the target worker group as the next maintenance work, and the end time of the assigned maintenance work is updated as the current time of the group (step S109). This satisfies constraint (A). At this time, priority is given to maintenance work on the same track as the immediately preceding maintenance work as the next maintenance work. When assigning maintenance work on a different track as the next work, the next maintenance work is determined to be the maintenance work whose travel time between maintenance works (the time from the end time of the previous maintenance work to the start time of the subsequent maintenance work) satisfies the specified track travel time condition (constraint (F)).

Next, it is determined whether the assignment of the new maintenance work means that the specified number of maintenance works assigned to the target worker group are "continuous." Maintenance works are determined to be "continuous" by determining whether the time interval between two maintenance works (the time interval from the end time of the previous maintenance work to the start time of the next maintenance work) meets a specified short-time condition. The short-time condition can be, for example, a specified time or less.

If it is determined that a predetermined number of maintenance tasks are consecutive (step S111: YES), immediately after the last maintenance task (i.e., the newly assigned maintenance task), additional tasks of a type corresponding to the number of consecutive maintenance tasks are added and assigned, and the current time of the target worker group is updated by adding the time corresponding to the type of additional task (step S113). Note that, because additional tasks are added and assigned immediately after a maintenance task, the work time for the maintenance task can also be considered to have been increased by the work time for the additional task. This satisfies constraint condition (E).

Figure 8 shows an example of a graph structure in which an additional task has been assigned to a target worker group. In the example of Figure 8, the two "Maintenance Tasks 1M and 9M" assigned to the target worker group, "Worker Group A," are "consecutive," and the additional task (an additional node in Figure 8) has been added and assigned immediately after the latter, "Maintenance Task 9M." The current time of "Worker Group A" has been updated to the end time of "Maintenance Task 9M" plus the working time of the additional task.

Returning to Figure 5, next, it is determined whether the current time of the target worker group exceeds the start time of the fixed work assigned to that group, and whether this excess time exceeds a predetermined allowable time. If the excess time exceeds the allowable time (step S115: YES), backtracking is performed, i.e., the allocation of the most recently assigned maintenance work is canceled, and the fixed work is connected to the previous maintenance work. The end time of the fixed work is then updated as the current time of the target worker group (step S117).

Figure 9 shows an example of a graph structure in which the current time has exceeded the start time of a fixed task. In the example of Figure 9, an attempt is made to assign a new "Maintenance Task 17M" to the target worker group, "Worker Group A," but the end time of "Maintenance Task 17M" is 12:10, which exceeds the start time of "12:00," the fixed task "Fixed A" for "Worker Group A," by 10 minutes. Because the exceeded time of 10 minutes exceeds the allowable time of 5 minutes, the assignment of "Maintenance Task 17M" is canceled, and an arc is set to connect the immediately preceding "Maintenance Task 9M" to the fixed task.

Returning to Figure 5, a determination is made as to whether the current time of the target worker group has passed the start time of the last maintenance task. If it has passed (step S119: YES), backtracking is performed, i.e., the most recently assigned maintenance task is canceled, and the previous maintenance task is connected to the last maintenance task (step S121). If the last maintenance task is connected, the target worker group has reached the end node from the start node. In other words, between the start time and end time of the target worker group, the maintenance tasks performed by that group and the fixed tasks defined for that group have been assigned in chronological order.

On the other hand, if the current time has not passed the start time of the last maintenance task (step S119: NO), a determination is made as to whether the number of maintenance tasks assigned to the target worker group has reached a predetermined upper limit. If the upper limit has been reached (step S123: YES), the most recently assigned maintenance task is linked to the last maintenance task (step S125). This satisfies constraint condition (D).

Then, it is determined whether the end node has been reached for all worker groups, and if not (step S127: NO), the process returns to step S109. If the end node has been reached for all worker groups (step S127: YES), unassigned maintenance work is extracted (step S129). This completes the processing for the worker groups in the selected category.

Next, it is determined whether all categories have been selected, and if there are any unselected categories (step S131: NO), the process returns to step S101. If categories for all worker groups have been selected (step S131: YES), the set of allocations of maintenance work, fixed work, etc. for each worker group is set as the initial solution for the maintenance work schedule (step S133). Once the above processing has been performed, this process ends.

Figure 10 shows an example of a graph structure after an initial solution has been generated. However, to avoid cluttering the drawing, additional nodes have been omitted from the illustration, except for "Maintenance Work 9M." In Figure 10, all of the "Worker Groups A to D" reach the end node from the start node via maintenance work, fixed work, etc. However, "Maintenance Work 21M" is not assigned to any worker group (unassigned). Therefore, for the initial solution in Figure 10, step S3 of the maintenance work schedule creation process (Figure 3) returns "NO," and the constraints are relaxed, and the initial solution generation process is executed again.

[Functional configuration]
Fig. 11 shows an example of the functional configuration of the maintenance work diagram creation device 1. According to Fig. 11, the maintenance work diagram creation device 1 is configured to include an operation unit 102, a display unit 104, a sound output unit 106, a communication unit 108, a processing unit 200, and a storage unit 300, and is realized as a type of computer system. Note that the maintenance work diagram creation device 1 may be realized by a single computer, or may be configured by connecting multiple computers.

The operation unit 102 is realized by input devices such as a keyboard, mouse, touch panel, and various switches, and outputs operation signals to the processing unit 200 in response to operations performed. The display unit 104 is realized by a display device such as an LCD display or touch panel, and produces various displays based on display signals from the processing unit 200. The sound output unit 106 is realized by a sound output device such as a speaker, and produces various sound outputs based on sound signals from the processing unit 200. The communication unit 108 is a communication device realized by a wireless communication module, router, modem, wired communication cable jack, control circuit, etc., and connects to a given communication network to communicate data with external devices.

The processing unit 200 is a processor implemented by an arithmetic device or circuit such as a CPU (Central Processing Unit) or FPGA (Field Programmable Gate Array), and performs overall control of the maintenance work diagram creation device 1 based on programs and data stored in the memory unit 300, input data from the operation unit 102 and communication unit 108, etc.

Furthermore, the processing unit 200 has, as functional processing blocks, an acquisition unit 202, a worker group setting unit 204, a fixed task setting unit 206, a candidate solution generation unit 208, an evaluation unit 210, and a selection unit 212. Each of these functional units of the processing unit 200 can be realized in software by the processing unit 200 executing a program, or can be realized by a dedicated arithmetic circuit. In this embodiment, the former software realization will be described.

The acquisition unit 202 acquires the return train schedule 10, which specifies the track number and time of each return train that will be subject to maintenance work at a given return station. For example, the schedule may be acquired by a user's operation input via the operation unit 102, or by reading the return train schedule 10 data from a storage medium or inputting it from an external device via the communication unit 108. The acquired return train schedule 10 is stored as return train schedule data 310.

The worker group setting unit 204 sets multiple worker groups with defined start and end times. It also sets worker groups for multiple categories of worker groups with different types of maintenance work. For example, the setting may be performed by operating the operation unit 102, or by reading data related to the worker groups from a storage medium or inputting it from an external device via the communication unit 108. The data related to the set worker groups is stored as worker group data 330.

The fixed task setting unit 206 sets fixed tasks with defined start and end times for each set worker group. It also sets fixed tasks for each worker group for multiple categories of worker groups with different types of maintenance tasks. For example, the settings may be made by operating the operation unit 102, or by reading the data from a storage medium or inputting it from an external device via the communication unit 108. Data related to the set fixed tasks is stored as fixed task data 332 included in the worker group data 330.

The candidate solution generation unit 208 generates multiple candidate solutions for a maintenance work timetable that, for each set worker group, assigns maintenance work trains for that worker group from among the return trains specified in the return train timetable, and fixed work set for that worker group, in chronological order between the start time and end time of that worker group, and that satisfy the platform change time condition when the platform platforms of previous and subsequent maintenance work trains assigned to the same worker group are different (corresponding to step S15 in Figure 3).

The candidate solution generation unit 208 also generates candidate solutions for the same worker group, where the basic work time for maintenance work on one return train is determined, so that the overlap time between the work period based on the basic work time for the maintenance work train and the fixed work period from the start time to the end time for the fixed work satisfies a given overlap time condition (corresponding to steps S115 to S117 in Figure 5; see Figure 9). The overlap time condition may be such that the allowable overlap time is set to zero or less, thereby eliminating overlap, or the allowable overlap time condition may be specifically set (for example, five minutes or less).

The candidate solution generation unit 208 also determines whether a candidate solution has been successfully generated based on whether all of the return trains specified in the return train timetable have been assigned as maintenance work trains for any of the worker groups (corresponding to step S3 in Figure 3), and changes the overlap time condition (corresponding to step S5 in Figure 3). If a candidate solution cannot be generated, it is preferable to change the overlap time condition to be more relaxed (by increasing the time threshold).

The candidate solution generation unit 208 also generates candidate solutions that satisfy the upper limit allocation condition regarding the number of maintenance work trains to be assigned to the same worker group (constraint condition (D), which corresponds to steps S123 to S125 in Figure 5).

Furthermore, when the time interval between two maintenance work trains assigned to the same worker group satisfies a predetermined short-time condition, the candidate solution generation unit 208 generates a candidate solution as the work time obtained by adding a given additional time to the work time for the maintenance work of the latter of the two maintenance work trains (constraint condition (E). This corresponds to steps S111 to S113 in Figure 5. See Figure 8).

The candidate solution generation unit 208 also generates a new candidate solution by switching the maintenance work trains between worker groups for a previously generated candidate solution (tentative solution) (see Figure 4).

In addition, the candidate solution generation unit 208 generates candidate solutions for each of multiple categories of worker groups with different types of maintenance work.

To explain the processing content of the candidate solution generation unit 208 in more detail, the candidate solution generation unit 208 performs an initial solution generation process (see Figure 5) to generate an initial solution, which is the first candidate solution (which is also the first tentative solution). This initial solution is generated so that at least all return trains specified in the return train timetable are assigned as maintenance work trains for one of the worker groups (constraint (B)). If an initial solution that cannot be assigned is generated, the overlap time condition (constraint (G)) that must be satisfied by the overlap time between the maintenance work period and the fixed work period for the same worker group is relaxed, and the initial solution generation process is performed again to generate an initial solution. If an initial solution can be generated in which all return trains are assigned as maintenance work trains for one of the worker groups, this initial solution is added to the tabu list 340 as the first tentative solution.

The candidate solution generation unit 208 then generates multiple new candidate solutions by switching the maintenance work trains between the two worker groups in the tentative solution. Each of the new candidate solutions generated is evaluated by the evaluation unit 210, and an evaluation value is calculated. Of the new candidate solutions generated, the candidate solution that is not included in the tabu list 340 and has the best evaluation value is selected as the new tentative solution, associated with the evaluation value, and added to the tentative solution list 360. The tabu list 340 is also updated by adding the previous tentative solutions to the tabu list 340 using a FIFO method. Subsequently, a similar process is repeated, in which further candidate solutions are generated based on the new tentative solution, the next tentative solution is selected, and the tentative solution list 360 and the tabu list 340 are updated.

The evaluation unit 210 evaluates the candidate solutions generated by the candidate solution generation unit 208 based on given evaluation indices. The evaluation indices include: (α) platform travel time, which is the total travel time between platform platforms when the previous and next maintenance work assigned to each worker group are on different platform platforms; (β) the number of consecutive maintenance work tasks, which is the total number of consecutive maintenance work tasks assigned to each worker group; (γ) the variation in the distribution of allocated time for maintenance work (maintenance work trains) between each worker group; and (δ) the difference in the number of work tasks, which is the difference in the number of maintenance work tasks (number of maintenance work trains) assigned to each worker group. The evaluation unit 210 calculates the value of each of these multiple evaluation indices for the candidate solution and calculates the total value weighted for each evaluation indices as the evaluation value for the candidate solution.

The selection unit 212 selects a final solution from the created candidate solutions based on a given evaluation index (corresponding to step S23 in Figure 3). Specifically, the selection unit 212 selects a final solution from the tentative solutions (candidate solutions) stored in the tentative solution list 360 based on the evaluation value. Only one final solution may be selected, or multiple final solutions may be selected in order of evaluation value.

The memory unit 300 is realized by a storage device such as an IC (Integrated Circuit) memory such as a ROM (Read Only Memory) or RAM (Random Access Memory) or a hard disk. It stores programs and data used by the processing unit 200 to comprehensively control the maintenance work diagram creation device 1, and is also used as a working area for the processing unit 200 to temporarily store the results of calculations performed by the processing unit 200 and input data from the operation unit 102 and communication unit 108. In this embodiment, the memory unit 300 stores a maintenance work diagram creation program 302, return train diagram data 310, maintenance work data 320, worker group data 330, a tabu list 340, a tentative solution list 360, and maintenance work diagram data 370.

The maintenance work diagram creation program 302 is a program that, when read and executed by the maintenance work diagram creation device 1, causes the maintenance work diagram creation device 1 to perform the maintenance work diagram creation process (see Figure 2) that creates a maintenance work diagram.

[Action and effect]
As described above, this embodiment can automatically create a maintenance work schedule. Specifically, for each set worker group, multiple candidate solutions are generated that assign the maintenance work trains to be subjected to maintenance work and the fixed work set for that group between the start time and the end time, and that satisfy the required time condition for platform change when the platform platforms of the previous and next maintenance work assigned to the same group are different. Then, a final solution for the maintenance work schedule is selected from the generated candidate solutions based on a given evaluation index. This avoids a maintenance work schedule that is too forceful for workers to change platform platforms, and allows for the creation of an appropriate maintenance work schedule based on a given evaluation index.

It should be noted that the applicable embodiments of the present invention are not limited to the above-described embodiments, and can of course be modified as appropriate without departing from the spirit of the present invention.

For example, while the tentative solution list 360 has been described as storing tentative solutions in association with their evaluation values, it may also store all candidate solutions generated in the past in association with their evaluation values. In this case, the tentative solution list 360 can be called a candidate solution list.

In addition, while the above embodiment describes an example in which a tabu list is used, it is also possible to not use a tabu list. In this case, in step S15 of FIG. 3, the solution with the best evaluation value is simply selected from the candidate solutions generated in step S13 as a new tentative solution without referring to the tabu list. Then, all of the generated candidate solutions are stored in a candidate solution list in association with their evaluation values, and the best candidate solution is ultimately output as the final solution.

In addition, in the above embodiment, a method for generating a new candidate solution from a tentative solution was described as switching maintenance work trains between two worker groups, but maintenance work trains may also be switched between three or more worker groups in a rotational manner. Furthermore, methods other than switching maintenance work trains may also be employed.

DESCRIPTION OF SYMBOLS 1...Maintenance work diagram creation device 200...Processing unit 202...Acquisition unit 204...Worker group setting unit 206...Fixed work setting unit 208...Candidate solution generation unit 210...Evaluation unit 212...Selection unit 300...Storage unit 302...Maintenance work diagram creation program 310...Shuttle train diagram data 320...Maintenance work data 330...Worker group data 332...Fixed work data 340...Tabu list 360...Tentative solution list 370...Maintenance work diagram data 10...Shuttle train diagram 20...Maintenance work diagram

Claims (10)

a return train timetable acquisition means for acquiring a return train timetable in which the track number and time of each return train that is the subject of maintenance work at a given return station are specified;
a worker group setting means for setting a plurality of worker groups each having a predetermined start time and end time;
a fixed task setting means for setting a fixed task with a predetermined start time and end time for each of the set worker groups;
a candidate solution generating means for generating, for each of the set worker groups, a plurality of candidate solutions for a maintenance work timetable in which maintenance work trains to be performed by the worker group among the return trains set in the return train timetable and the fixed work set for the worker group are assigned in chronological order between the start time and the end time of the work for the worker group, the candidate solutions satisfying a required time condition for moving between track platforms when the track platforms of the preceding and following maintenance work trains assigned to the same worker group are different;
a selection means for selecting a final solution from the generated candidate solutions based on a given evaluation index;
A maintenance work schedule creation device comprising: the selection means evaluates the candidate solutions using an evaluation index based on the platform movement time due to the difference in the platform platforms of the preceding and following maintenance work trains assigned to the same worker group in the candidate solutions, and selects the final solution.
The maintenance work schedule creation device according to claim 1. the candidate solution generating means generates a new candidate solution by switching the maintenance work trains between the worker groups for the previously generated candidate solution.
3. The maintenance work schedule creation device according to claim 1 or 2. A basic work time for the maintenance work for one return train is specified,
the candidate solution generating means generates the candidate solution for the same worker group such that an overlap time between a work period based on the basic work time for the maintenance work train and a fixed work period from the start time to the end time for the fixed work satisfies a given overlap time condition.
The maintenance work diagram creation device according to any one of claims 1 to 3. The candidate solution generating means
a success/failure determination means for determining whether the candidate solution has been successfully generated based on whether all of the turn-back trains defined in the turn-back train timetable have been assigned as the maintenance work trains of any of the worker groups;
overlap time condition changing means for changing the overlap time condition;
having
The maintenance work schedule creation device according to claim 4. the candidate solution generating means generates a candidate solution that satisfies an upper limit number allocation condition related to the number of maintenance work trains to be allocated to the same worker group.
The maintenance work diagram creation device according to any one of claims 1 to 5. When the time interval between two maintenance work trains assigned to the same worker group satisfies a predetermined short time condition, the candidate solution generation means generates a candidate solution as a work time obtained by adding a given additional time to the work time for maintenance work of the latter of the two maintenance work trains.
The maintenance work diagram creation device according to any one of claims 1 to 6. The selection means
an evaluation index based on the number of time intervals between maintenance work trains assigned to the same worker group in the candidate solution that satisfy a predetermined short time condition;
an evaluation index indicating the variation in the distribution of maintenance work train allocation times among each worker group in the candidate solution;
evaluating the candidate solutions using at least one of the following to select the final solution;
The maintenance work diagram creation device according to any one of claims 1 to 7. The worker group includes a plurality of divisions each having a different type of maintenance work,
For each of the categories, the worker group setting means sets a worker group, the fixed task setting means sets a fixed task, the candidate solution generation means generates candidate solutions, and the selection means selects a final solution.
The maintenance work diagram creation device according to any one of claims 1 to 8. A maintenance work schedule creation method for creating a maintenance work schedule to which a worker group is assigned for each turn-back train that is the subject of maintenance work at a given turn-back station, comprising:
Obtaining a return train schedule that specifies the track number and time of each return train that is subject to maintenance work at the return station;
Setting a plurality of worker groups each having a predetermined start time and end time;
setting a fixed work having a predetermined start time and end time for each of the set worker groups;
generating a plurality of candidate solutions for a maintenance work timetable that assigns, for each of the set worker groups, maintenance work trains to be performed by the worker group among the return trains set in the return train timetable and the fixed work set for the worker group in time series between the start time and the end time of the work for the worker group, and that satisfy a platform change required time condition when the platform platforms of the previous and next maintenance work trains assigned to the same worker group are different;
selecting a final solution from the generated candidate solutions based on a given evaluation index;
A method for creating a maintenance work schedule including: