基于行為的救援車(chē)輛調(diào)度干擾管理研究

任向陽(yáng)，周幸窈，梁武超，張秀娟，邵松娟

（1.河北工程大學(xué) 管理工程與商學(xué)院，河北 邯鄲 056001；2.中國(guó)礦業(yè)大學(xué)（北京） 管理學(xué)院，北京 100083）

1 引言

隨著信息與網(wǎng)絡(luò)技術(shù)的飛速發(fā)展，愈來(lái)愈多的企業(yè)構(gòu)建電子商務(wù)經(jīng)營(yíng)模式。應(yīng)用電子商務(wù)模式能夠省去從生產(chǎn)到最終銷(xiāo)售過(guò)程中的許多步驟，其中物流業(yè)起到了很大的作用[1-2]。在整個(gè)物流活動(dòng)中，配送作業(yè)承擔(dān)將貨物運(yùn)送到顧客指定位置的任務(wù)，與顧客滿意度緊密相關(guān)，但是配送過(guò)程中發(fā)生的干擾事件（如惡劣天氣、交通擁堵、車(chē)輛故障、顧客需求變動(dòng)等），會(huì)嚴(yán)重影響配送任務(wù)的完成，從而進(jìn)一步影響顧客滿意度。當(dāng)前，國(guó)內(nèi)外的專(zhuān)家學(xué)者對(duì)車(chē)輛調(diào)度干擾管理進(jìn)行了大量的研究。

Dantzig和Ramser[3]最早對(duì)車(chē)輛調(diào)度問(wèn)題進(jìn)行了研究，在此基礎(chǔ)上國(guó)內(nèi)外學(xué)者對(duì)這一問(wèn)題進(jìn)行了進(jìn)一步的研究，且取得了豐富的研究成果。Victor等[4]從動(dòng)態(tài)車(chē)輛調(diào)度方向展開(kāi)研究，從信息質(zhì)量和服務(wù)質(zhì)量變化角度出發(fā)，提出了解決動(dòng)態(tài)車(chē)輛路徑問(wèn)題的方案。張群[5]建立了多物流中心、多配送車(chē)型、多產(chǎn)品種類(lèi)的車(chē)輛路徑問(wèn)題的混合模型，提出了一種新的模糊遺傳算法求解混合車(chē)輛路徑問(wèn)題，運(yùn)用改進(jìn)的模糊邏輯控制器實(shí)現(xiàn)交叉概率和變異概率的動(dòng)態(tài)調(diào)整，來(lái)提高算法的收斂速度從而得到最優(yōu)解。葉勇[6]針對(duì)多個(gè)配送中心的動(dòng)態(tài)啟用與運(yùn)輸車(chē)輛的合理分配問(wèn)題，建立以總路徑長(zhǎng)度最小為目標(biāo)函數(shù)的多配送中心車(chē)輛路徑問(wèn)題的數(shù)學(xué)模型，并運(yùn)用狼群算法進(jìn)行求解。

吳緒[7]、王明春[8]、Huisman[9]、Larsen[10]、Smith[11]等專(zhuān)家學(xué)者運(yùn)用拉格朗日松弛算法、緊急搜索算法、聚類(lèi)-重排算法、遺傳算法、局部搜索算法、優(yōu)先選擇的迭代搜索算法等方法解決物流配送過(guò)程中產(chǎn)生的干擾問(wèn)題。Mu Q等[12]主要研究了單個(gè)車(chē)輛延遲與配送車(chē)輛出發(fā)延遲問(wèn)題，建立了車(chē)輛總行駛距離最短和總延遲時(shí)間最短為目標(biāo)的干擾模型。Figliozzi[13]主要研究了因道路擁堵帶來(lái)的配送干擾問(wèn)題，構(gòu)建了一種通用的的問(wèn)題模型，并在此基礎(chǔ)上總結(jié)了道路擁堵和顧客需求時(shí)間窗兩者的聯(lián)系。王旭坪等[14]對(duì)配送車(chē)輛調(diào)度中發(fā)生的顧客需求量變化、需求時(shí)間變化以及配送地點(diǎn)變化等干擾事件進(jìn)行總結(jié)，通過(guò)臨近救援策略和增派策略進(jìn)行了干擾管理。王征等[15]從顧客時(shí)間窗偏離程度最小化和配送成本最低的角度出發(fā)，構(gòu)建了行駛時(shí)間延遲下配送車(chē)輛調(diào)度的干擾管理調(diào)度模型。

