A Learning-based Capacitated Arc Routing Problem Solver Comparable to Metaheuristics While with Far Less Runtimes

Q1: Converting the graph G from arcs to nodes represents a common approach in many heuristics for addressing CARP. This process adds complexity to the problem and increases its scale. The proposed method appears to lack enough novelty, with most components bearing resemblance to neural models designed for CVRP.

A1: Thanks for your insightful question. However, our method actually differs from previous studies. Most earlier methods employed a common technique known as line graph conversion from edges to nodes, which completely ignores the directionality of edge traversal, hindering the application of learning-based CARP solvers. Our work specifically addresses this issue, aiming to eliminate barriers for learning-based CARP solvers. Additionally, we have combined supervised learning and reinforcement learning to jointly optimize a single strategy, achieving better results than using either approach independently.

Q2: In the experimental section, it is highlighted that supervised learning was employed for generating the initial policy using MAENS to produce real labels. Nonetheless, supervised learning may face challenges with large-scale datasets. Is supervised learning indispensable for this aspect? Would the final model's performance be affected if the initial policy was randomly generated instead?

A2: Thanks for the valuable comments. The main purpose of using supervised learning is to accelerate the convergence of reinforcement learning algorithms. While reinforcement learning algorithms can be initialized with random strategies, they often require more training time to converge or even cannot converge. Therefore, supervised learning is indispensable. To validate the effects of random strategy initialization, we conducted experiments, as shown in Table R2. As seen, Task 20 can converge in about 2.5 hours, but for other task sizes, we spent a significant amount of time training with difficulty in achieving convergence. Additionally, for the converging Task 20, the cost of training with random initialization was approximately 15% higher than that with the combined SL+RL approach. In fact, since supervised learning is only performed on Task20, the SL pre-training does not take a lot of time.

Table R2. Training comparison between supervised pre-training and random initialization. | Task20 | | Task40 | | Task60 | | Task80 | | |:---------|:-------------|:---------|:-------------|:---------|:-------------|:---------|:-------------| | SL+RL | Random | SL+RL | Random | SL+RL | Random | SL+RL | Random | |0.6h | 2.5h | 0.8h | 8h+ | 1.5h | 15h+ | 2h | 20h+ |

Q3: Is path optimization applied during both the training and inference/testing phases, or is it specifically used for the inference phase only? Moreover, the time specified in Figure 2 likely pertains to the inference time for sample testing. I am also curious about the model's training time—approximately how long does it typically take?

A3: Thanks for the insightful comment. PO is only utilized in the stage of inference, and the training times of DaAM models are are given in the General Response A2.

Q4: It appears that the paper focuses on an unlimited number of vehicles. How would the approach adapt to a specific set of vehicles?

A4: Thanks for the thought-provoking question. The solution to the CARP includes multiple routes, each of which must adhere to vehicle limits (not exceeding the vehicle capacity). The number of vehicles does not affect the total travel cost but does impacts the overall execution time of the task. The more vehicles available, the more routes can be traversed simultaneously. Therefore, considering and restricting the number of vehicles during CARP solving process should extend the overall task execution time.

Q1: It's better to redraw the first part of Figure 1 to enhance its aesthetic quality.

A1: Thank you for the great suggestion, we will carefully redraw the paper if it is accepted. We would like to see if you have any concise suggestions for improving the aesthetic quality.

Q2: The baseline is not very recent. After S2V-DQN and S2V-DQN, there are still some excellent works that can be used to address the CARP problem.

A2: Thanks for the insightful suggestion! The comparison with more methods are given in the Genreal Response A1. As far as we know, there are indeed many excellent works that can solve the CARP-like problem recently. However, we found that most of them focus on variants of CARP, such as uncertain CARP or time CARP, while PS-Efficiency is still the advanced algorithm among constructive heuristics to solve CARP.

Q3: Some writing errors have been identified, such as in line 2 of Algorithm 1. Please review the entire manuscript to check.

A3: Thanks for the valuable suggestion. This writing errors does confuse readers when they are trying to understand. We promise to correct all the writting errors in the final version.

Q4: The completeness of the manuscript still requires supplementation and refinement.

A4: Thanks for the valuable suggestion. We have realized that the lack of some content indeed leads to incompleteness, such as more recent methods, experiments on public datasets, details of training time, parameters of PS variants, etc. We will add all these details in the final version.

