城市公交线路选择模型

第一条:S3359-S1828 需要换乘 1 次车 从“S3359”乘 L436 到“S1784”转乘：L167；L217 到“S1828”下车；站数： 32；费用 2 元
第二条:S1557-S0481 需要换乘 2 次 从“S1557”乘 L084；L363 到“S1919”转乘：L189；L417 到“S3186”转乘： L460 到“S0481”下车；经过 32 站；费用 3 元
k
i, j ∈ Lk
当某线路不区分上行， 下行时该线路上任意两站点可以互相通车， 而区分上， 下行时，把上，下行看作是两条线路，且只能由起始站往终点站方向通车，这时 距离有正负，距离为负时，定义 d ij 为∞，即不通车。在 A0 矩阵中 d ij ≠∞表示有
直达车并且由 i 到 j 的最短时间是 3 d ij 。 ⎧ 1, ⎪ Mij= ⎨ 2 , ⎪ 3, ⎩ Mij=1.
2.2 符号的约定与说明 (1)、 d ij 表示 i 站点 到 j 站点的行车距离， d ij lk 表示 l k 线路上的 i 站到 j 站的
k 行车距离, d ij 表示 k 次转车到站后的最小行车距离。
(2)、 mij
lk
表示 l k 线路上 i 站到 j 站的行车费用。
(3)、Tab 表示 a 站到 b 站的乘车时间。 (4)、Mab 表示 a 站到 b 站的乘车费用。 (5)、 Li （i=1， · · · ，924）表示第 i 条线路上所有站点构成的集合，上行与下行 线路看作是两条不同线路。 (6)、 l k 表示公汽站名，sk 为地铁站名，Sk 地铁线路。 (7)、P1 表示分段计价公汽线路的集合，P2 表示单一计价公汽线路的集合。 (7)、Li 表示通过 i 站点的所有线路的集合。 (8)、Ni 表示地铁站点 Di 及其所对应的公汽站点的集合。 (9)、 a lk 是站点 a 在 l k 中的位置，即向量 l k 中的坐标
3、 问题的分析
这是一个比较复杂的多目标优化问题， 不同的查询者最优路线的标准是不一 样的，而且多数情况下会综合考虑换车次数，行车费用与行车时间问题，查询系 统应该给出多种方案供查询者选择。 因为同一路线上相邻站点间行车时间相等， 所以设同种类相邻站点间行车距 离为单位 1，行车时间与行车距离成正比。行车时间最少问题可以转化为行车距 离最短问题。 环行车第 i 站与第 j 站间的最小行车距离是：
在只考虑公汽线路的情况下，构造最小行车距离和最小行车费用矩阵,使用 双向 Dijkstra 算法 进行最优路径的搜索，并使用数据缓存技术优化程序运算 速度。 当把公汽线路和地铁线路一起考虑时，换乘不同种类车费时多，步行时间也 多，所以换乘同种类车优于换乘不同种类车。我们分三种情况利用动态规划的方 法解决问题。 在已知所有站点间步行时间的情况下， 我们认为步行十分钟以内可到达目的 地时，系统提示可以步行，并给出乘车方案，人们根据自己的需要去选择。 另外， 如果两个站点间的步行时间小于起始站时的换乘时间， 应该考虑步行。 关键词：多目标优化，双向 Dijkstra 算法，动态规划，矩阵迭代。
城市公交线路选择模型
摘 要
本文所讨论的是多目标优化问题，乘车的路线选择应该以省时间，省钱和倒 车次数最少为主要目标。把所有公交线路的往返都看成是两条线路，构成一个有 向网络图。要设计公交查询系统，我们如下建立从 r0 到 rk +1 站点的最小时间和最 小费用的数学模型。
k k i =1
min s.t.
地铁换乘地铁平均耗时： 地铁换乘公汽平均耗时： 公汽换乘地铁平均耗时：
4 分钟(其中步行时间 2 分钟) 7 分钟(其中步行时间 4 分钟) 6 分钟(其中步行时间 4 分钟)
公汽票价：分为单一票价与分段计价两种，标记于线路后；其中分段计价 的票价为：0～20 站：1 元；21～40 站：2 元；40 站以上：3 元 地铁票价：3 元（无论地铁线路间是否换乘）
用双向 dijkstra 算法计算存贮于数据库中的邻接矩阵中某一点的源程序： 见附录 2 运行结果如下图:
因为共有 528387 个站点.邻接பைடு நூலகம்阵的大小是 528387*528387 假设一次读写矩阵时间复杂度为 1 生成 A0 时间复杂度为 528387*528387 ≈ 2.79*10 12
矩阵迭代的时间复杂度约为:8*10 24 如果采用提前运算，并把运算结果存入数据库， 这样当查询时的时间复杂度为 1 但一次运算也很长的时间， 所以采用只运算有所查询站点有关的矩阵内点的方法减少运算时间； 每次运算的时间复杂度约为尝试查询次数 n 经实际使用平均时间复杂度约为 10000 可以接受. 3.1.4 几条线路的最佳选车路线
⎧ j − i, d ij = ⎨ ⎩n − i + j ,
j −i > 0 j −i < 0
由于数据量庞大，不能简单的应用常见的模型方法，并且必须利用计算机编 程，我们利用 Dijkstra 算法，构造最小距离和最小费用矩阵。然后借助双向 Dijkstra 算法减少计算机的查询次数，引入数据缓存技术大大优化程序运行效 率。
第三条: S0971-S0485 需要换乘 1 次 从“S0971”乘 L013 到“S2184”转乘：L417 到“S0485”下车； 站数：41；费 用3元
第四条:S0008----S0073 需要换乘 1 次车 从“S0008”乘 L63 下行到 “S2083” 转乘 L057 上行到“S0073” ，站数：26， 费用 2 元 从“S0008” 乘 L55 下行到“ S2263” 转乘 L345 上行到“S0073” ， 站数：26， 费用 2 元 从“S0008”乘 L55 下行到 “S2303” 转乘 L345 上行到“S0073” ，站数：26， 费用 2 元 从“S0008”乘 L59 下行到 “S0400”转乘 L474 下行到“S0073” ，站数：26，
佳转车位置，到达目的地的最短时间 3 d k ij +5k，Mij=Mir1+Mr1r2+…+Mrkj。
d ij k −1 =∞，d k ij ≠∞时，则表示 i 到 j 至少要转 k 次车。在一个公交系统非常
完善的城市里 k 应该不会超过 3。 4.1.2 乘车费用最少的方案 构造最小行车费用矩阵：B0=(Mij), i，j=S0001，…，S3968， S1 与 S2
2、同时考虑公汽与地铁线路，解决以上问题。 3、假设又知道所有站点之间的步行时间，请给出任意两站点之间线路选择问 题的数学模型。 4、T1,T2 两条地铁线路都是往返的车走相同的站点。
2、模型的假设与符号约定
2.1 模型的假设与说明 (1)、 假设公交系统运转正常， 不出现交通堵塞等问题， 红绿灯不影响行车时间。 (2)、同种类站点之间行车距离相等，都设为单位 1，与实际距离无关。 (3)、上行车与下行车看作是两条线路，并且都只往终点站方向行驶。不区分上 行，下行的线路不考虑方向问题。 (5)、每个地铁站都有公汽站点相对应，并且同一个地铁站相对应的公汽站之间 可以通过地铁站倒车，不计费用。 (6)、相邻公汽站平均行驶时间(包括停站时间)： 3 分钟 相邻地铁站平均行驶时间(包括停站时间)： 2.5 分钟 公汽换乘公汽平均耗时： 5 分钟(其中步行时间 2 分钟)
k k −1 k −1 k −1 k −1 这表示 i 到 j 至少要转 k 次车。m ij =min{ mir + mrj },使{ mir + mrj }取
最小值的 r 是第 k 次的最佳转车位置。 4.1.3 查询系统的设计
把每条线路存为向量，构成公汽线路的数据库，已知初始站 a 和终点站 b， 可以确定两种方案的转车点 ri ,从而根据费用最小和行车距离最短分别确定转车 路线，查询者根据自己的需要选择乘车路线。 1. 数据库:
i=0
i i +1
s.t.
d riri +1 ≤ 20 ⎧1, ⎪ Mri ri +1 = ⎨2, 20 < d riri +1 ≤ 40 ， ⎪ 3, d riri +1 > 40 ⎩ Mri ri +1 =1，
i=0,1,...,k
L ji ∈ P1 （分段计价线路）,
L ji ∈ P 2 （单一计价线路）
之间没有直达车时 mij 为∞， 有一条以上直达车时 mij 为在不同直达线路上行驶由 i 到 j 的最小行车费用，即 mij= min {mij Lk },
k
i, j ∈ Lk
k −1
通过矩阵迭代，当 B(k+1)=B(k)时迭代结束。 mij 有： mij= m k ij
=∞，m k ij ≠∞时，则此时
i=0,1,...,k
4.1.1 行车距离最短的方案 首先构造汽车站点间的最小距离矩阵： A0 = ( d ij ) ，i，j=S0001，…，S3968，
d ij 表示的‘距离’这样定义：S1 与 S2 之间没有直达车时 d ij 为∞，有一条以上
直达车时 d ij 为在不同直达线路上行驶由 i 到 j 的最短行车距离，即 dij= min {dij Lk },
4、模型的建立与求解
4．1 只考虑公汽线路时的路线选择 如下建立从 r0 到 rk +1 站点的最小时间和最小费用的数学模型。
k
min s.t.
Tr 0 rk +1 =
Tri ri ∑ i
=0
+1
+5k i=0,1,...,k
ri , ri +1 ∈ l ji ,
r1,r2,…,rk 为中间转车站点。 l ji （i=1， · · · ，924）表示第 j i 条公汽线路。
k
min
M r 0 rk +1 =
∑ Mr r
i=0
i i +1
s.t.
d riri +1 ≤ 20 ⎧1, ⎪ Mri ri +1 = ⎨2, 20 < d riri +1 ≤ 40 ， ⎪ 3, d riri +1 > 40 ⎩ Mri ri +1 =1，
l ji ∈ P1 ,
l ji ∈ P 2
费用公式：Mij=Mir+Mrj
1 d ij = ∞ 表示由 i 到 j 直达和转一次车都不能到达，这时需要构造第 3 个矩阵
A2=(d 2 ij )，只要还有 ∞在矩阵中，就需要构造新的矩阵。
k k −1 k −1 k −1 k −1 我们有 d ij =min{ d ir },使{ d ir }取最小值的 r 是第 k 次的最 + d rj + d rj
Tr 0 rk +1 =
∑ Tri ri+1 + ∑ t k （t k 为换车时间）
i =0
ri , ri +1 ∈ L ji ,
i=0,1,...,k,
r1,r2,…,rk 为中间转车站点。 L ji （i=1， · · · ，1044）表示第 j i 条线路。
k
min
M r 0 rk +1 =
∑ Mr r
1
费用公式：乘分段计价车
dij ≤ 20 20 < dij ≤ 40 ， dij > 40
乘单一票价车
1 1 1 利用 A0 矩阵构造新的矩阵 A1=（ d ij ） ， d ij =min{ d ir + d rj },则 A1 中包括了直 1 达，和需要转一次车的最短距离，使{ d ir + d rj }取得最小值的 r 为转车的最佳位 1 置，到达目的地的最短时间为 3 d ij +5（转车时间为 5 分钟） ， 1
[1]
1、 问题重述
我国人民翘首企盼的第 29 届奥运会明年 8 月将在北京举行，届时有大量观 众到现场观看奥运比赛，其中大部分人将会乘坐公共交通工具（简称公交，包括 公汽、地铁等）出行。这些年来，城市的公交系统有了很大发展，北京市的公交 线路已达 800 条以上，使得公众的出行更加通畅、便利，但同时也面临多条线路 的选择问题。 针对市场需求，某公司准备研制开发一个解决公交线路选择问题的 自主查询计算机系统。 为了设计这样一个系统，其核心是线路选择的模型与算法，应该从实际情况 出发考虑，满足查询者的各种不同需求。需要解决如下问题： 1、仅考虑公汽线路，给出任意两公汽站点之间线路选择问题的一般数学模型 与算法。并根据附录数据，利用所构造的模型与算法，求出以下 6 对起始站→终 到站之间的最佳路线（要有清晰的评价说明） 。 (1)、S3359→S1828 (4)、S0008→S0073 (2)、S1557→S0481 (5)、S0148→S0485 (3)、S0971→S0485 (6)、S0087→S3676