JP7480956B2 - Route generation device, route generation method, and program - Google Patents

Description

The present invention relates to a route generation device, a route generation method, and a program.

The optimal route for visiting multiple locations can be found, for example, by solving the traveling salesman problem (see, for example, Patent Document 1).

JP 2008-293262 A

On the other hand, when making rounds to customers in various locations to deliver kerosene, it may be better to select customers who are running low on kerosene rather than visiting every customer every time. In such cases, the number of customers visited in each round is reduced, and the working hours of the workers delivering the kerosene can be reduced.

However, if delivery hours continue to be reduced, eventually some customers will run out of kerosene, and the number of customers to whom kerosene must be delivered will suddenly increase, requiring long hours of overtime.

The present invention has been made in consideration of these problems, and provides a route generation device, route generation method, and program that can generate a route for supplying materials to multiple locations by performing multiple cycles of visiting at least some locations selected from multiple locations while changing the combination of locations, thereby generating a route for supplying materials to multiple locations that can both reduce and level the work time of workers performing the route.

A route generation device according to one embodiment of the present invention is a route generation device that generates a route for resupplying a plurality of locations by performing multiple cycles of visiting at least some locations selected from a plurality of locations while changing the combination of the locations, and includes a necessity memory unit that stores the degree of necessity of visiting each location in each cycle of a tour from the first to the final tour, which is calculated based on a stock forecast of materials for each location, a first index value that indicates the degree to which a location with a higher degree of necessity of visiting is selected as a tour location from among the plurality of locations for each tour cycle, a second index value that indicates the route length of the tour route that visits the tour locations, a tour time required for the tour route, and a predetermined and a third index value representing the difference between the target time and the first index value, and a route generation unit that performs a route generation process to select a route point from the plurality of points based on the first index value, the second index value, and the third index value to generate a route. When a route is generated in which the time required for a tour exceeds a predetermined target time by more than a first predetermined time in any cycle, the route generation unit corrects the degree of necessity stored in the degree of necessity storage unit so that the predetermined point selected as a route point in the time exceeding cycle is less likely to be selected as a route point in the time exceeding cycle, and then performs the route generation process again.

Other problems and solutions disclosed in this application will be made clear through the description in the section on the embodiment of the invention and the drawings, etc.

By performing multiple cycles of patrolling at least some of the locations selected from a plurality of locations while changing the combination of locations, it is possible to generate a patrol route for resupplying multiple locations that can both reduce and level out the work time of workers performing the patrol.

9 is a diagram showing a state in which a plurality of points 300 are scattered within an area 900. FIG. FIG. 1 is a diagram showing how a route generation device generates routes for multiple days. FIG. 2 is a diagram illustrating a hardware configuration of the route generation device. FIG. 4 is a diagram illustrating a storage device of the travel route generation device. FIG. 13 is a diagram showing a visiting point management table. FIG. 13 illustrates a necessity management table. FIG. 13 illustrates a work schedule management table. FIG. 13 is a diagram showing a work time adjustment table. FIG. 13 illustrates an area management table. FIG. 2 is a diagram illustrating a functional configuration of a route generation device. FIG. 13 is a diagram for explaining a tour route. 10 is a flowchart illustrating a process flow of a route generation method. 13 is a flowchart for explaining the hill-climbing method. 1 is a flowchart for explaining a simulated annealing method. FIG. 13 is a diagram for explaining score correction (correction using a positive score bias). FIG. 13 is a diagram for explaining score correction (correction using a negative score bias). FIG. 9 is a diagram for explaining the division of an area 900. FIG. 13 illustrates a work schedule management table. 10 is a flowchart illustrating a process flow of a route generation method. FIG. 11 is a diagram for explaining a target time update process.

At least the following points become clear from the description in this specification and the attached drawings. The present invention will be described below in accordance with an embodiment with reference to the attached drawings.

==Overview==
1 shows a state in which a plurality of points 300 (18 locations) are scattered within an area 900. The route generation device 100 according to the embodiment of the present invention performs multiple cycles of visiting at least some of the points 300 selected from the plurality of points 300 while changing the combination of the points 300, thereby generating a route for resupplying the plurality of points 300 with commodities such as kerosene.

A kerosene tank (not shown) is installed at each location 300, and kerosene is consumed daily by customers located at each location 300.

Kerosene is replenished from time to time by workers who make the rounds of each point 300. The workers leave the base (indicated by a star in FIG. 1) according to the route generated by the route generating device 100, and while making the rounds to the designated points 300, they replenish the tanks at each point 300 with kerosene and return to the base. The workers make one round, with one cycle being from leaving the base to returning. In this embodiment, the workers make one round per day, but multiple rounds per day may also be possible. Alternatively, there may be days when they do not make a round.

Kerosene does not have to be replenished at all points 300 every time, but can be selectively replenished at points 300 where the stock (remaining amount) in the tank is low. Therefore, the route generating device 100 generates an optimal route by taking into consideration the stock of kerosene at each point 300, the travel distance required for the tour, and the work time required for the tour. However, if the route is generated by focusing only on optimizing the immediate route, the number of points 300 that need to be patrolled in later cycles may increase, resulting in problems such as the need for significant overtime work by workers.

Therefore, the tour route generation device 100 according to this embodiment does not generate an optimal tour route only for the most recent cycle for which the tour route is being generated, but instead generates tour routes for each of the multiple cycles that follow that cycle, adjusts the work time in those cycles (from the first to the final cycle) to be leveled and shortened, and then generates a tour route from the first to the final cycles again. The tour route generation device 100 repeats this process a predetermined number of times (five times in this embodiment), and then generates and outputs the tour route for the first time (first day) that is to be obtained.

The route calculated for the cycle from the second day to the last day (the seventh day in this embodiment) is discarded because it is an attempt to level out the initial route. Therefore, for example, after actually performing patrol work along the route for the first day obtained by calculating the route for the first day from the first day to the seventh day, if a route equivalent to the cycle for the second day is required the next day, the route is calculated again for a new seven-day cycle (a cycle equivalent to the second day from the first day to the eighth day) that incorporates the latest predicted inventory status of kerosene. In this way, the route generation device 100 calculates a route for one day that always takes into account the situation up to a certain period of time ahead.

Figure 2 shows how the route generation device 100 generates routes for each cycle from the first day to the seventh day. Figure 11 shows the route for the first day that was generated after adjustments were made to shorten and level out the work time for each cycle.

In this manner, it is possible to generate a route that can both reduce and equalize the working hours of the workers performing the patrol.

The patrol of the locations 300 (18 locations in the example of Figure 1) within the area 900 may be performed by one worker, or the area 900 may be divided into multiple (e.g., three) small areas 910, with a different worker in charge of patrolling each small area 910 (see Figure 17).

Note that, although Figures 1, 11, and 17 show the route generation device 100 being installed at the base of the worker indicated by a star, the location where the route generation device 100 is installed does not have to be the base, and may be outside the area 900.

==Circulation Route Generation Device==
Next, the route generation device 100 will be described.

The hardware configuration of the route generation device 100 is shown in FIG. 3. The route generation device 100 is a computer that includes a CPU (Central Processing Unit) 110, a memory 120, a communication device 130, a storage device 140, an input device 150, an output device 160, and a recording medium reading device 170.

The storage device 140 stores various programs and data, such as the route generation device control program 700 executed by the CPU 110.

The various functions of the route generation device 100 are realized by reading the route generation device control program 700 and various data stored in the storage device 140 into the memory 120 and executing or processing them by the CPU 110.

Here, the storage device 140 is, for example, a non-volatile storage device such as a hard disk, SSD (Solid State Drive), or flash memory.

As shown in FIG. 4, the storage device 140 stores a route generation device control program 700, a visiting location management table 600, a necessity management table 610, a work schedule management table 620, a work time adjustment table 630, and an area management table 640.

