改 进 后 蚁 群 算 法 在 快 件 送 货 中 的 应 用 孙 国 太, 刘 寿 宝 2, 刘 彬 彬 3 4*, 雍 定 钰 (. 中 国 矿 业 大 学 材 料 科 学 与 工 程 学 院, 江 苏 徐 州 226; 2. 中 国 矿 业 大 学 机 电 工 程 学 院, 江 苏 徐 州 226; 3. 中 国 矿 业 大 学 计 算 机 学 院, 江 苏 徐 州 226; 4. 中 国 矿 业 大 学 理 学 院, 江 苏 徐 州 226) 摘 要 : 快 件 送 货 即 快 件 公 司 指 派 业 务 员 给 各 送 货 点 送 货, 以 总 的 送 货 路 径 为 优 化 目 标 的 车 辆 路 径 问 题 可 以 采 用 蚁 群 算 法 等 启 发 式 算 法 求 解, 但 容 易 陷 入 局 部 最 优 过 早 收 敛 该 文 提 出 了 用 2-opt 算 法 进 行 改 进, 对 可 行 解 进 行 组 合 优 化 并 利 用 该 方 法 对 优 化 模 型 进 行 求 解, 得 到 总 路 径 为 294km 的 最 优 送 货 策 略, 证 明 了 该 方 法 求 解 快 件 送 货 问 题 的 实 用 性 和 高 效 性 关 键 词 : 快 件 送 货 ; 车 辆 路 径 ;2-opt; 组 合 优 化 中 图 分 类 号 :O24 Study on the express delvery based on mproved ant colony algorthm Sun Guota, Lu Shoubao 2, LIU Bnbn 3, YONG Dngyu 4 (. School of Materals Scence and Engneerng, Chna Unversty of Mnng and technology, Xuzhou, Jangsu 226; 2. School of Mechatronc, Chna Unversty of Mnng and technology, Xuzhou, Jangsu 226; 3. School of Computer, Chna Unversty of Mnng and technology, Xuzhou, Jangsu 226; 4. School of Scences, Chna Unversty of Mnng and technology, Xuzhou, Jangsu 226) Abstract: The queston of the express delvery s that the express company apponts the clerk to delver goods to the customers, consderng total delvery route as the optmzed goal. we can use heurstc algorthm lke the ant group algorthm and so on to solve t, but t s easy to fall nto local optmzaton and prematurely restranng. Ths artcle proposes the mprovement by the 2-opt algorthm and carres on the combnaton optmzaton of the feasble soluton. And the artcle uses ths method to carry on the soluton to the optmzed model, obtanng the most superor delvery strategy s 294km and provng ths method s usablty and hghly effectve. Key words: the express delvery; Vehcle Routng; 2-opt; combnatonal optmzaton 0 引 言 随 着 电 子 商 务 的 发 展 和 行 业 竞 争 的 日 益 激 烈, 快 递 行 业 已 进 入 微 利 的 时 代, 如 何 优 化 快 递 路 径, 减 少 快 递 成 本 已 成 为 增 加 行 业 竞 争 的 有 力 手 段 [] 快 件 送 货 问 题 本 质 上 是 车 辆 路 径 问 题 车 辆 路 径 问 题 [2], 最 早 是 在 959 年 由 Dantzg 和 Ramser 首 先 提 出 的, 是 指 在 客 户 需 求 和 位 置 已 知 的 情 况 下, 确 定 车 辆 在 各 个 客 户 间 的 行 驶 路 线, 使 得 运 输 路 线 最 短 或 运 输 成 本 最 低 [3] 在 求 解 车 辆 路 径 问 题 的 优 化 算 法 中, 蚁 群 算 法 作 为 一 种 新 兴 的 启 发 式 算 法, 具 有 鲁 棒 性 易 收 敛 并 行 性 等 优 点, 但 经 常 会 出 现 陷 入 局 部 最 优, 收 敛 过 早 等 问 题 本 文 拟 结 合 蚁 群 算 法 和 2-opt 算 法 求 解 这 类 类 送 货 路 线 优 化 模 型, 并 将 其 应 用 到 实 际 的 快 件 送 货 问 题 中 作 者 简 介 : 孙 国 太 (988), 男, 中 国 矿 业 大 学 材 料 科 学 与 工 程 2007 级 本 科 生. E-mal: sgt.730@63.com - -
问 题 描 述 快 件 送 货 是 指 快 件 公 司 派 业 务 员 从 快 件 公 司 给 送 货 点 进 行 送 货, 根 据 各 送 货 点 的 位 置, 确 定 一 个 最 优 的 送 货 策 略, 使 得 总 的 送 货 路 径 尽 量 短 假 设 整 个 快 递 送 货 满 足 以 下 条 件 : () 所 有 业 务 员 以 快 件 公 司 为 起 点 并 最 终 回 到 公 司 总 部 ; (2) 各 送 货 点 的 货 物 一 次 性 送 到 ; (3) 公 司 必 须 满 足 每 个 送 货 点 的 需 求 假 设 m 为 总 共 有 业 务 员 总 数, n 为 送 货 点 总 数, p 为 每 天 公 司 快 件 总 量, q 为 业 务 员 携 带 快 件 的 最 大 重 量,T 为 业 务 员 每 天 工 作 最 长 时 间, t w 为 送 货 员 在 各 个 送 货 点 的 停 留 时 间 ; s 送 货 点 的 快 件 需 求 量, k b 个 送 货 点 到 第 k 个 送 货 点 的 最 短 距 离 ; k 表 示 第 个 为 表 示 第 业 务 员 是 否 从 a 送 货 点 到 k 送 货 点, 表 示 经 过,0 表 示 不 经 过 ; 同 理 表 示 业 务 员 是 否 经 过 送 货 点 [4] 基 于 以 上 的 假 设, 构 建 数 学 模 型 如 下 : mn m () m n n mn s b (2) k k = = k= n = = m n aw q = = m n a = n = = n n n k k = k= = st.. w p (3) (4) (5) ( s b )/ v t* a T (6) 上 述 模 型 中, 式 () 目 标 优 化 最 少 化 业 务 员 数 量 ; 式 (2) 目 标 最 小 化 送 货 路 径 ; 式 (3) 表 示 快 递 公 司 每 天 快 件 总 量 的 约 束 ; 式 (4) 表 示 业 务 员 携 带 快 件 重 量 的 限 制 ; 式 (5) 表 示 送 货 点 数 目 的 约 束 ; 式 (6) 表 示 业 务 员 工 作 时 间 的 约 束 2 改 进 蚁 群 算 法 求 解 快 件 送 货 模 型 2. 基 本 蚁 群 算 法 [5] 蚁 群 算 法 是 受 到 自 然 界 中 蚂 蚁 寻 路 行 为 启 发 而 产 生 的 一 种 具 有 自 适 应 特 征 的 分 布 式 算 法, 是 一 种 随 机 搜 索 算 法 用 蚁 群 算 法 解 决 快 递 公 司 送 货 问 题 时, 假 设 每 个 送 货 点 为 客 户, 蚁 群 算 法 其 实 就 是 模 拟 真 实 蚁 群 的 协 作 过 程, 算 法 由 许 多 人 工 蚂 蚁 共 同 构 成 用 人 工 蚂 蚁 代 替 业 务 员, 每 只 人 工 蚂 蚁 在 候 选 解 的 空 间 中, 独 立 地 搜 索 解, 并 在 所 得 的 解 上 留 下 一 种 称 之 为 信 息 素 的 物 质 进 行 信 息 传 递 解 的 性 能 越 好, 人 工 蚂 蚁 留 在 其 上 的 信 息 量 越 大, 信 息 量 越 大 的 解 被 选 择 的 可 能 性 也 越 大, 因 此, 由 大 量 蚂 蚁 组 成 的 集 体 行 为 便 表 现 出 一 种 信 息 正 反 馈 现 象 在 算 法 的 初 始 阶 段 所 有 - 2 -
解 上 的 信 息 量 是 相 同 的, 随 着 算 法 的 推 进, 较 优 解 上 的 信 息 量 增 加, 算 法 渐 渐 收 敛 每 只 蚂 蚁 是 一 个 独 立 的 用 于 构 造 路 线 的 过 程, 若 干 蚂 蚁 过 程 之 间 通 过 信 息 素 值 来 交 换 信 [6] 息, 合 作 求 解 并 优 化 蚁 群 算 法 求 解 本 问 题 过 程 如 下 : () 首 先 初 始 化, 设 迭 代 次 数 为 NC (2) 将 M 个 蚂 蚁 置 于 仓 库 (3) 构 造 解 每 个 蚂 蚁 按 照 状 态 变 化 规 则 逐 步 地 构 造 一 个 解, 即 生 成 一 条 线 路 此 过 程 蚂 蚁 任 务 是 在 约 束 条 件 下, 访 问 客 户 后 回 到 仓 库, 生 成 一 条 回 路 (4) 局 部 更 新 信 息 素 值 应 用 局 部 信 息 素 更 新 规 则 来 改 变 信 息 素 值 (5) 若 所 有 的 M 个 蚂 蚁 都 构 造 完 解, 则 转 (6); 否 则 转 (3) (6) 全 局 更 新 信 息 素 值 当 所 有 M 个 蚂 蚁 生 成 了 M 个 解, 其 中 有 一 条 最 短 路 径 是 本 代 最 优 解, 将 这 条 路 线 上 的 所 有 弧 相 关 联 的 信 息 素 值 按 固 定 规 则 更 新 (7) 终 止 若 终 止 条 件 满 足, 则 结 束 ; 否 则 NC = NC, 转 (2) 进 行 下 一 代 进 化 终 止 条 件 可 指 定 进 化 的 代 数, 也 可 限 定 运 行 时 间 2.2 蚁 群 算 法 的 改 进 传 统 蚁 群 算 法 尽 管 能 够 分 布 式 并 行 搜 索, 但 在 限 定 的 时 间 或 迭 代 次 数 内 找 到 最 优 解 仍 是 困 难 的, 可 能 找 到 的 只 是 可 行 的 较 优 解, 且 是 经 常 陷 入 局 部 最 优 解, 因 此 本 文 准 备 用 启 发 式 局 部 优 化 方 法 来 改 进 传 统 蚁 群 算 法, 其 中 最 有 效 的 是 2-opt 和 3-opt, 本 文 采 用 2-opt 对 蚁 群 算 法 进 行 局 部 优 化 2-opt 局 部 优 化 算 法 [7], 是 一 种 改 进 型 算 法, 它 以 某 一 解 作 为 初 始 解, 逐 步 迭 代, 优 化 解 下 面 简 单 介 绍 一 下 该 迭 代 思 想 : c = v, v,..., v,...,...,, a) 任 取 初 始 H: 0 2 v vn v ; b) 对 所 有,,< < < n, 若 ( v, v ) dv (, v) dv (, v ) < dv (, v ) dv (, v ) c, 则 在 0 ( v, 中 删 去 边 v ) ( v, v ) 和 而 加 入 边 ( v, v ) c = v, v2,..., v, v, v..., v, v,..., vn, v, 形 成 新 的 H 圈 C, 即, 如 图 所 示 : 和 图 局 部 优 化 算 法 Fg. Local optmzaton algorthm 我 们 在 蚁 群 算 法 中 混 入 2-opt 局 部 优 化 算 法, 对 每 次 迭 代 构 造 的 解 进 行 优 化, 从 而 进 一 步 缩 短 解 路 线 长 度, 以 加 快 蚁 群 算 法 的 收 敛 速 度 将 2-opt 方 法 混 入 蚁 群 算 法 求 解 过 程 中, [8] 对 每 次 迭 代 的 最 优 解 进 行 改 进, 这 样, 在 上 述 求 解 过 程 (5) 与 (6) 之 间 加 入 以 下 2-opt 方 法 对 传 统 蚁 群 算 法 最 优 解 进 行 改 进 Repeat - 3 -
Modfed_route:=apply_2opt_move(current_route) If length(modfed_route)<length(current_route) Then current_tour:=modfed_tour Untl no further mprovement or a specfed number of teratons 其 中 的 current_tour 是 某 业 务 员 从 公 司 出 发 送 货 后 又 回 到 公 司 的 路 线 3 实 例 分 析 假 设 快 件 公 司 的 坐 标 为 (0,0), 表 为 各 送 货 点 坐 标 数 据, 每 名 业 务 员 的 最 大 携 带 量 为 25kg, 每 个 业 务 员 的 最 大 工 作 时 间 6h 为 公 司 制 定 一 个 合 理 的 送 货 策 略, 使 得 业 务 员 的 总 路 径 最 短 表 送 货 点 数 据 Tab. Delvery pont data 送 货 点 坐 标 (km) 快 件 量 T 送 货 点 坐 标 (km) 快 件 量 T (3,2) 8 6 (2,6) 3.5 2 (,5) 8.2 7 (6,8) 5.8 3 (5,4) 6 8 (,7) 7.5 4 (4,7) 5.5 9 (5,2) 7.8 6 (0,8) 3 20 (7,4) 4.6 5 (3,) 4.5 2 (22,5) 6.2 7 (7,9) 7.2 22 (2,0) 6.8 8 (9,6) 2.3 23 (27,9) 2.4 9 (0,2).4 24 (5,9) 7.6 0 (4,0) 6.5 25 (5,4) 9.6 (7,3) 4. 26 (20,7) 0 2 (4,6) 2.7 27 (2,3) 2 3 (2,9) 5.8 28 (24,20) 6 4 (0,2) 3.8 29 (25,6) 8. 5 (9,9) 3.4 30 (28,8) 4.2 假 设 道 路 是 与 坐 标 轴 平 行 的, 所 以 各 需 求 点 之 间 以 及 各 需 求 点 与 配 送 中 心 的 送 货 路 径 计 算 公 式 为 : s = x x y y 分 别 利 用 传 统 蚁 群 算 法 和 改 进 后 蚁 群 算 法 进 行 多 次 求 解, 得 到 如 下 表 2 的 解 传 统 蚁 群 算 法 表 2 业 务 员 送 货 总 的 路 径 (km) Tab.2 The total delvery salesman path (km) 改 进 后 蚁 群 算 法 304 308 306 300 300 304 300 296 294 304 32 308 308 300 304 296 300 294 300 298 从 表 2 可 以 看 出 改 进 前 蚁 群 算 法 的 最 优 解 为 300km, 最 差 解 为 32km 改 进 后 蚁 群 算 法 的 最 优 解 为 294km, 最 差 解 为 304km, 可 见 改 进 后 的 蚁 群 算 法 得 到 的 送 货 路 径 更 短 以 下 是 最 优 解 (294km) 的 业 务 员 线 路 图, 及 对 应 改 进 后 蚁 群 算 法 的 仿 真 结 果 图 - 4 -
图 2 业 务 员 送 货 线 路 图 Fg.2 Salesman delvery route map 图 3 改 进 后 蚁 群 算 法 仿 真 图 Fg.3 Improved ant colony algorthm for smulaton of Fgure 4 结 束 语 本 文 采 用 了 2-opt 局 部 优 化 改 进 传 统 蚁 群 算 法, 来 求 解 快 件 送 货 路 径 优 化 问 题 从 实 验 结 果 可 以 看 出 : 与 传 统 的 蚁 群 算 法 相 比 较, 改 进 后 的 算 法 得 到 更 优 的 送 货 策 略 随 着 送 货 点 数 目 的 扩 大, 在 路 线 优 化 和 效 率 方 面 额 优 势 更 加 明 显 [ 参 考 文 献 ] (References) [] 陈 丽 芳, 须 方 波. 混 合 行 为 蚁 群 算 法 在 快 递 路 径 优 化 中 的 应 用 [J]. 计 算 机 工 程 与 应 用,2009,45(22): 228-229. [2] 刘 北 林, 高 爽. 配 送 车 辆 路 径 优 化 问 题 算 法 研 究 [J]. 商 业 经 济,2008,(9):3-34 [3] 荣 海 涛, 宁 宣 熙. 改 进 蚁 群 算 法 在 公 路 煤 运 路 径 选 择 中 的 应 用 [J]. 计 算 机 工 程 与 应 用,2009,45(2): 239-24. [4] 何 小 年, 谢 小 良. 带 装 载 量 约 束 的 物 流 配 送 车 辆 路 径 优 化 研 究 [J]. 计 算 机 工 程 与 应 用, 2009,45(34): 236-238. [5] 谢 民, 高 利 新. 蚁 群 算 法 在 最 优 路 径 规 划 中 的 应 用 [J]. 计 算 机 工 程 与 应 用,2008,44(8):245-247. [6] 徐 锋, 杜 军 平. 改 进 蚁 群 算 法 在 旅 游 路 线 规 划 中 的 应 用 研 究 [J]. 2009,45(23):93-95. [7] 王 斌, 尚 新 春, 李 海 峰. 解 决 车 辆 路 径 问 题 的 混 合 模 拟 退 火 算 法 [J]. 计 算 机 工 程 与 设 计,2009,30(3): 65-652. [8] 尹 晓 峰, 刘 春 煌, 张 惟 皎. 基 于 MATLAB 的 混 合 型 蚁 群 算 法 求 解 车 辆 路 径 问 题 [J]. 计 算 机 工 程 与 应 用, 2005,4(35):207-209. - 5 -