考慮客戶滿意度的網(wǎng)購物流配送路徑優(yōu)化

趙銳， 胡雄， 何紅弟

(上海海事大學 科學研究院，上海 201306)

?

考慮客戶滿意度的網(wǎng)購物流配送路徑優(yōu)化

趙銳， 胡雄， 何紅弟

(上海海事大學 科學研究院，上海 201306)

為更全面地反映網(wǎng)購物流配送的客戶滿意度, 引入客戶滿意度指標.首先，考慮城市交通管制的硬時間窗約束和客戶要求的軟時間窗約束，建立最小配送成本和最短配送時間的多目標優(yōu)化模型；然后，引入客戶滿意度指標，并設定客戶滿意度閾值，對該模型進行優(yōu)化.設計遺傳算法求解該優(yōu)化模型.結合實際算例對模型和算法的有效性進行驗證.結果表明：優(yōu)化后的模型可以在保證較低配送成本和較少配送時間的基礎上，最大化配送服務的客戶滿意度水平.該方法不存在客戶流失的風險，有利于提高企業(yè)的競爭優(yōu)勢，符合企業(yè)的長遠利益.

客戶滿意度； 物流配送； 硬時間窗； 軟時間窗； 遺傳算法

0 引 言

隨著計算機網(wǎng)絡技術的創(chuàng)新和消費者消費觀念的轉變，電子商務得到突飛猛進的發(fā)展.電子商務的發(fā)展離不開現(xiàn)代物流的支撐，且物流配送路徑的選擇關系到企業(yè)的配送成本、配送效率和配送服務水平，因此對網(wǎng)購物流配送路徑進行優(yōu)化十分必要.

自DANTZIG等[1]首次提出車輛路徑問題以來，該領域已取得非常豐富的研究成果.配送成本和配送時間是車輛路徑問題的基本優(yōu)化對象，該領域的研究起步較早.VIDAL等[2]研究有裝載能力和路線約束的多節(jié)點車輛路徑問題，并采用一種混合遺傳算法(Genetic Algorithm，GA)進行求解.BATTARRA等[3]提出基于空間聚類車輛路徑問題的整數(shù)目標規(guī)劃模型，并采用分支切割算法求解.彭碧濤等[4]研究多時間窗車輛路徑問題，首先利用基本蟻群算法進行求解，然后采用加入變異算子的元胞自動機算法對結果進行優(yōu)化.DABIA等[5]通過選擇在合適的時間為客戶提供配送服務，減少配送所需時間和配送成本.胡繼雪[6]研究基于車輛路徑問題的配送分區(qū)優(yōu)化問題，并采用“先分區(qū)，再排程，后改進”的三階段算法進行求解.JIANG等[7]研究帶時間窗的多車型車輛路徑問題，并采用基于二階段法的禁忌搜索算法進行求解，但是該算法容易陷于局部最優(yōu).隨著客戶對配送服務要求的提高，簡單地對配送成本和配送時間進行優(yōu)化已難以滿足實際需求.胡云超等[8]對6種交通管制情境下的城市配送優(yōu)化綜合效益進行對比，發(fā)現(xiàn)城市貨運交通管制政策會增加企業(yè)的配送成本，但具有較好的社會效益.陳文強等[9]考慮由時間延遲所造成的貨物價值損失，對運輸和裝卸過程分別建模，然后聯(lián)合求解總目標.

企業(yè)間的競爭不僅僅是價格的競爭，更是服務的競爭.何嬋等[10]為衡量企業(yè)的服務水平，引入客戶滿意度指標.OLIVER等[11]認為當買到的產(chǎn)品與客戶預期相符時即產(chǎn)生客戶滿意度.李逸珩[12]建立基于客戶服務中心的運營商客戶感知和外部評價與客戶滿意度內(nèi)部管理相統(tǒng)一的客戶滿意度管理模型，形成可衡量的客戶滿意度評價體系.SZYMZNSKI等[13]認為在網(wǎng)絡零售行業(yè)，服務屬性可以驅動客戶滿意度.SINGH等[14]發(fā)現(xiàn)客戶滿意度對企業(yè)績效有極其重要的影響，但客戶滿意度在物流配送領域的研究中比較有限.鄧麗君[15]研究考慮客戶滿意度的物流配送車輛調度問題，并建立最小化運輸成本和最大化客戶滿意度的多目標優(yōu)化模型.

