公交线路优化模型

1、 . 公交线路选择的网络优化模型摘要本文针对城市公交线路选择问题建立了相应的数学模型。将查询者寻找连接两点的最佳线路的过程看作车辆将查询者从起始站点运输到目的站点的过程，对于此类运输问题，可以建立网络流模型来求解。对于问题一，将公汽站点看作顶点，3957个公汽站点再加上源点S和收点T就构成了顶点集V。至于有向边vivj，并不是公汽站点间的实际线路，而是表明任意两站点i与j之间能否直达的有向弧，各边的容量为1、费用率为bij, 就构造了容量费用网络。再定义0-1变量fij作为流量，当fij=1时表明该有向边vivj中有流量通过，即最佳路线包括边vivj，就可以建立最小费用流模型来求解。由于源点S

2、的出度和汇点T的入度均为1，且所有有向边的容量cij=1，此最小费用流问题便转化为从vs到vt的最短路径问题，本文采用改进的Dijkstra算法求解此最短路问题。结合实际情况，本文从出行花费、换乘次数、出行时间三方面来理解所谓的“最佳线路”，用mij、kij和qij分别表征这三个目标的费用率，再引入优先因子来区分各目标的优先级，并结合实际增加换乘次数、费用、时间的上限约束，建立了类似目标规划的网络流模型，编程可求出任意两点在六种情况下的最佳线路。对于问题二，其实就是在问题一的容量费用网络中增加了39个顶点与部分有向边，仍旧是一个最小费用流问题，还可以用问题一中的方法求解，只是费用、换乘时间的计

3、算比问题一复杂。对于问题三，将步行看作独立于公汽、地铁的第三种交通方式，仍利用问题二中的网络图，不再增加有向边，并假设步行只能沿已有的有向边行进。主要从步行时间、换乘次数、出行花费和出行总时间四个方面来理解最佳线路，分别考虑各单目标，增加不同的上限约束，建立了相应的网络流模型。模型评价中对本文中的网络流模型进行了详细的评价说明，最后着眼于开发一个解决公交线路选择问题的自主查询计算机系统，提出了一点建议。关键词：最佳线路；最小费用流；Dijkstra算法；优先因子；上限约束一、 问题重述近年来，城市的公交系统有了很大发展，使得公众的出行更加通畅、便利，但公众也同时面临着多条线路的选择问题。针对此

4、市场需求，某公司准备研制开发一个解决公交线路选择问题的自主查询计算机系统。设计这样一个系统的核心是线路选择的模型与算法，应该从实际情况出发考虑，满足查询者的各种不同需求。现已给出某市公交线路与相关信息，请解决如下问题：1、仅考虑公汽线路，给出任意两公汽站点之间线路选择问题的一般数学模型与算法。并根据附录数据，利用你们的模型与算法，求出以下6对起始站终到站之间的最佳路线（要有清晰的评价说明）。 (1)、S3359S1828 (2)、S1557S0481 (3)、S0971S0485(4)、S0008S0073 (5)、S0148S0485 (6)、S0087S36762、同时考虑公汽与地铁线路，

5、解决以上问题。3、假设又知道所有站点之间的步行时间，请给出任意两站点之间线路选择问题的数学模型。二、 基本假设（1）仅考虑公汽线路时，换乘只发生在两条公汽线路的公共站点处。（2）对题目中基本参数设定进行补充：同一地铁站对应的任意两个公汽站之间通过地铁站换乘的平均耗时为11分钟（其中步行时间8分钟）。（3）根据实际情况，环行线的公交车到达始发站时不需要清人，所以始发站与其它站点可认为是没有区别的。上下行线路的公交车到达上行线的终点站（即下行线的始发站）时不需要清人，因此上行线的终点站（即下行线的始发站）与其他站点可认为是没有区别的。 （4）环行线的公交车是单方向行驶的。（5）所有站点之间都是相通

