□ 韋文鑫，劉新君,楊 洋,卞 貝,江億平

(南京農(nóng)業(yè)大學(xué) 工學(xué)院，江蘇 南京 210000)

1 引言

伴隨著經(jīng)濟的發(fā)展和人們生活水平的提高，冷鏈物流得到較快發(fā)展。由于我國生鮮冷鏈物流起步較晚，基礎(chǔ)薄弱，生鮮產(chǎn)品在運輸過程中損耗嚴重。據(jù)統(tǒng)計，我國現(xiàn)在每年約有4億噸生鮮農(nóng)產(chǎn)品進入流通領(lǐng)域,其中，果蔬類冷鏈流通率達到10%,冷藏運輸率達到15%，其中的損耗率高達30%，損耗值每年在1000億元以上[1]。水蜜桃作為生鮮配送中最重要的農(nóng)林作物，因其成熟階段正值高溫季節(jié)，加上自身保質(zhì)期限短，易破損腐爛等特殊的生理屬性[2]，如何合理安排配送車輛行駛路徑將水蜜桃高效快捷地配送到客戶手中，并且同時可以滿足客戶的成熟度需求成為當(dāng)下需要解決的問題。

針對帶時間窗的車輛路徑問題(VRPTW),國內(nèi)外學(xué)者做了大量的研究。謝秉磊等將貨運量約束和時間窗約束轉(zhuǎn)化為目標(biāo)約束,設(shè)計出了基于自然數(shù)編碼的可同時處理軟、硬時間窗約束的遺傳算法[3]。Sally Kassem等研究了閉環(huán)物流網(wǎng)絡(luò)優(yōu)化中同時取貨和配送的車輛路徑問題，提出了一種混合整數(shù)規(guī)劃模型來表達所考慮的問題，并開發(fā)了一種啟發(fā)式求解方法用作模擬退火過程的初始解決方案[4]。何小鋒等針對蟻群算法在求解VRPTW問題時易陷入局部最優(yōu)和收斂速度慢的問題，提出一種求解VRPTW的量子蟻群算法(QACA)，有效避免了算法陷入局部最優(yōu)[5]。孫明明等充分考慮冷鏈物流配送過程中時間、溫度、貨損因素，通過節(jié)約成本法分析求解達到降低配送成本、滿足客戶需求時間的雙重要求[6]。Junlong Zhang等提出了一種新的隨機規(guī)劃模型，開發(fā)了一種結(jié)合了路由約簡機制的迭代禁忌搜索啟發(fā)式算法求解在旅行和服務(wù)時間不確定的情況下的具有軟時間窗的隨機車輛路徑問題模型[7]。

然而，現(xiàn)在對于水蜜桃采摘后的成熟度變化做出預(yù)測和評估的研究卻很少，把水蜜桃的采摘后自我成熟的過程和冷鏈運輸過程進行聯(lián)合優(yōu)化的研究更是少有學(xué)者涉及。因此，本文的創(chuàng)新點體現(xiàn)在：以數(shù)學(xué)模型定量研究水蜜桃采摘后成熟度的動態(tài)變化，從而將客戶對水蜜桃成熟度的要求轉(zhuǎn)換為精確的配送時間窗的約束，再運用遺傳算法以總配送距離最短為目標(biāo)求解建立的水蜜桃配送的聯(lián)合優(yōu)化模型，不僅實現(xiàn)了對水蜜桃運輸過程中成熟度的預(yù)測和監(jiān)控，減少浪費損失，還大大提高了客戶滿意度和冷鏈物流企業(yè)的競爭力，有效地驅(qū)動了我國生鮮配送市場未來的發(fā)展。

2 水蜜桃成熟度模型

2.1 實驗材料和各項指標(biāo)分析

選取“湖景蜜露”水蜜桃品種作為試材，參照成熟度劃分標(biāo)準，選擇無傷害、大小均勻的果實。在20℃恒溫儲藏的條件下測定果實的硬度(Y1)、出汁率(Y2)、可溶性固形物(Y3)和失重率(Y4)四項指標(biāo)。得到各項指標(biāo)隨時間增加的動態(tài)變化情況(圖1)，并通過SPSS軟件對各項指標(biāo)進行曲線估計，擬合出四項指標(biāo)的回歸方程(表1)，且四條回歸曲線的決定系數(shù)R2均大于0.8，擬合效果很好。

