李善俊 陳淮莉

摘要：考慮到生鮮品的易腐性、高時效性和對運輸環(huán)境要求高的特點，為減少生鮮品配送企業(yè)的配送成本，提高客戶滿意度，在車輛載重、時間窗、生鮮品保質期等約束條件下，提出將配送總成本最小化和生鮮品新鮮度最大化的多目標車輛路徑優(yōu)化模型。利用改進的非支配排序遺傳算法（non-dominated sorting genetic algorithm Ⅱ，NSGA Ⅱ）對模型進行求解。求出滿足配送總成本最小和生鮮品新鮮度最大的相對較優(yōu)解，證明模型的有效性。該模型在大規(guī)模配送和客戶地理位置分布較為分散的情況下，對生鮮品新鮮度的優(yōu)化較為明顯。

關鍵詞： 生鮮品配送; 多目標優(yōu)化; 非支配排序遺傳算法（NSGA）; 帶時間窗的車輛路徑問題（VRPTW）

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

Optimization of fresh food distribution route with

time window based on NSGA II

LI Shanjun， CHEN Huaili

（Institute of Logistics Science & Engineering， Shanghai Maritime University， Shanghai 201306， China）

Abstract： Considering the characteristics of fresh food perishability， high timeliness and high demand for transportation environment， in order to reduce the distribution cost of fresh food distribution companies and improve customer satisfaction， under the constraints of vehicle load， time window and shelf life of fresh food， a multi-objective vehicle route optimization model is proposed to minimize the total cost of distribution and maximize the freshness of fresh food. The model is solved by an improved non-dominated sorting genetic algorithm （NSGA II）. A relatively better solution satisfying the minimum total cost of distribution and the maximum freshness of fresh food is obtained， which proves the validity of the model. The optimization on the freshness of fresh food by the model is obvious under the condition of large-scale distribution and scattered distribution of customers.

Key words： fresh food distribution; multi-objective optimization; non-dominated sorting genetic algorithm （NSGA）; vehicle routing problem with time window （VRPTW）

0 引 言

近年來，互聯(lián)網(wǎng)的迅猛發(fā)展讓生鮮企業(yè)的業(yè)務范圍從線下延伸到了線上，生鮮電商企業(yè)迎來了飛速發(fā)展的黃金時期。鑒于生鮮品易腐爛、高時效性的特點，對生鮮品配送企業(yè)提出了比傳統(tǒng)的物流配送更高的要求。生鮮品的配送是生鮮電商的重要組成部分，也是影響生鮮電商企業(yè)發(fā)展的最大的一塊絆腳石。

國內外許多學者，對生鮮品配送問題做了廣泛研究。TAGMOUTI等[1]考慮了服務成本、配送成本和逆向物流成本，構造了車輛路徑優(yōu)化模型，并重新設計了算法進行求解;TSANG等[2]提出了在生鮮品配送過程中采用多溫帶模型，并利用遺傳算法減小運輸過程中的食物腐敗率;OSVALD等[3]研究了帶配送時間窗和顧客時間窗的車輛路徑優(yōu)化問題，并設計了算法求解冷鏈配送問題;SONG等[4]研究了在冷藏車和普通車共同配送環(huán)境下，以消費者滿意度最大為目標的生鮮品配送路徑問題;WANG等[5]從低碳物流和環(huán)境保護的角度研究生鮮品配送問題，考慮碳排放成本，并利用改進遺傳算法對模型進行求解，并研究了碳稅政策對配送成本和碳排放的影響;TANG等[6]應用節(jié)約算法和蟻群算法對配送中心與超市之間的農產品冷鏈配送問題進行了研究;馬帥[7]研究了生鮮食品的配送中心選址和配送路徑優(yōu)化問題;李嘉棟等[8]通過邏輯斯蒂方程來表示保質期與變質成本的關系，并對生鮮品的生產與配送進行了研究。范厚明等[9]考慮到生鮮品對時效性敏感的特點，有針對性地設計了時間窗和懲罰成本，構建了以總成本（包括車輛運輸成本、時間窗懲罰成本和生鮮品變質成本）最小為目標的優(yōu)化模型，并利用蟻群算法對模型進行求解;翟恒星[10]對O2O模式下的生鮮冷鏈配送優(yōu)化和路徑規(guī)劃問題進行了研究，構建了一種新型的配送供應鏈模型，建立了實體店選址與配送為一體的數(shù)學模型，并利用基于字典順序的求解方法對模型進行了求解;楊曉華等[11]針對生鮮電商的需求不確定性以及退貨問題，提出了模糊環(huán)境下多周期生鮮閉環(huán)物流網(wǎng)絡系統(tǒng)，并利用遺傳算法和粒子群算法進行求解;陳久梅等[12]針對生鮮農產品多品種、小批量、易變質等特性，采用多隔室配送車輛對生鮮品進行冷鏈配送，并以配送成本最小為目標建立模型，采用粒子群算法對模型進行了求解。

