[發明專利]一種基于最小成本流網絡模型的物流配送方法

有效

• 申請號: 201910255414.1
• 申請日: 2019-04-01
• 公開（公告）號: CN109993362B
• 公開（公告）日: 2022-12-06
• 發明（設計）人: 史彥軍;呂玲玲
• 申請（專利權）人: 大連理工大學
• 主分類號: G06Q10/04
• 分類號: G06Q10/04;G06Q10/08
• 代理公司: 大連理工大學專利中心 21200
• 代理人: 溫福雪;侯明遠

1.一種基于最小成本流網絡模型的物流配送方法，其特征在于，步驟如下：

第一步：構建MCF-LD模型；

MCF-LD模型的特殊圖形定義為G_MCF-LD＝(G,NP,AP),G_MCF-LD＝(G,NP,AP)表示圖G中的節點N和弧A的屬性；NP和AP分別表示節點和弧線的屬性；

弧A中每一條弧都有四個屬性：弧線長度，流量下限，流量上限和單位流量成本；弧線屬性函數將每個弧線映射到這些屬性AP：A→R×R×R×R；對每個屬于弧A的弧線，將映射關系表示為AP(i,j)或簡記為AP_ij，因此將弧線長度、流量下限，流量上限和單位流量成本分別表示為Dij，m_ij，M_ij和c_ij；

用f_ij表示弧線上運輸流量的大小，它是MCF-LD模型的決策變量，其中f_ij∈[m_ij,M_ij],(i,j)∈A；

1.1 G_MCF-LD網絡圖中節點及其屬性的定義

(1)供應點Supply：供應點會提供一定量的商品，它是物流配送路線的源點；

(2)轉運點transshipment：轉運點不提供商品，也不需要商品，它是物流配送路線的中間點，此點作為更改運輸車輛的轉折點；定義所有從供應點到達同一轉運點的商品，會在所有商品都到達轉運點的同時，才會從轉運點出發，流向需求點；

(3)需求點demand：需求點帶有一個附加屬性，即時間窗[e_i,l_i]屬性，若商品在e_i之前到達，會產生一個等待成本，即會因為倉儲空間不足的情況產生這個等待成本；若在l_i之后到達，使得顧客滿意度下降，會產生一個延遲成本；

1.2 G_MCF-LD網絡圖中弧線及其屬性的定義

定義G_MCF-LD網絡圖中的兩種弧線及其屬性，兩種弧線是以轉運點為界限劃分的：

(1)進入弧：該弧是從每個供應點到轉運點的有向弧；這種弧線的性質為：

ARC_IN＝{(i,m)|i∈Supply,m∈Transshipment,AP(i,m)＝[D_im,m_im,M_im,c_im]}

E_im＝c_imf_im (1)

該成本公式中，E_im表示從供應點i到轉運點m運輸f_im流量的商品需要的費用；c_im表示弧線(i,m)的單位流量運輸成本，f_im表示弧線(i,m)的運輸流量大小；進入弧的時間屬性如下：

式中，t_im表示從i點到m點的運輸時間，也表示弧線(i，m)上運輸的商品到達m點的時間；D_im表示i點到m點的距離，V表示車輛的行駛速度；確定所有匯聚到m點的弧線上商品到達的最長時間T_m；

(2)流出弧：該弧是從轉運點到需求點的有向弧線；這種弧線的屬性為：

ARC_OUT＝{(m,j)|m∈Transshipment,j∈Demand,AP(m,j)＝[D_mj,m_mj,M_mj,c_mj]}

在該成本公式中，E_mj表示從轉運點m到需求點j運輸f_mj流量的商品需要的費用；c_mj表示弧線(m,j)的單位流量運輸成本，f_mj表示弧線(m,j)的運輸流量大小；

當商品提前到達需求點，即e_j≥T_m+t_mj，用ω₁(e_j-(T_m+t_mj))f_mj+ω₂c_mjf_mj計算，其中，ω₁和ω₂分別為商品的等待時間成本和流量運輸成本的權重；

當商品延遲到達，即l_j≤T_m+t_mj，用p((T_m+t_mj)-l_j)f_mj+c_mjf_mj計算，其中p表示延遲到達的懲罰因子；

當商品在時間窗內到達，那么不產生時間成本，使用c_mjf_mj公式計算；

1.3 MCF-LD模型的目標函數及其約束

MCF-LD模型的目標函數為：

約束為：

公式(5)表示目標函數，其中E_im和E_mj具體表達分別見公式(1)和公式(4)；公式(6)表示弧線(i，j)上的流量大小只能取[m_ij,M_ij]之間；公式(7)表示供應點的供應量可以比需求點的需求量大；

第二步：使用改進的網絡單純形法進行求解

2.1給定一個初始的可行生成樹解，并確定其中的生成樹結構(T,L,U)；其中，T表示屬于生成樹的弧線的集合；L表示帶有下限流量的弧線；U表示帶有上限流量的弧線；

2.2計算生成樹中每一個節點的單純系數λ_i，也叫單純形乘子；根據屬于T中的弧線，計算每一個點的單純系數；

生成樹結構中，令其中一個節點的單純系數為0，則根據以下公式連續推導出其他各點的單純系數K_ij；

K_ij表示兩個節點i和j之間的弧線運輸單位流量的商品耗費的成本；

公式(8)給出了屬于生成樹弧線集合T中的節點的單純系數λ_i的公式，其中K_ij的計算方式需要分情況討論；

公式(9)表示當某條弧線屬于進入弧的集合時，該弧線運輸單位流量的成本K_ij就等于某進入弧的供應點i到轉運點m的單位流量成本；

2.3計算非樹弧的相對成本系數r_ij；如果屬于L的弧線的相對成本系數都大于0；屬于U的弧線的相對成本系數都小于0；則所有弧線的相對成本系數都是不違背的，此時的解決方案是最優的，算法停止；否則，跳到步驟2.4；

2.4選擇一個帶有違背的相對成本系數的非樹弧作為進入弧，如果只有一條弧違反了它的最優條件，那么就將這條弧添加到樹弧中；如果有多條弧違背其最優條件，則隨機選擇一條違反規則的進入弧(k，l)添加到生成樹中，會形成一個帶有樹弧的循環W；

2.5在循環中選擇一條弧離開，此時形成了一個新的生成樹結構(T,L,U)；

2.6根據新的生成樹結構(T,L,U)，重新計算2.2和2.3步中的節點單純系數和非樹弧的相對成本系數；如果對每條弧線(i，j)∈{L+U}減少的成本都滿足最優條件，那么目前的基本可行解就是最優的；否則，如果存在違反規則的弧線(i,j)，則重復2.2和2.3步中的計算。

2.如權利要求1所述的基于最小成本流網絡模型的物流配送方法，其特征在于，步驟2.5的具體做法如下：在循環W中沿著屬于L中的違背弧的方向增加θ單位的流量，使得循環中的一條弧線達到了它的上限或下限，這條弧線作為離開弧，循環W就被打破；通過增加負成本循環的流量，提高了求解的目標值；改變的流量由公式(11)確定：