A Two-stage Learning-based method for Large-scale On-demand pickup and delivery services with soft time windows. (June 2023)

• Record Type: Journal Article
• Authors: Zhang, Ke; Li, Meng; Wang, Jiguang; Li, Yunxuan; Lin, Xi
• Is Part Of: Transportation research. Volume 151(2023)
• Publication Date: 2023-06
• Subjects: Pickup and Delivery Problem -- Deep Reinforcement Learning -- Graph Clustering Model -- Transfer Learning -- Multiple Vehicles; Transportation -- Periodicals; Transportation -- Technological innovations -- Periodicals; 388.011
• DOI: 10.1016/j.trc.2023.104122
• Languages: English
• ISSNs: 0968-090X

Abstract

Highlights: A novel two-stage learning-based method to solve the large-scale pick-up and delivery problems with soft time window. Superior performance in numerical experiments comparing with tradition heuristic methods. Computation time of high-quality solution within seconds even facing the problem of 500 customers. Strong transferability of this method with much less training time and data. Abstract: With the rapid growth of the on-demand logistics industry, large-scale pickup and delivery with soft time windows has become widespread in various time-critical scenarios. This problem has proven to be an NP-hard problem. Hence, the computation time and resources required to solve it increase exponentially with the growth of size. As a result, it is burdensome for the exact algorithm and heuristic method to generate a high-quality solution instantly. Machine learning seems to be a possible option due to the advantage of offline training. However, it is difficult to solve large-scale problems due to the lengthy training time, heavy computational cost, and training instability. Thus, this paper proposes the two-stage learning-based method composed of the clustering stage and the routing stage to tackle this problem. The clustering stage builds upon the attention mechanism by introducing graph convolutional network to the input, which can keep the match of pickup and paired delivery customers and classify them into different vehicles, while the routing stage adopts a well-trained model to generate a route for each capacitated vehicle. Furthermore, the well-trained model is utilized to train another problem inspired by transfer learning. Experiments show that the model, trained on small-scale problems, generalizes well to larger-scale problems, and achieves superior performance compared with the heuristic method and Google OR-Tools, with an extremely short computing time. In addition, the favorable transferability of this model is verified through contrast experiment, which can save a significant amount of training time.