考慮客戶價值的車輛調度干擾管理*

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

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

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

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

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

由于價值不同的客戶為企業創造的經濟效益是不同的，為了將物流企業有限的資源運用到不同的客戶中，使物流企業的經濟效益最大化，現有的研究對于客戶價值在車輛調度干擾管理方面的研究并不完善.本文在現有車輛調度干擾管理問題的基礎上，綜合考慮客戶的價值，建立了考慮客戶價值的多目標車輛調度干擾管理模型，并設計改進種子群優化算法對模型進行求解.

1 考慮客戶價值的車輛調度干擾管理模型

1.1 問題描述

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

1.2 參數基變量說明

1.3 模型建立

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

(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為目標函數，表示總的配送成本最低；式(2)表示每輛車的裝載量不超過其裝載能力；式(3)表示每輛車均從配送中心出發；式(4)表示所有客戶都能得到服務，并且只有一輛車對其進行服務；式(5)表示車輛對客戶進行服務后，返回配送中心；式(6)～(8)表示變量之間的關系；式(9)、(10)表示應當滿足客戶的時間窗要求.

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

在衡量擾動事件對物流配送系統的擾動之前，首先應該根據客戶的價值對客戶進行等級劃分.結合專家打分法，利用云模型中的正態云模型對客戶進行等級劃分.

1.4.1 客戶價值評價指標體系的構建

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

表1 客戶價值評價指標體系Tab.1 Evaluation indexes for customer value

1.4.2 基于云模型的客戶細分流程

基于云模型的客戶細分流程如下：

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

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

經過多輪打分后，確定了各二級指標的評分數據，如表2所示.

表2 客戶指標評分數據Tab.2 Scoring data for customer indexes

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

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

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

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

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

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

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

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

(11)

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

(12)

物流配送運營商的配送成本擾動公式為

(13)

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

(14)

以上述三個干擾度量函數為基礎，采用字典序多目標規劃方法，構建基于客戶等級劃分的干擾管理模型如下：

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

2 改進種子群優化算法

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

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

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

免疫算法的執行效率很大程度上取決于疫苗的選取和接種疫苗的位置，優良的疫苗是免疫算子有效發揮作用的基礎和保障.在提取疫苗的特征信息時，不同于以往的傳統方法，對于疫苗的提取設計了自適應機制來保證疫苗特征信息的提取率以及疫苗接種點的控制.

2.1 自適應疫苗特征信息的設計

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

(23)

特征信息提取的概率依據父種的適應度值不斷調整，當父種的適應度值較大時，特征信息提取的概率為1，當父種的適應度值低于平均適應度值時，特征信息提取概率會隨著適應度值的減小而減小.

2.2 疫苗接種點的自適應控制

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

(24)

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

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

判斷是否達到終止條件.將每次迭代的最優父種記為PBEST，將全局迭代產生的最優父種記為GBEST，當得到了理想的GBEST或者GBEST的值不再變化時，結束運行，輸出結果.改進種子群算法的流程圖如圖3所示.

圖3 改進種子群優化算法流程Fig.3 Flow chart of improved seedoptimization algorithm

3 仿真研究

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

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

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

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

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

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

表8 改進種子群優化算法與粒子群優化算法Tab.8 Improved seed swarm optimization algorithmand particle swarm optimization algorithm

圖4 最優解收斂Fig.4 Convergence of optimal solution

4 結 論

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

[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].計算機工程與應用，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] 劉艷秋，曹歌，張穎，等.基于分組策略的補貨配送問題優化模型 [J].沈陽工業大學學報，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].系統工程理論與實踐，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] 閆卓楠，王承文，俞虹.城市災害應急物流配送干擾管理系統模型研究 [J].工程管理學報，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].管理科學學報，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].運籌與管理，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] 王旭坪，阮俊虎，張凱，等.有模糊時間窗的車輛調度組合干擾管理研究 [J].管理科學學報，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無線通信技術的物流配送車輛優化調度問題 [J].物流技術，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.)