The recording medium reading device 170 reads the travel route generating device control program 700 and data recorded on a recording medium 800 such as a CD, DVD, or SD card, and stores them in the storage device 140.

The communication device 130 is an interface that transmits and receives various data and the route generating device control program 700 via the network 500 with other computers (not shown) installed at each of the above-mentioned points 300 or other points. For example, the route generating device control program 700 and data described above can be stored in another computer, and the route generating device 100 can obtain the route generating device control program 700 and data from this computer. Alternatively, the communication device 130 can communicate with a mobile terminal such as a smartphone or laptop (not shown) carried by a worker to transmit and receive various information.

The network 500 may be any of a variety of information and communication networks, such as the Internet, a LAN (Local Area Network), or a telephone network.

The input device 150 is a device such as various buttons, switches, a mouse, or a keyboard that accepts commands and data input by the user, and functions as an input user interface.

The output device 160 is, for example, a display device such as a display, a speaker, or other device, and functions as an output user interface.

<Visiting Point Management Table>
5 shows a visited point management table 600 stored in the storage device 140. The visited point management table 600 is a table that stores a visited point ID for uniquely identifying each point 300 and information indicating the location of each point 300 in association with each other.

In the example shown in FIG. 5, the location of each point 300 is identified by latitude and longitude as an example, but it may also be identified by address.

<Necessity Management Table>
The necessity management table 610 is shown in Fig. 6. The necessity management table 610 is a table that stores the necessity (score) of visiting each point 300 in each cycle of visiting from the first to the last (from the first to the seventh day in this embodiment). Fig. 6 shows a table related to point A. The score is larger the more preferable it is to visit that point 300, and is calculated and corrected by the visiting route generation unit 102 (described later) based on the stock forecast of kerosene at each point 300. The score is calculated, for example, from the ratio of the remaining amount of kerosene to the tank capacity.

The score is also appropriately corrected by the tour route generation unit 102 to make a specific location 300 more likely to be selected as a tour location or less likely to be toured. The score is corrected by adding or subtracting a correction value called a score bias to the score stored in the necessity management table 610. A score bias added to a score is called a positive score bias, and a score bias subtracted from a score is called a negative score bias. For this reason, when a positive score bias is added to a score, the necessity of touring the location 300 increases, making it easier for the tour route generation device 100 to select the location 300 as a tour location. Conversely, when a negative score bias is subtracted from a score, the necessity of touring the location 300 decreases, making it harder for the tour route generation device 100 to select the location 300 as a tour location.

The inventory forecast of kerosene at each point 300 is performed by the inventory forecasting unit 107, which will be described later. The inventory forecasting unit 107 collects, for example, daily consumption of kerosene and remaining amount of kerosene in the tank from each point 300 at any time via the communication device 130, and calculates a forecast value of the daily inventory of kerosene for each customer, taking into account changes in kerosene consumption trends due to seasons, time periods, days of the week, weather, etc., and the capacity of each customer's tank. In addition, when kerosene is refilled by a worker, the inventory forecasting unit 107 returns the inventory amount (remaining amount) of kerosene at that point 300 to the maximum value (tank capacity). In addition, the inventory forecast includes forecasts assuming all possible cases in which kerosene refilling at each point 300 is performed in each cycle from the 1st to the 7th day and all possible cases in which it is not performed.

The necessity management table 610 records information on "fueling record," "location condition," "amount of fuel refueled," and "score" for each "target date" from the first to the seventh day.

The "Fueling Record" column is a column for indicating whether or not refueling has occurred in the cycle prior to the target day. The "Fueling Record" column further includes columns for "Day 1" through "Day 6." For example, if kerosene was refilled on the first day of a tour, a circle is entered in "Day 1," and if kerosene was not refilled on the first day, a cross is entered in "Day 1."

The "Location Status" column records information on the necessity of patrolling the location 300, expressed in three levels: "Patrol Required," "Optional Patrol," and "No Patrol Required." "Patrol Required" indicates that the location 300 must be patrolled. "Optional Patrol" indicates that the location 300 may or may not be patrolled. "No Patrol Required" indicates that the location 300 is not subject to patrol. Each of the states, "Patrol Required," "Optional Patrol," and "No Patrol Required," is identified by the location classification unit 105, described below, from the score or the remaining amount of kerosene.

The "Fuel Amount" column indicates the amount of kerosene that can be replenished at that point 300. The amount of fuel that can be replenished can be calculated from the difference between the kerosene tank capacity and the remaining amount. The more points 300 with a larger amount of fuel are visited, the more efficient the patrol will be.

The "Score" column records the degree of necessity for patrolling. In this embodiment, when the state of the location 300 is "optional patrol," the score is recorded to indicate the degree to which patrolling the location 300 is desirable, but the score may also be recorded when the state is "required patrol" or "unnecessary patrol."

To explain the contents of the necessity management table 610 using the example shown in Figure 6, on the first day, point A has a score of 4 and is in an "optional patrol" state, and 90 liters of kerosene can be filled up. In this case, point A may or may not be selected as a patrol point when the patrol route for the first day is generated.

Also, on the second day, if kerosene was not replenished on the first day, the score would rise to 6, the state would be "optional patrol," and 220 liters of kerosene could be refueled. On the other hand, if kerosene was refueled on the first day, the state would be "no patrol required" on the second day, and 48 liters of kerosene could be refueled. If "no patrol required," point A would not be selected as a patrol point.

On the third day, if kerosene is not replenished on either the first or second day, the state will be "patrol required" and 320 liters of kerosene can be refueled. In this case, point A will always be selected as a patrol point on the patrol route on the third day. On the other hand, if kerosene is replenished on the first day, the state will be "patrol not required" as on the second day, and 84 liters of kerosene can be refueled. In this case, point A will not be selected as a patrol point on the patrol route on the third day. Also, if kerosene is replenished on the second day, the state will be "patrol not required" and 30 liters of kerosene can be refueled. In this case, point A will not be selected as a patrol point on the patrol route on the third day. Note that if kerosene is replenished on the second day, the state will be the same regardless of whether replenishment was performed on the first day. In Figure 6, this is collectively represented as "- 〇". For the same reason, the necessity state on the fourth day can be expressed in four ways: "× × ×", "〇 × ×", "- 〇 ×", and "- - 〇".

<Work Schedule Management Table>
The work schedule management table 620 is shown in Fig. 7. The work schedule management table 620 records work schedule information that describes the planned work times of the workers who replenish kerosene for each cycle from the first patrol to the last patrol (the first to seventh days in this embodiment), that is, the planned work start times and planned work end times of the workers who perform the patrol.

Note that Figure 7 shows an example in which there is one worker, but if there are multiple workers, the work schedule for each worker is recorded as shown in Figure 18.

This planned work time, together with the adjustment time recorded in the work time adjustment table 630 described below, becomes the target work time when the circular route generation device 100 generates a circular route. In other words, the circular route generation device 100 generates a circular route so that the work time is as close as possible to the total time of the planned work time recorded in the work schedule management table 620 and the adjustment time recorded in the work time adjustment table 630. Of course, if the adjustment time is 0, the circular route generation device 100 generates a circular route with the planned work time recorded in the work schedule management table 620 as the target time.

The work schedule management table 620 may also record work efficiency according to the weather and other factors for each day. Work efficiency represents the distance a worker can travel per unit of time, and is defined as 1.0 for sunny or cloudy days. Therefore, even if the patrol route is the same, on a day when the work efficiency is 0.5 (for example, a rainy or stormy day), twice as much work time is required as on a day when the work efficiency is 1.0.

The work schedule and work efficiency values are input in advance to the route generation device 100 via an interface such as the input device 150, the recording medium reading device 170, the communication device 130, or an API (Application Programming Interface).

<Work time adjustment table>
The work time adjustment table 630 is shown in Fig. 8. The work time adjustment table 630 records a time corresponding to the difference between a target time when the route generation device 100 generates a route and the scheduled work time recorded in the work schedule management table 620.

