考慮客戶滿意度的車輛路徑優化及其算法研究

羅明亮 袁鵬程

摘 要：針對當前車輛路徑問題中較少考慮客戶滿意度的情況，構建了基于模糊時間窗的車輛到達時間滿意度函數和貨物運輸時長滿意度函數，以最大化客戶滿意度和最小化配送總成本為目標建立VRPCCS數學模型.為了求解該問題，考慮到傳統遺傳算法存在依賴初始解、收斂速度較慢、容易陷入局部最優等缺點，設計改進的遺傳算法與大規模鄰域搜索算法相結合的混合算法進行求解，通過選取算例并與傳統遺傳算法進行對比，驗證了模型和算法的可行性和有效性.實驗仿真結果表明考慮客戶滿意度的物流配送方式不僅能夠有效提升客戶滿意度，也能夠降低物流企業配送成本以及車輛空載率，對于物流企業的車輛配送路徑決策具有一定的參考意義.

關鍵詞：模糊時間窗；客戶滿意度；傳統遺傳算法；混合算法

中圖分類號：TP301.6文獻標志碼：A文章編號：1000-2367（2024）02-0051-11

隨著當前物流運輸行業的市場競爭日益激烈，客戶對于貨物配送要求的不斷提高，客戶滿意度的提升對于物流企業的發展顯得尤為重要，提升客戶滿意度不僅能夠提高企業的市場競爭力，而且能夠培養客戶對于企業的信任度，因此在車輛路徑問題中考慮客戶滿意度是十分必要的.

車輛路徑問題（vehicle routing problem，VRP）作為物流配送中的關鍵環節，是當前相關研究中的熱點問題^［1］.車輛路徑問題由DANTZIG 等^［2］首次提出并為不同的需求點提供物資配送，以運輸成本最小化為目標建立模型；CALVETE等^［3］基于軟時間窗構建了多目標車輛路徑優化模型；KOVACS等^［4］研究了容量約束的多目標車輛路徑優化問題；符卓等^［5］研究了基于軟時間窗的需求可拆分的車輛路徑問題；范靜^［6］研究了同時收發貨的車輛路徑問題，以客戶等待時間的長短來衡量客戶滿意度，以車輛行駛路程和客戶等待時間最小化為目標采用禁忌搜索算法求解；李得成等^［7］研究了帶有時間窗的電動車與燃油車混合車輛路徑問題，以車輛行駛路程消耗成本最小化為目標采用分支定價算法進行求解；王奕璇等^［8］研究了低碳下帶時間窗的冷藏藥品車輛路徑問題，以制冷、運輸、貨損和固定成本為目標建立模型；葛顯龍等^［9］研究了帶軟時間窗的車輛路徑問題，以總成本最小化為目標建立模型；BRUGLIERI等^［10］提出了一個三階段數學方法求解城市內物流配送路徑問題，以車輛使用數量和行駛總時間最小化為目標；倪霖等^［11］考慮了車輛同時取送貨對車輛裝載率的影響，以配送總成本最小化為目標采用遺傳算法進行求解；任騰等^［12］考慮了同時取送貨的城市物流共同配送路徑問題，以總支出費用最小化為目標建立模型，并采用遺傳算法進行求解；AGHEZZAF等^［13］研究了單車型的車輛路徑問題，以利潤最大化為目標建立模型；王征等^［14］研究了多車場帶時間窗的車輛路徑問題，并提出了改進的變鄰域搜索算法進行求解；WANG等^［15］設計一種帶有禁忌搜索的混合遺傳算法求解多倉庫共同接送車輛路徑問題.潘立軍等^［16］提出基于時差插入法的遺傳算法求解帶時間窗的取送貨問題.

綜上所述，有關物流配送路徑問題的相關文獻主要集中在以降低成本為主要目標，而以客戶滿意度為目標的研究尚且不多，因此本文考慮了客戶滿意度的車輛路徑問題（vehicle routing problem considering custo-mer satisfaction，VRPCCS），從客戶對配送車輛的到達時間和貨物運輸時長兩方面來衡量客戶滿意度并建立滿意度函數，以客戶滿意度最大化和配送總成本最小化為目標建立VRPCCS數學模型，設計改進的遺傳算法（genetic algorithm，GA）與大規模鄰域搜索算法（large-scale neighborhood search algorithm，LNSA）相結合的混合算法進行求解，通過選取算例并與傳統遺傳算法進行對比，驗證VRPCCS數學模型以及混合算法的可行性和有效性.

