果蔬采后分級和預冷車輛協(xié)同調度模型與算法

王旭坪,王 悅,李 婭,林 娜

(1.海南科技職業(yè)大學 財經學院,海南 海口 571126;2.大連理工大學智慧商務物流研究所,遼寧 大連 116024)

近年來,隨著越來越多的農戶采用B2C模式銷售果蔬農產品,果蔬采后商品化處理及“最先一公里”冷鏈物流環(huán)節(jié)存在的問題日漸暴露,包括人工分級效率低下、預冷不及時、采后處理環(huán)節(jié)斷鏈等。這些問題大大加劇了果蔬采后損耗,進一步造成生產資源巨大浪費與農民經濟損失[1-3]。調研發(fā)現(xiàn),我國果蔬產品采后損耗高達15%～25%,相當于8×106ha(1.2億畝)耕地種植的產品被浪費,而美、日、西歐等發(fā)達國家這一比例在5%以下。針對我國果蔬農產品產地分散、小規(guī)模生產的特點,適合中國國情的移動式分級[4]、預冷設施[5]以及配套的運載車輛應運而生。移動式分級車、預冷車可開至田間地頭對果蔬進行就地分級、預冷,解決了人工分級效率低、預冷站預冷不及時等問題,有助于降低果蔬采后損耗,也催生了“最先一公里”冷鏈物流環(huán)節(jié)協(xié)同運作優(yōu)化問題。

以采后分級環(huán)節(jié)和預冷環(huán)節(jié)為例,果蔬采后通常需要先進行分級處理,后進行預冷處理,以便將預冷處理后的產品及時保存在冷藏環(huán)境中,維持預冷效果。同時,預冷環(huán)節(jié)具有強時效性,需要在果蔬采后較短時間內完成,以盡快去除田間熱、抑制呼吸作用,保持產品質量。若分級環(huán)節(jié)與預冷環(huán)節(jié)獨立運作優(yōu)化,不僅難以保障果蔬產品的預冷效果,也容易造成服務資源浪費。因此,在果蔬收獲時節(jié),如何結合分級、預冷環(huán)節(jié)的先后服務順序以及預冷環(huán)節(jié)的強時效性等特征,協(xié)同調度有限的移動式分級、預冷服務資源以滿足小農戶的多樣化服務需求,在保障產品質量的同時盡可能降低運作成本,成為果蔬采后“最先一公里”冷鏈物流環(huán)節(jié)亟待解決的運作優(yōu)化問題。

盡管移動式分級車、預冷車已開始應用于果蔬采后處理實踐中,但由于農戶對于果蔬采后分級、預冷處理的意識仍較為薄弱,移動式分級、預冷服務尚未形成規(guī)?；瘧脠鼍?鮮有學者關注果蔬采后“最先一公里”中的預冷分級環(huán)節(jié)運作優(yōu)化問題。目前關于生鮮產品物流運作優(yōu)化領域的研究較多聚焦于農產品采后“最先一公里”集貨[6-8]、冷鏈網絡布局[9-11]以及生鮮產品城市“最后一公里”配送等方面[12-14]。分析本研究問題特點,其屬于一類帶有雙需求的車輛路徑規(guī)劃問題(Vehicle Routing Problem,VRP),這類問題的主要代表為同時取送貨VRP[15-17]。然而,本研究中客戶的分級、預冷需求屬不同類別的需求,需要兩輛車協(xié)同服務,這與帶有協(xié)同約束的車輛路徑問題(Vehicle Routing Problem with Synchronized Visits,VRPSV)相類似。Ali等[18]研究了同時考慮配送和安裝兩種服務需求的車輛路徑問題,并通過分支定界算法進行求解。Qiu等[19]關注家居行業(yè)送貨上門和安裝路徑問題,目標是確定車輛的最佳送貨路線和技術人員的最佳服務路線,并提出深度強化學習方法進行求解。Liu等[20]研究了一類帶時間窗和協(xié)同服務約束的特殊車輛路徑問題,該問題的協(xié)同約束將不同車輛路徑相互連接,考慮到計算時間的復雜性,設計了高效的改進大鄰域搜索算法進行求解。Fink等[21]聚焦機場地勤運營規(guī)劃問題,將其抽象為具有工人和車輛同步的車輛路徑問題,并設計分支定價算法進行求解。Hintsch[22]研究了軟集群車輛路徑問題,考慮同一集群客戶必須由同一車輛提供服務特點,設計了多鄰域搜索算法進行求解。Aziez等[23]研究了具有動態(tài)需求AGV 協(xié)同的車隊規(guī)模和路由問題,該問題中醫(yī)院執(zhí)行不同任務需要不同類型的手推車,這些手推車由AGV運輸,目標是同時優(yōu)化手推車和AGV 的類型和路線并滿足服務時間限制。Erdem 等[24]研究了家庭醫(yī)生日常路線協(xié)同規(guī)劃問題,以便為分散區(qū)域的患者提供一系列服務,將其抽象為帶時間窗與電車充電的VRPSV,基于此構建了混合整數(shù)規(guī)劃模型,并設計了一種特定的自適應大鄰域搜索算法進行求解。Doulabi等[25]將具有隨機時間的VRPSV 表示為兩階段隨機整數(shù)規(guī)劃模型,并使用分支定界法對隨機家庭醫(yī)療計劃進行優(yōu)化求解。上述研究在模型構建和方法求解方面為本研究的順利開展奠定了重要的理論基礎。然而,現(xiàn)有關于VRPSV的研究中僅以兩個需求間的服務時間間隔作為協(xié)同條件。在本文中,除了考慮分級與預冷服務的時間間隔約束,還需要考慮果蔬最佳預冷時間約束,這進一步加劇了雙需求VRP的協(xié)同復雜度。同時,本文研究對象為采后“最先一公里”果蔬農產品,導致該問題與傳統(tǒng)生鮮產品車輛路徑問題具有明顯區(qū)別,主要體現(xiàn)在延遲預冷對果蔬新鮮度變化的獨特影響?；谏鲜龇治?研究果蔬農產品分級和預冷車輛協(xié)同調度優(yōu)化問題需要對現(xiàn)有VRP模型進行拓展,并設計考慮多協(xié)同約束的求解算法。

