王 勇,左佳昕,蔣 瓊,劉 永,許茂增

(重慶交通大學(xué) 經(jīng)濟(jì)與管理學(xué)院,重慶 400074)

在物聯(lián)網(wǎng)的發(fā)展時代,鼓勵顧客的即時回收,一種基于物聯(lián)網(wǎng)技術(shù)由眾多智能回收箱組成的智能回收系統(tǒng)得到廣泛應(yīng)用[1-2]。傳統(tǒng)回收模式存在回收產(chǎn)品定價難以有效測度和信息傳播途徑不暢等缺點,而智能回收系統(tǒng)具有產(chǎn)品回收定價可量化程度高和信息流通性強(qiáng)等優(yōu)勢,且產(chǎn)品回收定價調(diào)整與回收量之間的關(guān)系明確,有助于產(chǎn)品回收中心針對不同的回收產(chǎn)品定價進(jìn)行車輛的多頻次回收和共享車輛調(diào)度。因此,研究基于產(chǎn)品回收定價的逆向物流車輛路徑優(yōu)化問題,有利于進(jìn)一步完善城市逆向物流回收系統(tǒng),并有利于環(huán)境友好型社會構(gòu)建和可持續(xù)發(fā)展。國內(nèi)外學(xué)者在回收產(chǎn)品定價決策和智能回收模式下逆向物流車輛路徑問題方面進(jìn)行了一系列研究。

在回收產(chǎn)品定價決策方面的研究有:陳章躍等[3]以制造商主導(dǎo)的再制造閉環(huán)供應(yīng)鏈為研究對象,研究了制造商自營回收模式和外包回收模式下的回收產(chǎn)品定價和制造商利潤問題;李響等[4]研究了多個再制造商的回收定價策略問題,探討了回收價格對再制造商回收量的影響;朱曉東等[5]考慮傳統(tǒng)回收與互聯(lián)網(wǎng)回收之間的回收成本差異,構(gòu)建了定價決策模型,并通過數(shù)值仿真分析了各回收因素對回收定價與回收量的影響;許民利等[6]針對“互聯(lián)網(wǎng)+回收”背景下的智能回收定價策略問題,建立了考慮消費者行為的回收模型,提出競爭性回收環(huán)境下回收定價將直接影響回收量;馮章偉等[7]針對以回收商為領(lǐng)導(dǎo)的兩級再制造閉環(huán)供應(yīng)鏈定價決策問題構(gòu)建了博弈模型,分別在兩級再制造和僅產(chǎn)品再制造情形下分析了回收定價決策對回收數(shù)量和回收商收益的影響;李琰等[8]考慮多周期閉環(huán)營銷建立了產(chǎn)品差異定價模型,并結(jié)合算例分析了該定價模型下不同營銷策略對回收量的影響。由上述相關(guān)文獻(xiàn)可知,回收產(chǎn)品定價決策對回收量有直接影響,但在探討不同回收定價策略對回收中心回收量的影響,以及結(jié)合逆向物流車輛路徑優(yōu)化方面還有待進(jìn)一步的深入。

在智能回收模式下逆向物流車輛路徑問題方面的研究有:Hannan等[9]考慮了智能回收箱的實時收集狀態(tài),設(shè)計了一種改進(jìn)的粒子群算法,研究了基于智能回收箱固體廢料收集的逆向物流車輛路徑優(yōu)化問題;Ramos等[10]以智能回收箱回收量最大化和車輛運輸成本最小化為目標(biāo),針對不同管理模式建立了逆向物流車輛路徑優(yōu)化模型以確定動態(tài)最優(yōu)路線;Nowakowski等[11]研究了廢舊電器電子設(shè)備的智能回收問題,提出了一種和諧搜索算法以優(yōu)化車輛的智能回收路徑,并通過算法對比驗證了該算法設(shè)計的優(yōu)越性;Wu等[12]研究了以智能垃圾桶為應(yīng)用背景的城市濕垃圾收集與運輸優(yōu)化問題,構(gòu)建了一個帶機(jī)會約束的逆向物流車輛路徑優(yōu)化模型,并結(jié)合實例驗證了模型的應(yīng)用性。此外,逆向物流網(wǎng)絡(luò)中的車輛資源共享調(diào)度問題也逐漸受到學(xué)者的關(guān)注;Bergmann等[13]提出了考慮城市回收物流的車輛共享機(jī)制,研究了送貨與取貨相結(jié)合的路線效率權(quán)衡問題;Liu等[14]探討了基于物聯(lián)網(wǎng)實時信息獲取的逆向物流資源共享機(jī)制,建立了一個逆向物流實時信息動態(tài)優(yōu)化模型以實現(xiàn)回收車輛的合理分配;Wang等[15]考慮了基于狀態(tài)-空間-時間三維網(wǎng)絡(luò)的逆向物流車輛共享調(diào)度策略,并將精確算法和啟發(fā)式算法相結(jié)合研究了綠色可回收包裹的車輛路徑優(yōu)化問題。綜上所述,逆向物流車輛路徑優(yōu)化和運輸資源共享調(diào)度是智能回收模式下基于產(chǎn)品回收定價的逆向物流車輛路徑優(yōu)化問題研究的切入點。

本文研究了基于產(chǎn)品回收定價的逆向物流車輛路徑優(yōu)化問題,不同于前述研究問題和方法,本研究考慮了逆向物流網(wǎng)絡(luò)中回收產(chǎn)品數(shù)量和回收產(chǎn)品定價之間的線性關(guān)系,提出了基于不同回收定價策略和車輛共享調(diào)度的多頻次回收線路設(shè)計方案,并結(jié)合遺傳算法全局搜索能力強(qiáng)與粒子群算法收斂速度快的特點設(shè)計了混合算法間的精英保留策略,增強(qiáng)了混合算法的搜索性能。首先構(gòu)建了智能回收箱回收量與回收產(chǎn)品定價的線性函數(shù),然后構(gòu)建了以逆向物流回收運營成本最小化和回收中心產(chǎn)品收益最大化的雙目標(biāo)優(yōu)化模型,并設(shè)計了一種基于Kmeans時空聚類的GA-PSO 混合算法進(jìn)行模型求解,同時探討了不同回收產(chǎn)品定價策略下不同回收頻次和車輛資源共享的逆向物流車輛路徑優(yōu)化問題,為基于產(chǎn)品回收定價的逆向物流網(wǎng)絡(luò)資源配置問題提供了新的研究思路。