In other words, the route generation device 100 generates a route so that, in principle, the deviation from the planned work times listed in the work schedule management table 620 is as small as possible, but as a result of adjusting the work times of the route over multiple cycles (from the first day to the seventh day), there may be cases where it is determined that working overtime would be more efficient overall, or that it would be more efficient to finish work early and shorten the work time.

In such a case, the route generation device 100 updates the adjustment time in the work time adjustment table 630. For example, if it would be better to work 30 minutes of overtime, it would be entered as +0.5.

In this way, the tour route generation device 100 adjusts the target time for each tour cycle and recalculates the tour route.

In the example shown in Figure 8, +0.5 is written on the first day, which means that the target work time on the first day will be extended by 30 minutes. Also, -1.0 is written on the fifth day, which means that the target work time on the fifth day will be shortened by 60 minutes.

The contents of the work time adjustment table 630 are generated and updated as appropriate when the route generation device 100, described below, generates a route for each cycle.

<Area management table>
9 shows the area management table 640. The area management table 640 is a table that stores area IDs, which are identification information for each small area 910 obtained by dividing the entire area 900, and point IDs, which are identification information for points 300 within each small area 910, in association with each other.

In the example shown in FIG. 9, the entire area 900 is divided into three small areas 910 (area 0, area 1, and area 2), and each small area 910 includes six locations 300. This is shown in FIG. 17.

In this case, three workers will each be responsible for visiting six locations 300. The route generation device 100 then generates a route for each small area 910.

If the area 900 is not divided, the entire area 900 can be managed as one small area 910.

<Functional configuration of the route generation device>
Next, the functional configuration of the route generation device 100 will be described with reference to the functional configuration diagram shown in FIG.

As described above, the route generation device 100 realizes various functions as the route generation device 100 by reading the route generation device control program 700 and various data stored in the storage device 140 into the memory 120 and executing or processing them by the CPU 110.

Specifically, the tour route generation device 100 has the functions of a necessity memory unit 101, a tour route generation unit 102, a tour delay possible point selection unit 103, a target time memory unit 104, a point classification unit 105, a region division unit 106, and an inventory forecasting unit 107.

The inventory prediction unit 107 collects, for example, daily kerosene consumption and remaining amount of kerosene in the tank from each point 300 at any time via the communication device 130, and calculates a predicted value of each customer's daily kerosene inventory amount while taking into account changes in kerosene consumption trends due to season, time of day, day of the week, weather, etc., and the capacity of each customer's tank. In addition, when kerosene is refilled, the inventory prediction unit 107 returns the kerosene inventory amount (remaining amount) at that point 300 to the maximum value (tank capacity).

Alternatively, the inventory prediction unit 107 may not use the communication device 130 to obtain the current inventory amount, but may instead predict the amount of kerosene consumed based on past consumption trends and the date of the previous visit, and calculate a predicted value for the daily inventory amount.

The route generating device 100 may be configured not to include the inventory forecasting unit 107. In this case, the functionality of the inventory forecasting unit 107 is provided by another computer (not shown), and the route generating device 100 obtains daily inventory forecasts for kerosene at each point 300 via the communication device 130 using an API constructed to obtain the results of the inventory forecast from this computer.

Alternatively, another computer (not shown) may calculate information indicating the necessity of patrolling each point in each cycle of patrol from the first to the final patrol based on the kerosene inventory forecast for each point, and obtain each piece of information to be recorded in the necessity management table 610 based on this information. In this case, the tour route generation device 100 uses an API constructed to obtain each piece of information to be recorded in the necessity management table 610 from this computer, obtains each piece of information via the communication device 130, and records it in the necessity management table 610.

The necessity storage unit 101 stores the necessity (score) of patrols of each location 300 in each cycle of patrols from the first to the final one, which is calculated based on the kerosene inventory forecast for each location 300. In this embodiment, the necessity storage unit 101 is embodied as a necessity management table 610.

The tour delay possible point selection unit 103, which will be described in detail later, selects from among the multiple points 300 a tour delay possible point where it is expected that there will be no problems even if supplies are not replenished in the preceding cycle preceding the time overrun cycle described below, based on the inventory forecast of materials for each point 300.

The target time memory unit 104 stores the target time for each cycle of the tour from the first to the final one. In this embodiment, the target time memory unit 104 is embodied by the work schedule management table 620 and the work time adjustment table 630. In other words, the target time for each cycle is the sum of the planned work time stored in the work schedule management table 620 and the adjustment time stored in the work time adjustment table 630. For example, if the planned work time is 8 hours and the adjustment time is +1.0 hour, the target time is 9 hours.

The location classification unit 105 classifies the multiple locations 300 in the area 900 for each patrol cycle based on the inventory forecast of materials for each location 300 into required patrol locations that must be selected as patrol locations and optional patrol locations that do not necessarily have to be selected as patrol locations.

In this embodiment, the location classification unit 105 classifies the multiple locations 300 in the area 900 into locations that must be visited, locations that are optional for visiting, and locations that do not need to be visited and are not selected as locations for visiting.

For example, the location classification unit 105 classifies a location 300 where the remaining amount of kerosene is 20% or less of the tank capacity as a required patrol location, classifies a location 300 where the remaining amount of kerosene is 60% or more of the tank capacity as a non-required patrol location, and classifies a location that is neither a required patrol location nor a non-required patrol location as an optional patrol location.

The area division unit 106 divides an area 900 including a plurality of points 300 into a plurality of small areas 910. For example, the area division unit 106 classifies the plurality of points 300 scattered throughout the area 900 into a plurality of groups that are regionally cohesive, using a clustering method such as the k-means method, based on the location information of these points 300 stored in the visited point management table 600 and the number of workers patrolling that day, and divides the area 900 so that the points 300 in each group are included in each small area 910. Clustering methods such as the k-means method are well-known techniques, so a description thereof will be omitted. FIG. 17 shows the area 900 divided by the area division unit 106 into three small areas 910.

The circular route generating unit 102 generates a circular route for the target cycle (the first day in this embodiment). However, the circular route generating unit 102 does not simply generate a circular route for that cycle, but also generates circular routes for the subsequent cycles, adjusts the work time for each cycle to be shortened and leveled, and then generates a circular route for the target cycle. In this embodiment, the circular route generating unit 102 generates a circular route for each cycle from the first day to the seventh day in order, adjusts the work time to be shortened while leveling it out, and then generates a circular route from the first to the final cycle again. The circular route generating unit 102 repeats this process a predetermined number of times (five times in this embodiment) and then generates a circular route for the first day.

The number of cycles (7 cycles) and the predetermined number of times (5 times) can be set and changed through an interface such as the input device 150, the recording medium reading device 170, the communication device 130, or an API (Application Programming Interface).

The tour route generation unit 102 generates the tour route for each cycle by using a predetermined route search algorithm. The route search algorithm may be a hill climbing method, a simulated annealing method, a genetic algorithm, a tabu search, or the like. In this embodiment, the hill climbing method or the simulated annealing method is used.

When generating a circular route, the circular route generation unit 102 generates multiple candidates (candidate routes) that can become circular routes, and selects the best candidate from these candidates as the circular route.

When generating candidates, the tour route generation unit 102 generates candidate routes that include all required tour points on the route and do not include any unnecessary tour points.

Specifically, the tour route generation unit 102 first generates candidate routes (first candidates) for the tour route by arranging all points 300, excluding points that do not need to be toured, in a predetermined order (e.g., random order).

Of course, the first candidate does not have to include all of the optional tour points. In this case, the tour route generation unit 102 selects multiple points 300 from the points 300 excluding the points not required to be toured so as to include at least all of the required tour points (it is sufficient that there are zero or more optional tour points. The optional tour points are selected, for example, randomly), and then generates the first candidate for the tour route by arranging these points 300 in a predetermined order (for example, randomly).

