JP7130806B2 - DELIVERY VEHICLE DELIVERY PLAN GENERATION METHOD, DEVICE AND SYSTEM - Google Patents

Description

TECHNICAL FIELD The present invention relates to the technical field of vehicle routing problems (VRP), and more specifically to a method, apparatus and system for generating a delivery plan for delivery vehicles.

A vehicle routing problem (VRP) is one in which the needs of a certain number of customers, each with a different number of parcel delivery needs, can be met and the objectives of shortest distance, lowest cost, and lowest time can be achieved under certain constraints. After deciding who is in charge of delivering packages and designing an appropriate travel route, the delivery center delivers the packages to the customer.

Algorithms related to the vehicle path problem currently include exact algorithms such as the branch-and-bound method, the branch-cut method, and the set-cover method, the saving method, the pseudo-annealing method, the deterministic annealing method, the taboo search method, and the gene algorithm. , neural networks, the ant colony method, and heuristics algorithms such as the Genetic Algorithm (GA). In the automatic generation of vehicle delivery plans, the large neighborhood search (LNS) algorithm, which is one of the neighborhood search methods, is usually relatively effective. Search for The search is usually performed by approaching the optimum solution, quantifying the difference (sum of costs) from the optimum solution, and repeating the search gradually in the direction of cost reduction.

In some application scenes of VRP, it is necessary to put a delivery package into a delivery container and deliver it. In such a scene, it is usually necessary to return the empty container after the parcel has been delivered. For example, in logistics scheduling in the manufacturing industry, including the delivery of automobile parts, shipping containers differ depending on the manufacturer, and the number of shipping containers is limited, so empty containers are often returned to the manufacturer immediately after delivery. Due to such special needs, it is technically difficult to realize the optimum order of delivery tasks for the above application scene only by the neighborhood search method. Therefore, conventional algorithms have not yet reached a level of practicality in creating dispatch plans that include empty container returns. Currently, in the logistics industry, there are still many cases where delivery plans for the above application scenes are created manually.

The technical problem to be solved by the embodiments of the present invention is to automatically generate a delivery plan including a delivery requirement to return empty containers to the manufacturer after delivery, improve the efficiency of creating the delivery plan, and reduce human costs. To provide a delivery vehicle dispatch plan generation method, apparatus and system for reducing

To solve the above technical problems, the embodiments of the present invention provide a delivery plan generation method for outputting a delivery order for picking up and delivering packages between multiple locations using multiple delivery vehicles. do. In the delivery plan generation method, whether or not an empty container return task in a delivery plan candidate and a related parcel delivery task are assigned to the same delivery vehicle, and whether or not the empty container return task and the related parcel delivery task are assigned to the same delivery vehicle. Based on whether or not the task is executed within a predetermined period of time, the candidate delivery plan is evaluated to obtain an evaluation result. Also, one or a plurality of delivery plan candidates are output as a final delivery plan based on the evaluation results of the delivery plan candidates. Among them, the empty container return task and the related parcel delivery task are executed simultaneously, or the empty container return task is executed after the related parcel delivery task. and that there are no other delivery tasks between them.

Embodiments of the present invention further provide a dispatch plan generator for outputting a delivery order for picking up and delivering packages between multiple sites using multiple delivery vehicles. The delivery plan generation device determines whether the empty container return task in the delivery plan candidate and the related parcel delivery task are assigned to the same delivery vehicle, and if they are assigned to the same delivery vehicle, a delivery plan evaluation means for obtaining an evaluation result by evaluating a delivery plan candidate based on whether the empty container return task and the related parcel delivery task are executed within a predetermined time; and the delivery plan. a delivery plan output means for outputting one or a plurality of delivery plan candidates as a final delivery plan based on evaluation results of the candidates; Including that the empty container return task and the related package delivery task are executed at the same time, or that the empty container return task is executed after the related package delivery task and there are no other delivery tasks between them. .

Embodiments of the present invention further provide a dispatch plan generation system. The system includes a storage device, a processor, and a computer program stored in the storage device and executed by the processor. When the computer program is executed by the processor, the delivery plan generation method is realized. .

Embodiments of the invention further provide a computer-readable storage medium. When the computer program stored in this storage medium is executed by the processor, the above delivery plan generation method is realized.

Compared with the prior art, in the delivery plan generation method, apparatus and system according to the embodiment of the present invention, the task cost of the empty container return task is introduced into the total cost of the delivery plan candidates, and the task cost in the first delivery method is calculated in advance. is optimal, the algorithm automatically outputs the desired empty container return delivery order, satisfies the empty container return needs in the actual logistics scene, and avoids the manual preparation of the delivery plan. Therefore, it is possible to reduce the cost of creating a delivery plan and improve the efficiency of creating a delivery plan.

In order to describe the technical means of the embodiments of the present invention more clearly, the following briefly introduces the drawings required for describing the embodiments of the present invention. Apparently, the drawings in the following description are merely some examples of the present invention. Those skilled in the art can derive other drawings from these drawings without creative work.

FIG. 1 is a flow chart of a dispatch plan generation method according to an embodiment of the present invention. FIG. 2 is a schematic structural diagram of a dispatch plan generation device according to an embodiment of the present invention. FIG. 3 is a block diagram showing the overall structure of a dispatch plan generation system according to an embodiment of the present invention. FIG. 4 is an exemplary flowchart of a Dispatch Plan generation method according to an embodiment of the present invention. FIG. 5 is a diagram showing an example of site management data in the embodiment of the present invention. FIG. 6 is a diagram showing an example of vehicle management data in the embodiment of the invention. FIG. 7 is a diagram showing an example of delivery task data in the embodiment of the invention. FIG. 8 is a diagram showing an example of input data generated in an embodiment of the invention. FIG. 9 is an exemplary flowchart of adding empty container return task in an embodiment of the invention. FIG. 10 is an exemplary flowchart of adding an empty container pick-up task in an embodiment of the invention. FIG. 11 is a diagram showing an example of inter-site distance matrix data in the embodiment of the present invention. FIG. 12 is an exemplary flow chart of empty container mixing availability determination processing in the embodiment of the present invention. FIG. 13 is an exemplary flowchart of a total cost calculation process in an embodiment of the invention. FIG. 14 is an exemplary flowchart of same-vehicle mandatory constraint violation processing in an embodiment of the present invention. FIG. 15 is a diagram showing an example of output data in the embodiment of the invention. 16A and 16B are diagrams showing examples of output screens generated in an embodiment of the present invention. FIG. 17 is another schematic structural diagram of the block diagram of the dispatch plan generation system according to an embodiment of the present invention. FIG. 18 is a schematic diagram of the connection relationship of processing and data in another system block diagram shown in FIG.

In order to make the technical problems, technical means and advantages to be solved by the present invention clearer, the detailed description is given below in conjunction with the drawings and specific embodiments. Providing specific details of specific settings and components in the following description is merely an aid in providing a thorough understanding of the embodiments of the present invention. Accordingly, it will be apparent to those skilled in the art that various changes and modifications can be made to the embodiments described herein without departing from the scope and spirit of the invention. Also, for the sake of clarity and brevity, descriptions of well-known functions and constructions are omitted.

References to "one embodiment" or "an embodiment" throughout the specification mean that the particular feature, structure, or characteristic of the embodiment is included in at least one embodiment of the invention. It should be understood then. Thus, the phrases "in one embodiment" and "in one embodiment" appearing in various parts of the specification do not necessarily refer to the same embodiment. Also, any of these specific features, structures or characteristics may be combined in any one or more embodiments as appropriate.

In each embodiment of the present invention, the magnitude of the number of each process described later does not mean the order of execution. It should be understood that the order in which each step is performed is determined by its function and underlying logic and should not constitute any limitation on the process of implementing embodiments of the present invention.

See FIG. An embodiment of the present invention provides a dispatch plan generation method. The method can output the optimal order of delivery tasks for picking up and delivering parcels by patrolling a plurality of bases by a plurality of delivery vehicles. As shown in FIG. 1, the method includes the following steps.

In step 11, whether or not the empty container return task in the delivery plan candidate and the related package delivery task are assigned to the same delivery vehicle, and whether the empty container return task and the related package delivery task are An evaluation result is obtained by evaluating the delivery plan candidate based on whether or not it will be executed within a predetermined time.

