A Hierarchical Reinforcement Learning Based Optimization Framework for Large-scale Dynamic Pickup and Delivery Problems
Authors: Yi Ma
Xiaotian Hao
Jianye HAO
Jiawen Lu
Xing Liu
Xialiang Tong
Mingxuan Yuan
Zhigang Li
Jie Tang
Zhaopeng Meng
Venue: NeurIPS 2021 Poster (2021)
Keywords: Dynamic Pickup and Delivery Problem
Logistics
Reinforcement Learning

Abstract: 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.

A Hierarchical Reinforcement Learning Based Optimization Framework for Large-scale Dynamic Pickup and Delivery Problems
Yi Ma Xiaotian Hao'; Jianye Hao 12| Jiawen Lu2, Xing Liu', Xialiang Tong?, Mingxuan Yuan", Zhigang Li', Li',Ju Jie Tang', Zhaopeng Meng' 'College of Intelligence and Computing, Tianjin University (mayixiaootianhao, jianye.hao, ses Izg, mengzp) @ @tju.edu.cn Noah's 's Ark Lab, Huawei, (jiawen.lu, tongxialiang, Yuan. Mingxuan ) @huawei.com TTinghua University, jietang @ ttiinhua.cdu.cn
Abstract
The Dynamic Pickup and Delivery Problem (DPDP) is an essential problem the logistics domain, which is NP-hard. The objective 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 utilize the predicted future orders to optimize each sub-problen further. However, the solution quality and efficiency of these methods are unsatisfactory, especially when the problem scale very large. In this paper, we propose 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 optimize vehicles routes towards globally better solutions. Besides, lower-level agent is designed to efficiently solve each sub-problem by incorporating the strengths of classical operational research- baased methods with reinforcement learning-bast 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 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.
1 Introduction
The Dynamic Pickup and Delivery Problem (DPDP) constitutes an important family of routing problems, which generally contains three key elements: orders, goods and vehicles as shown in Figure Orders are generated in real-time. Different orders contain different types and quantities of goods. A number vehicles are scheduled to serve the orders by transporting the desired goods from different origins to different destinations. The objective of DPDP is to dynamically assign each order to the most appropriate vehicle so that the overall transportation cost (e.g., overall distances) could be minimized. DPDPs are widespread in order dispatching systems of the supply chain, express mail delivery services and elsewhere.
Equal contribution. Corresponding author.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

