易腐生鮮貨品車輛路徑問題的改進混合蝙蝠算法

殷 亞，張惠珍

(上海理工大學(xué) 管理學(xué)院，上海 2300093)

易腐生鮮貨品車輛路徑問題的改進混合蝙蝠算法

殷 亞，張惠珍*

(上海理工大學(xué) 管理學(xué)院，上海 2300093)

針對配送易腐生鮮貨品的車輛其配送路徑的選擇不僅受貨品類型、制冷環(huán)境變化、車輛容量限制、交貨時間等多種因素的影響，而且需要達到一定的目標(如：費用最少、客戶滿意度最高)，構(gòu)建了易腐生鮮貨品車輛路徑問題(VRP)的多目標模型，并提出了求解該模型的改進混合蝙蝠算法。首先，采用時間窗模糊化處理方法定義客戶滿意度函數(shù)，細分易腐生鮮貨品類型并定義制冷成本，建立了最優(yōu)路徑選擇的多目標模型;然后，在分析蝙蝠算法求解離散問題易陷入局部最優(yōu)、過早收斂等問題的基礎(chǔ)上，精簡經(jīng)典蝙蝠算法的速度更新公式，并對混合蝙蝠算法的單多點變異設(shè)定選擇機制，提高算法性能;最后，對改進混合蝙蝠算法進行性能測試。實驗結(jié)果表明,與基本蝙蝠算法和已有混合蝙蝠算法相比，所提算法在求解VRP時能夠提高客戶滿意度1.6%～4.2%，且減小平均總成本0.68%～2.91%。該算法具有計算效率高、計算性能好和較高的穩(wěn)定性等優(yōu)勢。

非同類易腐貨品；車輛路徑問題；混合蝙蝠算法；多目標；模糊時間窗

0 引言

車輛路徑問題(Vehicle Routing Problem, VRP)[1]是指：給定若干具有一定需求量的客戶，若干具有一定裝載能力的車輛從配送中心出發(fā)，為客戶進行配送服務(wù)后回到配送中心，同時使總路程最短、車輛數(shù)最少、費用最省等多個目標達到最優(yōu)。Solomon[2]于1987年首次考慮了帶時間窗的VRP(VRP with Time Window, VRPTW)，要求提供服務(wù)的配送車輛必須在客戶滿意的時間范圍內(nèi)進行配送。

冷鏈物流是指貨品在生產(chǎn)、運輸、銷售等環(huán)節(jié)始終處于規(guī)定的低溫環(huán)境下，以保證貨品質(zhì)量的貨物。易腐生鮮貨品作為冷鏈物流中的一部分，其配送成本與冷鏈物流一樣，不僅包括一般配送貨品中的運輸成本、固定成本等，而且包括在配送過程中為控制車廂溫度而增加的制冷成本[3]。本文研究的基于易腐生鮮貨品的VRP，相比一般貨品的車輛路徑問題，該問題的成本構(gòu)成及客戶滿意度構(gòu)成更為復(fù)雜，找到高效解決此類問題的方法已成為問題的關(guān)鍵。

本文研究的基于模糊時間窗的多目標車輛路徑問題是對基本VRP的拓展，屬于NP難題。由于智能啟發(fā)式算法求解效率高且有在短時間內(nèi)為大規(guī)模優(yōu)化問題提供滿意解的優(yōu)勢，所以更多學(xué)者青睞用智能啟發(fā)式算法求解此類組合優(yōu)化問題，如粒子群算法[4～5]、遺傳算法[6～7]、蟻群算法[8～9]、禁忌搜索算法[10～11]等。Yang[12]受到蝙蝠在高維空間定位、捕獵的啟發(fā)于2010年提出了蝙蝠算法(Bat Algorithm, BA),可以應(yīng)用于各種實際問題求解。Khan等[13]提出了模糊邏輯蝙蝠算法(Fuzzy Logic Bat Algrithm, FLBA)用于辦公場所的人因工程研究；Lin等[14]給出了混沌蝙蝠算法(Chaotic Bat Algorithm, CBA)實現(xiàn)線性生態(tài)系統(tǒng)中的參數(shù)估計；Nakamura等[15]在蝙蝠算法基礎(chǔ)上提出進一步研究用于解決特征選擇問題的二元蝙蝠算法(Binary Bat Algorithm, BBA)；Fister等[16]將蝙蝠算法用于體育訓(xùn)練規(guī)劃。相應(yīng)的研究成果表明，相比粒子群算法、遺傳算法等，蝙蝠算法具有模型簡單、魯棒性強、收斂性好、適應(yīng)性強的優(yōu)點；但是蝙蝠算法作為一種新興智能啟發(fā)式算法，在各個領(lǐng)域的應(yīng)用研究還不完善[17]。本文將在混合蝙蝠算法的基礎(chǔ)上進行進一步改進，并將優(yōu)化結(jié)果與基本蝙蝠算法及3種混合蝙蝠算法對比，驗證了本文算法對混合蝙蝠算法的改進具有良好的效果。