A delivery task in an embodiment of the present invention includes a package delivery task for delivering a package from one base (for example, a delivery departure base) to another base (delivery destination base). It may also include an empty container return task to return from the destination site to the delivery origin. Thus, for each empty container return task, there is one associated package delivery task, but for a package delivery task, there may be an associated empty package return task, or an associated empty package return task. It is also possible that the task does not exist. Here, to be executed within the predetermined time means that the empty container return task and the related parcel delivery task are executed simultaneously, or that the empty container return task is executed after the related parcel delivery task. and that there are no other delivery tasks between them.

In the embodiment of the present invention, when evaluating the delivery plan candidate, whether or not the empty container return task and the related package delivery task are assigned to the same delivery vehicle, and whether or not the empty container return task and the empty container return task , depending on whether or not the related parcel delivery task is executed within a predetermined period of time. The total cost of the obtained delivery plan candidate is used as the evaluation result of the delivery plan candidate.

In step 12, one or a plurality of candidate delivery plans are output as a final delivery plan based on the evaluation results of the candidate delivery plans.

Here, one or a plurality of delivery plan candidates are selected from the delivery plan candidates with the lowest total cost in descending order of the total cost of the delivery plan candidates, and output as the final delivery plan.

With the above steps, the embodiment of the present invention considers the task cost of the empty container return task for different delivery types in the total cost of the candidate delivery plan, so that the algorithm can automatically determine the desired order of return empty container deliveries. , it satisfies the need for returning empty containers in the actual distribution scene, avoids manual preparation of the delivery plan, reduces the cost of creating the delivery plan, and improves the efficiency of creating the delivery plan.

In an embodiment of the present invention, the candidate dispatch plan includes the execution order of the delivery tasks and the assigned delivery vehicles. Specifically, a search algorithm such as a genetic algorithm (GA) or a large neighborhood search (LNS) is used for delivery tasks waiting for assignment (including a package delivery task and an empty container return task). Then, the optimal solution is approached by multiple searches, and multiple delivery plans are acquired through the searches, and these delivery plans are used as delivery plan candidates.

The search may be executed until a predetermined upper limit of the number of searches is reached and then terminated, or may be terminated before the predetermined upper limit of the number of searches is reached. For example, if the acquired delivery plan candidate satisfies a predetermined condition and the number of delivery vehicles specifically required for the delivery plan candidate is equal to or less than a predetermined first threshold, the search is interrupted and the acquired delivery plan candidate is output. do. Also, for example, the number y1 of empty container return tasks that are assigned to a delivery vehicle different from the related parcel delivery task and that are assigned to the same delivery vehicle as the related parcel delivery task in the delivery plan candidate If the sum of the number y2 of the related parcel delivery tasks and the number y2 of the empty container return tasks that have not been executed within the predetermined time is equal to or less than a predetermined second threshold, the search may be terminated ahead of schedule.

If, during the search by the search algorithm, the number of empty container return tasks assigned to different delivery vehicles than the related package delivery tasks present in the current delivery plan candidate is greater than or equal to a predetermined second threshold, then the current delivery Make adjustments to the Delivery Tasks in the Plan Candidate or remove the current Dispatch Plan Candidate. The adjustment includes adjusting the delivery order of empty container return tasks assigned to different delivery vehicles than the associated package delivery tasks. For example, the empty container return task is inserted at another position in the current delivery plan candidate, or the delivery order is exchanged with other delivery tasks.

The total cost includes the task cost of the empty container return task. In order to achieve the purpose of returning the empty container immediately after delivery of the package, in the embodiment of the present invention, task costs of different magnitudes are provided for each empty container return task. When the empty container return task and the related parcel delivery task are assigned to the same delivery vehicle, and the empty container return task and the related parcel delivery task are executed within the predetermined time, the empty container return task has the lowest task cost. By introducing the above task costs into the Dispatch Plan candidates, embodiments of the present invention take into account the effect of the ordering of the Dispatch Tasks on the Dispatch Plan so as to obtain the desired Dispatch Plan.

In an embodiment of the present invention, whether or not the empty container return task and the related package delivery task are assigned to the same delivery vehicle, and whether the empty container return task and the related package delivery task are performed for a predetermined time. Depending on whether or not the empty container return task is executed within a time frame, each empty container return task is given a task cost of different magnitudes, causing the algorithm to output the desired delivery strategy. As one specific implementation form, for the empty container return task in advance, the first task cost in the first delivery method, the second task cost in the second delivery method, the third task cost in the third delivery method, and the fourth delivery Set the method to have the fourth task cost. Here, as the first delivery method, the empty container return task and the related parcel delivery task are assigned to the same delivery vehicle, and the empty container return task and the related parcel delivery task are completed within a predetermined time. executed. As the second delivery method, the empty container return task and the related cargo delivery task are assigned to the same delivery vehicle, and the empty container return task is executed after the related cargo delivery task, and another delivery is performed between them. Task exists. As the third delivery method, the empty container return task and the related package delivery task are assigned to the same delivery vehicle, but the empty container return task is executed before the related package delivery task. As the fourth delivery method, the empty container return task and the related parcel delivery task are assigned to different delivery vehicles.

Here, the first task cost, second task cost, third task cost, and fourth task cost increase in order. The above different task costs for different delivery methods show that the first delivery method is the most desired delivery method for the empty container return task in the embodiment of the present invention.

In addition to the task cost of the empty container return task, in an embodiment of the present invention, the delivery distance cost is also considered in the total cost of the delivery plan candidates. Different delivery plan candidates may have different delivery vehicle routes, and thus different delivery distances, corresponding to different delivery distance costs. In the above step 12, the delivery distance cost of each delivery task in the delivery plan candidate is statistically calculated, the task cost of the empty container return task in the delivery plan candidate is statistically calculated, and the delivery is made based on the delivery distance cost and the task cost. Get the evaluation results of plan candidates. For example, different weights are assigned to the delivery distance cost and the task cost, and the weighted sum of both is obtained to obtain the evaluation result of the delivery plan candidate.

In addition, in the embodiment of the present invention, there are many factors such as time required for delivery, delivery road cost (for example, different roads may incur different costs, and in the case of expressways, additional tolls are required). may be considered in the evaluation results. These factors are taken into account for searching by the search algorithm, but are not described in further detail in this text.

As one implementation form, the embodiment of the present invention, when acquiring one delivery plan candidate generated by a search algorithm (hereinafter referred to as the current delivery plan candidate), Determine the number of empty container return tasks that are assigned to different delivery vehicles than the package delivery tasks to be delivered. If the number exceeds a preset threshold, adjust the delivery tasks in the candidate delivery plans or eliminate the candidate delivery plans.

In the embodiment of the present invention, a mixed loading capacity having an upper limit value M _max is set in advance, which is used to determine whether mixed loading is possible, and the mixed loading capacity of a delivery task that cannot be mixed loaded is set to the upper limit value M max, and the mixed loading capacity is set to the above upper limit value M _max . Set the task's load capacity to a positive number K that is much smaller than _Mmax . The value of the positive number K is set with reference to the number of delivery tasks S, and is a value smaller than M _max /S, for example. In addition, a delivery capacity is set for each delivery vehicle, which is used to determine whether mixed loading is possible. As an example, the upper limit value M _max of the mixed loading capacity is set to 1, and the mixed loading capacity of the delivery task for which mixed loading is permitted is set to 0.01. In determining a delivery vehicle that violates a predetermined restriction condition in the current delivery plan candidate, for each delivery vehicle in the delivery plan candidate, total the mixed loading capacity of all delivery tasks delivered by the relevant delivery vehicle, and , it is determined that the delivery vehicle violates the setting condition of disallowing consolidation of the delivery task.

Further, whether or not a delivery task can be mixed may be determined by the task attribute of the delivery task. When obtaining a delivery task waiting for assignment, a task attribute can be specified, and the task attribute can include instruction information as to whether or not mixed loading is permitted. For the empty container return task, if the related package delivery task cannot be mixed-loaded, the empty container return task also cannot be mixed-loaded by default. Of course, if the package delivery task related to the empty-container return task cannot be mixed-loaded, it is possible to specifically indicate that the empty-container return task can be mixed-loaded.

As one implementation form, the embodiment of the present invention is configured such that when one delivery plan candidate (hereinafter referred to as the current delivery plan candidate) is acquired, there are delivery vehicles exceeding the mixed loading capacity among the delivery plan candidates. If there is a delivery vehicle exceeding the mixed loading capacity in the delivery plan candidate, the delivery task in the delivery plan candidate is adjusted or the delivery plan candidate is excluded.

