[![CI_Build](https://github.com/vidalt/HGS-CVRP/actions/workflows/CI_Build.yml/badge.svg)](https://github.com/vidalt/HGS-CVRP/actions/workflows/CI_Build.yml)
# HGS-CVRP: A modern implementation of the Hybrid Genetic Search for the CVRP
This is a modern implementation of the Hybrid Genetic Search (HGS) with Advanced Diversity Control of [1], specialized to the Capacitated Vehicle Routing Problem (CVRP).
This algorithm has been designed to be transparent, specialized, and highly concise, retaining only the core elements that make this method successful.
Beyond a simple reimplementation of the original algorithm, this code also includes speed-up strategies and methodological improvements learned over the past decade of research and dedicated to the CVRP.
In particular, it relies on an additional neighborhood called SWAP*, which consists in exchanging two customers between different routes without an insertion in place.
## References
When using this algorithm (or part of it) in derived academic studies, please refer to the following works:
[1] Vidal, T., Crainic, T. G., Gendreau, M., Lahrichi, N., Rei, W. (2012).
A hybrid genetic algorithm for multidepot and periodic vehicle routing problems. Operations Research, 60(3), 611-624.
https://doi.org/10.1287/opre.1120.1048 (Available [HERE](https://w1.cirrelt.ca/~vidalt/papers/HGS-CIRRELT-2011.pdf) in technical report form).
[2] Vidal, T. (2022). Hybrid genetic search for the CVRP: Open-source implementation and SWAP* neighborhood. Computers & Operations Research, 140, 105643.
https://doi.org/10.1016/j.cor.2021.105643 (Available [HERE](https://arxiv.org/abs/2012.10384) in technical report form).
We also recommend referring to the Github version of the code used, as future versions may achieve better performance as the code evolves.
The version associated with the results presented in [2] is [v1.0.0](https://github.com/vidalt/HGS-CVRP/releases/tag/v1.0.0).
## Other programming languages
There exist wrappers for this code in the following languages:
* **C**: The **C_Interface** file contains a simple C API
* **Python**: The [PyHygese](https://github.com/chkwon/PyHygese) package is maintained to interact with the latest release of this algorithm
* **Julia**: The [Hygese.jl](https://github.com/chkwon/Hygese.jl) package is maintained to interact with the latest release of this algorithm
We encourage you to consider using these wrappers in your different projects.
Please contact me if you wish to list other wrappers and interfaces in this section.
## Scope
This code has been designed to solve the "canonical" Capacitated Vehicle Routing Problem (CVRP).
It can also directly handle asymmetric distances as well as duration constraints.
This code version has been designed and calibrated for medium-scale instances with up to 1,000 customers.
It is **not** designed in its current form to run very-large scale instances (e.g., with over 5,000 customers), as this requires additional solution strategies (e.g., decompositions and additional neighborhood limitations).
If you need to solve problems outside of this algorithm's scope, do not hesitate to contact me at <thibaut.vidal@polymtl.ca>.
## Compiling the executable
You need [`CMake`](https://cmake.org) to compile.
Build with:
```console
mkdir build
cd build
cmake .. -DCMAKE_BUILD_TYPE=Release
make bin
```
This will generate the executable file `hgs` in the `build` directory.
Test with:
```console
ctest -R bin --verbose
```
## Running the algorithm
After building the executable, try an example:
```console
./hgs ../Instances/CVRP/X-n157-k13.vrp mySolution.sol -seed 1 -t 30
```
The following options are supported:
```
Call with: ./hgs instancePath solPath [-it nbIter] [-t myCPUtime] [-bks bksPath] [-seed mySeed] [-veh nbVehicles] [-log verbose]
[-it <int>] sets a maximum number of iterations without improvement. Defaults to 20,000
[-t <double>] sets a time limit in seconds. If this parameter is set, the code will be run iteratively until the time limit
[-seed <int>] sets a fixed seed. Defaults to 0
[-veh <int>] sets a prescribed fleet size. Otherwise a reasonable UB on the fleet size is calculated
[-round <bool>] rounding the distance to the nearest integer or not. It can be 0 (not rounding) or 1 (rounding). Defaults to 1.
[-log <bool>] sets the verbose level of the algorithm log. It can be 0 or 1. Defaults to 1.
Additional Arguments:
[-nbGranular <int>] Granular search parameter, limits the number of moves in the RI local search. Defaults to 20
[-mu <int>] Minimum population size. Defaults to 25
[-lambda <int>] Number of solutions created before reaching the maximum population size (i.e., generation size). Defaults to 40
[-nbElite <int>] Number of elite individuals. Defaults to 5
[-nbClose <int>] Number of closest solutions/individuals considered when calculating diversity contribution. Defaults to 4
[-targetFeasible <double>] target ratio of feasible individuals in the last 100 generatied individuals. Defaults to 0.2
```
There exist different conventions regarding distance calculations in the academic literature.
The default code behavior is to apply integer rounding, as it should be done on the X instances of Uchoa et al. (2017).
To change this behavior (e.g., when testing on the CMT or Golden instances), give a flag `-round 0`, when you run the executable.
## Code structure
The main classes containing the logic of the algorithm are the following:
* **Params**: Stores the main data structures for the method
* **Individual**: Represents an individual solution in the genetic algorithm, also provides I/O functions to read and write individual solutions in CVRPLib format.
* **Population**: Stores the solutions of the genetic algorithm into two different groups according to their feasibility. Also includes the functions in charge of diversity management.
* **Genetic**: Contains the main procedures of the genetic algorithm as well as the crossover
* **LocalSearch**: Includes the local search functions, including the SWAP* neighborhood
* **Split**: Algorithms designed to decode solutions represented as giant tours into complete CVRP solutions
* **CircleSector**: Small code used to represent and manage arc sectors (to efficiently restrict the SWAP* neighborhood)
In addition, additional classes have been created to facilitate interfacing:
* **AlgorithmParameters**: Stores the parameters of the algorithm
* **CVRPLIB** Contains the instance data and functions designed to read input data as text files according to the CVRPLIB conventions
* **commandline**: Reads the line of command
* **main**: Main code to start the algorithm
* **C_Interface**: Provides a C interface for the method
## Compiling the shared library
You can also build a shared library to call the HGS-CVRP algorithm from your code.
```console
mkdir build
cd build
cmake .. -DCMAKE_BUILD_TYPE=Release
make lib
```
This will generate the library file, `libhgscvrp.so` (Linux), `libhgscvrp.dylib` (macOS), or `hgscvrp.dll` (Windows),
in the `build` directory.
To test calling the shared library from a C code:
```console
make lib_test_c
ctest -R lib --verbose
```
## Contributing
Thank you very much for your interest in this code.
This code is still actively maintained and evolving. Pull requests and contributions seeking to improve the code in terms of readability, usability, and performance are welcome. Development is conducted in the `dev` branch. I recommend to contact me beforehand at <thibaut.vidal@polymtl.ca> before any major rework.
As a general guideline, the goal of this code is to stay **simple**, **stand-alone**, and **spec
没有合适的资源?快使用搜索试试~ 我知道了~
混合遗传搜索 (HGS)算法 的现代实现,专门针对有能力的车辆路径问题 (CVRP)_C++_代码_下载
共163个文件
vrp:134个
h:11个
cpp:10个
1.该资源内容由用户上传,如若侵权请联系客服进行举报
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
版权申诉
0 下载量 169 浏览量
2022-06-19
19:04:18
上传
评论 1
收藏 508KB ZIP 举报
温馨提示
混合遗传搜索 (HGS) 算法的现代实现,专门针对有能力的车辆路径问题 (CVRP) 该算法被设计为透明、专业和高度简洁,仅保留使该方法成功的核心元素。除了对原始算法的简单重新实现之外,此代码还包括加速策略和在过去十年的研究中学到的并致力于 CVRP 的方法改进。特别是,它依赖于一个名为 SWAP* 的附加邻域,该邻域包括在不同路径之间交换两个客户而无需插入到位 代码结构 包含算法逻辑的主要类如下: Params:存储方法的主要数据结构 Individual:表示遗传算法中的一个个体解,也提供I/O函数来读写CVRPLib格式的个体解。 人口:根据可行性将遗传算法的解决方案存储到两个不同的组中。还包括负责多样性管理的职能。 遗传:包含遗传算法的主要程序以及交叉 LocalSearch:包括本地搜索功能,包括 SWAP* 邻域 拆分:旨在将解决方案解码为完整的 CVRP 解决方案的算法 CircleSector:用于表示和管理弧形扇区的小代码(有效限制 SWAP* 邻域) 此外,还创建了其他类以促进接口: AlgorithmParameters:存储算法的参数 CVRPLIB包含
资源推荐
资源详情
资源评论
收起资源包目录
混合遗传搜索 (HGS)算法 的现代实现,专门针对有能力的车辆路径问题 (CVRP)_C++_代码_下载 (163个子文件)
test.c 6KB
TestExecutable.cmake 589B
LocalSearch.cpp 30KB
Population.cpp 12KB
Split.cpp 8KB
Params.cpp 5KB
C_Interface.cpp 4KB
InstanceCVRPLIB.cpp 3KB
Genetic.cpp 3KB
Individual.cpp 2KB
main.cpp 1KB
AlgorithmParameters.cpp 1KB
.gitignore 474B
LocalSearch.h 8KB
commandline.h 6KB
Population.h 5KB
Split.h 4KB
Params.h 4KB
Individual.h 3KB
Genetic.h 2KB
CircleSector.h 2KB
AlgorithmParameters.h 1KB
C_Interface.h 971B
InstanceCVRPLIB.h 722B
LICENSE 1KB
README.md 9KB
CMakeLists.txt 2KB
CMakeLists.txt 369B
X-n979-k58.vrp 18KB
X-n1001-k43.vrp 18KB
X-n957-k87.vrp 17KB
X-n936-k151.vrp 17KB
X-n895-k37.vrp 16KB
X-n876-k59.vrp 16KB
X-n916-k207.vrp 16KB
X-n819-k171.vrp 15KB
X-n856-k95.vrp 15KB
X-n837-k142.vrp 15KB
Golden_4.vrp 14KB
X-n783-k48.vrp 14KB
X-n801-k40.vrp 14KB
X-n749-k98.vrp 14KB
Golden_16.vrp 14KB
X-n766-k71.vrp 14KB
Golden_12.vrp 13KB
Golden_8.vrp 13KB
X-n716-k35.vrp 13KB
X-n733-k159.vrp 13KB
X-n685-k75.vrp 13KB
X-n701-k44.vrp 12KB
Golden_3.vrp 12KB
X-n670-k130.vrp 12KB
X-n641-k35.vrp 12KB
Golden_20.vrp 12KB
X-n655-k131.vrp 12KB
Golden_15.vrp 11KB
X-n613-k62.vrp 11KB
Golden_11.vrp 11KB
X-n599-k92.vrp 11KB
X-n627-k43.vrp 11KB
Golden_7.vrp 11KB
X-n586-k159.vrp 10KB
X-n573-k30.vrp 10KB
Golden_19.vrp 10KB
X-n561-k42.vrp 10KB
X-n536-k96.vrp 10KB
X-n548-k50.vrp 10KB
Golden_2.vrp 10KB
X-n524-k153.vrp 9KB
Golden_14.vrp 9KB
X-n513-k21.vrp 9KB
X-n491-k59.vrp 9KB
Golden_10.vrp 9KB
X-n502-k39.vrp 9KB
X-n469-k138.vrp 9KB
X-n459-k26.vrp 9KB
X-n480-k70.vrp 9KB
Golden_6.vrp 8KB
Golden_18.vrp 8KB
X-n449-k29.vrp 8KB
X-n429-k61.vrp 8KB
X-n439-k37.vrp 8KB
X-n401-k29.vrp 7KB
X-n420-k130.vrp 7KB
X-n411-k19.vrp 7KB
Golden_13.vrp 7KB
X-n384-k52.vrp 7KB
Golden_1.vrp 7KB
Golden_9.vrp 7KB
X-n393-k38.vrp 7KB
Golden_17.vrp 7KB
X-n376-k94.vrp 7KB
X-n367-k17.vrp 7KB
X-n351-k40.vrp 7KB
X-n359-k29.vrp 6KB
X-n322-k28.vrp 6KB
X-n336-k84.vrp 6KB
X-n327-k20.vrp 6KB
X-n331-k15.vrp 6KB
X-n313-k71.vrp 6KB
共 163 条
- 1
- 2
资源评论
快撑死的鱼
- 粉丝: 1w+
- 资源: 9156
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功