基于顧客時間滿意度的車輛路徑問題

李常敏,陶 穎,彭 顯,姚連杰

(上海大學(xué)管理學(xué)院,上海200444)

1 提出問題

車輛路徑問題(vehicle routing problem,VRP)是物流配送研究中的核心部分,配送路線的選定對企業(yè)的配送成本起決定性作用.經(jīng)典VRP模型關(guān)注的是所有配送車輛的配送路徑最短、耗費(fèi)時間最少的配送方案[1],帶時間窗VRP(vehicle routing problem with time windows,VRPTW)是在經(jīng)典的VRP基礎(chǔ)上增加時間窗約束衍生而來的.VRPTW模型在日常生活中有著廣泛的應(yīng)用:銀行的運(yùn)鈔車調(diào)度、郵政配送、工廠廢棄物回收、校車路線和準(zhǔn)時化(just in time,JIT)生產(chǎn)調(diào)度問題等.

針對VRPTW的嚴(yán)格時間約束,Balakrishnan[2]提出了帶軟時間窗的VRP(VRP with soft time windows,VRPSTW)進(jìn)行改進(jìn),即在超出顧客規(guī)定的時段外,運(yùn)用該模型可以通過支付合理的懲罰來補(bǔ)償.武佳佳等[3]認(rèn)為,VRPSTW是在經(jīng)典的VRP基礎(chǔ)上增加了時間窗約束條件的一種變化形式:①客戶配送中心希望在服務(wù)時間內(nèi)服務(wù)時,客戶配送中心接受貨物且滿意度高,在客戶配送中心可接受服務(wù)時間內(nèi)服務(wù)時,對物流公司予以懲罰,并將此懲罰成本作為對客戶配送中心經(jīng)濟(jì)上的補(bǔ)償,從而給客戶配送中心一定的心理安慰并提高客戶滿意度;②在客戶配送中心拒絕接收時間內(nèi)提供服務(wù)時,客戶配送中心拒絕接受貨物.Manisri等[4]基于VRPSTW問題提出了多目標(biāo)優(yōu)化模型,其第一優(yōu)化目標(biāo)是在配送任務(wù)中使用的配送車輛數(shù)量最少,第二優(yōu)化目標(biāo)是全程配送時間最短,并使用混合算法對模型進(jìn)行求解.一般的軟時間窗口利用其靈活性,為廣泛的應(yīng)用程序定義各種交付成本函數(shù).然而,這個問題是高度復(fù)雜的.Beheshti等[5]提出了一個數(shù)學(xué)模型和一個高效的混合列生成元啟發(fā)式方法來解決這個復(fù)雜的問題.Tas等[6]進(jìn)一步將VRPSTW模型中的整個時段劃分為等待區(qū)、早到懲罰區(qū)、正常服務(wù)區(qū)、遲到懲罰區(qū)、不接受服務(wù)區(qū)5個區(qū)間,對早于早到懲罰區(qū)的等待區(qū)和晚于遲到懲罰區(qū)的不接受服務(wù)區(qū)都不接受配送.Tas等[7]又進(jìn)一步提出了求解VRPSTW模型的禁忌搜索和鄰域搜索算法,并用實(shí)際數(shù)據(jù)對算法進(jìn)行驗(yàn)算和分析.李進(jìn)等[8]研究了考慮碳排放和速度優(yōu)化的帶時間窗VRP,引入了基于速度的碳排放計(jì)算方法,以油耗、碳排放和旅行時間費(fèi)用最小化為目標(biāo),將速度作為決策變量,建立了混合整數(shù)規(guī)劃模型并提出了2階段啟發(fā)式算法:①第一階段采用改進(jìn)的禁忌搜索算法優(yōu)化配送網(wǎng)絡(luò)中的速度;②第二階段設(shè)計(jì)了弧段速度優(yōu)化算法用于優(yōu)化路徑弧段上的速度以尋求對最優(yōu)解的進(jìn)一步改進(jìn).李珍萍等[9]研究了多時間窗VRP,考慮了車容量、多個硬時間窗限制等約束條件,以動用車輛的固定成本和車輛運(yùn)行成本之和最小為目標(biāo),建立了整數(shù)線性規(guī)劃模型;根據(jù)智能水滴算法,設(shè)計(jì)了求解多時間窗VRP的快速算法,利用具體實(shí)例進(jìn)行了模擬計(jì)算,并與遺傳算法的計(jì)算結(jié)果進(jìn)行了對比分析,結(jié)果顯示智能水滴算法能夠以較高的概率得到全局最優(yōu)解.穆東等[10]為提高傳統(tǒng)串行模擬退火(simulated annealing,SA)算法求解時間依賴型VRP的效率,提出了一種并行模擬退火算法,該算法首先使用前向插入啟發(fā)式算法生成初始解,在主從式并行模擬退火算法框架下使用4種鄰域搜索法對初始解進(jìn)行優(yōu)化.采用Figliozzi測試數(shù)據(jù)庫對算法性能進(jìn)行測試,得到不同時間依賴型行駛函數(shù)情形,當(dāng)使用6個線程時并行模擬退火算法相對于傳統(tǒng)串行模擬退火算法可以得到近似于5倍的加速比,且均能在較快時間內(nèi)得到比Figliozzi算法更優(yōu)的解.

