考慮時間窗服務(wù)價值的越庫車輛路徑優(yōu)化

劉虹，林楚玥

（福州大學(xué)經(jīng)濟(jì)與管理學(xué)院，福建福州350100）

一、引言

近年來，國內(nèi)物流行業(yè)發(fā)展迅猛，第九屆中國物流信息化大會以“創(chuàng)新驅(qū)動物流產(chǎn)業(yè)升級”為主題，力求推進(jìn)智慧物流的行業(yè)應(yīng)用。而越庫（cross-docking）作為一種以供給鏈間信息化為基礎(chǔ)的高效物流新技術(shù)，因其能大幅降低庫存水平，加快貨物流動，在國外已被廣泛應(yīng)用于配送網(wǎng)絡(luò)中[1]。

越庫問題的研究主要有內(nèi)部運作調(diào)度和外部車輛路徑兩方面，其中車輛路徑研究考慮了協(xié)調(diào)運送、運輸策略等方面。Lee 等學(xué)者首次提出越庫的車輛路徑問題，取貨車輛應(yīng)同時到達(dá)越庫中心，以便于合并處理[2]；Liao 等學(xué)者對此方法進(jìn)行了改進(jìn)[3]。Wen 等學(xué)者放寬了車輛在越庫中同步到達(dá)的假設(shè)，通過整合來協(xié)調(diào)運送路線[4]。Yu 等學(xué)者研究越庫的開放式車輛路徑問題，協(xié)同取貨車輛的到庫時間[5]。曹克官討論了直送和循環(huán)取貨兩種調(diào)度策略下的越庫配送網(wǎng)絡(luò)問題[6]。葛顯龍等學(xué)者在循環(huán)取送貨策略下，研究供應(yīng)鏈環(huán)境下的越庫協(xié)同配送網(wǎng)絡(luò)最小成本問題[7]。而Baniamerian 等學(xué)者則關(guān)注越庫配送網(wǎng)絡(luò)的最大利潤問題[8]。Maknoon 和Laporte 在多越庫的配送網(wǎng)絡(luò)中考慮車輛負(fù)載同步性，研究貨物可在越庫間轉(zhuǎn)移合并策略下的車輛路徑問題，并提出自適應(yīng)大領(lǐng)域搜索算法[9]。

越庫配送網(wǎng)絡(luò)注重整體的配送效率，而配送效率的高低直接影響著客戶服務(wù)水平，衡量配送服務(wù)水平的研究，主要集中在建立與時間相關(guān)的滿意度函數(shù)來評價服務(wù)水平，滿意度越高則服務(wù)水平越好。Fan 認(rèn)為配送服務(wù)水平與客戶等待時間呈現(xiàn)反比關(guān)系，由此構(gòu)建滿意度函數(shù)[10]。Chen、樓振凱等學(xué)者用梯形模糊數(shù)表征模糊時間窗，用模糊度隸屬函數(shù)刻畫客戶滿意度，通過線性分段式函數(shù)體現(xiàn)客戶對配送服務(wù)的滿意程度[11-12]。王君同樣是用模糊時間窗反映客戶對時間的偏好程度，并將客戶滿意度表示為關(guān)于時間的凹模糊數(shù)[13]。任亮等學(xué)者考慮客戶拖期厭惡行為，運用前景理論價值函數(shù)體現(xiàn)客戶配送服務(wù)水平[14]。

綜上所述，越庫配送的研究主要集中于車輛調(diào)度、協(xié)同到庫策略等，考慮分揀整合策略的越庫配送相對較少。另一方面，由于存在交通阻塞等一些不確定因素，可能使產(chǎn)品送達(dá)時間不確定，進(jìn)而使產(chǎn)品送達(dá)時間窗偏離，也會使客戶的心理感受隨之變化；對于越庫配送中心而言，產(chǎn)品配送時間的不確定對車輛和駕駛員的調(diào)度均會產(chǎn)生影響。本文主要研究的問題是：在連鎖零售的越庫配送網(wǎng)絡(luò)中，針對越庫中心內(nèi)部的協(xié)同到庫、分揀整合和外部車輛路徑的集成配送，考慮客戶對配送時間的心理感知對服務(wù)水平評價存在影響，引入前景理論，構(gòu)建客戶時間窗服務(wù)價值函數(shù)，尋求使得時間窗服務(wù)價值最高和配送成本最低的越庫車輛路徑優(yōu)化方案。

