梁力軍，袁苗苗，孫玉璇 LIANG Lijun, YUAN Miaomiao, SUN Yuxuan

（北京信息科技大學(xué) 信息管理學(xué)院，北京 100192）

0 引 言

物流車輛路徑研究中，帶時(shí)間窗的車輛路徑問(wèn)題是當(dāng)前學(xué)界的關(guān)注重心；同時(shí)，關(guān)于車輛路徑優(yōu)化的算法方面也受到學(xué)界的重點(diǎn)關(guān)注。首先，帶時(shí)間窗的車輛路徑問(wèn)題基于單純的車輛路徑問(wèn)題（VRP） 外，補(bǔ)充顧客滿意的服務(wù)訪問(wèn)時(shí)間窗口，拓展了VRP 的研究。另外，據(jù)此合理規(guī)劃路線是提高物流服務(wù)質(zhì)量和提升經(jīng)濟(jì)效益的重要手段。具有顧客限定的服務(wù)時(shí)間窗口早在20 世紀(jì)80 年代末就已經(jīng)被引入到車輛路徑問(wèn)題研究中，如Solomon 在研究中考慮了顧客要求的時(shí)間窗口，以解決車輛的配送問(wèn)題，同時(shí)為路徑分析拓展了新的研究思路[1]?，F(xiàn)實(shí)生活中，由于部分商品自身具有強(qiáng)時(shí)效性，如生鮮農(nóng)產(chǎn)品等，因此，考慮到帶時(shí)間窗口因素約束的研究也逐漸增多，如劉炎寶等[2]、范厚明等[3]、葛顯龍等[4]、酒艷妮等[5]均圍繞具有時(shí)效性要求的生鮮產(chǎn)品及外賣配送路徑最優(yōu)化展開(kāi)了相關(guān)探究。

遺傳算法和變鄰域搜索算法在解決路徑優(yōu)化問(wèn)題上的應(yīng)用較為成熟。Holland 最早提出遺傳算法，該算法以達(dá)爾文的物種演化原理為基礎(chǔ)，利用選擇、交叉、變異等方法，模擬自然界中的遺傳機(jī)理，尋求最優(yōu)，是一種具有全局隨機(jī)尋優(yōu)能力的仿生生物的自然演化模型[6]；然而，經(jīng)過(guò)王芳等[7]、成沖等人[8]在配送路徑相關(guān)研究中證實(shí)，遺傳算法得出的結(jié)果時(shí)常陷入局部最優(yōu)，未能尋到最優(yōu)的結(jié)果。由Ghosh 和Shan[9]提出的變鄰域搜索算法是一種局部搜索方法，具有通過(guò)變換鄰域位置不斷提高局部搜索能力，從而不會(huì)過(guò)早陷入局部?jī)?yōu)化。學(xué)術(shù)界內(nèi)諸多學(xué)者都在不斷嘗試探索尋找最優(yōu)的算法求解車輛路徑問(wèn)題，從相關(guān)研究來(lái)看，改進(jìn)后的變鄰域搜索算法與遺傳算法要比傳統(tǒng)算法呈現(xiàn)出的結(jié)果更優(yōu)。如李丹蓮等[10]、張鐸等人[11]提出多色體遺傳算法、多準(zhǔn)則決策遺傳算法等解決路徑優(yōu)化問(wèn)題，最終結(jié)果驗(yàn)證了優(yōu)化后算法的。Renata[12]提出了一種基于NSGAt 的變鄰域多目標(biāo)遺傳算法，結(jié)果表明，所提出的VN-MGA 算法優(yōu)于純VNS 算法；宋強(qiáng)等[13]在解決多行程車輛路徑問(wèn)題上采用了多種算法，其中改進(jìn)的變鄰域搜索算法與包括傳統(tǒng)變鄰域搜索等其他算法相比，其結(jié)果更優(yōu)；王偉權(quán)等[14]基于改進(jìn)變鄰域搜索算法中由啟發(fā)式算法構(gòu)造出初始解，進(jìn)而進(jìn)行變鄰域搜索的算法求解，驗(yàn)證出用該算法解決車輛配送路徑問(wèn)題比其他算法能大幅降低物流成本。

