2011重金属污染分析论文例题

摘 要

该问题的核心是最优化某目标函数。传统的约束下的离散或连续最优化模型都很难完整地刻画和描述本题。比较常用的是通过约束换乘次数，搜索可能的路线，然后根据优化目标进行选取。但显然这种方法具有如下缺点：（1）由于数据数量庞大，穷举需要大量时间，实际操作和应用性差；（2），对于所给路线和站点，存在两个站点经过给定次数换乘不能到达的情况，不具有一般性；人为增加这样的约束很有可能得不到最优化时间和费用的路线。

为了使问题得到完善的解决，我们利用图论的知识，将该问题描述为一赋权有向图求最短路的图模型，适当推广文献中的经典算法进行求解。简要说明如下：直观上看，该问题不能被刻画为一有向图，因为若将不同站点视为顶点，可能有多条线路连接两顶点。但若我们将同一站点分割为对应不同线路的多个顶点，则可得到一有向图。由所给的不同费用和时间数据，可根据所要优化的目标对不同顶点之间赋权，这样最终构成了一有向赋权图。对于任意给定的目标，即时间最短，费用最少，换乘约束，或综合考虑时间，费用和换乘，我们仅需要适当的修改赋权函数即可。求得此图的最短路径即可得到最优化给定的目标函数的乘车路线。适当推广著名的Dijkstra算法至二维表示情形，我们可以方便快速地求得所要路线。我们利用Fortran95实现该算法。该方法具有如下优点：计算量小，最多需要O(n2)阶运算即可完成，适当优化可使得计算量降至

O(nlog(n))；具有一般性和易用性，进行少量修改，就能够根据任意所指定的优化目标

进行优化，比如我们可利用该算法达到前面所述常用的约束换乘次数的目标；最优性，尽管满足某一目标的路线不一定唯一，但根据这种方法我们求出的路线必定能够最优化该目标。

对于问题一要求仅考虑公汽线路，我们在表一中给出包括用时最少及综合费用，换乘次数等因素在内的多种最佳路线选择。例如对(1)S3359S1828，经过计算，我们找到S3359

L484下(5)S3727

L485反(12)S1784

L167下(1)S1828作为最佳路线，用最

少时分钟，换乘两次，花费3元。

对于问题二考虑公汽与地铁线路，只需再增加4条线路，也就是对应的二维数组增加了4行，算法与之前相似。在表二中的结果说明，增加考虑地铁线路后，对于要求的6条路线中的部分路线，又有了新的最佳路径。如(6)S0087S3676, 直接可有地铁到达，行程20分钟，很大程度上减少了时间和费用的损失。

对于问题三，若将步行时间考虑进来，对于我们所构造的有向赋权图模型来说，仅需要将5.2节中的公共汽车和地铁同时考虑的模型进一步推广，具体来说，就是将所有已有的站点所对应的顶点个数都增加一个，然后修改权函数的定义方式，增加对步行方式的描述，这样最终依然是一有向赋权图，仅仅是顶点数为原来的一倍，在给定适当优化目标函数后，我们同样重复前述算法即可得到最佳路径。

关键词：赋权图；Dijkstra算法；最优化

1

一、问题的提出

我国人民翘首企盼的第29届奥运会明年8月将在北京举行，届时有大量观众到现场观看奥运比赛，其中大部分人将会乘坐公共交通工具（简称公交，包括公汽、地铁等）出行。这些年来，城市的公交系统有了很大发展，北京市的公交线路已达800条以上，公交线四通八达，使得公众的出行更加通畅、便利，但同时也面临多条线路的选择问题。而现实中，一个站点A到另一个站点B，应该有大量的不同选择的路线可以走，每一条线路中间可能转车，可能直达，路线所花费的时间、路程、费用和换车次数是完全不同的。针对这样的市场形式，某公司准备研制开发一个解决公交线路选择问题的自主查询计算机系统，使其可以从实际需要出发，满足查询者的各种不同需求。

二、问题的假设

1、假设一个地点只有一个相同的站点，我们不考虑一个相同的地点前后几米的位置有

两三个不同的站点的现象。

2、换乘时间根据不同交通工具转换采用不同的平均耗时，不考虑在原地换乘及步行到反方向换乘的时间差异。

三、问题分析

公交网络中乘客出行路径选择的问题，可以表述为在由各种公共交通方式构成的公

