CN-116182860-B - Multi-vehicle path planning method, system, equipment and medium with boxing constraint

CN116182860BCN 116182860 BCN116182860 BCN 116182860BCN-116182860-B

Abstract

The invention provides a multi-vehicle path planning method, system, equipment and medium with a boxing constraint, comprising the following steps of S1, constructing a path planning main model; the method comprises the steps of S2, S3, writing a limited relaxation model based on a group of initial solutions, S4, writing a dual problem of the limited relaxation model, S5, constructing a submodel based on an optimal solution of the dual problem, S6, solving the submodel, S7, judging whether an optimal path exists according to the solution of the submodel, adding the optimal path into the limited relaxation model if the optimal path exists, updating the limited relaxation model, starting to enter a cycle from the step S4, ending the cycle if the optimal path does not exist, S8, obtaining a solution space R ′ according to the step, and solving the main model based on R ′ to obtain the solution of the path planning problem. The invention can combine boxing and path planning, meet the actual requirements of business and improve the application value of algorithm.

Inventors

ZHAO YANYING
WU BEI
ZHENG REN

Assignees

上海赛创机器人科技有限公司

Dates

Publication Date: 20260508
Application Date: 20221209

Claims (4)

1. A method of multiple vehicle path planning with vanning constraints, comprising: S1, constructing a path planning main model; s2, relaxing the main model into a relaxation model; step S3, writing a limited relaxation model based on a group of initial solutions, wherein the initial solutions are a group of path combinations, and one path can be represented by the site sequence visited by the vehicle; step S4, writing out the dual problem of the limited relaxation model; S5, constructing a sub model based on the optimal solution of the dual problem; step S6, solving the submodel; step S7, judging whether an optimal path exists according to the solution of the sub-model, if so, adding the optimal path into a limited relaxation model, updating the limited relaxation model, and starting to enter a cycle from the step S4; Step S8, obtaining a solution space according to the steps And is based on Solving the main model to obtain a solution of the path planning problem; setting a punishment cost for each path in path planning with boxing constraint, wherein if goods at all stations on the path can be completely loaded, the punishment cost is 0, otherwise, the punishment cost is an arbitrarily large positive number; The path planning master model is as follows: Wherein use is made of Representing a path; representing a set of all paths, decision variables Representing a path Whether or not to be selected, if Representing a path Is selected; Representing a path Is a boxing penalty cost; , Is an arbitrarily large positive number; representing a set of all stations to be served; Representing a site Whether or not to be on the path If yes, the value is 1, otherwise, the value is 0; Representing a path Is a distance of (2); The relaxation in the limited relaxation model in the step S4 is realized by relaxing the decision variable of the main model from 0-1 variable to a continuous variable with the value between 0 and 1, and the limitation is realized by that the solution set of the relaxation model is a subset of a real solution set, and the solution set is continuously changed along with the addition of new paths in the solving process; The dual problem is that the original problem is described by the method with the same meaning and symmetrical structure from different angles, each linear programming problem is provided with a dual problem corresponding to the problem, and the dual problem is as follows: Wherein use is made of Representing a path; representing a set of all paths; Representing a site Whether or not to be on the path If yes, the value is 1, otherwise, the value is 0; A dual variable that is a relaxation problem of the master model; Representing a path Is a distance of (2); Representing a path Is a boxing penalty cost; , Is an arbitrarily large positive number; representing a set of all stations to be served; the sub-model of the path planning is as follows: Wherein, the Representing a site Sum site A distance therebetween; representing a vanning penalty cost; A dual variable that is a relaxation problem of the master model; Representing a discharge bin; an upper limit representing the number of loading stations on a path; representing an upper load limit of the vehicle; Representing a site The total weight of the goods to be loaded; Representing a site Service order on the path; Indicating a station having been serviced Load of rear vehicle, decision variable Representing a site Whether or not to be selected; And continuously calling a boxing algorithm in the solving process of the step S6, wherein the boxing algorithm comprises the following steps: 1) Stacking Cheng Tuo all cargoes to be loaded at the stations to be served according to the sizes to obtain the sizes and the numbers of different trays; 2) Taking the bracket list as input, and boxing by using a skyline algorithm; 3) If the returned result indicates that the goods are loaded, then Otherwise , Is an arbitrarily large positive number; 4) Return to And planning the path to the sub model.
2. A multiple vehicle path planning system with vanning constraints, comprising: The model M1 is used for constructing a path planning main model; a model M2 for relaxing the main model into a relaxed model; model M3, writing out a limited relaxation model based on a set of initial solutions; Model M4, writing out the dual problem of the limited relaxation model; Model M5, constructing a sub-model based on the optimal solution of the dual problem; Model M6, solving the sub-model; the model M7 judges whether an optimal path exists according to the solution of the sub-model, if so, the optimal path is added into a limited relaxation model, the limited relaxation model is updated, and the circulation is started from the model M4; model M8 obtaining solution space according to the above steps And is based on Solving the main model to obtain a solution of the path planning problem; In the path planning with boxing constraint, setting a punishment cost for each path, wherein if goods of all stations on the path can be completely loaded, the punishment cost is 0, otherwise, the punishment cost is an arbitrarily large positive number; The path planning master model is as follows: Wherein use is made of Representing a path; representing a set of all paths, decision variables Representing a path Whether or not to be selected, if Representing a path Is selected; Representing a path Is a boxing penalty cost; , Is an arbitrarily large positive number; representing a set of all stations to be served; Representing a site Whether or not to be on the path If yes, the value is 1, otherwise, the value is 0; Representing a path Is a distance of (2); The relaxation in the limited relaxation model in the module M4 is realized by relaxing the decision variable of the main model from 0-1 variable to a continuous variable with the value between 0 and 1, and the limitation is realized by that the solution set of the relaxation model is a subset of a real solution set, and the solution set is changed continuously along with the addition of new paths in the solving process; The dual problem is that the original problem is described by the method with the same meaning and symmetrical structure from different angles, each linear programming problem is provided with a dual problem corresponding to the problem, and the dual problem is as follows: Wherein use is made of Representing a path; representing a set of all paths; Representing a site Whether or not to be on the path If yes, the value is 1, otherwise, the value is 0; A dual variable that is a relaxation problem of the master model; Representing a path Is a distance of (2); Representing a path Is a boxing penalty cost; , Is an arbitrarily large positive number; representing a set of all stations to be served; the sub-model of the path planning is as follows: Wherein, the Representing a site Sum site A distance therebetween; representing a vanning penalty cost; A dual variable that is a relaxation problem of the master model; Representing a discharge bin; an upper limit representing the number of loading stations on a path; representing an upper load limit of the vehicle; Representing a site The total weight of the goods to be loaded; Representing a site Service order on the path; Indicating a station having been serviced Load of rear vehicle, decision variable Representing a site Whether or not to be selected; and continuously calling a boxing algorithm in the solving process of the module M6, wherein the boxing algorithm comprises the following steps: 1) Stacking Cheng Tuo all cargoes to be loaded at the stations to be served according to the sizes to obtain the sizes and the numbers of different trays; 2) Taking the bracket list as input, and boxing by using a skyline algorithm; 3) If the returned result indicates that the goods are loaded, then Otherwise , Is an arbitrarily large positive number; 4) Return to And planning the path to the sub model.
3. An apparatus, the apparatus comprising: One or more processors; Storage means for storing one or more programs, The one or more programs, when executed by the one or more processors, cause the one or more processors to implement the steps of the method of claim 1.
4. A computer readable storage medium storing a computer program, which when executed by a processor implements the steps of the method of claim 1.

