出版社资源配置优化（完整）

下面是小编为大家整理的出版社资源配置优化（完整）,供大家参考。

　

　奥运会公交线路查询系统最优方案研究

　朱惠雅， 梁培艳， 秦江星

　指导教师：

　刘平

　 摘要：

　本论文针对 2008 年北京奥运会期间乘客对于公交线路的选择问题进行了分析， 以乘客最短交通时间为首要目标， 综合考虑了转乘次数、 出行费用、 出行距离等其他次要因素，建立了公交线路查询系统的网络优化模型。

　首先， 我们对其换乘次数进行约束， 规定乘客的换乘次数不得超过 3 次。

　对于问题一， 仅考虑公汽站点之间的最佳线路选择问题。

　对于给定的起始点 A 与终到点 B， 利用广度优先算法搜索出这两点间所有连通的线路， 用这些线路建立起讫点网络， 通过对网络中的线路赋权值， 得到最终的目标函数。

　问题二中， 同时考虑地铁线路和公汽线路组成的网络。

　当任意两个站点间同时存在这两种交通方式时， 优先选择乘坐地铁出行。

　以最短交通时间为首要目标， 建立优化模型目标函数。

　问题三中， 假设已知所有站点之间的步行时间， 则所给站点和路线组成一个以最短交通时间为权值的全连通有向网络图。

　针对该交通网络图， 建立了两种模型。

　一为最短初等链模型， 在建立该模型过程中，未考虑换乘次数对算法的限制， 仅达到时间最优即可； 二为广度优先搜索模型， 在建立该模型过程中， 考虑了乘次数对算法的限制， 对路线进行了综合处理。

　关键词：

　广度优先搜索； 优化模型 ； 最短出行时间； 转乘次数； MATLAB

　 1

　基本假设 公交线路顺畅， 忽略外界客观因素引起的交通阻塞对公交车运行时间的影响。

　公交网络中的所有线路均为“无迂回线路”。

　假设转车的上限定为 3 次，

　鉴于 3 次以上的转车次数多， 不予考虑。

　当任意两站点间同时存在公汽线路和地铁线路这两种交通方式时， 优先选择乘坐地铁出行。

　2

　问题分析 问题一， 只考虑公汽出行的情况下确定任意两公汽站点之间线路选择问题的模型。

　首先考虑任意两站点之间的连通性， 确定出任意两站点之间转车次数在三次以内的路线。

　以乘车时间最短为首要目标， 以换乘次数少、 乘车费用低为次要目标， 确定最优线路。

　问题二， 将地铁线路与公共汽车线路结合考虑。

　基本思路与问题一相似， 只是在考虑任意两站点之间的连通性时， 需要检验这两个站点间所涉及到路线上是否有公汽站点与地铁站点可以换乘。

　如果有， 则将地铁站点计入线路中。

　再根据问题一中的标准分别确定不同乘客理想中的不同路线。

　问题三中， 假设已知所有站点之间的步行时间， 那么任意两站点之间都连接， 则所给站点和路线组成的交通网络成为一个全连通的有向网络图， 且该网络图以相邻站点间的最短到达时间为权值， 建立数学模型。

　3

　模型的建立与求解 4. 1

　 问题一 本问题要讨论公交网络中任意两个公汽站点之间的最佳线路选择问题。

　我们建立了一个起讫点网络数学规划模型对问题一进行求解。

　在这里， 最佳并不一定意味着最短。

　最佳线路是指在通达出行者目的的多条

　线路中， 能最好的满足出行者愿望的线路， 即是出行效用最大的线路。

　本文参照了在南京市做的一个公交乘客出行心理调查统计结果, 它主要对三个因素做了调查：

　换乘次数、 出行距离、 出行耗时。

　调查结果显示， 有 41. 16%的乘客在选择出行路径时首先考虑的是“换乘最少” , 其次考虑“时间最短” 的乘客占 30. 93％， 而将“路程最短” 作为出行时考虑的首要条件的乘客只占18. 60%， 最后考虑其他因素的乘客占 9. 30％。

