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

羅明亮 袁鵬程

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

關(guān)鍵詞：模糊時間窗；客戶滿意度；傳統(tǒng)遺傳算法；混合算法

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

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

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

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

1 數(shù)學(xué)模型構(gòu)建

1.1 問題描述

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

1.2 基本假設(shè)及參數(shù)說明

本文在構(gòu)建VRPCCS數(shù)學(xué)模型之前做出以下假設(shè)：

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

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

相關(guān)參數(shù)及變量如下所示：

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

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

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

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

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

d_ij：節(jié)點i到節(jié)點j的歐式距離；

s_i：車輛在客戶節(jié)點i花費的服務(wù)時間；

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

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

t_ij：車輛從節(jié)點i到節(jié)點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的到達時間滿意度函數(shù)；

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

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

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

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

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

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

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

x^k_ij：當(dāng)車輛k從節(jié)點i到節(jié)點j時，x^k_ij=1，否則為0；

w₁，w₂，w₃為相關(guān)目標函數(shù)權(quán)重.

1.3 車輛到達時間滿意度函數(shù)

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

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

1.4 貨物運輸時長滿意度函數(shù)

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

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

1.5 數(shù)學(xué)模型構(gòu)建

根據(jù)以上分析，構(gòu)建的數(shù)學(xué)模型如下：

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

1.6 目標函數(shù)處理

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

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

2 混合算法設(shè)計

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

2.1 改進遺傳算法設(shè)計

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

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

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

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

2.1.2 染色體解碼

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

2.1.3 適應(yīng)度函數(shù)設(shè)計

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

2.1.4 選擇操作

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

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

2.1.5 交叉操作

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

2.1.6 變異操作

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

2.2 大規(guī)模鄰域搜索算法設(shè)計

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

2.2.1 移除操作

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

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

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

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

2.2.2 修復(fù)操作

修復(fù)操作是將被移除的節(jié)點重新插回到染色體ch中，從而希望產(chǎn)生更加優(yōu)質(zhì)的染色體.修復(fù)操作具體如下.

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

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

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

2.3 其他操作

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

2.3.1 刪除重復(fù)的染色體

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

2.3.2 補足染色體種群

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

2.4 算法終止條件及流程圖

當(dāng)混合算法迭代次數(shù)達到預(yù)設(shè)的值時，終止混合算法的運行，求解流程如圖5所示.

3 仿真實驗及結(jié)果分析

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

3.1 算例選取

假設(shè)某貨物配送中心的可使用車輛數(shù)為8，向20個客戶節(jié)點配送貨物，貨物配送中心、客戶期望車輛到達時間窗、各個節(jié)點之間的距離均提前已知，貨物配送中心的坐標為（41，40），車輛最大載重量Q=5 t，車輛行駛速度為45 km/h，其他相關(guān)參數(shù)取值為：α_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，客戶節(jié)點坐標以及相關(guān)信息如表1所示.

3.2 遺傳算法求解結(jié)果

根據(jù)構(gòu)建的VRPCCS數(shù)學(xué)模型，GA相關(guān)參數(shù)設(shè)置為：選擇代溝、交叉和變異概率分別為0.9、0.9、0.1，種群規(guī)模和最大迭代次數(shù)分別為100、100.由圖6可得傳統(tǒng)遺傳算法求得的最優(yōu)車輛配送路徑為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，求解結(jié)果如表2所示.

3.3 混合算法求解結(jié)果

在上述GA相關(guān)參數(shù)設(shè)置的基礎(chǔ)上，LNSA的相關(guān)參數(shù)設(shè)置為：移除的客戶節(jié)點總數(shù)，隨機元素中的參數(shù)和分別取值為1、1，預(yù)設(shè)的次數(shù)Ge=5.由圖7可得混合算法求得的最優(yōu)車輛配送路徑為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，求解結(jié)果如表2所示.

3.4 結(jié)果對比分析

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

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

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

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

由表2可知，通過上述算例與傳統(tǒng)遺傳算法求解結(jié)果進行對比，本文設(shè)計的混合算法的優(yōu)點主要表現(xiàn)在以下兩個方面：

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

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

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

4 結(jié) 論

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

參 考 文 獻

［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］.中國管理科學(xué)，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］范靜.考慮客戶滿意度的同時收發(fā)車輛路徑問題［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］.系統(tǒng)工程理論與實踐，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］王奕璇，陳荔，王濤.低碳下帶時間窗的冷藏藥品路徑優(yōu)化［J］.科技和產(chǎn)業(yè)，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］.計算機應(yīng)用研究，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］倪霖，劉凱朋，涂志剛.考慮同時取送貨的城市快遞共同配送路徑優(yōu)化［J］.重慶大學(xué)學(xué)報，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］任騰，羅天羽，谷智華，等.考慮同時取送貨的城市物流共同配送路徑優(yōu)化［J］.計算機集成制造系統(tǒng)，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］.中國管理科學(xué)，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］.系統(tǒng)工程理論與實踐，2012，32（1）：120-126.

PAN L J，F(xiàn)U 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

［責(zé)任編校 陳留院 趙曉華］