技术领域technical field
本发明涉及即时配送时间预测技术领域，具体是一种基于时空注意力机制的送达时间智能预测方法。The invention relates to the technical field of instant delivery time prediction, in particular to an intelligent prediction method of delivery time based on a spatio-temporal attention mechanism.
背景技术Background technique
即时配送作为支撑新零售模式的关键环节，近年来发展迅速。由于配送时间是服务质量最直观的评价指标，客户对时间的高度敏感性要求平台在配送前合理评估订单总用时，以提供给客户准确的等待时长。因此对于即时配送送达时间的智能预测至关重要。针对这类时间预测问题，已有的解决方法包括机器学习和深度学习，机器学习常使用随机森林、梯度提升树等方法，深度学习利用循环神经网络、深层神经网络等模型组合进行预测。论文《A deep learning method for route and time prediction in food deliveryservice》提出了一种基于长短时记忆模型，该记忆模型和注意力机制结合预测下一步到达的目标地点，并根据预测结果预测这一段路程通行时间，循环预测完所有配送节点的顺序以及每段路程的时间(GAO C L,ZHANG F,WU G Q,et al.The 27th ACM SIGKDDConference on Knowledge Discovery & Data Mining(KDD'21). New York:Associationfor Computing Machinery,2021:2879-2889)。As a key link supporting the new retail model, instant delivery has developed rapidly in recent years. Since the delivery time is the most intuitive evaluation index of service quality, the high sensitivity of customers to time requires the platform to reasonably evaluate the total order time before delivery, so as to provide customers with accurate waiting time. Therefore, it is very important to intelligently predict the delivery time of instant delivery. For this kind of time prediction problem, existing solutions include machine learning and deep learning. Machine learning often uses methods such as random forests and gradient boosting trees. Deep learning uses a combination of models such as recurrent neural networks and deep neural networks for prediction. The paper "A deep learning method for route and time prediction in food delivery service" proposes a long-short-term memory-based model, which combines the memory model with the attention mechanism to predict the target location to be reached next, and predicts the passage of this section of the journey based on the prediction results Time, the order of all distribution nodes and the time of each journey after the loop prediction (GAO C L, ZHANG F, WU G Q, et al. The 27th ACM SIGKDDConference on Knowledge Discovery & Data Mining (KDD'21). New York: Association for Computing Machinery, 2021:2879-2889).
论文《Supervised learning for arrival time estimations in restaurantmeal delivery》提出了一种DNN模型和梯度提升决策树结合的配送时间预测模型，利用DNN预测每个节点的顺序，并利用梯度提升决策树预测配送用时(HILDEBRANDT F D,etal.Transportation Science,2022,56(4):1058-1084)。虽然以上方法在解决即时配送时间预测问题上进行了改进，有较好的预测表现，但现有方法仍存在不足。面对多个订单同时预测的场景，现有方法常选择分段预测，最后累加分路段用时作为预测结果，存在误差累加进而加大偏差的可能。在多种特征学习方面，现有方法利用梯度提升树、LSTM、注意力机制等多种模型进行学习，但是在对特征中存在的时空关系以及特征关联学习方面仍存在提升空间。The paper "Supervised learning for arrival time estimations in restaurant meal delivery" proposes a delivery time prediction model combining DNN model and gradient boosting decision tree, using DNN to predict the order of each node, and using gradient boosting decision tree to predict delivery time (HILDEBRANDT F D, et al. Transportation Science, 2022, 56(4):1058-1084). Although the above methods have been improved to solve the problem of real-time delivery time prediction and have better prediction performance, there are still deficiencies in the existing methods. Faced with the scenario of simultaneous forecasting of multiple orders, the existing methods often choose segmental forecasting, and finally accumulate the time of the segmented road segments as the prediction result, and there is a possibility of error accumulation and further increase the deviation. In terms of learning a variety of features, existing methods use various models such as gradient boosting trees, LSTMs, and attention mechanisms to learn, but there is still room for improvement in terms of spatiotemporal relationships in features and feature association learning.
发明内容Contents of the invention
为了避免和克服现有技术中存在的技术问题，本发明提供了一种基于时空注意力机制的送达时间智能预测方法。本发明通过卷积神经网络和循环神经网络对不同特征进行学习，并结合注意力机制，充分挖掘配送节点间的时空关系对用时的影响，提升了即时配送时间预测的准确度。In order to avoid and overcome the technical problems existing in the prior art, the present invention provides an intelligent prediction method of delivery time based on a spatio-temporal attention mechanism. The invention learns different features through the convolutional neural network and the cyclic neural network, and combines the attention mechanism to fully excavate the influence of the spatio-temporal relationship between delivery nodes on the time, and improves the accuracy of instant delivery time prediction.
为实现上述目的，本发明提供如下技术方案：To achieve the above object, the present invention provides the following technical solutions:
一种基于时空注意力机制的送达时间智能预测方法，包括以下步骤：A method for intelligent prediction of delivery time based on a spatio-temporal attention mechanism, comprising the following steps:
S1、获取即时配送订单的订单特征，订单特征包括商家地址和顾客地址；将商家地址和顾客地址作为配送节点，并收集配送节点的节点特征；S1. Obtain the order characteristics of the instant delivery order, the order characteristics include the address of the merchant and the address of the customer; use the address of the merchant and the address of the customer as the delivery node, and collect the node characteristics of the delivery node;
S2、根据节点特征，预测各个配送节点的遍历顺序，并将该遍历顺序记为配送路线；S2. Predict the traversal sequence of each delivery node according to the node characteristics, and record the traversal sequence as a delivery route;
S3、获取配送路线的路线特征；S3. Obtain the route characteristics of the delivery route;
S4、根据路线特征，预测各个即时配送订单的配送用时。S4. Predict the delivery time of each instant delivery order according to the route characteristics.
作为本发明再进一步的方案：步骤S1的具体步骤如下：As a further solution of the present invention: the specific steps of step S1 are as follows:
S11、获取各个即时配送订单的订单特征，订单特征包括订单编号、骑手编号、骑手速度、商家地址、顾客地址、商家与顾客之间的距离和时间戳；S11. Obtain the order characteristics of each instant delivery order, the order characteristics include order number, rider number, rider speed, merchant address, customer address, distance between merchant and customer, and time stamp;
S12、将商家地址和顾客地址作为配送节点，汇总得到设定配送区域内所有待遍历的配送节点，并保存在配送节点集合L中，其中l1表示配送节点集合L中第1个配送节点；l2表示配送节点集合L中第2个配送节点；/>表示配送节点集合L中第nl个配送节点，nl表示配送节点集合L即配送区域内配送节点的总数；S12. Using the address of the merchant and the address of the customer as the delivery node, summarizing and obtaining all the delivery nodes to be traversed in the set delivery area, and storing them in the delivery node setL , Wherel1 means the first delivery node in the delivery node setL ;l2 means the second delivery node in the delivery node setL ; /> Indicates thenlth delivery node in the delivery node setL , andnl indicates the delivery node setL , which is the total number of delivery nodes in the delivery area;
S13、根据订单特征，获取各个配送节点的节点特征，节点特征包括：订单编号、骑手编号、骑手速度、商家地址、顾客地址、商家与顾客之间的距离和时间戳，并将节点特征保存在节点特征矩阵Fl中。S13. According to the order characteristics, obtain the node characteristics of each distribution node. The node characteristics include: order number, rider number, rider speed, merchant address, customer address, distance between merchant and customer, and time stamp, and save the node characteristics in In the node feature matrixFl .
作为本发明再进一步的方案：步骤S2的具体步骤如下：As a further solution of the present invention: the specific steps of step S2 are as follows:
S21、根据节点特征矩阵Fl中保存的各个配送节点的节点特征，通过余弦相似度计算公式计算各个配送节点之间的相似度；S21, according to the node feature of each delivery node preserved inthe node feature matrixF1 , calculate the similarity between each delivery node by the cosine similarity calculation formula;
S22、选择节点特征矩阵Fl中的任一配送节点为原始节点，根据相似度计算结果，选择与原始节点相似度最高的另一配送节点作为邻近节点，且已经使用过的原始节点不再划入下一次原始节点的选择范围之内；S22. Select any distribution node in the node feature matrixF1 as the original node, and select another distribution node withthe highest similarity with the original node as the adjacent node according to the similarity calculation result, and the original node that has been used is no longer designated Into the selection range of the original node next time;
S23、将原始节点和对应的邻近节点的节点特征矩阵进行横向拼接，以获得拼接矩阵，并用拼接矩阵覆盖原始节点对应的节点特征矩阵，以更新节点特征；将设定配送区域内的所有配送节点的拼接矩阵保存在拼接节点特征矩阵FP中；S23. Horizontally splicing the node feature matrix of the original node and the corresponding adjacent nodes to obtain the splicing matrix, and cover the node feature matrix corresponding to the original node with the splicing matrix to update the node feature; set all the delivery nodes in the delivery area The splicing matrix of is stored in the splicing node feature matrixFP ;
S24、将拼接节点特征矩阵FP中各个配送节点的节点特征输入神经网络中，以得到各个配送节点的得分，得分是指配送节点作为配送目标的概率，将各个配送节点的得分保存在得分矩阵中；S24. Input the node features of each distribution node in the splicing node feature matrixFP into the neural network to obtain the score of each delivery node, the score refers to the probability of the delivery node asthe delivery target, and save the score of each delivery node in the score matrix middle;
S25、将具有多个相邻配送节点的配送节点定义为决策点，根据决策点的订单完成情况，使用由0和1构成的掩码矩阵以表示骑手在决策点时各个配送节点的状态；将已经遍历的配送节点和未取货的即时配送订单的配送节点用0表示，0表示配送节点不可到达；用1表示配送节点可到达；S25. Define a delivery node with multiple adjacent delivery nodes as a decision point, and use a mask matrix composed of 0 and 1 to represent the status of each delivery node when the rider is at the decision point according to the completion of the order at the decision point; The delivery nodes that have been traversed and the delivery nodes of the instant delivery orders that have not been picked up are represented by 0, 0 indicates that the delivery node is unreachable; 1 indicates that the delivery node is reachable;
S26、将掩码矩阵和得分矩阵相乘，以得到包含各个配送节点评分的评分矩阵；将评分矩阵中各个配送节点的评分输入概率计算函数中，以得到各个配送节点的被选概率，选择其中被选概率最大的配送节点作为决策点下一步前进的预测地点；S26. Multiply the mask matrix and the score matrix to obtain a score matrix containing the scores of each delivery node; input the scores of each delivery node in the score matrix into the probability calculation function to obtain the selection probability of each delivery node, and select The distribution node with the highest probability is selected as the predicted location for the next step of the decision point;
S27、返回步骤S21，重复步骤S21-S26，直到预测完所有配送节点的遍历顺序，并将该遍历顺序记为配送路线。S27. Return to step S21, and repeat steps S21-S26 until the traversal sequence of all delivery nodes is predicted, and record the traversal sequence as a delivery route.
作为本发明再进一步的方案：所述余弦相似度计算公式如下：As a further solution of the present invention: the formula for calculating the cosine similarity is as follows:
其中，Sim表示余弦相似度函数；Sim(fl,fφ)表示第l个配送节点和第φ个配送节点之间的相似度；fl表示第l个配送节点的节点特征矩阵；fφ表示第φ个配送节点的节点特征矩阵。Among them,Sim represents the cosine similarity function;Sim (fl, fφ ) represents the similarity between thel -th delivery node and theφ -th delivery node;fl represents the node feature matrix of thel -th delivery node;fφ Represents the node feature matrix of theφth delivery node.
作为本发明再进一步的方案：所述概率计算函数的计算公式如下：As a further solution of the present invention: the calculation formula of the probability calculation function is as follows:
其中，Softmax表示归一化函数；表示第l个配送节点在第t个决策点的评分值；表示第c个配送节点在第t个决策点的评分值；nl表示设定配送区域内所有配送节点的总数。Among them,Softmax represents the normalization function; Indicates the scoring value of thelth delivery node at thetth decision point; Indicates the scoring value of thecth delivery node at thetth decision point;nl indicates the total number of all delivery nodes in the set delivery area.
作为本发明再进一步的方案：所述神经网络的损失函数为交叉熵函数，交叉熵函数的计算公式如下：As a further solution of the present invention: the loss function of the neural network is a cross-entropy function, and the calculation formula of the cross-entropy function is as follows:
其中，Lseq表示损失函数的损失值；Z是神经网络训练集的数量；/>表示第z个任务决策点的数量；/>表示在第t个决策点时实际选择地点的预测概率。 Among them,Lseq represents the loss value of the loss function;Z is the number of neural network training sets; /> Indicates the number ofz- th task decision points; /> Indicates the predicted probability of actually choosing the location at thetth decision point.
作为本发明再进一步的方案：步骤S3的具体步骤如下：As a further solution of the present invention: the specific steps of step S3 are as follows:
S31、根据配送路线上各个配送节点的节点特征，构建该配送路线的路线特征；路线特征包括：订单编号、骑手编号、骑手速度、商家地址、顾客地址、商家与顾客之间的距离和时间戳，并将路线特征保存在配送路线特征矩阵Fr中；S31. According to the node features of each delivery node on the delivery route, construct the route features of the delivery route; the route features include: order number, rider number, rider speed, merchant address, customer address, distance between merchant and customer, and time stamp , and store the route features in the distribution route feature matrixFr ;
S32、根据配送路线中各个配送节点的遍历顺序，将各个配送节点依序存放在配送节点序列集合U中。S32. According to the traversal order of each delivery node in the delivery route, store each delivery node in the delivery node sequence setU in sequence.
作为本发明再进一步的方案：步骤S4的具体步骤如下：As a further solution of the present invention: the specific steps of step S4 are as follows:
S41、获取设定配送区域内各个即时配送订单对应的各条配送路线上的配送节点，将这些配送节点彼此相连，彼此相连的两配送节点之间的连线构成边，以构成配送节点网络G，G=(V,E)，V表示这些配送节点构成的配送节点集合；E为配送节点的关系矩阵，E={eij｜1≤i≤j≤ne}，eij表示节点网络G中第i个配送节点和第j个配送节点之间的关联程度，eij的取值为0或1，0表示无关联，1表示有关联；S41. Obtain the delivery nodes on each delivery route corresponding to each instant delivery order in the set delivery area, connect these delivery nodes to each other, and the connection between the two connected delivery nodes forms an edge to form a delivery node networkG ,G = (V ,E ),V represents the set of distribution nodes formed by these distribution nodes;E is the relationship matrix of distribution nodes,E = {eij ｜1≤i ≤j ≤ne} ,eij represents the node networkG The degree of association between thei -th delivery node and thej -th delivery node in , the value ofeij is 0 or 1, 0 means no association, 1 means association;
S42、通过转移概率计算公式计算配送节点序列集合U中各个配送节点间的转移概率；S42. Calculate the transition probability between each delivery node in the delivery node sequence setU by using the transition probability calculation formula;
S43、通过二阶随机游走获得配送节点集合V的随机游走节点序列，利用Skip-gram方法将随机游走节点序列中的配送节点向量化，得到配送节点向量矩阵Eu；接着利用配送节点向量矩阵Eu将配送节点序列集合U向量化为配送节点序列特征矩阵Fu；S43. Obtain the random walk node sequence of the delivery node setV through the second-order random walk, use the Skip-gram method to vectorize the delivery nodes in the random walk node sequence, and obtain the delivery node vector matrixEu ; then use the delivery node The vector matrixEu vectorizes the distribution node sequence setU into the distribution node sequence feature matrixFu ;
S44、将节点序列特征矩阵Fu输入卷积神经网络模块中，利用nc个大小为nk×nd的卷积核对配送节点序列特征矩阵进行计算，步幅为1，以得到对应的计算值，将所有的计算值/>拼接组合构成组合矩阵Ak，其中1≤k≤nk，1≤x≤nr-nk+1，计算值和组合矩阵Ak的表示如下：S44. Input the node sequence feature matrixFu into the convolutional neural network module, and usenc convolution kernels with a size ofnk ×nd to verify the distribution node sequence feature matrix Perform calculations with a step of 1 to get the corresponding calculated value , will all computed values /> Splicing and combining to form a combination matrixAk , where 1≤k ≤nk , 1≤x ≤nr -nk +1, the calculated value and the combination matrixAk are expressed as follows:
其中，为激活函数；Wk和bk为训练参数；/>表示第/>个卷积核在第/>个窗口所选的配送节点的节点特征，选取第/>到/>个节点特征，窗口大为nk；nr×nd表示配送节点序列特征矩阵Fu为nr行、nd列的矩阵；/>表示第k个卷积核在第x个窗口计算的输出；in, is the activation function;Wk andbk are the training parameters; /> Indicates the first /> convolution kernel at /> The node characteristics of the distribution node selected in the first window, select the first /> to /> node features, the window size isnk ;nr ×nd represents the distribution node sequence feature matrixFu is a matrix ofnr rows andnd columns; /> Indicates the output calculated by thekth convolution kernel in thexth window;
S45、将nr个卷积核计算得到的组合矩阵Ak进行拼接，得到输出矩阵Ec，，(nr-nk+1)×nc表示输出矩阵Ec为nr-nk+1行、nc列的矩阵；设置池化层大小为np×1，步幅为1，接着对输出矩阵Ec进行最大池化得到池化输出矩阵，(nr-np-nk+2)×nc表示池化输出矩阵为nr-np-nk+2行、nc列的矩阵；S45. Concatenate the combination matrixAk obtained by calculatingthe nr convolution kernels to obtain the output matrixEc , , (nr -nk +1)×nc indicates that the output matrixEc is a matrix ofnr -nk +1 rows andnc columns; set the pooling layer size tonp× 1, and the stride to 1, Then perform maximum pooling on the output matrixEc to obtain the pooled output matrix , (nr -np -nk +2)×nc indicates that the pooling output matrix is a matrix ofnr -np -nk +2 rows andnc columns;
S46、设置权重矩阵，且权重矩阵EQ中各个位置随机取值作为初始值，(nr-nk-np+2)×nc表示池化输出矩阵EQ为nr-nk-np+2行、nc列的矩阵；之后将权重矩阵EQ和输出矩阵/>相加，并依次通过tanh激活函数和一个线性层，得到相加矩阵，nr×nc表示相加矩阵Ekq为nr行、nc列的矩阵；将Ekq输入Softmax进行计算，得到注意力权重矩阵/>；相加矩阵Ekq表示如下：S46. Setting the weight matrix , and each position in the weight matrixEQ is randomly selected as the initial value, (nr -nk -np +2)×nc means that the pooling output matrixEQ isnr -nk -np +2 rows , matrix ofnc columns; then the weight matrixEQ and the output matrix /> Add, and pass through the tanh activation function and a linear layer in turn to get the addition matrix ,nr ×nc means that the addition matrixEkq is a matrix withnr rows andnc columns; inputEkq intoSoftmax for calculation, and get the attention weight matrix/> ; The addition matrixEkq is expressed as follows:
其中，Wkq和bkq均为线性层的参数；Among them,Wkq andbkq are parameters of the linear layer;
S47、将配送路线特征矩阵Fr中的所有路线特征向量化，得到新的配送路线特征矩阵，/>表示新的配送路线特征矩阵/>为nr行、/>列的矩阵，并将/>输入到单层的GRU模型中，得到输出矩阵/>，nr×ng表示输出矩阵Eg为nr行、ng列的矩阵；S47. Vectorize all route features in the delivery route feature matrixFr to obtain a new delivery route feature matrix , /> Represents the new delivery route feature matrix /> Fornr lines, /> a matrix of columns, and the /> Input into the single-layer GRU model to get the output matrix /> ,nr ×ng means that the output matrixEg is a matrix withnr rows andng columns;
S48、将和Eg相乘得到相乘矩阵/>，ng×nc表示相乘矩阵Eatt为nr行、nd列的矩阵；并将Eatt输入到一个多层感知机中计算，以得到即时配送订单的预测配送用时/>。S48. Will Multiply withEg to get the multiplication matrix /> ,ng ×nc means that the multiplication matrixEatt is a matrix ofnr rows andnd columns; andEatt is input into a multi-layer perceptron for calculation to obtain the predicted delivery time of instant delivery orders/> .
作为本发明再进一步的方案：转移概率计算公式如下：As a further solution of the present invention: the transition probability calculation formula is as follows:
其中，P(ui｜ui-1)表示配送节点ui-1转移到配送节点ui的概率；α表示随机游走参数；表示配送节点ui-1和配送节点ui之间边的权重；/>表示与配送节点ui-1相连接的配送节点构成的配送节点集合；v表示配送节点集合/>中的第v个配送节点，表示配送节点v和配送节点ui-1之间边的权重。Among them,P (ui ｜ui- 1 ) represents the probability that the delivery nodeui- 1 transfers to the delivery nodeui ;α represents the random walk parameter; Indicates the weight of the edge between delivery nodeui- 1 and delivery nodeui ; /> Indicates the delivery node set formed by the delivery nodes connected to the delivery nodeui- 1 ;v indicates the delivery node set/> Thevth delivery node in , Indicates the weight of the edge between delivery nodev and delivery nodeui- 1 .
作为本发明再进一步的方案：卷积神经网络模块使用的损失函数为均方差损失函数，表示如下：As a further solution of the present invention: the loss function used by the convolutional neural network module is a mean square error loss function, expressed as follows:
其中，Ltime表示均方差值；yn为第n个即时配送订单的实际配送用时，为第n个即时配送订单的预测配送用时，为数据总量。Among them,Ltime represents the mean square error value;yn is the actual delivery time of thenth instant delivery order, is the predicted delivery time of thenth instant delivery order, and is the total amount of data.
与现有技术相比，本发明的有益效果是：Compared with prior art, the beneficial effect of the present invention is:
1.本发明在配送路线确定之后，选择以配送节点表示订单配送路线，这种路线表示方法不仅降低了路线表示的难度，而且很大程度上降低了路线的稀疏性问题，同时预测整条路线的用时，避免了分段预测造成的误差加大的可能。1. After the delivery route is determined, the present invention chooses delivery nodes to represent the order delivery route. This method of route representation not only reduces the difficulty of route representation, but also reduces the sparsity of the route to a large extent, and at the same time predicts the entire route The time spent avoids the possibility of increased error caused by segmented prediction.
2.本发明在对路线预测时，通过计算节点间的余弦相似度,可以充分表现任务节点间的近邻关系和任务的紧迫程度相似性，有效模拟现实的选择策略。2. When the present invention predicts the route, by calculating the cosine similarity between nodes, it can fully express the neighbor relationship between the task nodes and the similarity of the urgency of the task, and effectively simulate the realistic selection strategy.
3.本发明通过将配送节点利用图嵌入的方法进行表示，同时利用卷积神经网络对配送路线进行空间特征提取，有效提取了配送节点间的空间关系。3. The present invention expresses the delivery nodes using a graph embedding method, and at the same time uses a convolutional neural network to extract the spatial features of the delivery route, effectively extracting the spatial relationship between the delivery nodes.
4.本发明通过利用门控循环单元模型对配送路线特征中存在的时间顺序关系进行提取，有效提取了特征中的时间关系。4. The present invention effectively extracts the temporal relationship in the feature by using the gated cyclic unit model to extract the time sequence relationship existing in the delivery route feature.
5.本发明基于注意力机制，将卷积神经网络和门控循环单元模型的输出分别作为注意力机制网络的参数矩阵，共同学习特征中时空关联关系，有效提取特征。5. The present invention is based on the attention mechanism, uses the output of the convolutional neural network and the gated recurrent unit model as the parameter matrix of the attention mechanism network, and jointly learns the spatiotemporal correlations in the features to effectively extract the features.
附图说明Description of drawings
图1为本发明的操作流程图。Fig. 1 is the operation flowchart of the present invention.
图2为本发明方法原理图。Fig. 2 is a schematic diagram of the method of the present invention.
图3为本发明的模型结构图。Fig. 3 is a model structural diagram of the present invention.
图4为本发明实验结果图。Fig. 4 is a graph showing the experimental results of the present invention.
具体实施方式Detailed ways
下面将结合本发明实施例中的附图，对本发明实施例中的技术方案进行清楚、完整的描述，显然，所描述的实施例仅仅是本发明一部分实施例，而不是全部的实施例。基于本发明中的实施例，本领域普通技术人员在没有做出创造性劳动前提下所获得的所有其他实施例，都属于本发明保护的范围。The technical solutions in the embodiments of the present invention will be clearly and completely described below in conjunction with the accompanying drawings in the embodiments of the present invention. Obviously, the described embodiments are only some, not all, embodiments of the present invention. Based on the embodiments of the present invention, all other embodiments obtained by persons of ordinary skill in the art without making creative efforts belong to the protection scope of the present invention.
请参阅图1～图4，本发明实施例中，一种基于时空注意力机制的送达时间智能预测方法，按照如下步骤进行的：Please refer to Figures 1 to 4. In the embodiment of the present invention, a method for intelligent prediction of delivery time based on the spatiotemporal attention mechanism is carried out according to the following steps:
1、获取配送订单信息，收集与订单相关特征数据，构造数据集；1. Obtain delivery order information, collect characteristic data related to the order, and construct a data set;
1.1、获取某时刻待完成配送的订单信息，将商家地址和顾客地址作为配送节点，汇总得到待遍历的节点集合，其中nl表示配送节点集合L即配送区域内配送节点的总数；1.1. Obtain the order information to be delivered at a certain time, use the merchant address and customer address as the delivery node, and summarize the node set to be traversed , wherenl represents the delivery node setL , which is the total number of delivery nodes in the delivery area;
1.2、根据订单特征，获取各个配送节点的节点特征，节点特征包括：订单编号、骑手编号、骑手速度、商家地址、顾客地址、商家与顾客之间的距离和时间戳，并将节点特征保存在节点特征矩阵Fl中；得到所有配送节点的特征，其中/>表示第/>个配送节点的节点特征，/>表示节点特征的数量。1.2. According to the order characteristics, obtain the node characteristics of each delivery node. The node characteristics include: order number, rider number, rider speed, merchant address, customer address, distance between merchant and customer, and timestamp, and save the node characteristics in In the node feature matrixFl ; get the features of all delivery nodes , where /> Indicates the first /> The node characteristics of a distribution node, /> Indicates the number of node features.
2、根据节点特征，通过配送路线预测模块对配送节点的遍历顺序进行预测：2. According to the characteristics of the nodes, the traversal sequence of the delivery nodes is predicted through the delivery route prediction module:
2.1、在第t个决策点，1＜t≤nt，其中表示决策点的总数，利于式(1)计算每个节点特征向量与其他节点特征向量的余弦相似度，其中Sim(l,φ)表示第l个和第φ个的节点特征向量的余弦相似度；2.1. At thetth decision point, 1<t ≤nt , where Indicates the total number of decision points, which is beneficial to formula (1) to calculate the cosine similarity between each node feature vector and other node feature vectors, whereSim (l, φ ) represents the cosine similarity of thelth andφth node feature vectors ;
(1) (1)
2.2、根据余弦相似度结果，针对每个配送节点，选择余弦相似度最高的另一配送节点作为邻近配送节点，并将邻近配送节点的信息和原配送节点的节点特征结合，构造新的节点特征矩阵；2.2. According to the cosine similarity results, for each delivery node, select another delivery node with the highest cosine similarity as the adjacent delivery node, and combine the information of the adjacent delivery node with the node characteristics of the original delivery node to construct a new node feature matrix ;
2.3、将新的节点特征矩阵输入到深度神经网络模块中，该模块由kl个线性层，ka个Relu激活函数和kb个归一化层堆叠组合而成，通过该模块计算输出每个候选配送节点的得分；2.3. Input the new node feature matrix into the deep neural network module. This module is composed ofkl linear layers,ka Relu activation functions andkb normalization layers. Through this module, the output of each The scores of candidate delivery nodes ;
2.4、根据第t个决策点时的订单完成情况，使用0和1构成的掩码矩阵，表示该时刻配送节点的状态，将已遍历的和未取货订单的配送节点用0表示，代表不可选择，即不可到达；用1表示节点可以选择，即可以达到；2.4. According to the completion of the order at thetth decision point, use a mask matrix composed of 0 and 1 , indicating the status of the delivery node at this moment, and the delivery nodes of the traversed and uncollected orders are represented by 0, which means that they cannot be selected, that is, they cannot be reached; 1 represents that the nodes can be selected, that is, they can be reached;
2.5、将掩码矩阵和评分矩阵/>相乘，得到第t个决策点时，可选择配送节点的评分矩阵/>，之后将/>输入Softmax函数中进行计算，如式(2)所示，其中/>表示第l个点的评分值，得到每个候选配送节点的选择概率，选择其中概率最大的配送节点作为下一步前往的预测地点；2.5, the mask matrix and scoring matrix /> Multiply to get thetth decision point, you can choose the scoring matrix of the delivery node /> , then the /> Enterthe Softmax function for calculation, as shown in formula (2), where /> Indicates the scoring value of thel- th point, obtains the selection probability of each candidate delivery node, and selects the delivery node with the highest probability as the predicted location for the next step;
(2) (2)
2.6、根据预测结果，更新掩码矩阵和节点特征，并返回2.1，重复以上步骤，直到预测完所有节点的顺序为止。2.6. According to the prediction results, update the mask matrix and node features, and return to 2.1, repeat the above steps until the order of all nodes is predicted.
2.7、配送路线预测部分在训练时采用交叉熵函数作为损失函数，式(3)所示，其中Z为训练集数量，表示第z个任务的决策点数量，/>表示在第t个决策点时，实际选择地点的预测概率。2.7. The delivery route prediction part uses the cross entropy function as the loss function during training, as shown in formula (3), whereZ is the number of training sets, Indicates the number of decision points for thezth task, /> Indicates the predicted probability of actually choosing the location at thetth decision point.
(3) (3)
3、根据配送路线预测结果，构造配送路线特征矩阵，，以及配送节点序列/>，其中nr和mr分别代表配送路线节点数量和特征数量。3. Construct the distribution route feature matrix according to the distribution route prediction results , , and the delivery node sequence /> , wherenr andmr represent the number of distribution route nodes and the number of features respectively.
4、根据配送路线特征，使用时间预测模块预测每个订单的配送用时：4. According to the characteristics of the delivery route, use the time prediction module to predict the delivery time of each order:
4.1、根据配送节点间的连接关系构建配送节点网络G，G=(V,E)，V为节点集合，E={eij｜1≤i≤j≤ne}，eij表示节点网络G中第i个配送节点和第j个配送节点之间的关联程度，eij的取值为0或1，0表示无关联，1表示有关联；ne为节点总数。4.1. Construct a distribution node networkG according to the connection relationship between distribution nodes,G = (V ,E ),V is a node set,E = {eij | 1≤i ≤j ≤ne },eij represents the node networkG The degree of association between thei- th delivery node and thej -th delivery node in , the value ofeij is 0 or 1, 0 means no association, 1 means association;ne is the total number of nodes.
4.2、基于节点网络，使用Node2vec方法对节点进行嵌入表示：4.2. Based on the node network, use the Node2vec method to embedding the nodes:
4.2.1、式(4)所示，计算节点间的转移概率，其中P(ui｜ui-1)表示配送节点ui-1转移到配送节点ui的概率；α表示随机游走参数；表示配送节点ui-1和配送节点ui之间边的权重；/>表示与配送节点ui-1相连接的配送节点构成的配送节点集合；v表示配送节点集合/>中的第v个配送节点，/>表示配送节点v和配送节点ui-1之间边的权重。4.2.1, as shown in formula (4), calculate the transition probability between nodes, whereP (ui |ui- 1 ) represents the probability that delivery nodeui- 1 transfers to delivery nodeui ;α represents random walk parameter; Indicates the weight of the edge between delivery nodeui- 1 and delivery nodeui ; /> Indicates the delivery node set formed by the delivery nodes connected to the delivery nodeui- 1 ;v indicates the delivery node set/> Thevth distribution node in, /> Indicates the weight of the edge between delivery nodev and delivery nodeui- 1 .
计算方法见式(5)，其中p和q是设定的参数，di,i-2表示上配送节点ui-2和邻接配送节点之间的最短距离，当两配送节点直接相连则di,i-2=0，配送节点间有一个中间配送节点则di,i-2=1，其他情况则di,i-2=2；The calculation method is shown in formula (5), wherep andq are set parameters,di,i- 2 represents the shortest distance between the upper delivery nodeui- 2 and the adjacent delivery node, when two delivery nodes are directly connected, thendi, i- 2 =0, if there is an intermediate delivery node between delivery nodes, thendi,i- 2 =1, and in other cases,di,i- 2 =2;
(4) (4)
(5) (5)
4.2.2、通过二阶随机游走获得随机游走节点序列，并利用Skip-gram方法将生成的节点向量化，得到节点向量矩阵，其中nd为向量化长度，并利用Eu将配送节点序列U向量化为节点序列特征矩阵/>；4.2.2. Obtain the random walk node sequence through the second-order random walk, and use the Skip-gram method to vectorize the generated nodes to obtain the node vector matrix , wherend is the vectorization length, and useEu to vectorize the delivery node sequenceU into a node sequence feature matrix /> ;
4.3、将节点序列特征矩阵输入卷积神经网络进行特征提取：4.3, the node sequence feature matrix Input convolutional neural network for feature extraction:
4.3.1、式(6)和(7)所示，利用nc个大小为nk×nd的卷积核对配送节点序列特征矩阵进行计算，步幅为1，以得到对应的计算值/>，将所有的计算值/>拼接组合构成组合矩阵Ak，其中1≤k≤nk，1≤x≤nr-nk+1，计算值/>和组合矩阵Ak的表示如下：4.3.1, as shown in formulas (6) and (7), usenc convolution kernels with a size ofnk ×nd to check the distribution node sequence feature matrix Perform calculations with a step of 1 to get the corresponding calculated value /> , will all computed values /> Splicing and combining to form a combination matrixAk , where 1≤k ≤nk , 1≤x ≤nr -nk +1, the calculated value/> and the combination matrixAk are expressed as follows:
(6) (6)
(7) (7)
其中，为激活函数；Wk和bk为训练参数；/>表示第/>个卷积核在第/>个窗口所选的配送节点的节点特征，选取第/>到/>个节点特征，窗口大为nk；nr×nd表示配送节点序列特征矩阵Fu为nr行、nd列的矩阵；/>表示第k个卷积核在第i个窗口计算的输出；in, is the activation function;Wk andbk are the training parameters; /> Indicates the first /> convolution kernel at /> The node characteristics of the distribution node selected in the first window, select the first /> to /> node features, the window size isnk ;nr ×nd represents the distribution node sequence feature matrixFu is a matrix ofnr rows andnd columns; /> Indicates the output calculated by thek- th convolution kernel in thei -th window;
4.3.2、将所有卷积核计算所得Ak拼接得到输出矩阵，设置池化层大小为np×1，步幅为1，之后进行最大池化得到/>；4.3.2. ConcatenateAk calculated by all convolution kernels to obtain the output matrix , set the size of the pooling layer tonp× 1, and the stride to 1, and then perform maximum pooling to obtain /> ;
4.4、式(8)所示，设置权重矩阵，并初始化，之后将EQ和相加，并通过tanh激活函数和一个线性层，得到输出/>；4.4, as shown in formula (8), set the weight matrix , and initialized, then addthe EQ sum, and pass the tanh activation function and a linear layer to get the output /> ;
(8) (8)
4.5、将Ekq输入Softmax中进行计算，得到注意力权重；4.5. EnterEkq intoSoftmax for calculation, and get the attention weight ;
4.6、将配送路线特征Fr中的所有特征向量化，得到新的路线特征，并将输入单层的GRU模型中，得到输出/>，其中ng为GRU输出大小；4.6. Vectorize all the features in the delivery route featureFr to get a new route feature , and will be input into the single-layer GRU model to get the output /> , whereng is the GRU output size;
4.7、将和Eg相乘得到/>，并输入到一个多层感知机中得到最终时间预测值/>；4.7, will Multiplied byEg to get /> , and input it into a multi-layer perceptron to get the final time prediction value/> ;
4.8、时间预测模块使用均方误差作为损失函数，式(9)所示，其中y为配送实际用时，为预测用时，N为数据总量。4.8. The time prediction module uses the mean square error as the loss function, as shown in formula (9), where y is the actual delivery time, is the prediction time,and N is the total amount of data.
(9) (9)
5、本方法的训练批量大小以及学习率均通过最小化损失函数确定，利用即时配送数据对模型进行训练，得到即时配送时间预测模型。5. The training batch size and learning rate of this method are determined by minimizing the loss function, and the instant delivery data is used to train the model to obtain the instant delivery time prediction model.
为验证本发明方法的有效性，在真实数据集上进行具体的实验，实验环境为：Windows操作系统，Intel(R) Core(TM) i5-8500 CPU，16GB内存，pytorch深度学习框架。In order to verify the effectiveness of the method of the present invention, a specific experiment is carried out on a real data set. The experimental environment is: Windows operating system, Intel(R) Core(TM) i5-8500 CPU, 16GB memory, and pytorch deep learning framework.
实验数据：选择某平台上的配送数据集作为实验数据。该数据集收集地点为某地区，时间跨度为2020年2月1日到2020年2月27日。数据集包括四个方面的信息，分别为：骑手数据、订单数据、距离数据和行为数据，具体统计值见表1。以订单数据为基准进行数据集成，构造的数据集共包含254802条配送订单数据，并将80%的数据用于训练，20%的数据用于测试。Experimental data: Select the distribution data set on a certain platform as the experimental data. The data set is collected in a certain region, and the time span is from February 1, 2020 to February 27, 2020. The data set includes four aspects of information, namely: rider data, order data, distance data and behavior data. The specific statistics are shown in Table 1. Based on the order data for data integration, the constructed data set contains a total of 254,802 delivery order data, and 80% of the data is used for training, and 20% of the data is used for testing.
表1 数据集统计信息Table 1 Dataset Statistics
图4实验结果表明，本发明的预测值能够和真实值较好的拟合，说明在对即时配送的送达时间预测方面能够实现准确的预测，证明了本发明方法的可行性。The experimental results in Fig. 4 show that the predicted value of the present invention can fit well with the real value, indicating that accurate prediction can be realized in the prediction of the delivery time of instant distribution, and the feasibility of the method of the present invention is proved.
上显示和描述了本发明的基本原理、主要特征和本发明的优点。本行业的技术人员应该了解，本发明不受上述实施例的限制，上述实施例和说明书中描述的只是本发明的原理，在不脱离本发明精神和范围的前提下本发明还会有各种变化和改进，这些变化和改进都落入要求保护的本发明的范围内。本发明要求的保护范围由所附的权利要求书及其等同物界定。The basic principles, main features and advantages of the present invention are shown and described above. Those skilled in the art should understand that the present invention is not limited by the above-mentioned embodiments. What are described in the above-mentioned embodiments and the description are only the principles of the present invention. Variations and improvements, which fall within the scope of the claimed invention. The scope of protection required by the present invention is defined by the appended claims and their equivalents.
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN202310875592.0ACN116596170B (en) | 2023-07-18 | 2023-07-18 | Intelligent prediction method for delivery time based on space-time attention mechanism |
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN202310875592.0ACN116596170B (en) | 2023-07-18 | 2023-07-18 | Intelligent prediction method for delivery time based on space-time attention mechanism |
| Publication Number | Publication Date |
|---|---|
| CN116596170Atrue CN116596170A (en) | 2023-08-15 |
| CN116596170B CN116596170B (en) | 2023-09-22 |
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| CN202310875592.0AActiveCN116596170B (en) | 2023-07-18 | 2023-07-18 | Intelligent prediction method for delivery time based on space-time attention mechanism |
| Country | Link |
|---|---|
| CN (1) | CN116596170B (en) |
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US20190156357A1 (en)* | 2017-11-22 | 2019-05-23 | Staples, Inc. | Advanced computational prediction models for heterogeneous data |
| WO2020024319A1 (en)* | 2018-08-01 | 2020-02-06 | 苏州大学张家港工业技术研究院 | Convolutional neural network based multi-point regression forecasting model for traffic flow forecasting |
| CN110766510A (en)* | 2019-09-18 | 2020-02-07 | 北京三快在线科技有限公司 | Recommendation method and device, electronic equipment and readable storage medium |
| CN111612400A (en)* | 2020-05-22 | 2020-09-01 | 上海明略人工智能(集团)有限公司 | Distribution time length prediction method and device |
| CN111860914A (en)* | 2020-07-31 | 2020-10-30 | 安徽梦馨信息技术有限公司 | Flower appointment order distribution method and system |
| CN111899510A (en)* | 2020-07-28 | 2020-11-06 | 南京工程学院 | Intelligent traffic system flow short-term prediction method and system based on divergent convolution and GAT |
| CN112308514A (en)* | 2020-10-30 | 2021-02-02 | 康键信息技术（深圳）有限公司 | Method, device, equipment and storage medium for automatic billing of logistics orders |
| CN112884390A (en)* | 2019-11-29 | 2021-06-01 | 北京三快在线科技有限公司 | Order processing method and device, readable storage medium and electronic equipment |
| CN112948412A (en)* | 2021-04-21 | 2021-06-11 | 携程旅游网络技术（上海）有限公司 | Flight inventory updating method, system, electronic equipment and storage medium |
| CN113947245A (en)* | 2021-10-20 | 2022-01-18 | 辽宁工程技术大学 | Multi-passenger multi-driver sharing matching method and system based on order accumulation |
| CN114819819A (en)* | 2022-04-15 | 2022-07-29 | 电子科技大学 | A realization method of route planning in real-time logistics scenario |
| CN115099460A (en)* | 2022-05-19 | 2022-09-23 | 大连海事大学 | A regional division method for real-time distribution merchants in urban logistics |
| WO2023279407A1 (en)* | 2021-07-06 | 2023-01-12 | 深圳市通拓信息技术网络有限公司 | Outbound and distribution method for e-commerce intelligent warehousing |
| US20230133602A1 (en)* | 2020-06-29 | 2023-05-04 | Walmart Apollo, Llc | Door-step time estimation and delivery route optimization |
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US20190156357A1 (en)* | 2017-11-22 | 2019-05-23 | Staples, Inc. | Advanced computational prediction models for heterogeneous data |
| WO2020024319A1 (en)* | 2018-08-01 | 2020-02-06 | 苏州大学张家港工业技术研究院 | Convolutional neural network based multi-point regression forecasting model for traffic flow forecasting |
| CN110766510A (en)* | 2019-09-18 | 2020-02-07 | 北京三快在线科技有限公司 | Recommendation method and device, electronic equipment and readable storage medium |
| CN112884390A (en)* | 2019-11-29 | 2021-06-01 | 北京三快在线科技有限公司 | Order processing method and device, readable storage medium and electronic equipment |
| CN111612400A (en)* | 2020-05-22 | 2020-09-01 | 上海明略人工智能(集团)有限公司 | Distribution time length prediction method and device |
| US20230133602A1 (en)* | 2020-06-29 | 2023-05-04 | Walmart Apollo, Llc | Door-step time estimation and delivery route optimization |
| CN111899510A (en)* | 2020-07-28 | 2020-11-06 | 南京工程学院 | Intelligent traffic system flow short-term prediction method and system based on divergent convolution and GAT |
| CN111860914A (en)* | 2020-07-31 | 2020-10-30 | 安徽梦馨信息技术有限公司 | Flower appointment order distribution method and system |
| CN112308514A (en)* | 2020-10-30 | 2021-02-02 | 康键信息技术（深圳）有限公司 | Method, device, equipment and storage medium for automatic billing of logistics orders |
| CN112948412A (en)* | 2021-04-21 | 2021-06-11 | 携程旅游网络技术（上海）有限公司 | Flight inventory updating method, system, electronic equipment and storage medium |
| WO2023279407A1 (en)* | 2021-07-06 | 2023-01-12 | 深圳市通拓信息技术网络有限公司 | Outbound and distribution method for e-commerce intelligent warehousing |
| CN113947245A (en)* | 2021-10-20 | 2022-01-18 | 辽宁工程技术大学 | Multi-passenger multi-driver sharing matching method and system based on order accumulation |
| CN114819819A (en)* | 2022-04-15 | 2022-07-29 | 电子科技大学 | A realization method of route planning in real-time logistics scenario |
| CN115099460A (en)* | 2022-05-19 | 2022-09-23 | 大连海事大学 | A regional division method for real-time distribution merchants in urban logistics |
| Title |
|---|
| 杨浩雄等: "" 考虑一单多品的外卖订单配送时间的带时间窗的车辆路径问题"", 《计算机科学》, pages 191 - 198* |
| Publication number | Publication date |
|---|---|
| CN116596170B (en) | 2023-09-22 |
| Publication | Publication Date | Title |
|---|---|---|
| CN110837602B (en) | User recommendation method based on representation learning and multi-mode convolutional neural network | |
| CN111008858B (en) | A product sales forecast method and system | |
| CN114372573B (en) | User portrait information recognition method and device, computer equipment and storage medium | |
| CN113988464B (en) | Network link attribute relation prediction method and device based on graph neural network | |
| CN110032632A (en) | Intelligent customer service answering method, device and storage medium based on text similarity | |
| CN114065048B (en) | Article recommendation method based on multi-different composition graph neural network | |
| CN112085615B (en) | Training method and device for graphic neural network | |
| WO2021164382A1 (en) | Method and apparatus for performing feature processing for user classification model | |
| CN112989059A (en) | Method and device for identifying potential customer, equipment and readable computer storage medium | |
| CN113610610B (en) | Conversational recommendation method and system based on graph neural network and review similarity | |
| CN109313720A (en) | Augmented neural network with sparse access to external memory | |
| CN113762595A (en) | Traffic time prediction model training method, traffic time prediction method and equipment | |
| CN112487199A (en) | User characteristic prediction method based on user purchasing behavior | |
| CN113536105A (en) | Recommendation model training method and device | |
| CN115953902A (en) | Traffic flow prediction method based on multi-view space-time diagram convolution network | |
| CN114584406B (en) | Industrial big data privacy protection system and method for federated learning | |
| CN118627614B (en) | Knowledge-graph path mining method by utilizing conditional random field and relation extraction | |
| CN113850654A (en) | Item recommendation model training method, item screening method, device and equipment | |
| CN115618079A (en) | Session recommendation method, device, electronic equipment and storage medium | |
| CN115310590A (en) | Graph structure learning method and device | |
| CN112150206A (en) | Method and equipment for predicting user interested article | |
| CN118072560A (en) | Sector traffic prediction method based on AGC-LSTM | |
| CN115880027A (en) | Electronic commerce website commodity seasonal prediction model creation method | |
| CN116596170B (en) | Intelligent prediction method for delivery time based on space-time attention mechanism | |
| CN115345687A (en) | Cross-website commodity alignment method and device |
| Date | Code | Title | Description |
|---|---|---|---|
| PB01 | Publication | ||
| PB01 | Publication | ||
| SE01 | Entry into force of request for substantive examination | ||
| SE01 | Entry into force of request for substantive examination | ||
| GR01 | Patent grant | ||
| GR01 | Patent grant | ||
| PE01 | Entry into force of the registration of the contract for pledge of patent right | ||
| PE01 | Entry into force of the registration of the contract for pledge of patent right | Denomination of invention:An intelligent delivery time prediction method based on spatiotemporal attention mechanism Granted publication date:20230922 Pledgee:Industrial and Commercial Bank of China Co.,Ltd. Hefei Science and Technology Sub branch Pledgor:HEFEI CITY CLOUD DATA CENTER Co.,Ltd. Registration number:Y2025980024501 |