分布式制造供應鏈低碳集貨模型與算法研究

史雨同，尹 靜，王柏琳

（1.北京建筑大學 機電與車輛工程學院，北京 100044；2.北京科技大學 東凌經濟管理學院，北京 100083）

分布式制造供應鏈低碳集貨模型與算法研究

史雨同1，尹 靜1，王柏琳2

（1.北京建筑大學 機電與車輛工程學院，北京 100044；2.北京科技大學 東凌經濟管理學院，北京 100083）

針對我國當前嚴峻的環境形勢和節能減排的現實要求，研究了低碳環境下分布式制造供應鏈節點集貨問題，研究過程中應用了最小碳排放和最短路徑的多目標優化模型。算法上設計了三階段集成啟發式方法分步求解，首先采用遺傳算法找到最短路徑的集貨方案；在此基礎上采用節約算法的基本思想進行路徑拆分和車輛匹配，降低碳排放水平；最后通過計算碳排放節約值對集貨方案進行局部重組，進一步優化碳排放指標。仿真實驗表明，分階段的求解方法可以設計出碳排放更優的解，同時滿足經濟效益和環境效益。

制造供應鏈；碳排放；集貨模型；路徑優化

1 引言

隨著網絡時代的到來，以往所有零部件自有生產模式已經無法經受市場的考驗，很多制造企業特別是汽車公司趨向于采用分布式制造模式。由于生產不同零件的廠商分散在不同的地理區域，導致集貨過程中物流成本上升和碳排放問題日益突出，減少集貨過程中的成本和碳排放，成為我國當前經濟發展的重要課題。

運輸成本和距離是之前集貨問題研究的主要目標，因此大多數學者將集貨問題歸于車輛路徑問題（Vehicle Routing Problem VRP）進行研究。前期的研究主要集中于無時間窗要求的VRP問題，潘震東等[1]研究了帶貨物權重的VRP問題，馬天宇等[2]用遺傳算法研究了分區的多配送中心車輛調度問題。隨著JIT思想在制造行業中普及，對配送時間的要求越來越高，產生了帶時間窗的車輛路徑問題（Vehicle Routing Problem with Times Windows,VRPTW)。Ziauddin U等[3]設計出局部優化框架，并結合遺傳算法解決了帶時間窗的車輛路徑問題。Tan K C等[4]采用啟發式與合并式相結合的交叉算子，融入了爬山算法和自適應變異機制，設計出了改進遺傳算法解決VRPTW問題。

2009年哥本哈根全球氣候峰會以來，我國對環境的重視程度越來越高，碳排放成為我國環境保護的重要指標。減少集貨過程中的碳排放量成為國內學者與企業管理人員關注的焦點。目前以減少碳排放為目標的集貨問題研究還比較少，邱雅君等通過改進遺傳算法求解了考慮碳排放因素的VRP問題[5-6]。Kirby認為車輛碳排放與燃油消耗成正比，可以將碳排放量和油耗問題一起研究[7]。史春陽[8]在給出了公路運輸中二氧化碳排放的計算方法后，針對同時取送貨的車輛路徑問題（VRPSPD）進行了低碳研究。

本文以最小碳排放和最短距離為目標建立多目標優化模型。碳排放的計算基于油耗，運輸過程需滿足時間窗和載重等多重約束，并考慮車型多樣和車輛數有限的情況。本文在算法設計方面采用了基于遺傳算法和啟發式節約算法的分階段法，分步求解最短路徑和最小碳排放問題，結果表明，該算法可用于解決低碳車輛路徑問題，找到低碳的集貨方案。

2 問題描述和數學模型

2.1 問題描述

本文研究問題可描述為：配送中心派遣一組車輛前往供貨商處取貨，然后返回配送中心。供貨商的地理位置、供貨數量、供貨時間窗和裝貨時間已知；配送中心保有多種類型的車輛且每種車型數量已知；車輛行駛過程看作勻速過程。目標是在滿足各種約束的前提下，找到總路徑最短和碳排放量最小的車輛選擇和路徑安排。集貨過程中的約束如下：

