运输问题研究

运输问题 摘要

本文主要是研究优化运输的问题。通过对十个客户两两之间的距离表进行分析并画出网络路线图，运用图与网络和最优化的方法建立相关数学模型，利用Lingo软件和Matlab软件进行计算，得出最优的行走路线。

针对问题一，求解单程最短路线问题，鉴于数据的有限性本文首先采用穷举法（枚举法）进行选定节点的单条路线分析，得到在给第二个客户卸完货时，到达客户10的最短路线，最后运用Dijkstra（迪杰斯特拉）算法进行检验，通过Lingo软件运行得到最短路程，与所求完全相同。

针对问题二，本文首先结合问题一所求最短路线进行分析，将双目标规划简化为单目标规划，并运用逐次逼近法对所给数据进行分析，获得最短的行驶路线。最后运用枚举法进行检验，发现所得数据一致。结果为：

V1?V5?V7?V6?V3?V4?V8?V9?V10?V2?V1

针对问题三，本文直接利用问题二得一辆车的最优回路，以货车容量为限制条件，建立相应的规划模型，设计了一个简单的寻路算法，最终确立合理的一号运输方案，经过模型检验，获得最优的二号方案，以下为一二号方案对比结果： 车号 行车路线 线路的长度 该车负责的客户 一号车 2，3，4，5，8 135公里 V1?V5?V2?V3?V4?V8?V9?V1 二号车 V1?V7?V6?V9?V10?V1 145公里 6，7，9，10 针对问题四，我们首先用Dijkstra算法确定提货点到每个客户点间的最短路线，然后结合一些限定条件建立一个目标模型，设计一个较好的解决方案进行求解可得到一种很理想的运输方案： 车号 行车路线 车号 行车路线 一号车 三号车 V1?V5?V2 V1?V7?V6 二号车 V1?V4?V3?V8 四号车 V1?V9?V10 该方案得到运输总费用是645元。

关键词; Dijkstra算法 枚举法 逐次逼近法

1.问题重述

运输问题关心的是以最低的总配送成本把供应中心(出发地)的任何产品运送到每一个接收中心(目的地)。每一个出发地都有一定供应量配送到目的地,每一个目的地都需要一定的需求量。每一个出发地都有一个固定的供应量, 所有的供应量都必须配送到目的地。与之类似,每一个目的地都有一个固定的需求量, 整个需求量都必须由出发地满足。某运输公司为10个客户配送货物，假定提货点就在客户1所在的位置，从第i个客户到第j个客户的路线距离（单位公里）用下面矩阵中的(i,j)(i,j?1,?,10)位置上的数表示（其中?表示两个客户之间无直接的路线到达）。

1、运送员在给第二个客户卸货完成的时候，临时接到新的调度通知，让他先给客户10送货，已知送给客户10的货已在运送员的车上，请帮运送员设计一个到客户10的尽可能短的行使路线（假定上述矩阵中给出了所有可能的路线选择）。

2、现运输公司派了一辆大的货车为这10个客户配送货物，假定这辆货车一次能装满10个客户所需要的全部货物，请问货车从提货点出发给10个客户配送完货物后再回到提货点所行使的尽可能短的行使路线？对所设计的算法进行分析。

3、现因资源紧张，运输公司没有大货车可以使用，改用两辆小的货车配送货物。每辆小货车的容量为50个单位，每个客户所需要的货物量分别为8，13，6，9，7，15，10，5，12，9个单位，请问两辆小货车应该分别给那几个客户配送货物以及行使怎样的路线使它们从提货点出发最后回到提货点所行使的距离之和尽可能短？对所设计的算法进行分析。

4、如果改用更小容量的车，每车容量为25个单位，但用车数量不限，每个客户所需要的货物量同第3问，并假设每出一辆车的出车费为100元，运货的价格为1元/公里（不考虑空车返回的费用），请问如何安排车辆才能使得运输公司运货的总费用最省？

