JP6660973B2 - Method, apparatus and system for generating delivery plan of delivery vehicle - Google Patents

Description

  The present invention relates to a technical field of a vehicle routing problem (VRP), and more particularly, to a method, an apparatus, and a system for generating a delivery plan of a delivery vehicle.

  The vehicle routing problem (VRP) is to meet the needs of a certain number of customers, each with a different number of package delivery needs, and to achieve the objectives of shortest distance, minimum cost, and minimum time under certain restrictions. In this way, after determining the person in charge of baggage delivery and designing an appropriate traveling route, the baggage is provided from the delivery center to the customer.

  At present, algorithms related to the vehicle route problem include exact algorithms such as a branch-and-bound method, a branch cut method, and a set covering method; a saving method, a pseudo-annealing method, a deterministic annealing method, a tabu search method, and a genetic algorithm. , Neural networks, ant colony methods, heuristics algorithms such as Genetic Algorithms (GA). In the automatic generation of a vehicle delivery plan, a large neighborhood search (LNS) algorithm, which is one of the neighborhood search methods, is relatively effective, and an optimal delivery task allocation method for a vehicle using the LNS is relatively effective. Search for. The search is usually performed by a method approaching the optimal solution, quantifying the difference from the optimal solution (the sum of the costs), and gradually repeating it in the direction of cost reduction.

  In some application scenes of VRP, it is necessary to deliver a delivery package in a delivery container. In such a scene, it is usually necessary to return the empty container after the completion of the package delivery. For example, in the logistics scheduling of the manufacturing industry including the delivery of automobile parts, since the number of delivery containers differs depending on the manufacturer and the number of delivery containers is limited, empty containers are often returned to the manufacturer immediately after delivery. Due to such special needs, it is technically difficult to realize an optimal order of the delivery tasks among the above-described application scenes only by the neighborhood search method. Therefore, the conventional algorithm has not yet reached a practical level in creating a delivery plan including return of empty containers. At present, in the distribution industry, there are still many cases where a delivery plan for the above-mentioned application scene is manually created.

  The technical problem to be solved by the embodiment of the present invention is to automatically generate a delivery plan including a delivery requirement of returning an empty container to a manufacturer after delivery, improve the efficiency of creation of the delivery plan, and reduce human cost. An object of the present invention is to provide a method, an apparatus and a system for generating a delivery plan of a delivery vehicle for reducing the number of delivery vehicles.

  In order to solve the above technical problem, an embodiment of the present invention provides a delivery plan generation method for picking up a package between a plurality of bases using a plurality of delivery vehicles and outputting a delivery order for delivery. I do. In the delivery plan generation method, whether 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 Based on whether or not the task is executed within a predetermined time, a delivery plan candidate is evaluated to obtain an evaluation result. Further, based on the evaluation results of the delivery plan candidates, one or more delivery plan candidates are output as a final delivery plan. Among them, to be executed within the predetermined time, the empty container return task and the related package delivery task are executed simultaneously, or the empty container return task is executed after the related package delivery task. In addition, there is no other delivery task between them.

  The embodiment of the present invention further provides a delivery plan generation device for picking up a package between a plurality of bases using a plurality of delivery vehicles and outputting a delivery order for delivery. The delivery plan generation device determines whether the empty container return task in the delivery plan candidate and the related package delivery task are assigned to the same delivery vehicle, and if the tasks are assigned to the same delivery vehicle, A delivery plan evaluation means for evaluating a delivery plan candidate to obtain an evaluation result based on whether the empty container return task and the related package delivery task are executed within a predetermined time; and A delivery plan output means for outputting one or more delivery plan candidates as a final delivery plan based on the evaluation results of the candidates. The empty container return task and the associated package delivery task are performed simultaneously, or the empty container return task is performed after the associated package delivery task and other deliveries between the two Including that the risk does not exist.

  Embodiments of the present invention further provide a delivery 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 present invention further provide a computer-readable storage medium. When the computer program stored in the storage medium is executed by the processor, the above-described delivery plan generation method is realized.

  Compared with the prior art, in the delivery plan generating 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 candidate, and the task cost in the first delivery method is determined in advance. Is optimal, the algorithm automatically outputs the delivery order of the desired empty container return, satisfies the empty container return needs in the actual logistics scene, and avoids the manual creation of the delivery plan. Thus, the cost of creating a delivery plan can be reduced, and the efficiency of creating a delivery plan can be improved.

  In order to more clearly explain the technical means of the embodiments of the present invention, the drawings required for describing the embodiments of the present invention will be briefly introduced below. Apparently, the drawings in the following description are merely some embodiments of the present invention. For those skilled in the art, other drawings can be obtained from these drawings without performing creative work.

