基于Benders分解的多方式物流運輸網絡優化模型

胡 輝，顧麗琴，倪 明

（1.華東交通大學經濟管理學院，江西 南昌330013；2.江西省新型工業化與城鎮化軟科學基地，江西 南昌330013）

作為一種求解混合整數規劃問題的方法，Benders 分解算法最早由Benders J F 于1962年提出，其基本原理是用割平面的方法把原問題分解為主問題與子問題，通過不斷迭代求解出原問題的最優值［1］。在難以計算的優化問題如大規模的混合整數規劃、隨機規劃等方面，Benders分解算法應用日趨常見，也往往是設計各種復雜算法的基礎［2-3］。

物流與供應鏈網絡模型在優化上常表現為混合整數規劃問題［4］，隨著問題規模的擴大，這些網絡模型的求解在有限的時間內難以達到，或是解的最優性難以保證［5］。造成問題規模擴大的主要原因在于模型所包含的變量、約束增多，導致最優解的搜索難度變大。譬如綠色運輸、綠色物流、綠色供應鏈等面向可持續發展提出的概念，使得物流與供應鏈網絡模型在決策變量和約束條件設置方面愈加復雜，問題規模越來越大，求解的難度更具挑戰性［6-7］。

基于以上考慮，我們首先對一個典型的物流運輸網絡優化模型的Benders 算法進行深入分析，指出其實現要點及可能存在的問題，且提出相應的解決方法。然后在此基礎上，通過引入不同交通方式的排放因子和污染物的排放成本，將模型進行擴展，建立多種交通方式下的物流運輸網絡優化模型，并構造出基于Benders分解算法進行模求解的主問題和子問題。最后，參考設計一個算例，對模型進行求解和比較分析，以說明模型的可行性和算法的有效性，為大規模的復雜物流供應鏈網絡優化模型的建立及求解奠定基礎。

1 物流運輸網絡優化模型的Benders分解算法及其實現要點和問題

1.1 物流運輸網絡優化模型

以一典型的物流運輸網絡優化模型為例［8］，該模型是一單層網絡，僅包括工廠和配送中心2個節點及二者之間組成的邊，模型形式化如下

式中：c為工廠和配送中心的運輸成本；f為工廠與配送中心建立聯系的固定成本；A、B為系數矩陣；b為配送中心的需求量；模型的目標函數為總成本最小（運輸成本和固定成本），約束條件為各工廠供應配送中心的貨物數量x大于配送中心的需求量；y為變量，取值0，1。

1.2 Benders分解算法

針對上面問題，Benders分解算法思想是把原始問題分解為主問題和子問題，主問題形式為式（2），子問題形式為式（3）

式中：k為極點解增加的約束；l為無界解增加的約束；K，L為不確定自數；u為子問題的解。

通過迭代求解主問題和子問題，最終求得原問題的最優解，算法流程如下圖。

圖1 Benders 分解算法流程圖Fig.1 Flow chart of Benders decomposition algorithm

1.3 Benders分解算法實現要點和問題

Benders 分解算法的實現可由不同的編程工具完成，采用GAMS 建模工具，求解器為Cplex12.5。算法的實現要點主要體現在3點。①初始解zˉ生成。理論上講，zˉ的初始值可以是｛0，1｝的隨機組合，但適合的zˉ初始值，可減少后續迭代求解的次數，加快求解速度。②對偶問題定義。在上面的模型中，對偶問題的目標函數和變量比較容易識別，但如果原問題形式更復雜，那么如何定義出正確的對偶問題是個不小的挑戰。③主問題中動態添加約束方程。從上面的算法可見，主問題是在迭代過程不斷通過添加約束建立的，并且要考慮無界可行的情況。在GAMS建模環境中，可以通過動態集合的建立加以實現。

但在用GAMS建模具體實現該模型的算法時，我們發現算法實現存在一個問題，導致程序運行異常終止。該問題具體表現在迭代過程中，如果初始可行解zˉ選擇不合適，子問題就有可能一開始就是無界可行解，添加約束形成主問題后，主問題沒有目標變量使得程序運行失敗。為了解決這一潛在的問題，我們在初始可行解基礎上，再定義了主問題目標變量的下界為初始可行解zˉ與f的乘積，即z≥fTy。這樣，不管原子問題的解是何種情況，主問題都不會出現沒有目標變量而出現程序運行終止的異常情況。

2 多種交通方式下物流運輸網絡優化模型及其Benders分解

不同的交通方式對物流供應鏈網絡有著多方面的影響，如物流成本、交貨期、庫存管理策略等［9］。同時，交通運輸在污染排放中的作用日益突出，不同交通方式有不同的排放因子，因此有必要在綠色物流、綠色供應鏈的體系設計中優化選擇交通方式，建立多種交通方式下的綠色物流運輸網絡優化模型。

2.1 多種交通方式的綠色物流運輸網絡優化模型

簡便起見，且為驗證Benders分解算法在更復雜情景下的有效性，我們在上節的物流網絡模型上，建立多種交通方式下考慮排放成本的綠色物流運輸網絡優化模型

