JP6901081B2 - Planning equipment, planning methods, and programs - Google Patents

Description

The present invention relates to a plan making device, a plan making method, and a program.

Generally, in logistics and production sites, it is necessary to plan delivery, procurement, and production schedules with less delay in delivery. In particular, when planning these, it is required to make a robust (stable against disturbance) plan so that the delivery date can be met even if road congestion, troubles on the production line, etc. occur. There is.

Japanese Unexamined Patent Publication No. 2009-32104 Japanese Unexamined Patent Publication No. 2006-293483 JP-A-2002-290304

In formulating such a robust plan, it is conceivable to apply a mathematical model, and as an example, it is conceivable to formulate a semi-optimal plan by the Monte Carlo method.
In this case, the derivation of the candidate plan and the calculation of the probability of delivery delay are repeatedly executed, and the one with the lowest probability of delivery delay is obtained from these candidates.

For example, as shown in FIG. 9, in the case of delivering from the X point to the Z point via the Y point, there are five movement routes from the X point to the Y point, from the Y point to the Z point. It is assumed that there are three routes to go, B1 to B3, and a probability distribution is given for each required time.

In this case, when the Monte Carlo method is used, first, in the first search, the movement route from the X point to the Y point and the movement route from the Y point to the Z point are arbitrarily specified (for example, A3 and B2). choose). Then, based on the specified route, M trials are performed according to the probability distribution of the route, and the total required time is obtained for each. For the obtained M required times, the average and variance are calculated.

Next, as the second search, a movement route different from that of the first search is specified (for example, A5 and B1 are selected). Then, as in the first search, M trials are performed for this specified route, and the required time is obtained for each. For the obtained M required times, the average and variance are calculated.

Then, by performing such a search N times and selecting a movement route that gives the optimum average value and variance value among them, a robust plan can be made.
Here, the optimum mean value and variance value are ideally those having the smallest mean value and the smallest variance value, but in reality, the travel route with the smallest mean value is not necessarily the most variance. The value is not always small, and which one is more important is selected by an appropriate selection method.

In the Monte Carlo method, a robust plan is made as described above, but in each search, in order to find the optimum movement route in relation to arbitrarily specifying the movement route, an extremely large number of searches are performed. There is a problem that it takes time. Even if the calculation time in one search is about one minute, it will take several tens of minutes if several tens of searches are performed.

It is also conceivable to use the stochastic planning method as another method for making a robust plan using a mathematical model.
In this case, a plurality of scenarios are prepared in advance, and for example, a plan that satisfies all of these scenarios is derived.

For example, to explain using the example of FIG. 9, in the probability planning method, first, for A1 to A5 and B1 to B3, specific values are extracted in advance according to the probability distributions that each follows, and a scenario is created.
Then, S such scenarios are prepared (see FIG. 10).

Next, a proposition is given to search for a solution that satisfies all scenarios at the same time (first search). For example, if the proposition that the travel time from the X point to the Z point is 15 minutes is given, if A4 and B1 are selected, this proposition will be satisfied at the same time in all scenarios.

In the probabilistic planning method, among those that satisfy the proposition, the mean or variance of the scenario is incorporated into the objective function, and the objective function is minimized. As the method, the iterative solution is shown below. The method is not limited to the iterative method, and other methods such as the branch-and-bound method can also be used. The iterative method is a branch-and-bound method, a branch-cut method, a local search method, a tabu search method, an annealing method, a genetic algorithm, or the like, which is an iteratively feasible solution (or its relaxation). This is a method of finding a (quasi) optimal solution while finding a solution), but an approximate solution method other than the iterative solution method can also be used.

In the case of the iterative solution method, in the above example, the total time required for the solutions searched for each scenario (select A4 and B1) is obtained, and the average and variance of these values are obtained.

Next, under the same proposition, as the second search, a solution different from the first search is searched. For example, even if A5 and B1 are selected, the above proposition is satisfied at the same time in all scenarios, so this is also a solution.
Then, as in the first search, for each scenario, the total required time of the searched solutions (select A5 and B1) is obtained, and the average and variance of these values are obtained.

A robust plan can be made by repeating such a search N'times and selecting a movement route that gives the optimum average value and variance value. The concept of optimal mean and variance is the same as for the Monte Carlo method.
Moreover, in the case of the probabilistic planning method, if the worst scenario is included in the scenario created in advance, it is possible to make a conservative plan that can be achieved even in the worst scenario.

In the case of the established planning method, since each search finds a solution (movement route) that satisfies a predetermined proposition, the solution obtained by each search is compared with the Monte Carlo method that selects an arbitrary movement route. It's a good solution. Therefore, the number of searches N'in the probability planning method is smaller than the number of searches N in the Monte Carlo method.

However, in the case of the probabilistic planning method, the number of variables and the number of constraints increase in proportion to the number of scenarios, and the constraint of obtaining a solution that satisfies all scenarios is a very strict constraint. There is a problem that it takes a lot of time.

The present invention has been made in view of the above problems, and an object of the present invention is to provide a plan making device for making a robust plan and a plan making method within a practical time.

Therefore, in order to solve the above problems, the present invention has adopted the following configuration.
The planning apparatus of the present invention
A planning device that creates a required schedule by selecting a plurality of specific work elements from a plurality of work elements.
A work element information acquisition unit that acquires an index indicating a plurality of work elements and the degree of variation in the required time for each work element.
A variation scenario creation unit that creates a variation scenario in which the required time is specified for each work element based on an index indicating the degree of variation in the required time.
A required schedule specifying unit that specifies a plurality of different required schedules based on the variation scenario,
It is characterized by including a determination unit for specifying a specific required schedule from the plurality of required schedules.