針對果蔬農產品分級和預冷環(huán)節(jié)協(xié)同優(yōu)化問題,本文綜合考慮分級和預冷的先后服務順序約束、最大時間間隔約束以及最佳預冷時間約束,結合預冷環(huán)節(jié)的時效性特點,將延遲預冷產生的新鮮度變化轉化為三階段成本函數(shù),構建了移動式分級和預冷車輛協(xié)同調度模型,進而結合問題的關鍵協(xié)同約束條件設計了混合遺傳算法進行求解。該算法融合了遺傳算法的全局尋優(yōu)能力與鄰域搜索算法的局部尋優(yōu)能力。最后,基于VRP 基準算例的數(shù)值實驗驗證了本文所設計算法在求解大規(guī)模算例時可以快速收斂到高質量的解,基于陜西省洛川縣水蜜桃產業(yè)的分級預冷數(shù)據證明了本文模型的合理性。

1 數(shù)學模型

1.1 問題描述

為便于后續(xù)存儲、銷售和運輸,農產品在采摘后均將進行分級,是否進行預冷則需根據農產品類型和農戶需要進行取舍。根據農戶的分級、預冷需求差異,可將農戶點分為兩類:一類是僅有分級需求的農戶點,另一類是具有分級和預冷的雙需求農戶點。對于僅有分級需求的農戶點,由一輛分級車服務一次,且分級車需要在給定的軟時間窗內到達,否則將產生早到等待和晚到懲罰成本。對于雙需求農戶點,由一輛分級車和一輛預冷車分別服務一次,且分級車需要在給定的軟時間窗內到達,預冷車則需要在分級車完成分級服務之后到達,且與分級服務的間隔不能超過最大允許間隔時間(見圖1),否則將產生對應的懲罰成本。這是因為首先按照分級、預冷的作業(yè)特點,分級服務應先于預冷服務。其次,為保證顧客滿意度,兩類服務間隔時間不宜過長。此外,為保證預冷的及時性和有效性,預冷服務需在農產品采摘后的一定時間內完成,否則會影響預冷效果,產生延遲預冷成本。如何在滿足上述時間窗約束的條件下,兼顧兩類農戶點的分級、預冷需求,協(xié)同規(guī)劃分級車和預冷車的服務路徑,實現(xiàn)系統(tǒng)資源的最優(yōu)配置,是本文所要解決的關鍵問題(見圖2)。

圖1 分級-預冷服務時間線Fig.1 Timeline of grading and pre-cooling services

圖2 移動式分級和預冷資源協(xié)同調度問題Fig.2 Collaborative scheduling of mobile grading and pre-cooling resources

基于上述分析,本文從系統(tǒng)成本最優(yōu)角度對果蔬農產品分級和預冷環(huán)節(jié)協(xié)同優(yōu)化問題進行研究,決策內容包括:①分級車、預冷車分配;②分級車、預冷車服務路徑;③分級車、預冷車服務時間規(guī)劃。