Q5: In the manuscript, what is the significance of transforming the initial undirected edges into fully connected directed edges at the beginning? If edges' directions are required, why not just convert them into bidirectional directed edges?

A5: Thanks for the insightful comment. In our method, by splitting the undirected edge into two directed edges, DaAM can calculate the embeddings for the two edges with opposite directions separately and explicitly choose one directed edge at each decision. If using bidirectional edges, the directionality contained in each bidirectional edge cannot be determined after computing the embedding.

Q6: In section 4.2, how is ϵ selected?

A6: Thanks for the comment. This parameter is obtained by searching. Based on the experience of previous related papers, we set his search range to (0, 0.2], with a step size of 0.05. We use values of 0.05, 0.1, 0.15, and 0.2 as training parameters and select the optimal value by comparing the final training loss.

Q7: In section 4.3, the authors remove all the depot arcs initially and then add them back. What is the purpose of these steps? Why does this not affect the calculation of vehicle capacity?

A7: Thanks for the insightful comment. PO aims to optimize the depot arcs' position in the result sequence, i.e., determining when to return. Therefore, all depot arcs need to be removed initially, which temporarily disrupts capacity constraints. Then the capacity constraints is restored by re-inserting the deport arcs' back into suitable positions within the result sequence. This process can be understood as a "Route First, Cluster Second" mechanism, as mentioned in answer to question 7 of Reviewer h6eF.

Q8: In the Solution Visualization section, the authors have visualized the streets of Beijing. How does the model handle the non-Euclidean space in real-world scenarios?

A8: Thanks for the valuable comment. In our experiments, we first obtain road network data from map SDKs such as OpenStreetMap, then extract the topology to create a non-Euclidean graph. The core steps are already provided by the map SDKs.

Q9: The detailed structure of the proposed model and algorithm should be further completed and supplemented in the appendix.

A9: Thank you for your valuable suggestion. Considering that the details of the network structures such as GAT and AM are not shown in detail in this paper, it indeed have a certain impact on understanding. If the paper is accepted, we are willing to describe all the model structure in the supplementary materials to help readers fully understand every detail of our algorithm.

Q10: The approach of decomposing undirected edges into directed ones introduces additional decision elements, which complicates the problem. It's better that the authors can find a more efficient graph processing method.

A10: Thanks for the insightful comment. In previous learning-based solvers, decisions were made directly on undirected edges. Actually, since decisions are made continuously, the directionality of the edges is also determined at the same time. Thus, these methods implicitly encoded the directionality of edges. In contrast, our approach explicitly encodes the direction of the edges, reducing the difficulty for the model in learning edge directionality. Although our transformation process indeed creates redundant edges and increases the amount of input data, we can further reduce the complexity through graph pruning.

Q1(abbreviation): The abstract inaccurately describes the CARP as finding a "minimum-cost tour" rather than finding a set of routes.

A1: Thanks for the valuable suggestion. This vague description does confuse readers when they are trying to understand. We promise to correct all ambiguities in the representation of the final version.

Q2(abbreviation): The paper incorrectly separates "heuristics" and "metaheuristics".

A2: Thanks for the valuable suggestion. The "heuristic" in the paper is indeed "constructive heuristics" as you said. We will adopt this expression in the final version and give a specific definition.

Q3(abbreviation): Introducing the "route-first, cluster-second" strategy and "giant tour" concept could clarify and improve the paper's approach to path optimization.

A3: Excellent suggestion! It is very useful for us to enhance the representation. These two concepts are indeed closely related to the proposed method. The core idea of ​​“Route-first, cluster second” is to construct a continuous tour (i.e., “giant tour”) including all the edges that need to be served, and then split it into multiple feasible sub-routes. We will re-construct the section of "path optimization" by using the two concepts to explain the mechanisms.

Q4(abbreviation): The paper should clarify that fair comparisons are between their basic approach and other constructive heuristics, and assess the impact of path optimization on the other constructive heuristics.

