搜索

[25727] 2016-11-16_天下武功，唯快不破——快递中的寻路算法

文档创建者：s7ckTeam
浏览次数：2
最后更新：2025-01-19
2016-11-16_天下武功，唯快不破——快递中的寻路算法 - -   周 正 中 0 7 % 1 6 % 2 2 % 3 7 % 4 1 % 5 6 % 6 6 % 6 8 % 7 6 % 8 3 % 8 4 % 天 下 武 功 ， 唯 快 不 破 — — 快 递 中 的 寻 路 算 法 作 者 ： 周 正 中   L i n u x 中 国   2 0 1 6 - 1 1 - 1 6 本 文 将 以 物 流 行 业 为 例 ， 给 大 家 分 析 一 下   P o s t g r e S Q L   与   G r e e n p l u m   在 地 理 位 置 信 息 处 理 ， 最 佳 路 径 算 法 ， 机 器 学 习 等 方 面 的 物 流 行 业 应 用 方 法 。 本 文 导 航 - 物 流 的 要 素 分 析 - 1 .   寄 件 - 2 .   货 物 在 仓 库 之 间 流 转 的 物 流 调 度 - 3 .   货 物 从 终 点 仓 库 到 网 点 的 物 流 调 度 - 4 .   派 件 - 地 址 转 换 成 坐 标 - 路 径 规 划 - 1 .   生 成 拓 扑 - 2 .   生 成 最 佳 路 径 - 支 持 的 内 置 算 法 如 图 - 小 结 前 几 天 双   1 1   下 的 单 ， 都 已 经 收 到 包 裹 了 吧 ？ 为 什 么   2 0 1 6   年 双   1 1   的 快 递 来 得 比 以 往 都 及 时 ？ 今 天 ， 就 来 给 大 家 分 享 一 下 物 流 与 背 后 的 数 据 库 技 术 。 物 流 行 业 是 被 电 子 商 务 催 生 的 产 业 之 一 。 快 件 的 配 送 和 揽 件 的 调 度 算 法 是 物 流 行 业 一 个 非 常 重 要 的 课 题 ， 直 接 关 系 到 配 送 或 揽 件 的 时 效 ， 以 及 物 流 公 司 的 运 作 成 本 。 好 的 算 法 ， 可 以 提 高 时 效 ， 降 低 成 本 ， 甚 至 可 以 更 好 的 调 动 社 会 资 源 。 本 文 将 以 物 流 行 业 为 例 ， 给 大 家 分 析 一 下   P o s t g r e S Q L   与   G r e e n p l u m   在 地 理 位 置 信 息 处 理 ， 最 佳 路 径 算 法 ， 机 器 学 习 等 方 面 的 物 流 行 业 应 用 方 法 。
物 流 的 要 素 分 析 物 流 的 要 素 分 析 物 流 做 的 事 情 很 简 单 ， 寄 件 ， 送 件 （ 但 是 后 面 蕴 藏 着 很 多 高 精 尖 的 黑 科 技 呢 ， 比 如 怎 么 调 度 ， 怎 么 获 得 最 佳 路 径 ） 。 物 流 环 节 的 要 素 有 几 个 ， 都 与 位 置 有 关 。 寄 件 人 揽 件 员 （ 揽 件 人 通 常 不 是 直 接 将 货 收 到 仓 库 ， 而 是 网 点 。 所 以 网 点 到 仓 库 也 是 需 要 调 度 的 ， 本 文 未 涉 及 。 ） 调 度 方 法 与 配 送 差 不 太 多 。 货 物 仓 库 运 输 工 具 派 件 员 收 件 人 我 们 这 里 先 从 简 单 的 入 手 ， 假 设 现 在 只 关 心 位 置 信 息 ， 剖 析 一 下 从 寄 件 到 收 到 包 裹 ， 整 个 过 程 串 起 来 ， 看 看 背 后 的 技 术 。 1 .   寄 件 寄 件 货 物 从 寄 件 人 到 揽 件 员 ， 通 常 是 预 约 的 操 作 ， 而 且 寄 件 人 可 以 直 接 去 网 点 办 理 寄 件 ， 所 以 没 有 太 多 的 算 法 在 里 面 。
如 果 派 件 和 揽 件 混 合 在 一 起 的 话 ， 可 以 用   K N N   算 法 来 解 决 ， 再 结 合 派 件 点 路 径 调 度 ， 选 出 最 佳 的 揽 件 人 。 例 如 ， 寄 件 人 当 前 位 置 ， 与 快 递 员 调 度 的 下 一 个 位 置 ， 进 行   K N N   运 算 ， 因 此   B   来 揽 件 是 成 本 最 低 的 。 2 .   货 物 在 仓 库 之 间 流 转 的 物 流 调 度 货 物 在 仓 库 之 间 流 转 的 物 流 调 度
假 设 上 图 为 仓 库 的 位 置 ， 两 个 仓 库 之 间 如 果 开 通 了 线 路 的 话 ， 就 以 线 段 连 接 起 来 。 每 个 仓 库 负 责 一 个 区 域 ， 这 个 区 域 是 一 个 几 何 的 图 形 。 通 过 寄 件 人 和 收 件 人 的 位 置 ， 与 仓 库 的 区 域 进 行 点 面 判 断 ， 找 出 寄 件 人 的 仓 库 与 收 件 人 的 仓 库 。 快 件 为 点 ， 仓 库 为 面 ， 寄 件 时 根 据 寄 件 人 填 写 的 寄 件 和 收 件 信 息 转 换 为 寄 件 和 收 件 两 个 经 纬 度 ， 通 过 这 两 个 经 纬 度 与 快 递 公 司 的 仓 库 表 进 行 点 面 包 含 的 判 断 匹 配 ， 就 可 以 找 出 快 件 对 应 的 起 点 和 终 点 的 仓 库 。 点 面 判 断 。
有 了 源 和 目 标 就 可 以 通 过   p g r o u t i n g   提 供 的 各 种 最 佳 路 径 算 法 算 出 每 件 货 物 的 最 佳 路 径 。 本 文 后 面 会 有   d e m o   来 讲 解 如 何 使 用   p g r o u t i n g   计 算 最 佳 路 径 。 仓 库 之 间 的 货 车 的 工 作 就 简 单 了 ， 装 满 就 走 或 分 波 次 ( 考 虑 到 时 效 )   的 原 则 ， 负 责 好 两 个 直 连 节 点 的 来 回 运 输 ， 并 不 是 一 辆 车 完 成 整 个 货 物 的 从 起 点 到 终 点 的 运 输 。 例 如 负 责   A   和   B   之 间 线 路 的 货 车 ， 只 在   A B   之 间 跑 运 输 。
3 .   货 物 从 终 点 仓 库 到 网 点 的 物 流 调 度 货 物 从 终 点 仓 库 到 网 点 的 物 流 调 度 货 物 在 抵 达 目 标 仓 库 后 ， 首 先 要 将 货 物 分 拣 到 派 件 的 网 点 。 其 实 也 是 一 个 点 面 判 断 的 过 程 ， 网 点 覆 盖 的 派 件 范 围 为 面 ， 快 件 则 为 点 ， 点 面 判 断 找 出 对 应 的 网 点 。 从 仓 库 到 网 点 ， 也 可 以 使 用 仓 库 建 流 转 的 原 理 ， 计 算 出 最 佳 线 路 。 货 车 只 负 责 2 个 网 点 之 间 的 货 物 流 转 即 可 。 4 .   派 件 派 件 进 入 派 件 的 流 程 ， 也 就 是 货 物 在 抵 达 收 件 人 手 中 的 最 后 一 公 里 要 做 的 事 情 。 为 了 更 好 的 实 现 派 件 调 度 ， 需 要 对 快 件 进 行 聚 合 操 作 ， 根 据 位 置 进 行 聚 合 。 原 理 和 前 面 类 似 ， 还 是 要 做 点 面 判 断 ， 只 是 目 标 更 加 精 确 ， 例 如 精 确 到 小 区 或 者 很 小 的 区 域 。 派 件 除 了 要 考 虑 快 件 的 目 的 地 （ 聚 合 后 的 ） ， 还 需 要 考 虑 快 件 的 体 积 ， 重 量 ， 以 及 快 递 员 的 运 货 能 力 （ 体 积 与 重 量 ）   。 假 设 一 个 网 点 当 前 收 到 的 快 件 覆 盖 了 以 下 需 要 派 送 的 点 （ 聚 合 后 的 ） ， 同 时 每 个 点 的 货 物 体 积 总 和 如 数 字 所 表 示 。 路 径 规 划 与 前 面 不 一 样 的 地 方 ， 这 里 规 划 的 是 多 个 点 作 为 目 标 。
多 点 目 标 的 最 佳 路 径 ， 用 意 是 确 保 相 邻 目 标 的 连 续 性 ， 确 保 切 分 不 同 网 点 的 快 件 后 ， 拿 到 快 件 的 人 跑 的 依 旧 是 相 邻 的 点 。 例 如 中 心 是 网 点 的 位 置 ， 其 他 点 是 目 标 位 置 ， 目 标 位 置 的 数 字 是 体 积 ， 假 设 每 个 快 递 员 一 次 运 输 的 体 积 是   7 0 0 0 ， 虚 线 是 一 个 快 递 员 拿 到 的 一 趟 的 快 件 。 这 种 方 法 确 保 了 每 趟 的 快 件 是 连 续 的 。
多 点 目 标 的 最 佳 路 径 规 划 ， 在 本 文 后 面 的 部 分 也 会 有   D E M O 。 地 址 转 换 成 坐 标 地 址 转 换 成 坐 标 如 何 将 地 址 转 换 成 坐 标 ， 不 在 本 文 的 讨 论 范 围 ， 很 多 做 导 航 的 公 司 都 可 以 输 出 这 个 能 力 。 但 是 作 为 快 递 公 司 ， 还 有 一 种 方 法 可 以 获 得 精 确 的 坐 标 信 息 ， 例 如 快 递 员 的 手 持 G P S 终 端 ， 收 件 时 扫 个 条 码 ， 同 时 上 报 位 置 信 息 。 有 了 一 定 的 基 数 后 ， 通 过 文 本 分 析 和 机 器 学 习 ， 也 可 以 输 出 地 址 转 坐 标 的 能 力 。 如 果 基 数 非 常 庞 大 ， 可 以 选 择 基 于   P o s t g r e S Q L   的   G r e e n p l u m   数 据 仓 库 ， 进 行 文 本 分 析 与 机 器 学 习 ( 支 持   M A D l i b   库 ， 支 持 R ， p y t h o n ， j a v a ) 。 P S ： G r e e n p l u m   支 持 文 本 分 析 ， 支 持 地 理 位 置 信 息 处 理 ， 支 持   M A D l i b   机 器 学 习 库 ， 还 支 持   R   语 言 自 定 义 函 数 ， p y t h o n   函 数 ， 支 持 分 布 式 并 行 计 算 。 最 重 要 的 是 它 开 源 ， 绝 对 是 有 文 本 和 地 理 位 置 分 析 需 求 的 用 户 最 好 的 选 择 。 你 可 以 使 用 熟 悉 的   R 、 P y t h o n 、 J a v a   自 定 义 数 据 库 端 的   U D F ， 满 足 灵 活 的 业 务 需 求 。
路 径 规 划 路 径 规 划 以 仓 库 之 间 的 数 据 流 转 为 例 ： 需 要 用 到   P o s t g r e S Q L   数 据 库 的   P o s t G I S   与   p g r o u t i n g 。 首 先 是 基 础 数 据 的 录 入 ， 即 道 路 数 据 ， 用 来 表 示 开 通 了 运 输 航 线 的 仓 库 之 间 的 线 段 数 据 ， 以 及 线 段 的 属 性 信 息 。 1 .   生 成 拓 扑 生 成 拓 扑 有 了 道 路 信 息 还 不 够 ， 要 生 成 最 佳 路 径 ， 首 先 要 生 成 合 法 的 拓 扑 ， 否 则 怎 么 生 成 路 径 呢 ？ 生 成 拓 扑 前 ， 需 要 添 加 两 个 字 段 ， 用 来 存 储 线 段 的 首 尾 编 号 。 调 用   p g r _ c r e a t e T o p o l o g y   生 成 拓 扑 ， 也 就 是 生 成 线 段 的 首 位 编 号 的 过 程 例 如 ， A B C   三 条 线 段 ， 其 中   B   线 段 的 两 端 都 没 有 和   A C   完 全 吻 合 ， 误 差 分 别 为   1   米 和   1 0   米 ， 所 以 需 要 设 置 容 错 。 生 成 线 段 ， 实 际 上 就 是 设 置   s o u r c e   和   t a r g e t   的   I D ， 设 置 完 后 ， 可 能 就 变 成 这 样 的 了 。  
2 .   生 成 最 佳 路 径 生 成 最 佳 路 径 我 们 知 道 道 路 是 有 坡 度 ， 有 弯 度 的 ， 还 有 颠 簸 程 度 ， 是 否 单 行 线 ， 过 路 费 ， 拥 堵 程 度 ， 怎 么 送 货 效 率 最 高 ， 不 能 只 看 路 程 。 想 象 一 下 你 打 车 去 机 场 的 场 景 ， 如 果 时 间 比 较 紧 的 话 ， 就 要 靠 司 机 了 。 一 个 优 秀 的 出 租 车 司 机 是 会 帮 你 选 择 最 佳 路 径 的 ， 算 上 拥 堵 费 ， 绕 路 其 实 可 能 更 省 。 p g r o u t i n g   支 持 的 最 佳 路 径 算 法 很 多 你 可 以 根 据 不 同 的 算 法 ， 输 入 当 时 每 条 路 段 相 关 的 因 素 （ 例 如 坡 度 ， 弯 度 ， 颠 簸 程 度 ， 是 否 单 行 线 ， 过 路 费 ， 拥 堵 程 度   数 字 化 的   w e i g h t   系 数 ） ， 生 成 最 佳 路 径 。 支 持 的 内 置 算 法 如 图 支 持 的 内 置 算 法 如 图
回复

举报

高级模式
B Color Image Link Quote Code Smilies
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

使用Markdown编辑器编辑 使用富文本编辑器编辑

Archiver| 手机版| 小黑屋|
Powered by Discuz! X3.4 Copyright © 2001-2020, Tencent Cloud. 商业源码建议获取授权，如侵犯您的权益，请联系客服处理