基于自建GIS及欧拉环游的路径优化算法研究与实现.pdf

年第 卷第 期总第 期物流工程与管理 物流技术:./.基于自建 及欧拉环游的路径优化算法研究与实现 杨 明喻 莎田 永邓梦航(中国烟草总公司湖北省公司湖北 武汉 )【收稿日期】【作者简介】杨 明()男汉族湖北恩施人硕士中国烟草总公司湖北省公司高级经济师研究方向:物流管理智慧物流 【摘 要】湖北省烟草公司在自建 服务的基础之上以 路网文件为底图利用高德地图 构建基础路网通过对路网进行分析处理得到基础欧拉图 并利用 代码得到该路网的欧拉环游之后根据每辆车实际装载量约束对欧拉环游进行分割得到代表车辆运行路线的欧拉环路从而高效、简洁地实现了烟草物流配送路径优化【关键词】欧拉环游算法烟草物流路径优化【中图分类号】.【文献标识码】【文章编号】()()【】.【】引言烟草商业企业配送环节的线路优化算法一直以来都是烟草物流研究的热点问题 烟草物流具有严格的专卖制度对配送范围、配送节点、配送标准等有着较高的要求 此外烟草物流具有季节性、时效性等特点要求配送服务必须具备高度的灵活性和应变能力 湖北省烟草公司自建的 部署于烟草内网当前已实现了零售客户及物流配送中心地图打点、基础图层及路网的发布、配送路线的轨迹回放并对接了部分区域的卷烟订单数据为路径优化算法的研究、模拟及优化提供了底层基础烟草物流商零配送是由多辆车负责烟草零售客户的配送都从物流中心出发经过若干街道回到配送中心约束条件为所有涉及送货的街道都至少有一台车经过 次这个问题称为多人中国邮递员问题而求解中国邮递员问题的最优解的算法就是欧拉环游 综述随着移动互联网、物联网、在烟草物流的广泛应用烟草物流配送路径优化已成为各省烟草局研究的热点 基于各类算法的路径优化策略相继被提出来 借助中国邮递员问题并利用 算法验证路径优化有效性首先被提出在此基础之上通过增加约束条件建立新的数学模型并利用遗传算法可快速求得配送路径的最优解 为了能更加符合中国国情和贴合路网信息提出了利用集束法及集成研讨厅方法相结合的方式得出路径优化的最优方案 近年来随着国家双碳战略的推进面向低碳的双重遗传算法路径优化策略也被提出它将碳排放及配送站均衡纳入约束条件极大地提高了物流配送效率 湖北烟草则在传统教与学优化()算法的框架基础上提出了一种自然启发式的新型智能优化算法本文是基于中国邮递员问题理论模型在自建烟草行业 服务的基础之上以 路网文件为底图利用高德地图 构建基础路网通过对路网进行分析处理最后使用欧拉环游算法实现了烟草物流配送路径优化 算法设计.算法思想为了方便数据处理可以把问题转化为图论中的问题多人中国邮递员问题中每个车辆从配送中心出发经过若干条街道回到配送中心其路径是有向图上一个有向圈(即有向回路)这就要求每个街道都要在某个车辆的路径中也就是对应边至少包含在某个圈中边 城市路网交通图是一个连通物流工程与管理第 卷双向图在数学上给定一个连通无向图()其中 为顶点集合 为边或弧的集合可以表示任何城市路网图 现在目标就是要找到若干个有向回路使得每条边至少属于一个有向回路且每个有向回路需求量之和满足载重限制与中国邮递员问题密切相关的问题是欧拉环游问题如果一个无向图或有向图的每个顶点的度数都是偶数那么该图就有欧拉环游如果一个图有欧拉环游则欧拉环游就是中国邮递员问题的最优解因此对于实际路网需要先预先处理使其成为欧拉图再找出欧拉图的欧拉环游将其切割成 段使得每段的需求量之和都小于等于货车载重限制给出其最优切割方法同时添加从每段起点和终点到配送中心 的最短路径最终找出较优的欧拉环游组合就可以构成该问题的可行解为了解决烟草配送问题假设有 辆车每辆车有一个载重量上限 路网中每个有向边有长度和客户需求量两个权重 目标是将每条有向边都包含在某个有向回路中且每个回路的总长度不超过 且每个回路的客户需求量之和满足车辆载重能力的限制 本文以宜昌地区为例进行讨论.实现步骤.数据处理以开源 地图为底图零售点原始坐标为 坐标系而 路网是 坐标因此先将零售点坐标进行转换统一坐标系 因 路网文件中部分道路信息不全且非最新需要通过高德地图 构建路网将路网进行处理使从配送中心点开始可以到达任一零售点位图 基础路网及转换前后配送中心、零售点位.路网处理构成欧拉图根据 路网实际道路情况对缺失路段做补全处理将支路进行连接对于有双向连通需求的道路进行增边补充使其成为每个节点所连弧的数量均为偶数的欧拉图.计算得到欧拉环游利用 编程.算法实现欧拉图中最大欧拉环游的寻找、判断并进行可视化就得到全路网的最大欧拉环游.添加需求量对于所有专卖店需求点使用 中 分析工具邻域分析近邻分析将其需求量赋予所在的边并进行同类项求和合并计算将得到的每条边的需求量数据作为该条边的权重从而得到具有需求权重的欧拉环游.分割欧拉图得到满足需求量约束的最少数量的环路将得到的欧拉环游根据需求量约束进行分割输出其总权重小于约束的欧拉环即为车辆实际运行路线 根据已知每条路段的权重(需求量)在()之间而总约束为 因此利用 分割算法产出欧拉图中所有四级以上的回路及其总权重 为得到最少数量的环路设 为第 条回路的总权重(为环路总数)设 为 变量第 条回路被选择第 条回路未被选择得到以下规划模型:.因此可以得到满足约束条件的最少数量环路组合 运输车辆从配送中心出发可以到达环的任意起点然后进行配送直到返回起点完成任务最后沿着路线返回配送中心.算法技术路线图在实现步骤.中寻找最大欧拉环游算法的技术路线图如图 所示 首先输入处理好的 路网文件库读取该 文件并将其转为.形式获取节点以及与节点关联的边遍历所有节点若任意两点均有路径相连则为连通若为连通图且所有节点相连接的边均为偶数无奇数度点则继续执行并输出 否则输出 算法停止取任一节点 作为起点令 设 若在有()没有与 关联的边则计算停止否则再从()中取一条边 满足:与 相关联 不应该为 中的桥(即在去掉之前走过的边后的图上再去掉该边会使图不再连通)设 ()将其加入 得到 之后 重复循环就得到最终欧拉路径并输出节点序列的 图在实现步骤.中分割欧拉环游得到实际运输路线算法的技术路线图如图 所示 首先输入欧拉图的 文件地址获取节点之间的连接关系以及每条边的权重从未访问过的节点 开始访问相邻节点 并保留访问过的节点数组依次遍历直至图中和 有路径相通的顶点都被访问之后找出所有没有访问过且与当前节点相邻的顶点递归调用这些顶点的函数如果递归函数返回 说明有环则输出该环路的节点列表并将这些节点所连接的路径删除再进行回溯直至所有路径都被删除之后输出回路的总权重 再利用实现第 期杨 明等:基于自建 及欧拉环游的路径优化算法研究与实现步骤.中的规划模型求解得到最少数量环路组合图 寻找最大欧拉环游算法的技术路线图图 分割欧拉环游得到实际运输路线算法的技术路线图 研究结论在烟草物流配送问题中仓库和顾客可以视为图的节点每个节点之间的距离可以视为边的权重 通过将每个节点之间的距离构成一个完全图并使用欧拉回路算法可以找到一条经过每个顾客恰好一次的最短路径从而实现最优的物流配送方案 此外本文的创新性体现在所涉及的地图数据处理、地图发布和前端渲染均基于自建开源地图服务并引入了车辆装载限制及车辆/线路任务均衡两个约束条件能极大提高策略的自主性和可行性但需要注意的是在配送路径优化过程中仍会面临许多实际操作问题例如欧拉环路算法可能存在多个最优解、路径优化计算时间会随着图规模的增加而增加、无法处理部分重叠路径及动态变化的问题 因此需要根据具体情况选择最适合的算法及增加约束条件如深度学习、智能调度、交通路况约束等来不断进行算法的调优及完善参考文献 莫韦嶙谭勇张宝华.烟草配送系统中路径优化问题.物流工程与管理():.叶安新.基于遗传算法的烟草配送车路径优化问题.计算机系统应用():.胡红春.烟草物流配送车辆线路优化研究与应用.物流技术():.李存兵谢林君杨金欣.面向低碳的双层遗传算法烟草物流路径优化.烟草科技():.高怡杰何湘竹石英等.求解烟草配送路径规划问题的新型智能优化算法.中南民族大学学报(自然科学版)():.