交线路网络中，乘客在任意两个给定的站点之间选择一套最优出行线路组合方案的问题。但是影响乘客选择公交线路的因素有很多，如出行时间、费用、换车次数等多种因素的影响。根据出行目的的不同，人们会选择不同的交通工具。步行一般适宜于近距离出行，费用低但舒适性与安全性差。地铁的优势是快速准点，但其服务面积较窄，只对其沿线产生作用，而公共交通的覆盖面则较广。出行时间短且费用低的交通方式的交通需求必然较大，相应的其换乘量较大。针对上述问题，我们以出行时间、费用作为两个不同的标准，其标准制定规则如下：

⑴、当时间相同时，以费用最少为最佳路线； ⑵、当费用相同时，以时间最少为最佳路线； 以满足乘客在不同的需求下对最优路径的选择。

从所给的公汽线路信息的数据中可知，公汽线路分三种情况：⑴下行线和上行线为同一路线，即他们往返经过相同的站点；⑵环行线，即公汽沿一环行路线行驶，每一站对于公汽来说都是起始站，同时也是终点站；⑶上行线跟下行线分开，即公汽往返经过的站点不完全相同。根据上述情况，为了在算法的实现过程中便于对数据的录入与处理，我们将所给数据导入Excel中进行如下预处理：

①将以S、S0、S00、S000开头的数据全部用空格替换，使其变成自然数的形式，这样做的原因是为了省去字符串的读写操作节省空间；

②将所有路线的数据都按往和返两种情况处理，为了区别情况⑴、⑶和⑵，在表格中我们分别以正向和反向表示，并将情况⑶记以环行标志； ③对于不同的计价方式，我们作如下标记：

2

1,单一票制1元时； 0，分段计价时；在Excel中每一条路线的开头按照上述标准对路线的计价进行标记； ④以-2作为每一条线路每往、返一次结束时的标记。

综上所述，我们逐步建模求解，攻克难题，试对公汽线路的选择体系做初步探讨，下面将具体阐述。

四、符号说明

vi--------编号为i的公汽站点，1i3957uj； ；

--------编号为j的地铁站点，1j39a---------公汽换乘公汽平均耗时；

b----------地铁换乘地铁平均耗时； ----------公汽换乘地铁平均耗时； ----------相邻公汽站平均行驶时间；

c----------地铁换乘公汽平均耗时；

dkl----------相邻地铁站平均行驶时间；

n0---------地铁票价；

m0---------单一票价时的公汽票价； mn---------分段计价时的公汽票价（其中n为乘车所经过的站数，即

mn1,0n202,21n403,40n

stat ---------二维数组存放站点 S0 ---------起始站点 S1 ---------结束站点

五、模型、算法的建立及结果分析

5.1.问题一 对任意两公汽站点之间的线路选择

5.1.1 算法的提出及建立

对于该问题，一种可能的方法就是枚举出所有可行路径，并计算出每条路径的长

3

度，然后选择最短的一条。那么我们很容易看到，即使不考虑包含回路的路径，依然存在数以百万计的行车路线，而其中绝大多数是不值得考虑的。

另一种可能的方法是根据大多数人对乘车换乘的厌烦心理，可将模型简化为最多换乘两次，于是有将其划分为分别搜索直达线路，一次换乘和两次换乘： 1、 直达线路：首先根据两个站点(始点和终点)名获取两个站点各自的公交路线，然后进

行查询，是否有在一条线路中出现，如果在就可以直接到达，如果不存在，则进行换乘的算法。

2、 一次换乘：首先根据两个站点名获取两个站点各自的公交线路， 然后搜寻两个站点

通过直达方式各自能够到达的站点集合，最后他们的交集就是我们所需要的换乘站点。再进一步进行优化筛选！

3、 二次换乘：首先根据两个站点名获取两个站点各自的公交线路，其中心思想是：站

点1能够通过直达到达的所有站点集合A，站点2能够通过直达到达的所有站点集合B，A和B之间有直达的线路。

但针对上述算法进行求解时，由于所给数据数量庞大，采用循环条件进行编程处理时，程序执行需要大量的时间，不具有实际的应用性。再者，对于3900多公汽站点520条公交路线，存在两个站点经过两次换乘不能到达的情况。所以，该算法不具有一般性。

