知识卡片

普通读书笔记卡 · 3739.b.1.a

按路由距离聚类任务

理解等级:中级

路由距离分组(RDG)要把“相似”的路线归到同一组。这里的任务是一条需服务的边(有两个端点),路线是一辆车依次服务的任务序列。距离不用地理直线距离,而用路网上的最短路距离(迪杰斯特拉算法求得),分三层计算:

  1. 任务距离(式 3-4):任务 z1 的 2 个端点与 z2 的 2 个端点两两组合,共 4 个最短路距离,取平均。
  2. 路线距离(式 3-5):Δroute(s1, s2) = 所有跨路线任务对 (z1∈s1, z2∈s2) 的任务距离之和 ÷ (|s1|·|s2|),即平均任务距离。
  3. 归一化(式 3-6):Δ̂route(s1, s2) = [Δroute(s1, s2)/Δroute(s1, s1)] × [Δroute(s1, s2)/Δroute(s2, s2)]。其中 Δroute(s, s) 是路线 s 内部任务两两的平均距离,可理解为路线自身的“松散度”。

示例(补充演算,数值为假设):s1 有任务 a、b,s2 有任务 c;Δtask(a, c) = 6,Δtask(b, c) = 10,则 Δroute(s1, s2) = (6 + 10)/(2×1) = 8。若 Δroute(s1, s1) = 4、Δroute(s2, s2) = 2,则归一化距离 = (8⁄4)×(8⁄2) = 8。

距离越小越相似,最后用模糊 K-medoids 对路线聚类,同组路线一起进化。原书没有交代自距离为零等边界情况,不能直接照式实现。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    • 3 . 4 . 1 路 由 距 离 分 组 · 查看原书依据

      这个分组就是路由距离分组,首先定义两个节点之间的距离,这里使用的不是地理信息中的欧几里得距离而是顶点间的路由距离,再利用迪杰斯特拉算法确定两个节点间的最短距离,最后根据路由中所有任务节点的距离确定路由间的距离。两个路由间的距离越小,说明这两个路由越相似,越应该放到一组中。

    参考来源

    - 位置:《智能算法导论》第 3 章 3.4.1 节“路由距离分组”(源文件:`EPUB/xhtml/chapter3_0010.xhtml`)。 - 结论依据:式(3-4)平均四个端点距离;式(3-5)平均跨路线任务对距离;式(3-6)把路线间距离分别与两条路线的自距离相比并相乘。原文以较小距离代表较高相似性,并用模糊 K-medoids 聚类。公式据 EPUB 公式 SVG 的 LaTeX 描述核对;a、b、c 的小数字演算为依据原书公式补充的教学示例,非书中数据。 - 原始内容:这里使用的不是地理信息中的欧几里得距离而是顶点间的路由距离,再利用迪杰斯特拉算法确定两个节点间的最短距离,最后根据路由中所有任务节点的距离确定路由间的距离。