JP7735854B2 - Delivery plan creation method and device - Google Patents

Description

The present invention relates to a delivery plan creation method and device that can create a delivery plan for delivering packages to multiple destinations departing from a logistics base (hereinafter also referred to as a depot) in a logistics system.

Patent Document 1 describes a delivery plan creation device that solves delivery planning problems and enables the creation of delivery plans for delivering cargo to multiple destinations. The device includes an input device that inputs information about each order and master data related to delivery plan creation, a processing device that creates a delivery plan for multiple vehicles to deliver cargo to multiple destinations, an output device that outputs the created delivery plan, and order grouping means that divides orders and creates groups based on distance data between destinations, and executes delivery plan creation processing for each divided order group.

Japanese Patent Application Laid-Open No. 2004-238129

The delivery planning problem involves determining the shortest total travel distance for multiple delivery vehicles departing from a depot to deliver packages to multiple destinations. A common approach to delivery planning problems is to formulate the problem conditions into a mathematical equation (objective function) and solve it using a computer. Patent Document 1 describes a delivery planning method that reduces the search space and speeds up calculations by geographically grouping delivery destinations into groups based on close proximity and limiting delivery routes to those groups.

However, because the method in Patent Document 1 groups delivery destinations, there are delivery routes that cross groups, and these delivery routes are eliminated. With this method, if the eliminated delivery routes include a good route that minimizes the objective function, there is a possibility that a solution that deviates from the optimal value will be obtained.

The present invention has been developed in consideration of the above-mentioned problems with the conventional technology, and one of its objectives is to provide a delivery plan creation method and device that can reduce the amount of calculations while maintaining a moderate degree of flexibility in route selection when creating a delivery plan.

The delivery planning method of the present invention creates a circular route that minimizes an objective function that formulates the sum of the total travel distances of a vehicle from departing from a delivery base, traveling the route distance between delivery destinations, and returning to the delivery base. When delivering packages from one delivery base to N delivery destinations, the method calculates the objective function by first excluding, in descending order of distance, the N-1 routes from one delivery destination to the other N-1 delivery destinations, from the longest route down to an exclusion rate exceeding 0%, in order of distance.

The delivery planning device of the present invention creates a circular route that minimizes an objective function that formulates the sum of the total travel distances of a vehicle from departing from a delivery base, traveling the route distance between delivery destinations, and returning to the delivery base. When delivering packages from one delivery base to N delivery destinations, the device is characterized by including a route calculation unit that, before calculating the objective function, calculates the objective function by first excluding, from N-1 routes from one delivery destination to the other N-1 delivery destinations, routes with an exclusion rate exceeding 0%, in descending order of distance, starting from the longest route.

The delivery planning method and device of the present invention can, for example, reduce the amount of calculation required for the objective function.

1 is a block diagram showing an example of the configuration of a delivery planning device according to an embodiment; 10 is a graph illustrating the pre-exclusion of routes up to an exclusion rate M in descending order of distance from the longest route among multiple routes between delivery destinations used when calculating an objective function in the delivery plan planning method of the delivery plan planning device of the embodiment. 10 is a graph showing changes in the value of the objective function (total travel distance) with respect to the calculation time executed by the delivery plan creation method of the present embodiment. 10 is a flowchart showing an operation when a delivery route is calculated using the delivery plan planning device of the present embodiment. 10 is a flowchart showing an operation when updating a table in an optimal M value storage unit of the delivery plan planning device of the present embodiment. 10 is a graph illustrating an operation for determining an optimal M value in a table of an optimal M value storage unit of the delivery plan planning device according to the present embodiment.

The following describes a delivery plan creation method and a delivery plan creation device according to an embodiment of the present invention, with reference to the drawings. Note that in the embodiments, components that have substantially the same functions and configurations are designated by the same reference numerals, and redundant explanations will be omitted.

Figure 1 is a block diagram showing the general configuration of a delivery plan development device 10 that executes the delivery plan development method of this embodiment.

The delivery plan planning device 10 is a computer device that includes a CPU (Central Processing Unit) 11, a storage device 12, an input unit 13 and an output unit 14 that serve as interfaces for inputting parameters from the user and returning calculation results to the user, and a communication unit 15, all of which are connected to each other via an internal bus (not shown). Input parameters and the like are acquired by the delivery plan planning device 10 via the input unit 13 and the communication unit 15.