李想等[11]指出,SA算法是一種通用性很強(qiáng)的優(yōu)化算法,求解效果比其他啟發(fā)式算法好,并具有對初始參數(shù)設(shè)置不敏感的優(yōu)點(diǎn).李江偉等[12]指出,模擬退火算法具有較強(qiáng)的全局搜索能力,且不要求目標(biāo)函數(shù)為凸函數(shù),能夠以一定概率接受次最優(yōu)解,使得算法在迭代過程中不會像Hopfield神經(jīng)網(wǎng)絡(luò)一樣陷入局部最優(yōu).理論上只要初始的系統(tǒng)溫度夠高,溫度下降夠慢,迭代次數(shù)夠多,算法收斂于全局最優(yōu)解的概率就為100%.

任力[13]從最小化總成本和最大時間滿意度出發(fā),假設(shè)配送的時間服從不確定分布,利用不確定變量的期望、方差和熵提出了配送中心選址問題的新模型;基于Hamiki的結(jié)論給出了該模型的等價形式;通過數(shù)值例子驗(yàn)證了該模型的有效性.齊艷等[14]給出了顧客對產(chǎn)品或者服務(wù)的滿意度與顧客等待時間的線性和非線性函數(shù)關(guān)系式.韓瑜睿等[15]對研究選址問題的基本覆蓋模型進(jìn)行了詳細(xì)的分析和敘述,重點(diǎn)討論集覆蓋模型和最大覆蓋模型;對模型中用到的重要函數(shù)(時間滿意度函數(shù))進(jìn)行分析,并將其轉(zhuǎn)換為通過距離衡量滿意度的函數(shù).Li等[16]研究了考慮客戶滿意度的積極配送網(wǎng)絡(luò)的可靠性評估;建立了配送網(wǎng)絡(luò)的運(yùn)行優(yōu)化模型,旨在利用需求響應(yīng)來最大化配送網(wǎng)絡(luò)的運(yùn)營效益.