除了對(duì)車(chē)輛調(diào)度與干擾事件的研究進(jìn)行分析與總結(jié)，還應(yīng)研究與分析物流配送活動(dòng)中各參與主體的行為感知因素。Simon[16]第一個(gè)在其研究中認(rèn)為只有人類(lèi)有能力進(jìn)行判斷與決策，認(rèn)為判斷與決策能力是人類(lèi)頭腦與思想活動(dòng)的表現(xiàn)，與人們的各種日常經(jīng)驗(yàn)、情感等息息相關(guān)。而劉作儀和查勇[17]則將行為感知這一概念引入國(guó)內(nèi)，在對(duì)國(guó)外行為研究的基礎(chǔ)上提出了行為運(yùn)作管理這一概念。王建軍等[18]從企業(yè)管理者、車(chē)間工人和客戶三方進(jìn)行基于前景理論的擾動(dòng)度量，并建立同時(shí)考慮初始成本目標(biāo)和基于行為運(yùn)籌擾動(dòng)目標(biāo)的干擾管理模型。丁秋雷[19]結(jié)合行為科學(xué)中對(duì)人的行為感知的研究方法與運(yùn)籌學(xué)中的定量研究，通過(guò)分析客戶時(shí)間窗變化這類(lèi)干擾事件對(duì)客戶、物流配送運(yùn)營(yíng)商和配送業(yè)務(wù)員等受擾主體的影響，構(gòu)建了客戶時(shí)間窗變化的字典序多目標(biāo)干擾管理模型。

當(dāng)前許多國(guó)內(nèi)外專(zhuān)家學(xué)者對(duì)車(chē)輛調(diào)度干擾管理問(wèn)題進(jìn)行了分析與總結(jié)，現(xiàn)有的研究大多從顧客層面對(duì)配送干擾問(wèn)題進(jìn)行研究，而對(duì)以車(chē)輛故障為背景的物流供應(yīng)商和配送員工產(chǎn)生干擾事件的研究并不完善，考慮到物流供應(yīng)商和配送員工的干擾事件也會(huì)影響企業(yè)的物流配送服務(wù)與顧客滿意度。因此，本文針對(duì)配送過(guò)程中的配送車(chē)輛故障這一干擾問(wèn)題，結(jié)合各配送主體的行為感知因素，在對(duì)各配送主體的感知因素進(jìn)行提取和度量的基礎(chǔ)上，構(gòu)建車(chē)輛調(diào)度模型，并設(shè)計(jì)改進(jìn)算法對(duì)模型進(jìn)行求解。

2 考慮配送主體感知的救援車(chē)輛調(diào)度模型

2.1 問(wèn)題描述

在配送車(chē)輛進(jìn)行配送時(shí)，有且僅有車(chē)輛故障這一干擾事件，不考慮惡劣的天氣狀況、道路阻塞與顧客需求變動(dòng)等其他情況；在配送車(chē)輛進(jìn)行配送時(shí)，可實(shí)時(shí)獲取每輛配送車(chē)輛的坐標(biāo)、車(chē)載余量、已服務(wù)顧客和未服務(wù)顧客等信息；在出現(xiàn)車(chē)輛故障這一干擾事件后，應(yīng)根據(jù)當(dāng)時(shí)配送車(chē)輛位置以及為服務(wù)顧客等進(jìn)行救援；所有配送車(chē)輛應(yīng)該以企業(yè)的物流中心為初始位置與終點(diǎn)；出現(xiàn)干擾事件后，當(dāng)時(shí)以完成配送任務(wù)并回到物流中心的配送車(chē)輛不參與故障車(chē)輛的救援活動(dòng)。

2.2 參數(shù)及變量說(shuō)明

具體參數(shù)如下[20]：

K—初始配送車(chē)輛調(diào)度方案中提供配送服務(wù)的全部車(chē)輛；

K'—干擾事件后提供救援服務(wù)的全部車(chē)輛；

μk—產(chǎn)生干擾事件時(shí)，正常配送車(chē)輛的實(shí)時(shí)地點(diǎn)；M—μk的集合；

