JP3534392B2 - Optimal delivery planning method and system - Google Patents

Description

Detailed Description of the Invention

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a delivery plan planning method for creating a delivery plan for leaving a distribution base or a warehouse in a distribution system and delivering a load to a plurality of delivery destinations. The present invention relates to a method of creating a delivery plan that is used to discover a transportation route for delivery and realizes reduction of logistics costs and improvement of services.

[0002]

2. Description of the Related Art The problem of a delivery plan in a physical distribution system is that a plurality of vehicles depart from a common physical distribution base, deliver loads to a plurality of destinations, and return to the original physical distribution base. It seeks something that minimizes. However, only one vehicle passes through each delivery destination. Further, each vehicle has an upper limit of the load amount, and there is a load amount constraint that the load amount is larger than the total of the load amount to the delivery destination visited by the vehicle. In addition, there is a travel distance constraint that the travel distance of each vehicle has an upper limit.

The step of creating a delivery plan created under such restrictions is usually divided into two steps. One is the problem of grouping in which delivery destinations are assigned to each vehicle.
The other is a route optimization problem in which order a vehicle goes through a delivery destination group determined by grouping. This is also called the so-called traveling salesman problem.

Regarding the problem of grouping, the sweep method and the saving method are known. These methods are described in the following documents. Gilbert Laporte: The Vehicle Routing Problem: An o
verview of exact and approximate algorithms: Europ
ean Journal of Operational Research 59 (1992) 345-
358 In addition, the full solution search method, which is a solution for the traveling salesman problem, and the NN method (Nearest method) used in the 2OPT method and grouping.
Knowledge about the Neighbor method) and the NI method (Nearest Insertion method) can be obtained from the following documents. Yoshitsugu Yamamoto, Mikio Kubo: Invitation to Traveling Salesman Problem: Asakura Shoten (1997)

[0005]

However, in the conventional delivery planning method, a single algorithm is used to perform grouping. For example, when the NN method is applied to the grouping, relatively good results can be obtained in many cases. However, in parts procurement applications and the like, some delivery destinations may be located far from the distribution base. In such a case, if the simple NN method is used for the problem of grouping, the delivery destinations that are relatively close to the distribution base are first grouped together, and then the delivery destinations that are far from the distribution base are grouped together. Tend to be summarized in. Therefore, this method has a problem that the total traveling distance becomes long as a whole. In general, the conventional delivery plan creation method may have an unsuitable result because the grouping method is not suitable depending on the distribution of the delivery destination positions.

Also, one algorithm has been used for route optimization. However, the number of delivery destinations included in one route varies. For example, the 2OPT method is efficient when the number of delivery destinations is large, but when the number of delivery destinations is small, it is more accurate than other methods. There is a problem of falling.

An object of the present invention is to provide an optimal delivery plan planning method and system capable of formulating an effective delivery plan for the distribution of positions of all delivery destinations.

[0008]

In order to achieve the above object, the optimal delivery plan planning method of the present invention generates a plurality of delivery plans by using a plurality of grouping strategies, and creates an optimal delivery plan among them. The feature is that it is selected.

That is, an input device for inputting input information relating to delivery planning, such as position information of a delivery destination, a package amount, and the number of delivery vehicles, and a plurality of delivery vehicles depart from a distribution base according to the input information. After the cargo is delivered to the delivery destination, a processing device that creates a delivery plan that minimizes the total mileage on the route that returns to the original distribution base, and an output device that outputs the created delivery plan A method for optimal delivery planning in a delivery planning system, wherein a plurality of delivery planning processes of algorithms having different planning strategies are executed in a single processing device in a time-sharing manner or in parallel by a plurality of processing devices, and executed. It is characterized in that the processing result that results in the shortest total travel distance is selected from the results and is output from the output device.

In the present invention, for example, an algorithm based on the following five grouping strategies is used. (1) Far-priority NN method (2) Far-priority NI method (3) Face-division NN method (4) Face-division NI method (5) Sweep method

