陳雄寅,韋妙花

(1.黎明職業(yè)大學(xué) 商學(xué)院,福建 泉州 362000;2.浙江師范大學(xué) 教師教育學(xué)院,浙江 金華 321004;3.泉州職業(yè)技術(shù)大學(xué)商學(xué)院,福建 泉州 362000)

0 引言

隨著我國生鮮農(nóng)產(chǎn)品的市場需求量的日益增長和對其品質(zhì)需求的不斷提升,生鮮農(nóng)副產(chǎn)品流通過程中存在的不足逐漸顯現(xiàn),特別是我國當(dāng)前農(nóng)副產(chǎn)品物流基礎(chǔ)設(shè)施和信息化程度仍存在很多欠缺。生鮮農(nóng)副產(chǎn)品品類眾多、保鮮方式差異大、儲存周期短、消費者需求點分散、路徑網(wǎng)絡(luò)繁雜,生鮮農(nóng)副產(chǎn)品物流配送路徑的優(yōu)化設(shè)計是相關(guān)企業(yè)亟待解決的難題。而且,市場對生鮮農(nóng)副產(chǎn)品的選擇性、多元性、新鮮度等品質(zhì)要求的提升,生鮮農(nóng)副產(chǎn)品的配送的時間方面的要求也為路徑優(yōu)化提出了新的要求。配送是生鮮農(nóng)產(chǎn)品流通過程中一個非常關(guān)鍵的環(huán)節(jié),科學(xué)、合理的設(shè)計配送車輛路徑對消費者、企業(yè)和社會都有著舉足輕重的影響。通過配送車輛路徑優(yōu)化設(shè)計,可以提高配送效率,降低配送成本,準(zhǔn)時快速地完成配送任務(wù),從而提高消費者的滿意度和企業(yè)經(jīng)濟效益,還可以節(jié)約車輛使用數(shù)量,減輕城市擁堵,減少汽車噪聲和尾氣排放量,保護了生態(tài)環(huán)境。

生鮮農(nóng)產(chǎn)品配送車輛路徑優(yōu)化(Vehicle Routing Optimization,VRP)問題屬于帶時間窗的車輛路徑(Vehicle Routing Optimization with Time Windows,VRPTW)問題,該問題是由Pullen等[1](1967),Knight等[2](1968)考慮提供服務(wù)間隔時間約束時提出的。我國對該類問題的研究主要集中在模型構(gòu)建和求解方法兩個方向。2014年,楊磊等以顧客滿意度為目標(biāo)函數(shù),以客戶的時間要求為約束條件,建立帶時間窗口的鮮活農(nóng)產(chǎn)品配送模型進行配送車輛路徑優(yōu)化研究[3]。2016年,葛顯龍等考慮路程等因素,以物流企業(yè)的最小成本(車輛成本和貨損成本)為目標(biāo)函數(shù),建立了帶時間窗口約束的優(yōu)化模型,并給出最優(yōu)車輛路徑[4]。2017年,朱莉等以最短車輛運行時間為最優(yōu)目標(biāo)提出了一種帶時間窗口的緊急救援路線優(yōu)化模型,解決了帶時間窗的跨區(qū)救援線路優(yōu)化問題[5]。2019年,冀巨海等以配送成本最小為目標(biāo)函數(shù),建立了基于軟硬時間窗口限制和取送兩種方式相結(jié)合的配送車輛路徑優(yōu)化模型[6]。2017年,郭詠梅等針對突發(fā)事件中的應(yīng)急物流VRPTW問題,提出一種螞蟻算法和人工魚群算法相結(jié)合的混合算法[7]。2018年,鄧紅星等構(gòu)建了公路零擔(dān)物流配送路徑優(yōu)化模型,并提出置換算法求解得出最優(yōu)方案[8]。2010年,汪勇等將協(xié)同進化思想引入遺傳算法,解決了傳統(tǒng)遺傳算法已陷入局部最優(yōu)點的不足,并在VRPTW問題上得到較優(yōu)的優(yōu)化結(jié)果[9]。2012年,石兆等以費用和最小為目標(biāo)函數(shù),考慮運輸、制冷、貨損和懲罰成本約束,構(gòu)建了配送車輛路徑優(yōu)化模型,再利用兩階段HGA算法給出最優(yōu)配送方案[10]。2019年,葛顯龍利用時空泊松分布來仿真客戶位置,考慮客戶的時間和空間隨機性,構(gòu)建了多商品同時配送的數(shù)學(xué)模型。同時,他通過GA和禁忌搜索相結(jié)合的優(yōu)化方法進行問題求解[11]。2020年,趙志學(xué)把交通擁堵情況引入VRPTW數(shù)學(xué)問題,構(gòu)建了配送車輛路徑優(yōu)化的數(shù)學(xué)模型,并采用GA進行問題求解[12]。