因此，要解决该问题，我们必须做更深一步的研究。我们不妨将各个站点看成结点，而两个站点之间有公交线路相连我们就认为这两个结点之间有线连接。我们用图来描述公交线路、各站点以及它们之间的关系，可以根据图的性质的分析来研究和揭示各种系统的特征，提供对系统决策的科学依据。在本题中，车站代表的是一个二维数组的点，即某一个线路中的一站。为此，我们将每一条线路的车站，包括公汽站和地铁站，都可以看作是图的顶点，如果某车站有n条线路通过，则我们将站点分成n个顶点。对于线路选择问题，我们可以将其转化为求赋权图最短路问题，根据查询者的不同需要，只要适当调整所赋的权值，即可以给出用时最少，或费用最少的最佳线路选择。

定义1 称G(V,E)是一个图，如果 （1）V是一个非空有限集合，

（2）E是V中元素的无序对所组成的有限集合。 并把V的元素叫做图的顶点，E的元素叫做图的边。

图G(V,E)常简记为图G，并以V(G)或V，E(G)或E分别表示G的顶点集，边集。

|E(G)|或|E|设S是一个集合，则以|S|表示集S的基数或元素个数。于是|V(G)|或|V|，

分别表示图G的顶点数，边数。由定义，边是顶点的无序对，若边e是顶点u和v的无

序对，则记e(u,v)或e(u,v)，其中称u，v是e的端点。

定义2 若图G的每一条边e都对应一个实数w(e)，则称w(e)为边e的权，并称图G为附权图。图G的子图H的权记为w(H)，定义为设G是赋权图且w(e)0，eE(G)。若P是最小的

vivjw(H){w(e)|eE(H)}

在实际问题中，权w(e)可表示距离，时间，容量，费用，利润，成本，效益，亏损等等。

vivj路，则路P的权w(e)成为P的长。长

vvj路成为最短路，

vivj最短路的长称为顶点i到的距离，记为

d(vi,vj)。

j如果没有i通道，则规定最短路和距离。

vvd(vi,vj)。我们的问题是如何求指定顶点到其余顶点的

4

为方便，以i表顶点vi，并设V(G){0,1,,n1}。若(i,j)E(G)则w(i,j)表示边(i,j)的

0jj权。若(i,j)E(G)，规定w(i,j)。设0j表示0最短路，并记0j。 最短路有一个重要而明显的性质：最短路是一条路，且最短路的任一段也是最短路。假

Pvvdw(P)设在

vivj最短路中只取一条，对有向图，有已知定理，从v0到其余顶点的最短路将构

成一棵以v0为树根的外向树。由此得到启示，求指定顶点v0到其余顶点的最短路，可采用树生长的过程。实现这一过程的方法是E.W.Dijkstra在1959年提出来的，一般称为Dijkstra算法。

设已经生长到树的顶点集为S，并设SV(G)\\S。在开始时，S{0}，并给图的顶点如下标号： l(0)0，l(j)w(0,j),jS.

这样的标号自然满足两个条件：l(i)d0i,iS （1）

l(j)min{l(i)w(i,j)|iS},jS （2） 为继续树的生长，需用到如下引理。

引理1. 设S为已经生长到树的顶点集，且顶点的标号满足式（1）与（2）。令 l(k)min{l(j)|jS}P，则l(k)d0k，且在0k上只有kS，其余顶点都在S中。

由引理1，若将k生长到S中，则式（1）满足。为了满足式（2），对jS\\{k}，令

l(j)min{l(j),l(k)w(k,j)} （3）

事实上，把（2）式代入(3)式，有l(j)min{l(i)w(i,j)|iS{k}}， 至此解决了求路是

v0到其余顶点的距离的问题。下面考虑求出最短路的问题，若最短则称

vjv0vjP0iv0vjvi,是i的紧前顶点。因此只要在树生长到S的顶点的紧前顶点，

vv则可逆向追踪求出最短路，我们用t(i)j表示顶点i的紧前顶点也不变；若顶点j由式

（3）得到新标号l(j)l(k)w(k,j)，则改变点j的紧前顶点为顶点k，即令t(j)k。

值得注意的是，上述算法为一元形式表示，而我们的问题中，对于所有的n个定点，采用此形式非常难以操作。这里我们适当推广其至一二维有向图，使得最终的算法实现的以大量简化。具体算法步骤如下（仅给出重要的步骤，详细程序可见附件）：

1.定义与赋值：

(1) stat(line_n,0:stat_max): stat(i,j)为第i条线路的第j站所对应的站名。其中line_n为所有线路的总和，也就是包括了实际中同一条线路的重复，stat_max为一足够大整数。将经处理后的原始数据读入，其中stat(line_n,0)纪录是否为单一票价。未被复值的元素全部置零。

(2) remove(line_n,stat_max):纪录每一次循环中去除的生长点的位置.