Here, the terms "distance priority" and "division of area" indicate the delivery destination to which the delivery vehicle goes first, that is, the seed designation method. The NN method, the NI method, and the sweep method are algorithms that generate routes around several delivery destinations. Therefore, the "far-distance priority NN method"
This is a grouping method in which the seed designation method is "far away priority" and the algorithm for the delivery destination is the "NN" method. Far priority NI method, area division NN method, area division N
Method I has the same meaning.

In the case of far-distance priority, among the undelivered delivery destinations, the delivery destination farthest from the distribution base is designated as the seed. In the direction division, for example, for each fan-shaped partial space (hereinafter, referred to as a direction) generated by dividing a space (delivery target area) by a straight line that passes through several distribution bases, the distribution destinations located in the direction are divided. Assign a number of seeds in that direction that is proportional to the sum of the luggage.

In the NN method, starting from the seed, while the constraint condition is satisfied, the delivery destination closest to the last visited delivery destination is visited one after another. If the constraint condition is not satisfied, the generation of one route is completed at the delivery destination that has been visited so far.
As before, continue to generate routes, starting with the seed, while the undelivered destination remains.

The NI method is the same as the NN method except that the delivery destination having the smallest increment of the traveled distance when it is inserted at an appropriate position on the route is taken out.

The sweep method is the same as the NN method except that the delivery destinations are taken out in ascending order of the angle formed by the x-axis (or y-axis) and the straight line connecting the delivery destination and the physical distribution base.

Further, the present invention is characterized in that the route optimization method is changed according to the number of delivery destinations included in the route. Specifically, an efficient full route search method is applied to a route having a relatively small number of delivery destinations, and a high-speed 2OPT method is applied to a route having a large number of delivery destinations to efficiently optimize the route. To realize.

[0017]

BEST MODE FOR CARRYING OUT THE INVENTION Hereinafter, the present invention will be described in detail based on illustrated embodiments. FIG. 1 is a block diagram of a hardware configuration showing an embodiment of an optimal delivery planning system of the present invention. The optimum delivery planning system of this embodiment comprises a keyboard 10, a display 20, a central processing unit 30, a main storage device 40 and a secondary storage device 50. A keyboard 10 and a display 20 are connected to the central processing unit 30, and using the keyboard 10, parameter information such as the position of the delivery destination in the delivery target area, the amount of baggage, the vehicle upper limit value, and the mileage upper limit value,
Also, various commands related to the creation of a delivery plan are input. The input parameter information and commands are displayed on the display 20. On the display 20, the optimum delivery route created based on the input parameter information is displayed by characters or a map. The main storage device 40 stores a delivery plan planning program group 41 for planning a delivery route by a plurality of planning strategies. Furthermore, a work area 42 for processing data is secured. The secondary storage device 50 stores data such as the position of the delivery destination, the amount of luggage and the upper limit of the loading amount of the vehicle, and the processing result of the command.

FIG. 2 is an overall configuration diagram of an optimum delivery plan making process using five grouping strategies. In the present embodiment, first, the delivery priority planning process of the distant priority NN method (step 101), the delivery priority planning process of the distant priority NI method (step 102), the delivery priority planning process of the area division NN method (step 103), The delivery destination is assigned to each vehicle by the distribution plan formulation process of the direction division NI method (step 104) and the delivery plan formulation process of the sweep method (step 105). Next, a route optimization process (step 106-)
In 110), a delivery plan is created for each delivery destination group so that the route of the vehicle becomes the shortest. Finally, this 5
The optimal delivery plan is selected from the two delivery plans (step 111), and the process is completed.

Here, the five delivery plan planning processes of steps 101 to 105 are constituted by corresponding programs and are stored in the main storage device 40 as a delivery plan planning program group 41 of FIG. In this embodiment, since there is only one processing device 30, the central processing device 30
Performs time-divisional five delivery plan planning processing, and further performs route optimization processing (steps 106 to 110) in time division, and finally selects an optimal delivery plan from the five delivery plan planning processing results. To do.

The present invention is not limited to the case where the five delivery planning processes are performed in a time-division manner, but five central processing units 30 are prepared, and the planning process and the optimization process are executed in parallel by these. It is also possible to configure one central processing unit so as to select the most suitable delivery plan from among the five delivery planning results.

