葛顯龍，薛桂琴

(重慶交通大學(xué) 經(jīng)濟與管理學(xué)院，重慶 400074)

0 引言

互聯(lián)網(wǎng)經(jīng)濟的發(fā)展推動了需求的個性化和碎片化，使企業(yè)物流配送管理充滿了不確定性，從而促使越來越多的企業(yè)希望根據(jù)累積的線上線下客戶歷史需求數(shù)據(jù)，利用數(shù)據(jù)分析和數(shù)據(jù)挖掘技術(shù)，預(yù)測客戶需求，洞悉市場變化，為制定科學(xué)的配送決策提供數(shù)據(jù)支持。此外，在配送決策實施過程中，企業(yè)往往將成本相近的客戶需求進行聚類，以實現(xiàn)便捷配送和低成本配送。因為需求預(yù)測直接影響車輛路徑優(yōu)化，且二者存在先后順序，所以將本文研究稱為基于前攝性調(diào)度的車輛路徑問題(Vehicle Routing Problem, VRP)。

從客戶歷史屬性出發(fā)進行動態(tài)客戶預(yù)測一直是國內(nèi)外學(xué)者研究需求不確定性的重要手段，F(xiàn)errucci等[1]對歷史數(shù)據(jù)進行了時間和空間上的聚類，構(gòu)建了前攝性VRP的基本體系；Sha等[2]根據(jù)備件需求的歷史數(shù)據(jù)對備件需求動態(tài)情況進行了前攝性預(yù)測，確保了備件配送的時效性；Ma等[3]引入交叉競爭策略，通過庫存數(shù)據(jù)預(yù)測客戶需求量；王亮等[4]利用前景理論描述動態(tài)客戶屬性，并根據(jù)決策者的主觀風(fēng)險認知確定不同的決策方案；周艷菊等[5]利用前景理論描述零售商的訂貨行為，分析了不同期望下零售商的訂貨偏好；Wohlgemuth等[6]分析了動態(tài)VRP中的旅行時間連續(xù)性和短時間內(nèi)需求區(qū)域整合等問題，并得出前攝性調(diào)度策略能夠提升車輛利用率的結(jié)論；Thomas[7]設(shè)計實時啟發(fā)式算法預(yù)測未來客戶位置和需求出現(xiàn)概率等信息，顯著降低了客戶服務(wù)延遲率；Lima等[8]從客戶的需求期望和企業(yè)自身條件入手，利用歷史數(shù)據(jù)和在線數(shù)據(jù)監(jiān)視等手段預(yù)測客戶動態(tài)需求，提高了客戶需求響應(yīng)的靈活性；Polacek等[9]通過分析客戶屬性，將客戶需求分為日配送和周配送兩種模式進行聚類，并建立其與實際地理位置的映射，從而保證了配送的穩(wěn)定性，降低了配送成本；Rahimi-Vahed等[10]綜合考慮多車場VRP、周期VRP和多車廠周期VRP 3類問題，設(shè)計了模塊化啟發(fā)式策略進行問題求解；Lei等[11-14]系統(tǒng)分析了隨機需求量、隨機服務(wù)時間、隨機客戶、隨機需求可拆分4種情況下的動態(tài)客戶分區(qū)聚類算法和配送路徑優(yōu)化方案設(shè)計；曹高立等[15]設(shè)計了求解帶容量限制的VRP的量子進化算法。

上述研究分別從動態(tài)客戶預(yù)測、分區(qū)聚類和車輛路徑優(yōu)化3個角度研究了配送車輛動態(tài)調(diào)度問題，但多從單一角度開展相關(guān)研究。為此，本文在利用客戶需求的歷史表現(xiàn)預(yù)測動態(tài)需求的基礎(chǔ)上，提出單周期和多周期配送路徑優(yōu)化的數(shù)學(xué)模型，設(shè)計了前攝性車輛調(diào)度方案來優(yōu)化配送流程，從而實現(xiàn)客戶需求的快速響應(yīng)。

1 問題描述

