JP4055987B2 - Route adjustment device - Google Patents

Description

[0001]
BACKGROUND OF THE INVENTION
The present invention relates to a route adjusting device, and more specifically, in a system in which a plurality of routes from a starting point to a plurality of points exist, the load (for example, distance, time, cost, operating rate, etc.) of each route is reduced. The present invention relates to a path adjustment device that adjusts a path by reducing a load.
[0002]
[Prior art]
There are many cases in which a plurality of places are visited by a plurality of moving bodies. For example, a courier company visits a plurality of points (specifically, companies, homes, etc.) that need to be delivered per day by a plurality of mobile bodies (specifically, trucks on which the person in charge has boarded). In other cases, the mail is delivered to a plurality of points (specifically, companies, homes, etc.) by a plurality of moving bodies (specifically, bicycles or motorcycles on which the person in charge has boarded).
When traveling around such multiple locations with multiple mobile units, it is of course possible to make the load (eg, distance, time, cost, availability, etc.) as small as possible. When it is preferable to make the load of the same as much as possible (for example, if there is a large difference in delivery time between the mobile bodies in the courier company, unfairness may occur between the mobile bodies). There are many.
[0003]
It is based on experience and intuition to date to determine a route that reduces the load or reduces the difference in load between each moving body when traveling around such multiple places with a plurality of moving bodies. Therefore, it has been performed by humans or by calculation using a computer.
[0004]
[Problems to be solved by the invention]
However, the method that a person performs based on experience and intuition is that the results obtained are greatly influenced by the experience and intuition of the person who performs it, and even if the same person has different dates and times, different results may be obtained. There was a problem of being obtained.
On the other hand, in a calculation using a computer, a method in which calculation is performed in all cases is not practical because it requires enormous calculation and a long time to be applied to an actual system.
[0005]
Therefore, in the present invention, there is provided an apparatus capable of practically determining a route that reduces a load when a plurality of places are circulated by a plurality of mobile bodies or reduces a load difference between the mobile bodies. The purpose is to provide.
[0006]
[Means for Solving the Problems]
(First device)
First, a first route adjustment apparatus (hereinafter referred to as “first main apparatus”) of the present invention will be described.
The first main apparatus includes a route data receiving unit that receives a plurality of route data including a start point and routes that go around a plurality of points, and a load among the plurality of route data that is received by the route data receiving unit. A start completion determination unit that determines a start route that is different from the lightest route, and a completion route that is a lighter load than the start route, and a plurality of route data received by the route data reception unit. Selecting a selection point that is a point included in one route and another route having a predetermined relationship with the selection point, and moving the selection point from the one route to the other route; At the first time, the starting route is selected as the one route, and from the next time onward, the other route before the previous time or the starting route as the one route, the affiliation changing means for repeating the selection and the movement, and the other No But and a completion determining means for determining whether or not to match with the complete path, the affiliation change means, and operates repeatedly until it is determined that the completion determination means matches a path adjusting device.
[0007]
By doing so, the route data accepting means accepts a plurality of route data including the starting point and the route around the plurality of points. Here, “route” refers to an order indicating the order of going around a plurality of points.
Then, the start completion determination unit has a start route that is a route different from the route with the lightest load among the plurality of route data received by the route data reception unit, and a completion route that has a lighter load than the start route. And decide. Here, “load” means the time required to travel around multiple points according to the route, the travel distance when traveling around multiple points according to the route, the cost required to travel around multiple points according to the route, etc. This refers to matters that should be borne when visiting multiple points according to the route. By doing in this way, the start completion determination means determines the start route and the completion route with a smaller load.
[0008]
The affiliation changing unit selects a selection point that is a point included in one route of the plurality of route data received by the route data reception unit, and another route having a predetermined relationship with the selection point, and Move the selected point from the route to the other route (refers to removing the selected point included in the one route from the one route and including it in the other route, ie, belonging to the one route) The selected point is removed from belonging to the one route and is assigned to the other route.) The start route is selected as the one route for the first time, and the next time and before The operation of the selection and the movement is repeated with the other route or the start route as the one route.
The completion determining means determines whether or not the other route matches the completion route. When the completion determining means determines that they match, the affiliation changing means repeats the operations of the selection and the movement. Stop (that is, the affiliation changing means repeats the operations of the selection and the movement until it is determined that the completion determination means match).
[0009]
In this way, in the first operation of the affiliation changing means (first time), a heavy starting route is set as the one route, and a selected point that is a point included in the starting route has a predetermined relationship with the selected point. Move to another route.
In the second operation of the affiliation changing means, the other route of the first time (first time) or the start route is set as the one route of the second time. A selection point that is a point included in the second route (that is, the other route or the start route of the first time (first time)) is moved to another route having a predetermined relationship with the selected point.
Hereinafter, such an operation (an operation of moving a selection point from one route to another route) is repeated until the other route matches the completed route, so that the number of points included in the heavy start route decreases. At the same time, the number of points included in the completed route with a light load increases, and the load difference between the routes can be reduced. For this reason, the first apparatus can determine a route that reduces the load difference between the moving bodies when the plurality of places are visited by the plurality of moving bodies.
Note that moving a selected point from one route to another route means that a selected point included in one route is excluded from one route and included in another route as described above. In other words, it means that a selected point belonging to one route is released from belonging to one route and belong to another route.
[0010]
In the first apparatus, the start route is a route having the heaviest load among the plurality of route data received by the route data receiving means, and the completion route has the highest load among the plurality of route data. A light path may be used.
This reduces the number of points included in the start route, which is the route with the heaviest load among multiple route data, and increases the number of points included in the completed route, which is the route with the lightest load. The load difference can be reduced.
[0011]
In the first apparatus, the affiliation changing means selects, as the selection point, a point having the highest degree of belonging to the completion route among points included in another route before the previous time or the start route. There may be.
Here, “degree of attribution” refers to the degree of membership in fuzzy clustering. Specifically, it is a number indicating the degree to which each point belongs to each group, with the points belonging to each route as each group. . The processing method of fuzzy clustering is a known technique, and is described in detail in, for example, Japanese Patent Laid-Open No. 05-274293 (the fuzzy c-means method, which is one of the methods of fuzzy clustering, including references). As a result, the degree of belonging to each cluster is calculated.) Therefore, the description is omitted here.
By doing so, the point belonging to the completion route among the points belonging to the other route before the previous time or the start route moves to the other route, so that the point existing in a suitable position can be moved. it can.
[0012]
In the first apparatus, the affiliation changing means uses, as the other route, a route indicating the highest degree of belonging among the degrees of belonging indicated by the selection point to another route before the previous time or a route other than the start route. You may choose.
In this way, the route showing the highest degree of belonging of the selected points to the other route before the previous time or the route other than the start route is selected as the other route, so the selected point is another route. (I.e., it shows a high degree of belonging to the fact that the selected point belongs to an unreasonable state because the route existing at a position far away from the selected point is set as another route) This can be prevented by setting the route as the other route.
[0013]
The first apparatus further includes route forming means for determining the order of the points belonging to the route in which the selected point is added / subtracted by the affiliation changing means and the change is included in the included points and forming a route. (Hereinafter referred to as “first apparatus owned by the path forming means”).
When the selected point is added or removed, a change occurs in the included point, and it becomes difficult to use the previous route as it is. For this reason, with respect to points belonging to a route in which the selected point is added or removed and the change is included in the included point, the route forming unit may determine the order of visiting the point again to form the route.
[0014]
In the first apparatus owned by the route forming means, the route data receiving means receives the route data including the route formed by the route forming means and further adjusts the route (hereinafter referred to as “repetitive first apparatus”). It may be.
By doing so, the route is adjusted a plurality of times by the first main apparatus, so that the load difference between the routes can be further reduced.
[0015]
In the first repetitive apparatus, the route may be repeatedly adjusted until the variation in the load for each route in the route formed by the route forming means falls within a predetermined range.
By doing this, the route is repeatedly adjusted by the first main apparatus until the variation in load for each route falls within a desired predetermined range, so that the load difference between the routes can be reduced well to a desired level. it can.
[0016]
In the first apparatus repeatedly, the equalization data forming means for forming equalization data, which is data indicating the variation in load for each path in the path formed by the path formation means, and the equalization for storing the equalization data Judgment whether the most recent equalized data formed by the equalized data storage means and the equalized data forming means is improved as compared to the past equalized data stored in the equalized data storage means And an improvement determination unit that, when it is determined that the improvement determination unit is improved, the route data reception unit receives the route data related to the route formed by the route formation unit and further adjusts the route. (Hereinafter referred to as “equalized data use first main apparatus”).
In this way, when the route is repeatedly adjusted by the first apparatus repeatedly, the situation in which the variation in the load for each route is being reduced (that is, the possibility that the variation may be reduced in the future) ) Repeatedly adjusts the route, so that the load difference between the routes can be reduced well. Further, when the route is repeatedly adjusted by the first device repeatedly, if the reduction in the variation in load for each route stops further (saturates), the route adjustment is stopped repeatedly, so the first route is repeatedly used. It is possible to prevent the apparatus from performing useless processing.
[0017]
In the first apparatus, the history storage means stores the history of the affiliation change process of the selected point performed by the affiliation change means, and the history storage means stores the same history as the affiliation change process of the most recently selected point. A convergence determination unit that determines whether or not the history storage unit stores the same history as the affiliation change process of the most recent selection point, The route data receiving unit may receive route data related to the route formed by the route forming unit and further adjust the route.
In this way, when the route is repeatedly adjusted multiple times by the first main apparatus, the operation for reducing the variation in the load for each route is still saturated when the same history as the affiliation change processing of the most recent selected point does not exist. It is determined that the operation has not been performed (that is, the operation has not yet oscillated), and the route is repeatedly adjusted, so that the load difference between the routes can be reduced well. If the same history as the process of changing the affiliation of the most recently selected point exists, it is determined that the operation for reducing the variation in load for each route is saturated (that is, the operation is vibrating), and the route is adjusted. Is stopped, it is possible to prevent the first apparatus from repeatedly performing unnecessary processing.
[0018]
In the first apparatus using equalization data, the history storage means for storing the history of the affiliation change process of the selected point performed by the affiliation change means and the improvement determination means are improved in the latest equalization data. A convergence determination unit for determining whether or not the history storage unit stores the same history as that of the selection point affiliation change processing related to the latest equalization data, the convergence determination unit However, if it is not determined that the history storage unit stores the same history as the selection point affiliation change processing related to the most recent equalization data, the route data related to the route formed by the route forming unit is The data receiving means may receive and further adjust the route.
In this way, even if the improvement determining means does not determine that the most recent equalized data has been improved in the first apparatus using equalized data, the same history as the affiliation change process of the most recent selected point When there is not, it is determined that the operation for reducing the variation in load for each route is not yet saturated (that is, the operation is not yet oscillating), and the route is repeatedly adjusted. Can be reduced more effectively.
[0019]
(Second book device)
Next, a second route adjustment apparatus (hereinafter referred to as “second main apparatus”) of the present invention will be described.
The second apparatus includes a route data receiving unit that receives a plurality of route data including a starting point and a route around the plurality of points, and each point included in the plurality of route data received by the route data receiving unit. , A total load evaluation unit that evaluates a change in load on all routes that occurs when the point belongs to a route that does not include the point, and a load change that is evaluated by the total load evaluation unit The point where the affiliation is changed when the load is reduced compared to before the change, and the previous affiliation where the point where the affiliation is changed belongs to before the change of affiliation A load change storage means for storing the associated route as a change candidate data, and a post-affiliation route that is a route to which the affiliation is changed. Remembered Extraction means for extracting one that satisfies a predetermined condition among said change candidate data, are those comprising a path adjusting device.
[0020]
By doing so, the route data accepting means accepts a plurality of route data including the start point and the route around the plurality of points.
Then, the overall load evaluation means evaluates the change in the load of all the routes that occurs when each point included in the plurality of route data received by the route data receiving means belongs to a route that does not include the point. .
Here, “route” and “load” are the same as those described in the first apparatus.
The load change storage means is a point where the affiliation is changed when the change in the load evaluated by the overall load evaluation means indicates that the load is reduced as compared to before the affiliation of the point is changed. A previous belonging route that is a route to which the point where the affiliation is changed belongs before the affiliation is changed, and a post-affiliation route that is a route to which the affiliation is changed is a route to which the affiliation is changed, , Are stored as change candidate data.
Finally, the extraction unit extracts data that matches a predetermined condition from the change candidate data stored in the load change storage unit.
[0021]
For this reason, a load change that occurs when a point belongs to a route that does not include the point is obtained by the overall load evaluation means, and this load change is a load compared to before the point affiliation is changed. Change candidate data is stored in the load change storage means. Then, the extraction unit extracts the change candidate data stored in the load change storage unit that matches the predetermined condition, so that the load is reduced compared to the route data received by the route data reception unit. Change candidate data can be obtained.
In other words, the second main apparatus is an apparatus that determines a route that reduces the load when a plurality of places are visited by a plurality of moving bodies.
[0022]
In the second apparatus, the change candidate data is further associated with a degree of reduction indicating how much the total load of all routes is reduced as compared to before the change of location affiliation. The predetermined condition may be a condition that the degree of reduction is the maximum.
In this way, the extraction means indicates how much the total load of all routes among the change candidate data stored in the load change storage means is reduced as compared to before the location affiliation is changed. Since the data with the maximum reduction degree is extracted, change candidate data that can reduce the load most can be obtained.
[0023]
The second apparatus further includes route forming means for forming a route according to the change candidate data extracted by the extracting means (hereinafter referred to as “route forming means-owned second apparatus”). Also good.
Since the change candidate data indicates that the affiliation of the point is changed, if this change is made, the point included in the route is changed, and it becomes difficult to use the previous route as it is. Therefore, the route may be formed again by the route forming means according to the change candidate data.
[0024]
In the second apparatus owned by the route forming means, the route data receiving means receives the route data including the route formed by the route forming means and further adjusts the route (hereinafter referred to as “repeated second apparatus”). It may be.
By doing so, the route is adjusted a plurality of times by the route forming means possessing second main device, so that the load can be further reduced.
[0025]
The second apparatus repeatedly includes a change candidate history storage unit that stores a history of change candidate data extracted by the extraction unit, and the extraction unit stores the change candidate data stored in the load change storage unit. Of these, the one extracted from the change history data excluding the same history as the history stored in the change candidate history storage means (hereinafter referred to as “duplicate history elimination second apparatus”) may be used.
By doing so, the change candidate history storage means stores the history of change candidate data previously extracted by the extraction means, and the extraction means changes the change candidate data stored in the load change storage means. Since it is extracted from the change history data excluding the same as the previous history stored in the candidate history storage means, it is possible to prevent the extraction means from duplicating what was previously extracted by the extraction means it can.
[0026]
In the duplicate history elimination second apparatus, the route data receiving unit receives route data including the route formed by the route forming unit until the extracting unit cannot extract the change history data, and further adjusts the route. You may do.
In this way, it is possible to thoroughly examine change candidate data that can reduce the load.
[0027]
(3rd device)
Furthermore, the present invention also provides a path forming device. The route forming apparatus of the present invention (hereinafter referred to as “third main apparatus”) will be described.
The third apparatus can receive position data of a plurality of points, and can calculate the total load calculating means for calculating the total load around all of the plurality of points, and each mobile body that visits a part of the plurality of points. A moving body number determining unit that receives a load allowable amount that is a load amount and determines the number of moving bodies by a predetermined method from the total load evaluated by the total load calculating unit and the load allowable amount; A point dividing unit that divides a plurality of points by the number of the moving bodies, a mobile body starting position information receiving unit that receives starting position information indicating a starting position of each of the moving bodies, and a point divided by the point dividing unit A mobile unit allocating unit for allocating the mobile unit according to the starting position information having a predetermined positional relationship with respect to each group, and a starting point of the mobile unit allocated by the mobile unit allocating unit as a starting point. Consisting includes a respective group primitive path forming means for forming a path for each group over the all points belonging to the group corresponding to the body, and a path forming apparatus.
[0028]
The “load” here is the same as that described in the first apparatus. If such a 3rd main apparatus is used, a total load calculation means will receive the position data of a some point, and will calculate the whole load over all this some point.
Then, the moving body number determination means receives a load allowable amount that is an amount of load that can be handled by each of the moving bodies that travel around some of the plurality of points. Further, the moving body number determining means determines the number of moving bodies by a predetermined method from the total load evaluated by the total load calculating means and the received load allowable amount.
Further, the point dividing means divides the plurality of points by the number of moving bodies (determined by the moving body number determining means).
The moving body departure position information receiving means receives departure position information indicating the departure position of each moving body.
Then, the moving body assigning means assigns the moving body related to the departure position information having a predetermined positional relationship to each group of points divided by the point dividing means.
Finally, each group original route forming means creates a route for each group that goes around all points belonging to the group corresponding to the moving object, with the starting position of the moving object assigned by the moving object assigning means as the starting point.
[0029]
Therefore, the third main apparatus receives the position data of a plurality of points to be visited, the allowable load that can be handled by each of the moving bodies that travel around some of the plurality of points, and the starting position of each of the moving bodies. Divides a plurality of points into groups according to the number of required moving bodies, assigns a moving body to each group, and starts from the starting position of the moving body assigned to the group for each group. Create a route around all points belonging to the group.
For this reason, when the third apparatus circulates a plurality of places by a plurality of mobile bodies, each mobile body can determine which place it takes over and how each mobile body goes around these places. .
[0030]
In the third apparatus, the first total amount obtained by summing up the loads related to the routes for each group formed by the group original route forming means for all the groups, and the moving body number determining means are received by each group, The total amount determining means for comparing the second total amount obtained by adding up the load allowable amounts of the allocated mobile objects and determining whether or not the second total amount is equal to or greater than the first total amount; and If the total amount is not determined to be greater than or equal to the first total amount, the mobile unit further includes a mobile unit increasing unit that increases the number of mobile units, and the point dividing unit includes a plurality of points according to the increased number of mobile units. The mobile body assigning means assigns a mobile body to each group of points divided according to the increased number of mobile bodies, and each group primitive path forming means assigns the increased number of mobile bodies. Path for each group of points that are divided according to the number of the mobile may be configured to create the.
[0031]
In this way, the total amount judging means adds up the load allowable amounts of the mobile units assigned to the respective groups, and the second total quantity has all the loads related to the routes for each group formed by the respective group original route forming means. It is judged whether it is more than the 1st total amount totaled about the group of. This is because the load capacity (capability) of all the mobile units that are handled cannot be executed unless it is equal to or greater than the total load on the route of each group.
Accordingly, the moving object increasing means increases the number of moving objects when the total amount determining means does not determine that the second total amount is greater than or equal to the first total amount. Then, the point dividing unit divides a plurality of points according to the increased number of moving objects, and the moving object assigning unit assigns the moving object to each group of the points divided according to the increased number of moving objects. And each group primitive route forming means creates a route for each group of points divided according to the increased number of moving bodies (ie, increasing the number of moving bodies and increasing the number of moving bodies). Depending on the number of bodies, the point dividing means, the moving object assigning means, and each group primitive route forming means operate.)
As a result, the path formed by the third main apparatus can be executed more reliably.
[0032]
Needless to say, the third book apparatus can be used alone, but can also be used in combination with the first book apparatus or the second book apparatus. In this case, the route data receiving means of the first book device or the second book device may accept the route for each group starting from the starting position of the mobile body formed by the third device as route data. . If constituted in this way, when a plurality of places are circulated by a plurality of mobile bodies, the third apparatus forms which places each mobile body takes charge of, and how each mobile body goes around these locations. Can be adjusted well (when combined with the first apparatus, the load difference between the paths can be reduced, and when combined with the second apparatus, the load can be reduced).
[0033]
Further, it goes without saying that either the first book apparatus or the second book apparatus can be used alone, but the first book apparatus and the second book apparatus can also be used in combination. It does not matter before and after combining these two cases (ie, when the result obtained by the first device is adjusted by the second device, and when the result obtained by the second device is adjusted by the first device. In this case, since it is necessary to pass the route data to the one located later, the one located before needs to be provided with a route forming means.
In other words, the route formed by the route forming unit of the first device owned by the route forming unit may be configured to receive the route data receiving unit of the second device as route data and further adjust the route. Furthermore, in such a case, the route for each group starting from the starting position of the mobile body formed by the third device is configured to be received as route data by the route data receiving device of the first device owned by the route forming device. May be.
Conversely, the route formed by the route forming means of the second device owned by the route forming means may be configured so that the route data receiving means of the first device accepts it as route data and further adjusts the route. Further, in such a case, the route for each group starting from the starting position of the moving body formed by the third device is configured to be received as route data by the route data receiving device of the second device owned by the route forming device. May be.
In this way, by combining the first main apparatus and the second main apparatus, it is possible to reduce the load difference between the paths and reduce the load at a time.
[0034]
Any of the first apparatus, the second apparatus, and the third apparatus can be realized by causing a computer to execute a predetermined program, and the program is recorded on a computer-readable storage medium. Can do.
[0035]
DETAILED DESCRIPTION OF THE INVENTION
Hereinafter, embodiments of the present invention will be described with reference to the drawings. However, the present invention is not limited by these.
[0036]
FIG. 1 is a schematic block diagram showing a hardware configuration of a route search apparatus (present apparatus) 11 according to an embodiment of the present invention. With reference to FIG. 1, a hardware configuration of the apparatus 11 according to an embodiment will be described. Here, when this apparatus 11 circulates a plurality of delivery points with a plurality of delivery vehicles, each delivery vehicle (moving body) is responsible for which delivery point (point), and how each vehicle is responsible for the delivery point. This is an apparatus for searching and determining a patrol route for patrol, and includes the above-described first main apparatus, second main apparatus, and third main apparatus.
In the present embodiment, the apparatus 11 is configured by a computer having a built-in program, and a hard disk 19 is connected to the apparatus 11.
The apparatus 11 includes a CPU 11a that performs arithmetic processing, a RAM 11b that serves as a work area for the CPU 11a, a ROM 11c that records control programs, and an interface 11d that exchanges information with the hard disk 19. Although not shown in FIG. 1, besides this, a keyboard for inputting data to the apparatus 11, a display for displaying information from the apparatus 11, and printing information from the apparatus 11. Are connected to the apparatus 11 via an interface 11d. In addition, although the program and the like are stored in the ROM 11c here, it goes without saying that the program may be stored in the hard disk 19.
[0037]
FIG. 2 is a schematic functional block diagram showing a rough basic configuration of the apparatus 11 realized by the hardware shown in FIG. 1 and a program recorded mainly in the ROM 11c. With reference to FIG. 2, the basic configuration of the apparatus 11 will be described.
Functionally, the apparatus 11 has an initial information database 21 that stores initial information of the apparatus 11, a cluster division unit 31, a provisional circuit formation unit 41, an affiliation adjustment unit 51, and an operation rate adjustment. Unit 61, random insertion unit 71, N-opt unit 73, traveling time calculation unit 75, initial information storage unit 91, vehicle number storage unit 93, cluster attribute value storage unit 95, route storage unit 97 And a history storage unit 98 and a required time storage unit 99.
[0038]
The initial information database 21 is configured by using a part of the storage area of the hard disk 19 and already stores data as shown in FIG. That is, the coordinates (position data of points) of the delivery points (points referred to in the present invention) shown in FIG. 3 (a) and the depot (delivery vehicle as a moving body) shown in FIG. Coordinates (departure position information) and the constraint conditions (allowable load) shown in FIG. 3C are already stored in the initial information database 21. Yes. The coordinates of the delivery point and the depot shown in FIGS. 3 (a) and 3 (b) are both indicated by XY coordinates, which are orthogonal coordinates set on the ground surface. For example, the position of the delivery point number 3 is (X, Y) = (401, 841), and the position of the depot number 2 is indicated by (X, Y) = (4227, 2259). The constraint condition shown in FIG. 3C is the maximum movement distance that can be moved in one day for each delivery vehicle (here, the movement distance is used as “load” in the present invention). Are shown as coordinate values in the XY coordinate system. Specifically, all four of the delivery vehicles 0 to 3 are set to 10000 (coordinates) (in FIG. 3C). The vehicle numbers 0 to 3 of the delivered vehicles correspond to the depot numbers 0 to 3 in Fig. 3 (b), for example, the delivery vehicle starting from the depot 3 is the vehicle 3.
[0039]
FIG. 4 is a detailed functional block diagram of the cluster dividing unit 31. A detailed configuration of the cluster dividing unit 31 will be described with reference to FIG.
Functionally, the cluster dividing unit 31 includes a file reading unit 33, a table initializing unit 35, and a cluster number calculating unit 37.
First, when the file reading unit 33 is activated (not shown, the file reading unit 33 is activated when a predetermined activation signal is input from the keyboard or the like connected to the apparatus 11). Is the access to the initial information database 21 and reads the coordinates of the delivery point (position data of a plurality of points) (shown in FIG. 3A, corresponding to each of the delivery point numbers 0 to 47 (X , Y)), and the file reading unit 33 writes and stores the coordinates of the read delivery point in the initial information storage unit 91. Next, the file reading unit 33 accesses the initial information database 21 and reads the coordinates of the depot (departure position information indicating the departure position of each delivery vehicle as a moving object) (shown in FIG. 3B). The file reading unit 33 writes the coordinates of the read depot in the initial information storage unit 91 and stores them. Further, the file reading unit 33 accesses the initial information database 21 and reads the constraint condition (the load allowable amount that is the amount of load that can be handled by each delivery vehicle as a moving body) (as shown in FIG. 3C). Yes, the constraint conditions are read corresponding to the vehicle numbers 0 to 3 (in this case, all are 10,000, but different values may be set depending on each vehicle)), and the file reading unit 33 Writes and stores the read constraint conditions in the initial information storage unit 91. As described above, all the coordinates of the delivery point (FIG. 3 (a)), the coordinates of the depot (FIG. 3 (b)), and the constraints (FIG. 3 (c)) stored in the initial information database 21 are stored. Is copied to the initial information storage unit 91. The initial information storage unit 91 is configured using a part of the storage area of the RAM 11b described above with reference to FIG.
Thereafter, the file reading unit 33 issues an activation signal to the table initialization unit 35.
[0040]
Upon receiving the activation signal from the file reading unit 33, the table initialization unit 35 accesses the initial information storage unit 91, and the delivery point coordinates (FIG. 3A) stored in the initial information storage unit 91 and the depot. The coordinates (Fig. 3 (b)) are read out and acquired, and a total of 52 locations (starting points) of delivery points 0 to 47 and depots 0 to 3 to 51 locations (end points) excluding themselves (starting points). The distances are calculated, and the calculated distances are collected as a two-dimensional table as shown in FIG. 5 (in FIG. 5, the distance data to be written in the table is shown for ease of illustration, etc. Description is omitted.) The distance calculation here is performed by calculating the linear distance between the position of the starting point and the position of the ending point (that is, assuming that the starting point coordinates (x1, y1) and the ending point coordinates (x2, y2) are ((x1- x2) ² + (Y1-y2) ² ) ^0.5 Is calculated by ), The table initialization unit 35 has map information of locations where delivery points and depots exist in advance, and the table initialization unit 35 uses the map information to map the shortest distance along the actual road (map information It is needless to say that calculating the distance between two points along the actual road by using it has already been widely performed in in-vehicle navigation systems and the like, so the description thereof is omitted here. Yes.
Further, the table initialization unit 35 writes and stores the collected two-dimensional table (hereinafter referred to as “distance table”) as shown in FIG. 5 in the required time storage unit 99.
Thereafter, the table initialization unit 35 issues an activation signal to the cluster number calculation unit 37.
[0041]
Upon receiving the activation signal from the table initialization unit 35, the cluster number calculation unit 37 transmits the activation signal to the random insertion unit 71.
The random insertion unit 71 that has received the activation signal from the cluster number calculation unit 37 accesses the initial information storage unit 91 and stores the coordinates of the delivery points stored in the initial information storage unit 91 (FIG. 3A: a plurality of (Location data of a point) is read and acquired, and the required time storage unit 99 is accessed to read and acquire the distance table (see FIG. 5) stored in the required time storage unit 99. Then, the random insertion unit 71 uses the read and acquired delivery point coordinates and the distance table to perform a tour (that is, the order in which all delivery points are visited by the random insertion method. Specifically, according to the order in which the delivery points are visited. The number of delivery points is arranged) and the circuit is transmitted to the cluster number calculation unit 37. Note that the random insertion method is a standard known method for creating a circuit for patroling a plurality of points. In addition, the circuit is created by the random insertion method here, but the invention is not limited to this, and any method may be used as long as the circuit is formed by any method, other than the random insertion method. For example, the farthest insertion method, the convex hull, the space filling curve method, the bucket method, the Karp's division algorithm, and the like can be exemplified.
[0042]
The cluster number calculation unit 37 that has received the tour from the random insertion unit 71 transmits the received tour to the N-opt unit 73.
The N-opt unit 73 that has received the received circuit from the cluster number calculation unit 37 accesses the initial information storage unit 91 and coordinates of the delivery point stored in the initial information storage unit 91 (FIG. 3A). ) Is further read, the required time storage unit 99 is accessed, the distance table (see FIG. 5) stored in the required time storage unit 99 is read out and acquired, and the coordinates of these delivery points (FIG. 3A) And the distance table, the N-opt method (the 2-opt method or the 3-opt method may be used in consideration of the processing time, and the 2-opt method is used here) is applied to the received circuit. Thus, the received circuit is improved. At this time, the delivery point of the starting point when executing the N-opt method is the first delivery point of the circuit received from the cluster number calculation unit 37. Note that the N-opt method is a method for performing local optimization of a circuit, and is a generic name for an object that can be executed at an arbitrary number N (for example, delivery points) (for example, a delivery point) (for example, "Http://www.daisy.ai.kyutech.ac.jp/~sin/demos/TSP/" The simplest of the N-opt methods is the 2-opt method. 2 ”is the number of cities exchanging the order of patrol.) Further, here, the circuit is improved by the N-opt method, but the present invention is not limited to this. When there is some circuit, the circuit is improved (for example, the circuit is improved). Anything other than the N-opt method, such as the 2-opt method or the 3-opt method, can be used as long as the calculation method of Lin and Kernighham can be used. The improvement method can be illustrated.
The N-opt unit 73 transmits, to the cluster number calculation unit 37, a tour circuit (the order in which the delivery points are visited) improved by applying the N-opt method.
FIG. 6 shows an example of the improved circuit (the circuit is shown in the coordinates) received by the cluster number calculation unit 37 from the N-opt unit 73 in this way. In FIG. 6, the delivery point of the starting point when executing the N-opt method is indicated as point A, and the traveling direction is indicated by arrow B. Note that the result of FIG. 6 is a result obtained using the coordinates of the delivery point shown in FIG.
[0043]
The cluster number calculator 37 that has received the improved circuit (hereinafter referred to as “improved circuit”) from the N-opt unit 73 transmits the improved circuit to the tour time calculator 75.
The traveling time calculation unit 75 that has received the improved traveling circuit reads out and acquires the distance table stored in the required time storage unit 99, and calculates the total distance of the improved traveling circuit (the entire load that travels all of the plurality of points). Calculate using. The calculated total distance of the improvement circuit is transmitted from the traveling time calculation unit 75 to the cluster number calculation unit 37. Note that the total distance of the improvement circuit shown in FIG. 6 is calculated as 35587.
As described above, the cluster number calculation unit 37, the random insertion unit 71, the N-opt unit 73, and the traveling time calculation unit 75 accept the position data of a plurality of points, and the overall load over the plurality of points. The total load calculating means (for the third apparatus) is calculated.
[0044]
The cluster number calculation unit 37 that has received the total distance of the improved tour from the cyclic time calculation unit 75 accesses the initial information storage unit 91 and the constraint condition stored in the initial information storage unit 91 (FIG. 3C: movement) It is a load tolerance that is the amount of load that each body delivery vehicle can handle. Specifically, it reads out and obtains the maximum travel distance that each delivery vehicle can move in a day), and restricts each delivery vehicle. The arithmetic average value of the conditions is calculated (here, since all four vehicles 0 to 3 are 10,000, the arithmetic average value is 10000 (4 × 10000/4)).
Next, the cluster number calculation unit 37 divides the total distance of the improved circuit received from the cyclic time calculation unit 75 by the arithmetic average value (total distance / the arithmetic average value), and the fractional part of the obtained quotient To the number of vehicles (for example, if the quotient is 3.0002, the number of vehicles is 4, and if the quotient is 5 (when divided), the number of vehicles is 5.) Here, the total distance of the improvement circuit is 35587, and the arithmetic average value of the constraint condition of each delivery vehicle is 10,000, so the quotient of (total distance / arithmetic average value) is 3.5587, which is a fractional part. Rounded up to 4 vehicles.
Then, the cluster number calculation unit 37 transmits the obtained number of vehicles to the vehicle number storage unit 93 and stores it in the vehicle number storage unit 93.
As described above, the cluster number calculation unit 37 allows the load (delivery vehicle) that can be handled by each mobile body (delivery vehicle) that visits a part of a plurality of points (delivery points) (see FIG. 3 as a constraint condition). (C)) is received, and the number of the moving bodies is determined by a predetermined method from the total load evaluated by the total load calculation means (of the third apparatus) and the allowable load (third apparatus). A) moving body number determining means is configured.
Finally, the cluster number calculation unit 37 issues an activation signal to the provisional circuit formation unit 41 (a fuzzy clustering calculation unit 43 described later).
[0045]
FIG. 7 is a detailed functional block diagram of the provisional circuit forming unit 41. With reference to FIG. 7, the detailed structure of the provisional circuit formation part 41 is demonstrated.
The provisional circuit forming unit 41 functionally includes a fuzzy clustering calculating unit 43 and an initial circuit forming unit 45.
First, the fuzzy clustering calculation unit 43 that has received the activation signal from the cluster number calculation unit 37 accesses the vehicle number storage unit 93 to read out and acquire the number of vehicles stored in the vehicle number storage unit 93 (here, 4). To do. Then, the fuzzy clustering calculation unit 43 accesses the initial information storage unit 91 to read out and acquire the coordinates of the delivery point (FIG. 3A) stored in the initial information storage unit 91. Further, the fuzzy clustering calculation unit 43 calculates the degree of attribution of each delivery point to each cluster using the number of vehicles read and acquired (here, 4) as the number of clusters. Note that this fuzzy clustering processing method is a known technique, and is described in detail, for example, in Japanese Patent Laid-Open No. 05-274293 (including the fuzzy c-means method, which is one of the fuzzy clustering methods, including references). As a result, the degree of belonging to each cluster is calculated.) FIG. 8 shows the degree of attribution of each delivery point (delivery points 0 to 47) to each cluster (clusters 0 to 3) calculated in this way. For example, it can be seen that the degree of membership of the delivery point number 10 is 0.49 for cluster 0, 0.03 for cluster 1, 0.38 for cluster 2, and 0.1 for cluster 3.
Then, the fuzzy clustering calculation unit 43 transmits the calculated degree of membership of each delivery point to each cluster (FIG. 8) to the cluster attribute value storage unit 95 and stores it in the cluster attribute value storage unit 95.
Finally, the fuzzy clustering calculation unit 43 transmits the calculated degree of membership of each delivery point to each cluster (FIG. 8) to the initial circuit creation unit 45.
[0046]
The initial circuit creation unit 45 that has received the degree of attribution of each delivery point to each cluster (FIG. 8) from the fuzzy clustering calculation unit 43 determines that each delivery point belongs to the cluster (ie, group) with the highest degree of attribution. Then, it is determined to which cluster (group) all delivery points belong. The method for determining the cluster to which the delivery point belongs is shown in FIG. That is, the initial circuit creation unit 45 compares the degree of belonging to each of the delivery points (delivery points 0 to 47) with respect to the cluster 0, the cluster 1, the cluster 2, and the cluster 3 and belongs to the cluster with the largest degree of belonging. decide. For example, the degree of membership of the delivery point of number 10 is 0.49 for cluster 0, 0.03 for cluster 1, 0.38 for cluster 2, and 0.1 for cluster 3, so The delivery point is determined to belong to cluster 0 giving the maximum degree of attribution 0.49. This determination is performed for all the delivery points 0 to 47, and results as shown in FIG. 9 are obtained. Then, the initial circuit creation unit 45 creates a delivery point number list in which the numbers of delivery points belonging to each cluster as shown in FIG. 10 are described for each cluster, and the delivery point number list is stored in the route storage unit 97. And stored in the route storage unit 97.
As described above, the fuzzy clustering calculation unit 43 and the initial circuit creation unit 45 determine a plurality of points (delivery points) by the number of moving bodies (of the third apparatus) moving body number determining means. Point dividing means (of the third apparatus) is divided.
[0047]
Next, the initial circuit creation unit 45 accesses the initial information storage unit 91, reads out and acquires the coordinates of the delivery point stored in the initial information storage unit 91 (FIG. 3A), and has created it. The center-of-gravity position (X, Y) of each cluster is obtained using the above-mentioned delivery point number list and the coordinates of the delivery points read and acquired. The center of gravity position is calculated by assuming that all delivery points belonging to each cluster have the same mass.
Furthermore, the initial circuit creation unit 45 accesses the initial information storage unit 91 and stores the coordinates of the depot stored in the initial information storage unit 91 (FIG. 3 (b): indicates the departure position of each delivery vehicle as a moving body. (Departure position information) is read out and acquired, and a depot closest to the center of gravity of each cluster obtained previously is selected to assign a depot to each cluster. Then, the initial circuit creation unit 45 accesses the route storage unit 97 and writes the depot assigned to each cluster in the delivery point number list stored in the route storage unit 97 as shown in FIG. Here, the depot is assigned to each cluster by selecting the depot closest to the center of gravity of each cluster. However, the present invention is not limited to this. For example, the distance to the delivery point belonging to each cluster is small. A depot may be assigned to the cluster.
As described above, the starting position information (FIG. 3B) indicating the starting position of each moving body (delivery vehicle) is received by the initial circuit creation unit 45 (the third apparatus). Accepting means is configured. Then, a predetermined positional relationship (here, the center of gravity of each cluster is set) with respect to each group (cluster) of the points (delivery points) divided by the point dividing means (of the third apparatus) by the initial circuit creation unit 45. A moving body allocating means (of the third apparatus) for allocating a moving body (delivery vehicle) related to departure position information having the closest positional relationship) is configured.
Thereafter, the initial circuit creation unit 45 transmits to the random insertion unit 71 the delivery point number list (the one shown in FIG. 11 in which the allocation depot is described) that the initial circuit creation unit 45 already has.
[0048]
The random insertion unit 71 that has received the delivery point number list from the initial circuit creation unit 45 accesses the initial information storage unit 91 and coordinates of the delivery point stored in the initial information storage unit 91 (FIG. 3A). And the coordinates of the depot (FIG. 3B) are read out and acquired, and the required time storage unit 99 is accessed and the distance table (see FIG. 5) stored in the required time storage unit 99 is read out and acquired. Then, the random insertion unit 71 uses the delivery point coordinates, the depot coordinates, and the distance table that have been read out and acquired, for each cluster in the received delivery point number list, the depot (mobile object assignment) assigned to that cluster. A traveling circuit that circulates all delivery points belonging to the cluster (hereinafter referred to as “initial traveling circuit for each cluster”) by using the random insertion method described above as a starting point) The cluster-specific initial circuit is transmitted to the initial circuit creation unit 45.
The initial circuit creation unit 45 that has received the cluster-specific initial circuit transmits the cluster-specific initial circuit to the N-opt unit 73.
The N-opt unit 73 that has received the cluster-specific initial circuit from the initial circuit creation unit 45 accesses the initial information storage unit 91 and coordinates of delivery points stored in the initial information storage unit 91 (FIG. 3A )) And the coordinates of the depot (FIG. 3B) are read and acquired, and further, the required time storage unit 99 is accessed to read out and acquire the distance table (see FIG. 5) stored in the required time storage unit 99. Using the coordinates of these delivery points (FIG. 3 (a)), the coordinates of the depot (FIG. 3 (b)), and the distance table, the above-described N-opt method is applied to each cluster initial circuit (for each cluster). This is applied to improve the initial circuit for each cluster, and the improved initial circuit for each cluster (hereinafter referred to as “initial circuit for each improved cluster”) is transmitted to the initial circuit creation unit 45.
As described above, the initial circuit creation unit 45 is also included by the random insertion unit 71 and the N-opt unit 73 (in consideration of the delivery of the cluster-based initial circuit from the random insertion unit 71 to the N-opt unit 73. ), Each group that visits all points belonging to the group (cluster) corresponding to each mobile object (delivery vehicle), starting from the starting position (depot) of the mobile object (delivery vehicle) assigned by the mobile object assigning means Each group original route forming means (for the third apparatus) for creating a route for each (cluster) (initial circuit for each improved cluster) is configured.
The initial circuit creation unit 45 that has received the improved initial circuit for each cluster accesses the route storage unit 97 and improves the order in which the delivery point numbers of the belonging delivery points in the delivery point number list stored in the route storage unit 97 are described. The order is rewritten according to the initial circuit for each cluster (the order of description of the delivery point belonging to the delivery point number list stored in the route storage unit 97 indicates the initial circuit for each improved cluster). FIG. 12 shows the initial circuit for each improved cluster obtained in this way. In FIG. 12, ■ (substantially squares filled in black) indicates each depot. In FIG. 12, the clusters 0 to 3 are indicated by “No. 0” to “No. 3”, respectively, and the traveling direction is the clockwise direction.
[0049]
Thereafter, the initial tour circuit creation unit 45 transmits the initial tour circuit for each improved cluster to the tour time calculation unit 75. The traveling time calculation unit 75 that has received the initial circuit for each improved cluster reads out and acquires the distance table stored in the required time storage unit 99, and calculates the traveling distance for each cluster indicated in the initial circuit for each improved cluster as a distance. Calculate from the table. The calculated traveling distance for each cluster is transmitted from the traveling time calculation unit 75 to the initial traveling circuit creation unit 45. Note that the cyclic distance for each cluster corresponding to the improved initial loop circuit by cluster shown in FIG. 12 is 10241 for cluster 0, 9509 for cluster 1, 11375 for cluster 2, and 4647 for cluster 3. It was.
The initial circuit creation unit 45 that has received the cyclic distance for each cluster corresponding to the improved initial circuit for each cluster accesses the initial information storage unit 91 and stores the constraint conditions stored in the initial information storage unit 91 (FIG. 3 ( c): load tolerance), the restriction condition of the vehicle corresponding to the depot used in the initial circuit for each improved cluster is read and acquired, and the read restriction condition (each of the delivery vehicles can move in one day) The maximum value (second total amount) is calculated (here, all of the depots 0 to 3 are used, and the four vehicles 0 to 3 corresponding thereto are 10,000, so the total value is 40,000. And the total (first total amount) of the received cyclic distances for each cluster is calculated (here, 10241 + 9509 + 11375 + 4647 = 35777). Then, the initial circuit creation unit 45 determines whether or not the total value of the constraint conditions (second total amount, here 40000) is equal to or greater than the total value of the cyclic distance (first total amount, here, 35772). The improved initial cluster circuit is determined to be appropriate, and an activation signal is issued to the affiliation adjustment unit 51 (route control unit 52). If the total value of the constraint conditions is not equal to or greater than the total value of the cyclic distance, the initial circuit creation unit 45 does not determine that this improved initial cluster circuit is appropriate, and sets the number of vehicles to 1 in the fuzzy clustering calculation unit 43. After the signal to be added is issued, the same signal as the start signal issued from the cluster number calculation unit 37 to the fuzzy clustering calculation unit 43 is transmitted (that is, the provisional circuit forming unit 41 of the above-described provisional circuit forming unit 41 increases according to the number of vehicles increased by 1). The operation is repeated.)
As described above, the initial circuit creation unit 45 assigns loads (cyclic distances) related to the routes (initial circuit for each improved cluster) for each group (cluster) formed by each group source route forming means to all groups. The first total amount summed with respect to (cluster) and the second total amount summed with the load allowance (constraint conditions) of each of the moving bodies (delivery vehicles) received by the moving body number determining means and assigned to each group (cluster). And a total amount judging means (of the third apparatus) for judging whether or not the second total amount is equal to or larger than the first total amount. If the initial circuit creation unit 45, which is the total amount determining means, does not determine that the second total amount is greater than or equal to the first total amount, the moving body increasing means (of the third apparatus) that increases the number of moving bodies It is comprised by the path creation part 45. The point dividing means divides a plurality of points according to the increased number of moving objects, and the moving object allocating means assigns the moving object to each group of the points divided according to the increased number of moving objects. And each group primitive route forming means creates a route for each group of the points divided according to the increased number of moving objects.
[0050]
FIG. 13 is a detailed functional block diagram for explaining the operation of the affiliation adjusting unit 51. The detailed configuration of the affiliation adjustment unit 51 will be described with reference to FIG.
Functionally, the affiliation adjustment unit 51 includes a route control unit 52, an affiliation change processing unit 53, a history check unit 54, a city affiliation change processing unit 55, and an affiliation change result setting unit 56.
First, the path control unit 52 that has received the activation signal from the initial circuit creation unit 45 accesses the initial information storage unit 91 and reads the constraints (FIG. 3C) stored in the initial information storage unit 91. Acquired (used to calculate the operation rate described later), accesses the required time storage unit 99, reads and acquires the distance table stored in the required time storage unit 99, and further accesses the route storage unit 97 to access the route storage unit 97 reads and acquires the initial circuit for each improved cluster (a plurality of route data including a starting point and a route around a plurality of points) stored in 97.
Next, the path control unit 52 calculates the cyclic distance for each cluster in the improved initial cluster circuit by using the distance table and the improved initial cluster circuit for the cluster.
Then, the route control unit 52 calculates the operation rate for each delivery vehicle. The operating rate is defined as a quotient obtained by dividing the traveling distance for each cluster calculated as described above by the restriction condition of the delivery vehicle in charge of the cluster (FIG. 3C, here, all 10000).
Further, the route control unit 52 obtains an average value (arithmetic) of the operation rate for each delivery vehicle, and calculates an equalization coefficient using the average value. For each delivery vehicle, the equalization coefficient is the absolute value of (the operation rate of the delivery vehicle−the average value of the operation rate) (that is, | (the operation rate of each delivery vehicle) − (the average value of the operation rate) |)). Is calculated by adding the absolute values obtained for all delivery vehicles to obtain a total value and dividing the total value by the number of delivery vehicles (ie, equalization coefficient = Σ (| (each Calculated as (operating rate of delivery vehicle) − (average value of operating rate) |) / (number of delivery vehicles)).
Finally, the route control unit 52 transmits the operation rate and the equalization coefficient for each delivery vehicle calculated as described above to the affiliation change processing unit 53.
[0051]
The affiliation change processing unit 53 that has received the operation rate and the equalization coefficient for each delivery vehicle from the route control unit 52 has the received equalization coefficient stored by itself (the affiliation change processing unit 53). (As will be described later, the affiliation change processing unit 53 stores the minimum equalization coefficient so far, so that the received equalization coefficient is the minimum equalization so far. It is determined whether or not it is smaller than the coefficient.) Or, it is determined whether or not itself (affiliation change processing unit 53) stores the equalization coefficient, and when it is determined that it is one of them, After overwriting and storing the received equalization coefficient (that is, the affiliation change processing unit 53 stores the smallest one of the equalization coefficients received from the path control unit 52 so far). Each delivery received from the route control unit 52 To send the rate of operation of each both to the city affiliation change processing unit 55. On the other hand, the affiliation change processing unit 53 determines that the received equalization coefficient is not smaller than the equalization coefficient stored by itself or does not store the equalization coefficient by itself. In this case (that is, when the affiliation change processing unit 53 stores the equalization coefficient and the received equalization coefficient is equal to or greater than the stored equalization coefficient), the history check unit 54 receives an activation signal. To emit.
[0052]
The city affiliation change processing unit 55 that has received the operation rate for each delivery vehicle from the affiliation change processing unit 53 accesses the initial information storage unit 91 and coordinates of delivery points stored in the initial information storage unit 91 (FIG. 3 ( a)) and the coordinates of the depot (FIG. 3B) are read and acquired, the cluster attribute value storage unit 95 is accessed, and the degree of attribution of each delivery point stored in the cluster attribute value storage unit 95 to each cluster (Fig. 8) is read and acquired, and the route storage unit 97 is accessed and the route storage unit 97 stores the initial circuit for each improved cluster (start point (depot) and route around a plurality of points (delivery points)) , A plurality of route data including). That is, here, the city affiliation change processing unit 55 constitutes route data receiving means (for the first apparatus) that receives a plurality of route data including a starting point and routes that go around a plurality of points.
Next, the city affiliation change processing unit 55 stores the cluster handled by the delivery vehicle that gives the highest operation rate among the operation rates for each delivery vehicle received from the affiliation change processing unit 53 as a cluster of the provider. It is also stored in the cluster list (the storage area of the city affiliation change processing unit 55 itself). Furthermore, the city affiliation change processing unit 55 stores, as a provision destination cluster, a cluster handled by the delivery vehicle that gives the lowest operation rate among the operation rates for each delivery vehicle received from the affiliation change processing unit 53. In this way, the start route (here, the load) that is different from the lightest route among a plurality of route data received by the route data receiving means (of the first main apparatus) by the city affiliation change processing unit 55. Is the heaviest route of the providing cluster), and the completed route that is lighter than the starting route (here, the route of the providing cluster that is the lightest route) Start completion determining means (of the first main apparatus) to determine is configured. Here, the load is evaluated based on the operation rate.
[0053]
Thereafter, the city affiliation change processing unit 55 out of the delivery points belonging to the cluster route stored in the cluster list (obtained from the initial circuit for each improved cluster (FIG. 11) read and acquired as described above). A delivery point having the highest degree of belonging to the cluster of the provider is selected (the degree of membership of each delivery point is obtained by using the degree of belonging to each cluster of each delivery point read and acquired as described above (FIG. 8). Hereinafter, the selected delivery point is referred to as “selected point”). When a plurality of clusters are stored in the cluster list, a selection point is selected from all delivery points belonging to the plurality of clusters (for example, three clusters of cluster 50, cluster 63, and cluster 78 are cluster clusters). In the case of being stored in the list, one selection point is selected from all of the delivery points belonging to the cluster 50, the delivery points belonging to the cluster 63, and the delivery points belonging to the cluster 78).
For example, if the cluster stored in the cluster list is cluster 2 and the destination cluster is 3, refer to FIG. 11 and FIG. 8 (FIG. 9 also shows the same result). The delivery point 46 having the highest degree of belonging to the cluster 3 of the providing destination is selected as a selection point among the delivery points belonging to the cluster 2 stored in the list (the delivery point 46 is assigned to the cluster 3 by 0.16). This is the highest degree of belonging to cluster 3 among the delivery points belonging to cluster 2.)
Then, the city affiliation change processing unit 55 sets the cluster to which the selected point belongs as the affiliation source cluster. In the above example, since the delivery point 46 as the selection point belongs to the cluster 2, the cluster 2 is set as the belonging cluster.
Next, the city affiliation change processing unit 55 moves to a cluster other than the clusters stored in the cluster list (if a plurality of clusters are stored in the cluster list, the cluster is not one of the plurality of clusters). The cluster indicating the highest degree of belonging among the degrees of belonging indicated by the selected point is selected and stored as the affiliation change destination cluster. For example, in the above example, since the number of clusters stored in the cluster list is 2, the clusters other than the cluster are clusters 0, 1, 3, and the degree of belonging indicated by the selection point 46 to the clusters 0, 1, 3 is Since they are 0.3, 0.05, and 0.16, respectively (see FIG. 8), cluster 0 showing the highest degree of belonging 0.3 is selected and stored as the affiliation change destination cluster.
[0054]
Thereafter, the city affiliation change processing unit 55 selects the selection points belonging to the route of the affiliation source cluster in the initial circuit for each improved cluster (as shown in FIG. 11 read from the route storage unit 97). delete. For example, in the above-described example, the delivery points belonging to the cluster 2 that is the affiliation source cluster in the initial circuit by improvement cluster are the delivery points 4, 12, 13, 20,. Therefore, the delivery point 46 as the selected point is deleted, and the delivery points belonging to the cluster 2 are set as delivery points 4, 12, 13, 20,... 38, 40, 47.
Furthermore, the city affiliation change processing unit 55 adds the selected point to the route of the affiliation change destination cluster in the initial circuit for each improved cluster that the selected point has deleted. For example, in the above-described example, the delivery points belonging to the affiliation change destination cluster 0 in the improved initial cluster circuit are the delivery points 0, 2, 7, 8,... 32, 37, 39, 45. Therefore, the delivery point 46 as the selection point is added, and the delivery points belonging to the cluster 0 are set as the delivery points 0, 2, 7, 8,... 32, 37, 39, 45, 46 (position where the selection point is added) Can be either.)
Finally, the city affiliation change processing unit 55 deletes the selected point from the affiliation source cluster and adds the selected point to the affiliation change destination cluster as described above. Is transmitted to the random insertion unit 71.
[0055]
The random insertion unit 71 that has received the selected point addition / departure circuit accesses the initial information storage unit 91 and stores the coordinates of the delivery point (FIG. 3A) stored in the initial information storage unit 91 and the coordinates of the depot (see FIG. 3 (b)) is read out, the required time storage unit 99 is accessed, the distance table stored in the required time storage unit 99 is read out and acquired, and each cluster is assigned to each cluster according to the selected point add / drop circuit. A cyclic circuit that circulates all the delivery points belonging to the cluster from the specified depot as a starting point (hereinafter referred to as a “random insertion selection point addition / division circuit”) is created by the random insertion method described above, and random insertion selection point addition / division circulation The route is transmitted to the city affiliation change processing unit 55.
The city affiliation change processing unit 55 that has received the random insertion selection point addition / removal circuit from the random insertion unit 71 overwrites and stores the random insertion selection point addition / division circuit in the route storage unit 97.
[0056]
Then, the city affiliation change processing unit 55 transmits the random insertion selection point addition / division circuit to the tour time calculation unit 75.
The traveling time calculation unit 75 that has received the random insertion selection point addition / removal circuit from the city affiliation change processing unit 55 reads out and acquires the distance table stored in the required time storage unit 99, and each of the random insertion selection point addition / removal circuit is obtained. The distance for each cluster is calculated from the distance table. The calculated distance for each cluster according to the random insertion selection point addition / division circuit is transmitted from the traveling time calculation unit 75 to the city affiliation change processing unit 55.
Then, the city affiliation change processing unit 55 writes and stores a history relating to the addition / removal processing of the selected point in the history storage unit 98 (the history is additionally written and stored instead of being overwritten). The history of the selection point addition / deletion processing includes items of a providing source cluster, a providing destination cluster, a belonging source cluster, a belonging change destination cluster, a delivery point as a selected point, and an operating rate of each delivery vehicle. FIG. 14 shows an example of the history written and stored in the history storage unit 98 (in FIG. 14, a work number and a figure number are added for easy understanding and explanation). Yes.) Details of FIG. 14 will be described later.
[0057]
Thereafter, the city affiliation change processing unit 55 determines whether or not the affiliation change destination cluster and the provision destination cluster match, and if it does not match, the affiliation change destination cluster at this time is added to the list of clusters described above. (In other words, the affiliation change destination cluster at this time is added to the cluster list and becomes a candidate to be selected as the affiliation source cluster of the next process.) After that, the city affiliation change processing unit 55 selects again. A point, an affiliation source cluster, and an affiliation change destination cluster are newly selected, and the above processing is performed. On the other hand, if the city affiliation change processing unit 55 determines that the affiliation change destination cluster and the provision destination cluster match, the city affiliation change processing unit 55 is included in the list of clusters in the random insertion selection point addition / division circuit (one or two or more). ) A plurality of clusters of the cluster and the destination cluster are read out and acquired from the path storage unit 97 (which stores the random insertion selection point addition / division circuit), and each of the acquired circuits is N -Send to the opt unit 73.
The N-opt unit 73 that has received a cyclic circuit (a part of a random insertion selection point addition / division circuit) related to a plurality of clusters from the city affiliation change processing unit 55 accesses the initial information storage unit 91 and the initial information storage unit 91 The stored coordinates of the delivery point (FIG. 3A) and the coordinates of the depot (FIG. 3B) are read and acquired, and the required time storage unit 99 is accessed and stored in the required time storage unit 99. The distance table (refer to FIG. 5) is read out and acquired, and the coordinates of the delivery points (FIG. 3 (a)), the coordinates of the depot (FIG. 3 (b)), and the distance table are used for each circuit. The improved N-opt method (for each cluster) is applied to improve the cyclic circuit (part of the random insertion selection point addition / division circuit) (hereinafter, “improved partial random insertion selection point addition / division circuit”). Is sent to the city affiliation change processing unit 55. To.
Then, the city affiliation change processing unit 55 that has received the improved partial random insertion selection point addition / removal circuit accesses the route storage unit 97 and improves the improvement of the random insertion selection point addition / removal circuit stored in the route storage unit 97. Rewrite the part corresponding to the part random insertion selection point addition and removal circuit.
Thereafter, the city affiliation change processing unit 55 issues an activation signal (same as the activation signal issued from the initial circuit creation unit 45 to the route control unit 52) to the route control unit 52, and the route control unit 52 that has received the activation signal The same operation as that when the activation signal is received from the initial circuit creation unit 45 is performed.
[0058]
As described above, the points (delivery points) included in one route (route of the original cluster) of a plurality of route data received by the route data receiving means (of the first apparatus) by the city affiliation change processing unit 55 And another path (affiliation change) having a predetermined relationship with the selected point (a relationship indicating the highest degree of belonging of the selected points to a cluster other than the cluster stored in the cluster list) And the selected point is moved from the one route to the other route (the selected point included in the one route is removed from the one route and included in the other route). In other words, the selected point belonging to one route is unaffiliated to one route and belongs to another route.) The start route is selected as the one route for the first time, and the next time and before Other pathways or starting points The repeated operation of said selection and said movement (of the one unit) the affiliation change means is configured as the one path. Then, the city affiliation change processing unit 55 determines whether or not the other route (the route of the affiliation change destination cluster) matches the completion route (the route of the provision destination cluster). A determination means is configured. Further, the affiliation changing unit (of the first apparatus) repeatedly operates until it determines that the completion determining unit (of the first apparatus) matches.
Here, the city affiliation change processing unit 55, which is affiliation change means (of the first apparatus), is a point included in the other route or start route (the route of the cluster stored in the cluster list) before the previous time. The point having the highest degree of belonging to the completed route (the route of the cluster to be provided) is selected as the selected point.
Further, the city affiliation change processing unit 55 (affiliation change means) (of the first main apparatus) selects the route other than the other route or start route (the route of the cluster stored in the cluster list) before the previous time. The route showing the highest degree of belonging among the degrees of belonging indicated by the points is selected as the other route (the route of the belonging change destination cluster).
In this case, the selected point is added / subtracted by the affiliation changing means (of the first apparatus) by the random insertion unit 71, and the order of the points belonging to the route in which the change is included is determined to form the route. The route forming means (of the first main apparatus) is configured.
Further, the route data including the route formed by the random insertion unit 71 as the route forming unit (of the first device) is received by the city affiliation change processing unit 55 as the route data receiving unit (of the first device). adjust.
Furthermore, an equalization coefficient that is equalization data that is data indicating variation in load for each path in the path formed by the random insertion unit 71 that is the path forming means (of the first main apparatus) is formed (calculated) (first calculation). The path control unit 52 constitutes the equalized data forming means of this apparatus. Then, the affiliation change processing unit 53 constitutes an equalization data storage unit (of the first apparatus) that stores the equalization coefficient as the equalization data (the affiliation change processing unit 53 is the smallest equalization so far). Memory). Further, the affiliation change processing unit 53 causes the most recent equalization data (equalization coefficient) formed by the equalization data forming means (of the first apparatus) to be stored in the equalization data storage means (of the first apparatus). An improvement determination means (of the first apparatus) is configured to determine whether or not the improvement has been made (in this case, whether or not it is smaller) than the stored past equalization data (equalization coefficient). Yes. If the affiliation change processing unit 53 (improvement determination unit) (of the first device) determines that the improvement has been made, the route formed by the route formation unit (random insertion unit 71) (of the first device) The route data receiving means (city affiliation change processing unit 55) receives the route data (of the first main apparatus) and further adjusts the route.
[0059]
On the other hand, as described above, the affiliation change processing unit 53 that has received the operation rate and the equalization coefficient for each delivery vehicle from the route control unit 52, the received equalization coefficient is the equalization coefficient stored by itself. If it is determined that the equalization coefficient is not stored, and it is determined that none of them is stored (that is, the affiliation change processing unit 53 stores the equalization coefficient and receives the equalization coefficient) When the equalization coefficient is equal to or greater than the stored equalization coefficient), the history check unit 54 issues an activation signal, but the history check unit 54 that has received the activation signal accesses the history storage unit 98. Then, the history relating to the addition / deletion process of the selected point stored in the history storage unit 98 is read and acquired. Then, the history check unit 54 selects the latest history (for example, “provider” indicated by the work number 19 in the case shown in FIG. (Provider cluster: cluster 3), "provider" (provider cluster: cluster 2), "affiliation source" (affiliation source cluster: cluster 3), "affiliation change destination cluster" (affiliation change destination cluster: cluster 2) ), “Delivery point number” (delivery point as a selection point: delivery point 46), hereinafter referred to as “most recent history”), and history other than the most recent history (for example, as shown in FIG. Each of the work numbers 1 to 18 (hereinafter referred to as “other history”) is compared, and it is determined whether or not the same history as the latest history exists in the other history. When the history check unit 54 determines that the same thing as the latest history exists in the other history, the history check unit 54 transmits an activation signal to the affiliation change result setting unit 56. When the history check unit 54 does not determine that the same thing as the most recent history exists in the other history, the history check unit 54 sends an operation rate for each delivery vehicle to the affiliation change processing unit 53 (the affiliation change processing unit 53 controls the route. (A signal received from the unit 52) is transmitted to the city affiliation change processing unit 55. That is, thereafter, the affiliation change processing unit 53 that has received the operation rate and the equalization coefficient for each delivery vehicle from the route control unit 52 determines that the received equalization coefficient is greater than the equalization coefficient stored by itself. Or the process performed when it is determined that the equalization coefficient is not stored and is determined to be one of them, and the received equalization coefficient is overwritten and stored. Similar processing is performed.
[0060]
That is, here, the history storage unit 98 constitutes a history storage unit (of the first device) that stores the history of the belonging point changing process of the selected point performed by the affiliation changing unit (of the first device). Then, whether or not the history storage unit (of the first apparatus) stores the same history as the affiliation change process of the most recently selected point by the history check unit 54 (the same as the latest history exists in the other history) Whether or not) the convergence determining unit (of the first apparatus) is configured (in this case, the improvement determining means (of the first apparatus) determines that the latest equalized data has been improved). If not, the history check unit 54, which is a convergence determination unit, determines whether or not the same history as the latest history exists in the other history. Further, the history check unit 54, which is a convergence determination unit, stores the same history as the affiliation change process of the latest selected point (the affiliation change process of the selected point related to the latest equalized data) (history storage unit). Is not stored, the route data receiving means (of the first apparatus) receives the route data relating to the route formed by the route forming means (of the first apparatus) and further adjusts the path.
[0061]
As described above, the history check unit 54 determines that the same history as the latest history exists in the other history, and the affiliation change result setting unit 56 that has received the activation signal issued by the history check unit 54 stores the history change unit in the history storage unit 98. The history relating to the addition / deletion processing of the selected point stored in the history storage unit 98 is read and acquired, and the equalization coefficient of each history is calculated using the operating rate of each delivery vehicle included in each history. Next, the affiliation change result setting unit 56 selects a tour that gives the smallest value among the equalization coefficients calculated for each history, and transmits the selected tour to the route storage unit 97 to transmit the selected route to the route storage unit 97. Remember me.
Thereafter, the affiliation change result setting unit 56 issues an activation signal to the operation rate adjustment unit 61 (operation rate adjustment control unit 63).
[0062]
FIG. 15 is a detailed functional block diagram for explaining the operation of the operation rate adjusting unit 61. With reference to FIG. 15, the detailed structure of the operation rate adjustment part 61 is demonstrated.
The operating rate adjustment unit 61 functionally includes an operating rate adjustment control unit 63, a change trial unit 65, and a result output unit 67.
First, the operation rate adjustment control unit 63 (route data receiving means (of the second device)) that has received the activation signal from the affiliation change result setting unit 56 is stored in a combination history list described later stored by itself. Delete the contents (deletion is not necessary if nothing is stored in the combination history list).
Next, the operation rate adjustment control unit 63 accesses the initial information storage unit 91 to read out and acquire the constraint condition (FIG. 3C) stored in the initial information storage unit 91 (used for calculating the operation rate described later). Further, the route storage unit 97 is accessed to read out and acquire the circuit stored in the route storage unit 97 (the one selected by the affiliation change result setting unit 56 as the circuit that gives the smallest equalization coefficient).
Then, the operating rate adjustment control unit 63 transmits the read and acquired tour to the tour time calculation unit 75.
[0063]
The traveling time calculation unit 75 that has received the tour from the operation rate adjustment control unit 63 reads out and acquires the distance table stored in the required time storage unit 99, and determines the traveling distance for each cluster of the tour circuit in the distance table. Calculate from The calculated traveling distance for each cluster according to the traveling circuit is transmitted from the traveling time calculation unit 75 to the operation rate adjustment control unit 63.
The operating rate adjustment control unit 63 that has received the traveling distance for each cluster according to the traveling circuit from the traveling time calculation unit 75, the received traveling distance for each cluster, and the constraints read and acquired from the initial information storage unit 91. The operating rate for each cluster is calculated using the conditions (FIG. 3 (c)) (Note that the operating rate is the traveling distance for each cluster, as described above, for the delivery vehicle in charge of the cluster. Constraints (the quotient divided by FIG. 3 (c), all here 10000).
Next, the operation rate adjustment control unit 63 determines the order in which the operation rate for each cluster calculated above is large, and arranges the cluster numbers in the descending order (for example, the operation rate for each cluster is cluster 3> cluster). If 0> cluster 2> cluster 1, then “3, 0, 2, 1”.) The arranged cluster numbers (for example, “3, 0, 2, 1”) are referred to as “aligned cluster numbers”.
[0064]
Thereafter, the operation rate adjustment control unit 63 deletes the contents stored in a candidate list (described later) stored by itself (the deletion is unnecessary if nothing is stored in the candidate list).
Next, the operation rate adjustment control unit 63 determines the cluster (here, the cluster) indicated by the cluster number located at the head of the aligned cluster number (“3” when the aligned cluster number is “3, 0, 2, 1”). 3) is selected as the operation rate adjustment provider cluster.
Furthermore, the operation rate adjustment control unit 63 selects one of the delivery points belonging to the operation rate adjustment providing source cluster as the change candidate delivery point p. As will be described later, each of the delivery points belonging to the operation rate adjustment providing source cluster is set as the change candidate delivery point p and the following processing is performed until all the delivery points belonging to the operation rate adjustment providing source cluster become the change candidate delivery point p. I do. Specifically, here, the delivery point located at the beginning of the route of the operation rate adjustment providing source cluster is first selected as the first change candidate delivery point p, and then the delivery point is selected in the order of the route, Select and process to the last delivery point on the circuit.
[0065]
Then, the operation rate adjustment control unit 63 selects one cluster from all the clusters as the operation rate adjustment provision destination cluster. Here, the one with the smallest cluster number, that is, cluster 0 is selected first. As will be described later, the following processing is performed with each existing cluster as an operation rate adjustment provision destination cluster, and processing is performed until all existing clusters are processed as operation rate adjustment provision destination clusters. Specifically, the cluster with the smallest cluster number (here, cluster 0) is first selected as the operation rate adjustment provision destination cluster first, and then the operation rate adjustment provision destination cluster is selected in the order of the cluster number. Yuki (cluster 1, cluster 2,...), The cluster having the largest cluster number (cluster 3 in this case) is selected and processed.
[0066]
Thereafter, the operation rate adjustment control unit 63 determines whether or not the operation rate adjustment providing source cluster and the operation rate adjustment providing destination cluster match, and if it is determined that the both clusters match, the operation rate adjustment rate is determined. The adjustment control unit 63 selects the next cluster as the operation rate adjustment provision destination cluster (note that all clusters have already been selected as the operation rate adjustment provision destination cluster, and other clusters have been selected as the operation rate adjustment provision destination cluster. If not, the next delivery point is selected as the change candidate delivery point p.)
When the operating rate adjustment control unit 63 determines that the operating rate adjustment providing source cluster and the operating rate adjustment providing destination cluster do not match, the operating rate adjustment control unit 63 reads and acquires the route from the route storage unit 97. Is transmitted to the change trial unit 65.
[0067]
The change trial unit 65 that has received the circuit from the operation rate adjustment control unit 63 changes the affiliation of the change candidate delivery point p from the operation rate adjustment providing source cluster (route) to the operation rate adjustment providing destination cluster (route). The change trial unit 65 reads and acquires the distance table stored in the required time storage unit 99 and calculates the cyclic distance difference. A method of calculating the traveling distance difference will be described with reference to FIG. FIG. 16A shows a state before changing the affiliation of the change candidate delivery point p, and FIG. 16B shows a state after changing the affiliation of the change candidate delivery point p. In FIG. 16, the operation rate adjustment providing source cluster (route) is indicated as cluster (A) (route), the operation rate adjustment providing destination cluster (route) is indicated as cluster (b) (route), a, point b, point c, and point d indicate delivery points. In the example of FIG. 16, as the affiliation of the change candidate delivery point p moves from cluster (b) to cluster (b) as shown in (a) to (b), the cyclic distance difference is ((ap + bp−ab)). -(Cp + dp-cd)).
As described above, each location included in the plurality of route data received by the route data receiving means (of the second apparatus) (operation rate adjustment control unit 63) by the operation rate adjustment control unit 63 and the change trial unit 65. Changes in load (distance) of all routes that occur when a point (delivery point) belongs to a route that does not include the point (delivery point) (route of the operation rate adjustment provision destination cluster) (cyclic distance difference) The total load evaluation means (of the second apparatus) is configured.
[0068]
The change trial unit 65 determines whether or not the cyclic distance difference is a positive value (if the cyclic distance difference is a positive value, the change candidate delivery point p is changed from the operation rate adjustment providing source cluster to the operation rate adjustment providing destination cluster. Changing the affiliation indicates that the traveling distance will be shorter.) If the traveling distance difference is determined to be a positive value, the operation rate adjustment providing source cluster, the operation rate adjustment providing destination cluster, and the change candidate delivery at that time The change trial unit 65 transmits information (change candidate data) associated with the delivery point as the point p and the data of the traveling distance difference to the operation rate adjustment control unit 63.
The operating rate adjustment control unit 63 that has received information relating to the data of the operating rate adjustment providing source cluster, the operating rate adjustment providing destination cluster, the delivery point as the change candidate delivery point p, and the traveling distance difference from the change trial unit 65, The related information is stored as a candidate list (additionally stored, not overwritten). At this time, the candidate list is stored in descending order of the difference in the cyclic distance included in the related information. That is, the change in the load (distance) evaluated by the overall load evaluation means (of the second main apparatus) reduces the load (the distance is shorter) than before the location (delivery point) is changed. The point where the affiliation is changed (delivery point) and the point where the affiliation is changed (delivery point) is the route to which the affiliation belongs before the affiliation is changed. The association between the rate adjustment providing source cluster and the operation rate adjustment providing destination cluster, which is the post-affiliation route that is the route to which the affiliation is changed, is stored as change candidate data ( The load change storage means (of the second apparatus) is configured by a candidate list of the operation rate adjustment control unit 63. Further, here, the change candidate data indicates a reduction in the traveling distance difference indicating how much the sum of the loads (distances) of all routes is reduced as compared to the point (delivery point) before the change. Are stored in an associated state.
In the case where the change trial unit 65 does not determine that the cyclic distance difference is a positive value, the change trial unit 65 issues a signal instructing the operation rate adjustment control unit 63 to select the next cluster as the operation rate adjustment providing destination cluster. .
[0069]
After receiving a signal instructing to select the next cluster or storing the related information as a candidate list, the operation rate adjustment control unit 63 selects the next cluster as the operation rate adjustment providing cluster ( If all the clusters have already been selected as the operation rate adjustment provision destination cluster and other clusters cannot be selected as the operation rate adjustment provision destination cluster, the next delivery point is selected as the change candidate delivery point p. ). Thereafter, the operation rate adjustment control unit 63 of the above-described processing is repeated from the operation of determining whether or not the operation rate adjustment providing source cluster and the operation rate adjustment providing destination cluster match.
[0070]
As described above, when all the clusters are selected as the operation rate adjustment provision destination cluster and the above processing is performed (all the clusters are already selected as the operation rate adjustment provision destination cluster, and the other clusters are When the adjustment provision destination cluster cannot be selected), the operation rate adjustment control unit 63 selects the next delivery point of the operation rate adjustment supply source cluster (out of the delivery points excluding the delivery point already selected as the change candidate delivery point p). The delivery point located at the head in the circuit is selected as the next change candidate delivery point p, and the operation rate adjustment control unit 63 repeats the operation of selecting the operation rate adjustment providing destination cluster in the above-described processing.
In this way, the operating rate adjustment control unit 63 sequentially selects the delivery points of the operating rate adjustment providing source cluster as the change candidate delivery points p, and the operating rate adjustment control unit 63 selects the operating rate adjustment providing destination cluster in the above processing. By repeating from the operation to be selected, all of the delivery points of the operation rate adjustment providing source cluster are selected as the change candidate delivery points p and the operation is performed, so that the delivery that is no longer selected as the change candidate delivery points p. When the operation rate adjustment control unit 63 determines that the point does not exist in the operation rate adjustment providing source cluster, the operation rate adjustment control unit 63 is selected as the operation rate adjustment providing source cluster in the next cluster (aligned cluster number). The next cluster after the current cluster) is selected as the availability adjustment provider cluster. Thereafter, the operation rate adjustment control unit 63 repeats the operation after selecting the delivery point belonging to the operation rate adjustment providing source cluster as the change candidate delivery point p among the operations described above.
[0071]
Similarly, the operation rate adjustment control unit 63 sequentially selects clusters as the operation rate adjustment providing source cluster, and the operation rate adjustment control unit 63 selects one of the delivery points belonging to the operation rate adjustment providing source cluster in the above-described processing. By repeating the operation after selecting the change candidate delivery point p, all the clusters are selected as the operation rate adjustment providing source cluster, and the operation is performed, so that it is no longer selected as the operation rate adjustment providing source cluster. When the operation rate adjustment control unit 63 determines that no cluster exists, the operation rate adjustment control unit 63 performs candidate check described below.
[0072]
The candidate check is a candidate list (operating rate adjustment providing source cluster, working rate adjustment providing destination cluster, delivery point serving as a change candidate delivery point p, information relating to the traveling distance difference data (hereinafter referred to as the operating rate adjustment control unit 63). , “Candidates”) are stored in order starting from the one with the largest difference in the cyclic distance.) And the affiliation that the operation rate adjustment control unit 63 has and has been performed so far as described later. Affiliation change history (operation rate adjustment providing source cluster, operation rate adjustment providing destination cluster, change candidate delivery point p delivery point, patrol distance, operation rate of each delivery vehicle stored in the history list storing the change history The operation rate adjustment control unit 63 compares the operation rate adjustment providing source cluster, the operation rate adjustment providing destination cluster, the delivery point that is the change candidate delivery point p, Same operation If there is an affiliation change history including the adjustment providing source cluster, the operation rate adjustment providing destination cluster, and the delivery point that is the change candidate delivery point p, the operation rate adjustment control unit 63 deletes the candidate from the candidate list. Check for candidates. The candidate check is performed until there are no unchecked candidates in the candidate list, and then the operation rate adjustment control unit 63 determines whether or not there is a candidate in the candidate list. The candidate at the head is extracted, and the cluster to which the delivery point belongs is changed according to the candidate (that is, the delivery point corresponding to the change candidate delivery point p indicated in the head candidate is adjusted from the operating rate adjustment providing source cluster. To change the affiliation to the destination cluster, specifically, the operation rate adjustment control unit 63 operates except for the change candidate delivery point p from the operation rate adjustment supply source cluster in the circuit read from the route storage unit 97. The change candidate delivery point p is added to the rate adjustment provision destination cluster.). When the operation rate adjustment control unit 63 does not determine that there are candidates remaining in the candidate list, the operation rate adjustment control unit 63 sends a circuit (tour circuit read and acquired from the path storage unit 97) and history to the result output unit 67. Send list and.
Therefore, here, the operation rate adjustment control unit 63 extracts the change candidate data stored in the load change storage means (of the second apparatus) that matches a predetermined condition (of the second apparatus). Means are configured. Note that here, as described above, the change candidate data indicates how much the sum of the loads (distances) of all routes is reduced as compared to before the location (delivery point) is changed. The data of the degree of the cyclic distance difference is stored in a further associated state, and the predetermined condition when the extraction means (of the second apparatus) extracts is the condition that the reduction degree is the maximum. . Further, here, the operation rate adjustment control unit 63 has a change candidate history storage unit (of the second device) that stores the history of change candidate data extracted by the extraction unit (of the second device) (second device). It is composed of a history list (of this device), and the extraction means (of the second device) is stored in the load change storage means (candidate list of the operation rate adjustment control unit 63) (of the second device). The change history data is extracted from the change history data excluding the same data as the history stored in the change candidate history storage means (of the second apparatus).
[0073]
As described above, the operation rate adjustment control unit 63 determines that there are candidates remaining in the candidate list, and after changing the cluster to which the delivery point belongs according to the candidate located at the head among the remaining candidates, the operation rate The delivery point included in each of the adjustment providing source cluster and the operation rate adjustment providing destination cluster (the delivery point as the change candidate delivery point p is excluded from the former and the latter is joined) is transmitted to the random insertion unit 71. .
Upon receiving the delivery points included in each of the clusters, the random insertion unit 71 accesses the initial information storage unit 91 and stores the coordinates of the delivery points stored in the initial information storage unit 91 (FIG. 3A) and the depot. The coordinates (FIG. 3B) are read out and acquired, the required time storage unit 99 is accessed, and the distance table stored in the required time storage unit 99 is read out and acquired for each cluster according to both of the circular routes. A circuit that circulates all delivery points belonging to the cluster starting from the depot assigned to the cluster is created by the above-described random insertion method and transmitted to the operation rate adjustment control unit 63.
[0074]
The operation rate adjustment control unit 63 that has received the tour from the random insertion unit 71 transmits the received tour to the N-opt unit 73.
The N-opt unit 73 that has received the circuit from the operation rate adjustment control unit 63 accesses the initial information storage unit 91 and coordinates of the delivery point stored in the initial information storage unit 91 (FIG. 3A). And the coordinates of the depot (FIG. 3B) are read and acquired, and the required time storage unit 99 is accessed to read and acquire the distance table (see FIG. 5) stored in the required time storage unit 99. Using the coordinates of the delivery point (FIG. 3 (a)), the coordinates of the depot (FIG. 3 (b)), and the distance table, the circuit (both the operation rate adjustment providing source cluster and the operation rate adjustment providing destination cluster) The above-described N-opt method is applied to (circulation circuit) to improve the circuit (for each cluster), and the improved circuit is transmitted to the operation rate adjustment control unit 63.
As described above, here, the random insertion unit 71 and the N-opt unit 73 form a route according to the change candidate data extracted by the extraction unit (of the second device) (the second device). Forming means are configured.
The operating rate adjustment control unit 63 that has received the improved tour from the N-opt unit 73 transmits the improved tour to the tour time calculation unit 75.
The traveling time calculation unit 75 that has received the improved traveling circuit from the operation rate adjustment control unit 63 reads out and acquires the distance table stored in the required time storage unit 99, and for each cluster of the improved traveling circuit. Is calculated from the distance table. The calculated traveling distance for each cluster is transmitted from the traveling time calculation unit 75 to the operation rate adjustment control unit 63.
[0075]
The operating rate adjustment control unit 63 that has received the traveling distance for each cluster from the traveling time calculation unit 75 and the traveling distances of all the clusters, the constraint condition read and acquired from the initial information storage unit 91 (FIG. 3C), and , The operation rate for each cluster is calculated. Further, the operation rate adjustment control unit 63 calculates an equalization coefficient using the calculated operation rate of each cluster.
Thereafter, the operation rate adjustment control unit 63 belongs to its own history list, and belongs to the change history (operation rate adjustment providing source cluster, operation rate adjustment providing destination cluster, change candidate delivery point p, delivery point, traveling distance, each delivery vehicle's The operation rate and the equalization coefficient are stored) and the circuit (the improved circuit received from the N-opt unit 73 as described above) is written to the path storage unit 97 and the operation is performed. The processing of the rate adjustment unit 61 is performed from the beginning (specifically, the operation rate adjustment control unit 63 deletes the contents stored in its own history list).
Thus, the route data including the route formed by the route forming unit (of the second main device) is received by the route data receiving unit (of the second main device), and the route is further adjusted. In this case, the route data including the route formed by the route forming unit (of the second device) is extracted from the second unit until the extracting unit (of the second device) cannot extract the change history data. The route data receiving means (of the device) receives and further adjusts the route.
[0076]
As described above, the operation rate adjustment control unit 63 checks candidates and receives the tour and history list issued by the operation rate adjustment control unit 63 when it is not determined that candidates remain in the candidate list. The result output unit 67 extracts all of the affiliation change histories in the received history list that have an operation rate of 1 or less and the minimum traveling distance, and finally ends the circuit corresponding to the extracted affiliation change histories. Output as a decision circuit by a predetermined method (printing, display on a display, etc.).
The result output unit 67 obtains the final decision circuit as follows (1) to (4). That is, first, (1) the result output unit 67 includes the affiliation change history (operation rate adjustment providing source cluster, operation rate adjustment providing destination cluster, change candidate delivery point p included in the history list received from the operation rate adjustment control unit 63. Among the delivery points, the traveling distance, the operating rate of each delivery vehicle, and the equalization coefficient), the operating rate is all 1 or less and the traveling distance is the minimum (hereinafter referred to as “target affiliation change history”) .) Is extracted. Next, (2) the result output unit 67 uses the history list received from the operation rate adjustment control unit 63 and the tour route received from the operation rate adjustment control unit 63 to each cluster corresponding to the target affiliation change history. Create a list of delivery points belonging to. Specifically, the circuit received from the operation rate adjustment control unit 63 shows the state after the most recent affiliation change of the history list received from the operation rate adjustment control unit 63, so the latest history list List of delivery points belonging to each cluster corresponding to the target affiliation change history (specifically, delivery points belonging to each cluster) (Numbers listed) are created. (3) The result output unit 67 transmits a list of delivery points belonging to each cluster corresponding to the target affiliation change history obtained in (2) above to the random insertion unit 71. The insertion unit 71 creates a tour according to the list of delivery points (in accordance with the delivery point list, a tour that travels around all delivery points belonging to the cluster starting from the depot assigned to each cluster is randomly selected. Created by the insertion method.) The random insertion unit 71 transmits the created tour to the result output unit 67. Finally, (4) the result output unit 67 that has received the tour from the random insertion unit 71 transmits the received tour to the N-opt unit 73, and the N-opt unit 73 receives the tour as before. The N-opt method is applied to the road (for each cluster) to improve the circuit. The N-opt unit 73 transmits the improved tour to the result output unit 67.
[0077]
Next, the operation of the apparatus 11 will be described.
FIG. 17 is a flowchart showing the operation of the cluster dividing unit 31 of the apparatus 11. With reference to FIG. 17, the operation of the cluster dividing unit 31 of the apparatus 11 will be described.
First, the file reading unit 33 activated by an activation signal or the like accesses the initial information database 21 to read the coordinates of the delivery point (FIG. 3A), and the file reading unit 33 further reads the coordinates of the read delivery point. Is written and stored in the initial information storage unit 91 (s301). Next, the file reading unit 33 accesses the initial information database 21 to read the coordinates of the depot (FIG. 3B), and the file reading unit 33 writes and stores the coordinates of the read depot in the initial information storage unit 91. (S302). Then, the file reading unit 33 accesses the initial information database 21 and reads the constraint condition (FIG. 3C), and the file reading unit 33 writes and stores the read constraint condition in the initial information storage unit 91 (s303). ).
Thereafter, the file reading unit 33 issues an activation signal to the table initialization unit 35 (s304).
[0078]
The table initialization unit 35 that has received the activation signal issued in s304 from the file reading unit 33 accesses the initial information storage unit 91 and coordinates of the delivery point stored in the initial information storage unit 91 (FIG. 3). (A)) and the coordinates of the depot (FIG. 3B) are read out and acquired (s305), and the coordinates of the delivery point read out and acquired in s305 (FIG. 3A) and the coordinates of the depot (FIG. 3B). )) To calculate the distance from each of the 52 locations (origin) of delivery points 0 to 47 and depots 0 to 3 to 51 locations (end points) excluding itself (start point). Are collected as a two-dimensional distance table as shown in FIG. 5 (s306).
Further, the table initialization unit 35 writes and stores the two-dimensional distance table created in s306 as shown in FIG. 5 in the required time storage unit 99 (s307). Thereafter, the table initialization unit 35 issues an activation signal to the cluster number calculation unit 37 (s308).
[0079]
The cluster number calculation unit 37 that has received the activation signal issued in s308 from the table initialization unit 35 transmits an activation signal that instructs the random insertion unit 71 to perform random insertion to the random insertion unit 71 (s309).
The random insertion unit 71 that has received the activation signal transmitted in s309 accesses the initial information storage unit 91 to read out and acquire the coordinates of the delivery point stored in the initial information storage unit 91 (FIG. 3A). At the same time, the required time storage unit 99 is accessed, and the distance table (see FIG. 5) stored in the required time storage unit 99 is read and acquired. Then, the random insertion unit 71 uses the read and acquired delivery point coordinates and the distance table to perform a tour (that is, the order in which all delivery points are visited by the random insertion method. Specifically, according to the order in which the delivery points are visited. The number of delivery points is arranged) and the circuit is transmitted to the cluster number calculation unit 37 (s310).
[0080]
Upon receiving the tour created by the random insertion unit 71 in s310, the cluster number calculation unit 37 transmits the tour to the N-opt unit 73 (s311).
The N-opt unit 73 that has received the circuit transmitted from the cluster number calculation unit 37 in s311 accesses the initial information storage unit 91 and coordinates of the delivery point stored in the initial information storage unit 91 (see FIG. 3 (a)) is read and acquired, and the required time storage unit 99 is accessed to read and acquire the distance table (see FIG. 5) stored in the required time storage unit 99, and the coordinates of these delivery points (FIG. 3). (A)) and the distance table are used to apply the N-opt method (here, 2-opt method) to the received circuit to improve the received circuit, and the improved improved circuit (The order in which the delivery points are circulated) is transmitted to the cluster number calculation unit 37 (s312).
The cluster number calculation unit 37 that has received the improved tour transmitted from the N-opt unit 73 in s312 transmits the improved tour to the tour time calculation unit 75 (s313). The traveling time calculation unit 75 that has received the improved tour transmitted in s313 reads out and acquires the distance table stored in the required time storage unit 99, calculates the total distance of the improved tour from the distance table, The calculated total distance of the improvement circuit is transmitted to the cluster number calculation unit 37 (s314).
[0081]
The cluster number calculation unit 37 that has received the total distance of the improved tour transmitted in s314 from the tour time calculation unit 75 accesses the initial information storage unit 91 and stores the constraint conditions (see FIG. 3 (c)) is read out and acquired, and the number of vehicles is calculated using the read and acquired constraint conditions (s315). As described above, the number of vehicles is calculated based on the total distance of the improved circuit received from the traveling time calculation unit 75 (transmitted from the traveling time calculation unit 75 in s314) as the constraint condition for each delivery vehicle. This is done by rounding up the fractional part of the quotient divided by the arithmetic mean value of.
Then, the cluster number calculation unit 37 transmits the number of vehicles calculated in s315 to the vehicle number storage unit 93 and stores it in the vehicle number storage unit 93 (s316).
Thereafter, the cluster number calculation unit 37 issues an activation signal to the provisional circuit formation unit 41 (a fuzzy clustering calculation unit 43 described later) (s317; after s317, the process proceeds to s401 described later).
[0082]
18 and 19 are flowcharts showing the operation of the provisional circuit forming unit 41 of the apparatus 11. With reference to FIGS. 18 and 19, the operation of the provisional circuit forming unit 41 of the present apparatus 11 will be described.
First, referring to FIG. The fuzzy clustering calculation unit 43 that has received the activation signal issued in s317 from the cluster number calculation unit 37 accesses the vehicle number storage unit 93 and stores the number of vehicles stored in the vehicle number storage unit 93 (here, 4). ) And the initial information storage unit 91 is accessed and the coordinates of the delivery point (FIG. 3A) stored in the initial information storage unit 91 are read and acquired (s401). Then, the fuzzy clustering calculation unit 43 calculates the degree of attribution of each delivery point to each cluster using the number of vehicles read and acquired in s401 (here, 4) as the number of clusters (s402). This fuzzy clustering processing method is a known technique as described above, and is described in detail, for example, in Japanese Patent Laid-Open No. 05-274293.
Then, the fuzzy clustering calculation unit 43 transmits the degree of belonging to each cluster of each delivery point calculated in s402 (FIG. 8) to the cluster attribute value storage unit 95 to be stored in the cluster attribute value storage unit 95, and also in s402. The degree of belonging to each cluster of each delivery point calculated in (8) is transmitted to the initial circuit creation unit 45 (s403).
[0083]
The initial circuit creation unit 45 that has received the degree of attribution of each delivery point (FIG. 8) transmitted from the fuzzy clustering calculation unit 43 in s403 belongs to the cluster with the highest degree of attribution for each delivery point. Judgment is made and it is determined to which cluster all delivery points belong (s404). Then, the initial circuit creation unit 45 creates a delivery point number list in which the numbers of delivery points belonging to each cluster as shown in FIG. 10 are described for each cluster, and the delivery point number list is stored in the route storage unit 97. And stored in the route storage unit 97 (s405).
[0084]
Next, the initial circuit creation unit 45 accesses the initial information storage unit 91, reads out and acquires the coordinates of the delivery point stored in the initial information storage unit 91 (FIG. 3A), and has created it. The center of gravity position (X, Y) of each cluster is obtained using the delivery point number list and the coordinates of the delivery point read and acquired (s406).
Further, the initial circuit creation unit 45 accesses the initial information storage unit 91 to read out and acquire the coordinates of the depot stored in the initial information storage unit 91 (FIG. 3B), and obtain each of the previously obtained values. A depot is assigned to each cluster by selecting a depot closest to the center of gravity of the cluster (s407). Thereafter, the initial circuit creation unit 45 accesses the route storage unit 97 and writes the depot assigned to each cluster in the delivery point number list stored in the route storage unit 97 as shown in FIG. 11 (s408).
Thereafter, the initial circuit creation unit 45 transmits the delivery point number list (the one shown in FIG. 11 in which the allocation depot is described) already owned to the random insertion unit 71 (s409).
[0085]
The random insertion unit 71 that has received the delivery point number list transmitted from the initial circuit creation unit 45 in s409 accesses the initial information storage unit 91 and coordinates of the delivery point stored in the initial information storage unit 91 ( 3A) and the coordinates of the depot (FIG. 3B) are read and acquired, and the distance table stored in the required time storage unit 99 by accessing the required time storage unit 99 (see FIG. 5). Is read and acquired. Then, the random insertion unit 71 uses the coordinates of the read delivery point, the coordinates of the depot, and the distance table as a starting point for the depot assigned to each cluster in the received delivery point number list. A circuit that circulates all delivery points belonging to the cluster (initial circuit by cluster) is created by the random insertion method described above, and the initial circuit by cluster is transmitted to the initial circuit creation unit 45 (s410).
The initial circuit creation unit 45 that has received the cluster initial circuit transmitted from the random insertion unit 71 in s410 transmits the cluster initial circuit to the N-opt unit 73 (s411).
In step S411, the N-opt unit 73 that has received the initial cluster-by-cluster circuit transmitted from the initial circuit creation unit 45 accesses the initial information storage unit 91 to determine the delivery point stored in the initial information storage unit 91. The coordinates (FIG. 3 (a)) and the coordinates of the depot (FIG. 3 (b)) are read and acquired, and the required time storage unit 99 is accessed to store the distance table (FIG. 5). (Refer to FIG. 3 (a)), the coordinates of the depot (FIG. 3 (b)), and the distance table, the above-described N-opt method is applied to the initial circuit for each cluster. It is applied (for each cluster) to improve the initial circuit for each cluster, and the improved initial circuit for each cluster (improved cluster-specific initial circuit) is transmitted to the initial circuit creation unit 45 (s412).
The initial circuit creation unit 45 that has received the improved cluster-specific initial circuit transmitted in s 412 accesses the route storage unit 97 and delivers the delivery point number of the delivery point belonging to the delivery point number list stored in the route storage unit 97. Is rewritten to the order according to the initial circuit for each improved cluster (s413) (the above, FIG. 18).
[0086]
Next, the process moves to FIG. After s413, the initial circuit creation unit 45 transmits the initial cluster circuit for each improved cluster to the tour time calculation unit 75 (s414). The traveling time calculation unit 75 that has received the improved cluster-specific initial circuit transmitted in s414 reads out and acquires the distance table stored in the required time storage unit 99, and displays each cluster indicated in the improved cluster-based initial circuit. The traveling distance for each cluster is calculated from the distance table, and the calculated traveling distance for each cluster is transmitted to the initial traveling circuit creation unit 45 (s415).
The initial circuit creation unit 45 that has received the cyclic distance for each cluster according to the improved initial circuit for each cluster transmitted in s415 accesses the initial information storage unit 91, and the initial information storage unit 91 stores the initial distance. The restriction condition of the vehicle corresponding to the depot used in the initial circuit for each improved cluster is read out and acquired from the restriction condition (FIG. 3 (c)), and the read restriction condition (one day for each delivery vehicle) A total value of the maximum movable distance is calculated (s416). Then, the initial cyclic circuit creation unit 45 calculates the total of the cyclic distances received for each cluster (s417). Thereafter, the initial circuit creation unit 45 determines whether or not the total value of the constraint conditions is equal to or greater than the total value of the cyclic distance (s418), and if so (YES), determines that the initial circuit for each improved cluster is appropriate. Then, an activation signal is issued to the affiliation adjusting unit 51 (s419. After s419, the process goes to s501 described later). If the total value of the constraints is not greater than or equal to the total value of the cyclic distances in s418 (NO), the initial circuit creation unit 45 does not determine that this improved initial cluster circuit is appropriate, and the fuzzy clustering calculation unit 43 A signal for adding 1 to the number of vehicles (vehicle increase signal) is issued (s420). After s420, the initial circuit creation unit 45 transmits the same signal as the activation signal issued from the cluster number calculation unit 37 to the fuzzy clustering calculation unit 43 (s421). After s421, the process returns to s402 again (that is, the process after s402 is performed by the number of vehicles increased by 1 from the number of vehicles used for the process after the previous s402).
[0087]
20 to 22 are flowcharts illustrating the operation of the affiliation adjustment unit 51 of the apparatus 11. The operation of the affiliation adjustment unit 51 of the apparatus 11 will be described with reference to FIGS.
First, refer to FIG. The path control unit 52 that has received the activation signal issued in step s419 from the initial circuit creation unit 45 accesses the initial information storage unit 91 and stores the constraint conditions stored in the initial information storage unit 91 (FIG. 3 (c )) Is read and acquired (used to calculate the operation rate described later), the required time storage unit 99 is accessed, the distance table stored in the required time storage unit 99 is read and acquired, and the route storage unit 97 is further accessed. The initial route for each improved cluster stored in the route storage unit 97 is read and acquired (s501).
Next, the path control unit 52 calculates the cyclic distance for each cluster in the improved initial cluster circuit by using the distance table and the initial cluster circuit by improved cluster (s502).
Then, the route control unit 52 calculates the operation rate for each delivery vehicle (s503). As described above, the operating rate is calculated as a quotient obtained by dividing the traveling distance for each cluster by the restriction condition of the delivery vehicle in charge of the cluster (FIG. 3C, here, all 10000).
Furthermore, the route control unit 52 obtains an average value (arithmetic) of the operation rate for each delivery vehicle, and calculates an equalization coefficient using the average value (s504). As described above, the equalization coefficient is the absolute value of (the operation rate of the delivery vehicle−the average value of the operation rate) for each delivery vehicle (ie, | (operation rate of each delivery vehicle) − (operation rate (Average value) |) is calculated by adding the absolute values obtained for all delivery vehicles to obtain a total value and dividing the total value by the number of delivery vehicles (ie, equalization coefficient = Σ (| (operating rate of each delivery vehicle) − (average value of operating rate) |) / (number of delivery vehicles))
Finally, the route control unit 52 transmits the operation rate and the equalization coefficient for each delivery vehicle calculated as described above to the affiliation change processing unit 53 (s505).
[0088]
The affiliation change processing unit 53 that has received the operation rate and the equalization coefficient for each delivery vehicle transmitted from the route control unit 52 in s505 stores the received equalization coefficient by itself (the affiliation change processing unit 53). If it is smaller than the equalization coefficient that is being used, or if it is determined that it (self-affiliation change processing unit 53) does not store the equalization coefficient (s506), and if it is determined that it is either (YES) After overwriting and storing the received equalization coefficient (s507) (that is, the affiliation change processing unit 53 stores the smallest equalization coefficient received from the path control unit 52 so far) The operation rate for each delivery vehicle received from the route control unit 52 is transmitted to the city affiliation change processing unit 55 (s550). On the other hand, the affiliation change processing unit 53 is not either whether the equalization coefficient received in s506 is smaller than the equalization coefficient stored by itself or does not store the equalization coefficient by itself. (NO) (that is, when the affiliation change processing unit 53 stores the equalization coefficient and the received equalization coefficient is equal to or greater than the stored equalization coefficient) An activation signal is issued to the check unit 54 (s551).
[0089]
The city affiliation change processing unit 55 that has received the operation rate for each delivery vehicle transmitted from the affiliation change processing unit 53 in s550 accesses the initial information storage unit 91 and stores the delivery points stored in the initial information storage unit 91. The coordinates (FIG. 3 (a)) and the coordinates of the depot (FIG. 3 (b)) are read out and acquired, the cluster attribute value storage unit 95 is accessed, and each delivery point stored in the cluster attribute value storage unit 95 is stored. The degree of belonging to each cluster (FIG. 8) is read and acquired, and the route storage unit 97 is accessed to read and acquire the initial circuit for each improved cluster stored in the route storage unit 97 (s508).
Next, the city affiliation change processing unit 55 stores the cluster handled by the delivery vehicle that gives the highest operation rate among the operation rates for each delivery vehicle received from the affiliation change processing unit 53 as a cluster of the provider. It is also stored in the cluster list (the storage area of the city affiliation change processing unit 55 itself) (s509). Furthermore, the city affiliation change processing unit 55 stores, as the provision destination cluster, the cluster handled by the delivery vehicle that gives the lowest operation rate among the operation rates for each delivery vehicle received from the affiliation change processing unit 53 (s510). ).
[0090]
After that, the city affiliation change processing unit 55 provides the provision destination among the delivery points belonging to the clusters stored in the cluster list (obtained from the initial circuit for each improved cluster (FIG. 11) read and acquired as described above). (S511) (The degree of membership of each delivery point is the degree of membership of each delivery point read and acquired as described above (see FIG. 8). ) Is used.) When a plurality of clusters are stored in the cluster list, a selection point is selected from all delivery points belonging to the plurality of clusters (for example, three clusters of cluster 50, cluster 63, and cluster 78 are cluster clusters). In the case of being stored in the list, one selection point is selected from all of the delivery points belonging to the cluster 50, the delivery points belonging to the cluster 63, and the delivery points belonging to the cluster 78).
The city affiliation change processing unit 55 stores the cluster to which the selected point belongs as the affiliation source cluster (s512).
Next, the city affiliation change processing unit 55 moves to a cluster other than the clusters stored in the cluster list (if a plurality of clusters are stored in the cluster list, the cluster is not one of the plurality of clusters). The cluster indicating the highest degree of belonging among the degrees of belonging indicated by the selected point is selected and stored as the affiliation change destination cluster (s513).
[0091]
Reference is now made to FIG. After s513, the city affiliation change processing unit 55 deletes the selected points belonging to the affiliation source cluster in the initial circuit for each improved cluster that has been read (from the route storage unit 97 in s508). Then, the selected point is added to the affiliation change destination cluster in the initial circuit for each improved cluster (s514).
After s514, the city affiliation change processing unit 55 transmits to the random insertion unit 71 the improved initial cluster circuit (selected point addition / division circuit) with the selected points deleted and added in s514 (s515).
[0092]
The random insertion unit 71 that has received the selected point addition / departure circuit accesses the initial information storage unit 91 and stores the coordinates of the delivery point (FIG. 3A) stored in the initial information storage unit 91 and the coordinates of the depot (see FIG. 3 (b)) is read out, the required time storage unit 99 is accessed, the distance table stored in the required time storage unit 99 is read out and acquired, and each cluster is assigned to each cluster according to the selected point add / drop circuit. A cyclic circuit (random insertion selection point addition / division circuit) that circulates all delivery points belonging to the cluster from the specified depot as a starting point is created by the random insertion method described above, and the random insertion selection point addition / division circuit is processed to change the city affiliation The data is transmitted to the unit 55 (s516).
The city affiliation change processing unit 55 that has received the random insertion selection point addition / removal circuit from the random insertion unit 71 overwrites and stores the random insertion selection point addition / removal circuit in the route storage unit 97 and also stores the random insertion selection point addition / division circuit. It transmits to the traveling time calculation part 75 (s517).
[0093]
Upon receiving the random insertion selection point addition / division circuit transmitted from the city affiliation change processing unit 55 in s517, the traveling time calculation unit 75 reads out and acquires the distance table stored in the required time storage unit 99, and selects the random insertion. The distance for each cluster of the point addition / division circuit is calculated from the distance table, and the calculated distance for each cluster is transmitted to the city affiliation change processing unit 55 (s518).
Then, the city affiliation change processing unit 55 writes and stores the history related to the addition / removal processing of the selected point in the history storage unit 98 (s519) (the history is additionally written and stored, not overwritten). As described above, the history of selection point addition / deletion processing includes each item of the source cluster, the destination cluster, the affiliation source cluster, the affiliation change destination cluster, the delivery point as the selection point, and the operating rate of each delivery vehicle. Is included.
[0094]
Thereafter, the city affiliation change processing unit 55 determines whether or not the affiliation change destination cluster and the provision destination cluster match (s520). If it does not determine that they match (NO), the affiliation change destination cluster at this time is determined. It is stored in the aforementioned cluster list (s521) (that is, the affiliation change destination cluster at this time is added to the cluster list and becomes a candidate to be selected as the affiliation source cluster for the next processing), and then again s511. Return to.
On the other hand, if the city affiliation change processing unit 55 determines in s520 that the affiliation change destination cluster and the provision destination cluster match (YES), it is included in the list of clusters in the random insertion selection point add / drop circuit ( A circuit of a plurality of clusters (one or two or more clusters) and a destination cluster is read out from the path storage unit 97 (which stores a random insertion selection point addition / division circuit). The route is transmitted to the N-opt unit 73 (s522).
The N-opt unit 73 that has received a cyclic circuit (a part of a random insertion selection point addition / division circuit) related to a plurality of clusters from the city affiliation change processing unit 55 accesses the initial information storage unit 91 and the initial information storage unit 91 The stored coordinates of the delivery point (FIG. 3A) and the coordinates of the depot (FIG. 3B) are read and acquired, and the required time storage unit 99 is accessed and stored in the required time storage unit 99. The distance table (refer to FIG. 5) is read out and acquired, and the coordinates of the delivery points (FIG. 3 (a)), the coordinates of the depot (FIG. 3 (b)), and the distance table are used for each circuit. The N-opt method is applied and improved (for each cluster), and the improved circuit (improved partial random insertion selection point addition / division circuit) is transmitted to the city affiliation change processing unit 55 (s523).
Then, the city affiliation change processing unit 55 that has received the improved partial random insertion selection point addition / removal circuit accesses the route storage unit 97 and improves the improvement of the random insertion selection point addition / removal circuit stored in the route storage unit 97. The part corresponding to the part random insertion selection point addition and removal circuit is rewritten (s524).
Thereafter, the city affiliation change processing unit 55 issues an activation signal (same as the activation signal issued from the initial circuit creation unit 45 to the route control unit 52) to the route control unit 52 (s525), and returns to s501 again.
[0095]
Next, refer to FIG. Upon receiving the activation signal issued by the affiliation change processing unit 53 in s551, the history check unit 54 accesses the history storage unit 98 and reads and acquires the history regarding the selection point addition / deletion processing stored in the history storage unit 98. (S526). Then, the history check unit 54 includes the latest history (for example, “provider” (provider cluster indicated by work number 19 in FIG. : Cluster 3), “Providing destination” (Providing destination cluster: Cluster 2), “Affiliation source” (Affiliation source cluster: Cluster 3), “Affiliation change destination” (Affiliation change destination cluster: Cluster 2), “Delivery point” "Number" (delivery point as selection point: delivery point 46), hereinafter referred to as "nearest history") and histories other than the latest history (for example, work numbers 1 to 18 in the case shown in FIG. 14). (Hereinafter referred to as “other history”) and a determination is made as to whether the same history as the latest history exists in the other history (s527). When the history check unit 54 determines in s527 that the same thing as the latest history exists in the other history, the history check unit 54 transmits an activation signal to the affiliation change result setting unit 56 (s528). When the history check unit 54 does not determine in s527 that the same thing as the latest history exists in the other history (NO), the history check unit 54 notifies the affiliation change processing unit 53 of the operation rate (affiliation change) for each delivery vehicle. The processing unit 53 issues a signal instructing to transmit the data received from the route control unit 52) to the city affiliation change processing unit 55 (s529), and the affiliation change processing unit 53 that has received this signal receives the signal for each delivery vehicle. The operating rate is transmitted to the city affiliation change processing unit 55 (s530), and the process returns to the above-described s550.
[0096]
The affiliation change result setting unit 56 that has received the activation signal issued by the history check unit 54 in s528 accesses the history storage unit 98 and reads the history relating to the addition / deletion processing of the selected point stored in the history storage unit 98. Obtaining and calculating the equalization coefficient of each history using the operating rate of each delivery vehicle included in each history (s531). Next, the affiliation change result setting unit 56 selects a tour that gives the smallest value among the equalization coefficients calculated for each history, and transmits the selected tour to the route storage unit 97 to transmit the selected route to the route storage unit 97. (S532).
Thereafter, the affiliation change result setting unit 56 issues an activation signal to the operation rate adjustment unit 61 (operation rate adjustment control unit 63) (s533), and goes to s601 described later.
[0097]
Here, the above-described FIG. 14 will be described in detail. FIG. 14 shows an example of the history written and stored in the history storage unit 98 in s519. Specifically, when the present apparatus is operated based on the data shown in FIG. The data written in the history storage unit 98 is shown. In FIG. 14, “provider cluster” is indicated at the position of “provider” in the cluster number column (for example, “2” indicates that the cluster of the provider is cluster 2) In the cluster number column, “providing destination” is indicated by “providing destination cluster” (for example, “3” indicates that the providing destination cluster is cluster 3). In the cluster number column, “belonging member cluster” is indicated at the position of “belonging member” (for example, “0” indicates that the belonging member cluster is cluster 0). ), The “affiliation change destination cluster” is indicated at the position of “affiliation change destination” in the cluster number column (for example, “1” indicates that the affiliation change destination cluster is Cluster 1)), "delivery point number""Delivery point as a selection point" is indicated (for example, "46" indicates that the delivery point as a selection point is the delivery point 46), and the "operating rate" In the column, the operating rates of the clusters 0 to 3 are shown (for example, “0.9688” in the column of cluster 1 indicates that the operating rate of cluster 1 is 0.9688. Is shown.) Further, in FIG. 14, work numbers (sequential numbers are given in order from the oldest work) and figure numbers are given for easy explanation and understanding. As for the operation rate, the portion of the operation rate that is the same as the operation rate shown above is omitted for ease of illustration (for example, the operation rates of work numbers 1 and 2 are both clustered). It is the same as 1.056 for 0, 0.9688 for cluster 1, 1.1694 for cluster 2, and 0.4406 for cluster 3.)
[0098]
Next, each history shown in FIG. 14 will be described with reference to FIGS.
First, FIG. 26 illustrates the initial circuit for each improved cluster obtained by the route control unit 52 accessing the route storage unit 97 and reading and acquiring from the route storage unit 97 in s501. The delivery points belonging to the same cluster are connected by a line to clarify the delivery points belonging to the cluster. The depot of each cluster is indicated by ■ (substantially square dot with black interior).
Then, the route control unit 52 calculates the traveling distance for each cluster in the improved initial cluster circuit shown in FIG. 26 in s502, and then calculates the operation rate for each delivery vehicle in s503. Specifically, the operation rate of cluster 0 is calculated as 1.0560, the operation rate of cluster 1 is 0.9688, the operation rate of cluster 2 is 1.1694, and the operation rate of cluster 3 is 0.4406. (Refer to the top column of “operation rate” in FIG. 14).
Further, the route control unit 52 calculates the equalization coefficient in s504, and transmits the operation rate and the equalization coefficient for each delivery vehicle calculated in s504 to the affiliation change processing unit 53 in s505. Here, the equalization coefficient (Σ (| (operating rate of each delivery vehicle) − (average value of operating rate) |) / (number of delivery vehicles)) is (| 1.0560−0.9087 |). /4+|0.9688−0.9087|/4+|1.1694−0.9087|/4+|0.4406−0.9087|/4)=0.2405.
[0099]
The affiliation change processing unit 53 that has received the operating rate and the equalization coefficient for each delivery vehicle transmitted in s505, the received equalization coefficient (here, 0.23405) is the equalization stored by itself. It is determined whether it is smaller than the coefficient, or whether the equalization coefficient is not stored by itself (s506). Here, since the equalization coefficient is not stored by itself, it is determined that it is either one (YES). The received equalization coefficient (here, 0.23405) is overwritten and stored (s507), and then the operation rate for each delivery vehicle received from the route control unit 52 (here, cluster 0: 1.0560, cluster) 1: 0.9688, cluster 2: 1.1694, cluster 3: 0.4406) are transmitted to the city affiliation change processing unit 55 (s550).
The city affiliation change processing unit 55 that has received the operation rate for each delivery vehicle transmitted from the affiliation change processing unit 53 in s550 reads out and acquires necessary data in s508, and accesses the route storage unit 97 to access the route. The initial circuit for each improved cluster (FIG. 26) stored in the storage unit 97 is read and acquired. In s509, the city affiliation change processing unit 55 receives the operation rate (cluster 0: 1.0560, cluster 1: 0.9688, cluster 2: 1.1694, cluster for each delivery vehicle received from the affiliation change processing unit 53. 3: 0.4406), the cluster (cluster 2) handled by the delivery vehicle that gives the highest operating rate (1.1694) is stored as the cluster of the provider, and is also stored in the list of clusters. Furthermore, the city affiliation change processing unit 55 determines the cluster (cluster 3) that the delivery vehicle giving the lowest operation rate (0.4406) out of the operation rates for each delivery vehicle received from the affiliation change processing unit 53, This is stored as a cluster to be provided (s510). Since these are written in the history storage unit 98 in s519 as shown in FIG. 14, 2 is stored as “providing source” and 3 as “providing destination” in the column of work number 1 in FIG. .
[0100]
After that, the city affiliation change processing unit 55 has the delivery point (selected point) having the highest degree of belonging to the cluster (cluster 3) of the delivery destination among the delivery points belonging to the cluster (cluster 2) stored in the cluster list. The delivery point 46 (degree of belonging to the cluster (cluster 3) of the provision destination: 0.16) is selected (s511).
Then, the city affiliation change processing unit 55 stores the cluster 2 to which the delivery point 46 as the selection point belongs as the affiliation source cluster (s512).
Next, the city affiliation change processing unit 55 assigns the degree of membership (cluster 0: cluster 0) indicated by the delivery point 46 to a cluster other than cluster 2 (ie, cluster 0, cluster 1, cluster 3) stored in the cluster list. 0.3, cluster 1: 0.05, cluster 3: 0.16) is selected and stored as the affiliation change destination cluster, with cluster 0 indicating the highest degree of belonging (0.3) (s513).
Since the selected point, the affiliation source cluster, and the affiliation change destination cluster are written in the history storage unit 98 in s519, “2” as the “affiliation source” in the column of work number 1 in FIG. 0 is stored, and 46 is stored as the “delivery point number”.
[0101]
After that, the city affiliation change processing unit 55 deletes the delivery point 46 as the selection point belonging to the cluster 2 that is the affiliation source cluster in the improvement cluster-specific initial circuit that the city belongs to, and the improvement cluster-specific initial circuit The delivery point 46 as the selected point is added to the cluster 0 as the affiliation change destination cluster (s514).
After s514, the city affiliation change processing unit 55 transmits the improved cluster-specific initial circuit (selected point addition / division circuit) in which the delivery point 46 as the selection point is deleted and added in s514 to the random insertion unit 71 (s515). ).
[0102]
The random insertion unit 71 that has received the selection point addition / division circuit circulates all the delivery points belonging to the cluster starting from the depot assigned to the cluster for each cluster according to the selection point addition / division circuit (random insertion) (Selection point addition / division circuit) is generated by the above-described random insertion method, and the random insertion selection point addition / division circuit is transmitted to the city affiliation change processing unit 55. The city affiliation change processing unit 55 that has received the random insertion selection point addition / removal circuit from the random insertion unit 71 overwrites and stores the random insertion selection point addition / removal circuit in the route storage unit 97 and also stores the random insertion selection point addition / division circuit. It transmits to the traveling time calculation part 75 (s517).
FIG. 27 shows a result illustrating the random insertion selection point addition / deletion circuit stored in the path storage unit 97 at this time. Comparing FIG. 26 and FIG. 27 described above, the delivery point 46 as the selection point has been changed from cluster 2 to cluster 0.
[0103]
The cyclic time calculation unit 75 that has received the random insertion selection point addition / division circuit transmitted from the city affiliation change processing unit 55 in s517 calculates the distance for each cluster of the random insertion selection point addition / division circuit, and the calculation is performed. The distance for each cluster is transmitted to the city affiliation change processing unit 55 (s518).
Then, the city affiliation change processing unit 55 writes and stores the history related to the addition / removal processing of the selected point in the history storage unit 98 (s519) (the history is additionally written and stored, not overwritten). As described above, the history of selection point addition / deletion processing is as follows: the providing source cluster (cluster 2), the providing destination cluster (cluster 3), the belonging source cluster (cluster 2), and the belonging change destination cluster (cluster 0). Each item includes a delivery point (delivery point 46) as a selection point and an operation rate of each delivery vehicle.
[0104]
Thereafter, the city affiliation change processing unit 55 determines whether or not the affiliation change destination cluster (cluster 0) and the provision destination cluster (cluster 3) match (s520). (NO), the affiliation change destination cluster (cluster 0) at this time is stored in the aforementioned cluster list (s521) (that is, the affiliation change destination cluster (cluster 0) at this time is added to the list of clusters, It becomes a candidate selected as an affiliation source cluster for the next process.) Thereafter, the process returns to s511 again.
[0105]
Returning to s511, the city affiliation change processing unit 55 includes the delivery points belonging to the clusters stored in the cluster list (cluster 0 and cluster 2. The affiliation change destination cluster is stored in the cluster list in s521). Then, the delivery point 30 (degree of belonging to the cluster (cluster 3) of the provider: 0.44) is selected as the delivery point (selected point) having the highest degree of belonging to the cluster (cluster 3) of the provider.
Then, the city affiliation change processing unit 55 stores the cluster 0 to which the delivery point 30 as the selected point belongs as the affiliation source cluster (s512).
Next, the city affiliation change processing unit 55 assigns the degree of membership indicated by the delivery point 30 as the selected point to a cluster other than the clusters (cluster 0 and cluster 2) stored in the cluster list (that is, cluster 1 and cluster 3). Cluster 3 showing the highest degree of belonging (0.44) among clusters 1: 0.02 and cluster 3: 0.44) is selected and stored as the affiliation change destination cluster (s513).
Since the selected point, the affiliation source cluster, and the affiliation change destination cluster are written in the history storage unit 98 in s519, 0 is assigned as the “affiliation source” in the column of work number 2 in FIG. 3 and 30 as “delivery point number” are stored.
[0106]
After that, the city affiliation change processing unit 55 deletes the delivery point 30 as the selection point belonging to the cluster 0 as the affiliation source cluster in the improvement cluster-specific initial circuit that the self belongs, and The delivery point 30 as the selected point is added to the cluster 3 as the affiliation change destination cluster (s514).
After s514, the city affiliation change processing unit 55 transmits the improved cluster-specific initial circuit (selected point addition / deduction circuit) from which the delivery point 30 as the selection point is deleted and added in s514 to the random insertion unit 71 (s515). ).
[0107]
The random insertion unit 71 that has received the selection point addition / division circuit circulates all the delivery points belonging to the cluster starting from the depot assigned to the cluster for each cluster according to the selection point addition / division circuit (random insertion) (Selection point addition / division circuit) is generated by the above-described random insertion method, and the random insertion selection point addition / division circuit is transmitted to the city affiliation change processing unit 55. The city affiliation change processing unit 55 that has received the random insertion selection point addition / removal circuit from the random insertion unit 71 overwrites and stores the random insertion selection point addition / removal circuit in the route storage unit 97 and also stores the random insertion selection point addition / division circuit. It transmits to the traveling time calculation part 75 (s517).
FIG. 28 shows a result illustrating the random insertion selection point addition / deletion circuit stored in the path storage unit 97 at this time. Comparison of FIG. 27 and FIG. 28 described above shows that the delivery point 30 as the selection point is changed from cluster 0 to cluster 3.
[0108]
The cyclic time calculation unit 75 that has received the random insertion selection point addition / division circuit transmitted from the city affiliation change processing unit 55 in s517 calculates the distance for each cluster of the random insertion selection point addition / division circuit, and the calculation is performed. The distance for each cluster is transmitted to the city affiliation change processing unit 55 (s518).
Then, the city affiliation change processing unit 55 writes and stores the history related to the addition / removal processing of the selected point in the history storage unit 98 (s519) (the history is additionally written and stored, not overwritten). As described above, the history of the selection point addition / deletion processing is as follows: the providing source cluster (cluster 2), the providing destination cluster (cluster 3), the belonging source cluster (cluster 0), and the belonging change destination cluster (cluster 3). Each item includes a delivery point (delivery point 30) as a selection point and an operation rate of each delivery vehicle.
[0109]
Thereafter, the city affiliation change processing unit 55 determines whether or not the affiliation change destination cluster (cluster 3) and the provision destination cluster (cluster 3) match (s520). (YES), a plurality of clusters (one or two or more) of clusters (here, cluster 0 and cluster 2) included in the list of clusters in the random insertion selection point add / drop circuit and a cluster to be provided (cluster 3) Are read out from the path storage unit 97 (which stores the random insertion selection point addition / division circuit), and the acquired respective circular circuits are transmitted to the N-opt unit 73 (s522). .
The N-opt unit 73 that has received a cyclic circuit (a part of a random insertion selection point addition / division circuit) related to a plurality of clusters from the city affiliation change processing unit 55 accesses the initial information storage unit 91 and the initial information storage unit 91 The stored coordinates of the delivery point (FIG. 3A) and the coordinates of the depot (FIG. 3B) are read and acquired, and the required time storage unit 99 is accessed and stored in the required time storage unit 99. The distance table (refer to FIG. 5) is read out and acquired, and the coordinates of the delivery points (FIG. 3 (a)), the coordinates of the depot (FIG. 3 (b)), and the distance table are used for each circuit. The N-opt method is applied and improved (for each cluster), and the improved circuit (improved partial random insertion selection point addition / division circuit) is transmitted to the city affiliation change processing unit 55 (s523).
Then, the city affiliation change processing unit 55 that has received the improved partial random insertion selection point addition / removal circuit accesses the route storage unit 97 and improves the improvement of the random insertion selection point addition / removal circuit stored in the route storage unit 97. The part corresponding to the part random insertion selection point addition and removal circuit is rewritten (s524).
Thereafter, the city affiliation change processing unit 55 issues an activation signal (same as the activation signal issued from the initial circuit creation unit 45 to the route control unit 52) to the route control unit 52 (s525), and returns to s501 again.
[0110]
When returning to s501 again, the route control unit 52, the constraint condition (FIG. 3C) stored in the initial information storage unit 91, the distance table stored in the required time storage unit 99, and the route storage unit 97. Is read out and acquired (step s501).
Then, the route control unit 52 calculates the traveling distance for each cluster in the improved initial cluster circuit shown in FIG. 28 in s502, and then calculates the operation rate for each delivery vehicle in s503. Specifically, the operation rate of cluster 0 is 1.0609, the operation rate of cluster 1 is 0.9688, the operation rate of cluster 2 is 1.0715, and the operation rate of cluster 3 is 0.5269. (Refer to the second row from the top of the “operation rate” in FIG. 14).
Further, the route control unit 52 calculates the equalization coefficient in s504, and transmits the operation rate and the equalization coefficient for each delivery vehicle calculated in s504 to the affiliation change processing unit 53 in s505. Here, the equalization coefficient (Σ (| (operating rate of each delivery vehicle) − (average value of operating rate) |) / (number of delivery vehicles)) is (| 1.0609−0.907025 |). /4+|0.9688−0.907025|/4+|1.0715−0.907025|/4+|0.5269−0.907025|/4)=0.19000625.
[0111]
The affiliation change processing unit 53 that has received the operation rate and the equalization coefficient for each delivery vehicle transmitted in s505, the received equalization coefficient (here, 0.1900565) is the equalization stored by itself. It is determined whether it is smaller than the coefficient or whether or not it has stored the equalization coefficient (s506). Here, since it stores the equalization coefficient (previous value 0.23405) (here, Is determined to be smaller than (previous value 0.23405) (YES), and the received equalization coefficient (here, 0.1900565) is overwritten and stored (s507), and then the path control unit The occupancy rate for each delivery vehicle received from 52 (here, cluster 0: 1.0609, cluster 1: 0.9688, cluster 2: 1.0715, cluster 3: 0.5269) is changed. And it transmits to the processing unit 55 (s550).
The city affiliation change processing unit 55 that has received the operation rate for each delivery vehicle transmitted from the affiliation change processing unit 53 in s550 reads out and acquires necessary data in s508, and accesses the route storage unit 97 to access the route. The initial circuit for each improved cluster (FIG. 28) stored in the storage unit 97 is read and acquired. Then, in s509, the city affiliation change processing unit 55 receives the operating rate for each delivery vehicle received from the affiliation change processing unit 53 (cluster 0: 1.0609, cluster 1: 0.9688, cluster 2: 1.0715, cluster 3: 0.5269), the cluster (cluster 2) handled by the delivery vehicle that gives the highest operating rate (1.0715) is stored as the cluster of the provider, and is also stored in the list of clusters. Furthermore, the city affiliation change processing unit 55 determines a cluster (cluster 3) in charge of the delivery vehicle that gives the lowest operation rate (0.5269) among the operation rates for each delivery vehicle received from the affiliation change processing unit 53. This is stored as a cluster to be provided (s510). Since these are written in the history storage unit 98 in s519 as shown in FIG. 14, 2 is stored as “providing destination” and 3 as “providing source” in the column of work number 3 in FIG. .
[0112]
After that, the city affiliation change processing unit 55 has the delivery point (selected point) having the highest degree of belonging to the cluster (cluster 3) of the delivery destination among the delivery points belonging to the cluster (cluster 2) stored in the cluster list. As shown, the delivery point 20 (the degree of attribution of the provider cluster (cluster 3): 0.09. Note that the delivery point 46 is deleted from the cluster 2 at work number 1 in FIG. 14. Here, the delivery point 40 also has an attribution degree of 0.09, but the one found earlier is selected preferentially.) (S511).
Then, the city affiliation change processing unit 55 stores the cluster 2 to which the delivery point 20 as the selection point belongs as the affiliation source cluster (s512).
Next, the city affiliation change processing unit 55 assigns the degree of membership (cluster 0: cluster 0: selected point) to a cluster other than cluster 2 (ie, cluster 0, cluster 1, cluster 3) stored in the cluster list. 0.16, cluster 1: 0.06, cluster 3: 0.09), cluster 0 showing the highest degree of belonging (0.16) is selected and stored as the affiliation change destination cluster (s513).
Since the selected point, the affiliation source cluster, and the affiliation change destination cluster are written in the history storage unit 98 in s519, “2” is assigned as “affiliation source” in the column of work number 3 in FIG. 0 is stored, and 20 is stored as the “delivery point number”.
[0113]
Thereafter, the city affiliation change processing unit 55 deletes the delivery point 20 as the selection point belonging to the cluster 2 that is the affiliation source cluster in the initial circuit for each improved cluster that the self belongs, and The delivery point 20 as the selected point is added to the cluster 0 that is the affiliation change destination cluster (s514).
After s514, the city affiliation change processing unit 55 transmits to the random insertion unit 71 the initial cluster-by-improvement circuit (selected point addition / division circuit) in which the delivery point 20 as the selection point is deleted and added in s514 (s515). ).
[0114]
The random insertion unit 71 that has received the selection point addition / division circuit circulates all the delivery points belonging to the cluster starting from the depot assigned to the cluster for each cluster according to the selection point addition / division circuit (random insertion) (Selection point addition / division circuit) is generated by the above-described random insertion method, and the random insertion selection point addition / division circuit is transmitted to the city affiliation change processing unit 55. The city affiliation change processing unit 55 that has received the random insertion selection point addition / removal circuit from the random insertion unit 71 overwrites and stores the random insertion selection point addition / removal circuit in the route storage unit 97 and also stores the random insertion selection point addition / division circuit. It transmits to the traveling time calculation part 75 (s517).
FIG. 29 shows a result illustrating the random insertion selection point addition / deletion circuit stored in the path storage unit 97 at this time. Comparing FIG. 28 and FIG. 29 described above, the delivery point 20 as the selection point is changed from cluster 2 to cluster 0.
[0115]
The cyclic time calculation unit 75 that has received the random insertion selection point addition / division circuit transmitted from the city affiliation change processing unit 55 in s517 calculates the distance for each cluster of the random insertion selection point addition / division circuit, and the calculation is performed. The distance for each cluster is transmitted to the city affiliation change processing unit 55 (s518).
Then, the city affiliation change processing unit 55 writes and stores the history related to the addition / removal processing of the selected point in the history storage unit 98 (s519) (the history is additionally written and stored, not overwritten). As described above, the history of selection point addition / deletion processing is as follows: the providing source cluster (cluster 2), the providing destination cluster (cluster 3), the belonging source cluster (cluster 2), and the belonging change destination cluster (cluster 0). Each item includes a delivery point (delivery point 20) as a selection point and an operation rate of each delivery vehicle.
[0116]
Thereafter, the city affiliation change processing unit 55 determines whether or not the affiliation change destination cluster (cluster 0) and the provision destination cluster (cluster 3) match (s520). (NO), the affiliation change destination cluster (cluster 0) at this time is stored in the aforementioned cluster list (s521) (that is, the affiliation change destination cluster (cluster 0) at this time is added to the list of clusters, It becomes a candidate selected as an affiliation source cluster for the next process.) Thereafter, the process returns to s511 again.
[0117]
Similarly, in the work number 4 in FIG. 14, the providing source cluster (cluster 2), the providing destination cluster (cluster 3), the belonging source cluster (cluster 0), and the belonging change destination cluster (cluster 3). The operation is performed as a delivery point (delivery point 19) as a selection point, and the result is shown in FIG. Comparing FIG. 29 and FIG. 30 described above, the delivery point 19 as the selection point has been changed from cluster 0 to cluster 3. In the work number 4, it is determined that the affiliation change destination cluster (cluster 3) and the provision destination cluster (cluster 3) match (s520, YES), and the processing after s522 is performed.
Thereafter, in work number 5 in FIG. 14, the providing source cluster (cluster 0), the providing destination cluster (cluster 3), the belonging source cluster (cluster 0), and the belonging change destination cluster (cluster 3) are selected points. It operates as a delivery point (delivery point 45), and the result is shown in FIG. Comparing FIG. 30 and FIG. 31 described above, the delivery point 45 as the selection point has been changed from cluster 0 to cluster 3. For work number 5, it is determined that the affiliation change destination cluster (cluster 3) and the provision destination cluster (cluster 3) match (s520, YES), and the processing after s522 is performed.
[0118]
In work number 6 in FIG. 14, the providing source cluster (cluster 0), the providing destination cluster (cluster 3), the belonging source cluster (cluster 0), the belonging change destination cluster (cluster 3), and the delivery point as the selection point It operates as (delivery point 32), and the result is shown in FIG. Comparing FIG. 31 with FIG. 32 described above, the delivery point 32 as the selection point has been changed from cluster 0 to cluster 3. In the work number 6, it is determined that the affiliation change destination cluster (cluster 3) and the provision destination cluster (cluster 3) match (YES in s520), and the processing after s522 is performed.
In the work number 7 in FIG. 14, the providing source cluster (cluster 0), the providing destination cluster (cluster 3), the belonging source cluster (cluster 0), the belonging change destination cluster (cluster 3), the delivery point as the selection point It operates as (delivery point 37), and the result is shown in FIG. Comparing FIG. 32 with FIG. 33 described above, the delivery point 37 as the selection point has been changed from cluster 0 to cluster 3. In the work number 7, it is determined that the affiliation change destination cluster (cluster 3) and the provision destination cluster (cluster 3) match (s520, YES), and the processing after s522 is performed.
[0119]
In work number 8 in FIG. 14, the providing source cluster (cluster 2), the providing destination cluster (cluster 3), the belonging source cluster (cluster 2), the belonging change destination cluster (cluster 0), and the delivery point as the selection point It operates as (delivery point 40), and the result is shown in FIG. Comparing FIG. 33 with FIG. 34 described above, the delivery point 40 as the selection point has been changed from cluster 2 to cluster 0. In the work number 8, it is not determined that the affiliation change destination cluster (cluster 0) and the provision destination cluster (cluster 3) match (s520, NO), and s521 (affiliation change destination cluster (cluster 0) is described above. Are stored in the cluster list).) The subsequent processing is performed.
In the work number 9 in FIG. 14, the providing source cluster (cluster 2), the providing destination cluster (cluster 3), the belonging source cluster (cluster 0), the belonging change destination cluster (cluster 3), the delivery point as the selection point It operates as (delivery point 46), and the result is shown in FIG. Comparing FIG. 34 and FIG. 35 described above, the delivery point 46, which is the selected point, has been changed from cluster 0 to cluster 3. In the work number 9, it is determined that the affiliation change destination cluster (cluster 3) and the provision destination cluster (cluster 3) match (s520, YES), and the processing after s522 is performed.
[0120]
In the work number 10 in FIG. 14, the providing source cluster (cluster 0), the providing destination cluster (cluster 2), the belonging source cluster (cluster 0), the belonging change destination cluster (cluster 2), the delivery point as the selection point The operation as (delivery point 20) is shown in FIG. Comparing FIG. 35 with FIG. 36 described above, the delivery point 20 as the selection point has been changed from cluster 0 to cluster 2. In the work number 10, it is determined that the affiliation change destination cluster (cluster 2) and the provision destination cluster (cluster 2) match (s520, YES), and the processing after s522 is performed.
[0121]
In the work number 11 in FIG. 14, the providing source cluster (cluster 1), the providing destination cluster (cluster 0), the belonging source cluster (cluster 1), the belonging change destination cluster (cluster 2), the delivery point as the selection point It operates as (delivery point 1), and the result is shown in FIG. Comparing FIG. 36 and FIG. 37 described above, the delivery point 1 as the selection point has been changed from cluster 1 to cluster 2. In the work number 11, it is not determined that the affiliation change destination cluster (cluster 2) and the provision destination cluster (cluster 0) match (s520, NO), and s521 (affiliation change destination cluster (cluster 2) is described above. Are stored in the cluster list).) The subsequent processing is performed.
In the work number 12 in FIG. 14, the providing source cluster (cluster 1), the providing destination cluster (cluster 0), the belonging source cluster (cluster 2), the belonging change destination cluster (cluster 0), and the delivery point as the selection point It operates as (delivery point 22), and the result is shown in FIG. Comparing FIG. 37 and FIG. 38 described above, the delivery point 22 as the selection point has been changed from cluster 2 to cluster 0. In the work number 12, it is determined that the affiliation change destination cluster (cluster 0) and the provision destination cluster (cluster 0) match (s520, YES), and the processing after s522 is performed.
[0122]
In the work number 13 in FIG. 14, the providing source cluster (cluster 2), the providing destination cluster (cluster 1), the belonging source cluster (cluster 2), the belonging change destination cluster (cluster 1), the delivery point as the selection point It operates as (delivery point 1), and the result is shown in FIG. Comparing FIG. 38 and FIG. 39 described above, the delivery point 1 as the selection point has been changed from cluster 2 to cluster 1. In the work number 13, it is determined that the affiliation change destination cluster (cluster 1) and the provision destination cluster (cluster 1) match (s520, YES), and the processing after s522 is performed.
In the work number 14 in FIG. 14, the providing source cluster (cluster 3), the providing destination cluster (cluster 2), the belonging source cluster (cluster 3), the belonging change destination cluster (cluster 2), the delivery point as the selection point It operates as (delivery point 46), and the result is shown in FIG. Comparing FIG. 39 and FIG. 40 described above, the delivery point 46 as the selection point has been changed from cluster 3 to cluster 2. In the work number 14, it is determined that the affiliation change destination cluster (cluster 2) and the provision destination cluster (cluster 2) match (s520, YES), and the processing after s522 is performed.
[0123]
In the work number 15 in FIG. 14, the providing source cluster (cluster 1), the providing destination cluster (cluster 3), the belonging source cluster (cluster 1), the belonging change destination cluster (cluster 2), the delivery point as the selection point It operates as (delivery point 1), and the result is shown in FIG. Comparing FIG. 40 with FIG. 41 described above, the delivery point 1 as the selection point has been changed from cluster 1 to cluster 2. In the work number 15, it is not determined that the affiliation change destination cluster (cluster 2) and the provision destination cluster (cluster 3) match (s520, NO), and s521 (affiliation change destination cluster (cluster 2) is described above. Are stored in the cluster list).) The subsequent processing is performed.
In the work number 16 in FIG. 14, the providing source cluster (cluster 1), the providing destination cluster (cluster 3), the belonging source cluster (cluster 2), the belonging change destination cluster (cluster 0), and the delivery point as the selection point It operates as (delivery point 46), and the result is shown in FIG. Comparing FIG. 41 and FIG. 42 described above, the delivery point 46 as the selection point has been changed from cluster 2 to cluster 0. In the work number 16, it is not determined that the affiliation change destination cluster (cluster 0) and the provision destination cluster (cluster 3) match (s520, NO), and s521 (affiliation change destination cluster (cluster 0) is described above. Are stored in the cluster list).) The subsequent processing is performed.
In the work number 17 in FIG. 14, the providing source cluster (cluster 1), the providing destination cluster (cluster 3), the belonging source cluster (cluster 0), the belonging change destination cluster (cluster 3), the delivery point as the selection point It operates as (delivery point 46), and the result is shown in FIG. Comparing FIG. 42 and FIG. 43 described above, the delivery point 46, which is the selected point, has been changed from cluster 0 to cluster 3. In the work number 17, it is determined that the affiliation change destination cluster (cluster 3) and the provision destination cluster (cluster 3) match (YES in s520), and the processing from s522 is performed.
[0124]
In the work number 18 in FIG. 14, the providing source cluster (cluster 2), the providing destination cluster (cluster 1), the belonging source cluster (cluster 2), the belonging change destination cluster (cluster 1), the delivery point as the selection point It operates as (delivery point 1), and the result is shown in FIG. Comparing FIG. 43 with FIG. 44 described above, the delivery point 1 as the selection point has been changed from cluster 2 to cluster 1. In the work number 18, it is determined that the affiliation change destination cluster (cluster 1) and the provision destination cluster (cluster 1) match (s520, YES), and the processing after s522 is performed.
[0125]
In the work number 19 in FIG. 14, the providing source cluster (cluster 3), the providing destination cluster (cluster 2), the belonging source cluster (cluster 3), the belonging change destination cluster (cluster 2), the delivery point as the selection point It operates as (delivery point 46), and the result is shown in FIG. Comparing FIG. 44 with FIG. 45 described above, the delivery point 46 as the selection point has been changed from cluster 3 to cluster 2. In the work number 19, it is determined that the affiliation change destination cluster (cluster 2) and the provision destination cluster (cluster 2) match (s520, YES), the processing from s522 is performed, and the process returns to s501 again.
At this time, after the operation of s501 to s505, the affiliation change processing unit 53 in s506 receives the equalization coefficient smaller than the equalization coefficient stored by itself, or stores the equalization coefficient by itself. (NO) (that is, the affiliation change processing unit 53 stores the equalization coefficient, and the received equalization coefficient is equal to or greater than the stored equalization coefficient. If there is, an activation signal is issued to the history check unit 54 (s551).
[0126]
The history check unit 54 that has received the activation signal issued by the affiliation change processing unit 53 in s551 accesses the history storage unit 98 and stores the history regarding the addition / deletion processing of the selected points stored in the history storage unit 98 (that is, FIG. 14) (S526). Then, the history check unit 54 records the latest history regarding the addition / deletion processing of the selected points acquired and acquired (represented by the work number 19 in the case shown in FIG. 14) and the history other than the latest history. (Other history. If it is what was shown in FIG. 14, what is shown by each of work numbers 1-18) is compared, and it is judged whether the same thing as the latest history exists in other history. (S527). Here, work number 19 and work number 14 are the source cluster (cluster 3), the destination cluster (cluster 2), the affiliation source cluster (cluster 3), the affiliation change destination cluster (cluster 2), and the selection points. Since all the delivery points (delivery points 46) match, the history check unit 54 determines that the same item (work number 14) as the most recent history (work number 19) exists in the other history (YES), The history check unit 54 transmits an activation signal to the affiliation change result setting unit 56 (s528).
The affiliation change result setting unit 56 that has received the activation signal issued by the history check unit 54 in s528 accesses the history storage unit 98 and stores the history regarding the selection point addition / removal processing stored in the history storage unit 98 (FIG. 14) is read and acquired, and the equalization coefficient of each history (each of work numbers 1 to 19) is calculated using the operating rate of each delivery vehicle included in each history (each of work numbers 1 to 19) (s531). . Next, the affiliation change result setting unit 56 selects a circuit (any one of work numbers 1 to 19) that gives the smallest value among the equalization coefficients calculated for each history (work numbers 1 to 19). The selected tour route is transmitted to the route storage unit 97 and stored in the route storage unit 97 (s532).
Thereafter, the affiliation change result setting unit 56 issues an activation signal to the operation rate adjustment unit 61 (operation rate adjustment control unit 63) (s533), and goes to s601 described later.
[0127]
23 to 25 are flowcharts showing the operation of the operation rate adjusting unit 61 of the apparatus 11. With reference to FIGS. 23 to 25, the operation of the operation rate adjusting unit 61 of the present apparatus 11 will be described.
First, referring to FIG.
The operating rate adjustment control unit 63 that has received the activation signal issued from the affiliation change result setting unit 56 in s533 described above deletes the content stored in the combination history list stored by itself (s601).
Next, the operation rate adjustment control unit 63 accesses the initial information storage unit 91 to read out and acquire the constraint condition (FIG. 3C) stored in the initial information storage unit 91 (used for calculating the operation rate described later). Further, the route storage unit 97 is accessed and the route stored in the route storage unit 97 (selected by the affiliation change result setting unit 56 as the circuit that gives the smallest equalization coefficient) is read and acquired ( s602). Then, the operating rate adjustment control unit 63 transmits the read and acquired tour to the tour time calculation unit 75 (s603).
[0128]
The traveling time calculation unit 75 that has received the tour transmitted from the operation rate adjustment control unit 63 in s603 reads out and acquires the distance table stored in the required time storage unit 99, and for each cluster of the tour circuit. Is calculated from the distance table, and the calculated cyclic distance for each cluster according to the cyclic circuit is transmitted to the operation rate adjustment control unit 63 (s604).
The operating rate adjustment control unit 63 that has received the cyclic distance for each cluster according to the cyclic circuit transmitted from the cyclic time calculation unit 75 in s604, the received cyclic distance for each cluster, and the initial information storage unit The operation rate for each cluster is calculated using the constraint condition read and acquired from 91 (FIG. 3C) (s605) (Note that the operation rate is the cyclic distance for each cluster as described above. , The restriction condition of the delivery vehicle in charge of the cluster (the quotient divided by FIG. 3C, here, all 10000).
Next, the operating rate adjustment control unit 63 determines the order of increasing operating rates for each cluster calculated in s605, and creates an aligned cluster number by arranging the cluster numbers in the descending order (s606).
[0129]
Thereafter, the operation rate adjustment control unit 63 deletes the contents stored in a candidate list (described later) stored by itself (s607) (if nothing is stored in the candidate list, the deletion is not necessary).
Next, the operation rate adjustment control unit 63 determines the cluster (here, the cluster) indicated by the cluster number located at the head of the aligned cluster number (“3” when the aligned cluster number is “3, 0, 2, 1”). 3) is selected as the operation rate adjustment providing source cluster (s608).
Furthermore, the operation rate adjustment control unit 63 selects one of the delivery points belonging to the operation rate adjustment providing source cluster as the change candidate delivery point p (s609).
[0130]
Then, the operating rate adjustment control unit 63 selects one cluster from all the clusters as the operating rate adjustment providing destination cluster (s610). Here, the one with the smallest cluster number, that is, cluster 0 is selected first.
Thereafter, the operation rate adjustment control unit 63 determines whether or not the operation rate adjustment providing source cluster and the operation rate adjustment providing destination cluster match (s611), and when determining that both clusters match ( If YES, go to s616 described below. When the operation rate adjustment control unit 63 determines in s611 that the operation rate adjustment providing source cluster and the operation rate adjustment providing destination cluster do not match (NO), the operation rate adjustment control unit 63 determines that the route storage unit 97 From s602, the circuit read out and acquired is transmitted to the change trial unit 65 (s612).
[0131]
Reference is now made to FIG.
The change trial unit 65 that has received the circuit transmitted from the operation rate adjustment control unit 63 in s612 changes the affiliation of the change candidate delivery point p from the operation rate adjustment providing source cluster to the operation rate adjustment providing destination cluster. The traveling distance difference is calculated (s613) (Note that the change trial unit 65 reads out and acquires the distance table stored in the required time storage unit 99 and calculates the traveling distance difference).
The change trial unit 65 determines whether or not the cyclic distance difference calculated in s613 is a positive value (s614), and if the cyclic distance difference is determined to be a positive value (YES), the operating rate adjustment provider at that time The change trial unit 65 transmits information relating to the cluster, the operation rate adjustment provision destination cluster, the delivery point as the change candidate delivery point p, and the data of the traveling distance difference to the operation rate adjustment control unit 63, and the information is adjusted to the operation rate adjustment. The controller 63 additionally stores the candidate list as a candidate list instead of overwriting (s615). At this time, the candidate list is stored in descending order of the difference in the cyclic distance included in the related information.
On the other hand, if the change trial unit 65 does not determine that the cyclic distance difference is a positive value in s614 (NO), the change trial unit 65 selects the next cluster as the operation rate adjustment provision destination cluster in the operation rate adjustment control unit 63. A signal instructing this is issued (s616).
[0132]
After receiving the signal issued in s616 or after s615, the operation rate adjustment control unit 63 determines whether or not the next cluster can be selected as the operation rate adjustment supply destination cluster (s617), and the operation rate adjustment supply destination If it is determined that the next cluster can be selected as a cluster (YES), the next cluster is selected as the availability adjustment provision destination cluster (s618), and the process returns to s611 again.
When the operation rate adjustment control unit 63 does not determine in step s617 that the next cluster can be selected as the operation rate adjustment provision destination cluster (NO) (all clusters have already been selected as the operation rate adjustment provision destination cluster, When the cluster cannot be selected as the operation rate adjustment provision destination cluster), the operation rate adjustment control unit 63 determines whether or not the next delivery point can be selected as the change candidate delivery point p (s619).
When the operating rate adjustment control unit 63 determines in s619 that the next delivery point can be selected as the change candidate delivery point p (YES), the operating rate adjustment control unit 63 sets the next of the operating rate adjustment providing source cluster. A delivery point (the delivery point located at the head in the circuit among the delivery points excluding the delivery point already selected as the change candidate delivery point p) is selected as the next change candidate delivery point p (s620), and the process proceeds to s610. Return.
When the operation rate adjustment control unit 63 does not determine that the next delivery point can be selected as the change candidate delivery point p in s619 (NO), the operation rate adjustment control unit 63 sets the next operation rate adjustment providing source cluster as the operation rate adjustment providing source cluster. It is determined whether or not a cluster can be selected (s621), and if it is determined that the next cluster can be selected as an operation rate adjustment providing source cluster (YES), the next cluster (with an aligned cluster number) is selected as the operation rate adjustment providing source cluster. Among them, the cluster next to the cluster selected as the operation rate adjustment providing source cluster is selected (s622), and the process returns to s609 again.
[0133]
If the operating rate adjustment control unit 63 does not determine in step s621 that the next cluster can be selected as the operating rate adjustment providing source cluster (NO) (that is, a cluster that is no longer selected as the operating rate adjustment providing source cluster). If not, the operation rate adjustment control unit 63 performs a candidate check (s623). As described above, the candidate check relates to the candidate list (operating rate adjustment providing source cluster, working rate adjustment providing destination cluster, delivery point serving as the change candidate delivery point p, and cyclic distance difference data held by the operating rate adjustment control unit 63. The information (candidates) attached is stored in order from the one with the largest cyclic distance difference.) And the history of affiliation changes made so far in the operating rate adjustment control unit 63 are stored. Affiliation change history (operating rate adjustment providing source cluster, operating rate adjustment providing destination cluster, change candidate delivery point p, delivery point, traveling distance, operating rate of each delivery vehicle, equalization coefficient are stored in the history list The operation rate adjustment control unit 63 compares the operation rate adjustment providing source cluster, the operation rate adjustment providing destination cluster included in each candidate, the same operation rate adjustment providing source as the delivery point p as the change candidate delivery point p. The If there is an affiliation change history that includes a delivery point that is a star, an operation rate adjustment provision destination cluster, and a change candidate delivery point p, the operation rate adjustment control unit 63 deletes the candidate from the candidate list. To check. Do this until there are no unchecked candidates in the candidate list.
[0134]
Further, refer to FIG.
After s623, the operation rate adjustment control unit 63 determines whether or not candidates remain in the candidate list (s624), and if they remain (YES), the delivery point is determined according to the candidate located at the head of the remaining candidates. (S625) (that is, the delivery point corresponding to the change candidate delivery point p indicated in the first candidate is changed from the operating rate adjustment providing source cluster to the operating rate adjustment providing destination cluster. The operating rate adjustment control unit 63 excludes the change candidate delivery point p from the operating rate adjustment providing source cluster in the circuit read from the route storage unit 97 in s602, and changes to the operating rate adjustment providing destination cluster as a change candidate. Add delivery point p). When the operation rate adjustment control unit 63 does not determine that there are candidates remaining in the candidate list (NO) in s624, the operation rate adjustment control unit 63 sends a circuit (route storage unit 97 in s602) to the result output unit 67. And the history list are transmitted (s626).
[0135]
After s625, the operating rate adjustment control unit 63 determines that both of the traveling routes related to the operating rate adjustment providing source cluster and the operating rate adjustment providing destination cluster (the delivery point as the change candidate delivery point p is excluded, the former is removed and the latter is added). Is transmitted to the random insertion unit 71 (s627). The random insertion unit 71 that has received both the tours transmitted from the operation rate adjustment control unit 63 at s627 accesses the initial information storage unit 91 and coordinates of the delivery point stored in the initial information storage unit 91. (FIG. 3A) and the coordinates of the depot (FIG. 3B) are read and acquired, the required time storage unit 99 is accessed, and the distance table stored in the required time storage unit 99 is read and acquired. According to both tour routes, a tour route that visits all delivery points belonging to the cluster starting from the depot assigned to the cluster for each cluster is created by the random insertion method described above, and transmitted to the operation rate adjustment control unit 63 (S628).
[0136]
The operation rate adjustment control unit 63 that has received the tour transmitted from the random insertion unit 71 in s628 transmits the received tour to the N-opt unit 73 (s629). The N-opt unit 73 that has received the circuit transmitted from the operation rate adjustment control unit 63 in s629 accesses the initial information storage unit 91 and coordinates of the delivery point stored in the initial information storage unit 91 ( FIG. 3A) and the coordinates of the depot (FIG. 3B) are read out and acquired, and the distance table stored in the required time storage unit 99 by accessing the required time storage unit 99 (see FIG. 5). Are read and acquired, and using the coordinates of these delivery points (FIG. 3 (a)), the coordinates of the depot (FIG. 3 (b)) and the distance table, the circuit (operation rate adjustment providing source cluster and operation rate adjustment providing) The above-described N-opt method is applied to both the loops related to the destination cluster (for each cluster) to improve the loop, and the improved loop is transmitted to the operation rate adjustment control unit 63 (s630). ).
The operation rate adjustment control unit 63 that has received the improved tour from the N-opt unit 73 transmits the improved tour to the tour time calculation unit 75 (s631).
The traveling time calculation unit 75 that has received the improved traveling circuit transmitted from the operation rate adjustment control unit 63 in s631 reads out and acquires the distance table stored in the required time storage unit 99, and the improved The traveling distance for each cluster of the traveling circuit is calculated from the distance table, and the calculated traveling distance for each cluster is transmitted to the operation rate adjustment control unit 63 (s632).
[0137]
The operation rate adjustment control unit 63 that has received the cyclic distance for each cluster transmitted from the cyclic time calculation unit 75 in s632, the cyclic distances of all the clusters, and the constraint conditions read and acquired from the initial information storage unit 91 (see FIG. 3 (c)), the operating rate for each cluster is calculated, and the operating rate adjustment control unit 63 calculates an equalization coefficient using the calculated operating rate of each cluster (s633).
After s633, the operation rate adjustment control unit 63 adds the change history (operation rate adjustment providing source cluster, operation rate adjustment providing destination cluster, delivery point serving as the change candidate delivery point p, traveling distance, each delivery) to the history list held by itself. The vehicle operation rate and the equalization coefficient are stored and written, and the circuit (the improved circuit received from the N-opt unit 73 as described above) is written to the route storage unit 97 ( s634), and returns to s601.
[0138]
Note that the result output unit 67 that has received the tour and the history list issued by the operation rate adjustment control unit 63 in s626 has the operation rate of all the affiliation change histories in the received history list being 1 or less. The one with the shortest distance is extracted, and the circuit corresponding to the extracted affiliation change history is output as a final determined circuit by a predetermined method (printing, display on a display, etc.) (s635).
The result output unit 67 obtains the final decision circuit as described in the following (1) to (4). That is, first, (1) the result output unit 67 includes the affiliation change history (operation rate adjustment providing source cluster, operation rate adjustment providing destination cluster, change candidate delivery point p included in the history list received from the operation rate adjustment control unit 63. Among the delivery points, the traveling distance, the operating rate of each delivery vehicle, and the equalization coefficient), the operating rate is all 1 or less and the traveling distance is the minimum (hereinafter referred to as “target affiliation change history”) .) Is extracted. Next, (2) the result output unit 67 uses the history list received from the operation rate adjustment control unit 63 and the tour route received from the operation rate adjustment control unit 63 to each cluster corresponding to the target affiliation change history. Create a list of delivery points belonging to. Specifically, the circuit received from the operation rate adjustment control unit 63 shows the state after the most recent affiliation change of the history list received from the operation rate adjustment control unit 63, so the latest history list List of delivery points belonging to each cluster corresponding to the target affiliation change history (specifically, delivery points belonging to each cluster) (Numbers listed) are created. (3) The result output unit 67 transmits a list of delivery points belonging to each cluster corresponding to the target affiliation change history obtained in (2) above to the random insertion unit 71. The insertion unit 71 creates a tour according to the list of delivery points (in accordance with the delivery point list, a tour that travels around all delivery points belonging to the cluster starting from the depot assigned to each cluster is randomly selected. Created by the insertion method.) The random insertion unit 71 transmits the created tour to the result output unit 67. Finally, (4) the result output unit 67 that has received the tour from the random insertion unit 71 transmits the received tour to the N-opt unit 73, and the N-opt unit 73 receives the tour as before. The N-opt method is applied to the road (for each cluster) to improve the circuit. The N-opt unit 73 transmits the improved tour to the result output unit 67.
[0139]
As described above, the apparatus 11 includes the third apparatus, the first apparatus, and the second apparatus according to the present invention.
First, the third main device included in the main device 11 is configured as follows.
The third apparatus receives total load calculating means (position data of a plurality of points (delivery points)) including a cluster number calculating unit 37, a random inserting unit 71, an N-opt unit 73, and a traveling time calculating unit 75. , A means for calculating the total load around the plurality of points) and a moving body number determining means constituted by the cluster number calculation unit 37 (a moving body (delivery vehicle around a part of the plurality of points (delivery points)) ) Accepting a load tolerance (FIG. 3C, which is a constraint condition) that is the amount of load that can be handled by each, and based on the overall load and the load tolerance evaluated by the overall load calculation means, A means for determining the number by a predetermined method), and a point dividing means (a plurality of points (delivery points)) constituted by a fuzzy clustering calculation unit 43 and an initial circuit creation unit 45. Decision And a moving body departure position information receiving means (starting position information indicating the departure position of each moving body (delivery vehicle) (FIG. 3). (B)) and a mobile unit allocating unit configured by the initial circuit creation unit 45 (predetermined positional relationship with respect to each group (cluster) of points (delivery points) divided by the point dividing unit) (Here, means for allocating a moving body (delivery vehicle) related to departure position information having a position relationship closest to the center of gravity of each cluster), a random insertion unit 71 and an N-opt unit 73 (and an initial circuit creation unit 45) ) Each group primitive route forming means (starting from the starting position (depot) of the moving body (delivery vehicle) assigned by the moving body assigning means) A route forming device comprising: a route for each group (cluster) that goes around all points belonging to the group (cluster) corresponding to the (delivery vehicle) (means for creating an initial circuit for each improved cluster). is there.
[0140]
The third main apparatus included in the present apparatus 11 includes a total amount judging means (path for each group (cluster) formed by each group original path forming means (initial for each improved cluster) formed by the initial circuit creation unit 45. The first total amount of loads (traveling distance) related to all the groups (clusters) and the moving body number determining means that are received by the moving body number determining means, and each of the moving bodies (delivery vehicles) assigned to each group (cluster) A mobile unit configured by comparing the second total amount obtained by adding up the load allowable amounts (constraint conditions) and determining whether or not the second total amount is equal to or greater than the first total amount) and the initial circuit creation unit 45 Increase means (means for increasing the number of mobile bodies (delivery vehicles) when the initial circuit creation unit 45 as the total amount determination means does not determine that the second total amount is greater than or equal to the first total amount). It is provided. Further, the point dividing means divides a plurality of points (delivery points) according to the increased number of mobile bodies (delivery vehicles), and the mobile body assigning means is the number of the increased mobile bodies (delivery vehicles). A moving body (delivery vehicle) is allocated to each group of points (delivery points) divided according to the number, and each group primitive route forming means divides according to the increased number of moving bodies (delivery vehicles) A route for each group of the received points (delivery points) is created.
[0141]
Next, the first apparatus included in the apparatus 11 is configured as follows.
The first apparatus includes route data accepting means (means for accepting a plurality of route data including a starting point and routes around a plurality of points) configured by the city affiliation change processing unit 55, and a city affiliation change process. Start completion determining means configured by the unit 55 (a start path (here, the heaviest load) which is different from the lightest path among a plurality of path data received by the path data receiving means of the first apparatus) A route that is a route of the providing cluster) and a completion route that is a lighter load than the start route (here, a route of the providing cluster that is the lightest route) ) And the affiliation change means constituted by the city affiliation change processing unit 55 (one route (the affiliation source class) The selected point that is a point (delivery point) included in the route) and a predetermined relationship with the selected point (the highest degree of belonging among the degrees of belonging indicated by the selected point to a cluster other than the cluster stored in the cluster list) Are selected, and the selected point is moved from the one route to the other route. At the first time, a start route (provided) is selected. The route of the original cluster) is selected as the one route, and the next and subsequent routes are means for repeating the selection and the movement with the other route or start route before the previous time as the one route), and the city affiliation change processing Completion judging means (means for judging whether or not the other route (route of the affiliation change destination cluster) matches the completion route (route of the cluster of the provision destination)) configured by the unit 55 The affiliation change means determines completion It is intended to operate repeatedly until it is determined that the stage coincide, the path adjustment device.
[0142]
In the first main apparatus included in the present apparatus 11, as described above, the start path is the path with the heaviest load among the plurality of path data received by the path data receiving unit, and the completion path is This is the route with the lightest load among the plurality of route data.
Further, in the first main apparatus included in the present apparatus 11, the city affiliation change processing unit 55 as the affiliation change means adds the other route or start route before the previous time (the route of the cluster stored in the cluster list). Of the included points, a point having the highest degree of belonging to the completion route (route of the cluster of the provision destination) is selected as the selection point.
Further, in the first main apparatus included in the present apparatus 11, the city affiliation change processing unit 55 as affiliation change means is other than the other route or the start route (the cluster route stored in the cluster list) before the previous time. The route that shows the highest degree of belonging to the route indicated by the selected point is selected as the other route (route of the affiliation change destination cluster).
[0143]
The first main device included in the present device 11 is a route in which the selected point is added or removed by a route forming unit (of the first main device) belonging to the random insertion unit 71, and the included point is changed. (Means for determining the order of visiting the points belonging to and forming a route).
In the first main apparatus included in the apparatus 11, the route data including the route formed by the random insertion unit 71 serving as the route forming unit of the first main apparatus is assigned to the city belonging as the route data receiving unit of the first main apparatus. The change processing unit 55 receives and further adjusts the route.
Although not described here, the route may be repeatedly adjusted until the variation in the load of each route in the route formed by the route forming means falls within a predetermined range.
[0144]
In addition, the first apparatus included in the apparatus 11 includes equalized data forming means configured by the path control unit 52 (for each path in the path formed by the random insertion unit 71 serving as the path forming unit of the first apparatus). A means for forming (calculating) equalization data (equalization coefficient) that is data indicating variation in load) and an equalization data storage means (equalization coefficient as equalization data) configured by the affiliation change processing unit 53 is stored. The affiliation change processing unit 53 stores the minimum equalization coefficient so far, and an improvement determination unit configured by the affiliation change processing unit 53 (formed by the equalization data forming unit of the first apparatus). Whether the latest equalized data (equalization coefficient) is improved compared to the past equalization data (equalization coefficient) stored in the equalization data storage means of the first apparatus. (Means for determining whether or not it is small here)), and when the affiliation change processing unit 53 as the improvement determination means determines that the improvement has been made, the route forming means ( The route data receiving means (city affiliation change processing unit 55) of the first apparatus receives route data relating to the route formed by the random insertion unit 71) and further adjusts the route.
[0145]
In the first apparatus included in the apparatus 11, a history storage unit configured by a history storage unit 98 (a unit for storing the history of the selection change of the selected point performed by the affiliation changing unit of the first apparatus); Convergence determination unit configured by the history check unit 54 (whether or not the history same as that of the latest selection point affiliation change process is stored in the history storage means of the first apparatus (the same as the latest history is other And a convergence determination unit for determining whether or not it exists in the history). Then, the history check unit 54, which is a convergence determination unit, stores the same history as the affiliation change process of the latest selected point (the affiliation change process of the selected point related to the latest equalization data) by the history storage unit of the first apparatus. If it is not determined that the data is stored, the route data receiving means of the first device accepts the route data relating to the route formed by the route forming means of the first device, and further adjusts the route. Here, when the improvement determination means of the first apparatus does not determine that the latest equalized data has been improved, the history check unit 54 that is the convergence determination unit has the same history as the latest history in the other history. Whether to judge whether or not.
[0146]
Next, the second main device included in the main device 11 is configured as follows.
The second apparatus includes route data receiving means (means for receiving a plurality of route data including a starting point and routes around a plurality of points) configured by the operation rate adjustment control unit 63, and operation rate adjustment control. Total load evaluation means (each point (delivery point) included in a plurality of route data received by the route data receiving means (operation rate adjustment control unit 63) of the second apparatus) configured by the unit 63 and the change trial unit 65 To evaluate the change (cyclic distance difference) in the load (distance) of all routes that occurs when the location (delivery point) is not included in a route (route of the operation rate adjustment provision destination cluster) And load change storage means configured by the candidate list of the operation rate adjustment control unit 63 (the change in load (distance) evaluated by the overall load evaluation means is different from that before the location (delivery point) is changed). Then negative In which the affiliation is changed (delivery point) and the point where the affiliation is changed (delivery point) belongs before the affiliation is changed The operation rate adjustment providing source cluster (the route) that is the previous belonging route that is the route and the operation rate adjustment providing destination cluster (the route that is the subsequent belonging route that is the destination route where the affiliation change is changed) ), And an extraction means configured by the operation rate adjustment control unit 63 (matching a predetermined condition among the change candidate data stored in the load change storage means) Means for extracting what to do).
[0147]
In the second main device included in the main device 11, the change candidate data is reduced to the extent that the sum of the loads (distances) of all routes is reduced as compared to before the affiliation of the point (delivery point) is changed. The data of the cyclic distance difference, which is a reduction degree indicating whether or not, is stored in an associated state, and the predetermined condition when the extraction means extracts is the condition that the reduction degree is the maximum.
The second apparatus included in the apparatus 11 forms a route according to the change candidate data extracted by the extraction unit (of the second apparatus) (consisting of the second apparatus) composed of the random insertion unit 71 and the N-opt unit 73. Means).
Further, in the second main apparatus included in the apparatus 11, the path data including the path formed by the path forming means (of the second main apparatus) is received by the path data receiving means (of the second main apparatus), and further the path adjust.
[0148]
The second apparatus included in the apparatus 11 further includes change candidate history storage means (means for storing the history of change candidate data extracted by the extraction means) configured by a history list included in the operation rate adjustment control unit 63. The extraction means is the same as the history stored in the change candidate history storage means among the change candidate data stored in the load change storage means (candidate list of the operation rate adjustment control unit 63) of the second apparatus. Extracted from the excluded change history data.
Then, in the second main apparatus included in the present apparatus 11, the path data including the path formed by the path forming means (of the second main apparatus) is obtained until the extraction means cannot extract the change history data ( The route data receiving means (of the second main apparatus) receives and further adjusts the route.
[0149]
Further, in the present apparatus 11, the route data receiving means of the first present apparatus displays the route for each group starting from the departure position (depot) of the moving body (delivery vehicle) formed by the third present apparatus. Accept as. Then, the route data receiving means of the second main device accepts the route formed by the route forming means of the first main device as route data and further adjusts the route.
[Brief description of the drawings]
FIG. 1 is a schematic block diagram showing a hardware configuration of a route search apparatus (this apparatus) according to an embodiment of the present invention.
FIG. 2 is a schematic functional block diagram showing a rough basic configuration of the apparatus.
FIG. 3 is a diagram illustrating an example of data stored in advance in an initial information database.
FIG. 4 is a detailed functional block diagram of a cluster dividing unit.
FIG. 5 is an example of a distance table created by a table initialization unit 35;
FIG. 6 is an example of a circuit (the circuit is illustrated in the coordinates) received by the cluster number calculation unit 37 from the N-opt unit 73;
FIG. 7 is a detailed functional block diagram of a provisional circuit forming unit 41;
FIG. 8 is a diagram showing the degree of attribution of each delivery point calculated to each cluster.
FIG. 9 is a diagram illustrating a method for determining a cluster to which a delivery point belongs.
FIG. 10 is an example of a delivery point number list in which delivery point numbers belonging to each cluster are described for each cluster;
11 is a diagram showing a depot assigned to each cluster in a delivery point number list stored in a route storage unit 97. FIG.
FIG. 12 is a diagram illustrating an example of an initial circuit for each improved cluster.
13 is a detailed functional block diagram of an affiliation adjustment unit 51. FIG.
14 is a diagram showing an example of a history written and stored in a history storage unit 98. FIG.
15 is a detailed functional block diagram of an operation rate adjusting unit 61. FIG.
FIG. 16 is a diagram for explaining a calculation method of a traveling distance difference.
17 is a flowchart showing the operation of the cluster dividing unit 31. FIG.
18 is a flowchart showing the operation of the provisional circuit forming unit 41. FIG.
19 is a flowchart showing the operation of the provisional circuit forming unit 41. FIG.
20 is a flowchart showing the operation of the affiliation adjustment unit 51. FIG.
FIG. 21 is a flowchart showing the operation of the affiliation adjustment unit 51.
22 is a flowchart showing the operation of the affiliation adjustment unit 51. FIG.
23 is a flowchart showing the operation of the operation rate adjustment unit 61. FIG.
24 is a flowchart showing the operation of the operation rate adjustment unit 61. FIG.
25 is a flowchart showing the operation of the operation rate adjustment unit 61. FIG.
FIG. 26 is a diagram showing an initial circuit for each improved cluster obtained by the route control unit 52 by reading from the route storage unit 97 in s501.
FIG. 27 is a diagram showing a random insertion selection point addition and removal circuit.
FIG. 28 is a diagram showing a random insertion selection point addition and removal circuit.
FIG. 29 is a diagram showing a random insertion selection point addition and removal circuit.
FIG. 30 is a diagram showing a random insertion selection point addition and removal circuit.
FIG. 31 is a diagram showing a random insertion selection point addition and removal circuit.
FIG. 32 is a diagram showing a random insertion selection point addition and removal circuit.
FIG. 33 is a diagram showing a random insertion selection point addition and removal circuit.
FIG. 34 is a diagram showing a random insertion selection point addition and removal circuit.
FIG. 35 is a diagram showing a random insertion selection point addition and removal circuit.
FIG. 36 is a diagram showing a random insertion selection point addition and removal circuit.
FIG. 37 is a diagram showing a random insertion selection point addition / division circuit.
FIG. 38 is a diagram showing a random insertion selection point addition and removal circuit.
FIG. 39 is a diagram showing a random insertion selection point addition and removal circuit.
FIG. 40 is a diagram showing a random insertion selection point addition and removal circuit.
FIG. 41 is a diagram showing a random insertion selection point addition and removal circuit.
FIG. 42 is a diagram showing a random insertion selection point addition and removal circuit.
FIG. 43 is a diagram showing a random insertion selection point addition and removal circuit.
FIG. 44 is a diagram showing a random insertion selection point addition and removal circuit.
FIG. 45 is a diagram showing a random insertion selection point addition and removal circuit.
[Explanation of symbols]
11 This device
11a CPU
11b RAM
11c ROM
11d interface
19 Hard disk
21 Initial information database
31 Cluster division
33 File reading part
35 Table initialization section
37 Cluster number calculator
41 Provisional circuit formation part
43 Fuzzy clustering calculator
45 Initial circuit creation section
51 Affiliation Adjustment Department
52 Route controller
53 Affiliation Change Processing Department
54 History check section
55 City Affiliation Change Processing Department
56 Affiliation change result setting section
61 Occupancy rate adjustment section
63 Operation rate adjustment control unit
65 Change trial section
67 Result output section
71 Random insertion part
73 N-opt part
75 Travel time calculator
91 Initial information storage unit
93 Number of vehicles storage
95 Cluster attribute value storage
97 Route memory
98 History storage
99 Time required storage

Claims (7)

Route data receiving means for receiving a plurality of route data including a starting point and a route around the plurality of points;
An overall load evaluation unit that evaluates a change in load of all routes that occur when each point included in a plurality of route data received by the route data receiving unit belongs to a route that does not include the point;
The point at which the affiliation is changed when the change in load evaluated by the overall load evaluation means indicates that the load is reduced as compared to before the affiliation of the point is changed, and the affiliation is changed The total of the load of all previous routes and the previous route, which is the route to which the point belongs before the change of affiliation, the post-affiliation route that is the route to which the affiliation is changed. Is a load change storage means for storing the associated degree as a change candidate data, and a degree of reduction indicating how much it is reduced compared to before the affiliation of the point is changed,
An extraction unit that extracts the change candidate data stored in the load change storage unit and that matches a condition that the degree of reduction is maximum;
With
Path adjustment device.         The route adjustment apparatus according to claim 1, further comprising route formation means for forming a route according to the change candidate data extracted by the extraction means.         The route adjustment apparatus according to claim 2, wherein the route data receiving unit receives route data including the route formed by the route forming unit and further adjusts the route. A change candidate history storage means for storing a history of change candidate data extracted by the extraction means;
The extraction means extracts from the change history data excluding the same change history data stored in the change candidate history storage means from the change candidate data stored in the load change storage means. 3. The route adjusting device according to 3.          5. The route data receiving unit receives route data including a route formed by the route forming unit until the extraction unit cannot extract change history data, and further adjusts the route. Route adjustment device.         A program for causing a computer to realize the route adjustment device according to claim 1.         A computer-readable storage medium storing a program for causing a computer to realize the path adjusting device according to claim 1.

Images