2.问题分析

2.1对问题一的分析

运送员到客户10的最短路程，首先运用数据分析，得到各个客户之间的连通图，并且将第二个用户分别假设为2、3、4、5、6、7、8、9，再运用穷举法对所给路线进行最优选择，通过Lingo软件计算出各个不同客户到客户10的最短路。

2.2对问题二的分析

本文结合第一问，将双目标规划简化为单目标规划，首先运用逐次逼近法对所给数据进行分析，通过逐次筛选，获得最短的出发路线，然后将最后一个目的地看做起始点，以始发地看做目的地，求得其最短路程。 2.3对问题三的分析

对于问题三我们先通过常归思维去分析问题，得到的一号运输方案并与后面

建模得到二、三号运输方案比较，两者相差不大，随后本文运用逐步筛选的算法，得到最优路线。同时，这正说明了我们设计的算法是比较符合实际的，准确性是比较高的。

2.4对问题四的分析

对于问题四本文设计一个算法来解决问题，得到相应的结果验证了我们算法是可行的也是可靠的，但是局限性好大，也许这一算法仅适用于这类问题，不过我们将会尽最大努力地改进。

3.问题假设

（1） 每个出发地都有一定的供应量配送到目的地； （2） 每个目的地都有一个固定的需求量；

（3） 从出发地到任何一个目的地的运送成本固定； （4） 不考虑货物的装卸成本；

（5） 不考虑货物在运输途中的损坏情况；

4符号说明

Cij--------------------------------------------------------从i点到j点

5.模型分析与求解

5.1针对问题一的模型建立与求解 5.1.1最短路问题

最短路问题是网络理论中最广泛的用法之一，许多优化问题可以使用这个模型，如设备更新、管道铺设、线路安排、厂区布局等。最短路问题的动态规划问题，是解决某些比较困难最短路问题（如道路不能整齐分段者）构造动态规划方程，使用二图论方法比较有效。

最短路问题的一般提法如下：设G=（V,E）为连通图，图中各边（vi,vj）有权lij（lij=?表示vi,vj间无边）vi,vj为图中任意两点，求一条道路?，使它是从vs到vt的

所有路中总权最小的路。即：lu?(vi,vj)???lij最小。

有些最短路问题也可以是求网格中某指定点道奇余所有节点的最短路，或求网络中任意两点间的最短路。下面我们介绍三种算法，可分别用于求解这几种最短路问题。

.5.1.2模型建立与求解

根据原数据求得各个客户之间的路线图；

图1、各个客户之间的路线图

根据题目可知运送员是在给第二个客户卸货完成的时候，而客户1被假设为提货点，因此本文将客户1作为第二个客户的可能性排除。由上图各个客户的路线图分析可得；以下三类情况。 建立模型如下；

目标函数:minZ???Cij?Xiji?1j?11010?10??Xij?1?i?1,2,?,10?j?1?10?Xij?1?j?1,2,?,10? ???i?1条件:?Xij?0或1?0,1变量???1i?1?1010?X?X????1i?10?ijij??j?1j?1?0i?1,10???（1）由客户2到客户10，共有5种路线，如下图：

由客户4到客户10，有一种，如下图；

由客户7到客户10，有两种，如下图；

由图分析可知：假设由客户2出发则到达客户10时，最短路为2-3-8-9-10，总路程为85；同理可知，假设由客户3出发则到达客户10时，最短路为3-8-9-10，总路程为55；假设由客户4出发到达客户10，最短路为4-8-9-10；总路程为50；假设由客户5出发到达客户10，最短路为5-10，总路程为55；假设由客户6出发到达客户10，最短路为6-9-10，总路程为55；假设由客户7出发到达客户10，最短路为7-10，总路程为60；假设由客户8出发到达客户10，最短路8-9-10；总路程为30；假设由客户9出发到达客户10，最短路为9-10，总路程20； 5.1.3模型检验