傳統(tǒng)的物流配送問題大多從物流配送企業(yè)的角度去同等看待所有顧客配送時間的要求,而忽略了顧客對特殊時段不同的滿意度水平.如何以顧客體驗(yàn)為導(dǎo)向,提升顧客滿意度,成為現(xiàn)代物流配送企業(yè)提升自身競爭優(yōu)勢的一個關(guān)鍵問題.然而在模型方面,大多數(shù)VRP研究都是基于出行成本的最小化為目的,而對于VRPTW和VRPSTW的研究大多假設(shè)各需求點(diǎn)的配送時間必須在一定范圍之內(nèi),早于或者晚于該范圍的都不能配送,這無疑與實(shí)際不符.另外在計(jì)算方面,在傳統(tǒng)的VRP問題中假設(shè)目標(biāo)函數(shù)是最小化配送路徑,所有需求點(diǎn)構(gòu)成一個完全圖,所有需求點(diǎn)滿足基本的幾何公理:2點(diǎn)之間線段最短,即配送路徑最短.但如果綜合考慮包括所有需求點(diǎn)的時間滿意度和配送路程的配送效益,對于所有需求點(diǎn)組成的網(wǎng)絡(luò)來說,其可行的最優(yōu)配送效益并不一定滿足2點(diǎn)之間的直接配送效益優(yōu)于經(jīng)過其余需求點(diǎn)的配送效益.鑒于以上分析,本工作將顧客滿意度水平定義為顧客對物流企業(yè)為其提供配送服務(wù)時間的滿意程度,物流企業(yè)通過盡量滿足所有顧客對配送時間段的要求獲得優(yōu)于競爭對手的優(yōu)勢;通過建立配送服務(wù)時間與顧客滿意度之間的函數(shù)關(guān)系式(稱作顧客時間滿意度函數(shù)),繼而將顧客對時間窗的限制轉(zhuǎn)化為顧客時間滿意度,將各需求點(diǎn)經(jīng)過且僅可經(jīng)過一次的約束放松為車輛可多次經(jīng)過需求點(diǎn),建立顧客時間滿意度配送模型(VRP with satisfaction,VRPWS),旨在配送過程中綜合考慮顧客滿意度和運(yùn)輸成本在內(nèi)的配送效益.該模型克服了傳統(tǒng)時間窗模型中對時間窗和需求點(diǎn)的限制缺陷,更有利于物流企業(yè)找到實(shí)際配送效益高的配送路徑方案.

2 VRPWS模型的建立

VRPWS模型是在經(jīng)典的VRP模型上,結(jié)合顧客時間滿意度函數(shù)衍生而來的.VRPWS問題的優(yōu)化目標(biāo)是使綜合考慮配送成本和顧客滿意度的配送效益最大,即在滿足約束條件的情況下,選擇適當(dāng)?shù)穆窂绞乖谶\(yùn)輸成本較低的同時顧客滿意度最大.

2.1 假設(shè)條件

2.1.1 顧客時間滿意度函數(shù)

在實(shí)際配送過程中,根據(jù)顧客對產(chǎn)品配送時段的要求,將顧客分為2類:對配送時間無特殊要求的顧客(類型1)和要求在特定時間段完成配送活動的顧客(類型2).2種類型的顧客的時間滿意度函數(shù)曲線如圖1所示.

圖1 顧客類型1與顧客類型2的時間滿意度函數(shù)Fig.1 Time satisfaction functions of customer type 1 and customer type 2

對于顧客類型1,有耐心等待期[0,ai]和焦躁等待期[ai,bi].如果顧客在耐心等待期[0,ai]內(nèi)收到產(chǎn)品,則時間滿意度為100%;顧客在焦躁等待期[ai,bi]內(nèi)收到產(chǎn)品,顧客時間滿意度會隨著收到時間與耐心等待時間之差增大而降低;而收到產(chǎn)品時間長于焦躁等待期,顧客的時間滿意度為0.對于顧客類型2,有期望時間段[ui,vi]和可接受配送時間段[ti,wi].如果顧客在期望時間段[ui,vi]內(nèi)收到產(chǎn)品,則滿意度為100%;顧客在[ti,ui]以及[vi,wi]內(nèi)收到產(chǎn)品,顧客時間滿意度會隨著收到時間與期望時間之差增大而降低;而在時間段[ti,wi]外收到產(chǎn)品,顧客時間滿意度為0.每個顧客對服務(wù)時間感知度不同,并且每次訂貨需求只有一種產(chǎn)品類型.顯然,從數(shù)學(xué)模型上來講,類型1是類型2的特殊情況.