bi—產(chǎn)生干擾事件時(shí)，出現(xiàn)故障的配送車(chē)輛位置及其虛擬點(diǎn)，i∈K'；B—bi的集合；

Q—車(chē)輛的最大載重量；

Qk—車(chē)輛k裝載貨物重量；

—產(chǎn)生干擾事件時(shí)，正常配送車(chē)輛還需配送的貨物量；

—產(chǎn)生干擾事件時(shí)，出現(xiàn)故障的車(chē)輛還需配送的貨物量；

Cij—顧客i與j之間的距離；

qi—正常服務(wù)車(chē)輛還應(yīng)為顧客i配送的貨物量，i∈Sk；

—出現(xiàn)故障的車(chē)輛還應(yīng)為顧客j配送的貨物量，j∈Sb；

k0—出現(xiàn)故障的配送車(chē)輛；

ω—不在顧客接受服務(wù)時(shí)間范圍內(nèi)應(yīng)受到的懲罰；

Sk—發(fā)生故障時(shí)，正常車(chē)輛還未服務(wù)的顧客集合；

Sb—發(fā)生故障時(shí)，故障車(chē)輛還未服務(wù)的顧客集合；

Sik—車(chē)輛k到達(dá)顧客i的時(shí)間；

Sk0k—救援車(chē)輛到達(dá)故障配送車(chē)輛處提取貨物的時(shí)間；

Pk—救援車(chē)輛從故障配送車(chē)輛k0處所需提取的貨物量；

Ei—顧客i最早能接受服務(wù)的時(shí)間限制；

Li—顧客i最晚能接受服務(wù)的時(shí)間限制；

tijk—車(chē)輛k從顧客i行駛到顧客j的時(shí)間；

Δtik—車(chē)輛k可以超過(guò)顧客i服務(wù)時(shí)間的最大范圍；

Tk—原計(jì)劃中車(chē)輛完成任務(wù)回到配送中心所需時(shí)間；

xik'={1在救援計(jì)劃中車(chē)輛k為顧客i提供服務(wù)0其他 。

2.3 模型建立

在對(duì)各變量進(jìn)行參數(shù)設(shè)置及配送主體行為感知因素提取和度量后，建立考慮顧客、物流供應(yīng)商與配送員工行為感知的救援車(chē)輛調(diào)度模型，所構(gòu)建的模型以顧客的不滿意度、物流供應(yīng)商的不滿意度以及配送員工的不滿意度為求解目標(biāo)[20]。

模型中，式（1）為顧客的不滿意度；式（2）為物流供應(yīng)商的不滿意度；式（3）為配送員工的不滿意度；式（4）是指采用理想點(diǎn)法對(duì)目標(biāo)函數(shù)進(jìn)行優(yōu)化；式（5）為在初始調(diào)度方案中運(yùn)輸車(chē)輛非滿載出發(fā)；式（6）表示在初始調(diào)度方案的運(yùn)輸車(chē)輛中，第k輛車(chē)的實(shí)際載貨量小于第k-1輛車(chē)的剩余裝載量；式（7）表示所有運(yùn)輸車(chē)輛運(yùn)送完全部貨物后，都應(yīng)返回起始位置；式（8）表示每輛配送車(chē)輛承擔(dān)的配送任務(wù)應(yīng)小于其實(shí)際承受能力；式（9）表示除干擾點(diǎn)外，僅能為各個(gè)顧客提供一次配送服務(wù)，所有顧客的需求不可拆分；式（10）表示所有出現(xiàn)故障的配送車(chē)輛至少應(yīng)救援一次；式（11）表示未受車(chē)輛故障干擾的配送車(chē)輛仍為原客戶提供配送服務(wù)；式（12）表示所有的救援車(chē)輛應(yīng)先到故障車(chē)輛處提取貨物，再為受干擾顧客提供配送服務(wù)；式（13）表示應(yīng)提取故障車(chē)輛所需配送的所有剩余貨物；式（14）表示應(yīng)合理安排所有配送車(chē)輛的行駛路線，所有配送車(chē)輛應(yīng)完成配送任務(wù)后再返回配送中心；式（15）表示救援車(chē)輛提供的配送服務(wù)量為其從故障車(chē)輛處所提取的貨物；式（16）表示只有一輛救援車(chē)輛到故障車(chē)輛處提取貨物，能且僅能提取一次；式（17）表示客戶可以接受服務(wù)的最大時(shí)間范圍。