本文研究的問題可描述為：在確定的服務(wù)區(qū)域內(nèi)，存在若干需求不變和動態(tài)變化客戶(下文統(tǒng)一采用術(shù)語“靜態(tài)客戶”和“動態(tài)客戶”描述)，采用前景理論計算每個動態(tài)客戶的前景值，并以此作為動態(tài)客戶的接受值；根據(jù)靜態(tài)客戶及已接受動態(tài)客戶的空間分布將服務(wù)區(qū)域分割為若干子區(qū)域，各子區(qū)域互不重疊；在一個確定的服務(wù)周期內(nèi)，僅調(diào)度一輛車為特定子區(qū)域提供服務(wù)。同時，將每個子區(qū)域空間重心視為“前攝性調(diào)度中心”，采用分散調(diào)度策略，由車輛自主決定客戶服務(wù)路徑，快速響應(yīng)動態(tài)客戶。由于在不同服務(wù)周期內(nèi)動態(tài)客戶的前景值不同，導(dǎo)致前攝性調(diào)度中心偏移至動態(tài)客戶前景值較大的區(qū)域。

圖1所示為單周期前攝性調(diào)度示意圖，其分為兩個階段：第1階段為在每個周期開始時，車輛由配送中心出發(fā)，前往預(yù)定的前攝性調(diào)度中心；第2階段為車輛由前攝性調(diào)度中心出發(fā)，前往服務(wù)客戶位置以響應(yīng)客戶需求。

單周期前攝性調(diào)度方案僅根據(jù)某一周期內(nèi)客戶的空間分布特性聚類，并進行路徑優(yōu)化。然而在動態(tài)需求情況下，不同周期內(nèi)待服務(wù)客戶位置是動態(tài)變化的，這必然導(dǎo)致不同周期聚類結(jié)果之間存在某些差異。圖2所示為包括T1和T2兩個配送周期的前攝性車輛調(diào)度方案示意圖，其中T1周期仍采用圖1所示的配送方案，T2周期出現(xiàn)3個無需服務(wù)客戶和4個新增客戶(包括靜態(tài)客戶和預(yù)測挖掘的動態(tài)客戶)。則為T2周期設(shè)計的的最優(yōu)調(diào)度方案如圖2b所示。

2 數(shù)學(xué)模型

2.1 單周期前攝性車輛調(diào)度數(shù)學(xué)模型

假定在某一配送周期內(nèi)，配送區(qū)域被劃分為K個前攝性子區(qū)域，在此基礎(chǔ)上建立單周期前攝性VRP的數(shù)學(xué)模型，模型涉及符號如下：

(1)用無向圖G(A,N)表示服務(wù)區(qū)域，其中A表示節(jié)點之間的鏈接集合，N表示服務(wù)區(qū)域的客戶集合；配送中心的位置記為O，各聚類中心為Oki；靜態(tài)客戶和動態(tài)客戶分別記為Ns，Nr；區(qū)域k包含的客戶數(shù)為nk，區(qū)域k的面積為Ak。

(2)配送中心有相同規(guī)格的汽車v，共有V輛；客戶i的需求量為qi，分區(qū)k的需求量為qk；車輛的最大載重量記為Q，在任一條車輛路徑上客戶的總需求量必須小于車輛的最大載重量。

(3)使用決策變量xvij標識車輛是否經(jīng)過某個客戶位置，xvij=0表示客戶被服務(wù)后，車輛不需要再從客戶行駛到客戶；xvij=1表示車輛服務(wù)客戶后直接行駛到客戶j為其服務(wù)。用決策變量yki標識客戶i在分區(qū)k內(nèi)的歸屬關(guān)系，如果客戶i在分區(qū)k內(nèi)，則參數(shù)yki=1，否則yki=0。

(4)任意兩個客戶之間的路徑成本為dij。

由此確定以服務(wù)完所有分區(qū)內(nèi)客戶的總成本最小為目標函數(shù)，模型如下：

minZ=Z1+Z2+Z3。

(1)

s.t.

(2)

K≤V；

(3)

(4)

qxkij-qxkjm≥qj，i,j,m∈N；

(5)

(6)

(7)

(8)

(9)

(10)

α≤0,β≥0。

(11)