1 問題描述

在智能回收物流網(wǎng)絡(luò)中,回收產(chǎn)品的不同定價策略將導(dǎo)致顧客投遞回收產(chǎn)品的數(shù)量有所不同,進(jìn)而導(dǎo)致一定時間周期內(nèi)達(dá)到滿載狀態(tài)的智能回收箱數(shù)量不同,從而影響智能回收箱的回收頻次。在回收中心車輛數(shù)量一定的情況下,為了有效整合物流資源、提高回收效率,需要綜合研究單位回收產(chǎn)品的定價、智能回收箱的回收頻次以及逆向物流回收運營成本間的相關(guān)關(guān)系[16],需要進(jìn)行合理的逆向物流車輛路徑優(yōu)化調(diào)度問題研究。基于產(chǎn)品回收定價調(diào)整的逆向物流車輛路徑優(yōu)化前后對比如圖1所示。

由圖1可知,圖1(a)表示單位回收產(chǎn)品定價調(diào)整前的回收量和顧客獲得的收益,由于單位回收產(chǎn)品的定價較低,導(dǎo)致顧客投遞回收產(chǎn)品的收益回報較低且投遞積極性不高。圖1(c)表示單位回收產(chǎn)品定價調(diào)整前的車輛回收路徑,由于單位回收產(chǎn)品的定價較低,導(dǎo)致在一定時間周期內(nèi)存在較多未滿足收集狀態(tài)的智能回收箱,且在車輛回收過程中存在多個違反智能回收箱服務(wù)時間窗的情況。圖1(b)表示單位回收產(chǎn)品定價調(diào)整后的回收量和顧客獲得的收益,由于單位回收產(chǎn)品定價的提高,增加了顧客的回收收益,進(jìn)而促使參與回收的客戶數(shù)增加,并有效提高了智能回收箱的回收產(chǎn)品數(shù)量。圖1(d)表示單位回收產(chǎn)品定價調(diào)整后的車輛回收優(yōu)化路徑,由于智能回收箱的回收產(chǎn)品數(shù)量增加,且存在一定時間周期內(nèi)智能回收箱多次滿載回收的情況,進(jìn)而結(jié)合多頻次回收和車輛共享調(diào)度策略進(jìn)行合理的車輛路徑優(yōu)化,可以有效節(jié)約逆向物流回收運營成本、提高回收效率。

假設(shè)單個智能回收箱達(dá)到滿載狀態(tài)時的回收量為50 kg,回收中心將回收產(chǎn)品轉(zhuǎn)讓至下游企業(yè)的單位回收產(chǎn)品期望收益為0.7元,回收產(chǎn)品定價調(diào)整前顧客投遞單位產(chǎn)品獲得的收益為0.2元,回收產(chǎn)品定價調(diào)整后顧客投遞單位回收產(chǎn)品獲得的收益為0.3元,回收產(chǎn)品的清潔成本為0.1元,違反時間窗的單位時間懲罰成本為10元,單位時間的運輸成本為30元,車輛的租賃成本為100元/輛,單位回收產(chǎn)品的環(huán)境外部性收益為0.8元。表1給出了單位定價調(diào)整和車輛共享調(diào)度優(yōu)化前后回收中心產(chǎn)品收益和相關(guān)物流成本的比較。結(jié)果表明:由于回收中心單位回收產(chǎn)品定價的調(diào)整,使得回收產(chǎn)品總量由400 kg增加至1 250 kg;考慮了車輛共享調(diào)度策略,使得回收線路數(shù)由3條增加至7條,提高了車輛利用率。此外,合理的車輛調(diào)度使逆向物流運營成本由830元降至450元,而回收中心產(chǎn)品收益由160元增加至375元。

表1 單位回收產(chǎn)品定價調(diào)整和車輛共享調(diào)度優(yōu)化前后回收中心產(chǎn)品收益和物流成本的比較

2 模型建立

2.1 問題假設(shè)

當(dāng)智能回收箱達(dá)到滿載狀態(tài)時,可以發(fā)送信息至回收中心,回收中心根據(jù)滿載智能回收箱的數(shù)量和分布情況進(jìn)行回收車輛的集中運輸調(diào)度[17-18]。模型假設(shè)如下:

(1)回收數(shù)量和回收定價之間通常呈線性[19-20]和非線性關(guān)系[21-22],本文假設(shè)回收數(shù)量和回收定價之間呈線性關(guān)系。

(2)回收中心擁有有限數(shù)量的同型回收車輛,且同一回收車輛能夠收集多種回收產(chǎn)品并能滿足智能回收箱的收集需求。

(3)滿載狀態(tài)的回收量是指單個智能回收箱達(dá)到一定裝載量要求后的回收量,且達(dá)到滿載狀態(tài)的智能回收箱數(shù)量已知。

(4)回收過程中,一個工作周期內(nèi)需要進(jìn)行多頻次回收服務(wù),每一服務(wù)頻次可看作一個服務(wù)周期。

2.2 符號定義

本文所涉及的變量及符號的相關(guān)定義如下:

I——回收點集合,I={ii=1,2,…,n}

I0——回收點與回收中心構(gòu)成的集合,I0=I∪{0},0表示回收中心

V——回收車輛v的集合,V={vv=1,2,…,r}

K——在一個工作周期內(nèi)的服務(wù)周期(頻次)集合,K={=1,2,…,z}

G——居民居住規(guī)模類型集合,G={g|g=1,2,…,j}

L——回收品種類集合,L={ll=1,2,…,e}