近年來，少數(shù)學者開始將生鮮配送與多目標車輛路徑問題聯(lián)合起來進行研究。侯宇超等[13]對配送過程中的配送成本、客戶滿意度和污染物排放3個目標進行了研究;丁歡[14]對客戶滿意度和配送中心選址進行了研究。然而，少有文獻將生鮮品的新鮮度與多目標車輛路徑問題聯(lián)系到一起?；诖?，針對帶時間窗的多目標生鮮品配送路徑優(yōu)化問題（multi-objective vehicle routing problem with time window dealing with perishable products，MO-VRPTW-P），結合相關理論與方法，建立MO-VRPTW-P模型，并利用改進的（即帶精英策略的）非支配排序遺傳算法（non-dominated sorting genetic algorithmⅡ，NSGA II），求出滿足配送總成本最小和生鮮品新鮮度最大的相對較優(yōu)解，驗證MO-VRPTW-P模型的有效性。

1 問題描述與MO-VRPTW-P模型的建立 ?基本的帶時間窗的車輛路徑問題（vehicle routing problem with time window， VRPTW）如下：一組車輛從配送中心出發(fā)，將貨物運輸給各個客戶，并在運輸任務完成后返回配送中心;每個客戶的地理位置和需求量是已知的;配送車輛有最大載荷限制;要求在特定的時間段內交付貨物給客戶;要求合理的行車路線實現(xiàn)優(yōu)化目標。

結合生鮮品運輸?shù)奶攸c，本文將MO-VRPTW-P描述為：一個配送中心對多個隨機客戶點進行配送服務，在此服務過程中，從企業(yè)利益角度出發(fā)將配送總成本最小作為追求目標，從客戶角度出發(fā)將生鮮品新鮮度最大作為追求目標，以期企業(yè)和客戶的利益都得到滿足。企業(yè)的配送總成本包括固定成本、運輸成本、懲罰成本和產品變質成本。在配送過程中，每個客戶都有不同的時間窗：早于時間窗到達的車輛，必須等待;晚到的車輛，會受到一定的懲罰。為表示生鮮品在運輸過程中的新鮮狀態(tài)，參考文獻[15]，考慮生鮮品的質量隨著運輸時間ti加速遞減的特點，令φ（ti）=etiln 2/Ti-1，這里φ（ti）為生鮮品的損耗比例系數(shù)，Ti 為客戶i的生鮮品保質期。用β（ti）=1-φ（ti）=2-etiln 2/T 表示生鮮品的新鮮度。

由于MO-VRPTW-P較為復雜，為便于對現(xiàn)實問題進行研究，假設：（1）客戶的地理位置、需求量和時間窗以及產品的保質期等信息已知;（2）所有的距離采用歐幾里得距離表示;（3）客戶點之間的配送時間等于歐幾里得距離;（4）每個顧客只能接受一輛車的一次配送服務;（5）從配送中心出發(fā)的車輛必須返回原配送中心;（6）車輛的實際裝載量不能超過其核定載荷;（7）生鮮品離開配送中心時處于最大新鮮狀態(tài)。

