考慮顧客滿意度的多目標(biāo)車輛路徑優(yōu)化問題

呂垚遠(yuǎn),張春美

(太原科技大學(xué) 電子信息工程學(xué)院,太原 030024)

車輛路徑問題(vehicle routing problem,VRP)[1]由Dantzing和Ramser于1959年首次提出,引起了大量學(xué)者的關(guān)注。隨著對(duì)傳統(tǒng)車輛路徑問題及其變體的深入研究,對(duì)于車輛到達(dá)時(shí)間及配送目標(biāo)的個(gè)數(shù)越來越有所要求,便提出了有時(shí)間窗的車輛路徑問題(VRP with time windows,VRPTW)[2]及多目標(biāo)車輛路徑問題(multi-objective vehicle routing problem,MOVRP)[3].文獻(xiàn)[4]根據(jù)車輛路徑問題的特征設(shè)計(jì)了一種二維編碼方式,并應(yīng)用懲罰函數(shù)構(gòu)建了以車輛行駛總費(fèi)用最小為目標(biāo)的單目標(biāo)數(shù)學(xué)模型,利用改進(jìn)狼群算法求解了該問題。文獻(xiàn)[5]建立了生鮮農(nóng)產(chǎn)品多隔室車輛路徑優(yōu)化模型,并通過對(duì)初始解生成方式的重新設(shè)計(jì)并加入局部搜索策略,重新設(shè)計(jì)了一種改進(jìn)粒子群算法,求解了以生鮮農(nóng)產(chǎn)品配送成本最小化為目標(biāo)的單目標(biāo)車輛路徑問題。然而,這些智能啟發(fā)式算法[6]的應(yīng)用還尚在求解單目標(biāo)車輛路徑問題的階段?？紤]到實(shí)際生活物流配送過程中顧客對(duì)服務(wù)的滿意程度、配送成本、車輛利用率等多個(gè)問題,單一目標(biāo)的物流配送已經(jīng)不再能滿足越來越復(fù)雜的物流配送任務(wù)。

差分進(jìn)化算法(Differential Evolution,DE)[7]最初是由Rainer Storn和Kenneth Price于1996年共同提出的在連續(xù)空間中進(jìn)行隨機(jī)搜索的優(yōu)化算法,如今,差分進(jìn)化算法及其變體被不斷提出,并廣泛應(yīng)用于解決現(xiàn)實(shí)生活中的離散問題。文獻(xiàn)[8]建立了帶時(shí)間窗的車輛路徑問題混合整數(shù)規(guī)劃模型,設(shè)計(jì)了一種整數(shù)序規(guī)范的輔助算子解決變異問題,應(yīng)用改進(jìn)的差分進(jìn)化算法實(shí)現(xiàn)了車輛與路徑的雙目標(biāo)優(yōu)化。但是,對(duì)于目標(biāo)函數(shù)的處理采用了一種加權(quán)的方法將多目標(biāo)轉(zhuǎn)化為了單目標(biāo),對(duì)于多目標(biāo)的優(yōu)化并沒有很好的展現(xiàn)出來。帶精英策略的非支配排序遺傳算法(NSGA-Ⅱ)由Deb等人于2000年提出,在遺傳算法的基礎(chǔ)上提出了非支配排序策略,降低了其算法復(fù)雜度,并引入精英策略提高種群的多樣性。文獻(xiàn)[9]建立以顧客滿意度最大及企業(yè)配送成本最小的多目標(biāo)數(shù)學(xué)模型,分析了顧客對(duì)配送滿意程度的影響因素,利用NSGA-Ⅱ算法對(duì)模型進(jìn)行了求解。文獻(xiàn)[10]通過對(duì)初始種群確定及交叉算子的改進(jìn),提出一種改進(jìn)的NSGA-Ⅱ算法,求解了以配送路徑最短、綜合費(fèi)用最低的多目標(biāo)車輛路徑問題。