(3) 求出对应起始点S0的任意一座标（line_0,st_0）。(仅需一个即可，下面的算法会自适应其他可能坐标并求最短路)

(4)loss(line_n,stat_max):纪录总损失（费用或时间等）,

prep1(line_n,stat_max)，prep2(line_n,stat_max): 纪录紧前顶点。 (5)road_line,road_stat两数组分别记录路径的横纵坐标。

2．给出赋权函数w(S0,k1,k2,k3,k4)，其中(k1,k2)，(k3,k4)分别对应有向图中的

5

前后顶点。

下面以仅考虑公共汽车和运行时间的情况举例说明如何定义w，对于其他各种更复杂的情况详见附件程序。

若stat(k1,k2)等于stat(k3,k4) 则:

若stat(k1,k2)=S0 则 w=0；否则 w=a;

若stat(k1,k2)不等于stat(k3,k4) 则：

若k1为环行线，那么若(k1等于k3且k4=k2+1)或(k1等于k3；stat(k1,k2+1)=0;k4=2)成立时，w=k;否则 w=无穷大; 若k1不是环行线，那么若那么若(k1等于k3且k4=k2+1) 成立时，w=k;否则 w=无穷大;

3. 迭代求出紧前顶点。

(1) remove=0; loss(line_0,st_0)=0;

loss(i,j)=w(S0, line_0,st_0,i,j) 对所有的remove(i,j)不为零的i,j;

(2) loss(temp_mini,temp_minj)=min{ loss(i,j)| remove(i,j)不等于零}，

loss(temp_mini,temp_minj)为无穷，停止； 否则令remove(temp_mini,temp_minj)=0；

(3) 若所有remove中的元素全为零，停止；否则，对每个remove(i,j)不为零的i,j，若loss(i,j)>loss(temp_mini,temp_minj)+w(S0, temp_mini,temp_minj,i,j),则

loss(i,j)=loss(temp_mini,temp_minj)+w(S0,temp_mini,temp_minj,i,j)

prep1(i,j)= temp_mini prep2(i,j)= temp_minj

若stat(i,j)=S1 则停止，否则回至第二步； 4. 由prep数组逆向寻踪求出最佳路径。 road_line(1)=i road_stat(1)=j

road_line(m)= prep1(road_line(m-1),road_stat(m-1)) road_stat(m)= prep2(road_line(m-1),road_stat(m-1))

最后逆向输出（road_line(m), road_stat(m)）即得最小损失路径。再根据这些 坐标所对应的线路列出实际的乘车路线。

算法复杂度分析及优化：整个外层循环最多为n0（stat数组的不为零的元素个数的总 和），因为若找到了最短路即跳出， 而不需要将所有n0次运算完毕。若想要得到由S0至其他任意站点的最短路，则可运行全部外层n0次循环。 每一次外层循环，最多只需要O(n0)次运算，但事实上，受益于我们前面的将同一站点分割为对应不同线路的多个顶点的处理方法，在步骤(3)中对于给定的（temp_mini,temp_minj），仅有最多一个w(S0,temp_mini,temp_minj,i,j)不为无穷，则适当优化程序可使得每一外层循环最多需要O(stat_max)次运算，因此整个算法可以O(n0* stat_max)运算完成，而最多也仅需要O(n0*n0)次运算。

该算法的优势不仅在于其速度及确定性上，而且体现在其广泛性和一般适用性。 无论是考虑仅公共汽车还是地铁，步行同时考虑，无论是仅考虑时间指标，费用指标还是其他综合指标，都可通过适当的简便的调整得以实现。举例来说，若公共汽车，地铁，步行同时考虑，则仅需要增加线路及每站所对应的顶点即可实现；而若考虑其他各种衡量指标最佳路线的指标，仅需对权函数w进行适当的调整即可。事实上，通过一些改变，此算法还可以实现通常人们所采用的以最多几次换乘为效果度量的方法。具体举例来

6

说，若考虑最多两次换乘中的最短时间路线，则仅需在上述算法中添加一新的指标变量记录换乘次数，然后类似于上面的算法的步骤2，建立以时间为度量的权函数w，添加新的判断准则：若换乘次数已等于2，置当前两个顶点的之间的权为无穷，完成循环后即可得到最多两次换乘的最小时间路线。其他情况以此类推可得。

5.1.2 算法的结果分析

在仅考虑公汽路线的情况下，以时间最短和所需费用最少为标准，所求得的路线如下表：

