DER-Solomon: A Large Number of CVRPTW Instances Generated Based on the Solomon Benchmark Distribution

Thank you for your helpful comments and great efforts in helping improve our work. The responses to your comments are listed as follows.

Q1. The practicality is not clear: Is there any evidence to demonstrate that, with only 56 instances, the original Solomon benchmark is complex enough to test all aspects of (traditional or DL-based) algorithms? If a company trains a DL-based model on DER-Solomon, could we guarantee its reliability in practice?

A1. Thank you for your insightful comments. It’s challenging to directly apply the model trained on the Solomon benchmark to real-world problems. We need to further collect real-world data and use our method to expand the collected data as training instances. Since most traditional algorithms demonstrate their performance on the Solomon benchmark, our work in this paper mainly constructs a dataset for training so that DRL algorithms can also show their inherent performance on the Solomon benchmark. This allows for a fair comparison between traditional algorithms and DRL algorithms, accelerating algorithm research in this field.

Q2. Is the proposed method generalizable to approximate other datasets?

A2. Thank you for your helpful comments. We have included additional expanded instances, validated through a comparison experiment on the Homberger benchmark, in the appendix of the updated manuscript. In the final version of the paper, we will add approximations for most of the public test benchmark in the VRP field. Due to time limits, experiments on them will be gradually released in the open-source code.

Q3. It seems only the distribution of the time window is approximated. However, other attributes, such as the customer location, may significantly affect the learned policy as well. Have you considered the variations of all attributes in DER-Solomon?

A3. Thank you for your thoughtful comments. We did take into account the point you raised, but we concluded that for a DRL method, it is not necessary to account for variations in customer coordinates between instances of the same series in the Solomon benchmark, as they remain fixed.

Q4. For the traditional algorithms, it would be better to add HGS. For the DL-based method, some recent studies [1, 2] demonstrate superior performance on CVRPTW, it would be better to benchmark them as well.

A4. Thank you for your thoughtful comments. Both papers used HGS, thus, we believe it should be a very useful solver. However, we noticed that HGS only has CVRP code implementation, and we are unsure whether it can be applied to CVRPTW. Article [1] is a great work, and the key is that there is a source code implementation. The README file is written in great detail, and the author have put a lot of effort into it. Thank you very much for recommending this article. We are very willing to use this algorithm in our experiment. Article [2] is also a great work, but we do not know whether it has source code published. If no source code is published and the author has not published the experimental results of the algorithm on the Solomon benchmark, it is challenging to conduct an experiment on it.

Q5. The provided link to the source code cannot be opened.

A5. Thank you for your insightful comments. Please compare the link you entered into the browser with the link in the pdf file. Because the underscore “_” may be lost during the pasting process, we made a reminder at the first source code reference on page 7 of the article.

Thank you for your insightful comments and great efforts in helping improve our work. The responses to your comments are listed as follows.

Q1. The paper lacks background descriptions of the CVRP and CVRPTW problems and also probably some more detailed introductions on the existing traditional algorithm approaches. Given there is plenty of space for the paper, such background information could be very beneficial to the audience. VRP may be well-known in the community, but the variants are probably not.

A1. Thank you for your helpful comments. To make the background descriptions clearer, we have added more background information on the CVRP and CVRPTW, as well as detailed introductions to existing traditional algorithm approaches in the updated manuscript.

Q2. A lot of details are not presented in the paper. E.g., given the estimated distributions of the parameters, how are the new instances sampled? Are all parameters considered independently? Why generate 1280k instances? Moreover, there are no given details on how the DRL model is trained using DER-Solomon.

A2. Thank you for your insightful comments. We sincerely apologize for any lack of detail in certain areas. Given the complexity of the subject matter, it can be challenging to cover every aspect in depth. To address this, we plan to release the source code in the final version of the paper. This will allow for a more comprehensive understanding as many details can be directly gleaned from the code.

• New instances are generated by random sampling from the estimated distributions.
• All parameters are considered independently. However, in Solomon's public test instance and another public test instance of CVRPTW, Homberger changes between instances, except for the time window variable, while other variables remain fixed. So, we also kept other variables fixed in the new instance, and only one variable changed. Whether other variables are independent of each other is irrelevant.
• The reason for generating 1280k instances is that most of the DRL algorithms solving VRP after 2019 are based on the transformer network and attention mechanism. The first author [1] to use this method set the training dataset to 1280k instances in his open-source code, so most subsequent researchers have followed suit.
• We didn’t mentioned in this paper how the DRL model is trained using DER-Solomon because the cited DRL algorithms, AM, MDAM, POMO, and MARDAM, all have source code released, and their articles also detailed their network structure and training methods. As for the training process, in short, the coordinates, demand, and time window data of DER-Solomon are input into the DRL network, and then the DRL network will plan a path that meets the time window and load constraints for each instance. The negative value of the average path length is used as the reward value, and the DRL network is trained using the gradient optimization algorithm.