1 數學模型構建

1.1 問題描述

本文的VRPCCS可以簡述為：某貨物配送中心擁有K輛相同的運輸車輛，為n個客戶提供貨物配送服務，所有車輛從配送中心出發，每個客戶的貨物需求量提前已知且每個客戶有且僅能被服務一次，車輛必須在最長行駛時間范圍內完成每條配送路線并回到終點處進行消毒，本文目標為尋找合理有效的車輛配送路線使得目標函數達到最優.

1.2 基本假設及參數說明

本文在構建VRPCCS數學模型之前做出以下假設：

1）運輸車輛為同一類型，不同客戶之間的貨物種類相同，車輛勻速行駛，不考慮其他因素的影響；

2）每個客戶的位置、時間窗、貨物需求量、以及配送中心位置均已知.

相關參數及變量如下所示：

V：所有節點集合，V=｛0，1，…，n｝，其中0和n+1分別表示貨物配送中心起點和終點；

N：所有客戶點集合，N=｛1，…，n｝；

K：可使用車輛集合，K=｛1，2，…，e｝；

q_i：客戶i的貨物需求量；

Q：車輛的最大貨物容量；

d_ij：節點i到節點j的歐式距離；

s_i：車輛在客戶節點i花費的服務時間；

a_ki：車輛k到達客戶節點i的時間；

p_ki：車輛k運輸客戶節點i的貨物時長；

t_ij：車輛從節點i到節點j的行駛時間；

［e_i，l_i］：客戶i對車輛到達時間的期望時間窗；

［E_i，L_i］：客戶i對于車輛到達時間的可容忍時間窗；

［0，m_i］：客戶i對于貨物運輸時長的期望時間窗；

［0，M_i］：客戶i對于貨物運輸時長的可接受時間窗；

L_max：車輛完成每條配送路徑的最長行駛時間限制；

A_ki（a_ki）：客戶i對于車輛k的到達時間滿意度函數；

P_ki（p_ki）：客戶i對于車輛k的貨物運輸時長滿意度函數；

φ：客戶對車輛到達時間的最低滿意度；

ω：客戶對貨物運輸時長的最低滿意度；

C₁：平均客戶對于車輛到達時間的不滿意度懲罰成本；

C₂：平均客戶對于貨物運輸時長的不滿意度懲罰成本；

C₃：單位里程車輛運輸成本；

C₄：車輛每次使用的固定損耗成本；

x^k_ij：當車輛k從節點i到節點j時，x^k_ij=1，否則為0；

w₁，w₂，w₃為相關目標函數權重.

1.3 車輛到達時間滿意度函數

車輛配送路徑問題中的硬時間窗和軟時間窗均無法準確地反映出客戶對于車輛到達時間的滿意度變化情況.通常情況下，大多數客戶期望車輛在某個特定的時間范圍內到達，車輛過早或者過晚的到達均會造成客戶對于車輛到達時間滿意度的降低.本文采用模糊時間窗來反映客戶對于車輛到達時間的滿意度程度，將模糊時間窗看作關于車輛到達時間a_ki的凹模糊數，用模糊數的隸屬度函數A_ki（a_ki）表示客戶對于車輛到達時間的滿意度，模糊時間窗包含客戶對于車輛到達時間的期望時間窗和可接受時間窗，其中客戶i的期望時間窗和可接受時間窗分別用閉區間［e_i，l_i］和［E_i，L_i］（E_i＜e_i＜l_i＜L_i）表示，車輛在客戶期望的時間窗內到達則客戶對于車輛到達時間的滿意度為100%，當車輛在客戶期望時間窗之外但在可接受的時間窗之內到達，客戶對于車輛到達時間的滿意度隨著車輛到達時間與客戶期望時間窗的差值的增大而降低.為了提升車輛配送過程中的服務質量，因此確保每一個客戶對于車輛到達時間的滿意度不低于φ，令E^*_i=｛a_ki|A_ki（a_ki）=φ，0＜a_ki＜e_i｝，L^*_i=｛a_ki|A_ki（a_ki）=φ，a_ki＞l_i｝，則E^*_i=E_i+φ^1/α_i（e_i-E_i），L^*_i=L_i-φ^1/β_i（L_i-l_i），此時客戶對于車輛到達時間的可接受時間窗為［E^*_i，L^*_i］（E_i＜E^*_i＜L^*_i＜L_i）處理后的客戶對于車輛到達時間滿意度函數和圖像分別如式（1）和圖1所示：