The storage device 12 may be, for example, a RAM (Random Access Memory), HDD (Hard Disk Drive), SSD (Solid State Drive), or flash memory, which stores various programs and data and serves as a working area for the CPU 11. The input unit 13 may be, for example, a keyboard, mouse, touch panel, or numeric keypad for inputting data. The output unit 14 may be, for example, a display or touch panel for displaying data to the user for outputting data. The communication unit 15 communicates with the network device 100 (or the internet) via a specified cable, either wired or wirelessly, to send and receive data. The input unit 13 and output unit 14 may also include a USB (Universal Serial Bus) for connecting an external device, such as a recording medium.

The overall operation of the delivery planning device is controlled by a CPU that runs an operating system (OS) software program and a delivery planning application (hereinafter referred to as the delivery planning app) installed in the storage device 12.

Examples of the delivery planning device 10 include a server device or a PC (Personal Computer) that is an electronic device capable of wired or wireless communication with other network devices 100 such as PCs over the Internet.

The delivery planning application is installed and stored in the storage device 12.
(1) A route calculation unit FCT that generates a delivery plan that creates a traveling route that minimizes an objective function that formulates the total total distance traveled by a vehicle from a delivery point to the delivery point, traveling the route distance between delivery destinations, and returning to the delivery point, using an exclusion rate (described later);
(2) an input parameter storage unit PKP (described later in a second embodiment) for storing input parameters such as variables and constraints of the delivery plan;
(3) An optimum M value storage unit FJP (to be described later in a second embodiment) for storing the exclusion ratio used in calculating the objective function.

(First Example)
The delivery plan creation method of this embodiment is executed mainly by using the route calculation unit FCT in the delivery plan creation device 10.

When multiple trucks k each depart a depot to deliver cargo to multiple destinations (destination i to destination j), the delivery planning problem of minimizing the total traveling distance can be expressed as follows using a mathematical model that uses, as examples of input parameters, the travel distance between destinations (distance d _ij is the main input parameter), the number of vehicles, the amount of cargo to be delivered to each destination, and the maximum load capacity of the vehicles. Note that the depot is assigned the number 0, the N destinations are assigned the numbers 1, 2, ..., N, and the K vehicles are assigned the numbers 1, 2, ..., K.

The objective function in this delivery planning problem, i.e., the total distance traveled, is given by equation (1). The variable X _ijk in equation (1) is defined as a binary variable that takes the value 1 when vehicle k moves from delivery destination i to delivery destination j, and takes the value 0 otherwise.

The objective function in equation (1) represents minimizing the total travel distance of all vehicles. Equations (2) to (6) represent the constraints.

(Input parameters: constraints)
Q: Maximum load capacity of the vehicle N: Set of delivery destinations K: Set of vehicles (k = 1 to K)
r _i : Requested quantity for delivery destination i. d _ij : Travel distance from delivery destination i (i=1 to N) to delivery destination j (j=1 to N, j≠i).

Equations (2) and (3) mean that one vehicle visits each destination only once. Equation (4) limits the total destination demand on any delivery route to less than the vehicle's maximum load capacity. Equations (5) and (6) mean that all vehicles depart and return to the depot.

Note that input parameters also include time constraints such as designated delivery time, travel time, and loading and unloading time, but these are omitted from the above model.

The values of the variables that minimize the objective function while satisfying these constraints are found. The resulting variable values correspond to the desired delivery route.

The number of variables _Xijk is ^KN2 . As the number of delivery destinations and the number of vehicles increase, the number of variables also increases accordingly. The number of possible combinations of variables (hereinafter sometimes referred to as the search space) increases exponentially as the number of variables increases, making it difficult to solve.

In this embodiment, therefore, it has been empirically determined that, when observing optimized delivery routes obtained through experiments and other processes in previous delivery planning, most vehicle movements are to delivery destinations that are close to each other, and that movements to distant delivery destinations are rare. Therefore, a method is considered that makes effective use of this empirical knowledge to reduce the amount of calculations.