6、的，即公交线路的实际地理图是联通图。（6）设0-1变量fij为有向边vivj过的流量，记f =fij。当fij=1时表明该有向边vivj中有流量通过，即最佳路线包括边vivj，当fij=0时表明该有向边vivj中没有流量通过，即最佳路线不包括边vivj 。（7）所有有向边的容量均为1.（8）对于问题一、问题二，假设线路长度与经过站点数成正比。（9）本文中提到的费用率bij与费用没有必然联系，而是指有向边的权值。 三、 符号说明vi网络图中第i个顶点vivj网络图中连接站点i和j的有向边cij各有向边的容量，为常数1fij0-1变量表示流量，fij=1表示流过有向边vivj , fij=0表示没

7、有流过有向边vivjuij0-1变量表示出行方式，uij=1表示从站点i到j采用步行wij0-1变量表示出行方式，wij=1表示从站点i到j采用乘车bij各有向边的费用率，分别可以表征费用、换乘次数、时间等mij表征实际乘车费用的各有向边费用率，可取1，2，3（单位：元）M常数，实际乘车费用的上限约束乘车费用优先因子，表示查询者对乘车费用的偏爱程度kij表征换乘次数的各有向边费用率，值为1或0K常数，换乘次数的上限约束换乘次数优先因子，表示查询者对换乘次数的偏爱程度qij表征乘车出行时间的各有向边费用率（单位：分钟）Q常数，乘车出行时间的上限约束pij表征步行出行时间的各有向边费用率（单位：分

8、钟）P常数，步行出行时间的上限约束tij表征总出行时间的各有向边费用率tij = wij qij +uij pij（单位：分钟）T常数，总的出行时间的上限约束出行时间优先因子，表示查询者对出行时间的偏爱程度四、 问题分析本题是一个给出城市中任意两站点，寻求其最佳线路方案的问题。考虑到查询者的各种不同需求，本文认为所谓最佳线路，应该从乘车费用、换乘次数、出行时间三方面来理解。查询者寻找连接两点的最佳线路，可看作车辆将查询者从起始站点运输到目的站点，对于此类运输问题，可以建立网络流模型来求解。而题目中的三个问题，其实是逐步考虑了公汽、地铁、步行三种交通方式后的线路选择问题，而评判某一线路方案好坏的

9、原则是不变的，仍旧是花费、换乘次数与时间，因此三个问题都可以用网络流模型来求解。考虑到不同查询者对三个目标的偏爱程度不同，而实际生活中人们更习惯于优先考虑某一目标，然后再考虑次要的目标，比如：当两个线路选择方案所用时间一样时，再考虑哪一个方案费用更低。也就是说不同情况下三个目标的优先级不同，因此可以引入优先因子来区分各目标的优先级，得出满足查询者不同需求的最佳线路。五、 模型的建立与求解5.1问题一：仅考虑公汽线路5.1.1模型准备：构造容量费用网络N=(V,E,C,B)。1b12b13b14b23b24b34234图1设两个虚拟点作为网络流的源点S（source）、汇点T（terminal）

10、，题目中给出的3957个公交站点与S、T共同构成顶点集V 。由于题目要求给出任意两站点之间线路选择问题的一般数学模型与算法，不妨考虑任意两站点M到N的线路选择问题。在S与M、N与T之间分别添加有向边，这两条边的容量为1、流量也都是1.对于网络中各点间的有向边，并不是实际中的公汽线路，而是表明任意两站点i与j之间能否直达的有向弧，如图1所示：图1表示某一条公汽线路，图中标出了部分站点1、2、3、4，其中站点1为起始站。乘坐该线路的公交车，从站点1直达到站点2形成有向弧为v1v2 ，从站点2直达到站点4形成有向弧为v2v4 ，依次类推，这样给每条线路都画上有向弧，即为有向边，所有的有向边vivj构

