考慮客戶價值的車輛調(diào)度干擾管理*

曹慶奎， 趙麗飛， 任向陽， 梁武超

(河北工程大學(xué) 管理工程與商學(xué)院， 河北 邯鄲 056038)

近年來，隨著科學(xué)技術(shù)和社會經(jīng)濟(jì)的飛速發(fā)展，物流配送在人們生活中扮演著越來越重要的角色.為了更大化物流企業(yè)的經(jīng)濟(jì)效益，需要對客戶進(jìn)行判斷、分類及管理，提高顧客滿意度，使企業(yè)經(jīng)濟(jì)效益最大化.

車輛調(diào)度問題可定義為運(yùn)輸車輛從一個或多個設(shè)施到多個地理上分散的客戶點，優(yōu)化設(shè)計一套貨物流動的運(yùn)輸路線，同時要滿足一系列的約束條件.車輛調(diào)度的前提條件是客戶點位置和道路情況已知，由此確定一套車輛運(yùn)輸路線，以滿足目標(biāo)函數(shù)的要求，通常的目標(biāo)函數(shù)是總費用最低.Pillac等針對動態(tài)車輛調(diào)度問題，從信息質(zhì)量和變化的角度，在提供一個一般描述的動態(tài)路徑基礎(chǔ)上，引入動態(tài)程度的概念，并全面回顧動態(tài)車輛路徑問題及解決方案，提出了完善車輛路徑問題可以從提高服務(wù)質(zhì)量著手[1]；Tas等研究了具有靈活時間窗的車輛路徑問題，通過構(gòu)造禁忌搜索算法對模型進(jìn)行求解，提出了一種線性規(guī)劃模型對客戶路徑進(jìn)行詳細(xì)優(yōu)化的方法[2]；馬冬青等研究了物流配送雙向車輛調(diào)度問題，參照經(jīng)典車輛路徑模型，考慮了車輛配送里程和用戶數(shù)等限制，建立了雙向車輛調(diào)度模型，將爬山算法引入粒子群算法當(dāng)中設(shè)計出改進(jìn)的粒子群算法，對模型進(jìn)行求解，提高了算法的局部搜索能力[3]；劉艷秋等針對已存在的供應(yīng)鏈環(huán)境下較少考慮補(bǔ)貨配送問題中分組配送策略，結(jié)合大量零售商對單一產(chǎn)品需求量不同等特點，構(gòu)建了帶有配送中心能力約束的補(bǔ)貨配送優(yōu)化模型，并利用改進(jìn)的遺傳算法對該模型求解[4].

自從干擾管理的思想被提出以來，國內(nèi)外學(xué)者對此進(jìn)行了研究.在計劃實施過程中存在很多不確定信息，經(jīng)常在執(zhí)行計劃過程中出現(xiàn)突發(fā)事件，這些突發(fā)事件會對原始的計劃產(chǎn)生影響，需要對干擾事件發(fā)生以后的車輛調(diào)度狀況進(jìn)行分析研究，迅速、準(zhǔn)確地生成對于整個配送系統(tǒng)擾動最小的車輛調(diào)度方案.物流配送中常見的干擾事件有車輛故障、道路阻塞、客戶時間窗變動和客戶需求量變動等.干擾管理與傳統(tǒng)的不確定決策理論以及重調(diào)度理論有著本質(zhì)的區(qū)別，車輛調(diào)度干擾管理主要側(cè)重于干擾事件發(fā)生以后如何避免對于初始配送計劃的擾動，是對原始車輛調(diào)度方案的局部調(diào)整.車輛調(diào)度干擾管理的目標(biāo)是對原始計劃產(chǎn)生最小的擾動.胡祥培等人敘述了干擾管理理念的形成與發(fā)展過程，總結(jié)了目前干擾管理的模型及算法，并指出現(xiàn)階段干擾管理仍存在的問題和今后的研究方向[5]；閆卓楠等人從客戶不滿意度、配送成本以及路徑偏離程度三個方面來度量物流配送系統(tǒng)中的擾動，建立字典序多目標(biāo)干擾管理模型，并利用啟發(fā)式算法對模型進(jìn)行求解[6]；丁秋雷等人結(jié)合行為科學(xué)中對人行為感知的研究方法與運(yùn)籌學(xué)中的定量研究方法，提出了基于前景理論的擾動度量方法，構(gòu)建了字典序多目標(biāo)干擾管理模型，并利用改進(jìn)的蟻群算法求解該模型，針對物流配送中的干擾事件，提出了對不同客戶采用不同的擾動策略[7]；文獻(xiàn)[8]對干擾模型進(jìn)行擾動分析，并且建立了車輛調(diào)度的干擾模型，在度量客戶不滿意度時分別采用不同的方法來區(qū)分客戶的重要程度.

