□劉 虹 傅曉敏

[福州大學(xué) 福州 350108]

引言

城市物流行業(yè)發(fā)展日益快速，促使物流企業(yè)競爭愈加激烈，為提高競爭優(yōu)勢，車輛路徑作為物流配送的關(guān)鍵環(huán)節(jié)，必須具備更大的靈活性才能適用多變、激烈的物流市場。在城市配送系統(tǒng)中，貨物經(jīng)由車輛從城市配送中心交付至客戶，考慮城市路況的局限性，一般采用小型容量車執(zhí)行配送任務(wù)，同時又存在車輛更早于工作日結(jié)束前返回配送中心的情況，在Olivera和Viera[1]發(fā)現(xiàn)單行程車輛路徑問題不適于較低車輛容量限制及配送時間較長的路徑后，多行程車輛配送開始受到廣泛的關(guān)注。

多行程（Multi-Trip，MT）配送由于允許車輛中途返回配送中心，可在配送中心和配送點之間多次往返完成任務(wù)[2]，在提高服務(wù)效率、降低車輛啟動成本和司機(jī)雇傭費用等方面占有明顯優(yōu)勢。隨著城市經(jīng)濟(jì)規(guī)模擴(kuò)大、新興技術(shù)發(fā)展，研究多行程車輛路徑在復(fù)雜配送環(huán)境中的優(yōu)化問題，對科學(xué)規(guī)劃城市配送具有重要意義。

在多行程物流中，MTVRP研究內(nèi)容主要集中于分配路線數(shù)量、限制車輛服務(wù)時間、求解優(yōu)化算法和調(diào)整策略等方面。Francois等學(xué)者先構(gòu)造初始路徑集合后單獨分配給車輛，并采用大規(guī)模鄰域搜索算法尋求最優(yōu)解[3]；Hernandez等學(xué)者開放車輛服務(wù)時間限制，研究了帶時間窗的多行程路徑問題，并設(shè)計分支定價算法尋求路徑最優(yōu)[4]；宋強(qiáng)等學(xué)者在時間約束條件下構(gòu)建MTVRP數(shù)學(xué)模型，并分別改進(jìn)了混合遺傳算法、迭代局部搜索算法和變鄰域搜索算法進(jìn)行求解，尋求運行成本最小化[5～7]；Ampol等學(xué)者改進(jìn)了插入啟發(fā)式算法求解帶有時間窗、班次時間限制和可變交貨時間的多行程庫存路徑問題[8]；學(xué)者李陽和范厚明針對客戶的不確定需求，引入不確定相關(guān)理論，提出點返回多行程策略進(jìn)行路徑優(yōu)化，研究了尋求總成本最小的MTVRP問題[9～10]；張曉楠等學(xué)者在客戶模糊需求和時間窗偏好約束下，以物流成本和時間成本總和最小為目標(biāo)構(gòu)建MTVRP模型，并提出“基于成本期望值”的實時調(diào)整策略[11]。

綜上所述，已有多行程路徑問題研究文獻(xiàn)主要集中以降低運輸成本為主要目標(biāo)的模型求解優(yōu)化上，考慮客戶滿意度的多行程配送的研究較少，且多行程路徑允許多次配送的特征直接影響車輛配送時間和次數(shù)，進(jìn)而會導(dǎo)致客戶滿意度發(fā)生變化，加之隨著物流配送的多樣化，客戶滿意度將作為企業(yè)提高核心競爭力的一個關(guān)鍵，因此研究考慮客戶滿意度的多行程車輛路徑優(yōu)化具有實際意義。根據(jù)多行程的特點，本文從配送時間窗、服務(wù)次數(shù)兩方面衡量客戶滿意度并建立相應(yīng)的客戶滿意度函數(shù)，同時兼顧客戶取送雙向隨機(jī)需求，構(gòu)建同時考慮運輸成本和滿意度的多目標(biāo)多行程路徑優(yōu)化模型，并設(shè)計求解算法尋求最佳車輛配送路徑?jīng)Q策。

一、問題描述及模型建立

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

本文研究的是包含配送中心和客戶點的配送網(wǎng)絡(luò)中的多行程車輛路徑問題。貨物在配送中心進(jìn)行集中送貨，客戶為同時取送貨及其需求具有隨機(jī)性，配送中心派遣車輛采用同時取送的多行程配送模式服務(wù)客戶點?？蛻舾鶕?jù)貨物送達(dá)時間的不同會產(chǎn)生不同程度的滿意度，客戶接受車輛服務(wù)次數(shù)的不同也會影響滿意度，多行程車輛配送需進(jìn)行路徑?jīng)Q策，使得客戶滿意度最大和運輸成本最小。