（1）配送中心約束：所有車輛由配送中心駛出，完成取貨任務后返回配送中心；

（2）車輛約束：配送中心有多車型的貨車，每種車型的數量和參數已知；

（3）訪問唯一性約束：每個供貨商只能被一輛車一次性服務；

（4）載重約束：每種類型車輛的裝載量需滿足該車型的容量限制；

（5）時間窗約束：供貨商只能在規定的時間窗內被車輛服務，如果車輛到達的時間早于最早開始服務時間，車輛將在供貨商處等待，如果車輛在最晚開始服務時間之后到達，則產生不可行解；

（6）裝貨時間約束：車輛到達供貨商后需完成裝貨過程，裝貨時間固定且已知；

（7）速度約束：行駛過程中所有車輛以相同的速度勻速行駛。

2.2 符號和決策變量

G=(V,E)：物流配送網絡；

V：供貨商集合，V={0,1,2,…,n},其中0表示配送中心，其他數表示供貨商；

E：弧集，E={(i,j)|i,j∈V,i≠j}；

P：表示一條從配送中心出發，完成服務過程又回到配送中心的路徑；

Pi,j,…：表示包含供貨商i,j,…的路徑，i,j,…∈V；

Dij：弧（i,j）的距離；

Rij：車輛行駛Dij所用的時間；

Si：供貨商i開始服務的時間；

Ti：供貨商i的裝貨時間；

[ETi,LTi]：供貨商i的時間窗，其中ETi為最早開始服務時間，LTi為最晚開始服務時間；

k：表示車輛集合，k={1,2,…,kK}；

Qijk：車輛k從i發往j的過程中的載重；

m：表示車型集合，m={1,2,…,mM}；

Nx：x車型的數量；

Qx：x車型的容量；

Ui：供貨商i的供貨量。

UP：路徑P的集貨量，UP=∑Ui，i為路徑P上的供貨商。

決策變量定義為：

2.3 碳排放計算

本文根據實際問題的需要，采用文獻[8]中史春陽等的計算方法，忽略了速度和道路坡度的影響，采用了以排放系數、行駛距離和裝載量為基礎的油耗計算方法：

然后由油耗來計算碳排放量：

本文碳排放的數學模型采用三下標模型（threeindex model），前兩個下角標表示兩端的供應商，第三個角標表示選擇的車輛[9]，如下：

其中，F為燃油消耗；D為行駛距離；Q為車輛當前載重；a,b為燃油排放系數；M為碳排放量；η為燃油轉換系數；Mijm為m類型的車從供貨商i到j的碳排放量；Dij為i到j的距離；am和bm為m類型車的燃油消耗系數；Qijk為車輛k在i和j運輸過程中的載重。

從式（3）-式（5）可知，碳排放和車輛排放系數相關，和行駛距離成正比，和負載量成正線性相關。

2.4 多目標優化模型

本文研究的最短路徑和最小碳排放集貨問題可表示如下：

式（6）表示運輸過程中總路徑最短；式（7）表示運輸過程中碳排放量最小；式（8）表示載重限制；式（9）表示一個供應商能且只能被一輛車服務，并且只能被訪問一次；式（10）-（12）表示所有由k車集貨的點構成一條Hamilton回路；式（13）表示車輛數為所有類型車輛的總和；式（14）、（15）表示配送中心限制；式（16）表示時間窗限制；式（17）表示決策變量的取值范圍。

3 算法設計

由于本文研究的集貨問題屬于NP-hard問題，不能直接計算出最優解。本文采用遺傳算法和啟發式算法相結合的分階段法尋找最小碳排放的集貨策略。算法階段1在多約束前提下用遺傳算法求解最短路徑問題。算法階段2對階段1中結果中的每條路徑進行路徑拆分和車輛匹配，結合不同車型數量的約束選擇碳排放最小的路徑拆分方法。階段3完成路徑局部重組，將負載率較低的路徑作為優化目標，通過合并其他供貨商節點的方式進一步降低集貨過程中的碳排放量。