其中α_i，β_i為客戶i對于車輛到達時間的滿意度系數.

1.4 貨物運輸時長滿意度函數

在實際的貨物運輸過程中，貨物的質量會隨著貨物運輸時長的增加而不斷下降，因此貨物運輸時長也會對客戶的滿意度產生影響.用模糊時間窗來反映客戶對于貨物運輸時長的滿意度變化情況，用隸屬度函數P_ki（p_ki）表示客戶對于貨物運輸時長的滿意度，此時模糊時間窗包含客戶期望貨物運輸時長的時間窗和可接受的貨物運輸時長的時間窗，其中客戶i的期望時間窗和可接受時間窗分別用閉區間［0，m_i］和［0，M_i］（0＜m_i＜M_i）表示，如果貨物在期望時間窗內到達則客戶滿意度為100%；如果貨物在期望時間窗之外但在可接受時間窗內到達，則客戶對于貨物運輸時長的滿意度隨著貨物運輸時長的增加而不斷下降.為了確保每個客戶對于貨物運輸時長的滿意度均不低于ω，令M^*_i=｛p_ki|P_ki（p_ki）=ω，p_ki＞m_i｝，則M^*_i=M_i-ω^1/γ_i（M_i-m_i），此時客戶可接的貨物運輸時長的時間窗為［0，M^*_i］（0＜m_i＜M^*_i＜M_i），處理后的客戶對于貨物運輸時長滿意度函數和圖像分別如式（2）和圖2所示：

其中γ_i為客戶i對于貨物運輸時長的滿意度系數.

1.5 數學模型構建

根據以上分析，構建的數學模型如下：

其中式（3）～（6）為目標函數，式（3）表示最大化平均客戶對于車輛到達時間滿意度；式（4）表示最大化平均客戶對于貨物運輸時長滿意度；式（5）為最小化車輛運輸成本；式（6）為最小化車輛固定損耗成本；式（7）～（10）為車輛在起點和終點的約束，即每輛車必須從起點出發，完成配送任務后回到終點進行消毒；式（11）和式（12）確保車輛在節點處保持流守恒；式（13）確保每個客戶有且僅能被服務一次；式（14）表示每個客戶的貨物運輸時長；式（15）表示車輛容量約束；式（16）、（17）表示車輛到達第一個客戶節點以及其他客戶節點的時間約束；式（18）表示車輛最長行駛時間約束；式（19）和（20）分別表示每個客戶對于車輛到達時間和貨物運輸時長的最低滿意度約束；式（21）表示決策變量為0-1變量.

1.6 目標函數處理

由于本文建立的為多目標優化數學模型，同時目標函數式（3）、式（4）和式（5）、式（6）之間的數量級相差較大且求解問題不統一，為了便于求解，做出以下處理：

其中式（22）表示將最大化平均客戶對于車輛到達時間的滿意度轉化為最小化平均客戶對于車輛到達時間的不滿意度；式（23）表示將最大化平均客戶對于貨物運輸時長的滿意度轉化為最小化平均客戶對于貨物運輸時長的不滿意度；式（24）表示本文最終處理后的目標函數，首先將目標函數式（22）和式（23）分別乘以對應的懲罰系數使其與目標函數式（5）和式（6）的數量級保持一致，然后通過加權的方法，對目標函數式（22）、式（23）、式（5）和式（6）分別賦予權重系數w₁，w₂，w₃，從而將本文多目標優化問題轉化為單目標優化問題.

2 混合算法設計

遺傳算法（GA）作為啟發式算法能夠在較短的時間內獲得問題的有效解，適合求解復雜的優化問題，具有較好的全局搜索能力和魯棒性，同時考慮到遺傳算法存在依賴初始解、收斂速度較慢、容易陷入局部最優等缺點，為了改進這一問題，設計一種改進的遺傳算法與大規模鄰域搜索算法相結合的混合算法進行求解，具體設計過程如下.

2.1 改進遺傳算法設計

2.1.1 染色體編碼及初始種群的生成

采用整數編碼方式進行染色體編碼，運用插入啟發式算法構造初始染色體種群.用e代表配送中心可使用的車輛數，po代表種群規模，初始種群生成的具體過程如下.

