(19)国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 202211040903.3 (22)申请日 2022.08.29 (71)申请人 重庆邮电大 学 地址 400065 重庆市南岸区黄桷垭崇文路2 号 (72)发明人 徐秀珍　牛义锋　宋祎璠　张媛媛　 袁梦梦　蔡万翠　王俊丰　 (74)专利代理 机构 北京同恒源知识产权代理有 限公司 1 1275 专利代理师 方钟苑 (51)Int.Cl. G06Q 10/08(2012.01) (54)发明名称 考虑运输费用约束的物流运输网络可靠性 计算方法 (57)摘要 本发明涉及一种考虑运输费用约束的物流 运输网络 可靠性计算方法， 属于物 流运输网络可 靠性评估领域。 该方法包括： S1： 确定基础数据， 包括商品需求d， 运输费用上限， 每条边的单位运 输费用和容量概率分布； S2： 确定网络所有的极 小路； S3： 求解所有的d ‑向量； S4： 求解每个d ‑向 量对应的流向量； S5： 对流向量进行检验； S6： 将 可接受流向量转化为对应的候选(d,b) ‑极小路； S7： 验证候选(d,b) ‑极小路是否是(d,b) ‑极小 路； S8： 删去重复(d,b) ‑极小路； S9： 计算运输费 用约束的物 流运输网络可靠性。 本发 明能够快速 寻找所有(d,b) ‑极小路， 提高运输费用约束的物 流运输网络可靠性整体 计算效率。 权利要求书2页 说明书7页 附图2页 CN 115358672 A 2022.11.18 CN 115358672 A 1.一种考虑运输费用约束的物流运输网络可靠性计算方法， 其特征在于， 该方法包括 以下步骤： S1： 确定基础数据， 包括商品需求d， 运输费用上限b， 每条边的单位运输费用Ci和容量概 率分布； S2： 确定网络所有的极小路； S3： 求解所有的d ‑向量； S4： 求解每个d‑向量对应的流向量F； S5： 对得到的流向量F进行检验； S6： 将可接受流向量 转化为对应的候选(d,b) ‑极小路； S7： 验证候选(d,b) ‑极小路是否是(d,b) ‑极小路； S8： 删去重复(d,b) ‑极小路； S9： 计算运输费用约束的物流 运输网络可靠性。 2.根据权利要求1所述的物流运输网络可靠性计算方法， 其特征在于， 步骤S2具体包 括： 极小路是由网络中的边组成的集合， 集合中的所有边构成一条从源点s到汇 点t的通路， 但去掉集合中的任何一条边， 剩 下的都不能够构成从源点s到汇点t的通路， 确定网络所有 的极小路P1,P2,…,Pp， p代表极小路的数量。 3.根据权利要求2所述的物流运输网络可靠性计算方法， 其特征在于， 步骤S3具体包 括： 令Out(s)＝{e1,e2,...,eλ}表示从源点s发出的边的集合， λ为从源点 s发出的边的数量； U＝(U1,U2,...,Um)为最大容量向量， Ui表示边ei的最大容量， 1≤i≤m， m为网络中边的数量， 容量向量U(0i)＝(U1,...,Ui‑1,0,Ui+1,...,Um)， F(U(0i))表示网络在U(0i)下的最大流量， 用 dk表示通过边ek∈Out(s)的流量， 1≤k≤ λ， 称D＝(d1,d2,…,dλ)为d‑向量， 如果D满足如下条 件： max{d‑F(U(0k)),0}≤dk≤min{Uk,d}， 1≤k≤ λ 根据上面的条件求 解所有的d ‑向量。 4.根据权利要求3所述的物流运输网络可靠性计算方法， 其特征在于， 步骤S4具体包 括： 令每个d ‑向量对应的流向量F＝(F1,F2,…,Fp)， Fj表示通过极小 路Pj的流量， Mj＝min{Ui |ei∈Pj}代表Pj的容量， 1≤j≤p， 用Ωk表示包含边ek的极小路集合， ek∈Out(s)， 即Ωk＝{Pj |ek∈Pj}， 1≤k≤λ， 根据下面的条件求解每个d ‑向量D＝(d1,d2,…,dλ)对应的流向量F＝ (F1,F2,…,Fp)： 5.根据权利要求4所述的物流运输网络可靠性计算方法， 其特征在于， 步骤S5具体包 括： 令 表示极小路Pj的单位运输 费用， 其中Ci代表边ei的单位运输 费用， 检验 每个流向量F 是否满足如下 条件： 权　利　要　求　书 1/2 页 2 CN 115358672 A 2如果流向量F满足以上两个条件， 称其为可接受流向量； 如果不存在可接受流向量， 则 停止， 考虑运输费用约束的物流 运输网络可靠性 为0。 6.根据权利要求5所述的物流运输网络可靠性计算方法， 其特征在于， 步骤S6具体包 括： 根据如下关系式将可接受流向量 转化为对应的候选(d,b) ‑极小路X＝(x1,x2,…,xm)： 7.根据权利要求6所述的物流运输网络可靠性计算方法， 其特征在于， 步骤S7具体包 括： 如果候选(d,b) ‑极小路X不包含有向圈， 则X是(d,b) ‑极小路， 对所有的候选(d,b) ‑极小 路进行检验， 得到(d,b) ‑极小路。 8.根据权利要求7所述的物流运输网络可靠性计算方法， 其特征在于， 步骤S8具体包 括： 对于每个(d,b) ‑极小路X＝(x1,x2,…,xm)， 定义X的映射值 对所有 的映射值进行排序， 找出重复映射值， 进而删去重复映射值对应的(d,b) ‑极小路， 得到所有 不重复(d,b) ‑极小路。 9.根据权利要求8所述的物流运输网络可靠性计算方法， 其特征在于， 步骤S9具体包 括： 将步骤S8中得到的所有不重复的(d,b) ‑极小路带入容斥定理公式， 便得到运输 费用约 束的物流 运输网络可靠性R(d,b)。权　利　要　求　书 2/2 页 3 CN 115358672 A 3