二、問題描述及建模

（一）問題描述與假設(shè)

連鎖零售的越庫配送網(wǎng)絡(luò)，包括：多個供應(yīng)商、一個越庫配送中心和多個客戶零售商。零售商依據(jù)各自的銷售需求向各供應(yīng)商提交貨物訂單，越庫配送系統(tǒng)由此獲取客戶訂單，其中客戶訂單包含三個屬性信息：取貨地點（即供應(yīng)商節(jié)點）、送貨地點（即零售商節(jié)點）和訂單貨物量。配送網(wǎng)絡(luò)見圖1。

根據(jù)越庫協(xié)同到庫和分揀整合策略，調(diào)度取貨車輛前往取貨點拾取貨物，并協(xié)同抵達(dá)越庫中心；訂單貨物根據(jù)目的地進(jìn)行分揀重裝；經(jīng)過整合的貨物由送貨車輛按一定順序送達(dá)客戶點，送貨車輛最后返回越庫中心?？蛻舾鶕?jù)貨物送達(dá)時間會產(chǎn)生不同的心理感知，影響著時間窗服務(wù)價值，越庫配送系統(tǒng)需要優(yōu)化車輛配送路徑，以期在降低配送成本的同時提高客戶時間窗服務(wù)價值。有以下假設(shè)：

假設(shè)1客戶訂單的三個屬性信息（取貨點、送貨點、貨物量）以及配送時間窗已知；

假設(shè)2每個取/送貨點僅由一輛取/送貨車輛服務(wù)，并且僅被服務(wù)一次；

假設(shè)3取/送貨車輛均從越庫中心出發(fā)，在訪問完取/送貨點之后必須返回越庫中心；

假設(shè)4取貨車輛采用整車直運方式運輸，即每個取貨點只需一輛車，且不考慮載重約束；

假設(shè)5送貨車輛具有載重約束，要求每輛車所分配的所有訂單貨物量之和不超過其最大載重量；

假設(shè)6節(jié)點間車輛運輸成本和運輸時間、貨物的單位裝卸時間和單位處理時間以及可用車輛數(shù)量已知。

圖1：越庫配送網(wǎng)絡(luò)

（二）符號與變量說明

1.模型參數(shù)

R{ r |r= 1, … l}：表示訂單集合；

D{i | i= 1, … n}：表示送貨點（零售商）集合；

P{ j |j= 1,…m }：表示取貨點（供貨商）集合；

O：表示越庫配送中心；

εjr：表示訂單r (r ∈R)與取貨點j (j ∈P)對應(yīng)關(guān)系，若 εjr=1，表示訂單r 的取貨點為j；

V{k |k= 1, … v}：表示取貨車輛集合；

V'{k |k= 1, … v'}：表示取貨車輛集合；

Q：表示送貨車輛最大載重量（以托盤為單位）；

Qv：表示可用車輛數(shù)量；

S =P ∪｛O｝ ∪ D ：表示配送網(wǎng)絡(luò)中所有節(jié)點集合；

Cv：表示車輛固定運營成本；

qr：表示訂單r(r∈R)貨物量（以托盤為單位）；

di：表示送貨點i(iD∈)供貨總量（以托盤為單位）；

pj：表示取貨點j(j∈P)收貨總量（以托盤為單位）；

Tab：表示節(jié)點a 到節(jié)點b 的運輸時間(a, b∈S)；

Cab：表示節(jié)點a 到節(jié)點b 的運輸成本(a, b∈S)；

γ ：表示在取/送貨點每一單位貨物所需裝/卸貨時間；

φ：表示在越庫中心每一單位貨物所需處理時間；

M ：表示極大的數(shù)；

[T1,T2]：表示送貨點最早最晚工作時間窗；

EETi：表示送貨點i(i∈D)期望送貨服務(wù)時間節(jié)點；

LLTi：表示送貨點i(i∈D)可容忍送貨服務(wù)時間節(jié)點。

2.決策變量

stk：取貨車輛 k(k∈V)離開越庫中心出發(fā)取貨的時間；

atk：取貨車輛k(k∈V)到達(dá)越庫中心的時間；

