申聰 董明

摘 要： 越庫（Cross-docking）作為一種高效的配送策略，具有降低庫存成本、加快商品轉運速度的特點，尤其適用于具有易腐特性的生鮮農產品。將車輛調度與車輛路徑問題集成為一個模型來考慮生鮮農產品的配送問題。以越庫中心轉運成本、存儲成本、車輛配送成本和貨損成本的總成本為優(yōu)化目標建立模型，設計了遺傳算法對模型求解，并進行數值實驗分析結果，驗證了模型和算法的可行性，得到了最優(yōu)的車輛與庫門的分配策略以及出庫車的的最優(yōu)配送路徑。

關鍵詞： 生鮮農產品;越庫中心;車輛調度;車輛路徑;遺傳算法

中圖分類號： F 50 ? 文獻標志碼： A

Abstract： As an efficient distribution strategy， cross-docking has the characteristics of reducing inventory costs and speeding up the transshipment speed of goods， especially for fresh agricultural products with perishable characteristics. This paper integrates vehicle scheduling and vehicle routing issues into a model to consider the distribution of fresh products. The model is established to minimize the total cost including the transshipment cost， the storage cost， the vehicle distribution cost and the corruption cost. Genetic algorithm will be designed to solve the model. Through the analysis of the example， the feasibility of the model and the algorithm is verified， and the optimal allocation strategy of the vehicle and the warehouse door and the optimal distribution path of the delivery vehicles are obtained.

Key words： fresh agricultural products; cross-docking center; vehicle scheduling; vehicle routing; genetic algorithm

隨著人們生活水平的提高，消費者對生鮮農產品的需求日益加大，對生鮮農產品配送的質量也提出了更高的要求。生鮮農產品主要指初級農畜產品，主要包括蔬菜水果、鮮肉蛋奶等產品。由于生鮮農產品具有易腐的特性，配送過程中的環(huán)境和時間會影響生鮮農產品的品質。提高生鮮農產品的物流效率和品質是零售企業(yè)搶占市場份額的必要手段。

越庫配送（cross-docking）是一種可以降低庫存和運輸流通時間的有效的配送策略，尤其適用于保質期短的生鮮農產品。實施越庫配送可以有效提高產品流動性，以達到降低庫存成本、減少存儲空間以及傳輸時間的目的，同時越庫配送也可以利用整車運輸來降低運輸成本。

回顧生鮮農產品以及越庫配送的相關文獻，Nahmials和Raafat研究了固定保質期以及隨機保質期的易腐產品的生產和庫存基礎系統(tǒng)。Zhang等人研究了在滿足產品質量的要求下最小化庫存與運輸成本的問題。Rong等人提出了一個食品生產與分配規(guī)劃的混合整數線性規(guī)劃模型，側重于供應鏈溫控對產品質量的研究。Zanoni 和 Zavanella構建了一個評估食品供應鏈和食品物流的概念框架，來控制在整個食品供應鏈中的產品質量、安全、持續(xù)性和物流效率。楊華龍等人結合了生鮮農產品的敏感特征，考慮產品因腐爛變質造成的成本損失，建立了基于生鮮農產品物流網絡布局的非線性規(guī)劃模型。陳杰等人研究了不確定環(huán)境下基于兩臺機器的越庫調度模型。Dwi等人研究了帶越庫中心的食品供應鏈車輛調度與車輛路徑混合整數線性規(guī)劃模型。麥家驥等人研究了考慮時間不確定環(huán)境下的循環(huán)取料情況，并建立了混合整數規(guī)劃的越庫調度模型。強瑞等人研究了轉運倉門的分配問題，并設計了高效的啟發(fā)式算法進行求解?？姵療樀热搜芯苛藥в袝r間窗和車輛容量限制的車輛調度問題并用遺傳算法進行求解，旨在合理分配倉門和越庫內部貨物來達到高效運作的目標。李敬峰等人將粒子群算法與改進粒子群算法還有遺傳算法進行對比，對倉門分配和貨車排序的問題進行了優(yōu)化。葛顯龍等人研究了供應商、零售商與一個配送中心還有多個配送中心的城市物流協(xié)同配送網絡，建立了車輛路徑模型，并設計了改進遺傳算法進行求解。侯宇超等人建立多目標路徑優(yōu)化模型，考慮客戶滿意度并利用了精英蟻群算法進行優(yōu)化。Dondo等人研究了越庫配送中心倉門分配以及車輛的排序問題。汪濤等人研究了基于改進人工蟻群算法對構建的生鮮農產品配送路徑模型進行優(yōu)化。

