帶客戶分級和需求可拆分的生鮮車輛路徑問題

夏揚坤，鄧永東，龐 燕+，王忠偉，高 亮

(1.中南林業(yè)科技大學(xué) 物流與交通學(xué)院，湖南 長沙 410004;2.華中科技大學(xué) 數(shù)字制造裝備與技術(shù)國家重點實驗室，湖北 武漢 430074)

0 引言

生鮮農(nóng)產(chǎn)品如蔬菜、水果、肉類及水產(chǎn)品等作為生活必須品，已成為當(dāng)下民生領(lǐng)域的關(guān)注焦點[1]。與歐美發(fā)達(dá)國家相比，我國生鮮農(nóng)產(chǎn)品實際物流運作水平整體相對落后，依舊以傳統(tǒng)粗放型物流配送方式為主。車輛路徑問題[1](Vehicle Routing Problem, VRP)是物流配送的核心環(huán)節(jié)，采用現(xiàn)代智能優(yōu)化技術(shù)對生鮮農(nóng)產(chǎn)品物流配送路徑優(yōu)化[2]進(jìn)行研究，對于提高物流配送效率[3]、降低配送成本[4]等均具有重要意義。如文獻(xiàn)[1-10]對生鮮VRP(Fresh VRP, FVRP)進(jìn)行了相關(guān)研究，從這些研究可知：FVRP與一般VRP有著明顯的不同，生鮮農(nóng)產(chǎn)品具有易腐蝕、高損耗等特點，其生鮮度會隨著配送時間的推移而降低，因此配送具有時間依賴性。在生鮮農(nóng)產(chǎn)品物流配送中應(yīng)該考慮生鮮損耗費用，在權(quán)衡配送成本的同時考慮降低生鮮損耗。

現(xiàn)代生鮮物流市場競爭激烈，配送企業(yè)要想在激烈的市場競爭中立于不敗之地，就必須保證一定的優(yōu)質(zhì)客戶資源，協(xié)調(diào)處理好客戶關(guān)系維護(hù)問題[11-12]。文獻(xiàn)[13-15]在研究帶軟時間窗的VRP(VRP with Soft Time Windows, VRPSTW)時，對考慮客戶滿意度的VRP(VRP with Customer Satisfaction, VRPCS)進(jìn)行了探討，研究認(rèn)為，在VRPSTW模型中考慮客戶滿意度因素有利于提升配送企業(yè)的服務(wù)質(zhì)量，促進(jìn)企業(yè)可持續(xù)發(fā)展。當(dāng)配送資源受限時，對客戶實施分級處理，優(yōu)先考慮重要客戶的服務(wù)要求，更有利于配送企業(yè)維護(hù)好優(yōu)質(zhì)客戶資源。在物流配送實踐中，配送企業(yè)的大訂單資源通常來自于少數(shù)重要客戶，這些少數(shù)客戶常能占據(jù)配送企業(yè)80%以上的年度業(yè)務(wù)量，有時一個大客戶企業(yè)的年度訂單收益完全可以超越上百個小客戶的總和，而且針對少數(shù)重要客戶進(jìn)行戰(zhàn)略合作，在單位業(yè)務(wù)收益的客戶關(guān)系維護(hù)時間成本方面也更為節(jié)約?？紤]到VRPSTW容易降低客戶滿意度，而配送企業(yè)在提供配送服務(wù)時必然需要權(quán)衡成本與收益，因此在能夠界定客戶重要性的情況下，配送企業(yè)可以對客戶的重要性進(jìn)行分級處理，優(yōu)先滿足重要客戶的期望時間窗。通過增大重要客戶的時間窗偏離量懲罰程度，引導(dǎo)算法求解時盡可能地優(yōu)先滿足重要客戶的時間窗，形成一個考慮客戶分級的VRPSTW(VRPSTW with Customer Classification, VRPSTWCC)。