Further, the plan making device of the present invention is the plan making device.
The first reference time is calculated based on the expected value of the required time of the work elements constituting the required schedule, and the second reference time is calculated based on the expected value of the required time of the work elements constituting the required schedule and the standard deviation. A calculation unit that calculates and calculates a third reference time based on the first reference time and the second reference time is provided.
The determination unit identifies a specific schedule from the plurality of required schedules based on the first reference time and the third reference time calculated for each of the plurality of different required schedules. ..

Further, the plan making device of the present invention is the plan making device.
The index indicating the degree of variation in the required time is an expected value and a standard deviation of the required time.

Further, the plan making device of the present invention is the plan making device.
It is characterized in that there are a plurality of variation scenarios created by the variation scenario creation unit.

Further, the plan making device of the present invention is the plan making device.
It is characterized by including an expected value scenario creation unit that creates an expected value scenario in which the required time is specified for each work element based on the expected value of the required time acquired by the work element acquisition information.

Further, the plan making device of the present invention is the plan making device.
The time required for each work element specified by the variation scenario creation unit is added by multiplying the expected value of the time required for each work element by the standard deviation of the time required for each work element and a desired coefficient. It is characterized by being a value.

Further, the plan making device of the present invention is the plan making device.
It is an arbitrary first work element or third work element, and the first work element and the second work element can be performed in parallel, but the third work element cannot be performed unless both are completed. A correction coefficient information acquisition unit that identifies a certain object and acquires an index indicating a probability distribution, a representative value, and a degree of variation in the time required for the first work element or the third work element.
A work element selection unit that selects a work element having a large representative value of the required time among the first work element and the second work element.
From the index showing the representative value and the degree of variation of the required time of the work element selected by the work element selection unit and the index showing the representative value and the degree of variation of the required time of the third work element, the reference representative value and the reference variation. A reference value calculation unit that calculates an index showing the condition, and
It is necessary to derive a specific time according to a probability distribution for each of the required times of the first working element or the third working element, and to perform the first working element or the third working element under the constraint of the waiting condition. A time-specific part that takes into account the waiting time to calculate the time,
The required time considering the waiting The required time considering the waiting is obtained by acquiring a plurality of times calculated by the specified unit and obtaining the approximate representative value of the required time considering the waiting and the index indicating the approximate variation of the required time considering the waiting. Computational unit and
The representative value correction time and variation are obtained by subtracting the reference representative value and the index indicating the reference variation from the approximate representative value of the required time considering the meeting and the index showing the approximate variation of the required time considering the meeting, respectively. An index that indicates the condition. A correction time calculation unit that calculates the correction time, and a correction time calculation unit.
It is characterized by including a correction calculation unit that corrects the first reference time and the third reference time calculated by the calculation unit based on the representative value correction time and the index correction time indicating the degree of variation.

Further, the plan making device of the present invention is the plan making device.
The working element includes a travel route
The required time includes travel time
The required schedule is a movement schedule.

Further, the plan making device of the present invention is the plan making device.
The work element includes a work process
The required time includes the process time
The required schedule is a production schedule.

Moreover, the plan making method of this invention
It is a planning method that creates a required schedule consisting of selecting multiple specific work elements from multiple work elements.
A work element information acquisition step for acquiring an index indicating a plurality of work elements and the degree of variation in the required time for each work element, and
A variation scenario creation step of creating a variation scenario in which the required time is specified for each work element based on an index showing the variation degree of the required time, and a variation scenario creation step.
A required schedule identification step for identifying a plurality of different required schedules based on the variation scenario,
It is characterized by including a determination step for specifying a specific required schedule from the plurality of required schedules.

In addition, the program of the present invention
On a computer for creating a required schedule consisting of selecting multiple specific work elements from multiple work elements,
A work element information acquisition means for acquiring a plurality of work elements and an index indicating the degree of variation in the required time for each work element.
A variation scenario creating means for creating a variation scenario in which the required time is specified for each work element based on an index indicating the degree of variation in the required time.
A required schedule specifying means for specifying a plurality of different required schedules based on the variation scenario, and
It is characterized in that a determination means for specifying a specific required schedule from the plurality of required schedules is executed.

According to the present invention, it is possible to create a robust plan within a practical time.

It is a functional block diagram which shows an example of the plan making apparatus in 1st Embodiment of this invention. It is a flowchart which shows an example of the plan making method in 1st Embodiment of this invention. It is a table which shows an example of the expected value, the standard deviation, and the probability distribution acquired by the movement route acquisition part in 1st Embodiment of this invention. It is a table which shows an example of the expected value scenario in 1st Embodiment of this invention. It is a table which shows an example of the variation scenario in 1st Embodiment of this invention. It is a functional block diagram which shows an example of the plan making apparatus in 2nd Embodiment of this invention. It is a flowchart which shows an example of the plan making method in 2nd Embodiment of this invention. It is a table which shows an example of the expected value, the standard deviation, and the probability distribution acquired by the correction time information acquisition part in the 2nd Embodiment of this invention. It is a figure for explanation of the probability planning method. It is a table for explanation of the probability planning method.

Hereinafter, embodiments of the planning apparatus and the planning method according to the present invention will be described with reference to FIGS. 1 to 8.

[First Embodiment]
In the present embodiment, a plan creation device for creating a vehicle movement schedule (required schedule) by selecting a plurality of vehicle movement routes (work elements) and a plan creation method will be described, but the object of the plan in the present invention is Not limited to the vehicle movement schedule, various things can be targeted.

<Planning device>
The planning device 1 of the present embodiment is, for example, a computer, and has an input device, an arithmetic unit, a storage device, and the like as a device configuration, and has a database 2 and a movement route acquisition as a functional configuration as shown in FIG. Judgment of unit (work element information acquisition unit) 3, expected value scenario creation unit 4, variation scenario creation unit 5, movement schedule specification unit (required schedule specification unit) 6, calculation unit 7, and detection unit 8. It consists of part 9.