A4: Thanks for the interesting suggestions. Firstly, we mainly compare the constructive heuristics and DaAM without PO. As shown in Tables 3 and 4 of the original paper, DaAM exceeds them on problem instances of Task300 and smaller ones, except for Task40. Especially, although DaAM is trained on Task100, it still surpass them on larger problem instances, Task200 and Task300. On Task400, Task500 and Task600, although DaAM did not lead due to lack of effective training, its gap with PS variants is very small. Secondly, we further leverage PO to optimize all constructive heuristics, as shown in Table 4 of the submitted PDF. Overall, PO consistently enhances the routes obtained by PS across all scales. On Task 20 and Task 60, PO achieves a gap reduction of 2%-5%, while the decrease in the gap is more modest on other scales.

Q5(abbreviation): The paper’s claims that NN-based methods lag in CARP are refuted by Rahmamoorty et al. (2024), who report an 11% improvement over memetic algorithms.

A5: Thanks for the insightful comment. The paper (Rahmamoorty et. al [1]) does not provide its implementation code publicly, nor does it outline the data partitioning scheme. Therefore, we are unable to reproduce its results or conduct a fair comparison. However, we will thoroughly describe its method and rectify any discrepancies in the final version of the paper.

[1] Ramamoorthy M, Syrotiuk V R. Learning heuristics for arc routing problems[J]. Intelligent Systems with Applications, 2024, 21: 200300.

Q6&Q11(abbreviation): How were the PS approaches parameterized?

A6&A11: Thanks for the insightful comment. In this paper, we apply the official setting for the parameter: $\alpha$ of these PS variants. To be specific, PS-Ellipse's $\alpha$ is 1.5, PS-Efficiency's $\alpha$ is 3.0, PS-Alt1's $\alpha$ is 3.0, PS-Alt2's $\alpha$ is 1.0. In terms of iteration number, the paper [2] stated that "For all sets of instances, the average deviations obtained by PS-Efficiency and PS-Ellipse with k = 1000 are better than those obtained by PS-RC and PS-RE with k = 20000." Based on this, we employ 1000 iterations for smaller problem instances from Task20 to Task100. Therefore, on smaller-scale data, the parameters we adopted for PS variants are exactly the same as those in the paper [2]. For larger problem instances from Task200 to Task600, we adjust the iterations to 100 to balance running time and solution quality.

[2] Rafael Kendy Arakaki and Fabio Luiz Usberti. An efficiency-based path-scanning heuristic for the capacitated arc routing problem. Computers & Operations Research (COR) , 103:288–295, 2019.

Q7(abbreviation): The description of path improvement and the state definition in the Dynamic Programming algorithm are unclear, particularly what "f()" denotes.*

A7: Thanks for the valuable comments. The overall mechanism of path optimization can be understood as a "Route First, Cluster Second" mechanism. In the path optimization, we initially disregard capacity constraints and remove all depots from the original path sequence to obtain path $P$. Subsequently, depots are replanned through dynamic programming to ensure the result meets capacity constraints. In dynamic programming, the state $f(P)$ represents the maximum cost saving that can be achieved by replanning the depots' positions within the path sequence $P$ (in terms of travel cost). The value of $f(P)$ is derived from the optimized results of its various subpaths, denoted as $f(P')$. We will clearly describe for this point in the final version.

Q8&Q9&Q13(abbreviation): Training time is not discussed at all.

A8&A9&A13: Thanks for the insightful suggestion! The training times and related discussion are given in the Genreal Response (Genreal A2).

Q10: Where does the implementation of the memetic algorithm come from?

A10: For MAENS, we use the code released by the original author of the paper on Github last year: https://github.com/meiyi1986/MAENS.

Q12: I think that for small instances, the approach by (Rahmamoorty et. al 2024) may surpass the results reported here, which should be mentioned.

A12: As mentioned in A5 above, the absence of a data partitioning scheme makes it difficult to make a fair comparison. Looking ahead, we aim to develop a learning-based solver inspired by Rahmamoorty et al.'s method, which we hope will outperform MA on small-scale CARP instances.

Q1: The comparison algorithms were published five years ago, and there is no discussion of existing methods aimed at big data.

Q2: The experiments only tested the self-constructed dataset and did not evaluate on public datasets.

A1&A2: The suggestions are greatly appreciated! The experimental results and discussions of more comparison method and public dataset are given in the Genreal Response A1.

Q3-1: How is the runtime for different algorithms defined in this paper?

