煙草工業企業多倉庫發貨的貨源平衡與調度優化模型

楊 軍，羅 衛，何 哲，熊世進，陳永鋒

（湖南中煙物流有限責任公司，湖南 長沙 410000）

1 研究背景

中國是目前世界上最大的煙草生產國和消耗國之一，中國煙草年營收額1萬億元，納稅超過9 000億元。每年巨大的營收背后，是龐大的物流壓力，因此建設現代化的供應鏈物流體系，已經成為煙草工業企業提高經營效率，減少物流成本的重要方式之一。同時，為了更精準地響應到貨點的服務需求，更合理地選擇配送線路，更快速地完成物流配送，導致煙草工業企業對整個供應鏈的管理和把控有著非常高的要求。因此，一個高效率低成本的物流供應體系，是煙草工業企業提高客戶滿意度，增強自身核心競爭力，保持企業健康穩定發展的重要手段之一。

煙草工業企業的整個生產供應環節其實和大多數企業沒有太大區別（如圖1），然而在實際運營的細節上，卻存在著許多不同：

（1）企業在全國通常只有幾個發貨點，而需求點則多達數百個且遍布全國。

（2）物流公司擁有多種車型，每種車型具有不同的最大裝載量，如果裝載量不足，煙草公司需要向物流公司提供額外的補貼，從而造成巨大的成本浪費。

（3）由于每個發貨點的生產能力以及供給量不同，為了成本最優，管理者經常會考慮在倉庫之間進行貨物的轉運。

（4）一個發貨點通常在配送中會通過拼車來降低運輸成本。

圖1 煙草工業企業生產供應環節

但是從目前的實際運營方式來看，煙草工業企業沒有考慮如何系統高效地完成整個運輸配送的過程。在傳統模式下，企業的物流部門被動接收營銷部門的發貨需求編排發貨計劃。當指定的發貨點貨源不足時，再通過移庫補充貨源，因此經常會產生大量的移庫成本，甚至由于移庫不及時導致無法按時發貨。此外，部分暢銷的品類由于安全庫存較低，當產生臨時需求訂單時，往往需要浪費大量人力處理，甚至出現由于發貨點分配不合理導致無法按時發貨的情況。

針對上述問題，本文構建了一個基于混合型整數線性規劃的煙草運輸調度模型，能夠綜合考慮到煙草工業企業運輸的各個環節，計算得出最優的生產運輸調度方案，在考慮企業各個發貨點的生產能力的同時，以滿足需求點的需求為原則，幫助企業制定發貨計劃和運輸調度計劃，實現成本的最優。

2 相關研究

對于煙草工業企業的物流運輸調度問題，已經有相關學者做過一些研究。黃飛航等人（2014）[1]考慮了現在煙草工業企業物流倉庫中普通存在的人工進行車輛調度的問題，設計了一個方法將排隊管理系統應用到倉庫管理中，從而提高倉庫裝卸貨的效率。黃戈文等（2015）[2]融合了云計算、物聯網、大數據、GIS、GPS 等設備，設計研發了一套基于云計算的煙草物流運輸調度系統，能夠對煙草配送的各個細節進行監控，從而達到提高物流效率、降低成本的效果。郭賢正等（2014）[3]基于煙草運輸管理現有業務的瓶頸分析，提出了運輸管理系統中智能車輛調度功能的設計方法，并總結了整個執行過程中全程可視化監控和管理的實現方法和實施經驗。葉小龍等（2012）[4]針對煙草工業企業物流配送效率低成本高的缺點，提出了用配送中心選址方法以及配送網絡的一般設計方法來改進整個供應鏈。

雖然已有部分學者研究過煙草工業企業的物流解決方案，現有大多數研究主要還是著眼于更加寬泛的物流運輸領域以及車輛路徑問題，Moons 等人（2016）[5]綜合考慮了生產調度和車輛路徑優化這兩個經常被獨立解決的問題，從而提高供應鏈的效率。謝天保等人（2010）[6]研究了在存在多個物流中心的前提下，各個物流中心相互協作以實現物流的協同配送問題。