The database 2 stores the movement route of the vehicle, the representative value of the movement time required for the movement for each movement route, the index showing the degree of variation, and the probability distribution. The movement route refers to, for example, a road through which a vehicle passes. When moving from point X to point Y, if there are five roads from point X to point Y, all of these five roads move. Corresponds to the route.
As a representative value of the travel time, an expected value, a median value, a mode value, and the like of the travel time are exemplified.
Further, as an index showing the degree of variation in the travel time, the standard deviation of the travel time can be exemplified, but in addition to this, the time when the sum of the probabilities from the longer travel time corresponds to exactly θ%, or , The time when the sum of the probabilities from the expected value to the longer one corresponds to exactly τ% can be considered. For example, when θ = 0, it means the worst travel time. θ and τ are predetermined constants and can be arbitrarily determined.
In the following description, the case where the expected value is selected as the representative value and the standard deviation is selected as the index indicating the degree of variation will be described.

Further, one expected value, standard deviation, and probability distribution stored in the database 2 may be stored for each movement route, and different expected values and standards are stored depending on the time, day, time, and the like. The deviation and probability distribution may be recorded.

The travel route acquisition unit 3 acquires the expected value, standard deviation, and probability distribution of the travel route and the travel time for each travel route from the database 2 based on the information about the more initialized travel point such as the input from the operator. It is a functional part to do.

The initially set information about the moving point is information about the starting point and the arriving point, for example, moving from the X point to the Z point. In this case, the movement route acquisition unit 3 acquires all the movement routes theoretically considered when moving from the X point to the Z point from the movement routes stored in the database 2.

The travel route acquisition unit 3 does not base the information on the initially set travel points, but has the expected value standard deviation of the travel time for all the travel routes and all the travel routes stored in the database 2, and the probability distribution. You may get information about.

The expected value scenario creation unit 4 is a functional unit that creates an expected value scenario by specifying the travel time for each travel route based on the expected value for each travel route.
Further, the variation scenario creation unit 5 is a functional unit that specifies the travel time for each travel route and creates a variation scenario based on the expected value and standard deviation for each travel route.
Details of the expected value scenario creation unit 4 and the variation scenario creation unit 5 will be described later.

The movement schedule specifying unit 6 is a functional unit that specifies a moving schedule that satisfies a proposition initially set by input from an operator or the like, at least based on a variation scenario.
Here, the movement schedule refers to a set of specifically specified movement routes from the starting point to the arrival point. For example, the movement schedule goes from the X point to the Y point through the movement route A2 and moves from the Y point. When moving to the Z point through the route B1, the movement route A2 and the movement route B1 become the movement schedule.

Further, as an example of the initially set proposition, there is a condition that the position from the X point to the Z point is reached within 30 minutes.
The movement schedule specifying unit 6 does not specify only one movement schedule, but specifies a plurality of movement schedules as long as the initially set proposition is satisfied.

The calculation unit 7 is a functional unit that calculates the expected value time (first reference time) based on the expected value of the travel time of the travel route constituting the specific travel schedule.
Here, since the scenario created based on the expected value of the travel time for each travel route is the expected value scenario, the calculation unit 7 calculates the time when a specific travel schedule is adopted in the expected value scenario. However, this may be used as the expected value time.

The calculation unit 7 is also a functional unit that calculates the variation time (second reference time) based on the expected value and standard deviation of the travel time of the travel route constituting the specific travel schedule.
Here, since the scenario created based on the expected value of the travel time and the standard deviation for each travel route is a variation scenario, the calculation unit 7 calculates the time when a specific travel schedule is adopted in the variation scenario. However, this may be used as the variation time.
The calculation unit 7 is also a functional unit that calculates the approximate standard deviation time (third reference time) by subtracting the variation time from the expected value time.

The detection unit 8 is a functional unit that detects whether or not the expected value time, the variation time, and the approximate standard deviation time calculated by the calculation unit 7 have reached a predetermined number.
Further, the determination unit 9 is a functional unit that specifies a specific movement schedule from a plurality of movement schedules based on the expected value time and the approximate standard deviation time calculated for each movement schedule.

<How to make a plan>
Next, a plan creation method for creating a movement schedule using the plan creation device 1 of the present embodiment will be described with reference to FIG.

(Step S1)
First, information on a moving point such as a starting point and an arriving point and information on a proposition such as completing the movement within a few minutes are acquired as initial settings by input from an operator or the like.
In the present embodiment, for example, it is assumed that the starting point X, the arrival point Z, and the waypoint Y are input as the information about the moving point, and the initial setting that the moving is completed within 30 minutes is acquired as the proposition.

(Step S2)
Next, based on the information about the movement point received in step S1, the movement route acquisition unit 3 obtains information on all the movement routes that can be obtained from the database 2, and the expected value and standard deviation of the movement time for each movement route. , And get information about the probability distribution.

For example, assuming that the movement route from the departure point X to the waypoint Y is from A1 to A5 and the movement route from the waypoint Y to the arrival point Z is from B1 to B3, the movement route acquisition unit 3 shows the figure. As shown in 3, the information on the travel routes A1 to A5 and B1 to B3, and the expected value, standard deviation, and probability distribution of the travel time for each travel route is acquired.
In this example, there are 15 possible movement schedules: 5 (movement routes A1 to A5) x 3 (movement routes B1 to B3).

In the present embodiment, the case where the expected value, standard deviation, and probability distribution of the travel time for each travel route are recorded in the database 2 will be described, but the present invention is not limited to this.
For example, if only the (approximate) probability distribution for each travel route is stored, the calculation unit (not shown) separately obtains the expected value and standard deviation of the travel time from the probability distribution for each travel route, and the travel route. The acquisition unit 3 may acquire this value.