dtk：送貨車輛k (k ∈V')離開越庫中心時間；

tik：送貨車輛k (k ∈V')到達(dá)送貨點i (i∈D)時間。

（三）客戶時間窗服務(wù)價值模型

考慮到客戶在評價配送水平時，往往會受行為和心理因素的影響，且對準(zhǔn)時性要求也并非完全剛性。前景理論價值函數(shù)，運用到服務(wù)評價中能夠表示為“收益”與“損失”，結(jié)合模糊時間窗，構(gòu)建客戶時間窗服務(wù)價值函數(shù)，以此衡量配送服務(wù)水平。

1.價值函數(shù)的表示

客戶對配送到貨時間產(chǎn)生主觀感受的滿意度或價值，前景理論可用來描述客戶對時間窗服務(wù)的不同感知，客戶i 的感知價值函數(shù)可表示為如下：

其中：α ,β,λ為參數(shù)，α 表示收益系數(shù)，β 表示損失系數(shù)，λ 表示客戶對損失的敏感程度。任何收益或損失都需要根據(jù)參考點做出判斷，一般選取價值為0 的點作為參考點，在模糊時間窗中，若送貨時間在客戶可容忍時間之前，則客戶的時間窗服務(wù)價值為正值，可看作是收益；反之則價值為負(fù)，即損失。因此，本文將客戶可容忍服務(wù)時間（LLTi）作為參考點?？紤]到在可容忍時間端點上是符合配送要求的，取值為0 不符合實際情況，故假設(shè)在此端點上取值為0.5。

2.背景假設(shè)

為表達(dá)客戶時間窗服務(wù)價值，作如下背景假設(shè)：

假設(shè)7在越庫配送網(wǎng)絡(luò)中，所有客戶（零售商）最早和最晚工作時間分別為 T1、 T2；

假設(shè)8所有客戶擁有相同的評價系數(shù)，即每個客戶的α 和β 取值相同；

假設(shè)9客戶在評價配送服務(wù)水平時，選擇可容忍服務(wù)時間端點作為參考點，送貨車輛在此端點到達(dá)，時間窗服務(wù)價值取值為0.5；

假設(shè)10當(dāng)送貨車輛在客戶i 期望時間EETi之前到達(dá)客戶點，時間窗服務(wù)價值最高，取值為1；

假設(shè)11當(dāng)送貨車輛在客戶i 期望時間EETi之后，且可容忍時間LLTi之前到達(dá)客戶點，客戶將車輛到達(dá)時間與參考點（可容忍時間端點）進(jìn)行比較，認(rèn)為符合自身時間要求，時間窗服務(wù)價值為正值，可看作收益，應(yīng)選用價值函數(shù)xi≥ 0部分；

假設(shè)12當(dāng)送貨車輛在客戶i 可容忍時間LLTi之后，且在最晚工作時間前到達(dá)客戶點，客戶接受服務(wù)但認(rèn)為不符合自身時間要求，時間窗服務(wù)價值為負(fù)值，可看作損失，應(yīng)選用xi＜ 0部分。

假設(shè)13當(dāng)送貨車輛在最晚工作時間端點到達(dá)客戶點時，時間窗服務(wù)價值取值為-1，而在2T 之后，客戶將不再接受服務(wù)。

3.客戶時間窗服務(wù)價值

定理1在越庫配送網(wǎng)絡(luò)中，若送貨車輛k 服務(wù)客戶點i，到達(dá)時間為 tik，在可容忍時間之內(nèi)（ [T1,EETi]和(EETi,LLTi]兩個區(qū)間），則時間窗服務(wù)價值函數(shù)U (tik)表達(dá)如下：

證明：由假設(shè)11 可知，客戶將送貨車輛到達(dá)時間與參考點（可容忍時間端點）進(jìn)行比較，車輛到達(dá)時間若在可容忍時間之前，則認(rèn)為符合自身時間要求，即時間窗服務(wù)價值為正，可看作收益，應(yīng)選用價值函數(shù)xi≥ 0部分，即

（1）當(dāng)tik∈[T1,EETi]，由假設(shè)10 可知，在期望時間內(nèi)，客戶時間窗服務(wù)價值最高，數(shù)值恒定為1，即：

（2）當(dāng)tik∈(EETi,LLTi]，設(shè)時間窗服務(wù)價值函數(shù) U (tik)為：

由假設(shè)10 和假設(shè)11 可知送貨車輛到達(dá)時間為EETi時，客戶時間窗服務(wù)價值數(shù)值為1，而LLTi時，時間窗服務(wù)價值數(shù)值為1/2，即：

將式（6）除以（5），得：

將1a 代入式（5），得：

即：

綜上，式（2）得證。

定理2在越庫配送網(wǎng)絡(luò)中，若送貨車輛k 服務(wù)客戶點i，到達(dá)時間為ikt ，在可容忍時間之后且在最晚工作時間內(nèi)（(LLTi, T2]區(qū)間），則時間窗服務(wù)價值函數(shù)U (tik)如下：

證明：

由假設(shè)12 和假設(shè)13 可知，客戶將送貨車輛到達(dá)時與參考點（可容忍時間端點）進(jìn)行比較，若車輛到達(dá)時間在可容忍時間之后，客戶認(rèn)為不符合自身時間要求，即時間窗服務(wù)價值為負(fù)，可看作損失，應(yīng)

選用價值函數(shù)中xi＜ 0部分，即V ( xi)=-λ · (-xi)β。

當(dāng)tik∈(LLTi, T2,]，時間窗服務(wù)價值函數(shù) U (tik)為：

由假設(shè)12 和假設(shè)13 可知，送貨車輛到達(dá)時間為LLTi時，時間窗服務(wù)價值數(shù)值可看作0，而 T2時，時間窗服務(wù)價值數(shù)值為-1，即：

由式（14）得：

將 a2代入式（15），得：

即：

式中λ 可約去，得：

式（12）得證。

推論在假設(shè)7 至假設(shè)13 背景下的越庫配送網(wǎng)絡(luò)中，如果送貨車輛k 在 tik時間到達(dá)客戶點i，則客戶時間窗服務(wù)價值函數(shù)模型為：

其圖形見圖2，其中，T1、T2分別為客戶最早、最晚工作時間，EETi是客戶期待服務(wù)時間節(jié)點、LLTi是客戶可容忍時間節(jié)點。

圖2：時間窗服務(wù)價值函數(shù)

車輛在不同時間段到達(dá)客戶點，客戶對配送服務(wù)的感知會有所不同，相應(yīng)的時間窗服務(wù)價值含義也有所不同：

（1）車輛在iEET 節(jié)點之前到達(dá)，客戶對配送服務(wù)感知最為滿意，時間窗服務(wù)價值取值均為1；

（2）車輛在(EETi,LLTi]內(nèi)到達(dá)，時間窗服務(wù)價值則隨時間減小，特別的，在LLTi節(jié)點上，仍滿足客戶配送要求，亦可看作收益，因此取值0.5；

（3）車輛在iLLT 之后到達(dá)，則看作損失，且在2T 節(jié)點上取得最小值-1。

4.數(shù)學(xué)模型

（1）目標(biāo)函數(shù)

（2）約束條件

其中：式（21）和式（22）為目標(biāo)函數(shù)，式(21)是總成本最小化目標(biāo)，包括車輛運輸成本以及車輛固定成本；式（22）是平均客戶時間窗服務(wù)價值最大化目標(biāo)；式（23）和式（24）分別是各取貨點和送貨點取貨或送貨的貨物量計算公式；式（25）是送貨車輛最大載重約束；式（26）表示整個配送過程所用車輛數(shù)目不超過可用車輛數(shù)；式（27）表示每個取/送貨點僅被服務(wù)一次且僅由一輛車服務(wù)；式（28）-式（31）表示每個訂單僅被分配一輛車，且同一個取/送貨點的訂單分配同一輛車；式（32）-式（33）表示變量 jrky 、'irky 與abkx 之間的正確關(guān)系；式（34）保證車輛路線的連續(xù)性；式（35）表示取貨車輛協(xié)同到達(dá)越庫中心；式（36）是取貨車輛到達(dá)越庫中心時間的計算公式；式（37）表示送貨車輛離開越庫中心的時間約束；式（38）和式（39）表示送貨車輛在配送階段的時間約束；式（40）和式（41）表示決策變量屬性。

三、求解算法

越庫的路徑優(yōu)化屬于NP-hard 問題，且雙目標(biāo)優(yōu)化模型的求解難度遠(yuǎn)大于單目標(biāo)優(yōu)化，宜采用啟發(fā)式算法求解。禁忌搜索算法（Tabu Search，TS）通過使用禁忌列表，能夠避免算法在局部最優(yōu)點迂回搜索，實現(xiàn)全局最優(yōu)化[15]。在此基礎(chǔ)上，本文結(jié)合局部搜索算法（Local Search，LS）設(shè)計了混合多目標(biāo)求解算法。整個算法主要分為兩層：外層使用TS 算法來優(yōu)化越庫車輛路徑問題，形成配送方案，其中在內(nèi)部嵌套了一層LS 算法判斷送貨車的載量，嵌套程序?qū)ζ浞桨高M(jìn)行判斷，將結(jié)果返回主程序，主程序再根據(jù)其返回值對路徑方案進(jìn)行調(diào)整，以此遞推，最終得到較優(yōu)的車輛路徑方案。