H——單位回收產(chǎn)品定價類型集合,H={1,2,…,u}

Qglh——當(dāng)居民規(guī)模類型為g時回收點選擇定價h收集產(chǎn)品l的滿箱回收總量

Plh——單位回收產(chǎn)品l選擇h類型回收定價

ulk——單位回收產(chǎn)品l在第k個服務(wù)周期的期望收益

ol——單位回收產(chǎn)品l的清潔成本

qil——回收點i達(dá)到滿載狀態(tài)時收集回收產(chǎn)品l的回收量

qgl0——當(dāng)居民規(guī)模類型為g時不依賴回收定價的情況下回收點收集產(chǎn)品l的回收總量

Nvk——回收車輛v在第k個服務(wù)周期內(nèi)的回收路線集合

Svkn——回收車輛v在第k個服務(wù)周期的第n條線路內(nèi)服務(wù)的回收點集合

fvk——回收車輛v在第k個服務(wù)周期的單位距離運輸成本

Cv——回收車輛v的最大載重

Dij——從回收點i至回收點j的回收距離

MV——回收車輛v的年平均維修成本

LN——一個足夠大的數(shù)

[aik,bik]——回收點i在第k個服務(wù)周期內(nèi)的時間窗

[mk,nk]——回收中心在第k個服務(wù)周期內(nèi)的時間窗

μe——回收車輛v在第k個服務(wù)周期內(nèi)提前到達(dá)回收點i的單位時間懲罰系數(shù)

μd——回收車輛v在第k個服務(wù)周期內(nèi)延遲到達(dá)回收點i的單位時間懲罰系數(shù)

dvkn——回收車輛v在第k個服務(wù)周期的第n條線路內(nèi)從回收中心出發(fā)的時間

rvkn——回收車輛v在第k個服務(wù)周期的第n條線路內(nèi)返回至回收中心的時間

eivkn——回收車輛v在第k個服務(wù)周期的第n條線路內(nèi)到達(dá)回收點i的時間

tijvk——回收車輛v在第k個服務(wù)周期內(nèi)從回收點i～j的行駛時間

WTivkn——回收車輛v在第k個服務(wù)周期內(nèi)的第n條線路內(nèi)到達(dá)回收點i之前的等待時間

T——1年中的工作周期數(shù)

Wk——回收中心在第k個服務(wù)周期內(nèi)的回收量

R——回收中心的最大回收量

Glk——回收中心在第k個服務(wù)周期內(nèi)收集單位回收產(chǎn)品l的固定回收成本

λlk——回收中心在第k個服務(wù)周期內(nèi)收集單位回收產(chǎn)品l的可變成本系數(shù)

Zlk——回收品l在第k個服務(wù)周期內(nèi)單位回收量的環(huán)境外部性收益

θg——當(dāng)居民規(guī)模類型為g時回收中心服務(wù)范圍覆蓋系數(shù)

?lh——當(dāng)單位回收產(chǎn)品l選擇h類型定價時回收點收集該類型回收產(chǎn)品的滿箱率

αlh——顧客對回收品l對應(yīng)回收定價h的敏感系數(shù)

ρl——回收產(chǎn)品l的回收量規(guī)模系數(shù)

xijvk——如果車輛v在第k個服務(wù)周期內(nèi)從回收點i駛向j,則決策變量等于1,否則等于0

xijvkn——如果車輛v在第k個服務(wù)周期內(nèi)的第n條線路中從回收點i駛向j,則決策變量等于1,否則等于0

svk——如果車輛v在第k個服務(wù)周期內(nèi)服務(wù)回收點,則決策變量等于1,否則等于0

yivkn——如果回收點i在第k個服務(wù)周期內(nèi)由車輛v在第n條路線中服務(wù)時,則決策變量等于1,否則等于0

2.3 回收產(chǎn)品數(shù)量與單位回收產(chǎn)品定價的關(guān)系確定

本文構(gòu)建不同回收定價下智能回收箱收集單一類型回收產(chǎn)品的滿箱回收總量Qglh與回收定價Plh的線性函數(shù)[23-24],如下式所示:

式中:qgl0為無償情形下回收點收集回收品l的回收總量,即當(dāng)回收定價為0時,智能回收箱所服務(wù)地區(qū)具有環(huán)保意識的顧客無償參與回收投遞時的回收量;αlh為顧客對回收產(chǎn)品l對應(yīng)回收定價h的敏感系數(shù),顧客對回收定價越敏感,則αlh越大,且0＜αlh＜1。

以3種不同回收產(chǎn)品為例,選取3種居民居住規(guī)模類型,g=1,2,3分別表示小型、中型和大型居民規(guī)模,在產(chǎn)品1單位回收定價為0.8元、產(chǎn)品2單位回收定價為0.5 元和產(chǎn)品3 單位回收定價為1.0 元的基礎(chǔ)上,分別調(diào)整回收定價Plh,并設(shè)θ1=2,θ2=4,θ3=8,q110=60,q210=120,q310=190,q120=90,q220=180,q320=240,q130=110,q230=210,q330=270,ρ1=300,ρ2=600,ρ3=900,應(yīng)用式(1)計算得到回收量Qglh,如表2所示。

表2 不同回收產(chǎn)品和不同回收產(chǎn)品定價所對應(yīng)的不同居民規(guī)模產(chǎn)品回收量

2.4 模型構(gòu)建

以回收中心物流運營成本W(wǎng)1最小和產(chǎn)品收益W2最大為優(yōu)化目標(biāo),建立如下數(shù)學(xué)模型:

式(2)中,T1為回收車輛耗損的維護(hù)成本和車輛駛向回收點進(jìn)行回收的運輸成本,

T2為設(shè)施固定回收成本、回收中心收集量改變后所產(chǎn)生的變動成本以及環(huán)境外部性收益,

T3為回收車輛未在規(guī)定的服務(wù)時間窗內(nèi)到達(dá)回收點所需支付的懲罰成本,

