构造CVRP问题初始解的启发式方法是什么

构造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了。

关于构造CVRP问题初始解的启发式方法是什么问题的解答就分享到这里了，希望以上内容可以对大家有一定的帮助，如果你还有很多疑惑没有解开，可以关注亿速云行业资讯频道了解更多相关知识。