Reinforcement learning for practical express systems with mixed deliveries and pickups

J Chen, Z Zong, Y Zhuang, H Yan, D Jin… - ACM Transactions on …, 2023 - dl.acm.org
J Chen, Z Zong, Y Zhuang, H Yan, D Jin, Y Li
ACM Transactions on Knowledge Discovery from Data, 2023dl.acm.org
In real-world express systems, couriers need to satisfy not only the delivery demands but
also the pick-up demands of customers. Delivery and pickup tasks are usually mixed
together within integrated routing plans. Such a mixed routing problem can be abstracted
and formulated as Vehicle Routing Problem with Mixed Delivery and Pickup (VRPMDP),
which is an NP-hard combinatorial optimization problem. To solve VRPMDP, there are three
major challenges as below.(a) Even though successive pickup and delivery tasks are …
In real-world express systems, couriers need to satisfy not only the delivery demands but also the pick-up demands of customers. Delivery and pickup tasks are usually mixed together within integrated routing plans. Such a mixed routing problem can be abstracted and formulated as Vehicle Routing Problem with Mixed Delivery and Pickup (VRPMDP), which is an NP-hard combinatorial optimization problem. To solve VRPMDP, there are three major challenges as below. (a) Even though successive pickup and delivery tasks are independent to accomplish, the inter-influence between choosing pickup task or delivery task to deal with still exists. (b) Due to the two-way flow of goods between the depot and customers, the loading rate of vehicles leaving the depot affects routing decisions. (c) The proportion of deliveries and pickups will change due to the complex demand situation in real-world scenarios, which requires robustness of the algorithm. To solve the challenges above, we design an encoder-decoder based framework to generate high-quality and robust VRPMDP solutions. First, we consider a VRPMDP instance as a graph and utilize a GNN encoder to extract the feature of the instance effectively. The detailed routing solutions are further decoded as a sequence by the decoder with attention mechanism. Second, we propose a Coordinated Decision of Loading and Routing (CDLR) mechanism to determine the loading rate dynamically after the vehicle returns to the depot, thus avoiding the influence of improper loading rate settings. Finally, the model equipped with a GNN encoder and CDLR simultaneously can adapt to the changes in the proportion of deliveries and pickups. We conduct the experiments to demonstrate the effectiveness of our model. The experiments show that our method achieves desirable results and generalization ability.
ACM Digital Library
以上显示的是最相近的搜索结果。 查看全部搜索结果