約束條件:

式(7)表示在任一服務(wù)周期內(nèi)滿足回收狀態(tài)的回收箱回收總量不能超過回收中心的最大回收量;式(8)表示在任一服務(wù)周期的任意回收路線內(nèi)車輛v的回收總量不超過車輛的最大載重;式(9)保證任一服務(wù)周期內(nèi)的回收量;式(10)表示在任一服務(wù)周期內(nèi)每個滿足回收狀態(tài)的回收點只能由一輛車服務(wù);式(11)～(13)表示在任一服務(wù)周期內(nèi)車輛v從回收中心出發(fā)完成收集任務(wù)后不作停留返回至回收中心;式(14)表示消除回收路徑上的子回路;式(15)保證在任一服務(wù)周期內(nèi)任意回收車輛的收集線路總數(shù);式(16)保證了回收車輛的收集路線順序;式(17)表示在任一服務(wù)周期內(nèi)車輛v能夠在規(guī)定的時間窗內(nèi)達(dá)到回收點i;式(18)、(19)表示在任一服務(wù)周期內(nèi)車輛v能夠在回收中心的服務(wù)時間窗內(nèi)離開和返回回收中心;式(20)、(21)表示車輛v在回收過程中的連續(xù)性;式(22)保證了在任一服務(wù)周期內(nèi)車輛不同路線時間的連續(xù)性;式(23)～(26)表示變量約束。

3 基于K-means時空聚類的GA-PSO混合算法

3.1 算法介紹

針對基于產(chǎn)品回收定價的逆向物流車輛路徑優(yōu)化問題,本文設(shè)計了一種基于K-means時空聚類的GA-PSO 混合算法,求解以回收中心產(chǎn)品收益最大化與逆向物流運營成本最小化的雙目標(biāo)優(yōu)化模型。首先,應(yīng)用K-means時空聚類算法生成初始聚類單元,然后指派智能回收箱至臨近聚類中心并更新聚類中心;其次,在聚類單元內(nèi)和聚類單元間進(jìn)行遺傳-粒子群算法迭代操作,結(jié)合遺傳算法的全局搜索能力強(qiáng)與粒子群算法的快速收斂性特點[25],同時設(shè)計精英保留迭代策略提高了算法的全局搜索性能,增加了混合算法的多樣性[26]?；贙-means時空聚類的GA-PSO 混合算法流程如圖2所示。

3.2 K-means時空聚類

根據(jù)模型特點,采用改進(jìn)的曼哈頓距離[27]作為三維網(wǎng)絡(luò)中的距離函數(shù),以評估各聚類中心與每個客戶之間的時空距離。本文建立包括智能回收箱地理坐標(biāo)和回收服務(wù)時間窗在內(nèi)的三維坐標(biāo)系,根據(jù)智能回收箱地理坐標(biāo)和服務(wù)時間的相似性,利用Kmeans聚類算法將各智能回收箱指派至最近的聚類單元獲得聚類結(jié)果。假設(shè)(xi,yi)和(xj,yj)分別為智能回收箱i和j的地理坐標(biāo),(mi,ni)和(mj,nj)分別為智能回收箱i和j的服務(wù)時間窗,則智能回收箱間距離為

式中,φ為時間和距離間的轉(zhuǎn)換系數(shù)。

K-means時空聚類算法具體過程如下:

步驟1導(dǎo)入?yún)⑴c聚類的智能回收箱地理坐標(biāo)與服務(wù)時間窗信息等相關(guān)數(shù)據(jù);

步驟2根據(jù)步驟1所導(dǎo)入智能回收箱服務(wù)時間窗的分布特征,確定回收服務(wù)周期數(shù)與回收服務(wù)周期時間區(qū)間;

步驟3確定各回收服務(wù)周期內(nèi)的聚類數(shù)為k,并在相應(yīng)回收服務(wù)周期內(nèi)選取k個聚類中心;

步驟4應(yīng)用式(27)計算每個回收服務(wù)周期內(nèi)智能回收箱到各聚類中心的時空距離;

步驟5在相應(yīng)回收服務(wù)周期內(nèi)將每個智能回收箱指派至最臨近的聚類中心;

步驟6更新k個聚類單元的聚類中心;

步驟7重復(fù)步驟4～7,直至各回收服務(wù)周期內(nèi)的聚類中心不再改變;

步驟8輸出聚類結(jié)果。

3.3 算法設(shè)計

3.3.1 適應(yīng)度函數(shù) 本文以回收中心產(chǎn)品收益最大化與逆向物流運營成本最小化為目標(biāo)函數(shù)設(shè)計算法適應(yīng)度,能更有效地權(quán)衡混合算法中個體的優(yōu)化程度。在PSO 算法與GA 算法過程中設(shè)定適應(yīng)度函數(shù)為

式中:W1為逆向物流運營成本;W2為回收中心的產(chǎn)品收益。

3.3.2 局部映射交叉和多項式變異 采用局部映射方法[28]進(jìn)行染色體的交叉操作。在各聚類單元生成的初始種群內(nèi),通過輪盤賭方法[29]選擇出適應(yīng)度值較大的個體作為父代染色體進(jìn)行聚類單元內(nèi)與聚類單元間的染色體局部映射交叉操作。在選擇出的染色體中隨機(jī)確定相應(yīng)位置的子序列作為交叉區(qū)域,然后進(jìn)行局部交叉操作,如果交叉后同一條染色體內(nèi)存在相同基因,則將其移除并根據(jù)父代染色體填補(bǔ)缺失基因,由此產(chǎn)生兩個子代染色體,進(jìn)而結(jié)合父代染色體選擇兩個最優(yōu)子代染色體。聚類單元內(nèi)與聚類單元間的染色體局部映射交叉操作如圖3所示。