綜上所述，學(xué)者用不同的算法圍繞服務(wù)時(shí)間窗口和商品的配送進(jìn)行了相關(guān)研究，但存在一定的局限性。一是，相關(guān)研究對(duì)象主要集中于具有時(shí)效性要求的冷鏈生鮮產(chǎn)品、醫(yī)藥產(chǎn)品、外賣配送等展開(kāi)，而面向非時(shí)效性的研究較為匱乏。二是，在車輛路徑問(wèn)題中，改進(jìn)后的算法與傳統(tǒng)遺傳算法和變鄰域搜索算法相比，呈現(xiàn)出的結(jié)果更優(yōu)。

1 本文物流配送路徑問(wèn)題描述及建模

本文將研究對(duì)象轉(zhuǎn)向非冷鏈生鮮產(chǎn)品，即將變鄰域搜索算法與遺傳算法進(jìn)行融合，構(gòu)建起一種新型變鄰域遺傳搜索算法，將配送總成本、顧客缺貨懲罰成本等納入目標(biāo)函數(shù)模型，探究新模型能否有效解決遺傳算法結(jié)果陷入局部最優(yōu)的問(wèn)題，以試圖解決車輛路徑的最優(yōu)選擇問(wèn)題。具體步驟如下：

1.1 問(wèn)題描述與假設(shè)

研究以單點(diǎn)配送中心向周邊多個(gè)客戶需求點(diǎn)配送商品為例，來(lái)研究配送服務(wù)車輛路徑選擇問(wèn)題。當(dāng)配送中心收到客戶需求點(diǎn)的線上需求訂單后，對(duì)訂單進(jìn)行快速響應(yīng)，并根據(jù)需求點(diǎn)的時(shí)限要求和配送車輛、配送路徑等因素，部署相關(guān)配送服務(wù)行為。本文相關(guān)假設(shè)如下：

假設(shè)1：?jiǎn)吸c(diǎn)物流配送中心和各客戶需求點(diǎn)地理位置已知。

假設(shè)2：客戶的需求量、期望的配送服務(wù)時(shí)間以及遲到懲罰成本已知。

假設(shè)3：實(shí)施配送任務(wù)的車輛車型相同，每輛配送車的最大承載能力已知，每輛配送車所服務(wù)的客戶需求總量之和不超過(guò)車輛的最大承載能力。

假設(shè)4：配送車輛的行程速度均衡且為定值，暫不考慮配送道路中車流量及路況的限制。

假設(shè)5：每個(gè)客戶需求點(diǎn)由一輛配送車實(shí)施配送，而每輛車可向多個(gè)客戶需求點(diǎn)實(shí)施配送。

假設(shè)6：每輛配送車輛配備一名配送人員，人員成本為定值。

1.2 模型相關(guān)參數(shù)設(shè)定

本文所構(gòu)建的配送路徑優(yōu)化模型的參數(shù)變量如表1 所示，并以成本作為評(píng)估配送路徑優(yōu)化模型效果的指標(biāo)。

表1 模型參數(shù)設(shè)定與釋義

由表1 可知，物流配送模型的變量主要包括運(yùn)輸總成本C總、配送運(yùn)輸成本C運(yùn)輸、配送人員變動(dòng)成本C變動(dòng)等。其中運(yùn)輸總成本由固定成本C固定、配送運(yùn)輸成本C運(yùn)輸和缺貨懲罰成本W(wǎng) 三大部分構(gòu)成。配送運(yùn)輸成本C運(yùn)輸與運(yùn)輸路程緊密關(guān)聯(lián)，不同的運(yùn)輸路徑造成配送運(yùn)輸成本C運(yùn)輸?shù)淖儎?dòng)；配送人員變動(dòng)成本C變動(dòng)和車輛行駛路程有關(guān)，單位距離變動(dòng)成本固定，行駛里程根據(jù)不同的行駛路線來(lái)決定。

1.3 相關(guān)成本分析