3 救援車(chē)輛優(yōu)化調(diào)度模型優(yōu)化算法設(shè)計(jì)

在種子群算法初始化的過(guò)程中，以免疫算法里記憶細(xì)胞的工作原理，對(duì)父代種群進(jìn)行篩選，初始化得到的N個(gè)初代父種用實(shí)值向量來(lái)表示，即[21]：

其中，N的大小由待求問(wèn)題的規(guī)模來(lái)決定。

免疫算法的執(zhí)行效率很大程度上取決于疫苗的選取和接種疫苗的位置，優(yōu)良的疫苗是免疫算子有效發(fā)揮作用的基礎(chǔ)和保障，同時(shí)為了使算法順利運(yùn)行，還應(yīng)注意提取疫苗信息的方式，應(yīng)采取自適應(yīng)的方式[22]。

（1）自適應(yīng)疫苗特征信息的設(shè)計(jì)。應(yīng)該根據(jù)疫苗的不同適應(yīng)度選擇不同程度的信息提取率，具體方式如下：

其中，fmax—最大適應(yīng)度值；ˉ—父種的平均適應(yīng)度值；f′—用于交叉的父種的適應(yīng)度值。

（2）疫苗接種點(diǎn)的自適應(yīng)選擇。通常情況下，應(yīng)該隨機(jī)選擇算法的接種點(diǎn)。但是，在種群具有相似基因的情況下，會(huì)降低算法的可靠性，因此為了改善隨機(jī)接種點(diǎn)對(duì)算法的影響，本文根據(jù)父種適應(yīng)度來(lái)選擇接種點(diǎn)的方式，具體公式如下[23]：

式中，l表示父種種分量的個(gè)數(shù)，f1為最優(yōu)父種的適應(yīng)度值，f2為其他待接種的疫苗的適應(yīng)度值。

判斷是否達(dá)到終止條件。將每次迭代的最優(yōu)父種記為PBEST,將全局迭代產(chǎn)生的最優(yōu)父種記為GBEST,當(dāng)?shù)玫搅死硐氲腉BEST或者GBEST值不再變化時(shí)，結(jié)束運(yùn)行，輸出結(jié)果。

4 算例仿真

本文根據(jù)上文設(shè)計(jì)的考慮配送主體感知的救援車(chē)輛調(diào)度模型，對(duì)配送車(chē)輛的初始調(diào)度方案與發(fā)生車(chē)輛故障這一干擾事件后的救援車(chē)輛調(diào)度方案進(jìn)行仿真試驗(yàn)，并運(yùn)用改進(jìn)種子群優(yōu)化算法對(duì)模型進(jìn)行運(yùn)算，為驗(yàn)證模型的有效性，還將運(yùn)算結(jié)果與粒子群算法的計(jì)算結(jié)果進(jìn)行對(duì)比分析。

4.1 算法求解

在坐標(biāo)系中有24個(gè)需求點(diǎn)和1個(gè)配送中心，各需求點(diǎn)坐標(biāo)及需求情況見(jiàn)表1。由4輛車(chē)來(lái)執(zhí)行配送任務(wù)，在執(zhí)行配送計(jì)劃過(guò)程中車(chē)輛4發(fā)生故障，此時(shí)車(chē)輛4在坐標(biāo)系中的坐標(biāo)為(107.5，41)，其他在途的配送車(chē)輛的具體位置以及客戶信息都可以實(shí)時(shí)獲取，此時(shí)選擇就近救援策略來(lái)對(duì)故障車(chē)輛進(jìn)行救援。

表1 數(shù)據(jù)收集

根據(jù)上文的改進(jìn)種子群優(yōu)化算法，運(yùn)用MATLAB7.0，其中相關(guān)參數(shù)設(shè)置如下：父種個(gè)數(shù)為3，子種群個(gè)數(shù)為3，最大迭代次數(shù)為200，種群規(guī)模為100，另外粒子群中C1=C2=1.494，得到救援車(chē)輛調(diào)度方案見(jiàn)表2，行車(chē)路線如圖1所示。