需求可拆分VRPSTW[16](VRPSTW with Split Deliveries, VRPSTWSD)是VRPTW的一個新研究方向，對客戶需求進(jìn)行合理的拆分配送能夠提高車輛裝載率，降低物流配送成本。在以往的VRPSTWSD研究中，常假設(shè)客戶需求量可按照計量單位來連續(xù)單元化拆分，對需求離散拆分的VRPSTWSD(VRPSTW with Discrete Split Deliveries, VRPSTWDSD)的研究很少。但在連鎖超市配送、快遞配送等過程中，為了方便裝卸作業(yè)，配送企業(yè)通常會將客戶的訂單需求按照一定的特性劃分來打包裝箱，而且不同產(chǎn)品的裝箱量通常是有差異的，農(nóng)產(chǎn)品一旦進(jìn)行打包作業(yè)形成了“背包”，則很難再對單個背包重新拆分組裝，若拆分則只可能依“背包”進(jìn)行拆。在多品種生鮮農(nóng)產(chǎn)品配送實踐中，每個客戶點可能有多種生鮮農(nóng)產(chǎn)品品種需求，且每一種農(nóng)產(chǎn)品的需求量可能不同，一般同種產(chǎn)品不適合拆分送達(dá)，若將單種農(nóng)產(chǎn)品的需求量看成一個不可再拆分的“背包”，則客戶需求可視為由多個背包離散組合而成。本文將“背包”定義為“不可進(jìn)一步拆分的客戶需求量的最小集合”，將結(jié)合客戶需求依背包拆分的特點，對客戶點與背包施行統(tǒng)一操作，針對客戶點與背包都設(shè)計相應(yīng)的鄰域操作算子，盡可能地降低由于需求拆分引發(fā)的求解難度。

VRP是NP-hard問題，當(dāng)VRP中需求可拆分時求解難度會更大，大規(guī)模問題適合采用啟發(fā)式算法進(jìn)行求解。由于一般的經(jīng)典啟發(fā)式算法不具備全局尋優(yōu)能力，學(xué)者們通常采用智能優(yōu)化算法進(jìn)行求解[17]。禁忌搜索(Tabu Search, TS)算法[18-19]是一種模仿人類智能思維的智能優(yōu)化算法，其鄰域搜索能力較強，可以使用短期禁忌表來記憶相應(yīng)的禁忌信息，避免搜索重復(fù)的解決方案，提升搜索效率。從已有的VRP文獻(xiàn)[20-21]來看，TS算法具有簡單性、易操作性、適應(yīng)性、高效性等優(yōu)點，是一種求解VRP的高效智能優(yōu)化算法。因此，本文也以TS算法為框架來設(shè)計改進(jìn)算法。

目前，學(xué)術(shù)界針對需求依背包拆分VRPSTW(VRPSTW with Split Deliveries by Backpack, VRPSTWSDB)的研究較為少見，而對于帶客戶分級和生鮮損耗費用的VRPSTWSDB(VRPSTWSDB with Customer Classification and Fresh Loss Cost, VRPSTWSDBCCFLC)的公開報道文獻(xiàn)尚未見到。因此，本文對VRPSTWSDBCCFLC這類新的問題類型進(jìn)行研究，并設(shè)計一個帶動態(tài)禁忌表的自適應(yīng)禁忌搜索算法(Adaptive Tabu Search Algorithm with Dynamic Linear Tabu List, ATSA-DLTL)進(jìn)行求解。

1 數(shù)學(xué)模型構(gòu)建

1.1 問題描述

本文對VRPSTWSDBCCFLC進(jìn)行研究，具體可描述為：配送中心使用一定數(shù)目的車輛對各客戶進(jìn)行生鮮農(nóng)產(chǎn)品配送后返回出發(fā)點，需要求得一組合理的車輛配送路線，并最小化車輛使用數(shù)量、行駛時間、生鮮損耗、等待時間及時間窗偏離量等對應(yīng)的費用。其中，車輛不許超載，每個客戶點的生鮮農(nóng)產(chǎn)品需求量必須滿足，客戶需求若拆分則只能依背包來離散拆分配送，配送中心點i=0的硬時間窗約束[0,Tmax]不許違反。另外，每個客戶點i∈V′的期望時間窗[ai,bi]可通過施行懲罰來實現(xiàn)軟時間窗，軟時間窗的處理方式為：早到需等待至?xí)r間窗開啟再進(jìn)行卸貨作業(yè)并需要支付等待費用，遲到則可以立即進(jìn)行卸貨作業(yè)并需要支付懲罰費用。