通過染色體選擇、交叉操作后,采用多項式變異[30]方法進(jìn)行變異操作。首先通過變異概率Pm從父代中選擇染色體進(jìn)行變異操作,然后在選擇出的父代染色體中隨機(jī)選擇兩個基因進(jìn)行交換,其余的基因隨機(jī)再生,最后檢查和移除重復(fù)基因并再生缺失基因以形成子代染色體。染色體多項式變異操作如圖4所示。

3.3.3 算法步驟 針對模型特點設(shè)計基于Kmeans時空聚類的GA-PSO 混合算法,具體步驟如下:

步驟1基于回收服務(wù)周期、智能回收箱地理位置與服務(wù)時間窗約束,應(yīng)用K-means時空聚類將各回收服務(wù)周期內(nèi)的智能回收箱指派為k個聚類單元,并設(shè)gen=1。

步驟2生成初始粒子,并采用不重復(fù)的自然數(shù)對染色體進(jìn)行編碼生成初始種群,初始化相關(guān)參數(shù)。其中包括:種群規(guī)模inn、交叉概率Pc、變異概率Pm、權(quán)重最大值wmax、權(quán)重最小值wmin、加速因子c1和c2,混合算法最大迭代次數(shù)max gen,精英迭代次數(shù)run max,精英個體數(shù)NN,并設(shè)置精英迭代次數(shù)run=1和聚類檢查迭代次數(shù)t=1。

步驟3染色體解碼后根據(jù)式(27)計算種群中各染色體適應(yīng)度值。

步驟4采用輪盤賭方法對種群進(jìn)行選擇操作,篩選出優(yōu)良的個體作為下一代的父體。

步驟5根據(jù)交叉概率Pc與變異概率Pm,在聚類單元內(nèi)與聚類單元間對種群中個體進(jìn)行局部映射交叉操作與多項式變異操作,改善種群質(zhì)量,保留較優(yōu)個體得到新的種群。

步驟6判斷精英迭代次數(shù)run 是否達(dá)到run max。若滿足,則采用精英迭代策略,即將GA算法中的NN個較優(yōu)染色體替換PSO 算法中NN個較差粒子,并設(shè)run=0;否則,直接進(jìn)入步驟7。

步驟7通過粒子更新機(jī)制尋找更優(yōu)個體最優(yōu)值與全局最優(yōu)值,并設(shè)置t=t+1。

步驟8判斷t是否達(dá)到最大迭代次數(shù)tmax。當(dāng)t達(dá)到tmax時,判斷每個回收服務(wù)周期內(nèi)聚類單元中的個體是否發(fā)生改變,若發(fā)生改變,則轉(zhuǎn)回步驟7進(jìn)行迭代,若未改變則進(jìn)入步驟9;當(dāng)t未達(dá)到tmax時,直接進(jìn)入步驟10。

步驟9記錄最優(yōu)個體與適應(yīng)度值。設(shè)置混合算法迭代次數(shù)gen=gen+1,精英迭代次數(shù)run=run+1。

步驟10重復(fù)步驟3～9,直至達(dá)到最大迭代次數(shù)max gen,終止算法并輸出優(yōu)化結(jié)果。

3.4 小規(guī)模算例驗證

為驗證GA-PSO 混合算法的計算性能,在30 km×30 km 范圍內(nèi)隨機(jī)生成了10 組包含智能回收箱地理位置的算例數(shù)據(jù),其中:1～5組算例包含20個智能回收箱,單位產(chǎn)品回收定價為0.8元,產(chǎn)品回收頻次為1 次,產(chǎn)品回收數(shù)量和時間窗從Solomon數(shù)據(jù)集C101 中[31]隨機(jī)選取;6～10 組算例包含30個智能回收箱,單位產(chǎn)品回收定價為1.2元,產(chǎn)品回收頻次為1次或2次,產(chǎn)品回收數(shù)量和時間窗從Solomon 數(shù)據(jù)集R101 中[31]隨機(jī)選取。此外,為了有效驗證混合算法的性能,在小規(guī)模算例計算部分不考慮單位回收產(chǎn)品收益和清潔成本的變量設(shè)定。選取ILOG CPLEX 12.10軟件和本文提出的GA-PSO 混合算法求解上述10組算例。其中,1～5組和6～10組算例的CPLEX 軟件最長求解時間分別設(shè)置為1 800 s和3 600 s,而GA-PSO 算法用于求解每個算例10次并選取已知的最優(yōu)解,GAPSO 混合算法的參數(shù)設(shè)置見表4。相關(guān)計算結(jié)果如表3所示。

表3 小規(guī)模算例的計算比較結(jié)果

由表3可見,在不同數(shù)據(jù)規(guī)模環(huán)境下,本文提出的GA-PSO 混合算法可以在較短時間內(nèi)獲得最優(yōu)解或近似最優(yōu)解,而CPLEX 需要花費較長的計算時間。在算例1～5 中,GA-PSO 混合算法在35 s計算時間內(nèi)均可獲得最優(yōu)解,而CPLEX 獲得優(yōu)化解則需要700 s左右。在算例6～10 中,GA-PSO混合算法可以獲得算例6、8和9的最優(yōu)解,而求得算例7和10的優(yōu)化解與最優(yōu)解的差值比例分別為1.2%和1.1%。此外,CPLEX 和GA-PSO 混合算法求解10組算例的平均逆向物流運營成本分別為1 201.6元和1 205.2元,成本差值的均值為0.2%。因此,本文設(shè)計的GA-PSO 混合算法計算結(jié)果穩(wěn)定,在獲得最優(yōu)解方面具有時間優(yōu)勢。

3.5 算法比較分析

