(19)国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 202210897779.6 (22)申请日 2022.07.28 (71)申请人 南通大学 地址 226019 江苏省南 通市崇川区啬园路9 号 (72)发明人 徐慧　余伟超　杨晨　赵静怡　 叶慧洋　 (51)Int.Cl. G06Q 10/04(2012.01) G06Q 10/08(2012.01) (54)发明名称 一种基于Dijkstra算法的最短物流路径规 划方法 (57)摘要 本发明涉及智能计算技术领域， 尤其涉及一 种基于Dijk stra算法的最 短物流路径规划方法， 包括： S1： 用迪杰斯拉Dijkstra算法计算配送中 心到所有配送点的最短距离和路径信息； S2： 解 析路径信息， 得到配送中心 到各配送 点最短距离 的路径； S3： 基于路径信息求覆盖所有可到达点 的最少往返趟数的配送路径； S4： 基于S1中的配 送中心到所有配送点的最短距离和S3得到最短 配送路程。 本发明首先基于Dijk stra算法计算出 的配送点到各配送点最短距离 路径， 给出往返配 送次数最少的配送方案， 然后基于该配送方案计 算出总的配送路程； 本发明能够减少物流成本， 提高物流时效性， 降低人力， 可 以有效提高生产 率。 权利要求书2页 说明书4页 附图2页 CN 115271205 A 2022.11.01 CN 115271205 A 1.一种基于Dijkst ra算法的最短物流路径规划方法， 其特 征在于， 具体步骤如下： S1： 用迪杰斯拉Dijkst ra算法计算配送中心到所有配送点的最短距离和路径信息； S2： 解析路径信息， 得到配送中心到各配送点 最短距离的路径； S3： 基于路径信息求覆盖所有可到 达点的最少往返趟数的配送路径； S4： 基于S1中的配送中心到所有配送点的最短距离和S3得到最短配送路程。 2.根据权利要求1所述的一种基于Dijkstra算法的最短物流路径规划方法， 其特征在 于， 在步骤S1中， 具体步骤如下： S101： 根据配送中心和配送点位置绘制配送图， 在图中标出配送中心和配送点之间所 有可以互通的路径和距离； S102： 顶号序号从0开始， 配送中心为第0个顶点， 另有n个 配送点； S103： 用Dijkstra算法求解配送中心， 第0个顶点到n个配送点的最短距离， 存于一维数 组D[]中， 其中第k个元 素D[k]表示： 配送中心到第k个 配送点的最短距离； S104： 用Dijkstra算法求解配送中心， 第0个顶点到n个配送点的最短距离的路径信息， 结果存于一维数组int  P[n+1]中； 其中第k个元素P[k]表示： 配送中心抵达第k个配送点， 且 目标点的前站是第P [k]个配送点。 3.根据权利要求1所述的一种基于Dijkstra算法的最短物流路径规划方法， 其特征在 于， 在步骤S2中， 具体步骤如下： S201： 创建n个堆栈， 配送中心到第k个 配送点的最短距离的路径将存 储在第k个栈中； S202： 对于配送中心到第k个 配送点的路径解析 方法为： Step 1： k1＝k,k2＝P[k1]； Step 2： 如果k2等于‑1， 表示配送中心到不了配送点 k； Step 3： 如果k2等于0,k入栈； Step 4： 如果k2既不等于‑1， 也不等于0， 进行下列处理： 4.1： 只要k2不 等于0， 重复下列操作， 求 解非直达路径上途经的配送点； 4.1.1： k1入 栈； 4.1.2： k1＝ k2， k2＝P [k1]； 4.2： 退出4.1循环后， k1入 栈。 4.根据权利要求1所述的一种基于Dijkstra算法的最短物流路径规划方法， 其特征在 于， 在步骤S3中， 具体步骤如下： S301： i从1到n依次考 量堆栈S[i]， 对每 个非空堆栈， 开始一条新的配送路径求取； S302： 创建一个队列Q； S303： 对于S[i]非空形成的配送路径的求取 方法是： Step 1： 清空队； Step 2： 只要第i个栈S [i]非空； 2.1： 出栈至k1,k1为该 条路径上的一个送货点； 2.2： 考量其余各栈S[j]， j取1到n： 2.2.1： 如果栈S [j]的栈顶元 素等于k1， 则出栈； 2.2.2： 如果栈S [j]出栈后非空， 则将 j入队； 2.3： 队列非空， 出队。权　利　要　求　书 1/2 页 2 CN 115271205 A 25.根据权利要求1所述的一种基于Dijkstra算法的最短物流路径规划方法， 其特征在 于， 在步骤S4中， 具体步骤如下： S401： 分别求各 条配送路径的长度， 某配送路径的距离的计算方法为： Stpe 1： 获取该配送路径的最后一个 配送点的序号 k； Step 2： 该配送路径的长度为D [k]； S402： 最短配送路程是 各条配送路径的距离的和。权　利　要　求　书 2/2 页 3 CN 115271205 A 3