文档介绍：公交转车问题
1
公交转车问题
针对市场需求，某公司准备研制开发一个解决北京市公交线路选择问题的自主查询计算机系统。
为了设计这样一个系统，其核心是线路选择的模型与算法，应该从实际情况出发考虑，满足查60
D37：S1961，S2817，S0455，S0456
D38：S3262，S0622
D39：S1956，S0289，S0291
9
问题分析
从实际情况考虑，不同的查询者有不同的要求。在数学上体现出目标的不同。
一般可以考虑转车次数、乘车费用、乘车时间这3个目标。
问题可以归结为多目标优化问题。
10
问题分析
如何处理上面的多个目标？
多目标的处理最常用的方法是单目标化，即采用加权平均等方法将多个目标结合形成一个单一的目标。
本问题中，单目标化并不合适，比较适当的方法是对每个目标寻求最佳线路，然后让乘客按照自己的需求进行选择。
11
模型建立
我们先仅考虑公汽线路的情况。
设N表示问题中的公汽站点数,即N=3957,
A0＝(a(i,j,0))N×N
是直达最小站数矩阵，当存在公共汽车从站点直达站点时，表示从直达的最小站数。否则该元素取为+∞。
12
模型建立
令Am＝(a(i,j,m))N×N是m次转乘最小站数矩阵，其元素a(i,j,m)表示m次转车情形下，从Si到Sj的最小站数。
显然
13
最小转车次数模型
对于给定的公汽站点Si与Sj ，最小转车次数模型可以写为
14
最小乘车时间模型
转车次数为m时，从Si到Sj的总时间为
5m+3a(i,j,m),
（转一次车5分钟，每乘一站，用时3分钟）
下面是最小乘车时间模型：
15
最小乘车费用模型
最小乘车费用模型可以写为如下的形式：
该模型是形式上的，对于求解没有实质性的作用。
16
最小转车次数模型求解
对于给定的公汽站点Si与Sj ，只要逐次求出(a(i,j,m))，直到其为有限值即可。
在实际求解时，先根据公汽线路的数据将a(i,j,0)的数据存储在矩阵A0中。
17
最小转车次数模型求解
算法一（逐次查找）
对于给定的i,j,
(1)若a(i,j,0)<+∞,表明转车次数为0,否则转(2);
(2)k从1到N进行搜索,若a(i,k,0)<+∞,a(k,j,0) <+∞,则转车次数为1,否则转(3);
(3) k1, k2从1到N进行搜索,若a(i,k1,0)<+∞, a(k1,k2,0)<+∞, a(k2,j,0) <+∞,则转车次数为2.
18
最小转车次数模型求解
逐次查找算法的复杂度
若只要转一次车,则循环的步数为N;
若要转2次车,循环的步数为N2;
若要转3次车,循环的步数为N3……
由于N=3957, N3 ≈×1010,普通计算机运行时间较长，
若要转4次车，很难承受计算量!
19
最小转车次数模型求解
算法二（存储逐次查找）
(1)若a(i,j,0)<+∞,表明转车次数为0,否则转(2);
(2) 求出矩阵A1＝(a(i,j,1))N×N ,其每个元素通过上面的表达式,,j,有a(i,j,1)<+∞,表明转车次数为1;
类似可以计算多次转车的情况
注:矩阵A0,A1等计算后存储在计算机中,
20
最小转车次数模型求解
存储逐次查找算法的复杂度
矩阵A1的计算:
一共计算N2个元素,每个元素的计算要循环N步,。
优点：
矩阵Am (m>1)的计算工作量与A1一致!
有可能计算转多次车.
21
最小转车次数模型求解
在前面的两个算法中,,对给定的i,满足a(i,k,0)<+∞的k是很少的,我们只要对这些k进行循环.
在实际问题中,任何一个城市中,任何一个公汽站点所能到达的公汽站点只是城市中的一些“线”,相对于整个城市而言,数目是比较少的.
22
最小转车次数模型求解
算法三（有限搜索逐次查找）
给出矩阵B,其第i行记录的是满足a(i,k,0)<+∞的所有的“k”.
将存储逐次查找算法中的k从1到N循环改为正对矩阵B第i行中的“k”进行循环.
23
最小转车次数模型求解
有限搜索逐次查找算法的复杂度
矩阵Am的计算:
一共计算N2个元素,每个元素的计算要循环的步数大大小于N,大约为N/10,计算量约为N3/10.
一般的计算机可以实现.
24
最小转车次数模型求解
对于题目中给出的六组公汽站点,其最小转车次数分别为
(1)S3359→S1828 1
(2)S1557→S0481 2
(3)S0971→S0485 1
(4)S0008→S0073 1