Multi-Task Learning for Routing Problem with Zero-Shot Generalization

Thank you very much for your time and effort in reviewing our work and providing valuable suggestions. We address your concerns as follows.

W1. While this work is well-motivated, there is no novelty from the methodology perspective. It seems like simple adaption of multitask learning and AM. Although the authors claim the attribute composition is novel, it looks quite naive and trivial.

In this work, rather than the simple multi-task learning, we investigate the attribute composition for NCO, which is a significant but less explored nature of many combinatorial optimization problems such as VRPs [1]. By only learning from a small number of problems with five fundamental attributes (capacity, time windows, open routes, backhauls, and duration limits), our model can easily generalize to tackle a larger number of problems with various combinations of these attributes in a zero-shot manner. This zero-shot generalization property is significantly different from a simple MTL problem and has not been investigated for neural combinatorial optimization. Our proposed attribute composition surpasses simply training all attributes as well as single-task learning in zero-shot generalization.

In addition, the implementation of both our unified model and baseline methods on 11 VRPs provides promising and valuable baselines to the research community. Most of these VRPs have not been studied yet using neural solvers but are commonly used in real-world applications [1][2].

Therefore, we believe our proposed method is novel and could make a good contribution to neural combinatorial optimization.

[1] Heuristics for multi-attribute vehicle routing problems: A survey and synthesis. European Journal of Operational Research, 2013.

[2] The vehicle routing problem: State of the art classification and review. Computers & industrial engineering, 2016.

Our attribute decomposition Vs. all-attribute learning Vs. single-attribute learning

Our work is different from simply learning all attributes together (all-attribute learning). As discussed in the main paper, we have conducted an experiment on directly training the unified model on OVRPBLTW with all attributes (ST_OVRPBLTW) to demonstrate the benefit of attribute composition. Line 11 in Tabel 4, Appendix B lists the results of ST_OVRPBTW. According to the results, ST_OVRPBLTW can achieve promising performance on the problem it trained on (OVRPBLTW) as well as two VRP variants with similar attributes (OVRPBTW and OVRPLTW). However, its performance becomes extremely poor for the rest VRPs (from simple CVRP to VRPBTW). This observation suggests that ST_OVRPBLTW is over-fitted to CVRPBLTW with all attributes and cannot generalize well to other variants with a subset of attributes. This comparison also confirms the effectiveness and usefulness of our proposed method for learning different VRP variants with attribute composition.

W2. The baseline POMO is classic, but not the SOTA. Quite a number of subsequent works surpass it, such as Efficient Active Search and 'Simulation-guided Beam Search for Neural Combinatorial Optimization'. In this sense, the comparison is not that convincing.

We address this concern from the following two aspects:

1) State-of-the-art heuristics: We have added the result of LKH3 in Tabel 2. We also want to mention that the HGS baseline used in this work is a well-known and very powerful heuristic solver that can obtain (nearly) optimal solutions for different VRP variants [1]. It has been widely used as the baseline method in research papers [2,3,4], and is also the benchmark algorithm in different competitions [5,6].

[1] A hybrid genetic algorithm with adaptive diversity management for a large class of vehicle routing problems with time-windows. Computers & Operations Research 2013.

[2] Towards Omni-generalizable Neural Methods for Vehicle Routing Problems. ICML 2023.

[3] Neural Combinatorial Optimization with Heavy Decoder: Toward Large Scale Generalization. NeurIPS 2023.

[4] Rl4co: an extensive reinforcement learning for combinatorial optimization benchmark. Submitted to ICLR 2024.

[5] DIMACS VRPTW Challenge 2021.

[6] EURO Meets NeurIPS Vehicle Routing Competition, NeurIPS 2022.

2) State-of-the-art NCO methods: We have conducted an additional comparison study with SGBS [4], which is a state-of-the-art post-hoc search method for construction-based NCO. According to the results reported in the revised Table 2, the performance of our proposed method can be further improved with SGBS.

We also want to mention that our method is implemented based on the model structure of POMO, which is the current standard baseline for construction-based NCO. As our framework is model-agnostic, one can easily promote cross-problem performance with more advanced base models in the future.

