- Rating
- 2
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 1
Read review
Paper summary
This paper proposes RT-NVR (Real-Time Neural Vehicle Routing), which extends neural vehicle routing methods from static optimization to real-time online decision-making. When dynamic events occur, the model solves the routing plan under the new state while maintaining the delivery commitment set originally assigned to each vehicle, through the Delivery Commitment Set-based Masking (DCSM) . The method proposes VCPO, which converts the performance gap between geometrically equivalent views into a learning signal via a contrast-adaptive baseline(CAB). Spatiotemporal Compatibility-Guided Sampling (SCGS) is used to modulate the decoding process, yet its core appears to merely introduce a heuristic term. Extensive experiments are finally conducted to verify the performance of the method and its planning capability when tackling dynamic problems.
Critical strengths
-
This paper investigates a dynamic vehicle routing problem with delivery commitments. Compared with conventional static problems, this problem has greater practical significance and is more challenging.
-
The experiments are relatively comprehensive, with sufficient tests conducted for different probabilities of cancellation event and the factor for new order adding. Compared with other neural solvers, VCPO achieves overall better performance.
Critical weaknesses
-
Methodological innovation is relatively limited, consisting mainly of incremental improvements to existing methods. For example, the proposed VCPO is a minor modification built upon existing multi-view methods(e.g., sym-nco), where the baseline is changed from the average baseline to baselines of high and low views. Spatiotemporal Compatibility-Guided Sampling (SCGS) can also be regarded as a heuristic term added on logits, with limited innovation.
-
There are some doubts regarding the description of the method. The approach decomposes the dynamic problem into multiple VRP-FSDC tasks, and re-plans the complete solution when dynamic events occurs. However, upon the occurrence of an event, multiple vehicles may have different positions and intermediate states, and the form of the solution will differ significantly from that of the standard VRP problem in Section 3.1. However, this method seems not to consider the state information of multiple vehicles, and the solution form is not clearly defined. Besides, regarding state broadcasting, the paper does not elaborate on this mechanism. It merely concatenates the current embedding with vehicle states.
-
The baselines used in the experiments are outdated (2017, 2021, 2024) and do not include methods specifically designed for dynamic tasks. In addition, my another concern is that unlike common fixed VRP test datasets, the test instances described in the experiments are random, meaning they are not consistent across all methods, which may introduce a certain degree of unfairness. Ablation studies for the core component SCGS are also missing. Although Figure 3 presents results for the REIN method without SCGS, the performance of VCPO with SCGS removed is not provided.
Questions for authors
-
As described in W1, how does the method handle the states of multiple vehicles running in parallel in dynamic problems? Sequential solutions generated by traditional methods such as POMO seem unable to represent the solutions to this multi-vehicle multi-origin problem.
-
Please explain what state broadcast is(see W1).
-
Do the encoder and decoder in the model rerun after every dynamic event? If there are no order cancellations or new orders, will replanning still be triggered when a vehicle arrival event occurs?
-
It is noted that the setting of this paper is training in a static environment and testing in a dynamic environment. Would dedicated training for dynamic environments enable better capture of dynamic characteristics?
-
As described in W3, random test instances are inconsistent across different algorithms, which may lead to certain unfairness. Especially for order cancellation events, different algorithms may select different routes, resulting in different candidate sets of customers for cancellation operations. Even if the random seed is fixed, the above problem seems unsolvable.
-
What exactly does the Delay metric in Table 2 refer to? It does not seem to be explained in the paper.
-
As described in W3, how does the performance of VCPO change after removing SCGS? In addition, in many sets of experiments, as increases, for example, at 0.4 and 0.5, why does the VCPO algorithm no longer show advantages over other algorithms?
7 comments
Thank you for the author's reply. Some of my concerns have been addressed, but I still have the following questions:
-
Although a static VRP problem can naturally be regarded as multiple trips of a single vehicle, multiple vehicles are operating simultaneously in the dynamic VRP. When a dynamic event occurs, each vehicle may be at a different location and in a distinct state. How is replanning carried out at this point? It seems that such replanning cannot be treated as multiple trips of a single vehicle as in the static problem.
-
According to the author, the event stream is fixed. In that case, I can understand that order release is fair. However, with regard to order cancellation: if the order has already been visited before it is cancelled, will this cancellation event be ignored?
Reply to Reviewer AUZz
Thanks for your comments.
-
Multiple vehicles are en route at the same time, and replanning accounts for that. Specifically, the decoder processes the vehicles one by one in index order; for each vehicle, it starts from that vehicle's current position and real-time state, applies DCSM over its delivery commitments, and autoregressively constructs that vehicle's remaining route only, and then moves on to the next vehicle until all vehicles are routed and no customer remains unrouted. Consequently, the static multi-trip form is merely the special case in which all vehicles start from the depot.
-
Cancellation is only valid under a precondition: if the customer has already been served, is being served, or has already been reserved for service, the order can no longer be cancelled, and the corresponding event is not generated, i.e., it is ignored. This matches practice, since a customer cannot withdraw an order that is already on the vehicle or has already been delivered.
Thank you again for your careful review.
Reply to Reviewer AUZz
Thanks for your positive comments.
We appreciate your recognition and your comments on methodological novelty, multi-vehicle states and state broadcasting, baselines and instance randomness, the missing SCGS ablation, the Delay metric, and the high-event-frequency behaviour were very helpful; the corresponding clarifications are now given in Section 4.1 (solution construction and state broadcasting), Section 4.3 (replanning triggers), Section 5.2 (SCGS ablation, Delay definition, high fi analysis) and Section 6, while the points on novelty and baselines are addressed in our response below. Thank you again for your careful review.
Responses to Weakness 1:
Our contribution is to make NVR deployable in real-time operations, not to propose another static VRP architecture. We have rewritten our conctributions in both abstract and introduction. Please see the revised manuscript.
Responses to Weakness 2:
The approach does not decompose the problem. Decoding is performed vehicle by vehicle rather than for multiple vehicles simultaneously. To show this part clearly, we have added the “Solution Construction” paragraph in Section 4.1 on page 5 of the revised manuscript.
We have also further explained state broadcasting in the “Decoder” paragraph in Section 4.1 on page 4 of the revised manuscript.
Responses to Weakness 3:
We did not include methods designed for dynamic tasks because they do not consider delivery commitment constraints and give no safe decision boundary.
Fairness is guaranteed, because the event flow of order releases and cancellations is determined before execution rather than by the routes an algorithm takes. All algorithms are evaluated on the same event flows. The procedure is implemented in realtime_instances.py and realtime_inference.py of the supplementary material.
Following your suggestions, we have reported the results of VCPO with SCGS removed and added related discussions in the revision. Please see the “Training performance comparison” paragraph in Section 5.2 on page 7 of the revised manuscript.
Responses to Question 1:
When a vehicle returns to the depot, the vehicle state is reset and the routing of the next vehicle starts, which is the same autoregressive decoding used in POMO and standard NVR methods. The solution has the same form as that of the static problem, and the difference lies only in how it is constructed, through the alternation of real-time optimization and deployment.
To show this part clearly, we have added the “Solution Construction” paragraph in Section 4.1 on page 5 of the revised manuscript.
Responses to Question 2:
Following your suggestions, we have further explained state broadcasting in the “Decoder” paragraph in Section 4.1 on page 4 of the revised manuscript.
Responses to Question 3:
We have added “At each replanning, the encoder is run once, and the decoder then constructs the solution autoregressively.” in the “Planning Level” paragraph in Section 4.3 on page 6 of the revised manuscript.
Only three dynamic events trigger the planning level, namely a released pickup order, a cancelled order, and an arrival later than the customer's latest arrival time. When none of these three dynamic events occurs, a vehicle arrival alone does not trigger replanning.
Responses to Question 4:
If dynamic scenarios contained predictable patterns, training in a dynamic environment would indeed lead to better performance. Order releases and cancellations, however, are difficult to predict reliably, so training directly in a dynamic environment would introduce noise and make it hard for the model to learn the basic routing strategy.
Training in a static environment can be regarded as the first step. The next step is to study how to fine-tune the model efficiently in real-time scenarios, where improved decision flexibility leaves low-cost room for responding to unpredictable dynamic events. This step is stated as future work in the Conclusion on page 10.
Responses to Question 5:
Please see Responses to Weakness 3.
Responses to Question 6:
We have rewritten “…, Delay denotes the average total delay time over served customers, i.e., the total excess of realized arrival times over latest arrival times, …; all metrics are averaged over instances and event-frequency combinations.” in the revision. Please see the “Real-time performance comparison with heuristic methods” paragraph in Section 5.2 on pages 7-8 of the revised manuscript.
Responses to Question 7:
Following your suggestions, we have reported the results of VCPO with SCGS removed in Figure 3 and Figure 4.
The performance degradation at fi=0.4 and fi=0.5 arises because greedy replanning may restrict future decision flexibility, which is a direction for future research and may be handled through fine-tuning. VCPO is not the only method affected, as ITAB and ITDA also degrade in performance at fi of 0.4 or higher.