构造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问题初始解的启发式方法是什么问题的解答就分享到这里了，希望以上内容可以对大家有一定的帮助，如果你还有很多疑惑没有解开，可以关注亿速云行业资讯频道了解更多相关知识。
免责声明：本站发布的内容（图片、视频和文字）以原创、转载和分享为主，文章观点不代表本网站立场，如果涉及侵权请联系站长邮箱：is@yisu.com进行举报，并提供相关证据，一经查实，将立刻删除涉嫌侵权内容。