在研究方法上，大多數研究采用的方法為目前廣泛使用的各種算法。其中應用最為廣泛的當屬遺傳算法。李軍等（2000）[7]利用了最大保留交叉、交叉率和變異率自適應調整等技術，設計了基于自然數編碼的遺傳算法，研究了在車輛非滿載的情況下滿足貨運需求的最短行車線路。王楨和黃磊（2016）[8]設計了一個兩階段優化遺傳算法，第一個階段為待發貨訂單指派最佳車輛，第二個階段指定車輛的最佳配送方案，來解決在不同的訂單發貨區域的情況下，貨車的裝載和車輛路徑的調度問題。廖良才等（2008）[9]將遺傳算法的全局搜索能力和CW節約啟發式算法的局部搜索能力結合了起來，用這種創新的混合遺傳算法來解決物流車輛配送調度問題。其他算法比如禁忌搜索、粒子群算法、模擬退火算法等也有一部分學者研究。何小年和謝小良（2009）[10]設計了一種禁忌搜索算法來研究在車輛裝載量存在約束的情況下的車輛路徑問題，相比其他算法，該文提出的算法耗時短且結果也更優。徐杰和黃德先（2007）[11]通過使用粒子群算法和變異操作結合的求解方式來解決多目標下的帶時間窗的車輛路徑優化問題，減少了算法的無效迭代，提高了有效性。鄭英和孟志青（2010）[12]使用了節約里程算法來解決煙草配送的問題。Bent 和 Hentenryck（2006）[13]針對帶時間窗撿貨送貨的車輛路徑問題，提出了一個兩階段的混合算法，第一階段使用模擬退火算法對車輛數量進行優化，使得使用的車輛數達到最低，第二階段使用LNS 方法對整個成本進行優化，使得在車輛數最少的情況下成本最低。Goel和Irnich（2017）[14]將駕駛員過度駕駛的情況考慮在內提出了一種分支定界法來求解這種車輛路徑和駕駛員調度問題。

3 理論模型

3.1 問題背景

在傳統模式下，企業的物流部門被動接收營銷部門的發貨需求編排發貨計劃，經常會產生大量的移庫成本，甚至由于移庫不及時導致無法按時發貨，往往需要浪費大量人力處理，甚至出現由于發貨點分配不合理導致無法按時發貨的情況。要解決當前面臨的上述困難，必須對現有物流運行模式進行調整優化，提升物流的協同效率和信息共享，由營銷、物流、生產等供應鏈各環節的參與方緊密協同。因此本文提出了月計劃的產銷平衡工作新模式（如圖2）。

在新模式下，對煙草工業企業的供應鏈來說，整個流程可以分為計劃環節、生產環節、調度環節、配送環節。計劃環節,指在每個月月末企業會收到下月需求計劃，需要根據收到的訂單以及各發貨點的實際情況預排發貨計劃；生產環節，指企業根據制定的生產計劃進行原材料的采購、加工和生產；調度環節，指生產完成之后，物流部門需要按照實際的需求重新制定發貨計劃，移庫和回購計劃；配送環節，指物流部門按照發貨計劃進行發貨，按照運輸計劃和拼車計劃將產品運送到到貨點（如圖3）。

為了幫助企業提升供應鏈效率，減少成本，本文提出了一個發貨調度優化模型，其目標是在滿足供需平衡的前提下實現運輸成本的最優化，同時確保較高的車輛滿載率，同時能夠基于到貨點的需求計劃數據輸出可供物流公司執行的具體發貨計劃和移庫計劃。

圖2 月計劃產銷平衡工作流程圖

圖3 煙草工業企業生產物流調度配送過程示意圖

模型在實際應用中，可以分為無貨源計劃約束和有貨源計劃約束兩種應用場景。無貨源計劃約束指的是，基于下個月的需求計劃為生產部門制定生產計劃提供參考，在該場景下只需要考慮各發貨點的可發貨品規，而不需要考慮貨源庫存，同樣以總成本最優的目標輸出各發貨點的貨源需求；有貨源計劃約束是指，在有貨源約束的前提下進行發貨調度，所有的發貨計劃嚴格按照各發貨點的庫存情況進行發貨，輸出總成本最優和滿載率較高的發貨計劃、移庫計劃以及貨源補充建議。

該模型的主要挑戰在于：（1）企業生產的產品品類較多，運輸車輛具有多種車型，同時計劃需要落實到計劃期內的每一天，使得模型需要考慮的變量較多；（2）在調度過程中需要考慮各發貨點的移庫操作，移庫可能進一步降低成本，但同時移庫過程和移庫后的貨物搬運都需要占用配送時間；（3）在配送環節，到達不同的到貨點時可能會有拼車的情況，拼車情況下的運費計算問題，以及配送環節的車輛選擇問題，都是最終影響成本的重要因素。正是這些情況的存在，使得問題難度大大增加。