已有文獻對成本和時間的優(yōu)化及模型的求解研究得比較多，但是對衡量配送服務水平的客戶滿意度的研究比較少.在實際應用中，城市交通管制和回程取貨等實際常見問題也容易被忽略.因此，對考慮客戶滿意度的網(wǎng)購物流配送優(yōu)化問題進行研究具有重要的理論與現(xiàn)實意義.

1 問題描述與假設

顧客在線完成下單后由電商企業(yè)或第三方物流企業(yè)提供配送服務.配送車輛從配送中心出發(fā)，依次為分布在不同位置的客戶提供配送服務，并最終回到配送中心.在滿足客戶貨物需求量和供應量、車輛載質量限制、客戶要求的服務時間和城市交通管制等約束的條件下，通過合理安排行駛路線，實現(xiàn)配送成本最小、配送時間最短、配送數(shù)量最大、利用資源最少等目標.結合網(wǎng)購的物流配送特點，作以下基本假設：

圖1 車輛配送路徑

(1)如圖1所示，車輛從同一配送中心(0)駛出，同時提供送貨和取貨服務，最終回到配送中心.配送人員需要將物流跟蹤信息及時通過終端傳回總部.

(2)車輛為客戶提供送貨和取貨服務時將產(chǎn)生貨物處理時間和貨物處理成本，這里的貨物處理時間和成本與客戶的貨物量相關.

(3)每個客戶的貨物需求量和供應量均在車輛最大載質量范圍內(nèi)，不同貨物可以根據(jù)需要混裝，且每個客戶只能由一輛車提供服務.

(4)交通管制時間窗內(nèi)禁止所有車輛在限行區(qū)域內(nèi)行駛.

圖2 滿意時間窗內(nèi)到達

(5)客戶有服務時間窗要求，車輛需要在客戶能夠接受的時間窗內(nèi)到達.車輛在客戶滿意時間窗內(nèi)到達不會被懲罰，如圖2所示；車輛在客戶滿意時間窗外到達則會有一定的時間懲罰，如圖3所示.但以上情況均不影響車輛正常送貨和取貨.懲罰成本與車輛到達時間相關.

圖3 可接受時間窗內(nèi)到達

(6)配送中心的車輛有一定數(shù)量限制，要求服務車輛總數(shù)不多于該上限.[3]

(7)客戶和配送中心的坐標位置，以及各客戶的貨物量均已在配送前確定.[15]

(8)所有車輛均有相同的行駛速度和最大載質量限制，且單位時間的運行成本相同.

(9)車輛只能在客戶要求的時間窗內(nèi)到達，不存在因提前到達而發(fā)生等待時間.不考慮紅燈的等待時間，以及駕駛員的休息和用餐時間.

2 模型建立

在考慮客戶時間要求和城市交通管制等約束的條件下，分別建立最小配送成本、最短配送時間和最大客戶滿意度的單目標優(yōu)化模型，并通過加權處理形成可以求解的多目標優(yōu)化模型.

2.1 最小配送成本模型

Z1=Z11+Z12+Z13,其中:Z11取決于車輛的行駛路線；Z12取決于客戶總的貨物需求量和供應量；Z13取決于車輛到達時間.最小配送成本模型為

(1)

s. t.

(2)

(3)

(4)

(5)

(6)

(7)

(k∈V;i,j∈C)

(8)

(9)

Di,Pi，dij,Tp,ik≥0

(10)

式(1)為最小配送成本模型的目標函數(shù)；式(2)為車輛在不同時刻到達客戶點被懲罰的時間；式(3)表示由配送中心出發(fā)的車輛總數(shù)不超過K；式(4)表示每個客戶只能由一輛車服務；式(5)表示全部車輛都是由配送中心出發(fā)，并最終回到配送中心的；式(6)和(7)分別對客戶的需求量和供應量進行約束；式(8)指車輛只能從某一客戶到另一客戶；式(9)對每輛車服務的客戶數(shù)進行約束；式(10)表示客戶的貨物需求量和供應量、客戶點間的距離以及懲罰時間都是非負實數(shù).

2.2 最短配送時間模型

Z2=Z21+Z22,其中:Z21取決于各客戶的坐標位置和行駛路線選擇；Z22取決于客戶的貨物需求量和供應量.最短配送時間模型為

(11)

s. t.

tijk=dij/v

(12)

Td,ik-Ta,ik=T(Di+Pi)

(13)

Td,ik≤Ta,i+1,k

(14)

Qi-1,k+Pi-Di=Qik,

Qik≤R(i=1,2,…,N;k∈V)

(15)

