面向大规模不确定物流网络的需求概率查询方法

摘要

一种面向大规模不确定物流网络的需求概率查询方法，采用不确定图G来描述不确定物流网络，计算配送量在不确定物流网络中从源节点到汇聚节点被成功配送的概率，具体是不确定图G的需求概率查询，得到物流网络数据的需求概率的查询结果，即配送量在不确定物流网络中从源节点到汇聚节点被成功配送的概率，不断更新需求概率，进行下一次查询；根据计算出的结果，制定物流配送线路进行物流配送。采用本方法来处理物流网络的不确定性，能够提高运输效率减少成本。

主权项

一种面向大规模不确定物流网络的需求概率查询方法，其特征在于，包括如下步骤：步骤1：采用不确定图G来描述不确定物流网络，其中，不确定图的顶点s用来表示物流网络中的源节点，不确定图的顶点t用来表示物流网络中的汇聚节点，不确定图的需求d表示物流网络中的配送量，不确定图中的每条边即配送方案；步骤2：计算配送量在不确定物流网络中从源节点到汇聚节点被成功配送的概率，方法为不确定图G的需求概率查询，具体如下：步骤2.1：初始化；首先，对整个不确定图G的概率状态空间初始化：将不确定图G中的每条边的可能取得的配送量设置为0，且不确定图G的概率分解空间为所有边的可能配送量的集合；然后，初始化需求概率q_pr＝0；步骤2.2：在概率分解空间不为空的情况下，循环执行步骤2.3‑2.8；步骤2.3：判断不确定图G中当前边的配送量是否超出物流网络容量范围，是，则对不确定图G中的与当前边相邻的下一个边进行判断，否，则舍弃当前边；物流网络容量包括物流网络的最大容量和最小容量，最大容量是指物流网络的最大配送量，最小容量是指最小配送量，因此物流网络容量范围即从物流网络的最小容量到最大容量；判断当前边的配送量是否超出物流网络容量的具体步骤是：首先，根据概率分解空间中每条边允许配送的最小容量l_i和最大容量u_i，选取整个物流网络的最小容量和最大容量，构成状态容量集合C；具体是：所有边的最小容量中的最小值即是物流网络的最小容量，同理所有边的最大容量中的最大值即是物流网络的最大容量，物流网络最大容量加上最小容量除以2的结果为物流网络容量的平均值，每条边的容量减去平均值的绝对值构成一个不确定图状态向量，m条边的状态向量组成状态容量集合C；然后，判断源节点s关联的边是否超出该边的容量范围，如果是，即进行下一条边的判断；否则该边被舍弃；步骤2.4：在不确定图G中，计算从源节点s到汇聚节点t的物流线路上，取最小容量状态下的最大需求和取最大容量状态下的最大需求；步骤2.5：判断最小容量l^C下的最大需求F(l^C)是否可满足配送量，即：F(l^C)≥d是否成立，是则更新需求概率，即需求概率q_pr加上可满足C的概率Pr(C)；否则判断最大容量u^C下的最大需求F(u^C)是否可满足配送量，F(u^C)≥d是否成立，成立，则计算每条边的配送量和满足该配送量的边的集合E^d(C)，E^d(C)的计算即是求出所有的大于d的边；不成立，则不处理，其中，m为不确定图的边的个数，表示1,2，……m条边在配送量d下的需求概率；计算每条边的配送量的步骤是：(1)为不确定图G添加一个虚拟顶点t*，并在t*和t之间加入一个配送量为d的边；(2)不确定图G中的每条边e_i取最大容量(3)求得从s到t*的最大需求；因为F(u^C)≥d，并且t到t*的容量为d，所以s到t*的最大需求为d；(4)对于G中的每条边e_i，通过e_i的需求f_i^d即可构成一个配送量步骤2.6：对计算出的所有满足物流网络容量的边，构建新的容量集合，并根据该集合构建状态不相容集合，将该新的容量集合进行概率状态分解；根据上步计算的求解状态容量集合C下的可行边集，公式为对所有e_i∈E^d(C)的边，构建边的状态容量的集合，计算公式为$K_i^C=\left\{c_i\right|l_i^C\le c_i\le u_i^C,1\le i\le m\},$最后根据构建状态不相容集合和可按规则和计算，基于上述结果，便可按概率状态分解规则将C分解成C¹,...,C^q和C⁰；其中，E表示边集合，表示在C下，边e_i的状态集合，c_i表示边e_i的一个概率容量，表示在C中边e_i的最小容量，表示在C中边e_i的最大容量，为的子集，并满足和${\underset{\_}{K}}_i^C\cup {\bar{K}}_i^C=K_i^C;$概率状态分解规则由以下5步来完成：(1)在边集E中任意选择一条边并以为临界边构建不包含的边容量集合，计算公式为$C^1=\left\{(c_1,...,c_m)\right|c_{x_1}\in {\underset{‾}{K}}_{x_1}^C,c_i\in K_i^C,e_i\in E/\left\{e_{x_1}\right\}\};$(2)在边集E中任意选择一条边除了以外的边构建不包含的边容量集合，计算公式为$C^2=\left\{(c_1,...,c_m)\right|c_{x_1}\in {\bar{K}}_{x_1}^C,c_{x_2}\in {\underset{‾}{K}}_{x_2}^C,c_i\in K_i^C,e_i\in E/\{e_{x_1},e_{x_2}\}\};$(3)……；(4)类似地，在边集E中任意选择一条边并构建不包含边集的边容量集合，计算公式为$C^q=\left\{(c_1,...,c_m)\right|c_i\in {\bar{K}}_i^C,e_i\in \{e_{x_1},...,e_{x_{q-1}}\},c_{x_q}\in {\underset{‾}{K}}_{x_q}^C,c_i\in K_i^C,e_i\in E/\{e_{x_1},...,e_{x_q}\}\};$(5)最后构建包含e_i∈E/E^d(C)的有效集合，计算公式为：$C^0=\left\{(c_1,...,c_m)\right|c_i\in {\bar{K}}_i^C,e_i\in E^d\left(C\right),c_i\in K_i^C,e_i\in E/E^d\left(C\right)\};$步骤2.7：形成新的概率分解空间；步骤2.8：得到物流网络数据的需求概率的查询结果，即配送量d在不确定物流网络中从源节点到汇聚节点被成功配送的概率Pr(C⁰)，至此完成一次查询，更新需求概率，进行下一次查询；步骤3：根据步骤2计算出的结果，制定物流配送线路进行物流配送。