路线 S3359 至S1828 具体路线，即从起始点通过换车到达终点。 L485反(12)费用 元 ３ S1784 时间 分钟 S3359S1828 L484下(5)S3727S3359L167下（1）L484下（5）S3727L485反（12）S17843 S1828 S1557至S0481 S1557L167下（1）L084下（12）S1919L1下（3）4 S318699 S090S0481 S1557L091上（11）L239反（2） S0481 L084下（12）S1919L1下（3）3 S3186106  S0971至S0971L460反（17）S0485 L013下（16）S2517L290反（13）S21593 103 S0485 S0971L469上（2）S0485 L013下（16）S2517L290反（13）S21593 103  S0008至S0008L469上（2）L198上（3）S3766L476下（4）5 S2085S052559 S0073 L103上（2）L017上（3）S0604S0073 7

L328上（1）

S0008L198上（3）S3766L290反（13）3 S218467 S0073 S0148至S0148L345上（3）S3351L308上（15）S3604L417下（1）L081下（2）4 S2361102 S0485 S0148L156上（11）S0485 S0036L308上（14）L156上（17）3 S3351106 S0485 S0087至S0087L417下（1）S3676 L021下（1）S0088L231正（10）S04273 46 S3676 L097上（1）S3496S0087

L4上（11）L209下（9）S3676 2 65 表1

对表1的评价说明如下：

Ⅰ、 对每一组起始至终到站，上行路径数据为以时间最短为标准所走路线，下行数据为以时间最少同时考虑换乘次数尽量少的前提下所走路线（通过改变算法中的权数来实现）。通过在两条标准下所得路线各自所需时间和各自的花费的对比，我们可以得出：在此算法下，对于一些起始至终到站点来说，存在一路线能够同时实现时间和费用都最省的情况。

Ⅱ、对于行走路线的注释：其中以S开头的（如S1557）为公汽站站点；以L开头

）为题目提供的已有路线；“上、下”分别表示沿上、下行的路的（如线行走，而“正、反”则表示下行线是上行线的原路返回的路线和环行路线的往、返路

线；括号中的数字（如（12））表示从它前面站点开始沿指定路线走过的站数；而S3359S3727整体表示在路线L484所经过的站点S3359处乘车，沿他的下行线过5个站点（即坐5站车）到达站点S3727处下车，再转乘其他路线的车。于是，S3359S1828的以时间最少为标准的行走路线可以描述为：从公汽站点S3359上车，沿路线L484的下行路线依次走过公汽站点S3359、S2023、S2027、S1746、S3697、S3727后，在站点 S3727 处下车，然后转乘路线L485反向的车走过站点S3727、S393、S391、S3674、S1522、S1520、S2992、S903、S1768、S955、S480、S2703、S1784后，在站点S1784处转乘路线L167下行路线的车

8

L484下（5）L084下（12）路过站点S1784 即到达目的地S1828。于是，在时间最短的情况下，从站点S3359到站点S1828用时分钟，花费3元，共换乘了两次车。

5.2 同时考虑公汽和地铁后的线路选择

5.2.1 算法的建立

若将地铁考虑进来，对于我们所构造的有向赋权图模型来说，仅需要将5.1节中的公共汽车的数组增加四行（对应两条线路的正反两种形式路线），然后修改权函数的定义方式，增加对乘地铁方式的描述，然后重复前述算法即可得到最佳路径。在此不再赘述。

5.2.2 结果分析

在同时考虑公汽和地铁路线的情况下，以时间最短和所需费用最少为标准，所求得的路线如下表：

在同时考虑公汽和地铁路线的情况下，以时间最短和所需费用最少为标准，所求得的路线如下表：

路线 S3359 至S1828 S3359(D21) 具体路线，即从起始点通过换车到达终点。 费时间 用 元 分钟 L201上（3）T2反（6）L324下（2）S2027D37(S1961) S0609 7 62 S1671L428上（2）S1828 S3359L041正（1）L484下（5）S3727L485反（12）S1784 3 S1828 S1557至S0481 S1557L167下（1）L084下（12）S1919L239反（2）L1下（3）S3186 4 99 S0903S0481 S1557L091上（11） S0481 L084下（12）S1919L1下（3） S31863 106  S0971至S0971L460反（17）S3351L094上（6）S0567(D01)D15(S2534)6 95 S0485 T1正（14） S0485 L156上（7）L417下（1） 9