FIG. 3 is a flow chart for explaining the algorithm of the delivery planning process of the distant priority NN method. First, in step 201, the vehicle t is set to the 0th vehicle. Next, in step 202, it is determined whether there is any undelivered delivery destination. If not, end. If yes, step 203
Then, the delivery destination i that is farthest from the distribution base among the delivery destinations that have not been delivered is set as the delivery destination i, and the delivery destination i is already delivered. Delivery destination i is a seed with priority to the distance. The information about each vehicle t is represented by the elements of the array T [t] of the structure. (1) T [t] .L is the amount of luggage carried by the vehicle t. (2) T [t] .D is the traveling distance of the vehicle t. (3) T [t] .R is an array of delivery destinations, which is the route of the vehicle t.

In step 204, a route connecting the distribution base of the vehicle t and the seed is generated as follows. (1) Substitute the package amount of the delivery destination i into T [t] .L. (2) Substitute T [t] .D with twice the distance between the delivery destination i and the distribution base. (3) Substitute the delivery destination i at the beginning of T [t] .R.

Next, at step 205, it is judged whether there is any undelivered delivery destination. If not, end. If so, in step 206, the delivery destination ii is the delivery destination ii that is closest to the delivery destination i that has not been delivered. Next, in step 207, the delivery destination ii
Calculate the increment D = d (i, ii) + d (depot, ii) d (depot, i) of the mileage when is added to the route of vehicle t. Where d is the distance function and depot is the physical distribution point.

Next, at step 208, it is judged whether or not the load capacity constraint and the travel distance constraint are satisfied. The load capacity constraint is that even if the vehicle t loads a package at the delivery destination ii, the upper limit of the given load capacity is not exceeded. Further, the mileage constraint is that even if the vehicle t further increases the mileage by D, it does not exceed the upper limit of the given mileage. If these two restrictions are satisfied, in step 209, the delivery destination ii is set so that the vehicle t can pass through. That is, the array of structures T
Change [t] as follows: (1) Add the package amount of the delivery destination ii to T [t] .L. (2) Add D to T [t] .D. (3) Add delivery destination ii to the end of T [t] .R.

Further, the delivery destination ii is set as delivered. Next, in step 210, the delivery destination ii is substituted for the delivery destination i, and the process returns to step 205 to loop. Step 208, 2
If the two constraints are not satisfied, in step 211, the vehicle t
Is set as the next vehicle and the process returns to step 202 to loop.

FIG. 4 is a flow chart for explaining the algorithm of the far priority NI method. In step 301, the vehicle t is set to the 0th vehicle. Then step 302
Then, the seed i with the distant priority is acquired and the seed i is delivered. Next, at step 303, the vehicle t is set to pass the seed i. 3 for algorithm after step 304
There is a heavy loop. With the loop of steps 304 and 317
loop of steps 306, 307, 316 for i and j
It is a loop of steps 309, 310 and 315 regarding.

At step 304, it is determined whether there is any undelivered delivery destination. If not, it exits the loop. If so, in step 305, a large constant M suitable for the variable min_d
Substitute AX. Next, at step 306, the 0th delivery destination is assigned to the delivery destination i. In step 307, i is compared with the number max_i of all delivery destinations. If i is not smaller than max_i, the loop for i is exited and the process proceeds to step 317.
If it is smaller, it is determined in step 308 whether the delivery destination i has been delivered. If it has been delivered, the process proceeds to step 316. If it has not been delivered, enter the loop for j. First, in step 309, 0 is substituted for the variable j. Next, in step 310, the variable j is compared with the length of the array T [t] .R. If j is large, the loop for j is exited and step 316 is performed.
Proceed to. If j is not large, the increment D of the mileage is calculated in step 311. As described above, T [t] .R is an array of delivery destinations and represents the route that the vehicle t takes. T
[t] .R [j] is the (j + 1) th delivery destination after the vehicle t departs from the distribution base. D represents the increment of the mileage when the delivery destination i is inserted between the jth and (j + 1) th. Expressed as an equation, D = d (T [t] .R [j1], i) + d (i, T [t] .R [j]) d (T [t] .R [j1], T [t ].
R [j]).