3.2 問題描述

本文模型考慮了多個發貨點和到貨點。每個發貨點的發貨數量有最大數量限制。每個到貨點對煙草規格及數量需求不同，但不同規格煙草包裝默認統一。物流公司可以使用多種車型，每種車型具有不同的最大裝載量。各個到貨點的月需求計劃中，包括了到貨點需要的產品品類、數量和需求時間。

在預排發貨計劃時，有貨源計劃約束場景下，模型需要考慮不同發貨點之間的移庫操作，移庫的煙草規格和數量沒有限制，移庫貨物到達倉庫后變為可發庫存有轉換時間。

在制定運輸計劃時，模型需要考慮每個發貨點對每個訂單的發貨時間、需要的運輸車次以及發出的貨物數量。發貨運輸過程中，多個到貨點到貨需求在時間允許的情況下，是允許拼車的，拼車能夠節省因為車輛滿載率不夠而產生的補貼。拼車的業務規則如下：

（1）每個拼車線路從一個發貨點出發，可以對多個到貨點倉庫的運輸需求進行拼車（通常不超過2個需求點）。

（2）僅限同一個承運商及標段的到貨點倉庫之間進行拼載。

（3）單輛車輛產生的運費等于不同線路的單位運輸成本與車輛載重，總運費等于各條運輸線路上車輛運費加總。拼車線路的運費以所串連的多個到貨需求中所指定最晚到貨倉庫的距離進行結算，但運輸時間需要考慮多個到貨倉庫之間的距離，每增加一個拼車到貨倉庫需要增加額外的卸貨時間。

3.3 模型構建

基于智能發貨調度模型的目標、相關因素和約束條件，可以建立無貨源計劃約束和有貨源計劃約束場景下分別對應的線性規劃模型的理論模型。

模型所需的符號和參數定義如下：

w：企業的發貨點，w ∈W，W為所有發貨點的集合；

l：到貨點，l ∈L,L為所有到貨點的集合；

p：煙草產品的產品規格和品類；

i：在配送過程中涉及到不同的車輛型號；

v：運輸車輛的平均行駛速度；

SI：期初庫存，發貨點每月初剩余的上個月的庫存余量；

dr：拼車線路，dr ?L 。

輸入參數為：

Pwl=發貨點w到到貨點l的單位運輸成本；

Pww'=發貨點w到發貨點w'的單位運輸成本；

=在第td天發貨點w到拼車線路dr的單位運輸成本；

dwl=發貨點w到到貨點l的運輸距離；

dww'=發貨點w到發貨點w'的運輸距離；

=在第td天發貨點w生產產品規格p的能力；

=第t天到貨點l對于產品規格p的需求；

Cw=發貨點w的庫容；

INVwptd=在第td天末，發貨點w剩余的產品規格p的數量；

tl=每個到貨點要求的貨物到達時間；

td=發貨點發出貨物的時間；

dt=路上所需的運輸時間；

buffertime1=發貨緩沖時間；

buffertime2=移庫緩沖時間；

SIwp=發貨點w的產品規格p的月初庫容；

V[i]=車型i對應的裝載量。

決策變量為：

=在第td天由發貨點w生產的產品規格p的數量；

=在第td天由發貨點w發往到貨點l的產品規格p的數量；

=在第td天由發貨點w移庫發往發貨點w'的產品規格p的數量；

trwlitd=在第td天由發貨點w不拼車發往到貨點l的車型i的數量；

tr_routewdritd=在第td天由發貨點w拼車發往拼車線路dr的車型i的數量；

=在第td天由發貨點w移庫發往發貨點w'的車型i的數量；

無貨源計劃約束下的運輸調度模型為：

模型的目標為總運費最小化，因為運費與車輛的數量有關，因此運費最優的同時也考慮了車輛滿載率最優，總運費包括了發貨點到到貨點的運費以及發貨點到拼車線路的運費。約束（2）為運輸時間約束，表示發貨點w發往到貨點l所需時間，包括實際運輸時間和緩沖時間，發貨過程中存在緩沖時間主要來自于駕駛員休息，天氣原因等耽誤運輸的偶發事件；約束（3）為供需匹配約束，代表著各個到貨點的需求必須被發出的產品滿足；約束（4）為生產能力限制，發貨點w當天生產產品p的數量小于等于其當天的生產能力上限。約束（5）-（11）對拼車的情況進行了約束。約束（5）保證拼車線路包含至少2個到貨點；約束（6）表示當拼車線路上的某一到貨點需求量為0時，此時此到貨點不需要拼車；約束（7）表示當整條拼車線路上到貨點需求均為0，則整條線路都不需要拼車；約束（8）表示當線路上存在拼車時，則拼車所用的車輛數量不為0；約束（9）保證了當到貨點存在拼車線路時，不需要單獨運往該到貨點；約束（10）保證了不拼車的車輛裝載容量大于等于目的地到貨點的實際需求量；約束（11）保證了拼車線路上的車輛裝載容量大于等于線路上所有到貨點的實際需求量。

