[20240715_LabSeminar_Huy]M2G4RTP: A Multi-Level and Multi-Task Graph Model for Instant-Logistics Route and Time Joint Prediction.pptx

M2G4RTP: A Multi-Level and Multi-Task Graph Model for Instant-Logistics Route and Time Joint Prediction

1. Quang-Huy Tran Network Science Lab Dept. of Artificial Intelligence The Catholic University of Korea E-mail: [email protected] 2024-07-15 M2G4RTP: A Multi-Level and Multi-Task Graph Model for Instant-Logistics Route and Time Joint Prediction Tianyue Cai et al. ICDE-2023 : The IEEE 39th International Conference on Data Engineering

2. OUTLINE MOTIVATION METHODOLOGY EXPERIMENT & RESULT CONCLUSION

3. MOTIVATION With the popularity of online shopping and online food ordering . Instant-logistics services are undergoing explosive development. The service Route and arrival Time Prediction (RTP) is increasingly becoming a hot topic in both academic and industry communities. A courier usually has several locations to be visited at a certain time. RTP aims to predict the future route as well as the arrival time of the courier’s all unvisited locations. Joint prediction of the route and time is of great significance for the platform: users and logistics. Overview and Limitation Limitations: Failing to consider the high-level transfer mode of couriers between AOIs (Areas Of Interest - residential quarters or office buildings). Previous works considered separately predict route/time or predict them in a two-step way. Failing to simultaneously make the route and time prediction. The widely adopted tree based or sequence-based architecture fails to fully encode the spatial relationship between different location.

4. INTRODUCTION A multi-level graph encoder equipped with GAT-e encoding module : Modeling couriers’ high-level transfer mode between AOIs and low-level transfer mode between locations. Contribution First to s tudy the joint prediction of route and time in instant-logistics . A multi-level and multi-task graph model is proposed for simultaneously predicting a courier’s route and arrival time. A multi-task decoder is designed to jointly predict route and time at both AOI-level and location-level. A homoscedastic uncertainty-based loss weighting method is utilized to adaptively adjust the weight of the route loss and time loss.

5. METHODOLOGY Problem Definition Given RTP dataset: Location: location order within the specified time to complete the delivery or pick-up on time where is central longitude and latitude of AOI. ID is unique and type is type of AOI (community, office building, hospital, etc ).   AOI: a certain regional entity in the map Multi-level graph: graph of location and AOI positional information of location AOI of location promised arrival deadline Location graph: locations to be visit by a courier Set of edges node feature set   edge feature set   AOI graph: AOIs that a courier is going to visit Set of edges node feature set   edge feature set   Multi-level graph: edges that connect locations and their corresponding AOIs .  

6. METHODOLOGY Problem Definition Problem: predict the route as well as arrival time foreach location Given multi-level graph G, goal is to build a model F Map the input query to route and time of the unvisited locations Route: a sequence of locations/AOIs to be visited by couriers Time: gap between the current time and arrival time Given RTP dataset: actual arrival time at location and AOI  

7. METHODOLOGY Main Architecture

8. METHODOLOGY Multi-Level Graph Encoder Take multi-level graph as input and learns the location/AOI representations: modeling their inter- and intra-relationships between locations and AOIs . Build a location graph and an AOI graph : location or AOI is a node.   Node Feature: location node , feature vector contains spatial and temporal information of location .   AOI node , feature vector contains spatial and temporal information of AOI .   geographical coordinate distance between location and courier   AOI’s ID and type of location arrival deadline of the location and accept time of location’s order central geographical coordinate distance between center AOI and courier   ID and type of AOI earliest arrival deadline for all locations in the AOI.

9. METHODOLOGY Multi-Level Graph Encoder Edge Feature: For location edge , edge feature vector contains spatial and temporal information related to task .   Define the k-nearest spatial neighbors based on distance between nodes and temporal neighbors based on time gap between deadlines of each node for an edge feature in AOI . Euclidean distance between location and   gap time between two arrival deadlines connectivity between two locations

10. METHODOLOGY Multi-Level Graph Encoder Global Feature : courier’s own attributes (working hours, driving speed, attendance, etc.), weather or weekday . where : courier’s average working hours per day, average driving speed, and attendance in last two months. codename of weather and weekday.   Prepare input for encoder : AOI ID and type: apply an embedding layer to project to the -dimensional vector space . C oordinates or time : apply a linear layer to to project to the -dimensional vector space . Concatenate to get input for encoder  

11. METHODOLOGY Multi-Level Graph Encoder Multi-Level GAT-e Encoding Module : Apply multi-head GAT on node and edge. where are learnable parameters, denotes LeakyReLU activation function, || is concatenation operation .   Node representation: Edge representation: Replace concatenation with average in last layer:

12. METHODOLOGY Multi-Task Decoder D ecodes the AOI-visiting route and arrival time based on the courier’s current state and the AOI repre sentations Decodes location-visiting route and arrival time based on courier’s current state, location representation, and AOI level guidance i nformation. Design based on quicksort algorithm idea: AOI guiding Location for route and time prediction. During process of quicksort, all elements to be sorted are divided into two groups, and all elements in one group are larger than those in the other group. D esign RNN- based module equipped with masked attention mechanism to simulate the decision-making process of couriers. Propose SortLSTM: RNN-based network with sorting function to calculate arrival time.

13. METHODOLOGY Multi-Task Decoder AOI-level Decoder : For AOI route prediction, calculates the probability of each candidate AOI node and selects the node with the maximum probability as the routing node by chain rule of courier u at time t where is all learnable parameters, is representation of AOIs obtained from encoder, denotes learnable parameter.   where are learnable parameters if node j has been output in previous step.   use an LSTM to aggregate the already generated AOIs into vector and concatenate with courier’s feature   To find the most likely neighbor of (s-1)- th output, concatenation of and u, and take neighbors to calculate probability distribution  

14. METHODOLOGY Multi-Task Decoder AOI-level Decoder : Use softmax for each output node in step and take maximum of all probabilities to form route prediction output in step s .   For time prediction module, SortLSTM is composed of several LSTM cells, which recurrently outputs the arrival time of each AOI . Position encoding module: where is the AOI’s position (from 1 to m) in the route.   SortLSTM:

15. METHODOLOGY Multi-Task Decoder Location-level Decoder: For location route prediction, add AOI guidance information to calculate conditional probability of each location in s- th decoding step : concatenate location representation with the position encoding vector and arrival time of AOI For location time prediction, sort all location representations based on the predicted location route, and concatenate positional encoding vector of location.

16. METHODOLOGY Model Training and Prediction O utput the route and time at both the location and AOI levels in a multi-task manner L ocation -level and AOI-level route prediction as a multi-classification problem: where T is the number of samples in the training dataset, is the number of distinct locations in the t- th sample, is the number of distinct AOIs in the t- th sample.   To learn the arrival time at each location and AOI: Total loss :

17. EXPERIMENT AND RESULT Experiment Settings Dataset: Package pick-up data in Hangzhou, China . Baselines: Heuristic: Time-Greedy, Distance-Greedy, and OR-Tools. Machine Learning/Deep Learning : OSquare , DeepRoute [1], and FDNET[2]. Graph-based: Graph2Route [3]. [1] Wen, H., Lin, Y., Wu, F., Wan, H., Guo, S., Wu, L., ... & Xu, Y. (2021, April). Package pick-up route prediction via modeling couriers’ spatial-temporal behaviors. In 2021 IEEE 37th International Conference on Data Engineering (ICDE) (pp. 2141-2146). IEEE. [2] Gao, C., Zhang, F., Wu, G., Hu, Q., Ru, Q., Hao, J., ... & Sun, Z. (2021, August). A deep learning method for route and time prediction in food delivery service. In Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining (pp. 2879-2889). [3] Wen, H., Lin, Y., Mao, X., Wu, F., Zhao, Y., Wang, H., ... & Wan, H. (2022, August). Graph2route: A dynamic spatial-temporal graph neural network for pick-up and delivery route prediction. In Proceedings of the 28th ACM SIGKDD conference on knowledge discovery and data mining (pp. 4143-4152). Measurement : HR@k : quantify the similarity between the top-k items of two sequences. Kendall Rank Correlation(KRC): measure the ordinal association between two sequences. LSD (Location Square Deviation): measures the degree that the prediction deviates from the label. where is the number of concordant pairs, and is the number of discordant pairs.  

18. EXPERIMENT AND RESULT Result – Overall Perfor mance Route Prediction Result

19. EXPERIMENT AND RESULT Result – Overall Perfor mance Time Prediction Result Measurement : Root Mean Square Error(RMSE), Mean Absolute Error (MAE) and Accuracy within 20 minutes (acc@20).

20. EXPERIMENT AND RESULT Result – Case Study

21. CONCLUSION Try to solve the problem of RTP in the field of instant-logistic. Model multilevel transfer mode of couriers between locations and AOIs . simultaneously predicted the route and time in a multi-task manner. Summarization Propose GAT-e to model the spatial-temporal correlation between nodes in multi-level graph. Overcomes the limitations of sequence-based model . A multi-task decoder equipped with a mask attention mechanism and SortLSTM is designed to simultaneously give route and time prediction.