FIG. 1 is a flowchart of a delivery plan generation method according to an embodiment of the present invention. FIG. 2 is a schematic structural diagram of a delivery plan generation device according to an embodiment of the present invention. FIG. 3 is a block diagram showing the overall structure of the delivery plan generation system according to the embodiment of the present invention. FIG. 4 is an exemplary flowchart of a delivery plan generation method according to an embodiment of the present invention. FIG. 5 is a diagram illustrating an example of the base management data according to the embodiment of the present invention. FIG. 6 is a diagram illustrating an example of vehicle management data according to the embodiment of the present invention. FIG. 7 is a diagram illustrating an example of the delivery task data in the embodiment of the present invention. FIG. 8 is a diagram illustrating an example of input data generated in the embodiment of the present invention. FIG. 9 is an exemplary flowchart of adding an empty container return task in the embodiment of the present invention. FIG. 10 is an exemplary flowchart of adding an empty container pickup task in the embodiment of the present invention. FIG. 11 is a diagram illustrating an example of the inter-site distance matrix data according to the embodiment of the present invention. FIG. 12 is an exemplary flowchart of an empty container mixed loading availability determination process according to the embodiment of the present invention. FIG. 13 is an exemplary flowchart of the total cost calculation process in the embodiment of the present invention. FIG. 14 is an exemplary flowchart of the same vehicle compulsory constraint violation process in the embodiment of the present invention. FIG. 15 is a diagram illustrating an example of output data according to the embodiment of the present invention. 16A and 16B are diagrams illustrating an example of an output screen generated according to the embodiment of the present invention. FIG. 17 is another schematic structural diagram of the block diagram of the delivery plan generation system according to the embodiment of the present invention. FIG. 18 is a schematic diagram showing a connection relation between processing and data in another system block diagram shown in FIG.

  In order to clarify the technical problem, technical means, and advantages to be solved by the present invention, the present invention will be described in detail below with reference to the drawings and specific embodiments. In the following description, providing specific details of specific settings and components is merely an aid in providing a thorough understanding of embodiments of the present invention. Thus, it will be apparent to one skilled in the art that various changes and modifications may be made to the embodiments described herein without departing from the scope and spirit of the invention. Also, for clarity and conciseness, descriptions of well-known functions and structures are omitted.

  “One embodiment” or “one embodiment” throughout the specification means that a particular feature, structure, or characteristic associated with the embodiment is included in at least one embodiment of the present invention. Then you should understand. Therefore, "in one embodiment" or "in one embodiment" appearing in each part of the specification does not necessarily refer to the same embodiment. Also, these particular features, structures, or characteristics may be arbitrarily combined in one or more embodiments as appropriate.

  In each embodiment of the present invention, the size of the number of each process described later does not mean before or after the execution order. It should be understood that the order of execution of each step is determined by its function and intrinsic logic and should not constitute any limitation to the implementation of an embodiment of the present invention.

  Please refer to FIG. Embodiments of the present invention provide a delivery plan generation method. According to this method, it is possible to pick up a package by patrol of a plurality of bases by a plurality of delivery vehicles and output an optimal order of a delivery task to be delivered. As shown in FIG. 1, the method includes the following steps.

  In step 11, whether 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 A delivery plan candidate is evaluated based on whether or not it is executed within a predetermined time, and an evaluation result is obtained.

  The delivery task according to the embodiment of the present invention includes a package delivery task for delivering a package from one location (for example, a delivery departure location) to another location (a delivery destination location). It may include an empty container return task to return from the destination base to the delivery departure point. Thus, for each empty container return task, there is one associated package delivery task, but for the package delivery task, there may be an associated empty container return task, and if so, the associated empty container return task. The task may not exist. Here, to be executed within the predetermined time, the empty container return task and the related package delivery task are simultaneously executed, or the empty container return task is executed after the related package delivery task. And there is no other delivery task between them.

  In the embodiment of the present invention, when evaluating the delivery plan candidate, whether the empty container return task and the associated package delivery task are assigned to the same delivery vehicle, and, and the empty container return task Based on whether or not the related package delivery task is executed within a predetermined time, task costs of different sizes are set for the empty container return task, and then the task costs in the delivery plan candidate are totaled. The obtained total cost of the delivery plan candidate is used as the evaluation result of the delivery plan candidate.

  In step 12, 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.

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

  According to the above steps, the embodiment of the present invention takes into consideration the task cost of the empty container return task in a different delivery format in the total cost of the delivery plan candidate, so that the algorithm automatically determines the delivery order of the desired empty container return. To satisfy the needs of returning empty containers in the actual logistics scene, avoid the manual creation of the delivery plan, reduce the cost of creating the delivery plan, and improve the efficiency of creating the delivery plan.

  In the embodiment of the present invention, the delivery plan candidates include a delivery task execution order and assigned delivery vehicles. Specifically, a search algorithm such as a genetic algorithm (GA: Genetic Algorithm) or a large neighborhood search (LNS: Large Neighborhood Search) is used for a delivery task (including a package delivery task and an empty container return task) waiting for assignment. Then, the optimum solution is approached by a plurality of searches, a plurality of delivery plans are obtained by the search, and these delivery plans are set as delivery plan candidates.

  The above search may be executed after reaching the predetermined upper limit of the number of searches, and may be ended, or may be ended earlier before reaching the upper limit of the predetermined number of searches. For example, if the obtained 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 obtained delivery plan candidate is output. I do. Also, for example, the number y1 of empty container return tasks assigned to a delivery vehicle different from the related package delivery task existing in the delivery plan candidate and the number of empty container return tasks assigned to the same delivery vehicle as the related package delivery task If the sum of the number y2 of empty container return tasks that are not executed within the above-mentioned predetermined time with the related package delivery task is equal to or less than a predetermined second threshold value, the search may be terminated ahead of schedule.

  During the search by the search algorithm, if the number of empty container return tasks present in the current delivery plan candidate and assigned to a delivery vehicle different from the related package delivery task is equal to or greater than a predetermined second threshold, the current delivery is performed. Make adjustments to the delivery tasks in the plan candidates or exclude the current delivery plan candidates. The adjustment includes adjusting the delivery order of the empty container return task assigned to a delivery vehicle different from the related package delivery task. For example, the empty container return task is inserted into another position in the current delivery plan candidate, or the delivery order is exchanged with another delivery task.

  The total cost includes the task cost of the empty container return task. In order to achieve the purpose of immediately returning the empty containers after the delivery of the package, in the embodiment of the present invention, task costs of different sizes are provided for the empty container return tasks. If the empty container return task and the related package delivery task are assigned to the same delivery vehicle, and the empty container return task and the related package 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 delivery plan candidates, the embodiment of the present invention considers the influence of the order of the delivery tasks in the delivery plan so as to obtain a desired delivery plan.

  In the embodiment of the present invention, whether 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. Task costs of different sizes are set for the empty container return tasks based on whether or not the tasks are executed within a period, and the desired delivery method is output to the algorithm. As one specific implementation, for the empty container return task, a first task cost is used in the first delivery method, a second task cost is used in the second delivery method, a third task cost is used in the third delivery method, and a fourth delivery is performed. Set to have a fourth task cost in the scheme. Here, as the first delivery method, the empty container return task and the related package delivery task are assigned to the same delivery vehicle, and the empty container return task and the related package delivery task are set within a predetermined time. Be executed. As the second delivery method, the empty container return task and the related package delivery task are assigned to the same delivery vehicle, and the empty container return task is executed after the related package delivery task, and another delivery is performed between the two. Task exists. As the third delivery method, an empty container return task and a 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, an empty container return task and a related package delivery task are assigned to different delivery vehicles.

  Here, the first task cost, the second task cost, the third task cost, and the fourth task cost increase in order. According to the different task costs in the different delivery methods described above, it is indicated that the first delivery method is the most desired delivery method of 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 the embodiment of the present invention, the total cost of the delivery plan candidate also considers the delivery distance cost. Since different delivery plan candidates may have different delivery vehicle routes, the delivery distances are different and correspond to different delivery distance costs. In step 12, the delivery distance cost of each delivery task in the delivery plan candidate is statistic, the task cost of the empty container return task in the delivery plan candidate is statistic, and the delivery is performed based on the delivery distance cost and the task cost. Obtain evaluation results of plan candidates. For example, different weights are assigned to the delivery distance cost and the task cost, and a weighted sum of both is obtained to obtain the evaluation result of the delivery plan candidate.

  In the embodiment of the present invention, there are many factors such as, for example, delivery time, delivery road cost (for example, different roads may have different costs, and a highway requires additional tolls). May be considered in the evaluation result. These factors are considered in the search by the search algorithm, but will not be described in further detail in the text.

  As one implementation, the embodiment of the present invention is configured such that when acquiring one delivery plan candidate generated by a search algorithm (hereinafter, referred to as a current delivery plan candidate), a related delivery plan candidate existing in the delivery plan candidate is acquired. The number of empty container return tasks assigned to a delivery vehicle different from the package delivery task to be performed is determined. If the number exceeds a preset threshold, adjustment is performed on the delivery tasks in the delivery plan candidates, or the delivery plan candidates are excluded.

