基于NSGAII的帶時(shí)間窗生鮮品配送路徑優(yōu)化

李善俊 陳淮莉

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

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

中圖分類號(hào)： F252 ? ?文獻(xiàn)標(biāo)志碼： 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è)務(wù)范圍從線下延伸到了線上，生鮮電商企業(yè)迎來了飛速發(fā)展的黃金時(shí)期。鑒于生鮮品易腐爛、高時(shí)效性的特點(diǎn)，對(duì)生鮮品配送企業(yè)提出了比傳統(tǒng)的物流配送更高的要求。生鮮品的配送是生鮮電商的重要組成部分，也是影響生鮮電商企業(yè)發(fā)展的最大的一塊絆腳石。

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

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

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

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

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

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

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

0， 其他

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

0， 其他 ?構(gòu)建配送總成本最小和生鮮品新鮮度最大的雙目標(biāo)數(shù)學(xué)模型如下，其中除有特殊說明外，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）表示配送總成本最小，配送總成本包括固定成本、運(yùn)輸成本、等待成本、延誤懲罰成本和變質(zhì)成本;式（2）表示生鮮品運(yùn)達(dá)時(shí)其平均新鮮度最大;式（3）為車輛載荷約束;式（4）表示到達(dá)客戶與離開客戶的車輛相同;式（5）表示所有客戶均得到服務(wù)且僅被一輛車服務(wù);式（6）保證從配送中心出發(fā)的車輛必須返回該配送中心;式（7）表示車輛m到達(dá)客戶i的時(shí)間;式（8）保證生鮮品新鮮度滿足客戶的最低新鮮度要求;式（9）表示車輛m是否從客戶i到達(dá)客戶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)

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

2.2 NSGA II

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

2.2.1 快速非支配排序

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

2.2.2 擁擠度比較

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

2.3 編碼

編碼是設(shè)計(jì)遺傳算法的第一步，也是遺傳算法在解決實(shí)際問題中極為關(guān)鍵的步驟。所謂編碼就是將求解問題的解空間映射到編碼空間（即搜索空間）的過程，它對(duì)搜索過程影響很大。本文染色體編碼采用自然數(shù)編碼，每個(gè)基因代表一個(gè)客戶，在客戶序列中插入“0”表示配送中心，并在首尾處插入“0”以表示車輛從配送中心出發(fā)最終又回到配送中心。這種編碼方式的優(yōu)點(diǎn)在于可以非常方便地將信息輸入染色體中，無須額外的解碼和計(jì)算。例如染色體{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 種群初始化

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

2.5 選擇操作

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

2.6 交叉算子

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

2.7 變異算子

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

2.8 終止條件

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

3 實(shí)驗(yàn)仿真與分析

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

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

表2是基于測(cè)試實(shí)例R103的數(shù)據(jù)，分別采用NSGA和NSGA II計(jì)算的結(jié)果。從計(jì)算結(jié)果可知，雖然用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模型進(jìn)行對(duì)比，分析兩種配送策略在客戶數(shù)量分別為25、50和100的情形下配送企業(yè)的總成本和生鮮品的新鮮度，并利用傳統(tǒng)遺傳算法對(duì)VRPTW模型進(jìn)行求解，結(jié)果見表3。

分析表3可得出結(jié)論：

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

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

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

4 結(jié)束語

本文利用改進(jìn)的非支配排序遺傳算法（NSGA II），考慮了企業(yè)實(shí)際配送過程中可能會(huì)出現(xiàn)的延時(shí)配送、貨物變質(zhì)等實(shí)際情況，考慮了固定成本、運(yùn)輸成本、等待成本、延誤懲罰成本和變質(zhì)成本，更加符合實(shí)際情況。通過測(cè)試實(shí)例，證明了帶時(shí)間窗的多目標(biāo)生鮮品配送路徑優(yōu)化（MO-VRPTW-P）模型的有效性，求出了滿足配送總成本最小和生鮮品新鮮度最大的相對(duì)較優(yōu)解。同時(shí)通過對(duì)MO-VRPTW-P模型的適用性討論，提出本文模型較為適合的配送場(chǎng)景，即適合大規(guī)模客戶訂單和客戶地理位置分布較為分散的配送場(chǎng)景。該研究可為生鮮電商配送企業(yè)決策提供參考。由于該模型只考慮了一個(gè)配送中心和單品種運(yùn)輸，所以還有進(jìn)一步的提升空間。

參考文獻(xiàn)：

[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.