[1] Kool, W, Van Hoof H, and Welling M. "Attention, Learn to Solve Routing Problems!." International Conference on Learning Representations. 2018.

Q3. The technical contribution is limited. It mainly estimates the distributions of a given small dataset to generate instances to form a larger dataset. It does not compare the proposed sampling method to some more basic methods. For example, what if we just add Gaussian noises to parameters in Solomon or use some uniform sampling to generate the instances.

A3. Thank you for your thoughtful comments. In fact, not only public test instances, but our original starting point was to consider the problems that may be encountered in actual situations when the available dataset is small. Imagine there is a logistics company, or a company that provides decision system solutions to logistics companies. In order to seize the first-mover advantage in the market, it’s crucial to act proactively when there are indications of a developing business scenario. This involves implementing an intelligent logistics and transportation planning system even before the scenario fully matures. At this time, the instances that can be collected in the business scenario are very few, and it may not even represent the characteristics of all future instances, but it needs to speculate on all future instances. Therefore, we assumed 11 forms of popular distribution functions and selected the one with the best goodness of fit. The 11 forms of distribution functions are the crystallization of human statistical technology over the past hundreds of years, not just a summary of the current few instances. This cannot be achieved by adding Gaussian noise and random sampling. The instances generated by Gaussian noise can only represent the characteristics of the current few instances, to a certain extent, they are just replicas of the current instances.

Thank you for your encouraging comments and great efforts in helping improve our work. The responses to your comments are listed as follows.

Q1. Besides the Solomon benchmark, the Gehring & Homberger benchmark is also a famous one of CVRPTW. It is better to further apply the proposed data generation method to the Gehring & Homberger benchmark.

A1. Thank you for your insightful suggestion. We have recorded the expanded dataset of the Gehring & Homberger benchmark in the appendix of the updated manuscript, along with some of our experimental results. The experimental verification process is time-consuming, given that each of the six series requires individual training. Furthermore, each series encompasses five different customer point scales, which also necessitate separate training. This results in a total of 30 training models, and that is just for one Deep Reinforcement Learning (DRL) method.

If we consider all three DRL methods mentioned in the article (i.e. AM, POMO, and MDAM), we would need to train a staggering 90 models. However, we will continue to update the remaining experiments and those extended to other optimization problems periodically on the source code, much like the author of AM, who has diligently maintained his source code for over two years.

Q2. How many instances are included in the DER-Solomon benchmark.

A2. As briefly mentioned in Appendix A.3, we used 1,280,000 DER-Solomon instances as the training set. In addition, during testing, 1024 instances were used as the test set in Tables 1 and 2. However, it's important to note that the DER-Solomon benchmark is not a fixed set of instances. It is more of an instance generation method that provides a distribution function of instances, generating a large number of training instances through random sampling to help the DRL method test its performance on Solomon.

Q3. How many DER-Solomon instances are used to train the learning-based method.

A3. As briefly mentioned in Appendix A.3, we used 1,280,000 DER-Solomon instances as the training set.

Q4. What and how many original Solomon instances are used to train the learning-based method.

A4. We opted not to use the original Solomon instances as part of the training set, given that they are ultimately designated as the test set. Instead, all training data exclusively comprises DER-Solomon instances.

Q5. How to calculate the std gaps reported in Table 1? They seem to be unequal to the relative gaps between the std values of two benchmarks

A5. We always set the denominator to be the mean. The calculation method of the gap is:

std gap: abs (std on Solomon – std on DER-Solomon ) / mean on Solomon.

mean gap: abs (mean on Solomon – mean on DER-Solomon ) / mean on Solomon.

And we have explained it in Table 1 in the updated manuscript.

Thank you for your thoughtful comments and great efforts to help improve our work. The responses to your comments are listed as follows.

Q1. The comparison with neural solvers is missed in Table 1.

A1. The purpose of Table 1 is to compare the differences between DER-Solomon and Solomon, not the differences between different algorithms. To clarify the manuscript, we have added vertical lines between algorithms and have made annotations at the bottom of Table 1. In addition, the comparison between algorithms are recorded in appendix Table 5.

Q2. The figures are not well presented. Also hard to find the relevant descriptions. This paper is not ready to be published.

A2. Thank you for your thoughtful comments. To make the figures present clear, we have described more content in legends of the figures and have made some essential explanations in the titles of the figures. We have utilized the PDF format for some Figures while rendering others in higher resolution for improved visual quality.

Thanks for your effort and timely reply, I will keep my score. In addition, I strongly encourage authors to consider applying this algorithm to scale more benchmarks.