1.2 模型設定

為便于討論且不失一般性,本文做出如下假定:

(1) 所有分級車和預冷車均以冷鏈物流中心為起始點,且所有車輛每天僅往返一次。

(2) 農戶點需求均為小批量,且不超過分級車、預冷車的最大服務工作量。

(3) 為每個農戶點提供分級服務的時間窗固定且已知。

(4) 同類型車輛之間是同質的,且車輛行駛速度均為勻速。

(5) 果蔬采摘結束便有分級需求,將農戶分級時間窗下限視為果蔬采摘結束時間。

符號說明:

決策變量

參數(shù)

1.3 成本分析

(1) 車輛固定啟動成本。車輛固定啟動成本是分級車、預冷車啟動時所需的固定啟動費用,包括車輛的折舊成本、司機的駕駛成本等,即

(2) 車輛行駛成本。車輛行駛成本是分級車和預冷車在行駛過程中產生的油耗成本,即

(3) 分級和預冷服務總成本。在田間地頭提供分級或預冷服務,需要人工和自動化設備的相互配合,將產生相應的能耗和人工成本。因此,分級和預冷服務總成本可按照下式計算:

(4) 早到等待和晚到懲罰成本。對于分級車,早到等待和晚到懲罰成本是指車輛早于和晚于規(guī)定的分級時間窗到達產生的懲罰成本。對于預冷車,當其早于分級車到達時需要等待至分級車結束服務才能開始服務,因此會產生相應的早到等待成本。此外,當預冷車晚于分級-預冷最大允許間隔時間到達時,亦會產生相應的晚到懲罰成本。因此,早到等待和晚到懲罰成本為

(5) 延遲預冷成本。延遲預冷成本是指延遲預冷時間過長時造成預冷效果不佳所產生的損失成本。果蔬農產品采摘后,若延遲預冷時間在tdelay內完成預冷,其預冷效果最佳,否則預冷效果將隨時間逐步減弱,且當延遲預冷時間超過臨界值t F時,預冷將失去意義[26]?？山朴孟率奖硎绢A冷效果隨時間變化的規(guī)律:

式中,α為折損率,且α=1/tdelay。

對Q(t)進行成本轉化,可得到果蔬農產品延遲預冷成本隨時間變化的函數(shù),即

式中:a為單位質量果蔬因延遲預冷產生的貨損成本為客戶點i的預冷需求量。

1.4 模型建立

綜合式(1)～(6),可得如下移動式分級-預冷資源協(xié)同調度優(yōu)化模型:

其中:式(7)表示最小化系統(tǒng)總運營成本z,包含車輛固定啟動成本z1、車輛行駛成本z2、分級和預冷服務總成本z3、超出分級時間窗、早到等待和晚到懲罰成本z4以及延遲預冷成本z5;式(8)表示所有啟動的預冷車輛和分級車輛均從冷鏈物流中心(閉合單車場)出發(fā),服務完成后返回車場;式(9)表示同一路徑上某種類型服務車輛服務的農戶需求量不得超過該車輛最大服務工作量;式(10)表示每個農戶點的每種需求僅由對應類型下的同一輛車完成服務,且相應需求不可拆;式(11)、(12)分別表示分級車和預冷車的數(shù)量限制;式(13)、(14)分別表示分級車和預冷車到達時間和開始服務時間的關系;式(15)～(18)分別表示分級車和預冷車的早到等待時長和晚到延遲時長;式(19)表示任意類型車輛到達相鄰農戶點之間的時間間隔關系;式(20)為農戶分級時間窗約束;式(21)表示具有雙重需求的農戶點服務時,必須先進行分級服務、后進行預冷服務;式(22)表示具有雙重需求的農戶點服務時,預冷車到達時間與分級車分級服務結束的間隔不能超過最大允許間隔時間;式(23)表示所有分級農戶點的分級服務結束時間不得超過果蔬最佳預冷時間;式(24)表示每種類型車輛的總行駛時間不得超過其對應的最大行駛時間;式(25)表示分級車和預冷車不得晚于物流中心最大服務時間返回;式(26)、(27)為車輛的進出平衡關系;式(28)為決策變量的取值約束。

2 算法設計