任意路徑上的車型選擇原則為：在車型集合m中，選擇車輛容量Qx≥UP且最接近UP的車型作為集貨車輛，不考慮車輛數量的限制。

3.1 最短路徑遺傳算法

階段1首先不考慮碳排放的因素，將集貨問題轉換為帶時間窗、最大載貨量和車輛數限制的VRP問題，并采用遺傳算法進行求解，計算過程如下：

（1）編碼生成。本文采用自然數編碼，每個染色體S代表一個路徑解，即一種路徑規劃方案。它由若干條子路徑的集合組成，S={P1,P2,…,Pn}。每條

子路徑為若干供貨商節點的集合，P…i,j,…={…i,j…}，由一輛車按照先后順序裝載集貨。（2）生成初始種群。按照編碼生成方式生成路徑解，根據約束檢查判斷是否為可行解。最終生成一組數量為NC的染色體種群作為初始種群。

時間約束檢查：

對于E路徑P中的兩個相鄰節點i和 j（i在 j之前），如果ETi+Ti+Rij≤LTj，則滿足時間窗約束，否則不滿足。

載重約束檢查：

對于可用車型1，2，…，mM，車型數量分別為N1,N2,…,NmM，載重量分別為 Q1,Q2,…,QmM，有Q＜Q2＜…＜QmM。 如 果 UP＜Q1 的 個 數，則滿足載重約束，否則不滿足。

（3）適應度的計算。本文的適應值函數fh=1/Z，fh是種群中個體生存能力的表現，fh越大表明其性能越好，即其對應的解越接近最優解。

（4）選擇。將每一代產生的染色體按適應度值從小到大排列。第一個染色體直接進入下一代，剩下的染色體則通過輪盤賭的方式進行選擇，最終有NC個個體進入下一代。一個個體被選擇的概率為：

這里，f(xi)為個體xi的適應度，F(xi)為個體被選擇的概率[10]。

（5）交叉。選擇[Nc/2]對染色體進行隨機配對，交叉概率為PC，具體操作為：產生一個（0，1）內的隨機數r，如果r≤PC，則將配對的染色體進行交叉。本文采用連續正向交叉的方式。

（6）變異。按變異概率Pm對染色體進行變異操作，具體操作方式為：產生一個隨機數r，若r≤Pm，則進行變異操作。變異算子為對換變異。

（7）停止。當算法迭代代數達到Nn時，停止進化，輸出適應度最大的染色體對應的路徑作為最優解。

本算法輸出結果為一組路徑{P1,P2,…,Pn}，根據每條路徑的集貨量依據車型選擇原則選擇車型，確定集貨方案。

3.2 路徑拆分與車輛匹配

通過上述遺傳算法可以解決最短路徑問題，本文算法階段2采用節約算法的基本思想對每一條路徑進行拆分和車輛匹配，尋找碳排放更少的集貨方案。具體計算步驟如下：

首先定義碳排放節約值：

Mpi表示路徑Pi的碳排放。

某條擁有n個供貨商的路徑的拆分步驟如下：

Step 1：讓各個供貨商單獨送貨，形成初始路徑P1,P2,…,Pn。

Step 2：令k=2，3，...，n，依次執行以下步驟：

（1）計算任意k個路徑Pi,Pj,…,Pk的節約值s(Pi,Pj,…,Pk)，并將其定義為數組。

（2）若s(Pi,Pj,…,Pk)的值均 ≤0，則轉入Step 2（4）；否則在節約值s(Pi,Pj,…,Pk)內求出值為最大的那一 項s(…Pi,Pj,…)，將路徑 …Pi,Pj,… 合并為P…i,j,…，轉入Step 2（3）。

（3）計算新路徑下的節約值s(Pi,Pj,…,Pk)，轉入Step 2（4）。

（4）記錄下當前的路徑安排和車輛選擇，計算當前碳排放Mk。