1 易腐生鮮貨品的車輛路徑問題

1.1 問題描述

基于模糊時間窗的多目標車輛路徑問題是在VRP的基礎(chǔ)上考慮了軟硬時間窗的混合，且通過服務(wù)時間對客戶滿意程度的影響模糊量化的多目標車輛路徑問題[18]。

由于本文研究的配送的貨物考慮不同種類的生鮮易腐貨品，所以相同的運輸時間及配送過程中相同的開門次數(shù)對不同類型的貨品價值，及客戶滿意度的影響程度不同。所以本文研究的易腐生鮮貨品VRP以總客戶滿意度最高及總成本最低作為優(yōu)化目標，并滿足條件：1)車輛從配送中心出發(fā)，完成其配送路徑上的所有任務(wù)后必須返回配送中心；2)配送途中，配送車輛的車載量不能超過配送車輛的最大載重量； 3)所有客戶的需求必須得到滿足，每個客戶僅可以被一輛車服務(wù)一次，且一輛車可以服務(wù)多個客戶；4)車輛必須在客戶允許的時間范圍內(nèi)提供配送服務(wù)，即車輛可以早到，但早到車輛必須等待，直到客戶允許的最早服務(wù)時間才能開始服務(wù)，但車輛不可以晚到。

1.2 構(gòu)建模型

1.2.1 符號定義

下面對易腐生鮮貨品車輛路徑問題數(shù)學(xué)模型中的符號進行定義：

已知一個配送中心(配送中心用0表示)和n個客戶(客戶集合N={1,2,…,n})構(gòu)成配送網(wǎng)絡(luò)中的節(jié)點集合U(U={0,1,…,n})，設(shè)總的車輛數(shù)為K(K={1,2,…,k})；每輛車的最大載重為WE；車輛到達客戶的時間ti；客戶i允許服務(wù)的最早開始時間和最晚開始時間分別為ETi和LTi;且客戶i接受服務(wù)的最大容忍時間上下限分別為EETi和ELTi；客戶i所需配送的載重、所需服務(wù)時間、配送車輛等待服務(wù)客戶i的時間、客戶i對配送服務(wù)的滿意度分別為wei、Si、wi、μi；車輛的行駛速度、固定成本和單位行駛距離的單位成本分別為v、C1和C2；每吸收千卡路里消耗單位制冷劑的價格為C3；車門關(guān)閉和打開時單位時間發(fā)生的熱負荷分別為Q1、Q2；車輛從客戶i到客戶j的距離為dij；S表示某一配送車輛的配送客戶集合；|S|表示集合S中所包含的頂點個數(shù)；P表示配送貨品的種類；fp為單位車門打開次數(shù)對p類易腐貨品客戶滿意度產(chǎn)生的影響因數(shù)；noi表示配送車輛為客戶i車門在某次配送中已打開次數(shù)；總客戶滿意度為CS。

決策變量為：

1.2.2 總成本構(gòu)成分析

本文的最小成本之和的目標建立基于易腐生鮮貨品，首先通過分析各項成本，構(gòu)成最終配送路徑上的各項總成本之和。

1)固定成本。

車輛的固定成本是指車輛的購置、日常的維護，以及人工費用等，且與完成此次配送任務(wù)所派出的配送車輛數(shù)成正相關(guān)。設(shè)每輛車的固定成本為C1，總車輛固定成本為TC1，則總車輛的固定成本計算公式為：

(1)

2)運輸成本。