Dijkstra（迪杰斯特拉）算法是图论中确定最短路的基本方法,也是其它算法的基础。为了求出赋权图中任意两结点之间的最短路径,通常采用两种方法。一种方法是每次以一个结点为源点,重复执行Dijkstra算法n次。另一种方法是由Floyd于1962年提出的Floyd算法,其时间复杂度为O?n3?,虽然与重复执行

Dijkstra算法n次的时间复杂度相同,但其形式上略为简单,且实际运算效果要好于前者。

Dijkstra算法基本步骤③： 令：s??vi?,i?1,s??v2,v3,?,vn? 并令：?W?v1??0T?vj???,vj?s??_

1、对vj?s，求minT?vj?,W?vi??wij?T?vj?。 2、求minTvjvj?s??????得T?v?，使T?v?=min?T?v??

kkjvj?s令W?vk??T?vk?

3、若vk?vn则已找到v1到vn的最短路距离W?vk?，否则令i?k从s中删去vi转1

这样经过有限次迭代则可以求出v1到vn的最短路线，可以用一个流程图来表示：

?

第一步 先取W?v1??0意即v1到v1的距离为0,而T?vj?是对T?vj?所赋的初

值。

第二步 利用W?v1?已知,根据minT?vj?,W?vi??wij对T?vj?进行修正。 第三步 对所有修正后的T?vj?求出其最小者T?vk?。其对应的点vk是v1所能一步到达的点vj中最近的一个,由于所有W?u??0。因此任何从其它点vj中转而到达vk的通路上的距离都大于v1直接到vk的距离T?vk?,因此T?vk?就是v1到vk的最短距离,所以在算法中令W?vk??T?vk?并从s中删去vk,若k=n则

W?vk??W?vn?就是v1到vn的最短路线,计算结束。否则令vi?vk回到第二步,继续

??运算,直到k=n为止。

这样每一次迭代,得到v1到一点vk的最短距离,重复上述过程直到vk?vn。 Floyd算法的基本原理和实现方法为:如果一个矩阵D???dij??其中dij?0表示i与

j间的距离,若i与j间无路可通,则dij为无穷大。i与j间的最短距离存在经过i与检查dij与j间的k和不经过k两种情况,所以可以令k?1,2,3,?,n,n(n为节点数)。

dik?dkj的值,在此,dik与dkj分别为目前所知的i到k与k到j的最短距离,因

此,dik?dkj就是i到j经过k的最短距离。所以,若有dij?dik?dkj,就表示从i出发经k再到j的距离要比原来的i到j距离短,自然把i到j的dij重写成dik?dkj。每当一个k搜索完,dij就是目前i到j的最短距离。重复这一过程,最后当查完所有k时,dij就为i到j的最短距离。

运用迪杰斯特拉方法，通过Lingo软件求解得到如下数据：（程序见附录）

通过检验求得结果相同，因此可以证明以上答案； 5.2针对问题二的模型建立与求解

5.2.1模型分析

很明显运输公司分别要对10个客户供货，必须访问每个客户，但问题要求我们建立相应模型寻找一条尽可能短的行车路线，首先不考虑送货员把10个客户所需的货送完货后不返回提货点的情形，利用求最小生成树的prim算法结合题中所给的邻接矩阵，很快可以得到以下一棵最小生成树：

1 5 7 6 3 2 10 9 8 4 以上路线的总行程为175公里，充分利用问题一所建的模型(1),很快就可以求得V2（客户2）返回V1（提货点）的最线路是V2?V1行程50公里(注:代用模型(1)时,需先将题中的邻接矩阵的第一行与第二行交换,第一列与第二列交换后参照附录[1]的代码可求解)，我们有理由相信这样构成的回路实际上也是最短回路：

1 5 7 6 3

2 109 8 4

该回路可描述为：

V1?V5?V7?V6?V3?V4?V8?V9?V10?V2?V1