傳統(tǒng)的物流配送車輛路徑問題大多數(shù)是從物流企業(yè)的角度出發(fā)考慮顧客對(duì)于配送服務(wù)的時(shí)間要求,較少考慮顧客對(duì)于不同時(shí)間段的配送滿意程度,且現(xiàn)有的多目標(biāo)車輛路徑問題一般以總行駛路徑或配送成本最小化為目標(biāo),缺乏綜合考慮配送過程中多個(gè)目標(biāo)函數(shù)的優(yōu)化。本文引入顧客滿意度函數(shù),考慮車輛到達(dá)時(shí)間對(duì)顧客滿意程度的影響,建立以最小化車輛行駛距離與使用車輛數(shù),及最大化客戶滿意度為目標(biāo)的多目標(biāo)數(shù)學(xué)模型,提出一種與變鄰域搜索相結(jié)合的混合差分進(jìn)化算法對(duì)模型進(jìn)行求解,并與常用于多目標(biāo)車輛路徑問題求解的NSGA-Ⅱ算法進(jìn)行對(duì)比,驗(yàn)證算法的有效性?；趯?shí)地調(diào)研數(shù)據(jù)構(gòu)建算例,利用所提出算法對(duì)其進(jìn)行求解,并找到一組最優(yōu)路線及相對(duì)于各目標(biāo)平均值較優(yōu)的折衷行駛路線。

1 多目標(biāo)VRPTW的問題描述及模型建立

1.1 問題描述

假設(shè)所有的車輛類型相同且載重量相同,根據(jù)文獻(xiàn)[11],本文所研究的問題應(yīng)該滿足以下5個(gè)條件:

(1)所有車輛服務(wù)完路徑上的所有客戶后回到它的起點(diǎn)——單一的配送中心。

(2)每個(gè)客戶有且只有一輛車為其服務(wù),但是每輛車可以服務(wù)多個(gè)客戶。

(3)任意一條配送路線上所有客戶的需求量之和不能超過配送車輛的最大載重量。

(4)任意一輛車配送過程中的運(yùn)輸時(shí)間不能超過最大運(yùn)輸時(shí)間T.

(5)時(shí)間窗約束:客戶接受服務(wù)的最早時(shí)間為ci,最晚接受服務(wù)的時(shí)間為di,即顧客允許接受服務(wù)的時(shí)間在[ci,di]的時(shí)間窗內(nèi)。

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

1.2.1 引入顧客滿意度

令顧客i接受配送服務(wù)的時(shí)段在[ai,bi]的時(shí)間窗內(nèi)。實(shí)際生活中,如果車輛因?yàn)橐恍┮蛩卦跁r(shí)間窗[ai,bi]以外的時(shí)刻到達(dá),此時(shí)客戶仍然會(huì)接受服務(wù),但對(duì)配送的滿意程度會(huì)降低,于是本文引入了顧客滿意度[12]這一概念。假設(shè)客戶允許接受服務(wù)的最早時(shí)間為ci,能接受服務(wù)的最晚時(shí)間為di.

車輛在時(shí)間窗[ai,bi]內(nèi)到達(dá)顧客點(diǎn)處,此時(shí)顧客的滿意度最大;若車輛在時(shí)間窗[ai,bi]之外到達(dá),但到達(dá)的時(shí)間窗仍然在ci和di之間,顧客仍然接受服務(wù),但對(duì)于服務(wù)的滿意度隨之下降。基于時(shí)間窗的顧客滿意度函數(shù)如圖1所示。

圖1 顧客滿意度函數(shù)圖Fig.1 The customer satisfaction function chart

圖2 擂臺(tái)法則示意圖Fig.2 Schematic diagram of challenge rules

引入顧客滿意度函數(shù)如下式所示:

(1)

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

令K={1,2,3,…,m}為配送中心車輛的集合和客戶的集合N={1,2,3,…n}(配送中心定義為1);每輛車的最大載重量為Q,最大工作時(shí)間為T;車輛到達(dá)客戶i的時(shí)刻為ti,顧客接受配送服務(wù)的軟時(shí)間窗為[ci,di];客戶i到客戶j的距離為Dij,從客戶i到客戶j的行駛時(shí)間為tij;第j個(gè)客戶需要配送的貨物量為qi,服務(wù)時(shí)間為si,等待時(shí)間為wi;S為某一車輛的配送客戶集合,|S|表示集合中所包含頂點(diǎn)的個(gè)數(shù)。

決策變量:

目標(biāo)函數(shù):

(2)

(3)

(4)

約束條件:

(5)

(6)

(7)

(8)

(9)

(10)

(11)

ci≤ti+wi≤di,i∈{1,2,…,n+1}

(12)