其中：式(1)為設(shè)計的目標函數(shù)，即服務(wù)完所有分區(qū)客戶的總成本最小，第1項為在每個前攝分區(qū)內(nèi)路徑成本，第2項為動態(tài)客戶的服務(wù)附加成本，第3項為補貨車輛成本；式(2)表示該周期需要的配送車輛數(shù)，[]運算符對浮點數(shù)執(zhí)行向上取整操作，對正整數(shù)不做任何操作；式(3)表示該服務(wù)周期內(nèi)的服務(wù)區(qū)域分區(qū)數(shù)目應(yīng)少于配送中心的實際可用車輛數(shù)；式(4)表示所有客戶需求量不大于配送中心實際可提供的服務(wù)供給量；式(5)表示為客戶i服務(wù)之前，車輛的實際載貨量不小于客戶i的需求量；式(6)表示所有派往前攝性調(diào)度中心的車輛在服務(wù)完其子區(qū)域內(nèi)所有客戶后必須返回配送中心；式(7)表示各配送子區(qū)域內(nèi)的客戶需求總量不小于靜態(tài)客戶需求總量；式(8)表示流量均衡約束，即前往一個客戶點的車輛必須從該客戶點離開；式(9)表示所有位于子區(qū)域k內(nèi)的客戶由同一車輛服務(wù)；式(10)表示所有分區(qū)面積之和等于服務(wù)區(qū)總面積，即不存在未服務(wù)的分區(qū)；式(11)中α,β分別為動態(tài)客戶服務(wù)成功獎勵因子和服務(wù)失敗懲罰因子。

2.2 多周期車輛調(diào)度數(shù)學(xué)模型

車輛在每個服務(wù)周期的開始時刻，由配送中心出發(fā)前往事先確定的前攝性調(diào)度中心；然后根據(jù)客戶需求屬性選擇最優(yōu)路徑，快速響應(yīng)客戶需求。車輛服務(wù)完區(qū)域內(nèi)的所有客戶后，在配送周期結(jié)束時刻返回配送中心。對于傳統(tǒng)靜態(tài)車輛調(diào)度問題，不同配送周期內(nèi)的配送范圍較穩(wěn)定，出現(xiàn)較大偏差的可能性不大；而在前攝性車輛調(diào)度問題中，由于考慮動態(tài)需求，動態(tài)客戶在不同周期內(nèi)的變動導(dǎo)致不同周期的分區(qū)模式不同。同時，當期客戶聚類中心與往期聚類中心位置變化越大，企業(yè)對該客戶所在區(qū)域服務(wù)的穩(wěn)定性越差。因此，定義矩陣Vi為某周期任意聚類中心到上周期所有聚類中心的距離鄰接向量，相鄰周期各聚類中心間的距離鄰接矩陣可以表示為M=[V1，V2,…,Vi,…,Vk]，則兩個相鄰周期服務(wù)離散度

(12)

單周期車輛調(diào)度問題以該周期內(nèi)所有分區(qū)調(diào)度成本最小為目標；多周期調(diào)度問題除單周期調(diào)度目標外，如果某一車輛能夠為某一區(qū)域的客戶提供經(jīng)常性的服務(wù)，則有助于提升客戶粘性，增強客戶忠誠度。因此在多周期調(diào)度目標函數(shù)中引入各周期分區(qū)數(shù)和區(qū)域離散度兩個指標，構(gòu)建W個周期內(nèi)服務(wù)N個客戶的調(diào)度模型如下：

(13)

(14)

(15)

Nw≤N，w∈W；

(16)

(17)

(18)

(19)

Sdev≥0。

(20)

其中：式(13)為多周期車輛調(diào)度的目標函數(shù)，第1項為單周期服務(wù)成本，第2項為分區(qū)數(shù)，第3項為服務(wù)離散度；式(14)為客戶歸屬約束，即客戶在某一周期出現(xiàn)，必從屬于該周期的某個聚類中心；式(15)為服務(wù)時間約束，即客戶所需的服務(wù)時間不大于其所屬聚類中心服務(wù)客戶的總時間；式(16)表示任意周期內(nèi)客戶總數(shù)不大于全區(qū)域內(nèi)客戶總數(shù)；式(17)表示任意聚類中心的服務(wù)供給量不大于車輛的核定載重量；式(18)表示任意聚類中心服務(wù)的客戶數(shù)不大于本周期客戶總數(shù)；式(19)表示任意周期內(nèi)的聚類數(shù)不大于企業(yè)可用車輛數(shù)；式(20)表示服務(wù)離散度，為非負數(shù)。