文章在現(xiàn)有研究成果的基礎(chǔ)上,針對生鮮農(nóng)副產(chǎn)品配送問題構(gòu)建配送路徑優(yōu)化模型,并提出一種改進的遺傳算法進行路徑優(yōu)化研究,為企業(yè)生鮮農(nóng)產(chǎn)品配送車輛及路徑?jīng)Q策提供理論參考。

1 配送車輛路徑優(yōu)化模型

文章以生鮮農(nóng)產(chǎn)品配送路徑優(yōu)化為研究對象,以配送路徑最短構(gòu)造優(yōu)化模型,尋找最優(yōu)配送方案。

1.1 模型假設(shè)

(1)假設(shè)存在一個配送中心和多個客戶,配送車輛充足;

(2)配送車輛勻速行駛且燃料充足,無故障;

(3)配送中心貨物充足,能滿足多個客戶需求;

(4)所有貨品運輸儲存溫度一致;

(5)車輛的載重量相同;

(6)車輛服務(wù)完最后一個顧客后返回配送中心。

1.2 符號定義

A:表示客戶節(jié)點數(shù)量,A={0,1,2,…,A}, 0表示配送中心;

K:配送中心車輛數(shù)量;

Q:配送中心車輛的容量;

ti:到達(dá)第i個客戶點的時間;

wi:第i個客戶點的等待時間;

dij:第i個客戶點與第j個客戶點的距離;

qi:第i個客戶點的需求量;

fi:第i個客戶點的服務(wù)時間;

Ei:第i個客戶點的最早服務(wù)時間;

Li:第i個客戶點的最晚服務(wù)時間;

Tk:第k輛車的最大行駛時間。

1.3 決策變量

1.4 目標(biāo)函數(shù)

根據(jù)符號定義及決策變量,運輸車輛路徑最短的目標(biāo)函數(shù)可以表述為:

(1)

1.5 約束條件

(1)配送中心車輛數(shù)量約束

(2)

(2)車輛配送完成后返回配送中心

i=0,1,2,…,A;k=1,2,…,K

(3)

(3)每個客戶點都被一輛車服務(wù)一次

(4)

(5)

(4)每輛車的容量約束

(6)

(5)車輛最大行駛時間約束

(7)

(6)客戶服務(wù)時間約束

(8)

Ei≤(ti+wi)≤Lii=1,2,…,A

(9)

t0=w0=f0

(10)

2 混合遺傳算法

2.1 混合遺傳算法

混合遺傳算法是在基礎(chǔ)遺傳算法的基礎(chǔ)上引入節(jié)約算法產(chǎn)生初始種群,進而降低遺傳算法的搜索維度;引入大規(guī)模鄰域搜索算法中的破壞算子和修復(fù)算子,增強算法的局部搜索能力?；旌线z傳算法流程如圖1所示。

圖1 混合遺傳算法流程圖

2.2 C-W節(jié)約算法改進種群初始化

C-W節(jié)約算法是為解決TSP問題提出的一種無約束算法,不能直接用于VRPTW問題求解的種群初始化,文章通過增加車輛負(fù)載量和配送時間窗口改進C-W算法,在滿足客戶需求量、時間窗口和車輛最大負(fù)載量的約束下,確定最短路徑作為初始種群。具體改進及實現(xiàn)步驟如下:

Step1: 計算路徑上任意兩個點節(jié)省的里程值s(i,j),構(gòu)造集合S={s(i,j)|s(i,j)>0},并對里程值從大到小排序。

Step2:若S=φ,終止計算。否則,判斷第一項(i,j)兩點間的最大s(i,j)是否滿足以下條件之一,若符合,轉(zhuǎn)Step2,否則,轉(zhuǎn)Step6。

(a)點i和點j不在意配置的路徑中;

(b)點i和點j已在意配置的路徑上,但兩點不屬于同一條路徑;

(c)點i和點j由多條直線連接,但它們不是路徑內(nèi)的點,點i和點j分別為起點和終點。

Step3:計算連接點i和點j后線路上的總載貨量dij,若dij

Step4:計算每條路徑上各點開始服務(wù)時間和返回配送中心時間。

Step5:連接點i和點j,計算車輛到達(dá)每個客戶點的新時間和返回配送中心時間,判斷是否違反TW約束。若滿足TW約束,則生成較優(yōu)的初始路徑,否則,轉(zhuǎn)Step6。

Step6:消除S中的元素s(i,j),點i和點j不能插入作為配送車輛服務(wù)的客戶點。如果S=φ,終止計算,否則,轉(zhuǎn)Step2。

2.3 大規(guī)模鄰域搜索算法改進局部搜索

