《送货路线-数学建模-一等奖》由会员分享，可在线阅读，更多相关《送货路线-数学建模-一等奖（26页珍藏版）》请在金锄头文库上搜索。
1、摘要本文讨论了送货员送货路线的优化设计问题，即在给定送货地点和给定 设计规范的条件下，综合考虑最大载重范围、最大带货体积以及各货物送货时限， 确定业务员的最佳运行路线策略.并总结出一些在这类图中求解近似最优回路的 有效法则对于问题1，采用了两种方法进行了计算，第一种是通过 Floyd算法做出各 顶点间的最短路径矩阵，然后选出130号货物所送达的顶点间的最短路径及距 离，用二边逐次修正法求解 Hamilton圈；第二种是通过蚁群算法获得多条近似 优解，选取最佳线路对于第二问，则采用改进的遗传算法，求解有时间约束条件的 TSP问题， 根据线路规划问题的特点，基于遗传算法（GA ）建立了一个适用于带
2、有时间约 束的送货路线规划模型实验证明了此算法的有效性和可行性对于第三问，利用分割求解法和蚁群算法的合成算法， 运用共同链分割全图， 对每一个分图进行最优求解，由此得到全图的最优解。关键词 送货问题；优化路线；TSP模型；蚁群算法#送货路线设计的数学模型1问题重述现今社会网络越来越普及，网购已成为一种常见的消费方式，随之物流行业 也渐渐兴盛，每个送货员需要以最快的速度及时将货物送达，而且他们往往一人 送多个地方，请设计方案使其耗时最少现有一快递公司，库房在图1中的0点，一送货员需将货物送至城市内多处， 请设计送货方案，使所用时间最少该地形图的示意图见图1,各点连通信息见表 3,假定送货员只能沿
3、这些连通线路行走，而不能走其它任何路线.各件货物的相关信息见表1，50个位置点的坐标见表2.假定送货员最大载重50公斤，所带货物最大体积1立方米.送货员的平均速 度为24公里/小时.假定每件货物交接花费3分钟，为简化起见，同一地点有多件 货物也简单按照每件3分钟交接计算.现在送货员要将100件货物送到50个地点.请完成以下问题1. 若将130号货物送到指定地点并返回设计最快完成路线与方式给出结果. 要求标出送货线路2假定该送货员从早上8点上班开始送货，要将130号货物的送达时间不 能超过指定时间，请设计最快完成路线与方式要求标出送货线路3.若不需要考虑所有货物送达时间限制（包括前30件货物），
4、现在要将100件 货物全部送到指定地点并返回设计最快完成路线与方式要求标出送货线路，给 出送完所有快件的时间由于受重量和体积限制，送货员可中途返回取货 可不考 虑中午休息时间.2模型的假设与符号说明2.1模型假设1 假设送货员只能沿如图所示连通线路行走，而不能走其它任何路线；2在连通线路中业务员可以任意选择路线；3假设送货员每到达一个地点，交接一件货物花费都为3分钟，交接完毕马上前往下一个地点，期间不花费时间；4假设送货员的速度保持匀速，即保持24公里/小时，不考虑堵车，发生意外等现象；2.2符号说明Wi :第i个货物的重量；(x, y)j :序号为i的送货点的坐标；V :第i个货物的体积；C
5、 :送货路线总路程；N :送货员送货次数；t:送货所用总时间；G(V,E):赋权连通图；Gi : G(V,E)的第i个子图；Li :子图Gi中的最佳回路；- (e):边e的边权；(v):点v的点权；li : Li的各边权之和；e : Li的各点权之和；T:送货中的停留时间；u :送货员的行驶速度；点权 (ViT V .为叙述方便起见，我们在文中不加说明地使用上述变量和符号的变形形式， 它们的含义可以通过上下文确定3模型的分析与建立3.1模型的建立把快递公司送货地点示意图抽象为一赋权连通图G(V,E)，在权图G中，v- V(G)对应示意图中的快递公司地点及货物送达点，V0表示快递公司所在地，eE
6、(G)对应示意图中路径.边权(ejT对应示意图中的路径长度建立的数学模型如下：飞 E(G),，(e) N, v V(G),(v) V?,v0 V求G中回路L1,L2jH,Lk(k1)，使得满足:k(1)V。V(Li),i 2|,k; (2)V(LJ=V(G);n(3)二二-：(e) = min(目标为总距离最短)i 二 e圧(LJjT%或 max 二 注(e) :二(v) = min(目标为时间最短 )1勺兰、e手(LJem(LJ为了讨论方便，先给出图论中相关的一些定义定义1经过图G的每个顶点正好一次的圈，称为G的哈密顿环路，也称Hamilton 圈.定义2在加权图G =(V,E)中(1) 权
7、最小的哈米顿圈称为最佳 Hamilton圈；(2) 经过每个顶点至少一次且权最小的闭通路称为TSP回路问题.由定义2可知，本问题是一个寻找 TSP回路的问题.TSP回路的问题可转化 为最佳Hamilton圈的问题.方法是由给定的图G=(V,E)构造一个以V为顶点集 的完备图G(V,E)，E中每条边(x,y)的权等于顶点x与y在图中最短路径的 权，即卩mm -1m-1 m-1、djmin dimdmj 在图论中有以下定理：定理1加权图G的送货员回来的权和G 的最佳Hamilton圈的权相同；定理2在加权完备图中求最佳 Hamilton圈的问题是NPC问题.在解决问题的过程中，我们用到以下算法：算
8、法一(Floyd算法)：令Dn表示一个N x N矩阵，它的(i, j)元素是dj.1. 将图中各顶点编为1,2,H|,N .确定矩阵Do，其中(i,j)元素等于从顶点i到 顶点j最短弧的长度(如果有最短弧的话).如果没有这样的弧，则令d/：.对 于 i，令 d/ =0 .2. 对m=1,2川|,N，依次由Dm-i的元素确定Dm的元素，应用递归公式mm JmJ m J.dij -mindmdmj ,dj .每当确定一个元素时，就记下它所表示的路.在算法终止时，矩阵Dn的元素(i,j)就表示从顶点I到顶点j最短路的长度.算法二：求加权图G =(V,E)的TSP问题回路的近似算法：1用算法一(Flo
9、yd算法)求出G=(V,E)中任意两个顶点间的最短路，构造出完备图G =(V,E ),-(x,y) E； (x,y)=mi n dG(x,y).2. 输入图G 的一个初始Hamilton圈；3. 用对角线完全算法产生一个初始 Hamilton圈；4. 随机搜索出GJ(V,E)中若干个Hamilton圈，例如2000个；5. 对2、3、4步所得的每个Hamilton圈，用二边逐次修正法进行优化，得到近似最佳Hamilton圈；6. 在第5步求出的所有H圈中，找出权最小的一个，此即要找的最佳Hamilton圈的近似解.算法三：蚁群算法蚁群算法是一种新型的模拟进化算法该算法由意大利学者 M. Dor
10、igo V.Maniezzo和A. Colorini 等人在90年代首先提出，称之为蚁群系统(ant colony system )，应用该算法求解TSP问题、分配问题，取得了较好的结果.算法受到 真实蚁群觅食行为的启发，科学家发现虽然单个蚂蚁没有太多的智力，也无法掌握附近的地理信息，但整个蚁群却可以找到一条从巢穴到食物源之间的最优路线 经过大量细致观察研究发现：蚂蚁个体之间通过一种称之为外激素(pheromo ne) 的物质进行信息传递蚂蚁在运动过程中，能够在它所经过的路径上留下该种物 质，而且蚂蚁在运动过程中能够感知这种物质，并以此指导自己的运动方向， 因此，由大量蚂蚁组成的蚁群的集体行为
11、便表现出一种信息正反馈现象：某一路径上单位时间走过的蚂蚁越多，表明该路线的可用性越好，则后来者选择该路径 的概率就越大.蚂蚁个体之间就是通过这种信息的交流寻找最优的到达食物源的线路.蚁群算法具有实现简单、正反馈、分布式的优点町b）c）图1蚁群算法说明在图1中， 从A到E （或者从E到A）有两条路径（ABCDE和ABHDE，其中B 到H D到卜的距离为1，B到C和D到C的距离为0.5.下面分别考虑在时刻t = 0 , 1 ,2 . 时蚁群的运动情况.如图2b,在时刻t = 0 ,设有30只蚂蚁从A运动到B. 此时路径BHBCh没有外激素（蚂蚁留下的信息量），故蚂蚁将以相同的概率向BC BH运动，
12、于是各有15只蚂蚁分别选择路径BH和BC.在真实蚁群中，外激素的数量会随时间的流逝而蒸发掉一部分， 为说明方便， 此处假设： 所有蚂蚁运动的速度相等； 外激素蒸发量与时间成正比例，即路径上外激素的剩余量与路径的长度成反比； 蚂蚁选路的概率与所选路上外激素的浓度成正比.因为路径BHD的长度是路径BCD勺2倍，当B点的蚂蚁到达D点后，路径BCDt的外激素是BHDt 的2倍.如图2c，在时刻t =1有30只蚂蚁从E到达D.因为路径DC上的外激素 量是DH1的2倍，根据蚂蚁选路特点，将会有20只蚂蚁选择DC而只有10 只蚂蚁选择DH.以此类推，当t = 2 ,3 ,4.时，将会有更多的蚂蚁选择路径BC
13、D经过较长时间运动后，蚁群最终会沿着最优路径 ABCD运 动.网络的路由问题与蚁群寻路的问题有很大的可比性，都是寻找可以到达目的地的最优路线.目前已经证明蚁群算法在解决路由问题上具有分布式、正反馈、全局收敛等优点3.2求解准备1）根据已知位置点的坐标和连接情况，使用Matlab做出各点位置图如下:图2各点位置与连通情况图2）根据已知各点坐标，由两点间距离公式 d （咅_x2）2 （% y2）2求得图中相邻连通点间的距离如下表：表1相邻连通点距离表序号点1点2距离（m）序号点1点2距离（m）序号点1点2距离（m）113191631162320986138361537218286432172317
14、75623927178032207823331831210463403416314242293341924225964404532175381958352022149965414423666343536362126219266413726027422293372136288067414627358515500538211718246842439189521253392230128769424919711061129440231717757043382618117185918412431178071444821531271196842254141557244504987138121757432519196673455031031491426814425291886744542235215910194645273110687546481494161018591046283313267