隨機選取一個客戶節點j（1≤j≤n），構成客戶序列［j，…，n，…，j+1］，從左到右依次遍歷序列中節點并插入到車輛路徑中.如果即將插入的客戶節點的貨物需求量q_i與當前該條車輛路徑中已插入的客戶節點的貨物需求量之和大于Q，則新增一條車輛路徑并將當前該客戶節點插入，否則將當前客戶節點插入到當前該條車輛路徑中，并按照客戶期望車輛到達時間窗的下限e_i的大小確定當前客戶節點的具體插入位置，即車輛路徑中的客戶節點按照期望車輛到達時間窗的下限e_i的大小從左到右進行排列；如果當前車輛路徑數目為e，則將剩余的尚未插入的客戶節點全部插入到第e條車輛路徑中.如此循環操作，直到所有的客戶節點全部插入到車輛路徑中為止，此時形成VC（VC≤e）條車輛路徑.分別在第1條到第VC車輛路徑的末端加入一個0節點，將第1條到第VC條車輛路徑從左到右進行排列組成一條不完整的染色體cr，并判斷cr長度是否為n+e，如果不是，則在當前cr的末端加入0節點，直到cr的長度為n+e時停止0節點的加入，此時生成一條完整的染色體cr.

循環上述操作，直到生成的染色體數量為po時停止，此時生成初始染色體種群Ch.

2.1.2 染色體解碼

提取染色體中的每條車輛路徑，其中第一個0節點之前的所有客戶節點代表第1條車輛行駛路徑；第k-1（2≤k≤e）個0節點到第k個0節點之間的客戶節點代表第k條車輛路徑；如果第k-1（2≤k≤e）個0節點和第k個0節點相鄰，則表示第k條車輛路徑為空路徑.直到染色體中的所有車輛路徑（不含空路徑）提取完成.

2.1.3 適應度函數設計

通過對種群中的每一個染色體Ch_i進行解碼操作，并根據式（24）求得的對應的目標函數值為Z_i，若染色體Ch_i為不可行解時，則對Z_i賦予一個極大數M.由于本文目標函數為最小化問題，故令染色體Ch_i的適應度函數值為f_i=1/Z_i，f_i越大則代表該染色體越接近待求解問題的最優解.

2.1.4 選擇操作

在選擇操作的過程中采用精英保留策略、隨機遍歷抽樣法與傳統GA中的輪盤賭法相結合，精英保留策略為：在每次迭代前，保留當前種群中前10%的優質染色體直接進入下一代種群中，這樣有利于提升算法的收斂速度和防止最優解的丟失.輪盤賭法的基本思想為：染色體的適應度值越大，在輪盤中所占的角度就越大，被選中的概率也就越大.當需要選擇出m₁個染色體時，輪盤需要轉動m₁次，為了提升輪盤賭法的選擇效率以及增加被選擇出的染色體的多樣性，加入隨機遍歷抽樣法，即只需要一次生成m₁個等間距的指針位置，便可選擇出m₁個染色體.選擇操作的具體流程如下.

首先保留前10%的優質染色體直接進入下一代種群；然后計算種群中每個染色體被選中的概率p_i=f_i/∑^po_x=1f_x以及累積概率P_i=∑ⁱ_x=1p_x，假設此時需要選擇出m₁個染色體，則指針間距Ga=∑^po_i=1f_i/m₁，隨機生成指針的起點位置St（0～Ga之間的隨機數）；最后計算各個指針的位置，其中St+Ga*ii（0≤ii≤m₁-1且ii為自然數）代表第ii+1個指針指向的位置，直到生成m₁個指針為止，指針所指的位置即為被選擇的染色體，此時選擇出m₁個染色體.假設種群中有6個染色體，此時需要選擇出5個染色體，則在輪盤賭法的基礎上采用隨機遍歷抽樣法的選擇過程如圖3所示.

2.1.5 交叉操作

在染色體種群中，以一定的交叉概率對選擇出的染色體進行交叉操作，本文采用一種新的交叉算子（簡稱隨機片段交叉）進行交叉操作.下面舉例說明具體交叉過程如圖4所示：其中1～7為客戶節點，可使用車輛數為4.首先隨機選取父代染色體1中的一條車輛路徑（不含空路徑）和父代染色體2中的一條車輛路徑（不含空路徑）進行隨機片段交叉操作；然后分別將交叉片段放入染色體1和2的首端，并刪除父代染色體1和2中與交叉片段相同的客戶節點；最后在父代染色體1和2的末端刪除1個0節點保持染色體的長度不變，此時生成兩個子代染色體1和2.與傳統GA交叉方法相比，隨機片段交叉最大的優點就是當兩個父代染色體相同時，仍能產生新的染色體，在一定程度上能夠避免迭代過程中出現“早熟”現象，有利于增加種群中染色體的多樣性以及提升算法收斂速度.