Description

Multi-vehicle path planning method, system, equipment and medium with boxing constraint Technical Field The invention relates to the technical field of algorithms for combining optimization problems, in particular to a multi-vehicle path planning problem with packing constraint based on a column generation algorithm, and particularly relates to a multi-vehicle path planning method, system, equipment and medium with packing constraint. Background In the current society, economy is rapidly developed, and the demand of logistics transportation and distribution by enterprises and institutions is increasing, so that the transportation of goods in sufficient quantity on time is required, and the logistics cost of transportation and distribution is required to be considered, including time, vehicle number, distance limitation and the like. How to make a vehicle path plan to get an optimal route is an important issue in the logistic field. The goal of considering the vehicle path planning problem is to design a set of feasible routes so that the cost can be reduced as much as possible while meeting customer needs. Typically, cost is positively correlated to distance travelled. Thus, the goal of modeling is typically to minimize the mileage. Meanwhile, the number of vehicles is limited, the load of the vehicles is limited, and considering the carpooling requirements of different stations, the loading rate of the vehicles needs to be improved as much as possible, so that the number of the vehicles is reduced, and the cost is reduced. Therefore, the problem of multi-vehicle path planning with boxing constraint is solved, and the cost reduction and synergy requirements of enterprises and public institutions can be effectively met. Aiming at the real problem, the boxing problem and the multi-vehicle path planning problem are NP-hard problems, and the problem is difficult to solve along with the expansion of the problem scale. For such large-scale problems, it is difficult to directly search for an accurate optimal solution, so a series of algorithms for searching for an approximate solution are developed, the speed of searching for an optimal solution is increased, and a better optimization effect is achieved when a complex large-scale NP problem is solved. In the solving algorithm of the boxing problem, an optimal boxing scheme can be quickly found by using a skyline algorithm. In the solving algorithm of the vehicle path planning problem, a column generating algorithm based on a simplex algorithm is an algorithm for efficiently solving a large-scale linear optimization problem. Although related algorithms applied to both the packing problem and the path planning problem have been widely studied, the vehicle path planning problem with packing constraints has not been well expanded and practiced. In actual logistics orders, the constraint condition of boxing is more complex under the condition of huge order quantity, and the quantity of stations is large, so that the optimal solution is very difficult to seek for vehicle path planning (VRP). In a conventional path planning problem, in order to simplify the problem, in the process of boxing, goods are often regarded as fluid parts, and loading is regarded as completed as long as the volume of the goods is ensured to be smaller than the capacity of a vehicle, so that after an optimal path planning scheme is obtained, actual loading is possibly not realized, and the scheme cannot be implemented. There is room for improvement and lifting in existing solutions. Aiming at the problem of multi-vehicle path planning with a large number of stations and packing constraint, the packing module based on the astronomical algorithm is placed in the optimization process of path planning, so that the optimal path is ensured, and meanwhile, the loading mode of cargoes is ensured to be feasible. Disclosure of Invention Aiming at the defects in the prior art, the invention provides a multi-vehicle path planning method, a system, equipment and a medium with a boxing constraint. The invention provides a multi-vehicle path planning method, a system, equipment and a medium with boxing constraint, wherein the scheme is as follows: in a first aspect, a method of multiple vehicle path planning with vanning constraints is provided, the method comprising: S1, constructing a path planning main model; s2, relaxing the main model into a relaxation model; step S3, writing a limited relaxation model based on a group of initial solutions, wherein the initial solutions are a group of path combinations, and one path can be represented by the site sequence visited by the vehicle; step S4, writing out the dual problem of the limited relaxation model; S5, constructing a sub model based on the optimal solution of the dual problem; step S6, solving the submodel; step S7, judging whether an optimal path exists according to the solution of the sub-model, if so, adding the optimal path into a limited relaxation mo