When judging whether there is a delivery vehicle exceeding the mixed loading capacity in the delivery plan candidate, for the delivery vehicle of the delivery plan candidate, determine the route between adjacent points that the delivery vehicle passes through, and determine the route of the delivery vehicle If the mixed loading capacity of all delivery tasks is accumulated and is equal to or greater than the upper limit value of the mixed loading capacity, it is determined that there is a delivery vehicle exceeding the mixed loading capacity. Alternatively, for a route between adjacent bases in a delivery plan candidate, one or more delivery vehicles that pass through the route are determined, and the mixed loading capacity of all delivery tasks on the route for each delivery vehicle is accumulated. If it is equal to or greater than the upper capacity limit, then it is determined that there are delivery vehicles that exceed the consolidated capacity.

Furthermore, in the embodiment of the present invention, it is also possible to set many limiting conditions other than the mixed loading capacity and determine whether the delivery vehicle satisfies these conditions. In this case, first, it is determined whether or not there is a delivery vehicle in the current delivery plan candidate that violates the predetermined vehicle restriction conditions. If there is a delivery vehicle in the current delivery plan candidate that violates the predetermined vehicle restriction condition, the delivery task in the delivery plan candidate is adjusted, or the current delivery plan candidate is excluded, and the current delivery plan candidate is Do not calculate the total cost of delivery plan candidates. If there are no delivery vehicles violating the predetermined vehicle restriction condition, the cost of each delivery task in the current delivery plan candidate is statistically obtained to obtain the total cost of the delivery plan candidate.

Here, the predetermined vehicle restriction condition is that the total cargo volume of the vehicle does not exceed the upper volume limit of the vehicle, or that the total cargo weight of the vehicle does not exceed the upper cargo volume limit of the vehicle, or that the vehicle does not deliver This includes not violating the setting conditions for disallowing task consolidation.

Further, in an embodiment of the present invention, after obtaining one candidate dispatch plan (which is the current candidate dispatch plan), it is determined that there are no delivery vehicles in the current candidate dispatch plan that violate the predetermined vehicle restriction conditions. Subsequently, determining a first number of empty container return tasks in the current candidate delivery plan that are assigned to delivery vehicles that are different from the associated package delivery tasks. If the first number exceeds a first predetermined threshold, adjustments are made to the Delivery Tasks in the Dispatch Plan or the current Dispatch Plan candidate is eliminated. If the first value is less than or equal to the predetermined first threshold, then statistical task costs of each delivery task in the current candidate dispatch plan to obtain a total cost of the candidate dispatch plan. Here, the predetermined first threshold is set based on factors such as the total number of delivery tasks and cost requirements.

The delivery tasks waiting for assignment in the embodiment of the present invention may be generated based on the package delivery tasks provided by the user, and may be delivery tasks including package delivery tasks and empty container return tasks. Specifically, for example, if the delivery tasks provided by the user include only the parcel delivery task, in the embodiment of the present invention, the parcel delivery task that requires the return of the empty container after delivery of the parcel is determined, and the return of the empty container is determined. Add a related empty container return task to the package delivery task that requires , and assume that the execution order of the related empty container return task is after the package delivery task that requires the empty container to be returned after the package is delivered. label.

Here, the task attribute of the parcel delivery task is analyzed, and it is determined whether the parcel delivery task requires the empty container to be returned. When a user provides a parcel delivery task, it is necessary to specify the task attributes of the task. Information such as whether or not the container needs to be returned is included.

Considering that the empty container may not be located at the departure base of the package delivery task, first the empty container is picked up from another base, and then the cargo is loaded at the departure base and delivered to the destination base. Therefore, in the embodiment of the present invention, after acquiring at least one package delivery task provided by a user, a package delivery task that needs to pick up an empty container from a base other than the delivery departure base before the package is delivered. Decide on a task. A related empty container pick-up task is added to a package delivery task that needs to pick up empty containers from other bases other than the delivery departure base, and the order of execution of the related empty container pick-up tasks is as follows: It is marked as before the parcel delivery task that requires picking up empty containers from other bases other than the above-mentioned delivery departure base.

According to the above method, the embodiment of the present invention can generate the waiting delivery tasks based on the package delivery tasks provided by the user, specifically including the package delivery tasks, Either or both of a container pick-up task and an empty container return task may be included.

In order to label the delivery tasks in the search algorithm, in an embodiment of the present invention, every delivery task is assigned a task indicator ID that uniquely identifies the delivery task, and a related delivery task is assigned a related ID. Establish relationships. For example, establish a relationship between a related empty container pick-up task and a package delivery task, and establish a related relationship between a related package delivery task and an empty container return task.

In the embodiment of the present invention, when generating delivery plan candidates for the delivery tasks waiting for assignment by the search algorithm, an upper limit value for the number of searches is set. When the number of searches reaches the upper limit, the search is terminated and delivery plan candidates are output. During the search, processing can be done in the following manner to speed up convergence.

Related When the number of empty container return tasks assigned to a delivery vehicle different from the package delivery task exceeds a predetermined value, the delivery tasks in the original task group whose initial value is the above-mentioned delivery task waiting for assignment are treated as related package delivery tasks. Divided into two groups, a first task group consisting of empty container return tasks assigned to different delivery vehicles and their related delivery tasks, and a second task group consisting of other delivery tasks, and performing a predetermined search. Based on the algorithm, generate delivery sub-plan candidates for the first task group and the second task group, respectively, obtain the first delivery sub-plan candidate and the second delivery sub-plan candidate, and obtain the first delivery sub-plan candidate and second delivery sub-plan candidate. If there is an empty container return task assigned to a delivery vehicle different from the related package delivery task in the delivery sub-plan candidates, the first task group is set as the above-mentioned original task group, and the delivery tasks in the above-mentioned original task group into two groups, and if there is no empty container return task assigned to a different delivery vehicle than the associated package delivery task in the first delivery sub-plan candidate, then the first delivery sub-plan candidate and all the second delivery sub-plan candidates to obtain the delivery plan candidates of the delivery tasks waiting for assignment.

According to the above method, embodiments of the present invention can accelerate the convergence of algorithms and improve search efficiency.

The method of generating a delivery plan for delivery vehicles according to the embodiment of the present invention has been introduced above. In each of the above-described embodiments of the present invention, a related empty container return task is added to a parcel delivery task with an empty container return request, and a task with a different size for the empty container return task is added during the delivery plan search. By setting a cost, it is possible to automatically generate and output a delivery plan for the desired delivery order using a search algorithm, improving the efficiency of creating a delivery plan that includes the delivery requirement of returning empty containers to the manufacturer after delivery. Let

Embodiments of the invention further provide a computer-readable storage medium. When the computer program stored in this storage medium is executed by the processor, it implements the dispatch plan generation method of any one of the above method embodiments.

Based on the above method, embodiments of the present invention further provide an apparatus for implementing the above method. As shown in FIG. 2, the delivery plan generation device 20 according to the embodiment of the present invention determines whether the empty container return task in the delivery plan candidate and the related parcel delivery task are assigned to the same delivery vehicle. Then, if they are assigned to the same delivery vehicle, the candidate delivery plan is evaluated based on whether or not the empty container return task and the related parcel delivery task are executed within a predetermined time, and an evaluation result is obtained. a delivery plan evaluation means 21 for obtaining and a delivery plan output means 22 for outputting one or more delivery plan candidates as a final delivery plan based on the evaluation results of the delivery plan candidates, Among them, the empty container return task and the related parcel delivery task are executed simultaneously, or the empty container return task is executed after the related parcel delivery task. and that there are no other delivery tasks between them.

The delivery plan evaluation means 21 determines whether the empty container return task and the related package delivery task are assigned to the same delivery vehicle, and determines whether the empty container return task and the related package delivery task are predetermined. Task costs of different magnitudes are set for each empty container return task based on whether it will be executed within the time or not, and the total cost of the candidate delivery plan obtained by totaling the task costs of the candidate delivery plans is called the candidate delivery plan. preferably includes a task cost statistical means for evaluating the results of

The delivery plan generation device determines the number of empty container return tasks assigned to a delivery vehicle different from the related package delivery task in the delivery plan candidate, and if the number exceeds a preset threshold, It is preferable to further include a dispatch plan analysis means for making adjustments to the dispatch tasks in the dispatch plan candidates or for excluding the dispatch plan candidates.

