CN-122022101-A - Instant distribution task allocation method based on two-stage meta heuristic algorithm

CN122022101ACN 122022101 ACN122022101 ACN 122022101ACN-122022101-A

Abstract

The invention discloses an instant distribution task distribution method based on a two-stage meta-heuristic algorithm, which relates to the field of instant distribution and comprises the steps of constructing an order rider mixed utility matrix and generating a candidate edge set, calibrating utility parameters based on the mixed utility matrix, determining reference parameters, constructing an MCMF model through a dynamic TopK pruning and time-interval soft capacity constraint method to generate an MCMF initial solution, and obtaining a final distribution task distribution result through a two-stage multi-objective task distribution optimization method of NSGA-II and ALNS based on the MCMF initial solution. The invention displays comprehensiveness, flexibility, global searching capability and local optimizing capability, so that the dispatching algorithm effectively reduces uneven load among different riders while improving the overall dispatching utility, is beneficial to improving the platform capacity utilization rate and the rider satisfaction, and is suitable for solving the task allocation problem of large supply and demand fluctuation under a plurality of peak scenes in the whole day.

Inventors

SHI JINGLIN
NI ZHIWEI
LIU WENTAO
ZHU XUHUI
NI LIPING
CHEN RUOLIN
LONG XUEMEI
Zhao Qianxi

Assignees

合肥工业大学

Dates

Publication Date: 20260512
Application Date: 20260213

Claims (7)

1. The instant distribution task allocation method based on the two-stage meta-heuristic algorithm is characterized by comprising the following steps of: step 1, constructing an order rider mixed utility matrix and generating a candidate edge set; Step 2, calibrating utility parameters based on the mixed utility matrix, and determining reference parameters; Step 3, constructing an MCMF model according to the mixed utility matrix, the candidate edge set and the reference parameters by a dynamic TopK pruning and time-interval soft capacity constraint method, and generating an MCMF initial solution; and 4, obtaining a final distribution task distribution result through a two-stage multi-objective task distribution optimization method of NSGA-II and ALNS based on the MCMF initial solution.
2. The method for distributing instant distribution tasks based on two-stage meta-heuristic algorithm according to claim 1, wherein said step 1 specifically comprises: Step 1.1, constructing an order completion time prediction model according to positions of a rider, a merchant point and a receiving point and waiting business constraint; Step 1.2, constructing a mixed utility function based on order promise delivery time; step 1.3, generating a candidate edge list through KDTree space-time filtration based on the business circle soft neighborhood; Step 1.4, carrying out de-duplication and writing into a mixed utility matrix on the candidate edge list, simultaneously counting the index of the number of riders of each candidate of the order candidate degree and outputting a merging log; And 1.5, performing TopK pruning and K=150 recursion on the mixed utility matrix to obtain the candidate edge set.
3. The method for distributing instant distribution tasks based on two-stage meta-heuristic algorithm according to claim 2, wherein the order completion time prediction model is expressed as: ; ; ; Wherein, the Representing two points of a sphere The distance between the two adjacent substrates is determined, And For a corresponding latitude to be considered, Representing the latitude distance between the points a and b, i.e , Representing the longitude distance of points a and b, i.e R=6371000 meters; Indicating the length of travel from the rider position to the merchant, Indicating the effective position of the rider, Representing the point of the merchant, Indicating the length of time for delivery from the merchant to the point of receipt, The point of receipt is indicated as being the point of receipt, Representing rider speed; the time of taking the meal is indicated, The order push time is indicated as such, The time when the preparation of the meal is completed is indicated, Representing the order completion time; The mixed utility function represents: ; ; ; ; Wherein, the 、 And Respectively representing the completion utility, quasi-punctual utility and time-efficient utility, Respectively, the corresponding weight parameters are represented, Representing the mixed utility; representing the scale of the quasi-punctual decay, Indicating the coefficient of the time-dependent attenuation, Indicating the order promise delivery time.
4. The method for distributing instant distribution tasks based on two-stage meta-heuristic algorithm according to claim 1, wherein said step 2 specifically comprises: Step 2.1, constructing a calibration order subset based on the full order detail set; 2.2, constructing a parameter grid set by taking the standard of the quasi-punctuality punishment scale parameter and the standard of the aging attenuation parameter as the center; Step 2.3, rapidly recalculating the mixed utility of each group of parameters in the parameter grid set based on power transformation; Step 2.4, adopting a simplified MCMF equivalent distribution method of argmax to evaluate the coverage rate and average mixing utility of each group of parameters in the parameter grid set; Step 2.5, evaluating the service index CTD and the comprehensive evaluation index of each group of parameters in the parameter grid set by utilizing the order time and the expected delivery time in the calibration order sheet set ; And 2.6, calculating a normalized comprehensive evaluation index and selecting a reference parameter.
5. The method for distributing instant distribution tasks based on two-stage meta-heuristic algorithm according to claim 4, wherein said step 2.3 specifically comprises: In subset with the calibration order Corresponding hybrid utility matrix On, to And (3) with The power transformation is adopted to realize parameter migration, and the formula is as follows: ; Wherein, the Representing parameters The corresponding time-efficient utility is that, Indicating the coefficient of the time-dependent attenuation, , Representing parameters The corresponding quasi-punctual utility is that, Representing the quasi-punctual penalty scale parameter, Second, wherein the second is; For each set of parameters The mixing utility is calculated by the formula: ; Wherein, the Representing parameters The corresponding mixing utility is that, The utility of the completion is indicated as such, Respectively representing corresponding weight parameters; The step 2.4 specifically includes: for each order Direct selection of candidate riders with greatest mixed utility Obtaining an allocation set The formula is: ; each set of parameters Output of the distribution result of (2) and record the coverage rate Mixing utility with average The formula is: ; Wherein, the Representing a set of matching pairs of order-rider, Expressed in parameters The number of matching pairs obtained in the following, Representing the size of the subset of orders for the calibration parameters.
6. The method for distributing instant distribution tasks based on two-stage meta-heuristic algorithm according to claim 1, wherein said step 3 specifically comprises: step 3.1, data input and symbol unification are carried out according to the mixed utility matrix, the candidate edge set and the reference parameters; step 3.2, constructing a dynamic window, calculating the window peak ratio, mapping a dynamic TopK threshold according to the window peak ratio, and calculating the off-peak capacity ratio; Step 3.3, screening input data through a dynamic TopK pruning and K=150 rollback mechanism; Step 3.4, dividing the rider set into time-period capacity according to the off-peak capacity proportion, and setting a soft upper limit and a total daily gate; step 3.5, introducing a fairness penalty term into the side weight according to the segmentation load rate; Step 3.6, performing MCMF modeling and solving based on the data screened in the step 3.3, the capacity division, the soft upper limit and the total gate in the whole day in the step 3.4, and the fairness penalty term; Step 3.7, submitting the commit through horizons rolling according to the solving result of the MCMF, and updating the rider state; and 3.8, carrying out result derivation calculation and interpretable output on the result submitted in the step 3.7, and finally obtaining the initial allocation result.
7. The method for distributing instant distribution tasks based on two-stage meta-heuristic algorithm according to claim 1, wherein said step 4 specifically comprises: step 4.1, determining decision variables and constraint conditions of the multi-objective optimization model; step 4.2, determining an objective function of the multi-objective optimization model; Step 4.3, carrying out population initialization by taking the MCMF initial solution as an anchor point, and carrying out NSGA-II global multi-target search oriented to a large-scale feasible domain; and 4.4, extracting Pareto elite solution from the output population in the step 4.3, and carrying out ALNS local search to obtain a final distribution result.