模型參數(shù)：N={1，2，…，n}為全部客戶需求點集合，0為配送中心;M 為車輛集合，m∈M; C為車輛最大載荷;si為服務客戶i的時間;tij為從客戶i到客戶j的配送時間;dij為從客戶i到客戶j的距離;di為客戶i的需求量;cm為車輛m的單位距離運輸成本;ei為客戶i時間窗起始時刻;li為客戶i時間窗結束時刻;w（m）i為車輛m到達客戶i的時刻;fm為車輛m的固定成本;Ti為客戶i的生鮮品保質期;β為客戶可以接受的最低新鮮度;β（ti）為客戶i收貨時的生鮮品新鮮度;q1為等待成本懲罰系數(shù);q2為延誤成本懲罰系數(shù);q3為變質成本懲罰系數(shù)。

決策變量：x（m）ij=1， 車輛m從客戶i到達客戶j

0， 其他

y（m）i=1， 車輛m訪問客戶i

0， 其他 ?構建配送總成本最小和生鮮品新鮮度最大的雙目標數(shù)學模型如下，其中除有特殊說明外，i∈N，j∈N，m∈M。

min f （1）=i，j，m（x（m）ijtijcm）+j，m（x（m）0jfm）+

q1i，j，m（x（m）ijmax （ei-w（m）i，0））+

q2i，j，m（x（m）ijmax （w（m）i-li，0））+

q3i，j，m（φ（ti）dix（m）ij）

（1）

max f （2）=Ni=0（β（ti）di）Ni=0di

（2）

s.t.

i（y（m）idi）≤C

（3）

ix（m）ij=ix（m）ji

（4）

m ix（m）ij=m jx（m）ij=1

（5）

m ix（m）0i=m jx（m）j0=1

（6）

w（m）i=w（m）i-1+si-1+t（i-1）i

（7）

β（ti）≥β

（8）

x（m）ij∈{0，1}

（9）

y（m）i∈{0，1}

（10）

式（1）表示配送總成本最小，配送總成本包括固定成本、運輸成本、等待成本、延誤懲罰成本和變質成本;式（2）表示生鮮品運達時其平均新鮮度最大;式（3）為車輛載荷約束;式（4）表示到達客戶與離開客戶的車輛相同;式（5）表示所有客戶均得到服務且僅被一輛車服務;式（6）保證從配送中心出發(fā)的車輛必須返回該配送中心;式（7）表示車輛m到達客戶i的時間;式（8）保證生鮮品新鮮度滿足客戶的最低新鮮度要求;式（9）表示車輛m是否從客戶i到達客戶j，若是則x（m）ij=1，否則x（m）ij=0;式（10）表示車輛m是否訪問過客戶i，若是則y（m）i=1，否則等于y（m）i=0。

2 帕累托最優(yōu)和NSGA II

2.1 帕累托最優(yōu)

在求解單目標問題時，可以在所有的候選解中選出最好的解作為最優(yōu)解。然而，在多目標優(yōu)化問題中，因為各目標相互沖突，所以最優(yōu)解不一定只有一個。由于不能簡單地進行比較，通常能夠求得不比其他任何解差的解，這種解成為帕累托最優(yōu)解或者非支配解，同時帕累托解的目標變量集合稱為帕累托前沿。

2.2 NSGA II

本文主要采用NSGA II，其整體過程與普通遺傳算法大同小異，都要經歷編碼、種群初始化、選擇、交叉、變異、迭代等過程，與普通遺傳算法稍有不同的是：在初始化種群之后的步驟中，其在計算個體適應度環(huán)節(jié)進行了快速非支配排序和擁擠度比較，并且在算法選擇時引入保存精英策略，保證了個體的多樣性。首先闡述NSGA II的兩個核心步驟，即快速非支配排序和擁擠度比較。

2.2.1 快速非支配排序

