[發明專利]一種帶成本約束的配送網絡容量可靠性評估方法

在審

• 申請號: 202011072509.9
• 申請日: 2020-10-09
• 公開（公告）號: CN112184041A
• 公開（公告）日: 2021-01-05
• 發明（設計）人: 牛義鋒;徐秀珍;萬曉榆;蹇潔;丁冬;付德強;劉進
• 申請（專利權）人: 重慶郵電大學
• 主分類號: G06Q10/06
• 分類號: G06Q10/06;G06Q10/08
• 代理公司: 北京同恒源知識產權代理有限公司 11275
• 代理人: 趙榮之

本發明涉及一種帶成本約束的配送網絡容量可靠性評估方法，屬于計算機技術領域。該方法包括以下步驟：步驟1：計算網絡中各條邊的容量下界；步驟2：用枚舉法求解成本約束的候選極小容量向量；步驟3：從成本約束的候選極小容量向量中找出成本約束的極小容量向量；步驟4：剔除重復的成本約束的極小容量向量；步驟5：把不重復的成本約束的極小容量向量代入不交和公式，計算帶成本約束的容量可靠性。本發明方法在搜索成本約束的候選極小容量向量、剔除重復的成本約束的極小容量向量方面具有非常好的計算效率。能夠快速地實現對帶成本約束的配送網絡容量可靠性開展評估。

技術領域

本發明屬于計算機技術領域，涉及一種帶成本約束的配送網絡容量可靠性評估方法。

背景技術

配送網絡作為一個開放網絡，容易受到內部故障或者外部不確定因素的干擾，例如交通阻塞、車輛故障、惡劣天氣等，這些隨機因素已經成為導致配送網絡服務功能失效的主要威脅。因此，評估隨機環境下配送網絡的服務質量對于保障網絡正常運行、維護社會經濟健康發展具有重要的現實意義?？煽啃允呛饬颗渌途W絡服務質量最重要的指標之一，廣義的配送網絡可靠性是指，網絡在一定的條件下能夠向用戶提供符合要求的服務質量的能力?，F代社會快節奏的生活方式使得人們對配送網絡的可靠性水平越來越重視。

在現實的商品配送過程中，由于受隨機因素的影響，配送網絡各條運輸線路上的運輸工具可能處于失效狀態，部分失效狀態，維護狀態等多種狀態。因此，配送網絡各條運輸線路的配送容量是隨機的，從而導致整個配送網絡的配送容量也是隨機的。在理論研究上，配送網絡常常被建模為一個多態網絡模型，網絡中每條邊具有相互獨立的、有限的、取非負整數的隨機容量。配送網絡容量可靠性是指，網絡能夠把d單位的商品需求量從出發地配送到目的地的概率。

此外，配送成本也是衡量配送網絡運行效率的一個重要方面，同時也是影響運營利潤極其關鍵的一個因素，因此，在可靠性指標中引入配送成本，能夠更全面、更合理地評估配送網絡的服務效率和服務質量。帶成本約束的配送網絡容量可靠性是指，網絡能夠把d單位的商品需求量從出發地配送到目的地且總的配送成本不超過給定的預算b的概率，用CR_d,b來表示。

計算CR_d,b最簡單方法是窮舉法，該方法需要對容量向量空間中的每個容量向量逐一進行枚舉，故時間復雜度很高，只適用于規模較小的配送網絡。目前，計算CR_d,b最常用的一種方法是利用成本約束的極小容量向量，該方法屬于間接法。如果一個容量向量滿足，網絡在該容量向量下能夠把d單位的商品需求量從出發地配送到目的地且總的配送成本不超過給定的預算b，而任何小于該容量向量的其他容量向量這兩個條件都不能同時滿足，則稱該容量向量為成本約束的極小容量向量。如果知道了網絡所有成本約束的極小容量向量，則CR_d,b就可以通過不交和公式計算得到。因此，尋找成本約束的極小容量向量是該方法的核心目標。目前，研究者已經提出了一些方法來尋找成本約束的極小容量向量，但這些方法在尋找成本約束的極小容量向量時大多效率不高。特別地，這些方法在搜索成本約束的候選極小容量向量、剔除重復的成本約束的極小容量向量時面臨計算效率瓶頸。

發明內容

有鑒于此，本發明的目的在于提供一種帶成本約束的配送網絡容量可靠性評估方法。

為達到上述目的，本發明提供如下技術方案：

一種帶成本約束的配送網絡容量可靠性評估方法，包括以下步驟：