总行程为225公里。这种寻路方法并不比其他方法差而且它的速度也很快，只是它局限于顶点数较少的情形，一旦顶点数扩大实现起来难度就会大大提高，而且它的不易推广，因此我们有必要对此问题深入研究，进而建立起一个数学模型以适应顶点数变化，使它能够具有较好的推广性，应用到现实生活中去来实现以不变应万变的现象。 5.2.2模型建立与求解

可建立问题的模型(2)为：

1010目标函数:minZ???Cij?Xiji?1j?1?10??Xij?1?i?1,2,?,10?j?1?10?X?1?j?1,2,?,10?ij??i?1?X?0或1?0,1变量? ?条件:?ij?整型变量??Xij?N?ui?uj?n?Xij?n?1??2?i?j?n??ui?0???i?1,2,?,10??

同样借助数学软件求解可得结果：

从中可以找出一条较为理想的回路是：

V1?V5?V7?V6?V3?V4?V8?V9?V10?V2?V1

可见按此模型求解的结果与采用prim算法求解的结果是一样的。 5.2.3模型检验

在程序设计中，有时会用到由若干个有限数据元素组成的集合，程序中某个变量取值仅限于集合中的元素。此时，可将这些数据集合定义为枚举类型。因此，枚举类型是某类数据可能取值的集合：下面为运用枚举法求解所得到的数据； 一种方式；

1 5 7 6 3 2 109 8 4

第二种方式：

1 2 3 4 5 10 9 8 7 6 通过总路程对比可知，两种方法所得数据相同，因此可以证明此结论正确；

5.3针对问题三的模型建立与求解

5.3.1模型的猜想

用两辆容量为50单位的小货车运货，在每个客户所需固定货物量的情况下，要使得行程之和最短，我们假设每个客户的货物都由同一辆货车提供，这样只要找出两条尽可能短的回路，并保证每条线路客户总需求量在50个单位以内。实际 上这样的两条回路是存在的：由题二得到了一条哈密顿回路

V1?V5?V7?V6?V3?V4?V8?V9?V10?V2?V1

可根据货物需求量的大小将其分为前后两部分，并将之分别构成回路。（注：由于提货点在客户1所在的位置，故不必考虑为客户1送货的情况。） （1）由此思想建立以下模型

Step1：根据以下模型获得一个值k；

Step2：依k的取值分两条路径：

L1:V1?VGet?N1????VGet?Nk?L2:VGet?NK?1??VGet?NK?2????V1

Step3：利用模型(1)分别求得VGet?Nk?到V1的最短路径：VGet?NK????V1 以及

V1到VGet?NK?1?的最短路径：V1???VGet?NK?1?

Step4：从而获取两辆货车的路线如下表： 车号 路线 一号车 V1?VGet?N1????VGet?Nk????V1 二号车 V1???VGet?NK?1??VGet?NK?2????V1 据上描述可建立模型；

目标:maxk?kU?Ni??50???1条件:?ki??1??U?Ni??50??i?1

?k?1,2,?,9?

依据模型很容易求得：k=5

所以根据我们所设计的算法很快找到一组合理的运输路线是： 车号 行车路线 一号车 V1?V5?V7?V6?V3?V4?V1 二号车 V1?V5?V8?V9?V10?V2?V1 （2）模型优化 由上知，两辆车都经过了客户5，根据算法二号车必经过客户5，因此将一号车进行优化可得如下所示； 车号 行车路线 线路的长该车负责的客度 户 一号车 140公里 3,4,6,7 V1?V7?V6?V3?V4?V1 二号车 V1?V5?V8?V9?V10?V2?V1 155公里 2,5,8,9,10 两辆车全程总和为295公里。 5.3.2模型建立与求解

用两辆容容量相等的货车为这10个客户分配货物，要求使行驶的路线尽量最短，因此本文运用问题二所求得的最短行驶路线，进行假设分析；同样本文建立线性规划模型对运输方案进一步优化，并且将问题简化为单目标，首先确定第一辆车的最优行驶路线，再将模型进行简化定义和说明；

