物流路由线路配载前端算法逻辑实现方案
![物流路由线路配载前端算法逻辑实现方案](https://static001.geekbang.org/infoq/b4/b42bb813e1a8adc1f75a1cdc1036b717.png)
作者:京东物流 柳宏
1.前置知识
1.1 基本概念
1.1.1 配载
配载代表着某条线路是否具有发往某个方向(区域、省市县、分拣等)的能力,也可以说是网点(分拣中心)是否具有承载配载所指方向货物的能力。一般网络规划者,在均衡线路间货量时,会通过调整配载来完成。
线路上可允许配载货物的“产品类型、最终妥投目的地”,通过线路的配载,计算 当前网点 到 目的网点 的 下一个网点 ,线路 绑定的配载代表通过当前线路最终可以到达的目的地 。以下图为例
![](https://static001.geekbang.org/infoq/24/24e8bd89e171dffff2cc9d2049c89370.jpeg?x-oss-process=image%2Fresize%2Cp_80%2Fauto-orient%2C1)
表示:如果放置在整个路由网络资源中,一个标记 T1 的货物要从北京发往福建,可选的路由有①北京站-北京-武汉-福建-福建站;②北京站-北京-广州-福建-福建站;之所以剔除了北京站-北京-上海-福建-福建站以及北京站-北京-武汉-上海-福建-福建站,正是因为后两条线路中未包含 T1 的配载代码,只标记了 T2 ,说明这条线路只有配载航空的货物,而没有普通陆运的带货能力。
下图就是用于描述配载的树形结构
![](https://static001.geekbang.org/infoq/95/951d4df9653aace6114a55899ca92ada.png)
1.1.2 班期与生失效日期
班期:指的是发运频率,1234567 代表着每周七天中,这个班次的“上线时间”,一般来讲,维护时缺失某个值,会造成路由中断的现象。
生失效日期:指的是该配载有效时间范围
![](https://static001.geekbang.org/infoq/ac/acd3868898dbc5e101de64e77c34dd7e.png)
1.1.3 配载合并逻辑
网点四级地址的关系以配载树的形式展现,勾选节点添加的配载在右侧的配载列表中展示
![](https://static001.geekbang.org/infoq/cc/cc81ee73800abf7ae1bdc3cb6cb527ef.png)
当某个节点的子节点没有全部勾选时,展示当前勾选的节点到配载列表中
![](https://static001.geekbang.org/infoq/0e/0ec84cfac2f693bb2a7a71a5593d212f.png)
当某个节点的子节点全部勾选时(在符合相关条件时,这里涉及到的算法逻辑后面详述),展示相应的父节点到配载列表中,这个逻辑是递归的
![](https://static001.geekbang.org/infoq/e4/e47d1ab16e73ab4e83580041318ed235.png)
![](https://static001.geekbang.org/infoq/c7/c74bb302bc1e1df0818574794c4f7031.png)
1.2 现有实现技术
•目前的线路配载前端基于 zTree+FixedHeaderTable+JQuery 实现,通过 zTree 监听节点被选中和取消选中,计算该操作后是否触发节点的合并或展开,进而重新渲染配载列表中的数据
2. 现状问题
2.1 节点合并算法逻辑有误
如果一个父节点下的所有子节点都被维护,即使子节点下的班期不同、生失效日期不重叠,系统都会自动合并到父节点。合并的展示效果为:
班期:对于纯新增配载显示 1234567;对于父节点下有一个子节点,班期显示为已存在配载的班期
生失效时间:统一为该切段线路的生失效日期
例如:X 线路被切割成两段,2022-11-02~2023-01-25 以及 2022-01-26~长久有效两段,在线路视图点击 2022-11-02~2023-01-25 这段的配载维护,X 下有 A1(配载时间为 2022-11-02~长久有效、班期 12),其父节点为 A,A 下还有子节点 A2、A3。今天是 11.17 日,将 A2、A3 都勾选上(时间任意,班期为 12345),配载会立刻合并为 A(生效时间 2022-11-02~2023-01-25,配载 1234567)
2.2 配载保存和显示的值不一致
上面操作触发合并,提交后库中保存的配载记录为:
2.3 本质原因
原有根据 zTree 节点触发合并的算法有问题,不考虑当前节点下其他子节点的配载的班期和生失效日期,而是根据是否同一个父节点直接合并。导致合并逻辑错误,保存与展示的数据不一致。
3. 预期效果
3.1 配载合并班期逻辑
条件:同一个父节点+各个子节点班期一致
3.2 配载生失效日期切断逻辑
新添加节点,生效日期为 参考日期,失效日期为 线路失效日期
![](https://static001.geekbang.org/infoq/f5/f506fd8462cf9ad727103893fd71a0c3.png)
参考日期选择 大于 当前 同级子节点的某天,当触发合并时
合并后的父节点:生效日期取参考日期,失效时间取同级子节点列表中失效时间最小的
合并后的子节点:
1)如果 原始生效日期小于合并后父节点的生效日期,则切断 原始生效日期 ~ 父节点的生效日期-1 天(相当于保留切断前的生效日期那一段)
2)如果 原始失效日期大于合并后父节点的失效日期,则切断 父节点的失效日期+1 ~ 原始失效日期 (相当于保留切断前的失效日期那一段)
![](https://static001.geekbang.org/infoq/1a/1a1dd17aeb7a65a3cf7423d8aae64f37.png)
![](https://static001.geekbang.org/infoq/fa/faca7d8c4d08b05b84cd2f48641456cc.png)
针对同一个节点的配载生失效日期切断的逻辑,举例
3.3 配载合并后保存逻辑
•采用所见即所的方式保存数据,用户在前端完成切断操作后,保存到数据库的记录与前端展示一致
4. 实现逻辑
4.1 整体逻辑
![](https://static001.geekbang.org/infoq/0a/0a9f343b8667346718d455ad83c1cc42.png)
4.2 定义数据结构及初始化
在配载树上监听事件,当触发选中/取消选中时,递归的获取 childrenNodes
![](https://static001.geekbang.org/infoq/ed/ed4969d04e043905321f585287d53d89.jpeg?x-oss-process=image%2Fresize%2Cp_80%2Fauto-orient%2C1)
维护配载与班期、配载与生失效日期的关系
![](https://static001.geekbang.org/infoq/ed/ed4969d04e043905321f585287d53d89.jpeg?x-oss-process=image%2Fresize%2Cp_80%2Fauto-orient%2C1)
将已有配载列表中的数据维护到 stowageFrequencyMap、stowageTimeMap、originStowageMapTI 中
![](https://static001.geekbang.org/infoq/e3/e3f9791bc0b8126d85aa252be289b069.png)
4.3 配载合并班期逻辑
1)如果当前节点非禁用 && 勾选 执行 合并逻辑;否则递归遍历节点;最终返回结果集
![](https://static001.geekbang.org/infoq/74/74e108cf71ca446331c8212c0e66510f.png)
2)如果当前节点非半选 && 非父节点,向父节点中查找班期,维护节点属性,加入结果集并返回
![](https://static001.geekbang.org/infoq/55/551461184a6cd5d1fb2e8ac475e89ce1.png)
3)根据节点的 pid 查找 stowageFrequencyMap 中是否存在班期
1.如果是父节点则遍历,按照每个子节点去 stowageFrequencyMap 中获取班期,分为两种情况如下;找到班期后维护 frequencyTreeMap,将同班期的节点维护到 list 中保存,即形成 班期-节点 list 的数据结构
2.向父节点中获取班期,同上
3.向子节点中递归获取班期,并将结果保存到新的数据结构 frequencyChildMap 中,然后合并到 frequencyTreeMap 中
![](https://static001.geekbang.org/infoq/d4/d46a5d70a2a01c180e22bf679e10346f.png)
![](https://static001.geekbang.org/infoq/41/416c46005c6189cd2d8d2a8e8913b471.png)
对 frequencyTreeMap 集合进行判断,如果数量为 1 表示 与该节点同级的节点班期相同,触发了合并,将节点加入结果集返回;否则说明当前节点的同级节点存在不同班期,不能进行节点向上合并,直接遍历 frequencyTreeMap 中的 value 集合,加入结果集返回
![](https://static001.geekbang.org/infoq/fe/fe65aff43a793f73fed7ca16b7cf650e.png)
对于触发了合并的结果集 frequencyTreeMap 中的每个节点遍历 同 当前线路的生失效日期比较,取出同级节点中的最大生效时间,最小失效时间,作为该同级节点中的最大公共时间范围设置到每个节点属性中
![](https://static001.geekbang.org/infoq/a7/a7009a323f24c2ac56c8fe2a3980c426.png)
4.4 配载生失效日期切断逻辑
定义变量
循环遍历每个结果集中的节点,判断是否渲染到配载列表中
![](https://static001.geekbang.org/infoq/d7/d7028a8c6081d0f527c657c4e95a0346.png)
根据当前节点 id 判断是否存在于 stowageList 中,如果存在直接显示;根据节点 id 删除 originStowageMapTI 集合
![](https://static001.geekbang.org/infoq/09/09831ca7ea3592078cb4af52e8cb8d3a.png)
更新生失效日期,分别判断 原始配载中是否存在需要切断的日期,新添加配载中是否存在需要切断的日期;然后将当前节点添加到配载列表中
![](https://static001.geekbang.org/infoq/19/196b1d7ca60932dfb3b3742128ca1da8.png)
遍历 originStowageMapTI ,判断历史的配载节点是否需要进行日期切断,分为以下两种情况;然后根据节点 id 删除 originStowageMapTI
如果 originEnableTime < enableTime:添加新的配载记录,生效时间取 originEnableTime, 失效时间取 newDisableTime
如果 originDisableTime > disableTime:添加新的配载记录,生效时间取 newEnableTime, 失效时间取 originDisableTime
![](https://static001.geekbang.org/infoq/0d/0d8a882f1c0a0c93cfff59f652d1676e.png)
遍历 newStowageMapTI ,判断新添加的节点是否需要进行日期切断;然后根据节点 id 删除 newStowageMapTI
如果 originDisableTime > disableTime:添加新的配载记录,生效时间取 newEnableTime, 失效时间取 originDisableTime
![](https://static001.geekbang.org/infoq/a9/a9004b707da519ff7a0878968228b83b.png)
5. 总结
•路由线路配载维护业务核心且频繁使用功能,为了实现业务述求,将完全没有关联的树形结构和 Dom 列表结合在一起。采用了多种数据模型+数据结构的组合形式,构造两者之间的关系,结合遍历、深度优先搜索、字符串查找等算法进行实现,在春节串点优化专项上线后取得了预期的收益。
版权声明: 本文为 InfoQ 作者【京东科技开发者】的原创文章。
原文链接:【http://xie.infoq.cn/article/0abbc64f7a19942f325bf4077】。文章转载请联系作者。
评论