式（4）的目標函數為運輸成本、固定成本與運輸過程中排放成本之和，其中ρe為污染物e的排放成本，為交通方式h下污染物e的排放因子。前4個約束條件分別表示：貨物運輸量不超過工廠的供應量Si；配送中心的需求量Dj；交通方式的最大運輸能力Th；各種交通方式下運輸量限制（M是一個很大的正數）。

2.2 模型的Benders分解

為利用Benders分解算法求解上面模型，需要構造出原問題的主問題（5）和子問題（6）

式中：u，v，w，r均為子問題的解。

在此基礎上，利用上節的算法可求解出原問題的最優解。

3 模型算例求解分析

為驗證上述模型及其算法的可行性和有效性，我們參考文獻［10］中的模型算例，以之為基礎擴展成新的模型并進行比較分析。

3.1 模型數據

根據模型需要的參數，我們假設不同交通方式下網絡節點間的運輸成本如表1所示（其中第1種交通方式的運輸成本和文獻［10］中成本數據相同）。同時為簡便起見，表中參數和求和結果沒有標注具體單位，僅為示意。

此外，3種交通方式的運輸能力分別設置為30，50，40，它們的排放因子分別為30，5，2（只考慮一種污染排放物），單位污染物排放成本為0.1。

3.2 模型求解結果分析

為說明多種交通方式下綠色物流運輸網絡模型的可行性和算法的有效性，我們以物流運輸成本最小（簡稱原模型）、包括排放在內的總成本最小（簡稱綠色模型）為目標函數分別對模型進行求解，模型最優解及基于Benders分解算法和Cplex求解的迭代次數分別如表2，表3所示，原模型、綠色模型基于Benders分解算法的求解迭代結果如表4。

表1 不同交通方式下網絡節點間的單位運輸成本Tab.1 Unit transportation cost between network nodes under different transport modes

表2 模型最優解Tab.2 Optimal solution of model

表3 模型求解結果比較Tab.3 Comparison analysis of models’solution results

表4 基于Benders分解算法的求解迭代過程Tab.4 Solving iteration process based on Benders decomposition

從表2、表3可見，在考慮不同交通方式后，模型的最優解發生了較大的變化，說明交通方式對物流網絡的優化有相當程度的影響，而從目標函數來看，雖然綠色模型物流運輸成本比原模型物流運輸成本高，但排放成本比原模型小得更多，因此從總成本來看，綠色物流網絡更具有競爭力。

另外從表4可明顯看出，基于Benders分解算法迭代次數少，收斂速度較快，求解效率有顯著提高，對于更大規模的復雜問題求解具有參考價值。

4 結束語

作為一種有效求解混合整數規劃的求解方法，Benders分解算法在解決各種應用領域中難以計算的優化問題方面得到了廣泛的應用。以一個典型的物流運輸網絡優化模型為例，認為Benders分解算法的難點在于初始解的確定、對偶問題的識別以及動態添加約束方程，同時指出算法實現可能存在的問題，且提出了相應的解決方法。然后在此基礎上，通過引入不同交通方式的排放因子和各種污染物的排放成本，建立了多種交通方式下考慮排放成本的物流運輸網絡優化模型，構造了基于Benders分解算法以進行模型求解的主問題和子問題。最后，參考設計了一個模擬算例，對模型及其算法的效率和效果進行了比較分析，說明了模型和算法的可行性和有效性，希望能為更復雜的物流供應鏈網絡的設計優化奠定基礎。

[1]BENDERS J F.Partitioning procedures for solving mixed variables Programming problems[J].Numersiche Mathematik,1962,4(1):238-252.

[2]李穎浩,郭瑞鵬.基于廣義Benders 分解的啟發式機組組合優化[J].電網技術,2012,36(3):179-184.

[3]柴月珍.農村固體廢棄物回收逆向物流網絡優化[J].重慶理工大學學報,2014,28(9):143-146.

[4]MARC G, VIDAL C J, DOGAN K.Modeling and design of global logistics systems:A review of integrated strategic and tactical models and design algorithms[J].European Journal of Operation Research,2002,143(1):1-18.

[5]HOSSEIN B,MAHDI B,TAHA H H.Integrated strategic and tactical planning in a supply chain network design with a heuristic solution method[J].Computers&Operations Research,2013,40(4):1143-1154.

[6]ANNA N, LADIMER S N.Sustainable supply chain network design:A multicriteria perspective[J].International Journal of Sustainable Engineering,2010,3(3):189-197.

[7]郭軍華,張威,朱佳翔.廢舊家電回收再利用的政府激勵機制研究[J].華東交通大學學報,2014,31(1):56-62.

[8]RICHARD K M.Large scale linear and integer optimization:A unified approach[M].Boston:Kluwer Academic Publishing, 1998:349-359.

[9]SADJADY H,DAVOUDPOUR H.Two-echelon,multi-commodity supply chain network design with mode selection,lead-times and inventory costs[J].Computers&Operations Research,2011,39(7):1345-1354..

[10]ERWIN K.Benders Decomposition with GAMS [EB/OL].(2008-7-5)[2014-10-15].http://www.amsterdam-optimization.com/pdf/benders.pdf.