[4] Simulation-guided beam search for neural combinatorial optimization. NeurIPS 2022.

W5. In table 3, the generic traditional methods like LKH-3 and OR-tools should be included.

Thank you for this suggestion, we have added the result of LKH3 in Tabel 2. However, according to the user guide of OR-Tools (https://developers.google.com/optimization/examples), it does not support the problems listed in Table 3. We also want to mention that the HGS baseline used in this work is a well-known and very powerful heuristic solver that can obtain (nearly) optimal solutions for different VRP variants [1]. It has been widely used as the baseline method in research papers [2,3,4], and is also the benchmark algorithm in different competitions [5,6]. We observed similar results when comparing HGS, LKH3, and OR-Tools on XML100 instances as is listed in the Table below.

[1] A hybrid genetic algorithm with adaptive diversity management for a large class of vehicle routing problems with time-windows. Computers & Operations Research 2013.

[2] Towards Omni-generalizable Neural Methods for Vehicle Routing Problems. ICML 2023.

[3] Neural Combinatorial Optimization with Heavy Decoder: Toward Large Scale Generalization. NeurIPS 2023.

[4] Rl4co: an extensive reinforcement learning for combinatorial optimization benchmark. Submitted to ICLR 2024.

[5] DIMACS VRPTW Challenge 2021.

[6] EURO Meets NeurIPS Vehicle Routing Competition, NeurIPS 2022.

W3. Although the authors reviewed and criticized 'Efficient Training of Multi-task Combinatorial Neural Solver with Multi-armed Bandits', it is the most relevant baseline to this paper. It is good to compare with it in some adapted or tailored experimental settings.

The mentioned work provides an effective approach for doing multi-task learning for different combinatorial optimization problems (Travelling Salesman, Capacitated Vehicle Routing, Orienteering, and Knapsack). However, their work and ours actually investigate two different research directions, and they are hard to be directly compared. Our work adopts the attribute composition to learn a unified model from a small number of VRPs with basic attributes (Time Windows, Open Routes, Backhauls, and Duration Limits), and the model can be used to solve a much larger number of VRPs in a zero-shot manner. In contrast, the mentioned work requires one decoder for each problem, therefore prohibiting the zero-shot generalization on new VRPs. How to combine these two methods for a more efficient MTL NCO solver could be an interesting future work.

W4. In table 2, where the proposed method is inferior to other neural baselines should be analyzed and explained.

Our multi-task learning model is slightly poorer than POMO, which is directly trained on each specific task. This result is reasonable and acceptable because 1) on the one hand, our model trained on five VRPs simultaneously. The training instances used on each VRP are only one-fifth of the compared single-task learning models. 2) on the other hand, the single-task learning model overfits a single VRP with a given distribution, which is also commonly observed in multi-task learning in other fields [1]. There is always a tradeoff between specific-task performance and general performance in a given budget. Our model significantly promotes cross-problem performance (from over 20% to less than 5%) and reduces the training cost while slightly sacrificing the performance on some specific tasks.

[1] A survey on multi-task learning. IEEE Transactions on Knowledge and Data Engineering, 2021.