在生鮮農(nóng)產(chǎn)品物流配送中，客戶的需求位置分布具有分散性，需求時間也具有差異性。如在城市生鮮農(nóng)產(chǎn)品物流配送中，一個農(nóng)產(chǎn)品生產(chǎn)基地(如城市蔬菜生產(chǎn)基地)每天都要為眾多生鮮農(nóng)產(chǎn)品需求點(客戶點)進(jìn)行供貨，這些客戶通常分布于城市的各個街道小區(qū)內(nèi)，位置非常分散，配送網(wǎng)絡(luò)龐大且每個客戶點都會根據(jù)自身情況而提出不同的期望時間窗，其路徑優(yōu)化難度很大。為了簡化問題，本文將生鮮農(nóng)產(chǎn)品物流網(wǎng)絡(luò)抽象為一個連通圖，假設(shè)各點之間均可互通，點之間的行駛時間符合三角不等式，忽略天氣、交通堵塞等其他因素帶來的影響。為了方便模型描述，定義VRPSTWSDBCCFLC的數(shù)學(xué)模型的符號，如表1所示。

表1 VRPSTWSDBCCFLC數(shù)學(xué)模型的符號定義

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

(1)

(2)

(3)

配送系統(tǒng)的生鮮損耗費用Z4，

(4)

另外，VRPSTWSDBCCFLC模型中需對客戶的重要性進(jìn)行分級，不同級別的客戶，其單位時間窗偏離量的費用ci不同，重要客戶對應(yīng)的ci值應(yīng)該更大，即盡可能地保證重要客戶的期望時間窗。結(jié)合帕累托定律[17]，約定客戶群中含有20%的重要客戶(當(dāng)0.2N非整數(shù)時則將重要客戶的數(shù)目向上取整為?0.2N?)。

綜上所述，結(jié)合以往帶時間窗VRP相關(guān)模型[22-24]，本文給出VRPSTWSDBCCFLC的雙目標(biāo)數(shù)學(xué)模型如下：

minG(y)=p1K+p2Z。

(5)

Z=Z1+Z2+Z3+Z4，

(6)

(7)

(8)

(9)

(10)

s.t.

(11)

(12)

(13)

(14)

(15)

(16)

(17)

(18)

(19)

(20)

(21)

(22)

(23)

(24)

(25)

(26)

(27)

(28)

式(5)表示雙目標(biāo)函數(shù)，其中參數(shù)p1與p2為定性概念，只表示權(quán)重p1》p2，即第一目標(biāo)“最小化車輛數(shù)”相對于第二目標(biāo)“最小化行駛費用”具有絕對優(yōu)先權(quán);式(6)表示行駛費用(在行駛過程中引發(fā)的費用);式(7)表示行駛時間費用;式(8)表示因早到等待引發(fā)的時間窗偏離量費用;式(9)表示因遲到立即服務(wù)引發(fā)的時間窗偏離量費用;式(10)表示配送系統(tǒng)的生鮮損耗費用。式(11)為車輛的裝載能力限制;式(12)為配送中心的硬時間窗限制;式(13)為車輛k在點i的等待時間;式(14)表示車輛k到達(dá)點j的時刻;式(15)～式(19)表示各客戶的需求量必須全部滿足，客戶點的需求可拆分，但單個背包量不可再拆，即客戶需求只能通過依背包離散拆分來實現(xiàn)分批多次配送;式(20)～式(21)為各頂點進(jìn)出車輛流平衡約束;式(22)～式(23)表示全部車輛從配送中心出發(fā)后最終都返回原出發(fā)點;式(24)可消去子回路;式(25)可用于估算車輛數(shù)的下界;式(26)～式(28)為變量的取值范圍。