有貨源計劃約束下的模型僅在無貨源計劃約束下的模型基礎上進行了改動。其目標函數如式（12）所示，總運費包括了不拼車的運貨成本、拼車成本以及移庫成本。

約束條件在無貨源計劃約束下的模型的基礎上添加了以下幾條：

約束（13）表示發貨點間進行移庫花費的時間，這里存在緩沖時間的主要原因來自于移庫后通常要進行的裝貨、卸貨、錄入系統等操作；約束（14）保證了發貨點當天庫存等于前一天末庫存和當天生產、移入數量之和減去當天發貨、移出數量；約束（15）保證了td天末發貨點w的庫存不大于其庫容并不小于0；約束（16）保證了移庫使用的車輛裝載容量大于等于總的移庫產品數量。

4 模型求解

由理論模型可以看出，由于最終的決策變量既包括生產數量等浮點型數據，也包括整數型數據如車輛數，因此本文的問題可以歸結為一個混合整數線性規劃問題(MILP,Mixed Integer Linear Programming)。本文采用Python 下的第三方軟件包Pyomo[15]結合Gurobi求解器對模型進行求解。具體的求解過程如圖4所示。

圖4 模型的求解過程示意圖

由于本文的理論模型約束多、維度多、數據量大，導致算法時間復雜度和空間復雜度較高，求解難度大，因此本文通過以下兩種方式降低了求解的復雜度：（1）在部分約束條件中應用了啟發式算法的思想來使得求解空間縮小，以尋找近似的最優解：先允許一個較小的拼車距離，確定發貨點的發貨，再將允許拼車距離加大，在發貨確定的情況下計算出運輸安排；（2）對部分約束條件進行了McCormick envelopes轉換使帶有0/1變量的約束轉換成線性約束，加快求解速度。

5 算例分析

為了評估模型的優化效果，本文算例使用的數據來自湖南中煙工業有限責任公司2017年11月的真實到貨點需求數據等數據，將其輸入模型進行優化計算，得到模擬的模型輸出結果，包含運輸總成本、發貨計劃明細、車輛總滿載率和使用車輛總數等，將這些模型計算結果與該月份實際的運營數據進行比較，以評估模型的優化效果。

實際對比的數據涵蓋湖南中煙工業有限公司下的7 個發貨點，包含4 個位于湖南省長沙、常德、零陵、郴州的發貨點，其余三個位于寧夏吳忠、吉林四平和河北保定。企業可以提供包括芙蓉王、白沙等共19 種品牌，各發貨點期初庫存和生產能力較為繁重。數據包括近400 個需求點，需求數量和時間、需求點與發貨點距離信息各有不同。企業使用的裝載車輛共有 3 種，裝載量分別為 1 500 件，750 件，650件。車輛的平均行駛速度為50km/h。發貨點與需求點的分布如圖5所示，三角形代表發貨點，圓點代表需求點。

在本文算例中，先以50km為拼車距離進行模型計算，即距離在50km之內的需求點的貨物可以通過同一輛車進行拼車運輸，由此確定出各倉庫的發貨日期和數量以及移庫的信息，再以50km為拼車距離進一步計算出具體的運輸路線、拼車安排。

本模型運算得到的部分具體調度明細如圖6所示。本文將得到的結果與該企業實際運營數據進行比較，具體見表1。

圖5 發貨點和需求點分布情況

表1 模型運算結果與實際數據比較

從表1可以看到，在無貨源計劃約束的應用場景下，其單位運輸成本下降了19.7%，出現成本大幅度下降的主要原因在于無貨源計劃約束不考慮貨源庫存。有貨源計劃約束模型與物流公司的實際運營情況比較貼近，因為該場景嚴格按照實際所提供的貨源來安排發貨計劃，其模型計算模擬出來的發貨計劃成本可以與實際運輸成本直接對比，用于評價模型的優化效果。從以上數據可以看出，單位運輸成本下降了9.8%，下降的幅度也比較明顯，另外發車次數也下降了8%，總滿載率提高了1.79%。

