遗传算法求解VRP问题的技术报告
更新时间:2023-03-08 06:13:50 阅读量: 综合文库 文档下载
- 遗传算法求解VRP问题推荐度:
- 相关推荐
遗传算法求解VRP问题的技术报告
摘要:本文通过遗传算法解决基本的无时限车辆调度问题。采用车辆和客户对应排列编码的遗传算法,通过种群初始化,选择,交叉,变异等操作最终得到车辆配送的最短路径。通过MATLAB仿真结果可知,通过遗传算法配送的路径为61.5000km,比随机配送路径67km缩短了5.5km。此结果表明遗传算法可以有效的求解VRP问题。
一、 问题描述
1.问题描述
车辆调度问题(Vehicle Scheduling/Routing Problem,VSP/VRP)的一般定义为[1]:对一系列送货点和/或收货点,组织适当的行车路线,使车辆有序地通过它们,在满足一定的约束条件(如货物需求量、发送量,送发货时间、车辆容量限制、行驶里程限制、时间限制等)下,达到一定的目标(如路程最短、费用极小、时间尽量少、使用车辆数尽量少等)。问题描述如下[2]:有一个或几个配送中心Di(i?1,...,n),每个配送中心有K种不同类型的车型,每种车型有n辆车。有一批配送业务Ri(i?1,...,n),已知每个配送业务需求量qi(i?1,...,n)和位置或要求在一定的时间范围内完成,求在满足不超过配送车辆载重等的约束条件下,安排配送车辆在合适的时间、最优路线使用成本最小。 2.数学模型
设配送中心有K台车,每台车的载重量为Qk(k?1,2,...,K),其一次配送的最大行驶距离为Dk,需要向L个客户送货,每个客户的货物需求量为qi(i?1,2,...,L),客户i到j的运距为dij,配送中心到各个客户的距离为d0j(i,j?1,2,...,L),再设nk为第K台车配送的客户数(nk=0表示未使用第K台车),用集合Rk表示第k条路径,其中rki表示客户rki在路径 k 中的顺序为 (不包括配送中心),令 rk0 表示配送中心,若以配送总里程最短为目标函数,则可建立如下数学模型:
minZ??[?drk(i?1)rki?drknk?1i?1Knkkrk0?sign(nk)] (1)
nk?qri?1nkki?Qk (2)
?di?1rk(i?1)rki?drknkrk0?sign(nk)?Dk (3)
0?nk?L (4)
Page 1 of 8
?nk?1Kk?L (5)
Rk?{rkirki?{1,2,...,L},i?1,2,...,nk} (6) Rk1?Rk2??,?k1?k2 (7)
?1nk?1? sign(nk)??? (8)
?0其他?上述模型中,式(1)为目标函数,即要求配送里程最短;式(2)保证每条路径上各个客户的货物需求量之和不超过配送车的载重;式(3)保证每条配送路径的长度不超过配送车的最大行驶距离;式(4)表明每条路径上的客户数不超过总客户数;式(5)表明每个客户都得到配送服务;式(6)表示每条路径的客户组成;式(7)限制每个客户仅能由一台配送车送货;式(8)表示当第 k 辆车服务的客户数大于等于1时,说明该台车参加了配送,则sign(n)的值取1,否则为0。
二、 研究现状
车辆调度问题在目标和范围方面有很大差别,主要是研究的目标和限定条件不同。在研究目标方面有的是最短路线,有的是最短时间,有的是客户的方便程度等等。在限定条件方面,有配送中心方面的区别,和有单配送中心的,有多配送中心;有配送车辆的数量、种类方面的区别,如车辆数有限、无限、单一车型和多种车型;在业务种类方面,有的是集货任务,有的是送货业务,有的是集送一体化业务,有的是各种业务混合情况。有时间窗的车辆调度问题是最为普通的问题,以成为研究热点。
遗传算法在搜索过程中能够自动获取和积累有关搜索空间的知识,并能利用问题固有的知识来缩小搜索空间,自适应地控制搜索过程,动态有效地降低问题的复杂度,从而求得原问题的真正最优解或满意解,因此我来选用遗传算法来求解VSP问题。
三、 解决方法
遗传算法的流程图如下:
Page 2 of 8
初始化群体个体评价终止Nt 基于车辆和客户对应排列编码的遗传算法的基本步骤: (1) 编码:采用车辆和客户对应排列的编码方法,其基本思路是:用车辆数间的任意自然数(可重复)的排列表示车辆排列,用客户数间的互不重复的自然数排列表示客户排列,两者相对应,构成一个解,并对应一个配送路径方案。例如:对于一个用3台车向9个客户送货的车辆调度优化问题,设某解为(122131223)(456712398),即车辆排列为122131223,客户排列为456712398,两个排列相对应。 (2)适应度函数:直接采用公式(1)作为适应度评估函数。对不可行路径进行权重惩罚。 (3)选择策略:采用最佳个体保存与赌轮相结合的选择策略。其具体操作为:将每代群体中的N个个体按适应度由小到达排列,排在首位的个体性能最好,将它直接复制到下一代。下一代群体的令N-1个体需要根据上一代群体的N个个体的适应度采用赌轮选择。 (4)交叉操作:在该编码方式下有几种编码方式:仅对车辆编码进行交叉、仅对客户编码进行交叉和同时对客户编码和车辆编码进行交叉。本方法中采用仅对车辆编码的方式来交叉。 (5)变异操作:本程序中对于变异操作,采用对客户编码变异的方式。 用MATLAB编程,在内存为2G,CPU 2.10GHz的微机上运行。采用运行参数:种群规模为100,交叉概率为0.9,变异概率为0.2,进化代数100。变异仅对客户编码,对不可行路径的惩罚权重去100km,具体程序代码见附录。 四、 仿真结果 某配送中心有2台车,其载重量均为8t,车辆每次配送的最大行驶距离均为50km,配送中心与8个客户之间及8个客户之间相互距离及货物需求见下表: 表1 客户需求 Page 3 of 8 表2 点对间距表 运行结果如下: Page 4 of 8 五、 结论 从以上仿真结果可知,用遗传算法通过选择,交叉,变异等操作最终求得配送车辆物流问题中的最短路径,减少了车辆资源和时间的浪费,缩短了运输成本。同时,在车辆调度问题中,进一步加入时间窗等参数的车辆调度问题的遗传算法的求解,还需要进一步的学习研究。 六、 参考文献 [1]施朝春,王旭,葛显龙。带有时间窗的多配送中心车辆调度问题研究[J] 。计算机工程与应用,2009; 45(34):21—24 [2]程世东,刘小明,王兆赓。物流配送车辆调度研究的回顾与展望[J]。交通运输工程与信息学报,2004;2(3):93—97 七、 附录:程序 clear all; close all; D=[ 0 6.5 4 10 5 7.5 11 10 4; 6.5 0 7.5 10 10 7.5 7.5 7.5 6; 4 7.5 0 10 5 9 9 15 7.5; 10 10 10 0 10 7.5 7.5 10 9; 5 10 5 10 0 7 9 7.5 20; 7.5 7.5 9 7.5 7 0 7 10 10; 11 7.5 9 7.5 9 7 0 10 16; 10 7.5 15 10 7.5 10 10 0 8; 4 6 7.5 9 20 10 16 8 0]; n=40; C=100; Pc=0.9; Pm=0.2; N=8; family=zeros(n,N); tic for i=1:n family(i,:)=randperm(N); end Gt=family(1,:); Ln=zeros(n,1); for kg=1:1:C time(kg)=kg; %------------------------------计算路径长度----------------------------- for i=1:1:n Page 5 of 8 Ln(i,1)=fitness1(D,family(i,:)); %计算每条染色体的适应度值 End MinLn(kg)=min(Ln); minLn=MinLn(kg); rr=find(Ln==minLn); Gt=family(rr(1,1),:); %更新最短路径 Family=family; kg; minLn; %--------------------------------选择复制------------------------------- K=30; aa=0;bb=0; [aa,bb]=size(Family); Family2=Family; Ln2=Ln; [Ln]=sort(Ln); for i=1:aa tt=find(Ln2==Ln(i,1)); Family(i,:)=Family(tt(1,1),:); end for i=1:K j=aa+1-i; Family(j,:)=Family(i,:); end %---------------------------------交叉--------------------------------- [aa,bb]=size(Family); Family2=Family; for i=1:2:aa if Pc>rand&&i %-------------------------------变异----------------------------------- Family2=Family; for i=1:aa if Pm>=rand %变异条件 Family(i,:)=mutate(Family(i,:)); End end Family=[Gt;Family]; %保留上一代最短路径 [aa,bb]=size(Family); if aa>n Page 6 of 8 Family=Family(1:n,:); end family=Family; clear Family end toc Gt RL=fitness1(D,Gt) plot(time,MinLn); xlabel('times');ylabel('MinLn'); (1)适应度函数 function len=fitness1(D,p) N=8; len=0; for i=1:(N-1) len=len+D(p(i),p(i+1)); end len=D(N,p(1))+len+D(p(N),N); b=0; total=[0 0]; volume=8; demand=[1 2 1 2 1 4 2 2 0]; b=find(p==8); if b==1 total(1)=0; for i=2:N total(2)=demand(p(i))+total(2); end elseif b==9 total(2)=0; for i=1:(N-1) total(1)=demand(p(i))+total(1); end else for i=1:(b-1) total(1)=demand(p(i))+total(1); end for i=(b+1):N total(2)=demand(p(i))+total(2); end end if total(2)>volume|total(1)>volume len=len+100; end (2)交叉操作函数 function [a1,b1]=intercross(a1,b1) Page 7 of 8 L=length(a1); w=[0 0]; w(1)=unidrnd(L-2); w(2)=L-w(1); if w(2) w(1)=w(1); w(2)=w(2); end for i=w(1):(w(2)-1) xx=find(a1==b1(i+1)); yy=find(b1==a1(i+1)); [a1(i+1),b1(i+1)]=exchange(a1(i+1),b1(i+1)); [a1(xx),b1(yy)]=exchange(a1(xx),b1(yy)); end (3)对调操作函数 function [x1,y1]=exchange(x1,y1) temp=x1; x1=y1; y1=temp; (4)变异函数 function c=mutate(c) L1=length(c); rray=randperm(L1); [c(rray(1)),c(rray(2))]=exchange(c(rray(1)),c(rray(2))); Page 8 of 8
- 计算机试题
- 【2012天津卷高考满分作文】鱼心人不知
- 教育心理学历年真题及答案--浙江教师资格考试
- 20180327-第六届“中金所杯”全国大学生金融知识大赛参考题库
- 洪林兴达煤矿2018年度水情水害预测预报
- 基本要道讲义
- 机电设备安装试运行异常现象分析与对策
- 《有机化学》复习资料-李月明
- 非常可乐非常MC2--非常可乐广告策划提案 - 图文
- 2011中考数学真题解析4 - 科学记数法(含答案)
- 企业人力资源管理师三级07- 09年真题及答案
- 基于单片机的光控自动窗帘控制系统设计说明书1 - 图文
- 20160802神华九江输煤皮带机安装方案001
- (共53套)新人教版一生物必修2(全册)教案汇总 word打印版
- 2014行政管理学总复习
- 中国银监会关于加强地方政府融资平台贷款风险监管的指导意见
- 民宿酒店核心竞争与研究
- 游园活动谜语大全2012
- 河南省天一大联考2016届高三英语5月阶段性测试试题(六)(A卷)
- 小型超市管理系统毕业论文详细设计4
- 求解
- 遗传
- 算法
- 报告
- 问题
- 技术
- VRP
- 人防门型号
- 痰瘀互结证的辨治体会 金妙文
- 北京101中学高一记叙文写作课(特级教师程翔)
- 钻井工(初级)理论知识试题答案
- 关于规范填写2015届《毕业生就业推荐表》的通知
- (新课标)高中物理教参新人教版必修2
- 前期物业服务合同 贵阳住房和城乡建设局
- JAVA实验-综合应用实验
- 2017年二级建造师网络继续教育考试试题及答案
- 禁牧牧民生产生活情况调研报告
- 走进儿童诗
- 家长一封信
- 采购管理工作细化执行与模板 - 图文
- 一,充分认识农村劳动力转移就业对促进农民增收的重要意义
- 离子膜法电解饱和食盐水实验的项目教学法思考-最新教育资料
- JavaScript习题(带答案)
- 务实谈柔性引才
- 新视野大学英语第三版第四册读写教程课后习题翻译
- 实验一 算法的实验分析
- 人胎素对人体有副作用吗