Ta,ik≤Ls，Td,ik≤Ls，i∈Ctr；

或Ta,ik≥Le，Td,ik≥Le，i∈Ctr

(16)

Ta,ik,Td,ik,tijk,Tp,ik≥0

(17)

式(11)為最短配送時間模型的目標函數(shù)；式(12)表示車輛在各客戶點間的行駛時間；式(13)表示車輛在各客戶點的停留時間；式(14)表示只有服務完客戶i才可以服務客戶i+1；式(15)表示離開客戶i的載質量取決于離開客戶點i-1的載質量以及客戶i的貨物需求量和供應量；式(16)表示禁止車輛在交通管制時間內(nèi)通行，交通管制政策增加了企業(yè)物流配送成本[8]；式(17)表示車輛到達時間、離開時間、行駛時間以及懲罰時間都為非負實數(shù).

2.3 最大客戶滿意度模型

當客戶買到的產(chǎn)品或服務與預期相符即產(chǎn)生客戶滿意度.[11]本文從配送的準時性著手，建立最大客戶滿意度模型.考慮到不同客戶的重要程度有差異[5]，有必要對不同客戶的滿意度進行加權處理.設λi為客戶i的客戶滿意度權重，其大小主要取決于客戶i的貨物量.最大客戶滿意度模型為

(18)

s. t.

(19)

Fi(Ta,ik)=

(20)

式(18)為最大客戶滿意度模型的目標函數(shù)；式(19)為不同客戶的滿意度權重；式(20)是從車輛到達時間入手，形成可衡量的客戶滿意度評價體系[12].

2.4 最小配送成本和最短配送時間的多目標優(yōu)化模型

通常建立多目標優(yōu)化模型更符合實際.考慮到多目標函數(shù)的量綱并不統(tǒng)一，故運用極差法對目標函數(shù)進行無量綱化處理，其公式為

(21)

(22)

經(jīng)過線性加權處理，將多目標優(yōu)化問題轉換為如式(22)所示的單目標優(yōu)化問題.

2.5 考慮客戶滿意度的多目標優(yōu)化模型

企業(yè)間的競爭已經(jīng)從單一的價格競爭變成以價格和服務為一體的綜合競爭，服務屬性可以驅動客戶滿意度.[13]客戶滿意度對企業(yè)的績效有重要影響[14]，在物流配送行業(yè)尤為明顯.物流服務水平直接影響客戶對產(chǎn)品的需求.[10]因此,在原有模型的基礎上引入客戶滿意度指標，建立最小配送成本、最短配送時間和最大客戶滿意度的多目標優(yōu)化模型.對Z3取負號，求整體最小化.Z3的無量綱化處理公式為

3=-(Z3-minZ3)/(maxZ3-minZ3)

(23)

經(jīng)過線性加權處理，將多目標優(yōu)化問題轉換為如式(23)所示的單目標優(yōu)化問題.

3 模型求解算法設計

圖4 簡單GA的運算流程

GA是一種借鑒生物界自然選擇和自然遺傳機制的隨機搜索算法.[6]與禁忌搜索等算法相比，GA主要特點是可以對搜索空間中的多個解同時進行評估，減少陷于局部最優(yōu)的風險.[7]與精確算法相比，GA求解過程耗時更短，適合于實際配送企業(yè)的決策.因此，GA在求解多目標優(yōu)化問題中得到廣泛應用.針對以上多目標優(yōu)化模型的求解算法流程見圖4.具體求解算法設計如下.

(1)染色體編碼.求解車輛路徑問題時，適合采用排列法進行編碼來構造染色體.將配送中心和所有客戶按連續(xù)的整數(shù)編號，由這些整數(shù)隨機排列組成染色體,其中，0代表配送中心，1,2,…,N表示N個客戶.如采用排列法構造染色體0-1-5-2-0-9-0-3-7-4-6-0-0,可理解為:第一輛車由配送中心出發(fā)，按“0-1-5-2-0”的路線行駛，分別為客戶1,5,2提供送貨和取貨服務，最后回到配送中心；第二輛車按路徑“0-9-0”提供送取貨服務；第三輛車按路線“0-3-7-4-6-0”提供送取貨服務；第四輛車停在配送中心.

(2)初始種群設定.種群規(guī)模指群體中全部個體數(shù)量，初始種群的設定對算法的性能影響很大.為避免可能產(chǎn)生未成熟收斂和陷入局部最優(yōu)的風險，可以先生成數(shù)字1至N，然后將N個隨機排列的數(shù)字作為初始染色體表示N個客戶的配送順序，從而形成初始群體.