圖1 水蜜桃成熟度各項評價指標(biāo)隨時間增加(成熟度增加)的變化情況

表1 水蜜桃成熟度各項評價指標(biāo)隨時間增加(成熟度增加)的回歸方程

2.2 構(gòu)建表征成熟度隨時間變化的數(shù)學(xué)模型

為了得到更加精確簡易的描述水蜜桃成熟度隨時間變化的模型，綜合了硬度(Y1)、出汁率(Y2)、可溶性固形物(Y3)和失重率(Y4)四項指標(biāo)通過多元線性回歸建立了新的綜合回歸模型(1)，通過綜合指標(biāo)Z關(guān)于時間t的數(shù)學(xué)模型更加全面地量化成熟度變化情況。

Z=7.443-0.027Y1+0.029Y2-0.030Y3+0.099Y4Z=6.872673+0.608970t-0.073632t2+0.006039t3

(1)

借助公式(1)，通過多元指標(biāo)Z的變化規(guī)律，可為貯藏過程中的優(yōu)化提供有價值的依據(jù)，用于水蜜桃采摘后貯藏過程中成熟度變化的預(yù)測和監(jiān)控。 在20℃恒溫貯藏下，計算得到不同成熟度所需分配時間的范圍，如表2所示。

表2 各成熟度對應(yīng)的分配時間

3 帶時間窗的車輛路徑問題的模型建立

3.1 問題描述

在生鮮農(nóng)產(chǎn)品(水蜜桃)的配送中,需要經(jīng)過生產(chǎn)加工，儲存運輸?shù)拳h(huán)節(jié)才能交付到消費者手中。早期時候農(nóng)產(chǎn)品運輸條件簡陋,路徑規(guī)劃不合理，導(dǎo)致運輸過程中大量農(nóng)產(chǎn)品腐爛、變質(zhì),不能在客戶規(guī)定的時間段內(nèi)把貨品送至客戶點。既給企業(yè)帶來了一定的經(jīng)濟損失，又影響顧客體驗。

為了盡可能地提升客戶的服務(wù)質(zhì)量和滿足配送的時效性，降低生鮮配送成本，則需要對配送車輛行駛路徑和時間進行合理規(guī)劃。從成熟度模型(1)中可以得到將不同成熟度的水蜜桃送到消費者手中所對應(yīng)的時間窗約束，從而可以得到配送所需的時間。

本文以某地域的水蜜桃配送服務(wù)情況為研究對象。某個配送中心統(tǒng)一安排車輛對區(qū)域內(nèi)的多個配送點提供配送服務(wù)，完成任務(wù)后返回配送中心，客戶信息已知，但是客戶對收到的水蜜桃有成熟度要求，配送車輛送達的水蜜桃必須滿足顧客所需的成熟度，又由于水蜜桃極易腐爛的特性，所以，客戶所需求的成熟度對應(yīng)的時間窗為硬時間窗。在滿足一些假設(shè)的情況下，對配送路徑進行合理規(guī)劃，因為生鮮配送更強調(diào)時效性，所以，以車輛行駛總路程最小為目標(biāo)函數(shù)。

3.2 基本假設(shè)

考慮到該地域的實際業(yè)務(wù)關(guān)系和生鮮配送行業(yè)的特點，為了完成規(guī)定的配送任務(wù)，將帶時間窗的生鮮配送問題轉(zhuǎn)換為數(shù)學(xué)模型，現(xiàn)在做出如下假設(shè)：

①單一配送中心，所有的配送車輛均由運輸中心發(fā)出，結(jié)束配送任務(wù)后都返回配送中心。

②每輛車只能服務(wù)一條路線，每個客戶有且只有一輛車提供配送服務(wù)，不可以一輛車服務(wù)多次或者由多輛車來服務(wù)同一個需求點。

③車輛提供的配送服務(wù)時間需要在規(guī)定的時間窗[ETi,LTi]范圍內(nèi)。

④所有客戶的位置坐標(biāo)，需求量，時間窗等都已知且相互獨立。

⑤配送中心到各客戶的距離已知，各客戶間的距離已知。

⑥每個車輛的限載量相同且已知，車輛配送過程中的載重量不可超過限載量。

⑦貨物恒溫運輸，其品質(zhì)只與運輸時間相關(guān)。

3.3 參數(shù)定義

表3 參數(shù)定義