Correlation among Attributes: We have conducted additional experiments to show the correlation and conflicting among attributes. Similar to [3], we separately train our model on each pair of VRPs to investigate the pairwise correlation among tasks. As a result, we have a total $C(5,2) = 10$ pairwise combinations with respect to the $5$ basic VRPs (i.e., CVRP, VRPTW, OVRP, VRPB, and VRPL). The detailed experimental settings and results can be found in Appendix F. We also provide an anonymous link (https://drive.google.com/file/d/1CtOwsgayGxFURA8luqIfDLMeCAFOJC23/view?usp=sharing) for fast checking of the resulting correlation matrix, which measures the performance gap between each task pair and our unified model. The positive values represent a positive correlation between two VRPs, while negative values denote a conflict.

The results reveal that the CVRP, being a fundamental routing problem, has a positive correlation with all the other problems except for OVRP. The OVRP is found to exhibit the most severe conflicts among the attributes followed closely by the VRPTW. It aligns with our intuition that the open route conflicts with the other VRPs that force every route back to the depot. Similarly, time windows pose additional constraints on the choosing of the next node, which may significantly influence generalization performance, as we will discuss in W2.

[3] Which tasks should be learned together in multi-task learning? ICML 2020.

Distribution of Different VRPs: We have also conducted a comparison of distributions of different VRPs on the two-dimensional reduction space of the decoder hidden layer (1000 samples for each VRP), where the results can be found in Appendix F as well as an anonymous link for fast checking (https://drive.google.com/file/d/1syLwzAy9tRspsvjrPkqAT4vQ-xrR67HH/view?usp=sharing). According to the result, there is a clearly distinct distribution of VRPTW compared with others as the time window attribute poses a strong constraint over the route. In addition to VRPTW, OVRP also shows a different pattern compared to others followed by VRPB, as we have mentioned that OVRP does not force routes back to the depot. In contrast, CVRP and VRPL follow a very close distribution and overlap with each other in the majority of areas, which is also reflected in the close final distances. This can be attributed to the fact that our route length limit is set to 3 on the normalized coordinates, which is easily satisfied due to the tighter capacity constraint. The distribution analysis of the hidden layer aligns with the findings from our correlation matrix discussions.

Thank you again for your time and effort in reviewing our work. There is only less than 1 day left to the rebuttal deadline, and we sincerely want to know whether our responses can successfully address all your concerns. We are glad to continually improve our work to address them.

Thank you very much for your time and suggestions. To further address your concern, we conducted three set of experiments to analyze the correlation of different attributes in our framework and also highlight the difference between our target combinatorial optimization problems and multi-task learning for general purposes.

Correlation among Attributes: Similar to [3], we separately train our model on each pair of VRPs to investigate the pairwise correlation among tasks. As a result, we have a total $C(5,2) = 10$ pairwise combinations with respect to the $5$ basic VRPs (i.e., CVRP, VRPTW, OVRP, VRPB, and VRPL). The detailed experimental settings and results can be found in Appendix F. We also provide an anonymous link (https://drive.google.com/file/d/1CtOwsgayGxFURA8luqIfDLMeCAFOJC23/view?usp=sharing) for fast checking of the resulting correlation matrix, which measures the performance gap between each task pair and our unified model. The positive values represent a positive correlation between two VRPs, while negative values denote a conflict.

The results reveal that the CVRP, being a fundamental routing problem, has a positive correlation with all the other problems except for OVRP. The OVRP is found to exhibit the most severe conflicts among the attributes followed closely by the VRPTW. It aligns with our intuition that the open route conflicts with the other VRPs that force every route back to the depot. Similarly, time windows pose additional constraints on the choosing of the next node, which may significantly influence generalization performance, as we will discuss in W2.

[3] Which tasks should be learned together in multi-task learning? ICML 2020.

Distribution of Different VRPs: We have also conducted a comparison of distributions of different VRPs on the two-dimensional reduction space of the decoder hidden layer (1000 samples for each VRP), where the results can be found in Appendix F as well as an anonymous link for fast checking (https://drive.google.com/file/d/1syLwzAy9tRspsvjrPkqAT4vQ-xrR67HH/view?usp=sharing). According to the result, there is a clearly distinct distribution of VRPTW compared with others as the time window attribute poses a strong constraint over the route. In addition to VRPTW, OVRP also shows a different pattern compared to others followed by VRPB, as we have mentioned that OVRP does not force routes back to the depot. In contrast, CVRP and VRPL follow a very close distribution and overlap with each other in the majority of areas, which is also reflected in the close final distances. This can be attributed to the fact that our route length limit is set to 3 on the normalized coordinates, which is easily satisfied due to the tighter capacity constraint. The distribution analysis of the hidden layer aligns with the findings from our correlation matrix discussions.

Influence of the Degree of Constraint: In the second part of the experiments, we examine how the degree of constraint affects the correlation and zero-shot generalization performance. We illustrate this using an example of VRPTW (Vehicle Routing Problem with Time Windows). Specifically, we trained a single-task model on VRPTW (ST_VRPTW) with various TW lengths $\Delta_i$ = {0.15, 1 ,2 ,4} (where a smaller $\Delta_i$ represents a tighter TW constraint). We then evaluated the models on OVRPLTW and OVRPBTW. Our results reveal that as the TW length increases (i.e., the time window constraint is relaxed), the performance gap becomes larger compared to our multi-task learning approach. This can be attributed to the fact that the time window constraint, which is tightly enforced in our paper, is a dominant factor compared to other attributes that explain the strong generalization of ST_VRPTW on tasks with time window constraints.

Thank you very much for your time and effort in reviewing our work and providing valuable suggestions. We address your concerns as follows.

Q1. This paper emphasizes zero-shot generalization, e.g., in the title. More discussions in experiments refer to fine-tuning, which seems to be inconsistent with the “zero-shot”. It is better to give more descriptions about this point.

Thank you for your valuable suggestion. We have reorganized and revised the content to emphasize our zero-shot generalization performance. Our evaluation includes the results on Table 2, Table 3, and most of Table 4, which are all assessed in a zero-shot manner. In addition, we have also included the results obtained through a powerful post-hoc search method (SGBS [1]) with the non-fine-tuned model for further comparison.

[1] Simulation-guided beam search for neural combinatorial optimization. NeurIPS 2022.

Q2. As illustrated, different VRPs need to use different masking mechanisms to handle constraints. If a VRP variant is very complex, would it be hard to design a masking mechanism? Or even would there be some complex constraints that cannot be handled directly by masking?

Yes, there are attributes that may not fit perfectly to the masking procedure. However, we argue that 1) our model can be extended to handle a large majority of problems through our attribute decomposition since the top ten attributes contribute to over 90% of the VRP variants [1]. 2) If there are special attributes that can not be handled with the masking procedure, a specific decoding procedure might be required.

[1] The vehicle routing problem: State of the art classification and review. Computers & industrial engineering, 2016.

Q3. Some typos still exist, such as the beginning of Section 3 and the reference “Select and optimize: Learning to aolve large-scale tsp instances”. Please check carefully.

Thank you very much for pointing them out. We have revised the main paper as well as the appendix to correct the typos carefully.

Q1. How do different VRP attributes collaborate in the learning process?

Please refer to our response to W1a and W1b.

Q2. Are the baseline methods in Table 1 and Table 2 are. the state-of-the-art methods for all VRP variants?

Please refer to our response to W5.

Q3. How does the proposed method perform on more large-scale problems?

Please refer to our response to W3.

Q4.Is the proposed method model-agnostic to other neural methods?

Yes, our method is model agnostic to both 1) the model structures and 2) the post-hoc neural search methods. For the former, we can easily incorporate the attribute composition input and multi-task training procedure into the new model structure. For the latter, we can directly adopt the post-hoc search approach with our method, such as the powerful SGBS approach in response to W5.

