# 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)
没有合适的资源?快使用搜索试试~ 我知道了~
资源推荐
资源详情
资源评论
收起资源包目录
基于C,使用遗传算法解决物流运输中的VRP问题项目资源.zip (50个子文件)
.git\logs\refs\remotes\origin\HEAD 190B
tc\tai385.dat 21KB
.git\hooks\update.sample 4KB
tc\tai150d.dat 7KB
.git\hooks\applypatch-msg.sample 478B
.git\logs\refs\heads\master 190B
src\cvrp.cpp 8KB
.git\hooks\pre-push.sample 1KB
tc\tai75a.dat 4KB
.git\hooks\pre-applypatch.sample 424B
.git\packed-refs 114B
img\image2.jpg 80KB
.git\refs\remotes\origin\HEAD 32B
.git\description 73B
tc\tai75b.dat 4KB
.git\logs\HEAD 190B
tc\tai100d.dat 5KB
.git\hooks\pre-rebase.sample 5KB
.git\hooks\prepare-commit-msg.sample 1KB
tc\tai150a.dat 7KB
.git\index 2KB
.git\objects\pack\pack-3b285655140e5d248f9edcff51f6639261889c14.pack 702KB
.git\hooks\pre-commit.sample 2KB
img\image2.png 52KB
tc\tai150b.dat 7KB
tc\tai150c.dat 7KB
.git\HEAD 23B
sample.txt 89B
src\readme.txt 244B
.git\hooks\push-to-checkout.sample 3KB
.git\hooks\fsmonitor-watchman.sample 5KB
.git\hooks\pre-merge-commit.sample 416B
.git\info\exclude 240B
tc\tai75d.dat 4KB
doc\用遗传算法解决CVRP问题.doc 151KB
.git\refs\heads\master 41B
tc\tai100a.dat 5KB
tc\tai100c.dat 5KB
.git\hooks\pre-receive.sample 544B
bin\cvrp.exe 1.92MB
img\image1.png 25KB
tc\tai75c.dat 4KB
.git\objects\pack\pack-3b285655140e5d248f9edcff51f6639261889c14.rev 216B
README.md 4KB
.git\hooks\commit-msg.sample 896B
.git\config 302B
.git\hooks\post-update.sample 189B
tc\tai100b.dat 5KB
.git\objects\pack\pack-3b285655140e5d248f9edcff51f6639261889c14.idx 2KB
.git\hooks\sendemail-validate.sample 2KB
共 50 条
- 1
资源评论
项目资源总站点博客专家
- 粉丝: 1351
- 资源: 3693
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
最新资源
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功