2.1.6 變異操作

在GA中將經過選擇和交叉操作后的染色體以較低的概率進行變異操作，類似于生物進化過程中的基因突變，因此變異的可能性較小.本文變異操作采用互換變異的方法，即隨機選取4個客戶節點基因進行兩兩互換，從而產生新的染色體.

2.2 大規模鄰域搜索算法設計

LNSA是由SHAW^［17］首次提出的，其主要思想為：使用移除算子從當前解中移除若干點，然后使用修復算子將被破壞的解進行修復，從而希望得到更加優質的解.在該理論基礎上結合本文所求問題，進行了相應的調整和改進，LNSA具體求解流程如下.

2.2.1 移除操作

在LNSA中，ch表示當前染色體，c表示當前被移除的客戶節點，C表示當前被移除的客戶節點集合，s表示當前已經被移除的客戶節點數量，S表示預先設定的被移除的客戶節點總數，in表示當前移除s個客戶節點后的剩余客戶節點集合.初始化集合in=｛1，2，…，n｝，移除操作的具體過程如下：

首先從in中隨機選取一個客戶節點c并放入C中作為第一個元素，隨后將c從in中刪除；其次剩余的S-1個被移除的客戶節點按照以下策略進行移除：每次從C中隨機選擇一個客戶節點c₁，計算c₁與in中的剩余的客戶節點的相關性，并且按照與c₁的相關性由大到小進行排列，從in中選擇出一個與c₁相關性較大的客戶節點c，將c從in中刪除并且放入C中，重復該操作S-1次，當C中的客戶節點數量等于S時停止移除操作；最后將被移除的客戶節點從當前ch中移除，并更新ch.相關性計算公式如下所示：

其中R_ij的取值范圍為（0，1）;D′_ij的取值范圍為（0，1］，表示歐式距離越近的客戶節點之間的相關性就越強；V_ij表示當節點i和j在同一條車輛路徑中為1，否則為0；T′_ij的取值范圍為（0，1］，表示客戶節點的期望車輛到達時間窗的下限差值的絕對值越小，則客戶節點之間的相關性就越強.

將in中剩余客戶節點與c₁相關性按照從大到小進行排列，如果每次移除都選擇in中相關性最大的客戶節點進行移除，可能會降低客戶節點移除的隨機性，因此加入隨機元素D×（n-s），其中（n-s）表示當前in中的客戶節點數目；當算法迭代Ge次仍未得到改進時，則令D=D+X（1≤D≤n-S），X和D的值可由算例規模的大小進行設定，即D值越小，則被移除的客戶節點的相關性就越強.

2.2.2 修復操作

修復操作是將被移除的節點重新插回到染色體ch中，從而希望產生更加優質的染色體.修復操作具體如下.

首先，提取當前ch中的每條車輛路徑（不含空路徑），尋找C中的每一個客戶節點的最優插入位置，最優插入位置為：探尋每一個客戶節點在每一條車輛路徑中的每一個可行的插入位置，并記錄其對應的車輛序號、插入位置以及距離增量，距離增量為該節點插入后相比插入前車輛需要多行駛的距離，對比每一個客戶節點的所有可行的插入位置，找出使得節點插入后距離增量最少的可行插入位置即為最優插入位置，如果某個客戶節點在當前所有的車輛路徑中沒有可行的插入位置，則新增一條車輛路徑，并且計算其距離增量.可行的插入位置為：如果該客戶節點插入某條車輛路徑中的某一個位置后，該條車輛路徑同時滿足以下3個約束：車輛到達每個客戶節點的時間不超過客戶節點對于車輛到達時間的期望時間窗的上限L_i、車輛不超過容量約束以及車輛最長行駛時間約束，則為可行的插入位置.

然后，對比C中所有客戶節點的最優插入位置的距離增量，采用最遠插入啟發式算法，找出距離增量最大的客戶節點并插回到車輛路徑中，并更新該條車輛路徑和刪除C中的該客戶節點.

最后，每插回一個客戶節點則重新尋找C中剩余客戶節點的最優插入位置，循環上述操作直到C為空集，隨后更新染色體中的每條車輛路徑，通過刪除末端0節點確保生成的新的染色體ch^new的長度為n+e.判斷經過LNSA處理前后染色體的目標函數值，如果ch^new更優，則更新染色體，令ch=ch^new，否則不更新.