本文問題是考慮客戶雙需求帶有的雙時間窗、雙需求服務先后順序、服務延遲時間等對分級車輛和預冷車輛服務路徑進行協(xié)同優(yōu)化的經典VRP的拓展問題,屬于NP-hard問題。采用精確算法求解困難,因而本研究結合問題特點,設計了一種特定的啟發(fā)式算法進行求解。遺傳算法具有較好的全局搜索能力,但該算法存在局部搜索能力差的缺點。同時,遺傳算法可擴展性強,因而較容易與其他算法進行結合,而鄰域搜索算法具有局部搜索能力強的特點。因此,為提高算法的收斂速度與求解質量,本研究綜合考慮遺傳算法的全局搜索能力與鄰域搜索算法的局部搜索能力,采用遺傳算法的框架,引入鄰域搜索算法嵌入遺傳算法中的變異操作,設計混合遺傳算法求解上述模型。所設計算法的創(chuàng)新點主要包括3個方面:①結合問題的雙需求特點,設計基于雙序列的解的表達方式,其中一條序列表示分級車輛路徑,另一條序列表示預冷車輛路徑,并結合雙時間窗、服務先后順序等問題特點設計特定的初始種群生成機制與解碼機制;②設計基于最佳插入策略的順序交叉算子,以最小化運作成本為評估機制,結合模型的相關協(xié)同約束條件進行可行性檢查,保證生成高質量的可行子代,以加速算法收斂;③結合雙需求服務的協(xié)同條件,設計基于大路徑-相鄰路徑-子路徑三階段鄰域搜索的變異操作,對種群中部分個體進行變異,提高算法的局部搜索能力。

圖3所示為算法運行框架。其中,生成初始種群、種群個體交叉和種群個體變異3個部分為本研究關鍵創(chuàng)新環(huán)節(jié)。

圖3 混合遺傳算法流程Fig.3 Flow chart of the hybrid genetic algorithm

2.1 基于雙序列染色體的解的表達與初始種群生成

該研究問題中客戶具有兩類需求,且分別需要不同類型車輛進行服務。為了表示不同類型車輛的服務路徑,設計了基于雙序列染色體的編碼方式,并基于此設計了解碼及初始種群生成機制,如圖4所示。其中:序列G r為所有的分級服務需求點,通過將其解碼得到分級車輛服務路徑(解碼機制見步驟2);序列P r為所有的預冷服務需求點,結合分級預冷服務最大時間間隔約束得到預冷車輛服務路徑(解碼機制見步驟5)。

圖4 初始個體生成過程示意圖Fig.4 An example of the initial individual generation

基于所設計的雙序列編碼方式及對應的解碼機制,初始種群生成步驟如下:

步驟1基于客戶聚類生成分級服務需求點序列G r。隨機選擇K1個分級客戶點作為聚類簇中心,將剩余N1-K1個客戶點分配給距離最近的聚類簇。隨機選擇一個聚類簇中心i作為G r序列的起始點,依次排列屬于聚類簇i的客戶點,繼而選擇距離聚類簇中心i最近的聚類簇中心j進行排列,并依次排列屬于聚類簇j的客戶點。重復此步驟,直至完成所有客戶點排列。

步驟2解碼得到分級車輛服務路徑G v。以冷鏈物流中心0點作為第一條分級車輛路徑的起始點,將G r中的點依次添加至當前路徑,并基于約束式(9)檢查分級車輛載重約束是否滿足。若不滿足,則在當前路徑末尾添加0 作為路徑終點;若滿足,則按照客戶點分級時間窗下限E1i自小到大的順序對當前路徑進行排序。基于約束式(23)檢查分級服務結束時間是否滿足果蔬最佳預冷時間約束。若不滿足,將當前客戶點移至序列G r末尾;若滿足,基于約束式(24)、(25)分別檢查分級車輛工作時間約束、分級車輛到達冷鏈物流中心的時間約束。若不滿足,則在當前路徑末尾添加0作為路徑終點;若滿足,則繼續(xù)從序列G r中添加點至當前路徑。重復上述步驟,直至序列G r為空。

步驟3基于分級車輛服務路徑G v得到預冷服務需求點序列P r。按照預冷服務需求點在分級車輛服務路徑G v中出現(xiàn)的順序,將其依次插入序列P r。

步驟4基于分級車輛服務路徑G v計算預冷訂單的服務時間窗。在求解分級預冷車輛協(xié)同調度問題時,關鍵是尋求兩種服務的協(xié)同優(yōu)化。在本研究中,分級服務在預冷服務之前完成,且兩者之間的服務間隔不能超過一定的限制。由于分級車輛服務路徑已知,則預冷訂單服務時間窗上下限均可基于分級服務完成時間與兩者之間的最大間隔時間得到,如式(22)所示。

