网站建设资讯

NEWS

网站建设资讯

VNS求解CVRP问题=怎么解决

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

成都创新互联公司长期为1000多家客户提供的网站建设服务,团队从业经验10年,关注不同地域、不同群体,并针对不同对象提供差异化的产品和服务;打造开放共赢平台,与合作伙伴共同营造健康的互联网生态环境。为青云谱企业提供专业的网站设计、成都网站设计,青云谱网站改版等技术服务。拥有十余年丰富建站经验和众多成功案例,为您定制开发。

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

1.CVRP及数学模型

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

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

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

带容量约束的车辆调度问题模型建立:配送中心(用0表示),用户编号为1,2,……,L;配送中心及客户点均以点ij表示,车辆用k表示;编号1,2,……,k;用户i的货物需求为qiqiQ;从i地到j地的运输成本为Cij,, wijk表示车辆K从客户i到客户j的车的剩余容量,

定义决策变量

VNS求解CVRP问题=怎么解决

数学模型如下

VNS求解CVRP问题=怎么解决

目标函数(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问题=怎么解决有进一步的了解吗?如果还想了解更多知识或者相关内容,请关注创新互联行业资讯频道,感谢大家的支持。


分享名称:VNS求解CVRP问题=怎么解决
浏览地址:http://njwzjz.com/article/goosep.html