算法具體步驟如下：

Step1：初始化算法參數(shù)。包括最大迭代次數(shù)max_iter，禁忌長度tb_length，鄰域解個數(shù)neighbor_coun，禁忌表tabulist=?，全局非劣解集局部非劣解集

Step2：生成初始解。采用隨機(jī)方式產(chǎn)生初始送貨路徑序列Initial_TSP，由此得到初始解Initial_Sol，并置當(dāng)前解Current_Sol=Initial_Sol，

Step3：計算目標(biāo)函數(shù)值 f1、 f2，并判斷是否滿足時間窗約束條件，若不滿足，則令 f2= f2- M，M是一個很大的數(shù)。

Step4：調(diào)用局部搜索算法，判斷裝車是否成功，若成功直接返回 f1、 f2，否則返回 f1= f1+M，f2= f2- M。

Step5：對當(dāng)前解進(jìn)行鄰域操作，得到候選解集Candidate_Sol。

Step6：重復(fù)Step3 和Step4，得候選解Candidate_Soli 的目標(biāo)函數(shù)值 f1(i )、f2(i )。

Step7：更新局部非劣解、全局非劣解，在候選解集中，應(yīng)用非支配排序算法篩選局部非劣解集與全局非劣解

Step 8：判斷候選解集是否滿足藐視準(zhǔn)則。若是，則將對應(yīng)的禁忌對象替換最早進(jìn)入禁忌表的禁忌對象，更新全局非劣解集；否則，在非禁忌對象的候選非劣解中選擇一個作為當(dāng)前解，并將相應(yīng)的禁忌對象替換最早進(jìn)入禁忌表的禁忌對象，更新全局非劣解集。

