物质运输的优化方案.doc

灾区物资运输的最优路径规划摘要近些年，自然灾害频繁发生。海啸、地震、泥石流、台风等自然灾害给人们带来了无尽的灾难，使人们的生活处于水深火热之中。面对大自然的爆发，人类却显得那么渺小。虽然我们无法避免自然灾害，但却可以降低它给人们带来的损失。因此，灾难发生后，如何快速、准确的确定灾区的位置、各灾区之间的联系及确定物资的发放路径便显得尤为重要了。本文讨论了一个灾区物资运输的最优路径规划问题，灾区应急物资运输非一般的物流活动，它具有弱经济性，讲究时间的紧迫性和运输路程的最优化，为此本文将提出一套优化的路径，来解决灾区物资运输难，速度慢，效率低的问题。对于问题一，计算任意两区域间的最短距离，题干中已经明确指出这30个受灾区域并非任意两个区域间都有道路直接相通，所以不能直接求这30个坐标两两之间的欧氏距离来作为这两个区域间的最短距离，所以我们把问题转化为图论问题来求解，先确定赋权图的权矩阵，然后再运用Floyd算法来求任意两点间的最短路径。对于问题二，把一批物资从发放站出发运输到各受灾区，最后运输车辆又回到发放站，这是一个典型的TSP回路问题，我们运用寻求最佳Hamilton圈的方法来求解，其中结合了二边逐次修正法进行优化，从而得到近似最佳Hamilton圈,从而确定了灾区物资运输的最优路径。关键词：最短路径问题、物资运输、Floyd（弗洛伊德）算法、赋权图、权矩阵、0-1规划问题、最佳Hamilton圈、TSP回路一问题的重述1.1 问题背景 在一次大的自然灾害中共有30个区域受灾，现需将A、B、C、D、E、F、G共7种物资发放到各个受灾区域，并且这30个受灾区域并非任意两个区域间都有道路直接相通。1.2 问题描述问题一：计算任意两区域间的最短距离；问题二：有一批物资需从发放站出发运输到各受灾区，最后运输车辆又回到发放站，请设计一条最短路径；二问题分析计算任意两区域间的最短距离，属于图论中无向图的最短路径问题，任意两点之间的权可取为这两点的欧氏距离，显然在求解此最短路径问题前，需要先将问题转化为一个图论问题，即将二维空间的路线问题转化为平面的图问题。问题一要求计算任意两区域间的最短距离，这里需要注意的是，题干中已经明确指出这30个受灾区域并非任意两个区域间都有道路直接相通，所以不能直接求这30个坐标两两之间的欧氏距离来作为这两个区域间的最短距离，而是要先根据道路间的相通条件来确定出赋权图，对不满足此道路相通条件要求的，可赋权为无穷大，从而转化为图论问题来求解。对于问题二则是利用上一问构造出完备图，用二边逐次修正法求解最优Hamilton圈的TSP回路问题。三模型假设与符号说明3.1 模型假设 （1）忽略七种物资从体积和重量方面不同而对各运输车辆的运输速度产生的影响。 （2）忽略运输途中自然灾害和外界的客观因素对正常运输速度的影响。 （3）任意两点间的曲线距离近似为其欧氏距离。（4）假设任意一区域都为一质点，不考虑区域内的距离。3.2 符号说明G(V,E,W): 赋权连通图V: G的点集合，即为各灾区及物资发放站的集合E: G的边集合，即为相邻各灾区或相邻的灾区与物资发放站之间两两连线的集合W：G的权集合，即为相邻两灾区或物资发放站与灾区之间距离的集合v、v：受灾区域v：物资发放站e:两受灾区域间的路径w(e):对应路径的长度、：受灾区域的横坐标、：受灾区域的纵坐标d: 两受灾区域间的欧式距离四模型建立与求解4.1 任意两区域最短距离的数学规划模型设P(v,v)是赋权图G=(V,E,W)中从点v到v的路径，记E(P)表示路径P(v,v)中全部边的集合，W(P)=,则称W(P)为路径P(v,v)的长度。如果P(v,v)是G中连接v到 v的某条路径，且对任意路径P(v,v)都有W(P)W(P),则称P(v,v)是G中连接v 到v的最短路径。假设图G有n个点，记为v，v，v，任意一条边vv的权w，下面建立数学规划模型求顶点v到v的最短路径。由于路径v到v要么在最短路径上，要么不再，故设0-1决策变量x，定义x=1表示路径v到v在最短路径上，否则为0.对于任意顶点v（vv且vv），如果=1，则说明所有以v为起点的边中必然有一条在最短路径上，即最短路径经过该顶点，所以所有从其他顶点到达该顶点的边中也必然有一条边在最短路径上，即有=1；如果=0，则说明最短路径不经过v，故必有=0，于是有=（1in）对于起点v和终点v，显然有=1，=1，于是建立最短路径的数学模型：Min z=（1in；j=1，n）=1 =1X0，1（i，j=1，n）4.1.1 模型的建立 把灾区位置分布图抽象为一赋权连通图G=(V,E,W)，在赋权图中，对应示意图中的各个灾区，v表示物资发放站，e 对应示意图中路径.边权w(e)W(G)对应示意图中的路径长度.4.1.2 算法介绍（Floyd算法） 在图论中，求解最短路径一般有两种方法，即Dijkstra*(狄克斯特拉)算法和Floyd（弗洛伊德）算法，Floyd算法可以一次性求出任意两顶点间的最短路径和距离，因此在第一问中我选择用Floyd算法，下面对Floyd算法的原理做一个简单的介绍 令表示一个矩阵，它的元素是1将图中各顶点编为确定矩阵，其中元素等于从顶点到顶点最短弧的长度(如果有最短弧的话)如果没有这样的弧，则令对于，令2对，依次由的元素确定的元素，应用递推公式每当确定一个元素时，就记下它所表示的路在算法终止时，矩阵的元素就表示从顶点到顶点最短路的长度 Floyd算法的软件实现详见模型的求解 4.1.3 求解准备1）根据已知位置点的坐标和连接情况，使用Matlab做出各点位置图如下：图1 各点位置与连通情况图2）根据已知各点坐标，由两点间距离公式求得图中相邻连通点间的距离如下表：表1 相邻连通点距离表序号点1点2距离（m）序号点1点2距离（m）序号点1点2距离（m）11273.658811261753.1905223141924.695921443.0122511361873.9477224142022.051231580.2833311461983.0045225142170.317441611.0579411562080.2596226142266.598551739.846281166229.6071227142331.717261823.4320411762457.1466228142426.2698711073.8527511862644.6727229142628.2507811139.031411963018.3477230142713.0642911282.52191207843.8447231142856.4131011461.5651217961.6802232143060.20211111743.81621227113.967323314311212069.741712371322.4382234151755.96821312111.428812471477.1089235151831.3041412215.062712571563.6445236151945.05191512371.215212671717.5789237152148.2031612446.369112771974.748238152554.98241712516.999212872073.214623915263.02171812637.389712972131.9523240152737.34831912774.164613072254.259241152840.85542012952.994813172368.8777242152940.9243211308.407513272451.8622243153038.88532213146.561213372538.56232441531232451.502613472664.8575245161772.309242546.3113572896.9983246161839.5284252683.341613673032.0677247162148.8233262783.81611378919.4461248162230.295272934.215113881051.4578249162551.3677282109.612513981635.0737250162622.41872921186.750914081851.0657251162757.34433021217.179714182046.4351252162822.63593121361.378514282232.9858253162917.6413221414.329314382348.6844254163043.30493321539.934914482423.6269255171884.82753421663.079214582621.0096256171958.51683521769.04914682752.0704257172057.273621836.984214782855.8629258172140.07053721916.053614883160.95746259172258.84373822014.806814991033.1813260172438.08393922181.49615091163.5136261172657.86364022279.97715191241.7922262172776.43194122325.066315291421.0121263172893.69254222712.230315391632.6685264172989.89894322974.393315491752.2444265173035.43174423071.253215591938.042266182048.6554453443.165915692035.0084267182266.8719463577.255415792150.0259268182358.6218473749.836515892341.0512269182449.2878483816.674415992420.5995270182835.94944931062.076816092557.6538271182943.51255031149.870816192610.2814272183069.89845131338.691916292733.415927319203.0345231524.969616393040.148274192178.37165331624.808516493180.31049275192281.44755431749.287165101191.088527619239945416610129.8038277192426.37295631964.3744167101366.1151278192647.93745732125.4406168101412.3358279192728.10475832217.1009169101658.3695280192880.67535932364.795170101774.7152281192983.86526032439.8706171101828.2119282193068.30426132530.6117172102182.6522283193199.353866232623.9001173102278.4048284202175.89366332762.0988174102334.3454285202278.57026432941.6414175102436.753286202310.42556533018.5833176102590.6725287202423.9257664538.2732177102639.4894288202726.4837674733.146317810272.6201289202877.8058684827.8884179102862.3547290202980.8889694937.3769180102968.0035291203065.7857041136.5231181103072.5303292203197.562557141266.98041821031110.3259293212223.04767241311.79631831112100.8599294212375.92937341542.3774184111325.4601295212451.99957442040.1331185111565.0765296212647.93787542256.8152186111721.4541297212783.19047642335.9918187112076.4743298222381.60287742420.786188112130.2935299222456.58067842553.6261189112253.0389300222522.11247942644.7481190112372.3962301222639.20038042882.3715191112792.4337302222778.21468142980.2193192112991.3087303222851.1238243035.7286193113031.6495304222942.5378343158.1129194113122.0891305223023.4614845691.3219195121375.9239306223156.81877855766.357196121421.6262307232425.05818651263.0008197121784.4894308232585.48828751349.3143198121828.8128309232651.30098851452.9081199122031.9711310232736.90018951565.758200122286.1074311232886.20629051690.7089201122342.0984312233066.16819151748.8361202122446.5544313242561.30399251879.8806203122646.912314242630.29389351930.2616204122864.6178315242738.37419452031.9247205123081.6456316242868.07199552182.15762061231119.9629317243041.92989652292.921207131455.0383318243174.870869752321.5264208131544.81319252654.299852438.9546209131711.3125320252791.05689952591.8773210131874.1871321252872.994510052668.7565211131952.796322253019.380410152758.3332212132051.0856323262739.119810253192.2946213132133.7561324262838.09631036833.8254214132249.7727325262937.93421046949.6638215132543.2772326263038.938710561082.8137216132646.6291327263180.741610661144.8608217132767.6154328272860.511410761291.0795218132882.4216329273073.129110861345.2962219133026.96683302731111.42410961470.6729220133146.5843331282910.514311061545.8405221141764.2827332293059.682511161639.1441222141826.9728333293198.8494.1.4 模型的求解 问题1要求计算这30个受灾区域任意两个的最短距离，首先根据表一中的数据利用matlab做出赋权图的权矩阵，再利用floyd算法结合Matlab的软件实现，D,path=floyd(W),其中，输入量W为赋权图的权矩阵，输出量D为一个n阶矩阵，其元素d表示从顶点v到v的最短路径的长度，path也是一个n阶矩阵，其元素p=k表示在顶点v到v的最短路径中顶点v的后继点为v，以此类推。M函数文件floyd.m内容如下：functionD,path=floyd(W)n=size(W,1);D=W;path=zeros(n,n); %设置D和path的初值 for i=1:n for j=1:n if D(i,j)=inf path(i,j)=j; %j是i的后继点 end endendfor k=1:n %做n次迭代，每次迭代均更新D（i,j）和path（i，j） for i=1:n for j=1:n if D(i,k)+D(k,j)D(i,j) D(i,j)=D(i,k)+D(k,j); %修改长度 path(i,j)=path(i,k); %修改路径 end,end,end,end 4.2 TSP回路模型TSP问题是数学领域中著名问题之一。假设有一个旅行商人要拜访n个城市，他必须选择所要走的路径，路径的限制是每个城市只能拜访一次，而且最后要回到原来出发的城市。路径的选择目标是要求得的路径路程为所有路径之中的最小值。4.2.1 模型的建立先给出图论中相关的一些定义.定义1 经过图G的每个顶点正好一次的圈，称为G的哈密顿环路，也称Hamilton圈.定义2 在加权图G=(V,E)中 (1)权最小的哈米顿圈称为最佳Hamilton圈； (2)经过每个顶点至少一次且权最小的闭通路称为TSP回路问题.由定义2可知，本问题是一个寻找TSP回路的问题.TSP回路的问题可转化为最佳Hamilton圈的问题.方法是由给定的图G=(V,E)构造一个以V为顶点集的完备图，中每条边（x,y）的权等于顶点x与y在图中最短路径的权，即在图论中有以下定理：定理1 加权图的物资运输员回来的权和的最佳Hamilton圈的权相同；定理2 在加权完备图中求最佳Hamilton圈的问题是NPC问题.求加权图G(V,E)的TSP问题回路的近似算法:1.利用第一问的结果构造出完备图， 2输入图的一个初始Hamilton圈； 3用对角线完全算法产生一个初始Hamilton圈；4随机搜索出中若干个Hamilton圈，例如3000个；5对2、3、4步所得的每个Hamilton圈，用二边逐次修正法进行优化，得到近似最佳Hamilton圈；6在第5步求出的所有H圈中，找出权最小的一个，此即要找的最佳Ha