A3-1: Thanks for the insightful comment. The mean runtimes per CARP instance for MAENS and PS variants have already been displayed in Fig 2 of the original paper. Additionally, we have tested the runtimes of S2V-DQN and VRP-DL implemented in our experimental section, as shown in Table R1.

Firstly, on smaller scale problem instances (Task 100 and smaller scales), DaAM (blue line) only cost less than 10% of the computation time of the advanced PS variants and VRP-DL. On larger scale problem instances (Task 200 and larger scales), DaAM's computation time still remains large advantage compared to them. While the time consumed by S2V-DQN is much higher than these methods. It should be noted that S2V-DQN and VRP-DL did not originally support this task, so we modified them to be compatible with CARP. Thus, the low efficiency may be due to the improper implementation. When using the CPU-dependent PO, the advantage in computation time relative to the PS variants is reduced, but it still maintains a computational time advantage on problem instances above Task 60.

To prove fairness, we will release all the data and source codes of the mentioned comparisons.

Table R1. Runtime (second) of different methods on our dataset | Instance | MAENS | PS | PS-Ellipse | PS-Efficiency | PS-Alt1 | PS-Alt2 | VRP-DL* | S2V-DQN* | DaAM | DaAM+PO | |:-------------|--------:|-----:|-------------:|----------------:|----------:|----------:|----------:|-----------:|-------:|----------:| | Task20 | 17 | 1 | 1 | 1 | 1 | 1 | 4 | 113 | 1 | 2 | | Task40 | 775 | 1 | 2 | 5 | 3 | 2 | 9 | 221 | 1 | 5 | | Task60 | 2671 | 1 | 7 | 12 | 8 | 7 | 13 | 310 | 1 | 7 | | Task80 | 5021 | 1 | 16 | 22 | 19 | 17 | 20 | 588 | 2 | 12 | | Task100 | 8587 | 1 | 25 | 35 | 30 | 26 | 28 | 721 | 3 | 19 |

Q3-2: Does the training time for the learning-based algorithms take into account?

A3-2: Thank you for the insightful comment! Indeed, the performance of learning-based solvers like DaAM, VRP-DL and S2V-DQN heavily depends on the training time, which ensures whether the model is adequately trained.

In terms of training time, the General Response A2 provides the training times of DaAM models. For the training time of other learning based solvers, we first ensure that all the models are trained until convergence, so that they are adequately trained for fairness. As a result, the training time of S2V-DQN on different instance sizes is 0.5h, 1.5h, 2.5h, 3.5h, and 6h respectively, and The training times of VRP-DL on different instance scales are 1 to 2 hours. In terms of technique, we carefully considered ways to reduce training time in the design of DaAM. As mentioned in the General Response A2, we take the idea of curriculum learning to reduce the training time of each training scale so that DaAM can be trained sufficiently in an afforable time cost.

Q4: How can one assess the effectiveness of the arc features used in this paper in a more intuitive way?

A4: Thanks for the insightful comment. The efficacy of our arc feature design can be demonstrated through ablation studies. Our arc feature is bifurcated into two components. The first encompasses essential information pertinent to CARP tasks, as detailed in the referenced literature:

• ${is\\_depot}_i$: Indicates whether $arc_i$ is the depot.
• ${cost}_i$: Cost associated with $arc_i$.
• $demand_i$: Demand of $arc_i$.
• $|e_{x_{t-1} i}|$: Edge weight from $arc_{x_{t-1}}$ to $arc_i$.
• ${allow\\_serve}_t^{(i)}$: Service eligibility of $arc_i$ at time t.

The second component involves using MDS to enhance low-dimensional information. The effectiveness of arc feature can be verified by Table 5 and Figure 3. The lack of MDS or other CARP descriptions will lead to slower model convergence, poor performance, and large solution quality fluctuations.

Q5: The amount of data required for algorithm training needs to be discussed.

A5: Thanks for the valuable comment. Due to the nature of deep learning, which requires extracting decision-making knowledge from data, the amount of training data is crucial for learning-based methods. In our implementation, all training data must be loaded into the GPU memory before training. As the problem scale increases, we have been compelled to reduce the number of instances used for training.

In our experiments, for problem instances of Task 20, Task 40, and Task 60, we trained the DaAM model using 5,000 to 10,000 instances. For Task 80 and Task 100, we used approximately 2,000 to 4,000 instances for training.