Step9：終止條件判斷。若達(dá)到最大循環(huán)迭代次數(shù)，輸出全局非劣解集結(jié)束算法；否則繼續(xù)Step5-Step8。

四、算例與仿真

（一）算例與實驗設(shè)計

越庫車輛路徑優(yōu)化模型尚無標(biāo)準(zhǔn)測試算例，本文選用已有算例數(shù)據(jù)，由10、50 個節(jié)點組成的兩種規(guī)模問題，并根據(jù)研究內(nèi)容對數(shù)據(jù)進(jìn)行擴(kuò)展[5]，算例參數(shù)值見表1。

兩組實驗設(shè)計如下：

實驗1：對小規(guī)模算例進(jìn)行仿真求解，研究協(xié)同到庫和分揀整合策略在越庫車輛路徑中的作用。

實驗2：對大規(guī)模算例進(jìn)行仿真，對比研究存在負(fù)值的時間窗服務(wù)價值（場景1）與其他文獻(xiàn)中服務(wù)水平最低值僅為0（場景2）。

表1：參數(shù)信息

表2：第1 組實驗取貨調(diào)度方案

表3：第1 組實驗Pareto 解集及送貨方案

（二）實驗結(jié)果與分析

本文應(yīng)用MATLAB R2016a 進(jìn)行仿真實驗，系統(tǒng)是Windows 7，硬件環(huán)境是Intel（R）Core（TM）i3-7100 CPU@3.90GHz，內(nèi)存3.87G。經(jīng)過反復(fù)測試，參數(shù)設(shè)置如下：迭代次數(shù)max_iter=500，鄰域解個數(shù)neighbor_count=160，禁忌長度tb_length=20。根據(jù)Kahneman 的結(jié)論[16]，α 、β 取值為0.88。通過算法求解，實驗1 仿真結(jié)果見表2 和表3。

