考慮客戶滿意度的SDVRPTW問題研究

摘 要：本文將客戶滿意度引入需求可拆分車輛路徑問題，改進拆分策略，同時考慮最小化配送總成本和最大化客戶滿意度，建立考慮客戶滿意度的多目標SDVRPTW模型，并應用Pareto禁忌搜索算法進行求解，通過算例驗證模型和算法的正確性及有效性。

關鍵詞：需求可拆分車輛路徑問題 客戶滿意度 Pareto禁忌搜索算法

一、引言

傳統(tǒng)的車輛路徑問題設每個任務點的需求由一輛車在一次服務中完成，即客戶點需求不允許拆分。但在實際問題中，將單一客戶點的需求允許由不止一輛車進行配送，更能提高車輛利用率，降低運輸成本，具有現(xiàn)實意義。現(xiàn)代配送早已不是單純追求成本最小化，提高客戶滿意度已成為物流企業(yè)服務的目標之一。綜上所述，本文研究考慮客戶滿意度的需求可拆分車輛路徑問題，提出適用于解決該問題的優(yōu)化方法并驗證其可行性，從而優(yōu)化企業(yè)服務水平和經濟效益兩個指標。

二、問題模型

1.問題描述。針對單一配送中心和多個客戶點所組成的配送網絡，每個客戶點坐標、可接受服務時間及需求量已知，車輛從配送中心出發(fā)，完成各客戶點服務后，返回配送中心。當客戶點的需求量大于車輛的剩余載重時，允許進行分割配送，即一個客戶點允許不同車輛服務不止一次。完成以上任務是在客戶的時間窗約束下進行的，根據車輛開始服務時間，反應客戶的滿意度水平。

2.模型假設。（1）每條路線上各客戶的需求量之和不得超過車輛的載重限制；（2）每個客戶的需求必須滿足，但可以由一輛或一輛以上的車輛來滿足。

3.符號和變量說明：

（1）參數符號：：，所有節(jié)點的集合，0代表車場，代表n個客戶點；：車輛的滿載量；：客戶點的需求量；：任意兩個客戶點之間的距離；：車輛k到達客戶點i的時間；：客戶點的期望服務時間窗；：客戶點的可容忍服務時間窗；：車輛行駛距離費用系數；：等待費用系數；：車輛啟用成本。

（2）決策變量：

；

4.模型建立。

（1）滿意度函數：

（2）目標函數：

=……（1）

=……（2）

（1）、（2）式為 SDVRPTW 的目標函數，（1）表示線路行駛總費用最小，包含車輛行駛產生的路徑費用、提前到達等待費用以及車輛啟用費用；（2）表示最大化客戶的平均滿意度。

三、Pareto禁忌搜索算法

1.初始解。用最近距離法生成初始解，先生成一組TSP初始解，再根據車輛最大載重量進行拆分形成VRP初始解。

2.鄰域結構。本文采用插入（Insert）、互換（Swap）和逆序（Inverse）來產生TSP鄰域解，再轉化為VRP。

3.非劣解集的篩選及更新。初始非劣解的篩選是指根據生成的初始解，經過帕累托原理判斷后，選擇不受其他解支配的解放入非劣解集中；更新非劣解集是指當新的解不受其他當前解以及非劣解集中的非劣解支配時，把當前解放入非劣解集中。

四、算例分析

本文采用50個客戶點的Solomon數據集R102作為基本數據，通過隨機方法生成客戶的期望時間窗。設定車載量為50，車輛單位距離運輸成本為1，車輛啟用成本為100，單位時間等待成本為10，車速為1。算例前10個客戶的坐標及時間窗數據見表一。

3.參數設置。循環(huán)代數=500，候選解個數=300，最大迭代次數=100，禁忌表長度=10。對算例重復仿真10次，對比不拆分情況，得到結果如表二所示。

由表三可知，采用需求可拆分的策略可以降低配送車輛數，從而降低啟用成本，除此之外，拆分可以明顯降低等待時間成本，避免等待所產生的成本消耗，但隨著滿意度要求的提高，可拆分的路徑成本要高于不可拆分。故企業(yè)在進行物流配送規(guī)劃時，還需衡量三者關系，對比分析，從而做出合理的決策。

參考文獻：

[1]Archetti， C.， M. Bouchard and G. Desaulniers， Enhanced Branch and Price and Cut for Vehicle Routing with Split Deliveries and Time Windows[J]. Transportation Science， 2011. 45（3）： p. 285-298.

[2]朱玲， 吳迪. 需求可拆分的汽車零部件循環(huán)取貨路徑優(yōu)化研究. 計算機應用研究， 2013， 30（6）： 1647-1651.

[3]楊鵬， 鄒浩， 徐賢浩. 帶時間窗集送貨需求可分車輛路徑問題的改進蟻群算法. 系統(tǒng)工程， 2015， （9）： 58-62.