本文主要考慮產品為生鮮農產品，研究帶有越庫配送的車輛路徑問題（Vehicle Routing Problem with Cross-Docking， VRPCD），旨在通過車輛與庫門的合理分配，以及車輛配送路徑的研究，在考慮硬時間窗和生鮮農產品易腐特點的情況下，最小化以轉運成本、存儲成本、運輸成本、貨損成本組成的總成本，建立模型進行算法優(yōu)化，實現越庫中心內部的最優(yōu)調度與供應鏈的高效運作。

1 生鮮農產品帶越庫配送的車輛路徑問題模型構建

1.1 問題描述

本文研究的生鮮農產品帶越庫配送的車輛路徑問題的結構如圖1所示，由入庫車輛和入庫門、越庫操作中心、出庫門和出庫車輛，以及客戶所在節(jié)點組成。初始時刻，所有入庫車與出庫車均已到達越庫中心等待分配庫門，入庫車分配到入庫門后進行貨物卸載，通過重新分配，將訂單轉運到?？吭谙鄳鰩扉T的出庫車上。出庫車裝載完畢后再根據訂單信息將其配送到客戶手中。

1.2 模型假設

本文的生鮮農產品帶越庫配送的車輛路徑模型是由一個越庫中心向多個客戶節(jié)點進行配送。為簡化模型，對問題做如下假設：

（1）初始時刻，所有入庫車和出庫車均到達越庫中心等待調度;

（2）所有客戶訂單信息已知，訂單種類相同、數量不同;

（3）不考慮單一貨物體積，只考慮貨物重量;

（4）所有車輛均為同一類型，且容量已知;

（5）所有車輛與庫門必須都參與調度;

（6）越庫中心臨時存儲區(qū)域無限大;

（7）貨物在越庫中心轉運操作時，從入庫門到出庫門的操作時間與其距離成正比，且單位轉運成本相同;

（8）每輛出庫車都開始并結束于越庫中心;

（9）考慮貨物的腐敗率;

（10）每個客戶節(jié)點的需求僅由一輛出庫車完成配送。

1.3 模型構建

1.3.1 參數符號

D={0，1，2，…，n，n+1}：表示越庫中心及客戶集，其中1，2，…，n表示客戶，0表示越庫中心，n+1可以看成越庫中心的復制點，即出庫車均從配送中心出發(fā)，并且最終回到配送中心。

l={1，2，…，L}：入庫車輛集合。

f={1，2，…，F}：越庫中心的入庫門集合。

k={1，2，…，K}：出庫車輛集合。

h={1，2，…，H}：越庫中心的出庫門集合。

tupload：每個訂單卸載的時間。

tload：每個訂單裝載的時間。

atl：入庫車輛l到越庫停車區(qū)域的時間（初始時刻都為0）。

uil：如果訂單i在入庫車l上為1，否則為0。

[eti，lti]：表示客戶i可接受的時間窗。

qi：表示訂單i的大小。

tij：表示從節(jié)點i到節(jié)點j的行駛時間。

Q：表示出庫車輛k的最大載重量。

cfh：表示訂單從入庫門f轉運到出庫門h所用的操作時間。

B0：貨物初始狀態(tài)。

p：單位貨物的價格。

α：表示訂單從入庫門運送至出庫門的單位運輸成本。

β：表示在越庫配送中心的單位存儲成本。

γ：表示出庫車的單位運輸成本。

μ：貨物的腐敗率。

T：時間維度。

M：一個大數。

決策變量：

rtl：入庫車l分配給入庫門并且訂單開始卸載的時間。

Atk：出庫車輛k分配給出庫門的時間。

dtl：入庫車輛l完成卸載的時間。

Rtk：出庫車輛k離開越庫配送中心的時間。

vik：如果訂單i分配給出庫車輛k則為1，否則為0。

sik：出庫車輛k完成訂單i的時間。

wifh：如果訂單i從入庫門f轉運到出庫門h則為1，否則為0。

xlf：如果入庫車l分配給入庫門f則為1，否則為0。

Xll′f：如果入庫車l和l′都停靠在入庫門f，且入庫車l′離開后接著入庫車l?？縿t為1，否則為0。

ykh：如果出庫車k分配給出庫門h則為1，否則為0。

Ykk′h：出庫車k和k′都?？吭诔鰩扉Th，且出庫車k′離開后接著出庫車k?？縿t為1，否則為0。

zijk：如果出庫車k從節(jié)點i直接到達節(jié)點j則為1，否則為0。