Then, the circular route generation unit 102 randomly selects one of the following first, second, or third processes and repeatedly executes them to sequentially generate multiple candidate routes.

The first process generates a second candidate by switching the order of two locations 300 selected (e.g., randomly selected) from the locations 300 included in the first candidate.

The second process generates a second candidate by deleting a point 300 selected (e.g., randomly selected) from the arbitrary tour points included in the first candidate from the tour route of the first candidate.

The third process generates a second candidate by incorporating a point 300 selected (e.g., randomly selected) from any patrol points not included in the first candidate into the patrol route of the first candidate.

At this time, the tour route generating unit 102 adds the new point 300 to the route so that the increase in route length due to adding this point 300 to the route is minimized. For example, if the first candidate is "base → A → C → D → E → base" and "B" is added to this route to generate the second candidate, it can be inserted at any position before or after A, C, D, or E, but it is inserted at a position where the sum of the distances "(distance from base to B) + (distance from B to A)", "(distance from A to B) + (distance from B to C)", "(distance from C to B) + (distance from B to D)", "(distance from D to B) + (distance from B to E)", or "(distance from E to B) + (distance from B to base)" is minimized.

Then, the circular route generation unit 102 randomly selects one of the first to third processes again, using the second candidate generated in each of the above processes as the first candidate, and repeatedly executes the process of generating a new second candidate.

This aspect makes it possible to generate candidate routes with a variety of numbers of points 300 to visit, so as to exclude points that do not need to be visited and to always include points that must be visited.

For each of these candidate routes, the tour route generation unit 102 calculates a first index value indicating the degree to which a point with a higher degree of necessity (score) for patrolling is selected as a tour point, a second index value indicating the route length of the tour route that patrols the tour points, and a third index value indicating the difference between the time required for the tour of the tour route and a predetermined target time, and generates a tour route by selecting tour points from the multiple points 300 based on the first index value, second index value, and third index value.

Specifically, the circular route generation unit 102 calculates the cost shown in the following formula (1) for each candidate route, and selects the candidate route with the smallest cost value as the circular route.

Cost = a × first index value + b × second index value + c × third index value (a is a negative weighting coefficient, b is a positive weighting coefficient, and c is a positive weighting coefficient) ... (1)
Here, the first index value is calculated by the following formula (2).

First index value = score at each point along the Σ route … (2)
Since the first index value is a value obtained by adding up the scores of the points 300 in the candidate route, the larger the first index value, the smaller the product with the negative weight coefficient a, and the more likely the route is to be selected as a tour route. In other words, the more points 300 with higher scores are included in a candidate route, the more likely the route is to be selected as a tour route.

For example, when determining a tour route for the first day, if one candidate route visits points A, B, and C, the tour route generation unit 102 refers to the necessity management table 610, reads out the scores for the first day for each of points A, B, and C, and calculates the first index value by summing up these scores.

For example, when determining a tour route for the second day, the tour route generation unit 102 refers to the necessity management table 610, and depending on whether or not a point in the route candidate is included in the tour route for the first day (whether or not it has already been visited on the first day), reads out the corresponding score for the second day for each point, and calculates the first index value by summing up these scores.

Next, the travel route generation unit 102 calculates the second index value using the following formula (3).

Second index value = Σ distance between two adjacent points on the route ... (3)
The second index value indicates the route length (total travel distance) of the candidate route. The distance between two points 300 can be calculated from the location information of each point 300 stored in the visited point management table 600. Alternatively, map data (not shown) may be used to calculate the distance along the road between each point 300. The larger the second index value, the higher the cost, and therefore the less likely the point is to be selected as a tour point.

The second index value may be the route length of the candidate route itself, or may be any other value related to the route length. For example, the value related to the route length may be the patrol time required to patrol the candidate route by converting the travel distance into travel time using the worker's travel speed. In this case, the worker's travel speed may be calculated using, for example, the route length of the patrol route taken when patrolling point 300 in the past and the time required for the worker to patrol that patrol route, or a predetermined fixed value equivalent to the travel speed may be used.

Next, the travel route generation unit 102 calculates the third index value using the following formula (4A) or formula (4B).

Third index value = (required time for round trip - target time) x number of optional round trip points included in the candidate route
(When the required time for the tour is greater than the target time) ... (Formula 4A)
Third index value = (target time - required time for tour) x number of optional tour points not included in the candidate route
(When the required tour time is less than or equal to the target time) ... (Formula 4B)
Note that (Equation 4A) is a calculation formula for the third index value used when the patrol time is greater than the target time, and is a calculation formula for when a worker has to work overtime, for example, when the target time is set so that the worker returns to the base at the end of his/her shift.

Furthermore, (Formula 4B) is the calculation formula for the third index value used when the required tour time is less than or equal to the target time.

When calculating the third index value, the tour route generation unit 102 simulates the time it takes for a worker to visit each location 300 and return.

This patrol time can be calculated by multiplying the travel time between adjacent points 300, calculated using the distance between the adjacent points 300 and the worker's movement speed, and the work time at each point 300 for each candidate route, by the work efficiency recorded in the work schedule management table 620. The worker's movement speed and work time may be set to predetermined values obtained from past experience, for example.

To elaborate on the third index value, for example, if an optional patrol point is visited even though overtime would occur, the time required for the patrol should be shortened by not visiting this optional patrol point, so this is added to the cost as a penalty due to the third index value. The magnitude of the impact on the cost is adjusted using coefficient c. As a result, when overtime occurs, candidate routes with fewer optional patrol points are recognized as better routes and are more likely to remain.

Conversely, if the patrol work is completed earlier than the target time but there are still unpatrolled optional patrol points remaining, the work time should be increased by patrolling these optional patrol points, so a penalty proportional to the number of unpatrolled optional patrol points is added to the cost.

However, the third index value may also be calculated using the following formula (5A) and formula (5B).

Third index value = tour time required - target time (if tour time required > target time)... (5A)
Third index value = target time - tour time (if tour time ≦ target time)... (5B)
Even with these formulas, if the time required for the tour deviates from the target time, the third index value increases in proportion to the time difference, which increases the cost of formula (1).

Alternatively, when the patrol time is less than or equal to the target time, instead of using formula (4B) or formula (5B), the third index value may be set to a predetermined value (for example, a fixed value such as 0 or 1). In this case, even if a candidate route completes the patrol in a shorter time than the target time, the cost of formula (1) is hardly increased, so a route that completes the patrol early is more likely to be selected, thereby reducing the workload of workers. Alternatively, when the target time is too long despite the number of points to be patrolled being small, it is possible to prevent the generation of a patrol route that takes an unreasonably long detour in order to bring the patrol time closer to the target time.

In this way, the tour route generation unit 102 executes a tour route generation process that generates tour routes for each cycle of the tour from the first day to the seventh day in sequence.

Then, the route generation unit 102 makes adjustments so that the work time in each of these cycles is equalized and shortened.

In other words, the routes for each cycle generated by the above route generation process are all generated taking into account the third index value, so in principle the time required for the tour will be close to the target time. However, if the number of required tour points suddenly increases due to kerosene running low, the time required for the tour may significantly exceed the target time, even if the optional tour points are excluded from the route and the route is composed of only required tour points while taking into account the third index value.

In such a case, the route generation unit 102 performs the processes shown in a) to d) below to adjust the route points that make up the route so that the travel time for each route is averaged and shortened.

a) Adjustment for positive score bias (correction of the score by adding a correction value)
b) Adjustment for negative score bias (correction of the score by subtracting a correction value)
c) Adjustment by increasing the target time d) Adjustment by decreasing the target time Of these, a) and b) adjust the patrol points by correcting the score, and when a patrol route is generated in any cycle in which the time required for patrol exceeds the specified target time by a first specified time or more (for example, 30 minutes or more), the patrol route generation unit 102 corrects the score stored in the necessity management table 610 so that the specified point selected as a patrol point in the time exceeding cycle in question is less likely to be selected as a patrol point in the time exceeding cycle in question.