11、成边集E.图中各有向边上的数据b12 、b13等称为各有向边的费用率，所有费用率bij构成集合B=bij|vivjE。所有边的容量都为1，即cij=1.所有的 cij构成集合C。设0-1变量fij为有向边vivj过的流量，记f =fij,当fij=1时表明该有向边vivj中有流量通过，即最佳路线包括边vivj，当fij=0时表明该有向边vivj中没有流量通过，即最佳路线不包括边vivj 。题目中公汽线路可分为两种：上下行、环路。下面本文将详细说明网络图中画有向边的规则：126图21）对于环路上的任意两点，都有两种连有向边的方式，但要考虑环线的车辆行驶方向。如图2，站点1为环路的始发站，若该环路

12、的车辆行驶方向为顺时针方向，则有向边v2v6必须按顺时针方向计算，不能按照逆时针方向计算。2）对于上下行路线站点均一样的情况，由于上行线的终点站（即下行线的始发站）与其他站点可认为是没有区别的，可将下行线逆序接到上行线之后，看作一条线路，这样某些站点之间也有两种连边方式，但只有经过站点较少的边才是许可的。(见图3)1324321上行线下行线b32b23图3：1为始发站，4为上行终点站（下行始发站），中间两条弧均是不允许的。3）对于上下行线站点不同的情况，仍将下行线逆序接到上行线之后，看作一条线路（见图4）。乘客如果想从站点3到站点5，可以乘坐公交从站点3直达站点5，画出有向边v3v5 ，其费用

13、率为b35；但如果乘客想从站点5到站点3（仅考虑图中这一条线路），则必须走52123，此时认为乘客走了两条线路，即在站点1处“换乘”，因而不能画有向边v5v31324521上行线下行线b35图4：1为始发站，4为上行终点站（下行始发站）5.1.2目标函数的构成结合实际情况，本文选择最佳线路时考虑了三个目标：出行花费、换乘次数、出行时间。针对不同的目标，各有向边的费用率bij均不一样，表征出行花费、换乘次数、出行时间的费用率分别可以记作mij、kij、tij 。对于公汽线路，三者的计算方法如下：1）乘车费用mij从站点i直达到站点j的实际乘车费用为mij。所有公汽线路可分为两种：环行、上下行。根

14、据假设，环行线上的各站点都是没有区别的。公汽线路中共有22条环路，其中采取分段计价的线路有：L017、L027、L152、L290、L296、L296、L485.这些线路上mij的值可取1，2，3. 分别对应乘客乘坐了020站、2140站、40站以上。其余的环路都是单一票制1元，故mij=1. 对于上下行线路，上行线的终点站（下行线的始发站）与其他中间站点可认为是没有区别的。若采取分段计价，乘客乘车经过上行线的终点站后只要继续数站点数即可，乘客乘坐了 020站：mij=1；2140站：mij=2；40站以上：mij=3 .若采取单一票制，那么不论乘客是否乘车经过的上行线的终点站，mij都等于1

15、.2）换乘次数kij模型中令所有有向边的kij =1，则对某一线路方案的kij求和减1就是该方案实际换乘的次数。3） 出行时间qij出行时间qij代表公交车从站点i直达到站点j的平均行驶时间。但是由于我们的最佳路线是由网络图中不少于一条边衔接而成，每次衔接时即是公汽换乘，而公汽换乘公汽平均耗时5分钟，因此可以把这5分钟算到qij中，可得qij=3×经过站数+5（单位：分钟）。利用MATLAB编程可得出所有qij的值，程序代码见附录中的程序，由于数据量大在此不便给出qij.4） 优先因子这三个目标性质不同，量纲不同，查询者对其偏爱程度也不同。考虑到实际生活中人们更习惯于优先考虑某一目标