　鉴于北京即将进入奥运会的特殊时期， 大批奥运观众涌入京城， 为保证奥运观众能正常地观看赛事， 避免将时间无谓的浪费在出行过程中， 大部分公交乘客在选择出行路径时会首先考虑以满足“出行时间最短” 为标准， 其次以“步行”、“换乘次数最少”、“所经过公交站点最少” 相结合作为判断标准。

　设 A、 B 为公交网络中的任意两点， 现在欲查找起始站点 A 到目的站点 B 的最优路线， 为使最终得到的线路出行时间最短， 建立了一个起讫点网络数学模型，需要分以下两步进行：

　(1)

　初始起讫点网络的建立 起讫点网络是一个由任意起始点 A 和终点 B 组成的节点集合， 以及描述这些起始点和终点之间配对关系的线路组成的网络。

　起讫点可以作为一条线路的始终点， 也可同时作为其它线路的过路点。

　利用广度优先搜索和深度优先搜索方法搜索出 A、 B 两点之间的所有“无迂回线路”， 包括 A、 B 之间得以实现连通的所有方案， 即直达方案、 换乘一次、 换乘二次、 换乘二次等三种方案的所有集合， 建立初始起讫点网络。

　(2)

　赋权值 将以上初始起讫点网络中的所有线路赋上时间权值。

　由题目中的“相邻公汽站平均行驶时间(包括停站时间)：

　3 分钟； 公汽换乘公汽平均耗时：

　5 分钟(其中步行时间 2 分钟)” 可知， 在一条公交线路上， 行进一站地需要 3 分钟， 起讫点网络中任意两相邻站点边权值为 3， 全程行驶时间为（站点个数－1）

　×3 分钟。又因为， 每转乘一次， 平均消耗 5 分钟， 故转乘时间为：

　转乘次数×5 分钟。

　将以上两种时间相加便得到全过程交通时间。

　设初始起讫点网络中起讫点 A、 B 之间“无迂回线路” 上的结点共为 m 个，其中转乘了 n（n=0， 1， 2， 3， ）

　次， 则这条线路的行车时间为

　=(1) 3∗ + ∗

　5ijtmn−ijT=Mint (03597,03597)ij≤ ≤≤≤ 表示从站点 i 到站点 j 的沿公交网络所需花费的最短时间。

　(3)

　建立起讫点数学规划优化模型 在起讫点网络后， 便可以对其进行优化。

　以服务区内乘客总乘车时间最短为主要目标建立数学模型， 得到构成最终每条奥运会交通线路的任意两站点之间的最短行驶时间路径。

　建立起讫点配对问题的数学规划模型如下：

　目标函数：ijT=Mint

　(03597,03597ij≤ ≤≤≤) 约束条件：

　=(1) 3∗ + ∗

　5ijtmn−

　 03n≤≤

　 13597m≤≤

　m、 n 均为整数 对于问题一中给定的六组数据， 在 MATLAB 中编制程序， 求出最终结果。

　4. 2

　问题二 本问题在问题一的基础上， 又涉及到了另一种交通工具：

　地铁， 即考虑乘坐地铁和公汽出行， 选择最佳线路， 使乘坐时间达到最短。

　建模过程中， 仍以最短出行时间为第一目标， 同时综合考虑出行费用和转乘次数， 从而确定出最佳路线。

　对所给数据的处理：

　（1）

　从所给地铁线路信息及其换乘公汽信息文档可以看出， 地铁线路 T2是一个环形线路， 而且与线路 T1 相交于地铁站点 D12 和 D18。

　（2）

　用 MATLAB 软件对地铁线路换乘公汽信息进行处理， 可分别得到起始站点和终点站点与公汽线路 Li 以及地铁站点 Dj 间的对应关系。

　为避免数据的繁琐， 在此， 我们只选取一组较简单的数据举例说明， 例如第一问中的第二组站点(2)、 S1557→S0481 的相关信息进行处理可得到以下关系：

　 公汽线路转乘地铁处所在公汽站点 S1919 S1919 S1919 S1921 S1920 S1920 S0978 S0978

　 对两条地铁线路关系进行简单模拟， 如下图所示：

　公汽线路 公汽线路转乘地铁处所在地铁站点