Q5. How does the proposed method encounters unseen attributes? Could the method be adapted quickly to new attributes with relatively small training samples?

If the new attribute is closely relative to the seen one (e.g., flexible soft time windows), it can be properly handled by the unified model with a fast adaption. However, for a brand new and irrelevant attribute, we should expect our proposed method will require more effort to handle it, which might involve attribute-dependent inference design and model retraining.

In addition, our model can be extended to handle a large majority of problems through our attribute decomposition since the top ten attributes contribute to over 90% of the VRP variants [1].

[1] The vehicle routing problem: State of the art classification and review. Computers & industrial engineering, 2016.

W5. For all the VRP variants in Table 2 and Table 3, the baselines may not include all the corresponding state-of-the-art methods for multiple problems.

We address this concern from the following two aspects:

1) State-of-the-art heuristics: We have added the result of LKH3 in Table 2. We also want to mention that the HGS baseline used in this work is a well-known and very powerful heuristic solver that can obtain (nearly) optimal solutions for different VRP variants. It has been widely used as the baseline method in research papers [1,2,3], and is also the benchmark algorithm in different competitions [4,5].

[1] Towards Omni-generalizable Neural Methods for Vehicle Routing Problems. ICML 2023.

[2] Neural Combinatorial Optimization with Heavy Decoder: Toward Large Scale Generalization. NeurIPS 2023.