首先定義2個變量wp和sp，wp表示解p被支配的數(shù)量，sp表示解p支配的解的集合，w=0表示該解為非支配解。如圖1所示：對于一個有多個目標函數(shù)且均為求解其最小值的問題（本文中的目標函數(shù)f （2） 為求其最大值，為便于計算，將其倒置，轉化為求其最小值問題），圖中每個點都表示一個解;對于c點而言，由于a、b兩點的目標函數(shù)f （1） 、f （2） 所對應的值都優(yōu)于c點，因此c點被a、b兩點支配，wc=2，同理sb={c，d，e}。尋遍解集中的所有點，計算出所有點所對應的w值和s值，將w=0的點劃入F1（帕累托第一前沿），然后刪去w=0的點;重新遍歷計算各點所對應的w值和s值，將新的w=0的點劃入F2（帕累托第二前沿）;以此類推，直到所有的點都被劃分到對應的前沿中，得到F1F2…（符號表示優(yōu)先）。

2.2.2 擁擠度比較

通過快速非支配排序方法可以對所有的解進行排序，將解歸屬到不同的帕累托前沿，帕累托前沿越小，解的優(yōu)先級越高。若兩個解都屬于同一個帕累托前沿，則需對解進行進一步處理，稱這個過程為擁擠度比較。以圖2中的a點為例（假設a、b、c均處于同一個帕累托前沿），以a點左右鄰近的兩個解為頂點構造矩形，矩形的平均邊長作為a的擁擠距離。當兩個解屬于同一個帕累托前沿時，優(yōu)先選擇擁擠距離大的解，這樣可以保證種群的多樣性。當兩個解屬于不同的帕累托前沿時，帕累托前沿越小，解的優(yōu)先級越高。

2.3 編碼

編碼是設計遺傳算法的第一步，也是遺傳算法在解決實際問題中極為關鍵的步驟。所謂編碼就是將求解問題的解空間映射到編碼空間（即搜索空間）的過程，它對搜索過程影響很大。本文染色體編碼采用自然數(shù)編碼，每個基因代表一個客戶，在客戶序列中插入“0”表示配送中心，并在首尾處插入“0”以表示車輛從配送中心出發(fā)最終又回到配送中心。這種編碼方式的優(yōu)點在于可以非常方便地將信息輸入染色體中，無須額外的解碼和計算。例如染色體{0，5，7，9，0，3，1，0，2，8，4，6，0}代表3條路徑：0-5-7-9-0、0-3-1-0和0-2-8-4-6-0。

2.4 種群初始化

種群初始化是遺傳算法的開端，一個好的起點對問題的求解至關重要。本文隨機生成n個客戶點，并在首尾處插入“0”，如（0，i1，1，…，i1，n，0），根據(jù)車輛最大載荷和時間窗要求初始化染色體。當考慮車輛載荷約束時，若rj=1di1-j≤C且r+1j=1di1-j>C，則在第i1，r個客戶與第i1，r+1個客戶之間插入0，或者將客戶向前或向后移動一個位置再插入0;同理，當考慮時間窗約束時在第i1，r個客戶與第i1，r+1個客戶之間插入0，或者將客戶向前或向后移動一個位置再插入0;重復以上步驟，直到產生足夠的種群數(shù)量。

2.5 選擇操作

本文中的選擇操作主要存在于兩個過程中。第一個選擇操作是算法剛開始，與普通遺傳算法一樣，在生成子代的過程中采用錦標賽選擇法，從父代中選擇個體進行交叉和變異，生成新的子代。第二個選擇操作就是NSGA-II的核心部分，在第2.2.1節(jié)和第2.2.2節(jié)中已詳細介紹。

2.6 交叉算子

為避免交叉過程中產生不可行解，提高算法的收斂效果，并且保留優(yōu)良基因，采用最大保留交叉方法。首先，從兩個父代染色體中分別選擇一段基因作為保留區(qū)域。此過程中，要確保兩個基因段長度相同并且有相同的起始序列，為防止交叉后生成的染色體出現(xiàn)基因段缺失，選擇的基因段包含的配送中心（即編碼基因為0）數(shù)也必須一致。兩個父代染色體P1、P2分別刪去對方染色體保留區(qū)域的客戶基因，最后按順序覆蓋對方非保留區(qū)域的基因，并生成兩個子染色體。如染色體P1=017506380240， P2=034207180650，若P1的保留區(qū)域為0638，P2的保留區(qū)域為0718，則p′ 1=056307180240，p′ 2=042706380150。顯然，從路徑中刪除部分客戶，不會違背車輛載荷約束和時間窗約束，因此生成的子染色體一定是可行的。