　 起始站点 下行 L084 上行 L363 下行 L 363 上行 L 084 上行 L 457 下行 L 457 上行 L 084 下行 L 084 D20 D20 D20 D20 D20 D20 D32 D32 在上图中， 椭圆表示线路 T2, 上方的箭头表示本路线运行方向为逆向行驶。其中， 地铁站点 D24、 D25、 D26、 ......D38、 D39 依次按照顺序逆向排列在线路T2 中， 站点 D12、 D18 穿插其中， 作为线路 T1 与 T2 的交点。

　横贯左右的近似直线即为地铁线路 T1。

　各个地铁站点 D1、 D2、 D3、 ……、 D22、 D23 从左至右依次排列在线路 T1 上。

　其中， 线路 T1 应该包括从 D1——D23 的上行路线以及从 D23——D1 的下行路线。

　(1)

　 起讫点网络的建立

　a、 从起始站点 A 乘坐公汽至最近的地铁站点阶段。

　此过程为：

　首先从起始站点乘坐公共汽车到达可以与地铁站点直接换乘的公汽站点。

　对于任意起始点 A 从 A 点开始进行广度优先搜索，

　找出经过 A 点的所有公共汽车线路， 这些线路上的所有公汽站点集合记为 Z ， 如果与地铁站点nD相连的公汽站点n S 在集合 Z 中， 则输出站点nD 与n S ， 并且输出连接nD 与n S 的公汽线路nL 。

　b、 从地下的地铁线路转乘回至公汽线路最后到达终止点 B。

　这一过程可以看成是第一阶段的反过程， 算法步骤基本相同。

　对于任意起始点 B， 从 B 点开始进行广度优先搜索， 找出经过 B 点的所有公共汽车线路，这些线路上的所有公汽站点集合记为 Z′ ， 如果与地铁站点nD′相连的公汽站点n S′在集合 Z′ 中， 则输出站点nD′与n S′， 并且输出连接nD′与n S′的公汽线路nL′。

　c、 从公汽站点转乘至地铁路线后的地铁线路 在 a、 b 的基础上， 连接起地铁站点nD 与nD′的地铁线路即为所求。

　(2)

　 赋权值：

　将以上初始起讫点网络中的所有线路赋上时间权值

　设初始起讫点网络中起讫点 A、 B 之间“无迂回线路” 上的公交站点共为 m个 ，其 中 转 乘 了(0,1,2,3)n n =次 ，则 这 条 线 路 的 地 上 行 车 时 间 为 =(1) 3∗ + ∗ 。

　设在地铁线路上经过地铁站点数目为 p 个， 在地铁线路转5ijtmn−乘 (0,1,2,3)q q =次， 则在地下运行时间为(1)*2.5*4ijtpq′=−+。

　那么整个过程的交通时间为67ijijttt′=++ +

　T＝Mint表示从站点 i 到站点 j 的沿公交网络所需花费的最短时间。

　(3)

　 建立起讫点数学规划优化模型 在确定了起讫点网络后， 便可以对其进行优化。

　以服务区内乘客总乘车时间最短为主要目标建立数学模型， 得到构成最终每条奥运会交通线路的任意两站点之间的最短行驶时间路径。

　建立起讫点配对问题的数学规划优化模型如下：

　目标函数：ijT=Mint

　约束条件：

　=(1) 3∗ + ∗

　 5ijtmn−

　 (1)*2.5*4ijtpq′=−+

　03n≤≤

　 03q≤≤

　 13597m≤≤

　139p≤≤

　m、 n、

　p、 q 均为整数 4. 3

　 问题三 模型一：

　最短初等链法 本模型主要运用网络图的权映射的概念 ， 并通过它把所有求解图的最短路问题转化为最简单的分阶段单向动态规划问题， 并在此基础上提出了一种求解图的最短路问题的通用算法——最短初等链法。

　设所给公汽线路， 地铁线路和步行线路及其各个站点构造的网络图 G=(V，W )(其中 {}01, ,...,v vnVv=，0v 为起点，nv 为终点)的一等效作业图是一个 m 阶段的动态规划图。(0,1,,)iV im=是其 m+1 个状态集。

　那么此时的寻优函数方程为：

