一种构造CVRP问题初始解的启发式方法

今天小编为大家讲解一种构造CVRP（容量受限的车辆路径问题）的启发式方法。什么是CVRP问题，不太了解的小伙伴可以看一下​​VNS（变邻域搜索算法）求解CVRP问题​​这篇文章。首先说一下思路，构造CVRP问题启发式方法，最著名的莫过于Clark and Wright在1964年提出的方法——节约算法。

在这里我们以solomon算例种的c102算例为例进行讲解。

设顾客数量为n，每辆车容量为200，0代表配送中心

下面小编详细介绍一下这种经典的启发式方法。

step1：假设有n辆车，每辆车只服务一个顾客，因此就产生n个独立的回路。

然后计算将顾客i 和顾客j合并到一条路径上，距离的减少量也就是所谓的节约值：，找出最大节约值对应的那两个顾客i 和顾客j，然后将顾客i 和顾客j合并到一条路径上，如下图所示。

step2：当一条路径上有两个顾客时，比如说上图中的0120这种情况，再想将没有被融合的路径上的一个顾客i 融合到该路径时，一共有3种插入位置，也就是：0i120、01i20、012i0，需要计算这3种情况的节约值。如果一条路径上只有一个顾客，节约值还像上述方法计算即可。

step3：当一条路径上所有顾客的需求总量超过车的容量时，这时就需要开辟一条新的路径，然后按照step1和step2再次计算节约值，然后进行路径融合，直到所有的顾客都被分配到车辆来送货时，该算法就STOP了。

代码小编今天没有码完，下次再更新代码。

最后祝各位小伙伴圣诞节快乐！

小编的微博名也是“随心390”，各位有什么问题的话可以微博私信我，我会及时回复的。