(Step S3)
Next, the expected value scenario creation unit 4 creates an expected value scenario in which the travel time is specified for all the travel routes, based on the expected value of the travel time for each travel route acquired in step S2. As a method of specifying the travel time of each travel route, for example, the expected value may be used as it is, or may be corrected by an appropriate correction coefficient. Further, instead of the expected value, other representative values such as the median value and the mode value may be used.
For example, when the expected value of the travel time for each travel route is the value shown in FIG. 3, if the expected value is used as it is, the expected value scenario created by the expected value scenario creation unit 4 is the one shown in FIG. It becomes.

(Step S4)
Next, the variation scenario creation unit 5 creates a variation scenario in which the travel time is specified for all the travel routes, based on the expected value and standard deviation of the travel time for each travel route acquired in step S2. As a method of specifying the travel time of each travel route, for example, a value obtained by adding a value obtained by multiplying the expected value of the travel time by the standard deviation of the travel time and a desired coefficient β may be used.

Specifically, when the expected value of the travel time of the travel route A1 is 10 minutes, the standard deviation is 4 minutes, and the desired coefficient β is 0.5, the travel time of the travel route A1 is set in the variation scenario. It will be 12 minutes (10 minutes + 4 minutes x 0.5).
If the expected value and standard deviation of the travel time for each travel route are the values shown in FIG. 3, and the desired coefficient β is 0.5, the variation scenario created by the variation scenario creation unit 5 is shown in FIG. It becomes as shown in 5.

The desired coefficient β may be determined as appropriate, but if it is set to a small value, the meaning of creating a variation scenario in addition to the expected value scenario is reduced, and conversely, if it is set to a large value, the worst situation with extremely low probability is assumed. It is not practical because it is a scenario. Therefore, practically, it is desirable to set the desired coefficient β in the range of 0.1 or more and 2 or less.
It is desirable to set β to a positive value based on the policy of creating a plan so that there is no delay.

In the above, the case where the variation scenario creation unit 5 creates one variation scenario has been described, but it is not always necessary to create one variation scenario, and a plurality of variation scenarios may be created depending on the size of the problem and the like. .. For example, as a variation scenario 1, a scenario is created by adding a value obtained by multiplying an expected value by a standard deviation by β, and as a variation scenario 2, a scenario is created by adding a value obtained by multiplying an expected value by a standard deviation by γ (> β). May be created.
Also, when creating the variation scenario, instead of using the value obtained by adding the value obtained by multiplying the standard deviation by β to the expected value, the time when the sum of the probabilities from the longer travel time corresponds to exactly θ%. Alternatively, an index indicating other variations such as the time when the sum of the probabilities from the expected value to the longer one corresponds to exactly τ% may be used.

(Step S5)
Next, the movement schedule specifying unit 6 specifies a movement schedule that satisfies the proposition initially set in step S1 based on the expected value scenario created in step S3 and the variation scenario created in step S4.
For example, the expected value scenario and the variation scenario are shown in FIGS. 4 and 5, and the proposition set by step S1 reaches the arrival point Z from the starting point X via the waypoint Y in 30 minutes. If this is the case, the combination of (A1, B1), (A1, B3), and (A3, B3) for the movement route is a movement schedule that satisfies this proposition.

As is clear from the above example, based on the expected value scenario and the variation scenario, the movement schedule that satisfies the proposition is not limited to one, and it is usually assumed that there are a plurality of movement schedules.
Then, in the following, a method of specifying a specific movement schedule from the plurality of movement schedules will be described using an iterative solution method, but the method is not limited to the iterative method and other methods such as the branch-and-bound method. You may use to specify the solution. The iterative method is a branch-and-bound method, a branch-cut method, a local search method, a tabu search method, an annealing method, a genetic algorithm, or the like, which is an iteratively feasible solution (or its relaxation). This is a method of finding a (quasi) optimal solution while finding a solution), but an approximate solution method other than the iterative solution method can also be used. In the case of the iterative solution, the movement schedule specifying unit 6 selects any one from a plurality of movement schedules in this step S5.

Further, in the present embodiment, the case of specifying the movement schedule that satisfies the proposition in both the expected value scenario and the variation scenario has been described. However, as described above, in the present embodiment, the variation scenario has a standard deviation more than the expected value scenario. The schedule is conservative (long travel time) for the time multiplied by the desired coefficient β.
Therefore, when a certain movement schedule satisfies the proposition under the variation scenario, the proposition is naturally satisfied also based on the expected value scenario for the movement schedule. Therefore, the movement schedule specifying unit 6 may specify the movement schedule that satisfies the proposition based on the variation scenario without referring to the expected value scenario.

(Step S6)
Next, the calculation unit 7 calculates the expected value time based on the expected value of the travel time of each travel route for the travel schedule specified in step S5, and sets the expected value and standard deviation of the travel time of each travel route. The variation time is calculated based on the variation time, and the expected value time is subtracted from the variation time to calculate the approximate standard deviation time.

As a method of calculating the expected value time, the expected value of the travel time of each travel route constituting the travel schedule may be simply added.
For example, when travel route A1 and travel route B3 are selected as the travel schedule, and assuming that the expected values of these travel times are as shown in FIG. 3, the expected value time of this travel schedule is 20 minutes (10 minutes). +10 minutes).

Here, since the expected value scenario is a scenario created based on the expected value of the travel time of each travel route, the calculation unit 7 adopts the travel schedule specified in step S5 in the expected value scenario. May be calculated and this may be used as the expected value time.
Specifically, the expected value time is calculated by adding the travel times of each travel route constituting the specified travel schedule with reference to the expected value scenario.