影響運輸成本的因素主要是運輸距離，且與運輸距離呈正相關(guān)關(guān)系。假設(shè)單位路徑運輸成本為C2，則總的運輸成本計算公式如下：

(2)

3)制冷成本。

易腐生鮮貨品要求在整個物流配送環(huán)節(jié)一直處于低溫環(huán)境來確保貨品品質(zhì)，因此，配送車輛必須通過消耗制冷劑維持低溫。這種因制冷增加的成本稱為制冷成本。

在整個配送過程中，制冷劑的消耗源于外部環(huán)境與配送車廂之間的熱量傳遞，且此熱消耗主要分為兩種方式：車輛行駛過程中產(chǎn)生的熱消耗和車門開啟對客戶進行服務(wù)時產(chǎn)生的熱消耗，制冷成本計算公式如下：

(3)

1.2.3 總客戶滿意度構(gòu)成分析

1) 模糊時間窗對客戶滿意度的隸屬函數(shù)。

車輛在配送途中，受到各種不確定因素，如交通順暢度、天氣等的影響，導(dǎo)致貨物不能在規(guī)定的時間內(nèi)送達客戶，而在實際配送過程中，客戶一般會接受貨物，只是會降低客戶滿意度，所以硬時間窗VRP不具有一般性。本文所構(gòu)建的模糊時間窗在原時間窗范圍[ETi,LTi] 客戶的滿意度最高為100；超過原時間窗且在[EETi,ELTi] 時間窗范圍之內(nèi),滿意度隨時間呈下降趨勢，但客戶仍可接受服務(wù)，體現(xiàn)了軟時間窗的特點；一旦超過時間窗最大容忍上限EETi或下限ELTi，客戶不接受服務(wù)，且客戶滿意度為0，滿足硬時間窗的條件。

對應(yīng)上述描述，構(gòu)建的梯形模糊時間窗的客戶滿意度隸屬函數(shù)如圖1所示，對應(yīng)計算式(4)。

圖1 梯形模糊時間窗的客戶滿意度隸屬函數(shù)Fig. 1 Customer satisfaction membership function of trapezoidal fuzzy time window

(4)

(5)

2)車門打開次數(shù)對不同類型的生鮮貨品的影響。

在對客戶進行配送服務(wù)途中，對于不同種類的生鮮貨品，每打開一次車門，對車廂中尚待配送的貨品的品質(zhì)影響大小不同。所以本文根據(jù)車廂門打開次數(shù)對貨品產(chǎn)生的影響大小將待配送的生鮮貨品分成p類，每種貨品對應(yīng)的單位車門開啟次數(shù)對客戶滿意度產(chǎn)生的影響因數(shù)為fp，基于以上所述，配送途中車廂門打開次數(shù)對客戶滿意度的影響對應(yīng)計算公式：

(6)

1.3 模型建立

在滿足約束條件下建立的基于易腐生鮮貨物的帶模糊時間窗的多目標車輛路徑問題的數(shù)學(xué)模型如下：

(7)

(8)

s.t.

(9)

(10)

(11)

(12)

(13)

(14)

EETii≤ti+wi≤ELTi; ?i∈N

(15)

模型中，式(7)、(8)分別表示最小化總成本和最大化客戶滿意度的目標函數(shù)；式(9)保證所有客戶僅被服務(wù)一次；式(10)表示每輛車必須從配送中心出發(fā)；式(11)則表示所有車輛結(jié)束其路徑上的配送任務(wù)后必須返回配送中心；式(12)保證配送車輛進入某一客戶節(jié)點后必須從該客戶節(jié)點離開；式(13)確保每輛配送車輛服務(wù)的所有客戶的需求量之和不超過該車的最大承載量；式(14)為支路消除約束；式(15)為客戶時間窗約束。

2 車輛路徑的改進混合蝙蝠算法設(shè)計

2.1 經(jīng)典蝙蝠算法公式

蝙蝠是一種神奇的動物，它靠一種神奇的回聲定位系統(tǒng)來捕捉獵物，在黑暗中找到自己的棲息地[19]。經(jīng)典蝙蝠算法是受蝙蝠在搜尋獵物過程中的回聲定位行為啟發(fā)而提出的一種群體智能啟發(fā)式算法，其思想是利用蝙蝠的回聲定位行為搜尋優(yōu)化空間中的潛在解。

