D2Park: Diversified demand-aware on-street parking guidance
计 算 机 与 大 数 据 学 院 Fuzhou University D 2 Park: Diversified demand-aware on-street parking guidance 论 文 出 处 ： Proceedings of the ACM on Interactive, Mobile, Wearable and Ubiquitous Technologies 发 表 时 间 ： 2020 作 者 ： 汇 报 人 ： 邱 添 立 日 期 ： 2023-08-02 D 2 Park: 多 样 化 需 求 感 知 的 街 道 停 车 引 导
1.摘要
1. 摘 要 为 了 解 决 日 益 严 重 的 停 车 问 题 ， 并 且 “ 多 车 竞 争 同 一 车 位 ” 的 现 象 仍 然 存 在 ， 尤 其 是 在 路 边 停 车 。 现 有 的 基 于 预 约 的 资 源 分 配 方 案 可 以 在 一 定 程 度 上 解 决 停 车 竞 争 问 题 ， 但 将 所 有 停 车 位 都 视 为 可 预 约 资 源 是 不 现 实 的 。 本 文 首 先 识 别 出 不 同 的 停 车 需 求 ， 包 括 预 约 用 户 ， 普 通 用 户 ， 外 部 用 户 。 为 此 ， 本 文 设 计 的 系 统 ， 提 供 多 样 化 的 需 求 感 知 停 车 引 导 服 务 。 系 统 主 要 采 用 两 个 模 块 :1) 多 步 停 车 预 测 ， 根 据 当 前 停 车 事 件 数 据 和 外 部 因 素 ， 进 行 占 用 率 预 测 ;2) 多 样 化 停 车 引 导 ， 结 合 了 基 于 合 作 和 基 于 竞 争 的 资 源 分 配 机 制 ， 实 现 了 不 同 用 户 群 体 之 间 更 好 的 性 能 平 衡 。
2.引言
2. 引 言 城 市 停 车 难 的 问 题 是 由 车 辆 数 量 的 增 加 和 停 车 位 的 有 限 造 成 的 。 一 项 调 查 显 示 ， 纽 约 的 驾 驶 员 平 均 每 年 花 费 107 个 小 时 寻 找 停 车 位 ， 这 会 浪 费 时 间 、 燃 料 和 排 放 。 现 有 的 停 车 应 用 程 序 提 供 有 关 停 车 可 用 性 、 价 格 和 距 离 的 信 息 。 然 而 ， 将 所 有 车 位 视 为 可 预 留 资 源 是 不 现 实 的 。 有 必 要 考 虑 到 很 多 用 户 只 是 临 时 使 用 ， 没 有 预 约 。 本 文 考 虑 了 一 个 更 现 实 的 停 车 场 景 ， 一 部 分 停 车 位 可 被 预 约 ， 如 果 没 被 预 约 ， 则 可 被 其 他 用 户 使 用 。 系 统 中 有 三 类 用 户 : 预 约 用 户 ， 以 预 约 费 为 代 价 请 求 有 保 证 的 车 位 ; 普 通 用 户 ， 以 “ 尽 最 大 努 力 ” 提 供 无 保 证 的 车 位 。 外 部 用 户 ， 他 们 不 发 送 任 何 请 求 ， 直 接 开 车 到 目 的 地 附 近 的 街 道 停 车 。 通 过 综 合 考 虑 预 约 用 户 和 正 常 用 户 的 实 时 请 求 以 及 所 有 用 户 未 来 的 不 确 定 需 求 ， 实 时 做 出 分 配 决 策 并 动 态 更 新 。
3.模型概述
3. 模 型 概 述 有 两 个 预 约 用 户 𝑢 1 和 𝑢 2 ， 他 们 各 自 的 目 的 地 𝑑 1 和 𝑑 2 。 有 两 个 候 选 街 区 𝑠 1 和 𝑠 2 ， 这 两 个 街 区 都 只 剩 下 一 个 停 车 位 。 虽 然 𝑢 2 在 𝑢 1 之 前 到 达 𝑠 1 ， 但 合 作 机 制 会 将 𝑢 1 分 配 到 𝑠 1 ， 𝑢 2 分 配 到 𝑠 2 。 这 是 因 为 该 解 决 方 案 的 总 体 成 本 较 低 ， 𝑐 11+ 𝑐 22=17 ， 而 另 一 种 替 代 方 案 ( 𝑐 21+ 𝑐 12=18 ) 。 对 于 这 两 个 普 通 用 户 ， 竞 争 机 制 根 据 先 到 先 服 务 ， 优 先 将 s1 推 荐 给 u2 ， 并 将 另 一 个 街 道 推 荐 给 u1 ， 以 避 免 冲 突 。 但 由 于 外 部 用 户 的 存 在 ， 普 通 用 户 仍 有 可 能 无 法 停 车 。 因 此 推 荐 了 一 系 列 的 街 道 ， 这 样 可 以 在 多 次 尝 试 后 最 小 化 预 期 的 总 停 车 成 本 。 如 图 6 所 示 ， 优 先 推 荐 s1 给 u2 ， 若 s1 无 余 位 ， 推 荐 s2 。 同 时 推 荐 [s2,s3] 给 u1 。
3.模型概述
3. 模 型 概 述 (i) 对 于 每 个 预 约 用 户 ， 服 务 器 首 先 将 其 放 入 等 待 队 列 中 ， 直 到 下 一 个 决 策 时 点 。 如 果 用 户 被 分 配 车 位 ， 则 进 入 预 约 队 列 中 ， 到 达 当 前 分 配 的 位 置 之 前 ， 仍 然 有 机 会 在 以 后 的 决 策 时 段 获 得 一 个 更 好 的 位 置 。 车 位 被 分 配 时 ， 该 停 车 位 的 状 态 将 为 预 约 ， 以 保 证 其 他 用 户 没 有 使 用 该 停 车 位 的 权 限 。 这 样 ， 预 留 用 户 在 每 个 决 策 时 段 都 能 得 到 停 车 成 本 的 上 界 保 证 ， 且 随 着 到 目 的 地 距 离 的 减 小 ， 停 车 成 本 逐 渐 降 低 。 (ii) 对 于 每 个 普 通 用 户 ， 可 能 需 要 多 次 尝 试 才 能 成 功 停 车 ， 因 为 当 用 户 到 达 时 ， 推 荐 的 街 道 可 能 已 经 没 有 空 位 了 。
3.模型概述-多步预测
3. 模 型 概 述 - 多 步 预 测 结 合 GCN 和 LSTM ， 以 同 时 捕 获 空 间 和 时 间 相 关 性 。 时 空 组 件 ： 利 用 GCN 以 提 取 高 阶 空 间 信 息 ， 然 后 通 过 LSTM 层 捕 获 时 间 相 关 性 ; 时 间 组 件 : 将 时 变 天 气 特 征 序 列 输 入 LSTM; 外 部 组 件 : 将 不 含 时 间 和 空 间 信 息 的 数 据 ， 即 局 部 事 件 和 节 假 日 ， 输 入 前 馈 神 经 网 络 ; 融 合 组 件 : 利 用 融 合 层 将 前 三 个 组 件 输 出 的 所 有 特 征 进 行 聚 合 ， 并 采 用 多 层 前 馈 网 络 的 解 码 器 输 出 所 有 街 区 预 测 的 占 用 率 或 流 入 量 。
3.模型概述-普通用户引导
3. 模 型 概 述 - 普 通 用 户 引 导 单 普 通 用 户 需 求 感 知 引 导 算 法 (DG-SN) 首 先 考 虑 只 有 一 个 普 通 用 户 的 简 单 情 况 ， 然 后 将 其 扩 展 到 多 个 普 通 用 户 的 情 况 。 假 设 任 何 用 户 最 多 可 以 在 尝 试 m 后 成 功 停 车 , 问 题 的 目 标 是 最 小 化 m 次 决 策 的 预 期 停 车 成 本
3.模型概述-普通用户引导
3. 模 型 概 述 - 普 通 用 户 引 导 多 普 通 用 户 竞 争 需 求 感 知 引 导 算 法 (DG-MNC ) 为 适 应 多 正 常 用 户 的 情 况 ， 需 要 根 据 多 用 户 信 息 修 改 竞 争 概 率 ， 是 修 正 因 子 这 些 𝛽 的 普 通 用 户 中 可 能 有 一 部 分 已 经 被 的 预 测 模 型 计 算 过 了 ， 所 以 为 了 避 免 重 复 ， 需 要 减 少 相 应 的 因 子 。 比 当 前 用 户 先 到 的 普 通 用 户 车 辆 数 系 统 预 测 的 入 流 车 辆 数 普 通 用 户 占 所 有 用 户 的 比 例
3.模型概述-预约用户引导
3. 模 型 概 述 - 预 约 用 户 引 导 预 约 用 户 停 车 引 导 (DG-MRC) 算 法 采 用 基 于 合 作 的 机 制 ， 对 所 有 预 留 用 户 的 整 体 效 用 进 行 优 化 。 一 个 自 然 的 方 法 是 在 每 个 决 策 时 段 共 同 最 小 化 停 车 总 成 本 和 不 能 分 配 资 源 的 用 户 数 量 这 种 方 法 只 考 虑 当 前 供 需 状 况 下 的 资 源 分 配 ， 忽 略 了 长 期 影 响 。 为 克 服 这 一 问 题 ， 引 入 一 个 负 面 影 响 因 素 这 种 负 面 影 响 可 以 被 认 为 是 𝑢 𝑖 实 际 占 据 𝑠 𝑗 之 前 对 街 区 𝑠 𝑗 的 一 种 资 源 浪 费 。
3.模型概述-预约用户引导
3. 模 型 概 述 - 预 约 用 户 引 导 从 直 观 上 看 ， 应 该 是 一 个 单 调 递 增 函 数 和 凸 函 数 ， 满 足 本 文 构 造 了 一 个 具 有 上 述 性 质 的 特 别 方 便 直 观 的 函 数 因 此 ， 目 标 函 数 改 写 为
3.模型概述-联合停车引导
3. 模 型 概 述 - 联 合 停 车 引 导 步 骤 1): 利 用 DG-MNC 虚 拟 地 将 资 源 分 配 给 所 有 普 通 用 户 。 而 这 些 分 配 将 被 考 虑 到 更 新 POR 预 测 结 果 ， 这 有 利 于 可 靠 地 评 估 每 个 候 选 街 区 的 未 来 “ 流 行 度 ” 。 因 此 ， 负 影 响 因 子 可 进 行 更 新 。 步 骤 2): 基 于 更 新 后 的 负 影 响 因 子 ， 利 用 DG- MRC 为 预 约 用 户 分 配 适 当 的 资 源 。 此 外 ， 清 除 之 前 在 步 骤 1) 中 的 分 配 对 POR 预 测 结 果 的 影 响 ， 并 根 据 所 有 预 留 用 户 的 最 新 分 配 更 新 预 测 结 果 。 步 骤 3): 根 据 更 新 后 的 POR 预 测 结 果 ， 重 新 运 行 DG-MNC ， 实 际 将 资 源 分 配 给 所 有 正 常 用 户 。 现 在 ， 分 配 结 果 将 被 推 送 到 所 有 普 通 用 户 。
4.实验
4. 实 验 实 验 数 据 ： 深 圳 市 南 山 区 76 个 街 区 1735 个 传 感 器 从 2018 年 9 月 1 日 至 2018 年 12 月 31 日 收 集 的 停 车 数 据 。 Baseline ： NG ： 基 于 贪 婪 搜 索 策 略 搜 索 空 车 位 : 首 先 搜 索 离 目 的 地 最 近 的 候 选 街 区 ; 如 果 失 败 了 ， 那 么 将 在 周 围 的 区 域 执 行 一 个 逐 渐 增 大 的 搜 索 半 径 。 SP ： 该 方 法 采 用 基 于 目 的 地 步 行 距 离 的 基 于 预 约 的 资 源 分 配 机 制 。 它 与 DG-MRC 的 不 同 之 处 在 于 ， 它 只 考 虑 当 前 的 保 留 需 求 ， 而 忽 略 了 未 来 可 能 产 生 的 负 面 影 响 。 已 搜 索 的 街 道 数 目 (NSSB ) 、 额 外 驾 驶 时 间 (EDT ) 、 步 行 时 间 (WT ) 、 总 延 迟 (TD ) 、 资 源 浪 费 率 (RWR )
4.实验-DG-MNC
4. 实 验 -DG-MNC 在 不 同 普 通 用 户 数 的 情 况 下 ， DG-MNC 性 能 优 于 DG-SN 和 NG ， 这 主 要 是 因 为 DG-MNC 可 以 考 虑 到 多 用 户 的 竞 争 ， 帮 助 用 户 优 先 选 择 更 可 能 有 可 用 停 车 位 的 街 区 ， 从 而 大 大 降 低 了 EDT 。 同 时 ， 不 同 的 方 法 有 相 似 的 WT 。
4.实验-DG-MRC
4. 实 验 -DG-MRC 当 预 约 用 户 数 量 在 10 ~ 30 之 间 变 化 时 ， DG-MRC+NG 相 比 SP+NG 可 以 大 大 降 低 RWR 约 30% ~ 13% ， 这 有 助 于 减 少 外 部 用 户 潜 在 的 不 满 意 ， 同 时 保 证 保 留 用 户 的 服 务 质 量 。
4.实验-系统总体
4. 实 验 - 系 统 总 体 TD 随 着 所 有 三 个 用 户 组 的 用 户 总 数 的 增 加 而 增 加 。 同 时 ， R 组 和 N 组 都 比 E 组 具 有 更 大 的 优 势 。 与 E 组 相 比 ， R 组 TD 减 少 8.9 至 20.8 分 钟 ， 而 N 组 TD 减 少 3.8 至 11.9 分 钟 。 这 表 明 系 统 具 有 良 好 的 可 扩 展 性 。 此 外 ， 它 可 以 刺 激 更 多 的 用 户 使 用 ， 以 减 少 停 车 延 迟 ， 特 别 是 在 停 车 资 源 有 限 的 地 方 ， 从 而 提 高 路 边 停 车 的 资 源 利 用 效 率 。 R ： 预 约 用 户 N ： 普 通 用 户 E ： 外 部 用 户
5.结论
5. 结 论 本 文 设 计 了 多 样 化 需 求 感 知 停 车 引 导 系 统 ， 旨 在 实 现 不 同 用 户 群 体 之 间 的 卓 越 性 能 平 衡 。 为 了 优 化 系 统 的 长 期 性 能 ， 将 多 步 停 车 预 测 模 块 引 入 系 统 ， 设 计 了 多 样 化 停 车 引 导 模 块 ， 实 现 了 停 车 位 的 动 态 分 配 。 最 后 ， 使 用 来 自 深 圳 四 个 月 的 真 实 街 道 停 车 数 据 集 来 实 现 和 广 泛 评 估 。 评 估 结 果 表 明 ， 在 停 车 需 求 较 高 的 区 域 ， 本 文 的 方 法 与 贪 心 方 法 相 比 ， 平 均 延 迟 减 少 至 少 33% 。 更 重 要 的 是 ， 它 为 多 样 化 的 用 户 群 体 实 现 了 出 色 的 性 能 平 衡 。
谢谢！
计 算 机 与 大 数 据 学 院 Fuzhou University 谢 谢 ！