16、，然后再考虑次要的目标，比如：当两个线路选择方案所用时间一样时，再考虑哪一个方案费用更低。因此不能将三者简单的动态加权为一综合目标，而应分情况讨论，不同情况下三个目标的优先顺序不同。为达到以上目的，本文引入优先因子表示不同查询者对乘车费用、换乘次数、出行时间三个目标的不同喜好程度，通过巧妙设置的值来区分各单目标的优先级，从而建立类似目标规划的网络流模型，如：令=1，=0.01，=0.00001，表示查询者优先选择乘车费用最少的线路，当乘车费用一样时，再优先选择换乘次数较少的，当换乘次数也一样时，再考虑出行时间。 5.1.3约束条件分析本文建立网络流模型解决此问题。首先，网络中中间点的出度应等于

17、入度其次，源点S的出度与汇点T的入度均为1第三，各边的流量fij不能超过边的容量cij，并且fij是0-1变量 ，第四，M、K、T都是常数，分别作为对乘车费用、换乘次数、出行时间的上限约束，具体数值视情况而定。因为当某一目标达到最优时，如果其它目标的值很差，也是没有实际意义的。5.1.4最小费用流模型的建立 本小问中取K = 3，M = 10，Q = 150作为约束。 5.1.5模型求解5.1.5.1求解算法改进的Dijkstra算法由于源点S的出度和汇点T的入度均为1，且所有有向边的容量cij=1，此最小费用流问题便转化为从vs到vt的最短路径问题，本文采用改进的Dijkstra算法求解最短

18、路问题，具体程序见附录中的程序.改进的Dijkstra算法：求赋权有向图G中从顶点u0到ut的最短路。记 S：具有永久标号的顶点集。D：一次转车可达的顶点集对每个顶点，定义三个标记（l(v)，z(v)，zhuan(v)），其中：l(v)：表示从顶点u0到v的一条路的权；z(v)：v的父亲点，用以确定最短路的路线；zhuan(v)：v的转车次数，用以确定最短路中到达v点转了几次车。算法的过程就是在每一步改进这三个标记，使最终l(v)为从顶点u0到ut的最短路的权。输入为带权邻接矩阵WStep1 赋初值：令,，zhuan(v)=0.且zhuan(v)<=2,令，z(v)=u0,uu0Step

19、2 更新l(v)、z(v) 、zhuan(v)：且zhuan(v)<=2，若l(v)> l(u)+W(u,v),则令l(v)= l(u)+W(u,v)，z(v)=u，zhuan(v)= zhuan(u)+1；Step3 设v*是使l(v)取最小值D中的顶点，则令S=S v*, uv*.Step4 若且ut，转（2）；否则，停止。 用上述算法求出的l(v)就是u0到ut的最短路的权，从ut的父亲标记z(ut)追溯到u0，就得到u0到ut的最短路的路线。根据以上算法，利用MATLAB编程，就能求出任意两公汽站点的最佳线路。5.1.5.2求解结果三个目标一共有六种排序，按不同的排序结果可

20、以分别给出相应的优先因子取值，然后计算最佳线路。针对题目中给出的6对起始站终到站，本文将分别给出其在这六种情况下的最佳线路。1）优先考虑乘车费用，然后再考虑换乘次数，最后考虑出行时间，即令模型中=1，=0.001，=0.00001，结果见表1.（备注：表中给出的最佳线路中的站点即是公汽换乘站点，表格后面还接着给出了最佳线路的详细信息，横线上表示公交线路，横线下的数字表示两者之间的站点数。以后的表格与之类似，不再注明。）表1：优先考虑乘车费用，然后再考虑换乘次数起始站终到站最佳线路费用（元）换乘次数时间（分）S3359S1828S3359S1784S182831101S1557S0481S155