2.1.2 車輛配送服務(wù)

配送車輛從一個配送中心出發(fā)服務(wù)多位顧客,當(dāng)完成該條線路上的顧客需求任務(wù)后仍返回配送中心,且已知車輛平均行駛速度,單位距離的運(yùn)輸成本固定,車輛禁止超載,車輛數(shù)目足夠.每個顧客對服務(wù)時間感知度不同,并且每次訂貨需求只有一種產(chǎn)品類型,且各需求點(diǎn)的需求量不超過配送車輛的最大載運(yùn)量.允許車輛經(jīng)過而不服務(wù)需求點(diǎn),但每個顧客只能被一輛車服務(wù)且僅服務(wù)一次,這與傳統(tǒng)的VRP模型及其衍生模型有較大區(qū)別.

2.2 符號定義

基于以上假設(shè),還需引入如下符號:

有向圖G=(V,E)為配送網(wǎng)絡(luò),其中V={0,1,···,n}為節(jié)點(diǎn)集,節(jié)點(diǎn)0為配送中心;V/{0}表示顧客節(jié)點(diǎn);

E={(i,j)|i,j鄰接,j∈V,i?=j}表示為配送路段集合,共有M 輛配送車,分別記為1,2,···,M;

Qmax為每輛配送車的最大載運(yùn)量;

vij為節(jié)點(diǎn)i到節(jié)點(diǎn)j的平均車速;

dij為節(jié)點(diǎn)i到節(jié)點(diǎn)j的配送路段距離;

tij為車輛從顧客節(jié)點(diǎn)i到達(dá)顧客節(jié)點(diǎn)j所需要的時間;

Ne為接受產(chǎn)品類型e的顧客節(jié)點(diǎn)集合;

μ為顧客的時間滿意度權(quán)重系數(shù),反映了企業(yè)對顧客滿意度的重視程度;

c為配送車的單位距離行駛時的運(yùn)輸成本(包括油費(fèi)、車輛維修保養(yǎng)費(fèi))；

x¨ym和yim為決策變量(當(dāng)x¨ym=1時,表示車輛m訪問弧(i,j),否則x¨ym=0;當(dāng)yim=1時,車輛m為顧客i配送產(chǎn)品,即為需求點(diǎn)i服務(wù),否則yim=0).

2.3 VRPWS模型構(gòu)建

本工作建立的VRPWS模型從顧客滿意度視角出發(fā),對VRP進(jìn)行深入研究.在制定配送路徑的過程中,考慮到顧客對配送時段的要求,本工作放寬了傳統(tǒng)的VRP模型中關(guān)于車輛經(jīng)過即被服務(wù)的限制,允許車輛多次經(jīng)過需求點(diǎn)但不一定服務(wù)該需求點(diǎn),具體模型如下:

約束條件：

式(1)為目標(biāo)函數(shù):滿意度權(quán)重系數(shù)乘以顧客滿意度減去運(yùn)輸成本;式(2)為配送車輛的載裝能力約束;式(3)和(4)表示車輛m可以多次經(jīng)過顧客節(jié)點(diǎn)i和顧客節(jié)點(diǎn)j,但不一定被服務(wù),放寬了傳統(tǒng)VRP模型中關(guān)于需求點(diǎn)經(jīng)過即被服務(wù)的限制;式(5)保證了每個顧客i只能被服務(wù)一次;式(6)表示從配送中心0處出發(fā)的配送車有M輛;式(7)表示行駛路徑的一致性;式(8)表示車輛服務(wù)順序,先到顧客節(jié)點(diǎn)i再到顧客節(jié)點(diǎn)j.

2.4 求解VRPWS模型的改進(jìn)模擬退火算法