1.3.2 成本分析

越庫中心操作成本： COST（operation）= ∑ni=1∑Ff=1∑Hh=1αqi cfh wifh。

越庫中心存儲成本：COST（inventory）= ∑i=1∑Ff=1∑Kk=1βqi uil vik （Rtk-rtl）。

配送運輸成本：COST（transportation）= ∑ni=0∑n+1j=1，j≠i∑Kk=1γtij zijk。

貨損成本：生鮮農產品在存儲運輸過程中，品質會隨著時間的增加而下降，這里采用易腐品的腐敗函數：B（t）=B0·e-μt。其中，B0表示貨物初始狀態(tài)，μ表示為腐敗率，腐敗率與環(huán)境溫度和產品自身特性等有關。本文假設整個過程中只考慮時間為產品腐敗帶來的影響，腐敗率相同為μ，進而獲得整個過程中的貨損成本。

COST（corruption） = ∑ni=1∑Ll=1∑Kk=1pqi B0 （1-e-μuil vik （Rtk-rtl）-μvik （sik-Rtk））

2.3.3 建立模型

在上述模型中：（1）表示入庫車輛開始卸載的時間不早于入庫車輛到達入庫的時間;（2）和（3）表示入庫車和出庫車離開越庫中心的時間限制;（4）表示訂單i在且僅在一輛入庫車上;（5）表示訂單i在且僅在一輛入庫車上;（6）表示訂單能且僅能從一個入庫門轉運到一個出庫門;（7）和（8）表示每輛車只可以分配到一個庫門;（9）和（10）表示所有庫門必須參與調度;（11）規(guī)定了在同一入庫門分配的挨著的兩輛入庫車前車的離開時間等于后車的卸載時間;（12）規(guī)定了在同一出庫門分配的挨著的兩輛出庫車前車的離開時間等于后車的?？康臅r間;（13）和（14）表示車輛在庫門?？康臅r間順序關系;（15）表示出庫車的載重限制;（16）表示所有入庫車訂單總量等于所有出庫車訂單總量;（17）表示每一輛出庫車都必須從越庫中心發(fā);（18）表示每一輛出庫車都必須回到越庫中心點;（19）表示每一輛出庫車都不能回到越庫中心0點;（20）表示每一輛出庫車都不能從越庫中心n+1點離開;（21）表示恰好有一輛出庫車為每個客戶提供服務;（22）表示每個訂單僅且僅被一輛出庫車送達;（23）表示限制出庫車輛的配送路徑;（24）表示s0k的初始值;（25）表示每個訂單必須在T時段配送完畢;（26）表示每個顧客訂單完成時間的關系;（27）和（28）表示訂單i的到達時間必須在要求的時間窗之內;（29）表示整數化約束條件。

2 算法設計

2.1 解結構設計

根據對生鮮農產品帶越庫配送的車輛路徑問題的描述，其對應的解可以分為兩部分：第一部分表示車輛與庫門的分配策略，第二部分表示出庫車輛的路徑分配。第一部分可以描述為In_x1，…，In_xL，Out_x1，…，Out_xK，長度為L+K（入庫車數目+出庫車數目）。設定變量中有車輛對應庫門的順序，因此其中In_xl只表示為入庫車L對應的入庫門，Out_xk只表示出庫車k對應的出庫門;第二部分可以描述為Out_11，…，Out_21，…，Out_K1，…，長度為需求點的總數目n，其中Out_k1，…代表出庫車k對應的路徑。因此問題的解的結構可以表示為

{In_x1，…，In_xL，Out_x1，…，Out_xK，Out_11，…，Out_21，…，Out_K1，…}。

2.2 編碼設定

本文根據解結構的設計，對其組成的兩部分分別進行編碼。解結構的第一部分是車輛與庫門的分配問題，由于每個庫門可以對應多輛車，因此這部分染色體編碼可以相同，本文采用整數編碼（自變量取整操作），例如1 2 2 1 2;第二部分是車輛路徑問題，涉及順序問題，染色體編碼不能相同，這里采用序列編碼，例如4 3 1 2 5。

假設有1輛入庫車、1個入庫門、2個出庫車、2個出庫門、10個需求點，則染色體編碼可以為以下形式：

1 1 2 4 9 10 8 7 2 1 6 3 5

解碼后結果可能形式如下：

入庫車門1停靠入庫車1;

出庫車門1?？砍鰩燔?;

出庫車門2?？砍鰩燔?;