傳統(tǒng)遺傳算法的局部搜索容易出現(xiàn)過程停滯,在一定程度上影響了優(yōu)化求解的效率和最優(yōu)結(jié)果的精度,文章引入大規(guī)模鄰域搜索算法的破壞和修復(fù)思想改進遺傳算法的局部搜索操作,提高VRPTW問題配送路徑優(yōu)化精度。

對于帶時間窗的配送路徑優(yōu)化問題,定義客戶點i和客戶點j之間的相關(guān)性為

(11)

(12)

根據(jù)式(11)和式(12)可知,客戶點i和客戶點j在同一配送路徑上,相關(guān)性越大,則在破壞操作中越先移除。破壞操作選擇移除客戶點的過程中,為確保每次調(diào)用時都能破壞解決方案的不同部分,引入控制確定性的隨機性參數(shù)。

移除若干客戶后,再使用修復(fù)操作將移除的客戶點重新插入車輛行駛路徑增加最少的位置,并檢驗插入后是否滿足車輛載重量和時間窗約束。具體修復(fù)過程為:首先,找到滿足約束條件的位置,計算增加值最小的位置插入;然后,計算所有移除客戶點插入最佳位置后的目標(biāo)增加值,將增加值最大的客戶作為第一個插入;重復(fù)上述操作,直至移除客戶點全部插入配送路徑。

3 仿真實驗及結(jié)果分析

為檢驗混合遺傳算法的求解性能,在Intel Core i5 2.7 Gz處理器, 8.0 GB內(nèi)存, 64位Windows 10環(huán)境下,運用Python編程實現(xiàn)了求解VRPTW問題的混合遺傳算法,并對算例進行仿真實驗。

本算例來源于文獻[13],配送中心標(biāo)記為0點,20個客戶點標(biāo)記為1～20,車輛最大載重量為9噸,車輛行駛速度為40 km/h,以滿足車輛載重量和時間窗約束為前提,規(guī)劃最短配送路徑及車輛數(shù)量?？蛻酎c和配送中心位置信息如表1所示。

表1 配送中心及客戶點信息

針對上述算例,運用文章給出的混合遺傳算法進行仿真實驗,實驗初始參數(shù)選取如表2所示。程序運行10次,實驗結(jié)果見表3。

表2 仿真實驗初始參數(shù)

表3 仿真結(jié)果及分析

由表3可知,10次仿真求解獲得2種最優(yōu)配送路徑,方案1求得次數(shù)為7次,配送路徑最短距離為68.72 km;方案2求得次數(shù)為3次,配送路徑最短距離為68.87 km;兩種方案的最短路徑的絕對差為0.15 km。對比結(jié)果表明:文章提出的混合遺傳算法求解過程穩(wěn)定,結(jié)果精度高,雖然兩種方案的最短配送路徑存在一定的距離差異,但均可以指導(dǎo)企業(yè)配送路徑規(guī)劃。

運用傳統(tǒng)遺傳算法求解最短路徑為86.24 km,配送車輛3輛,具體路徑為:0-1-14-15-3-9-18-2-0,0-17-16-6-20-10-7-0,0-11-8-12-19-5-13-4-0。對比兩種優(yōu)化結(jié)果可以看出混合遺傳算法所得路徑優(yōu)于傳統(tǒng)遺傳算法,生鮮配送車輛路徑較傳統(tǒng)算法大幅縮短。

文章提出的混合遺傳算法可以有效避免陷入“局部收斂”的現(xiàn)象,加快了收斂速度,較好地解決了有時間窗的VRPTW問題,文章所述配送路徑的優(yōu)化結(jié)果是一個較優(yōu)的方案,可以指導(dǎo)生鮮農(nóng)產(chǎn)品規(guī)劃配送車輛路徑。

4 結(jié)論

文章以生鮮農(nóng)產(chǎn)品配送路徑優(yōu)化為切入點,考慮時間窗約束構(gòu)建了配送路徑最短的優(yōu)化模型,基于遺傳算法、節(jié)約算法、大規(guī)模鄰域搜索算法給出了一種混合遺傳算法的實現(xiàn)流程,詳細(xì)闡述了C-W節(jié)約算法初始化種群和大規(guī)模鄰域搜索算法局部搜索操作的具體步驟,并通過算例仿真實驗進行驗證。仿真試驗獲得算例配送路徑為4條,最多需要車輛數(shù)量為4輛,最短配送路徑68.72 km,優(yōu)于傳統(tǒng)遺傳算法所得最短路徑。驗證結(jié)果表明:本研究給出的混合遺傳算法能較好地解決有時間窗的車輛路徑問題,所得方案較優(yōu),可以指導(dǎo)企業(yè)規(guī)劃配送車輛的路徑。