由于價值不同的客戶為企業(yè)創(chuàng)造的經(jīng)濟(jì)效益是不同的，為了將物流企業(yè)有限的資源運(yùn)用到不同的客戶中，使物流企業(yè)的經(jīng)濟(jì)效益最大化，現(xiàn)有的研究對于客戶價值在車輛調(diào)度干擾管理方面的研究并不完善.本文在現(xiàn)有車輛調(diào)度干擾管理問題的基礎(chǔ)上，綜合考慮客戶的價值，建立了考慮客戶價值的多目標(biāo)車輛調(diào)度干擾管理模型，并設(shè)計改進(jìn)種子群優(yōu)化算法對模型進(jìn)行求解.

1 考慮客戶價值的車輛調(diào)度干擾管理模型

1.1 問題描述

本文中數(shù)學(xué)模型問題描述如下：原始配送方案為最優(yōu)方案；每輛車都從配送中心出發(fā)，把裝載的貨物配送到指定的客戶后，返回配送中心；每輛車可以服務(wù)多個客戶，但是每個客戶只能有一輛車提供服務(wù)；每輛車配送貨物的總量不能超過其裝載能力，為了簡化問題，假設(shè)每輛車的裝載能力相同；客戶對貨物不準(zhǔn)時送達(dá)有一定的容忍限度，但是無論何時送達(dá)，均不會拒收，并且本文中客戶的不滿意程度只與送貨時間有關(guān)；當(dāng)擾動發(fā)生以后，假設(shè)配送車輛所在位置為虛擬配送中心，是擾動后配送的起點，初始配送中心為配送的終點，并且在擾動發(fā)生以后，配送中心沒有多余的車輛進(jìn)行救援，只能使用原有的配送車輛完成配送任務(wù)；要求合理安排車輛的配送線路和行車時間，使得目標(biāo)函數(shù)最優(yōu).

1.2 參數(shù)基變量說明

1.3 模型建立

根據(jù)上述條件，建立初始方案模型如下：

(1)

(2)

(3)

(4)

(5)

(6)

(7)

(8)

ti≥ETi(i=1，2，…，n)

(9)

ti+wi≤LTi(i=1，2，…，n)

(10)

上述模型中，式(1)中Z為目標(biāo)函數(shù)，表示總的配送成本最低；式(2)表示每輛車的裝載量不超過其裝載能力；式(3)表示每輛車均從配送中心出發(fā)；式(4)表示所有客戶都能得到服務(wù)，并且只有一輛車對其進(jìn)行服務(wù)；式(5)表示車輛對客戶進(jìn)行服務(wù)后，返回配送中心；式(6)～(8)表示變量之間的關(guān)系；式(9)、(10)表示應(yīng)當(dāng)滿足客戶的時間窗要求.

1.4 客戶價值的條件處理及干擾管理模型的建立

在衡量擾動事件對物流配送系統(tǒng)的擾動之前，首先應(yīng)該根據(jù)客戶的價值對客戶進(jìn)行等級劃分.結(jié)合專家打分法，利用云模型中的正態(tài)云模型對客戶進(jìn)行等級劃分.

1.4.1 客戶價值評價指標(biāo)體系的構(gòu)建

針對物流企業(yè)的特點，考慮到客戶具有主觀能動性特征，在以往客戶價值評價指標(biāo)體系構(gòu)成要素的基礎(chǔ)上，引入了客戶關(guān)系價值.在進(jìn)行物流企業(yè)客戶分類時，將客戶價值分為客戶當(dāng)前價值、客戶潛在價值和客戶關(guān)系價值三個維度構(gòu)建客戶價值評價指標(biāo)體系.將客戶價值評價指標(biāo)體系分為兩個層次，即3個一級指標(biāo)，11個二級指標(biāo)，具體如表1所示.

