CVRP-GA

基于C++，使用遗传算法解决物流运输中的VRP问题

1．导言

当今社会，随着像阿里，京东这样的电商巨头的崛起，我国的物流行业也变得空前的繁荣。特别是诸如淘宝双十一的日子里，更是达到了全民网购这种盛况。而随之而来的则是物流的运输问题。物流公司为了获得更高的利益，目标是在完成物流任务的条件下，通过合理的运输路径安排，使得使用最少的货车，运输的总里程也最少，货车利用率更高。而这也就是经典的 CVRP 问题。由于该问题为 NP-hard 问题，使用传统的算法较难解决，所以这里我们使用启发式智能算法中的遗传算法，去解决这个问题。

2．实验过程

在使用遗传算法解决 CVRP 问题时，步骤如下：

• 输入要选择的数据文件，种群大小，遗传进化的代数。
• 读取数据文件，得到每个客户点的坐标、运载需求量，以及货车最大装载量。
• 按种群大小与客户数量，初始化种群。假设种群大小为 100，有 75 个客户，初始化的方式为产生一个 100 * 75 的二维 vector，然后对这 100 条染色体，每一条都产生一个 1~75 随机排序的数列。
• 算出种群中每一条染色体的适应度。具体方法是，从左往右遍历染色体，并在里面插入 0（代表原点仓库）。每两个 0 之间，则代表一趟货车的运输路线。而插入的方法是多个 0 之间的距离尽量远，让每一趟货车经过的点尽量多，直至再加就要超过货车的载重。
• 根据每条染色体的适应度，求每条染色体累积概率。产生 0 到 1 之间的一个随机数，对轮盘转动种群大小的次数，选择下一代（或者转动种群大小-1 的次数，最后一条染色体固定为当前最高适应度的染色体）。
• 进行遗传操作。与传统的交叉和变异的遗传方式不同，这里使用一种称为 Inver- Over 算子的遗传操作。具体步骤是设定一个变异概率 p 。先在染色体中随机选择一个起始客户 C，如 C=5,。产生一个随机小数，若小于 p，则第二个客户 C’来自同一个个体的另外一个任意客户，如 C’ =2，然后客户 C 与 C’之间的部分被导致（不包括城市 C）；若小数大于 p，则从种群中任意再选择一个染色体，找出 C=5 在该个体中，下一个位置客户的值，如下一个客户为 9，则回到原来的个体，C’=9，客户 5 到 9 之间被导致（不包括 C=5）。这种遗传的思路在于，它能尽量利用种群中获得的信息，来指引个体的变异或者导致操作，最后使得遗传算子比较高效。

• • 判断当前迭代的代数。若迭代次数已够，则进入第 8 步，否则回到第 4 步。
  • 输出迭代中，最高适应度染色体的客户排列情况，以及该染色体的运输花费。

3.结果分析

在对第一个数据样本”tai75a.dat”进行测试时，采用种群大小为 300，迭代次数为 10000 代，如下图：

迭代完毕后，最后的输出结果为

得到最少花费为 1955，目标值是 1618，大概有 300 的差距。

而当把种群大小设到 500，然后迭代 20 万代，输出结果如下：

得到最少花费为 1660，目标值是 1618，大概只有 40 的差距。

而本程序的不足点就是，在对于具有较多客户数的数据文件进行计算时（如”tai385.dat”），性能会有所下降，体现在收敛速度减慢，容易进入到局部最优解。要想改变这个问题，还是要在遗传操作的时候，再做优化。如增加另外的变异方式，让其容易跳出局部解。

4.结论

通过本次实验，我觉得使用遗传算法这种启发式算法，在解决类似 CVRP 这种 NP-hard 问题时，与传统的算法相比还是挺有优势的。在不用花费太长时间的情况下，算出来的解也可以很接近极限最优值。而且对 CVRP 问题的解决在现实生活中，具有巨大的使用价值，遗传算法是一个很好的解决该问题的方式。

主要参考文献

李向阳. 遗传算法求解 VRP 问题.计算机工程与设计，1000-7024(2004)02-0271-0.

 ♻️ 资源

大小： 816KB

➡️ 资源下载：https://download.csdn.net/download/s1t16/87415788

注：更多内容可关注微信公众号【神仙别闹】，如当前文章或代码侵犯了您的权益，请私信作者删除！