2007年全国生数学建模竞赛优秀及题目一等奖cumcm

1、摘线路查询系统的线路选择的模型与算法 可关键字：邻接关系矩阵 满意摘线路查询系统的线路选择的模型与算法 可关键字：邻接关系矩阵 满意度函数 节点带权网目录1问题重2问题分问题一的分问题二的分问题三的分目录1问题重2问题分问题一的分问题二的分问题三的分3模型假问题一的假问题二的假问题三的假和符号说.符号说45问题一的求模型一的建模型求基于邻接矩阵的换乘搜索算法-准则 1，2，3 的求基于广度优先换乘搜索算法-准则 4 的求结果分问题二的求对地铁站附近的公汽站的处模型二：基于出行时间最短的线路搜索模模型三：节点带权的网络模6模型求结果分7问题三的求8模型评优缺9算法的稳定性分参考文-11 问题重2

2、9 8 场800 条以上，某公司准备研制开发一个解决1 (5)、(6)、1 问题重29 8 场800 条以上，某公司准备研制开发一个解决1 (5)、(6)、22 问题分2.1 问题一的分。考虑换一次车的方案；如果没有换一次车的方案则又要考虑换两次车到达 B 的乘车方-22.2 问题二的分2.3 问题三的分3 模型假3.1 问题一的假假设城市系统的线路信息都是已知的，即如果将每个站抽象为一2.2 问题二的分2.3 问题三的分3 模型假3.1 问题一的假假设城市系统的线路信息都是已知的，即如果将每个站抽象为一2225（23.2 问题二的假547钟、611问题三的假-33) 仅考虑地铁和公汽的换乘时

