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

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

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

1 提出問題

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

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

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

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

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

2 VRPWS模型的建立

VRPWS模型是在經典的VRP模型上,結合顧客時間滿意度函數衍生而來的.VRPWS問題的優化目標是使綜合考慮配送成本和顧客滿意度的配送效益最大,即在滿足約束條件的情況下,選擇適當的路徑使在運輸成本較低的同時顧客滿意度最大.

2.1 假設條件

2.1.1 顧客時間滿意度函數

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

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

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

2.1.2 車輛配送服務

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

2.2 符號定義

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

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

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

Qmax為每輛配送車的最大載運量;

vij為節點i到節點j的平均車速;

dij為節點i到節點j的配送路段距離;

tij為車輛從顧客節點i到達顧客節點j所需要的時間;

Ne為接受產品類型e的顧客節點集合;

μ為顧客的時間滿意度權重系數,反映了企業對顧客滿意度的重視程度;

c為配送車的單位距離行駛時的運輸成本(包括油費、車輛維修保養費)；

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

2.3 VRPWS模型構建

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

約束條件：

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

2.4 求解VRPWS模型的改進模擬退火算法

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

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

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

步驟3.5 ePkn+N對應的路徑路徑上各途徑點的到達時間由如下公式可得t?轉步驟4.

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

步驟7 zk為可接受的最優解,Zk為相應的最優值.算法終止.

3 算例

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

表1 配送中心與需求點信息Table 1 Distribution center and demand point informatim

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

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

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

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

3.1 模擬退火算法參數選取

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

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

3.2 實驗結果及分析

基于以上參數的設置和選取,利用Matlab 7.0.1進行求解,結果如表2所示.

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

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

4 結束語

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