VNS求解CVRP问题=怎么解决

今天就跟大家聊聊有关VNS求解CVRP问题=怎么解决，可能很多人都不太了解，为了让大家更加了解，小编给大家总结了以下内容，希望大家根据这篇文章可以有所收获。

CVRP问题就是容量受限制的车辆路径问题，容量受限指的是每辆车的容量都有限制，我们对问题的目标进行设定，下面设定问题的目标为在用最少车辆的前提下，使得所用车辆所行使的总距离最短。

1.CVRP及数学模型

1.1  带容量的车辆路径问题描述

带容量约束的车辆路径问题描述为：有一个车场，共有Ｋ辆车，每辆车的最大载重为Q，这些车辆为L个客户服务，客户i的需求为q_i，每个客户可由任一辆车进行服务，但只能被一辆车服务一次，每辆车服务完后必须返回原车场。其目标是找到一个合适的车辆调度方案，在满足客户需求的同时使车辆的运输成本最低。

1.2  带容量的车辆路径问题模型

带容量约束的车辆调度问题模型建立：配送中心（用0表示），用户编号为1,2,……,L；配送中心及客户点均以点i和j表示，车辆用k表示；编号1,2,……，k；用户i的货物需求为q_i，q_i＜Q；从i地到j地的运输成本为C_ij，, w_ijk表示车辆K从客户i到客户j的车的剩余容量，

定义决策变量

数学模型如下

目标函数(1)表示车辆运行的总费用最低；式(2)表示每辆车运输的货物不超过最大载重；式(3)表示保证每个 客户都要被访问；式(4)、式(5)表示保证每个客户只能被 一辆车访问；式(6)表示每辆车从配送中心出发是满载的； 式(7)表示进入任一客户之前，车上足够的货物供给客户；式(8)表示消除子回路；式(9)表示变量的取值范围。

2.VNS求解CVRP问题

不同于上次推文所使用的交换算子和插入算子，本文使用的是逆转算子，即将两个位置之间的所有元素都逆序排列。

因为本文的目标是在使用车辆数量最少的前提下，使总行驶距离最短。小编认为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}。小伙伴们是否明白了呢，不过这是小编一家之言，虽然能出一个不错的结果，但这个方法究竟是否可行，还需各位小伙伴们指点。

看完上述内容，你们对VNS求解CVRP问题=怎么解决有进一步的了解吗？如果还想了解更多知识或者相关内容，请关注亿速云行业资讯频道，感谢大家的支持。