1)經(jīng)典蝙蝠的搜索過程。

經(jīng)典蝙蝠算法的搜索過程實質(zhì)是通過頻率f實現(xiàn)對蝙蝠的移動步伐和范圍的控制來更新蝙蝠的速度和位置。假設(shè)在t時刻將數(shù)量為m的蝙蝠種群散布到d維搜索空間，則編號為i的蝙蝠在位置xi=(xi1,xi2,…,xid)以速度vi=(vi1,vi2,…,vid)隨機飛行，通過改變頻率fi調(diào)整與最優(yōu)解之間的距離，跟隨最優(yōu)解，則蝙蝠在t+1時刻的位置和速度更新公式如下 ：

fi=fmin+(fmax-fmin)β

(16)

(17)

(18)

其中:i=1,2,…,m；fi∈[fmin,fmax];當前位置最優(yōu)的蝙蝠為x*；β是一個隨機因子且β∈[0,1] 。

2)經(jīng)典蝙蝠的尋優(yōu)過程。

另外，與其他智能啟發(fā)式算法類似，可以設(shè)定蝙蝠的尋優(yōu)行為，當前最優(yōu)蝙蝠xold通過公式在最優(yōu)位置附近隨機游走產(chǎn)生新位置。

xnew=xold+εAt

(19)

其中:At表示當前代蝙蝠種群響度的平均值；ε∈[0,1] 是一個隨機數(shù)。

當蝙蝠找到獵物時，脈沖音強Ai降低，同時脈沖頻度ri增加，具體更新公式如下：

(20)

(21)

2.2 改進混合蝙蝠算法的設(shè)計

2.2.1 經(jīng)典蝙蝠算法的簡化

經(jīng)典蝙蝠算法最初用于求解連續(xù)型函數(shù)優(yōu)化，而車輛路徑問題等實際應(yīng)用工程問題大多都是組合優(yōu)化問題，為了使蝙蝠算法在解決組合優(yōu)化問題時有較好的運算效率，本文采用基于客戶編號的編碼方式對個體進行編碼。且對蝙蝠算法中蝙蝠速度的更新方式作出簡化，以編號1～8的客戶為例進行編碼為例，求出蝙蝠與當前最優(yōu)解之間對應(yīng)位不同的數(shù)量即漢明距離，作為蝙蝠下一次飛行的速度，過程如圖2所示。

圖2 蝙蝠速度更新方式的簡化

Fig. 2 Simplification of bat’s speed updating mode

2.2.2 保留精英片段策略的引入

圖3 精英片段保留策略Fig. 3 Elite segment retention strategy

2.2.3 選擇性單、多點單親遺傳變異策略的引入

為了蝙蝠個體能夠有效地進行鄰域搜索，使得在當前蝙蝠種群的最優(yōu)個體搜尋到更好的解，本文設(shè)計出單親遺傳選擇性單、多點變異操作，用最優(yōu)解對每個蝙蝠個體進行引導(dǎo)，最優(yōu)個體也隨著進化的進行不斷更新，種群在多個精英個體領(lǐng)導(dǎo)下，可以避免陷入局部最優(yōu)。同樣以編號為1～8的客戶為例，首先求出當前蝙蝠與最優(yōu)蝙蝠之間的漢明距離：如果漢明距離大于n/2，隨機選出當前蝙蝠的一對位點，交換對位點上的解完成單點變異操作；如果漢明距離小于等于n/2，隨機選出當前蝙蝠解的兩對位點，交換對位點上的解完成多點變異操作。選擇性變異策略過程如圖4所示。

圖4 單親遺傳選擇性單、多點變異策略Fig. 4 Selective singlepoint or multipoint mutation strategy of single parent

2.2.4 改進混合蝙蝠算法的設(shè)計

針對組合優(yōu)化的特點，本文首先對基本蝙蝠算法進行簡化，并采用精英片段保留策略和單親遺傳算法中的單(多)點變異策略，較好地克服了蝙蝠算法在求解類似于車輛路徑這種離散型函數(shù)問題的局限性。

設(shè)計的改進混合蝙蝠算法具體步驟如下：

步驟1 初始化各參數(shù)，確定蝙蝠種群的數(shù)量m；最大迭代次數(shù)Itermax；蝙蝠種群的位置Bi(i=1,2,…,m)。