3 前攝性調(diào)度方案設(shè)計

本文提出的前攝性車輛方案由前攝性動態(tài)客戶評估方法、前攝性分區(qū)聚類方法和配送路徑優(yōu)化方法3部分構(gòu)成。前攝性動態(tài)客戶評估方法旨在根據(jù)客戶的歷史表現(xiàn)，逐層分解出現(xiàn)在系統(tǒng)中的歷史客戶需求，進而挖掘客戶需求潛力，提前預(yù)知客戶需求動向，識別動態(tài)需求；前攝性分區(qū)聚類方法旨在根據(jù)客戶的空間分布特性，前攝性地引導(dǎo)車輛前往需求出現(xiàn)概率更大的區(qū)域；前攝性路徑優(yōu)化算法旨在為每個客戶分區(qū)設(shè)計最優(yōu)配送路徑，降低配送成本。

3.1 前攝性動態(tài)客戶評估方法

(21)

(22)

(23)

當動態(tài)需求前景值為正時，μ1越大，相同前景值評估水平下，決策者的客戶選擇決策越樂觀；在動態(tài)需求前景值為負時，μ2越大，相同前景值評估水平下，決策者的客戶選擇決策越悲觀。依據(jù)決策者對動態(tài)客戶前景值的評估，選擇符合決策風(fēng)險偏好的動態(tài)客戶，將動態(tài)客戶與動態(tài)客戶合并后組成待服務(wù)客戶群。

3.2 前攝性分區(qū)聚類方法

確定一個周期的待配送客戶群后，如何調(diào)度車輛對這些客戶進行快速響應(yīng)，是企業(yè)戰(zhàn)勝競爭對手、贏得市場主動權(quán)的關(guān)鍵。由于客戶對配送時間相當敏感，如果配送企業(yè)無法依照其與客戶約定的配送時間將客戶所需的商品及時送達，或配送時間與客戶通過其他渠道獲取的服務(wù)時間相當，那么企業(yè)將面臨部分客戶流失的風(fēng)險。因為待服務(wù)客戶群中的動態(tài)客戶由前攝性動態(tài)客戶評估方法得到，無法確保在配送過程中一定出現(xiàn)，僅以實際需求量為約束聚類會導(dǎo)致聚類自區(qū)域邊界的無效擴張，所以在聚類算法中添加服務(wù)半徑擴張因子u和載重量膨脹因子v，允許聚類區(qū)域內(nèi)的需求量(靜態(tài)客戶需求量及可能產(chǎn)生的動態(tài)客戶需求量)大于車輛荷載，但是車輛在離開配送中心時不允許超載。本文設(shè)計的前攝性分區(qū)聚類方法的具體步驟如下：

步驟1根據(jù)已知的客戶坐標數(shù)據(jù)，計算配送中心與所有客戶的鄰接矩陣。

步驟2以每個節(jié)點i為圓心，在服務(wù)半徑R內(nèi)進行搜索，記錄落在該范圍內(nèi)的客戶節(jié)點，選擇包含客戶節(jié)點最多的圓所覆蓋的區(qū)域為前攝服務(wù)子區(qū)域。

步驟3生成前攝性服務(wù)子區(qū)域。

(1)重心法確定該子區(qū)域的前攝性調(diào)度中心。

(2)判斷初始服務(wù)子區(qū)域內(nèi)的客戶需求總量QD(iter)是否大于車輛載重Q，大于則為真，執(zhí)行(3)；小于則為假，執(zhí)行(4)。

(3)計算落在該子區(qū)域內(nèi)的客戶與前攝性調(diào)度中心的距離，得到以遞減順序排序的客戶序列MD，剔除序列MD的第一個元素，得到QD(iter+1)，執(zhí)行(5)。

