Timezone: »

 
Poster
A Hierarchical Reinforcement Learning Based Optimization Framework for Large-scale Dynamic Pickup and Delivery Problems
Yi Ma · Xiaotian Hao · Jianye Hao · Jiawen Lu · Xing Liu · Tong Xialiang · Mingxuan Yuan · Zhigang Li · Jie Tang · Zhaopeng Meng

Wed Dec 08 12:30 AM -- 02:00 AM (PST) @
in Poster Session 3 »

The Dynamic Pickup and Delivery Problem (DPDP) is an essential problem in the logistics domain, which is NP-hard. The objective is to dynamically schedule vehicles among multiple sites to serve the online generated orders such that the overall transportation cost could be minimized. The critical challenge of DPDP is the orders are not known a priori, i.e., the orders are dynamically generated in real-time. To address this problem, existing methods partition the overall DPDP into fixed-size sub-problems by caching online generated orders and solve each sub-problem, or on this basis to utilize the predicted future orders to optimize each sub-problem further. However, the solution quality and efficiency of these methods are unsatisfactory, especially when the problem scale is very large. In this paper, we propose a novel hierarchical optimization framework to better solve large-scale DPDPs. Specifically, we design an upper-level agent to dynamically partition the DPDP into a series of sub-problems with different scales to optimize vehicles routes towards globally better solutions. Besides, a lower-level agent is designed to efficiently solve each sub-problem by incorporating the strengths of classical operational research-based methods with reinforcement learning-based policies. To verify the effectiveness of the proposed framework, real historical data is collected from the order dispatching system of Huawei Supply Chain Business Unit and used to build a functional simulator. Extensive offline simulation and online testing conducted on the industrial order dispatching system justify the superior performance of our framework over existing baselines.

Keywords: Optimization · Reinforcement Learning and Planning

Author Information

Yi Ma (Tianjin University)
Xiaotian Hao (Tianjin University)
Jianye Hao (Tianjin University)
Jiawen Lu (Tsinghua University, Tsinghua University)
Xing Liu
Tong Xialiang (Huawei Technologies Ltd.)
Mingxuan Yuan (Huawei Noah's Ark Lab)
Zhigang Li (Tianjin University, Tsinghua University)
Jie Tang (Tsinghua University)
Zhaopeng Meng (School of Computer Software, Tianjin University)

More from the Same Authors