Specifically, when there is a cycle (e.g., the fifth day) in which the required tour time exceeds the target time by 30 minutes or more, the tour route generation unit 102 corrects the score stored in the necessity management table 610 so that the above-mentioned specified point 300 (e.g., point A) included in the tour route on the fifth day is less likely to be selected as a tour point on the fifth day. By correcting the score in this way, if point A can be prevented from being included as a tour point in the tour route on the fifth day generated in the next tour route generation process, the number of tour points will decrease, and the tour time on the fifth day can be shortened. As a result, the tour time for each cycle can be averaged out.

a) Adjustment using positive score bias In this case, the tour route generation unit 102 corrects the necessity (score) of the mandatory tour location (location A) visited on the day when overtime occurs (the fifth day) with the aim of having this location visited in an earlier cycle.

Specifically, the tour route generation unit 102 corrects the necessity of the above-mentioned specified point (point A) in the preceding cycle (before the fourth day) that precedes the time exceeding cycle (the fifth day) by increasing it by a first specified value (positive score bias), making this specified point more likely to be selected as a tour point in the preceding cycle, and therefore making this specified point less likely to be selected as a tour point in the time exceeding cycle (the fifth day).

For example, the route generating unit 102 may take the maximum value among the degrees of necessity of the multiple locations 300 in the previous cycle as a first predetermined value (positive score bias) and add this first predetermined value to the degree of necessity of the specified location in the previous cycle, thereby correcting the degree of necessity of the specified location to be increased.

With reference to FIG. 15, if the third day cycle is a time exceeding cycle, in order to make it easier for points 2 and 5 (the patrol points are shaded in FIG. 15) selected as patrol points in this time exceeding cycle to be selected as patrol points in the preceding cycle (second day cycle), the score 2 of point 2 in the second day cycle is updated to 7 by adding 5 (first predetermined value), and the score 4 of point 5 is also updated to 9 by adding 5 (first predetermined value). Note that the increment in score at this time, 5 (first predetermined value), is the maximum score of each point in the second day cycle (point 3's score 5). The first predetermined value can be obtained by referring to the necessity management table 610. In this manner, it is possible to make it easier for patrol points in the time exceeding cycle to be selected as patrol points in the preceding cycle, and as a result, it is possible to make it harder for them to be selected as patrol points in the time exceeding cycle. In the example shown in FIG. 15, the score (necessity) of location 5 in the second day cycle increases (from 4 to 9), allowing location 5 to be selected as a patrol location in the second day cycle.

Furthermore, to make points 2 and 5 selected as patrol points in the time exceeding cycle more likely to be selected as patrol points in the preceding cycle (first day cycle), the score 1 of point 2 in the first day cycle may be updated to 8 by adding 7 (first predetermined value), and the score 2 of point 5 may also be updated to 9 by adding 7 (first predetermined value). The score increment of 7 (first predetermined value) in this case is the maximum score of each point in the first day cycle (point 1's score of 10) multiplied by a coefficient of 0.67. This type of embodiment also makes it possible to make patrol points in the time exceeding cycle more likely to be selected as patrol points in the preceding cycle and less likely to be selected as patrol points in the time exceeding cycle.

In the second day cycle, the highest score in that cycle is set as the first predetermined value, and in the first day cycle, the highest score in that cycle multiplied by a coefficient of 0.67 is set as the first predetermined value, so that the degree of increase in score increases the closer the preceding cycle is to the time-exceeded cycle. With this configuration, it is possible to induce a specified point that is not to be patrolled in the time-exceeded cycle to be selected as a patrol point in a preceding cycle that is closer to the time-exceeded cycle. This makes it possible to delay the timing of replenishment of kerosene to that specified point, increase the amount of kerosene replenished, and improve the work efficiency of kerosene replenishment.

The first predetermined value may be a fixed value that is appropriately determined. This simplifies the score update process and reduces the processing load on the travel route generation device 100.

b) Adjustment using negative score bias In this case, the circular route generation unit 102 reduces the necessity in the preceding cycle of the circular delay possible point (a point where it is expected that there will be no problem if kerosene is not replenished in the preceding cycle) selected by the circular delay possible point selection unit 103 by a second predetermined value (negative score bias), making this circular delay possible point less likely to be selected as a circular point in the preceding cycle, and making the specified point (point A mentioned above) relatively more likely to be selected as a circular point in the preceding cycle, making this specified point less likely to be selected as a circular point in the time exceeding cycle.

Explaining with reference to FIG. 16, if the second day cycle is a time-overrun cycle (the patrol points are shaded in FIG. 16), the preceding cycle becomes the first day cycle. The patrol delay possible point selection unit 103 also recognizes points 3 and 4 as possible patrol points in the preceding cycle (first day cycle) because there is no need to visit points 3 and 4 before the second day cycle when overtime occurs (because patrol is not mandatory) and they can be visited after the time-overrun is resolved. In this case, the patrol route generation unit 102 subtracts 3.5 (second predetermined value) from the score of point 3 in the first day cycle (7) (multiplying the score by 1/2) to update it to 3.5, and subtracts 1 (second predetermined value) from the score of point 4 in the first day cycle (multiplying the score by 1/2) to update it to 1. Note that the score reduction at this time is a value that is 1/2 of the score in the first day cycle.

As a result, point 3, which was originally selected as a patrol point in the preceding cycle (first day cycle), is no longer selected as a patrol point along with point 4. Instead, point 5, which was selected as a patrol point in the time-exceeding cycle (second day cycle), became relatively more necessary in the preceding cycle (first day cycle) and was selected as a patrol point for the preceding cycle. As a result, the number of patrol points in the time-exceeding cycle was reduced from three (points 2, 5, and 6) to two (points 2 and 6).

By using this method, it becomes difficult for a point in the preceding cycle where a tour delay is possible to be selected as a tour point, and it becomes relatively easy for a specific point to be selected as a tour point in the preceding cycle, so that it becomes difficult for this specific point to be selected as a tour point in the time-exceeding cycle.

c) Adjustment by increasing the target time Furthermore, when the number of points whose necessity can be corrected so that the above-mentioned specified points are less likely to be selected as patrol points in the time exceeding cycle is less than a specified number (for example, less than a number equivalent to 30%), and the excess working time cannot be absorbed (leveling out is difficult), the patrol route generation unit 102 may increase, by the first target time, each of the target times for patrol in a specified number of consecutive cycles including the time exceeding cycle, which are stored in the target time memory unit 104 described later.

Note that adjustments due to an increase in the target time are made when, in the previous adjustment, the adjustments a) and b) above were performed to correct the degree of necessity for each route from the first cycle to the final cycle, but the current adjustment is unable to correct the degree of necessity any further.

This is because when the number of points where the degree of necessity can be adjusted falls below a certain number, there is little room left to level out work hours by adjusting the degree of necessity, so the system aims to level out work hours by increasing the target time over multiple cycles (i.e., by increasing overtime).

For example, if the target time for the overtime cycle is 9 hours and the required tour time is 10 hours, the tour route generation unit 102 increases the target time for the overtime cycle and the preceding cycle by 0.5 hours each. This type of configuration also makes it possible to level out work hours.

As described above, the target time is the sum of the planned work time stored in the work schedule management table 620 and the adjusted time stored in the work time adjustment table 630. For example, if the planned work time is 8 hours and the adjusted time is +1.0 hour, the target time is 9 hours. The first target time is, for example, the difference between the patrol time and the target time divided by the above-mentioned specified number (the number of cycles for which the target time is to be corrected). In other words, as described above, if the target time for the time-overrun cycle is 9 hours and the patrol time is 10 hours, the target times for the time-overrun cycle and the preceding cycle one cycle before that are each increased by 0.5 hours.

