公交线路优化模型

《公交线路优化模型》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

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

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

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

4、畅、便利，但公众也同时面临着多条线路的选择问题。针对此市场需求，某公司准备研制开发一个解决公交线路选择问题的自主查询计算机系统。设计这样一个系统的核心是线路选择的模型与算法，应该从实际情况出发考虑，满足查询者的各种不同需求。现已给出某市公交线路及相关信息，请解决如下问题：1、仅考虑公汽线路，给出任意两公汽站点之间线路选择问题的一般数学模型与算法。并根据附录数据，利用你们的模型与算法，求出以下6对起始站→终到站之间的最佳路线（要有清晰的评价说明）。(1)、S3359→S1828(2)、S1557→S0481(3)、S0971→S0485(4)、S0008→S0073(5)、S

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

6、）与其他站点可认为是没有区别的。（4）环行线的公交车是单方向行驶的。（5）所有站点之间都是相通的，即公交线路的实际地理图是联通图。（6）设0-1变量fij为有向边vivj中通过的流量，记f={fij}。当fij=1时表明该有向边vivj中有流量通过，即最佳路线包括边vivj，当fij=0时表明该有向边vivj中没有流量通过，即最佳路线不包括边vivj。（7）所有有向边的容量均为1.（8）对于问题一、问题二，假设线路长度与经过站点数成正比。（9）本文中提到的费用率bij与费用没有必然联系，而是指有向边的权值。三、符号说明31vi网络图中第i个顶点vivj网络图中连接站点i和j

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