Next, in step 312, the variable min_d is compared with the increment D of the traveling distance. If min_d is not greater than D, proceed to step 315 and repeat the loop for j. If min_d is larger than D, go to step 313,
It is determined whether the load capacity constraint and the travel distance constraint are satisfied.
If not, proceed to step 315 and repeat the loop for j. If satisfied, D, I, and j at this time are substituted into min_d, min_I, and min_j, respectively, and the process proceeds to step 315 to repeat the loop for j. After all, here i and j
Gets the minimum value of D for.

FIG. 5 is a flowchart showing the details of step 317 to be executed next after exiting the loop for i in step 307. First, in step 401, min_
Determine if d is MAX. If it is MAX, it means that min_d has not changed, that is, the delivery destination to be inserted has not been found, and therefore the extension of the route of the vehicle t is stopped. Then, in step 402, the vehicle t is changed to the next vehicle. Further, in step 403, the seed i having the distant priority is acquired and the seed i is delivered. Next, at step 404, the vehicle t is set to pass the seed i. On the other hand, if min_d is not MAX, in step 405, the vehicle t
Sets delivery destination min_i to visit (min_j + 1) th and makes delivery destination min_i already delivered.

The direction division NN method calls procedures allocate and reallocate for allocating vehicles to a direction. In the following, al first
The locate and reallocate algorithms are explained.

FIG. 6 is a flow chart for explaining the allocate algorithm. In step 501, the direction i including each delivery destination is calculated, and FL [i] is obtained by adding the amount of the delivery destination. Next, at step 502, the initial value N of the number of vehicles is assigned to each direction i as a number FT [i] proportional to FL [i]. However, the division value is an integer here. Moreover, the sum TFT about i of the number FT [i] of allocations is calculated.
Next, in step 503, the remainder of division is put into W [i]. Then, in steps 504 and 505, the remaining (N-TFT) vehicles that have not been assigned are assigned to the direction i in the descending order of W [i]. That is, FT [i] is incremented by 1. Next, in step 506, the number of vehicles FT [i] in each direction i is randomly selected as the delivery destination, and a route connecting the distribution base and the seed is generated using this as the seed. Further, the delivery j is already delivered. Finally, in step 507, to the variable maxtruck
Substitute N.

Reallocate obtains the number of vehicles in proportion to the total remaining luggage amount TRL and allocates it to each direction when the effective vehicles are exhausted. reallocate is basically al except for the following two points
Same as locate. First, the total number of assigned vehicles is not the initial value N, but is the number IN obtained by dividing the total remaining luggage amount TRL by the upper limit of the vehicle loading amount. Second, the number of vehicles in each direction i is proportional to the amount of left luggage RFL [i], not the amount of luggage FL [i] in each direction. The total remaining luggage amount TRL is the total amount of undelivered delivery destination luggage, and the remaining luggage amount RFL [i] in each direction i is the total amount of undelivered delivery destinations in direction i.

FIG. 7 is a flow chart for explaining the algorithm of the face division NN method. The face-division NN method includes double loops. The outer loop ends when all the shipping destinations are included in the route of the vehicle. The inner loop starts at step 603 with vehicle t 0 and ends when all delivery destinations are included in the vehicle route or when vehicle t reaches maxtruck. First, in step 601, allocate is called and all N vehicles are allocated to the direction. next,
In step 602, it is determined whether there is any undelivered delivery destination. If not, end. If there is, the vehicle t is set to 0 in step 603.

Next, at step 604, it is determined whether there is a delivery destination that has not been delivered and the vehicle t is smaller than maxtruck. If not, the process returns to the head step 602 of the outer loop.
If so, it is determined in step 605 whether the vehicle t is valid. The vehicle t is valid at the initial value. Further, in step 611, the vehicle t is invalidated. If it is not valid, the value of t is incremented by one in step 615, and the process returns to the first step 604 of the inner loop. If valid, step 606.
Set the end of T [t] .R to i, and the undelivered destination closest to i to ii. Next, in step 607, the increment D of the mileage D = d (i, ii) + d (depot, ii) d (depot, i) is calculated.