為突出多行程配送的特性，做出如下假設(shè)：

1. 配送中心的坐標(biāo)以及客戶點數(shù)量、坐標(biāo)、配送時間窗、服務(wù)次數(shù)要求已知；

2. 客戶取送貨需求均服從隨機(jī)分布，且只有當(dāng)車輛到達(dá)客戶點時其需求才會被確認(rèn)；

3. 每輛車僅有一條配送路線，且每條路線上的客戶取送貨需求總量不能超過車輛容量能力；

4. 取送貨物可以進(jìn)行混合運輸，車輛從配送中心出發(fā)，完成配送任務(wù)之后需要返回配送中心；

5. 配送途中勻速行駛且速度已知，配送途中的運輸成本只與配送路程相關(guān)；

6. 預(yù)優(yōu)化中每個客戶點僅能接受一輛車服務(wù)，且車輛首次從配送中心出發(fā)時均處于滿載狀態(tài)；

7. 實際配送中可采用部分服務(wù)策略，即客戶允許同一輛車多次配送。

（二）符號和變量說明

1. 參數(shù)符號

TB：車輛k在配送中心處的補(bǔ)貨時間；

2. 決策變量

（三）滿意度測度

在多行程配送活動中，客戶具有自己的期望配送時間窗和服務(wù)次數(shù)要求，為兼顧客戶的服務(wù)需求，考慮客戶對車輛到達(dá)時間和實際配送次數(shù)的不同心理感受，分別建立客戶滿意度測度函數(shù)，綜合衡量客戶服務(wù)水平。

1. 時間窗滿意度函數(shù)

定義1比較車輛到達(dá)客戶時刻與客戶配送時間窗以背離配送時間窗程度衡量客戶滿意度，見圖1，客戶滿意度函數(shù)表達(dá)式詳見式（1）。

圖 1 時間窗滿意度函數(shù)

不同時間區(qū)間的滿意度如下：

2. 服務(wù)次數(shù)滿意度函數(shù)

定義2服務(wù)次數(shù)與客戶滿意度呈負(fù)相關(guān)，服務(wù)次數(shù)越多，客戶滿意度越低，比較車輛實際配送次數(shù)與客戶服務(wù)次數(shù)范圍，對客戶滿意度函數(shù)描述詳見式（2）。

不同次數(shù)區(qū)間的滿意度如下：

3. 客戶綜合滿意度函數(shù)

定義3客戶綜合滿意度由基于配送時間窗的滿意度式（1）和基于服務(wù)次數(shù)的滿意度式（2）共同決定，客戶綜合滿意度函數(shù)表現(xiàn)為式（3）。

（四）數(shù)學(xué)模型

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

2. 約束條件

其中，式（4）和（5）為目標(biāo)函數(shù)，式（4）為最小化車輛派遣成本和配送成本之和；式（5）為最大化客戶平均滿意度，包括時間窗滿意度和服務(wù)次數(shù)滿意度；式（6）表示配送路線上需求點的正向配送總量小于等于車輛載重限制；式（7）表示配送路線上需求點的逆向攬收總量小于等于車輛載重限制；式（8）表示車輛在配送途中的負(fù)載量不超過車輛最大載重限制；式（9）為車輛在服務(wù)客戶點j后的動態(tài)負(fù)載量的計算等式；式（10）～（11）保證預(yù)階段路徑方案中任一客戶點有且僅有一條車輛配送路線，且車輛只能從配送中心出發(fā)一次；式（12）～（13）消除不合理回路，且保證同一個客戶點之間沒有車輛配送路線；式（14）表示車輛配送時間先后要與客戶配送順序一致；式（15）為車輛配送客戶前后的時間計算式；式（16）～（17）表明決策變量屬性。

二、模型轉(zhuǎn)換與求解

（一）隨機(jī)機(jī)會約束規(guī)劃模型

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

同目標(biāo)函數(shù)式（4）～（5）。

2. 約束條件

其余約束同式（10）～（17）。

（二）點判斷實時策略

定理1車輛服務(wù)下一客戶點，擬選擇方案一，則客戶點的成本期望值和滿意度期望值詳見如下：

證明：

由將式（24）代入式（3）得

由將式（25）代入式（3）得

將式（25）～（26）、式（28）～（29）、式（31）代入式（30）可得式（23），至此式（23）得證。

定理2車輛服務(wù)下一客戶點，擬選擇方案二，則客戶點的成本期望值和滿意度期望值詳見如下：

證明：

