基于前攝性調(diào)度的車輛路徑問題

葛顯龍，薛桂琴

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

0 引言

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

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

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

1 問題描述

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

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

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

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

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

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

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

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

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

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

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

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

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

(12)

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

(13)

(14)

(15)

Nw≤N，w∈W；

(16)

(17)

(18)

(19)

Sdev≥0。

(20)

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

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

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

3.1 前攝性動(dòng)態(tài)客戶評(píng)估方法

(21)

(22)

(23)

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

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

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

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

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

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

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

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

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

(4)將搜索半徑擴(kuò)大為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)象，這在實(shí)際應(yīng)用場(chǎng)景下是不允許的，為此，在配送中心和各前攝性調(diào)度中心之間使用補(bǔ)貨車輛對(duì)各分區(qū)進(jìn)行補(bǔ)貨，以解決實(shí)際配送需求量大于車輛荷載子區(qū)域的配送差額問題。

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

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

(24)

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

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

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

4 仿真分析

4.1 算例描述

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

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

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

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

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

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

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

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

(25)

(26)

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

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

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

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

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

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

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

4.2.3 對(duì)比分析

因?yàn)樵架囕v調(diào)度方案在第2階段為第1階段的動(dòng)態(tài)客戶提供服務(wù)，而前攝分區(qū)方案服務(wù)靜態(tài)客戶的時(shí)間可能更早，所以對(duì)于服務(wù)成功的動(dòng)態(tài)客戶的單位獎(jiǎng)勵(lì)因子設(shè)置為路徑成本的3%，動(dòng)態(tài)客戶服務(wù)失敗的單位懲罰因子為5%，得出兩方案的總成本值如表7所示。

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

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

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

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

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

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

4.3.2 多周期配送成本分析

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

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

4.4 算法性能測(cè)試

4.4.1 聚類算法性能測(cè)試

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

4.4.2 算法性能分析

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

表9 量子遺傳算法性能對(duì)比表

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

5 結(jié)束語

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