表1 客戶價值評價指標(biāo)體系Tab.1 Evaluation indexes for customer value

1.4.2 基于云模型的客戶細(xì)分流程

基于云模型的客戶細(xì)分流程如下：

1) 利用逆向云發(fā)生器結(jié)合專家打分法確定指標(biāo)的權(quán)重；根據(jù)客戶的實際情況，咨詢了十位專家的意見后，采用云模型對評價指標(biāo)的權(quán)重進(jìn)行了修正.以客戶周期服務(wù)費用為例，在第一輪的專家意見咨詢中，專家對各指標(biāo)權(quán)重的意見不太統(tǒng)一，相應(yīng)的評分比較分散，熵和超熵都比較大，需進(jìn)行再次評分.將上次評分得出的結(jié)果遞交給各位專家，各位專家根據(jù)上次的結(jié)果修改自己的評分，隨著不斷地改善與反饋，打分情況逐漸統(tǒng)一，云模型對專家打分的修正過程如圖1所示.

圖1 專家打分情況Fig.1 Expert scoring situations

經(jīng)過多輪打分后，確定了各二級指標(biāo)的評分?jǐn)?shù)據(jù)，如表2所示.

表2 客戶指標(biāo)評分?jǐn)?shù)據(jù)Tab.2 Scoring data for customer indexes

2) 利用正向云發(fā)生器進(jìn)行客戶等級概念的劃分，本文定義物流企業(yè)客戶的評語集為：V=(v1，v2，v3)，其中，v1(85～100分)表示重要客戶；v2(40～85分)表示較為重要客戶；v3(0～40分)表示一般客戶，通過正態(tài)云模型進(jìn)行概念劃分，將等級概念幾何化，并由此得出等級概念云，如圖2所示.

圖2 等級概念云Fig.2 Hierarchical concept cloud

3) 利用逆向云發(fā)生器得出云的三個數(shù)字特征[Ex，En，He]，分別選取某物流企業(yè)的8個客戶的十位專家作為評分樣本，利用逆向云發(fā)生器求得各個客戶總評價云模型的三個數(shù)字特征，如表3所示.

4) 利用X條件云發(fā)生器確定各個客戶的隸屬度進(jìn)行客戶等級劃分.由于偶然性的存在，在分界處的等級評價有可能會不同，但總的趨勢趨于穩(wěn)定.該物流企業(yè)的8個客戶評價云模型的10次模擬結(jié)果以及評價結(jié)果如表4所示.

1.4.3 客戶擾動的度量及模型的建立

本文主要從三個方面衡量物流配送系統(tǒng)的擾動，分別為客戶整體滿意度、物流配送成本以及貨車司機(jī)滿意度.單一客戶的滿意度同時滿足軟時間窗和硬時間窗的要求，其懲罰函數(shù)[9]為

表3 客戶云模型指數(shù)Tab.3 Cloud model indexes for customer

表4 客戶等級云評價結(jié)果Tab.4 Cloud evaluation results of customer grades

(11)

采用客戶分級策略對整體的擾動大小進(jìn)行度量，在進(jìn)行客戶等級劃分時采用云模型對客戶進(jìn)行動態(tài)等級劃分，客戶整體不滿意度度量公式為

(12)

物流配送運(yùn)營商的配送成本擾動公式為

(13)

貨車司機(jī)的滿意程度主要由路徑偏離量引起，因此用路徑偏離量來代替貨車司機(jī)的滿意度，則路徑偏離量擾動公式為

(14)

以上述三個干擾度量函數(shù)為基礎(chǔ)，采用字典序多目標(biāo)規(guī)劃方法，構(gòu)建基于客戶等級劃分的干擾管理模型如下：

min Lex=(P1∶DP，P2∶DF，P3∶DN)

(15)

P1≥P2≥P3

(16)

(17)

(18)

(19)

(20)

ti≥ETi(i=1，2，…，m)

(21)

ti+wi≤LTi(i=1，2，…，m)

(22)