步驟5解碼得到預冷車輛服務路徑P v。在得到預冷訂單服務時間窗后,可基于此進行解碼得到預冷車輛服務路徑,該過程與步驟2類似。首先,以冷鏈物流中心0點作為第一條預冷車輛路徑的起始點,將P r中的點依次添加至當前路徑,并基于約束式(9)檢查預冷車輛服務能力是否滿足。若不滿足,則在當前路徑末尾添加0 作為路徑終點;若滿足,則按照預冷時間窗下限自小至大的順序對當前路徑進行排序?；诩s束式(24)、(25)分別檢查預冷車輛工作時間約束、預冷車輛到達冷鏈物流中心的時間約束。若不滿足,則在當前路徑末尾添加0作為路徑終點;若滿足,則繼續(xù)從序列P r中添加點至當前路徑。重復上述步驟,直至序列P r為空。

步驟6重復步驟1～5,直至生成G個初始個體。

2.2 基于輪盤賭機制的選擇操作

采用輪盤賭的方式,根據適應度值選擇個體進入下一次迭代。具體如下:將每條染色體一對一映射到[0,Sum]的連續(xù)區(qū)間(Sum 為所有染色體的適應度之和),每條染色體區(qū)間的大小與其適應度值相匹配,因而適應度值越大的染色體被選中的概率越大。染色體i的適應度f i等于其對應解的目標函數(shù)值Z i的倒數(shù),即

2.3 基于最佳插入策略的順序交叉操作

交叉操作采用經典的順序交叉算子,融合最佳插入算子以生成高質量的可行后代。首先選擇父代個體A 和B,在其分級服務需求點序列中隨機選擇兩個基因位點P1和P2,順序交換父代個體A、B中P1～P2序列,進而對交換后的個體進行沖突檢測,刪除重復的需求點,并基于最佳插入策略插入缺失的需求點

以圖5為例,在父代個體的分級服務需求點序列中選擇第4～第7個位點進行交換,得到中間父代A1和B1。在交換后,父代A1中需求點7、9、10重復,需求點1、5、6缺失;同時,父代B1中需求點1、5、6 重復,需求點7、9、10 缺失。在父代A1、B1中刪除重復點,進而基于最佳插入策略插入缺失點。

圖5 交叉算子示意圖Fig.5 The schematic of the crossover operator

具體步驟如下:

步驟1以父代A 為例,對刪除重復點后的G r序列進行解碼,得到分級車輛服務路徑G v與預冷車輛服務路徑P v,便于后續(xù)插入成本的計算。

步驟2插入缺失點至當前解(以需求點1為例)。將點1插入G v中的可行位置,這里每一條分級車輛路徑至多只有一個可行位置。這是因為分級服務車輛開展服務時基本按照節(jié)點的時間窗先后順序,無須將節(jié)點插入一條分級車輛路徑中的所有位置,僅須將節(jié)點1插入E1i比其小的節(jié)點之后且E1i比其大的節(jié)點之前。插入位置的可行性判斷基于約束式(9)以及式(23)～(25)。針對所有可行的插入位置,根據1.4節(jié)中式(7)計算插入點1前后成本A1和A2,得到點1的插入成本A2-A1。最后,將點1插入成本最小的位置。需要注意的是,在計算點1插入G v前后的成本時,只計算點1插入當前分級車輛路徑的成本,無須計算所有分級車輛路徑。

步驟3重復步驟(2),直到父代A 中所有缺失點均插入G v。

步驟4重復步驟(1)～(3),直到父代B 中所有缺失點均插入G v。

2.4 基于三階段鄰域搜索的變異操作

考慮到鄰域搜索算法的局部搜索能力,本研究將其嵌入到遺傳算法的變異操作中,結合雙需求服務的協(xié)同條件,分別設計大路徑-相鄰路徑-子路徑3個層面的鄰域搜索算子。鄰域搜索算法的基本框架如下:假設x為問題的一個可行解,將x作為當前解,應用鄰域搜索算子得到x的鄰域解x',若x'的目標值更優(yōu),則將x'作為新的當前解繼續(xù)進行鄰域搜索,直到達到最大迭代次數(shù)。

由于3種算子的局部搜索過程按照由大至小的層級展開,故在操作時依序作用于待變異的個體。假設結束第一/二層鄰域搜索后得到的局部最優(yōu)解為x'/x″,則將x'/x″作為第二/三層鄰域搜索的初始解,從而保證變異過程總是生成不劣于變異前的個體。

3種算子的具體過程如下:

(1) 最佳插入算子——大路徑層。該算子旨在對大路徑進行局部搜索,首先將個體A 的G r序列進行解碼得到G v,然后隨機刪除G r序列中的部分點,并在G v中對應刪除,最后按照2.3節(jié)步驟2中采用的最佳插入策略,將已刪除的點插入G v。

(2)Reverse算子——相鄰路徑層。在本研究中,基于Reverse算子對個體進行局部搜索時,在個體A 的G r序列中隨機選擇點i、j,將點i、j間點的順序進行倒序操作。這一操作將直接影響解碼過程中相鄰路徑的生成過程,旨在通過交換相鄰路徑的節(jié)點實現(xiàn)局部搜索。

(3) 相似點交換算子——子路徑層。隨機交換個體A 的G r序列中兩個相似的節(jié)點i、j,由于兩個節(jié)點均來自某一條分級車輛路徑,故該算子旨在實現(xiàn)子路徑層面的局部優(yōu)化。兩點i、j的相似性R ij基于下式得到:

3 數(shù)值分析

3.1 算法有效性驗證

目前有關雙需求車輛協(xié)同調度問題尚未有可供參考的基準算例,為了測試所設計的混合遺傳算法的有效性,本文以Solomon帶時間窗的標準算例庫[27]為基礎,并根據本文問題所需對其進行了數(shù)據修改和補充。選取Solomon 算例庫中的C101、C201、R101、R201、RC101、RC201等6類算例為實驗對象,每類算例中分別隨機選取25、50、100個客戶點生成3組不同客戶規(guī)模的算例,共組成18個測試算例。客戶地理位置、需求量及時間窗信息保持不變,客戶處的服務時間通過計算客戶需求量與服務速度的比值得到,并對其含有25、50、100個客戶點的算例分別隨機生成10、25、50個雙需求客戶點。算例中分級車與預冷車的固定成本分別為200和300元/輛;分級車的早到與晚到懲罰系數(shù)為0.04和0.06;車輛最大行駛時間均為200 min。算法采用Matlab2016a進行編程,在Windows10操作系統(tǒng)8 GB 內存環(huán)境下運行。經過多次實驗,設置相關參數(shù)如下:種群規(guī)模均為100;客戶規(guī)模為25、50、100的算例最大迭代次數(shù)分別為1 000、1 000和2 000。

為測試混合遺傳算法求解雙需求車輛路徑問題的性能,選取標準遺傳算法和變鄰域搜索算法與之進行對比。其中,標準遺傳算法與本研究所設計的混合遺傳算法主要區(qū)別在于交叉和變異操作部分,前者的交叉操作采用與本研究類似的步驟,但是在重新插入缺失點時僅將點插入可行位置而非最佳位置。變異操作采用一種經典的變異算子,即在染色體中隨機選擇兩個基因點進行交換。標準遺傳算法中初始種群生成及編解碼機制、選擇操作均與本研究所設計的混合遺傳算法一致。變鄰域搜索算法則按照該算法的標準框架進行基于單初始解的求解,其中鄰域搜索部分采用本研究設計的三階段鄰域搜索算子。其初始解生成及編解碼機制均與本研究所設計的混合遺傳算法一致?；谌炙阉鞯倪z傳算法與基于局部搜索的鄰域搜索算法結合后的混合遺傳算法的效果將在本部分得到測試。

使用3種算法對每個算例求解20次,結果如表1所示。

表1 3種算法結果比較Tab.1 Comparison of results of three algorithms

由表1可以看出,在求解質量上,本文算法最優(yōu)值較標準遺傳算法平均改進幅度為12.32%,相較于變鄰域搜索算法平均改進幅度為17.13%,且在求解大規(guī)模算例時改進幅度更大。在求解時間上,與變鄰域搜索算法相比,本文算法在小規(guī)模、中等規(guī)模和大規(guī)模算例中具有顯著優(yōu)勢;與標準遺傳算法相比,本文算法在小規(guī)模算例中與之表現(xiàn)相當,但在大規(guī)模算例中優(yōu)勢凸顯。綜上所述,本文提出的混合遺傳算法在求解質量與求解時間方面均優(yōu)于現(xiàn)有的變鄰域搜索算法與標準遺傳算法,且在求解大規(guī)模算例時優(yōu)勢更加突出。

為了直觀地顯示本文算法在求解性能上的顯著優(yōu)勢,以算例R101為例,將3種算法的收斂情況進行對比,如圖6所示。

圖6 3種算法求解R101算例的收斂過程Fig.6 The convergence process of three algorithms for solving the R101 instance