3.4 數(shù)學(xué)模型

(2)

(3)

(4)

Rk={rki|rki∈{1,2,…,w},i=1,2,…,nk}

(5)

Rk1∩Rk2=Φ,?k1≠?k2

(6)

Ski=Srk(i-1)+trk(i-1)rki+trk(i-1)

(7)

ti=Max{ETi-Si,0},i=1,2,…,W

(8)

Si≤LTi(i=1,2,…,W)

(9)

(10)

式(2)為目標(biāo)函數(shù)，表示車輛配送的總路徑最小。

式(3)表示每輛車的載重要在車輛的限載范圍內(nèi)。

式(4)表示k臺配送車輛所配送的客戶總數(shù)與需求的客戶數(shù)相等，即表示所有的客戶都獲得了配送服務(wù)。

式(5)表示每條線路的客戶組成。其中rki表示客戶rki由k號配送車輛的配送順序為i(rk0表示配送中心)。

式(6)表示每個客戶點只能由一臺配送車輛提供配送服務(wù)。

式(7)表示每條配送路徑上，車輛到達下一個客戶點rki的時刻等于當(dāng)前到達K客戶rk(i-1)的時刻Srk(i-1)，在此客戶點的等待時間tk(i-1)和到達下一客戶點rki所花行駛時間三者之和。

式(8)表示等待時間非負。

式(9)表示配送車輛必須在客戶結(jié)束時間窗LTi之前完成配送任務(wù)。

式(10)表示如果第k輛車服務(wù)的客戶數(shù)≥1時，說明該輛車參與了配送。反之，則未參與配送。

4 基于遺傳算法的帶時間窗的車輛路徑問題的模型求解

4.1 染色體編碼與解碼

在遺傳算法中，人們經(jīng)常使用的染色體編碼方式有自然數(shù)編碼和二進制編碼。結(jié)合處理問題的實際情況和本文中的帶時間窗的農(nóng)產(chǎn)品配送路徑模型，明顯可得，采取自然數(shù)編碼的方式可以有效求解這一基于次序的組合優(yōu)化模型，避免出現(xiàn)無效解的情況，具體采用自然數(shù)編碼的操作如下：

假設(shè)運輸網(wǎng)絡(luò)中有W個客戶，配送中心有K輛配送車輛，rki表示第k輛車服務(wù)第i個客戶，0表示配送中心。車輛從配送中心出發(fā)，完成對客戶點的配送任務(wù)后，最后回到配送中心，最終形成長度為W+K+1的染色體，染色體編碼串可表示為(0,r11,r12,…,r1t,0,r21,r22,…,r2n,0,…,0,r31,r32,…,r3s,0)，每條染色體反映的是車輛的配送路徑即代表一個候選解。其中相鄰的兩個0之間表示一個子路徑，子路徑的內(nèi)部順序不可更改，子路徑與子路徑之間的順序可以更改。以染色體編碼串{0157024308690}為例：表示3輛車對9個客戶點進行服務(wù)，解碼后的3條子路徑為：子路徑(1)：0-1-5-7-0；子路徑(2)：0-2-4-3-0；子路徑(3)：0-8-6-9-0。

4.2 生成初始種群

遺傳算法的最優(yōu)解對初始群體的要求并不是很高，且為了減少算法陷入局部最優(yōu)的情況，本文采取隨機方式產(chǎn)生初始種群。隨機選取W個客戶點，根據(jù)服務(wù)的時間窗約束和車輛的最大載重約束，將K+1個0插入染色體中，形成(0,r11,r12,…,r1t,0,r21,r22,…,r2n,0,…,0,r31,r32,…,r3s,0)，如此反復(fù)至形成N條染色體，即生成種群規(guī)模為N的初始種群。

4.3 適應(yīng)度函數(shù)

適應(yīng)度函數(shù)是對目標(biāo)函數(shù)的評價，其取值是選擇下一代的標(biāo)準，適應(yīng)度值的大小和被選擇的幾率成正比。本文構(gòu)建的是以總距離最短為目標(biāo)的組合優(yōu)化模型，這就要求進行函數(shù)轉(zhuǎn)化。所以，將目標(biāo)函數(shù)的倒數(shù)設(shè)置成適應(yīng)度函數(shù)，設(shè)計的適應(yīng)度函數(shù)為：fi=1/zi，zi表示第i個體的目標(biāo)函數(shù)值。