1．Dj为每个客户的需货量,它是在向量?8,13,6,9,7,15,10,5,12,9?的每j个分量,据上分析知:36???Xij?Dj?50(不考虑客户1的需求量,因为它在提货点)。

i?1j?110102．由于这里是分两条路线分别给10个客户送货,就没有必要设计每条路线都能够访问每个客户点,但要保证送货员能回提货点,且均从提货点出发回到提货点，则送货员进入一个客户同时也必须出来。故我们用以下条件来分别保证我们的假设：

?Xi?110ij?1?j?1,2,?,10? ?Xij?1?i?1,2,?,10?

j?110i?210?Xj?2101,j?1与?Xi,1?1 ?X??Xijj?1j?11010ij?0

到此我们得到了一个模型，它是一个指派问题的整数规划模型。其目标是使式子：

??Ci?1j?11010ij?Xij

在约束条件下取得最小值。

其余变量的假设与问题二的假设一致。

故可建立模型（3）如下：

目标函数:minZ???Ci?1j?11010ij?Xij?10??Xij?1?i?1,2,?,10?j?1?10?Xij?1?j?1,2,?,10???i?1?X?0或1?0,1变量?ij??Xij?N?整型变量??u?u?n?Xi?n?1jj?i??2?i?j?n??条件:?ui?0i?1,2,?,101010??36???Xij?Dj?50i?1j?1?1010?Xij??Xij?0??j?1j?1?1010?Xij?K???i?1j?1?1010 ?X?1,X?1?1,j?i,1?i?2?j?2在36?Dj?50约束下，参加附录[3]的代码，在lingo中求解可得以下结果： K的值 <=5 6 >=7 以上可视为确定首先确定的第一辆车的行车方案；则这两条路线所对的第二辆车最优路线的选择，（以长度为95公里的路线为例）只需将模型（3）中的条件：

满足条件的较短路径（1-1） V1?V5?V7?V8?V9?V1 V1?V4?V8?V9?V10?V5?V1 路径长度（单位：公里） 95 135 …… 不存在符合条件的路径 ?X??Xijj?1j?11010ij?0与??Xij?K改为条件Xij?1i?1j?11010?j?2,3,4,6,10且j?i?

即要保证第二辆访问到所有第一辆车未访问过的客户，允许其访问第一辆车访问过的客户，故模型基本上不用改动。同样参照参加附录[3]的代码，可求得上述路线对应的另一条路线为： K的值 满足条件的较短路径（2-1） 路径长度 （单位：公里）

<=5 6 >=7 V1?V5?V2?V3?V4?V6?V9?V10?V1 V1?V5?V2?V3?V6?V7?V1 205 155 …… 不存在符合条件的路径 此时我们可以为公司提供一种更好的二号运输方案： 车号 行车路线 线路的长度 该车负责的客户 一号车 135公里 4，5，8，9，10 V1?V4?V8?V9?V10?V5?V1 二号车 V1?V5?V2?V3?V6?V7?V1 155公里 2，3，6，7 两辆车全程总和为290公里。 5.3.3模型检验

从以上产生的结果中很容易，往往第一辆车通过的线路，有些第二辆车也要经过，并不能保证两条线路完全独立，显然这样话，我们可以确定第一辆车的线路的时候让其线路上的货物承受量大一点，两车都经过的让第二辆车去送货，这样模型（3）很可能就存在缺陷了，这是由于对条件：36???Xij?Dj?50的上界进行约束引起的，因此

i?1j?11010们可以这个条件的上界放大，给模型有更大的自由选择空间，可将它改为：

36???Xij?Dj?86