2 禁忌搜索算法設(shè)計

基本TS算法[22]前期具有較強的禁忌能力和尋優(yōu)速度，但在中后期容易因禁忌過度而難以搜索到更好解。基本TS算法對多約束多極值的NP-hard問題易陷入局部最優(yōu)，一般需在算法中設(shè)計一些有效的禁忌策略和鄰域搜索策略來增強尋優(yōu)能力。本文在基本TS算法基礎(chǔ)上，構(gòu)建一個動態(tài)禁忌表，設(shè)計一個多鄰域結(jié)構(gòu)體，嵌入自適應(yīng)懲罰機(jī)制，采用禁忌表重新初始化等策略來增強其自適應(yīng)尋優(yōu)能力，從而形成了一個ATSA-DLTL進(jìn)行求解。

為方便算法描述，定義相關(guān)符號，如表2所示。

表2 ATSA-DLTL的相關(guān)符號定義

2.1 解的表示與初始解

采用“最近0法”來生成初始解，可行初始解的具體生成方式為：在車輛裝載能力Q和路線的最長工作時間Tmax約束下，按照各客戶點到配送中心點0的距離依次將客戶的背包加入車輛路線中，約定初始解不考慮拆分，即初始解中同一點的背包均添入同一車輛路線。

2.2 解的評價設(shè)計

ATSA-DLTL取總的評價函數(shù)G如式(29)所示：

G=p1K+p2F。

(29)

式中參數(shù)p1與p2只表示兩個目標(biāo)的權(quán)重p1》p2。

行駛費用評價函數(shù)F如式(30)所示：

F=Z+Z′。

(30)

式中Z′表示違反約束最長工作時間Tmax限制的懲罰費用。

文獻(xiàn)[22]指出，接受部分違反約束的鄰域解有利于算法對鄰域進(jìn)行充分搜索，也有利于算法從不可行的當(dāng)前解過渡到更好的可行解。但若是對不可行解接受過度，則容易產(chǎn)生大量的不可行解，反而不利于尋優(yōu)進(jìn)程。因此，為了在不可行解與可行解之間尋找到一個較好的平衡，ATSA-DLTL對不可行解的接受范圍進(jìn)行控制，約定候選解(當(dāng)前解是從候選解中挑選出來的)不能違反載重約束，即候選解只能接受部分違反最長工作時間Tmax限制的鄰域解，懲罰值Z′如式(31)所示：

(31)

式中：δk為第k條路線的工作時間超出量;H為一自適應(yīng)懲罰系數(shù)。

ATSA-DLTL對H的取值方式進(jìn)行調(diào)整，具體如下：

記Λ1與Λ2為整型計數(shù)變量，且Λ1,Λ2∈[0,15]，初值都取為0。在接連迭代過程中，每次當(dāng)選出的“當(dāng)前解”Snow為不可行解時，便讓Λ1加1，否則讓Λ2加1，若Λ1或Λ2取值超出范圍[0,15]，則設(shè)為0。參數(shù)H可引導(dǎo)算法的搜索方向。H代表超出最長工作時間Tmax限制的自適應(yīng)懲罰權(quán)重系數(shù)，通過實驗將取值范圍限定為H∈[5,1 000]，H的初值取為5，當(dāng)超出范圍時取最小值；當(dāng)Λ1=15時，將H乘以δ；當(dāng)Λ2=15時，則將H除以δ，δ的取值如式(32)所示：

δ=2+rand()。

(32)

根據(jù)以上規(guī)定，記Hθ為第θ次迭代中H的取值，則當(dāng)H值發(fā)生變化時，其第(θ+1)次迭代的取值Hθ+1如式(33)所示：

(33)