Next, at step 608, it is judged whether the load amount constraint and the traveling distance constraint are satisfied. If these two restrictions are satisfied, in step 609 the delivery destination ii is set so that the vehicle t can pass through. Further, the delivery destination ii is already delivered. Next, at step 610, the value of t is incremented by one. If the two constraints are not satisfied, t is invalidated in step 611, and it is determined in step 612 whether there is another valid vehicle. If there is, the value of t is incremented by 1 in step 613. If not,
Call step 614 reallocate to reallocate the vehicle. In either case, the first step 6 of the inner loop
Return to 04.

FIG. 8 is a flow chart for explaining the algorithm of the face division NI method. First, step 701
In the above, allocate is called to allocate N vehicles in the direction. Next, in step 702, it is determined whether there is any undelivered delivery destination. If not, end. If there is, the vehicle t is set to 0 in step 703. Next, in step 704, it is determined whether there is a delivery destination that has not been delivered and the vehicle t is smaller than maxtruck. Otherwise, it returns to step 702. If so, it is determined in step 705 whether the vehicle t is valid. The vehicle t is valid at the initial value. Further, in step 718, the vehicle t may become invalid.
If it is not valid, the value of t is incremented by 1 in step 719, and the process returns to step 704. If valid, step 70
Go to 6.

Steps 706-717 are exactly the same as steps 305-316 of the far-first NI method. D is the increment of the mileage when the delivery destination i is inserted between the jth delivery destination and the (j + 1) th delivery destination of the route through which the vehicle t passes. Here, the minimum value of D is obtained by the double loop for i and j, and D, I, and j at that time are min_d, min_I, and min, respectively.
Substitute for _j and proceed to step 718.

FIG. 9 is a flowchart showing details of step 718 to be executed next after exiting from the loop for i in step 708. First, in step 801, min_
Determine if d is MAX. If it is MAX, it means that min_d has not changed, that is, the delivery destination to be inserted was not found. Therefore, in order to stop the extension of the route of the vehicle t, the vehicle t is invalidated in step 802. . Next, in step 803, it is determined whether there is another valid vehicle. If there is, the value of t is incremented by 1 in step 804. Otherwise, in step 805, the reallocate described earlier
To reassign the vehicle.

On the other hand, if min_d is not MAX, step 8
At 06, the vehicle t is set to visit the delivery destination min_i at the (min_j + 1) th time, and the delivery destination min_i is set to be delivered. Next, at step 807, the value of t is incremented by one.

FIG. 10 is a flow chart for explaining the algorithm of the sweep method. In the sweep method, vehicles pass through the delivery destination in ascending order of angle. What is the delivery angle?
The angle formed by the x-axis (or y-axis) and the straight line that connects the delivery destination and the distribution base. Also, the x-axis passes through the logistics base,
It is a straight line that faces east-west.

In step 901, the vehicle t is set to the 0th vehicle. Next, in step 902, it is determined whether there is a delivery destination that has not been delivered. If not, end. If so, in step 903, the delivery destination i having the smallest angle among the delivery destinations that have not been delivered is set as the delivery destination i, and the delivery destination i is set as delivered. Step 9
At 04, a route connecting the distribution base of the vehicle t and the delivery destination i is generated. Next, in step 905, it is determined whether there is a delivery destination that has not been delivered. If not, end. If so, step 90
In step 6, the smallest undelivered delivery destination is the delivery destination ii.

Next, at step 907, the delivery destination ii is set to the vehicle t.
Calculate the mileage increment D = d (i, ii) + d (depot, ii) d (depot, i) when added to the route. Next, at step 908, it is determined whether the load capacity constraint and the travel distance constraint are satisfied. If these two constraints are satisfied, in step 909, the delivery destination ii is set so that the vehicle t can pass through. Further, the delivery destination ii is set as delivered. Next, in step 910, the delivery destination i is substituted for the delivery destination i, and the process returns to step 905 to loop. In step 908,
If the two constraints are not satisfied, then in step 911, the vehicle
Let t be the next vehicle and return to step 902 to loop.