In the embodiment of the present invention, a mixed capacity having an upper limit M _max is set in advance, and a mixed capacity of a non-mixable delivery task is set to the upper limit M _max , and the mixed capacity is set. The mixed capacity of the tasks is set to a positive number K which is much smaller than M _max . The value of the positive number K is set with reference to the number S of the delivery tasks, and is a value smaller than, for example, M _max / S. In addition, a delivery capacity used for determining whether or not consolidation is possible is set for the delivery vehicle, and the cargo volume of the delivery vehicle at the same time must not exceed the delivery capacity. As one example, the upper limit value M _max of the consolidation capacity is set to 1, and the consolidation capacity of the delivery task that can be mixed is set to 0.01. In determining a delivery vehicle that violates the predetermined restriction condition in the current delivery plan candidate, for each delivery vehicle in the delivery plan candidate, the combined capacity of all delivery tasks delivered by the delivery vehicle is accumulated, and the combined capacity is equal to or greater than the combined capacity. In this case, it is determined that the delivery vehicle violates the setting condition of the delivery task in which the consolidation cannot be performed.

  Further, whether or not the delivery task can be mixed may be determined based on the task attribute of the delivery task. When acquiring a delivery task waiting to be assigned, a task attribute can be specified, and the task attribute can include instruction information indicating whether mixed loading is possible. If the related package delivery task cannot be mixed with the empty container return task, the default is that the empty container return task also cannot be mixed. Of course, if the luggage delivery task related to the empty container return task cannot be mixedly loaded, it can be specially indicated that the empty container return task can be mixedly loaded.

  In one implementation, the embodiment of the present invention is configured such that, when one delivery plan candidate (hereinafter, referred to as a current delivery plan candidate) is obtained, a delivery vehicle exceeding the mixed capacity exists in the delivery plan candidate. If the delivery plan candidate includes a delivery vehicle exceeding the consolidation capacity, the delivery task in the delivery plan candidate is adjusted or the delivery plan candidate is excluded.

  In determining whether there is a delivery vehicle exceeding the consolidation capacity in the delivery plan candidate, a route between adjacent bases through which the delivery vehicle passes is determined for the delivery vehicle of the delivery plan candidate, and the route of the delivery vehicle is determined. Are accumulated, and if the combined capacity is equal to or more than the upper limit of the combined capacity, it is determined that there is a delivery vehicle exceeding the combined capacity. Alternatively, for a route between adjacent bases of a delivery plan candidate, one or a plurality of delivery vehicles that pass through the route are determined, and the combined capacity of all delivery tasks of the delivery vehicle on each route is accumulated, and the combined loading is performed. If the capacity is equal to or larger than the upper limit, it is determined that there is a delivery vehicle exceeding the mixed capacity.

  Furthermore, in the embodiment of the present invention, it is also possible to set many limiting conditions other than the above-mentioned mixed capacity and determine whether or not the delivery vehicle satisfies these conditions. In this case, first, it is determined whether or not a delivery vehicle violating the predetermined vehicle restriction condition exists in the current delivery plan candidate. If there is a delivery vehicle that violates the predetermined vehicle restriction condition in the current delivery plan candidate, adjust the delivery task in the delivery plan candidate, or exclude the current delivery plan candidate, and remove the current delivery plan candidate. Do not calculate the total cost of the delivery plan candidate. If there is no delivery vehicle that violates 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 load of the vehicle does not exceed the upper limit of the volume of the vehicle, or that the total weight of the vehicle does not exceed the upper limit of the load of the vehicle, or that the vehicle is delivered. Including not violating the setting condition that task loading is not allowed.

  Further, in the embodiment of the present invention, after obtaining one delivery plan candidate (current delivery plan candidate), it is determined that no delivery vehicle violating the predetermined vehicle restriction condition exists in the current delivery plan candidate. Then, a first number of empty container return tasks that are present in the current delivery plan candidate and are assigned to delivery vehicles different from the related package delivery task is determined. When the first number exceeds a predetermined first threshold value, the distribution task in the distribution plan is adjusted or the current distribution plan candidate is excluded. When the first value is equal to or less than the predetermined first threshold, the task 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 first threshold value is set based on factors such as the total number of delivery tasks and cost requirements.

  Note that the delivery task waiting for assignment according to the embodiment of the present invention may be a delivery task that is generated based on a package delivery task provided by a user and includes a package delivery task and an empty container return task. Specifically, for example, when the only delivery task provided by the user is a package delivery task, in the embodiment of the present invention, a package delivery task that requires return of an empty container after package delivery is determined, and the return of the empty container is performed. The related empty container return task is added to the package delivery task that needs to be performed, and the execution order of the related empty container return task is after the package delivery task that needs to return the empty container after the above package delivery. Label.

  Here, the task attribute of the package delivery task is analyzed to determine whether it is necessary to return an empty container to the package delivery task. When providing a package delivery task, the user needs to specify the task attribute of the task. Usually, the departure base and end base of the package delivery task, delivery time request, package volume and weight information, mixed availability, empty, Information such as the necessity of returning the container is included.

  Considering that the empty container may not be located at the departure point of the package delivery task, the empty container is first picked up from another point, and then the luggage is loaded at the departure point and delivered to the destination point. Therefore, in an embodiment of the present invention, after obtaining at least one package delivery task provided by the user, package delivery that requires collection of an empty container from another location other than the delivery departure location before package delivery. Determine the task. A related empty container collection task is added to the package delivery task that requires the collection of empty containers from other bases other than the above delivery departure base, and the execution order of the related empty container collection task is as follows. It is marked as being before a package delivery task that requires picking up empty containers from other locations other than the delivery departure location.

  According to the above method, the embodiment of the present invention can generate a delivery task waiting for assignment based on a package delivery task provided by a user. It may include one or both of a container collection task and an empty container return task.

  In order to mark the delivery task in the search algorithm, in the embodiment of the present invention, all the delivery tasks are assigned a task indicator ID that uniquely identifies the delivery task, and the related task is assigned to the delivery task having the related relationship. Establish relationships. For example, the related relationship between the related empty container pickup task and the package delivery task is established, and the related relationship between the related package delivery task and the empty container return task is established.

  In the embodiment of the present invention, when generating a delivery plan candidate of the delivery task waiting to be assigned by the search algorithm, an upper limit value of the number of searches is set. When the number of searches reaches the upper limit, the search is terminated and a delivery plan candidate is output. During the search, processing can be performed in the following manner to accelerate convergence.

  Based on a predetermined search algorithm, in the process of repeating generation of a delivery plan candidate up to a preset search frequency upper limit value, in a delivery plan candidate obtained when the number of generations reaches the preset number, the relevant If the number of empty container return tasks assigned to delivery vehicles different from the baggage delivery task exceeds a predetermined value, the delivery task in the original task group whose initial value is the delivery task waiting to be assigned is set to the related package delivery task. A first task group consisting of an empty container return task assigned to a different delivery vehicle and its related delivery task, and a second task group consisting of other delivery tasks are divided into two groups, and a predetermined search is performed. Based on the algorithm, generation of a delivery sub-plan candidate is performed for each of the first task group and the second task group. Acquiring a first delivery sub-plan candidate and a second delivery sub-plan candidate, and determining that there is an empty container return task assigned to a delivery vehicle different from the associated package delivery task in the first delivery sub-plan candidate. The first task group is set as the original task group, and the process returns to the step of dividing the delivery tasks in the original task group into two groups. In the first delivery subplan candidate, the delivery different from the related package delivery task is performed. If there is no empty container return task assigned to the vehicle, the first delivery sub-plan candidate and all the second delivery sub-plan candidates are put together, and a delivery plan candidate of the delivery task waiting for assignment is acquired.

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

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

  Embodiments of the present invention further provide a computer-readable storage medium. When the computer program stored in the storage medium is executed by the processor, the delivery plan generating method according to any one of the method embodiments is realized.

  Based on the above method, embodiments of the present invention further provide an apparatus for performing 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 package delivery task are assigned to the same delivery vehicle, And, if assigned to the same delivery vehicle, evaluates the delivery plan candidate based on whether the empty container return task and the associated package delivery task are executed within a predetermined time, and And a delivery plan output means 22 for outputting one or more delivery plan candidates as a final delivery plan based on the evaluation result of the delivery plan candidates, The task executed within the above-mentioned predetermined time includes that the empty container return task and the related package delivery task are simultaneously executed, or that the empty container return task is related to the package delivery. And it is performed after the disk including the absence of 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 Task costs of different sizes are set for the empty container return tasks based on whether they are executed within the time, and the total cost of the delivery plan candidates obtained by summing up the task costs of the delivery plan candidates is the delivery plan candidate It is preferable to include a task cost statistical means for obtaining the evaluation result.

  The delivery plan generation device is present in the delivery plan candidate, determines the number of empty container return tasks assigned to delivery vehicles different from the related package delivery task, and when the number exceeds a preset threshold, It is preferable to further include a delivery plan analysis unit for adjusting the delivery task in the delivery plan candidate or excluding the delivery plan candidate.

  The above-mentioned delivery plan generation device sets in advance a delivery capacity to be used for determining whether or not mixed loading is possible for a delivery vehicle, is used to determine whether or not mixed loading is possible for a delivery task, and sets in advance a mixed capacity having an upper limit value, and is not allowed to be loaded. It is preferable to further include a capacity setting means for setting the mixed capacity of the delivery task to the upper limit of the mixed capacity.

  The above-mentioned delivery plan generation device determines whether a delivery vehicle exceeding the consolidation capacity exists in the distribution plan candidates after generating one delivery plan candidate by a search algorithm, and If it exists in the candidate, it is preferable to further include a consolidation determination unit for adjusting the delivery task in the delivery plan candidate or excluding the delivery plan candidate.

  Specifically, when determining whether or not there is a delivery vehicle exceeding the combined capacity, the mixed loading determination means determines a route between adjacent bases through which the delivery vehicle passes with respect to the delivery vehicle of the delivery plan candidate. Then, the combined capacity of all delivery tasks of the delivery vehicle on the route is accumulated, and when the combined capacity is equal to or more than the upper limit of the combined capacity, it is determined that there is a delivery vehicle exceeding the combined capacity. Alternatively, for a route between adjacent bases of the delivery plan candidate, one or a plurality of delivery vehicles passing through the route are determined, and the combined loading capacities of all delivery tasks on the route of each delivery vehicle are respectively accumulated, and If it is equal to or more than the upper limit of the mixed capacity, it is determined that there is a delivery vehicle exceeding the mixed capacity.

  It is preferable that the delivery plan generation device further includes a delivery plan generation unit. Based on a predetermined search algorithm, the delivery plan generation means repeats generation of a delivery plan candidate up to a preset search count upper limit value, and obtains a delivery obtained when the generation count reaches the preset count. If the number of empty container return tasks assigned to a delivery vehicle different from the related package delivery task exceeds the predetermined value during the plan candidate, the delivery task in the original task group whose initial value is the delivery task waiting for assignment is A first task group consisting of an empty bag return task and a related delivery task assigned to a different delivery vehicle from the related package delivery task, and a second task group consisting of other tasks. And, based on a predetermined search algorithm, respectively, for the first task group and the second task group, Is generated to obtain a first delivery sub-plan candidate and a second delivery sub-plan candidate, and during the first delivery sub-plan candidate, return of empty containers assigned to a delivery vehicle different from the associated package delivery task If there is a task, the first task group is set as the original task group, and the process returns to the step of dividing the delivery tasks in the original task group into two groups. If there is no empty container return task assigned to a delivery vehicle different from the task, the first delivery sub-plan candidate and all the second delivery sub-plan candidates are combined, and the delivery plan candidate of the assignment task waiting for assignment is determined. get.

  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 to obtain a delivery plan candidate evaluation result.

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

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

  In the secondary storage device 106, for example, a data input processing module 1061, a calculation condition setting processing module 1062, an optimal solution search processing module 1063, a delivery plan output processing module 1064, a base management data 1065, a vehicle management data Each type of input data and program modules required for the arithmetic processing of the embodiment of the present invention, such as 1066, delivery task data 1067, and road vector data 1068, are stored. In the execution of 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 the search processing is performed together with the inter-base distance data 1052 to make a delivery plan. Output.

  In order to understand the above technical means of the embodiment of the present invention, the method of the embodiment of the present invention will be more specifically described below by way of specific flows of some examples.

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

  In the data reading step 210, the base management data 1065, the vehicle management data 1066, and the delivery task data 1067 are read. After that, a calculation condition setting step 220 is performed as a pre-process of the main operation processing step 230. In the main operation processing step 230, generation of a delivery plan is repeatedly performed to obtain an optimal delivery plan.

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

  In step 232, a delivery plan candidate is obtained by searching using a search algorithm such as the LNS algorithm or GA. In step 233, it is determined whether the generated delivery plan candidate violates the compulsory restriction condition. In the case of a violation, the current delivery plan candidate is adjusted or the current delivery plan candidate is excluded, and the process returns to step 232 to generate a new delivery plan candidate. If not, the process proceeds to step 234 to calculate the total cost of the current delivery plan candidate.

  Here, the compulsory restriction condition may include the aforementioned predetermined vehicle restriction condition. Furthermore, the mandatory restriction condition includes that the first number of empty container return tasks assigned to a delivery vehicle different from the associated package delivery task and present in the delivery plan candidate is smaller than the first threshold. If it is necessary to generate a new delivery plan candidate in violation of the mandatory restriction condition, insert the delivery task related to the violation of the mandatory restriction condition at another position in the current delivery plan candidate, or Exchange the delivery order with other delivery tasks in the candidate.

  In step 235, it is determined whether or not the search can be completed ahead of schedule. When it is determined to be possible, the process proceeds to step 240, but when it is determined to be impossible, the process returns to step 231. For example, the number of delivery vehicles required for the current delivery plan candidate is equal to or less than a predetermined first threshold value and / or is assigned to a delivery vehicle different from the associated package delivery task that is present in the delivery plan candidate and enters. If the number of container return tasks is equal to or less than the second predetermined threshold, the search can be terminated earlier.

  In step 240, one or a plurality of delivery plans are output in ascending order of the total cost of each currently acquired delivery plan candidate, and are set as a final delivery plan.

  5 to 7 show an example of a data format read in the data reading 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 that can support the base (that is, a vehicle type that can receive delivery at the base) 415. And parameters such as start time 416 and end time 417 of the base, and required unloading time 418.

  The vehicle management data 1066 in FIG. 6 includes a vehicle ID 431 for uniquely identifying a vehicle, a vehicle type 432 of the vehicle, a driver and a communication method 433, a base 434 at the time of departure of the vehicle, and a base 435 at the end of the vehicle. The vehicle volume upper limit 436 (cubic meters / number of pallets (baggage carriers), etc.), vehicle loading upper limit 437 (t or kg, etc.), vehicle operation start time 438, and vehicle end time 439. , And the parameters such as the jurisdiction 440 of the vehicle.

  The delivery task data 1067 in FIG. 7 includes a delivery date 451 of the delivery task, a departure base 452 of the delivery source, a destination base 453 of the delivery destination, a pickup deadline 454 for acquiring the package at the delivery source, and a delivery destination. , Delivery baggage volume 456, vehicle type 458 when there is a limit to the types of vehicles that can be delivered, necessity of returning empty containers 459, and availability 460 of mixing with other delivery tasks. Including.

  In the calculation condition setting step 220, the input data 500 shown in FIG. 8 is generated using the base management and delivery task data. From the delivery task data 1067 shown in FIG. 7, the return of empty containers cannot be directly reflected in the plan by the calculation process of the delivery plan generation algorithm. Therefore, prior to the main calculation process step 230, the calculation condition setting step 220 shown in FIG. Generate empty container return task by processing.

  As shown in FIG. 9, in the calculation condition setting step 220, an operation loop process is performed on all delivery tasks waiting for delivery provided by the user. In step 221, it is determined whether traversal of all delivery tasks has been completed. When the traverse is completed, input data as shown in FIG. 8 is output. When the traverse is not completed, one unprocessed delivery task i is selected in step 222, and in step 223, the delivery task i is assigned to the unprocessed delivery task i. On the other hand, it is determined whether the empty container needs to be returned. If unnecessary, the process returns to step 221. If necessary, in step 224, an empty container return task j is added to the delivery task i to generate the task, and in step 225, it is determined whether the empty container return task j can be mixed. For the determination of the necessity of returning the empty container for the delivery task i, refer to the setting of the necessity of returning the empty container 459 for the task in FIG. If return is required, add empty container return task.

  Taking the delivery task data 461 in FIG. 7 as an example, since the empty container return 459 is “necessary”, 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 of FIG. 8 in order to correspond to the original delivery task J001. Here, the task order 519 indicates the order relationship between the current task and the related task ID 520. For example, NEXT 541 indicates that the current task J001_01 is located after the task J001 indicated by the related task ID 520.

  In step 225, when judging whether or not mixed loading is possible for the empty container return task j, the mixed loading possibility 521 in FIG. 8 is set with reference to the mixed loading possibility 460 in FIG. That is, in the mixed loading availability determination process 225 of FIG. 9, if the original delivery is not mixed loading, the empty container return is also not mixed loading. Of course, embodiments of the present invention may use an asymmetric processing scheme, i.e., the original delivery may not be mixed and the empty container return may be mixed.

  In the task assignment process of the delivery plan generation algorithm, a non-mixable empty container return task is not mixed with other tasks, so a capacity different from the volume V and weight W is introduced and added to the delivery task. The mixed capacity is M. In the example of FIG. 9, the upper limit value of the mixed capacity of all vehicles is set to 1.0, and the mixed capacity of the empty container return task i that cannot be mixed is set to 1.0 in step 226. As a result, when the mixed loading capacity of the delivery task is 1.0, the capacity becomes full. At this time, even if there is a margin in the volume V and the weight W, it is not possible to mix loading with other tasks.

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

  Finally, the original delivery task and the empty container return task are supplemented during the vacant time period between the pick-up time limit 454 and the delivery time limit 455 in FIG. If there is no time in the deadline, the end time of the site may be input with reference to the site management data in FIG. Further, for example, since the time is basically not specified in the empty container return task, the business hours of the base may be all input. If the business hours of each base are not specified, the default value (for example, 8:00 to 17:00) is specified. Therefore, the input data shown in FIG. 8 is obtained. FIG. 8 shows an example of the mixed capacity setting processing after the input data is determined and before the main calculation processing step 230. Of course, the input data itself may include the mixed capacity.

  The process of adding an empty container return task in FIG. 9 is a case where it is necessary to return an empty container after delivery. As another case, before delivery of a task, it is necessary to pick up an empty container from another location different from the departure location of the delivery task (Pickup), which is the same as the case of the delivery task 462 in FIG. Correspondingly, one processing method is shown in FIG. In the case of the delivery task 462 in FIG. 7, the necessity of returning an empty container 459 is “necessary in advance”. More specifically, first, the empty container is picked up at the delivery destination base B, then the baggage is loaded again at the base C and the baggage 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, a calculation loop process is performed on all the delivery tasks waiting for delivery provided by the user, and it is determined whether or not the empty container pickup task needs to be added. . In step 221a, it is determined whether the traversal of the empty container pickup process has been completed for all the delivery tasks. If the traverse has been completed, the process proceeds to step 221 in FIG. 9, and it is determined whether the traverse of the empty container return process has been completed for all the delivery tasks. If the traversal of the empty container pick-up process has not been completed, one unprocessed delivery task is selected as the current delivery task in step 222a, and in step 223a, the current delivery task is transferred from another location to the empty container. Determine if collection is required. If it is determined that it is necessary, an empty container collection task is added to the current task in step 224a, and the process returns to step 221a. Specifically, when an empty container pickup task is added, the related parameters in the task may be set with reference to a similar method in the empty container return task.

  Based on the delivery task 462 in FIG. 7, an empty container pickup task J002 and an empty container return task J002_02 are generated for the delivery task in FIG. 7, respectively. Here, in order to carry out empty container collection, package delivery, and empty container return, the task ID of the task performed before that is set for the related task IDs of J002_01 and J002_02. In the actual delivery, there is no need to return the empty container to the base l after the delivery, and the scene ends when the empty container is delivered to the destination base B, or the empty container is picked up at another base other than the delivery destination base B. There are scenes and the like. What is necessary is just to adaptively change the above various possible scenes according to business requirements and output appropriate input data 500. In this example, a scene in which input data 500 is generated based on the delivery task 1067 by the calculation condition setting step 220 is shown. However, in a specific implementation, the input data 500 may be directly input without performing the calculation condition setting step 220. That is, by directly inputting the task order 519 and the related task ID 520, the relation between a plurality of tasks such as the empty container return task may be defined.

  FIG. 11 shows an example of the data format of the inter-site distance matrix data 1052 required for the main operation 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 traveling route reciprocating between the two bases may be different, if the number of bases is N, the number of all distances is N * (N-1). Using the road vector data as input, the distance between two bases is obtained by a program using the shortest route calculation method (for example, the Dijkstra method). The data 1052 is generated by using the site management data 1065 prior to the main arithmetic processing step 230, or the generated data is input and read into the input / output / calculation execution processing means 1051 of the main storage device. In addition, high-speed arithmetic processing can be directly performed.

  The parameters such as the mixed capacity set in FIG. 9 are used in the compulsory restriction condition violation processing step 233 in the main calculation processing step 230. Here, the compulsory restriction condition may be set with reference to the above-mentioned predetermined vehicle restriction condition, and the total load of the vehicle does not exceed the upper limit of the volume of the vehicle, or the total load of the vehicle is This includes not exceeding the upper limit of the load of the vehicle, or the vehicle does not violate the setting condition of the delivery task that the load cannot be mixed. Violating any one of the above conditions indicates that the compulsory restriction condition is violated.

  FIG. 12 shows an example of an empty container mixed loading availability determination process. With respect to the delivery plan candidate output from the delivery plan candidate generation 232, the vehicles assigned to each delivery task are checked one by one (step 2331), and the vehicle capacity exceeds the upper limit (step 2332) or the cargo upper limit is exceeded. (Step 2333) When the mixed capacity exceeds the upper limit (Step 2334), it is determined that the mandatory restriction condition has been violated (Step 2336), and the process returns to the delivery plan candidate generation 232 again. In the opposite case, it is determined that the compulsory restriction condition is satisfied (step 2335), and the process proceeds to the total cost calculation step 234. Of course, in the embodiment of the present invention, the above-described determination 233 of the forced restriction condition violation may be performed in the delivery plan candidate generation 232.

  Specifically, in the case of the output data 550 in FIG. 15 as an example, the total volume is obtained by adding the increase / decrease 570 of the volume according to the time series order 564 to all the vehicles assigned by the current delivery plan candidate. When the state 565 is moving, the total volume and the total weight are equal to the upper limit value of the volume V and the upper limit value of the weight W (362, 363). Is determined. Similarly, it is determined whether the mixed capacity M exceeds the upper limit of the mixed capacity. Also, if the mixed capacity is set to 0 in the processing step 227 of FIG. 9, even if there is a case where the mixed capacity is 1 in the determination of the step 2334, the current vehicle can be mixed, so that the mixed capacity is possible. The mixed capacity of the vehicle is set to a small positive number less than or equal to 1 (for example, 0.001). In FIG. 12, the timing of returning to the delivery plan candidate generation step 232 is when a certain parameter of the vehicle violates the corresponding mandatory restriction condition or when a certain number of vehicles violate the corresponding mandatory restriction condition. It is at the time when the determination for all vehicles in the delivery plan candidate is completed.

  One embodiment of the processing flow of the 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 the total total cost in the operation loop processing. First, it is determined in step 23401 whether all delivery tasks have been processed. If the processing has been completed, the total cost is output, and the process proceeds to step 235. If not, one unprocessed delivery task is extracted and set as the current delivery task. In step 23402, it is determined whether the current delivery task is an empty container return task. In the example of FIG. 8, whether or not the task is an empty container return task can be determined by specifying that the task order 519 is NEXT and by specifying a task ID corresponding to the related task ID 520.

  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, and the delivery task (hereinafter, the original task) related to the empty container return task is performed. Distribution task) is assigned to the same vehicle. Specifically, in the data format of the output data 550 described later, it can be determined whether or not the two corresponding delivery tasks belong to the same vehicle ID 562 to determine whether the two delivery tasks are the same vehicle. If they are not the same vehicle, it is determined that there is no optimal solution (far from the optimal solution), and a preset cost α is added to the total cost (step 23404), and the process returns to step 23401. If the vehicle is the same, it is close to the optimal solution, so α is subtracted from the total cost or another set value (for example, 30% of α) is subtracted (step 23405). Here, since addition or subtraction of α from the total cost is performed on the total cost, if the vehicles are not the same, only one of them may be performed. After the same vehicle determination processing, the process proceeds to step 23406, where it is determined whether the empty container return task is executed after the original task. In the data format of the output data 550, the order of the delivery tasks can be determined by the order 564 of the same vehicle ID 562. The determination of the order before and after is determined based on whether there is a load of the return task after unloading of the corresponding original delivery task. In the determination, another delivery task may be provided between the unloading and the loading, and the time may be vacant. When the empty container return task is executed before the original task, β is added to the total cost (step 23407) because the solution is far from the optimal solution, and the process returns to step 23401. When the empty container return task is executed after the original task, β is subtracted from the total cost in the same manner as the above determination (step 23408). Lastly, in step 23409, it is determined whether the empty container return task and the related package delivery task are executed within the predetermined time, and the empty container return task and the package delivery task corresponding to the empty container return task are determined. It is determined whether there is no other delivery task in between and the empty container return task is executed immediately after the package delivery task corresponding to the empty container return task. Specifically, in determining whether the empty container return task is executed immediately after the corresponding package delivery task, the determination can be made based on whether the empty container return task is loaded immediately after unloading of the corresponding package delivery task. If there is another delivery task between the two, γ is added to the total cost (step 23410), and the process returns to step 23401. In the opposite case, γ is subtracted from the total cost (step 23411), and the process returns to step 23401.

  In the three determination processes 23403, 23406, and 23409, constants α, β, and γ determined in advance are numerical values of costs, and different costs are set in a method of gradually approaching the optimal solution in the optimal solution search process. (Α >> β >> γ is preferred). Therefore, in the main operation processing step 230, the assignment of the original task to the same vehicle and the empty container return task are performed with priority. Next, the context of the delivery task and the empty container return task can be realized. Finally, consider a delivery order in which there is no other delivery task between the two. Here, the determination processes 23406 to 23408 relating to the cost β are processes for quickly and surely converging to the optimal solution.

  If the number of delivery tasks is relatively large, it may be difficult to converge to the optimal solution with only the total cost calculation 234, and there may be a delivery order mismatch in the delivery plan. Here, the order mismatch indicates that the baggage delivery task related to the empty container return task is assigned to a different delivery vehicle. In this case, in the embodiment of the present invention, the convergence is improved in combination with the above-described order mismatch determination processing, and the delivery order mismatch is reduced or set to zero. FIG. 14 shows an example of combination with the above-described order mismatch determination processing. Here, it is determined whether there is an order mismatch with respect to the delivery plan candidate output in the delivery plan candidate generation step 232. If there is, the process returns to the step of generating the delivery plan candidate 232, and the order mismatch determination processing is performed in the generation of the delivery plan candidate 232.

  Specifically, first, after obtaining one delivery plan candidate in the delivery plan candidate generation step 232, the delivery plan candidate is set as the current delivery plan candidate. First, in step 2321, it is determined whether the traverse has been completed for all delivery tasks of the current delivery plan candidate. If it has been processed, the process proceeds to step 233. If not, in step 2322, one unprocessed delivery task is extracted and set as the current delivery task. In step 2323, it is determined whether 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, the process returns to step 2321. In the opposite case, the process proceeds to step 2324, and it is determined whether a delivery task related to the empty container return task (hereinafter, referred to as an original delivery task) is assigned to the same vehicle. If it is to be assigned to the same vehicle, the process returns to step 2321. In the opposite case, the process proceeds to step 2325, where the result of the determination of the order mismatch is output, and the process returns to the delivery plan candidate generation step 232 to generate another delivery plan candidate. The timing of returning to the delivery plan candidate generation step 232 is when a delivery task with an out-of-order mismatch is found, after traversal processing of all delivery tasks in the current delivery plan candidate is completed, or when a delivery task with an out-of-order May have reached a predetermined number. Since the above processing has been performed, there is no order mismatch in the delivery plan candidates output thereafter. Therefore, in the total cost calculation of FIG. 13, steps 23403, 23404, and 23405 of FIG. 13 may be omitted.

  In the delivery plan candidate generation step, a certain number or more of delivery tasks whose delivery order does not match may exist in the delivery plan candidates acquired after the execution of a certain number of operation loops. The processing may be terminated earlier, or the range of the input delivery task data may be reduced so that the data may be divided into several parts and the calculation loop processing may be executed again.

  In the division of the input data, for example, the delivery task in which the order mismatch occurs and all the delivery tasks related thereto are grouped into one group, and the remaining delivery tasks are grouped into another group. Then, a delivery plan candidate generation process is performed for each group.

  When generating a delivery plan candidate for the group acquired in the first two divisions, if there is no delivery order mismatch in each group, the delivery sub-plans of each group are put together to obtain an overall delivery plan candidate. For example, when acquiring the delivery sub-plans of 5 and 7 delivery vehicles for the two divided groups, a delivery plan candidate for performing delivery processing by a total of 12 units is acquired and output. On the other hand, if the delivery order mismatch occurs again in a certain group, the group may be divided into two by the above method. The above two-partitioning process may be performed a plurality of times until the delivery order mismatch does not occur in 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. The output delivery plan is not limited to one, and the calculation result can be selected based on a plurality of elements. For example, an appropriate delivery plan is selected and output from one or more of a plurality of factors such as the total travel distance, the total delivery time, the number of vehicles, the number of unassigned delivery tasks, and the number of out-of-order delivery tasks. It can be output in the form of data 550. In the output data 550, the operating status 565 of each delivery vehicle (vehicle ID 562) on the delivery date 561 is output according to the chronological order 564, and the output content includes the vehicle type 563, the departure base / destination base (566) during traveling. / 567), the start / end time of the operating state 565 (568, 569), the increase / decrease in volume / weight (570, 571) according to the operating state 565 up to that time, and the delivery task ID 572 for loading / unloading. Since one delivery task ID usually includes a load and an unloading, two different operating states are generated.

  16A and 16B show an example of the output screen generated based on the output data 550 in the delivery plan candidate 240. FIG. 16A is a delivery schedule table 600 showing the operating state of each delivery vehicle in a time series in a Gantt chart format, and FIG. 16B is a delivery route 700 showing a delivery base and a delivery route included in the delivery plan on a map. Here, an output in which 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 as the vertical axis, and the specific operating state is displayed on the right side in chronological order (order 564). The output data 550 outputs a total of eight operating states of loading, moving, waiting, unloading, loading, lunch break, moving, and unloading. In the delivery schedule table 600, the base 1, the transfer, the standby, the base A, the lunch break, A total of 7 states of movement and base 1 are shown. This is because the two operating states of unloading / loading are indicated using “base A” on the display.

  The delivery schedule table 600 and the delivery route 700 can correspond to each other. For example, in the delivery route 700, only the designated vehicle on the screen of the delivery schedule table 600 is displayed. In the delivery schedule table 600, when the specific time 661 is designated on the time axis which is the horizontal axis, the delivery route 700 A planned position 731 is shown. When the operation state of the vehicle is “moving”, in order to determine the vehicle position 731 on the map, when the moving speed is constant, the route between the destination and the departure place is subdivided, and The point at which the time has been reached may be set as the display position. 16A and 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 with reference to the block diagram of FIG. FIG. 17 shows a scene in which the structure of the computer 100 of FIG. 3 is disassembled into a server / client and the structure of one server 172 and a plurality of clients 171 and 173 is an example. The server 172 and the client 171 have basically the same hardware structure as the computer 100 of 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 an inter-base distance data module 17232. The secondary storage device 1724 includes a calculation condition setting processing module 17241, a base management data module 17242, an optimal 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 performs the arithmetic processing and output processing shown in FIG. 4 in cooperation with the remote client 171 via the network 175 (intranet or Internet).

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

  After that, the input data 500 is generated by the calculation condition setting processing 17241 or, as shown in FIG. 18, the base management data 17242 is acquired via the API 1727 by reading the data by the API 1727 of the server 172 as the data input processing 17141. Is generated. That is, this corresponds to executing a part of the calculation condition setting process 17241 by the data input process 17141. At this time, after the input of the data 500, the setting of the possibility of mixed loading may be performed only by 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. The road vector data 17245 may be collected from an external map information providing service system 176 such as the Internet via the NIC 1726 in an on-demand manner.

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

  The invention is implemented by means of electronic hardware, or a combination of computer software and electronic hardware, in conjunction with each exemplary means and algorithm steps described in the embodiments disclosed herein. This can be recognized by those skilled in the art. Whether these functions are performed in a hardware or software manner depends on the particular application of the technical means and design constraints. Those skilled in the art may implement the described functionality in different ways for each particular application, but these implementations are not considered to be beyond the scope of the present invention.

  For the sake of convenience and brevity of the description, it will be apparent to those skilled in the art that reference can be made to the corresponding steps of the above-described method embodiments for the specific working steps of the systems, devices and means described above. Here, it is not described repeatedly.

  It should be understood that in the embodiments according to the present application, the disclosed apparatus and method can be implemented in other manners. For example, the apparatus embodiments described above are merely exemplary. For example, the division of the means is merely a division of a logical function, and there may be another division system 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, the coupling or direct coupling or communication connection between the components shown and discussed herein is through an interface, and the indirect coupling or communication connection of the devices or means is an electrical connection, a mechanical connection or other forms.

  Means described as separate components may or may not be physically separated, and members designated 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 the means are selected according to actual needs to achieve the objects of the embodiments of the present invention.

  Further, each functional unit in each embodiment of the present invention may be integrated into one processing unit, or each unit may physically exist individually, and two or more units may be one unit. May be integrated.

  When the above functions are realized in the form of software function means and sold and used as an independent product, they can be stored in one computer-readable storage medium. Based on this understanding, the technical means of the present invention may be substantially, or a part contributing to the prior art, or a part of the technical means, may be in the form of a software product. The computer software product is stored on a single storage medium and includes several instructions on a single computer device (such as a personal computer, a server, or a network device) including all of the methods described in the embodiments of the present invention. Or let them perform some steps. The storage medium includes a medium capable of storing various program codes, such as a U disk, a removable hard disk, a ROM, a RAM, a magnetic disk, or an optical disk.

  The above description is only specific embodiments of the present invention, and the scope of protection of the present invention is not limited thereto. Any modification or replacement readily figured out by a person skilled in the art within the scope of the present invention is covered by the protection scope of the present invention. Therefore, the protection scope of the present invention is based on the protection scope according to the claims.