式(32)中的δ為H設(shè)置的一個隨機(jī)伸縮變換系數(shù)，其中rand()為區(qū)間[0,1]內(nèi)的隨機(jī)數(shù)。ATSA-DLTL在自適應(yīng)參數(shù)H內(nèi)引入隨機(jī)數(shù)δ，可使H的取值具有多樣性，增強對鄰域的擾動，有利于新解的豐富性，引導(dǎo)算法在可行解與不可行解之間自適應(yīng)地變換，提升ATSA-DLTL的全局尋優(yōu)能力。

2.3 解改進(jìn)策略設(shè)計

本節(jié)取鄰域解的數(shù)目上限為P=60+N(對應(yīng)了鄰域搜索終止條件)，采用一種“解改進(jìn)”策略來挑選“最好解”Sbest與“當(dāng)前解”Snow，以加速算法尋優(yōu)進(jìn)程。結(jié)合兩級評價指標(biāo)K與F分層來評價優(yōu)化解，在鄰域解的生成過程中，若某個“可行候選解”Sfeasible比“最好解”Sbest更優(yōu)，即當(dāng)滿足“K(Sfeasible)

若在鄰域搜索中不存在“可行候選解”Sfeasible優(yōu)于原“最好解”Sbest，則Sbest保持不變，只需挑選新的Snow。由于部分候選解可能被禁忌，此處Snow分兩種情況進(jìn)行挑選：若存在“非禁忌候選解”Snon-tabu，則挑選出“最佳非禁忌候選解”#Snon-tabu，并將其設(shè)定為新Snow；若全部候選解都被禁忌，則挑選出“最佳候選解”#Scandidate，并釋放該#Scandidate(即消去其禁忌)，同時將此#Scandidate設(shè)為新Snow。這里#Snon-tabu、#Scandidate都是結(jié)合兩級評價指標(biāo)K與F分層挑選，不再贅述。

2.4 多鄰域結(jié)構(gòu)體設(shè)計

2.3 PRMDR設(shè)計

ATSA-DLTL設(shè)計“最長工作時間路線擾動規(guī)則”(PRMDR)來輔助挑選兩相異路線R1與R2，PRMDR含有的一個顯著特點為“最長工作時間路線超限必選”策略，此舉可以較好地配合ATS-DLTL算法的自適應(yīng)懲罰機(jī)制，盡可能地減少對無效解集的搜索。具體的路線挑選方式為：當(dāng)最長工作時間路線(R*)的長度值T(R*)=max(Tk)>Tmax時，令R1=R*，然后在其余路線內(nèi)再隨機(jī)挑選出一條作為路線R2；當(dāng)R*的長度值T(R*)=max(Tk)≤Tmax時，便仍采用隨機(jī)方式挑選出兩條相異路線R1與R2。

2.4 動態(tài)線性禁忌表設(shè)計

以往的TS算法[22]常采用N×N階的方陣禁忌表，但方陣禁忌表禁忌容量過大，雖在迭代前期能夠加速算法尋優(yōu)，但隨著迭代次數(shù)的增加，容易造成對優(yōu)良候選解的禁忌過度。

本文ATSA-DLTL設(shè)計一個動態(tài)禁忌表(Dynamic Linear Tabu List, DLTL)，大小取為l×3階動態(tài)線性表，以鄰域交換中的客戶點對(i,j)為禁忌對象。其中：第1,2列存儲鄰域操作的客戶點對(i,j);第3列則存儲對應(yīng)的禁忌長度值ζ。當(dāng)客戶點對(i,j)所對應(yīng)的候選解被選擇為下次迭代的“當(dāng)前解”時，就在禁忌表的對應(yīng)位置填入禁忌信息，約定禁忌長度ζ每次迭代都可取5～16之間的隨機(jī)整數(shù)。規(guī)定禁忌對象每次迭代后都要將禁忌長度減1，直到降為0才可解禁。ATSA-DLTL允許禁忌表的長度l隨迭代而動態(tài)取值，將其長度l取值為：在迭代的前Nu0步以內(nèi)取為N，在Nu0步后每隔u次迭代，就使l在區(qū)間[5+N/20,5+N/10]內(nèi)取隨機(jī)整數(shù)值。