Next, route optimization will be described. The vehicle routes resulting from the grouping are not necessarily optimal. Therefore, it is necessary to rearrange the order of the delivery destinations included in the route to generate a shorter route. For routes with relatively few delivery destinations, the full solution search method gives fully optimized answers. For many routes, the full solution search method is too slow. On the other hand, the 2OPT method is less accurate, but the processing is faster. Therefore, the route is optimized by applying the full solution search method when the number of delivery destinations included in the route is less than or equal to a threshold value, and by applying the 2OPT method when the number of delivery destinations included in the route exceeds the threshold value.

Since the algorithms for the full solution search method and the 2OPT method are known in the literature, their explanations are omitted.

Note that the five programs for the delivery planning process are not limited to the form of being executed by one processing unit in a time-sharing manner, for example, the form of being executed in parallel by five central processing units. 3 with 2 central processing units
Alternatively, the two planning processes may be shared and executed.

[0046]

As is apparent from the above description, according to the present invention, the grouping using a plurality of delivery planning strategies and the route optimizing process using two kinds of methods are performed.
Since the delivery plan is designed, an effective delivery plan can be prepared for a wide range of distribution destination positions.

[Brief description of drawings]

FIG. 1 is a hardware configuration diagram showing an embodiment of an optimal delivery planning system of the present invention.

FIG. 2 is an overall configuration diagram of an optimal delivery planning process using five grouping strategies.

FIG. 3 is a flowchart showing an algorithm of a far-first priority NN method.

FIG. 4 is a flowchart showing an algorithm of the far-first NI method.

5 is a flowchart showing details of step 317 of FIG. 4. FIG.

FIG. 6 is a flowchart showing an algorithm for assigning a vehicle to a direction.

FIG. 7 is a flowchart showing an algorithm of a face division NN method.

FIG. 8 is a flowchart showing an algorithm of a face division NI method.

FIG. 9 is a flowchart showing details of step 718 in FIG.

FIG. 10 is a flowchart showing an algorithm of the sweep method.

[Explanation of symbols]

10 ... Keyboard, 20 ... Display, 30 ... Central processing unit, 40 ... Main storage unit, 41 ... Delivery planning program group, 42 ... Work area, 50 ... Secondary storage unit.

─────────────────────────────────────────────────── --Continued from the front page (56) References JP-A-5-61848 (JP, A) JP-A-8-153085 (JP, A) JP-A-4-317168 (JP, A) JP-A-7- 175504 (JP, A) JP 10-253374 (JP, A) JP 9-311702 (JP, A) JP 8-329149 (JP, A) JP 10-55349 (JP, A) JP-A-10-303126 (JP, A) JP-A-7-234997 (JP, A) JP-A-4-71062 (JP, A) (58) Fields investigated (Int.Cl. ⁷ , DB name) G08G 1/00 B65G 1/137 G06F 17/00 G06F 17/10

Claims (6)