由將式（34）代入式（3）得

由將式（37）代入式（3）得

將式（34）～（35）、式（37）～（38）、式（40）代入式（39）可得式（32），至此式（32）得證。

針對不同方案下得到的客戶點期望值結(jié)果，選擇配送成本期望值較小且客戶滿意度較高的方案作為車輛在服務(wù)客戶點之后的路徑優(yōu)化選擇。

（三）模型求解

多行程車輛路徑問題屬于NP難題，考慮多目標(biāo)優(yōu)化的MTVRP模型求解難度增加，禁忌搜索算法可通過使用禁忌規(guī)則使算法跳出局部迂回，實現(xiàn)全局最優(yōu)化[14～15]，故本文針對多目標(biāo)優(yōu)化模型，設(shè)計了嵌套調(diào)整策略的灰關(guān)聯(lián)分析多目標(biāo)禁忌搜索算法進(jìn)行求解。

1. 灰關(guān)聯(lián)分析

灰關(guān)聯(lián)分析主要通過灰關(guān)聯(lián)度判斷序列間關(guān)聯(lián)程度。確定一個序列作為參考標(biāo)準(zhǔn)，然后將其他序列與參考序列進(jìn)行比較，與參考序列越接近，表示該序列效果越好，反之則表示效果越差?；趥鹘y(tǒng)灰色關(guān)聯(lián)分析，引入信息熵理論，用均衡接近度代替灰關(guān)聯(lián)度，有效彌補(bǔ)了關(guān)聯(lián)傾向的缺陷[16～17]。

灰關(guān)聯(lián)分析的具體步驟如下：

2. 嵌套調(diào)整策略的灰關(guān)聯(lián)分析多目標(biāo)禁忌搜索算法

針對MTVRP多目標(biāo)優(yōu)化模型設(shè)計的算法如下：

Step 9：生成最終解。通過點判斷實時策略進(jìn)行多行程路徑調(diào)整，生成實際路徑?jīng)Q策，輸出最終解。

三、算例驗證與結(jié)果分析

（一）實驗算例

本文研究的考慮客戶滿意度的同時取送貨多行程車輛路徑問題模型，尚無標(biāo)準(zhǔn)測試算例，針對所建模型特點，參考Prodhon的選址-路徑問題標(biāo)準(zhǔn)算例集50-5-1，進(jìn)行適當(dāng)選取和擴(kuò)展得到本文測試算例。設(shè)客戶點送貨需求和取貨需求分別服從為50和35的泊松分布，參考文獻(xiàn)[18]增加時間窗限制，具體數(shù)據(jù)如表1所示。此外，配送中心坐標(biāo)為（43,3），車輛派遣成本=2 500，單位配送成本=25，車容量能力=220，客戶點服務(wù)時間=10，補(bǔ)貨時間=10，車輛速度=1。由于本文的多行程配送方式，對于參數(shù)、需根據(jù)配送中客戶對服務(wù)次數(shù)的接受程度來設(shè)定，本實驗設(shè)定參數(shù)= 1，=3來測試算例。

表 1 客戶節(jié)點坐標(biāo)及配送時間窗數(shù)據(jù)

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

1. 預(yù)先優(yōu)化階段

對算例進(jìn)行仿真實驗，得到的Pareto解集結(jié)果如表2所示。為了更好分析，通過客戶滿意度公式，計算以運輸成本為單目標(biāo)求得最優(yōu)解對應(yīng)的客戶滿意度為86.87%，并將其標(biāo)注于Pareto解集坐標(biāo)圖上，如圖2所示。

從空間分布對比圖中可以看出：只關(guān)注成本的單目標(biāo)多行程路徑模型在配送成本上取得了比同時考慮成本和客戶滿意度的多目標(biāo)多行程路徑模型的所有決策方案都更好的表現(xiàn)。然而在客戶滿意度上的表現(xiàn)均劣于多目標(biāo)多行程路徑模型的所有方案。由此可見，運輸成本和服務(wù)水平兩個目標(biāo)是不能同時達(dá)到最優(yōu)，追求低成本需要以降低客戶滿意度為代價，提高滿意度通常也會增加物流成本。企業(yè)可根據(jù)自身發(fā)展需求選擇合適的決策方案。

圖 2 單目標(biāo)最優(yōu)解與Pareto解集空間圖

表 2 Pareto解集

