Knowledge-Enhanced Spatial-Temporal Routing Optimization in Last-Mile Delivery

¹ Department of Master of Computer Applications, Nitte Meenakshi Institute of Technology, Nitte (Deemed to be University), Bengaluru, India
² Department of Electronics and Communication Engineering, Siddaganga Institute of Technology, Tumkur, India
³ Department of Visual Communication, Kumaraguru College of Liberal Arts and Science, Coimbatore, India

^* Corresponding author: vmasit@sit.ac.in

Abstract

Currently, last-mile delivery has become a crucial component of modern logistics because accurate planning ensures efficiency and customer satisfaction. Thus, the spatiotemporal graph neural network (ST-GNN) has been applied for traffic forecasting; however, existing methods fail to integrate external knowledge into the process of route optimization. Hence, this paper proposes a Knowledge-Enhanced ST Routing Optimization (KE-STRO) framework that improves predictions and influences route planning. Initially, the input data were collected from courier Global Positioning System (GPS) traces and delivery logs for travel times, OpenStreetMap for road network structures, and external sources to enrich knowledge-based route planning. Then, the data were preprocessed using a Kalman filter, z-score normalization, and spatial join mapping to remove outliers, scale the features, and link the external knowledge with the road network. Furthermore, a knowledge graph is constructed, and its embeddings are fused with ST-GNN outputs using an adaptive gating mechanism to predict time-dependent travel costs. Finally, these predictions were converted into dynamic arc costs and knowledge-aware constraints for the (VRPTW) which were solved using a hybrid optimization module. The proposed KE-STRO outperformed the existing Deep ST Attention Network (DeepSTA) framework in terms of mean absolute error (0.1458).