[3] Rl4co: an extensive reinforcement learning for combinatorial optimization benchmark. Submitted to ICLR 2024.

[4] DIMACS VRPTW Challenge 2021.

[5] EURO Meets NeurIPS Vehicle Routing Competition, NeurIPS 2022.

2) State-of-the-art NCO methods: We have conducted an additional comparison study with the simulation-guided bean search (SGBS) [4], which is a state-of-the-art post-hoc search method for construction-based NCO. According to the results reported in the revised Table 2, the performance of our proposed method can be further improved with SGBS.

We also want to mention that our method is implemented based on the model structure of POMO, which is the current standard baseline for construction-based NCO. As our framework is model-agnostic, one can easily promote cross-problem performance with more advanced base models in the future.

[4] Simulation-guided beam search for NCO. NeurIPS 2022.

W2. In Table 2, the performance of LKH3 should be given for VRP variants except for CVRP.

Thank you for your suggestion. We have incorporated the results in the revised Table 2.

W3. The problem scale is relatively small, only up to 100.

We understand and acknowledge your concern regarding the significance of performance on instances at a large scale. In order to address this concern, we have conducted additional experiments on two groups of instances: 1) randomly generated instances ranging in size from 100 to 500, and 2) benchmark instances from CVRPLib ranging in size from 30 to 1000, where the best-known solutions (BKS) provided by CVRPLIB were utilized as the baseline for comparison. The detailed experimental settings and results can be found in Appendix E in the revised paper.

We also report the results in the following two tables for a quick check. In the CVRPLib experiment, the 100 instances in Benchmark X are divided into four groups based on their problem size. According to the results, as the problem size increases, our unified model performs much better than POMO. For example, on the X problem with size 700-100, our model achieves a $13.8\%$ optimal gap, while the gap for POMO is $31.9\%$.

In addition, we want to acknowledge that the VRP variant with 100 nodes can have practical value in real-world applications as well as academic research. For example, all the 10,000 instances used for testing machine learning heuristics in the AAAI 2022 ML4OR workshop are of size 100 [1]. In addition, there are several recent works specific to large-scale generalization for construction-based NCO [2,3]. Our multi-task learning approach can be readily incorporated into that model for enhanced performance on large-scale problems.

[1] 10,000 optimal CVRP solutions for testing machine learning based heuristics. ML4OR workshop AAAI 2022.

[2] BQ-NCO: Bisimulation Quotienting for Efficient Neural Combinatorial Optimization. NeurIPS 2023 (to appear).

[3] Neural Combinatorial Optimization with Heavy Decoder: Toward Large Scale Generalization. NeurIPS 2023 (to appear).

W4. In Table 3, for evaluation results on VRPBTW, POMO-VRPTW outperforms the proposed method. The result is not logical since the proposed method learns more features and information but leading to inferior performance in comparison with POMO-VRPTW. More analysis on this result is expected.

As we have mentioned in W1b, we believe the reason is that the time window constraint used in our paper is much tighter than other attributes. As a result, ST_VRPTW generalizes well on tasks with time window constraints. We conducted experiments on training single-task model on VRPTW ST_VRPTW with different TW lengths $\Delta_i$ = {0.15, 1, 2 ,4} (small $\Delta_i$ represents tight TW constraint) and test the models on OVRPLTW and OVRPBTW. The results show that the gap becomes much worse compared to our multi-task learning with the increasing TW length (i.e., relaxing time window constraint).

W1b More analysis on the relations and effects of learning different tasks is expected.

Thank you for your valuable suggestion. We have conducted three sets of new experiments to further analyze the relation and effects of learning different tasks:

Correlation among Attributes: Similar to [3], we separately train our model on each pair of VRPs to investigate the pairwise correlation among tasks. As a result, we have a total $C(5,2) = 10$ pairwise combinations with respect to the $5$ basic VRPs (i.e., CVRP, VRPTW, OVRP, VRPB, and VRPL). The detailed experimental settings and results can be found in Appendix F. We also provide an anonymous link (https://drive.google.com/file/d/1CtOwsgayGxFURA8luqIfDLMeCAFOJC23/view?usp=sharing) for fast checking of the resulting correlation matrix, which measures the performance gap between each task pair and our unified model. The positive values represent a positive correlation between two VRPs, while negative values denote a conflict.

The results reveal that the CVRP, being a fundamental routing problem, has a positive correlation with all the other problems except for OVRP. The OVRP is found to exhibit the most severe conflicts among the attributes followed closely by the VRPTW. It aligns with our intuition that the open route conflicts with the other VRPs that force every route back to the depot. Similarly, time windows pose additional constraints on the choosing of the next node, which may significantly influence generalization performance, as we will discuss in W2.

[3] Which tasks should be learned together in multi-task learning? ICML 2020.

Distribution of Different VRPs: We have also conducted a comparison of distributions of different VRPs on the two-dimensional reduction space of the decoder hidden layer (1000 samples for each VRP), where the results can be found in Appendix F as well as an anonymous link for fast checking (https://drive.google.com/file/d/1syLwzAy9tRspsvjrPkqAT4vQ-xrR67HH/view?usp=sharing). According to the result, there is a clearly distinct distribution of VRPTW compared with others as the time window attribute poses a strong constraint over the route. In addition to VRPTW, OVRP also shows a different pattern compared to others followed by VRPB, as we have mentioned that OVRP does not force routes back to the depot. In contrast, CVRP and VRPL follow a very close distribution and overlap with each other in the majority of areas, which is also reflected in the close final distances. This can be attributed to the fact that our route length limit is set to 3 on the normalized coordinates, which is easily satisfied due to the tighter capacity constraint. The distribution analysis of the hidden layer aligns with the findings from our correlation matrix discussions.

Influence of the Degree of Constraint: In the second part of the experiments, we examine how the degree of constraint affects the correlation and zero-shot generalization performance. We illustrate this using an example of VRPTW (Vehicle Routing Problem with Time Windows). Specifically, we trained a single-task model on VRPTW (ST_VRPTW) with various TW lengths $\Delta_i$ = {0.15, 1 ,2 ,4} (where a smaller $\Delta_i$ represents a tighter TW constraint). We then evaluated the models on OVRPLTW and OVRPBTW. Our results reveal that as the TW length increases (i.e., the time window constraint is relaxed), the performance gap becomes larger compared to our multi-task learning approach. This can be attributed to the fact that the time window constraint, which is tightly enforced in our paper, is a dominant factor compared to other attributes that explain the strong generalization of ST_VRPTW on tasks with time window constraints.

Thank you very much for your time and effort in reviewing our work and providing valuable suggestions. We address your concerns as follows.

W1a The paper seems to simply add some VRP attributes as input to POMO and introduce an REINFORCE loss as multi-task loss. The novelty and contribution are relatively low.

In this work, rather than the simple multi-task learning, we investigate the attribute composition for NCO, which is a significant but less explored nature of many combinatorial optimization problems such as VRPs [1]. By only learning from a small number of problems with five fundamental attributes (capacity, time windows, open routes, backhauls, and duration limits), our model can easily generalize to tackle a larger number of problems with various combinations of these attributes in a zero-shot manner. This zero-shot generalization property is significantly different from a simple MTL problem and has not been investigated for neural combinatorial optimization. Our proposed attribute composition surpasses simply training all attributes as well as single-task learning in zero-shot generalization.

In addition, the implementation of both our unified model and baseline methods on 11 VRPs provides promising and valuable baselines to the research community. Most of these VRPs have not been studied yet using neural solvers but are commonly used in real-world applications [1][2].

Therefore, we believe our proposed method is novel and could make a good contribution to neural combinatorial optimization.

[1] Heuristics for multi-attribute vehicle routing problems: A survey and synthesis. European Journal of Operational Research, 2013.

[2] The vehicle routing problem: State of the art classification and review. Computers & industrial engineering, 2016.

Thank you again for your time and effort in reviewing our work. There is only less than 1 day left to the rebuttal deadline, and we sincerely want to know whether our responses can successfully address all your concerns. We are glad to continually improve our work to address them.