Destination numbers j are sorted in descending order of distance from destination i, i.e., in descending order of the value of d _ij . The set of numbers that fall within a certain M% exclusion rate (hereinafter simply referred to as M) from the top of the sorted list of j is called j*. Routes traveling from i to j* are excluded from the solution search. In other words, X _ijk = 0 (j∈j*), and these variables are treated as constants. There are no restrictions on travel from the depot to the destination or from the destination to the depot; in other words, X _0jk and X _i0k (i = 1 to N, j = 1 to N) remain variables.

The method of this embodiment solves a delivery planning problem for delivering packages from a delivery center to N destinations. Of the N-1 routes from a given destination to the other N-1 destinations, a group of long-distance routes is excluded in advance at an exclusion rate M and excluded from the solution search (only a fixed rate m (where m + M = 1) of short-distance routes is included in the solution search).

This delivery planning method is characterized by the fact that, when delivering packages from one delivery center to N delivery destinations, before calculating the objective function of equation (1) above, the objective function is calculated by first excluding, from among the N-1 routes from one delivery destination to the other N-1 delivery destinations, routes with an exclusion rate M exceeding 0% in descending order of distance, starting from the longest route, as shown in Figure 2, for example.

By implementing the method of this embodiment, it is possible to reduce the number of variables in the exclusion percentage M %. The solution search space becomes smaller accordingly, reducing the amount of calculation required for the objective function. This effect becomes more pronounced as the value of M is increased. However, increasing M too much will significantly limit the routes available. If the excluded routes include an optimal or near-optimal route, the resulting objective function will deviate from the minimum value. Taking these trade-offs into consideration, the optimal value of M is determined as appropriate.

Therefore, in this embodiment, there are no restrictions on movement from the depot to the delivery destination, or from the delivery destination to the depot. Therefore, the first delivery destination can be freely selected and determined regardless of distance. This has the effect of preventing routes from the depot to distant delivery destinations from disappearing.

This method is limited to routes to nearby delivery destinations, but does not group delivery destinations geographically. Therefore, the traditional problem of restricting movement between groups does not arise.

(Explanation of effects)
To verify the effectiveness of this method, we conducted a numerical calculation experiment. We set up a scenario in which packages were delivered to destinations (number of destinations N = 300) uniformly distributed around a depot. We performed calculations with the route exclusion ratio M set to 0% (no exclusions, before applying this method), 50%, 80%, and 90%. Figure 3 shows the change in the objective function value (total distance traveled) versus calculation time. In this experiment, a heuristic method was used to gradually find a feasible solution. It can be seen that the objective function converges more quickly as the route exclusion ratio M is increased. The final objective function value is virtually the same regardless of M. In other words, applying this method makes it possible to obtain a solution equivalent to conventional solutions in a shorter time.

(Second Example)
The delivery plan creation method of this embodiment is executed mainly using the route calculation unit FCT, input parameter storage unit PKP, and optimal M value storage unit FJP in the delivery plan creation device 10 shown in Fig. 1. The optimal M value storage unit FJP includes a determination unit DCT that compares a set of stored input parameters with newly inputted input parameters and determines the minimum exclusion ratio M according to the newly inputted calculation time limit.

The delivery plan planning device obtains input parameters to be used by the device from the input unit 13 (or communication unit 15). The route calculation unit FCT receives the input parameters and calculates a delivery route from them. The input parameter storage unit PKP stores input parameters from calculations previously performed. The optimal M value storage unit FJP returns the optimal M value based on the input parameters and calculation time limit.

(Explanation of operation)
The operation when a user calculates a delivery route using the delivery plan planning device will be described with reference to FIGS.

The user provides input parameters (travel distance between delivery destinations, number of trucks, cargo volume, etc.) and a calculation time limit (upper limit of calculation time) to the delivery planning device via the input unit 13 (step S1).

The input parameters provided by the user are saved in the input parameter storage unit PKP (step S2). The input parameters saved here are used in the optimal M value calculation described below.

The input parameters and calculation time limit given in step S1 are passed to the optimal M-value storage unit FJP (step S3).

The optimal M value storage unit FJP uses these input parameters and the calculation time limit as keys to search an internally stored table and output the optimal M value for route calculation (step S4).

The route calculation unit FCT uses the input parameters provided in step S1 and the M value provided in step S4 to calculate the route until the calculation time limit is reached (step S5). The calculation results are returned to the user via the output unit 14 (step S6).