Step 3：比 較M2、M3、…Mn的 值 ：若?k∈[ ]

2,n-1，有Mk≤Mn，說明該路徑上的路徑拆分不能減少碳排放，則路徑不予拆分，算法結束；否則轉Step4進行路徑拆分。

Step4：計算Mk-Mn（?k∈[ ]2,n-1），取其中的最大正數作為碳排放節約值，并記錄相應的路徑拆分車型選擇。

通過以上路徑拆分方法可以輸出一組數據{En.Pn,kn,Pn',kn'}，其中En為＞0的碳排放節約值；Pn為En在最短路徑的遺傳算法結果中對應的路徑；kn為Pn占用車輛集合；Pn'為En對應的拆分后的路徑；kn'為Pn'占用車輛集合。記所有車輛的集合為k，最短路徑的遺傳算法結果中占用車輛集合為k0，車型可用集合初始值k*為（k-k0），車輛匹配步驟如下：

Step 1：將路徑拆分后得到的En定義為數組，在所有路徑Pn中設置選擇參數“已拆分/未拆分”，并將初始狀態設置為“未拆分”。

Step 2：如果所有En都≤0，則結束該算法；如果有En＞0，找到En中的最大量E1和路徑拆分方法結果中E1對應的P1,k1,P1',k1'，將E1定義為0，轉入Step 3。

Step 3：如果路徑P1選擇參數為“已拆分”，則轉入Step 3；否則轉入Step 4。

Step 4：如果 (k-k0+k1-k1*)中所有車型數都≥0，則按該拆分方法進行路徑拆分和車輛匹配，將P1定義為該拆分方法進行路徑拆分和k*更新為（k*+k1-k1

*），轉入Step 2，否則直接轉入Step 2。本算法在不同車型數量的約束條件下尋找碳排放最優的路徑拆分和車輛匹配方法，生成新的集貨方案。由于最短路徑遺傳算法中的解是在硬時間窗的約束條件下求得的，拆分后的路徑和車輛選擇仍滿足時間窗的要求。

3.3 路徑局部重組

通過路徑的拆分可以找到碳排放更少的集貨方案，但路徑拆分只能在階段1最短路徑的基礎上尋求每條路徑上的碳排放最小集貨方法，而沒有考慮路徑間的重組。本文算法第3階段對只有一個供貨商的路徑與其他路徑進行局部重組，尋找碳排放更少的集貨方法。

局部重組的基本思想是：讓由一輛車單獨服務的供貨商與其他供貨商組成新的路徑，參與重組供貨商從原路徑拆分出后也形成一條新的路徑，計算重組前后的碳排放節約值，尋找碳排放更低的集貨方案。通過時間窗的約束和局部重組前后碳排放的對比驗證局部重組的可行性。

對于只有一個供貨商i的路徑Pi，路徑重組的步驟如下：

Step 1：對于路徑拆分和車輛匹配算法輸出的路徑組合，將供貨商j(j∈n且j≠0,j≠i)從原路徑Pj中拆分出來，與i組成新路徑Pi,j，Pj中剩余供貨商組成新路徑Pj'，計算碳排放節約值s(i,j)。碳排放節約值的計算方法為：s(i,j)=WPi+WPj-WPi,j-WPj'。

Step 2：對供貨商i和j進行時間約束檢查。如果滿足時間約束，則轉入Step 3，否則令s(i,j)=0，轉入Step 3。

時間約束檢查：

如果供應商i和j同時滿足ETi+Ti+Rij＞LTj;ETj+Tj+Rij＞LTi，則i和j不滿足時間約束；否則滿足。

Step 3：對供貨商i和j進行車型數量約束檢查。如果滿足車型數量約束，則轉入Step 4；否則令s(i,j)=0，轉入Step 4。

車型數量約束檢查：

所有車輛的集合為k，拆分集貨方法已用車輛集合為k0，路徑Pj和Pi所用車輛集合為k1，路徑Pi,j和Pj'所用車輛集合為k2，如果集合（k-k0+k1-k2）中所有車型數都≥0，則滿足車型數量約束，否則不滿足約束。