2.3 其他操作

混合算法每次迭代后進行以下處理.

2.3.1 刪除重復的染色體

當求解的問題規模越小，種群規模越大時，種群中出現重復的染色體的可能性就越大，重復的染色體過多則會影響算法的求解效率和收斂性，因此將種群中重復的染色體進行刪除是十分必要的.

2.3.2 補足染色體種群

當刪除種群中重復的染色體后，隨機生成新的染色體來補足種群規模，有利于提升算法的求解效率和收斂性.

2.4 算法終止條件及流程圖

當混合算法迭代次數達到預設的值時，終止混合算法的運行，求解流程如圖5所示.

3 仿真實驗及結果分析

本文利用MATLAB R2017b進行編程求解，所有數據均在Intel（R） Core（TM）i5-4200H CPU@2.80 GHz配置的計算機上進行仿真實驗，具體如下.

3.1 算例選取

假設某貨物配送中心的可使用車輛數為8，向20個客戶節點配送貨物，貨物配送中心、客戶期望車輛到達時間窗、各個節點之間的距離均提前已知，貨物配送中心的坐標為（41，40），車輛最大載重量Q=5 t，車輛行駛速度為45 km/h，其他相關參數取值為：α_i=0.3，β_i=0.8，γ_i=0.6，φ=0.3，ω=0.3，C₁=100 元，C₂=200 元，C₃=3 元，C₄=100 元，w₁=0.3，w₂=0.3，w₃=0.4.客戶可接受的車輛到達時間窗［E_i，L_i］為：E_i=e_i-0.6，L_i=l_i+0.4，客戶可接受的貨物運輸時長的時間窗［0，M_i］為：M_i=m_i+0.6，車輛最長行駛時間為4 h，客戶節點坐標以及相關信息如表1所示.

3.2 遺傳算法求解結果

根據構建的VRPCCS數學模型，GA相關參數設置為：選擇代溝、交叉和變異概率分別為0.9、0.9、0.1，種群規模和最大迭代次數分別為100、100.由圖6可得傳統遺傳算法求得的最優車輛配送路徑為7條，分別為0→5→8→9→13→0；0→20→14→17→12→0；0→3→15→0；0→6→19→18→0；0→10→0；0→1→4→7→0；0→2→11→16→0，平均客戶對于車輛到達時間滿意度和貨物運輸時長的滿意度分別為94.15%、97.15%，平均客戶滿意度為95.65%，車輛總行駛路程為545.35 km，求解結果如表2所示.

3.3 混合算法求解結果

在上述GA相關參數設置的基礎上，LNSA的相關參數設置為：移除的客戶節點總數，隨機元素中的參數和分別取值為1、1，預設的次數Ge=5.由圖7可得混合算法求得的最優車輛配送路徑為5條，分別為：0→1→4→7→0；0→2→8→11→16→0；0→20→14→17→12→0；0→3→6→9→19→13→0；0→10→5→15→18→0，平均客戶對于車輛到達時間滿意度和貨物運輸時長的滿意度分別為99.87%、97.15%，平均客戶滿意度為98.51%，車輛總行駛路程為436.25 km，求解結果如表2所示.

3.4 結果對比分析

通過對每種算法重復5次仿真實驗，輸出其中最優的車輛行駛路線圖分別如圖6、圖7所示.對應的算法迭代圖分別如圖8、圖9所示，求得的算法最優值分別為937.89元、725.25元.

由圖8和圖9對比可知，與傳統遺傳算法相比，混合算法在求解考慮客戶滿意度的物流配送路徑問題中表現出較優的求解性能.在求解過程中，傳統遺傳算法在72代開始收斂，混合算法在34代收斂.在求解中期，傳統遺傳算法就已陷入局部最優且難以跳出，而本文設計的混合算法以其極強的局部搜索能力在求解前中期就已經大概率求得了問題的最優解.

