Thank you for the implementation, it gives very promising results in our use case. However, it seems the program segfaults if the number of vehicles is too low for the particular problem:

Program$ ./genvrp ../Instances/CVRP/CMT1.vrp  ../test.sol -seed 1 -veh 2
----- READING DATA SET: ../Instances/CVRP/CMT1.vrp
----- INSTANCE LOADED WITH 50 CLIENTS AND 2 VEHICLES
----- BUILDING INITIAL POPULATION
Segmentation fault (core dumped)

The code above runs the algorithm and returns the solution if -veh is increased to 5.

Hi, I'd like to use your code in java. It looks pretty good but I don't understand the structure of the datasets. I was wondering if you have a more detailed description of it. Thanks in advance!

Is it possible that setting duration_limit when we have a large quantity of data brings the algorithm into a soft lock state where it fails to build the initial population ?

For some reason, the git actions designed to test the code started failing recently after a commit that only involved the README.md (https://github.com/vidalt/HGS-CVRP/actions/runs/3420070648). As the considered update had no impact on the code, it seems that some configuration or upgrade in the way git actions run makes the experiment fail. So far, we know that only the Windows action fails (the others get automatically canceled as a consequence). @chkwon tested the code locally on Windows, and everything worked fine. I'm not personally an expert on Git actions and could not pinpoint so far where the issue is; anyone has a clue?

Is the distance matrix that we pass as input to the algorithm made of spatial or temporal distances? Because looking at the Individual.cpp section, it seems that the distances are indeed temporal! In case the distance are spatial, is it possible to use temporal distances?
Thank you in advance for your attention.

great job.
could it solve Leuven2 instance, which have 4000 customers.
see http://vrp.atd-lab.inf.puc-rio.br/index.php/en/
under Arnold, Gendreau and Sörensen (2017)

I am confused about the calculation of BiasedFitnesses.

The calculation of BiasedFitnesses seems not consistent with that given in the paper (Hybrid genetic search for the CVRP: Open-source implementation and SWAP* neighborhood)

In this HGS-CVRP code it looks like this:

In the paper it is formulated as:

I suppose the difference is that the divRank in the source code is actually the ranking of fitness while fitRank is the ranking of diversity.

It seems the current implementation enforces one route per vehicle. Assume we have one vehicle with CAPACITY 1 and two nodes each with DEMAND 1, and the DURATION is set to 5. Let the travel time between Depot -> 1 -> Depot equal 2 and Depot -> 2 -> Depot equal 2. I would like to extend the current implementation in such a way that it creates the following route: Route #1: 0 1 0 2 0. Can you maybe give me a hint how to start to implement this feature?

Of course in the actual use case we have multiple vehicles and many shops to serve.

I am bringing our VRPTW solver under test, by writing unit tests for most code points. It's an immense amount of work, but it's going well. This testing effort forces me to look at every bit of code in considerable detail, to determine how it works and how to encode that in meaningful test cases.

I am currently testing our implementation of the broken pairs distance (BPD) measure. HGS-CVRP also uses this, and ours is a direct descendant of your efforts. There are two issues that I noticed with our relatively unmodified broken pairs distance:

1. The code (in various places) assumes it is symmetric, that is, BPD(X, Y) == BPD(Y, X). For example, here, where it is computed only once but used in both ways:
   

   HGS-CVRP/Program/Population.cpp

   Lines 35 to 40 in 387b5c5

   	for (Individual * myIndividual2 : subpop)
   	{
   	double myDistance = brokenPairsDistance(*myIndividual,*myIndividual2);
   	myIndividual2->indivsPerProximity.insert({ myDistance, myIndividual });
   	myIndividual->indivsPerProximity.insert({ myDistance, myIndividual2 });
   	}

2. The BPD distance as currently implemented is not symmetric. A fairly minimal example are individuals with the following two route sets: X = {{1, 2, 3, 4}, {}, {}} and Y = {{1, 2}, {3}, {4}}. Now, BPD(X, Y) = 2, but BPD(Y, X) = 3. The issue is a double increment for a single client when both conditions here are true:
   

   HGS-CVRP/Program/Population.cpp

   Lines 225 to 234 in 387b5c5

   	double Population::brokenPairsDistance(const Individual & indiv1, const Individual & indiv2)
   	{
   	int differences = 0;
   	for (int j = 1; j <= params.nbClients; j++)
   	{
   	if (indiv1.successors[j] != indiv2.successors[j] && indiv1.successors[j] != indiv2.predecessors[j]) differences++;
   	if (indiv1.predecessors[j] == 0 && indiv2.predecessors[j] != 0 && indiv2.successors[j] != 0) differences++;
   	}
   	return (double)differences / (double)params.nbClients;
   	}

   
   My fix for this has been to merge the two conditions into a single update, as follows:

   if ((indiv1.successors[j] != indiv2.successors[j] && indiv1.successors[j] != indiv2.predecessors[j])
           || (indiv1.predecessors[j] == 0 && indiv2.predecessors[j] != 0 && indiv2.successors[j] != 0))
       differences++;

   This passes all the symmetry tests I have so far thrown at it.

I am not sure if this is a "bug", but is definitely something I struggled understanding for a while. Am I misunderstanding BPD as it is implemented now?

For tests involving successive runs until a time limit is reached, the algorithm/population is reset each time maxIterNonProd is reached. From my analysis of the code, the population is completely reset, but the next run starts with the last offspring of the previous run. Is that intended behavior? I'm asking this because it is very important for our current research to know if each run is completely independent from other runs during the same execution of the program.

In this piece of code the population and the iteration counter are reset, but not offspring:

And offspring is used in the beginning of the main loop:

crossoverOX method does not seem to completely overwrite offspring: some of the not-overwritten values are used in localSearch.run (namely chromR).

Thanks!

As mentioned in the paper "Vidal, T. (2022). Hybrid genetic search for the CVRP: Open-source implementation and SWAP* neighborhood.", the fitness in HGS is based on objective value and diversity considerations with formula (1).

The diversity is measured as its average broken-pairs distance; We found the calculation of diversity rank in the function updateBiasedFitnesses() is as follows:
double divRank = (double)i / (double)(pop.size() - 1);
while the solution quality is
double fitRank = (double)ranking[i].second / (double)(pop.size() - 1);

Are these two calculations reversed? Maybe it should be:
double divRank = (double)ranking[i].second / (double)(pop.size() - 1);
double fitRank = (double)i / (double)(pop.size() - 1);

since the ranking store the averageBrokenPairsDistance
ranking.push_back({-pop[i]->averageBrokenPairsDistanceClosest(params->nbClose),i});

I apologize for all these issues, but these are doubts I need to clarify: I am using your algorithm along with a Python wrapper created by Changhyun Kwon. By installing the hygese library with pip, I am able to run the algorithm successfully in Python (except for the issue related to the previous duration_limit issue). I have modified the C code and compiled the shared library (following the instructions on your algorithm's GitHub page) to allow Changhyun Kwon's Python wrapper to use my modified version of C (the library in question is libhgscvrp.so). The tests conducted via the terminal are good and end with success. However, when I try to use the algorithm with the Python wrapper, I consistently get 0 iterations. Clearly, there is an issue! The folder where I copy libhgscvrp.so is the same folder where the "functional" library is installed using "pip install hygese". Additionally, there are differences in size between the library compiled following your instructions and the one downloaded via pip. Could you please provide some solutions to this problem?

I apologize for the inconvenience and thank you for your attention while awaiting your response.

Dev Environment

• CMake, .gitignore #8 #9
• Use CMake and ctest in CI actions to check the solution correctness #14

Interface

• time measure improvement, floating timeLimit47848a5 623d821
• refactoring Params, file read by CVRPLIB #13
• Algorithm parameters control #16
• extern "C" interface for Python/Julia wrappers #18

New features

• verbose control for solver logs #15
• turn off SWAP* local search for dist_mtx only instances #20
• better handling of duration constraints
• improve CVRPLIB to handle more general .vrp files, e.g. instances without coordinates

Testing

• test for instances with duration constraints #22

When I use a instance with small customers for example 15, then start is greater than end. so the while loop can't be stopped.
Don't we need to check whether start is greater than end?

This is to brainstorm wrapper package names of Julia and Python.

Python

There are three names required, which can be the same, or different.

• Project Name (say, the GitHub repository name)
• pip package name (to be used when we install the package: pip install packagename)
• module name (to be used when we import the module: import modulename)

Examples:

• PyTorch / torch / torch
• PyConcorde / pyconcorde / concorde
• elkai / elkai / elkai (a python wrapper for LKH)
• NumPy / numpy / numpy
• PyVroom / pyvroom / vroom

Python style guide says:

Modules should have short, all-lowercase names. Underscores can be used in the module name if it improves readability. Python packages should also have short, all-lowercase names, although the use of underscores is discouraged.

I think the Project Name can be anything, but it will be better to make the package name and the module name the same.

Some ideas for the package/module name:

1. hgscvrp
2. hygese
3. hygesecvrp
4. hgs_cvrp (the use of underscores is discouraged)
   ...

Julia

There is only one name to determine: PackageName.jl.

The GitHub repo will be called PackageName.jl.
When we install, we will type add PackageName.
When we use it in the code, we will type using PackageName.

The package naming guidelines are given here. It needs to be CamelCase without hyphen or underscore.

Some examples:

• DifferentialEquations.jl
• Pluto.jl
• DiffEqFlux.jl
• NeuralPDE.jl
• Convex.jl
• PATHSolver.jl

Julia generally doesn't like all capital letters, but we could probably make a case, since the original C++ code is called HGS-CVRP. In that case, it will be called HGSCVRP.jl, which could a little difficult to read and type.

Some ideas:

1. HGSCVRP.jl
2. Hygese.jl
3. HygeseCVRP.jl
4. HgsCvrp.jl
5. HybridGeneticSearchCVRP.jl
   ...

In general, I think the benefit of having both HGS and CVRP in the name is clear. On the other hand, using only HGS or its variant can leave the door open to the possibility that the package extends to HGS like algorithms applied in other types of routing/transportation problems. But this may not be important at this moment.

Please let me know if you have any suggestions. To satisfy the two different style guidelines with a single name for both Python and Julia, I ended up with hygese or Hygese.jl, while keeping usability, readability, and consistency, but sacrificing some clarity. But maybe we don't need to use the same name for Python and Julia. Let me know what you think.

The latest updates to the repository had been done over the dev branch but stashed+merged on the main branch. This had led to a different commit history on both branches, which is problematic for a long-lived branch such as dev. To correct this situation, I have made a copy of dev into dev-old to preserve access to un-stashed older commits, and resetted dev to the main branch head.

Therefore, before editing the code, make sure you have checked out the current state of the dev branch. Contact me if you encounter any issues. In the future, I will only register clean (aggregated commits) on the dev branch and directly merge them (without stash) into the main, so we will not encounter again this issue.

Kind Regards,
--Thibaut

Hello, I tried simple vrp file that works in lkh-3 and in your solver it is not supported. Can the solver find a solution for ACVRP instances ?

NAME : SIMPLE_TEST
TYPE : ACVRP
EDGE_WEIGHT_TYPE : EXPLICIT
EDGE_WEIGHT_FORMAT : FULL_MATRIX
DIMENSION : 3
VEHICLES : 2
CAPACITY : 2
EDGE_WEIGHT_SECTION
0 2 0 100 0 1000 0 0 0
DEMAND_SECTION
1 1
2 1
3 0
DEPOT_SECTION
3
EOF

The code gives a very cryptic terminate called after throwing an instance of 'char const*' error when failing the distance or demand checks. This seems to be fixed by adding std::string after the throw keywords (as is done in other places in the code). See #1