公汽线路的类型是有差别的：
一．按票价信息分为：单一票制和分段计价，两种线路有不同的收费方法。 二．按线路的循环模式分为：单线（分为上下行不一致的Ⅰ型和上下行一致的Ⅱ型两种）、环线（设为Ⅲ型）和按原路返回（设为IV）。
其中可将按原路返回的线路（IV）归为上下行一致的II型（原序作为上行，倒序作为下行），这样就将线路分为两类：单线和环线。
针对问题一：我们将公汽线路1~1040进行编号，把公汽线路信息表做成如下1040?3的结构数组——“公汽线路信息数组”data_1： 公汽线路编号 票价信息 线路信息 分段计价 S0619-S1914-??S0128-S0710 001 分段计价 S0710-S0128??S1914-S0619 002 分段计价 S3748-S2160??-S1968-S0004 003 分段计价 S0004-S1968??S2160-S3748 004 ?? ?? ?? 1037 1038 1039 1040 ?Li??2?????Li????2??分段计价 分段计价 单一票制1元 单一票制1元 S0036-S0203??-S1462-S3414 S3414-S1462??-S0203-S0036 S0600-S2861??-S2645-S1848 S1848-S2645??-S2027-S0600 公汽线路编号对应的公汽线路为： Li%2?0Si
Li%2?0针对问题二：将地铁线路T1分为上下行（原序作为上行，倒序作为下行），这样地铁线路T1为单线，地铁线路T2为环线。将地铁线路T1、T2编号1041~1044存入公汽线路的三维数组中，并作出所有公汽站点和地铁站点的关联矩阵。把公汽—地铁线路信息表做成如下1044?3的结构数组——“公汽—地铁线路信息数组”data_2：
公汽线路编号 票价信息 线路信息 分段计价 S0619-S1914-??S0128-S0710 001 分段计价 S0710-S0128??S1914-S0619 002 分段计价 S3748-S2160??-S1968-S0004 003 分段计价 S0004-S1968??S2160-S3748 004 ?? ?? ?? 1037 1038 1039 1040 1041 1042 1043 1044 分段计价 分段计价 单一票制1元 单一票制1元 单一票制3元 单一票制3元 单一票制3元 / S0036-S0203??-S1462-S3414 S3414-S1462??-S0203-S0036 S0600-S2861??-S2645-S1848 S1848-S2645??-S2027-S0600 D01-D02-D03……-D22-D23 D23-D22-D21……-D02-D01 D24-D25-D26……-D39-D24 /
END 公汽-地铁线路编号对应的公汽-地铁线路为： ?Li??2?????Li????2??Li%2?0Si
Li%2?05.问题一的解答
针对问题一：尽考虑公汽线路，给出任意两公汽站点之间线路选择问题的一般数学模型与算法。 5.1算法的设计
【】
扩散路由算法设计1
设城市的所有公交线路，记为L?(L(1),L(2),...,L(i),...,L(n))其中L(i)表示第i号公交线路的线路名，记为L(i)?(i,ria,...,rij,...,rim)，其中rij表示i路公交车线路上的第j站名称。因此，R?(rij)Route1:A?B?C?D Route2:D?E?F Route3:B?G?H?D
n?m
假设公交存在如下线路(暂只考虑单程)：
?Route1:A?B?C?D???则R??Route2:D?E?F?
?Route3:B?G?H?D???其中每行代表一路公交，任一站的全部后续站为它所能直接到达的站，如图1所示，在连通图中表现为邻结点。路由扩散算法具体的实现是将每一个分组将被发送到除了它进来的那条线路以外的每一条输出线路上。公交网络中可直达的站类似网络中的邻接点，在R中表现为同一行的后继元素。
图一 从A点开始依次可到达的站点
查询从起点X开始，扩散到除了它过来的那个站点以外的每一个站点上，然后判断这些站点中是否包括终点Y，否则再从每个扩散到达的站点继续扩散，逐步扩展以X为基点的网络，一直找到Y为止。扩散深度越大，运算也越复杂，因此深度一般不超过4，即换乘3次。而现实中如果一个城市的公交足够发达，线
路设置较合理的话，极少有换乘超过3次的情况。
很显然，扩散法将会产生大量的重复分组，实际上，需要采取一种办法来抑制扩散过程，否则将有大量无效重复的运算。选择性扩散是很重要的，在换乘时，问题很突出的表现出来。假设线路Routel，Route2和Route3如上，且其它任何线路均不经过C地。考察从B地出发去往F地，易知，需要换乘一次。由于FlB={C，D，G，H)(其中FlB的l表示扩散深度，对应乘车的次数，B为扩散点)。因此C，D，G，H均可能成为换乘地点，但经过C的公交线路集Rc={Routel}，而经过B的线路集RB={Route1，Route3}，Rc?RB??，即换乘无意义。因此扩散只进入D，G和H，到C后应给予抑制，防止进入下一层的扩散。最后，线路集合中经过结点数最少、总权值最小的路径，即X到Y的最佳路径。
算法实现：
Step1:确定起始站X(X?Li?)与终点站Y（Y?Lj?），并将其输入系统中; Step2:由X在Li中开始扩散，逐个查找其对应元素Li?所在行的后续元素：当
Li??Lj?，i=j则Li?为Li线路上的直达站，集合记为F1X={x1(Dx1), x2(Dx2),
x3(Dx3)….}(其中F1X的1为扩散深度，X为扩散点，Dx1为X到x1间隔站数，xm多次存在，只保留Dxm值的最小者)。
Step3:Y是否属于集合F1X中？如果是，则说明X到Y可以直达，不需换乘，直接转到Step6步执行；否则，执行Step4。
Step4：选择集合F1X换乘有意义的站，逐个作为顶点在扩散，访问它们除X以外每个元素。
Step5:Y是否属于集合F2X中？如果是，说明X到Y乘两次（换一次车）可以到达，直接转到Step6步执行；否则，进行进一步扩散到深度为3的顶点（换二次车）。
Step6：将满足条件的线路（可能不止一种）优化并输出结果，结束运算。
算法的具体流程图如下（图5.1）：
图5.1 算法流程图
5.2模型一的建立
为了满足不同查询者的各种不同需求，我们分别以总费用M最小、总耗费时间
T最少以及总换车次数N最少为目标建立最优化模型。
g（1） 以总费用M最少为最优路线的模型：
N?1 目标函数为： minM??Pi?1i
Pi?1,w?1orw?2,i?2s???2,w?2,2?1si?40 ?3,w?2,?41si?（2） 以总耗费时间Tg最少为最优路线的模型： 总时间Tg等于公汽行驶时间与公汽换乘时间之和 目标函数为：minTN?1g?3??i?1si?5?N
（3） 以总换车次数N最少为最优路线的模型： 目标函数为：min
N?Nss
5.2模型一的求解
根据以上算法和前面建立的模型一（不考虑地铁站换乘），用matlab进行编程（程序见附录一）就可以得出不同目标下的最优路线。 （1）以耗时最少为目标的最优路线
起始站S3359到终到站S1828耗时最少为101min； 起始站S1557到终到站S0481耗时最少为106min； 起始站S0971到终到站S0485耗时最少为128min； 起始站S0008到终到站S0073耗时最少为83min； （注：其耗时最少的路线有13条）
起始站S0148到终到站S0485耗时最少为106min； （注：其耗时最少的路线有3条）
起始站S0087到终到站S3676耗时最少为65min； 其耗时最少的最优路线如表5.1所示。 起始站到终点站 最佳线路 车费 时间换车/元 /min 次数 S3359?S1828 3 101 1 L436dL167dS3359????S1784????S1828 S1557?S0481 S0971?S0485 S0008?S0073 S0148?S0485 S0971????S2184????S485 S0008????S2083????S0073 S0087????S3496????S3676 S1557????S1919????S3186????S0481L460uL363uL189dL013dL417d3 3 2 3 106 128 83 106 2 1 1 2 L463dL057uL454uL209d