本文將配送路徑優(yōu)化模型的成本分為三個(gè)部分：一是配送車輛的出車固定成本；二是配送車輛的配送運(yùn)輸成本；三是缺貨懲罰成本，即因配送未滿足時(shí)限要求而導(dǎo)致客戶需求點(diǎn)發(fā)生缺貨所產(chǎn)生的損失。

（1） 車輛出車固定成本。單車固定成本主要包括車輛通訊費(fèi)、月檢費(fèi)、駕駛員基本工資和保險(xiǎn)費(fèi)等。固定成本總費(fèi)用與駕駛?cè)藛T及配送車輛的數(shù)量相關(guān)，計(jì)算公式如式（1） 所示。

（2） 配送運(yùn)輸成本。為便于研究，假設(shè)配送網(wǎng)絡(luò)中兩個(gè)位置之間的距離是根據(jù)歐幾里德線性距離計(jì)算所得，Dij定義為從位置i 到位置j 的線性距離，如式（2） 所示，車輛配送運(yùn)輸總成本計(jì)算公式如式（3） 所示。

（3） 缺貨懲罰成本。假設(shè)客戶需求點(diǎn)的配送限定時(shí)間為[Ta,Sb]，Ta代表需求點(diǎn)能接受的最早配送時(shí)間，Sb代表需求點(diǎn)能接受的最晚服務(wù)時(shí)間。如在限定時(shí)間內(nèi)完成配送，則不發(fā)生懲罰成本；反之則產(chǎn)生懲罰成本，且懲罰成本由配送不及時(shí)給需求點(diǎn)實(shí)際造成的缺貨損失決定。

客觀而言，配送時(shí)間的提前或延遲均會(huì)對(duì)客戶需求點(diǎn)產(chǎn)生負(fù)向影響，但研究對(duì)象主要針對(duì)非生鮮產(chǎn)品，故忽略配送時(shí)間提前而產(chǎn)生的懲罰成本。懲罰成本計(jì)算公式如式（4） 所示。

1.4 物流配送路徑模型構(gòu)建

在分析相關(guān)成本后，總配送成本的計(jì)算公式如式（5） 所示。

式（5） 表示的配送總成本，包括配送車輛的使用成本、運(yùn)輸成本、超出規(guī)定服務(wù)時(shí)間窗的懲罰成本。

相關(guān)約束條件如下：

式（6） 表示車輛k 的最大限制容量能滿足服務(wù)對(duì)象需求點(diǎn)的需求量；式（7） 表示對(duì)服務(wù)每個(gè)需求點(diǎn)的車輛進(jìn)行了限制，一個(gè)服務(wù)需求點(diǎn)只能安排一輛車進(jìn)行服務(wù)操作；式（8） 表示車輛從配送中心啟動(dòng)并最終返回配送中心。

Ti>Sb時(shí)：

式（9） 表示超出顧客規(guī)定服務(wù)時(shí)間窗口的懲罰成本。

否則：

式（10） 表示送貨到達(dá)時(shí)間若早于規(guī)定的服務(wù)時(shí)間窗口，則懲罰成本為0，即不會(huì)產(chǎn)生懲罰成本；式（11） 表示車輛k 在行駛過(guò)程中到達(dá)服務(wù)需求點(diǎn)j 的時(shí)間等于車輛到達(dá)服務(wù)需求點(diǎn)i 的時(shí)間加上在i 點(diǎn)服務(wù)的時(shí)間g 再加上從i 點(diǎn)行駛到j(luò) 點(diǎn)消耗的時(shí)間；式（12） 表示到達(dá)各個(gè)服務(wù)需求點(diǎn)的車有且僅有一輛。

2 變鄰域遺傳搜索算法求解

本文所運(yùn)用的變鄰域遺傳搜索算法在車輛調(diào)度應(yīng)用[15]、車輛路徑分析[16]、貨架分配方法[17]、車間物流調(diào)度[18-19]等方面的研究中已較為成熟，能夠解決區(qū)域配送路徑的相關(guān)問(wèn)題，且在算法上效率更高，求解的質(zhì)量更優(yōu)。另外，相關(guān)學(xué)者已將該算法用于生鮮冷鏈配送路徑的研究[20]。

