改进遗传算法求解VRP问题
更新时间:2024-06-04 03:27:01 阅读量: 综合文库 文档下载
- 遗传算法求解VRP问题推荐度:
- 相关推荐
龙源期刊网 http://www.qikan.com.cn
改进遗传算法求解VRP问题
作者:梁佳成
来源:《科技创新导报》2012年第36期
摘 要:用遗传算法(GA)求解车辆路径问题,但总体上他们所得解的质量都不高,这是由GA本身局部搜索能力不强所致.针对GA这一缺陷,该文对标准遗传算法改进,用于求解VRP问题,并通过实验计算证明了该算法具有良好的寻优性能。 关键词:改进遗传算法 VRP 忳能
中图分类号:U491.2 文献标识码:A 文章编号:1674-098X(2012)12(c)-0-01 1 VRP数学模型的建立
问题描述如下:1个物流中心和个客户,第k个客户需运输的货物量为,物流中心派出多辆货车,从物流中心将个客户的所有货物运出,求满足货运需求的最短距离车辆运输行程路线。设物流中心派出m辆货车,每辆货车的载重量为q,且q>gi,表示点i到点j的运输成本,物流中心的编号为0,各客户的编号为,另外几个变量定义如下: 货车s由i驶向j;点i的货运任务由s货车完成
由这些参数和变量可以求出VRP问题的数学模型表示为:
每辆货车的载货量不超过车辆载重量;保证通过每一个客户有且仅有一辆车,所有车从物流中心出发,最后回到物流中心;确保每个客户的运输任务仅由1辆货车来完成,所有的运输任务则由m辆货车协同完成。 2 遗传算法改进
改进交叉概率pc和变异概率
fmax是种群中最大的适应度值,favg每一代种群的平均适应度值,fmin每代种群中最小的适应度值,f'要交叉的两个个体种较大的适应度值,f要变异个体的适应度值。,取(0,1)区间的值,在优化过程中,根据需要不断调整。
改进后的交叉概率和变异概率能够随适应度自动改变,够较高的概率产生出较大多样性的子代,即能够高概率产生适应度更高的新个体,使得它们不会处于一种近似停滞不前的状态,从而使算法跳出局部最优解。 3 算法实例计算
龙源期刊网 http://www.qikan.com.cn
采用matlab 6.0进行程序仿真,以9个客户为例进行求解。
9家客户(依次用1,2,…,9来表示)之间的距离(km)如表1所示,各客户的需求量(kg)如表2所示。每辆货车的容量为12 t,在保证车辆不超载,并且保证每家客户的送货量的前提下,找出对这9家客户进行配货的最短路径。 参数初始化: (1)车辆数
按照参考文献对m进行评估。 其中,[ ]表示对括号内的数字取整,0
(2)进化代数G=50,初始群体p=50,pw=1000. (3)车辆载重限制=12 t
改进遗传算法运行总距离746 km,普通遗传算法运行总距离830 km。
由以上的试验结果可以看出,采用改进的遗传算法与普通遗传算法分别求解上面应用实例,改进遗传算法优化结果明显优于普通遗传算法。这说明标准遗传算法中标准选择,交叉,变异算子在求解VRP问题时搜索能力较差。将整数编码、改进交叉算子引入改进标准遗传算法后,算法的搜寻能力明显加强,收敛性显著提高,仿真试验结果证明改进后算法的可行性和有效性。 参考文献
[1] 李军,郭耀煌.物流配送车辆优化调度理论与方法[M].中国物资出版社,2001. [2] 欧阳森,王建华,耿英三,等.一种新的改进遗传算法[J].计算机工程与应用,2003,39(11).
正在阅读:
改进遗传算法求解VRP问题06-04
教师招聘考试(教育学心理学试题大全)-选择判断大全(很多150多页)03-08
磁致气流富氧助燃系统与其他富氧方式09-18
迎新年请客吃饭邀请短信03-22
高级化工检修钳工试题01-27
立式原料磨施工方案 - 图文04-29
牧鹅姑娘-公主童话故事02-07
物流地理测试题2015.10.2801-30
学校财务报帐员个人事迹材料08-23
农产品集散中心可行性研究报告书08-07
- 《江苏省环境水质(地表水)自动监测预警系统运行管理办法(试行)》
- 安乐死合法化辩论赛立论稿(浙大新生赛)
- 公共科目模拟试卷公务员考试资料
- 我国固定资产投资FAI对GDP的影响
- 大学生创新创业训练计划项目申请书大创项目申报表
- 完美版—单片机控制步进电机
- 2013资阳中考化学试题
- 18.两位数减一位数退位(397道)
- 工程量计算规则
- 二年级操行评语(下)
- 第3章 流程控制语句
- 浅基桥墩加固技术
- 课题研究的主要方法
- 5100软件说明书 - 图文
- 车间技术员年终总结
- 关于印发《中铁建工集团开展项目管理实验室活动方案》的通知
- 经典诵读结题报告
- 地下水动力学习题答案
- 2018年全国各地高考数学模拟试题平面解析几何试题汇编(含答案解
- 街道办事处主任2018年度述职述廉报告
- 求解
- 遗传
- 算法
- 改进
- 问题
- VRP
- 创造力成分理论及其应用研究
- 从Matlab Simulink生成易读可重用代码
- 2018年聚氨酯模具板行业现状及发展趋势分析(目录)
- 乌鲁木齐市河西污水处理厂设计计算
- 初级会计实务试题十一
- 轻型井点降水施工方案(标准版)
- 【物理】2010-2011-2012三年高考真题试题分类汇编:电磁感应
- 2018年湖北省随州市中考数学试卷
- 第一次团课教案
- 2015保险公司述职报告
- 教师职业道德复习指导
- 包含一阶段所有内容- 第一阶段考试复习
- 行政执法考试题库(有答案)
- 新媒体时代的“媒介审判”现象
- 黄奇帆在调研江苏南通时的发言实录
- 2011云南省会计从业资格考资料
- 人教课标版小学五年级语文上册 13 钓鱼的启示 公开课教学设计
- 3.1.3二倍角的正弦、余弦、正切公式 讲义
- 地理科学的发展现状和前景分析
- 作文