As a method of calculating the variation time, the expected value and standard deviation of the travel time of each travel route constituting the travel schedule may be simply added, but the squares of the standard deviations are added together. , You may add the square root of it to the expected value.
That is, when the expected value of the travel time constituting each travel route L1 to Lx is μ _{1 to μ x} and the standard deviation is σ _{1 to σ x} , the variation time is (μ ₁ + μ ₂ + ... + Μ _x ) ＋ (σ ₁ ＋ σ ₂ ＋ ・ ・ ・ ＋ σ _x ) may be used, but (μ ₁ ＋ μ ₂ ＋ ・ ・ ・ ＋ μ _x ) ＋ (σ ₁ ² ＋ σ ₂ ² ＋ ・ ・ ・ ＋ σ _x ² ) ^It may be 1/2.

For example, when travel route A1 and travel route B3 are selected, assuming that the expected values and standard deviations of these travel times are as shown in FIG. 3, the variation time of this travel schedule is 27 minutes (10 minutes + 10). Minutes + 4 minutes + 3 minutes) may be used, but 25 minutes (10 minutes + 10 minutes + (4 minutes ² + 3 minutes ² ) ^1/2 ) may be used.

Further, since the variation scenario is a scenario created based on the expected value and standard deviation of the travel time of the travel route, the calculation unit 7 sets the time when the travel schedule specified in step S5 is adopted in the variation scenario. It may be calculated and used as the variation time.

Specifically, the variation time is calculated by adding the travel times of each travel route constituting the specified travel schedule with reference to the variation scenario. In this case, when the travel time for each travel route in the variation scenario is the sum of the expected value and the value obtained by multiplying the standard deviation by the desired coefficient β, the calculated variation time is (μ _1). + Μ ₂ + ... + μ _x ) + β (σ ₁ + σ ₂ + ... + σ _x ).

(Step S7)
Next, the detection unit 8 detects whether or not the number of expected value time and approximate standard deviation time calculated in step S6 has reached N search numbers.
If the number of searches has not reached N, the process returns to step S5, and if the number of searches has been reached, the process proceeds to step S8.

The number of searches N may be set appropriately, but unlike the Monte Carlo method, which specifies the movement schedule regardless of the proposition, the movement schedule that satisfies the proposition is specified in this embodiment as well. Then, the number of searches N may be a relatively small number.

(Step S8)
Next, the determination unit 9 selects one movement schedule from the N movement schedules specified up to step S7 based on the expected value time and the approximate standard deviation time for each movement schedule, thereby selecting one movement schedule. A movement plan based on one movement schedule is created.

The basic policy of the selection method is to select the one with the minimum expected value time and the one with the minimum approximate standard deviation time. However, the movement schedule with the minimum expected value time does not always have the minimum approximate standard deviation time, so the selection should be focused on the expected value time or the approximate standard deviation time. It will be selected or weighted appropriately.

Here, the reason why the expected value time and the approximate standard deviation time are indicators of selection will be described in comparison with the probability planning method.
For example, the travel schedule S consists of travel route A1 and travel route B3, the expected travel time of travel route A1 is μ ₁ , the standard deviation is σ ₁ , and the expected travel time of travel route B3 is μ ₂ , standard. It is assumed that the deviation is σ ₂ and the travel time of the travel schedule S is simply the sum of the travel time of the travel route A1 and the travel time of the travel route B3.