出庫車1配送路線：0-4-9-10-8-7-0;

出庫車2配送路線：0-2-1-6-3-5-0。

2.3 初始解的生成

根據參數設置，初始解第一部分為隨機產生的（L+K）個整數，要求前L個整數取值為[1∶F]，后K個整數取值為[1∶H];初始解的第二部分為序數整數，要求數量為需求點個數n，且數字為1～n的某個順序，不存在重復數字。

2.4 適應度函數

遺傳算法通過適應度函數聯系需要解決的具體問題。適應度值是種群中個體對環(huán)境的適應程度。適應度函數與優(yōu)化目標存在一種對應關系，也是將具體問題抽象化成數學模型的過程。考慮到本文模型，需要目標函數總成本最小化，這里采取總成本的倒數表示適應度函數。個體的適應度值越大，表示目標函數總成本越小，個體適應環(huán)境的程度越好。

Fitness= 1COST

2.5 選擇

選擇是優(yōu)勝劣汰的一種操作，目的是把優(yōu)秀的解直接遺傳到下一代或者通過配對交叉產生新的個體再遺傳到下一代，整個操作是基于群體中適應度評估基礎上的。

這里采用隨機遍歷抽樣法，具體操作如下：

1）計算種群中每個個體的適應度;

2）計算個體遺傳到下一代的概率：

P（xi）=f（xi）∑nj=1f（xj）

3）計算累計函數：

qi=∑ij=1P（xj）

4）設n為需要選擇的個體數目，等距離選擇個體，選擇指針的距離為1/n，第一個位置為[0，1/n]的均勻隨機數決定，以此類推得到所有需要選擇得個體。

2.6 交叉操作

第一部分：單點交叉，是指只在個體的編碼串中隨機取一個交叉點，然后兩條染色體在這個交叉點互相交換基因片段。 第二部分：部分映射交叉，是指對父代中的兩個交叉點所屬的部分基因互相建立的一種映射關系。在基因交換后，根據所建立的映射關系將沖突的基因消除。交叉過程如圖2所示。

2.7 變異操作

第一部分：單點變異，根據變異概率在基因串中選取一位進行變異，數值變異范圍為自變量取值范圍。第二部分：互換變異。變異過程如圖3所示。

2.8 逆轉操作

只針對第二部分：被選擇兩個位置之間所有數字逆轉，如圖4所示。

2.9 重插入子代的新種群

父代經由交叉產生子代，根據代溝設置，將子代適應度最差部分丟棄，將同等數量父代適應度值最高種群插入子代，獲得新種群。過程如圖5所示。

2.10 算法步驟

步驟1：參數設置，包括種群規(guī)模大小、交叉概率、變異概率和最大迭代次數。

步驟2：初始種群的生成，根據問題描述和解結構的設計，將其分為第一部分整數編碼，第二部分序數編碼，并生成初始種群。

步驟3：適應度函數設置，這里將總成本的倒數作為適應度函數，計算種群中個體的適應值。

步驟4：選擇，根據隨機遍歷選擇法，從種群中選取進入下一代的個體。

步驟5：按照交叉概率，對種群進行交叉操作，其中解結構中第一部分種群進行單點交叉，第二部分進行部分映射交叉。

步驟6：根據變異概率，對種群進行第一部分單點變異及第二部分進行互換變異。

步驟7：沒有滿足迭代次數，轉回進行步驟2直到達到設置的迭代次數為止。

步驟8：輸出種群中滿足條件的最優(yōu)個體作為問題的解。

遺傳算法流程如圖6所示。

3 數值實驗

3.1 算例設計

參考文獻的數據，設計算例。某生鮮農產品越庫配送中心，收到了16個來自其覆蓋范圍的訂單。入庫車根據訂單信息已經取貨，并到達越庫中心，配送中心入庫車、出庫車載重限制均為1500kg，車輛單位時間配送成本為1.3元/min。入庫車共7輛，入庫門3個，出庫車5輛，出庫門3個，入庫門到出庫門的單位時間轉運成本為0.01元/min，對應轉運時間如表1所示。入庫車負載訂單情況如表2所示。16個需求點、客戶訂單時間窗、配送需求量如表3所示。越庫中心點到客戶需求點的配送時間如表4所示。其他參數如表5所示。

3.2 算法求解

遺傳算法參數如表6所示，運行10次結果如表7所示。

從遺傳算法運行結果可以得出，平均總成本為4031.712，最小總成本為3628.23，此時車輛與庫門的分配方案如下：

入庫門1：5->6;

入庫門2：1->7;

