利索能及
我要发布
收藏
专利号: 2022108977796
申请人: 南通大学
专利类型:发明专利
专利状态:已下证
更新日期:2025-12-30
缴费截止日期: 暂无
联系人

摘要:

权利要求书:

1.一种基于Dijkstra算法的最短物流路径规划方法,其特征在于,具体步骤如下:S1:用迪杰斯拉Dijkstra算法计算配送中心到所有配送点的最短距离和路径信息;

S2:解析路径信息,得到配送中心到各配送点最短距离的路径;

S3:基于路径信息求覆盖所有可到达点的最少往返趟数的配送路径;

S4:基于S1中的配送中心到所有配送点的最短距离和S3得到最短配送路程;

在步骤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]个配送点;

在步骤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入栈;

在步骤S4中,具体步骤如下:

S401:分别求各条配送路径的长度,某配送路径的距离的计算方法为:Stpe 1:获取该配送路径的最后一个配送点的序号k;

Step 2:该配送路径的长度为D[k];

S402:最短配送路程是各条配送路径的距离的和。

2.根据权利要求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:队列非空,出队。