The delivery plan generation device presets a delivery capacity used for determining whether mixed loading is possible for a delivery vehicle, and presets a mixed loading capacity having an upper limit value, which is used for determining whether mixed loading is possible for a delivery task, and determines whether mixed loading is impossible. It is preferable to further include capacity setting means for setting the mixed loading capacity of the delivery task to the upper limit value of the mixed loading capacity.

After generating one delivery plan candidate with a search algorithm, the above-mentioned delivery plan generation device determines whether or not a delivery vehicle exceeding the mixed loading capacity exists in the delivery plan candidates. It is preferable to further include consolidation determination means for adjusting the delivery tasks in the delivery plan candidates or excluding the delivery plan candidates if they exist in the candidates.

Specifically, when judging whether or not there is a delivery vehicle exceeding the mixed loading capacity, the mixed loading determination means determines a route between adjacent bases that the delivery vehicle passes through for the delivery vehicle of the delivery plan candidate. Then, if the mixed loading capacity of all the delivery tasks on the route of the relevant delivery vehicle is summed up and is equal to or greater than the upper limit value of the mixed loading capacity, it is determined that there is a delivery vehicle exceeding the mixed loading capacity. Alternatively, for a route between adjacent bases in the delivery plan candidate, one or more delivery vehicles that pass through the route are determined, and the mixed loading capacity of all delivery tasks on the route of each delivery vehicle is totaled. If it is equal to or greater than the upper limit of the mixed loading capacity, it is determined that there is a delivery vehicle exceeding the mixed loading capacity.

It is preferable that the delivery plan generation device further includes a delivery plan generation means. The delivery plan generation means repeats the generation of delivery plan candidates up to a preset search frequency upper limit based on a predetermined search algorithm. If the number of empty container return tasks assigned to a delivery vehicle different from the related parcel delivery tasks exceeds a predetermined value among the plan candidates, the delivery tasks in the original task group whose initial value is the delivery tasks waiting for assignment are selected. , a first task group consisting of a related package delivery task, an empty container return task assigned to a different delivery vehicle, and its related delivery task, and a second task group consisting of other tasks. Based on a predetermined search algorithm, candidate delivery sub-plans are generated for each of the first task group and the second task group to obtain first candidate delivery sub-plans and second candidate delivery sub-plans. , and if there is an empty container return task assigned to a delivery vehicle different from the related package delivery task in the first delivery sub-plan candidate, the first task group is set as the above-mentioned original task group, and the above-mentioned original Returning to the step of dividing the delivery tasks in the task group into two groups, if there is no empty container return task assigned to a delivery vehicle different from the related package delivery task in the first delivery sub-plan candidate, the first 1 delivery sub-plan candidate and all second delivery sub-plan candidates are combined to obtain the delivery plan candidate of the delivery task waiting for assignment.

The delivery plan evaluation means 21 in the delivery plan generation device further calculates the sum of the total cost and the delivery distance cost of each delivery task in the delivery plan candidate, and obtains the evaluation result of the delivery plan candidate.

Embodiments of the present invention further provide a dispatch plan generation system for a delivery vehicle. The system includes a storage device, a processor, and a computer program stored in the storage device and executed by the processor, and when the computer program is executed by the processor, delivery of any one of the above method embodiments. Implement a plan generation method.

FIG. 3 shows an example of an overall structural block diagram of a dispatch plan generation system according to an embodiment of the present invention. In FIG. 3, a single computer will be described as an example. Computer 100 comprises processor (CPU) 104 , main storage device 105 , secondary storage device 106 , main bus 103 , video card 107 , network interface card (NIC) 108 and video output port 109 . be. The computer 100 can input/output data to/from the outside of the computer via the NIC 108, and can perform screen output to an external display device via the video output port 109. FIG. In an actual structure, input devices such as a keyboard, mouse, etc. may be further included in addition to the modules shown in FIG.

The secondary storage device 106 stores, for example, a data input processing module 1061, a calculation condition setting processing module 1062, an optimum solution search processing module 1063, a delivery plan output processing module 1064, base management data 1065, and vehicle management data. 1066, delivery task data 1067, road vector data 1068, and other types of input data and program modules required for the arithmetic processing of the embodiment of the present invention are stored. In executing the arithmetic processing, the data in the secondary storage device 106 is appropriately read by the input/output/calculation execution processing means 1051 in the main storage device 105, and search processing is performed together with the base distance data 1052 to create a delivery plan. Output.

In order to understand the above technical means of the embodiments of the present invention, the methods of the embodiments of the present invention will be described in more detail below through the specific flows of several examples.

Referring to FIG. 4, an exemplary flow of a delivery vehicle dispatch plan generation method according to an embodiment of the present invention includes the following.

In the data reading step 210, the site management data 1065, the vehicle management data 1066, and the delivery task data 1067 are read. After that, as a pre-process of the main arithmetic processing step 230, a calculation condition setting step 220 is performed. In the main processing step 230, generation of the dispatch plan is iteratively performed in order to obtain the optimum dispatch plan.

Before generating a delivery plan each time, in step 231, it is determined whether the predetermined number of search loops has reached the upper limit. If so, the process proceeds to step 240 to output a delivery plan;

In step 232, a search algorithm such as the LNS algorithm or GA is used to retrieve delivery plan candidates, and in step 233, it is determined whether the generated delivery plan candidates violate the compulsory restrictive conditions. If there is a violation, the current Dispatch Plan Candidate is adjusted or the current Dispatch Plan Candidate is removed, and the process returns to step 232 to generate a new Dispatch Plan Candidate. If not, proceed to step 234 to calculate the total cost of the current Dispatch Plan Candidate.

Here, the compulsory restriction conditions may include the predetermined vehicle restriction conditions described above. Further, the compulsory constraint condition includes that a first number of empty container return tasks present in the candidate delivery plan that are assigned to a different delivery vehicle than the associated package delivery task is less than a first threshold. If it is necessary to regenerate a Delivery Plan Candidate due to a violation of the compulsory restriction condition, insert the delivery task related to the violation of the above compulsory restriction condition into another position in the current Delivery Plan Candidate, or insert the current Delivery Plan Candidate Exchange the delivery order with other delivery tasks in the candidates.

In step 235, it is determined whether the search can be terminated ahead of schedule. If so, the process proceeds to step 240; otherwise, the process returns to step 231. For example, the number of delivery vehicles required for the current Dispatch Plan Candidate is less than or equal to a predetermined first threshold and/or there are available vacancies in the Dispatch Plan Candidate that are assigned to different delivery vehicles than the associated package delivery task. If the number of container return tasks is equal to or less than a predetermined second threshold, the search can be terminated ahead of schedule.

In step 240, one or a plurality of delivery plans are output in descending order of the total cost of each currently acquired delivery plan candidate to be the final delivery plan.

5-7 show an example of the data format read in the data read step 210. FIG.

The base management data 1065 in FIG. 5 includes a base name 411, a latitude 412 and a longitude 413 indicating the position of the base, a location area 414 of the base, and a vehicle type compatible with the base (that is, a vehicle type that can be delivered at the base) 415. , opening hours 416 and closing hours 417 of the base, and parameters such as unloading time 418 .

The vehicle management data 1066 in FIG. 6 includes a vehicle ID 431 for uniquely labeling a vehicle, a vehicle type 432, a driver and contact method 433, a base 434 at the time of departure of the vehicle, and a base 435 at the time of termination of the vehicle. , vehicle volume upper limit value 436 (cubic meter/number of pallets (loading platforms for cargo), etc.), vehicle loading upper limit value 437 (t or kg, etc.), vehicle operation start time 438, and operation end time 439. , the vehicle's jurisdiction 440 and other parameters.

The delivery task data 1067 in FIG. 7 includes the delivery date 451 of the delivery task, the departure base 452 of the delivery source, the target base 453 of the delivery destination, the pick-up deadline 454 for acquiring the package at the delivery source, and the delivery destination. Parameters such as delivery deadline 455 to be delivered to , delivery package volume 456 , vehicle type 458 if there is a limit to the vehicle type that can be delivered, necessity of empty container return 459 , and possibility of mixed loading with other delivery tasks 460 . include.

In calculation condition setting step 220, the site management and delivery task data are used to generate input data 500 shown in FIG. From the delivery task data 1067 in FIG. 7, it is impossible to directly reflect the return of empty containers in the plan in the computation processing of the delivery plan generation algorithm. An empty container return task is generated by processing.