21、7S1919S3186S048132106S0971S0485S0971S2184S048531128S0008S0073S0008S0400S00732183S0148S0485S0148S0036S3351S048532106S0087S3676S0087S3496S367621652）优先考虑乘车费用，然后再考虑出行时间，最后考虑换乘次数，即令模型中=1，=0.00001，=0.001，结果见表2.表2：优先考虑乘车费用，然后再考虑出行时间起始站终到站最佳线路费用（元）换乘次数时间（分）S3359S1828S3359S1784S18283273S1557S0481S1557S1919S3

22、186S048132106S0971S0485S0971S1609S048532106S0008S0073S0008S0400S00732183S0148S0485S0148S0036S3351S048532106S0087S3676S0087S3496S367621653）优先考虑换乘次数，然后再考虑乘车费用，最后考虑出行时间，即令模型中=0.001，=1，=0.00001，结果见表3.表3：优先考虑换乘次数，然后再考虑乘车费用起始站终到站最佳线路费用（元）换乘次数时间（分）S3359S1828S3359S1784S182831101S1557S0481S1557S1919S3186S048

23、132106S0971S0485S0971S2184S048531128S0008S0073S0008S0400S00732183S0148S0485S0148S0036S3351S048532106S0087S3676S0087S3496S367621654）优先考虑换乘次数，然后再考虑出行时间，最后考虑乘车费用，即令模型中的 =0.00001，=1，=0.001，结果见表4.表4：优先考虑换乘次数，然后再考虑出行时间起始站终到站最佳线路费用（元）换乘次数时间（分）S3359S1828S3359S1784S182831101S1557S0481S1557S1919S3186S04813210

24、6S0971S0485S0971S2184S048531128S0008S0073S0008S0400S00732183S0148S0485S0148S0036S3351S048532106S0087S3676S0087S3496S367621655）优先考虑出行时间，然后再考虑乘车费用，最后考虑换乘次数，即令模型中=0.01，=0.0001，=1，结果见表5.表5：优先考虑出行时间，然后再考虑乘车费用起始站终到站最佳线路费用（元）换乘次数时间（分）S3359S1828S3359S2903S1671S18283273S1557S0481S1557S1919S3186S048132106S097

25、1S0485S0971S1609S2654S048532106S0008S0073S0008S0630S2650S00733270S0148S0485S0148S0036S3351S048532106S0087S3676S0087S0088S0427S367632466）优先考虑出行时间，然后再考虑换乘次数，最后再考虑乘车费用，即令模型中 =0.0001，=0.01，=1，结果见表6.表6：优先考虑出行时间，然后再考虑换乘次数起始站终到站最佳线路费用（元）换乘次数时间（分）S3359S1828S3359S2903S1671S18283273S1557S0481S1557S1919S3186S0

26、48132106S0971S0485S0971S1609S2654S048532106S0008S0073S0008S0630S2650S00733270S0148S0485S0148S0036S3351S048532106S0087S3676S0087S0088S0427S367632465.2问题二：同时考虑公汽与地铁线路5.2.1模型准备：构造容量费用网络图N=(V,E,C,B)问题二仍旧可以利用网络流模型来求解，其容量费用网络图N=(V,E,C,B)比问题一中的网络图增加了以下三方面的容：1） 地铁线路上的站点所构成的新顶点 vi | i=3958, 3996.2） 同一地铁线路上各站

27、点之间的有向边。3） 考虑到同一地铁站对应的任意两个公汽站之间可以通过地铁站换乘，因而增加了不同公汽站点之间换乘的有向边。（如图5）公交线路1公交线路2地铁站地铁站1234b14b41图5：公汽站点1与地铁站4之间存在有向边v1v4、v4v1，费用率分别为b14、b415.2.2目标函数的构成1）乘车费用mij从站点i直达到站点j的实际乘车费用为mij，其中可能包括两部分：公汽与地铁。公汽线路费用计算方法与问题一一样。对于地铁：T1、T2两条线路的票价都是3元，当乘客从一条地铁线路换乘到另一条时要花费3元；如果乘客乘地铁后换乘公汽，然后又换乘地铁，即使他乘坐的还是同一条地铁线路，也要重新买票；