式(11)是對單一客戶不滿意度的度量，對于配送系統(tǒng)中整體不滿意度的度量，本文采用客戶分級策略對整體的擾動大小進(jìn)行度量，其中，M為非常大的數(shù)，ai、bi、mi和ni為懲罰系數(shù)；式(12)為客戶整體不滿意度，其中，Z1、Z2和Z3表示客戶所屬等級的集合，α、β和γ為這三類客戶重要程度相關(guān)系數(shù)；式(13)為物流運(yùn)營供應(yīng)商配送成本擾動度量公式；式(14)為路徑偏離量擾動公式；式(15)為目標(biāo)函數(shù)表達(dá)式，表示在考慮客戶等級劃分的情況下調(diào)整方案與原始方案的偏離程度最小，即對系統(tǒng)擾動程度最?。皇?16)為不同目標(biāo)的優(yōu)先級，決策者可以根據(jù)實際情況進(jìn)行適當(dāng)調(diào)整，本文模型中客戶擾動最小化為第一級目標(biāo)，物流配送運(yùn)營商擾動最小化為第二級目標(biāo)，物流配送員即貨車司機(jī)擾動最小化為第三級目標(biāo)；式(17)為車輛裝載的貨物量不能超過其裝載能力；式(18)為每輛車都從虛擬配送中心出發(fā)；式(19)為車輛對客戶服務(wù)結(jié)束以后，返回初始的配送中心；式(20)為各變量之間的關(guān)系；式(21)、(22)為滿足客戶時間窗.

2 改進(jìn)種子群優(yōu)化算法

在種子群算法初始化過程中，父代種群的隨機(jī)選擇可以借鑒免疫算法中記憶細(xì)胞的原理，即根據(jù)先驗知識來判斷，若之前有過類似問題出現(xiàn)，則可以從數(shù)據(jù)庫中提取該類問題的記憶細(xì)胞，作為初代父種選擇的基礎(chǔ).在種子群優(yōu)化算法中，初始化得到的N個初代父種用實值向量來表示，即

X1={x11，x12，x13，…，x1e}
X2={x21，x22，x23，…，x2e}
X3={x31，x32，x33，…，x3e}
?
XN={xN1，xN2，xN3，…，xNe}

其中，N的大小由待求問題的規(guī)模來決定，e為后代種群的個數(shù).

免疫算法的執(zhí)行效率很大程度上取決于疫苗的選取和接種疫苗的位置，優(yōu)良的疫苗是免疫算子有效發(fā)揮作用的基礎(chǔ)和保障.在提取疫苗的特征信息時，不同于以往的傳統(tǒng)方法，對于疫苗的提取設(shè)計了自適應(yīng)機(jī)制來保證疫苗特征信息的提取率以及疫苗接種點的控制.

2.1 自適應(yīng)疫苗特征信息的設(shè)計

疫苗特征信息的提取率不僅可以使每一代最優(yōu)父種的特征信息被最大限度的保留，而且保證了適應(yīng)度值較小的父種得到一定進(jìn)化，提高了其空間搜索能力.對于較大適應(yīng)度值，采用較大的特征信息提取率；對于較小適應(yīng)度值，采用較低的特征信息提取率.自適應(yīng)特征信息提取概率的公式為

(23)

特征信息提取的概率依據(jù)父種的適應(yīng)度值不斷調(diào)整，當(dāng)父種的適應(yīng)度值較大時，特征信息提取的概率為1，當(dāng)父種的適應(yīng)度值低于平均適應(yīng)度值時，特征信息提取概率會隨著適應(yīng)度值的減小而減小.

2.2 疫苗接種點的自適應(yīng)控制

標(biāo)準(zhǔn)免疫算法的疫苗接種點是隨機(jī)選取的，當(dāng)群體中的基因類似時，免疫算子的影響力就會削弱，使得算法的搜索效率降低.為改變由于接種點的隨機(jī)性和盲目性所帶來的影響，本文設(shè)計了依據(jù)父種的適應(yīng)度值來控制接種點位置的方法，適應(yīng)度值大的父種接種到其他父種的疫苗的特征信息就多，反之就少.接種點的長度公式為

(24)

式中：l為父種分量的個數(shù)；f1為最優(yōu)父種的適應(yīng)度值；f2為其他待接種疫苗的適應(yīng)度值.最優(yōu)父種的疫苗特征信息的接種按照式(24)中的l2來接種，根據(jù)式(24)可知，當(dāng)被接種疫苗的父種適應(yīng)度值較小時，該父種分量改變的長度就會較長，對應(yīng)分量的個數(shù)就較多，反之，如果被接種父種的適應(yīng)度值較大，那么接種疫苗時，所保留的疫苗特征信息就會較少，即父種分量的個數(shù)參與接種的較少.