S0971L094上（6）S0567(D01)S0466(D21)T1正（20）5 96  S0485 S0008至S0008L051上（5）L200上（6）S2534(D15)T1反（3）D12 5 53.5 S0073 103上（2）D25(S0525)LS0073 T2反（2）S0008L200上（6）S2534(D15)T1反（3）D125 59 L103上（3）S3580(D24)S0073 T2反（3） S0148至S0148S1487(D02)S3351S0485 S0148L165上（7）L024反（4）T1正（13）D15(S2534)6 86.5 L417下（1）S0485 L024反（4）S1487(D02)T1正（19）S0466(D21)5 87.5  S0485 L051上（5） S0087至S3676(D36) S0087(D27)T2反（8）3 20 S3676 S3676(D36) S0087(D27)T2反（8）3 20 表2 对表2的评价说明如下：

Ⅰ、同时考虑公汽与地铁路线且时间要求最短时，其表格的介绍同上所述。所不同的是，在该表格的路线中包含了地铁的路线和地铁站点，现说明如下（注：该表格中其他部分说明同上表，在这里不再赘述）：符号

Di表示地铁站点，T1、T2分别表示地铁的

两条路线，其中T1为下行线是上行线的原路返回路线，T2为环行路线。

D37(S1961)部分的说明：由地铁线T2换乘公汽信息表 Ⅱ、对S0609 (D21)可知：公汽站点S0609对应地铁站点D12，公汽站点S1961对应地铁站点D37。上

式部分的乘车路线为：从S0609下公汽，在地铁站D12转乘地铁，沿地铁的T2的反向路线走6站地，然后在地铁站D37下车，再去公汽站S1961转乘公汽。

Ⅲ、通过改变算法中的权数，我们又可得到多条可行路线，综合考虑使得乘车费用尽可能少、转乘次数也尽可能少的情况下，我们选出了费用相对较少的路线，即对每一组起始至终到站的第二条路线。

Ⅳ、该种情况与仅考虑公汽时相比，除了第二组路线的时间相同之外，其他组均比仅考虑公汽时消耗时间 要少。这充分说明了地铁的建立确实在公汽的基础上更加便利了人们的出行。

10

T2反（6）

5.3 考虑步行时间

由前所述，由于我们的图模型非常容易推广，可以很容易的处理这个问题。具体模型描述如下:

若将步行时间考虑进来，对于我们所构造的有向赋权图模型来说，仅需要将5.2节中的公共汽车和地铁同时考虑的模型进一步推广，具体来说，就是将所有已有的站点所对应的顶点个数都增加一个，即可将两个二维数组stat(line_n,0:stat_max)

合并在一起。然后修改权函数的定义方式，增加对步行方式的描述，也就是说，从步行出发的点可以达到相邻顶点（步行，权可根据给定的不通站之间的步行时间而定），也可在当前顶点“换乘”其他方式（权为零），这样最终依然是一有向赋权图，仅仅是顶点数为原来的一倍，在给定适当优化目标函数后，我们同样重复前述算法即可得到最佳路径。

六、模型的评价与改进。

我们将同一站点分割为对应不同线路的多个顶点，得到一有向图。根据所给的不同费用和时间数据，可根据所要优化的目标对不同顶点之间赋权，这样最终构成了一有向赋权图。对于任意给定的目标，即时间最短，费用最少，换乘约束，或综合考虑时间，费用和换乘，我们仅需要适当的修改赋权函数即可。适当推广著名的Dijkstra算法至二维表示情形，我们可以方便快速的求得所要路线。该方法具有如下优点：计算量小，最多需要O(n2)阶运算即可完成，适当优化可使得计算量降至O(nlog(n))；具有一般性和易用性，进行少量修改，就能够根据任意所指定的优化目标进行优化，比如我们可利用该算法达到前面所述常用的约束换乘次数的目标；最优性，尽管满足某一目标的路线不一定唯一，但根据这种方法我们求出的路线必定能够最优化该目标。

今后的改进目标是如何将时间，费用和换乘等多种因素更好地综合起来，给出某个 具体的函数指标，即由多个变量构成的权函数，这样最终可得令人满意的最佳路线。

参考文献：

[1]费培之，《图和网络及其应用》，四川：四川大学出版社，1996年。 [2]宋来钟等，《数学建模与实验》，北京：科学出版社，2005年。 [3]薛毅，《数学建模基础》，北京：北京工业大学出版社，2004年。 [4]孙麟平，《运筹学》，北京：科学出版社，2005年。 [5]卢向南，《应用运筹学》，浙江：浙江大学出版社，2005年。

11