(4)將搜索半徑擴大為uR，判斷UR≤Rmax是否為真，為真則執(zhí)行(2)，否則執(zhí)行步驟4。

(5)判斷QD(iter)

步驟4移除步驟3生成服務(wù)子區(qū)域內(nèi)包含的客戶，執(zhí)行步驟5。

步驟5判斷所有客戶是否以被包含在所有聚類中，如果判斷結(jié)果為假，則執(zhí)行步驟2;如果判斷結(jié)果為真，則算法終止。

由于聚類算法中加入了載重量膨脹因子，可能出現(xiàn)車輛超載現(xiàn)象，這在實際應(yīng)用場景下是不允許的，為此，在配送中心和各前攝性調(diào)度中心之間使用補貨車輛對各分區(qū)進行補貨，以解決實際配送需求量大于車輛荷載子區(qū)域的配送差額問題。

3.3 前攝性車輛路徑優(yōu)化算法

量子遺傳算法是VRP中常用的經(jīng)典算法，算法步驟為：假定有MC個客戶，則可以構(gòu)造MC×MC×2的量子比特矩陣，由此矩陣建立量子種群。對量子種群進行觀測，得到橫軸為客戶服務(wù)順序、縱軸為客戶編號的0-1觀測矩陣OM；根據(jù)3.1節(jié)規(guī)定的模型約束條件，將觀測矩陣轉(zhuǎn)化為初始路徑集合。

(24)

式(24)表示MC=5時對應(yīng)的0-1觀測矩陣OM，得到的客戶服務(wù)順序為2-1-4-3-5；當客戶序列滿足當前車輛約束時，增派新車進行服務(wù)，并通過在原始序列對應(yīng)的位置插入0表示。例如，對于5個客戶的序列，假設(shè)當前車輛約束僅在編號為4的客戶處被打破，則其對應(yīng)的初始路徑為0-2-1-0-4-3-5-0。

量子遺傳算法的適應(yīng)度值使用單周期調(diào)度模型目標函數(shù)值的倒數(shù)，當對應(yīng)個體不滿足3.1節(jié)規(guī)定的約束條件時，附加一個較大的常數(shù)C=10 000，淘汰種群中的非可行解。量子遺傳算法的選擇算子仍采用傳統(tǒng)的輪盤賭選擇法，而交叉算子采用最優(yōu)子串提取策略，其原理為分別提取兩個父代個體中包含客戶數(shù)目最多的子串放置到另一個父代個體的首部，剩余客戶按照規(guī)定的約束條件進行路徑更新，如圖3所示。變異算子為隨機選擇一條染色體，在該染色體上隨機產(chǎn)生一個基因變異位，若該變異位非0，則將該基因位變異為新基因，否則重新生成基因變異位。

綜上，本文設(shè)計的前攝性車輛調(diào)度方案完整流程如圖4所示。

4 仿真分析

4.1 算例描述

本文算例以重慶某超市的客戶需求數(shù)據(jù)為基礎(chǔ)，對數(shù)據(jù)進行脫敏處理后作為本文的仿真測試數(shù)據(jù)。該超市原始的配送方案將每一周期配送任務(wù)分為兩個階段：第1階段為所有靜態(tài)客戶提供服務(wù)，并返回配送中心；第2階段為第1階段服務(wù)失敗，和第1階段未出現(xiàn)而在第2階段配送前出現(xiàn)的客戶進行服務(wù)。原始配送方案未考慮動態(tài)客戶的前景值評估。前攝性調(diào)度方案是通過分析客戶屬性的歷史表現(xiàn)，計算動態(tài)客戶前景值，進而將整個服務(wù)區(qū)域的劃分成若干聚類子區(qū)域，車輛僅為特定子區(qū)域內(nèi)的客戶服務(wù)。服務(wù)區(qū)域客戶情況如圖5所示，其中：配送中心坐標為(30,2)，擁有4輛可用車輛，一共有35個需求點。

4.2 單周期調(diào)度測試

