DOCSEARCHbyAlgolia
Submit Docs

HGS-CVRP

repository·main·Indexed 19 days ago

https://github.com/vidalt/hgs-cvrp

A highly optimized implementation of the Hybrid Genetic Search (HGS) algorithm for the Capacitated Vehicle Routing Problem (CVRP). It features advanced diversity control and a specialized SWAP* neighborhood to efficiently solve medium-scale instances of up to 1,000 customers. The project provides a standalone executable, a shared library for C/C++ integration, and wrappers for Python (PyHygese) and Julia (Hygese.jl).

Tokens
1.6K
Snippets
3
Records
6
Agent score
16%

What's inside hgs-cvrp

  1. Run the HGS-CVRP algorithm

    main

    Once the hgs executable is built, you can run it by providing an instance path and a solution path.

    Example usage:

    ./hgs ../Instances/CVRP/X-n157-k13.vrp mySolution.sol -seed 1 -t 30

    Command Syntax

    ./hgs instancePath solPath [-it nbIter] [-t myCPUtime] [-bks bksPath] [-seed mySeed] [-veh nbVehicles] [-log verbose]

    Primary Options

    OptionTypeDescription
    -it <int>integerMaximum number of iterations without improvement. Defaults to 20,000.
    -t <double>doubleTime limit in seconds. If set, the code runs iteratively until the limit is reached.
    -seed <int>integerFixed seed for reproducibility. Defaults to 0.
    -veh <int>integerPrescribed fleet size. Otherwise, a reasonable upper bound is calculated.
    -round <bool>booleanRound distance to nearest integer. 1 for rounding (default, recommended for X instances), 0 for no rounding (e.g., CMT or Golden instances).
    -log <bool>booleanVerbose level of the algorithm log. 1 for enabled (default), 0 for disabled.
    -bks <path>pathPath to best known solution (bksPath).

    Additional Parameters

    OptionTypeDescription
    -nbIterTraces <int>integerIterations between trace displays. Defaults to 500.
    -nbGranular <int>integerGranular search parameter (limits moves in RI local search). Defaults to 20.
    -mu <int>integerMinimum population size. Defaults to 25.
    -lambda <int>integerGeneration size (solutions created before reaching max population). Defaults to 40.
    -nbElite <int>integerNumber of elite individuals. Defaults to 5.
    -nbClose <int>integerNumber of closest solutions considered for diversity calculation. Defaults to 4.
    -nbIterPenaltyManagement <int>integerIterations between penalty updates. Defaults to 100.
    -targetFeasible <double>doubleTarget ratio of feasible individuals between penalty updates. Defaults to 0.2.
    -penaltyIncrease <double>doublePenalty increase if insufficient feasible individuals. Defaults to 1.2.
    -penaltyDecrease <double>doublePenalty decrease if sufficient feasible individuals. Defaults to 0.85.
    ./hgs ../Instances/CVRP/X-n157-k13.vrp mySolution.sol -seed 1 -t 30

  2. Compile the HGS-CVRP shared library

    main

    To use the HGS-CVRP algorithm within your own C/C++ code, you can build it as a shared library. Use the following commands:

    mkdir build
cd build
cmake .. -DCMAKE_BUILD_TYPE=Release -G "Unix Makefiles"
make lib

    This generates the following library files in the build directory:

    • Linux: libhgscvrp.so
    • macOS: libhgscvrp.dylib
    • Windows: hgscvrp.dll

    You can test the shared library integration using the provided C test:

    make lib_test_c
ctest -R lib --verbose

  4. Compile the HGS-CVRP executable

    main

    To compile the standalone hgs executable, you need CMake installed. Use the following commands to build the project in Release mode using Unix Makefiles:

    mkdir build
cd build
cmake .. -DCMAKE_BUILD_TYPE=Release -G "Unix Makefiles"
make bin

    This generates the hgs executable in the build directory. You can verify the build by running tests with:

    ctest -R bin --verbose
    mkdir build
cd build
cmake .. -DCMAKE_BUILD_TYPE=Release -G "Unix Makefiles"
make bin

  5. Run the HGS-CVRP algorithm via CLI

    main

    The main entrypoint of the HGS-CVRP executable orchestrates the Hybrid Genetic Search for the Capacitated Vehicle Routing Problem. The execution flow follows these steps:

    1. Argument Parsing: Uses CommandLine to parse input parameters, instance paths, and output paths.
    2. Instance Loading: Loads a CVRPLIB format instance using InstanceCVRPLIB.
    3. Parameter Initialization: Initializes a Params object containing coordinates, distance matrices, demands, capacities, and algorithm parameters (ap).
    4. Solver Execution: Runs the Genetic solver using the provided parameters.
    5. Result Export: If a solution is found, it exports the best solution in CVRPLIB format and saves the search progress to a .PG.csv file.

    Note: The program handles exceptions by printing the error message to standard output.

    // Conceptual usage flow within the executable
CommandLine commandline(argc, argv);
InstanceCVRPLIB cvrp(commandline.pathInstance, commandline.isRoundingInteger);
Params params(cvrp.x_coords, cvrp.y_coords, cvrp.dist_mtx, ...);

Genetic solver(params);
solver.run();

if (solver.population.getBestFound() != NULL) {
    solver.population.exportCVRPLibFormat(*solver.population.getBestFound(), commandline.pathSolution);
    solver.population.exportSearchProgress(commandline.pathSolution + ".PG.csv", commandline.pathInstance);
}

  6. Understand the HGS-CVRP algorithm progress output

    main

    The algorithm outputs progress to standard output in the following format:

    It [N1] [N2] | T(s) [T] | Feas [NF] [BestF] [AvgF] | Inf [NI] [BestI] [AvgI] | Div [DivF] [DivI] | Feas [FeasC] [FeasD] | Pen [PenC] [PenD]

    Key Definitions:

    • [N1], [N2]: Total iterations and iterations without improvement.
    • [T]: CPU time elapsed.
    • [NF], [NI]: Number of feasible and infeasible solutions in subpopulations.
    • [BestF], [BestI]: Value of the best feasible and infeasible solution in subpopulations.
    • [AvgF], [AvgI]: Average value of solutions in feasible and infeasible subpopulations.
    • [DivF], [DivI]: Diversity of feasible and infeasible subpopulations.
    • [FeasC], [FeasD]: Percentage of naturally feasible solutions regarding capacity and duration constraints.
    • [PenC], [PenD]: Current penalty level per unit of excess capacity and duration.