Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: The paper proposed a framwork to solve  Dynamic Pickup and Delivery Problem (DPDP) via Reinforcement Learning Based Bi-level
Optimization 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.
main_review: Strengths:
The 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. 
The upper-level uses DQN to eliminate the need to maintain a fixed size cache or prediction for future orders.
The experimental results show that this method is worth popularizing

Weaknesses:
It 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?
limitations_and_societal_impact: Yes
review_title: null

final_score: rating: 7: Good paper, accept
review_content: 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. 

A 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". 
The 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. 

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.

Quality: The submission technically sound? The claims are supported by experimental results. The weaknesses and the limitation of the work are not discussed.

Clarity: The submission is clearly written and it is organized OK. 

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

I enjoyed reading the paper. I have few comments:


Q1- 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.  

Q2- 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]. 

Minor comments: 
"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."
This 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. 

[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

[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.

[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.

[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.

[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.

[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.


limitations_and_societal_impact: There is no social impact and the limitations of the work are not discussed.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: 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.  
main_review: <Originality>
The 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. 


The 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.  

/


<Problem formulation>
I 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? 

The 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.  

/

<Learning>
The learning method is not described in detail. How the upper-level and lower-level policies are trained? Are they trained simultaneously or alternatively? 

/

<Baseline>
Comparing 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. 

/

<Clarity>
The paper is well written and well organized.

/

<Significance> 
The 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.


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_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: 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.
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. 

Despite 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).

The 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.

The 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.

**************POST REBUTTAL COMMENTS*********************************

I read the rebuttals and they clarified some questions raised in the review.

In particular, the specific answer regarding generalization is interesting, but it does not address out-of-distribution generalization.
I 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. 
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.

Their contribution does not seem to imply any negative societal impact, thus it is not discussed.
review_title: null

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)