If there are multiple workers, the first target time is calculated by adding up the difference between the patrol time and the target time for all workers, divided by the total number of workers in each cycle for which the target time is being corrected. For example, in the example shown in Figure 20, if the total difference between the patrol time and the target time is 10 hours, the total number of workers in the three cycles of the first day cycle, the second day cycle, and the third day cycle is 5, so the first target time is 2 hours (10 hours ÷ 5 people).

d) Adjustment by reducing the target time Furthermore, when a circular route is generated in any cycle such that the time required for the tour exceeds the target time by a second predetermined time (e.g., 10 minutes) or less that is shorter than a first predetermined time (e.g., 30 minutes), and the proportion of required tour points and optional tour points for which the degree of necessity has already been corrected among the tour points in the light-load cycle in question is a third predetermined value or less (e.g., 30% or less), i.e., when there is some leeway in the time required for the tour, the circular route generation unit 102 may reduce the target time for the tour in that light-load cycle, which is stored in the target time memory unit 104 described below, by the second target time (e.g., 20 minutes), and then perform the circular route generation process again.

This approach makes it possible to reduce the time required for a tour.

The ratio of required tour points and optional tour points whose necessity has already been corrected among the tour points included in one tour route is called the non-adjustable rate. The non-adjustable rate is expressed by the following formula (6).

Unadjustable rate = (number of required patrol points + number of optional patrol points after score correction) / (number of points on the patrol route) ... (6)
The rate of non-adjustment is an index value that represents the nature of the tour route. For example, if all the points on the tour route are required tour points, the rate of non-adjustment is 1, and the scores of the points on this tour route cannot be corrected to guide them to tour in another cycle. Conversely, if all the points on the tour route are optional tour points, and the scores of all the points have not yet been corrected, the rate of non-adjustment is 0, and the scores of all the points on this tour route can be corrected to guide them to tour in another cycle.

When the rate of adjustment failure of the light load cycle is 30% or less (a third predetermined value or less), the tour route generation unit 102 reduces the target time of this light load cycle, thereby reducing the number of tour points on the tour route. In this manner, it is possible to shorten the time required for the tour.

As described above, the tour route generation unit 102 executes an adjustment process to adjust the scores and target times for the tour routes generated by the tour route generation process from the first cycle (first day) to the final cycle (seventh day), and then executes the tour route generation process again to regenerate the tour routes for each cycle from the first to the final cycle.

The route generation unit 102 repeats this route generation process and adjustment process a predetermined number of times (five times in this embodiment).

Then, the tour route generation unit 102 again calculates the first index value, the second index value, and the third index value for the first cycle of the tour, and generates a tour route by selecting tour points from the multiple points 300 based on the first index value, the second index value, and the third index value. An example of a tour route generated in this way is shown in FIG. 11.

This approach makes it possible to generate optimal patrol routes that shorten and standardize the work time of workers performing the patrol, not only for the immediate future but also for a certain period of time thereafter.

==Process flow==
Next, the flow of processing by the route generation device 100 according to this embodiment will be described with reference to the flowcharts shown in FIGS.

In FIG. 12, the route generating device 100 obtains the results of the kerosene inventory forecast for each cycle from the first day to the seventh day at each point 300 in the area 900 (S1000). As described above, the kerosene inventory forecast is executed by the inventory forecasting unit 107 or another computer (not shown). This inventory forecast also includes predictions for all cases in which kerosene replenishment at each point 300 is performed and is not performed in each cycle from the first day to the seventh day.

Then, the route generation device 100 calculates the status, fuel supply amount, and score of each point 300 based on the inventory forecast for each point 300, and creates a necessity management table 610 (S1010).

The traveling route generating device 100 initializes variables i and j to 1 (S1020, S1030), and then generates a traveling route for the jth day (jth cycle) (S1040). That is, the traveling route generating device 100 calculates a first index value representing the degree to which a point with a higher degree of necessity for visiting is selected as a traveling point from among the multiple points 300 for the jth cycle of visiting, a second index value representing the path length of the traveling route visiting the traveling points, and a third index value representing the difference between the time required for visiting the traveling route and a predetermined target time, and generates a traveling route by selecting a traveling point from the multiple points 300 based on the first index value, the second index value, and the third index value. The traveling route is generated by a hill climbing method or a simulated annealing method, and details will be described later with reference to FIG. 13 and FIG. 14.

Then, the traveling route generating device 100 determines whether j=7 (7th day) (S1050), and if No, adds 1 to j (S1060), and generates a traveling route for the jth day (S1040). In this way, the traveling route generating device 100 executes a traveling route generation process that generates traveling routes from the first to the final time.

On the other hand, when j=7, the tour route generation device 100 compares each tour route from the first day to the seventh day, and adjusts the score in the necessity management table 610 or the adjustment time in the work time adjustment table 630 in order to shorten and level out the tour work time for each day (S1070).

Specifically, the route generation device 100 adjusts the score or adjustment time by evaluating the overtime hours for each day (i.e., the time required for the tour minus the target time) as follows:

When the overtime hours are equal to or less than a second predetermined time (e.g., 10 minutes or less) and the rate of unadjustable hours on the route is equal to or less than a third predetermined value (e.g., 30% or less), the route generation device 100 shortens the target time for that day by the second target time (e.g., 20 minutes). Specifically, the adjustment time in the work time adjustment table 630 is reduced by the second target time.

Furthermore, the route generation device 100 does not make any adjustments if the overtime hours exceed the second predetermined time (e.g., 10 minutes) and are less than the first predetermined time (e.g., 30 minutes).

In addition, when the overtime is equal to or longer than a first predetermined time (e.g., 30 minutes), the route generating device 100 first clears to 0 any negative adjustment time recorded in the work time adjustment table 630 by the previous day. The route generating device 100 also corrects the score of the previous day of the essential points (predetermined points) on the route so as to increase it by a first predetermined value. Furthermore, the route generating device 100 corrects the score of the points on the previous day where the route can be delayed by a second predetermined value. However, if the number of points where the score can be increased or decreased is equal to or less than a predetermined number (e.g., 30% or less), the route generating device 100 distributes the overtime to each day before the current day. In other words, the route generating device 100 increases the adjustment time recorded in the work time adjustment table 630 for the current day and each day before by the time (first target time) divided by the number of days to distribute the overtime (note that, as described above, this process is executed only when i is 2 or more).

Then, the traveling route generating device 100 determines whether i=5 (fifth time) (S1080), and if No, adds 1 to i (S1090) and returns to S1030. In this way, the traveling route generating device 100 repeats the traveling route generation process a predetermined number of times (five times).

On the other hand, when i=5, the tour route generation device 100 generates a tour route for the first day's tour cycle again using the hill climbing method or the simulated annealing method, as in S1040 (S1100).

This approach makes it possible to generate optimal patrol routes that shorten and standardize the work time of patrolling workers, not just on the first day but for a certain period of time thereafter.

Next, with reference to FIG. 13, we will explain the flow of the process for generating a circular route using the hill-climbing method (hereinafter referred to as route search process S1200).

First, the traveling route generation device 100 classifies each point 300 to be patrolled into a required point, an optional point, and a point not required to be patrolled. The traveling route generation device 100 then generates an initial value for the current route (S1211). As an example in this embodiment, the traveling route generation device 100 generates the initial value for the current route by including all points 300 (all required points and all optional points) except for the points not required to be patrolled in the route, and setting the order randomly. The traveling route generation device 100 also records this current route as current route information and sets it as a tentative solution for the traveling route.

Next, the travel route generation device 100 calculates the third index value from the first index value for the current route (S1212), and determines the cost of the current route from these calculation results (S1213).

Then, the traveling route generating device 100 generates a next route based on the current route (S1214). At this time, the traveling route generating device 100 generates the next route by randomly selecting and executing one of the first process, the second process, or the third process described above. The traveling route generating device 100 also records this next route as next route information.

