最近小编在学(xiao)习(xi)CVRP问题，相信小伙伴们CVRP问题并不陌生，没错CVRP问题就是容量受限制的车辆路径问题，容量受限指的是每辆车的容量都有限制，我们对问题的目标进行设定，本文设定问题的目标为在用最少车辆的前提下，使得所用车辆所行使的总距离最短。
本文数学模型部分参考《求解CVRP的改进量子遗传算法研究》
1.CVRP及数学模型
1.1 带容量的车辆路径问题描述
带容量约束的车辆路径问题描述为：有一个车场，共有Ｋ辆车，每辆车的最大载重为Q，这些车辆为L个客户服务，客户i的需求为qi，每个客户可由任一辆车进行服务，但只能被一辆车服务一次，每辆车服务完后必须返回原车场。其目标是找到一个合适的车辆调度方案，在满足客户需求的同时使车辆的运输成本最低。
1.2 带容量的车辆路径问题模型
带容量约束的车辆调度问题模型建立：配送中心（用0表示），用户编号为1,2,……,L；配送中心及客户点均以点i和j表示，车辆用k表示；编号1,2,……，k；用户i的货物需求为qi，qi＜Q；从i地到j地的运输成本为Cij，, wijk表示车辆K从客户i到客户j的车的剩余容量，
定义决策变量
数学模型如下
目标函数(1)表示车辆运行的总费用最低；式(2)表示每辆车运输的货物不超过最大载重；式(3)表示保证每个 客户都要被访问；式(4)、式(5)表示保证每个客户只能被 一辆车访问；式(6)表示每辆车从配送中心出发是满载的； 式(7)表示进入任一客户之前，车上足够的货物供给客户；式(8)表示消除子回路；式(9)表示变量的取值范围。
2.VNS求解CVRP问题
通过上一篇推文《变邻域搜索算法通俗讲解》，想必大家已经了解VNS框架的基本流程了，不同于上次推文所使用的交换算子和插入算子，本文使用的是逆转算子，即将两个位置之间的所有元素都逆序排列。
因为本文的目标是在使用车辆数量最少的前提下，使总行驶距离最短。小编认为CVRP问题依然可以看成另一种形式的TSP问题。举个例子，比如说一共有10个顾客，每个顾客所需要装货的容积为{4 3 6 9 10 4 6 5 8 7}，而每辆车的载货量为30，假设初始顾客排序为1 2 3 4 5 6 7 8 9 10，那么我们就可以依次求容积和，一旦总容积和大于30就将顾客进行分为一组，每一组的顾客由一辆车取货，因此分组情况为{4 3 6 9| 10 4 6 4| 8 7}，分为3组，每组再按照顺序依次取货。因此第1辆车服务的顾客为{1 2 3 4}，第2辆车服务的顾客为{5 6 7 8},第3辆车服务的顾客为{9 10}。小伙伴们是否明白了呢，不过这是小编一家之言，虽然能出一个不错的结果，但这个方法究竟是否可行，还需各位小伙伴们指点。
3.代码
这个代码小编觉得写得比较粗糙，运算时间较长，不过结果还算不错。小编觉得代码传递的是思想，各位小伙伴们可以对代码进行优化，并积极地与小编交流。
链接：https://pan.baidu.com/s/1tDH1IYfgo1SR6VcPS5PLxw
提取码：2oyd