夏揚(yáng)坤，鄧永東，龐 燕+，王忠偉，高 亮

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

0 引言

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

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

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

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

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

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

1.1 問(wèn)題描述

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

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

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

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

(1)

(2)

(3)

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

(4)

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

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

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

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

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

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

2.1 解的表示與初始解

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

2.2 解的評(píng)價(jià)設(shè)計(jì)

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

G=p1K+p2F。

(29)

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

行駛費(fèi)用評(píng)價(jià)函數(shù)F如式(30)所示：

F=Z+Z′。

(30)

式中Z′表示違反約束最長(zhǎng)工作時(shí)間Tmax限制的懲罰費(fèi)用。

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

(31)

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

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

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

δ=2+rand()。

(32)

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

(33)

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

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

本節(jié)取鄰域解的數(shù)目上限為P=60+N(對(duì)應(yīng)了鄰域搜索終止條件)，采用一種“解改進(jìn)”策略來(lái)挑選“最好解”Sbest與“當(dāng)前解”Snow，以加速算法尋優(yōu)進(jìn)程。結(jié)合兩級(jí)評(píng)價(jià)指標(biāo)K與F分層來(lái)評(píng)價(jià)優(yōu)化解，在鄰域解的生成過(guò)程中，若某個(gè)“可行候選解”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(即消去其禁忌)，同時(shí)將此#Scandidate設(shè)為新Snow。這里#Snon-tabu、#Scandidate都是結(jié)合兩級(jí)評(píng)價(jià)指標(biāo)K與F分層挑選，不再贅述。

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

2.3 PRMDR設(shè)計(jì)

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

2.4 動(dòng)態(tài)線性禁忌表設(shè)計(jì)

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

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

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

2.5 迭代終止條件

ATSA-DLTL共含有3個(gè)迭代的終止條件，約定只要滿足條件之一便使算法終止迭代，具體為：①當(dāng)“實(shí)際總迭代次數(shù)”Mu1達(dá)到預(yù)設(shè)的上限值Nu1;②當(dāng)“最好解”保持連續(xù)不變的迭代次數(shù)Mu2達(dá)到預(yù)設(shè)的上限值Nu2;③當(dāng)計(jì)算機(jī)CPU的運(yùn)行時(shí)間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 算法測(cè)試

3.1 算例描述

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

3.2 求解結(jié)果分析

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

續(xù)表9

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

4 結(jié)束語(yǔ)

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

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

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