模擬退火算法[13]是源于固體退火原理,相對于其他智能算法,模擬退火算法在求解傳統(tǒng)VRP問題時具有收斂速度快且能迅速找到全局最優(yōu)解的優(yōu)點(diǎn).一般算法容易局限于局部最優(yōu)解而停滯不前,而模擬退火算法是以一種概率的方式進(jìn)行搜索,增加了搜索過程的靈活性.考慮到VRPWS模型中目標(biāo)函數(shù)的非凸性,基于模擬退火算法的以上優(yōu)點(diǎn),修正模擬退火算法求解傳統(tǒng)VRP構(gòu)造的鄰域解中,默認(rèn)同一輛車最多經(jīng)過需求點(diǎn)一次的局限性,通過模擬退火算法給出各車輛的服務(wù)顧客順序點(diǎn)集合,按一定概率選取其中相鄰的2個服務(wù)點(diǎn),尋找最佳配送效益的配送路徑.模擬退火算法的內(nèi)循環(huán)中通過路徑間調(diào)整和路徑內(nèi)優(yōu)化構(gòu)造鄰域解,采用雙終止準(zhǔn)則來提升模擬退火算法的記憶功能和優(yōu)度.簡記將模型目標(biāo)函數(shù)記為配送效益Z.該問題在k步對應(yīng)的一個解zk以及配送效益Zk分別與固體的一個降溫時間Tk及其能量Ek等價.具體算法如下.

步驟1 設(shè)定初始溫度T0以及終止溫度Tz,令k=0,計(jì)算初始可行解zk.

步驟3使用2-opt法和插入法構(gòu)造VRPWS模型的鄰域解?zk.

步驟3.5 ePkn+N對應(yīng)的路徑路徑上各途徑點(diǎn)的到達(dá)時間由如下公式可得t?轉(zhuǎn)步驟4.

步驟4根據(jù)式(1)計(jì)算?zk下的配送效益值?Zk,如果?Zk>Zk,則令Zk=?Zk,轉(zhuǎn)步驟6;否則轉(zhuǎn)步驟5.

步驟7 zk為可接受的最優(yōu)解,Zk為相應(yīng)的最優(yōu)值.算法終止.

3 算例

本工作通過一個算例來比較VRPSTW模型、VRPTW模型和本工作提出的VRPWS模型,并對滿意度權(quán)重系數(shù)進(jìn)行敏感性分析.假定某快銷品公司的一個配送中心要向其服務(wù)范圍內(nèi)的10個需求點(diǎn)進(jìn)行貨物配送,配送中心與需求點(diǎn)信息如表1所示.配送中心共有10輛規(guī)格相同的配送車輛,載重量均為15 t,在配送過程中平均行駛速度為100 km/h,每輛車油耗及維護(hù)成本為1元/km,配送車在每個需求點(diǎn)的服務(wù)時間長度為6 min.由于產(chǎn)品類型1是產(chǎn)品類型2的特殊情況,故本工作假設(shè)VRPSTW模型中客戶要求配送的時間窗以及VRPWS模型中顧客的時間滿意度函數(shù)如圖2所示.

表1 配送中心與需求點(diǎn)信息Table 1 Distribution center and demand point informatim

圖2 VRPSTW中的時間窗與VRPWS中的顧客滿意度函數(shù)Fig.2 Time window in VRPSTW and customer’s satisfaction functions in VRPWS

VRPSTW時間窗與VRPWS顧客滿意度函數(shù)中的參數(shù)ti,ui,vi,wi分別為2,4,6,8 h.當(dāng)然在VRPSTW模型中,不接受配送超出最早配送時間和最晚配送時間范圍的客戶.

為研究滿意度權(quán)重系數(shù)的變化對配送效益的影響,選取不同的滿意度權(quán)重系數(shù)μ(其他條件均保持不變),求得的運(yùn)輸成本和顧客滿意值(見圖3).圖3中,運(yùn)輸成本數(shù)值=運(yùn)輸成本×103,權(quán)重系數(shù)數(shù)值=權(quán)重系數(shù)×102.

