知识卡片
按路由距离聚类任务
路由距离分组(RDG)要把“相似”的路线归到同一组。这里的任务是一条需服务的边(有两个端点),路线是一辆车依次服务的任务序列。距离不用地理直线距离,而用路网上的最短路距离(迪杰斯特拉算法求得),分三层计算:
- 任务距离(式 3-4):任务 z1 的 2 个端点与 z2 的 2 个端点两两组合,共 4 个最短路距离,取平均。
- 路线距离(式 3-5):Δroute(s1, s2) = 所有跨路线任务对 (z1∈s1, z2∈s2) 的任务距离之和 ÷ (|s1|·|s2|),即平均任务距离。
- 归一化(式 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 对路线聚类,同组路线一起进化。原书没有交代自距离为零等边界情况,不能直接照式实现。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 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 的小数字演算为依据原书公式补充的教学示例,非书中数据。
- 原始内容:这里使用的不是地理信息中的欧几里得距离而是顶点间的路由距离,再利用迪杰斯特拉算法确定两个节点间的最短距离,最后根据路由中所有任务节点的距离确定路由间的距离。