　{}{}{}{}00111( )f v0( )f vmin()(, )vmin( ) |nf v|,1,2,...,iiiiiiknjfvw vkj vV jm−−−==+∈∈=

　 (),1,2,...,iivV im∈=

　其中( )knf v 即从初始站点0v 到达终到站点nv 所用时间，iv 表示题目中的各个站点，1(, )viiw v−作为权值， 即为任意两相邻站点交通所用时间， 当两站点间可通过多种交通工具到达时，1(, )viiw v−的值即为所有交通工具中用时最短的一种所对应的时间。

　当两点间不存在公汽和地铁线路时， 可选择步行到达， 步行所需时间it 已在题目中得到假设。

　模型二：

　基于广度优先算法的最优路线求法。

　步骤 a：

　如果itT<， 则进行步行分析， 如果存在合适的步行路线则建议乘客步行。

　步骤 b：

　经过站点 A 的所有车的集合为 P（A1）， 经过站点 B 的所有车的集合为 P（B）， 如果 P（A1）

　与 P（B）

　的交集非空， 则找出此交集， 即乘一次车即可到达。

　若可以一次到达， 则计算出 A， B 之间公共站点最少的线路为最优路线， 算法结束。

　否则转步骤 3。

　步骤 c：

　找出 P（A）

　中车的所有能转乘车次的集合 P（A2）， （假设共有转车 n1 车次）

　如果 P（A2）

　与 P（B）

　的交集非空， 则找出此交集， 并按顺序找出这个交集中的车由哪些车转来。

　即知经一次转车即可到达目的站点。

　5

　模型的结果分析 在本题中建立的模型， 给出了任意两公汽站点之间线路选择问题的一般数学模型与算法。

　通过对结果进行分析， 得到以下：

　问题一中， 求得的最终结果为如下所示：

　(1)、 S3359→S1828：

　67mins； (2)、

　S1557→S0481：

　106mins；

　(3)、 S0971→S0485：

　115mins； (4)、 S0008→S0073

　64mins ； (5)、 S0148→S0485 ：

　111mins； (6)、 S0087→S3676 ：

　46mins。

　 可见， 为得到两点之间的最佳路线， 需要适当增加转乘次数， 可以获得相对更短出行时间。

　例如在第三组数据中(3)、 S0971→S0485 中， 转乘一次的交通时间为 128mins， 转乘二次降低为 115mins。

　问题二中， 我们做了如此假设：

　鉴于地铁线路的高速低价等优点， 当两点间同时存在这两种交通方式时， 优先选择乘坐地铁出行。

　得到最佳线路的用时分别为如下所示：

　(1)、 S3359→S1828：

　76mins； (2)、 S1557→S0481：

　86mins； (3)、S0971→S0485：

　78mins； (4)、 S0008→S0073：

　50mins； (5)、 S0148→S0485：

　79mins (6)、 S0087→S3676：

　30mins。

　将问题一与问题二的结果进行比较， 绘制折线图， 发现两点间同时存在这两种交通方式， 优先选择乘坐地铁线路的出行时间确实低于公汽线路所需时间， 证明了我们假设是非常合理的。

　020406080100120140S3359→S1828S1557→S0481S0971→S0485S0008→S0073S0148→S0485S0087→S3676问题一问题二 6

　模型的推广与探讨 模型的推广：

　本文中我们建立了公交线路查询系统的网络优化模型。

　该模型可以用于辅助设计电子地图， 用于地理信息系统或其他信息检索系统。

　同时， 在解决本类问题时， 除了利用 Matlab 这一常见软件进行编程求解。我们还可以尝试利用数据库加 VB 实现， 或者其他诸如 mathematica、 spss 等软件进行求解。

　进一步探讨：

　在确定最佳路线时， 我们以出行时间最短作为首要考虑目标，对乘客的乘车心理统一按照一种思路考虑， 这种方法可能并不能使所有的乘客满意， 因此进一步研究要设计出合乎不同用户乘车心理的线路选择标准； 可以考虑对出行时间、 出行费用、 出行距离、 换乘次数等目标加权， 对不同需求的乘客设置不同的权值， 从而可以满足所有乘客各种不同的要求。