因此，本文將其應(yīng)用于物流車輛的配送領(lǐng)域，針對(duì)附帶時(shí)間窗的配送路徑優(yōu)化問(wèn)題，運(yùn)用MATLAB 軟件和優(yōu)化后的變鄰域遺傳搜索算法來(lái)實(shí)現(xiàn)求解，從而實(shí)現(xiàn)車輛配送路徑的優(yōu)化。變鄰域遺傳搜索算法的實(shí)現(xiàn)流程如圖1 所示。

圖1 變鄰域遺傳搜索實(shí)現(xiàn)流程

2.1 編碼與解碼

（1） 編碼與解碼。路徑優(yōu)化問(wèn)題有兩種主編碼方法：路徑表示法和鄰接表示法。為直觀表達(dá)，研究采用路徑表示法。假設(shè)共有7 個(gè)便利店需求點(diǎn)（用數(shù)值1~7 表示），1 個(gè)配送中心（用0 數(shù)值表示），外加3 輛配送車輛，整個(gè)配送過(guò)程中的配送路徑從配送中心0 開(kāi)始出發(fā)，最終再返回到配送中心0 結(jié)束。例如：若最終生成的編碼為：0,1,3,0,5,7,2,0,4,6,0。則該編碼主要構(gòu)成三條不同的配送路徑，分別為：0→1→3→0；0→5→7→2→0；0→4→6→0。

（2） 種群初始化及適應(yīng)度函數(shù)。為了確保個(gè)體的多樣性，通過(guò)隨機(jī)生成的方式生成原始種群。若將原始種群的規(guī)模大小設(shè)定為N，則原始種群的第一代種群由N 個(gè)個(gè)體構(gòu)成，N 個(gè)個(gè)體分別對(duì)應(yīng)表示有N 個(gè)初始解，且在未進(jìn)行遺傳演化之前，原始種群內(nèi)的個(gè)體適應(yīng)性是比較低的。群體的個(gè)體品質(zhì)通常是以適應(yīng)度值來(lái)衡量，如果一個(gè)染色體對(duì)應(yīng)的路徑選擇成本較低，那么相應(yīng)的解決方案就會(huì)有更高的適應(yīng)度，并且隨著相應(yīng)方案成本的減少，其適應(yīng)度也會(huì)隨之增加。該方法以物流總成本和便利店缺貨損失成本為目標(biāo)函數(shù)，并以此進(jìn)行優(yōu)化。

2.2 遺傳算子

遺傳算子主要包括選擇、交叉、變異三個(gè)部分。

（1） 選擇算子。通過(guò)選擇輪盤(pán)賭的形式選擇出算子，通過(guò)這種形式可以更大的概率選擇質(zhì)量較高的個(gè)體。思路如下：

首先，將種群中的個(gè)體納入適應(yīng)度函數(shù)，分別計(jì)算適應(yīng)值fi和整體適應(yīng)值F 值。

其次，計(jì)算出從種群整體中選擇出個(gè)體i 的概率pi，計(jì)算公式為：

再次，計(jì)算選擇累計(jì)的概率Pi, 計(jì)算公式為：

下一步，生成隨機(jī)數(shù)n，n 存在于0~1 之間，當(dāng)隨機(jī)數(shù)n

最后，不斷進(jìn)行群體大小的次輪盤(pán)賭，以產(chǎn)生下一代群體。

（2） 交叉算子。交叉操作能夠保持父代個(gè)體的中優(yōu)良特性的同時(shí)提高全局搜索的能力，為了防止交叉過(guò)程中出現(xiàn)重復(fù)的個(gè)體，提出了交叉算子，即先生成兩段交叉區(qū)間的端點(diǎn)，然后把交換后的基因序列交叉到另一條染色體的前端，把原來(lái)的基因序列中的重復(fù)的基因剔除掉，從而形成新的后代。其過(guò)程示例如圖2 所示。

圖2 交叉算子過(guò)程示意圖