步驟2 通過路徑約束、車載量限制、服務(wù)約束等確定每只蝙蝠路徑上的配送車輛和所有配送車輛的路徑，根據(jù)目標函數(shù)，找出適應(yīng)度值最小的函數(shù)，確定為當前最優(yōu)蝙蝠。

步驟3 將當前最優(yōu)解的客戶排列編碼視為精英個體，并將精英片段與當前所有蝙蝠個體進行交叉，刪除重復(fù)客戶編號，形成基于精英進化的新蝙蝠。

步驟4 排列現(xiàn)有所有蝙蝠(解)，并更新當前最優(yōu)解B*。

步驟6 平衡局部搜索和全局搜索機制：如果((rand

步驟7 排列現(xiàn)有所有蝙蝠(解)，并更新當前最優(yōu)解B*。

步驟8 令I(lǐng)ter=Iter+1，如果Iter

改進混合蝙蝠算法框圖如圖5所示。

圖5 改進混合蝙蝠算法流程Fig. 5 Flow chart of improved hybrid bat algorithm

在實際編碼過程中本文將蝙蝠的位置及位置的優(yōu)劣分別與它所代表的解、目標函數(shù)的大小建立對應(yīng)關(guān)系：1)將客戶編號隨機排列(視為當前蝙蝠的位置)；2)按隨機排列的順序，派出車輛對第一個客戶進行服務(wù)，同時更新配送車輛實時載重、當前時間、已開門次數(shù)；3)計算當前客戶滿意度、當前車輛累計消耗成本；4)對第二個客戶進行配送，根據(jù)測試算例設(shè)定的車輛載重限制值，當前客戶配送時間窗的最大容忍上下限值等約束條件確定該配送車輛是否適合對該客戶進行配送，一旦約束條件不滿足當即從配送中心重新派車對該客戶進行服務(wù)；5)下一客戶同理判定是否需新增車輛進行配送，最終確定路線，并計算目標函數(shù)值(判斷當前蝙蝠位置優(yōu)劣)。另外，本文對多目標函數(shù)通過目標線性加權(quán)和法處理轉(zhuǎn)換成單目標求最小值。

3 實驗結(jié)果與分析

文獻[18]求解了帶軟、硬時間窗客戶的VRP，本文也采用該實例部分數(shù)據(jù)進行實驗，如表1所示；并將本文研究的單位車門打開次數(shù)對p類易腐貨品客戶滿意度產(chǎn)生的影響添加入算例，來驗證本文設(shè)計的改進混合蝙蝠算法在求解VRP的有效性。

3.1 算例描述

測試算例中各參數(shù)設(shè)定情況如下：車輛的最大載重量WE為30 t，行駛速度為60 km/h，車輛向15個客戶提供配送服務(wù)，考慮避開交通擁堵高峰時段，設(shè)開始工作時間為早上6:00，晚18:00停止工作，所有配送車輛于18:00之前返回配送中心。此外，單位車輛派遣成本C1=200元;單位距離每km運費C2=3元；單位制冷劑價格C3=0.2元/kCal；冷藏車車門關(guān)閉時發(fā)生的熱負荷Q1=48 kCal/h；冷藏車車門開啟時發(fā)生的熱負荷Q2=60 kCal/h。要求合理安排路線，使得完成所有配送任務(wù)之后，總成本最少，總客戶滿意度最高。配送中心與客戶需求點數(shù)據(jù)如表1所示，將貨品類型1～3按照隨機生成類型1、2、3添加入算例。

表1 配送中心與客戶需求點相關(guān)數(shù)據(jù)Tab. 1 Related data of distribution center and customer demand point

3.2 計算結(jié)果分析