28、同一地铁站对应的任意两个公汽站之间通过地铁站换乘时，无需支付地铁费（图5）。2）换乘次数kij模型中令所有有向边的kij=1，则对某一线路方案的kij求和减1就是该方案实际换乘的次数，但对于像图5所示的情况，k14 = k43 =0，即从143记作换乘0次。kij具体计算函数如下：5） 出行时间qij出行时间qij代表乘客从站点i直达到站点j的平均出行时间，包括公汽或地铁行驶时间、换乘时间。对于图5中v1v4 这类边，由于地铁换乘地铁时费时4分钟，公汽换乘地铁时费时6分钟，故本文中设乘客从v1到v4费时2分钟，即q14=2，q43的设置类似。对于不同的换乘情况，qij的值不同，其计算方法见下式

29、，其中n代表公交车或地铁已行驶的站点数，即各自的有向边vivj覆盖的站数-1。6） 优先因子优先因子的定义与计算方法与问题一中的一样。5.2.3约束条件分析: 约束条件与问题一一样。5.2.4建立最小费用流模型本小问中取K = 3，M = 10，Q = 150作为约束。5.2.5模型算法与求解考虑了地铁线路后，问题仍能转化为最短路径问题，仍旧分6种情况，根据改进的Dijkstra算法用MATLAB求解。本小问中取K = 3，M = 10，Q = 150作为约束。1）优先考虑乘车费用，然后再考虑换乘次数，最后考虑出行时间，即令模型中=1，=0.001，=0.00001，结果见表7.表7：优先考虑

30、乘车费用，然后再考虑换乘次数起始站终到站最佳线路费用（元）换乘次数时间（分）S3359S1828S3359S1784S182831101S1557S0481S1557S1919S3186S048132106S0971S0485S0971S2184S048531128S0008S0073S0008S0400S00732183S0148S0485S0148S0036S3351S048532106S0087S3676S0087S3496S367621652）优先考虑乘车费用，然后再考虑出行时间，最后考虑换乘次数，即令模型中=1，=0.00001，=0.001，结果见表8.表8 ：优先考虑乘车费用，然

31、后再考虑出行时间起始站终到站最佳线路费用（元）换乘次数时间（分）S3359S1828S3359S2903S1671S18283273S1557S0481S1557S1919S3186S048132106S0971S0485S0971S1609S2654S048532106S0008S0073S0008S0400S00732183S0148S0485S0148S0036S3351S048532106S0087S3676S0087S3496S367621653）优先考虑换乘次数，然后再考虑乘车费用，最后考虑出行时间，即令模型中=0.001，=1，=0.00001，结果见表9.表9 ：优先考虑换乘次

32、数，然后再考虑乘车费用起始站终到站最佳线路费用（元）换乘次数时间（分）S3359S1828S3359S1784S182831101S1557S0481S1557S1919S3186S048132106S0971S0485S0971S2184S048531128S0008S0073S0008S0400S00732183S0148S0485S0148S1487S0466S04855287.5S0087S3676S0087S367630254）优先考虑换乘次数，然后再考虑出行时间，最后考虑乘车费用，即令模型中=0.00001，=1，=0.001，结果见表10.表10 ：优先考虑换乘次数，然后再考虑出

33、行时间起始站终到站最佳线路费用（元）换乘次数时间（分）S3359S1828S3359S1784S182831101S1557S0481S1557S1919S3186S048132106S0971S0485S0971S2184S048531128S0008S0073S0008S0400S00732183S0148S0485S0148S1487S0466S04855287.5S0087S3676S0087S367630255）优先考虑出行时间，然后再考虑乘车费用，最后考虑换乘次数，即令模型中=0.001，=0.00001，=1，结果见表11.表11 ：优先考虑出行时间，然后再考虑乘车费用起始站终到