通過分析進一步表明，一方面，傳統遺傳算法在初始種群生成的過程中，雖然隨機生成初始解以保持染色體的多樣性，但是種群中染色體的適應度值普遍偏低，甚至部分染色體為不可行解，從而導致了算法的尋優能力下降，也更容易過早地陷入局部最優；而在生成初始種群的過程中，加入插入啟發式算法并保持節點插入的隨機性，使得初始種群的染色體質量得到了有效提升，不僅保證了種群中染色體的多樣性，而且有利于提升算法的收斂速度.另一方面，在選擇操作的過程中，加入隨機遍歷抽樣法和精英保留策略提升了算法在求解過程中的擾動機制，有利于降低算法陷入局部最優的概率，同時較為優質的染色體得到了保留，不僅增加了種群染色體的多樣性，而且使得算法在迭代的過程中收斂于一個較好的最優解；在交叉的過程中采用隨機片段交叉，有利于降低種群中重復染色體的數量并提升算法的收斂速度.

將改進的遺傳算法與大規模鄰域搜索算法進行混合求解，有效地提升傳統遺傳算法的局部搜索能力以及陷入局部最優的概率，使得算法能夠在較短的時間內獲得高質量的解.因此可以表明本文加入的GA改進策略和LNSA能夠有效地解決GA陷入局部最優、收斂速度較慢等問題，并且設計的混合算法在求解VRPCCS數學模型上具有更優的表現.

由表2可知，通過上述算例與傳統遺傳算法求解結果進行對比，本文設計的混合算法的優點主要表現在以下兩個方面：

1）相比傳統遺傳算法，本文設計的混合算法求得的目標函數值質量提升了22.67%，車輛運輸成本和固定損耗成本分別降低了20.00%、28.57%，車輛使用數量降低了28.57%，對于物流運輸公司而言，車輛使用數以及行駛路程的減少，可以有效提高車輛在物流配送過程中的使用率，降低車輛的空載率；

2）不僅能夠有效降低物流配送成本，而且可以提升客戶滿意度，相比傳統遺傳算法，混合算法求得的平均客戶滿意度提高了2.86%.

隨著當前客戶對于物流配送服務的要求越來越高，如果物流企業僅考慮物流運輸成本，而忽略提升客戶滿意度，勢必會影響物流企業的長期發展，對于企業而言得不償失.

4 結 論

針對當前物流配送路徑問題中較少考慮客戶滿意度的情況，本文以客戶對于車輛到達時間滿意度、貨物運輸時長滿意度、車輛運輸成本和固定損耗成本為目標建立多目標優化模型；考慮到傳統遺傳算法存在的不足，設計一種混合算法來進行求解VRPCCS模型，通過選取算例和傳統遺傳算法進行對比，驗證了本文構建的VRPCCS數學模型以及求解算法的可行性和有效性.由于本文只考慮了車輛到達時間和貨物運輸時長對客戶滿意度的影響，在實際問題中，配送人員的服務態度、不同客戶的時間偏好、裝卸貨過程的貨物損耗等因素都會影響客戶滿意度，可作為下一步的研究方向.

參 考 文 獻

［1］WANG Z W，YU J，HAO W，et al.Joint optimization of running route and scheduling for the mixed demand responsive feeder transit with time-dependent travel times［J］.IEEE Transactions on Intelligent Transportation Systems，2021，22（4）：2498-2509.

［2］DANTZIG G B，RAMSER J H.The truck dispatching problem［J］.Management Science，1959，6（1）：80-91.

［3］CALVETE H I，GAL?C，OLIVEROS M J，et al.A goal programming approach to vehicle routing problems with soft time windows［J］.European Journal of Operational Research，2007，177（3）：1720-1733.

［4］KOVACS A A，PARRAGH S N，HARTL R F.The multi-objective generalized consistent vehicle routing problem［J］.European Journal of Operational Research，2015，247（2）：441-458.

［5］符卓，劉文，邱萌.帶軟時間窗的需求依訂單拆分車輛路徑問題及其禁忌搜索算法［J］.中國管理科學，2017，25（5）：78-86.

FU Z，LIU W，QIU M.A tabu search algorithm for the vehicle routing problem with soft time windows and split deliveries by order［J］.Chinese Journal of Management Science，2017，25（5）：78-86.

［6］范靜.考慮客戶滿意度的同時收發車輛路徑問題［J］.運籌與管理，2011，20（1）：60-64.

FAN J.The vehicle routing problem with simultaneous pickup and delivery considering customer satisfaction［J］.Operations Research and Management Science，2011，20（1）：60-64.

［7］李得成，陳彥如，張宗成.基于分支定價算法的電動車與燃油車混合車輛路徑問題研究［J］.系統工程理論與實踐，2021，41（4）：995-1009.