Step 4：找出碳排放節約值最大值Max s(i,j)，記錄相應的路徑重組和車型匹配方法。

對所有由一輛車單獨集貨的供貨商執行以上操作，在車型數量約束條件下尋找最優的路徑重組策略。

4 算例分析

4.1 參數設置

本文算例與數據來源于國內某大型物流企業A為華晨寶馬汽車裝配線B供貨的實際問題。B在上海市附近有50家供貨商，供貨商的位置已知，每天有不同的供貨商按照生產計劃需求給總裝廠供貨，B與其供貨商共同擬訂供貨時間窗和裝貨時間，供貨廠家以及數量等信息會提前發送給A企業，然后由A企業分派車輛完成集貨任務，所有車輛從上海配送中心出發，遍歷所有的供貨商，完成集貨過程然后返回配送中心。

配送中心和供貨商的地理位置已知，配送中心擁有的車輛類型和數量已知。某天共有15家供貨商需要為A供貨，具體數據見表1，位置如圖1所示。

表1中序號0代表配送中心，1-15代表15家供貨商。配送時間為8點至第二天6點。時間單位為0.1h，也就是6min。從8點開始計時，車輛要在220個時間單位也就是22h內完成集貨并回到配送中心。長度單位為5km，文中忽略了速度對碳排放的影響，假設車輛以速度50km·h-1勻速行駛。配送中心共有3種類型10輛車可供使用，車輛的具體信息見表2。

表2 車輛信息

車輛的里程數不限，燃油轉換率取2.610kg·L-1[11]。某類型車輛的每公里碳排放可根據排放標準A和排放標準B及燃油轉換率η參考式（3）。

4.2 計算結果

（1）最短路徑的遺傳算法：種群規模Nc取50，交叉概率Pc設置為0.5，變異概率Pm設置為0.05，更迭代數Nn取1 000。每種目標函數下運行20次，路徑最短集貨方案見表3，路徑如圖2所示。

表3 階段1集貨方案

圖2 階段1的路徑

（2）路徑拆分與車輛匹配算法：分別對最短路徑遺傳算法產生的5條路徑進行拆分，尋求碳排放最小的拆分方法。結果如下：（0-10-1-9-15-0）；（0-12-4-5-13-0）；（0-6-0）三條路徑任何拆分方法都不能減少碳排放，不進行拆分。（0-2-11-3-0）在拆分為（0-2-11-0）和（0-3-0）時，碳排放節約值為8 130.15kg；根據已有車型數量限制和車型選擇原則，路徑拆分和車輛匹配后的集貨方案見表4，路徑如圖3所示。

表4 階段2集貨方案

（3）路徑局部重組算法：對路徑拆分與車輛匹配算法產生的的單點路徑進行局部重組，尋找碳排放更小的集貨方法。重組后的集貨方案見表5，路徑如圖4所示。

各階段得到的集貨方案行駛距離和碳排放指標數值見表6。

表1 配送中心和供貨商信息

圖3 階段2的路徑

表5 階段3集貨方案

圖4 階段3的路徑

表6 運算結果

由表6可知，從階段1的最短距離集貨方案到階段3的最小碳排放集貨方案，距離僅增加了33km，碳排放降低了0.14t，在最短距離方案的基礎上降低碳排放量，同時優化經濟效益與環境效益，是切實可行的。

5 結語

低碳環境下分布式制造供應鏈集貨問題的研究是我國現階段面對的重要課題，對于推廣“綠色物流”，完成節能減排目標有著重大意義。針對該問題，本文提出了基于油耗的碳排放計算方法，將路徑優化和最小碳排放量結合起來，建立統一的多目標優化模型。為了降低計算復雜度，本文設計了分階段算法進行求解。首先用遺傳算法解決最短車輛路徑問題，產生初始集貨方案，進而基于節約算法的基本思想對所得方案中的路徑進行拆分和重組，根據車型數量限制匹配車輛，得到更為低碳的集貨方案。實例中拆分重組后的集貨方案較之前降低了0.14t碳排放量，可以看到本文提出的模型和算法是有效的。