i?1j?11010，再用上述方法可以求解，但此最后形成运输方案的时候应该多考虑另一个因素，即哪些客户的货物由走哪条线路的货车负责运送，同样地可以得到以下的运输方案： K的值 满足条件的较短路径（1-2） 路径长度 （单位：公里） <=5 95 V1?V5?V7?V8?V9?V1 6 7 8 9 V1?V5?V2?V3?V8?V9?V1 V1?V5?V2?V3?V4?V8?V9?V1 V1?V7?V5?V2?V3?V4?V8?V9?V1 V1?V7?V5?V2?V3?V4?V8?V9?V10?V1 125 135 150 185 10 不存在符合条件的路径 …… 而计算第二辆车的路径，与模型（3）的计算方法完全一样，其结果如下： K的值 满足条件的较短路径（2-2） 路径长度

<=5 6 7 8 9 V1?V5?V2?V3?V4?V6?V9?V10?V1 V1?V7?V6?V4?V8?V9?V10?V1 V1?V7?V6?V9?V10?V1 V1?V7?V6?V9?V10?V1 V1?V7?V6?V9?V1 （单位：公里） 205 170 145 145 110 10 不存在符合条件的路径 …… 根据两个表中的路径，进行对比很容易得出一个最优的三号运输方案那就是：

车号 行车路线 线路的长度 该车负责的客户 一号车 135公里 2，3，4，5，8 V1?V5?V2?V3?V4?V8?V9?V1 二号车 V1?V7?V6?V9?V10?V1 145公里 6，7，9，10 两辆车全程总和为280公里。

5.4问题四的模型建立与求解

5.4.1模型的假设

由于出车费100一辆,相当于100公里的行程费用,当行程超200公里时是否以多出车来换取小行程呢?我们认为没必要:其一从题中给出的数据阵可以看出行程超过200公里该车至少经过4个客户点,其总货物需求量超过小车的容量,是不可取的;其二即使可行,但要保证加车后,两辆车总行程要控制在100公里以内也不是一件容易的事。从此两个原因可以看出我们不必考虑加车的方案，即根据客户总需求量与货车的容量可决定只派4辆车为客户送货即可。

（1）假设派四辆车运送货物；

分析，首先将10个地点分成4条路线去完成，即每条线路行驶的路程最短，货物量不得超过25 各单位，每辆车的出车费为100元，每公里的路程为1元，（不考虑空车返回时的费用），计算费用最优； 5.4.2模型建立

由问题可知，十个客户总的货物需求量为94个单位，每辆货车最多承载25个单位，假设每辆货车只是送一趟货，而且尽量使每辆车在运输过程中经过的站

4点不重复，那么至少需要的货车数为[94/25]?（辆）。因此本文首先以四辆车进

行送货尝试，除去固定的出车费用外要求总的运输成本最小，则该问题可以转化为寻求每辆车所行驶的最短路径问题。

设Li(i?1,2,3,4)为每辆车行驶的路线，每条路线经过的站点

Li?[PjQjWjRj](j?1,,,10)且有[PjQjWjRj]?[Zj]其中Z（为所jj=1,,,10）有的客户站点，aij为第i条路线前一个站点到第j站点距离，bi为每条路线的最短距离。

MinC?400?Li(u)

s.t?U(k)?25,k?1,2,3,4?4 ?minL(?)?b?ii?i?1?引入0—1变量，建立bi的最优化模型：

?10??Pjaij(j?1,,,10)?j?1?10??Qjaij(j?1,,,10)?j?1?10? bi(i?1,2,3,4)???Wjaij(j?1,,,10)?j?1?10??Rjaij(j?1,,,10)?j?1?0表示在第i条路线上不经过该j点?P,Q,W,R???jjjj?表示在第i条路线上经过该j点?1?根据Lingo软件可以得出运输公司所派出的4辆车所走的路线及每

路线总长度 40 80 55 70 货物需求量 20 20 25 21 条线上的货物总需求量如下表： 车号 行车路线 一号车 二号车 三号车 四号车 V1?V5?V2 V1?V4?V3?V8 V1?V7?V6 V1?V9?V10 显然每条发车路线上的货物总需求量均不会超过货车的容量25，故方案可行；则公司运货的总费用：