LI D C，CHEN Y R，ZHANG Z C.A branch-and-price algorithm for electric vehicle routing problem with time windows and mixed fleet［J］.Systems Engineering-Theory & Practice，2021，41（4）：995-1009.

［8］王奕璇，陳荔，王濤.低碳下帶時間窗的冷藏藥品路徑優化［J］.科技和產業，2017，17（2）：83-87.

WANG Y X，CHEN L，WANG T.Vehicle routing optimization with time windows of refrigerated drug in low-carbon economy［J］.Science Technology and Industry，2017，17（2）：83-87.

［9］葛顯龍，辜羽潔，譚柏川.基于第三方帶軟時間窗約束的車輛路徑問題研究［J］.計算機應用研究，2015，32（3）：689-693.

GE X L，GU Y J，TAN B C.Research on vehicle routing problem with soft time window based on the third party logistics［J］.Application Research of Computers，2015，32（3）：689-693.

［10］BRUGLIERI M，MANCINI S，PEZZELLA F，et al.A three-phase matheuristic for the time-effective electric vehicle routing problem with partial recharges［J］.Electronic Notes in Discrete Mathematics，2017，58：95-102.

［11］倪霖，劉凱朋，涂志剛.考慮同時取送貨的城市快遞共同配送路徑優化［J］.重慶大學學報，2017，40（10）：30-39.

NI L，LIU K P，TU Z G.Optimization on vehicle routing problem with simultaneous pickup-delivery for urban express joint distribution［J］.Journal of Chongqing University，2017，40（10）：30-39.

［12］任騰，羅天羽，谷智華，等.考慮同時取送貨的城市物流共同配送路徑優化［J］.計算機集成制造系統，2022，28（11）：3523-3534.

REN T，LUO T Y，GU Z H，et al.Optimization of urban logistics co-distribution path considering simultaneous pickup and delivery［J］.Computer Integrated Manufacturing Systems，2022，28（11）：3523-3534.

［13］AGHEZZAF E H，ZHONG Y Q，RAA B，et al.Analysis of the single-vehicle cyclic inventory routing problem［J］.International Journal of Systems Science，2012，43（11）：2040-2049.

［14］王征，張俊，王旭坪.多車場帶時間窗車輛路徑問題的變鄰域搜索算法［J］.中國管理科學，2011，19（2）：99-109.

WANG Z，ZHANG J，WANG X P.A modified variable neighborhood search algorithm for the multi depot vehicle routing problem with time windows［J］.Chinese Journal of Management Science，2011，19（2）：99-109.

［15］WANG Y，LI Q，GUAN X Y，et al.Collaborative multi-depot pickup and delivery vehicle routing problem with split loads and time windows［J］.Knowledge-Based Systems，2021，231：107412.

［16］潘立軍，符卓.求解帶時間窗取送貨問題的遺傳算法［J］.系統工程理論與實踐，2012，32（1）：120-126.

PAN L J，FU Z.Genetic algorithm for the pickup and delivery problem with time windows［J］.Systems Engineering-Theory & Practice，2012，32（1）：120-126.

［17］SHAW P.Using constraint programming and local search methods to solve vehicle routing problems［M］.Berlin：Springer，1998：417-431.

Research on vehicle path optimization and its algorithm considering customer satisfaction

Luo Mingliang， Yuan Pengcheng

（Business School， University of Shanghai for Science and Technology， Shanghai 200093， China）

Abstract： In view of the fact that customer satisfaction is seldom considered in the current logistics distribution path problem， this paper constructs the satisfaction function of vehicle arrival time and the satisfaction function of cargo transportation duration based on the fuzzy time window， and establishes the VRPCCS mathematical model with the goal of maximizing customer satisfaction and minimizing the total distribution cost. Considering that the traditional genetic algorithm has the shortcomings of relying on the initial solution， the convergence rate is slow， and it is easy to fall into local optimization， the hybrid algorithm combining the improved genetic algorithm and the large-scale neighborhood search algorithm is designed to solve the problem， and the feasibility and effectiveness of the model and algorithm are verified by selecting the study example and comparing it with the traditional genetic algorithm. Experimental simulation results show that the logistics distribution method that considers customer satisfaction can not only effectively improve customer satisfaction， but also reduce the distribution cost and vehicle no-load rate of logistics enterprises， which has certain reference significance for the vehicle distribution path decision of logistics enterprises.

Keywords： fuzzy time window; customer satisfaction; traditional genetic algorithm; hybrid algorithm

［責任編校 陳留院 趙曉華］