乘客公汽线路选择优化模型

刘国英　曹才子　吴华香

摘 要 公汽是整个城市交通系统中的一个重要组成部分，在方便人们出行的同时也给乘客带来了线路选择的困扰。本文给出任意两公汽站点之间线路选择问题的一般数学模型与算法，首先利用图论思想建立邻接矩阵，将其转化为有向最短线路问题，再根据公众出行对时间、费用和换乘次数的不同需求，建立单目标优化模型，得出单目标最优方案；此外通过建立多目标优化模型，还提供了同时考虑三种因素的综合最优方案，供乘客选择符合自己乘车需求的路线。

关键词 图论思想 最短线路 单目标优化模型 多目标优化模型

中图分类号：TP301 文献标识码：A

1公汽线路选择分析

1.1公汽线路的三种情况

本文依据公汽行驶的轨迹，综合考虑实际情况后将公汽线路主要划分为三种类型：

（1）上行线、下行线原路返回：这种线路有两个端点站，在两个端点站之间双向行车，而且两个方向上的行车路线相同，经过同样的站点序列。由于路线的方向不同，因此上行线和下行线可抽象成两条线路处理，线路号与收费规则相同。

（2）环行线：对于环形线路，一次线路无重复经过的站点，以城市中心为基点，从始发站绕市中心行驶一圈到终点站，且始发站与终点站相同。

（3）往返线路不一致：上行线、下行线经过的站点不完全一致。

1.2公汽线路选择的影响因素

随着城市化的加速，城市交通线路逐渐四通八达，公汽作为城市重要的交通方式之一，在优化城市交通，方便市民出行，发展城市经济等方面均发挥着重要的作用。在实际生活中，公众乘坐公汽主要考虑步行时间、转乘次数、行程时间、车站始发情况、负载量及乘车费用等因素，其中转乘次数、时间、车费三个因素对乘客公汽线路的选择影响最大，因此本文主要基于这三个因素建立优化模型来设计不同的乘车方案以满足乘客不同的出行需求。其中对于换乘次数，本文把换乘次数限制在转乘两次之内，这符合大多数乘客的乘车习惯，换乘次数分别为直达、一次换乘和两次换乘；时间由乘车时间和换乘时间决定，换乘时间包含步行时间和等车时间；费用的差别主要由换乘次数决定，换乘次数越多费用越高。

2模型的建立

2.1模型假设

假设1：出发点和目的地都为站点所在地，步行时间仅为换乘步行时间；

假设2：各路径上公汽发车频率相同，相邻站点平均行驶时间一定；

假设3：所有换乘都需再付费，因此换乘次数是费用差别产生的主要因素；

假设4：为了模型的简化和计算方便并且考虑到交通系统的合理性及完善性，实际生活中两次以上换乘情况出现较少，因此本文不讨论两次以上的换乘方案。

2.2 模型的准备

对于特定城市的公汽路线，将所有站点的车辆运行线路做出有P个顶点的向量图，P为该城市站点总数。其中为始发站的顶点仅有出的边无进的边，终点站的顶点仅有进的边无出的边，对于中间的站点出入边都有。用E表示弧的集合，设为邻接矩阵，其分量为

其中，为决策变量，当，说明弧位于顶点至顶点的线路上，否则。

2.3模型的建立

由于不同的人群乘车时考虑的侧重点不同，如时间观念强的人群侧重缩短时间；对开销敏感的节约型人群侧重减小乘车花费；残疾人士或者不愿转乘的人群侧重减少转乘次数。针对不同人群，给出三种乘车最佳路线方案，分别为用时最短方案、费用最少方案和综合最优方案，建立如下模型。

2.3.1用时最短方案

（1）目标函数的建立。

建立最短用时模型的单目标函数为：

其中从起始点到达目的地有三种乘车方案，从地直达地所需时间为：

换乘一次从地到地换乘，再从地到地所需时间为：

换乘两次从地到地换乘，从地到地换乘，再从地到地所所需时间为：

（2）约束条件的建立。

约束所有的线路在该有向图上：

其中，表示换乘次时乘车所需时间，表示乘车所需的最短时间，表示公汽站点之间的平均行驶时间，表示公汽换乘平均耗时，表示从站点到站点经过的站点个数。

2.3.2花费最少方案

（1）目标函数的建立。

建立最少费用模型的单目标函數为：

MIN = MIN（，，）

其中从起始点到达目的地有三种乘车方案，从地直达地所需费用为：

换乘一次从地到地换乘，再从地到地所需费用为：

换乘两次从地到地换乘，从地到地换乘，再从地到地所所需费用为：

根据不同的公汽线路收费标准，费用为：

（2）约束条件的建立。

约束所有的线路在该有向图上：

其中，表示从站点到站点经过的站点个数，表示从站点到站点的费用，表示乘车所需最少费用。

2.3.3综合最优方案

综合最优方案用时短费用少且换乘次数少，为使这三方面因素同时满足，建立以时间费用和换乘次数为目标的多目标函数：

3模型的求解思路

step1：根据城市的公汽线路信息数据，将公汽线路编号后导入，对每条线路进行抽象处理，将其分为上下行线路、往返线路不一致型线路和环行线路。

step2 ：利用图论的思想建立线路矩阵和邻接矩阵，将其转化为有向最短线路问题。

step3 ：在转乘次数最少的基础上考虑行程时间和乘车费用，分别以耗时最短、费用最小为目标函数，以最短时间矩阵和最少费用矩阵为基础建立单目标优化模型，给出供公众选用的多种参考方案以满足不同乘客需求。

step4 ：建立时间、换乘次数、车费的多目标模型，通过系统的搜索计算，利用优化决策的条件限制，采用基于枚举的搜索算法使得时间和费用都为最少时取最优。最短时间为直达的情况时其费用也最少即为最优方案。

4模型的评价

4.1模型的优点及推广

优点：

（1）站在乘客的角度，对乘客实际生活中线路选择可能会引起困扰的因素进行了详细分析，通过建立不同模型优化线路选择，给不同需求的乘客提供了单目标最优和综合最优的线路选择方案，使得模型的通用性、推广性更强。

（2）模型中的距离采用的是实际线路距离而非起点终点两点之间的直线距离，对乘客有更明确的指导。

推广：

模型解决的是一个典型的运筹学最短路线问题，不仅适用于乘客公汽线路选择问题，而且在工业、商业、交通运输、工程技术、行政管理等领域有着广泛的应用。文中建立的双目标的网络模型对图论类的优化问题的求解也可以起到指导作用。

4.2模型的缺点及改进

（1）由于假设相邻站点平均行驶时间一定是非现实的，所以使得模型的计算与实际有所偏差，可以尝试采用更多更有效的指标来优化模型。

（2）在给出路径源和目的地的条件下，模型通过算法可求得应走的路线，所花的时间及费用。但在现实生活中，交通系统随时可能发生变化，如上下班时线路交通拥堵或者因交通事故暂时中断，这样我们的路径推荐模型就可能将用户带到已经中断或者是非常拥挤的线路中。但这些在模型中未能反应出来，应建立动态的系统，这样才能根据最新的数据信息判断出最优方案。

参考文献

[1] 龚劬.图论与网络最优化算法[M].重庆大学出版社，2000.

[2] 谢金星.优化建模与LINDO/LINGO软件[M].北京：清华大学出版社，2005：180-190.

编辑整理：发展改革理论与实践杂志社官方网站