圖6結果顯示,在求解小規(guī)模算例時,標準遺傳算法和變鄰域搜索算法均可得到與混合遺傳算法相近的解,且標準遺傳算法與本文算法收斂速度相當,這進一步解釋了小規(guī)模算例中,標準遺傳算法與本文算法求解時間相當。但在求解中等規(guī)模、大規(guī)模算例時,相較于另兩種算法,混合遺傳算法具有更快的收斂速度,可以在更短時間內收斂到更高質量的解,在求解質量和速度上具有顯著優(yōu)勢。這進一步解釋了在中等規(guī)模、大規(guī)模算例中,本文算法求解時間顯著短于標準遺傳算法和變鄰域搜索算法。

3.2 實例分析

3.2.1基礎數(shù)據與參數(shù)設定 根據實地調研,本部分選取陜西省洛川縣25個典型村的水蜜桃種植數(shù)據進行實例研究。假設一家冷鏈物流中心擬在洛川縣提供水蜜桃采后商品化處理服務,該中心同時配置有移動式分級車和預冷車,可為農戶提供移動式分級與預冷服務。在每一典型村中選取一戶典型戶作為客戶點,25個客戶點的地理坐標、分級量、預冷量、分級服務時間窗等具體信息如表2 所示,其中,0表示冷鏈物流中心。客戶分級需求量計算方式如下:根據調研得到的25個村落典型戶2020年水蜜桃產量和種植面積數(shù)據,結合水蜜桃的采收時長(單位:d),計算得到每個典型戶平均一天內采摘水蜜桃量。農戶的分級時間窗根據果農實際采收時間生成,其服從U(14,18)的均勻分布(單位:h)。

表2 農戶基本信息Tab.2 Basic information of farmers

其他實例參數(shù)結合調研數(shù)據設定如下:分級車的固定啟動成本為500元/輛,預冷車為300元/輛;分級車的車輛行駛成本為2 元/km,預冷車為1.5元/km;分級車上設備的能耗成本為1.5元/min,預冷車為1.2元/min;分級車行駛速度為30 km/h,預冷車為40 km/h;分級車提供分級服務時的工作速度為30 kg/min,預冷車為15 kg/min;分級車的最大行駛時間為500 min,預冷車為600 min;農戶所能接受的分級、預冷服務最大允許間隔時間(以農戶分級車結束服務時間為起點計算)為100min;分級車的最大服務處理量為7t,預冷車為4 t;水蜜桃最大預冷延遲時間為6h;分級車早到等待和晚到懲罰系數(shù)分別為0.5 和1.5 元/min,預冷車分別為0.8和20元/min;預冷車預冷方式為差壓預冷。

3.2.2模型求解與結果分析采用本文算法對該實例進行10次求解,最優(yōu)方案如表3所示。冷鏈物流中心總計派出5輛分級車和4輛預冷車為25個農戶提供服務,其總成本為9 448.91元。移動式分級服務的單位成本基本維持在0.2元/kg左右,移動式預冷服務的單位成本維持在0.3元/kg左右,該結果相對于調研中得到的人工分級成本0.4元/kg、預冷庫預冷成本0.8 元/kg 均有所降低。這表明,使用移動式設備進行采后處理可以節(jié)約成本,當然這不排除參數(shù)理想化的結果。此外,分級車5由于只服務了一個農戶,造成分級服務單位成本高于人工分級的情況。這表明,當農戶點數(shù)量較少時,采用移動式服務設備進行采后處理無法實現(xiàn)規(guī)模經濟。算例結果中延遲預冷成本均為0,這是因為分級時間窗設定較為集中,在服務最大允許間隔時間的約束下,可以確保水蜜桃采后預冷的及時性,也間接說明本文所提出的移動式分級與預冷資源協(xié)同調度模型可以有效避免預冷延遲。

表3 車輛調度方案Tab.3 Vehicle scheduling plan

3.3 靈敏度分析

3.3.1服務水平分析 分級和預冷環(huán)節(jié)的服務時間間隔在一定程度上反映了服務水平,該間隔越小,表明農戶等待預冷服務的時間越短,對服務過程滿意度越高,服務水平越高,但協(xié)同調度的困難就會越大。為了尋找最佳服務間隔時間,本文將其分別設定為60、80、100、120和140 min,其余參數(shù)不變,具體計算結果如表4所示。通過對比可以得出,改變服務時間間隔對固定成本和服務成本均不產生影響。這表明,改變服務時間間隔,其使用車輛數(shù)未產生變化;延遲預冷成本始終為0,表明本文模型能較好保證預冷及時性;隨著服務時間間隔的增大,分級車和預冷車的協(xié)同服務時間窗更容易滿足,故懲罰成本逐漸降低,當間隔時間為140 min時總成本最低。因此,考慮到農戶對服務過程的滿意度,本實例中應將其設定為100 min。