另外，增設(shè)一定的重新初始化策略，以增強算法的尋優(yōu)能力。ATSA-DLTL再設(shè)計一個“禁忌表重新初始化”策略，約定在迭代Nu0步以后，每隔u次迭代就重新初始化禁忌表。本文取Nu0=500+10N，u=40。

2.5 迭代終止條件

ATSA-DLTL共含有3個迭代的終止條件，約定只要滿足條件之一便使算法終止迭代，具體為：①當(dāng)“實際總迭代次數(shù)”Mu1達(dá)到預(yù)設(shè)的上限值Nu1;②當(dāng)“最好解”保持連續(xù)不變的迭代次數(shù)Mu2達(dá)到預(yù)設(shè)的上限值Nu2;③當(dāng)計算機(jī)CPU的運行時間Mu3達(dá)到預(yù)設(shè)的上限值Nu3。經(jīng)綜合考慮，ATSA-DLTL取Nu1=4 000+80N，Nu2=3 000+5N，Nu3=600+12N。

2.6 算法流程圖

ATSA-DLTL的基本算法流程如圖1所示。

3 算法測試

3.1 算例描述

本文使用MATLAB 2014a進(jìn)行編程，并且在LENOVO?V3000，CUP為2.40 GHz，內(nèi)存為4 GB的AMD筆記本上測試ATSA-DLTL。目前，尚無VRPSTWSDBCCFLC的研究文獻(xiàn)，自然也沒有對應(yīng)的標(biāo)準(zhǔn)測試算例。以往學(xué)者們常采用Solomn算例[22-24]作為標(biāo)準(zhǔn)算例來求解VRPTW，本文以含N=100個客戶點的Solomn算例[21-23]來構(gòu)建VRPSTWSDBCCFLC的相應(yīng)算例。根據(jù)Solomn算例的數(shù)據(jù)特點，以點間的歐氏距離代表點間的行駛時間。結(jié)合帕累托定律[17]，從算例中挑選出20%的客戶作為重要客戶，為方便描述，直接將原始算例中前20%的客戶作為重要客戶，取前20個客戶的ci=0.5(1≤i≤20)，后續(xù)客戶的ci=0.1(21≤i≤100)。另外，將客戶需求量隨機(jī)拆分為1～4個背包量(R=4)并固定下來，由此便可得到所需要的算例。本文以其中的算例R111為例進(jìn)行VRPSTWSDBCCFLC測試分析。

3.2 求解結(jié)果分析

(1)VRPSTWSDBCCFLC求解結(jié)果

以Solomn算例中的R111為例來進(jìn)行VRPSTWSDBCCFLC類型測試分析，測試平臺不變，對算例R111進(jìn)行5次測試，并記錄相關(guān)結(jié)果。采用“最近0”法求得的“初始解”Sinitial結(jié)果如表3，由于“最近0”法每次求得的“初始解”(可視為原始人工計劃方案)都一樣，因此本文只給出一次測試結(jié)果。以ATSA-DLTL對“最近0”法得到的“初始解”進(jìn)行優(yōu)化，求得的“最好解”Sbest結(jié)果如表4。

表3 “最近0”法求得的“初始解”結(jié)果

表4 ATSA-DLTL求得的“最好解”結(jié)果

(2)計算結(jié)果分析

1)整體費用指標(biāo)的改進(jìn)效果分析。

以VRPSTWSDBCCFLC類型為例，對求得的“最好解”與“初始解”稍作比較分析。ATSA-DLTL以“最近0”法求得的“初始解”來進(jìn)行深度優(yōu)化，“最近0”法屬于一種經(jīng)典啟發(fā)式算法，簡單易行，便于人工快速規(guī)劃配送路線，但求解效果通常較差。ATSA-DLTL屬于一種智能優(yōu)化算法，現(xiàn)對二者進(jìn)行比較。