As shown in FIG. 9, in the calculation condition setting step 220, an arithmetic loop process is performed for all delivery tasks waiting for delivery provided by the user. At step 221, it is determined whether all delivery tasks have been traversed. When the traverse is finished, the input data as shown in FIG. 8 is output. If the traverse is not finished, one unprocessed delivery task i is selected in step 222, and the delivery task i is selected in step 223. Determine whether the empty container needs to be returned. If not necessary, return to step 221 . If necessary, at step 224, an empty container return task j is added to the delivery task i and generated. Refer to the setting of the empty container return necessity 459 for the task in FIG. If return is required, add an empty container return task.

Taking the delivery task data 461 in FIG. 7 as an example, since the empty container return 459 is “required”, the next empty container return task J001_01 is added to the first delivery task J001 in FIG. In this case, J001 is entered in the related task ID in FIG. 8 to correspond to the original delivery task J001. Here, task order 519 indicates the order relationship between the current task and related task ID 520 . For example, NEXT 541 indicates that current task J001_01 is located after task J001 indicated in related task ID 520 .

In step 225, when judging whether mixed loading is permitted for the empty container return task j, the mixed loading permitted/disabled 521 in FIG. 8 is set by referring to the mixed loading permitted/disabled 460 in FIG. That is, if mixed loading is not permitted for the original delivery in the mixed loading possibility determination process 225 of FIG. 9, mixed loading is also prohibited for empty container return. Of course, embodiments of the present invention may use an asymmetrical processing scheme, ie, the original delivery may be non-consolidated whereas the empty container return may be consolidate.

In the task assignment process of the delivery plan generation algorithm, in order not to mix the empty container return task that cannot be mixed with other tasks, a capacity different from the volume V and weight W is introduced and added to the delivery task. Assume that the mixed load capacity is M. In the example of FIG. 9, the upper limit of the mixed loading capacity of all vehicles is set to 1.0, and at step 226, the mixed loading capacity of the empty container return task i that cannot be mixed is set to 1.0. As a result, when the mixed loading capacity of the delivery task is 1.0, the capacity becomes full, and at this time, for example, even if there is room in the volume V and the weight W, the mixed loading with other tasks is disabled.

On the other hand, if it is determined that mixed loading is possible by the mixed loading possibility determination processing 225, in step 227, the mixed loading capacity of the empty container return task i is set to a value larger than 0 and extremely small, for example, a value smaller than the aforementioned M _max /S. set to The volume 516 and the weight 517 of the empty container return task are determined separately, for example, in step 227, they are uniformly set to 15% of the original delivery task.

Finally, for the original delivery task and the empty container return task, complementary processing is performed during the free time slot between the pick-up deadline 454 and the delivery deadline 455 in FIG. If there is no time in the deadline, it is sufficient to refer to the site management data in FIG. 5 and input the closing time of the site. Also, for example, since the empty container return task basically does not have a specified time, it is sufficient to input the business hours of the base in question. If the business hours of each base are not specified, a default value (for example, 8:00 to 17:00) is specified. Therefore, the input data shown in FIG. 8 are obtained. Also, FIG. 8 shows an example of mixed loading capacity setting processing after determination of input data and before main operation processing step 230 . Of course, the input data itself may also contain the consolidated capacity.

The additional processing of the empty container return task in FIG. 9 is a case where the empty container needs to be returned after delivery. As another case, before the task is delivered, it is necessary to pick up an empty container from a location different from the departure location of the delivery task (Pickup). Correspondingly, one processing scheme thereof is shown in FIG. In the case of the delivery task 462 in FIG. 7, the empty container return necessity 459 is "advance required". Specifically, after the empty container is picked up at the delivery destination base B, the cargo is loaded again at the base C, the cargo is delivered to the base B, and finally the empty container is returned to another base l. That is, as shown in FIG. 10, in the calculation condition setting step 220, first, an arithmetic loop process is performed for all delivery tasks waiting for delivery provided by the user, and it is determined whether or not an empty container pick-up task needs to be added. . At step 221a, it is determined whether or not the traversal of the empty container pick-up process has been completed for all delivery tasks. If the traversal has been completed, the process proceeds to step 221 in FIG. 9 to determine whether the empty container return processing traversal has been completed for all delivery tasks. If the traversal of the empty container pick-up process has not ended, one unprocessed delivery task is selected as the current delivery task in step 222a, and empty containers are picked up from another site for the current delivery task in step 223a. Determine if withdrawal is required. If it is determined that it is necessary, in step 224a an empty container pick-up task is added to the current task, and the process returns to step 221a. Specifically, when an empty container pick-up task is added, related parameters in the task may be set by referring to a similar method in the empty container return task.

Based on the delivery task 462 in FIG. 7, an empty container pick-up task J002 and an empty container return task J002_02 are generated for the delivery task in FIG. Here, the task ID of the task to be performed before is set for the related task IDs of J002_01 and J002_02 in order to carry out pick-up of the empty container, package delivery, and return of the empty container in this order. In the actual delivery, there is no need to return the empty container to the base 1 after the delivery, and the empty container is picked up at another base other than the delivery destination base B. There are scenes. Appropriate input data 500 may be output by adaptively changing the above various possible scenes according to business requirements. In this example, the scene where the input data 500 is generated based on the delivery task 1067 by the calculation condition setting step 220 is shown. However, in a concrete implementation, the calculation condition setting step 220 may be skipped and the input data 500 may be directly input. That is, by directly inputting the task order 519 and the related task ID 520, it is possible to define the relationship between a plurality of tasks such as the empty container return task.

FIG. 11 shows an example of the data format of the base distance matrix data 1052 required for the main arithmetic processing step 230 . The inter-base distance matrix data is two-dimensional matrix data formed by digitizing the distance (or travel time) for all combinations of bases. Since the round trip route may differ between two bases, the total number of distances is N*(N−1), where N is the number of bases. A program using road vector data as an input and a shortest route calculation method (for example, Dijkstra's method) calculates the distance between two bases. The data 1052 is generated using the site management data 1065 prior to the main arithmetic processing step 230, or by inputting generated data and reading it into the input/output/calculation execution processing means 1051 of the main storage device. , can directly perform high-speed arithmetic processing.

Parameters such as the mixed loading capacity set in FIG. Here, the compulsory limit conditions may be set with reference to the predetermined vehicle limit conditions described above, and the total cargo volume of the vehicle does not exceed the upper limit of the volume of the vehicle, or the total cargo weight of the vehicle is This includes not exceeding the vehicle's load limit or not violating the delivery task's no consolidation setting conditions. Violation of any one of the above conditions indicates a violation of the mandatory limit.

FIG. 12 shows an example of empty container mixed loading determination processing. Vehicles assigned to each delivery task are checked one by one (step 2331) with respect to the delivery plan candidates that are the output of delivery plan candidate generation 232, and if the capacity limit of the vehicle is exceeded (step 2332) or the load limit is exceeded, (Step 2333), and if the mixed loading capacity upper limit is exceeded (Step 2334), it is determined that the compulsory restriction condition has been violated (Step 2336), and the process returns to Delivery Plan Candidate Generation 232 again. Otherwise, it determines that the mandatory constraint has been met (step 2335 ) and proceeds to total cost calculation step 234 . Of course, embodiments of the present invention may implement the mandatory constraint violation determination 233 described above in Dispatch Plan Candidate Generation 232 itself.

Specifically, taking the output data 550 of FIG. 15 as an example, the volume increase/decrease 570 is added according to the chronological order 564 to all the delivery vehicles assigned by the current delivery plan candidate to obtain the total volume. , the weight increase/decrease 571 is added to obtain the total weight, and when the state 565 is moving, the total volume and the total weight are the upper limit of the volume V and the upper limit of the weight W of the vehicle (362, 363). Determine whether the Similarly, it is determined whether the mixed-load capacity M exceeds the upper limit of the mixed-load capacity. Also, if the mixed loading capacity is set to 0 in the processing step 227 of FIG. Set the consolidation capacity of the vehicle to a small positive number less than or equal to 1 (for example, 0.001). In FIG. 12, the timing for returning to the delivery plan candidate generation step 232 is when a parameter of a vehicle violates the corresponding compulsory limiting condition, or when the number of vehicles violating the corresponding compulsory limiting condition reaches a certain number. Or, it is the time when all the vehicles in the delivery plan candidate have been judged.

One implementation of the process flow of total cost calculation 234 is shown in FIG. In the total cost calculation 234, for each delivery task of the delivery plan candidate output by the delivery plan candidate generation 232, from the viewpoint of the optimal solution, there is a certain difference in the assignment order of the delivery tasks, and the difference is quantified, Output as total total cost in operation loop processing. First, in step 23401, it is determined whether all delivery tasks have been processed. If so, output the total cost and go to step 235 . If not, one unprocessed delivery task is extracted as the current delivery task, and step 23402 determines whether the current delivery task is the empty container return task. Whether it is an empty container return task can be determined by specifying that the task order 519 is NEXT and the task ID corresponding to the related task ID 520 in the example of FIG.

If it is determined in step 23402 that the current delivery task is not the empty container return task, the process returns to step 23401. In the opposite case, the process proceeds to step 23403 to find a delivery task related to the empty container return task (hereinafter referred to as the original task). delivery task) to be assigned to the same vehicle. Specifically, in the data format of the output data 550 described later, it is possible to determine whether the two corresponding delivery tasks described above belong to the same vehicle ID 562 as the same vehicle. If it is not the same vehicle, it is determined that there is no optimum solution (it is far from the optimum solution), the preset cost α is added to the total cost (step 23404), and the process returns to step 23401. If it is the same vehicle, it is close to the optimum solution, so α is subtracted from the total cost, or another set value (for example, 30% of α) is subtracted (step 23405). Here, addition or subtraction of α to the total cost is performed on the total cost, so if the vehicles are not the same vehicle, only one of them may be performed. After the same vehicle determination process, the process proceeds to step 23406 to determine whether the empty container return task is executed after the original task. In the data format of the output data 550, the order 564 of the same vehicle ID 562 can be used to determine the order relationship of each delivery task. The determination of the order of order is determined by whether or not there is a load for the return task after the corresponding original delivery task is unloaded. In the determination, there may be other delivery tasks between unloading and loading, and there may be time vacancies. If the empty container return task is executed before the original task, it is far from the optimal solution, so add β to the total cost (step 23407) and return to step 23401. Also, if the empty container return task is executed after the original task, β is subtracted from the total cost in the same manner as the determination above (step 23408). Finally, in step 23409, it is determined whether the empty container return task and the related parcel delivery task are executed within the predetermined time, and the empty container return task and the parcel delivery task corresponding to the empty container return task are executed. Determine if the empty container return task is executed immediately after the package delivery task corresponding to the empty container return task, with no other delivery tasks in between. Specifically, in determining whether the empty container return task is executed immediately after the corresponding package delivery task, it can be determined by whether the empty container return task is loaded immediately after the corresponding package delivery task is unloaded. If there are other delivery tasks between them, add γ to the total cost (step 23410) and return to step 23401. Otherwise, subtract γ from the total cost (step 23411) and return to step 23401.