本文碳排放量應用了考慮車型、運載量和行駛距離的計算方法，沒有考慮行駛速度和路況等因素的影響，未來可進一步深入探討，同時可以考慮提取問題特征，將智能搜索與進化計算方法結合起來設計開發求解算法，提高計算效率，降低問題的計算復雜度。

[1]潘震東,唐加富,韓毅.帶貨物權重的車輛路徑問題及遺傳算法[J].管理科學學報,2007,10(3):23-29.

[2]馬宇紅,姚婷婷,張浩慶.基于分區的多配送中心多車型車輛調度問題與遺傳算法設計[J].科技導報,2013,31(2):61-67.

[3]Ziauddin U,Daryl E.Localized genetic algorithm for vehicle routing problem with time windows[J].Applied Soft Computing,2011,11(8):537-539.

[4]Tan K C,Lee L H,Zhu Q L.Heuristic methods for vehicle routing problem with time windows[J].Artificial Intelligence in Engineering,2001,15(3):281-295.

[5]邱雅君,宋國防.考慮碳排放因素的車輛路徑問題研究[J].物流技術,2012,(7):222-226.

[6]雷兆明,王東東,廖文喆,等.Levy人工蜂群在鋼鐵企業供應端的優化[J].科學技術與工程,2016,(28):251-258.

[7]Kirby H R,Hutton,Quaid R W.Modeling the effects of transport policy levers on fuel efficiency and national fuel consumption.Transport research part D[J].Transport and Environment,2000,5(3):265-282.

[8]史春陽,趙磊.同時取送貨的車輛路徑問題中的低碳研究[D].北京:清華大學,2011.

[9]Montane F,Galvao R D.A tabu search algorithm for the vehiclerouting problem with simultaneous pick-up and delivery service[J].Computers&Operations Research,2006,33:595-619.

[10]雷英杰,張善文.MATLAB遺傳算法工具箱及應用[M].西安:西安電子科技大學出版社,2014.

[11]Ubeda S,Arcelus F J,Fanlin J.Green logistics at Eroski:A case study[J].International Journal of Production Economics,2011,131:44-51.

Study on Low-carbon Cargo Consolidation Model and Algorithm of Distributive Manufacturing Supply Chain

Shi Yutong1,Yin Jing1,Wang Bailin2
(1.School of Electrical&Mechanical Engineering,Beijing University of Civil Engineering&Architecture,Beijing 100044;2.Dongling School of Economics&Management,University of Science&Technology Beijing,Beijing 100083,China)

In this paper,in view of the several environment condition in China and the realistic demand of the initiative to cut energy consumption and emissions,we studied the issue of cargo consolidation of a distribution manufacturing supply chain within the low-carbon environment,during which the optimization model that intended to both minimize carbon emissions and distribution distance was used;the on such basis,we approached the route division and vehicle matchmaking following the fundamental principle of the saving algorithm so as to lower the carbon emissions level;and at the end,we regrouped partially the cargo consolidation solution in light of the calculation result to further optimize the carbon emissions index,the validity of which was demonstrated through a simulation study.

manufacturing supply chain;carbon emissions;cargo consolidation model;route optimization

F224.0;F274

A

1005-152X(2017)10-0114-07

10.3969/j.issn.1005-152X.2017.10.023

2017-09-04

北京市自然科學基金項目（9174038）；北京市教委科技計劃面上項目（Z14012）；長城學者計劃（CIT&TCD20150312）

史雨同（1992-），男，河南開封人，碩士生，主要研究方向：物流系統調度與仿真；尹靜（1978-），女，通訊作者，河北石家莊人，副教授，博士，碩士生導師，主要研究方向：生產調度與物流優化；王柏琳（1983-），女，河北石家莊人，講師，博士，主要研究方向：生產計劃與調度。