為進(jìn)一步驗證GA-PSO 算法的優(yōu)越性,將該算法與混合遺傳算法(HGA)[32]、遺傳-禁忌搜索混合算法(GA-TS)[33]和混合蟻群算法(HACO)[34]進(jìn)行比較。其中,文獻(xiàn)[32]中提出的HGA 算法主要用于求解帶時間窗的多回路車輛路徑問題,設(shè)計了基于多回路車輛路徑的染色體生成、選擇和序列編碼機(jī)制,并用于本文基于車輛共享調(diào)度的多頻次回收路徑染色體編碼設(shè)計求解。文獻(xiàn)[34]中提出的HACO 算法主要用于求解帶軟時間窗的多目標(biāo)車輛路徑問題,設(shè)計了基于變異算子的蟻群算法獲取多目標(biāo)函數(shù)的帕累托優(yōu)化解,并用于求解本研究涉及的回收中心物流運營成本最小和回收收益最大的雙目標(biāo)優(yōu)化解。此外,本文提出的GA-PSO 混合算法可以分別擴(kuò)展染色體編碼設(shè)計和結(jié)合雙目標(biāo)的帕累托優(yōu)化解求解上述兩篇文獻(xiàn)的相關(guān)問題,并可取得滿意的優(yōu)化結(jié)果。上述4種對比算法相關(guān)參數(shù)設(shè)置如表4所示。

表4 算法參數(shù)設(shè)置

從Solomon數(shù)據(jù)集[31]選取了20組求解規(guī)模分別為80、100、120的隨機(jī)測試數(shù)據(jù),并分配不同的定價方案進(jìn)行計算,其中實驗數(shù)據(jù)對應(yīng)的Solomon數(shù)據(jù)集、智能回收箱個數(shù)、回收產(chǎn)品定價方案及其對應(yīng)的回收頻次如表5所示。此外,為了算法比較和計算的正確性,本部分不涉及單位回收產(chǎn)品收益和清潔成本的變量設(shè)定。

表5 實例數(shù)據(jù)特征

在不同規(guī)模與定價方案下將4種算法的每組實例數(shù)據(jù)分別計算10次,并選取最優(yōu)值對應(yīng)的計算結(jié)果進(jìn)行比較,算法比較結(jié)果如表6所示。

由表6可見,在不同求解規(guī)模與回收產(chǎn)品定價下,本文提出的基于K-means時空聚類的GA-PSO算法在逆向物流運營成本,回收車輛的使用數(shù)和算法計算時間方面所得結(jié)果均優(yōu)于HGA、GA-TS和HACO 算法。其中,基于K-means 時空聚類的GA-PSO 算法計算所得的逆向物流運營成本均值比HGA 算法下降了8.6%,比GA-TS 算法下降了3.6%,比HACO 算法下降了6.2%;由GA-PSO、HGA、GA-TS和HACO 算法求解得出的平均車輛使用數(shù)分別為10輛、12輛、11輛 和11輛。此外,GA-PSO 算法的平均計算時間為197 s,而HGA、GA-TS和IACO 算法的平均計算時間分別為266 s、225 s和246 s。由t檢驗和P值的統(tǒng)計分析所得,GA-PSO 算法與其他3種算法有顯著差異。因此,本文所設(shè)計的基于K-means時空聚類的GAPSO 算法較其他3種算法的搜索性能更優(yōu)。

表6 算法比較結(jié)果

4 實例分析

4.1 實例相關(guān)數(shù)據(jù)

本文選取中型居民居住規(guī)模,以重慶市某回收中心(RC)及所服務(wù)的100個智能回收箱所在回收點(R1-R100)作為研究對象,實例相應(yīng)地理位置及智能回收箱所收集產(chǎn)品類型如圖5所示。以表2中3種回收產(chǎn)品為例,產(chǎn)品1 單位定價選取0.8 元、1.1元和1.6元,產(chǎn)品2單位定價選取0.5元和0.9元,產(chǎn)品3單位定價選取0.6元和1.0元,并設(shè)定回收產(chǎn)品1、2和回收產(chǎn)品3的清潔成本均為0.4元,其對應(yīng)的單位回收產(chǎn)品收益、回收量、單個回收箱回收頻次等相關(guān)數(shù)據(jù)如表7所示?；厥债a(chǎn)品對應(yīng)產(chǎn)品定價為(0.8,0.9,0.6)時單個回收箱回收量和回收頻次如表8所示。

表7 回收產(chǎn)品的定價類型與回收頻次

表8 回收產(chǎn)品對應(yīng)產(chǎn)品定價為(0.8,0.9,0.6)時的單個回收箱回收量和回收頻次

根據(jù)已有文獻(xiàn)[35-37]與多次實驗計算獲取的數(shù)據(jù),本文算法參數(shù)設(shè)置為:種群規(guī)模inn=100,混合算法最大迭代次數(shù)max gen=200,交叉概率Pc=0.8,變異概率Pm=0.2,加速因子c1=加速因子c2=3,權(quán)重最大值wmax=0.6,權(quán)重最小值wmin=0.3,精英迭代次數(shù)run max=100,精英個體NN=30,3種產(chǎn)品智能回收箱滿足收集狀態(tài)時的回收量分別為qi1=30,qi2=35和qi3=40,回收車輛提前到達(dá)回收點的單位時間懲罰系數(shù)μe=50,回收車輛延遲到達(dá)回收點的單位時間懲罰系數(shù)μd=40,1年中的工作周期數(shù)T=365,回收中心在第k個服務(wù)周期內(nèi)收集單位回收產(chǎn)品的固定回收成本Gik=30,回收品在第k個服務(wù)周期內(nèi)單位回收量的環(huán)境外部性收益Zjk=0.8,回收車輛的年平均維修成本Mv=18 000,回收車輛的最大載重Qv=400,回收車輛在第k個服務(wù)周期的單位距離運輸成本fvk=0.8。

將不同單位回收產(chǎn)品定價類型相組合,所得離散定價組合情況如表9所示,各離散定價組合的回收產(chǎn)品收集量情況如表10所示,其中,方案1為定價調(diào)整前的初始產(chǎn)品定價。

表9 回收產(chǎn)品單位回收定價組合方案

表10 不同組合方案的產(chǎn)品回收量

4.2 優(yōu)化結(jié)果及分析