某配送周期內(nèi)存在25個靜態(tài)客戶和10個動態(tài)客戶，其分布如圖6所示，其中動態(tài)客戶有無需求及需求的出現(xiàn)時間并未確定。

4.2.1 原始車輛調(diào)度方案

原始車輛調(diào)度方案未考慮動態(tài)客戶前景值評估，僅將配送周期劃分為兩個配送階段：第1階段的服務(wù)客戶群為表1所示的第1階段靜態(tài)客戶；第2階段的服務(wù)客戶群為表1中第2行和第3行所示的客戶，分別采用量子遺傳算法計算這兩個階段的最優(yōu)路徑，最優(yōu)方案如表2所示。

4.2.2 前攝性車輛調(diào)度方案

(1)前攝性動態(tài)客戶評估與分區(qū)聚類

為有效描述服務(wù)區(qū)域內(nèi)動態(tài)客戶出現(xiàn)的情況，選擇客戶依賴度a1、付款速度a2、需求量a33個評估指標刻畫動態(tài)客戶屬性，3個指標對應(yīng)的權(quán)重分別為0.4,0.3,0.3,其中客戶依賴度分為不依賴、輕微依賴、中等依賴、嚴重依賴4個等級，付款速度分為拖延、一般和即時3個等級。根據(jù)式(23)可以推導(dǎo)出客戶依賴度及付款速度計算公式，式中l(wèi)值與客戶屬性的定義順序一致:

(25)

(26)

采用設(shè)定的3個指標衡量10個動態(tài)客戶的客戶屬性，通過計算其前景值來確定動態(tài)客戶服務(wù)期望值。計算前景值時，取μ1=1，μ2=-2.25，考慮到不同客戶屬性量綱不同，對數(shù)據(jù)進行歸一化處理，處理后的動態(tài)客戶前景值如表3所示。

表3 動態(tài)客戶屬性值

表3中，前景值為正，表示決策者對動態(tài)客戶的期望值優(yōu)于以往，予以配送；前景值為負，表示決策者對動態(tài)客戶的期望值劣于以往，決策者會表現(xiàn)出風(fēng)險規(guī)避，不予配送。對比表1與表3可以發(fā)現(xiàn)，采用前景預(yù)測方法成功預(yù)測到了4個動態(tài)客戶，其中客戶8，13預(yù)測到，但并未出現(xiàn)，客戶25預(yù)測失敗，預(yù)測成功率為50%。

將25個靜態(tài)客戶及前景預(yù)測方法得到的6個動態(tài)客戶進行分區(qū)聚類，結(jié)果如圖7所示。圖中將服務(wù)區(qū)域分成3個前攝性子區(qū)域，前攝性調(diào)度中心分別為C1，C2和C3，有效動態(tài)客戶指前景值為正值的動態(tài)客戶，無效動態(tài)客戶指前景值為負值時的動態(tài)客戶。

(2)路徑生成與路徑變更

根據(jù)聚類結(jié)果將圖3中的C1，C2，C3點作為前攝性調(diào)度中心，對其各自所屬圓內(nèi)的客戶進行服務(wù)。因為每個子區(qū)域內(nèi)的需求量均不超過車輛的最大載貨量，所以子區(qū)域內(nèi)的路徑優(yōu)化問題可視為旅行商問題，采用量子遺傳算法計算得到初始子路徑，如表4所示。在補貨階段，調(diào)度補貨車輛為各前攝性調(diào)度中心補貨，之后各前攝性中心分別為其各自區(qū)域內(nèi)的待服務(wù)客戶提供服務(wù)，最優(yōu)補貨路徑如表5所示，則一個完整周期內(nèi)各分區(qū)的總調(diào)度成本如表6所示。

注：表中CG為前攝性調(diào)度方案的全局補貨成本。

4.2.3 對比分析

因為原始車輛調(diào)度方案在第2階段為第1階段的動態(tài)客戶提供服務(wù)，而前攝分區(qū)方案服務(wù)靜態(tài)客戶的時間可能更早，所以對于服務(wù)成功的動態(tài)客戶的單位獎勵因子設(shè)置為路徑成本的3%，動態(tài)客戶服務(wù)失敗的單位懲罰因子為5%，得出兩方案的總成本值如表7所示。

