




版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
:然后选出1~30号货物所送达的顶点间的最短路径以及距离,再用二边逐次修对Hamilton圈进30:228.18TSP问题,根据线路规划的特点,基于过程中自动淘汰。经过多次迭代求出其中耗时最短的路线即为所需结果,最终路线:228.18案进行路线的分划,并根据最终求得结果的比较,得出前者方案更优,因此选用第案送货。总时间为:394.3分。背企业互不相通的单一方式以及邮政普遍服务那种保证送达,但时间长、问50124公里/小时,33分钟交接计算等条件,要求合理模型假条件假假设 假设送货员的送货路线一旦确定就不在改变假设假设 假设送货员到某送货点后必须把该送货点的快件送完假设 假设每个送货点的货物一次被送到,不会出现分批送到的情况假设假设 24公里/假设5 假设 假设同一地点有多件货物也简单按照每件3分钟交接计算假设 假设送货员只能按已知的连通线路行走,而不能走其它任何路线假设 假设送货员在送货的过程中互不影响假设 假设每一个送货点由同一个送货员送货符 变量意xij
0-1 tntntWiW3
节点s和节点e之间的最短距离问题二中第n问题二中第n问题i的总路程(i1,2,3)问题3第i阶段的总路程问题i的总时间(i1,2,3) 问题分的送货行程最短。此即图论中最佳路径问题。而送货路线问题可以理解为:已知起点和终圈(H圈。从而得出送货员的最佳送货方案。模型准问题一的基本算法及其相关概念Floyd算法的基本思想GV,E,V为顶点集合,En(n1)个顶V1,…,Vn。FloydViVj(1ijn)Vk(k1n),并计算出只任取初始H圈
C0v1,v2,...vi,...vj,..vn,对所有的ij,1i1jn,若w(vivjw(vi1,vj1w(vivi1w(vjvj1,在C0中删去边(vivi1和(vjvj1而加入边(vi,Cv1,v2,...,vi,vj,vj1,...,vi1,vj1,...,
和(vi1,j
,形成新的H圈C(2相关概念完备图令G=(V,E)为一个无向图,其中V=|v1,v2,……,vn|为顶点集合,E为Gew(e)w(e)为该边的权。若任意两点均有边相连,则G为完备图。哈图设G=(V,E)是连通无向图,经过G的每个顶点正好一次的圈,称为G的一条哈圈,简称H圈;含H圈的图成为哈图或H图。最佳H圈在图G=(V,E)中,权最小的哈圈称为最佳H圈判定一个图G=(V,E)是否存在哈圈是一个NP问题而它的完备图G'=(V,E(E'中的每条边(x,y)xyG中最短路径的权)中一定存在哈圈所以在完备图G'=(V,E')中寻找最佳H圈该过程采用二边逐次修 在一个矩阵中,对它的第i行(列)到第j行(列)翻转是以第i行(列)和j行(列的)中心位置为转轴,旋转180度,这样:第i行(列)和第j行(列)的位置互换,第i+1行(列)和第j-1行(列)位置互换,……最后就会收敛到最适应环境的一个“”上,它就是问题的最优解。遗传算法步骤1)编码,创建初始2)中适应度计根据适应度选择被选择进行交叉繁殖繁殖出新的,回到第二)n-1模型建立针对问题1~30显然送货员能够一次带上所有货物到达各送货点,而且货物要送达的送货点总共为个本模型运用图论中最佳路径问题与最佳H圈中的相出发点O/5121个送货点结合起来构造完备图。问题一需要从1~30号货物送到指定地点并返回至O点,要求总时间T11(各货物信息表)30
TW130 1其中:W11
W Wss1 nss
Wss
Wnnv
W
30约束条件:必须全部遍历并返回O求解过程中,根据FloydStep1:定义并初始化辅助矩阵Dist[n][n]和Path[n][n],矩阵元素Dist[i][j]与Path[ij]ViVj之间的最短距离和最短路径(由于最短路径的源点ViVjPath[ij]只保存路径中途径其它顶点的部分)Dist与PathViVj之间直接到达(中间不途径其它顶点)时的最短距ijDist[ij]置为∞,否则将Dist[ij]置为弧<Vi,VjijDist[ij0Path[ij没Step3ViVj组合(1in1jn)Dist[i][kDist[kDist[ij]Dist[ijDist[i][kDist[kj]Path[ijPath[i][k]"Vk"Path[kj];Dist[i][j]Path[i][j]保持不变(VkViVj之间的最短路径中。符号“”表示连接运算,如"abcd""fg"="abcdfg"。);Step4:kk+1kn转Step3ViVj之间的最Dist[ij]ViVj之间的最短路径则为"Vi"Path[ij"Vj"。从上面给出Floyd算法步骤可以看出,该算法过程极为简捷,然而,为何经过这样的运算ViVj之间的最短距离。下面仅列出几条用编程得到的近似最佳送货路线及总路线长度:第I条送货路线(图二→45→40→34→39→27→31
Tf(Vi)/240.05*长度(米123 4→43→385→36→326圈(H圈。由完备图,确定初始H圈,列出该初始H圈加点序边框的距离定近似最佳H圈。1i在所有H圈中,找出权最小的一个,此即要找的最佳H圈的近似解。1i最佳H
1000f(V针对问题二
00
Wnnv
W
时间约束条件
Ws
Ws t 1 n1
总模型
nnv
00.
v
mm
nn
利用遗传算法的思想得出如下计算步骤 记A为{1,2,3……22}的所有固定起点和终点的循环排列集合,起点和终点固定为点0(即22点。解空间S是满足时间约束的A的子集。2)编 随机序列L[012]作 ,其中,0<
<1(i=
0
=1如:取一个6目标问题为
表示一个或路径)iiii在路径中的顺序。6— 种群初始化10~160150计算。适应度函数的确定:取适应度函数为走遍n个点的距离的倒数的的适应度0 L为f(L)
1/Tn L为合 优化的目标就是选择适应度函数值尽量可能大的,适应度函数值越大的越终止条件设定 设置最大迭代次数 此排序。选择群体中前70%的 交叉 采用单点交叉对两个父 的部分结构加以替换重组而生成新的。如f1f2设交叉点为第四个处,则s1s20.9变异:在群体中随机确定座,以0.01的变异概率度这些座的值进行变得到两个新的问题三遍历所有的50个点单由于M147kg,V总
,而M50kg,V1m3Mk50kg和V1m判断的标3kk目标函数
WW1W2约束条件
wk(i,
Mk
kV (kk算法与过程(5(Prim)(也即产生局部区域最小生成树28每一阶段(区域)多阶段组合路线(无次序问题6.1遗传算法从问题解的中集开始嫂索,而不是从单个解开始。这是遗传算法与传统优化参考文[1],利用矩阵翻转法求最佳H圈,后勤学报,第24卷第2008196页[2],利用矩阵翻转法求最佳H圈,后勤学报,第24卷第2008196页刘国华包宏超, 2001,100083,第80页.将金山潘少华最优化计算方法遗传算法的模式理论广州华南理工大学238辛运帏刘璟陈有褀第6章图数据结构与算法高等教育2006第136附1第一问的floyd算法程fori=1:83V=[x1E=[x2y2fori=1:51forforif(i==x2(k)&j==y2(k))|(i==y2(k)&j==x2(k))elseifi==j
forforforforforifd(i,k)d(i,j)=d(i,k)+d(k,j);
forq=1:2000forp=1:a2(2)fori=1:21forforE=zeros(25,25);%Áгö¸Ã³õʼHȦ¼ÓµãÐò±ß¿òµÄ¾àÀë¾ØÕófori=1:23;forforforfo
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 2025年四川中医药高等专科学校高职单招职业技能测试近5年常考版参考题库含答案解析
- 2025年哈尔滨传媒职业学院高职单招职业技能测试近5年常考版参考题库含答案解析
- 2025年伊春职业学院高职单招职业技能测试近5年常考版参考题库含答案解析
- 贵州2025年贵州省住房和城乡建设厅所属事业单位招聘4人笔试历年参考题库附带答案详解
- 门诊护长述职报告
- 错误唇部护理案例分享
- 重症超声护理科普
- 江门市第三届职业技能大赛劳动关系协调员竞赛实施方案
- 钕磁铁工艺流程
- 第1课 鸦片战争(新教学设计)2023-2024学年八年级上册历史(部编版)
- 桥式起重机PLC控制改造设计
- 高考语文复习【知识精研】信息类文本阅读 课件
- 外研版(2024)七年级上册英语Unit4学情调研测试卷(含答案)
- 2024年9月证券专项《证券投资顾问业务》真题卷(74题)
- 保健品项目的商业计划书五篇
- 计算机软件及应用算王文字教程
- 印章管理责任承诺书4篇
- 《吊装起重作业培训》课件
- 2024年度供应商管理培训课件
- 2024-2030年中国写字楼行业发展态势规划分析报告版
- 培养内驱力培训课件
评论
0/150
提交评论