以回收中心產(chǎn)品收益最大與逆向物流運營成本最小為雙目標(biāo),應(yīng)用基于K-means時空聚類的GA-PSO算法對表11中各離散回收產(chǎn)品定價組合方案分別進(jìn)行計算,同時結(jié)合目標(biāo)函數(shù)特點將回收中心產(chǎn)品收益與逆向物流運營成本的比值作為定價組合方案尋優(yōu)的評價指標(biāo)。各方案目標(biāo)函數(shù)計算結(jié)果如表11所示。

表11 各定價方案下回收中心的收益與物流運營成本

由表11可知,方案11的回收收益和回收成本之比為0.461,優(yōu)于其他定價方案。因此,方案11為最優(yōu)定價方案。此外,方案11的回收中心產(chǎn)品收益為3 984元,逆向物流運營成本為8 639元,并且此方案產(chǎn)品1的單位回收產(chǎn)品定價為1.6元,產(chǎn)品2為0.9元,產(chǎn)品3為0.6元。

在最優(yōu)定價方案中,首先,應(yīng)用K-means時空聚類算法并結(jié)合智能回收箱時間窗的分布特點劃分出回收服務(wù)周期區(qū)間;其次,在各回收服務(wù)周期內(nèi)對相應(yīng)智能回收箱進(jìn)行多回收單元的聚類操作。得到回收服務(wù)周期與聚類方案如表12所示,各回收服務(wù)周期內(nèi)時空聚類結(jié)果如圖6所示。

表12 各回收服務(wù)周期內(nèi)智能回收箱聚類方案

在回收聚類單元內(nèi)應(yīng)用GA-PSO 算法,計算得出該方案中各回收服務(wù)周期對應(yīng)的逆向物流運營成本和回收中心收集不同產(chǎn)品收益如表13所示。選取各回收頻次內(nèi)的車輛使用數(shù)、物流運營成本和回收中心產(chǎn)品收益進(jìn)行對比分析,如圖7所示。

表13 各服務(wù)頻次內(nèi)逆向物流運營成本和回收中心收益

由圖7對比分析可得,回收服務(wù)周期于6:00～14:00時段在車輛使用數(shù)、物流運營成本和回收中心產(chǎn)品收益方面均高于14:00～19:00 時段和19:00～23:00時段的相應(yīng)數(shù)值。其中,3個回收服務(wù)周期內(nèi)車輛使用數(shù)分別為6輛、4輛和2輛,回收中心回收成本分別為4 629元、2 946元和1 064元,回收中心產(chǎn)品收益分別為2 220元、1 260元和504元。在各回收服務(wù)周期內(nèi)應(yīng)用車輛共享調(diào)度策略,車輛共享情況與優(yōu)化后的回收路線如表14所示。

由表14可知,車輛V2、V4、V5和V6均參與車輛共享回收,其中車輛V4 和V5 服務(wù)于回收周期6:00～14:00,14:00～19:00和19:00～23:00,車輛V2和V6服務(wù)于回收周期6:00～14:00和14:00～19:00,其余回收車輛只服務(wù)于回收周期6:00～14:00。

表14 車輛共享調(diào)度回收優(yōu)化路線

應(yīng)用基于K-means時空聚類的GA-PSO 算法計算單位回收產(chǎn)品定價調(diào)整和車輛共享調(diào)度優(yōu)化前后回收中心產(chǎn)品收益和逆向物流運營成本,計算結(jié)果如表15所示。通過結(jié)果對比分析可知,單位回收產(chǎn)品定價調(diào)整和車輛共享調(diào)度優(yōu)化后,即定價調(diào)整為表9中的方案11,在滿足收集狀態(tài)回收箱的回收頻次與回收總量均增加44.4%的情況下,逆向物流運營成本有效降低9.9%,回收中心的回收收益相對增加16.1%,其中運輸成本和環(huán)境外部性收益分別增加20.3%和44.4%,違反時間窗懲罰成本分別降低42.7%。

表15 單位回收產(chǎn)品定價調(diào)整和車輛共享調(diào)度優(yōu)化前后回收中心產(chǎn)品收益和物流成本的比較

為進(jìn)一步驗證所選最優(yōu)定價方案的優(yōu)越性和基于車輛共享調(diào)度策略的多頻次路徑優(yōu)化的合理性,對比分析單位回收產(chǎn)品定價調(diào)整和車輛共享調(diào)度優(yōu)化前后的回收產(chǎn)品總量、運輸成本、違反時間窗成本、環(huán)境外部性收益、逆向物流運營成本和回收中心產(chǎn)品收益,如圖8所示。

由圖8可知,單位回收產(chǎn)品定價調(diào)整和車輛共享調(diào)度優(yōu)化后雖然運輸成本由7 273元增加至8 753元,但是由于違反時間窗的懲罰成本由3 654元降低至2 094元,環(huán)境外部性收益由1 944元增加至2 808元。因此,單位回收產(chǎn)品定價調(diào)整和車輛共享調(diào)度優(yōu)化后的逆向物流運營成本降低明顯,由9 583元降低至8 639元。同時,回收產(chǎn)品數(shù)量的大幅提升使得回收中心產(chǎn)品收益由3 432元增加為3 984元。

4.3 分析與討論

由于不同顧客對回收產(chǎn)品定價的敏感度不同,單位回收產(chǎn)品定價的不同選擇將改變智能回收箱的回收產(chǎn)品數(shù)量,進(jìn)而改變逆向物流運營成本和回收中心產(chǎn)品收益。本文采用車輛共享調(diào)度策略對多頻次回收路徑進(jìn)行優(yōu)化,分析各類型回收產(chǎn)品的不同定價對逆向物流運營成本和回收中心產(chǎn)品收益的影響,并對回收產(chǎn)品定價進(jìn)行敏感度分析,探討回收頻次與車輛共享情況,逆向物流運營成本以及回收中心產(chǎn)品收益的相關(guān)關(guān)系。