The operation when updating the table in the optimal M value storage unit FJP is explained using Figure 5.

This operation is intended to be performed during times when the user is not using the device. The input parameter history from previous calculations is retrieved from the input parameter storage unit PKP (step S11). Route calculation is performed using these input parameters (step S12). The M value is set to multiple appropriate values between 0% and 100%, and the calculation is repeated. Multiple current solutions (total distance traveled) versus calculation time are recorded (step S13). In other words, the total distance traveled result of the objective function shown in Figure 3 is obtained. The calculation start time for these changes in total distance traveled, as shown in Figure 3, is aligned, for example, as shown on the right in Figure 6, and the calculation time is scanned to map the change in total distance traveled versus the M value, as shown on the left in Figure 6. From the results shown on the left in Figure 6, the M value that minimizes the total distance traveled at each calculation time is determined as the optimal M value, and the table in the optimal M value storage unit FJP is updated (step S14). In this way, the optimal M value is calculated in step S14.

In this way, the delivery plan planning device 10 performs multiple trial calculations in advance to minimize the objective function using multiple exclusion percentages for each set of input parameters for the objective function, and the optimal M value storage unit FJP stores the exclusion percentage value that minimizes the total driving distance for each calculation time for each set of input parameters, in association with each set of input parameters.The saved set of input parameters is compared with newly input parameters to determine the minimum exclusion percentage exceeding 0% that corresponds to the newly input calculation time limit (determination unit DCT).In other words, when the user performs a delivery plan calculation, the M value is determined by searching (comparing) an optimal M value table calculated in advance using past calculation history for one that is closest to the input conditions for the current calculation.

(Explanation of effects)
When a user repeatedly performs delivery plan calculations using this device, the optimal M value can be retrieved from the optimal M value storage unit FJP of this device, and calculations can be automatically performed using a value of M that is close to the optimal value. In other words, it becomes possible to create and provide a better plan in a shorter calculation time.

10 Delivery plan planning device FCT Route calculation unit PKP Input parameter storage unit FJP Optimal M value storage unit DCT Determination unit

Claims (5)

A delivery plan creation method for creating a travel route that minimizes an objective function that formulates a total sum of a total travel distance from a delivery point to a vehicle traveling a travel distance between delivery destinations and returning to the delivery point, using a delivery plan creation device,
When delivering packages from one delivery base to N delivery destinations, before creating a circular route , the total number of N-1 routes from one delivery destination to the other N-1 delivery destinations is set to 100%, the routes are arranged in descending order of travel distance starting from the longest route , and an exclusion percentage M % of multiple routes to be excluded in order from the longest route is set,
The route with the exclusion rate M% is excluded in advance so that it is not included in the route creation .
A delivery plan creation method characterized by calculating the objective function and creating a tour route . A delivery plan creation device that creates a traveling route that minimizes an objective function that formulates the sum of the total travel distances of a vehicle that departs from a delivery base, travels the travel distances of a route between delivery destinations, and returns to the delivery base,
When delivering packages from one delivery base to N delivery destinations, before creating a circular route, the delivery plan creation device is characterized by comprising a route calculation unit that sets the total number of N-1 routes from one delivery destination to the other N-1 delivery destinations to 100%, arranges the routes in descending order of travel distance starting from the longest route, sets an exclusion percentage M% of multiple routes to be excluded in order from the longest route, and excludes routes with the exclusion percentage M% in advance so that they are not included in the creation of the circular route, and calculates the objective function to create the circular route. 3. The delivery plan planning device according to claim 2, further comprising an optimal M value storage unit that performs a plurality of trial calculations of the objective function for each of the plurality of exclusion percentages M %, scans changes in the objective function for each of the exclusion percentages M % relative to the calculation time of the objective function, and stores the value of the exclusion percentage M % that minimizes the total travel distance for each calculation time as an optimal M value. 4. The delivery plan planning device according to claim 3, wherein when a calculation limit time for calculating an objective function is input to the delivery plan planning device, the delivery plan planning device outputs the optimal M value according to the calculation limit time. 5. The delivery schedule planning device according to claim 4, wherein the objective function is calculated using the optimal M value until the calculation time limit is reached.