In this case, when a sufficient number of scenarios are searched by the probability planning method, the expected value of the travel time of the travel schedule S is the sum of the expected value of the travel time of the travel route A1 and the expected value of the travel time of the travel route B3. , Μ ₁ + μ ₂ . The dispersibility of the moving time of the moving schedule S is normal if the distribution is equal to the sum of the variances of the moving time of the moving variance of the time (σ _{1 ²⁾} and the moving route B2 of the moving route A1 (σ _{2 ²⁾} Therefore, the standard deviation of the movement schedule S is (σ ₁ ² + σ ₂ ² ) ^1/2 .

On the other hand, according to the present embodiment, the expected value time of the movement schedule S is μ ₁ + μ ₂ , and the approximate standard deviation time is β (σ ₁ + σ ₂ ) (the variation time is obtained based on the variation scenario). When the approximate standard deviation time is calculated).

Therefore, the expected value time of this embodiment is equal to the expected value when the probability planning method is used.
In the stochastic programming, rather than the absolute value of the standard deviation, where the relative magnitude is important, whether it is β times is not important, also (σ _{1 +} σ ₂₎ and (sigma ₁ ² + Σ ₂ ² ) ^1/2 shows a sufficiently similar behavior.
Therefore, it can be said that the approximate standard deviation time of the present embodiment can be an index sufficiently close to the standard deviation when the probability planning method is used.

According to this embodiment, it is possible to create a robust plan with the same accuracy as the probability planning method, and it is not necessary to create a plurality of types of scenarios unlike the probability planning method, and the expected value scenario and the variation scenario. Since only the movement schedule is created, it is possible to find a movement schedule that satisfies all the scenarios without difficulty, and it is possible to create a robust plan within a practical time.

[Second Embodiment]
This embodiment is a modification of the first embodiment, and description of the same parts as those of the first embodiment will be omitted. In the present embodiment, a plan creation device and a plan creation method for creating a robust plan suitable when a meeting condition occurs will be described.
The meeting condition can be performed in parallel for the first work element and the second work element when there are the first work element and the second work element, but both must be completed. For example, there is a condition that the work cannot be completed or the next work element cannot be performed. For example, there are a vehicle moving from the point L to the point M and a vehicle moving from the point N to the point M. At the point M, 2 It refers to the condition that two vehicles meet.

<Planning device>
As shown in FIG. 6, the plan creation device 11 of the present embodiment has a correction time information acquisition unit 12, a reference value selection unit 13, and a reference value calculation unit in addition to the plan creation device 1 of the first embodiment. 14, a travel time specifying unit considering a wait (a required time specifying unit considering a wait) 15, a detection unit 16, a moving time calculation unit considering a wait (a required time calculation unit considering a wait) 17, and It includes an independent correction time derivation unit 18, a detection unit 19, a correction time derivation unit 20, and a correction time calculation unit 21.
These are all functional units that calculate the correction time for correcting the expected value time and the approximate standard deviation time so as to approximate the expected value and the standard deviation according to the probability planning method. Details will be described later.

<How to make a plan>
Next, a method of creating a movement schedule using the plan creation device 11 of the present embodiment will be described with reference to FIG. 7.

(Step S1')
In the present embodiment, first, information on the moving point including the meeting condition and information on the proposition are acquired as initial settings by input from the operator or the like.

(Steps 2 to 5)
Next, in the present embodiment, steps S2 to S5 are performed in the same manner as in the first embodiment.

(Step S11)
Further, in the present embodiment, at the same time as or before or after steps S1'to S5, the correction time information acquisition unit 12 selects two movement routes from which the waiting conditions can be randomly set (arbitrarily) from the database 2. One movement route that moves from the meeting place to another place is selected, and information on the probability distribution, the expected value, and the standard deviation is acquired for each movement route.
For example, the movement route C from the point P to the point Q, the movement route D from the point R to the point Q, and the movement route E from the point Q to the point S are selected, and the expected value and standard as shown in FIG. 8 are selected. Get information about deviations and probability distributions.
In this embodiment as well, the expected value and the standard deviation will be described as an example, but as in the first embodiment, another representative value may be used instead of the expected value, for example, the median value and the mode. You may use a value or the like. Further, instead of the standard deviation, another index indicating the degree of variation may be used. For example, the time when the sum of the probabilities from the longer travel time corresponds to exactly θ%, or from the expected value to the longer one. You may use the time when the sum of probabilities corresponds exactly to τ%.

(Step S12)
Next, the reference value selection unit 13 selects the two travel routes for which the waiting conditions selected in step S11 can be set, which have a larger expected value of the travel time.
For example, in the above example, as shown in FIG. 8, the expected value of the travel time of the travel route C is 15 minutes, and the expected value of the travel time of the travel route D is 10 minutes. The selection unit 13 selects the movement route C.

(Step S13)
Next, the reference value calculation unit 14 determines the expected value and standard deviation of the travel time for the travel route specified in step S12, and the travel time for the travel route that moves from the meeting place selected in step 11 to another location. Based on the expected value and standard deviation, the values of the standard expected value (reference representative value) and the reference standard deviation (index indicating the degree of reference variation) are calculated.
As a specific calculation method, the expected value and the standard deviation may be simply added. For example, in the above example, as shown in FIG. 8, the expected value of the travel route C is 15 minutes, and the standard deviation is 5 minutes. On the other hand, the expected value of the travel route E is 20 minutes, and the standard deviation is 6 minutes. Therefore, the reference value calculation unit 14 calculates the reference expected value as 35 minutes (15 minutes + 20 minutes) and the reference standard deviation as 11 minutes (5 minutes + 6 minutes).
As for the reference standard deviation, the square root of the square root of each travel route may be calculated by adding the squared standard deviation.

(Step S14)
Next, the travel time specifying unit 15 in consideration of the meeting derives specific values according to the probability distribution for each of the two travel routes specified in step S11 and the travel route that moves from the meeting location to another location, and waits. Calculate the total travel time under the constraints of the conditions.
For example, if the travel time of the travel route C is 14 minutes, the travel time of the travel route D is 12 minutes, and the travel time of the travel route E is 18 minutes, the total travel time is 32 minutes (14 minutes + 18 minutes).

(Step S15)
Next, the detection unit 16 detects whether or not the total number of travel times specified by step S14 has reached T.
If the total number of travel times has not reached T, the process returns to step S14, and if it does, the process proceeds to step S16.
The number T may be any number as long as it is suitable for obtaining the average and the variance.

(Step S16)
Next, the travel time calculation unit 17 considering the wait calculates the expected value and the standard deviation based on the T travel times specified by step S15, so that the travel time considering the wait can be calculated. Obtain the approximate expected value (approximate representative value of the required time considering the waiting time) and the approximate standard deviation of the travel time considering the waiting (an index indicating the approximate variation of the required time considering the waiting time).

(Step S17)
Next, the independent correction time derivation unit 18 obtains the reference expected value and the reference standard in step S13 from the approximate expected value of the travel time considering the wait and the approximate standard deviation of the travel time in consideration of the wait obtained in step S16. The deviation is subtracted to obtain the single expected value correction time (single representative value correction time) and the single standard deviation correction time (index correction time indicating the degree of individual variation).
For example, in the previous example, it is assumed that the approximate expected value of the travel time considering the wait calculated in step S16 is 40 minutes, and the approximate standard deviation of the travel time considering the wait is 15 minutes. Further, in the previous example, since the reference expected value was 35 minutes and the reference standard deviation was 11, the independent correction time derivation unit 18 set 5 minutes (40 minutes-35 minutes) as the independent expected value correction time. Calculate 4 minutes (15 minutes-11 minutes) as the independent standard deviation correction time.

(Step S18)
Next, the detection unit 19 detects whether or not the number of the single expected value correction time and the single standard deviation correction time specified by step S17 has reached U. If the number of U has not been reached, the process returns to step S11, and if the number is reached, the process proceeds to step S19.
The number U may be any number as long as a reliable average can be obtained for the single expected value correction time and the single standard deviation correction time.

(Step S19)
Next, the correction time derivation unit 20 obtains the average value of each of the U single expected value correction time and the single standard deviation correction time obtained in step S17, thereby obtaining the expected value correction time (representative value correction time). ) And the standard deviation correction time (index correction time indicating the degree of variation) are calculated.

Here, the meanings of the expected value correction time and the standard deviation correction time will be described.
First, the single expected value correction time and the single standard deviation correction time are simply the expected value and standard deviation of the travel time of the travel route from the expected value and standard deviation that can actually occur when an arbitrary waiting condition occurs. It is the value obtained by subtracting the sum.
Therefore, if the single expected value correction time and the single standard deviation correction time are known, the expected value and standard deviation of the travel time for each travel route are simply added under this waiting condition. Then, by adding the single expected value correction time and the single standard deviation correction time to this, the expected value and the standard deviation that can actually occur can be obtained.

However, since the single expected value correction time and the single standard deviation correction time are values found based on arbitrary waiting conditions, the possibility that they are special conditions cannot be ruled out, and they were applied to other meeting conditions. In that case, the accuracy is inferior.

Therefore, the expected value correction time and the standard deviation correction time are obtained by collecting U individual expected value correction times and individual standard deviation correction times and calculating the average of them.
As a result of obtaining this value, the expected value and standard deviation of the travel time for each travel route are added under any waiting condition, and the expected value correction time and standard deviation correction time are added, respectively. Therefore, the expected value and standard deviation that can actually occur can be approximated and obtained.

If it is considered that the waiting conditions for the independently expected value correction working time and the independent standard deviation correction time that are arbitrarily obtained are not special conditions and can be applied to other waiting conditions, the values are expected. It may be regarded as the value correction time and the standard deviation correction time.
Further, in the above, the correction when the expected value and the standard deviation are used has been described, but as in the first embodiment, another representative value is used instead of the expected value, and other variations are used instead of the standard deviation. Even if an index indicating the degree is used, the representative value correction time and the index correction time indicating the degree of variation may be obtained in the same manner.

(Step S6-1)
Next, the correction calculation unit 21 corrects the expected value time and the approximate standard deviation time for the specific movement schedule calculated in step S6 based on the expected value correction time and the standard deviation correction time calculated in step S19.

As a method of correction, for example, the approximate expected value time is corrected by adding the expected value correction time to the approximate expected value time.
Further, if the variation time is obtained in step S6 based on the variation scenario, the approximate standard deviation time is a value obtained by multiplying the standard deviation by the desired coefficient β (β (σ1 + σ2 + ... + σx)). Therefore, the correction calculation unit 21 may correct the approximate standard deviation time by adding a value obtained by multiplying the standard deviation correction time by a desired coefficient β to the approximate standard deviation time.

(Step S7)
Next, the detection unit 8 detects whether or not the number of the approximate expected value time and the approximate standard deviation time corrected by step S6-1 has reached N search numbers. If it has not been reached, the process returns to step S5, and if it has been reached, the process proceeds to step S8.

(Step S8)
Next, the determination unit 9 selects one of the N movement schedules specified in step S7 based on the corrected expected value time and the corrected approximate standard deviation time for each movement schedule. Select and this will create a travel plan based on one travel schedule.
The selection method is the same as the selection method of the expected value time and the approximate standard deviation time in the first embodiment.

Generally, when a wait condition occurs for the first work element and the second work element, the total required time is basically determined by the work element having a long expected value of the required time, but in some cases, the required time is determined. Working elements with shorter expectations may take longer.
Therefore, the probability distribution of the total required time is such that the probability distribution of the work element having a long expected value of the required time is slid to the right.
Therefore, it is not possible to obtain a sufficiently approximate probability distribution by simply adding the probability distributions for each work element.
In the present embodiment, even when such a waiting condition occurs, the expected value correction time and the standard deviation correction time to be corrected when the waiting condition occurs are obtained in advance, so that the accuracy is higher. It can be approximated to the plan created by the probabilistic planning method.

The process of each process in the above-mentioned planning apparatus is stored in a computer-readable recording medium in the form of a program, and the process is performed by the computer reading and executing this program. Here, the computer-readable recording medium refers to a magnetic disk, a magneto-optical disk, a CD-ROM, a DVD-ROM, a semiconductor memory, or the like. Further, this computer program may be distributed to a computer via a communication line, and the computer receiving the distribution may execute the program.

Further, the above program may be for realizing a part of the above-mentioned functions. Further, it may be a so-called difference file (difference program) that can realize the above-mentioned function in combination with a program already recorded in the computer system.
Further, the planning apparatus may be composed of one computer, or may be composed of a plurality of computers connected so as to be able to communicate with each other.

Further, in the above embodiment, the travel route as a work element, the travel time as the required time, and the travel schedule as the required schedule have been described as an example, and the plan for delivering the vehicle has been described in mind, but the present invention is not limited to this.
In addition, the present invention can be applied to the planning of a production schedule for planning the order in which parts are produced on each production line in a factory.

For example, part X can be manufactured on production line A and production line B, but the process time is different, part Y can be manufactured on production line C, and parts X and Y can be attached to production line D and manufacturing. It can also be applied to cases where it can be manufactured on line E.
In this case, the work element is a work process such as production line A to production line E, the required time is the process time in each production line A to E, and the required schedule is which production line manufactures part X and which production line. It is a production schedule that determines whether to install parts X and Y on the line.
Further, in this case, since the next process cannot be proceeded unless the parts X and Y are completed, the production line A (or the production line B) and the production line C have a waiting condition.

The simulation results of carrying out the present invention will be described below.
In this simulation, 56 vehicle delivery problems in which 20 vehicles are arranged at 20 locations are randomly created, and the case of the plan in which the present invention is implemented and the case of the conventional mathematical model in which the travel time is fixed are selected. Compared.
As a result, when the present invention was implemented, it was possible to obtain a robust delivery plan with a low probability of delivery delay within 10 minutes as compared with the conventional technique.

The present invention is applicable when creating a robust plan by combining work elements that require work time according to a probability distribution.

1,11 ... plan creation device, 2 ... database, 3 ... movement route acquisition unit, 4 ... variation scenario creation unit, 5 ... expected value scenario creation unit, 6 ... movement schedule Specific unit, 7 ... Calculation unit, 8, 16, 19 ... Detection unit, 9 ... Judgment unit, 12 ... Correction coefficient information acquisition unit, 13 ... Reference value selection unit, 14 ... -Reference value calculation unit, 15 ... Movement time identification unit considering waiting, 17 ... Movement time calculation unit considering waiting, 18 ... Independent correction time derivation unit, 20 ... Correction time derivation unit , 21 ... Correction calculation unit

Claims (10)

A planning device that creates a required schedule by selecting a plurality of specific work elements from a plurality of work elements.
A work element information acquisition unit that acquires an index indicating a plurality of work elements and the degree of variation in the required time for each work element.
A variation scenario creation unit that creates a variation scenario in which the required time is specified for each work element based on an index indicating the degree of variation in the required time.
A required schedule specifying unit that specifies a plurality of different required schedules based on the variation scenario,
A determination unit that specifies a specific required schedule from the plurality of required schedules,
The first reference time is calculated based on the expected value of the required time of the work elements constituting the required schedule, and the second reference time is calculated based on the expected value of the required time of the work elements constituting the required schedule and the standard deviation. It is provided with a calculation unit that calculates and calculates a third reference time based on the first reference time and the second reference time.
The determination unit identifies a specific schedule from the plurality of required schedules based on the first reference time and the third reference time calculated for each of the plurality of different required schedules. Planning device. The planning apparatus according to claim 1 , wherein the index indicating the degree of variation in the required time is an expected value and a standard deviation of the required time. The planning creation device according to claim 1 or 2 , wherein there are a plurality of variation scenarios created by the variation scenario creation unit. Claim 1 is characterized in that it includes an expected value scenario creating unit that creates an expected value scenario in which the required time is specified for each work element based on the expected value of the required time acquired by the work element information acquisition unit. The planning apparatus according to any one of claims 3. The time required for each work element specified by the variation scenario creation unit is added by multiplying the expected value of the time required for each work element by the standard deviation of the time required for each work element and a desired coefficient. The planning apparatus according to any one of claims 2 to 4, wherein the value is a value. It is an arbitrary first work element or third work element, and the first work element and the second work element can be performed in parallel, but the third work element cannot be performed unless both are completed. A correction coefficient information acquisition unit that identifies a certain object and acquires an index indicating a probability distribution, a representative value, and a degree of variation in the time required for the first work element or the third work element.
A work element selection unit that selects a work element having a large representative value of the required time among the first work element and the second work element.
From the index showing the representative value and the degree of variation of the required time of the work element selected by the work element selection unit and the index showing the representative value and the degree of variation of the required time of the third work element, the reference representative value and the reference variation. A reference value calculation unit that calculates an index showing the condition, and
It is necessary to derive a specific time according to a probability distribution for each of the required times of the first working element or the third working element, and to perform the first working element or the third working element under the constraint of the waiting condition. A time-specific part that takes into account the waiting time to calculate the time,
The required time considering the waiting The required time considering the waiting is obtained by acquiring a plurality of times calculated by the specified unit and obtaining the approximate representative value of the required time considering the waiting and the index indicating the approximate variation of the required time considering the waiting. Computational unit and
The representative value correction time and variation are obtained by subtracting the reference representative value and the index indicating the reference variation from the approximate representative value of the required time considering the meeting and the index showing the approximate variation of the required time considering the meeting, respectively. An index that indicates the condition. A correction time calculation unit that calculates the correction time, and a correction time calculation unit.
The claim is characterized in that it includes a correction calculation unit that corrects the first reference time and the third reference time calculated by the calculation unit based on the representative value correction time and the index correction time indicating the degree of variation. planning apparatus according to any one of 1 to claim 5. The working element includes a travel route
The required time includes travel time
The planning apparatus according to any one of claims 1 to 6 , wherein the required schedule is a moving schedule. The work element includes a work process
The required time includes the process time
The planning apparatus according to any one of claims 1 to 6 , wherein the required schedule is a production schedule. It is a planning method that creates a required schedule consisting of selecting multiple specific work elements from multiple work elements.
A work element information acquisition step in which the planning apparatus acquires a plurality of work elements and an index indicating the degree of variation in the required time for each work element.
A variation scenario creation step in which the planning apparatus creates a variation scenario in which the required time is specified for each work element based on an index indicating the variation degree of the required time.
A required schedule specifying step in which the planning device identifies a plurality of different required schedules based on the variation scenario.
A determination step in which the planning apparatus specifies a specific required schedule from the plurality of required schedules.
The planning apparatus calculates the first reference time based on the expected value of the required time of the work elements constituting the required schedule, and is based on the expected value and standard deviation of the required time of the work elements constituting the required schedule. The second reference time is calculated, and the first reference time and the third reference time are calculated based on the second reference time.
The determination step is characterized in that a specific schedule is specified from the plurality of required schedules based on the first reference time and the third reference time calculated for each of the plurality of different required schedules. How to make a plan. On a computer for creating a required schedule consisting of selecting multiple specific work elements from multiple work elements,
A work element information acquisition means for acquiring a plurality of work elements and an index indicating the degree of variation in the required time for each work element.
A variation scenario creating means for creating a variation scenario in which the required time is specified for each work element based on an index indicating the degree of variation in the required time.
A required schedule specifying means for specifying a plurality of different required schedules based on the variation scenario, and
A determination means for specifying a specific required schedule from the plurality of required schedules,
The first reference time is calculated based on the expected value of the required time of the work elements constituting the required schedule, and the second reference time is calculated based on the expected value of the required time of the work elements constituting the required schedule and the standard deviation. A calculation means for calculating and calculating a third reference time based on the first reference time and the second reference time.
Is a program that executes
The determination means is a program that specifies a specific schedule from a plurality of required schedules based on the first reference time and the third reference time calculated for each of a plurality of different required schedules.

Images