Next, the travel route generation device 100 calculates the third index value from the first index value for the next route (S1215), and determines the cost of the next route from these calculation results (S1216).

Then, the traveling route generation device 100 determines whether the cost of the next route is less than the cost of the current route (S1217). If the cost of the next route is less than the cost of the current route (S1217: YES), the traveling route generation device 100 resets the next route as a tentative solution (S1218). Then, the process proceeds to S1219. On the other hand, if the cost of the next route is not less than the cost of the current route (S1217: NO), the process proceeds to S1219.

In S1219, the traveling route generation device 100 determines whether the cost of the tentative solution is equal to or less than a preset threshold. If the cost of the tentative solution is equal to or less than the preset threshold (S1219: YES), the traveling route generation device 100 executes S1220. If the cost of the tentative solution is not equal to or less than the preset threshold (S1219: NO), the traveling route generation device 100 sets the next route as the current route, transcribes the next route information into the current route information, and then returns to S1214 to continue processing.

In S1220, the traveling route generation device 100 stores the tentative solution as a route search result. The traveling route generation device 100 outputs the route search result to the output device 160 as appropriate.

Figure 14 is a flowchart explaining the process (hereinafter referred to as route search process S1300) performed by the travel route generation device 100 when searching for a travel route using the simulated annealing method. The route search process S1300 will be explained below with reference to Figure 14.

First, the travel route generation device 100 sets an initial value for temperature T (S1311).

Then, the traveling route generation device 100 classifies each point 300 to be visited into a required point, an optional point, and a point not required to be visited. The traveling route generation device 100 then generates an initial value for the current route (S1312). At this time, as an example, the traveling route generation device 100 generates the initial value for the current route by including all points 300 (all required points and all optional points) except for the points not required to be visited in the route, and setting the order randomly. The traveling route generation device 100 also records this current route as current route information, and sets it as a tentative solution for the traveling route.

The travel route generation device 100 calculates the first index value to the third index value for the current route (S1313), and finds the cost of the current route based on these calculation results (S1314).

Then, the traveling route generating device 100 generates a next route based on the current route (S1315). At this time, the traveling route generating device 100 randomly selects and executes one of the first process, the second process, or the third process described above to generate the next route. The traveling route generating device 100 also records this next route as next route information.

Next, the travel route generation device 100 calculates the first index value to the third index value for the next route (S1316), and finds the cost of the next route based on these calculation results (S1317).

Then, the traveling route generating device 100 judges whether or not to accept the next route (S1318). In the above judgment, the traveling route generating device 100 accepts the next route if the cost of the next route is smaller than the cost of the current route in principle, but even if the cost of the next route is not smaller than the cost of the current route (i.e., even if it is a deterioration), the next route is accepted with a probability that depends on the temperature T. Note that, for example, the Metropolis criterion is used as the above probability. In this way, it is possible to make it difficult to fall into a local optimum solution. If the traveling route generating device 100 judges that the next route is accepted (S1318: Accept), it resets the next route as a tentative solution (S1319) and proceeds to the process of S1320. On the other hand, if it is judged that the next route is not accepted (S1318: Not Accepted), the traveling route generating device 100 proceeds to the process of S1320.

In S1320, the traveling route generation device 100 determines whether or not to lower the temperature T. For example, the traveling route generation device 100 determines to lower the temperature T when the loop process of S1315 to S1320 has been repeated a preset number of times or more. Note that by increasing the number of repetitions, it is possible to improve the possibility of obtaining a true optimal solution for the traveling route. Conversely, by decreasing the number of repetitions, it is possible to shorten the time required for the traveling route generation process.

Therefore, for example, when generating a circular route in S1040 of FIG. 12, the number of repetitions can be reduced to shorten the processing time, and when generating a circular route in S1100 of FIG. 12, the number of repetitions can be increased to generate a more optimal circular route.

When the traveling route generation device 100 determines that the temperature T should be lowered (S1320: YES), the traveling route generation device 100 lowers the temperature T (S1321) and proceeds to the process of S1322. For example, in the case of exponential annealing, the traveling route generation device 100 sets T _t+1 = γ·T _t (where γ is a coefficient that determines the cooling rate). On the other hand, when the traveling route generation device 100 determines that the temperature T should not be lowered (S1320: NO), the traveling route generation device 100 sets the next route as the current route, transcribes the next route information into the current route information, and returns to S1315 to continue the process.

In S1322, the traveling route generation device 100 determines whether the cost of the tentative solution is equal to or less than a preset threshold. If the cost of the tentative solution is equal to or less than the preset threshold (S1322: YES), the traveling route generation device 100 executes S1323. If the cost of the tentative solution is not equal to or less than the preset threshold (S1322: NO), the traveling route generation device 100 sets the next route as the current route, transcribes the next route information into the current route information, and then returns to S1315 to continue processing.

In S1323, the traveling route generation device 100 stores the tentative solution as a route search result. The traveling route generation device 100 outputs the route search result to the output device 160 as appropriate.

==Other embodiments==
Next, a case will be described in which an area 900 is divided into a plurality of small areas 910 and different workers patrol each of the small areas 910.

Figure 17 shows an example of an area 900 divided into three small areas 910. Figure 9 shows the area management table 640 in this case.

Figure 18 shows a work schedule management table 620 that records the work schedules of multiple workers. As shown in Figure 18, the number of workers delivering kerosene varies from day to day. Therefore, the route generation device 100 divides the area 900 into small areas 910 according to the number of workers available to work on that day.

The area 900 is divided by the area division unit 106. The area division unit 106 classifies the points 300 scattered throughout the area 900 into multiple groups that are regionally cohesive, using a clustering method such as the k-means method based on the location information of the points 300 stored in the visited point management table 600 and the number of workers on that day, and divides the area 900 so that the points 300 in each group are included in each small area 910. Clustering methods such as the k-means method are well-known techniques, so a description thereof will be omitted.

Then, the travel route generation device 100 generates a travel route for each cycle from the first (e.g., the first day) to the final (e.g., the seventh day) for each small area 910.

Figure 19 shows a flowchart illustrating the process flow when the travel route generation device 100 generates travel routes for multiple small areas 910.

First, the travel route generation device 100 initializes a variable k to 1 (S2000), and then determines the small area 910 for the kth day (kth cycle) (S2010). In other words, the travel route generation device 100 divides the area 900 into the number of small areas 910 according to the number of workers on that day.

Then, the traveling route generation device 100 determines whether k=7 (seventh time) (S2020), and if No, adds 1 to k (S2030) and returns to S2010. In this way, the traveling route generation device 100 divides the area 900 into small areas 910 for each cycle from the first to the final cycle.

On the other hand, when k=7, the travel route generation device 100 starts the process of generating a travel route shown in FIG. 12. Note that this process of generating a travel route is performed for each small area 910.

In this way, the route generation device 100 can generate an optimal route so that the work time of each worker is shortened and equalized, even when there are multiple workers. An example of a route generated in this way is shown in Figure 17.

As described above, according to the route generation device 100 and route generation method and program of this embodiment, by performing multiple cycles of visiting at least some of the locations 300 selected from the multiple locations 300 while changing the combination of locations, it is possible to generate a route for generating a route for resupplying the multiple locations 300 that can both reduce and level the work time of workers performing the route.

The above-described embodiment is intended to facilitate understanding of the present invention, and is not intended to limit the present invention. The present invention may be modified or improved without departing from its spirit, and equivalents are also included in the present invention.

For example, the supplies that workers deliver to each point 300 are not limited to kerosene, but may be various materials and products consumed by machines, factories, stores, and vending machines, or even water consumed in agricultural water tanks. When generating a route for agricultural water tanks, the route generation device 100 may, for example, collect the amount of remaining water from each agricultural water tank.