為了驗證本文改進過后的混合蝙蝠算法較混合蝙蝠算法及基本蝙蝠算法在求解車輛路徑問題的有效性，本文利用Matlab R2010a對基本蝙蝠算法(基本)、精英遺傳混合蝙蝠算法[20](精英混合)、單親單點重組精英遺傳混合蝙蝠算法[20](單點+精英)、單親多點重組精英遺傳混合蝙蝠算法[20](多點+精英)、改進混合蝙蝠算法(改進混合)等5種算法進行編程實現(xiàn)，5種算法在Intel Core i5- 5200U 2.19 GHz(4.00 GB RAM)，操作系統(tǒng)為Win 10的環(huán)境下進行?？紤]到本文選取的算例為中小型算例，為了避免蝙蝠算法中的最大頻率和初始蝙蝠響度值Qmax、A0選值不當出現(xiàn)算法無法收斂、收斂過快或全局部搜索不和諧等問題，本文選取文獻[20]的最大聲波頻率值和蝙蝠音量值，且?、γ值選取基本蝙蝠算法經(jīng)驗值。算法具體設(shè)置參數(shù)如下：Qmax=10，Qmin=0，?=0.9,γ=0.9，蝙蝠的初始響度A0∈[0,1]，初始脈沖發(fā)生率r0∈[0,1]，蝙蝠種群數(shù)n=30，Itermax=500。其中，基本蝙蝠算法種群數(shù)為60，改進混合蝙蝠算法種群數(shù)為20。

表2～3數(shù)據(jù)皆為算法隨機運行10次所有解數(shù)據(jù)記錄和計算得出。表2為用本文設(shè)計的改進混合蝙蝠算法求解得到的最佳配送路徑線路表；表3為根據(jù)求解結(jié)果進行實際配送所消耗的成本和客戶滿意度等的數(shù)據(jù)結(jié)果。

由表3可見，改進混合蝙蝠算法在更短的求解時間內(nèi)減小了此次配送任務(wù)的總成本，同時提高了客戶滿意度。為進一步驗證本文設(shè)計的改進混合蝙蝠算法的有效性，以本文的改進混合蝙蝠算法各結(jié)果數(shù)值為基數(shù)1，計算出該算法與其他蝙蝠算法[20]結(jié)果提高的百分比，計算提高結(jié)果如表4所示。

表2 改進混合蝙蝠算法最優(yōu)路徑Tab. 2 Optimal route of improved hybride bat algorithm

表3 改進混合蝙蝠算法與其他蝙蝠算法性能比較Tab. 3 Performance comparison of improved hybrid bat algorithm with other bat algorithms

表4改進混合蝙蝠算法相比其他蝙蝠算法性能提高幅度%

Tab. 4 Performance improvement of the improved hybrid bat algorithm over other bat algorithms %

由表4可知，改進后的混合蝙蝠算法在平均客戶滿意度上的提高均大于1.60%，最大提高了4.20%；在平均總成本方面減小多于0.68%。所以，本文所提算法比基本蝙蝠算法、混合蝙蝠算法具有更好的搜索性能和穩(wěn)定性。

4 結(jié)語

易腐生鮮貨品車輛路徑問題的關(guān)鍵在于保證貨品品質(zhì)的的基礎(chǔ)上節(jié)約成本，而在實際配送過程中也應(yīng)充分考慮客戶對不同生鮮貨品的品質(zhì)要求及配送服務(wù)時間要求，本文在考慮客戶軟、硬時間窗的同時將生鮮貨品分類，最大化滿足客戶需求，提高客戶滿意度。

另外，本文算法針對組合優(yōu)化特點，對原有混合蝙蝠算法速度更新算子進行精簡，并將單點重組精英遺傳算子和多點重組精英遺傳算子進行選擇性調(diào)用，提高了算法運算效率。實例對本文算法、基本蝙蝠算法及文獻[20]中的3種蝙蝠算法進行測試，測試結(jié)果表明，改進混合蝙蝠算法在確保種群多樣性的基礎(chǔ)上，平衡了全局與局部搜索的能力，全面提高了混合蝙蝠算法的計算速率和計算效果，同時具有更高的穩(wěn)定性。在實際應(yīng)用中，易腐生鮮貨品車輛路徑問題有求解規(guī)模大的特點，如何進一步提高算法求解大規(guī)模算例是下一步研究的重點。

References)

[1] 劉云,張惠珍.多目標帶時間窗的車輛路徑問題的單親遺傳混合蟻群算法[J].公路交通科技,2016,33(6):95-100.(LIU Y, ZHANG H Z. A partheno-gentic hybrid ant colony algorithm for solving multi-objective vehicle routing problem with time window [J]. Journal of Highway and Transportation Research and Development, 2016, 33(6): 95-100.)

