Deep Learning-based Heuristic Construction for Routing Problems with Dynamic Encoder and Dual-Channel Decoder Architecture
Routing problem;Combinatorial optimization;Heuristics;Deep learning
Yes
No ethics review needed.
See weaknesses above.
The paper was largely easy to follow and the experimental results included a suite of strong baselines.
This paper proposes a deep learning model, called DEDD, to solve combinatorial optimization problems such as traveling salesman problem (TSP) and capacitated vehicle routing problem (CRP). DEDD uses a dynamic encoder to update node embeddings at each step of the process and includes a dual-channel decoder for more diverse node selection strategies. Extensive experimental results for TSP and CVRP are presented to compare the performance of DEDD to standard baselines.
1. The novelty/contribution of the method is weak given LEHD (Luo et al., 2023). The proposed method seems incremental compared to LEHD and DR (in the current paper) seems very similar to RRC (in LEHD).

1. A better motivation for the encoder and decoder structure would have helped to better understand the value of the proposed approach.

1. The rationale for the dual channel decoder is not explained clearly. Also, why only two channels and why not more?

1. In fact, in terms of performance, for both TSP and CVRP, LEHD is not that far off from the proposed DEDD. This further takes away from the value of DEDD.
 
1. In Table 1, for CVRP, HGS (Vidal, 2022) seems better than all solutions but this is not mentioned. Can you please comment on this?

1. Since HGS performs the best in the CVRP experiments, why not use HGS as the baseline reference, instead of LKH3?

1. Future work mentions exploring the training DEDD with RL. This seems like a straightforward approach to implement and I am curious why the paper did not do that. This might strengthen the contributions of the paper (see point 1 above).

1. Some practical considerations such as training time and computational complexity are not discussed in the paper. This would allow readers to better understand the paper's contributions and results in the context of existing work.

1. The paper needs to release code for all the presented results. Otherwise, how are we to know that the results in Table 1/Table 2 were computed correctly and fairly?

1. There are minor errors scattered throughout the paper. Please proofread the paper carefully. One such example is: (i) The caption of Figure 2 is not appropriate.
Yes
No ethics review needed.
See weaknesses.
The idea of dynamic encoder and dual-channel decoder is interesting and novel. And extensive experiments were performed to compare the proposed method with the existing methods.
This paper proposes a supervised learning based method for finding the optimal path in the routing problem. The contribution of this work features a dynamic encoder and a dual-channel decoder, which are designed with the aim to increase diversity and get more updated information when making decisions. Results are evaluated in the Traveling Salesman Problem and the Capacitated Vehicle Routing Problem.
Major weaknesses:
1. The motivations behind the design choices and design details are not clear. 
     - When designing the dynamic encoder, the starting point and the previous node are included to generate the new embedding. How much global information do the previous node and the starting point have? Would it be too weak to be helpful? This may be related to the ablation results presented in Table 2. 
     - How is each channel of the decoder trained? Namely, how are p1 and p2 in Eq(14) decided? Also, the authors mentioned on Ln251 "After training, the diversity in node selection strategies primarily stems from the training data of the model." How is the diverversity ensured during the training? 

2. How is the training/testing dataset collected? Is it a public dataset or generated by the authors? If generated by the authors, what's the protocol for generating these instances?

3. Statistical tests should be performed in Table 1 and Table 2 to show the significance of the comparison, as some of the results are very close. 

4. It is mentioned in the paper that the computational and the memory consumption are very high. And it is the reason why reinforcement learning is not used. Could the author elaborate more why reinforcement learning means more memory and computations? Also, from Section 4, the encoder and decoder seem to be relatively small, with shallow layers and small embedding dimensions (128). It seems that the computational and memory costs are very affordable, even for RTX3090.

5. How does the performance change if the models are scaled up? For example, more channels in the decoder, or more layers?

Some minor issues:
1. Figure 2 does not have a caption.
2. On  Ln181, does the author mean "CVRP" instead of "VRP" ?
Yes
N.A.
No ethics review needed.
In addition to the points mentioned in the weaknesses section, I have some further questions and suggestions:

1. Could you clarify the training process for DEDD? Specifically, do you perform backpropagation after each construction step or only after generating the entire solution?
2. The term "labeled node" in Equation (14) is somewhat ambiguous. My assumption is that it refers to the node in the optimal solution corresponding to the current step. If this is correct, how do you handle situations where the labeled node is no longer available, such as when it has already been selected in previous steps?
3. In the reconstruction phase, it appears that a starting segment and an ending segment are given, and the middle part needs to be reconstructed. Unlike constructing the sequence from scratch, the ending segment may also contain valuable information. However, it seems that DEDD does not take the information from the ending segment into account during the reconstruction of the middle part.
4. The caption for figure 2 is missing. 
5. Some key concepts in the paper are not adequately explained. For instance, the term "subproblem" is used without clear definition.
1. The design of the dynamic encoder is well-executed, enabling the model to produce more accurate node embeddings by re-encoding at each construction step. And the dual-channel decoder enhances node selection by maintaining two independent channels that share parameters in all but the final layer, leading to a richer and more diverse solution search space.