REFERENCE SIGNS LIST 100 Tour route generation device 101 Necessity level storage unit 102 Tour route generation unit 103 Tour delay possible point selection unit 104 Target time storage unit 105 Point classification unit 106 Area division unit 110 CPU
120 Memory 130 Communication device 140 Storage device 150 Input device 160 Output device 170 Recording medium reader 300 Location 500 Network 600 Visiting location management table 610 Necessity management table 620 Work schedule management table 630 Work time adjustment table 640 Area management table 700 Tour route generation device control program 800 Recording medium 900 Area 910 Small area

Claims (15)

A route generating device that generates a route for resupplying a plurality of points by performing a plurality of cycles of visiting at least some of the points selected from the plurality of points while changing a combination of the points,
a necessity storage unit that stores a necessity of visiting each point in each cycle of the tour from the first to the final tour, the necessity being calculated based on the inventory forecast of the material for each point;
a circular route generating unit that performs a circular route generation process that calculates, for each circular cycle, a first index value that indicates the degree to which a location having a higher degree of necessity for visiting is selected as a circular route from among the plurality of locations, a second index value that indicates a route length of a circular route that visits the circular locations, and a third index value that indicates a difference between a required time for visiting the circular route and a predetermined target time, and that selects a circular route from the plurality of locations based on the first index value, the second index value, and the third index value to generate a circular route;
Equipped with
The tour route generation unit,
When a circular route is generated in any cycle in which the time required for the tour exceeds a predetermined target time by a first predetermined time or more, the circular route generation device corrects the degree of necessity stored in the necessity memory unit so that the predetermined point selected as a tour point in the time exceeding cycle is less likely to be selected as a tour point in the time exceeding cycle, and then performs the circular route generation process again. The travel route generation device according to claim 1,
The tour route generation unit,
A tour route generation device that corrects the necessity of the specified point in a preceding cycle preceding the time exceeding cycle by increasing it by a first specified value, making the specified point more likely to be selected as a tour point in the preceding cycle, thereby making the specified point less likely to be selected as a tour point in the time exceeding cycle. The travel route generation device according to claim 2,
The tour route generation unit,
a first predetermined value being a maximum value among the degrees of necessity of the plurality of points in the previous cycle, and the first predetermined value being added to the degree of necessity of the specified point in the previous cycle, thereby correcting the degree of necessity of the specified point. The route generation device according to any one of claims 1 to 3,
a tour delay possible point selection unit that selects, from the plurality of points, a tour delay possible point at which it is expected that no problems will occur even if the supply of the material is not performed in a preceding cycle preceding the time overrun cycle, based on an inventory forecast of the material for each of the points;
Equipped with
The tour route generation unit,
A circular route generation device that corrects the necessity of the circular delay possible point in the preceding cycle to reduce it by a second predetermined value, making the circular delay possible point less likely to be selected as a circular point in the preceding cycle, and making the predetermined point relatively more likely to be selected as a circular point in the preceding cycle, making the predetermined point less likely to be selected as a circular point in the time exceeding cycle. The route generation device according to any one of claims 1 to 4,
A target time storage unit stores a target time for each cycle from the first to the final cycle,
The tour route generation unit,
When the number of points whose necessity can be corrected to make the specified point less likely to be selected as a patrol point in the time exceeding cycle is equal to or less than a specified number, the target times for patrol in a specified number of consecutive cycles including the time exceeding cycle, which are stored in the target time memory unit, are corrected so as to be increased by a first target time, and then the patrol route generation process is performed again. The route generation device according to any one of claims 1 to 5,
a target time storage unit that stores a target time for each cycle from the first to the final cycle;
a location classification unit that classifies the plurality of locations into required patrol locations that must be selected as patrol locations and optional patrol locations that do not necessarily have to be selected as patrol locations for each patrol cycle based on an inventory forecast of materials for each location;
Equipped with
The tour route generation unit,
When a circular route is generated in any cycle such that the time required for traveling exceeds the target time by a second predetermined time or less that is shorter than the first predetermined time, and the proportion of required traveling points and optional traveling points for which the degree of necessity has already been corrected among the traveling points in the light-load cycle that is the cycle is equal to or less than a third predetermined value, the circular route generation device reduces the target time for traveling in the light-load cycle that is stored in the target time memory unit by the second target time, and then performs the circular route generation process again. The route generation device according to any one of claims 1 to 6,
a region dividing unit for dividing a region including the plurality of points into a plurality of small regions;
Equipped with
The travel route generation unit generates, for each of the small regions, a travel route for visiting a plurality of points within the small regions in a plurality of cycles from a first cycle to a final cycle. The route generation device according to any one of claims 1 to 7,
The tour route generation unit,
a circular route generation device that, after repeating the circular route generation process a predetermined number of times, again calculates the first index value, the second index value, and the third index value for a first cycle of the tour, and selects a circular point from the multiple points based on the first index value, the second index value, and the third index value to generate a circular route. The route generation device according to claim 8,
a route generating device including an interface for acquiring information indicating the predetermined number of times that the route generating unit repeats the route generating process. The route generation device according to any one of claims 1 to 9,
A tour route generation device that includes an interface for acquiring information indicating a target time for each tour in each cycle from the first to the final cycle. The travel route generation device according to claim 10,
The information indicating the target time is work schedule information that describes the scheduled work start time and scheduled work end time of the worker who will be patrolling. The route generation device according to any one of claims 1 to 11,
The traveling route generating device includes an interface for acquiring information indicating the number of cycles of traveling from the first time to the final time for which the traveling route generating unit generates the traveling route. The route generation device according to any one of claims 1 to 12,
A route generation device having an interface for acquiring information indicating the degree of necessity of visiting each location in each cycle of the tour from the first to the final tour, the information being calculated based on a stock forecast of materials for each location. A route generation method by a computer for generating a route for resupplying a plurality of points by performing a plurality of cycles of visiting at least some of the points selected from the plurality of points while changing a combination of the points, the method comprising:
The computer,
storing the degree of necessity of patrol of each point in each cycle of patrol from the first to the final patrol, the degree being calculated based on the inventory forecast of the material for each point;
calculating, for each cycle of a tour, a first index value representing the likelihood that a point having a higher degree of necessity for visiting from among the plurality of points will be selected as a tour point, a second index value representing the length of a tour route that tours the tour points, and a third index value representing the difference between a required time for traveling on the tour route and a predetermined target time, and performing a tour route generation process that selects tour points from the plurality of points based on the first index value, the second index value, and the third index value to generate a tour route;
In the case where a circular route is generated in any cycle in which the time required for the tour exceeds a predetermined target time by a first predetermined time or more, the circular route generation method corrects the degree of necessity so that the predetermined point selected as a tour point in the time exceeding cycle is less likely to be selected as a tour point in the time exceeding cycle, and then performs the circular route generation process again. a computer that generates a route for resupplying a plurality of points by performing a plurality of cycles of visiting at least some of the points selected from the plurality of points while changing the combination of the points;
a step of storing a degree of necessity of patrol of each point in each cycle of patrol from the first to the final patrol, the degree being calculated based on the inventory forecast of the material for each point;
a step of calculating, for each cycle of a tour, a first index value representing the likelihood that a point having a higher degree of necessity for visiting from among the plurality of points will be selected as a tour point, a second index value representing the length of a tour route that tours the tour points, and a third index value representing the difference between a required time for travelling on the tour route and a predetermined target time, and performing a tour route generation process of selecting tour points from the plurality of points and generating a tour route based on the first index value, the second index value, and the third index value;
a step of performing the circular route generation process again after correcting the degree of necessity so that the predetermined point selected as a circular route in the time exceeding cycle is less likely to be selected as a circular route in the time exceeding cycle in question, when a circular route is generated in which the time required for the circular route exceeds a predetermined target time by a first predetermined time or more in any cycle;
A program for executing.

Images