Description

Instant distribution task allocation method based on two-stage meta heuristic algorithm Technical Field The invention relates to the field of instant distribution, in particular to an instant distribution task distribution method based on a two-stage meta-heuristic algorithm. Background The instant distribution task allocation can be generally abstracted into matching optimization of 'order set-rider set', wherein orders are used as demand nodes, riders are used as resource nodes, feasible connection edges are formed between the two by the conditions of space distance, store time, promised delivery time limit, business circle limit, rider capacity and the like, and benefits or costs are defined on the connection edges. The instant distribution task distribution process is generally that firstly, batch (such as window or rolling period) processing is carried out on orders on a time axis, secondly, candidate edges of the orders and the riders are constructed, the edge weights are calculated, a solver is called to obtain distribution results, and finally, the results are output and the rider state is updated to enter the next batch. However, the prior art still has a significant limitation in the large-scale instant distribution task distribution scene, and the reasons for the limitation are mainly due to the complexity of the problem structure and the multi-objective conflict (1) the candidate edge explosion causes uncontrollable calculation. In a real service, the number of orders and the number of riders are large, and if a full-scale 'order multiplied by the number of riders' utility matrix is directly constructed, the number of edges is increased in product level, so that the memory occupation and the solving scale are rapidly beyond the bearable range. Even if a network flow or a matching algorithm is adopted, the time and space complexity of the network flow or the matching algorithm can be amplified by the scale of the candidate edges, and the engineering problem of 'model building but not solvable' or 'slow' occurs. The root cause is that the feasible connection edges are commonly determined by a plurality of factors such as geographic proximity, time accessibility, business district limitation, rider status and the like, and the factors change with time, so that the candidate set is not stable and is difficult to fix. (2) Single-objective solutions have difficulty expressing platform real preferences, and multi-objective constraints are easily "marginalized". A few accurate optimization methods tend to favor a single index on the goal (e.g., total cost or total utility maximization), fairness, peak coverage, overload penalty, etc. tend to be achieved by additional constraints or post-processing. However, in the case of shortage of resources in peak hours, a single target naturally tends to enable a few high-efficiency riders to accept more orders, so that the problems of high concentration of load, idle tail riders, fluctuation of service experience and the like are caused. The method is characterized in that natural conflict exists between fairness and total effectiveness, once fairness constraint is set too hard, the feasible region is easy to shrink sharply, coverage rate is easy to drop, and the phenomenon that a model is written but a result is not controlled is caused when the fairness constraint is set too soft and the constraint function is difficult to play. (3) The peak/off-peak period hybrid modeling results in "local optimality" and "period crowding. Many online or windowed methods process orders in fixed windows and solve or partially greedy decisions independently within each window. This configuration presents a typical problem in that the front window consumes more premium rider capacity to boost local metrics, resulting in insufficient rear window (especially peak tail) available capacity, coverage dips or large orders can only be distributed to remote riders. The reason is that the time distribution of the order stream is uneven in height, the fixed window cannot adapt to peak-to-valley change, meanwhile, the capacity of the rider belongs to cross-window shared resources, and if a uniform constraint mechanism of 'cross-window budget/soft capacity' is lacking, unreasonable consumption of resources on a time axis can be generated. (4) The pure element heuristic method is highly sensitive to the primary solution quality and parameters, and has insufficient stability and reproducibility. Although the GA/NSGA-II/ALNS method can explore better solutions under complex constraint, two problems often occur in engineering, namely firstly, if the initial solution is poor or the quality of candidate edges is insufficient, the searching is difficult to enter a high-quality area in early stage, convergence is slow, the result fluctuation is large, secondly, the operator selection probability, cross mutation probability, penalty weight and other parameter combination space is large, a unifie