入庫門3：3->4->2;

出庫門1：5;

出庫門2：3;

出庫門3：1->2->4。

出庫車配送方案如下：

第 1 輛車路徑：0->10->8->1->0;

第 2 輛車路徑：0->7->5->4->0;

第 3 輛車路徑：0->14->9->15->0;

第 4 輛車路徑：0->6->11->12->0;

第 5 輛車路徑：0->16->13->2->3->0。

數值實驗結果表明本文模型可以應用于生鮮農產品帶越庫配送問題中，遺傳算法可以得出越庫配送中心車輛與庫門的有效分配，以及出庫車的最優(yōu)配送方案。

4 結論

本文同時考慮了越庫中心車輛調度問題和車輛配送路徑問題，基于客戶訂單的時間窗，考慮到生鮮農產品的腐敗率，以越庫中心轉運的操作成本、庫存成本、交通運輸成本、貨損成本總成本最小化為目標，構建了復合模型。設計遺傳算法求解，同時應用了兩種解碼方式構建初始解。數值實驗表明，生鮮農產品在越庫配送模式下能夠更好地整合供應鏈上的各種資源，能夠合理分配越庫中心車輛與庫門的調度，給出在最低總成本下的車輛與庫門的分配方案和合理的車輛配送路徑，對于現實應用具有很大的參考價值。

此外，本文的研究還有不足之處，可以考慮在冷鏈物流、取送貨過程與多配送中心三個方面進行下一步的深入研究。

參考文獻：

[1] 陳軍， 但斌. 基于實體損耗控制的生鮮農產品供應鏈協(xié)調[J]. 系統(tǒng)工程理論與實踐， 2009， 29（3）.

[2] LEE Y H， JUNG J W， LEE K M. Vehicle routing scheduling for cross-docking in the supply chain[J]. Computers and Industrial Engineering， 2006， 51（2）：247-256.

[3] NAHMIAS， STEVEN. Perishable inventory theory： a review[J]. Operations Research， 1982， 30（4）：680-708.

[4] RAAFAT F. Survey of literature on continuously deteriorating inventory models[J]. The Journal of the Operational Research Society， 1991， 42（1）：27-37.

[5] ZHANG G， HABENICHT W， SPIE W E L. Improving the structure of deep frozen and chilled food chain with tabu search procedure[J]. Journal of Food Engineering， 2003， 60（1）：67-79.

[6] RONG A， AKKERMAN R， GRUNOW M. An optimization approach for managing fresh food quality throughout the supply chain[J]. International Journal of Production Economics， 2011， 131（1）：421-429.

[7] ZANONI S， ZAVANELLA L. Chilled or frozen？ Decision strategies for sustainable food supply chains[J]. International Journal of Production Economics， 2012， 140（2）：731-736.

[8] 楊華龍， 計瑩峰， 劉斐斐. 生鮮農產品物流網絡節(jié)點布局優(yōu)化[J]. 大連海事大學學報， 2010， 36（3）：47-49.

[9] 陳杰， 陳峰. 不確定環(huán)境下的越庫調度的模型及算法[J]. 工業(yè)工程與管理， 2010， 15（1）：97-102.

[10] AGUSTINA D， LEE C K M， PIPLANI R. Vehicle scheduling and routing at a cross docking center for food supply chains[J]. International Journal of Production Economics， 2014（152）：29-41.

[11] 麥家驥， 陳峰. 基于循環(huán)取料的不確定越庫調度模型與算法[J]. 上海交通大學學報（自然科學版）， 2011， 45（2）： 159-0163.

[12] 強瑞， 繆朝煒， 吳為民. 供應網絡中越庫轉運中心倉門分配問題研究[J]. 管理工程學報， 2011， 25（1）：209-215.

[13] 繆朝煒， 蘇瑞澤， 張杰. 越庫配送車輛調度問題的自適應遺傳算法研究[J]. 管理工程學報， 2016， 30（4）， 166-171.

[14] 李敬峰， 葉艷， 傅惠. 面向貨物裝卸需求的越庫倉門分配和貨車排序[J]. 工業(yè)工程， 2016， 19（2）：112-120.

[15] 葛顯龍， 鄒登波. 供應鏈環(huán)境下帶越庫配送的車輛路徑問題[J]. 計算機工程與應用， 2018（24）：252-259.

[16] 葛顯龍， 鄒登波. 供應鏈環(huán)境下帶越庫配送的多配送中心車輛路徑問題[J]. 控制與決策， 2018， 33（12）：60-67.