將接種疫苗后父種的適應(yīng)度與之前未接種的種子適應(yīng)度進(jìn)行比較，如果接種疫苗之后種子的適應(yīng)度值大于接種疫苗之前，并且種群間的距離符合給定的閾值，則采用接種后的種子作為下一代父種，否則，舍棄接種疫苗之后的種子，將原有的種子作為父種.

判斷是否達(dá)到終止條件.將每次迭代的最優(yōu)父種記為PBEST，將全局迭代產(chǎn)生的最優(yōu)父種記為GBEST，當(dāng)?shù)玫搅死硐氲腉BEST或者GBEST的值不再變化時，結(jié)束運(yùn)行，輸出結(jié)果.改進(jìn)種子群算法的流程圖如圖3所示.

圖3 改進(jìn)種子群優(yōu)化算法流程Fig.3 Flow chart of improved seedoptimization algorithm

3 仿真研究

對文獻(xiàn)[10]中的算例進(jìn)行實驗分析，該算例有8項貨物運(yùn)輸任務(wù)(編號為1，2，…，8)，各任務(wù)貨運(yùn)量為gi(單位：t).裝貨(或卸貨)時間Ti(單位：h)以及要求每項任務(wù)開始執(zhí)行的時間范圍[ETi，LTi]如表5所示.這些任務(wù)由車場0發(fā)出的3輛容量為8 t的車輛來完成，車場0與各任務(wù)點之間以及各任務(wù)點之間的距離如表6所示.本文假設(shè)車輛的行駛時間與距離成正比，每輛車的平均行駛速度為50 km/h，則從點i到j(luò)的行駛時間為tij=dij/50.把各點之間的距離dij作為費用，則有Cij=dij(i，j=0，1，…，8).

表5 客戶點信息Tab.5 Information of customer points

表6 各任務(wù)點之間的距離Tab.6 Distance between each task point km

采用Matlab 7.1編程實現(xiàn)上述算法，相關(guān)參數(shù)設(shè)置如下：父種個數(shù)為3，子種群個數(shù)為3，最大迭代次數(shù)為100，種群規(guī)模為100，粒子群中固定參數(shù)c1=c2=1.494.初始方案的配送路徑以及兩種算法運(yùn)行結(jié)果比較分別如表7、8所示，圖4為最優(yōu)解的收斂情況，表明本文設(shè)計的改進(jìn)種子群優(yōu)化算法能夠在較短時間內(nèi)收斂到全局最優(yōu)解.

表7 初始配送計劃Tab.7 Initial distribution plan

當(dāng)t=2時，客戶2的需求量變?yōu)?，分別利用改進(jìn)種子群優(yōu)化算法對考慮客戶價值的車輛調(diào)度干擾管理模型以及普通的干擾管理模型進(jìn)行求解，其中，式(12)中的參數(shù)采用專家打分法獲得，從企業(yè)中選取10名專家，分別是物流配送中心工作人員3名，配送中心經(jīng)理3名以及物流企業(yè)管理層4名對不同等級的客戶進(jìn)行打分.根據(jù)打分結(jié)果分析得出α=2，β=1，γ=0.6.利用普通車輛調(diào)度干擾管理模型求解出總的配送成本為945.77元，客戶整體不滿意度為42.06%，路徑偏離量為3；利用考慮客戶價值的車輛調(diào)度干擾管理模型求解出總的配送成本為944.64元，客戶整體不滿意度為39.89%，路徑偏離量為3.

表8 改進(jìn)種子群優(yōu)化算法與粒子群優(yōu)化算法Tab.8 Improved seed swarm optimization algorithmand particle swarm optimization algorithm

圖4 最優(yōu)解收斂Fig.4 Convergence of optimal solution

4 結(jié) 論