2. The experimental results are convincing, showing that DEDD can achieve near-optimal solutions for both TSP and CVRP, especially after the destruction-reconstruction  approach is applied.
The paper addresses the challenging problem of combinatorial optimization in routing problems by proposing a deep learning-based heuristic approach. Specifically, it introduces an architecture called DEDD, which aims to learn effective heuristics for problems like the TSP and CVPR. The dynamic encoder enhances node embedding by re-encoding features at each construction step, while the dual-channel decoder increases diversity in node selection, improving solution quality. Experimental results show that the proposed model performs well for instances up to 1000 nodes, demonstrating nearly optimal solutions.
1. The paper does not explicitly address how feasibility constraints are managed, particularly for the CVRP where vehicle capacities must be respected. The authors should discuss how they ensure that the solutions generated by DEDD are feasible with respect to capacity constraints.
2. The paper lacks a detailed discussion of the limitations of the proposed approach. It would be beneficial to provide a formal mathematical formulation that clearly defines the scope of problems that DEDD is designed to solve, including the assumptions and conditions under which the model operates effectively.
3. The authors highlight that a significant limitation of previous methods is their focus on small-scale problems and their poor generalization to larger or unseen instances. However, it remains unclear how the proposed DEDD model specifically addresses these issues. The paper lacks a detailed explanation of how the design choices within DEDD—such as the dynamic encoder and dual-channel decoder—are intended to overcome the problem of scaling and improve generalization.
4. The problem settings for CVRP instances are not fully elaborated. Important details such as the number of vehicles, vehicle capacities, and customer demands are missing. If these settings are based on a public dataset, it should be explicitly mentioned, and if they are generated, details on how the instances were constructed should be provided.
5. The overall writing quality of the paper is lacking, which significantly impacts readability and comprehension. Many crucial details are omitted, leaving gaps that force readers to make assumptions about the authors' intended meaning. Improving the writing, providing more detailed explanations, and avoiding ambiguity would greatly benefit the presentation.
@inproceedings{
anonymous2024deep,
title={Deep Learning-based Heuristic Construction for Routing Problems with Dynamic Encoder and Dual-Channel Decoder Architecture},
author={Anonymous},
booktitle={Submitted to The Thirteenth International Conference on Learning Representations},
year={2024},
url={https://openreview.net/forum?id=IA3wm5vwUl},
note={under review}
}
The routing problem is a classic combinatorial optimization challenge. Constructing heuristics using deep learning models presents a promising approach for its resolution. In this paper, we propose a novel model with a dynamic encoder and dual-channel decoder (DEDD) architecture to learn construction heuristics for the routing problem. The dynamic encoder en-codes the node features of the decomposed sub-problems at each selection step, thereby obtaining more accurate node em-beddings. The dual-channel decoder facilitates more diverse node selections at each step, increasing the probability of the model identifying optimal solutions. Additionally, we design an effective node selection strategy to assist the model in choosing nodes at each step. Experimental results on the Traveling Salesman Problem (TSP) and the Capacitated Ve-hicle Routing Problem (CVRP) with up to 1000 nodes demonstrate that the solutions generated by the DEDD model are nearly optimal, underscoring its efficacy.
I certify that there is no URL (e.g., github page) that could be used to find authors’ identity.
I acknowledge that I and all co-authors of this work have read and commit to adhering to the ICLR Code of Ethics.
Routing problem Combinatorial optimization Heuristics Deep learning
I certify that there is no acknowledgement section in this submission for double blind review.
/pdf/c206a71453ddaaddd1ff9c62c7adfeb89698e297.pdf
optimization
I understand the reciprocal reviewing requirement as described on https://iclr.cc/Conferences/2025/CallForPapers. If none of the authors are registered as a reviewer, it may result in a desk rejection at the discretion of the program chairs. To request an exception, please complete this form at https://forms.gle/Huojr6VjkFxiQsUp6.
I certify that this submission complies with the submission instructions as described on https://iclr.cc/Conferences/2025/AuthorGuide.
/attachment/c937431e98e6a0a8736533f043512c71161619b6.zip
Deep Learning-based Heuristic Construction for Routing Problems with Dynamic Encoder and Dual-Channel Decoder Architecture
ICLR 2025 Conference Submission
ICLR.cc/2025/Conference/Submission