(19)国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 202210314782.0 (22)申请日 2022.03.28 (71)申请人 重庆邮电大 学 地址 400065 重庆市南岸区黄桷垭崇文路2 号 申请人 重庆普小云科技有限公司 (72)发明人 邓维斌　阳秋林　王俊骥　麻存瑞　 缪文一　 (74)专利代理 机构 北京同恒源知识产权代理有 限公司 1 1275 专利代理师 廖曦 (51)Int.Cl. G06Q 10/04(2012.01) G06Q 10/08(2012.01) G06K 9/62(2022.01)G06V 10/762(2022.01) (54)发明名称 一种基于多维度分区的医药配送车辆路径 规划方法及装置 (57)摘要 本发明涉及一种基于多维度分区的医药配 送车辆路径规划方法及装置， 属于医药车辆领 域。 该方法包括以下步骤： 构建一个以资源点为M 原点， 半径为r的圆形配送区域； 其中半径r覆盖 该资源点的最大服务范围； OpenStreetMap开源 地图数据库中包含大量城市道路 交通数据， 利用 GIS得到某个区域某 个资源点的该区域的道路 交 通情况； 计算区域医药客户点密度， 重新得到一 个优化后的配送区域D； 对优化后的配送区域D 进 一步划分成若干个子区域， 形成固定线路； 考虑 医药配送车辆在运行中的实时情况， 构建目标函 数； 利用TSP临近插入算法求解， 得到最优里程。 本发明的方法时间快、 优化效果 好、 当日送达 。 权利要求书4页 说明书10页 附图2页 CN 114611830 A 2022.06.10 CN 114611830 A 1.一种基于多维度分区的医药配送车辆路径规划方法， 其特征在于： 该方法包括以下 步骤： S1： 选定某个城市某个区域内的某一资源点M； S2： 构建一个以资源点为M原点， 半径为r的圆形配送区域； 其中半径r覆盖该资源点的 最大服务范围； S3： Open Street Map开源地图数据库中包含大量城市道路交通数据， 利用GIS得到某 个区域某个资源点的该区域的道路交通情况； S4： 调用地图API， 将医药客户点在地图中可视化， 得到该区域医药客户点的分布情况； S5： 利用由S4和S5得到的道路交通情况和客户点分布情况， 计算该区域医药客户点密 度， 重新得到一个优化后的配送区域D； S6： 使用行政划分法或K ‑mean聚类对优化后的配送区域D进一步划分成若干个子区域， 形成固定线路； S7： 考虑医药配送车辆在运行中的实时情况， 包括车辆抛锚和交通拥堵等因素， 构建目 标函数； S8： 算法设计以及模型求 解； 利用TS P临近插入算法求 解， 得到最优里程。 2.根据权利要求1所述的一种基于多维度分区的医药配送车辆路径规划方法， 其特征 在于： 所述S1中， 资源点为仓库， 利用层次分析法确定最终的仓库， 在现有的仓库中选定一 个最佳医药仓库； 所述层次分析法为： 将经济因素和非经济因素结合起来， 确定各种因素的 重要性因子和各个因素 的权重比率， 按重要程度计算各方案的场址重要性指标， 以仓库重 要性指标最高的方案作为 最佳方案， 具体包 含以下几个步骤： S11： 建立层次结构模型 将决策的目标、 决策准则和决策对象， 按它们之间的相互关系分为最高层、 中间层和最 低层， 绘出层次结构图； 最高层是指决策的目的和要解决 的问题； 最低层是指决策时的备选 方案； 中间层是指考虑的因素和决策 的准则； 对于相邻的两层， 称高层为 目标层， 低层为因 素层； S12： 构建判断矩阵 在确定各层次各因素之间的权重时， 不把所有因素放在一起比较， 而是两两相互比较， 对此时采用相对尺度， 以减少性质不同的诸因素相互比较的困难； 对于某一准则， 对其下的 各方案进行两两对比， 并按其重要性程度评定等级； 按两两比较结果构成的矩阵称作判断 矩阵； S13： 权重计算 计算出权重值， 如果需要计算权重， 则首先计算特征向量值， SPSSAU提供特征向量指 标； 得到最大 特征根值CI， 用于一 致性检验使用； S14： 一致性检验 使用一致性检验是否出现问题， 一致性检验使用CR值进行分析， CR值小于0.1则说明通 过一致性检验， 反 之则说明没有通过一 致性检验。 3.根据权利要求2所述的一种基于多维度分区的医药配送车辆路径规划方法， 其特征 在于： 所述S2中， 从现成的医药仓库中选择一个医药仓库M， 以其为坐标原点， 半径为r的圆 形配送区域； 其中半径 r值为设定的标准密度值， 且覆盖该资源点的最大服 务范围。权　利　要　求　书 1/4 页 2 CN 114611830 A 24.根据权利要求3所述的一种基于多维度分区的医药配送车辆路径规划方法， 其特征 在于： 所述S3中， Open  Street Map开源地图数据库中包含大量城市道路交通数据， 结合 ArcGIS Pro软件， 得到某个区域某个资源点M的该区域的道路交通情况。 5.根据权利要求4所述的一种基于多维度分区的医药配送车辆路径规划方法， 其特征 在于： 所述S4中， 调用地图API， 通过python程序将所有医药客户点在地图中可视化， 即在地 图中看到客户点的分布情况。 6.根据权利要求5所述的一种基于多维度分区的医药配送车辆路径规划方法， 其特征 在于： 所述S5具体为： S51： 计算该区域某一 街道医药客户点密度； 设该区域某街道一天的订单总量为Pa， 该街道的辐射面积为Sa， 计算该区域某一街道医 药客户点密度： S52： 重复S51， 计算该区域内街道医药客户点密度， 当Ka＞K时， 定义该区域为高密度区 域， K值为设定的标准密度值， 选择配送； 反 之， 则该街道选择不予配送； S53： 考虑S4和S5得到的道路交通情况和客户点分布密度情况， 重复S52重新得到一个 优化后的配送区域D。 7.根据权利要求6所述的一种基于多维度分区的医药配送车辆路径规划方法， 其特征 在于： 所述S6具体为： S61： 配送区域划分； 方案1： 在优化后的配送区域D内， 若此 区域内存在不同的行政区域且其刚好满D内扇形 分布， 则根据行政区划分直接将此区域进一 步划分， 分成若干个固定的扇形子区域； 方案2： 在优化后的配送区域D内， 若不存在若干个完整的扇形行政区， 则利用K ‑means 聚类算法对配送区域的进行划分； 所述K‑means算法中， K表示类簇个数， means表示类簇内数据对象的均值， 将各个聚类 子集内的所有 数据样本的均值作为该聚类的代表 点， 通过迭代过程把数据划分为不同的类 别， 使得评价聚类性能的准则函数达 到最优； K‑means算法具体为： (1)首先选取K个对象作为初始的聚类中心， 得到使用的类的数量； (2)然后计算每个对象与各个聚类中心之间的距离， 把每个对象分配给距离它最近的 聚类中心； 距离的度量手段包括欧氏距离和曼哈顿距离； 设数据集X包含n个数据点， 需要划分到K个类； 类中心为用集合U表示； 聚类后所有数据 点到各自聚类中心的差的平方和为聚类平方和用J表示， 聚类目标是使得J值最小化； J值 为： S62： 构建配送线路 按照方案1或方案2划分得出的几个子区域， 构建对应的线路， 然后计算各个子区域内 各个仓库和客户点之间的距离矩阵；权　利　要　求　书 2/4 页 3 CN 114611830 A 3