表5給出了“最近0”法和ATSA-DLTL的相關(guān)均值的對比結(jié)果。從表5中可以明顯發(fā)現(xiàn)，ATSA-DLTL算法相比“最近0”法，其在車輛數(shù)(K)、總行駛費用(Z)、行駛時間費用(Z1)、早到的等待時間費用(Z2)、遲到的時間窗懲罰費用(Z3)及生鮮損耗費用(Z4)等各項指標(biāo)都表現(xiàn)出了絕對的改進(jìn)優(yōu)勢。ATSA-DLTL對“初始解”的改進(jìn)效果十分明顯。

表5 相關(guān)費用指標(biāo)的改進(jìn)結(jié)果

2)考慮客戶分級的效果分析。

由于“最近0”法只是在考慮車輛載重與路線工作時間限制的情況下，按照距離點0的遠(yuǎn)近來構(gòu)建初始方案(初始解)。因此，不論配送企業(yè)[28]是否對客戶進(jìn)行分級處理，初始解都不會優(yōu)先考慮滿足重要客戶的時間窗。由表3與表4可知，在“初始解”Sinitial中有β1(Sinitial)<β(Sinitial)<β2(Sinitial)，重要客戶的時間窗滿足率(β1)比全部客戶的時間窗滿足率(β)和非重要客戶的時間窗滿足率(β2)都要低。

雖然初始解中沒有考慮優(yōu)先滿足重要客戶的時間窗，但經(jīng)過ATSA-DLTL優(yōu)化后，在各次測試求得的“最好解”結(jié)果中有β1(Sbest)>β(Sbest)>β2(Sbest)，即重要客戶的時間窗滿足率(β1)成為了最高的?？梢姡谇蠼馑惴ㄖ锌紤]客戶分級，可以引導(dǎo)算法盡可能地優(yōu)先滿足重要客戶的時間窗。另外，在“最好解”中，不僅重要客戶的時間窗滿足率(β1)得到了提高，全部客戶的時間窗滿足率(β)和非重要客戶的時間窗滿足率(β2)也都得到了提高，說明ATSA-DLTL相比“最近0”法在減少配送成本的同時還能提升整個配送系統(tǒng)的客戶滿意度。本文的VRPSTWSDBCCFLC模型確實有助于在提升重要客戶滿意度的同時綜合優(yōu)化配送成本。Sbest相對于Sinitial在時間窗滿足率上的改進(jìn)程度如表6所示。

表6 相關(guān)時間窗滿足率的改進(jìn)結(jié)果

3)考慮生鮮損耗費用的效果分析。

表7 相關(guān)生鮮指標(biāo)的改進(jìn)結(jié)果

3.3 文獻(xiàn)對比分析

雖然目前尚未有VRPSTWSDBCCFLC類型的研究文獻(xiàn)，但符卓等[22]對需求依訂單拆分的VRPSTW(VRPSTW with Split Deliveries by Order，VRPSTWSDO)進(jìn)行了研究，若將其文中的訂單當(dāng)成本文的背包，則其相當(dāng)于研究了一種需要依背包拆分的VRPSTW(VRPSTWSDB)。因此，為了進(jìn)一步說明本文ATSA-DLTL的優(yōu)化性能，采用VRPSTWSDB類型作為文獻(xiàn)對比分析。在利用VRPSTWSDBCCFLC模型求解VRPSTWSDB時，統(tǒng)一全部客戶的重要性，并在行駛費用中去掉生鮮損耗費，即在采用ATSA-DLTL求解時，令全部ci=0.1(1≤i≤100)且Z4=0。