In the above three determination processes 23403, 23406, and 23409, predetermined constants α, β, and γ are used as cost values, and different costs are set by gradually approaching the optimal solution in the optimal solution search process. (α>>β>>γ is preferred). Therefore, in the main processing step 230, the assignment of the original task and the empty container return task to the same vehicle are preferentially performed. Next, the context of the delivery task and the empty container return task can be realized. Finally, consider a delivery order with no other delivery tasks between them. Here, the determination processes 23406 to 23408 regarding the cost β are processes for quickly and reliably converging to the optimum solution.

If the number of delivery tasks is relatively large, it may be difficult for the total cost calculation 234 alone to converge to an optimal solution, and there may be delivery order discrepancies in the delivery plan. Inconsistent ordering here indicates that the package delivery task associated with the empty container return task is assigned to different delivery vehicles. In this case, the embodiment of the present invention improves convergence in combination with the order mismatch determination process described above, and reduces or eliminates the delivery order mismatch. FIG. 14 shows an example of combination with the order mismatch determination process described above. Here, it is determined whether or not there is an order inconsistency with the delivery plan candidates output in the delivery plan candidate generation step 232 . If there is, the process returns to the delivery plan candidate generation step 232 again, and the order mismatch determination processing is performed in the delivery plan candidate generation 232 .

Specifically, first, after obtaining one delivery plan candidate in the delivery plan candidate generating step 232, the said delivery plan candidate is set as the current delivery plan candidate. First, in step 2321, it is determined whether or not the traversal of all delivery tasks of the current delivery plan candidate is completed. If so, go to step 233 . If not, step 2322 extracts one unprocessed delivery task as the current delivery task, and step 2323 determines if the current delivery task is an empty container return task. If it is determined in step 2323 that the current delivery task is not the empty container return task, step 2321 is returned to. In the opposite case, the process proceeds to step 2324 to determine whether the delivery task related to the empty container return task (hereinafter referred to as the original delivery task) is assigned to the same vehicle. When assigning to the same vehicle, the process returns to step 2321 . In the opposite case, the process proceeds to step 2325 to output the judgment result of order mismatch, and returns to the delivery plan candidate generating step 232 to generate one new delivery plan candidate. The timing for returning to the delivery plan candidate generation step 232 may be when a delivery task whose order does not match is found, or after traversing all the delivery tasks in the current delivery plan candidate is completed, or when the order of the delivery tasks does not match. reaches a predetermined number. Since the above processing has been performed, there is no order mismatch in the delivery plan candidates output thereafter. Therefore, steps 23403, 23404, and 23405 of FIG. 13 may be omitted in the total cost calculation of FIG.

In the delivery plan candidate generation step, there may be a certain number or more of delivery tasks whose delivery orders do not match among the delivery plan candidates acquired after a certain number of computation loops have been executed. Alternatively, by reducing the range of the delivery task data to be input, the operation loop processing may be divided into several times and executed again.

In dividing the input data, the input data is divided into two by, for example, grouping the delivery task in which the order mismatch occurs and all related delivery tasks into one group, and grouping the remaining delivery tasks into another group. Then, delivery plan candidate generation processing is performed for each group.

When generating delivery plan candidates for the groups acquired in the first division into two, if there is no discrepancy in the delivery order in each group, the delivery sub-plans of each group are put together to acquire an overall delivery plan candidate. For example, when acquiring delivery sub-plans for 5 and 7 delivery vehicles for 2 divided groups, delivery plan candidates for performing delivery processing with a total of 12 vehicles are acquired and output. On the other hand, if a delivery order mismatch occurs again in a certain group, the group may be divided into two by the above method. The above-described two-part dividing process may be performed multiple times until there is no discrepancy in the delivery order for each group.

After the main operation processing step 230, in the delivery plan output step 240, the generated delivery plan data is acquired in the data format of the output data 550 shown in FIG. 15, and display processing and the like are performed. The number of delivery plans to be output is not limited to one, and calculation results can be selected based on a plurality of factors. For example, select and output an appropriate delivery plan based on one or more of multiple factors such as total distance traveled, total delivery time, number of vehicles, number of unassigned delivery tasks, number of out-of-order delivery tasks, etc. It can be output in the form of data 550 . In the output data 550, the operation status 565 of each delivery vehicle (vehicle ID 562) on the delivery date 561 is output according to the chronological order 564. / 567), the start/end time of the relevant operating state 565 (568, 569), volume/weight increase/decrease (570, 571) according to the operating state 565 up to that point, and a delivery task ID 572 for loading/unloading. One delivery task ID usually has loading and unloading, so two different operating states are generated.

16A and 16B show examples of output screens generated based on the output data 550 in the delivery plan candidate 240. FIG. FIG. 16A is a delivery schedule table 600 showing the operating status of each delivery vehicle in chronological Gantt chart format, and FIG. 16B is a delivery route 700 showing on a map the delivery bases and delivery routes included in the delivery plan. Here, the output when the vehicle ID 562 in FIG. 15 is A0123 will be described as an example. In the display of the delivery schedule table 600, the vehicle A0123 (611) is labeled on the vertical axis, and the specific operational states are displayed in chronological order (order 564) on the right side. In the output data 550, a total of 8 operation states of loading, movement, standby, unloading, loading, lunch break, movement, and unloading are output. A total of 7 states of movement and base 1 are shown. This is because the two operating states of unloading/loading are indicated by using "site A" for display purposes.

The delivery schedule table 600 and the delivery route 700 can correspond. For example, in the delivery route 700, only the specified vehicle on the screen of the delivery schedule table 600 is displayed. Planned positions 731 and the like are shown. When the operating state of the vehicle is "moving", in order to determine the vehicle position 731 on the map, the route between the destination and the departure point is subdivided when the movement speed is constant, and the route from the departure point is divided into The point at which the time is reached may be set as the display position. 16A-16B are examples of display screen output. However, similar display contents may be output to an output medium such as PDF or paper.