表4 服務水平分析Tab.4 Service level analysis

3.3.2預冷需求占比分析 為了尋找較優(yōu)的預冷需求占比(總預冷需求量/總分級需求量),保持實例中其余參數(shù)不變,通過改變所有客戶點中有預冷需求的客戶點數(shù),測試預冷車服務率(同一路徑上預冷車總服務量/預冷車最大服務量)的影響,具體情況如圖7所示。由圖7可以得出,隨著預冷需求占比的增加,預冷車服務率呈現(xiàn)先增加后減少的趨勢,并在預冷需求占比為50%時預冷車服務率達到最高。

圖7 預冷需求占比分析Fig.7 Analysis of pre-cooling demands’proportion

3.4 實驗結果討論

基于上述研究結果,可以得到以下管理啟示:

(1) 與傳統(tǒng)的人工分級和預冷庫預冷模式相比,新興的移動式分級和預冷資源協(xié)同調度有助于降低企業(yè)運作成本并有效縮短產品預冷延遲時間,這主要得益于協(xié)同優(yōu)化思想對資源的有效整合與利用。生鮮農產品物流服務企業(yè)應逐步將果蔬采后移動式預處理技術應用于實際運作中,并積極開展多環(huán)節(jié)協(xié)同運作優(yōu)化,以增強企業(yè)競爭力。

(2) 在開展分級、預冷服務協(xié)同運作優(yōu)化時,增大兩項服務之間的時間間隔有助于降低優(yōu)化難度以及總運營成本,這是因為更寬的時間間隔增大了調度的柔性進而降低了協(xié)同的難度與服務延遲成本。然而,更寬的時間間隔會延長客戶等待時間,并進一步導致客戶滿意度下降。因此,物流企業(yè)在開展服務前應充分調研客戶對服務時間間隔的期望分布,以確定合理的折中。

(3) 當客戶需求的種類及數(shù)量變化時,車輛的服務率也會隨之變化。例如,隨著預冷需求占比的增加,預冷車服務率先升高后降低,這主要是由于原有車輛未達到較高的服務率,故增加部分需求將會增加車輛的平均服務率。然而,當需求過大時,原有車輛無法滿足所有需求,此時新增車輛將會降低平均服務率。因此,物流企業(yè)應綜合考慮需求特點配置不同的車型,通過提高車輛服務率來減少車輛使用,最大限度降低總運作成本。

4 結論

本研究聚焦果蔬采后“最先一公里”冷鏈物流分級預冷環(huán)節(jié)協(xié)同運作優(yōu)化問題,旨在為服務主體開展分級和預冷服務協(xié)同優(yōu)化提供決策支持,主要貢獻包括3個方面:

(1) 綜合考慮果蔬最佳預冷時間、先分級后預冷的服務順序等特有協(xié)同情景,構建了移動式分級預冷資源協(xié)同調度優(yōu)化模型,拓展了VRPSV 的應用場景。

(2) 考慮延遲預冷帶來的果蔬新鮮度的特殊變化,設計了延遲預冷成本函數(shù),在保障產品質量的同時最小化服務運作成本。

(3) 結合問題的關鍵協(xié)同約束條件設計混合遺傳算法求解該模型,并結合問題特點設計了特有的基于雙序列的解的表達方式、基于最佳插入策略順序交叉算子以及基于三階段鄰域搜索的變異操作,可實現(xiàn)大規(guī)模算例高效高質求解。

實驗證明,本研究提出的移動式分級預冷資源協(xié)同調度模型及求解方法能有效解決果蔬采后人工分級效率低、預冷庫預冷不及時以及“最先一公里”冷鏈物流環(huán)節(jié)斷鏈問題。隨著國家對農產品上行“最先一公里”建設力度的加大以及移動式預處理技術的發(fā)展成熟,基于協(xié)同優(yōu)化思想開展“最先一公里”冷鏈物流環(huán)節(jié)協(xié)同運作優(yōu)化研究對整合村鎮(zhèn)冷鏈服務資源、降低果蔬采后損耗具有重大價值,并助力農產品冷鏈物流行業(yè)轉型升級和高質量發(fā)展。未來將對多品類果蔬產品、不同車型的移動式分級預冷車輛協(xié)同調度展開研究。