最优公交线路选择问题的数学模型及算法.pdf

第 1 7卷 第 5期 2 0 0 8年 1 0月 运 筹 与 管 理 OPERATI ONS RES EARCH AND MANAGEMENT SCI ENCE Vo 1 1 7 No 5 0c t 2 0 0 8 最优公交线路选择 问题 的数学模 型及算法 周文峰 李珍萍 刘洪 伟 王吉光 1 北京物资学院 教务处 北京 1 0 1 1 4 9 2 北京物资学院 信息学 院 北京 1 0 1 1 4 9 3 中国科学院 数学与系统科学研究 院 北 京1 0 0 0 8 0 摘要 公交线路选择问题是城市公共交通信息查询 的重要 内容 本文建立了满足不 同公 交线路查询 者需求 的 最优线路选 择模 型并 给出了相应的算法 首先通过引入各 条公交 线路直达最短距离矩 阵构 造 了公交 网络直达 关系图 直达矩阵 在直达关系图 直达矩阵 上 利用修 改 了的最短路 算法 即可求 得最优换乘 路线 根据 出 行者的不同需求 通过在直达关系 图上定义不同的权系数 可 以分别求得换乘次数最少的公交 出行线 路 经过 站 点最少 的公交 出行线路 通过修改最短路算 法 可以求得 出行 耗时最少的线路及 出行费用最低 的线路 另外 本 模型还 可以综合考虑 出行者的需求情况 求 得出行者满意度最 大的出行路线 关键词 运筹学 最优路线 直达矩阵 换乘 最短路 中图分 类号 0 2 2 3 文章标识码 A 文章编 号 1 0 0 7 3 2 2 1 2 0 0 8 0 5 0 0 8 0 0 5 Ma t h ema t i c a l Mo de l s an d Al go r i t hms o f Op t i ma l Pub l i c Tr a n s p O r t a t iO n L in e Ch o i c e Pr o b l e m ZHOU W e n f e n g L I Zh e n p i n g LI U Ho n g we i W ANG J i Gu a n g 1 E d u c a t i o n a l A d m i n i s t r a t i o n S e c t i o n B e r i n g W u z i U n i v e r s i t y B e n g 1 0 1 1 4 9 C h i n a 2 S c h o o l o f I n f o r m a t i o n B e ij i n g Wu z i U n i v e r s i t y B e ij i n g 1 0 1 1 4 9 C h i n a 3 I n s t i t u t e o f Ma t h e m a t i c s a n d S y s t e m s S c i e n c e C h i n e s e A c a d e m y of S c i e n c e B e n g 1 0 0 0 8 0 C h i n a Ab s t r ac t P u b l i c t r a n s p o r t a t i o n l i n e c h o i c e p r o b l e m i s t h e mo s t i mp o r t a n t i s s u e i n q u e r y o f p ub l i c i n f o r ma t i o n T hi s p a p e r g i v e s t h e ma t h e ma t i c a l mo d e l s a nd a l g o r i t h ms o f o pt i ma l p u b l i c t r a n s p o r t a t i o n l i n e c h o i c e a c c o r d i n g t o t h e d i f f e r e n t r e qu e s t o f t h e q u e s t e r s F i r s t t h e d i s t a n c e ma t r i x o f p u b l i c t r a n s p o r t a t i o n l i n e i s i n t r o d u c e d t he n t h e d i r e c t e d r e l a t i o n g r a p h i s c o n s t r uc t e d I n t h e d i r e c t e d r e l a t i o n g r a p h we c a n g i v e t h e o p t i ma l l i n e b y r e v i s e d s h o r t e s t p a t h a l g o r i t h ms Fo r d i f f e r e n t r e qu e s t s we c a n f i n d t h e p u b l i c t r a n s p o r t a t i o n l i ne o f l e a s t c h a n g e s h o r t e s t p a t h a n d S O o n b y r e v i s i n g t he we i g h t c o e f f i c i e n t o f e d g e s i n t h e d i r e c t e d r e l a t i o n g r a p h By r e v i s i n g e t h e a l g o r i t h m o f s h o r t e s t p a t h we c a n fi n d t h e o p t i ma l l i n e s o f t h e s h o rte s t t i me o r t h e 1 o we s t f e e F u r t he r mo r e t h e mo d e l c a n b e u s e d t o fin d t h e mo s t s a t i s f a c t i o n l i n e o f d i fie r e n t t r a v e l e r s Ke y wo r ds o p e r a t i o n a l r e s e a r c h o p t i ma l l i n e d i r e c t e d ma t r i x t r a n s f e r t he s ho rte s t p a t h 0 引言 随着 城市公 交 系统 的快 速发展 各个 大城市普 遍建立 了 四通八 达 的公 交 网络 例如 北京市 目前公 交线 收稿 日期 2 0 0 7 1 1 O 3 基金项 目 北京市属 市管高等学校人 才强教项 目 2 0 0 7 2 0 0 9 和北京物资学院科研基地联合 资助 作者简 介 周 文峰 1 9 6 6 男 经济师 学士 在读硕 士研 究生 主要研 究方向 供 应链管理 计算机算法 李珍 萍 1 9 6 6 一 女 教授 博 士 主要研 究方 向 运筹学理论及应 用 生物信息学 刘洪伟 1 9 7 8 男 讲师 博士 主要研 究方 向 运筹学理论及 应用 王吉光 1 9 8 2 一 男 博士研 究生 主要研究方向 运筹学 生物信息学 第 5期 周 文峰 等 最优 公 交线路 选择 问题 的数 学模 型 及算 法 8 l 路 已达 8 0 0条 以上 公 交 线路 的增加 一方 面使得 公众 的 出行更 加通 畅 便 利 另 一方 面也使 得 乘坐公 交 工 具 出行 的人们 面 临多 条线路 的选 择 问题 尤 其是 2 0 0 8年 奥运会 期 间 会有 大 量的 国 内外 观众 涌人 北 京 这些 人不 熟悉 北京 的公 交线路 所 以他们 迫切 需要 一种方 便快 捷 的公交 线路查 询 系统 以便 能及 时查询 需 要乘坐的公交车次 换乘站位置等信息 由于不同的出行者有不同的需求 如有的乘客希望换乘次数最少 有的希望经过的路程最短 有 的希 望所花费的时间最短 还有的希望所花费的费用最低等 因此如何在现有的公共交通条件下 针对不 同乘 客的需求 提出一种合理的公交线路查询模型和算法是建立公交信息查询系统的关键 目前应用 比较广泛的公交线路查询方法主要是利用启发式算法直接从经过 出发站点和终到站点的线 路中搜索 寻找满足条件的换乘方案 本文主要考虑公交出行者的换乘次数 出行时间 出行费用等因 素 建 立最 优公 交线 路查 询 问题 的数学模 型 并设 计 算法寻 找最 优公 交 出行 路线 1 最优公交 出行线路选择模型及算法 问题的描述 在给定有若干条公交线路的公交网络图中 求任意两个站点之间的最佳出行路线 根据 乘 客 的要求 不 同 最佳 出行 路线 可 以分别 表示为 最短距 离路 线 最 少换 乘次 数路 线 最 短 时间路 线 最少 费 用路线 以及最大满意度路线等 下面分别讨论 1 1 最 短距 离公 交 出行线 路选 择模型 及算 法 第 1步建立每条线路的直达距离矩阵 首先 把 所有 的公交 站点 作 为顶点 对 每 条公 交 线路 按 照 公 交车 的运行 方 向 双 向 上 行 或 下 行 在 相 邻两个 站 点之 间连边 或 弧 如果 是上 下行 站点完 全 相 同 则 在相 邻两 个 站点 之 间 连边 否 则在 相 邻 站点 之间连弧且弧的方向与公交车运行方向一致 边或弧的权均为 1 得到该公交线路邻接关系图 在该图上 运 用 D i j k s t r a算法 可 以求 出任意 两点 之间 的最短 路 根 据最 短路 建立该 线路 对应 的最 短距 离直 达矩 阵 以下 以一个 简单 的例子 说 明 6 图1 是由6 个站点两条公交线路构成的公交网 对每一条线路建立一个 直达关系矩阵 d 图1 一个简单的例子 0 b c d e 厂分别表示六个公交车站 实线表示 1 7 号公交线路 虚线表示2号公交线路 假定两条线路都是双向的且来回站点完 全相同 因此使用无向图表示 为了方便 本文中把 o b c d e 厂 分别编号为 e D 一一D 1 2 3 4 5 6 Al 图 1 再 利用 D i j k s t r a 算 法计 算最 短路 得 到每条 线路 的直达 距离 矩阵 1号线路和 2号线路的直达距离矩阵分别为 B 其 中 B B 的每个元素表示乘 1号 2号 线路 的车从第 i 站到第 站走 过 的最短 距离 Bl 0 0 1 2 3 3 2 1 a 0 0 B2 第 2步构 造公 交系统 总 的直达距 离矩 阵 定义取小运算 如下 a b m i n a b 0 0 1 2 3 2 3 1 2 O l 1 0 0 0 0 0 0 O I l l 2 A O 0 O O 0 O 8 2 运 筹 与 管 理 2 0 0 8年 第 l 7卷 利用 取小运算 将所 有线路 对应 的直达距 离矩阵 合成 得 到一个 总 的直达 距离矩 阵 B B B2 B 0 1 1 2 1 0 1 2 1 1 1 2 0 1 1 2 1 1 1 0 3 2 2 2 1 2 3 2 2 2 1 2 0 其 中括 号里的数字表示线路 的编号 如 b 2 1 表示从站点 a到站点 d的直达最短 距离是 2站 需要 乘坐的是 1 路车 第 3步对总 的直达 距离矩 阵使用 Di j k s t r a算法 得到任 意两点之 间 的最 短距离 矩阵 D及最优 路线 本 例 中 D 0 2 2 0 1 1 2 2 2 2 3 3 1 2 1 2 0 1 1 0 1 1 2 2 2 3 2 3 1 2 1 2 0 1 1 0 根据 最短 距离 矩阵 即可确定 经过站点 最少 的乘 车路 线 如本 例 中从 a到 厂 的最 短距 离 是 3 即需 要 走 过 3站路 乘车方案是先做 1站 1 路车 然后在 C 站换乘 2路车 坐2站即可到达 厂 站 如果把各条线路对 应 的直 达关 系矩 阵 中的 1 换 成两 站之 间的实 际距 离 则 用该 方法 可 以得 出任意 两 站之 间 的 实际 距离 最 短 的乘 车方案 1 2 换 乘次 数最 少的线路 选择模 型及算 法 在影响乘客选择公交线路的诸多因素中 换乘次数是最重要的 如果要得到换乘次数最少的线路 我 们只需要把 1 1中公交直达距离矩阵加以修改 即可用 D i j k s t r a 算法得到最少换乘公交 出行线路 修 改方法 将 1 1中矩 阵 曰的非零有 限元 素全部 改 为 1 即得 到公 交 网络 的直 达关 系矩 阵 本例 中 的 直 达关 系矩 阵为 B 对该矩阵使用 D i j k s t r a 算法 即可得到任意两站之问换乘公交车次数最少的乘 车方案 本例中任意 两 站之 间 的乘 坐 车次最 少的矩 阵为 C O 2 2 0 l l 1 2 1 l 2 1 1 1 1 2 0 1 1 0 l 1 1 2 1 2 l 1 1 l 1 2 0 1 1 O 其 中 C 2表示从 a到 厂 乘 坐公 交车 的最少 次数为 2次 换 乘 次数为 2 1 1次 换乘 方案 为 先 从 a 点坐 l 路车到 c 再换乘 2路车坐 2站到 厂 点 或者先从 a 点坐 1 路车到 e 再换乘 2路车坐 1站到 点 1 3 总费 用最少 的线路选 择模 型及算 法 对于把总费用最少作为选择出行路线依据的乘客 必须考虑各条公交线路 的计价方式 目前虽然各 路 公交 车 的票 价计 价方式 不 同 但通 常可分 为单一票 价和分 段计价 两种 不管 哪种方 式 票价 都与路 程直 接相关 因此 我们可以根据各条公交线路的直达距离矩阵和公交线路的计价方式 直接利用票价与路程 的关 系 计 算得 到各 条线路 的直达 票价矩 阵 0 1 2 2 1 2 0 0 O 0 O 第 5期 周文峰 等 最优 公 交线路 选择 问题 的数 学模 型及 算 法 8 3 假设本例中 1 号线路为单一票价 票价为 1 元 2号线路为分段计价 不妨假设 2站以内为 1元 超过 2站 为 2元 则 根据 直达 距离 矩阵 B B 可 以分 别计算 得到 直达 票价矩 阵 P P Pl 再将 直 达票 价矩 阵利用 取小 运算 合成 即可 得到 总的直 达票 价矩 阵 P 1 1 0 0 1 对该 直达 票 价矩 阵利用 D i j k s t r a 算 法 即可求 出任 意两点 之 间 的总 费用 最 少 的乘 车方 案 本 例 中任 意 两 站之 间 的最 小 费用矩 阵 为 Q 0 2 2 0 1 1 l 2 l 1 2 2 1 l 1 2 0 1 1 0 l 1 1 2 l 2 1 2 1 l 1 2 0 l 1 0 其中q 1表示 a到 e 乘坐公交车的最少费用为 1 元 乘车方案为直接乘 1号线路的公交车 不需换乘 1 4 总 时 间最短 的线 路选择 模型 及算 法 出行耗时指乘客在一次出行过程中所需要的总时间 其中包括在车上消耗的时间 在车外换乘以及等 车 的时 间 由于在 车上 消耗 的时 间与公 交车走 行 的距离 有 直接 的关 系 在 车外 消 耗 的 时 间则 与 换 乘次 数 直接相关 因此 在求最优路线时 我们必须把两者结合考虑 为 了简化 问题 我们 假设 同 一条 公 交 线 路上 公 交 车 在 相邻 两 站 之 间 的运 行 时 间 包 括停 站 时 间 相 同 乘客在同一公交车站换乘的时间 包括等车时间 相同 换乘时间不同的情况可以类似处理 为了求 出总时 间最短 的 出行路 线 我 们可 以先将 同一 公交 线路对 应 的直达 距离 矩阵 转换成 直 达时 间矩 阵 再 把不 同线路的直达时间矩阵按照取小运算合成一个总的直达时间矩阵 然后按照下列修改 了的最短路算法计 算任意两点之间的最短通行时间 第 1 步给定直 接 到达时 间矩 阵 f 0 第 2步 构造最多经过一次换乘 即可到达的最短时间矩阵 f mi n 0 t l t o t 其 中 t 表 示 换 乘时 间 第 3步 对 于任 意 k 2 构 造 最 多经过 k一1次换 乘 即可 到 达 的最短 时 间矩 阵 其 中 mi n 一 一 0 直到 T T 即得到任意两个站点之间的最短通行时间矩阵 其中 t 为换乘一次所用的时间 本例中 假设任意两个相邻公交车站之间的平均行驶时间均为 3分钟 公交车换乘耗时 包括等车时 间 为 5分钟 则按照上述方法可以得到两条公交线路的直达时间矩阵分别为 Tl 再将直达时间矩阵利用取小运算合成 即可得到总的直达时间矩阵 6 3 0 0 3 l 0 l l 0 l 2 O I 2 P 0 1 1 1 0 l l 0 1 1 0 l l 0 O l l l 0 2 1 1 1 2 2 l 2 0 O 0 O 1 l 2 0 3 O 3 6 O 3 6 9 O I O 9 6 3 O 6 3 0 3 3 0 3 6 0 8 4 运 筹 与 管 理 2 0 0 8年 第 l 7卷 T 对该 直达 时间矩 阵利用修 改 的 D i j k s t r a算 法 即可求 出任意 两点 之 间 的总 出行 时间 最 短 的乘 车方 案 本 例 中任 意两 站之 间的最少 出行时 间矩阵为 T 0 l l l 1 0 3 3 6 1 1 9 6 1 4 9 6 1 1 3 0 3 l l l 4 9 6 1 l 3 0 其 中 t t 9表示 乘坐公 交车从 a到 e的最 短时间 为 9分钟 乘 车方案 为直接乘 1号线路 的公交 车 不 需换 乘 在实际中 由于等车耗时比较多 所以 当两个换乘点之间只有一站路并且该站路距离又不是很远时 许 多乘客会选 择步行到达下一个换乘 点 以减少 出行时 间并节约 出行费用 因此 在选择 出行路 线 时 应 该 考 虑乘客在某些站点之间步行的情况 这时我们只需要把乘客步行对应的最短时间矩阵列出来 与各条公交线 路对应的最短时间矩阵一起合成 构造总的最短时间直达矩阵 再按照修改的 D i j k s t r a算法即可求出最短时 间 出行方 案 在使用这种方法时 当选择在两站之间步行时 可 以减少一 次换乘机会 因此 应该将 步行对应 的最短距 离矩 阵里的每个非零有 限元素减去一次换乘时间 以便直接使用修改了的最短路算法 1 5 满意 度最大 的线路 选择模 型 以上我们介绍了单纯考虑一种 因素 如换乘次数 距离 时间 费用等 时最优线路 的选择模型及算 法 由于 在人们 实际选 择公交 出行线路 的时候 往往不 止考 虑一 种 因素 比如 人们 通 常会 综