考慮客戶滿意度的多目標多行程車輛路徑優化

□劉 虹 傅曉敏

[福州大學 福州 350108]

引言

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

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

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

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

一、問題描述及模型建立

（一）問題描述與假設

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

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

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

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

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

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

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

6. 預優化中每個客戶點僅能接受一輛車服務，且車輛首次從配送中心出發時均處于滿載狀態；

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

（二）符號和變量說明

1. 參數符號

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

2. 決策變量

（三）滿意度測度

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

1. 時間窗滿意度函數

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

圖 1 時間窗滿意度函數

不同時間區間的滿意度如下：

2. 服務次數滿意度函數

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

不同次數區間的滿意度如下：

3. 客戶綜合滿意度函數

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

（四）數學模型

1. 目標函數

2. 約束條件

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

二、模型轉換與求解

（一）隨機機會約束規劃模型

1. 目標函數

同目標函數式（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）得證。

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

（三）模型求解

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

1. 灰關聯分析

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

灰關聯分析的具體步驟如下：

2. 嵌套調整策略的灰關聯分析多目標禁忌搜索算法

針對MTVRP多目標優化模型設計的算法如下：

Step 9：生成最終解。通過點判斷實時策略進行多行程路徑調整，生成實際路徑決策，輸出最終解。

三、算例驗證與結果分析

（一）實驗算例

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

表 1 客戶節點坐標及配送時間窗數據

（二）實驗結果與分析

1. 預先優化階段

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

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

圖 2 單目標最優解與Pareto解集空間圖

表 2 Pareto解集

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

表 3 Pareto解集均衡接近度

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

圖 3 配送中斷路徑圖

（2）在實際配送中，采取本文提出的“點判斷”多行程策略進行實時路徑調整，實際配送路徑方案為車輛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%。“點判斷”實時調整策略基于預先優化最佳路徑方案進行調整，較于無任何調整策略下實際配送產生中斷，可避免因客戶需求隨機導致路徑中斷。

四、結論

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

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

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

3. 用灰關聯分析理論和禁忌搜索算法相結合，能有效尋求路徑最優，提高算法求解質量。

在多方因素的影響下，現實中的多行程配送網絡較為復雜，進一步研究多行程配送系統中的多動態模型將是下一步的研究重點。