從數據可以看出，本文提出的模型及算法，通過有效的供需匹配和拼車計劃，能夠幫助企業大幅降低運輸成本，減少了發車次數，滿載率也得到了提高，減少了不必要的裝載空間浪費。

圖6 部分調度明細

6 數值實驗

在數值實驗部分，本文對算例進行了擴展，通過改變是否拼車、車型組合、拼車距離，來觀察決策變量是如何改變最優成本的。

（1）是否拼車。保持和算例相同的輸入，本文對比了優化算法中允許拼車和不允許拼車兩種情況，對比結果見表2，允許拼車使得11月的運輸成本下降了3.87 個百分點，同時也大幅減少了需要使用的車次。允許拼車的策略能夠充分利用運輸工具的裝載空間，從而大幅減少企業的運輸成本。

表2 是否拼車對結果的影響

（2）車型組合（1 500件，750件，650件）。在這部分，本文對現有的三種車型進行排列組合，探討不同車型組合對企業運輸成本的影響（如圖7）。本文將容量為1 500件、750件、650件的貨車分別定義為A、B、C，測試的車型組合包括：只使用A，只使用B，只使用C，使用A 和B，使用A 和C，使用B 和C，使用A、B和C。

可以看到當僅能使用一種車型進行運輸時（MN段），使用容量為1 500的貨車成本最高，而使用容量為650 的車輛的運輸成本最低，使用的車輛數最多，這是因為使用容量較大的貨車導致車輛滿載率降低，不僅運費較高，還有大量裝載空間被浪費。

圖7 車型組合對優化成本的影響

觀察僅使用兩種車型進行運輸的數據（PQ段）可以發現，使用兩種車型顯然相比僅用一種車型更加節約成本，同樣，當使用兩種最小的車型進行聯合運輸時，運輸成本是最低的。而使用三種車型進行聯合運輸時運輸成本在該實驗中達到了最低，多車型聯合運輸使得不同車輛能夠進行互補，避免了空間的浪費，從而使裝載空間利用率達到更高，進而節省了成本。

（3）最大允許拼車到貨點間距離參數。保持和算例相同的輸入數據，本文調整了模型求解中啟發式算法對拼車距離的限制，在拼車距離分別為0、50km、100km、150km、200km、250km、300km時進行計算，得到結果如圖8所示。可以看出，不拼車時，單位產品成本為8.026，滿載率達到了77.92%；而當拼車距離達到300 時，單位產品成本降低到了7.02，滿載率達到了84.85%。隨著拼車距離的增大，優化算法提供的計劃中單位產品成本在不斷降低，但滿載率在不斷升高。這說明，由于拼車距離加大，有更多的需求點進入允許拼車范圍內，從而算法能夠搜尋到使運輸成本越小的拼車計劃，車輛的滿載率得到提高，進而單位產品的運輸成本得到降低。

圖8 拼車距離對優化成本的影響

7 結論

本文針對煙草工業企業目前供應鏈存在的一些問題，在按時按量滿足各個到貨點需求等約束條件的基礎上，以成本最優的目標建立了理論模型，可以為煙草工業企業提高運營的效率，提高服務滿意度，對整個供應鏈可以進行更好的計劃和把控，同時使用Pyomo構建了算法，獲得了較好的求解效果。相比傳統的關于物流調度優化方法的文章，本文主要突出解決了以下幾個問題：（1）不僅僅只對物流調度的過程進行了優化，同時還對煙草工業企業每日的生產過程進行了優化，求解的結果包括每日每個倉庫的生產量，為各個倉庫的生產計劃提供指導建議；（2）更多地關注模型本身，使模型更加符合實際的情況，模型求解也會更加貼近于最優解；（3）在數值實驗里使用的數據來自于企業的真實數據，所以在實踐中本文的模型可以取得較好的效果；（4）模型具有普適性，對多車型、多品類的供應鏈調度研究具有一定指導意義。

除了優點之外，本文的研究目前依然也存在一些問題：（1）模型的約束條件較多，如果數據規模很大，會導致模型過于復雜，求解起來耗時較高，會產生一定的困難；（2）尋求的是最優解，沒有采用智能算法，雖然求出來的最終解較優，但是效率較低，在未來的研究中可以進一步完善。