由表7可知，僅對路徑成本而言，前攝性車輛調(diào)度方案的路徑成本較原始車輛調(diào)度方案提高了4%；但原始車輛調(diào)度方案調(diào)度了5次車輛，而前攝性車輛調(diào)度方案僅調(diào)度了4次車輛，調(diào)度次數(shù)減少了25%。在附加動態(tài)客戶服務(wù)獎勵因子后，原始車輛調(diào)度方案成本降低了27.86，而前攝性車輛調(diào)度方案的成本卻降低了70.71，使得前攝性總成本值較原始調(diào)度策略降低了約7%。

原始調(diào)度方案將第2階段的動態(tài)客戶25推遲到下一周期服務(wù)，帶來了一定程度的客戶延遲；本文設(shè)計的前攝性調(diào)度方案雖然預(yù)測失敗，但通過子區(qū)域路徑變更在當前周期為其提供了配送服務(wù)?？蛻?，24，27，32被成功預(yù)測，在配送周期的第一個階段即可實現(xiàn)配送，較原始調(diào)度方案響應(yīng)更早。由此驗證了本文設(shè)計前攝性調(diào)度方案的優(yōu)越性，通過服務(wù)區(qū)域分區(qū)實現(xiàn)了動態(tài)客戶的快速響應(yīng)，即使在預(yù)測失敗情況下，車輛在整個配送周期內(nèi)一直活躍在需求高發(fā)區(qū)域，客戶響應(yīng)更加及時；另外，由于從前攝性調(diào)度中心出發(fā)，配送路徑成本也大大降低。

值得說明的是，本算例中的前攝性調(diào)度方案是以動態(tài)客戶前景值是否大于零作為動態(tài)客戶接受標準，是穩(wěn)健性風(fēng)險決策。其出發(fā)點基于趨利避害的風(fēng)險決策習(xí)慣，在預(yù)測風(fēng)險與預(yù)測收益的折中點選擇接受動態(tài)客戶。然而，不同的決策者對風(fēng)險的感知水平存在差異，因此動態(tài)客戶選擇策略具有可拓展性。對于風(fēng)險承擔(dān)能力較強的決策者，可能會以小于零的某個前景值為標準接受動態(tài)客戶，而對風(fēng)險承擔(dān)能力較弱的決策者可能恰恰相反。同時，考慮到各前攝型子區(qū)域內(nèi)的需求總量可能超過單個車輛的核定載重量，設(shè)置僅通過各前攝性調(diào)度中心的補貨路徑，這也有助于在風(fēng)險承擔(dān)能力較弱時配送成本控制。

4.3 多周期調(diào)度仿真

4.3.1 多周期分區(qū)離散度分析

選取該超市7個周期的配送數(shù)據(jù)，進行前攝分區(qū)聚類，聚類數(shù)均為3，根據(jù)式(4)計算各周期服務(wù)離散度，如圖8所示。因為該超市服務(wù)區(qū)域比較穩(wěn)定，動態(tài)客戶僅在指定區(qū)域內(nèi)動態(tài)變化，所以相鄰周期的聚類中心點在空間位置上比較接近。經(jīng)計算發(fā)現(xiàn)10個周期的離散度最大值為0.18，最小值為0.06，波動幅度為0.12，屬于服務(wù)區(qū)域離散度較小的應(yīng)用場景，與該超市營業(yè)額穩(wěn)定、客戶群相對固定、超市服務(wù)區(qū)位穩(wěn)定的發(fā)展現(xiàn)狀相吻合。

4.3.2 多周期配送成本分析

由于補貨策略的存在，聚類中心數(shù)將直接影響補貨路徑的長度，且隨著聚類中心數(shù)的增加，補貨成本將上升。在本文測試場景下，超市在7個配送周期內(nèi)產(chǎn)生的聚類中心數(shù)均為3個。因此，配送成本分析僅考慮了各周期配送總成本和補貨成本，如表8所示。