(3)適應度函數(shù)定義.首先需要將原始染色體處理成帶有配送路徑的染色體,也就是在考慮車輛載質量限制的情況下，在原始染色體中有序插入0，使其形成多個閉合的配送路徑.如果最終使用的車輛數(shù)小于配送中心總的車輛數(shù)K,則需要在染色體的尾部補足0的數(shù)量.在對個體進行評價時，需要把每個染色體的目標函數(shù)值轉換為相應的適應度值.對最小化問題，可建立目標函數(shù)與適應度函數(shù)的映射關系：f(x)=Cmax-g(x),g(x)

(5)控制參數(shù)設定.控制參數(shù)的選擇非常重要，它會影響整個算法的收斂性.在基本GA中，必須預先設定：①群體中全部個體的數(shù)量M，一般取10～200；②終止進化代數(shù)T，一般取50～500；③交叉概率Pc，一般取0.40～0.99；④變異概率Pm，一般取0.000 1～0.1.

4 算例分析

客戶的基本信息見表1.共有配送中心1個,其坐標為(10,10)；客戶點數(shù)N=20,所有客戶在邊長為20的矩形框內(nèi)隨機生成;K=6；R=20；dmax=30；v=10；f=5；H=2；cp=12；客戶滿意度閾值為80%；配送時間為[8，18]；交通管制時間窗為[8.0,8.5]和[17.0,17.5]，交通管制區(qū)域涵蓋客戶6，11，13，16，18和20.

算法中的控制參數(shù)設置為：M=20，T=50，Pc=0.6，Pm=0.01.模型的求解是使用MATLAB在Windows 7 (AMD Athlon(tm)Neo X2 Dual Core Processor L335 1.6 GHz)平臺上編程實現(xiàn)的.

4.1 最小配送成本和最短配送時間的多目標優(yōu)化模型

首先建立常規(guī)的最小配送成本和最短配送時間的多目標優(yōu)化模型.采用GA求得的最優(yōu)解對應的染色體是0-13-11-10-0-7-3-2-1-0-8-4-5-6-9-0-12-15-17-16-0-14-19-20-18-0-0，即共需安排5輛車提供配送服務.詳細的求解結果見表2.

4.2 考慮客戶滿意度的多目標優(yōu)化模型

在原有模型的基礎上，建立最小配送成本、最短配送時間和最大客戶滿意度的多目標優(yōu)化模型.采用GA求得的最優(yōu)解對應的染色體是0-13-10-11-0-3-2-1-0-7-8-4-5-6-0-12-9-0-15-17-16-0-14-19-20-18-0，即共需安排6輛車提供配送服務.詳細的求解結果見表3.

在原有模型中，平均每位客戶的配送成本為33.4，配送時間為1.1，客戶滿意度為85.4%.但是客戶10,1,6,17,20的滿意度值均低于設定的客戶滿意度閾值80%，即面臨客戶流失的風險.在考慮客戶滿意度約束的優(yōu)化模型中，平均每位客戶的配送成本為37.6，配送時間為1.2，客戶滿意度為98.6%，且每位客戶的滿意度值均高于設定的客戶滿意度閾值80%，即不存在客戶流失的風險.通過對比發(fā)現(xiàn)，雖然平均每位客戶的配送成本增加4.2，配送時間增加0.1，但整體客戶滿意度水平提高13.2%，不存在客戶流失的風險.

表1 客戶的基本信息統(tǒng)計

表2 不考慮客戶滿意度的求解結果

表3 考慮客戶滿意度的求解結果

5 結束語

物流配送是電子商務的重要組成部分，高效的物流配送能夠提高電商企業(yè)核心競爭力.本文首先建立最小配送成本和最短配送時間的多目標優(yōu)化模型，并考慮到城市交通管制的硬時間窗約束和客戶要求的軟時間窗約束；然后引入客戶滿意度指標，并設定客戶滿意度閾值，對該模型進行優(yōu)化;最后設計算法和算例對以上兩個模型進行求解分析.原有模型可以保證較低的配送成本和較少的配送時間，但是部分客戶滿意度值較低，存在客戶流失的風險.優(yōu)化后的模型可以在保證較低配送成本和較少配送時間的基礎上，最大化配送服務的客戶滿意度水平,不存在客戶流失的風險，有利于提高企業(yè)的競爭優(yōu)勢，符合企業(yè)的長遠利益.