針對模型求解所得的Pareto解集所對應(yīng)的方案很難進(jìn)行優(yōu)劣之分，但決策者總是需要從中選擇一個用以指導(dǎo)路徑規(guī)劃。本文分別將運輸成本、客戶滿意度作為單目標(biāo)進(jìn)行優(yōu)化，仿真15次求得最優(yōu)解26 368、1（作為灰關(guān)聯(lián)參考序列），通過計算并比較Pareto解集所對應(yīng)的目標(biāo)函數(shù)值序列與參考序列（26 368，1）的均衡接近度，確定最優(yōu)方案，為企業(yè)提供最佳參考。Pareto解集對應(yīng)的均衡接近度如表3所示。

表 3 Pareto解集均衡接近度

由表3可知，Pareto解6與最優(yōu)解（26 368,1）的均衡接近度為0.715 6最大，根據(jù)灰關(guān)聯(lián)分析理論可知，均衡接近度越大，表明Pareto解6越接近理想最優(yōu)解。由此，選擇Pareto解6作為預(yù)優(yōu)化階段最佳參考解，具體決策方案為車輛1：0-6-24-7-11-0，車輛2：0-8-23-22-20-0，車輛3：0-19-9-1-2-0，車輛4：0-4-10-15-12-0，車輛5：0-5-17-14-16-0，車輛6：0-21-13-18-3-0，總成本為28 443.99，客戶滿意度為99.82%。

2. 實際配送階段

（1）實際配送中，在沒有采取任何實時策略的前提下，車輛按預(yù)優(yōu)化階段參考路徑服務(wù)客戶，由于取送貨需求的隨機(jī)性，車輛的剩余載貨量或者空余可載貨量可能不足導(dǎo)致客戶點配送失敗，造成配送路徑的中斷，具體情況如圖3所示。在路線1中，客戶11為配送失敗的中斷點，致使客戶點11前后相鄰路徑為無效配送路徑；在路線4中，客戶4為中斷點，客戶4作為車輛服務(wù)首個客戶點，導(dǎo)致整個車輛服務(wù)路線4為無效路徑；在路線5中，客戶16為配送失敗的中斷點，因此客戶點16前后相鄰配送路徑無效。

圖 3 配送中斷路徑圖

（2）在實際配送中，采取本文提出的“點判斷”多行程策略進(jìn)行實時路徑調(diào)整，實際配送路徑方案為車輛1：0-6-24-7-0-11-0，車輛2：0-8-23-22-20-0，車輛3：0-19-9-1-2-0，車輛4：0-4-0-4-10-15-12-0，車輛5：0-5-17-14-0-16-0，車輛6：0-21-13-18-3-0，總成本為31 838，客戶滿意度為92.15%?！包c判斷”實時調(diào)整策略基于預(yù)先優(yōu)化最佳路徑方案進(jìn)行調(diào)整，較于無任何調(diào)整策略下實際配送產(chǎn)生中斷，可避免因客戶需求隨機(jī)導(dǎo)致路徑中斷。

四、結(jié)論

在多行程配送網(wǎng)絡(luò)中，綜合考慮客戶滿意度和運輸成本建立多行程路徑多目標(biāo)優(yōu)化模型，針對模型具有同時取送、隨機(jī)參數(shù)、多行程動態(tài)以及多目標(biāo)等特征，提出“點判斷”實時調(diào)整策略，引入隨機(jī)機(jī)會約束規(guī)則和灰關(guān)聯(lián)分析理論，設(shè)計了嵌套調(diào)整策略的灰關(guān)聯(lián)多目標(biāo)禁忌搜索算法尋求最佳配送路徑。通過算例實驗，驗證了模型和算法的有效性。得出以下結(jié)論：

1. 低成本運輸是物流企業(yè)追求的長期目標(biāo)，而隨著物流行業(yè)間競爭的愈發(fā)激烈，服務(wù)水平將成為企業(yè)提高核心競爭力的一個關(guān)鍵。多行程路徑配送模型同時考慮成本和客戶滿意度進(jìn)行多目標(biāo)優(yōu)化，可為企業(yè)如何同時兼顧物流成本和服務(wù)水平提供參考。

2. 采用“點判斷”實時策略調(diào)整進(jìn)行多行程配送，可有效避免配送路徑中斷，同時多行程配送會產(chǎn)生基于服務(wù)次數(shù)的客戶滿意度，符合實際情境。

3. 用灰關(guān)聯(lián)分析理論和禁忌搜索算法相結(jié)合，能有效尋求路徑最優(yōu)，提高算法求解質(zhì)量。

在多方因素的影響下，現(xiàn)實中的多行程配送網(wǎng)絡(luò)較為復(fù)雜，進(jìn)一步研究多行程配送系統(tǒng)中的多動態(tài)模型將是下一步的研究重點。