表2 救援車(chē)輛調(diào)度方案

圖1 救援車(chē)輛行車(chē)路線

4.2 對(duì)比分析

為驗(yàn)證上文所設(shè)計(jì)的改進(jìn)種子群優(yōu)化算法是否適用，采用粒子群優(yōu)化算法對(duì)模型進(jìn)行求解對(duì)比，具體的救援車(chē)輛的調(diào)度方案見(jiàn)表3，行車(chē)路線如圖2所示。

表3 粒子群優(yōu)化算法求解救援車(chē)輛調(diào)度方案

圖2 遺傳算法求解救援車(chē)輛行車(chē)路線

分別用粒子群算法和改進(jìn)種子群優(yōu)化算法對(duì)上文構(gòu)建的考慮行為的救援車(chē)輛調(diào)度模型進(jìn)行求解，比較兩種算法的求解結(jié)果：

（1）顧客不滿意度對(duì)比。用粒子群算法和改進(jìn)種子群優(yōu)化算法得出的顧客不滿意度分別為0.931和0.797，對(duì)比結(jié)果如圖3所示，從圖中可以看出，粒子群算法的收斂速度要慢于改進(jìn)種子群優(yōu)化算法。因此，改進(jìn)種子群優(yōu)化算法具有較好的適用性，更為適用于模型的求解。

圖3 顧客不滿意度對(duì)比圖

（2）服務(wù)商不滿意度對(duì)比。本文所建立的模型中，運(yùn)用綜合成本來(lái)代表物流供應(yīng)商的不滿意度，綜合成本主要包括配送車(chē)輛的購(gòu)置、運(yùn)行與維修費(fèi)用以及超過(guò)顧客接受的時(shí)間窗的損失與賠償費(fèi)用。從圖4可以看出，運(yùn)用粒子群算法與改進(jìn)種子群優(yōu)化算法對(duì)模型進(jìn)行求解得到的結(jié)果分別為4 930和3 690，而且改進(jìn)種子群優(yōu)化算法的收斂速度明顯快于粒子群算法，具有明顯的優(yōu)越性。

圖4 物流供應(yīng)商不滿意度對(duì)比圖

（3）配送員工不滿意度對(duì)比。配送車(chē)輛的服務(wù)時(shí)間超過(guò)原計(jì)劃的服務(wù)時(shí)間是配送員工不滿意的主要原因，運(yùn)用粒子群算法和改進(jìn)種子群優(yōu)化算法進(jìn)行運(yùn)算，得出的配送員工不滿意度如圖5所示，粒子群算法和改進(jìn)種子群優(yōu)化算法的計(jì)算結(jié)果分別為69.51和58.36，且改進(jìn)種子群優(yōu)化算法的運(yùn)算速度較快。因此，改進(jìn)種子群優(yōu)化算法的計(jì)算結(jié)果明顯優(yōu)于粒子群算法。

5 結(jié)語(yǔ)

文章從車(chē)輛故障的干擾管理角度入手，在對(duì)配送過(guò)程中的三個(gè)行為主體即顧客、配送員工與物流供應(yīng)商進(jìn)行分析后，度量車(chē)輛故障對(duì)配送任務(wù)所造成的擾動(dòng)，并建立了考慮配送主體感知的救援車(chē)輛調(diào)度模型。此外，采用免疫算法對(duì)種子群算法進(jìn)行優(yōu)化，設(shè)計(jì)出改進(jìn)種子群優(yōu)化算法，并運(yùn)用算法對(duì)模型進(jìn)行求解，通過(guò)對(duì)比粒子群算法與改進(jìn)種子群算法對(duì)模型的求解結(jié)果可以得出結(jié)論，改進(jìn)種子群優(yōu)化算法具有明顯的優(yōu)越性。所構(gòu)建的模型與算法能夠在考慮配送主體感知的基礎(chǔ)上，及時(shí)地做出針對(duì)車(chē)輛故障這類(lèi)干擾事件的救援方案，豐富和完善了車(chē)輛調(diào)度和干擾管理理論。

圖5 配送員工不滿意度對(duì)比圖

[]

[1]張娜娜,謝偉.中國(guó)電子商務(wù)模式創(chuàng)新的合法化機(jī)制—基于淘寶網(wǎng)的案例研究[J].科學(xué)學(xué)與科學(xué)技術(shù)管理,2014,5(10):133-141.