2.7 變異算子

在一條染色體上選擇兩個變異點，變異點之間的區(qū)域稱為變異段，將變異段進行逆轉變異，生產新的個體。如染色體p=0123‖456‖7890，變異后生成p′=0123‖654‖7890。

2.8 終止條件

當?shù)螖?shù)達到設定最大迭代次數(shù)1 000時終止。

3 實驗仿真與分析

案例數(shù)據(jù)主要來自國外著名學者Solomon對VRPTW的研究數(shù)據(jù)集。目前，國外關于VRPTW的研究，大多以Solomon的數(shù)據(jù)集為參照。在Solomon研究的VRPTW中，一共設計了6類問題，即R1、R2、C1、C2、RC1、RC2，其中R類（random）表示客戶的地理位置是隨機均勻分布的，C類（clustered）表示客戶的地理位置是聚集分布的，RC類表示客戶的地理位置是混合分布的。在此基礎上，又將R、C、RC類分為1類和2類：1類表示調度范圍較小，在配送路徑上有較少的客戶對象;2類表示調度范圍較大，即要服務的客戶數(shù)量比較多。本文所使用的數(shù)據(jù)來自Solomon的R103中的100組數(shù)據(jù)，由于Solomon公開的研究數(shù)據(jù)均無量綱，故下文所有數(shù)據(jù)均無量綱。由于Solomon的數(shù)據(jù)集中只包括客戶坐標、時間窗開始時刻和結束時刻、服務時間和客戶需求量，不包括本文中的另一個重要參數(shù)——生鮮品的保質期Ti ，因此為便于研究，特在選擇的客戶時間窗結束時刻li的數(shù)據(jù)的基礎上，隨機加減50生成保質期Ti。算法通過MATLAB 2016a在配置為Intel（R） Core（TM）i5-5200U CPU @2.20 GHz，運行內存為8 GB，操作系統(tǒng)為WIN8.1的計算機上運行。實驗設置種群規(guī)模為100，交叉概率為0.8，其他參數(shù)見表1。

圖3是在NSGA II下本文模型的初始迭代收斂結果，圖中實心圓表示帕累托前沿，空心圓代表新生成的個體適應度。圖4為經過迭代計算得到的最終的帕累托最優(yōu)解集。需要指出的是，由于多目標優(yōu)化目標大多相互沖突，因此最終的結果是一個無法進行簡單比較的帕累托最優(yōu)解集，在不對目標函數(shù)增加權重的情況下，可以認為帕累托最優(yōu)解集中的任何一個解都不比其他的解差。在此基礎上，從帕累托最優(yōu)解集中隨機選擇一個解進行車輛路徑分配，并繪制車輛路徑圖，見圖5。根據(jù)圖5 的結果，對得到的車輛路徑規(guī)劃進行甘特圖繪制，以方便生鮮品配送企業(yè)進行調度和作業(yè)，見圖6。

表2是基于測試實例R103的數(shù)據(jù)，分別采用NSGA和NSGA II計算的結果。從計算結果可知，雖然用NSGA得到的總成本4 198.67略優(yōu)于用NSGA II得到的總成本4 205.25，但用NSGA得到的新鮮度0.712 8明顯劣于用NSGA II得到的新鮮度0.918 1，證明了NSGA II算法和MO-VRPTW-P模型的有效性。

為探討模型的適用性，將本文中提出的考慮配送總成本最小和生鮮品新鮮度最大的MO-VRPTW-P模型與傳統(tǒng)的不考慮生鮮品新鮮度的VRPTW模型進行對比，分析兩種配送策略在客戶數(shù)量分別為25、50和100的情形下配送企業(yè)的總成本和生鮮品的新鮮度，并利用傳統(tǒng)遺傳算法對VRPTW模型進行求解，結果見表3。

分析表3可得出結論：