機動車數(shù)量的不斷增長給城市道路交通帶來更多壓力.進一步的研究將考慮配送車輛對城市道路交通環(huán)境的影響.

[1]DANTZIG G B, RAMSER J H. The truck dispatching problem[J]. Manage Sci, 1959, 6(1): 80-91.

[2]VIDAL T, CRAINIC T G, GENDREAU M,etal. A hybrid genetic algorithm for multidepot and periodic vehicle routing problems[J]. Operations Res, 2012, 60(3): 611-624.

[3]BATTARRA M, ERDOGAN G, VIGO D. Exact algorithms for the clustered vehicle routing problem[J]. Operations Res, 2014, 62(1): 58-71.

[4]彭碧濤, 周永務. 多時間窗車輛路徑問題的混合蟻群算法[J]. 計算機工程與應用, 2010, 46(31): 28-31.

[5]DABIA S, ROPKE S, WOENSEL T V,etal. Branch and price for the time-dependent vehicle routing problem with time windows[J].Transportation Sci, 2013, 47(3): 380-396.

[6]胡繼雪. 基于大規(guī)模車輛路徑問題的配送分區(qū)優(yōu)化研究[D]. 濟南: 山東大學, 2013.

[7]JIANG J, NG K M, POH K L,etal. Vehicle routing problem with a heterogeneous fleet and time windows[J]. Expert Systems with Applications, 2014, 41: 3748-3760.

[8]胡云超, 申金升, 黃愛玲. 城市貨運交通管制情境下城市配送多目標優(yōu)化效益研究[J]. 交通運輸系統(tǒng)工程與信息, 2012, 12(6): 119-125.

[9]陳文強, 顧玉磊. 基于貨物時間價值的物流網(wǎng)絡最優(yōu)配送路徑模型研究[J]. 交通運輸工程與信息學報, 2013, 11(2): 19-23.

[10]何嬋, 劉偉, 崔愛平. 考慮物流服務水平影響的三級物流服務供應鏈協(xié)調[J]. 上海海事大學學報, 2014, 35(1): 41-48.

[11]OLIVER R L, SWAN J E. Equity and disconfirmation perceptions as influences on merchant and product satisfaction[J]. J Consumer Res, 1989, 16(3): 372-383.

[12]李逸珩. 基于客戶服務中心的運營商客戶滿意度管理研究[D]. 武漢: 華中科技大學, 2012.

[13]SZYMZNSKI D M, HISE R T. E-satisfaction: an initial examination[J]. J Retailing, 2000, 76(3): 309-322.

[14]SINGH S, RANCHHOD A. Market orientation and customer satisfaction: evidence from British machine tool industry[J]. Ind Marketing Manage, 2004, 33: 135-144.

[15]鄧麗君. 基于客戶滿意度的物流配送車輛調度優(yōu)化模型與算法研究[D]. 北京: 北京交通大學, 2012.

(編輯 趙勉)

E-commerce logistics distribution routing optimization considering customer satisfaction

ZHAO Rui, HU Xiong, HE Hongdi

(Academy of Science & Technology, Shanghai Maritime Univ., Shanghai 201306, China)

In order to better reflect customer satisfaction in the process of e-commerce logistics distribution, the customer satisfaction index is introduced. First, a multi-objective optimization model is formulated with the minimal distribution cost and time under the hard time window constraint of urban traffic control and the soft time window constraint of customer requirements. Then, the index of the customer satisfaction is introduced and its threshold is set to optimize the model. The genetic algorithm is designed to solve the optimized model. Finally, the efficiency of the model and the algorithm is verified with an example. The result shows that the optimized model can maximize the customer satisfaction with the lower distribution cost and the shorter distribution time. It is helpful for enterprises to improve the competitive advantage and satisfy the long-term interest without the risk of losing customers.

customer satisfaction; logistics distribution; hard time window; soft time window; genetic algorithm

10.13340/j.jsmu.2015.03.011

1672-9498(2015)03-0064-07

2014-06-13

2014-09-29

國家自然科學基金(71171129)；上海市自然科學基金(12PJ1404000)

趙銳(1989—)，男，江蘇淮安人，碩士研究生，研究方向為物流工程、物流資源配置和物流設備管理，(E-mail)ranenchao@gmail.com； 胡雄(1962—)，男，上海人，教授，博導，博士，研究方向為港航物流裝備的健康管理、故障診斷與安全評估， (E-mail)huxiong@shmtu.edu.cn

F252.14；F252.2

A