wi={ci-ti,0},i∈{1,2,…,n+1}

(13)

式(2)和式(3)分別為要求車輛運(yùn)輸距離和車輛數(shù)最少的目標(biāo)函數(shù);式(4)表示最大化平均顧客滿意度;式(5)表示車輛載重約束;式(6)表示任意一個(gè)客戶的配送服務(wù)只能由一輛車完成;式(7)表示配送車輛從配送中心出發(fā),在完成配送服務(wù)后返回配送中心;式(8)表示車輛對(duì)客戶i完成配送服務(wù)后服務(wù)客戶j;式(9)表示車輛在完成客戶j的配送任務(wù)之前服務(wù)客戶i;式(10)表示消除子回路。式(11)表示任意一輛車完成配送的運(yùn)輸時(shí)間不能超過最大運(yùn)輸時(shí)間; 式(12)為車輛開始服務(wù)時(shí)刻在時(shí)間窗范圍內(nèi);式(13)為等待時(shí)間表達(dá)式。

本文研究多目標(biāo)車輛路徑問題主要包含三個(gè)目標(biāo),分別為總的行駛距離最短,車輛使用數(shù)最少,以及顧客滿意度最大。為了求解方便,即最后能同時(shí)得到三個(gè)目標(biāo)函數(shù)的最小值或者最大值,于是本文在求解的時(shí)候目標(biāo)函數(shù)取顧客滿意度的倒數(shù),從而能夠使得最后求得的解(三個(gè)目標(biāo)函數(shù))都能同時(shí)得到最小或者最大。

2 改進(jìn)后的混合差分進(jìn)化算法

2.1 擂臺(tái)法則

擂臺(tái)法則[13]構(gòu)造非支配解集:

(1)從當(dāng)前初始解集中先選出一個(gè)個(gè)體作為擂主(一般為當(dāng)前解集的第一個(gè)解或第二個(gè)解);

(2)將選出的擂主與當(dāng)前解集中的解逐一進(jìn)行比較,將被支配者淘汰出局,非支配解將作為新的擂主再與解集中的其他解進(jìn)行比較直至結(jié)束;

(3)重復(fù)比較過程,直至當(dāng)前構(gòu)造解集為空,篩選出最終的非支配解集。

(4)若在解與解的比較過程中出現(xiàn)了更替現(xiàn)象(即擂主被更換了一次以上),這時(shí)需要記錄并保留更替發(fā)生時(shí)的當(dāng)前解集和新的擂主,因?yàn)樾碌睦拗髋c更替現(xiàn)象發(fā)生時(shí)被保留下來的解有可能并不是互不相關(guān)的關(guān)系,反而可能會(huì)相互支配。這種情況下,最新比較出的擂主必須與之前被保留下來的個(gè)體再進(jìn)行比較,并清除被它所支配的個(gè)體。

2.2 染色體編碼設(shè)計(jì)

采用針對(duì)于車輛路徑問題的自然數(shù)編碼方式,將差分進(jìn)化算法離散化用于解決離散空間的實(shí)際問題。任意一條染色體S用(g1,g2,g3,…,gn)來表示,第i個(gè)顧客點(diǎn)用染色體的基因位gi來表示。這樣的編碼方式不僅能夠體現(xiàn)車輛訪問顧客點(diǎn)的順序,還能夠保證每輛車只訪問每個(gè)顧客點(diǎn)一次。1表示配送中心,k表示車輛數(shù),從第一個(gè)顧客點(diǎn)開始,對(duì)配送車輛的容量和時(shí)間窗約束進(jìn)行檢驗(yàn),若滿足所有約束則將該顧客點(diǎn)加入路徑中,然后考慮下個(gè)顧客點(diǎn),否則,重新使用新的車輛服務(wù)該顧客。這種編碼方式可以更直觀地反映出車輛數(shù)量以及路徑的劃分,從而更方便地對(duì)車輛數(shù)量和車輛路徑進(jìn)行自動(dòng)尋優(yōu)。例如染色體串4 7 5 8 6 2 3 9,可以編碼為(1,4,7,1,5,8,6,1,2,3,9,1),即表示有三輛車,行駛路徑分別為(4→7),(5→8→6),(2→3→9).

2.3 改進(jìn)變異策略

