考慮客戶滿意度的多目標多行程車輛路徑優(yōu)化

□劉 虹 傅曉敏

[福州大學 福州 350108]

引言

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

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

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

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

一、問題描述及模型建立

（一）問題描述與假設

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

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

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

2. 客戶取送貨需求均服從隨機分布，且只有當車輛到達客戶點時其需求才會被確認；

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

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

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

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

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

（二）符號和變量說明

1. 參數(shù)符號

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

2. 決策變量

（三）滿意度測度

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

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

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

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

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

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

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

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

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

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

（四）數(shù)學模型

1. 目標函數(shù)

2. 約束條件

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

二、模型轉換與求解

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

1. 目標函數(shù)

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

2. 約束條件

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

（二）點判斷實時策略

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

證明：

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

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

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

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

證明：

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

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

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

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

（三）模型求解

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

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

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

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

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

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

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

三、算例驗證與結果分析

（一）實驗算例

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

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

（二）實驗結果與分析

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

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

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

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

表 2 Pareto解集

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

表 3 Pareto解集均衡接近度

由表3可知，Pareto解6與最優(yōu)解（26 368,1）的均衡接近度為0.715 6最大，根據(jù)灰關聯(lián)分析理論可知，均衡接近度越大，表明Pareto解6越接近理想最優(yōu)解。由此，選擇Pareto解6作為預優(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ōu)化階段參考路徑服務客戶，由于取送貨需求的隨機性，車輛的剩余載貨量或者空余可載貨量可能不足導致客戶點配送失敗，造成配送路徑的中斷，具體情況如圖3所示。在路線1中，客戶11為配送失敗的中斷點，致使客戶點11前后相鄰路徑為無效配送路徑；在路線4中，客戶4為中斷點，客戶4作為車輛服務首個客戶點，導致整個車輛服務路線4為無效路徑；在路線5中，客戶16為配送失敗的中斷點，因此客戶點16前后相鄰配送路徑無效。

圖 3 配送中斷路徑圖

（2）在實際配送中，采取本文提出的“點判斷”多行程策略進行實時路徑調(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ōu)化最佳路徑方案進行調(diào)整，較于無任何調(diào)整策略下實際配送產(chǎn)生中斷，可避免因客戶需求隨機導致路徑中斷。

四、結論

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

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

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

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

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