（3） 變異算子。變異操作可以彌補(bǔ)交叉操作過(guò)早收斂，陷入局部?jī)?yōu)化的缺陷。本文選擇Swap 算子作為變異算子，在群體中隨機(jī)選擇個(gè)體，并隨機(jī)選擇兩個(gè)突變的基因進(jìn)行交換操作以形成新的個(gè)體。例如：變異前：2 6 4 1 3 5 8 7 1 5，變異后：2 6 4 8 3 5 1 7 1 5，可發(fā)現(xiàn)基因1 與基因8 進(jìn)行了位置互換。

2.3 鄰域結(jié)構(gòu)

本文主要采用逆序變化和互換變化兩種鄰域結(jié)構(gòu)進(jìn)行搜索，兩種鄰域結(jié)構(gòu)的變化如圖3 所示。

圖3 鄰域結(jié)構(gòu)變化示意圖

2.4 終止條件設(shè)定

當(dāng)?shù)M(jìn)化數(shù)達(dá)到預(yù)先設(shè)定的最大進(jìn)化代數(shù)時(shí)，算法停止循環(huán)運(yùn)行，最終擁有最大適應(yīng)度值的個(gè)體作為最優(yōu)解輸出。

3 算例分析

本文參考京東北京K 配送中心為周邊便利店配送便利商品需求的歷史數(shù)據(jù)[21]，設(shè)產(chǎn)生合理的便利店配送需求為Qi，且單個(gè)便利店的需求量不超過(guò)京東配送中心車輛的最大載重量；該配送中心使用車型為江淮帥鈴H 載貨車來(lái)向周邊便利店需求點(diǎn)進(jìn)行配送服務(wù)，且其自有6 輛配送車輛，車速Vk一般為40~80km/h，最大運(yùn)載量Qk為1 噸，單位燃油油耗費(fèi)用C油耗為1.5 元/公里，單位維修與輪胎費(fèi)用Ca為0.8 元/公里，配送人員基礎(chǔ)工資為100 元/每輛/每天，車輛的通信及月檢費(fèi)為20 元/每輛/每天，車輛配送人員的可變工資為C變動(dòng)為0.6 元/公里。

假設(shè)單位缺貨懲罰成本為2 元/min，配送車輛每天早上7 時(shí)出發(fā)，每個(gè)便利店服務(wù)停留時(shí)間不超過(guò)半小時(shí)。K 京東配送中心由于向周邊服務(wù)的門(mén)店較多，數(shù)據(jù)分析比較困難，因此本文選定了周邊固定區(qū)域的15 家便利店作為研究樣本，算法中相關(guān)參數(shù)經(jīng)過(guò)不斷調(diào)試最終設(shè)置如表2 所示。

表2 算法相關(guān)參數(shù)設(shè)置

通過(guò)整理坐標(biāo)、各個(gè)便利店需求點(diǎn)的需求量及所要求的配送服務(wù)時(shí)間窗，得到所有需求節(jié)點(diǎn)的相關(guān)信息如表3 所示，為了獲得更清晰直觀的路線圖，給定便利店需求點(diǎn)的序號(hào)為1~15，京東配送中心點(diǎn)的序號(hào)用0 表示。

表3 配送中心、便利店需求點(diǎn)相關(guān)數(shù)據(jù)

為了便于計(jì)算眾多需求點(diǎn)及配送中心點(diǎn)之間的空間距離，將配送中心與便利店需求點(diǎn)的實(shí)際具體位置映射到平面上，形成橫縱（X, Y ）坐標(biāo)點(diǎn)分布如圖4 所示，其中紅色實(shí)心點(diǎn)為配送中心。

圖4 配送中心和需求點(diǎn)坐標(biāo)的位置

本文利用MATLAB R2018a 軟件，結(jié)合上述實(shí)例數(shù)據(jù)，分別用傳統(tǒng)的遺傳算法和變鄰域遺傳搜索算法進(jìn)行了求解，并給出兩種算法的最優(yōu)路線圖分別如圖5 所示，最優(yōu)車輛配送路線、綜合總成本如表4 所示。