針對(duì)車輛路徑問題重新設(shè)計(jì)變異操作產(chǎn)生變異個(gè)體,增加不同解的個(gè)數(shù)從而保證種群的多樣性,避免算法陷入局部最優(yōu),即“早熟”現(xiàn)象。

隨機(jī)生成兩個(gè)顧客點(diǎn)位隨機(jī)數(shù),交換兩個(gè)隨機(jī)數(shù)所對(duì)應(yīng)的這兩個(gè)顧客點(diǎn),產(chǎn)生新的變異個(gè)體。

改進(jìn)后的變異策略如圖3所示:

圖3 變異操作示意圖Fig.3 Variation operation diagram

2.4 改進(jìn)交叉策略

為避免傳統(tǒng)的單點(diǎn)交叉造成的非法子代及基本差分進(jìn)化算法因交叉的父代個(gè)體相同而不能產(chǎn)生新子代的缺點(diǎn),設(shè)計(jì)一種以隨機(jī)的交叉點(diǎn)進(jìn)行自定義交叉的交叉算子。改進(jìn)后的交叉算子圖如圖4所示。

圖4 交叉算子示意圖Fig.4 The schematic diagram of crossover operator

圖5 局部搜索過程示意圖Fig.5 Schematic diagram of local search process

對(duì)傳統(tǒng)交叉策略進(jìn)行改進(jìn),改進(jìn)后的交叉策略:

(1)隨機(jī)選擇兩個(gè)序列Q1和Q2進(jìn)行交叉,并隨機(jī)產(chǎn)生兩個(gè)交叉點(diǎn)X和Y.

(2)把交叉點(diǎn)Y后的序列移動(dòng)至原序列的最前面,得到新個(gè)體Q3和Q4.

(3)將Q1與Q2的交叉部分分別移動(dòng)至Q4的尾部和Q3的首部。

(4)將與交叉片段相同的部分消去,得到Q5和Q6兩個(gè)新的個(gè)體。

2.5 變鄰域的局部搜索策略

變鄰域搜索(VNS)由Hansen等學(xué)者于1997年提出,基本思想是通過不同的鄰域結(jié)構(gòu)進(jìn)行搜索,不斷提高解的質(zhì)量,具有較強(qiáng)的局部搜索能力。混合差分進(jìn)化算法局部搜索執(zhí)行變鄰域的局部搜索過程,擴(kuò)展當(dāng)前解的搜索空間,減小算法陷入局部最優(yōu)的可能,平衡算法的尋優(yōu)能力。采用兩種鄰域搜索算子產(chǎn)生鄰域解。當(dāng)不能繼續(xù)改進(jìn)當(dāng)前解時(shí),局部搜索過程結(jié)束。

鄰域結(jié)構(gòu):

(1)互換鄰域:在自然數(shù)編碼的顧客序列中隨機(jī)選擇兩個(gè)顧客點(diǎn)位a和b,將這兩個(gè)位置對(duì)應(yīng)的顧客點(diǎn)交換。

(2)插入鄰域:在自然數(shù)編碼的顧客序列中隨機(jī)選擇兩個(gè)顧客點(diǎn)位,把點(diǎn)位a對(duì)應(yīng)的顧客點(diǎn)抽出并插入到位置b.

混合差分進(jìn)化算法流程圖如圖6所示。

圖6 混合差分進(jìn)化算法流程圖Fig.6 The flow chart of hybrid differential evolution algorithm

3 實(shí)驗(yàn)與分析

3.1 算例描述與參數(shù)設(shè)置

采用20個(gè)配送點(diǎn)為例,通過Matlab R2018a對(duì)本文算法DDE-VNS及NSGA-Ⅱ算法進(jìn)行求解,20個(gè)配送點(diǎn)信息取自北京燕京啤酒部分營銷數(shù)據(jù)。測(cè)試算例中各參數(shù)設(shè)定情況如下:用自重為8 t,最大載重量為20 t,車速為50 km/h的車向20個(gè)客戶提供服務(wù),每輛車的最大運(yùn)行時(shí)間T為8 h,在每個(gè)客戶點(diǎn)處的服務(wù)時(shí)間為0.4 h.配送中心坐標(biāo)為(30 km,30 km).算法的實(shí)驗(yàn)參數(shù)設(shè)置:維數(shù)20,種群規(guī)模為100,最大迭代次數(shù)為1 000,鄰域解搜索最大次數(shù)為100,客戶數(shù)據(jù)以及每輛車的服務(wù)時(shí)刻如表1所示。第一列為客戶點(diǎn)編號(hào),第二列為客戶點(diǎn)的橫縱坐標(biāo),即客戶點(diǎn)的位置,第三列為每個(gè)客戶點(diǎn)的需求量,第四列與第七列為硬時(shí)間窗限制,第五列與第六列為反應(yīng)顧客滿意度的軟時(shí)間窗限制。

