# CVRP-GA
基于C++,使用遗传算法解决物流运输中的VRP问题
##1.导言
当今社会,随着像阿里,京东这样的电商巨头的崛起,我国的物流行业也变得空前的繁荣。特别是诸如淘宝双十一的日子里,更是达到了全民网购这种盛况。而随之而来的则是物流的运输问题。物流公司为了获得更高的利益,目标是在完成物流任务的条件下,通过合理的运输路径安排,使得使用最少的货车,运输的总里程也最少,货车利用率更高。而这也就是经典的CVRP问题。由于该问题为NP-hard问题,使用传统的算法较难解决,所以这里我们使用启发式智能算法中的遗传算法,去解决这个问题。
##2.实验过程
####在使用遗传算法解决CVRP问题时,步骤如下:
1. 输入要选择的数据文件,种群大小,遗传进化的代数。
2. 读取数据文件,得到每个客户点的坐标、运载需求量,以及货车最大装载量。
3. 按种群大小与客户数量,初始化种群。假设种群大小为100,有75个客户,初始化的方式为产生一个100 * 75的二维vector,然后对这100条染色体,每一条都产生一个1~75随机排序的数列。
4. 算出种群中每一条染色体的适应度。具体方法是,从左往右遍历染色体,并在里面插入0(代表原点仓库)。每两个0之间,则代表一趟货车的运输路线。而插入的方法是多个0之间的距离尽量远,让每一趟货车经过的点尽量多,直至再加就要超过货车的载重。
5. 根据每条染色体的适应度,求每条染色体累积概率。产生0到1之间的一个随机数,对轮盘转动种群大小的次数,选择下一代(或者转动种群大小-1的次数,最后一条染色体固定为当前最高适应度的染色体)。
6. 进行遗传操作。与传统的交叉和变异的遗传方式不同,这里使用一种称为Inver- Over算子的遗传操作。具体步骤是设定一个变异概率p 。先在染色体中随机选择一个起始客户C,如C=5,。产生一个随机小数,若小于p,则第二个客户C’来自同一个个体的另外一个任意客户,如C’ =2,然后客户C与C’之间的部分被导致(不包括城市C);若小数大于p,则从种群中任意再选择一个染色体,找出C=5在该个体中,下一个位置客户的值,如下一个客户为9,则回到原来的个体,C’=9,客户5到9之间被导致(不包括C=5)。这种遗传的思路在于,它能尽量利用种群中获得的信息,来指引个体的变异或者导致操作,最后使得遗传算子比较高效。
7. 判断当前迭代的代数。若迭代次数已够,则进入第8步,否则回到第4步。
8. 输出迭代中,最高适应度染色体的客户排列情况,以及该染色体的运输花费。
##3. 程序运行
####运行程序时,需要输入以下三样数据:
1.所使用的数据文件名字,如:"../tc/tai75a.dat"
2.种群大小,如: "300"
3.遗传迭代的代数,如:"10000"
程序运行的时间,取决于种群大小与迭代代数的大小,需要耐心等候。最终的最优解,将在程序最后输出。
##4.结果分析
####在对第一个数据样本”tai75a.dat”进行测试时,采用种群大小为300,迭代次数为10000代得到最少花费为1955,目标值是1618,大概有300的差距;而当把种群大小设到500,然后迭代20万代,得到最少花费为1660,目标值是1618,大概只有40的差距。
![Alt text](./img/image1.png)
![Alt text](./img/image2.jpg)
辣椒种子
- 粉丝: 4151
- 资源: 5808
最新资源
- 学之思开源考试系统是一款java+vue的前后端分离的考试系统 主要优点是开发、部署简单快捷、界面设计友好、代码结构清晰 支持web端和微信小程序,能覆盖到pc机和手机等设备 支持多种部署方式
- PHP旅游智能CRM系统源码数据库 MySQL源码类型 WebForm
- 大数据1+x(蓝桥课堂实操231216)解析
- 基于STM32F103C8T6的双轮平衡小车项目源码(代码注释全面适合小白)
- 金杰.m4a..mp3
- PHP出租屋租赁系统源码带小程序数据库 MySQL源码类型 WebForm
- Matlab实例:频谱、功率谱和功率谱密度计算作业
- 企业级免费开源商城系统,可视化DIY拖拽装修、包含PC、H5、多端小程序(微信+支付宝+百度+头条&抖音+QQ+快手)、APP、多仓库、多商户、多门店、IM客服、进销存,遵循MIT开源协议发布
- 毕业设计基于STM32F103C8T6的智能宠物屋系统源码+文档说明+原理图
- windows上OpenSSH服务安装及启动
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