針對干擾模型的求解，本文設(shè)計了改進(jìn)的種子群優(yōu)化算法，并與粒子群算法相比較，在搜索速度上優(yōu)于粒子群算法，并且解的穩(wěn)定性較好，可以有效求解干擾管理過程中的車輛調(diào)度問題.對物流企業(yè)的客戶根據(jù)客戶價值進(jìn)行劃分，建立了考慮客戶價值的車輛調(diào)度干擾管理模型.通過具體實例表明在根據(jù)客戶價值對客戶進(jìn)行等級劃分以后，優(yōu)化所得的干擾管理模型的求解結(jié)果與一般的求解結(jié)果相比，配送成本雖然沒有較大變化，但是客戶整體的不滿意度降低了2.17%.客戶的整體滿意度提高，有利于提高客戶的忠誠度，通過發(fā)掘客戶的潛在價值以及客戶的關(guān)系價值，通過良好的客戶關(guān)系管理為物流企業(yè)帶來更多的經(jīng)濟(jì)效益，同時，也證明了在干擾管理過程中考慮客戶價值的現(xiàn)實意義.

[1] Pillac V，Gendreau M，Guéret C，et al.A review of dynamic vehicle routing problems [J].European Journal of Operational Research，2013，225(1)：1-11.

[2] Tas D，Jabali O，Van Woensel T.A vehicle routing problem with flexible time windows [J].Computers & Operations Research，2014，52(Part A)：39-54.

[3] 馬冬青，王蔚.基于改進(jìn)粒子群算法的物流配送車輛調(diào)度 [J].計算機(jī)工程與應(yīng)用，2014，50(11)：246-250.

(MA Dong-qing，WANG Wei.Logistics distribution vehicle scheduling based on improved particle swarm optimization [J].Computer Engineering and Applications，2014，50(11)：246-250.)

[4] 劉艷秋，曹歌，張穎，等.基于分組策略的補(bǔ)貨配送問題優(yōu)化模型 [J].沈陽工業(yè)大學(xué)學(xué)報，2017，39(2)：165-169.

(LIU Yan-qiu，CAO Ying，ZHANG Ying，et al.Optimiza-tion model for replenishment and distribution problems based on grouping strategy [J].Journal of Shenyang University of Technology，2017，39(2)：165-169.)

[5] 胡祥培，張漪，丁秋雷，等.干擾管理模型及其算法的研究進(jìn)展 [J].系統(tǒng)工程理論與實踐，2008，28(10)：40-46.

(HU Xiang-pei，ZHANG Yi，DING Qiu-lei，et al.Review on disruption management model and its algorithm [J].Systems Engineering-Theory & Practice，2008，28(10)：40-46.)

[6] 閆卓楠，王承文，俞虹.城市災(zāi)害應(yīng)急物流配送干擾管理系統(tǒng)模型研究 [J].工程管理學(xué)報，2014，28(2)：61-65.

(YAN Zhuo-nan，WANG Cheng-wen，YU Hong.Emergency logistics distribution management system of city disaster interference model [J].Journal of Engineering Management，2014，28(2)：61-65.)

[7] 丁秋雷，胡祥培，姜洋.基于前景理論的物流配送干擾管理模型研究 [J].管理科學(xué)學(xué)報，2014，17(11)：1-19.

(DING Qiu-lei，HU Xiang-pei，JIANG Yang.A model of disruption management based on prospect theory in logistic distribution [J].Journal of Management Sciences in China，2014，17(11)：1-19.)

[8] 丁秋雷，胡祥培，姜洋.物流配送受擾問題的干擾管理兩階段決策方法 [J].運(yùn)籌與管理，2012，21(6)：84-93.

(DING Qiu-lei，HU Xiang-pei，JIANG Yang.Two-stage decision-making method of disruption management for solving delay in distribution [J].Operations Research and Management Science，2012，21(6)：84-93.)

[9] 王旭坪，阮俊虎，張凱，等.有模糊時間窗的車輛調(diào)度組合干擾管理研究 [J].管理科學(xué)學(xué)報，2011，14(6)：2-15.

(WANG Xu-ping，RUAN Jun-hu，ZHANG Kai，et al.Study on combinational disruption management for vehicle routing problem with fuzzy time windows [J].Journal of Management Sciences in China，2011，14(6)：2-15.)

[10]李海濤.基于3G無線通信技術(shù)的物流配送車輛優(yōu)化調(diào)度問題 [J].物流技術(shù)，2014(15)：338-341.

(LI Hai-tao.Study on logistics distribution vehical optimal dispatching based on 3G wireless telecommunication technology [J].Logistics Technology，2014(15)：338-341.)