Next, another embodiment of the system block diagram of the embodiment of the present invention will be described using the block diagram of FIG. FIG. 17 shows a structure of the type in which the computer 100 of FIG. The server 172 and client 171 have basically the same hardware structure as the computer 100 in FIG. The client 171 includes a CPU 1711/main storage device 1713, a secondary storage device 1714, a main bus 1712, a video card 1715, a network interface card (NIC) 1716, a video output port (not shown), and the like. The client 171 includes a CPU 1711, a main storage device 1713, a secondary storage device 1714, a main bus 1712, a video card 1715, a network interface card (NIC) 1716, a video output port (not shown), and the like. . Here, the main storage device 1713 includes an input/output processing module 17131 . The secondary storage device 1714 includes a data input processing module 17141 , a delivery plan output processing module 17142 and a delivery task data module 17143 . The server 172 includes a CPU 1721, a main storage device 1723, a secondary storage device 1724, a main bus 1722, a video card 1725, a network interface card (NIC) 1726, a video output port (not shown), and the like. . Here, the main storage device 1723 includes a calculation execution processing module 17231 and a base distance data module 17232 . The secondary storage device 1724 includes a calculation condition setting processing module 17241, a site management data module 17242, an optimum solution search processing module 17243, a vehicle management data module 17244, road vector data 17245, and a delivery task data module 17246. . In FIG. 17, the server 172 cooperates with the remote client 171 via the network 175 (intranet or Internet) to perform the arithmetic processing and output processing shown in FIG.

FIG. 18 shows the connection relationship of processing/data in FIG. Client 171 first establishes a connection with server 172 . Therefore, authentication processing such as ID/PW is performed for the API 1727, a 1:1 connection is established, and an execution standby state is entered. At this time, execution requests from a plurality of clients (for example, the clients 171) can be processed in parallel by activating a process or thread dedicated to the operation of the client 171 on the server side. In the data reading process 210, the site management data 17242, the vehicle management data 17244, and the delivery task data 17143 may be read from the client 171. As in the example shown in FIG. The base management data 17242 and the vehicle management data 17244 may be read from. Since base information and vehicle information are usually changed infrequently, they are set on the server side as main (master) data to reduce the load of data input processing 122 and improve processing efficiency. Main data is usually stored in CSV, table format, database format, or the like. As a result of data input processing 17141 , delivery task data 17143 is input by API 1727 of server 172 via network 175 .

After that, the input data 500 is generated by the calculation condition setting processing 17241, or the site management data 17242 is acquired via the API 1727 by reading it by the API 1727 of the server 172 as the data input processing 17141 as shown in FIG. generates the input data 500 shown in . In other words, the data input processing 17141 corresponds to executing part of the calculation condition setting processing 17241 . At this time, after inputting the data 500 , it is sufficient to set whether mixed loading is possible only in the calculation condition setting processing 17241 . The inter-base distance data 17232 is generated by the server 172 using the road vector data 17245 and the base management data 17242 . Also, the road vector data 17245 may be collected on demand from an external map information providing service system 176 such as the Internet via the NIC 1726 .

After that, the optimum solution search process 17243 corresponding to the main operation process step 230 is executed, and one or more generated output data 550 are transmitted to the client 171 via the API 1727 . In the delivery plan output process 17142, the process corresponding to the delivery plan output 240 in FIG. 3 is executed, and the result such as a screen is output. The map used for the delivery route 700 output by the client 171 may be collected on demand from an external map information providing service 176 such as the Internet via the NIC 1716 .

The present invention is realized by electronic hardware, or a combination of computer software and electronic hardware, in conjunction with each of the exemplary means and algorithmic steps described in the embodiments disclosed herein. A person skilled in the art can recognize that. Whether these functions are implemented in a hardware or software manner depends on the particular application and design constraints of the technical means. Skilled artisans may implement the described functionality in varying ways for each particular application, but these implementations are not considered beyond the scope of the invention.

For the convenience and brevity of the description, the specific working steps of the systems, devices and means described above can be referred to the corresponding steps of the method embodiments described above, which will be obvious to those skilled in the art. It will not be repeated here.

It should be understood that the disclosed apparatus and methods can be implemented in other ways in embodiments according to the present application. For example, the apparatus embodiments described above are merely exemplary. For example, the division of the above means is merely the division of logical functions, and there may be other division schemes when actually implemented. For example, several means or components may be combined or integrated into another system, or some features may be ignored or not performed. Also, any coupling or direct or communicative connection between components shown and discussed herein is through an interface, and any indirect or communicative connection of devices or means may be electrical, mechanical or otherwise.

Means described as separate parts may or may not be physically separated, and members indicated as means may or may not be physical means. That is, it may be located at one location or distributed over a plurality of network means. Some or all of these means can be selected according to actual needs to achieve the purpose of the embodiments of the present invention.

Also, each functional means in each embodiment of the present invention may be integrated into one processing means, or each means may physically exist separately, and two or more means may be combined into one means. may be accumulated in

The functions described above can be stored in a single computer-readable storage medium when realized in the form of software function means and sold and used as independent products. Based on such an understanding, the technical means of the present invention may be in the form of a software product, or the part that contributes to the prior art, or the part of the technical means. The computer software product is stored on a single storage medium and includes several instructions to implement all of the methods described in each embodiment of the present invention on a single computer device (such as a personal computer, server, or network device). Or let some steps be executed. The above storage media include media capable of storing various program codes, such as U disk, removable hard disk, ROM, RAM, magnetic disk or optical disk.

The above descriptions are only specific embodiments of the present invention, and the protection scope of the present invention is not limited thereto. Any variation or replacement readily figured out by a person skilled in the art within the disclosure scope of the present invention shall be covered by the protection scope of the present invention. Therefore, the protection scope of the present invention shall be based on the protection scope of the claims.

Claims (16)