4.4 選擇算子

本文的選擇操作采取混合選擇機制，使得上一種群中的優(yōu)良個體大概率地被選擇成為優(yōu)良父代進行繁衍。具體操作步驟如下：

步驟1：計算種群中個體的適應(yīng)度，對適應(yīng)度函數(shù)值進行從小到大排序，其中，前M個(設(shè)為種群規(guī)模的50%)個體直接進入下一代。

步驟2：剩下的個體通過輪盤賭法進行篩選。

④以[0,1]之間的隨機數(shù)α模擬輪盤指針，若α≤qi，則選擇個體1；否則，選擇個體i。

步驟3：重復(fù)步驟2，直到得到N-M個個體。

4.5 交叉操作

為了避免交叉操作破壞過多優(yōu)良基因，在一定程度上保持種群的多樣性，同時，也為了能在最大范圍內(nèi)進行搜索最優(yōu)解，降低算法陷入局部最優(yōu)的可能，本文采用部分匹配交叉法(PMX)。具體操作為：在染色體上隨機產(chǎn)生兩個位串交叉點，對兩個個體的位串交叉點之間的部分進行交叉操作。下面以兩個父代個體A(321654987)和B(147258369)舉例說明。

A：3 21 6 5 49 8 7 B：1 47 2 5 83 6 9

對方基因串位置前置自身染色體最前端

A’：7 2 5 83 2 1 6 5 4 9 8 7 B’：1 6 5 41 4 7 2 5 8 3 6 9

去掉與前端基因相同的基因片段，得到子代

A1：7 2 5 8 3 1 6 4 9 B1：1 6 5 4 7 2 8 3 9

4.6 變異操作

為了保持種群多樣性，將父代優(yōu)秀的基因遺傳到下一代，本文采取對換變異的變異方式。具體操作：隨機選中一條染色體，在其上隨機產(chǎn)生兩個非0的自然數(shù)r1,r2,(r1,r2≠0)，然后交換r1,r2的基因。例如：r1=1，r2=4;A：3 216 549 8 7 ，變異后為，A’：3 246 519 8 7。

4.7 算法終止條件

當(dāng)?shù)螖?shù)達到預(yù)設(shè)次數(shù)時或者算法中的某一結(jié)果出現(xiàn)多次時，運算終止并輸出最優(yōu)解。

5 案例分析

某配送中心rk0，坐標(biāo)為(4.6，5.5)(單位：100km)。該配送中心擁有5輛配送車輛，每輛車的載重量為25t，平均速度為40km/h，運輸溫度是20°攝氏度?？偣卜?wù)20位客戶，每個客戶所需的數(shù)量(單位：t)，所需的服務(wù)時間窗[ETi，LTi](H)和坐標(biāo)位置見表4。通過設(shè)計的遺傳算法獲得適當(dāng)?shù)穆肪€，以滿足客戶的時間需求和車輛的最短里程。

表4 客戶相關(guān)數(shù)據(jù)

初始參數(shù)定義如下：種群規(guī)模N=100,最大迭代次數(shù)C=500,交叉概率為0.8，變異概率為0.1，運用MATLAB軟件實現(xiàn)。得到最優(yōu)配送路徑軌跡圖示意圖(圖2)和最優(yōu)里程迭代圖(圖3)。

圖2 最優(yōu)配送路徑軌跡圖示意圖

圖3 最優(yōu)里程迭代圖

本文的遺傳算法的結(jié)果表明該算例中需要用到4輛配送車輛，對應(yīng)最優(yōu)的配送路線為：

路線1：3→16→8→13→4

路線2：18→17→15→20→7

路線3：14→9→6→19→5→10

路線4：11→1→12→2

6 結(jié)語

本文從現(xiàn)實生活中水蜜桃配送過程中面臨的問題出發(fā)，在建立蜜桃采摘后的成熟度變化的數(shù)學(xué)模型的基礎(chǔ)上，再構(gòu)建硬時間窗的車輛路徑規(guī)劃的數(shù)學(xué)模型，最后，通過遺傳算法求解。通過將成熟度模型和配送路徑模型進行聯(lián)合優(yōu)化，大大減少了水蜜桃配送過程中的浪費損耗，節(jié)約了運輸資源，最大程度地滿足了客戶的需求，對解決類似的采摘后成熟的生鮮配送問題有一定的參考意義。