實驗1 結(jié)果分析：

1.由表2 可知，取貨階段采用直運方式，共需4 輛車，路徑1 中，行車時間為186.3 個單位時間，在供應(yīng)商處裝貨時間為19 個單位時間，路徑總時間為205.3 個單位時間。4 輛車的路徑總時間在[169.9,225.5]區(qū)間，根據(jù)協(xié)同到庫策略要求，以225.5 作為取貨車輛協(xié)同到庫基準(zhǔn)，據(jù)此調(diào)度取貨車輛的發(fā)車順序，為后續(xù)貨物進(jìn)行分揀整合提供有效保障。

2.由表3 可知，24 份訂單貨物在越庫中心根據(jù)不同目的地被分揀重裝為6 份，并由3 輛送貨車進(jìn)行后續(xù)配送。

表4：第2 組實驗仿真結(jié)果

實驗2 仿真結(jié)果如表4 所示，場景1 所得解集中，總成本最低為7305.6307，時間窗服務(wù)價值最高為0.8234，當(dāng)時間窗服務(wù)價值上升時，總成本會亦有所增加。時間窗服務(wù)價值的提高往往是以增加配送成本為代價。

對比場景1 和場景2 可知，通過改變超過可容忍時間的價值函數(shù)，函數(shù)值取零和取負(fù)的結(jié)果是不同的。在相近成本下，場景2 所衡量的服務(wù)水平會高于場景1。為考慮具體影響，選取場景1 總成本最低的實驗結(jié)果進(jìn)行下一步分析，根據(jù)相應(yīng)的配送方案計算每一個客戶在場景1 和場景2 下的時間窗服務(wù)價值，結(jié)果對比見圖3。其中，場景1 中時間窗服務(wù)價值平均值為0.7277，場景2 平均值為0.7446。

圖3：時間窗服務(wù)價值對比分析圖

實驗2 結(jié)果分析：

（1）時間窗服務(wù)價值和配送總成本之間存在相關(guān)性，兩者互相沖突，決策者可根據(jù)實際情況選擇合適的配送方案。

（2）由圖3 可知，該方案有6 個客戶點出現(xiàn)了配送延遲，超過了客戶可容忍時間，兩種方法計算出的客戶時間窗服務(wù)價值平均值分別為0.7446 和0.7277，由于存在負(fù)數(shù)，降低了整個配送的服務(wù)水平。

（3）場景1 中的客戶時間窗服務(wù)價值存在負(fù)值，直觀地表示出客戶負(fù)向的心理認(rèn)知，大大影響了其總體配送服務(wù)水平，應(yīng)引起決策者的重視。

五、結(jié)論

在越庫配送系統(tǒng)中，通過協(xié)同到庫策略，相同目的地的貨物得以在越庫中心得到分揀整合，合理規(guī)劃車輛路徑，有助于進(jìn)一步降低配送成本，同時提高配送服務(wù)水平。本文同時考慮了協(xié)同到庫、分揀和客戶時間窗服務(wù)，以配送總成本最小、客戶時間窗服務(wù)價值最大化為優(yōu)化目標(biāo)，建立越庫配送路徑多目標(biāo)優(yōu)化模型；針對模型特點，設(shè)計了禁忌搜索算法和局部搜索算法相結(jié)合的混合算法尋求最優(yōu)配送路徑。得出以下結(jié)論：

（1）越庫中心的協(xié)同到庫及分揀策略、配送車輛運輸路徑是越庫問題中較重要的影響因素，將兩階段集成研究能有效提高越庫的整體配送效率，更符合實際。

（2）采用客戶時間窗服務(wù)價值，符合客戶的心理變化，反映出客戶對越庫配送服務(wù)的感知水平。

（3）禁忌搜索算法和局部搜索算法相結(jié)合的混合多目標(biāo)求解算法，能降低無效路徑生成的概率，提高算法求解效率。

在現(xiàn)實中，越庫配送網(wǎng)絡(luò)的應(yīng)用更為復(fù)雜，未來將進(jìn)一步研究多個越庫中心、多個周期的動態(tài)越庫系統(tǒng)調(diào)度。