空领域 ， Ａｎ ｂ ｉ ｌ 等［ ， Ｗｅ ｄ ｅ ｌ ｉ ｎ ［ ， Ａｈ ｍａ ｄ Ｂ ｅ ｙ ｇ ｉ 等［ 。 ］ 将
关键词 ：城市轨道交通 ；乘务任务 配对 ；集合 分割 问题 ； 列
生成思想 ； 跟 随分 支策 略
中 图分 类 号 ： Ｕ２ ９ ３ ． ５ 文 献标 志 码 ： Ａ
Ａｂ ｓ ｔ ｒ ａ ｃ ｔ ：Ａ ｓ ｅ ｔ ｐ ａ ｒ ｔ ｉ ｔ ｉ ｏ ｎ ｍｏ ｄ ｅ ｌ（ Ｒ— Ｃ Ｐ）ｆ ｏ ｒ ｔ ｈ ｅ ｃ ｒ ｅ ｗ ｐ ａ ｉ ｒ ｉ ｎ ｇ
ｐ ｒ ｏ ｂ ｌ ｅ ｍ ｉ ｎ ｕ ｒ ｂ ａ ｎ ｒ ａ ｉ ｌ ｔ ｒ ａ ｎ ｓ ｉ ｔ ｗａ ｓ ｐ ｒ ｏ ｐ ｏ ｓ ｅ ｄ ｂ ａ ｓ ｅ ｄ ｏ ｎ ｐ ｒ ａ ｃ ｔ ｉ ｃ ａ ｌ ｃ ｏ ｎ ｓ ｉ ｄ ｅ ｒ ａ ｔ ｉ ｏ ｎ ｓ ｉ ｎ ｒ ａ ｉ ｌ ｔ ｒ ａ ｎ ｓ ｉ ｔ ｏ ｐ ｅ ｒ ａ ｔ ｉ ｏ ｎ ｓ ．Ａ ｈ ｙ ｂ ｒ ｉ ｄ ａ ｌ ｇ ｏ ｒ ｉ ｔ ｈ ｍ ｏ ｆ
第４ ３卷 第 ２ 期
２ ０ １ ５年 ２月
同 济 大 学 学 报（ 自然 科 学 版） Ｊ Ｏ Ｕ Ｒ Ｎ Ａ Ｌ Ｏ Ｆ Ｔ Ｏ Ｎ Ｇ Ｊ Ｉ Ｕ ＮＩ Ｖ Ｅ Ｒ Ｓ Ｉ Ｔ Ｙ （ Ｎ Ａ Ｔ Ｕ Ｒ Ａ Ｌ Ｓ Ｃ Ｉ Ｅ Ｎ Ｃ Ｅ ）
Ｖｏ １ ． ４ ３ Ｎｏ ． ２
乘务 任 务 配 对 问 题 归 纳 为 集 合 分 割 问 题 （ ｓ ｅ ｔ
ｐ ａ ｒ ｔ ｉ ｔ ｉ ｏ ｎ ｐ ｒ ｏ ｂ ｌ ｅ ｍ， Ｓ Ｐ Ｐ ） ， 并分 别采 用分 支定 界法 、 分 支裁 剪 法 和 动 态 规 划 法 进 行 求 解 ； Ｂ ｅ ａ ｓ ｌ ｅ ｙ ｌ ４ Ｊ ， Ａｙ ｄ ｅ ｍｉ ｒ － Ｋａ ｒ ａ ｄ ａ ｇ等［ ５ ］ ， Ｓ ｏ ｕ ａ ｉ 等ｌ ６ ］ 则将 问题 归 纳 为 集合 覆盖 问题 （ ｓ ｅ ｔ ｃ ｏ ｖ ｅ ｒ ｉ ｎ ｇ ｐ ｒ ｏ ｂ ｌ ｅ ｍ， Ｓ Ｃ Ｐ ） ， 并 分 别 采用 拉 格 朗 日次 梯 度算 法 、 组 合 优 化 算 法 和遗 传 算 法进 行求解 ． 航 空乘 务任 务配 对研 究 成 熟 ， 但 与城 轨
１ 问题 描 述 与 建 模
１ ． １ 问题 描述
轮换点 ２一 用餐点 一 出退勤点 一 轮换点 卜
乘 务计 划 主要 包 括 两个 部 分 工 作 ： 乘 务 任 务 配
对 和乘 务任 务 轮转． 其 中， 乘 务任 务 配对 指 将 给 定 的
列 车运行 计 划 （ 即运 行 图 ） 配对成若干乘务任务 ， 每 个 乘 务 任务 由 １ 个乘务员一天完成 ； 乘 务 任 务 轮转
城 轨乘 务任 务 配对 主要 涉点 、 用 餐点 、 任务 段 和乘 务 任务 ． 出退 勤 点 指 乘 务 员 出 勤 和退 勤 的车 站 ， 轮 换 点 指 乘 务 员 中途下 车 轮换 休息 的 车站 ， 用 餐 点指 乘 务员 用 餐 的车 站． 出 退 勤点 、 轮转 点 、 用餐 点均 为允 许 乘 务员 下 车 停 留 的
摘要 ： 基于城轨乘务值乘 规则 ， 建立 了城轨乘务 任务 配对 的
任务 配对 的工 作难度 越来 越 大 ， 且编 制 质 量低 ． 设 计
集合分割模型 （ Ｒ － Ｃ Ｐ ） ， 并结合列 生成思想 和跟随分支策略设 高 效 的乘 务 任 务 配 对 模 型 及 算 法 成 为 亟 需 解 决 的 计了求解算法 （ Ｃ Ｇ Ｂ Ｆ算法 ） ． 实例验证结果表 明 ： 该模 型与算 问题．
指 按照 特定 的 轮 转 制度 （ 四班 两转 、 五班三转等） 安 排 乘 务 员 的阶段 任 务． 乘 务任 务 配对 为 乘 务 任 务 轮
图 ２ 乘 务 任 务 示 意 图
Ｆｉ ｇ． ２ Ｓ ｋｅ ｔ ｃ ｈ ｏ ｆ ｃ ｒ ｅ ｗ ｐ ａ ｉ ｒ ｉ ｎ ｇ
转 的基 础 ， 本文 研究 重点 为乘 务任 务配对 问题．
Ｓ ＨＩ ｄ ｕ ｎ ｇ ａ ｎ ｇ，Ｚ ／ － ／ Ｏ Ｕ Ｆ ｅ ，ＸＵＲ¨ｉ ｈ ｕ ａ
（ Ｋｅ ｙ Ｌ ａ ｂ ｏ ｒ ａ ｔ ｏ ｒ ｙ ｏ ｆ Ｒｏ ａ ｄ ａ ｎ ｄ Ｔｒ ａ ｆ ｆ ｉ ｃ Ｅｎ ｇ ｉ ｎ ｅ ｅ ｒ ｉ ｎ ｇ ｏ ｆ ｔ ｈ ｅ Ｍｉ ｎｉ ｓ ｔ ｒ ｙ ｏ ｆ
Ｆ ｅ ｂ．２ Ｏ １ Ｓ
文 章 编 号 ：０ ２ ５ ３ — ３ ７ ４ Ｘ （ ２ ０ １ ５ ） ０ ２ — ０ ２ ３ ２ — ０ ７
城 轨 交通 乘 务 任务 配对 的集 合 分 割模 型及 算 法
石俊 刚 ， 周 峰 ， 徐 瑞 华
（ 同 济 大学 道 路 与 交 通 工 程 教 育 部重 点 实验 室 ， 上海 ２ ０ １ ８ ０ ４ ）
核心． 目前 ， 我 国城轨 乘务任 务 配对 基 本采 用 人 工编
本 文 以城轨 乘务 任 务 配 对 为研 究 对 象 ， 以提 高
制， 且 随着 列 车 发 车 间 隔缩 短 ， 运 营 时 间增 长 ， 乘 务 乘务 任务 配对 的质 量 、 效 率及 合 理性 为 目标 ， 建 立 乘
以上 约 束 大 多 为范 围约 束 ， 加 之 城 轨发 车 间隔 短， 约束 范 围内任 务段之 间 组合 情况 多 ， 因此乘 务 任
务数量 巨大． 一 般任 务段 数量 在 ５ （ ） （ ） ～２ ０ ０ ０ ， 任务 数 量在 １ ０ ～１ ０ 。 ． 如 何获 取所 有 可能 的组 合 任务 ， 如 何 获取最 优 的乘务 任务 配对 方 案并 提 高求 解效 率 是 建 模 和设 计 算法 的 目标 ．
优 化程 度有 限 ； 石 俊刚 等ｌ ｌ ４ ］ 结 合乘务 劳 动作息 规则 ，
建 立 了相应 的 Ｓ Ｃ Ｐ模 型 ， 并 结合 列生 成 思 想 设 计 了 乘务 计划 编制是 城 市轨 道交 通 （ 以下 简称 城 轨 ） 算法， 优 化 效果 较 好 ， 但 不 能 避 免 随乘 现 象 （ 随 乘 现
收稿 日期 ：２ ０ １ ４ — ０ ８ — ０ ６ 基金项 目：国家 自然科学基金 （ ７ １ ２ ７ １ １ ５ ３ ， ５ １ ４ ０ ８ ３ ２ ３ ） ； 中国博士后科学基金 （ ２ ０ １ ４ Ｍ５ ５ １ ４ ５ ４ ） ； 浙江省 自然科 学基金 （ Ｌ Ｑ１ ３ Ｇ０ １ ０ ０ １ ０ ） 第 一 作 者 ：石 俊 刚 （ １ ９ ８ ６ 一） ， 男， 博士生 ， 主 要 研 究方 向 为 城轨 乘 务 计 划 优 化 编 制 方 法 ． Ｅ － ｍａ ｉ ｌ ： １ ０ ２ ０ １ ２ ０ １ １ ２ ＠ｔ ｏ ｎ ｇ ｊ ｉ ． ｅ ｄ ｕ ． ｃ ｎ 通讯作 者：徐瑞华（ １ ９ ６ ３ 一） ， 男， 教授 ， 博士生导师 ， 工学博士， 主要研 究方 向为运输组织现代化． Ｅ － ｍａ ｉ ｌ ： ｒ ｈ ｘ ｕ ＠ｔ ｏ ｎ ｇ Ｓ ｉ ． ｅ ｄ ｕ ． ｃ ｎ
Ｓ ｅ ｔ Ｐａ ｒ ｔ ｉ ｔ ｉ ｏ ｎ Ｍｏ ｄ ｅ ｌ ａ ｎ ｄ Ａ ｌ ｇ ｏ ｒ ｉ ｔ ｈ ｍ ｆ ｏ ｒ Ｃｒ ｅ ｗ Ｐ ａ ｉ ｒ ｉ ｎ ｇ Ｐｒ ｏ ｂ ｌ ｅ ｍ ｉ ｎ Ｕｒ ｂ ａ ｎ Ｒａ ｉ ｌ Ｔ ｒ ａ ｎ ｓ ｉ ｔ
系统 工程 （ Ｓ Ｅ） 方法 、 蚁群算法 、 分 支 定 界 法 进 行 求 解． 高 铁乘 务任 务配 对虽然 与 城轨 相 似 度较 高 ， 但 城 轨发 车密 度 大 ， 轮换点多， 求解复杂度高， 因此 其 模 型 与算法 难 以适用 ． 城轨 领域 ， 刘德 利［ １ ］ 对 乘务 值乘 方式 进行 了探 讨 ； 李献 忠等 Ｌ ｌ ３ ｌ 构 建 了基 于 广 义 费用 的乘务 排班模 型 ， 并设计 采 用禁 忌搜 索 算 法求 解 ， 但
其 中 １名 乘 务 员 乘 务 管 理 的重 要 工 作 ， 良好 的乘 务 计 划 既 能保 证 乘 象 指 ２个乘 务 员 同时 驾驶 一 列 车 ， 务员 之 间 工作 的均 衡 性 ， 又 能 保证 乘 务 员 的驾 车效 担任 司 机 ， 另 １名 乘 务 员 以乘 客 身 份 随乘 前 往 目的 率 和 安 全性 ， 其 中乘 务 任 务 配 对是 乘 务 计 划 编制 的 地 ） ， 存 在缺 憾．
法能够满足乘 务 任务 配对 方 案 的要求 ， 相对 于 当前 手 工编
制， 具有编制效率 高 、 目标 函 数 更 优 （ 即任 务数 量少 、 任 务 工 作效率高） 等特点．
国内外 在乘务 任务 配对 问题 的研究 主要 集 中在 航 空和 高铁领 域 ， 城 轨领 域 的研 究成 果 相 对 较少 ． 航
ｐ ａ ｉ ｒ ｉ ｎ ｇ ａ ｎ ｄ ｙ ｉ ｅ ｌ ｄ ｂ ｅ ｔ ｔ ｅ ｒ ｏ ｂ ｊ ｅ ｃ ｔ ｉ ｖ ｅ ｖ ａ ｌ ｕ ｅ ｓ ｔ ｈ ａ ｎ ｔ ｈ ｅ ｅ ｘ ｉ ｓ ｔ ｉ ｎ ｇ
ｍａ ｎ ｕ ｔ ｌ ａ 】 ｍｅ ｔ ｈ ｏ ｄ ｓ ．
Ｋｅ ｙ ｗｏ ｒ ｄ ｓ ：ｕ ｒ ｂ ａ ｎ ｒ ａ ｉ ｌ ｔ ｒ ａ ｎ ｓ ｉ ｔ ｃ ｒ ｅ ｗ ｐ ａ ｉ ｒ ｉ ｎ ｇ ｐ ｒ ｏ ｂ ｌ ｅ ｍ；ｓ ｅ ｔ
ｐ ａ ｒ ｔ ｉ ｔ ｉ ｏ ｎ ｐ ｒ ｏ ｂ ｌ ｅ ｍ；ｃ ｏ ｌ ｕ ｍｎ ｇ ｅ ｎ ｅ ｒ ａ ｔ ｉ ｏ ｎ；ｂ ｒ ａ ｎ ｃ ｈ ｏ ｎ ｆ ｏ ｌ ｌ ｏ ｗ— ｏ ｎ ｓ
在 乘务值 乘规 则 、 运 营模式 等方 面 差异 较 大 ， 难 以完
全借 鉴 ． 高铁 领域 ， 夏平 等ｌ ７ ］ 构建 了乘 务任 务 配 对 的 多 目标 规 划 模 型 ， 并 设 计 回溯 搜 索 策 略 求 解 ； 程 岩
Ｅ ｄ ｕ ｃ ａ ｔ ｉ ｏ ｎ ， Ｔｏ ｎ ｇ ｊ ｉ Ｕｎ ｉ ｖ ｅ ｒ ｓ ｉ ｔ ｙ 。 Ｓ ｈ ａ ｎ ｇ ｈ ａ ｉ ２ ０ １ ８ ０ ４ ， Ｃ ｈ ｉ ｎ ａ ）