3、间，其他方式如：步行换乘、步行换乘地铁等所花4和符号说4.2符号说ij间有直达线路时d0为从ij3) 仅考虑地铁和公汽的换乘时间，其他方式如：步行换乘、步行换乘地铁等所花4和符号说4.2符号说ij间有直达线路时d0为从ij行驶时间，否则d0 (d(K)经k；ns(0) 1表示站点ijs(0) 0站点ij (s(K)经k；n可直达站点的线路序列矩阵即站点i和j间有直达线路时为过i、j的线路序号，否则 0-4 (l(K)经k；nn5 问题一的求5.1 模型一的建的研究来确定模型的优化 (l(K)经k；nn5 问题一的求5.1 模型一的建的研究来确定模型的优化目标和约束条件。根据杨新苗1 等K 、出

4、行费用C 、出行距离T 。先考虑目标函数1)minK；为了避免换乘的麻烦，部分乘客（如新的外来）minC；对于时间比较充裕或收入不高的乘客，则会选择出行费minT；有些乘客赶时间，不会考虑换乘次数和费用的多少，将再考虑约束条件1)邻接关系矩阵S (sij )nn 2)根据假设用两站之间的平均行驶时间来衡量站点距离，则 该城市共有520条公汽线路（包括上下行和环形）和2条地铁线路（环形L的所有元素4)站点i经kj-5n s(k1) 0(s(k(k s(k1) 的意义是站点i 经k 次换乘n s(k1) 0(s(k(k s(k1) 的意义是站点i 经k 次换乘到达 j 站点的换乘方式有s(k1)

5、种5.2 模型求乘客类选择最优路线的优先对应准K 出行费用C 出行距离T出行费用CK 出行距离T出行距离T K 出行费用CK C T准则KCTK最小的线路，如果不止一条，则选择C最少的线路，仍然不止一条则选择T 最短的线路。其他与此类5.2.1 基于邻接矩阵的换乘搜索算准则1，2，3的求此算法以矩阵为基本数据结构。在邻接关系矩阵S D 是根据S（K）以准则1为例，算法具体步骤如下Step1根据题目所给数据并分析网络的拓扑结构，初始化S LDK 0K的上界supK K为整数 KABStep2 :查网络的S、L和D矩阵，计算出可直达关系矩阵S（0）、可直达的站点离矩阵和可直达站点的线路序列矩阵。若

6、入可行线路集合Z K K 1；转到Step5Step3K K ，如果不满足，转到Step5。计算S S(0) S(0s 表示站点i和j -6S(0) Ss Ssn 1则站点A,B间经一次转乘有可达线路，根据s(1) 若ss(0) s 0的中转站点hS(0) Ss Ssn 1则站点A,B间经一次转乘有可达线路，根据s(1) 若ss(0) s 0的中转站点hL入可行线路集合Z K K 1；转到Step5Step4K K ，如果不满足，转到Step5。按照Step3K入Z ，转到Step5，否则转到Step4Step5根据票价信息，计算Z 中各条线路的费用C，C最小的为最优线路，如果满足最小的线路不

7、止一条，则选取线路距离T K 2， 2，3(1) S3359下 13准则S3359下 13准则S3359下 13准则(2)S1557下 S1919下S1557下 S1919下准则23 23准则 23准则-7(3) S0971下 准则13S0971下 准则13S0971下 13准则(4) 下上S准则12S可以为 S0400 S2633 下(3) S0971下 准则13S0971下 准则13S0971下 13准则(4) 下上S准则12S可以为 S0400 S2633 下上S准则12S可以为 S2683 S0291 S3614 下上S12准则S为S2263S3917(5)S0148上 S0036上S

8、可以S221S333S3351S23准则S0148上 S0036上S可以S221S333S3351S准则23S0148上 S0036上S可以S221S333S3351S准则23(6) 上12准则准则 上12准则 上12说明：时间和费用min 和yuan -8基于广度优先目标函数换乘搜索算准则4的求用U(K,iK )(K supK K为整数，iK为整数)表示第K 次换乘的iK基于广度优先目标函数换乘搜索算准则4的求用U(K,iK )(K supK K为整数，iK为整数)表示第K 次换乘的iK 条可行线的集合。当综合考虑这三个指标时，面对iK K是指标TK F (C,T,K一个更实用的目标函数先将

9、各指标抽象成同质1) 出行费用指标标准化根据初始模型，出行费用指标是越小目标越优，应用模糊数学3 中隶属度的定义1，max(Ci )Cmax(C )min(C 2) 出行距离指标标准化max(Ti )Tmax(T )min(T K与C、T KK 1F (w1Cw2TK 足w1 w2 1KF K基于广度优先换乘搜索算Step1ABK的上界supK K为整数 KStep2网络的邻接关系矩阵SDL为X(i)(i A线Yjj b,b为整数-91Step3 x(i) y( j，将满足条件的存入直达线路集合Z0X(i即Y( j为从站点A到站点B的直达线路，如图1所示K K 1Step3 x(i) y( j

10、，将满足条件的存入直达线路集合Z0X(i即Y( j为从站点A到站点B的直达线路，如图1所示K K 1Step4K K ，如果不成立，停止；否则查询SDLX(i交站点存换乘矩阵O(i,u)(u 线路Y( j站点存换乘矩阵P( j,v)(v f, f为整数Step5搜索O(iuP( jv，判断是否有o(iu) p( jv1，则站点o(iupjv为从站点A到站点B路集合Z1X(i),Y( j为换乘一次的最优路线，如图2K K 1Step6K supK K为整数，如果不成立，停止；否则搜索SLD为R(k)(k 1,2,3, g为整数)，点o(iu) R(k) G(kh)(h 换乘矩阵O(iu) Ste

11、p7p( jv) g(khZ2Z21g(kh) p( jv为从站点A到站点BX(iR(k),Y( j为换乘二次的最优路线，如图3K K 1Step8K K ，图1.点A,B直达的搜索线-10o(1,2) o(2,2) 图2. 换乘1次时站点A,B的搜索线g(2,3) g图3. 换乘2次时站o(1,2) o(2,2) 图2. 换乘1次时站点A,B的搜索线g(2,3) g图3. 换乘2次时站点A,B的搜索线K 2K，出行费用C和出行距离T (1) W1 W2 S3359下 13W1 W2 S3359下 13W1 W2 S3359下 13-11(2) W1 W2 23 (2) W1 W2 23 W1

12、 W2 23S1557下 S1919下S1557下 S1919下W1 12W2 W1 W2 S0971下 13W1 W2 S0971下 13W1 W2 S0971下 13 S 12W2 S可以为 S0400 S2633 W1 W2 S12S可以为 S0400 S2633 SW1 W2 12S可以为 S0400 S2633 -12(5) S0148上 S0036上S可以,S221S333S3351W1 W2 S23S0148上 S0036上S可以(5) S0148上 S0036上S可以,S221S333S3351W1 W2 S23S0148上 S0036上S可以,S221S333S3351 S2

13、3S0148上 S0036上S可以,S221S333S3351S 23W1 W2 上12W1 W2 上12W1 W2 上125.3 结果分转乘才能到达目的地而6 问题二的求6.1 对地铁站附近的公汽站的处汽。所以，A、B11-13图4. 同一地铁对应的任意两站点的换乘情的6.1 模型二：基于出行时间最短的线路搜索模2.2（即出行距离T 改进的基于广图4. 同一地铁对应的任意两站点的换乘情的6.1 模型二：基于出行时间最短的线路搜索模2.2（即出行距离T 改进的基于广度优先换乘搜索算Dk(k 为在地铁站k Step2ADk(k 1.39为X(i)(i a,a 交为Y(j)(j b,b为整数Ste

14、p3 Step4Step5搜索O(iu) P( jv，判断是否有o(iu) p( jv，如果存在，则站点o(iup( jv为从站点A到站点B的一次换乘站点；再判断是否有o(iup( jvDp(p1.39且p kp mDp为从站点A到站点BX(i),Y( j-14入一次转乘线路集合Z1。若存在o(iuDk(k 1.39Dk素添加到O(iu) 线路Y( jPjv)(v 1,2,3f, f为整数入一次转乘线路集合Z1。若存在o(iuDk(k 1.39Dk素添加到O(iu) 线路Y( jPjv)(v 1,2,3f, f为整数pjvDk(k 1.39P( jvK K 1Step6K supK K为整数，

15、如果不成立，停止；否则搜索SLD为R(k)(k 1,2,3, g为整数)，点o(iu) R(k) G(kh)(h 换乘矩阵O(iu) Step7p( jv) g(kh，如果有满足条件的线路且该线路没有在Z1g(kh) p( jv为从站点A到站点BX(iR(k),Y( j为换乘二次的最优路线；再判断是否有一对o(iup( jvDpDq 中，如果有满足条件的线路且该线路没有在Z1中出现，则DpDq为从站点A到站点B乘线路集合Z2中， K K 1Step8仅以出行时间（出行距离）(1) 换乘次数 时间S3359下S1784 S3359下 13(2) S1557下 S1919下S1557下 S1919

16、下23-15换乘次数 时间S0971下 13 SS可以为 S0400 S2633 下换乘次数 时间S0971下 13 SS可以为 S0400 S2633 下上S，2S可以为 S2683 S0291 下上SSS2263, S3917, 换乘次数 时间S0148下 D02 上S0466下 S0148下 S1487D02 上D21 S0464 下 S048525 146.2 模型三：节点带权的网络模6.3.1模型的建通网络图45 G(V , E) ，由于每一上下行或环线组成，故G(VE铁和其附近站点合并成一个节点，所有节点用集合V v1,v2,.,vn；-16E vi vj vi vj V表示站点v

17、i 和vj vi 和vE vi vj vi vj V表示站点vi 和vj vi 和vj E vivjk,lk 1,2分别表地铁;l为线f (vi vj k，可以表示为两顶点间距离，或者途中所经过的时间，或者交设起始站点为vS ，目地站点为vT ，交通图G(VEf (vi ,v j , k f图5. 同时考虑公汽和地铁线路的网络示意图（仅标出单向站的平均行使时间3min2.5minif k if k ,k)f (v ,2.5入边是公汽线路，出边是公汽线路（在同一站换乘入边是公汽线路，出边是公汽线路（在地铁站换乘-17ei入 公汽线路，ei出为公汽线路（在同一公汽车站换乘5公汽线路，e 为公汽线路

18、（在同地铁站换乘iiei入 地铁线路，ei出为地ei入 公汽线路，ei出为公汽线路（在同一公汽车站换乘5公汽线路，e 为公汽线路（在同地铁站换乘iiei入 地铁线路，ei出为地铁线f2(ei入，ei出地铁线路，e 为公汽线ii公汽线路，e 为地铁线iiei入和ei出为同一线”，提出“节”的方法对上述模型进行改进的节点分列成N 个虚拟节点（N 与相交线路的条数相关），组成所以将D 点分解成六边形。如图7所示：图6.节点的连接B7. 节方法的示意图7中当D 节设起始站点为vS ，目地站点为vT ，问题可转化成求vS 到vT -18接vS 与vT 的目的是求出vS 到vT 转化为求从vS 到vT 的

19、最短路问6.3.2模型求可以用 Dijstra 算法57 （或其他算法）进行求解。结果如下(1) 换乘次数 时间 费用S3359下 接vS 与vT 的目的是求出vS 到vT 转化为求从vS 到vT 的最短路问6.3.2模型求可以用 Dijstra 算法57 （或其他算法）进行求解。结果如下(1) 换乘次数 时间 费用S3359下 13(2) S1557 下 S1919 下 23换乘次数 时间 13S0008 下S3053 上12S0148 下 S1487 转地S0466 下 25转-19(6) 换乘次数 时间 费用14转地 6.3 结果分相对于问题一的结果而言， S3359S1828、S155

20、7S0481、S0971S0485(6) 换乘次数 时间 费用14转地 6.3 结果分相对于问题一的结果而言， S3359S1828、S1557S0481、S0971S0485、S0008 S0073而且它们均不在地铁站周围，甚至连换乘站也不在地铁站周围。S0148S0485、 S0087S3676 这两种行车路线都给出了换乘地铁的路径，相对问题一的解来说运行时间大大减低了。其中，S0148S0485 比问题一中的节少了约分钟，这是因为两个S1487 D02， S0466 挨着 D21。S0087S3676 少S0087S3676S3676均在地铁站附近。7 问题三的求模型四：改进的网络流模新网络图G(VEE vi vj klk 1,2,3分别表地铁,步行;l为线路标号f (vi vj kl仍用时间表示边权 f (vi ,vj ,k,l) ，则：t地if k if k if k f (v ,v ,k,l) 步 3m