DPDP is a complex variant of the Travelling Salesman Problem (TSP) and Vehicle Routing Problem (VRP), which are both NP-Hard combinatorial optimization problems 25 The main difficulty of DPDP comes from the dynamically generated orders in real-time, thus the order dispatching decisions cannot be made beforehand an offline style. Besides, compared with TSP and VRP, there exist various additional complex constraints in DPDP such as pickup and delivery constraint, Cast-In-Firs--uu (LIFO) constraint, time window constraint, split demand constraint, etc.
Traditional methods for DPDP. Existing solutions for DPDP fall into two categories.
The first category maintains a fixed buffer to cache the most recent generated orders and periodically dispatches all cached orders in a delayed mode, By this way, the overall dynamic problem is partitioned into a series of static sub-problems with subsets of known orders, Le., static Pickup and Delivery Problems (PDPs). Then, op- erational assearc-bbased (OR)
9:00
1:
Vehicles
Depot
Lead guods
Unload goods
9:30
Dynamically generated orders
Goods
Factories & Warehouses
Figure 1: Demonstration of DPDP
methods [2 20), heuristic and
designed solve each sub-problem. However, myopically optimizing each static sub-problem cannot guarantee the overall dynamic problem could be optimized from a long-term perspective since the split sub-problems are not independent of each other. The main reasons are previous orders assigmment results will influence (I) the number of remaining orders to be dispatched, (2) the vehicle's remaining capacity and (3) the relative positions to the following orders. To acquire better solutions, the second category methods (2 g 12 try to predict the distribution of future orders and take the predicted orders into consideration when computing the solution for each sub bob--roolem.m However, predicting future orders not realistic due to the high uncertainty in the real world. Inaccurate predictions will mislead the order dispatcher and route planner, and result in poor solution quality.
meta-heuristic methods 77 16 25
26 23
Learning-based methods for VRP. Additionally, common flaw of traditional OR and meta- heuristic methods is that they are computationally expensive and normally unable to obtain a desired solution within the allowable time. Besides, the design of them heavily relies on complex domain knowledge. To improve the solution computing efficiency and ease the difficulty of the algorithm design, recently. several learning-basee based methods are proposed (27
6 [3] These methods have demonstrated that the solution computing efficiency can be significantly improved by leveraging the generalization ability of the trained models. Besides, they could obtain solutions with competitive qualities compared with the statc-of-the-ar traditional methods. Although these methods mainly focus on TSPs or VRPs, of which all orders' information known in advance and much fewer constraints are considered comparing with DPDP, learning-based -ased methods have shown great potential to help solve large-scale DPDPs and reach superior performance.
In this paper, we propose a novel hierarchical reinforcement learning (RL) based optimization framework solve the real-world large-scale DPDPs. Considering that order dispatching has long- term impact on the overall optimization objective, the upper-level RL agent dynamically determines whether wait longer at each moment for caching more future orders. In this way, the orders can be more flexibly assigned to vehicles (since each vehicle will have more candidate orders to choose) and the routes of vehicles could be optimized towards globally better solutions. The lower-level RL agent is responsible for assigning the cached orders to the most appropriate vehicles by sequentially manipulating heuristic operators to improve the solution quality iteratively. To verify the effectiveness of the framework, we collected real historical data from the order dispatching system of Huawei Supply Chain and built a simulator to simulate the order dispatching and vehicle transportation process. Further, we deployed our method on the company's ' Supply Chain Business Unit. Extensive offline simulation and online testing showed the superior performance of our algorithm.
Our main contributions are as follows:
2

---

We are the first to propose practical hierarchical RL framework to efficiently and far- sightedly compute superior solutions for the real-world large-scale DPDPs with complex constraints.
We design a simulator using real industrial data to be the experimental benchmark to verify the proposed method, which is available here for interested researchers.
We show that our approach considerably improves the optimization objectives compared with existing algorithms both in the offline evaluation and online testing. The ablation study indicates our approach can obtain high-quality solutions with fast running speed and has strong generalization ability.
2 Problem Formulation
We now give the formulation of DPDP in our logistics scenario. For the orders dynamically generated in real-time at different nodes (i.e., factories and warehouses) within a day, vehicles should be scheduled to transport the goods from pickup nodes to delivery nodes fulfil the orders with minimal transportation cost. In our case, the objective is to minimize K vehicles average travelling distances D(K) of the entire DPDP:
min D(K)
while meeting several constraints: Pickup and Delivery Constraint, Capacity Constraint, LIFO Constraint, Time Window Constraint, etc. Detailed constraints are shown in Appendix A
In practice, however, some orders are destined to violate time window constraints Thus, we add it the objective function as an associated penalty to convert the hard time window constraint a soft one. The penalty function is defined as the overtime beyond the specified completion time of each order. The optimization objective is then reformulated as minimizing the weighted sum of average vehicles travelling distances (kilometers) D(K) and total overtime (seconds) OT of all orders C:
2
min D(K) + À OT(C)
Apart from the various complex constraints mentioned above, the additional difficulties of this problem mainly come from two aspects:
(1) The problem scale is very large. In practical logistic scenarios of the company, millions of products and intermediate materials are manufactured every day. As these products and materials might be used in the subsequent phases (e.g., assembling or selling), they have to be scheduled and transported between hundreds of factories and warehouses by dozens of vehicles within stringent timeline constraints, which constitutes a very large-scale and complex DPDP.
(2) Besides, as the orders are generated online in real-time, the schedule planning cannot be made aforehand in an offline style. From the oracle's point of view, i.c., when all orders of a day are known in advance, the uncertainty is climinated and this DPDP can be formulated complex Mixed Integer Programming (MIP) Problem, of which the optimal solution could be obtained utilizing exact algorithms (e.g., cutting plane algorithms, branch-and- bound algorithms or modern solvers such as Gurobi (20) [22]. However, in reality, it's impossible to know all the orders in advance, thus these approaches are not applicable.
To eliminate the uncertainties brought by the unknown orders, a practical way is to utilize a buffer to cache the most recent generated orders and periodically dispatches all cached orders in little delayed mode. With the known orders in the cache, the static PDP can be formulated as an MIP as shown in Appendix A We could resort to modern solvers to solve this MIP. However, even for the static PDP with very few orders, it still costs several hours to compute a feasible solution, which is beyond the acceptable limits (details are shown in Table and 3). Besides, even if we could obtain the optimal solution for each fixed split static PDP, still cannot guarantee the global DPDP can be optimized as these static sub-problems are not independent each other.
For example, goods of order need to be transported to far destination in short time. Even if vehicle used to serve order as soon as the order is generated, violation of time window constraints can occur. 'If the overtime happens, the subsequent assembling and selling will be delayed or cancelled, resulting in great economic loss. Therefore, set À very large number, e.g., 10000, severely punish the overtime.
3

---

3 Method
3.1
Overall Framework
New Orders 0,1
New Orders 0,
New Orders O1
Opa
Order Buffer
Releuse
Relrace
Release
Remaining Orders
DQN
DQN
DQN
O
Releuse
Release
Release
feok
Get Initial solution for current static problem
Upper-level geent
Lower-leved gent
Best solation
Improve the solution
Order Dispatching System
iteratively
Figure 2: Hierarchical Optimization Framework
In this paper, considering the challenges mentioned above, we propose novel hierarchical rein- forcement learning based optimization framework, which contains two levels of agents. As shown in Figure 2 we maintain a buffer cache the newly generated orders and periodically dispatch all cached orders at once. But instead of dispatching the cached orders of fixed numbers or predicting future orders, we design an upper-level agent to dynamically determine whether to wait longer for caching more future orders at each moment. Though waiting longer will postpone the dispatching and transportation of the earlier cached orders, additional future orders can be taken into account for the vehicle-order matching. In this way, each vehicle will have more candidate orders to choose, thus the overall travelling distances will be more potentially to optimized for shorter") This process could be regarded as sacrificing little time in exchange for precise estimation of future orders. However, waiting for too long will also increase the risk of overtime the earlier cached orders. Thus, whether to wait longer to cache more orders each moment will have a long- tergttermmn impact on the overall dispatching results, and can be naturally modeled as a sequential decision problem. We model this procedure to wait longer at each moment, the overall DPDP can be dynamically partitioned into a series of static sub- arooprolems, each of which includes different numbers of orders. As shown in Figure [2] the generated orders are accumulated in the buffer until the upper-level agent decides to stop caching at time 4+ Then, the agent releases the cached orders to the lower-level agent and clears the buffer.
whether Markov Decision Process (MDP). Depending
Given the released orders (which form a static sub-problem, i.e., a PDP), the lower-level agent appointed to assign the orders to the most appropriate vehicles and arrange the transportation route of each vehicle, such that the transportation cost of these orders could be minimized. First, a set of basic operators maintained, whose roles are converting one feasible solution to another. For instance, given an initial solution's 's route (A->B->C) with three nodes A, B and C, a typical operator is swapping [3]. the travelling cost of (B->A->C) is less than (A->B->C), the initial solution is improved. On this basis, design the lower-level agent similar the traditional meta- heuristic algorithms which sequentially manipulates these operators to improve the solution of each PDP. The difference is that model the process of sequentially manipulating these operators MDP and incorporate RI methods to optimize the policy instead of manually designing complex rules. Finally, the best found solution is adopted by the order dispatching system to assign the orders to the vehicles and arrange their transportation routes. In the following two subsections, we will go into more details of the designed two agents.
converted to (B->A->C). e.g., swapping A and B. After applying this operator, (A->B->C) is
'In Table of Appendix I time spans will lead different qualities of solutions
we show that splitting the overall DPDP into different sub problems with different

---

3.2 Upper-level Agent
3.2.1 Workflow
The workflow of the upper-level agent is described in Figure 2 We partition a day into T = 144 fixed time intervals, and the time span of each interval is ten minutes. Each time interval starts at time 4-1 and ends at time 44, i < T is a positive integer. We name (,,..., 44, LT as decision points. At each decision point 1,, the upper-level agent decides whether release the accumulated orders the lower-level agent according to their overtime risk. Taking Figure 2 as an example, at decision point 4-11. the buffer already cached some orders 0;- At f.-1. the upper-level agent makes a decision and determines to wait longer and not to release O,-1 to the lower-level agent. Thus 0;-1 are still maintained in the buffer. Thereafter, all decision points before f,+8, the upper-level agent makes the same decisions as at f4-1, i.e., 'not release'. Therefore, new generated orders (O:.... Oi++) between 1 and f are all appended the buffer as well. At & the upper-level agent makes a change and determines to release all accumulated orders (O;-1. Oz. ..... Os+k) to the lower-level agent. At this time, all accumulated orders together with the remaining orders O Oremain (assigned to the vehicles before 4-11 but the goods of the orders are still not loaded onto the vehicles even at 44++) will be released by the upper-level agent. In this way, we get static sub-problem constituting of orders (O,-1, Oi.... ..... Ou+k, Oremain) for the lower-level agent. By analogy, the overall DPDP can be divided into a series of static PDPs with different scales. We model the procedure whether to wait longer at each decision moment an MDP described in the following subsection.
3.2.2 Markov Decision Process (MDP)
State: The state includes the number of orders accumulated in the buffer, the number of available vehicles, the amount of time left before exceeding the time limit of each order, etc. All these features are normalized and concatenated together. Detailed descriptions are postponed to the Appendix due to the space limitation.
Action: The action is a binary variable indicates whether to release orders to the lower-level agent.
Reward: Our ultimate goal is to minimize the optimization objective for the entire dynamic problem. Therefore, we first get the the overtime of the orders completed and the corresponding vehicle travelling distances between two consecutive decision moments 4:-1 and 4 as shown in Figure 2 i.e., avgaavagaaaaoa diittditeeceeee + À overtime. Then We set the immediate reward of action executed 4-11 as -(avg_ distance + X overtime). By this rule, the sum of the immediate rewards forms the negative value of the total objective for the entire dynamic problem. With this reward, the overall objective for the entire dynamic problem could be optimized. In other words, we encourage the upper-level agent to optimize the overall dynamic problem from long-term perspective when making decisions.
3.2.3 Agent Model
For the upper-level agent, we use Deep Q Network (DQN) [17]. We parameterize a value function Q (xx a; Φi) using the deep neural network of MLPs in which di are the parameters of the Q-network at updating iteration 1. When reaching decision point 4, we obtain the state St,, action at,, and reward rt; according to Section 3.2.2 for the current static problem and save them the replay buffer. When reaching decision point 4+11 we obtain the state $1,41, which is the next state of the previous
static sub- buob-problem and we get new transition e₁2 (st. Qt Fits St.mi). ). We store the transitions during the running of simulator. During the training, we apply Q-learning updates on uniformly sampled transitions (s, a, r, r²) ~ U(D) from the replay buffer. The model updates at iteration | uses the following Temporal Difference (TD) loss function:
into buffer D = {Ety.-... (et......ft......
[1+ m (5'. Q((, - 27
Li (0i) = (ssanns
(3)
where 7 is the discount factor, or are the parameters of the Q-network iteration I and o7 are the parameters of the target network at iteration I.
5

---

Max Steps or Max Running Time
Initial Solution
Improved Solution
Improve
Reconstruct
Improve
Reconstruct
Iteration
Ieration N
Lover-level
Figure 3: Workflow of Lower-level Agent
3.3 Lower-level Agent
3.3.1 Workflow
The workflow of the lower-level agent described in Figure We first generate a feasible initial solution of the static sub-problem using greedy algorithm (described in Section 4.2). Given the initial solution, the lower-level agent iteratively improves the solution by manipulating different operators according to solution states mentioned in Section 3.1 (we call this step Improvement [6 [3).. When the improved solution reaches local optimum (i.e., the solution could not be improved further for series of steps), will partially entirely re-assigning the orders using the greedy algorithm (we call this step Reconstruction) The improvement of the next iteration will start from the reconstructed solution. Note that the lower-level agent only selects improvement operators as reconstruction operator has a long-lasting effect on solutions compared with improvement operators and found mixing up them will lead to instability during the training. The process of improvement and reconstruction alternates until reaching the maximum number of steps or the maximum allowable running time. The best generated solution during the improvements and reconstructions will be adopted to dispatch orders to vehicles. Note that the final accepted solution is ensured to be at least as good as the initial solution. Overall, by transferring the knowledge learned from previously solved PDPs to the new ones, the agent could efficiently and monotonically improve the solution quality. The MDP definition of the operators- mantitorrmmmiiplattiing procedure is described in the following subsection.
3.3.2 Markov Decision Process (MDP)
The state the current solution consists of the states of all nodes, i.e., s - 82, ..., 8 v where is the state of node Each includes the position information, order information, vehicle information and objective-related information. Details can be found in Appendix
State:
Action: The action set consists of 4 carefully designed operators, i.e., inmer-exchange, inner-relocate, inter-exchange and inter-relocate. We provide a proof in Appendix G that any feasible solution (including the optimal one) could be obtained by iteratively applying these 4 operators from any given initial solution. Details are described in Appendix G
Reward: We find that the total objective can be easily reduced by a large margin during the first few improvement steps of initial solution reconstructed solution in the experiments (See Figure 4... If we assign the actions at these improvement steps large reward, it's not fair for the actions in the subsequent steps. This is because the actions in the subsequent steps also play important roles in improving solutions in the complex solution space. Therefore, the overall objective OBJ, of the sub-problem after the first iteration (e.g., Iteration in Figure 33) is used as the baseline following [13] For each subsequent iteration i, we first get the optimized objective after the iteration as OBJ; and then assign (JOBJ, OBJ,))/m n, to all n; actions executed in iteration as reward.
3.3.3 Agent Policy Network
The policy network of the lower-level agent inputs the state of the current solution and outputs action probabilities of length A where A is the set of operators. In our case, a critical challenge of designing the policy network is the number of orders and the number of available vehicles are different for each static sub-problem. As the quantity of the combination of orders and vehicles are extremely huge, we cannot train a separate model for every combination of different numbers of orders and vehicles. Thus, the desired model should be able to transfer the knowledge learned from the previously solved

---

problems and generalize to new problems of any scale without fine-tuning, Besides, the routes of a solution naturally form certain topological graph structure as shown Figure Therefore, in this paper, we incorporate GIN (Graph Isomorphism Network) B0], powerful Graph Neural Network (GNN), to be the basis of the policy network of the lower-level agent. We use the REINFORCE algorithm [28] to train the policy network. Details of the policy network are shown in Appendix H
4 Offline Evaluation
4.1
Experiments Settings
We start with designing a simulator to shed light on the contributions of the proposed framework under more controlled settings. Details of the simulator can be found in Appendix To comprehensively verify the effectiveness of our approach on problems of different scales, we use four types of datasets of different sizes, i.c.. 15 orders with 5 vehicles, 50 orders with 5 vehicles, 300 orders with 20 vehicles, 1000 orders with 50 vehicles (matching the practical problem of thousand scales). Note that the orders/vchicles ratios are set according to realistic business settings. Each type of datasets contains 10 datasets, including 7 training sets and 3 test sets according to the ratio of 7:3 (e.g.. 300-1, 300-2 and 300-3 are test sets with 300 orders). The vehicles have the same load capacity. Details of the datasets are described in Appendix D According to the realistic business settings, the time span between two consecutive decision points is set to 10 minutes the simulator.
The comparisons of different methods proceed as follows. For our approach, we first train a shared model on each type of training datasets and then evaluate the model on the test datasets of the same size. At each decision point, the upper-level agent decides whether to release orders to the lower-level agent. The lower-level agent is executed for no more than 10 minutes after receiving orders from the upper-level agent. Both agents are trained simultancously. This training process is relatively stable due to the following reasons. The iterative solution optimization process (starts from an initial greedy solution) of our lower-level agent can ensure the obtained solutions have relatively high quality even at the initial training stages. In other words, the solutions given by the lewer-level agent are relatively stable. Therefore, the unstable issue of co-training both levels of policies in our case is negligible, and thus both levels can trained simultaneously. For baselines showed in Section 4.2 we also run them for up to 10 minutes at each decision point. We run the simulator until all the orders of the dataset are dispatched and completed to ensure fair comparisons. All the results in the experiments are obtained by running each algorithm ten times to get the mean and variance value of the optimization objective.
4.2 Baselines
To help readers better understand the baselines, we name them in the format of 'upper-level method + lower-level method' except for the Optimal baseline. '10min-Interval means the dynamic problem is partitioned into static sub- problems with fixed interval of ten minutes. Morder-Interval means the dynamic problem is partitioned into static sub-problems consists of a single order.
10min-Interval Greedy: Greedy [15] is the most widely-used method in industry, which is also the online deployed baseline method. The solution routes are expanded by greedily inserting new pickup and delivery nodes until all the orders are inserted.
10min-Interval ALNS: ALNS 29 is one of the most representative meta- heda-hheriisic local search frameworks for solving DPDP that uses series of operators to improve the solution. In each iteration, an operator selected to destroy the current solution, and an operator selected to repair the solution.
lorder-Interval + E2ERL: According to [14, we use a DQN model to assign vehicles to each generated order and insert each order into the vehicle's 's order queue using the Greedy algorithm. It's an E2ERL (end-to-end RL) algorithm.
10min-Interval + ST-DDGN: ST-DDGN 12 is the state-of-the-ar method that predicts future orders of DPDP. Then both the predicted orders and real generated orders are considered when solving each sub- problem using E2ERL.
Optimal: We convert DPDPs to static PDPs as we can obtain all the orders' information beforehand in offline style. Then we use Gurobi to solve the corresponding MIP model to get the optimal solution. As Gurobi can only solve small-scale PDPs within acceptable time due to the NP-hard property, we only compare with the optimal solution problems of 15 and 50 orders in Section 4.4.1
7

---

4.3 Main Results
Here we show part of the experimental results in Table I The com- plete results are shown in Table 6 of Appendix I The objective improve- ment measurement is the improvement percentage of each algorithm com- pared with the Greedy algorithm. Our ap- proach consistently out- performs all baselines
Table 1: Main results of different methods on test datasets
Dataset
Algocithm
Overtame
Avg Dis
Oboective
Oby
TOmen- Interval Croedy
30
lorder-interval E21RL
96.55
50-1
10min-Intaraal ALNS
107.95
107.95
1.245%
10nin-latervall + ST-DIGN
0
108:95
108.95
0.324
Our (U @Upperlevel RL. Lower-leve RE.
93.70
93.70
14.27%
Maner- Fiterva + Cinaly
0
147.75
147.75
lurder Interval E2ERL
158.39
158.39
-7.18%
500-1
10min-Interval ALNS
137.31
7,08%
10min-Interval- ST-DDGN
131,99
10.68%
Our (Upeer-leel RL Lower-lerd RL)
122,42
17.16%
10man Exteraal Creedy
183.04
18300
0.007%
lorder-luterval E2ExL.
180.56
180. 36
1.46%
1000-1
10min-Inicrval + ALNS
174.68
174.68
4.57%
1Dmin-luterval + ST-DDIN
171,09
171 111.09
6,534
Our (U Upper-level RL Lower-level RL)
159,18
159,18
13,04%
on all datasets (lower total objective is better). On some datasets, the baselines have overtime results due to their lack of long-term planning and exhaustively optimization of each static problem from a myopic perspective. As a result, dispatching of some orders is delayed for too long, and finally, overtime is inevitable in any case. In contrast this, our upper-level RL partitions the dynamic problem into sub- uub-problems considering the balance between the orders overtime (seconds) risk and optimization of vehiele travelling distances (kilometers), and our lower-level RL is responsible for the optimization of each static sub-problem. The cooperation of the two agents enables our method to find solutions with less overtime and vehicle travelling distances on the overall dynamic problem from a long-term perspective. The comparison of the learning curves of all learning-basee methods on 50-1 are shown in Figure I1 in Appendix [
4.4 Ablation Studies
4.4.1 How far is our lower-level agent from the optimal one on static PDP?
We convert the DPDP assigned to vehicles all at once, there is no need to use upper-level agent. Similarly, without the prediction of future orders, ST-DDGN essentially the same as E2ERL. Therefore we only use the lower-level agent and E2ERL in the static PDP. Each algorithm is run without time or step limitation to discover its full potential. As shown in Table 3 the difference of the total objective of our method with the optimal solution is much smaller than the baselines (as all the overtime is O, the column is omitted from the two Tables). The time consumption is much shorter than ALNS and Gurobi. It is because our method can exert the generalization ability to quickly improve the initial solution by using the most appropriate operators based on the experiences obtained from training, without the need of manually designing complicated search as in ALNS and Gurobi. Note that the time consumption of Gurobi on problems of 50 orders is represented using hyphen symbol '-', which means can't 't get results even after 100 hours due to the various complex constraints as described in Appendix [A] Comparing with baselines, our method is the most qualified to meet the online deployment requirements that the algorithm should obtain high-quality solutions with fast speed.
single static PDP as described in Section 4.2 As the orders should be
Table 2: Results on static 15-1, 15-2, 15-3
Table 3: Results on static 50-1, 50-2, 50-3
Algonitam
Avg. Dis
Obyoctive
Ubj Impro
Time
Algurithm
Avg Dis
Objective 93.68
Obi Impgro
Time
Greedl
33,85
$3.85
0.002
0,38s
Grerdy
95.68
0.00%
66.75
E2ERL
$1.70
3.99%
0.58%
E2ERI.
3.79%
52
AL.NS
51.58
51.58
4.225
40%
ALNS
96.88
96.98
1.72%
10728
(1 (Lower-devl RL)
Our
45.72
45.72
15.10%
68,21s
(Lower-level RL.)
Our
82.43
82.43
16.47%
1459.23
Optimal
41.35
$1.35
17.6F%
141360s
Optimal
Greedl
0.10s
Oneedy
22.27%
EZERL
68:00
68.00
2.31%
0.79,
EZERL
76.04
76.04
5.74%
16
ALNS
62.62
62.62
10.04%
6016
ALNS
65.31
65.31
19.04%
6012 566
(Lower-level RL)
Our
62.32
62.32
10.47%
27.96s
(Lower-level RE,
Our
58.42
58.42
27.58%
1152,64s
Optimal
$7.48
17.43%
193680s
Optimal
Greedy
78.75
78.75
0.002%
0.34s
Ureedy
83.31
83.34
0.00%
44.31s
EZERL
59.02
59.02
25.03/%
0.83s
E2ERL
80.92
80.92
2,90%
20.35 20.34%
ALNS
52.21
52.21
33 689
920k
ALNS
80.51
80.51
3.40%
4140. 1.40.154
(Lower-level RL)
Our
50.95
50.95
35.29%
71.98s
(Lower-level RL)
Our
12.81%
1998.09s
Optimal
50.75
50.75
35.54%
28651s
Optinal
8

---

4.4.2 Does lower-level agent learn how to select operators?
To verify that our lower-level agent learns to choose the most suitable operators at different states, we compare the results of different operator selection methods on both static problems and dynamic problems. We first compare the total objective during the solution improve- ment process on the static problems using the lower-level agent with the method that randomly iteration process designed in Section 3.3
selects operators. As the improvemeen--reconstin ensures the quality of the solution can be monotonically improved, selecting operators ran- domly is also powerful baseline that can achieve satisfactory performance for the static PDP. Therefore, for the static problem, mainly focus whether the lower-level agent can improve the solving speed. As we see in
actions
Totel Clopetur
Ro mit
Figure 4 at the same step, choos-
ing operators using lower-level RL
can reach a better objective than ran-
domly choosing operators, which
indicates our lower-level method learned to accelerate the searching for better solutions. Since the static sub-pnt sub-problems of dynamic problem are not independent of each other, the small gap between the above two methods in static sub-problem will continue to enlarge in the subsequent sub-problems, resulting in a very large result gap on the entire dynamic problem. We compare the total objectives of the entire dynamic problems in Table 4 To ensure fairness, we control the upper-level methods to be 10tinnInterval and use the lower-level agent and random selection as lower-level methods, respectively. As we can see in Table 4 using the lower-level agent can help find better solutions on the entire dynamic problems.
106
153
200
282
(a) 50-1
(b) 50-2
(c) 50-3
Figure 4: Comparison of different selection methods of opera- tors on static problems
4.4.3 Does the upper-level agent learn to partition DPDP from a long-term perspective?
To verify that our upper-level agent
Table 4: Effectiveness of lower-level agent and upper-level agent
Overtime
Objective
Obj Impro
learns to partition the dynamic prob- lem into static sub- problems from a long-term perspec- tive, we compare the results of differ- ent static sub-problems partitioning methods. We compare our upper-level agent with the '10min- Interval' method. As we can see in Table 4 using an upper-level agent to partition the dynamic problem reaches the best objective. The results illustrate that our upper-level agent can partition the problem from a long-term perspective to balance the orders overtime risk and optimization of vehicle travelling distances.
300-1
10min Interval + Lower RL
Inter-lntervall Kandom Search
0
0
126.95 1: 4.50
139.18 #: 8.59
126.95
139.16
0.00%s
8.77%
Our (1. pper--lll RI. Lower-levd RL.)
0
122.42 = 4.02
122.42
12,03%
Tümis- Inkerval Randon
10.20
166.11
0.00%
10min-Interval Lower-lvell RI.
154.30 8.13
30
7.17%
Our (Upper-lerel RL. Lower-level RL.
0
142.33
7.47
142.33
14.42%
300-3
10min Interval Lower-level RL.
Interval Random Search
0
188.69 + 7.70
158.04 4: 7.50
156.64
168.09
7.14%
0.00%%
(Upper-level RI. Lowes-levd RI.)
146.88
12.93%
4.4.4
Can our method generalized to larger-scale problems?
To verify our method's generalization ability, we evaluate the models trained using datasets of 300 orders/ / 20 vehicles on larger-scale datasets, i.e., 1000 orders / 50 vehicles. As shown in Table 5] the model trained on datasets of 300 orders achieves similar performance with the one trained on datasets of 1000 orders. Note that the model trained on datasets of 300 orders also outperforms the baselines in Table It
Table 5: Generalization verification
Dataset
Model
Overtime
Avg_Dis
Objective
1000-1
Tramedd on 1000
159.18
159.18
Trained on 300
10.27
170.78
Tramed on 1000
196.66 1 9.52
196.66
1000-2
Trained on 300
209.48 8.68
209.48
Tramed on 1000
176.39 7.61
176.39
1000.3
Trained on 300
182.83 5.61
182.83
verifies that our method can be generalized to new problems of different scales without fine-tuning after well trained on existing problems.

---

Online Testing
We deployed our method on the order dispatching system in Huawei supply chain. the online experiments, we pare our method with the pre- viously online deployed greedy algorithm (10min-Interval + Greedy). For fair compar- ison, we control the vehicles and the nodes (factories and warehouses) involved in the online testing to be the same.
100%G-
1000
400
5000
530
299022
Averge Ove sue (ecoadd)
2003
1800.41
Ovds Nan
6030
1634.3
11231
0221
1:00
200
4030-
1583
1607
1167
116
Order Nun
Averngo (scoodo)
Averago Disunces (sntes)
Normally, a standard A/B test- ing required be performed on homogeneous experimental groups using different methods at the same time dimension. Then experimental data of each group are collected and evaluated to choose the best method. However, in our situation, it's unrealistic to split each order into two sub-orders to ensure the experimental groups are homogeneous, Besides, a large number of offline experiments have demonstrated that our method is significantly better than the greedy algorithm. Even in the worst case when there is no improvement in each sub-problem, our method is still the same with Greedy. Thus, we directly replaced the greedy algorithm for online deployment. Figure summarises the results from Nov 2020 to Apr 2021. The points of Nov and Dec 2020 shown in Figure [] are generated by greedy algorithm and our method deployed from Jan to Apr 2021. As we can see, method can reduce the average orders' overtime and vehicles' travelling distances compared with the greedy baseline. Even with more orders, our method can still reach a better optimization objective. Note that in the actual business scenario, orders generated in each day follow similar distribution with a small variance. These results indicate that our method could achieve a better performance in the realistic deployment environment with varied data distributions.
2020 11, Greedy 3029.12, Greedy 2021 OL, 2021 02, Our
2021,61,0 2021 ONk
Figure 5: Online Results
Conclusions
In this paper, we propose a novel hierarchical reinforcement learning based optimization framework to solve the large-scale DPDP in the real world. The upper-level agent is equipped with the far far-sight ability whose target is to optimize the long-term cumulative objective. The lower-level agent exerts the generalization ability of GNN to quickly improve the solution quality by transferring the knowledge (policy) learned from training. The cooperation of the upper-level and lower-level agents enables method find globally better solutions. Extensive offline simulation the simulator built real historical data and online testing verify that our method can obtain higher-quality solutions with faster running speed.
The core idea of our learning-based framework are beneficial a number of similar problems supply chain community that have time-evolving components (e.g., orders/customers/assk)) such as dynamic routing problems, dynamic flow shop scheduling, dynamic job shop scheduling, dynamic bin packing and so on. As orders/customerr/ttskk of all these dynamic problems that are not known a priori, the orders/customerrsuskk should first be cached and then be dispatched. In this way, these problems can be modeled hierarchical optimization problems like DPDP that the upper-level problem is "how to cache onders/customerr/aaskss and the lower-level problem "how to dispatch cached onders/customerr/taskss"" We will verify proposed framework in these fields in the future work.
online generated
Acknowledgments and Disclosure of Funding
The work is supported by the National Natural Science Foundation of China (Grant Nos: U1836214) and the New Generation of Artificial Intelligence Science and Technology Major Project of Tianjin under grant: 19ZXZNGX00010.
10

---

References
[1] Irwan Bello, Hieu Pham, Quoe V Le. Mohammad Norouzi, and Samy Bengio. Neural combinatorial optimization with reinforcement learning. arXiv preprint urXiv:1611.0900 2016.
[2] Enrique Benavent, Mercedes Landete, Enrique Mota, and Gregorio Tirado. The multiple vehicle pickup and delivery problem with lifo constraints. European Journal of Operational Research, 24363)7752-762, 2015.
[3] Gerardo Berbeglia. Jean-François Cordeau, and Gilbert Laporte. Dynamic pickup and delivery problems. European journal of operational research, ()::81)8155..) 2010.
[4] Francesco Carrabs, Jean-François Cordeau, and Gilbert Laporte. Variable neighborhood search for the pickup and delivery traveling salesman problem with lifo loading. INFORMS Journal on Computing. 19 (4):618-632, 2007.
[5] Brenda Cheang, Xiang Gao, Andrew Lim, Hu Qin, and Wenbin Zhu. Multiple pickup and delivery traveling salesman problem with last-in- fast-in-first-ou first-out loading and distance constraints. European journal of operational research, 223(1):60-75 75, 2012.
[6] Xinyun Chen and Yuandong Tian. Learning to perform local rewriting for combinatorial optimization. In Hanna M. Wallach, Hugo Larochelle, Alina Beygelzimer, Florence d' A'chh-Bhuuc Emily B. Fox, and Roman Garnett, editors, Advances in Neural Information Processing Systems 32: Annual Conference Neural Information Processing Systems 2019, NeurlPS 2019, December 8-14, 2019, Vancouver, BC. Canada, pages 0278-6289 2019. URL https:// http:p/:///oooeeings...se wwt.rrppp.ccpppppp/////// 01080000444444400111144eeee..
[7] Michel Gendreau, Francois Guertin, Yvan-Vves Potvin, and René Séguin. Neighhorhood search heuristics for dynamic vehicle dispatching problem with pick-ups and deliveries. Transportation Research Part C: Emerging Technologies, 14(3):157-174, 2006.
[8] Gianpaolo Ghiani, Emanuele Manni, Antonella Quaranta, and Chefi Triki, Anticipatory algorithms for same-day courier dispatching. Transportation Research Part E: Logistics and Transportation Review, 45 (1):96 106, 2009.
[9] Péter Györgyi and Tamás Kis. A prohabilistic approach to pickup and delivery problems with time window uncertainty. European Journal of Operational Research, 274(3):909-922 2019.
[10] Matheus Nohra Haddad, Rafael Martinelli, Thibaut Vidal, Simone Martins, Luiz Satoru Ochi, Marcone Jamilson Freitas Souza, and Richard Hartl. Large neighborhood based metaheuristic and branch-and braric-and-price for the pickup and delivery problem with split loads. European Journal of Operational Research, 270(3): 1014-1027, 2018.
[11] Farzaneh Karami. Wim Vancroonenburg, and Greet Vanden Berghe. A periodic optimization approach to dynamic pickup and delivery problems with time windows. Journal Scheduling, 23(6)711-7331 2020.
[12] Xijun Li, Weilin Luo, Mingxuan Yuan, Jun Wang, Jiawen Lu, Jie Wang, Jinhu Lv, and Jia Zeng. Learning to optimize industry-scale dynamic pickup and delivery problems. 37th IEFF International Conference on Data Engineering. 2021.
[13] Hao Lu, Xingwen Zhang, and Shuang Yang. learning-based iterative method for solving vehicle routing problems. In 8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020. OpenReview.net, 2020. URL httL:httts/:/:/eneee
wwt. 1d-3.ee333 YDH
[14] Hongzi Mao, Malte Schwarzkopf, Shaileshh Bojja Venkatakrishnan, Zili Meng, and Mohammad Alizadeh. Learning scheduling algorithms for data processing clusters. In Proceedings of the ACM Special Interest Group on Data Communication, pages 270-288. 2019.
[15] Snežana Mitrovié-Ming and Gilbert Laporte. Waiting strategies for the dynamic pickup and delivery problem with time windows. Transportation Research Part B: Methodological, 38(7)6335 655, 2004.
[16] Snezana Mitrovie-Minie, Ramesh Krishnamurti, Gilbert Laporte, et al. Double-horizon based heuristies for the dynamic pickup and delivery problem with time windows. Transportation Research Part B: Methodological, 3888)6669688, 2004.
[17] Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A Rusu, Joel Veness. Mare G Bellemare, Alex Graves, Martin Riedmiller, Andreas K Fidjeland, Georg Ostrovski, et al. Sluman-leve control through deep reinforcement learning. nature, 518(7540):529-553 5333, 2015.

---

[18] MohammadReza Nazari, Afshin Oroojlooy. Lawrence V. Snyder, and Martin Takác. Reinforcement learning for solving the vehicle routing problem. In Samy Bengio, Hanna M. Wallach, Hugo Larochelle. Kristen Grauman, Nicolò Cesa-Bianchi, and Roman Garnett, editors, Advances in Neural Information Processing Systems 31: Anmual Conference on Neural Information Processing Systems 2018, NeurIPS 2018, December 3-8, 2018, Montréal, Canada, pages 9861 9871, 2018. URLhttps: htttps://pooceddigg// neurips wwtpccppppppppeeeeeec / 201 Baaas///ashh/// wtt///aahhaaa/ee1eeeeee ott.e4655..052ooooooaaaaaaaaoe.. e0b0395550 Abstract.
[19] Macick Nowak, Özlem Ergun, and Chelsea C White III. Pickup and delivery with split loads. Transportation Science, 42(1 ):32-43, 2008.
[20] GUROBI OPTIMIZATION, Inc. gurobi optimizer reference manual, 2015, URL: http://www. gurobi. com, page 29, 2014.
[21] Bo Peng, Yuan Zhang, Zhipeng Lü, TCE Cheng, and Fred Glover. A learning- based memetic algorithm for the multiple vehicle pickup and delivery problem with lifo loading. Computers & Industrial Engineering, 142:106241, 2020.
[22] Martin Savelshergh and Marc Sol. Drive: Dynamic routing of independent vehicles. Operations Research, 4644))474-490, 1998.
[23] Zhiyuan Su, Wantao Li, Jicao Li, and Bin Cheng. Heterogeneous fleet vehicle scheduling problems dynamic pickup and delivery problem with time windows in shared logistics platform: formulation, instances and algorithms. International Journal of Systems Science: Operations & Logistics, pages 1-25, 2021.
[24] Barrett W Thomas. Waiting strategies for anticipating service requests from known customer locations. Transportation Science, 11333319-331, 2007.
[25] Paolo Toth and Daniele Vigo. Vekicle routing: problems, methods, and applications. SIAM, 2014.
[26] Marlin W Ulmer, Barrett W Thomas, Ann Mclissa Campbell, and Nicholas Woyak. The restaurant meal delivery problem: Dynamic pickup and delivery with deadlines and random ready times. Transportation Science, 55(1):75-100, 2021.
[27] Oriol Vinyals, Meire Fortunato, and Navdeep Jaitly. Pointer networks. In Corinna Cortes, Neil D. Lawrence, Daniel D. Lee, Masashi Sugiyama, and Roman Garnett, editors, Advances in Neural Information Processing Systems 28: Annual Conference Neural Information Processing Systems 2015, December 7- 12, 2015, Montreal, Quebec, Canada, pages 2692-2700, 2015. URL httpaattttt//// //popeeddi///o neurips i Abstraatt-bbrattttt...a
[28] Ronald J Williams. Simple statistical gradient-foloowigg algorithms for connectionist reinforcement learning. Machine learning, 8(3-4):229-255 1992.
[29] David Wolfinger. A large neighborhood search for the pickup and delivery problem with time windows, split loads and transshipments. Computers & Operations Research, 126: 10.
[30] Keyulu Xu, Wcihua Hu, Jure Leskovee, and Stefanic Jegelka. How powerful are graph neural networks? In 7th International Conference on Learning Reprexentations, ICLR 2019, New Orleans, LA, USA, May net
6-9, 2019. OpenReview.ned 2019. URL http:////ppppreeeeeeeeeeee/oaaap
12


Reviews:
[{"review_id": "uU_6aTQi6bb", "reviewer": "Reviewer_8RBm", "summary": "The authors propose an approach to solve the Dynamic Pickup and Delivery Problem. The main challenge of this problem is that the orders are not known a priori. To solve this, the authors propose a bi-level approach composed of: (1) an upper-level agent to decide whether to solve the problem for current orders in a cache or to wait for new orders, and (2) a lower-level agent based on a Graph Isomorphism Network to solve the problem. Both agents are trained using classical reinforcement learning techniques. According to the results, this approach improves state of the art by showing superior performance over existing baselines for DPDP.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The authors propose a novel approach to solve DPDP based on a bi-level structure which combines well-known techniques from reinforcement learning with Graph Isomorphism Networks to model the problem. The upper-level agent, which is responsible of the decision to wait for new requests, is what distinguishes their approach from previous ones, which are well explained and adequately cited. The authors claim to achieve superior performance over existing baselines, which is supported with an exhaustive experimental analysis on data generated by simulations based on real data. Results are confirmed to be consistent with further experimentation on real-time data. \n\nDespite the authors study the ability of their approach to generalize to a different problem size, the ability to generalize to different distributions is not evaluated (data from the simulations and real-time data are likely to have the same distribution).\n\nThe paper is clearly written, except for small details listed here: (1) In section 3.2.1 it is not clear where remaining orders come from. (2) Section 3.3.1 does not make clear why reconstruction is needed after the lower-level agent reaches a local optimum. (3) In section 4.3 authors do not specify with respect to which measure the objective improvement has been computed in table 1. (4) In the same table the Overtime and Objective columns seem repetitive, since objective will only be different from average distance if there is some overtime, in which case the objective value does not bring any valuable information to the reader. Moreover, in table 1 the overtime is always 0 (and objective is always equal to average distance), so both columns could be avoided since they do not bring any information.\n\nThe approach proposed in the paper seems relevant to the community as it applies Reinforcement Learning approaches to an important and relevant problem (DPDP) improving on the state of the art. Researchers might use ideas from this paper to keep improving state of the art for DPDP or even for other similar fields, specially those which have some time-evolving component where the dynamics are not known a priori.\n\n**************POST REBUTTAL COMMENTS*********************************\n\nI read the rebuttals and they clarified some questions raised in the review.\n\nIn particular, the specific answer regarding generalization is interesting, but it does not address out-of-distribution generalization.\nI agree this is a challenge but I would have appreciated a more detailed discussion on how this limits the current approach. As pointed out in the review, discussing potential application to other domains could clarify this point. However, authors in their answer essentially say that the model is general and could be used also in other problems without limitations. I think it is important to discuss the possible limitations of the approach rather than the possibility of applying it to other problems. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors do not specify the limitations of their model. It is true that their model seems pretty robust for their application, but some discussion about potential use in other problems would be appreciated, and it would make clear the limits of application of their approach.\n\nTheir contribution does not seem to imply any negative societal impact, thus it is not discussed.\n", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "10"}, "extra_text": {}}, {"review_id": "rLtCldEGcon", "reviewer": "Reviewer_WBgW", "summary": "The paper proposed a framwork to solve  Dynamic Pickup and Delivery Problem (DPDP) via Reinforcement Learning Based Bi-level\nOptimization method. The upper-level agent used DQN to make a decision whether to release cached orders, while the lower-level agent used GNN to solve each sub-problem. The overall objective function is the weighted sum of travelling distances and overtime. This proposed framwork got a superior performance over baseline.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths:\nThe paper applied the idea of bi-level optimization to DPDP, which is a novel solution for DPDP. And the detailed algorithm of each level is also given. \nThe upper-level uses DQN to eliminate the need to maintain a fixed size cache or prediction for future orders.\nThe experimental results show that this method is worth popularizing\n\nWeaknesses:\nIt seems to be a technical application paper, rather than an academic research one. So the overall novelty may be limited but still interesting. Also, I have a feeling that the training process might be unstable or hyperparameters may be sensitive?", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"ethical_concerns": "no ethical issues", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "MyK2epT6s9Z", "reviewer": "Reviewer_T5ZV", "summary": "The paper considers dynamic pickup and delivery problems in which a limited number of vehicles need to be scheduled to handle all demands with the goal of minimizing the average traveling distance. The problem involves capacity constraints of the vehicles, LIFO constraint, and soft time window constraint, where violating the time windows result in some penalty. \n\nA new algorithm is proposed which is based on the existing idea: Make a buffer to cache the newly arrived orders, then periodically dispatch all the orders in the buffer. The current approaches add the orders to the buffer up to a given size or based on the prediction of the future, but the new proposed approach uses an upper-level agent which determines whether to wait for more items (and get some delay penalty) or dispatch the current orders. For this purpose, a day is partitioned into 144 time-slots of each 10 minutes and the goal is to decide to continue or wait at each of those steps. Then, the received ordered in the buffer with all the orders that are not picked up will be passed to the lower-level agent to solve the static pick-up and delivery sub-problem. The upper-level agent uses DQN to train the agent in which the same goal as of the problem is used as the reward. The state includes \"the number of orders accumulated in the buffer, the number of available vehicles, the amount of time left before exceeding the time limit of each order\". \nThe lower level agent learns the assignment of the orders to the vehicles and the sequence to pass over the orders. The state includes the position information of the customers and vehicles. Action is choosing one of four introduced heuristic improvements for routes. They can be applied to the routes and if there are any improvements, the new route will be accepted. A graph neural network with REINFORCE algorithm is used to train the policy. \n", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Originality: A new method based on hierarchical RL is used to address an existing problem.  Compared to the previous papers, the contributions are clear in terms of the model and the results. I am not aware of all the recent research in this field, but as long as my limited knowledge allows, there are several recent non-RL algorithms for this problem which are not cited.\n\nQuality: The submission technically sound? The claims are supported by experimental results. The weaknesses and the limitation of the work are not discussed.\n\nClarity: The submission is clearly written and it is organized OK. \n\nSignificance: The results are important and probably the results will be used by other researchers or practitioners. It seems that it does advance the state of the art based on numerical experiments. It provides an environment based on a real-world dataset.\n\nI enjoyed reading the paper. I have few comments:\n\n\nQ1- In several places of the paper the term \"bi-level reinforcement learning (RL) based optimization framework\" is used. This is misleading since bi-level optimization is a known type of problem in mathematical programming in which the solution of an optimization problem is a constraint in the main problem (see the problem definition and the formulation in [1] as a recent paper in this field). This is not the case in the problem that you have defined. The algorithm that is defined, has two levels, which are commonly named hierarchical RL. I suggest revising the paper accordingly to avoid any confusion in the future.  \n\nQ2- Several recent papers are not missed in the literature review section. I would add and review the contributions of [3, 4, 5, 6]. For older papers see [2]. \n\nMinor comments: \n\"Although these methods mainly focus on TSPs or VRPs, of which all orders’ information is known in advance and much fewer constraints are considered comparing with DPDP, learning-based methods have shown great potential to help solve large-scale DPDPs and reach superior performance.\"\nThis is not correct. There are several works on RL for VRP which consider stochastic VRP problems in which the demands and their locations are not known a priori. \n\n[1] Tahernejad, S., Ralphs, T.K. & DeNegre, S.T. A branch-and-cut algorithm for mixed integer bilevel linear optimization problems and its implementation. Math. Prog. Comp. 12, 529–568 (2020). https://doi.org/10.1007/s12532-020-00183-6\n\n[2] Berbeglia, Gerardo, Jean-François Cordeau, and Gilbert Laporte. \"Dynamic pickup and delivery problems.\" European journal of operational research 202, no. 1 (2010): 8-15.\n\n[3] Karami, Farzaneh, Wim Vancroonenburg, and Greet Vanden Berghe. \"A periodic optimization approach to dynamic pickup and delivery problems with time windows.\" Journal of Scheduling 23, no. 6 (2020): 711-731.\n\n[4] Ulmer, Marlin W., Barrett W. Thomas, Ann Melissa Campbell, and Nicholas Woyak. \"The restaurant meal delivery problem: Dynamic pickup and delivery with deadlines and random ready times.\" Transportation Science 55, no. 1 (2021): 75-100.\n\n[5] Su, Zhiyuan, Wantao Li, Jicao Li, and Bin Cheng. \"Heterogeneous fleet vehicle scheduling problems for dynamic pickup and delivery problem with time windows in shared logistics platform: formulation, instances and algorithms.\" International Journal of Systems Science: Operations & Logistics (2021): 1-25.\n\n[6] Györgyi, Péter, and Tamás Kis. \"A probabilistic approach to pickup and delivery problems with time window uncertainty.\" European Journal of Operational Research 274, no. 3 (2019): 909-923.\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "There is no social impact and the limitations of the work are not discussed. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": ["I don’t know"], "time_spent_reviewing": "6"}, "extra_text": {}}, {"review_id": "FBGQbaP1Xr-", "reviewer": "Reviewer_JFQW", "summary": "The current paper proposes a hierarchical approach to solve the dynamic pickup and delivery problem (DPDP). The method uses two RL modules. The upper-level RL policy is designed to segment the time window thus transforming DPDP into a static PDP. For the upper-level RL, DQN is used. The lower-level RL policy is trained to select one solution improving heuristics. The lover level policy is parameterized with the GNN network and trained under the framework of Reinforce.  ", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "<Originality>\nThe current study aims to tackle the important and practical problems in the logistics and transportation fields. The paper explains well the importance of the DPDP. However, the proposed approach to solve the target problem is a combination of heuristics, mainly seeking to improve the performance rather than seeking to answer the fundamental research questions that can be rooted in the target problem. \n\n\nThe term “Bi-level optimization” is misleading. Bi-level optimization refers hierarchical optimization problem where the upper-level solution defines the lower-level optimization and thus affects the lower-level solution. In the proposed approach, it is difficult to understand how the upper-level and lower-level decision-making problems are interrelated. They just affect the final cost.  \n\n/\n\n\n<Problem formulation>\nI don’t quite understand what dynamic effect the upper-layer MDP trying to model. For example, what transition rule that DQN is trying to implicitly learn? Does the releasing action affect actually the long term performance? Can you verify if the estimated Q-value is actually modeling the future accumulated reward? \n\nThe action of the lower level of MDP is choosing one possible operator. It is not clear how such activities affect the state transition. In solving static PDP, there are numerous RL algorithms. I think the author should compare with one of these well-defined RL solvers for solving routing problems to justify the proposed method. In addition, the static PDF can be also solved with well know heuristics, such as LKH. In short, justify more the usage of a specific MDP formulation of the lower-level policy. In addition, there are many engineered heuristics in choosing a route or node to swap. Without learning selecting procedure for such operator-dependent actions, the learned policy is difficult to generalize over different sized problems, I think.  \n\n/\n\n<Learning>\nThe learning method is not described in detail. How the upper-level and lower-level policies are trained? Are they trained simultaneously or alternatively? \n\n/\n\n<Baseline>\nComparing with the baseline using the fixed wind duration is not fair. Obviously using the variable window length is beneficial. The study should compare the different methods for segmenting the time window instead of comparing the fixed window and variable window. \n\n/\n\n<Clarity>\nThe paper is well written and well organized.\n\n/\n\n<Significance> \nThe proposed method proposed one of the possible heuristic approaches to solve DPDP. The proposed method rarely exploits the specific structure of the target problem and the proposed approach is far from tackling general research questions that the general ML community would be interested in. Thus, the significance is limited.\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors did not comment on the limitation of the proposed method. The storing limitation is that the proposed approach is designed to tackle a very specific type of problem thus the proposed method cannot provide general insight or intuition for other related fields. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "8 hours"}, "extra_text": {}}]

Author rebuttal:

Meta-review: All reviewers are positive to this paper. The pickup and deliver problem is important and the bi-level optimization solution (or hierarchical RL) shows nontrivial technical depth.

Most concerns or confusions have been addressed or clarified by the rebuttal and the multiple round in the interaction. This paper is recommended to be accepted. Please follow the post review to appropriately polish this paper, for example, the generalization issue needs to be discussed in the revision. 
Decision: Accept (Poster)