构造CVRP问题初始解的启发式方法是什么，针对这个问题，这篇文章详细介绍了相对应的分析和解答，希望可以帮助更多想解决这个问题的小伙伴找到更简单易行的方法。今天小编为大家讲解一种构造CVRP（容量受限的车辆路径问题）的启发式方法。什么是CVRP问题，不太了解的小伙伴可以看一下VNS（变邻域搜索算法）求解CVRP问题这篇文章。首先说一下思路，构造CVRP问题启发式方法，最著名的莫过于Clark and Wri 香港云主机ght在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问题初始解的启发式方法是什么问题的解答就分享到这里了，希望以上内容可以对大家有一定的帮助，如果你还有很多疑惑没有解开，可以关注开发云行业资讯频道了解更多相关知识。
前言：前面几篇博客主要介绍了MapReduce与Yarn的架构设计及简单工作流程，本篇文章将以wordcount程序为例，简单介绍下Yarn的使用。登录网页查看相关信息：http://192.168.6. 香港云主机217:8088/cluster参考：htt…
免责声明：本站发布的图片视频文字，以转载和分享为主，文章观点不代表本站立场，本站不承担相关法律责任；如果涉及侵权请联系邮箱：360163164@qq.com举报，并提供相关证据，经查实将立刻删除涉嫌侵权内容。
微信扫一扫 
