Deep Learning-based Heuristic Construction for Routing Problems with Dynamic Encoder and Dual-Channel Decoder Architecture

Authors: Jianlin Chen, Jianping Luo
Primary area: optimization
Keywords: Routing problem, Combinatorial optimization, Heuristics, Deep learning

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

Decision: reject
Reviewer scores: 5, 3, 3

Reviews and discussion:
<thread>
creation date:
1729777343047

thread_type:
official_review

<thread_object>
creator: reviewer_rnan

<content>
summary:
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.

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

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

questions:
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.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730443099872

thread_type:
official_review

<thread_object>
creator: reviewer_aceg

<content>
summary:
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.

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

weaknesses:
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" ?

questions:
See weaknesses.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730737985044

thread_type:
official_review

<thread_object>
creator: reviewer_gphi

<content>
summary:
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.

strengths:
The paper was largely easy to follow and the experimental results included a suite of strong baselines.

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

questions:
See weaknesses above.
</content>
</thread_object>

</thread>


Metareview:
metareview:
This paper addresses the classic combinatorial optimization challenge of routing problems by introducing a novel deep learning-based model called DEDD (Dynamic Encoder and Dual-Channel Decoder). Designed to learn construction heuristics for routing problems such as the Traveling Salesman Problem (TSP) and the Capacitated Vehicle Routing Problem (CVRP), DEDD introduces several innovative features to enhance solution quality and efficiency.

The dynamic encoder updates node embeddings at each step by encoding the features of decomposed sub-problems, providing more accurate and context-aware representations. Complementing this, the dual-channel decoder facilitates diverse node selection, increasing the likelihood of identifying near-optimal solutions. Additionally, the model employs a carefully designed node selection strategy to improve decision-making at each step.

Experimental results demonstrate DEDD’s effectiveness in solving large-scale TSP and CVRP instances. The model achieves near-optimal solutions for problems involving up to 1000 nodes. Compared to standard baseline methods, DEDD consistently outperforms in both accuracy and efficiency, highlighting its potential for real-world applications. By combining supervised learning with innovative architectural components, DEDD foresees advancing the development of deep learning-based heuristics for combinatorial optimization. Its ability to dynamically adapt embeddings and promote diversity in solutions positions it as a promising approach for solving complex routing problems in scalable and effective ways.

The three reviewers list a large number of weaknesses. I consolidate the lists and itemize the major ones:

1- Weak Novelty and Incremental Contribution: The proposed DEDD method appears incremental compared to prior work, such as LEHD (Luo et al., 2023), with DR in DEDD resembling RRC in LEHD. Additionally, the performance improvements over LEHD are marginal, which undermines the novelty and value of the contributions.

2- Lack of Motivation and Justification for Design Choices: The paper does not sufficiently motivate or justify key design decisions, such as the encoder and decoder structures, the rationale for using two channels in the decoder instead of more, or how diversity is ensured during training. Greater clarity and justification of these choices would strengthen the work.

3- Inadequate Baselines and Comparisons: The paper uses LKH3 as the baseline for CVRP, even though HGS performs better and is a more relevant reference point. The lack of statistical significance tests in Tables 1 and 2 further limits the rigor of performance comparisons.

4- Omission of Practical Considerations: Critical practical aspects, such as training time, computational complexity, and memory requirements, are not adequately discussed. These omissions prevent readers from fully understanding the feasibility of DEDD in comparison to existing methods.

5- Lack of Information about Dataset: The paper does not clearly explain how datasets were generated or whether public datasets were used. Furthermore, the absence of publicly released code raises concerns about the reproducibility and fairness of reported results.