（1）VRPTW策略下的配送總成本略低于考慮生鮮品新鮮度的MO-VRPTW-P策略下的配送總成本，但MO-VRPTW-P配送策略對生鮮品新鮮度的優(yōu)化較為明顯。在9組對比數(shù)據(jù)中，VRPTW策略下的配送總成本比MO-VRPTW-P策略下的低1.27%～5.02%，但可以發(fā)現(xiàn)，MO-VRPTW-P策略對生鮮品的新鮮度最低優(yōu)化3.30%，最高優(yōu)化14.43%，這說明對于注重服務水平的生鮮電商配送企業(yè)來說，使用MO-VRPTW-P策略只需略微提高配送成本就能夠達到很好的配送效果，提高服務質量。

（2）客戶訂單數(shù)量越多，生鮮品新鮮度的提升效果越明顯，即MO-VRPTW-P模型優(yōu)化效果越好。如算例中，大規(guī)?？蛻舡h(huán)境R1_100相比于小規(guī)?？蛻舡h(huán)境R1_25， R1_100的新鮮度優(yōu)化率為14.43%，R1_25的新鮮度優(yōu)化率為5.48%，因此本文提出的MO-VRPTW-P模型更加適合大規(guī)?？蛻粲唵苇h(huán)境。

（3）對比分析客戶地理位置隨機分布的R類算例和客戶地理位置聚集分布的C類算例，客戶地理位置較分散，其優(yōu)化效果越明顯。在同樣的訂單量環(huán)境下，R類的優(yōu)化效果比C類的明顯，如同樣是50個客戶，R1_50的新鮮度優(yōu)化率為8.58%，C1_50的為4.51%，可能是因為客戶地理位置越分散，配送時間就越長，對生鮮品新鮮度的影響就較大，因此本文提出的MO-VRPTW-P策略更適合客戶地理位置較為分散的配送場景。

4 結束語

本文利用改進的非支配排序遺傳算法（NSGA II），考慮了企業(yè)實際配送過程中可能會出現(xiàn)的延時配送、貨物變質等實際情況，考慮了固定成本、運輸成本、等待成本、延誤懲罰成本和變質成本，更加符合實際情況。通過測試實例，證明了帶時間窗的多目標生鮮品配送路徑優(yōu)化（MO-VRPTW-P）模型的有效性，求出了滿足配送總成本最小和生鮮品新鮮度最大的相對較優(yōu)解。同時通過對MO-VRPTW-P模型的適用性討論，提出本文模型較為適合的配送場景，即適合大規(guī)?？蛻粲唵魏涂蛻舻乩砦恢梅植驾^為分散的配送場景。該研究可為生鮮電商配送企業(yè)決策提供參考。由于該模型只考慮了一個配送中心和單品種運輸，所以還有進一步的提升空間。

參考文獻：

[1] TAGMOUTI M， GENDREAU M， POTVIN J-Y. Arc routing problems with time-dependent service costs[J]. European Journal of Operational Research， 2007， 181： 30-39. DOI： 10.1016/j.ejor.2006.06.028.

[2] TSANG Y P， CHOY K L， WU C H， et al. An intelligent model for assuring food quality in managing a multi-temperature food distribution centre[J]. Food Control， 2018， 90： 81-97. DOI： 10.1016/j.foodcont. 2018.02.030.

[3] OSVALD A， STIRN L Z. Vehicle routing algorithm for the distribution of fresh vegetables and similar perishable food[J]. Journal of Food Engineering， 2008， 85（2）： 285-295. DOI： 10.1016/j.jfoodeng.2007.07.008.

[4] SONG B D， KO Y D. A vehicle routing problem of both refrigerated- and general-type vehicles for perishable food products delivery[J]. Journal of Food Engineering， 2016， 169： 61-71. DOI： 10.1016/j.jfoodeng. 2015.08.027.

[5] WANG Songyi， TAO Fengming， SHI Yuhe. Optimization of location-routing problem for cold chain logistics considering carbon footprint[J]. International Journal of Environmental Research and Public Health， 2018， 15（1）： 86-102. DOI： 10.3390/ijerph15010086.