Claims (13)

A delivery plan generation method,
If the computer has one or more delivery tasks associated with information that requires empty container return among delivery tasks represented by 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 the
A computer assigns the plurality of delivery tasks and the generated empty container return task to the plurality of delivery vehicles represented by the vehicle management data including information on a plurality of delivery vehicles by a predetermined delivery plan generation algorithm. Creating a suggestion;
Computer, in the delivery plan candidate, the delivery tasks and with the free container returning tasks associated with it, whether assigned to the same delivery vehicle included in the plurality of delivery vehicles, and the empty vessel return task is executed after the delivery tasks with associated, based on whether those tasks are executed within a predetermined time, the step of evaluating the delivery plan candidates,
Computer, the delivery plan based on the evaluation of candidate delivery plan generating method characterized by comprising the steps of outputting a distribution delivery plan to one or more delivery plan candidates, a. The method of claim 1, wherein
The step of evaluating the delivery plan candidate includes:
Whether the delivery task and the associated empty container return task are assigned to the same delivery vehicle, and whether the empty container return task is executed after the associated delivery task, and and it but that on the basis of whether or not executed within a predetermined time, providing different tasks cost of each size emptied-out container returning task,
Delivery plan generation method characterized by comprising the method comprising the evaluation results of the total cost of the delivery plan candidates of the delivery plan the delivery plan candidate tasks cost obtained by the sum of the candidate. The method of claim 1, wherein
Determining a number of the delivery plan candidates present in,-out empty delivery task is assigned to a delivery vehicle that is different from the delivery vehicle assigned to a free container returning tasks associated container returning task,
If the number exceeds a preset threshold , adjust the delivery order of such empty container return tasks , or the delivery order of the delivery tasks associated with such empty container return tasks , or delivery plan generation method characterized by including the step of excluding a plan candidates. The method of claim 1, wherein
A step delivery vehicle to a preset delivery volume used for determination of mixed whether, and, where used in the mixed possibility determination to delivery tasks, sets the embedded capacitor having an upper limit in advance,
Delivery plan generation method characterized by including the step of setting the mixed volume delivery task mixed not the upper limit of the mixed volume. The method of claim 4, wherein
After generating the single delivery plan candidates, comprising the steps of delivery vehicle more than mixed capacity it is determined whether or not present in the delivery plan candidates,
When the delivery vehicle exceeding the mixed volume is present in the delivery plan candidate, the transmission order of such delivery tasks, or to adjust the transmission order of free container returning tasks associated with such delivery tasks, or, delivery plan generation method characterized by including the step of excluding the delivery plan candidate. The method of claim 5, wherein
After generating the single delivery plan candidates, in the step of delivery vehicle more than mixed capacity it is determined whether or not present in the delivery schedule candidate
Against delivery vehicles of the delivery plan candidate, the delivery vehicle to determine a route between adjacent bases via, Accumulates mixed capacity of all shipping tasks in the route of the delivery vehicle, the upper limit value of the embedded capacitance If so, determining that there is a delivery vehicle that exceeds the combined capacity;
Or
The relative path between adjacent bases of the delivery plan candidates, to determine the one or more delivery vehicles via the route, the mixed volume of all shipping tasks in the path of each delivery vehicles accumulates respectively, wherein A method for generating a delivery plan , comprising determining that there is a delivery vehicle exceeding the mixed capacity when the mixed capacity is equal to or more than the upper limit value of the mixed capacity. The method of claim 1, wherein
Prior to generating the delivery plan candidate, further,
For all delivery tasks, delivery plan generation method distributes a single task label ID that uniquely labeled the delivery tasks, characterized by comprising the steps of: providing a binding relationship to the associated delivery tasks. The method of claim 1, wherein
Based on a predetermined delivery plan generation algorithm, in the process of repeating the generation of the delivery plan candidates up to the preset search count upper limit, in the delivery plan candidates obtained when the number of generations reaches the preset number, If the number of empty-out container returning tasks assigned delivery vehicle and different delivery vehicles the delivery task free container returning tasks associated assigned exceeds a predetermined value, further,
Delivery task in the original task group initial value is assigned waiting delivery tasks, empty container returning task-out air and assigned to a different delivery vehicle delivery vehicles is assigned delivery tasks associated container returning task and a first task group consisting of a delivery task free container returning tasks associated, comprising the steps of Ru divided two groups with a second task group consisting of other tasks,
Based on a predetermined delivery plan generation algorithm, a delivery sub-plan candidate is generated for each of the first task group and the second task group, and the first delivery sub-plan candidate and the second delivery sub-plan candidate are generated. the method comprising the steps of: obtaining,
During the first delivery sub-plan candidates, the vacant container returning task is different from the delivery vehicles that are assigned delivery tasks associated delivery vehicle assigned to air-out container returning task exists, the first task group was said original task group, the steps returns to the step of separating the delivery task in the original task group into two groups,
During the first delivery sub-plan candidate, when the free container returning task is being delivered task is assigned and delivery vehicles with different shipping empty assigned-out in the vehicle container returning task not exist associated said first Summary delivery subplan candidates and all of the second delivery sub-plan candidates, delivery plan generation method characterized by comprising the steps of obtaining a delivery plan candidate delivery task of the allocation wait. 3. The method according to claim 2, wherein
Delivery plan generation evaluating the delivery schedule candidate, characterized in that further the total delivery distance cost distribution transmission task in the total cost and delivery schedule candidate calculates the evaluation result of the delivery plan candidate How . 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 that requires empty container return, each of the one or more delivery tasks is associated with the delivery task. Generate information about the empty container return task,
By a predetermined delivery plan generation algorithm, create a delivery plan candidate to assign the plurality of delivery tasks and the generated empty container return task to the plurality of delivery vehicles represented by the vehicle management data,
In the delivery plan candidate, whether the delivery task and the empty container return task associated therewith are assigned to the same delivery vehicle included in the plurality of delivery vehicles , and the empty container return task It is executed after the delivery tasks with associated, based on whether those tasks are executed within a predetermined time, and evaluate the delivery plan candidates,
On the basis of the assessment of the delivery plan candidates, and outputs a feed distribution of one or more delivery plan candidates planning, characterized in that it comprises a processor, a delivery plan generator. The device according to claim 10,
Evaluating the delivery plan candidate includes:
Whether the delivery task and the associated empty container return task are assigned to the same delivery vehicle, and whether the empty container return task is executed after the associated delivery task, and Is performed within a predetermined time, based on whether the empty container return task has different task costs of different sizes,
A delivery plan generation device, wherein the total cost of the delivery plan candidate obtained by summing up the task costs of the delivery plan candidate is used as an evaluation result of the delivery plan candidate. The device according to claim 10,
The processor comprises:
The number of empty container return tasks assigned to a delivery vehicle different from the delivery vehicle to which the delivery task associated with the empty container return task is present, which is present in the delivery plan candidate, is determined,
If the number exceeds a preset threshold, adjust the delivery order of such empty container return tasks, or the delivery order of the delivery tasks associated with such empty container return tasks, or Exclude planning ideas,
A delivery plan generation device characterized by the above-mentioned. When there is one or more delivery tasks associated with the information that requires empty container return among the delivery tasks represented by the delivery task data including information on a plurality of delivery tasks, for each of the one or more delivery tasks, Generating information about the empty container return task associated with the delivery task;
According to a predetermined delivery plan generation algorithm, a delivery plan candidate is created that allocates 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 a plurality of delivery vehicles. Steps to
In the delivery plan candidate, whether the delivery task and the empty container return task associated therewith are assigned to the same delivery vehicle included in the plurality of delivery vehicles, and the empty container return task Evaluating the delivery plan candidate based on whether or not those tasks are performed within a predetermined amount of time, performed after the delivery tasks associated therewith;
Outputting one or more delivery plan candidates as a delivery plan based on the evaluation of the delivery plan candidates.

Images