圖5 傳統(tǒng)遺傳算法（左） 和變鄰域遺傳算法（右） 最優(yōu)路徑圖

表4 車輛配送最優(yōu)路徑圖

由結(jié)果可以看出，變鄰域遺傳搜索算法要優(yōu)于傳統(tǒng)遺傳算法，行駛里程、缺貨損失成本以及變動(dòng)成本都呈現(xiàn)不同程度的下降，表明變鄰域遺傳搜索算法可以更好地服務(wù)于客戶，同時(shí)有利于配送中心的長(zhǎng)期發(fā)展，也驗(yàn)證了該算法在解決車輛配送路徑中的可行性和有效性。通過(guò)該算法的驗(yàn)證，非冷鏈商品的配送路徑選擇時(shí)應(yīng)關(guān)注以下要點(diǎn)：一是，面向不同服務(wù)對(duì)象的地理位置信息及各項(xiàng)服務(wù)需求信息時(shí)，物流企業(yè)若追求利益的最大化，應(yīng)對(duì)模型中的參數(shù)不斷進(jìn)行調(diào)試，尋找出最優(yōu)的配送路線；二是，將變鄰域遺傳算法應(yīng)用于非冷鏈運(yùn)輸時(shí)要保證一定數(shù)量的服務(wù)對(duì)象，服務(wù)對(duì)象數(shù)量較少時(shí)呈現(xiàn)的結(jié)果與傳統(tǒng)算法相比效果不明顯，只有選定較多的服務(wù)對(duì)象時(shí)，效果才能愈加顯著。因此，當(dāng)需求點(diǎn)數(shù)量較多時(shí)可選擇該算法進(jìn)行研究，既能降低成本也能提高求解速度。

4 結(jié)論與展望

本文基于相關(guān)文獻(xiàn)研究，面向非冷鏈商品，考慮顧客缺貨損失成本，構(gòu)建了帶有顧客服務(wù)時(shí)間窗口，并以總成本最低為目標(biāo)的車輛配送路徑模型。研究中，將傳統(tǒng)遺傳算法和變鄰域搜索算法相結(jié)合形成變鄰域遺傳搜索算法，能實(shí)現(xiàn)利用不同動(dòng)作構(gòu)成的鄰域結(jié)構(gòu)進(jìn)行交替搜索操作，在平衡了疏散性與集中性的基礎(chǔ)上，形成局部最優(yōu)解，并將局部最優(yōu)解進(jìn)一步作為遺傳算子進(jìn)行交叉變異搜索操作來(lái)求取全局最優(yōu)解。經(jīng)研究得出如下結(jié)論：一是，在面向非冷鏈商品車輛配送路徑的研究中，充分考慮需求點(diǎn)的服務(wù)需求與商品的特性，建立起合理有效的優(yōu)化模型并運(yùn)行后，結(jié)果表明將研究提出的變鄰域遺傳搜索算法用于非冷鏈商品配送路徑優(yōu)化，能夠有效實(shí)現(xiàn)各項(xiàng)成本的最低化；二是，從模型應(yīng)用視角，本文應(yīng)用的變鄰域遺傳搜索算法充分結(jié)合了變鄰域算法的全局搜索特點(diǎn)及變鄰域搜索算法高效的局部搜索能力，該算法較傳統(tǒng)遺傳算法和變鄰域算法而言，既提高了求解精度又提升了求解速度，同時(shí)驗(yàn)證了該算法的可行性。

本文探究了面向非冷鏈商品，以綜合成本最小為目標(biāo)的車輛配送新方法后，考慮到研究對(duì)象與研究目標(biāo)的局限性，認(rèn)為可繼續(xù)向具有一定時(shí)效性的冷鏈商品進(jìn)一步探索，驗(yàn)證變鄰域遺傳搜索算法的適用性。除此之外，后續(xù)還可開(kāi)展以最短配送時(shí)間、最短配送路徑等為目標(biāo)的研究，進(jìn)一步驗(yàn)證其可行性，為物流行業(yè)的發(fā)展添磚加瓦。