符卓等[22]設(shè)計了一個禁忌搜索(TS)算法，并采用含100個客戶點的Solomn算例進(jìn)行了測試，其在對C1類算例(文獻(xiàn)[22]只給出了7個算例的結(jié)果)的測試結(jié)果中求得了滿足時間窗的結(jié)果。本文也采用C1類型算例(含C101～C109共計9個算例)對VRPSTWSDB進(jìn)行測試分析，每個算例測試5次，取最好結(jié)果。雖然測試的是VRPSTWSDB類型，但計算結(jié)果顯示，本文ATSA-DLTL在對C1類型的求解結(jié)果中都獲得了滿足硬時間窗的結(jié)果(即9個算例都求得了β=100%)，該結(jié)果可與符卓等[22]的結(jié)果進(jìn)行直接比較分析。另外，Belfiore等[23]和Shi等[24]分別采用分散搜索(Scatter Search, SS)和混合遺傳算法(Hybrid Genetic Algorithm, HGA)對帶硬時間窗的VRP(VRPHTW)進(jìn)行了測試，其對C1類算例的測試結(jié)果也可與本文結(jié)果進(jìn)行間接對比分析。各算法車輛數(shù)的對比結(jié)果如表8所示，距離值的對比結(jié)果如表9所示。

表8 K值的對比結(jié)果

表9 距離值的對比結(jié)果

續(xù)表9

由表8和表9結(jié)果可知，本文ATSA-DLTL的求解結(jié)果已達(dá)到或接近目前世界已知的最好結(jié)果。在車輛數(shù)方面，ATSA-DLTL與TSA、SS一樣，都求得了最少車輛數(shù)的結(jié)果，比HGA的求解效果要好；在行駛距離方面，ATSA-DLTL都要好于或等于3種對比文獻(xiàn)算法，好于TSA、SS及HGA的算例數(shù)目分別為1、6及4個，算例的平均距離值相對于TSA、SS及HGA分別節(jié)省0.51%、0.73%及0.07%。可見，本文ATSA-DLTL的求解效果優(yōu)于3種對比文獻(xiàn)算法。

4 結(jié)束語

農(nóng)產(chǎn)品具有生鮮屬性，將生鮮損耗費用加入行駛費用目標(biāo)中，有利于降低路途的生鮮損耗，保持生鮮農(nóng)產(chǎn)品的生鮮程度，維護(hù)食品安全。對客戶進(jìn)行分級處理，優(yōu)先滿足重要客戶的時間窗，可提高重要客戶的滿意度，使配送企業(yè)盡可能地保持優(yōu)質(zhì)客戶資源。本文結(jié)合需求依背包拆分條件，將客戶分級思想融入約束，將生鮮損耗費用納入行駛費用目標(biāo)，并以“最小化車輛數(shù)”與“最小化行駛費用”分別為第一與第二目標(biāo)，構(gòu)建了VRPSTWSDBCCFLC的雙目標(biāo)數(shù)學(xué)模型。

以“最近0”法生成初始解，并以ATSA-DLTL進(jìn)行優(yōu)化。測試結(jié)果表明，對客戶實施分級處理，通過增大重要客戶的時間窗偏離系數(shù)，可提高重要客戶的時間窗滿足率。相比“最近0”法得到的初始解，經(jīng)過ATSA-DLTL優(yōu)化后的各項費用指標(biāo)與生鮮損耗指標(biāo)都得到了大幅度下降，而各項時間窗滿足率指標(biāo)則得到了提升。ATSA-DLTL在降低配送成本的同時，還可以降低生鮮農(nóng)產(chǎn)品的生鮮損耗和提升客戶滿意度。可見，在物流配送中并非增大配送投入成本(如增加使用車輛數(shù))就會提高客戶滿意度。更新物流優(yōu)化技術(shù)，采用現(xiàn)代智能優(yōu)化方法對原有配送方案進(jìn)行優(yōu)化，具有非常重要的實踐價值。

隨著電子商務(wù)業(yè)務(wù)和第三方物流配送業(yè)務(wù)的快速發(fā)展，共同配送和協(xié)同配送等已成為配送實踐中急需要解決的問題。后續(xù)，在本文的研究基礎(chǔ)之上，將對共同配送和協(xié)同配送中涉及的需求可拆分半開放式生鮮VRP這一新問題類型進(jìn)行研究，并優(yōu)化算法設(shè)計；在禁忌搜索算法的基礎(chǔ)之上設(shè)計超啟發(fā)式算法進(jìn)行求解，進(jìn)一步改進(jìn)算法的尋優(yōu)性能。