[2]馮暉.現(xiàn)代物流學(xué)[M].北京:科學(xué)出版社,2011.

[3]Dantzig G B,Ramser J H.The truck dispatching problem[J].Management Science,1959,6(1):80-91

[4]Pillac V,Gendreau M,Gueret C.A review of dynamic vehicle routing problems[J].European Journal of Operational Research,2013,225(1):1-11.

[5]張群,顏瑞.基于改進(jìn)模糊遺傳算法的混合車(chē)輛路徑問(wèn)題[J].中國(guó)管理科學(xué),2012,20(2):121-128.

[6]葉勇,張惠珍.多配送中心車(chē)輛路徑問(wèn)題的狼群算法[J].計(jì)算機(jī)應(yīng)用研究,2017,(9):1-7.

[7]吳緒.配送車(chē)輛受擾下車(chē)輛調(diào)度干擾管理問(wèn)題研究[D].大連:大連理工大學(xué),2010.

[8]王明春,成修,永廷.VRPTW的擾動(dòng)恢復(fù)及其TABU SEARCH算法[J].數(shù)學(xué)雜志,2006,26(2):231-236.

[9]Dennis Huisman,Richard Freling,Albert P M Wagelmans.A robust solution approach to the dynamic vehicle scheduling problem[J].Transportation Science,2004,38(4):447-458.

[10]Jesper Larsen,Michael Liee,Kim Riis Serensen,et al.Disruption Management for an Airline Rescheduling of aircraft[J].Applications of Evolutionary Computing,2002,(3):315-324.

[11]S F Smith,M A Becker,L A Krame.Continuous Management of Airlift and Tanker Resources:A Const raint-Based Approach[J].Mathematical and Computer Modeling,2004,39(6):581-598.

[12]Mu Q,Fu Z,Lysgaard J,et al.Disruption management of the vehicle routing problem with vehicle breakdown[J].Journal of the Operational Research Society,2011,62(4):742-749.

[13]Figliozzi M A.The time dependent vehicle routing problem with time windows:Benchmark problems,an efficient solution algorithm,and solution characteristics[J].Transportation Research Part E:Logistics and Transportation Review,2012,48(3):616-636.

[14]王旭坪,阮俊虎,孫自來(lái),等.帶回程取貨車(chē)輛路徑問(wèn)題的干擾恢復(fù)模型[J].系統(tǒng)工程學(xué)報(bào),2013,28(5):608-616.

[15]王征,胡祥培,王旭坪.行駛時(shí)間延遲下配送車(chē)輛調(diào)度的干擾管理模型與算法[J].系統(tǒng)工程理論與實(shí)踐,2013,33(2):378-387.

[16]Simon H A.Rational choice and the structure of the environment[J].Psychological review,1956,63(2):129-145.

[17]劉作儀,查勇.行為運(yùn)作管理:一個(gè)正在顯現(xiàn)的研究領(lǐng)域[J].管理科學(xué)學(xué)報(bào),2009,12(4):64-74.

[18]王建軍,劉亞凈,劉鋒,等.考慮行為主體的置換流水車(chē)間干擾管理研究[J].系統(tǒng)工程理論與實(shí)踐,2015,35(12):3 092-3 106.

[19]丁秋雷.客戶時(shí)間窗變化的物流配送干擾管理模型—基于行為的視角[J].中國(guó)管理科學(xué),2015,23(5):89-97.

[20]邵松娟.考慮配送主體感知的救援車(chē)輛調(diào)度研究[D].邯鄲:河北工程大學(xué),2016.

[21]張曉明.基于種子傳播方式和植物分布演化的種子優(yōu)化算法研究[D].合肥:中國(guó)科學(xué)技術(shù)大學(xué),2011.

[22]靳宗信,劉寒冰,樊紅娟.基于動(dòng)態(tài)疫苗提取的免疫遺傳算法求解TSP問(wèn)題[J].現(xiàn)代計(jì)算機(jī)(專(zhuān)業(yè)版),2010,(4):20-22.

[23]趙麗飛.考慮客戶等級(jí)劃分的車(chē)輛調(diào)度干擾管理研究[D].邯鄲:河北工程大學(xué),2017.