c?400?40?80?55?70?645（元）

5.4.3模型的检验

由以上分析可得若派出四辆车，则最小费用为645元，但是问题当中没有对时间进行限制，因此，我们也可假设只雇用一辆车，按以上运输方案进行运输，如下表所得; 车号 行车路线 路线总长度 货物需求量 一号车 40 20 V1?V5?V2 一号车 一号车 一号车 V1?V4?V3?V8 80 55 70 20 25 21 V1?V7?V6 V1?V9?V10 则最小费用为c=100+40+80+55+70=345(元)；

6.模型评价

6.1模型的优点

本文从模型建立来看，无论是理论值还是实际值都比较接近，而且我们从模型的假设到模型的创新，以及方法运用上都是合理的，因此可以说明本文实际运用性比较强，可以与用于其他问题的研究和求解。

首先，该模型是基于Dijkstra算法的基础上转化为线性规划模型来求最短路径的模型,优点是实现较简单,也容易求解；

其次，虽然我们猜想模型很简单，但它是解决本问题的关键，也是我们建模思路的切入点，通过这个模型的建立与求解我们逐渐发现问题的所在，故而引导我们对自己所建的模型一步一步地优化，最终得到一个非常理想的运输方案

最后，我们设计的解决方案是以Dijkstra算法为基础，以小车容量为约束条件得出的一种解决问题的方法，从模型分析可以看出我们没有必要去考虑以加车的方法来换取短路线的方案，因此直接根据客户的总需货量可以知道，至少需要4辆小车来送货。从得出的运输方案来看，这种办法确实是可行了，且并不会很差。

6.2模型的缺点

首先本文有个令人不是很满意的地方就是其模式固定,要求任两个客户点间最短距离时,需将其一客户的位置与提货点互换,另一个客户的位置则需与客户10的位置互换,将其看成原始的提货点到客户10最短距离的模型进行求解，这样较为烦琐,有待改进。

其次，本文模型也存在不少问题，例如我们没有用一个统一的模型来同时得出两辆车的最优路线，这是我们觉得比较郁闷的地方，我们将慢慢地对其不断改进与完善。

6.3模型的推广

最短路径问题在交通网络结构的分析，交通运输线路(公路、铁路、河流航运线、航空线、管道运输线路等)的选择，通讯线路的建造与维护，运输货流的最小成本分析，城公共交通网络的规划等，都有直接应用的价值。

在很多目标信息引导系统的设计中．需要获得最优化路径引导信息。例如，在日益增多的高层建筑、大型公共建筑(超级市场、博物馆、医院、游乐场等)场台的火灾事故现场救生疏导系统，需要根据现场情况动态地为逃生者实时提供最短的安全通道指引信息；而当这些场合发生盗窃、抢劫等突发犯罪事件时，安全监控系统如能为警方实时提供通向罪犯所处位置最短搜索路径信息．则可以达到迅速制止犯罪的目的。在设计一个大型高层建筑火灾事故现场救生疏导系统时，将图论中Dijkstra算法应用于目标信息引导系统的设计中，通过Dijkstra算法，首先计算出任一指定位置点距各疏导出口的最短路径树，进而通过编制辅助方向指示箭头程序．动态地将火灾事故现场救生疏导路径引导图加以显示，从而达到优化目标引导路径的目的．

7.参考文献

【1】卜月华 图论及其应用 南京：东南大学出版社，2000 【2】最短路问题在运输网络中的应用 李玲 2006

【3】戴文舟. 交通网络中最短路径算法的研究 [D ]. 重庆大学硕士学位论文 ,2004.

【4】荣玮.基于道路网的最短路径算法的研究与实现.武汉理工大学硕士学位论文[D],2005. 【5】朱建青 ,张国梁.数学建模方法M. 郑州大学出版社. 【6】杨民助 ,运筹学M. 西安交通大学出版社.