可見,當(dāng)權(quán)重系數(shù)取值從0到2 000變化時,運(yùn)輸成本、顧客滿意值以及配送效益都隨之發(fā)生了相應(yīng)的改變(見圖3).隨著權(quán)重系數(shù)的增大,顧客滿意度數(shù)值(顧客滿意值=滿意度權(quán)重系數(shù)×顧客滿意度)和運(yùn)輸成本也在增大.當(dāng)權(quán)重系數(shù)由0增大至500時,顧客滿意度增加顯著;但當(dāng)權(quán)重系數(shù)超過500之后,運(yùn)輸成本和顧客滿意值基本穩(wěn)定.可見,權(quán)重系數(shù)反映了企業(yè)對顧客滿意度的重視程度.上述結(jié)果表明,企業(yè)對顧客滿意度的重視程度對物流配送成本和顧客滿意度影響較大;但當(dāng)重視程度達(dá)到一定程度后,就不能通過提高重視程度來提升顧客滿意度了.因此,本工作將VRPWS模型中顧客時間滿意度權(quán)重系數(shù)μ設(shè)置為穩(wěn)定值500,并將VRPSTW模型中的懲罰系數(shù)也設(shè)置為500.

3.1 模擬退火算法參數(shù)選取

模擬退火算法中初始溫度(T0)、降溫系數(shù)(p)、終止溫度(Tz)參數(shù)分別取值為

圖3 權(quán)重系數(shù)變化對運(yùn)輸成本和顧客滿意值的影響Fig.3 Influence of variation of weight coefficient on transportation cost and customer satisfaction

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

基于以上參數(shù)的設(shè)置和選取,利用Matlab 7.0.1進(jìn)行求解,結(jié)果如表2所示.

表2 3類模型結(jié)果比較Table 2 Comparison results of the three models

通過比較3種模型可以發(fā)現(xiàn),在VRPSTW模型中,當(dāng)超出最早配送時間2和最晚配送時間8范圍的配送時間,不接受配送會導(dǎo)致其配送效益要遠(yuǎn)遠(yuǎn)低于VRPWS模型和VRPWS模型的配送效益;VRPTW模型和VRPWS模型相比較,二者的最優(yōu)配送路徑都需要4輛車來進(jìn)行,第3輛車和第4輛車的配送路徑完全一樣,由于VRPWS模型放寬了車輛經(jīng)過即被配送的限制,需求點(diǎn)10有2輛車經(jīng)過,但只有1輛車為其配送,盡管第2輛車多行駛了距離,但對于整個配送需求來說增強(qiáng)了顧客配送效益.與VRPSTW模型和經(jīng)過即被服務(wù)的VRPTW模型相比較,VRPWS模型將配送效益從VRPSTW模型的248.9和VRPTW模型的651.30提高到672.12,分別提高了170.0%和3.2%.可見,VRPWS模型以顧客時間滿意度的形式代替時間窗,通過放寬路徑假設(shè)范圍,使模型的配送效益更高,適用性更強(qiáng).

4 結(jié)束語

隨著電子商務(wù)的發(fā)展和時效性強(qiáng)的商業(yè)模式的出現(xiàn),在物流配送過程中考慮顧客的時間滿意度變得尤為重要.考慮在配送過程中顧客對于時間有較高的敏感性,本工作在車輛路徑優(yōu)化模型的基礎(chǔ)上,結(jié)合顧客時間滿意度,放寬對需求點(diǎn)和配送路徑關(guān)系的限制,建立了VRPWS模型;通過算例說明本工作所提出的VRPWS模型是可行且有效的,并且在一定程度上為物流企業(yè)保障顧客滿意度、降低運(yùn)輸成本提供方案.