一问题提出.doc

PAGE  PAGE 16 一 ：问题提出 我国人民翘首企盼的第29届奥运会明年8月将在北京举行，届时有大量观众到现场观看奥运比赛，其中大部分人将会乘坐公共交通工具（简称公交，包括公汽、地铁等）出行。这些年来，城市的公交系统有了很大发展，北京市的公交线路已达800条以上，使得公众的出行更加通畅、便利，但同时也面临多条线路的选择问题。针对市场需求，某公司准备研制开发一个解决公交线路选择问题的自主查询计算机系统。 为了设计这样一个系统，其核心是线路选择的模型与算法，应该从实际情况出发考虑，满足查询者的各种不同需求。需要解决如下问题： 1、仅考虑公汽线路，给出任意两公汽站点之间线路选择问题的一般数学模型与算法。 2、同时考虑公汽与地铁线路，解决以上问题。 3、假设又知道所有站点之间的步行时间，请你给出任意两站点之间线路选择问题的数学模型。 二 ：基本假设 1：相邻站点间的距离近似相等，公交车的车速匀速适中，故公交车在相邻站点间的行驶时间认为相等。 2：假设1对于地铁也成立。 3：环形路线是双向对发的。 4：若上行和下行站点完全相同，我们认为此路线是双向运行的。 5：除了环行站点首末站点相同外，同一路线一次单向行驶过程中经过的站点互不相同。 三 ：变量及符号说明 相邻公汽站平均行驶时间(包括停站时间)： t1=3分钟 相邻地铁站平均行驶时间(包括停站时间)： t2=2.5分钟 公汽换乘公汽平均耗时： t3=5分钟(其中步行时间2分钟) 地铁换乘地铁平均耗时： t4=4分钟(其中步行时间2分钟) 地铁换乘公汽平均耗时： t5=7分钟(其中步行时间4分钟) 公汽换乘地铁平均耗时： t6=6分钟(其中步行时间4分钟) 公汽票价：分为单一票价与分段计价两种，标记于线路后；其中： 单一票价为：p1=1元。 分段计价的票价为：0～20站： p1=1元； 21～40站：p2=2元； 40站以上：p3=3元。 地铁票价：p4=3元（无论地铁线路间是否换乘。） 公交路线的连接矩阵: A。 公交路线的饱和连接矩阵: A。 总的路线集合为：L 路线为：L(i),简单记为：i。 换乘i次的可行路线集合：Bi 总的可行路线集合：B 时间函数：T（y） 费用函数：M（y） 四 : 问题分析和模型建立 我们把公交路线和公交路线间的换乘情况考虑成有向图【1】的结构，用有向图的连接矩阵【1】来描述。 我们先考虑所有路线均可双向运行，在此前提下，假定北京共有n条公交线路，可以把n条公交线路抽象为n个顶点，任意两条公交线路之间是否连通取决两者之间有无共同的站点，相应地该两条线路之间的矩阵元素值为1或者0，这样就把城市公交线路系统可以抽象为n*n连接矩阵．可以借用连接矩阵的特性和算法，来解决公交线路换乘问题．【2】 不失一般性，假定有1路、2路、3路、4路这四条公交线路，组成的连接矩阵为： A= 该矩阵表明，1路与2路有共同的停靠站点，1路和2路的各站点间最多经过1次换乘就可到达，1路与3路、4路没有共同的停靠站点，经过1次换乘无法到达．其他依次类推．连接矩阵表示了公交线路系统各公交线路之间的直接连接关系，其特点是对角线上的值为1，且为对称阵． 通过对连接矩阵的计算，可以得到更多的信息．按布尔法则（逻辑法则）进行乘法和加法运算，即 0+0=0， 1+0=1， 1+1=1， 0*0=0， 1*0=0， 1*1=1， 可以得到： A2=A*A=. A2中带“*”的元素表明通过第三条路线（2次换乘）可以实现相应路线的连通。 类似有： A=A*A*A= 我们发现A= A2，表明路线之间的连通状态已经饱和，不会产生新的连通状态，即1路与3路还有2路与3路之间无论经过多少次换乘都不会连通。 一般的，对于n条双向公交路线的连接矩阵A，按布尔法则进行乘法和加法运算，则存在正整数r（rn），使得A A = A。我们称A=为此公交系统的饱和连接矩阵，在A中，若a=1，表明第i路和第j路之间可以连通；若a=0，表明第i路和第j路之间无论经过多少次换乘都不可能连通。 一般的，对于正整数s（s=r）,若有（A）=0而（A）=1，表明第i路和第j路之间最少经过s次换乘可以连通。（（A）表示取矩阵A的第i行第j列的元素。） 可以说上述交通系统的连接矩阵是此问题的核心模型，在连接矩阵的基础上可以给出可行路线的算法。 假设L是所有公交路线构成的集合，若想求出任意出发点x1到任意目的地x2的可行路径。设换乘i次的可行路线集合：Bi（0≤i≤r） 下面给出算法的描述：（