34、站最佳线路费用（元）换乘次数时间（分）S3359S1828S3359S2903S1671S18283273S1557S0481S1557S1919S3186S048132106S0971S0485S0971S0567S0466S04855296S0008S0073S0008S2534S0609S00735265.5S0148S0485S0148S1487S0466S04855287.5S0087S3676S0087S367630256）优先考虑出行时间，然后再考虑换乘次数，最后再考虑乘车费用，即令模型中=0.00001，=0.001，=1，结果见表12.表12：优先考虑出行时间，然后再考虑换乘

35、次数起始站终到站最佳线路费用（元）换乘次数时间（分）S3359S1828S3359S2903S1671S18283273S1557S0481S1557S1919S3186S048132106S0971S0485S0971S0567S0466S04855296S0008S0073S0008S2534S0609S00735265.5S0148S0485S0148S1487S0466S04855287.5S0087S3676S0087S367630255.3问题三：所有站点之间的步行时间已知5.3.1问题分析： 将步行看作独立于公汽、地铁的第三种交通方式，仍利用问题二中的网络图，不再增加有向边，假设

36、步行只能沿已有的有向边行进。对于目标函数，如果分别考虑乘车费用、换乘这些单目标时，继续沿用问题二中的约束条件，而不附加任何限制，将得不到最佳线路的解。（比如：只考虑乘车费用时，由于步行没有任何费用，这样将得到全程步行这样一个没有意义的解。）为了解决这个问题，本文首先定义了0-1变量uij 、wij来区分从站点i到j所采用的出行方式，采用步行时，uij=1，wij=0；采用乘车时，uij=0，wij=1 。此时出行总时间tij = wij qij +uij pij 。然后在约束条件中加上了步行时间的上限约束：对于最佳线路，分别考虑步行时间、出行总时间、换乘次数、乘车费用四个单目标下的最优解。网络

37、流模型中的其它约束条件与问题二的一样。 5.3.2模型建立5.3.2.1模型一：步行时间最少目标函数为：沿用问题二中的约束条件，就能求出步行时间最短的线路。由于有乘车费用、换乘次数、和乘车时间的上限约束，故避免了全程乘车步行时间为0的情况，从而使得考虑步行时间最短的单目标有意义。5.3.2.2模型二：换乘次数最少目标函数为：但在考虑换乘次数最少这个目标时，应加入步行时间、总出行时间的上限约束，来避免全程步行这样没有意义的解。此时的约束条件为5.3.2.3模型三：乘车费用最低目标函数：但在考虑乘车费用最低这个目标时，应加入步行时间、总出行时间的上限约束，来避免全程步行这样没有意义的解。因此只需将

38、（5.3.2.2）中对乘车费用的约束条件改为对换乘次数的约束即可，即5.3.2.4模型四：总出行时间最少目标函数为求总时间最少：此时考虑总出行时间最少，就不用分别对步行时间、乘车时间增加上限约束。约束条件如下：5.3.3模型四的解的预测与分析1）该问题中的步行时间参数pij没有给出具体的数值，因此没法求出具体的解，本文只对解的情况进行了简单的预测分析：b34图6b451b132345参见图6，在约束围，假设求点1到点4的最优路线，依据模型求出的解可能是1到3步行，3到4乘地铁，4到5乘公汽。总之，当两点之间的乘车时间大于步行时间时，就选择步行。2）问题三模型四在求总出行时间最短时，将步行时间和

39、乘车时间分开表示，因此在求出最佳线路后，可分别得出步行时间为，乘车时间为。六、 模型的改进与评价6.1模型评价优点：1） 引入优先因子，通过巧妙设置优先因子的值来区分三个目标的优先级，建立了类似目标规划的网络流模型，求解得到满足乘客不同需求的最优线路。2） 网络流模型适用面广（可用于解决资源配置、运输、路径选择等一系列问题），灵活多变，通过对费用率的不同设置，既可以求出单目标最优解，又可以对多目标进行动态加权后求解，结果精确。另外网络流理论研究已相当成熟，非常复杂的问题也能利用计算机在有限的时间解决。缺点：1) 本文没有对网络流模型进行有效性证明，如果给予足够时间，我们将改正这一缺点。2) 模

