校内培训竞赛2问题三修改

：然后选出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（２相关概念完备图令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显然送货员能够一次带上所有货物到达各送货点，而且货物要送达的送货点总共为个本模型运用图论中最佳路径问题与最佳Ｈ圈中的相出发点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