A delivery plan generation method comprising:
If there is one or more delivery tasks associated with the information that the empty container must be picked up, among the delivery tasks represented by the delivery task data including information on a plurality of delivery tasks, the computer determines that the one or more delivery tasks generating, for each delivery task, information about an empty container pick-up task associated with that delivery task;
A computer allocates the plurality of delivery tasks and the generated empty container pick-up task to the plurality of delivery vehicles represented by vehicle management data including information on the plurality of delivery vehicles, using a predetermined delivery plan generation algorithm. creating a plan candidate;
A computer selects the candidate delivery plan based on whether the empty container pick-up task is executed before the delivery task associated with it and there are other tasks between the tasks in the candidate delivery plan. a step of evaluating;
A method for generating a delivery plan, comprising a step of outputting one or more candidates for a delivery plan as a delivery plan based on the evaluation of the candidates for the delivery plan. A delivery plan generation method comprising:
If the computer has one or more delivery tasks associated with the information that the empty container must be returned among the delivery tasks represented by the delivery task data including information on a plurality of delivery tasks, the one or more delivery tasks generating information about the empty container return task associated with the delivery task for each of
A delivery plan in which the computer assigns the plurality of delivery tasks and the generated empty container return task to the plurality of delivery vehicles represented by vehicle management data including information on the plurality of delivery vehicles, using a predetermined delivery plan generation algorithm. creating a candidate;
A computer evaluates the candidate shipping plan based on whether the empty container return task is executed after the associated shipping task in the candidate shipping plan and whether there are other tasks between those tasks. a step;
A method for generating a delivery plan, comprising a step of outputting one or more candidates for a delivery plan as a delivery plan based on the evaluation of the candidates for the delivery plan. 3. The method of claim 1 or 2,
The step of evaluating the delivery plan candidate includes:
whether the delivery task and an empty container task group, which is at least one of an empty container pick-up task and an empty container return task associated therewith, are assigned to the same delivery vehicle; providing different task costs for empty container tasks based on whether there are other tasks between them that run before and/or after the delivery task associated therewith;
and setting a total cost of the candidate for the delivery plan obtained by totaling task costs of the candidate for the delivery plan as an evaluation result of the candidate for the delivery plan. 3. The method of claim 1 or 2,
The step of evaluating the delivery plan candidate includes:
whether the delivery task and an empty container task group, which is at least one of an empty container pick-up task and an empty container return task associated therewith, are assigned to the same delivery vehicle; providing different task costs for empty container tasks based on whether there are other tasks between them that run before and/or after the delivery task associated therewith;
calculating the sum of the total cost of the delivery plan candidate obtained by summing the task costs of the delivery plan candidate and the delivery distance cost of the delivery tasks in the delivery plan candidate, and making the evaluation result of the delivery plan candidate. A delivery plan generation method, comprising: 5. The method of any one of claims 1-4 ,
Assigned to a delivery vehicle different from a delivery vehicle to which a delivery task associated with an empty container task group that is at least one of an empty container pick-up task and an empty container return task existing in the delivery plan candidate is assigned determining the number of empty container task groups;
adjusting the delivery order of such empty container tasks or the delivery tasks with which such empty container tasks are associated, if said number exceeds a preset threshold; or and a step of excluding plan candidates. 6. The method of any one of claims 1-5 ,
a step of presetting a delivery capacity to be used for determining whether mixed loading is possible for a delivery vehicle, and presetting a mixed loading capacity having an upper limit, which is used for determining whether mixed loading is possible for a delivery task;
setting a mixed loading capacity of a delivery task for which mixed loading is not permitted to an upper limit value of the mixed loading capacity. 7. The method of claim 6 , wherein
a step of, after generating one delivery plan candidate, determining whether or not there is a delivery vehicle exceeding the mixed loading capacity in the delivery plan candidate;
If a delivery vehicle exceeding the consolidated loading capacity exists in the delivery plan candidate, adjusting the delivery order of such a delivery task or the delivery order of the empty container task group associated with such a delivery task, or a step of excluding the delivery plan candidate, wherein the empty container task group is at least one of an empty container pick-up task and an empty container return task. 8. The method of claim 7 , wherein
After generating one delivery plan candidate, the step of determining whether or not a delivery vehicle exceeding the consolidated capacity exists in the delivery plan candidate includes:
For the delivery vehicle of the delivery plan candidate, a route between adjacent bases that the delivery vehicle passes through is determined, the mixed loading capacity of all delivery tasks on the route of the delivery vehicle is accumulated, and the upper limit of the mixed loading capacity is calculated. If so, determine that there are delivery vehicles that exceed the consolidated capacity;
or,
One or a plurality of delivery vehicles that pass through the route between the adjacent bases of the delivery plan candidate are determined, and the mixed loading capacity of all delivery tasks on the route of each delivery vehicle is totaled, A method for generating a delivery plan, comprising: determining that there is a delivery vehicle exceeding the consolidated capacity when the consolidated capacity is equal to or greater than the upper limit value of the consolidated capacity. 9. The method of any one of claims 1-8 ,
Before generating the delivery plan candidate, further,
Allocating to all delivery tasks one task indicator ID uniquely labeling the delivery task, and establishing a relationship between related delivery tasks. 9. The method of any one of claims 1-8 ,
Based on a predetermined delivery plan generation algorithm, in the process of repeating the generation of delivery plan candidates up to a preset upper limit of search times, in the delivery plan candidates obtained when the number of generations reaches a preset number of times, When the number of empty container task groups assigned to a different delivery vehicle than the delivery vehicle to which the delivery task associated with the empty container return task is assigned exceeds a predetermined value,
An empty container task group assigned to a delivery vehicle different from the delivery vehicle to which the delivery task associated with the empty container task group is assigned, and dividing into two groups, a first task group consisting of delivery tasks associated with the empty container task group, and a second task group consisting of other tasks;
Based on a predetermined delivery plan generation algorithm, delivery sub-plan candidates are generated for the first task group and the second task group, respectively, and the first delivery sub-plan candidate and the second delivery sub-plan candidate are generated. a step of obtaining;
If there is an empty container task group assigned to a delivery vehicle different from the delivery vehicle to which the delivery task associated with the empty container task group is assigned in the first delivery sub-plan candidate, the first task group is selected. returning to the original task group and dividing the delivery tasks in the original task group into two groups;
If there is no empty container task group assigned to a delivery vehicle different from the delivery vehicle to which the delivery task associated with the empty container task group is assigned in the first delivery sub-plan candidate, the first delivery sub-plan candidate does not exist. summarizing candidate sub-plans and all second candidate delivery sub-plans to obtain candidate delivery plans for said pending delivery tasks, wherein the empty container task group comprises an empty container pick-up task and an empty container return task. A delivery plan generation method characterized by being at least one of A delivery plan generation device,
a storage device for storing vehicle management data including information on a plurality of delivery vehicles and delivery task data including information on a plurality of delivery tasks;
If there are one or more delivery tasks associated with the information indicating that empty containers must be picked up among the delivery tasks represented by the delivery task data, each of the one or more delivery tasks is associated with the delivery task. generate information about the empty container pick-up task,
creating a delivery plan candidate for allocating the plurality of delivery tasks and the generated empty container pick-up task to the plurality of delivery vehicles represented by the vehicle management data using a predetermined delivery plan generation algorithm;
evaluating the candidate Dispatch Plan based on whether, in the Candidate Dispatch Plan, the empty container pick-up task is executed before the Dispatch task associated with it, and there are other tasks between those tasks;
and a processor that outputs one or more candidates for the delivery plan as a delivery plan based on the evaluation of the candidates for the delivery plan. A delivery plan generation device,
a storage device for storing vehicle management data including information on a plurality of delivery vehicles and delivery task data including information on a plurality of delivery tasks;
Among the delivery tasks represented by the delivery task data, if there is one or more delivery tasks associated with information indicating that the empty container must be returned, each of the one or more delivery tasks is associated with the delivery task. generate information about the empty container return task,
creating a delivery plan candidate for allocating the plurality of delivery tasks and the generated empty container return task to the plurality of delivery vehicles represented by the vehicle management data using a predetermined delivery plan generation algorithm;
evaluating the Candidate Dispatch Plan based on whether, in the Candidate Dispatch Plan, the Return Empty Container task is executed after the Dispatch task associated with it and there are other tasks between those tasks;
and a processor that outputs one or more candidates for the delivery plan as a delivery plan based on the evaluation of the candidates for the delivery plan. 13. A device according to claim 11 or 12,
In evaluating the delivery plan candidate,
whether the delivery task and the associated empty container tasks are assigned to the same delivery vehicle, and the empty container tasks are executed before and/or after the associated delivery tasks; providing task costs of different magnitudes to empty container task groups based on whether there are other tasks between those tasks;
and setting the total cost of the delivery plan candidate obtained by totaling the task costs of the delivery plan candidate as the evaluation result of the delivery plan candidate. A delivery plan generation device characterized by being at least one of empty container return tasks. 14. A device according to any one of claims 11-13,
The processor
Determining the number of empty container task groups that are present in the delivery plan candidate and that are assigned to a different delivery vehicle from the delivery vehicle to which the delivery task associated with the empty container task group is assigned;
adjusting the delivery order of such empty container tasks or the delivery tasks with which such empty container tasks are associated, if said number exceeds a preset threshold; or Exclude plan candidates,
A delivery plan generating device, wherein the empty container task group is at least one of an empty container pick-up task and an empty container return task. If there are one or more delivery tasks associated with the information that empty containers need to be picked up, among the delivery tasks represented by the delivery task data containing information on a plurality of delivery tasks, each of the one or more delivery tasks generating information about an empty container pick-up task associated with the delivery task for
A delivery plan candidate for allocating the plurality of delivery tasks and the generated empty container pick-up task to the plurality of delivery vehicles represented by vehicle management data including information on the plurality of delivery vehicles by a predetermined delivery plan generation algorithm. a step to create;
Evaluating the Candidate Dispatch Plan based on whether, in the Candidate Dispatch Plan, the Empty Container Pickup Task is executed before the Dispatch Task with which it is associated, and there are other tasks between those tasks. When,
and outputting one or more candidate delivery plans as a delivery plan based on the evaluation of the candidate delivery plans. If there are one or more delivery tasks associated with the information that the empty container must be returned among the delivery tasks represented by the delivery task data containing information on multiple delivery tasks, for each of the one or more delivery tasks , generating information about the empty container return task associated with the delivery task;
Using a predetermined delivery plan generation algorithm, a delivery plan candidate is created for allocating the plurality of delivery tasks and the generated empty container return task to the plurality of delivery vehicles represented by vehicle management data including information on the plurality of delivery vehicles. and
evaluating the Candidate Dispatch Plan based on whether, in the Candidate Dispatch Plan, the Return Empty Container task is executed after the Dispatch task associated with it and there are other tasks between those tasks;
and outputting one or more candidate delivery plans as a delivery plan based on the evaluation of the candidate delivery plans.

Images