以本文選取的3種回收產(chǎn)品為例,假設(shè)各回收點的地理位置和服務(wù)時間窗等信息不變,將表2中產(chǎn)品1的單位回收定價設(shè)置為0.8～1.4元,產(chǎn)品2設(shè)置為0.5～1.1元,產(chǎn)品3設(shè)置為0.6～1.2元,進(jìn)而計算不同回收定價下各類回收產(chǎn)品對應(yīng)的逆向物流網(wǎng)絡(luò)的車輛使用數(shù),以及逆向物流運營成本和回收中心產(chǎn)品收益。計算結(jié)果如表16所示。

由表16可知,各類型回收產(chǎn)品的回收頻次存在差異,在相同的定價增長區(qū)間內(nèi),產(chǎn)品1存在3種回收頻次,而產(chǎn)品2和產(chǎn)品3僅有兩種,由此可知,顧客對產(chǎn)品1的回收定價更為敏感。選取表18中3種回收產(chǎn)品不同回收定價下對應(yīng)回收線路數(shù)與共享車輛使用數(shù),分析不同定價下各類回收產(chǎn)品的共享車輛使用數(shù)和回收車輛線路數(shù),如圖9所示。

表16 3類回收產(chǎn)品不同定價下的逆向物流運營成本與回收中心產(chǎn)品收益

由圖9可知,隨著各類回收產(chǎn)品定價的增長,其回收車輛線路數(shù)總體呈上升趨勢,當(dāng)產(chǎn)品1單位回收定價由0.8元上升至1.4元,產(chǎn)品2單位回收定價由0.5元上升至1.1元時,其回收車輛線路數(shù)均由2條增加至4條;當(dāng)產(chǎn)品3單位回收定價由0.6元上升至1.2 元時,其回收車輛線路數(shù)由3 條增加至4條,而考慮車輛共享調(diào)度策略的車輛使用數(shù)變化不大,其中收集產(chǎn)品1和產(chǎn)品2所使用的車輛數(shù)為1輛或2輛,收集產(chǎn)品3所使用的車輛數(shù)為2輛或3輛。因此,車輛共享調(diào)度策略有效集成了物流資源,為回收中心節(jié)約了更多的運營成本。此外,不同定價下各類回收產(chǎn)品逆向物流運營成本與回收中心產(chǎn)品收益的變化情況,如圖10所示。

由圖10可知,當(dāng)產(chǎn)品1單位回收定價由0.8元上升至1.4元,產(chǎn)品2單位回收定價由0.5元上升至1.1元,產(chǎn)品3 單位回收定價由0.6 元上升至1.2元時,3種回收產(chǎn)品的逆向物流運營成本均會相應(yīng)減少,其中,產(chǎn)品1的逆向物流運營成本由3 020元降低至2 352元,產(chǎn)品2由3 102元降低至2 401元,產(chǎn)品3由2 871元降低至2 057元。此外,由于顧客對3種產(chǎn)品的回收定價敏感程度存在差異,使其回收中心產(chǎn)品收益的變化有所差別,其中,產(chǎn)品1的回收中心產(chǎn)品收益由1 140元提高至1 512元,產(chǎn)品2的回收中心產(chǎn)品收益穩(wěn)定在1 153～1 272元,而產(chǎn)品3的回收中心產(chǎn)品收益在887～1 178元之間起伏。因此,適當(dāng)調(diào)整單位回收產(chǎn)品定價和進(jìn)行不同產(chǎn)品定價的合理組合,并結(jié)合車輛共享策略進(jìn)行多頻次的逆向物流車輛路徑優(yōu)化,在有效降低逆向物流回收運營成本的同時能為回收中心帶來了更高的收益,進(jìn)而有效整合了物流資源,提高了回收效率。

5 結(jié)論

本文研究了基于產(chǎn)品回收定價的逆向物流車輛路徑優(yōu)化問題,通過構(gòu)建智能回收箱回收量與回收定價的線性函數(shù)分析了不同定價下的回收量情況。將多頻次回收與車輛共享策略相結(jié)合,建立了以回收中心產(chǎn)品收益最大化和逆向物流運營成本最小化的雙目標(biāo)模型,并設(shè)計了基于K-means時空聚類的GA-PSO 混合算法對模型進(jìn)行優(yōu)化求解。該算法根據(jù)智能回收箱時間窗分布與地理位置信息進(jìn)行聚類操作,并將遺傳算法全局搜索能力強(qiáng)與粒子群算法收斂速度快的算法優(yōu)勢相結(jié)合增強(qiáng)了混合算法的多樣性。同時,應(yīng)用精英保留策略將算法迭代過程中較優(yōu)個體替代較差個體,進(jìn)而增強(qiáng)了算法搜索性能,并將GA-PSO 算法與HGA、GA-TS 和HACO 算法進(jìn)行優(yōu)化求解對比分析,進(jìn)一步驗證了本文所提出的混合算法的有效性。

本文以重慶市某智能回收物流網(wǎng)絡(luò)為例,將3種回收產(chǎn)品的不同定價進(jìn)行組合優(yōu)化,通過對基于回收定價的模型計算,驗證了模型與算法的有效性。結(jié)果表明,當(dāng)產(chǎn)品1的單位回收定價為1.6元,產(chǎn)品2的單位回收定價0.9元,產(chǎn)品3的單位回收定價0.6元時為最優(yōu)定價方案,其中優(yōu)化后的回收中心產(chǎn)品收益和回收總量分別增加了16.1%和44.4%,逆向物流運營成本有效降低9.9%。此外,對3種回收產(chǎn)品類型不同定價下共享車輛使用數(shù)、逆向物流運營成本和回收中心產(chǎn)品收益進(jìn)行敏感度分析,結(jié)合車輛共享調(diào)度策略可使回收頻次增加和保持車輛使用數(shù)不變,并可有效降低逆向物流運營成本,且通過分析可知,回收中心的收益與顧客對不同類型產(chǎn)品的回收定價敏感度存在一定的相關(guān)性。本文為研究基于產(chǎn)品回收定價的逆向物流車輛路徑優(yōu)化問題提供了新思路,有較強(qiáng)的理論意義和應(yīng)用價值。