[2] SOLOMON M M. Algorithms for the vehicle routing and scheduling problems with time window constraints [J]. Operations Research, 1987, 35(2): 254-265.

[3] 馬向國,劉同娟,楊平哲,等.基于隨機需求的冷鏈物流車輛路徑優(yōu)化模型[J].系統(tǒng)仿真學(xué)報,2016,28(8):1824-1832.(MA X G, LIU T J, YANG P Z, et al. Vehicle routing optimization model of cold chain logistic based on stochastic demand [J]. Journal of System Simulation, 2016, 28(8): 1824-1832.)

[4] MARINAKIS Y, MAGDALENE M. A hybrid particle swarm optimization algorithm for the open vehicle routing problem [C]// Proceedings of the 2010 8th International Conference on Swarm Intelligence, LNCS 7461. Berlin: Springer, 2010: 180-187.

[5] 陳玉光,陳志祥.基于準時送貨和最小耗油的配送車輛路徑問題研究[J].中國管理科學(xué),2015, 23(S1):156-164.(CHEN Y G, CHEN Z X. Study on the vehicle routing problem with objectives of on-time delivery and oil consumption minimization [J]. Chinese Journal of Management Science, 2015, 23(S1): 156-164.)

[6] URSANI Z, ESSAM D, CORNFORTH D, et al. Localized genetic algorithm for vehicle routing problem with time windows [J]. Applied Soft Computing, 2011, 11(8): 5375-5390.

[7] GHOSEIRI K, GHANNADPOUR S F. Multi-objective vehicle routing problem with time windows using goal programming and genetic algorithm [J]. Applied Soft Computing, 2010, 10(4): 1096-1107.

[8] 何小鋒,馬良.帶時間窗車輛路徑問題的量子蟻群算法[J].系統(tǒng)工程理論與實踐,2013,33(5):1255-1261.(HE X F, MA L. Quantum-inspired ant colony algorithm for the vehicle routing problem with time windows[J]. Systems Engineering — Theory & Practice, 2013, 33(5): 1255-1261.)

[9] 段征宇,楊東援,王上.時間依賴型車輛路徑問題的一種改進蟻群算法[J].控制理論與應(yīng)用,2010,27(11):1557-1563.(DUAN Z Y, YANG D Y, WANG S. Improved ant colony optimization algorithm for time-dependent vehicle routing problem [J]. Control Theory & Application, 2010, 27(11): 1557-1563.)

[10] RENAUD J, LAPORTE G, BOCTOR F F. A tabu search heuristic for the multi-depot vehicle routing problem [J]. Computers & Operations Research, 1996, 23(3): 229-235.

[11] 程碧榮,趙曉波,秦進.考慮供應(yīng)不足的應(yīng)急物流車輛路徑優(yōu)化模型及算法[J].計算機應(yīng)用研究,2016,33(6):1682-1685.(CHEN B R, ZHAO X B, QIN J. Optimization model and algorithm for emergency vehicle route with insufficiency supply [J]. Application Research of Computers, 2016, 33(6): 1682-1685).

[12] YANG X S. A New Metaheuristic Bat-Inspired Algorithm [M]// Nature Inspired Cooperative Strategies for Optimization. Berlin: Springer, 2010: 65-74.

[13] KHAN K, NIKOV A, SAHAI A. A fuzzy bat clustering method for ergonomic screening of office workplaces [C]// Proceedings of the 2011 Third International Conference on Software, Services and Semantic Technologies, AINSC 101. Berlin: Springer, 2011: 59-66.

[14] LIN J H, CHOU C W, YANG C H, et al. A chaotic levy flight bat algorithm for parameter estimation in nonlinear dynamic biological systems [J]. Journal of Computer and Information Technology, 2012, 2(2): 56-63.

[15] NAKAMURA R Y M, PEREIRA L A M, COSTA K A, et al. BBA: a binary bat algorithm for feature selection [C]// Proceedings of the 2012 25th SIBGRAPI Conference on Graphics, Patterns and Images. Piscataway, NJ: IEEE, 2012: 291-297.

[16] FISTER I, RAUTER S, YANG X S, et al. Planning the sports training sessions with the bat algorithm [J]. Neurocomputing, 2015, 149(PB): 993-1002.