【7】殷剑宏 ,吴开亚.图论及其算法M. 中国科学技术出版社. 【8】王朝瑞.图论M. 国防工业出版社.

【9】姚思瑜.数学规划与组合优化M. 浙江大学出版社.

【10】秦裕瑗 ,秦明复.运筹学简明教材M. 高等教育出版社.

8.附录

附录一 求解问题一

n=9; a=zeros(n);

a(1,2)=30;a(1,4)=35;a(1,5)=50;a(1,7)=60;

a(2,3)=15;a(2,5)=30;a(2,6)=50;a(2,7)=25;a(2,9)=60;

a(3,4)=45;a(3,5)=30;a(3,6)=55;a(3,7)=20;a(3,8)=40;a(3,9)=65; a(4,5)=60;a(4,6)=10;a(4,7)=30;a(4,9)=55; a(5,6)=25;a(5,7)=55;a(5,8)=35; a(6,7)=30;a(6,8)=45;a(6,9)=60; a(7,8)=10;a(8,9)=20;

a=a+a'; M=max(max(a))*n^2; %M为充分大的正实数 a=a+((a==0)-eye(n))*M; path=zeros(n); for k=1:n for i=1:n

for j=1:n

if a(i,j)>a(i,k)+a(k,j) a(i,j)=a(i,k)+a(k,j); path(i,j)=k; end end end end a, path a =

0 30 45 35 50 45 55 65 85 30 0 15 55 30 50 25 35 55 45 15 0 45 30 50 20 30 50 35 55 45 0 35 10 30 40 55 50 30 30 35 0 25 45 35 55 45 50 50 10 25 0 30 40 60 55 25 20 30 45 30 0 10 30 65 35 30 40 35 40 10 0 20 85 55 50 55 55 60 30 20 0

path =

0 0 2 0 0 4 2 7 8 0 0 0 7 0 0 0 7 8 2 0 0 0 0 7 0 7 8 0 7 0 0 6 0 0 7 0 0 0 0 6 0 0 8 0 8 4 0 7 0 0 0 0 7 0 2 0 0 0 8 0 0 0 8 7 7 7 7 0 7 0 0 0 8 8 8 0 8 0 8 0 0

附录二

求解问题二的程序 MODEL: SETS:

CUSTOMERS / 1.. 10/: U; LINK( CUSTOMERS, CUSTOMERS):DIST,X; ENDSETS DATA: DIST =

0 50 100000 40 25 100000 30 100000 50 100000 50 0 30 100000 35 50 100000 60 10000 100000

100000 30 0 15 100000 30 50 25 100000 60 40 10000 15 0 45 30 55 20 40 65

25 15 100000 45 0 60 10 30 100000 55 100000 50 30 30 60 0 25 55 35 1000000 30 100000 50 100000 10 25 0 30 45 60 100000 60 25 20 30 55 30 0 10 100000 20 100000 100000 40 100000 15 25 45 0 20 35 20 10 45 20 100000 60 100000 30 0; ENDDATA

N = @SIZE( CUSTOMERS); MIN = @SUM( LINK: DIST * X);

@FOR( CUSTOMERS( K): @SUM( CUSTOMERS( I)| I #NE# K: X( I, K)) = 1; @SUM( CUSTOMERS( J)| J #NE# K: X( K, J)) = 1;

@FOR( CUSTOMERS( J)| J #GT# 1 #AND# J #NE# K: U( J) >= U( K) + X ( K, J) -( N - 2) * ( 1 - X( K, J)) +( N - 3) * X( J, K)); ); @FOR( LINK: @BIN( X));

@FOR( CUSTOMERS( K)| K #GT# 1: U( K) <= N-1- (N - 2) * X(1,K);U( K) >=1+(N-2)*X(K, 1)); END

本文来源：https://www.bwwdw.com/article/iz9g.html