比較7個周期的分區(qū)調(diào)度補貨成本可見，當聚類中心比較穩(wěn)定，即服務(wù)區(qū)域離散度較小時，多個周期補貨成本是穩(wěn)定的。因此，穩(wěn)定的分區(qū)數(shù)使前攝性分區(qū)調(diào)度補貨成本處于穩(wěn)定可控狀態(tài)，從而避免了補貨成本不穩(wěn)定對配送成本控制的不利影響。從總服務(wù)成本角度分析，本文設(shè)計的前攝性車輛調(diào)度方案能夠確保企業(yè)在快速響應(yīng)客戶需求的同時獲得穩(wěn)定的配送成本預(yù)期。

4.4 算法性能測試

4.4.1 聚類算法性能測試

為驗證聚類算法的正確性，本文在30×30坐標范圍內(nèi)隨機生成111個點(如圖9)，采用K-mean聚類算法對整個區(qū)域客戶點進行聚類，結(jié)果如圖9a所示；采用本文設(shè)計的聚類算法，對111個客戶點進行聚類，服務(wù)半徑為5時的聚類結(jié)果如圖9b所示。假定以客戶點所在位置為前攝性調(diào)度中心時，本文設(shè)計的聚類算法與K-mean聚類算法在聚類區(qū)域吻合，這也從側(cè)面論證了本文聚類算法的合理性。本文聚類算法中各個聚類區(qū)域的客戶數(shù)目相對比較均衡，即使在客戶分布嚴重失衡的情況下，還可通過調(diào)節(jié)半徑擴張因子實現(xiàn)聚類區(qū)域的自適應(yīng)分區(qū)。圖9a反映的全區(qū)域的聚類結(jié)果也顯示，對設(shè)計仿真數(shù)據(jù)實行前攝性分區(qū)聚類是可行的，即使整個區(qū)域內(nèi)的所有客戶都出現(xiàn)，采用前攝性分區(qū)聚類方法亦能有效覆蓋85%以上的客戶。此外，因為補貨策略的存在，每個前攝性子區(qū)域內(nèi)的貨源都是充足的，即使不在聚類分區(qū)的客戶也能調(diào)度距離其最近的車輛為其快速服務(wù)，所以比從配送中心調(diào)度新車輛為其服務(wù)的時效性要好。

4.4.2 算法性能分析

路徑優(yōu)化算法的性能將直接影響調(diào)度方案的有效性，因此采用TSPLIB數(shù)據(jù)庫提供的標準算例，分別采用蟻群算法、粒子群算法和量子遺傳算法進行路徑優(yōu)化，迭代次數(shù)為1 000，運行50次，得到的最優(yōu)解如表9所示。

表9 量子遺傳算法性能對比表

由表9可知，蟻群算法和量子遺傳算法均未得到理論最優(yōu)解，但較蟻群算法而言，量子遺傳算法搜索到的最優(yōu)解和已知理論最優(yōu)解的平均偏差更小。因此，量子遺傳算法的性能優(yōu)于蟻群算法，能夠較好地滿足前攝性調(diào)度方案最優(yōu)路徑的要求。

5 結(jié)束語

針對互聯(lián)網(wǎng)經(jīng)濟發(fā)展導(dǎo)致客戶需求不確定的問題，本文以某超市為例開展研究，分析了企業(yè)原始車輛配送方案與本文前攝性調(diào)度方案的成本構(gòu)成，得出如下結(jié)論：①本文方法在需求響應(yīng)速度和動態(tài)客戶服務(wù)能力上優(yōu)于原始策略；②在靜態(tài)車輛調(diào)度場景下本文方法與原始調(diào)度方案成本大致相當，而在動態(tài)應(yīng)用場景下本文方法優(yōu)于企業(yè)原始車輛調(diào)度方案；③在多周期車輛調(diào)度時，車輛補貨成本依賴于聚類算法的性能，穩(wěn)定的聚類中心數(shù)及其空間分布是補貨成本穩(wěn)定性的重要保證。未來將深入研究不同類型動態(tài)客戶分布對聚類算法性能的影響，以驗證聚類算法和調(diào)度方案在其他數(shù)據(jù)集上的性能。