表1 20個(gè)配送點(diǎn)的坐標(biāo)以及客戶需求量信息表

3.2 實(shí)驗(yàn)結(jié)果與分析

本文算法DDE-VNS及NSGA-Ⅱ算法分別運(yùn)行15次,兩種算法得到Pareto解前沿如圖7和圖8所示。

圖7 DDE-VNS算法Pareto解前沿Fig.7 The distribution of the mean value of Pareto solution

圖8 NSGA-Ⅱ算法Pareto解前沿Fig.8 Pareto solution frontier of NSGA-Ⅱ algorithm

由圖7及圖8可以看出,相較于NSGA-Ⅱ算法,DDE-VNS算法的Pareto解集中且最優(yōu)解數(shù)量更多,Pareto前沿具有更好的分布性及聚集性。兩種算法運(yùn)行結(jié)果如表2所示,DDE-VNS算法在平均顧客滿意度上相比于NSGA-Ⅱ算法提高3.1%,在平均路徑長度上提高了6.8%.

表2 兩種算法的運(yùn)行結(jié)果

本文算法DDE-VNS求解得到9組車輛最優(yōu)路線如圖9所示。

圖9 車輛最優(yōu)路線圖 Fig.9 Vehicle optimal roadmap

平均顧客滿意度為6.932 5,平均行駛路徑長度為349.39 km,平均用車輛數(shù)為4輛車。各目標(biāo)值相對(duì)平均值最優(yōu)的折衷行駛路線為路線8,其顧客滿意度為7.984 4,用車輛數(shù)為3輛,行駛距離為326.75 km.

滿足各目標(biāo)值較優(yōu)的折衷行駛路線為路線8,行駛路線圖如圖10所示:

圖10 折衷解行駛路線圖Fig.10 A compromise solution to the road map

4 結(jié)束語

研究多目標(biāo)VRPTW問題,是目前較為復(fù)雜的多目標(biāo)優(yōu)化問題,不僅難于實(shí)現(xiàn),而且目標(biāo)函數(shù)之間容易產(chǎn)生沖突,很難找到一組各方面都達(dá)到最優(yōu)的解,甚至應(yīng)用進(jìn)化算法來解決該問題都比較困難。本文為使得車輛路徑問題更貼近實(shí)際生活,在同時(shí)優(yōu)化車輛數(shù)及行駛距離的基礎(chǔ)上,增加了顧客對(duì)配送服務(wù)的滿意程度,即顧客滿意度最大化這一優(yōu)化目標(biāo)。針對(duì)該問題,在基本差分進(jìn)化算法的基礎(chǔ)上,通過采用針對(duì)于車輛路徑問題的自然數(shù)編碼和種群初始化方式,以及對(duì)變異算子和交叉算子的重新設(shè)計(jì),最后結(jié)合兩種鄰域結(jié)構(gòu)的局部搜索策略,設(shè)計(jì)了一種混合差分進(jìn)化算法。經(jīng)過算例求解,得到一組非支配解集及相對(duì)于各目標(biāo)平均值較優(yōu)的折衷行駛路線,實(shí)現(xiàn)了運(yùn)輸距離與車輛數(shù)、以及顧客滿意度的多目標(biāo)優(yōu)化。本文研究了帶時(shí)間窗的物流配送多目標(biāo)優(yōu)化問題,其目標(biāo)函數(shù)僅定義了顧客滿意度,運(yùn)輸距離及車輛數(shù),而在實(shí)際生活中,車輛的非滿載率、碳排放量、能量消耗等目標(biāo)函數(shù)都會(huì)影響物流配送方案的決策。如何實(shí)現(xiàn)物流配送中更多目標(biāo)的優(yōu)化以及如何正確處理好各個(gè)目標(biāo)之間的制約關(guān)系,將是今后進(jìn)一步研究的內(nèi)容。