[17] 楊鵬,鄒浩,徐賢浩.帶時間窗集送貨需求可分車輛路徑問題的改進蟻群算法[J].系統(tǒng)工程,2015,33(9):58-62.(YANG P, ZOU H, XU X H.Improved ant colony algorithm for vehicle routing problem with time windows and split pickups and deliveries [J]. Systems Engineering, 2015,33(9):58-62.)

[18] 楊翔,范厚明,張曉楠,等.基于模糊時間窗的多中心開放式車輛路徑問題[J].計算機集成制造系統(tǒng),2016,22(7):1768-1778.(YANG X, FAN H M , ZHANG X N, et al. Optimization of multi-deport open vehicle routing problem with fuzzy time window [J]. Computer Integrated Manufacturing Systems, 2016, 22(7): 1768-1778.)

[19] 李枝勇,馬良,張惠珍.蝙蝠算法在多目標多選擇背包問題中的應(yīng)用[J].計算機仿真,2013,30(10):350-353.(LI Z Y, MA L, ZHANG H Z. Application of bat algorithm in multi-objective and multi-choice knapsack problem [J]. Computer Simulation, 2013, 30(10): 350-353.).

[20] 殷亞,張惠珍.求解帶硬時間窗的多目標車輛路徑問題的多種混合蝙蝠算法[J].計算機應(yīng)用研究,2017,34(12):1-7.(YIN Y, ZHANG H Z. Multi-hybrid bat algorithm for solving multi-objectives vehicle routing problem with hard time window [J]. Application Research of Computers, 2017, 34(12): 1-7.)

This work is partially supported by the National Natural Science Foundation of China (71401106), the Shanghai Municipal Education Commission Scientific Research Innovation Project (14YZ090), the Humanities and Social Science Project of Ministry of Education (16YJA630037).

YINYa, born in 1993, M. S. candidate. Her research interests include logistic enginnering, intelligent optimization.

ZHANGHuizhen, born in 1979, Ph. D., sssociate professor. Her research interests include operations research, intelligent optimization.

Improvedhybridbatalgorithmforvehicleroutingproblemofperishablefreshgoods

YIN Ya, ZHANG Huizhen*

(SchoolofManagement,UniversityofShanghaiforScienceandTechnology,Shanghai200093,China)

The choice of distribution route for vehicle with perishable fresh goods is not only affected by various factors such as the type of goods, the change of refrigeration environment, vehicle capacity limit and delivery time, but also needs to reach the certain targets such as the least cost and the highest customer satisfaction. In order to solve the problem, a multi-objective model for Vehicle Routing Problem (VRP) of perishable fresh goods was constructed and an improved hybrid bat algorithm was proposed to solve the constructed model. Firstly, the time window fuzzy processing method was used to define the customer satisfaction function, and the multi-objective model of optimal path selection was established by subdividing the perishable fresh goods types and defining the refrigeration cost. The bat algorithm is easy to fall into local optimum and premature convergence in solving discrete problems. Then, on the basis of analyzing the above problems, the speed update formula of classical bat algorithm was simplified, and the singlepoint or multipoint mutation selection mechanism of the hybrid bat algorithm was set up to improve the performance of the algorithm. Finally, the performance of the proposed algorithm was tested. Compared with the basic bat algorithm and several existing hybrid bat algorithms, the customer satisfaction of the proposed improved hybrid bat algorithm is improved by 1.6%-4.2% in solving VRP and the average total cost is reduced by 0.68%-2.91%. The proposed algorithm has better computational performance, higher computational efficiency and stability.

different type of perishable goods; Vehicle Routing Problem (VRP); hybrid bat algorithm; multi-objective; fuzzy time window

2017- 06- 29;

2017- 09- 04。

國家自然科學(xué)基金資助項目(71401106)；上海市教委科研創(chuàng)新項目(14YZ090)；教育部人文社會科學(xué)研究項目(16YJA630037)。

殷亞(1993—)，女，江蘇鹽城人，碩士研究生，主要研究方向：物流工程、智能優(yōu)化； 張惠珍(1979—)，女，山西沂州人，副教授，博士，主要研究方向：運籌學(xué)、智能優(yōu)化。

1001- 9081(2017)12- 3602- 06

10.11772/j.issn.1001- 9081.2017.12.3602

(*通信作者電子郵箱zzhzzywz@163.com)

TP301.6

A