(57) [Claims] Claim: What is claimed is: 1. An input device for inputting input information relating to delivery planning, such as location information of distribution bases and delivery destinations, amount of packages, number of delivery vehicles, etc., input information input and processing results.
The storage device that stores the
Read out the force information, multiple delivery vehicles departed from the distribution base,
After delivering the load to multiple destinations, output a single or multiple processing device that creates a delivery plan that minimizes the total mileage on the route back to the original distribution base, and the created delivery plan A method for planning an optimum delivery plan in a delivery plan planning system including an output device for: (a) input relating to a delivery plan stored in the storage device;
The information is read and not yet delivered as the delivery destination for the delivery vehicle.
Select the delivery destination farthest from the distribution base
After that, select the delivery destination closest to the delivery destination in order
First, which is composed of an algorithm for searching a delivery route by
Delivery planning process, (b) input related to the storage device to the stored delivery schedule
The information is read and not yet delivered as the delivery destination for the delivery vehicle.
Select the delivery destination farthest from the distribution base
Then, after that, the increment of the mileage when inserted in the delivery route
Search the delivery route by sequentially selecting the delivery destination with the smallest
Second delivery plan planning processing configured by an algorithm, (c) Input relating to the delivery plan stored in the storage device
Read information and deliver in all directions centered on the delivery base
The area is divided into multiple areas, and delivery vehicles are
One of the undelivered delivery destinations as the first delivery destination
The number of deliveries that is proportional to the sum of the package amount of the delivery destinations located in the plane
Select the destination and then select the closest destination to the destination.
It consists of an algorithm that sequentially selects and searches delivery routes.
Third delivery plan planning process, (d) input relating to the delivery plan stored in the storage device
Read information and deliver in all directions centered on the delivery base
The area is divided into multiple areas, and delivery vehicles are
One of the undelivered delivery destinations as the first delivery destination
The number of deliveries that is proportional to the sum of the package amount of the delivery destinations located in the plane
Distance traveled when selecting the destination and inserting it in the delivery route after that
Select delivery destinations with the smallest separation increments one after another
4th delivery planning consisting of search algorithms
Processing, (e) input relating to the delivery plan stored in the storage device
The information is read, and the straight line connecting the delivery destination and the distribution base and the delivery area
Delivered in ascending order of angle with the x-axis or y-axis on the map
It consists of an algorithm that selects the destination and searches the delivery route.
Multiple deliveries composed of a fifth delivery planning process
Time-sharing execution of the planning process with the single processing device, and
Are executed in parallel by multiple processing units, and the processing results are stored in the storage device.
The first step of storing in the storage device and the processing result stored in the storage device,
The processing result with the shortest separation is obtained by
Output device selected by any of a number of processing devices
An optimal delivery plan planning method, comprising a second step of outputting from . 2. In the second step, for each of the results of a plurality of delivery planning processes, one delivery vehicle departs from the distribution base and delivers the load to a plurality of delivery destinations, A full solution search method is applied to a delivery route in which the number of delivery destinations on the delivery route returning to the distribution base is smaller than a threshold value, and a 2OPT method is applied to a delivery route in which the number of delivery destinations is large, thereby optimizing. The delivery planning method according to Item 1. 3. An input device for inputting input information relating to delivery planning such as location information of distribution bases and delivery destinations, quantity of packages, number of delivery vehicles, and a storage device for storing the input information input and processing results. , Read the input information related to the stored delivery plan, multiple delivery vehicles leave the distribution base,
After delivering the load to multiple delivery destinations, a processing device that creates a delivery plan that minimizes the total mileage on the route that returns to the original distribution base, and an output device that outputs the created delivery plan are provided. A delivery plan planning system comprising: (a) an undelivered delivery destination as a delivery destination to which a delivery vehicle first travels, where (a) the input information relating to the delivery plan stored in the storage device is read. Selects the delivery destination farthest from the distribution base, then sequentially selects the delivery destination closest to the delivery destination, searches the delivery route, and stores the processing result in the storage device. And (b) reading the input information relating to the delivery plan stored in the storage device, and selecting the delivery destination farthest from the distribution base among the delivery destinations not yet delivered as the delivery destination that the delivery vehicle goes around first. After that, delivery route Insert traveling distance increment of time has is sequentially selects destination is minimum explore the delivery path,
Second delivery plan planning processing means for storing the processing result in the storage device, and (c) reading the input information relating to the delivery plan stored in the storage device, and carrying out a delivery target area in all directions centering on the delivery point Is divided into multiple destinations, and for each destination, the number of delivery destinations that are proportional to the sum of the package amount of the delivery destinations located within that destination among the delivery destinations that the delivery vehicle goes around first Selecting a delivery destination that is closest to the delivery destination thereafter, searching for a delivery route, and storing the processing result in the storage device; and (d) the storage Read the input information related to the delivery plan stored in the device, divide the omnidirectional delivery target area centered on the delivery base into multiple directions, and do not deliver as the delivery destination that the delivery vehicle goes around first in each direction Located within that destination Select a number of delivery destinations that is proportional to the sum of the package amount of the delivery destinations, and then sequentially select the delivery destinations that have the smallest increment of the mileage when inserted into the delivery route, and search the delivery route. Fourth delivery plan planning processing means for storing the processing result in the storage device, and (e) reading input information relating to the delivery plan stored in the storage device, and a straight line connecting the delivery destination and the distribution base and a delivery area map Fifth delivery plan planning processing means for selecting delivery destinations in descending order of angle with the x-axis or y-axis to search delivery routes and storing processing results in the storage device; and storing in the storage device. An optimum delivery plan planning system, comprising: a selected output unit that reads out the processed result, selects a processing result having the shortest total travel distance, and outputs the selected processing result from the output device. Is wherein said selective output means, for each of the plurality of delivery planning process results, after the delivery vehicle of one departs distribution bases, and deliver cargo to a plurality of destinations, the original distribution It is characterized by comprising means for optimizing by applying the full solution search method to the delivery routes having a smaller number of delivery destinations on the delivery route returning to the base and the 2OPT method to the delivery routes having a larger number of delivery destinations. The delivery planning system according to claim 3. 5. An input device for inputting input information relating to delivery planning such as location information of distribution bases and delivery destinations, quantity of packages, number of delivery vehicles, and a storage device for storing the input information input and processing results. , Read the input information related to the stored delivery plan, multiple delivery vehicles leave the distribution base,
After delivering the load to multiple destinations, multiple processing devices that create a delivery plan that minimizes the total mileage on the route that returns to the original distribution base, and an output device that outputs the created delivery plan And a plurality of processing devices read (a) the input information related to the delivery plan stored in the storage device, and the undelivered destination is the delivery destination that the delivery vehicle goes around first. A first delivery destination is selected which is the farthest from the distribution base among the delivery destinations, and thereafter the delivery destination closest to the delivery destination is sequentially selected to search the delivery route, and the processing result is stored in the storage device. Delivery plan planning processing means, (b) reading the input information relating to the delivery plan stored in the storage device, and selecting the delivery destination farthest from the distribution base among the delivery destinations not yet delivered as the delivery destination that the delivery vehicle goes around first. Select and after Incremental mileage when inserted into the delivery path sequentially selects destination is minimum explore the delivery path,
Second delivery plan planning processing means for storing the processing result in the storage device, and (c) reading the input information relating to the delivery plan stored in the storage device, and setting the delivery target area in all directions centering on the delivery point. Divide into multiple destinations, and for each destination, the number of delivery destinations that are proportional to the sum of the package amount of the delivery destinations located within that destination among the delivery destinations that the delivery vehicle goes around first Third delivery plan planning processing means for selecting a delivery destination, sequentially selecting the delivery destination closest to the delivery destination thereafter, searching the delivery route, and storing the processing result in the storage device, (d) in the storage device Read the input information related to the stored delivery plan, divide the omnidirectional delivery target area centered on the delivery base into multiple destinations, and deliver the undelivered destination as the first destination of the delivery vehicle for each destination Located in that direction from the inside Select a number of delivery destinations that is proportional to the sum of the package quantity of the destinations, and then sequentially select the delivery destinations that have the smallest increments in the mileage when inserted into the delivery route, search the delivery route, and process. Fourth delivery plan planning processing means for storing the result in the storage device, (e) reading input information relating to the delivery plan stored in the storage device, and a straight line connecting the delivery destination and the distribution base and the delivery area map A plurality of delivery plan processing means including fifth delivery plan planning processing means for selecting delivery destinations in descending order of angle with the x-axis or y-axis to search delivery routes and storing the processing results in the storage device. Each of the processing devices has a delivery plan planning unit that does not overlap with other processing devices, and any one of the processing devices reads the processing results of the plurality of processing devices stored in the storage device, and the processing result that the total traveling distance becomes the shortest. Select the output Optimal delivery planning system, characterized in that it comprises the selective output means for laid et output. Is wherein said selective output means, for each of the plurality of delivery planning process results, after the delivery vehicle of one departs distribution bases, and deliver cargo to a plurality of destinations, the original distribution It is characterized by comprising means for optimizing by applying the full solution search method to the delivery routes having a smaller number of delivery destinations on the delivery route returning to the base and the 2OPT method to the delivery routes having a larger number of delivery destinations. The delivery planning system according to claim 5.