• / 9
  • 下载费用:5 金币  

当前位置:首页>> 理工学论文 >>


邮路规划与邮车调度最优化理论研究.pdf

关 键 词:
邮路 规划 邮车 调度 优化 理论研究
资源描述:
第 38 卷 第 14 期2008 年 7 月数 学 的 实 践 与 认 识M A TH EM A T ICS IN PRA CT ICE AND TH EO R YV o l138 N o114 July, 2008 邮 路 规 划 与 邮 车 调 度 最 优 化 理 论 研 究汤 志 高 1, 王 继 利 2, 曹 颖 瑛 2指 导 教 师 : 曹 华 林 2, 梁 希 泉 1(1. 青 岛 科 技 大 学 数 理 学 院 , 青 岛 266061)(2. 海 军 航 空 工 程 学 院 (青 岛 ) 航 空 机 械 系 , 青 岛 266041)摘 要 : 对 小 规 模 M T SP 问 题 , 建 立 了 可 精 确 求 解 方 案 的 0- 1 规 划 模 型 , 并 在 满 足 邮 政 运 输 需 求 的 前 提 下给 出 了 最 佳 方 案 . 问 题 一 首 先 以 县 支 局 、 县 局 为 顶 点 构 建 无 向 赋 权 图 , 通 过 F loyd 算 法 求 解 各 局 间 的 最 短 距离 ; 然 后 以 F ijk 为 决 策 变 量 , 以 邮 车 工 作 时 间 、 车 辆 运 载 能 力 为 主 要 约 束 , 建 立 以 总 空 载 损 失 费 用 最 小 为 目 标的 021 非 线 性 规 划 模 型 , 运 用 规 划 软 件 L ingo 求 解 . 问 题 二 考 虑 到 市 邮 路 成 本 , 我 们 采 用 分 层 规 划 策 略 , 首先 以 市 支 局 、 县 局 为 顶 点 构 建 无 向 赋 权 图 , 求 解 出 最 短 路 矩 阵 , 建 立 以 邮 路 运 行 成 本 最 小 为 目 标 的 0- 1 非 线性 规 划 模 型 IIA 求 解 ; 然 后 , 建 立 各 县 区 的 最 短 路 矩 阵 , 同 样 建 立 规 划 模 型 IIB 求 解 各 县 运 输 方 案 . 问 题 三 由于 县 局 地 理 位 置 不 变 , 对 区 邮 路 无 影 响 , 故 以 全 市 各 县 支 局 为 中 心 采 用 逐 步 最 优 方 法 对 所 有 县 区 支 局 重 新 划分 ; 然 后 采 用 模 型 IIB 求 解 . 第 四 问 中 考 虑 县 局 迁 移 , 我 们 建 立 近 似 的 启 发 式 算 法 完 成 县 局 选 址 , 并 运 用 规 划模 型 II求 解 的 到 新 方 案 . 最 后 , 我 们 对 两 种 区 域 划 分 调 整 方 法 还 进 行 了 定 量 的 分 析 .关 键 词 : 无 向 赋 权 图 ; 021 非 线 性 规 划1 模 型 假 设收 稿 日 期 : 20082042011) 一 辆 邮 车 仅 负 责 一 条 邮 路 ;2) 一 个 邮 局 的 邮 件 仅 由 一 辆 邮 车 运 送 ;3) 区 、 县 级 邮 车 行 驶 中 皆 以 其 平 均 时 速 65、 30km h 运 行 ;4) 区 级 两 个 班 次 邮 车 的 行 驶 路 线 相 同 , 但 方 向 可 以 不 相 同 .2 符 号 说 明d kq— — 图 中 节 点 k 到 j 的 最 短 路 距 离 ;F ijk— — 表 示 第 i 辆 车 第 j 次 装 卸 邮 件 是 否 在 第 k 个 节 点 ;GQk — — 第 k 个 支 局 寄 出 的 邮 件 总 量 ;GHk — — 寄 达 第 k 个 支 局 的 邮 件 总 量 .3 模 型 3. 1 邮 局 间 最 短 路 径由 于 题 中 仅 提 供 了 两 支 局 间 直 达 距 离 , 但 这 不 一 定 是 最 短 距 离 . 因 此 , 首 先 需 要 利 用F loyd 算 法 把 各 支 局 间 的 最 短 路 径 矩 阵 D 求 出 .3. 2 模 型 分 析邮 车 运 输 时 限 约 束设 第 i辆 车 最 多 经 过 m 个 节 点 , 则 第 i 辆 车 共 在 ∑mj= 1 ∑16k= 1F ijk 个 支 局 进 行 了 装 卸 邮 件 工 作 ,题 中 给 出 邮 车 在 各 支 局 装 卸 邮 件 耗 时 5 分 钟 , 则 第 i辆 车 在 运 输 过 程 中 耗 费 在 各 支 局 装 卸 邮件 的 时 间 为 :T 1 = 560∑mj= 1∑16k= 1F ijk (h)结 合 F ijk 定 义 可 知 , 当 且 仅 当 F ijk 与 F i, j+ 1, q 同 时 为 1 时 表 示 第 i 辆 车 由 支 局 k 到 支 局 q,其 余 情 况 为 不 经 过 .F ijk ı F i, j+ 1, q = 1 第 i 辆 车 经 过 弧 (k, q)0 第 i 辆 车 不 经 过 弧 (k, q)已 知 各 县 级 车 平 均 行 驶 速 度 为 30km h, 以 d kq 表 示 第 k 个 支 局 到 第 j 个 支 局 的 最 短 路 距离 , 则 第 i 辆 车 运 输 途 中 耗 时 为 :T 2 = ∑m - 1j= 1∑17k= 1∑17q= 1d kq30F ijkF i, j+ 1, q (h)第 i 辆 车 邮 运 过 程 总 耗 时 不 超 过 运 输 时 限 (6 小 时 ) 约 束 可 表 示 为 :T 1 + T 2 = 560∑mj= 1 ∑16k= 1F ijk + ∑m - 1j= 1 ∑17k= 1∑17q= 1d kq30 F ijkF i, j + 1, q F 6 (i = 1, … , n) (1. 1)邮 车 运 载 能 力 限 制根 据 问 题 一 要 求 , 每 辆 县 级 邮 车 最 多 容 纳 65 袋 邮 件 , 这 里 实 际 上 限 制 了 两 个 方 面 : 其一 , 每 辆 车 在 出 发 时 装 载 所 要 运 送 的 所 有 邮 件 量 , 而 这 些 邮 件 需 要 在 沿 途 支 局 全 部 卸 下 , 所以 各 车 卸 下 的 邮 件 总 量 不 能 超 过 65 袋 ; 其 二 , 邮 车 在 经 过 支 局 时 卸 下 一 部 分 邮 件 , 同 时 收 取一 部 分 邮 件 , 则 在 每 个 分 局 装 卸 完 成 后 , 各 车 上 所 载 邮 件 数 不 超 过 65 袋 .以 GHk 表 示 寄 达 第 k 个 支 局 的 邮 件 总 量 , 第 i 辆 车 最 多 经 过 节 点 数 为 m , F ijk 表 示 第 i 辆车 第 j 次 装 卸 邮 件 是 否 在 第 k 个 支 局 , 则 第 i 辆 车 在 出 发 时 装 载 的 所 要 运 送 的 所 有 邮 件 量为 :∑mj= 1 ∑16k= 1F ijkGHk邮 车 在 运 输 途 中 不 断 装 卸 邮 件 , 以 GQk 表 示 第 k 个 支 局 寄 出 的 邮 件 总 量 , 则 经 过 第 k 个 支局 时 邮 车 上 邮 件 数 量 变 化 量 为 GQk - GHk , 第 i 辆 车 在 出 发 时 及 运 输 途 中 邮 件 总 量 始 终 不 超 过邮 车 运 载 能 力 (65 袋 ) 约 束 可 表 示 为 :∑mj = 1∑16k= 1F ijkGHk + ∑qj = 1∑16k= 1F ijk (GQk - GHk ) F 65 (q = 1, 2, … ,m ) (1. 2)覆 盖 本 县 内 所 有 支 局设 最 少 需 要 n 量 邮 车 , 第 i 辆 车 最 多 经 过 节 点 数 为 m , F ijk 表 示 第 i 辆 车 第 j 次 装 卸 邮 件是 否 在 第 k 个 支 局 , 则 该 县 级 邮 政 运 输 网 必 须 覆 盖 本 县 内 所 有 支 局 且 仅 覆 盖 一 次 可 表 示 为 :∑ni= 1 ∑mj= 1F ijk = 1 (k = 1, 2, … , 16) (1. 3)各 邮 车 每 次 仅 到 一 个 支 局 装 卸由 于 F ijk 表 示 第 i 辆 车 第 j 次 装 卸 邮 件 是 否 在 第 k 个 支 局 , 则 只 要 经 过 第 k 个 顶 点 则 F ijk= 1 (注 意 , 此 处 经 过 某 一 邮 局 不 一 定 有 邮 件 的 装 卸 工 作 , 可 能 仅 仅 是 路 过 , 则 装 卸 量 为 零 ).202 数 学 的 实 践 与 认 识 38 卷则 对 于 X 1 县 邮 路 图 中 的 17 个 顶 点 而 言 , 第 i 辆 车 第 j 次 仅 到 一 个 邮 局 可 表 示 为 :∑17k= 1F ijk = 1 (i = 1, … , n; j = 1, … ,m ) (1. 4)本 县 邮 车 始 、 终 点 为 X 1由 题 中 关 于 该 区 邮 政 运 输 流 程 的 规 定 , 县 局 X 1 将 邮 件 处 理 后 通 过 县 级 邮 车 将 邮 件 送 往其 县 内 各 支 局 , 同 时 将 各 支 局 需 要 寄 送 的 邮 件 运 回 X 1 进 行 统 一 处 理 后 配 送 , 则 本 县 级 邮 车行 程 的 始 终 点 皆 为 X 1.在 模 型 准 备 中 将 X 1 看 作 图 中 编 号 为 17 的 顶 点 , 设 第 i 辆 车 最 多 经 过 节 点 数 为 m , 则 各邮 车 由 X 1 出 发 并 最 终 回 到 X 1 可 表 示 为 :F i, 1, 17 = 1, F i,m , 17 = 1 (i = 1, … , n) (1. 5)第 一 目 标 : 所 需 邮 车 数 目 最 少根 据 问 题 一 要 求 , 需 求 在 满 足 邮 运 约 束 下 , 最 少 需 要 的 邮 车 数 量 . 所 以 应 以 邮 车 数 量 最少 为 第 一 目 标 , 再 在 最 少 车 辆 数 的 基 础 上 , 以 由 空 载 率 损 失 的 费 用 最 小 为 第 二 目 标 对 邮 路 进行 规 划 及 邮 车 运 输 安 排 .由 于 双 目 标 问 题 实 际 中 不 可 解 , 而 本 问 中 研 究 点 数 较 少 , 所 以 车 辆 数 目 不 会 太 多 , 这 里采 取 将 目 标 一 转 化 为 约 束 的 方 法 求 解 .具 体 方 法 为 : 以 目 标 二 为 目 标 进 行 建 模 编 程 , 在 模 型 中 以 n 表 示 所 需 最 少 车 辆 数 , 再 依次 对 n 赋 值 1, 2, 3, … 令 模 型 可 解 的 最 小 n 值 即 为 所 求 最 小 车 辆 数 .第 二 目 标 : 运 输 效 益 最 大 (由 空 载 率 损 失 的 费 用 最 小 )在 满 足 邮 车 数 量 最 少 的 前 提 下 , 应 尽 量 提 高 运 输 效 益 . 提 高 运 输 效 益 的 方 法 为 尽 量 降 低由 于 空 车 率 而 减 少 的 收 入 , 根 据 题 目 信 息 , 空 车 率 的 计 算 表 达 式 为 :空 车 率 = 邮 车 最 大 承 运 的 邮 件 量 (袋 ) - 邮 车 运 载 的 邮 件 量 (袋 )邮 车 最 大 承 运 的 邮 件 量 (袋 )3. 3 模 型 的 建 立基 于 以 上 分 析 , 以 空 车 率 而 减 少 的 收 入 最 少 为 目 标 , 式 (1. 1)~ (1. 5) 为 约 束 , 建 立 县 邮路 规 划 模 型 如 下 :M in ∑ni= 1 ∑m - 1p = 1(∑17k= 1 ∑17q= 1q≠ kd kqF ip kF i, p + 1, q × 2 (65 - (∑mj= 1 ∑16k= 1F ijkGHk + ∑pj= 1 ∑16k= 1F ijk (GQk - GHk ) ) ) 65)s. t.560∑mj= 1 ∑16k= 1F ijk + ∑m - 1j= 1 ∑17k= 1∑17q= 1d kq30F ijkF i, j+ 1, q F 6 (i = 1, … , n) (1. 1)∑mj= 1 ∑16k= 1F ijkGHk + ∑qj = 1∑16k= 1F ijk (GQk - GHk ) F 65 (q = 1, … ,m ) (1. 2)∑ni= 1 ∑mj = 1F ijk = 1 (k = 1, … , 16) (1. 3)∑17k= 1F ijk = 1 i = 1, … , nj = 1, … ,m (1. 4)F i, 1, 17 = 1; F i,m , 17 = 1 (i = 1, … , n) (1. 5)F ijk ∈ {0, 1}30214 期 汤 志 高 , 等 : 邮 路 规 划 与 邮 车 调 度 最 优 化 理 论 研 究4 模 型 II本 节 主 要 研 究 在 现 有 县 的 划 分 下 , 通 过 对 邮 路 的 规 划 及 邮 车 的 安 排 使 得 总 运 行 成 本 最低 (邮 车 数 目 最 少 、 总 费 用 最 少 ) , 同 时 满 足 时 限 要 求 及 运 输 任 务 要 求 .由 于 区 级 车 一 天 有 2 班 而 县 级 车 一 天 仅 1 班 , 所 以 区 级 车 费 用 远 远 大 于 县 级 , 同 时 , 结 合现 实 中 邮 政 网 的 分 层 构 建 及 管 理 , 应 在 优 先 满 足 区 级 车 数 尽 量 少 、 费 用 尽 量 低 的 前 提 下 , 分层 构 建 区 、 县 两 级 邮 运 网 络 .4. 1 模 型 IIA (区 级 邮 路 )区 级 邮 车 运 输 时 限 约 束当 区 车 仅 经 过 某 支 局 一 次 时 , 均 在 经 过 时 装 卸 邮 件 . 当 区 车 经 过 某 支 局 两 次 (往 返 经 过 )时 , 为 了 延 长 县 级 车 的 运 输 时 间 , 第 一 班 车 在 去 时 不 进 行 装 卸 工 作 而 在 回 时 装 卸 邮 件 ; 第 二班 车 在 去 时 装 卸 邮 件 而 在 回 时 仅 仅 路 过 .当 k = 1, … , 16时 在 各 区 支 局 装 卸 邮 件 , 设 第 i区 辆 车 最 多 经 过 m 个 节 点 , 第 i辆 区 车 共在 ∑mj= 1 ∑16k= 1F ijk 个 支 局 进 行 了 装 卸 邮 件 工 作 , 已 知 邮 车 在 各 支 局 装 卸 邮 件 耗 时 5分 钟 , 则 第 i辆区 车 在 运 输 过 程 中 耗 费 在 各 支 局 装 卸 邮 件 的 时 间 为 :T D1 = 560∑mj = 1∑16k= 1F ijk (h) (i = 1, … , n)当 k = 17, … , 21 时 为 在 各 县 局 (X 1~ X 5) 装 卸 邮 件 , 则 第 i 辆 区 车 共 在 ∑mj= 1∑21k= 17F ijk 个 县局 进 行 了 装 卸 邮 件 工 作 , 已 知 邮 车 在 各 县 局 装 卸 邮 件 耗 时 10 分 钟 , 则 第 i辆 区 车 在 运 输 过 程中 耗 费 在 各 县 局 装 卸 邮 件 的 时 间 为 :T D2 = 1060∑mj = 1∑21k= 17F ijk (h) (i = 1, … , n)已 知 各 区 级 车 平 均 行 驶 速 度 为 65km h, 以 d kq 表 示 区 级 邮 路 图 的 第 k 个 节 点 到 第 j 个 节点 的 最 短 路 距 离 , 且 当 且 仅 当 F ijk 与 F i, j+ 1, q 同 时 为 1 时 表 示 第 i 辆 区 车 经 过 弧 (k, q) , 则 第 i辆 区 车 运 输 途 中 耗 时 为 :T D3 = ∑m - 1j= 1 ∑23k= 1∑23q= 1d kq65 ı F ijk ı F i, j+ 1, q (h) (i = 1, … , n)区 级 邮 车 在 运 输 过 程 中 耗 时 由 在 各 支 局 、 县 局 装 卸 邮 件 耗 时 及 运 输 途 中 耗 时 三 部 分 构成 , 第 i 辆 区 车 邮 运 过 程 总 耗 时 不 超 过 区 级 车 运 输 时 限 (5 小 时 )约 束 可 表 示 为 :T D1 + T D2 + T D3 F 5 (2. 1)区 级 运 输 网 覆 盖 面 约 束根 据 该 地 区 的 邮 政 运 输 规 定 , 区 级 邮 政 运 输 网 必 须 覆 盖 该 地 市 附 近 的 16 个 支 局 和 5 个县 局 , 即 对 于 区 级 邮 路 网 络 中 的 任 一 节 点 而 言 , 至 少 有 一 辆 邮 车 经 过 .设 最 少 需 要 n 量 区 邮 车 , 第 i 辆 区 车 最 多 经 过 节 点 数 为 m , F ijk 表 示 第 i 辆 区 车 第 j 次 是否 经 过 第 k 个 节 点 , 则 该 区 级 邮 政 运 输 网 必 须 覆 盖 该 地 市 附 近 的 16 个 支 局 和 5 个 县 局 可 表示 为 :∑ni= 1 ∑mj= 1F ijk E 1 (k = 1, 2, … , 23) (2. 2)各 区 级 邮 车 每 次 仅 到 一 个 邮 局402 数 学 的 实 践 与 认 识 38 卷对 于 区 级 邮 路 的 23 个 节 点 而 言 , 第 i 辆 车 第 j 次 仅 到 一 个 邮 局 可 表 示 为 :∑23k= 1F ijk = 1, i = 1, 2, … , n; j = 1, 2, … ,m (2. 3)区 级 邮 车 始 、 终 点 为 市 局 D由 于 在 区 级 邮 路 图 中 将 D 抽 象 为 始 点 22及 终 点 23, 则 各 区 级 邮 车 由 D 出 发 并 最 终 回 到D 可 表 示 为 :F i, 1, 22 = 1, F i,m , 23 = 1, i = 1, 2, … , n (2. 4)模 型 ˚ A 的 建 立基 于 以 上 分 析 , 以 所 有 区 级 邮 车 总 运 输 成 本 最 低 为 目 标 , (2. 1~ 2. 4) 为 约 束 , 建 立 区 级邮 路 规 划 模 型 :M in 3 × 2∑ni= 1 ∑m - 1p = 1∑23k= 1 ∑23q= 1q≠ kd kqF ip kF i, p + 1, qs. t.T D1 + T D2 + T D3 F 5 (2. 1)∑ni= 1 ∑mj= 1F ijk E 1 (k = 1, … , 23) (2. 2)∑23k= 1F ijk = 1 i = 1, … , nj = 1, … ,m (2. 3)F i, 1, 22 = 1, F i,m , 23 = 1 (i = 1, … , n) (2. 4)F ijk ∈ {0, 1}4. 2 模 型 ˚ B (县 级 邮 路 )各 县 级 邮 车 运 输 时 限 约 束第 i 辆 县 邮 车 在 运 输 过 程 中 耗 费 在 所 需 覆 盖 的 各 支 局 装 卸 邮 件 的 时 间 为 :T 1 = 560∑mj = 1∑Nk= 1F ijk (h) (i = 1, … , n)已 知 各 县 级 车 平 均 行 驶 速 度 为 30km h, 以 d kq 表 示 县 级 邮 路 图 的 第 k 个 节 点 到 第 j 个 节点 的 最 短 路 距 离 , 得 到 第 i 辆 县 车 运 输 途 中 耗 时 为 :T 2 = ∑m - 1j= 1∑Nk= 1∑Nq= 1d kq30F ijkF i, j+ 1, q (h)以 T 表 示 县 级 车 运 输 的 最 大 时 间 范 围 , 则 :T 1 + T 2 = 560∑mj = 1∑N - 1k= 1F ijk + ∑m - 1j = 1∑Nk= 1∑Nq= 1d kq30 F ijkF i, j+ 1, q F T (i = 1, … , n) (2. 5)县 级 车 运 输 时 限 T 的 确 定由 于 题 中 仅 说 明 第 一 、 二 班 区 级 车 的 路 线 相 同 , 则 可 能 两 班 车 行 驶 方 向 相 同 、 不 相 同 两种 情 况 . 下 面 分 别 分 析 这 两 种 情 况 下 的 T. 为 进 一 步 增 大 县 局 的 运 输 时 间 范 围 , 两 班 区 级 车通 过 市 内 支 局 时 , 在 两 个 班 次 中 只 停 留 一 次 .情 况 1: 区 级 两 班 车 行 走 路 线 方 向 一 致在 极 限 情 况 下 , 为 使 县 级 车 的 运 输 总 时 间 最 大 , 令 第 一 班 车 6: 00 离 开 市 局 到 达 县 局 运输 时 间 为 t1, 第 二 班 车 最 晚 18: 00到 达 市 局 , 令 第 二 班 车 由 该 县 局 到 达 市 局 的 运 输 时 间 为 t2.由 于 第 一 、 二 班 车 沿 同 一 路 线 行 走 , 另 外 加 上 邮 车 在 县 局 停 留 的 10 分 钟 , 得 到 每 一 班 车 的 总50214 期 汤 志 高 , 等 : 邮 路 规 划 与 邮 车 调 度 最 优 化 理 论 研 究时 间 t, 即 :t = t1 + t2 + 1060由 于 县 级 车 出 发 时 在 第 一 班 车 到 达 1 小 时 以 后 , 并 且 在 第 二 班 车 离 开 县 局 时 的 1 小 时 之前 返 回 . 故 县 级 车 的 最 大 运 输 时 间 范 围 满 足 :T F 12 - (t1 + t2 + 2)情 况 2: 区 级 两 班 车 行 走 路 线 方 向 相 反为 使 县 级 车 的 运 输 总 时 间 更 大 , 第 一 班 车 走 最 短 路 到 达 县 局 , 第 二 班 车 沿 反 向 走 远 路 到达 县 局 . 此 时 , 第 一 班 车 由 市 局 到 达 县 局 的 时 间 和 第 二 班 车 离 开 县 局 返 回 市 局 的 时 间 都 为t1. 故 此 时 县 级 车 的 运 输 时 间 满 足 :T F 12 - (2t1 + 2)各 县 的 邮 车 始 、 终 点 为 所 在 县 的 县 局 X i由 题 中 关 于 该 区 邮 政 运 输 流 程 的 规 定 , 各 县 级 邮 车 从 其 所 在 县 局 X i 出 发 将 邮 件 运 送 到其 所 负 责 的 支 局 , 并 将 各 支 局 收 寄 的 邮 件 运 回 X i; 则 县 级 邮 车 行 程 的 始 终 点 皆 为 X i, 各 县 的邮 车 始 、 终 点 为 所 在 县 的 县 局 为 X i 为 :F i, 1, N = 1, F i,m ,N = 1 (i = 1, 2, … , n) (2. 6)模 型 ˚ B 的 建 立基 于 以 上 分 析 , 以 县 级 邮 车 运 输 成 本 最 低 为 目 标 , (2. 2, 2. 3, 2. 5, 2. 8)为 约 束 , 建 立 各 县级 邮 路 规 划 模 型 :M in 3∑ni= 1 ∑m - 1p = 1∑Nk= 1 ∑Nq= 1q≠ kd kqF ip kF i, p + 1, qs. t560∑mj= 1 ∑16k= 1F ijk + ∑m - 1j= 1 ∑Nk= 1∑Nq= 1d kq30 F ijkF i, j + 1, q F T (i = 1, … , n) (2. 5)∑ni= 1 ∑mj= 1F ijk E 1 (k = 1, … ,N ) (2. 2)∑Nk= 1F ijk = 1 i = 1, … , nj = 1, … ,m (2. 3)F i, 1, N = 1, F i,m ,N = 1 (i = 1, … , n) (2. 6)F ijk ∈ {0, 1}5 支 局 归 属 划 分5. 1 县 网 中 支 局 归 属 划 分 的 算 法 与 步 骤在 本 问 中 考 虑 到 部 分 县 与 县 交 界 地 带 的 支 局 , 采 取 就 近 原 则 , 得 到 县 局 行 政 域 规 划 (其中 已 不 包 括 区 级 车 负 责 支 局 ) :Step 1 初 始 化 所 有 县 支 局 , 不 属 于 县 局 X 1~ X 5;Step 2 选 取 一 个 支 局 Z i, 判 断 与 X 1~ X 5 距 离 ;Step 3 若 Z i 离 X j 县 局 距 离 小 于 其 他 县 局 , 则 令 Z i ∈ X j;Step 4 若 所 有 支 局 Z i 已 属 于 X 1~ X 5 结 束 程 序 ; E lse 转 Step 2.602 数 学 的 实 践 与 认 识 38 卷基 于 此 算 法 将 各 县 所 辖 支 局 重 新 规 划 后 结 果 如 下 :表 1 各 县 局 行 政 域 规 划 表X 1 X 2 X 3 X 4 X 5Z 1 Z 17 Z 29 Z 35 Z 45Z 2 Z 18 Z 30 Z 36 Z 46Z 3 Z 19 Z 31 Z 37 Z 47Z 4 Z 20 Z 32 Z 38 Z 48Z 5 Z 21 Z 33 Z 39 Z 49Z 6 Z 22 Z 34 Z 40 Z 50Z 7 Z 23 Z 42 Z 51Z 8 Z 24 Z 43 Z 53Z 11 Z 25 Z 44 Z 54Z 12 Z 26 Z 55Z 13Z 14Z 56Z 57 其 中 已 不 包 括 区 级 车 负 责 支 局6 县 局 最 优 选 址极 限 分 析假 设 整 个 邮 政 网 络 全 部 由 县 级 车 将 各 县 局 和 支 局 的 邮 件 运 送 到 市 局 , 令 此 时 整 个 网 络的 最 短 路 线 长 度 为 L ; 由 于 县 级 车 每 天 只 运 输 一 次 , 此 时 对 应 的 全 部 邮 路 长 度 为 L. 假 设 整 个邮 政 网 络 的 全 部 由 区 级 车 完 成 运 输 任 务 , 则 区 级 车 每 一 班 次 行 走 的 路 线 与 上 一 个 假 设 中 县级 车 的 行 走 路 线 相 同 , 最 短 路 线 长 度 也 为 L. 由 于 区 级 车 每 天 有 两 班 车 , 故 邮 路 总 长 度 为 2L.根 据 极 限 法 分 析 , 为 减 少 邮 路 总 长 度 , 在 确 定 各 个 县 的 县 局 选 址 时 , 应 尽 量 减 少 市 局 到 县 局的 距 离 .启 发 式 算 法根 据 上 述 分 析 可 知 各 县 的 县 局 要 尽 量 靠 近 市 局 . 由 于 区 级 邮 政 网 络 至 少 要 覆 盖 市 局 附近 的 16 个 支 局 , 且 行 每 一 班 车 行 走 线 路 相 同 . 为 尽 量 减 少 区 级 车 的 行 走 路 线 长 度 , 县 局 的 选址 距 离 16 个 支 局 中 最 近 的 支 局 距 离 最 短 .在 保 证 市 局 距 离 县 局 尽 量 近 的 情 况 下 , 为 保 证 各 县 内 的 支 局 到 达 县 局 的 总 线 路 尽 量 短 ,县 局 选 址 尽 量 在 县 区 中 心 , 即 县 局 距 离 最 远 支 局 距 离 最 短 .根 据 上 述 两 种 选 址 原 则 得 到 启 发 : 县 局 选 址 既 要 靠 近 市 区 内 任 意 一 点 的 距 离 尽 量 短 , 又要 尽 量 安 排 在 县 局 中 心 . 为 解 决 这 种 矛 盾 , 由 于 区 级 车 行 走 线 路 对 应 成 本 权 值 是 县 级 车 行 走线 路 对 应 权 值 的 2 倍 , 因 此 将 县 局 选 址 问 题 抽 向 成 如 下 问 题 :将 县 区 和 市 区 内 所 有 邮 局 抽 象 为 点 , 令 某 县 区 内 邮 局 点 数 量 为 m , 市 区 内 的 邮 局 点 数 量为 n, 即 17. 令 县 局 内 第 i 个 点 到 县 区 内 第 j 个 点 的 最 短 距 离 为 d ij (i ≠ j ) , 县 局 内 第 i 个 点 到市 区 内 第 k 个 点 的 最 短 距 离 为 D ij. 县 局 内 第 i 个 点 到 县 区 内 所 有 点 中 最 长 的 距 离 为 S i, 县 局70214 期 汤 志 高 , 等 : 邮 路 规 划 与 邮 车 调 度 最 优 化 理 论 研 究内 第 i 个 点 到 市 区 内 所 有 点 中 最 短 的 距 离 为 S i.为 尽 量 缩 短 县 区 内 区 级 车 的 路 线 长 度 , si 尽 量 取 最 小 值 ; 为 尽 量 缩 短 县 局 到 市 局 的 距离 , S i 尽 量 取 小 值 . 为 确 定 县 局 具 体 位 置 , 根 据 县 级 邮 路 和 市 级 邮 路 对 应 的 成 本 权 值 , 以 si +2S i 最 小 为 确 定 县 局 位 置 的 标 准 . 运 用 搜 索 求 解 的 方 法 求 解 出 各 县 的 县 局 选 址 列 表 2, 针 对新 的 县 局 位 置 , 可 以 调 用 模 型 I I 来 求 解 (只 需 要 改 变 不 同 的 最 短 路 矩 阵 D ).表 2 县 局 选 址 表原 县 局 编 号 X 1 X 2 X 3 X 4 X 5迁 至 支 局 编 号 Z 16 X 2 Z 29 Z 36 Z 527 求 解 分 析模 型 I 直 接 使 用 L ingo 语 言 编 程 , 可 以 得 到 目 标 值 54. 30769 元 (局 部 最 优 解 ).县 局 选 址 、 区 域 归 属 的 合 理 与 否 对 构 建 经 济 、 快 速 的 邮 政 运 输 网 络 起 到 决 定 性 的 作 用 ,通 过 建 模 求 解 可 得 到 如 下 数 据 :严 格 区 域 划 分 松 弛 区 域 划 分总 费 用 (元 ) 总 邮 车 数 总 费 用 (元 ) 总 邮 车 数目 前 县 局 设 置 9549 14 9267 13新 县 局 设 置 8997 14 8667 13由 上 表 四 组 方 案 可 以 看 出 目 前 县 局 设 置 与 区 域 划 分 并 不 十 分 合 理 , 而 最 经 济 的 方 案 应该 是 结 合 问 题 三 与 问 题 四 的 调 整 方 案 , 全 区 最 优 费 用 为 8667 元 .参 考 文 献 :\[ 1 \] 谢 金 星 , 薛 毅 . 优 化 建 模 与 L INDO L IN GO 软 件 [M \]. 清 华 大 学 出 版 社 , 2005, 7.\[ 2 \] D uane H anselm an 著 , 朱 仁 峰 译 . M atlab 7\[M \]. 清 华 大 学 出 版 社 , 2006, 5.Optim ization Theory Research onPost Route and M a il CartTAN G Zh i2gao 1, W AN G J i2li2, CAO Y ing2ying2A dviso r: CAO H ua2lin2, L IAN G X i2quan1(1. D epartm ent of M athem atical, Q ingdao U niversity of Science then develop modelIIB to so lve it. In the fourth p roblem , w e develop app roxim ate heuristic algo rithm to selectaddress fo r county po st offices and develop p rogramm ing models II to get new so lutions. A t theend, w e m ake quantitative analysis about the tw o region division adjusting m ethods.Keywords: U ndirected eigh ted diagram; 0- 1 nonlinear p rogramm ing90214 期 汤 志 高 , 等 : 邮 路 规 划 与 邮 车 调 度 最 优 化 理 论 研 究
展开阅读全文
1
  金牌文库所有资源均是用户自行上传分享,仅供网友学习交流,未经上传用户书面授权,请勿作他用。
0条评论

还可以输入200字符

暂无评论,赶快抢占沙发吧。

关于本文
本文标题:邮路规划与邮车调度最优化理论研究.pdf
链接地址:http://www.gold-doc.com/p-290892.html
收起
展开