40、型求解时，我们把流量为1的费用流问题转化成最短路径问题，根据改进的Dijkstra算法用MATLAB编程求解，由于费用率矩阵规模很大，故求解比较慢。3) 针对网络流模型没有提出效率更高的求解算法。6.2其他建议题目中提到某公司要研制开发一个解决公交线路选择问题的自主查询计算机系统，而一个较好的查询系统应该是智能化的，与查询者的互动性强。考虑到查询者有各种不同需求，仅仅是出行花费、换乘次数、出行时间这三个方面在不同查询者心中就占有不同的权重，因此在建立综合模型时可以将权值改为由查询者自行输入，然后系统再给出最佳路线方案。参 考 文 献1 省大学生数学建模竞赛专家组，数学建模，：华中科技大学，20

41、06年2静、但琦，数学建模与数学实验，：高等教育，2003年附 录程序1：计算问题一模型一价格费用率矩阵mijclc;clear;x=load('C:Documents and Settingswly桌面新建文件夹1bB2007dataw1checi.txt');w=inf(3957,3957);for k=1:929 clear xx; if x(k,2)=1 %单一价 if x(k,3)=0 %往返 xx=x(k,4:last(x(k,:) fliplr(x(k,4:last(x(k,:)-1); l=length(xx(1,:); q=1; for i=1:(l-1) f

42、or j=(i+1):l if w(xx(1,i),xx(1,j)>q w(xx(1,i),xx(1,j)=q; end end end elseif x(k,3)=1 %上行 xx=x(k,4:last(x(k,:) x(k+1,4+1:last(x(k+1,:); l=length(xx(1,:); q=1; for i=1:(l-1) for j=(i+1):l if w(xx(1,i),xx(1,j)>q w(xx(1,i),xx(1,j)=q; end end end elseif x(k,3)=2 %下行 elseif x(k,3)=3 %环线 xx=x(k,4:las

43、t(x(k,:)-1) x(k,4:last(x(k,:)-1); l=length(xx(1,:)/2; for i=1:l j=1; while i+j<=length(xx(1,:) if w(xx(1,i),xx(1,i+j)>1 w(xx(1,i),xx(1,i+j)=1; end j=j+1; end end end elseif x(k,2)=0 %分段 if x(k,3)=0 %往返 xx=x(k,4:last(x(k,:) fliplr(x(k,4:last(x(k,:)-1); l=length(xx(1,:); for i=1:(l-1) j=1; while

44、 i+j<=l if j<=20 && w(xx(1,i),xx(1,i+j)>1 w(xx(1,i),xx(1,i+j)=1; elseif j<=40 && w(xx(1,i),xx(1,i+j)>2 w(xx(1,i),xx(1,i+j)=2; elseif w(xx(1,i),xx(1,i+j)>3 w(xx(1,i),xx(1,i+j)=3; end j=j+1; end end elseif x(k,3)=1 %上行 xx=x(k,4:last(x(k,:) x(k+1,4+1:last(x(k+1,:); l=l

45、ength(xx(1,:); for i=1:(l-1) j=1; while i+j<=l if j<=20 && w(xx(1,i),xx(1,i+j)>1 w(xx(1,i),xx(1,i+j)=1; elseif j<=40 && w(xx(1,i),xx(1,i+j)>2 w(xx(1,i),xx(1,i+j)=2; elseif w(xx(1,i),xx(1,i+j)>3 w(xx(1,i),xx(1,i+j)=3; end j=j+1; end end elseif x(k,3)=2 %下行 elseif x(k,3)=3 %环线 xx=x(k,4:last(x(k,: