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

摘要：針對當(dāng)前車輛路徑問題中較少考慮客戶滿意度的情況，構(gòu)建了基于模糊時間窗的車輛到達(dá)時間滿意度函數(shù)和貨物運輸時長滿意度函數(shù)，以最大化客戶滿意度和最小化配送總成本為目標(biāo)建立VRPCCS數(shù)學(xué)模型.為了求解該問題，考慮到傳統(tǒng)遺傳算法存在依賴初始解、收斂速度較慢、容易陷入局部最優(yōu)等缺點，設(shè)計改進(jìn)的遺傳算法與大規(guī)模鄰域搜索算法相結(jié)合的混合算法進(jìn)行求解，通過選取算例并與傳統(tǒng)遺傳算法進(jìn)行對比，驗證了模型和算法的可行性和有效性.實驗仿真結(jié)果表明考慮客戶滿意度的物流配送方式不僅能夠有效提升客戶滿意度，也能夠降低物流企業(yè)配送成本以及車輛空載率，對于物流企業(yè)的車輛配送路徑?jīng)Q策具有一定的參考意義.關(guān)鍵詞：模糊時間窗；客戶滿意度；傳統(tǒng)遺傳算法；混合算法隨著當(dāng)前物流運輸行業(yè)的市場競爭日益激烈，客戶對于貨物配送要求的不斷提高，客戶滿意度的提升對于物流企業(yè)的發(fā)展顯得尤為重要，提升客戶滿意度不僅能夠提高企業(yè)的市場競爭力，而且能夠培養(yǎng)客戶對于企業(yè)的信任度，因此在車輛路徑問題中考慮客戶滿意度是十分必要的.車輛路徑問題（vehicleroutingproblem，VRP）作為物流配送中的關(guān)鍵環(huán)節(jié)，是當(dāng)前相關(guān)研究中的熱點問題［1］.車輛路徑問題由DANTZIG等［2］首次提出并為不同的需求點提供物資配送，以運輸成本最小化為目標(biāo)建立模型；CALVETE等［3］基于軟時間窗構(gòu)建了多目標(biāo)車輛路徑優(yōu)化模型；KOVACS等［4］研究了容量約束的多目標(biāo)車輛路徑優(yōu)化問題；符卓等［5］研究了基于軟時間窗的需求可拆分的車輛路徑問題；范靜［6］研究了同時收發(fā)貨的車輛路徑問題，以客戶等待時間的長短來衡量客戶滿意度，以車輛行駛路程和客戶等待時間最小化為目標(biāo)采用禁忌搜索算法求解；李得成等［7］研究了帶有時間窗的電動車與燃油車混合車輛路徑問題，以車輛行駛路程消耗成本最小化為目標(biāo)采用分支定價算法進(jìn)行求解；王奕璇等［8］研究了低碳下帶時間窗的冷藏藥品車輛路徑問題，以制冷、運輸、貨損和固定成本為目標(biāo)建立模型；葛顯龍等［9］研究了帶軟時間窗的車輛路徑問題，以總成本最小化為目標(biāo)建立模型；BRUGLIERI等［10］提出了一個三階段數(shù)學(xué)方法求解城市內(nèi)物流配送路徑問題，以車輛使用數(shù)量和行駛總時間最小化為目標(biāo)；倪霖等［11］考慮了車輛同時取送貨對車輛裝載率的影響，以配送總成本最小化為目標(biāo)采用遺傳算法進(jìn)行求解；任騰等［12］考慮了同時取送貨的城市物流共同配送路徑問題，以總支出費用最小化為目標(biāo)建立模型，并采用遺傳算法進(jìn)行求解；AGHEZZAF等［13］研究了單車型的車輛路徑問題，以利潤最大化為目標(biāo)建立模型；王征等［14］研究了多車場帶時間窗的車輛路徑問題，并提出了改進(jìn)的變鄰域搜索算法進(jìn)行求解；WANG等［15］設(shè)計一種帶有禁忌搜索的混合遺傳算法求解多倉庫共同接送車輛路徑問題.潘立軍等［16］提出基于時差插入法的遺傳算法求解帶時間窗的取送貨問題.綜上所述，有關(guān)物流配送路徑問題的相關(guān)文獻(xiàn)主要集中在以降低成本為主要目標(biāo)，而以客戶滿意度為目標(biāo)的研究尚且不多，因此本文考慮了客戶滿意度的車輛路徑問題（vehicleroutingproblemconsideringcusto-mersatisfaction，VRPCCS），從客戶對配送車輛的到達(dá)時間和貨物運輸時長兩方面來衡量客戶滿意度并建立滿意度函數(shù)，以客戶滿意度最大化和配送總成本最小化為目標(biāo)建立VRPCCS數(shù)學(xué)模型，設(shè)計改進(jìn)的遺傳算法（geneticalgorithm，GA）與大規(guī)模鄰域搜索算法（large-scaleneighborhoodsearchalgorithm，LNSA）相結(jié)合的混合算法進(jìn)行求解，通過選取算例并與傳統(tǒng)遺傳算法進(jìn)行對比，驗證VRPCCS數(shù)學(xué)模型以及混合算法的可行性和有效性.1數(shù)學(xué)模型構(gòu)建1.1問題描述本文的VRPCCS可以簡述為：某貨物配送中心擁有K輛相同的運輸車輛，為n個客戶提供貨物配送服務(wù)，所有車輛從配送中心出發(fā)，每個客戶的貨物需求量提前已知且每個客戶有且僅能被服務(wù)一次，車輛必須在最長行駛時間范圍內(nèi)完成每條配送路線并回到終點處進(jìn)行消毒，本文目標(biāo)為尋找合理有效的車輛配送路線使得目標(biāo)函數(shù)達(dá)到最優(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｝；qi：客戶i的貨物需求量；Q：車輛的最大貨物容量；dij：節(jié)點i到節(jié)點j的歐式距離；si：車輛在客戶節(jié)點i花費的服務(wù)時間；aki：車輛k到達(dá)客戶節(jié)點i的時間；pki：車輛k運輸客戶節(jié)點i的貨物時長；tij：車輛從節(jié)點i到節(jié)點j的行駛時間；［ei，li］：客戶i對車輛到達(dá)時間的期望時間窗；［Ei，Li］：客戶i對于車輛到達(dá)時間的可容忍時間窗；［0，mi］：客戶i對于貨物運輸時長的期望時間窗；［0，Mi］：客戶i對于貨物運輸時長的可接受時間窗；Lmax：車輛完成每條配送路徑的最長行駛時間限制；Aki（aki）：客戶i對于車輛k的到達(dá)時間滿意度函數(shù)；Pki（pki）：客戶i對于車輛k的貨物運輸時長滿意度函數(shù)；φ：客戶對車輛到達(dá)時間的最低滿意度；ω：客戶對貨物運輸時長的最低滿意度；C1：平均客戶對于車輛到達(dá)時間的不滿意度懲罰成本；C2：平均客戶對于貨物運輸時長的不滿意度懲罰成本；C3：單位里程車輛運輸成本；C4：車輛每次使用的固定損耗成本；xkij：當(dāng)車輛k從節(jié)點i到節(jié)點j時，xkij=1，否則為0；w1，w2，w3為相關(guān)目標(biāo)函數(shù)權(quán)重.1.3車輛到達(dá)時間滿意度函數(shù)車輛配送路徑問題中的硬時間窗和軟時間窗均無法準(zhǔn)確地反映出客戶對于車輛到達(dá)時間的滿意度變化情況.通常情況下，大多數(shù)客戶期望車輛在某個特定的時間范圍內(nèi)到達(dá)，車輛過早或者過晚的到達(dá)均會造成客戶對于車輛到達(dá)時間滿意度的降低.本文采用模糊時間窗來反映客戶對于車輛到達(dá)時間的滿意度程度，將模糊時間窗看作關(guān)于車輛到達(dá)時間aki的凹模糊數(shù)，用模糊數(shù)的隸屬度函數(shù)Aki（aki）表示客戶對于車輛到達(dá)時間的滿意度，模糊時間窗包含客戶對于車輛到達(dá)時間的期望時間窗和可接受時間窗，其中客戶i的期望時間窗和可接受時間窗分別用閉區(qū)間［ei，li］和［Ei，Li］（Ei＜ei＜li＜Li）表示，車輛在客戶期望的時間窗內(nèi)到達(dá)則客戶對于車輛到達(dá)時間的滿意度為100%，當(dāng)車輛在客戶期望時間窗之外但在可接受的時間窗之內(nèi)到達(dá)，客戶對于車輛到達(dá)時間的滿意度隨著車輛到達(dá)時間與客戶期望時間窗的差值的增大而降低.為了提升車輛配送過程中的服務(wù)質(zhì)量，因此確保每一個客戶對于車輛到達(dá)時間的滿意度不低于φ，令E*i=｛aki|Aki（aki）=φ，0＜aki＜ei｝，L*i=｛aki|Aki（aki）=φ，aki＞li｝，則E*i=Ei+φ1/αi（ei-Ei），L*i=Li-φ1/βi（Li-li），此時客戶對于車輛到達(dá)時間的可接受時間窗為［E*i，L*i］（Ei＜E*i＜L*i＜Li）處理后的客戶對于車輛到達(dá)時間滿意度函數(shù)和圖像分別如式（1）和圖1所示：其中αi，βi為客戶i對于車輛到達(dá)時間的滿意度系數(shù).1.4貨物運輸時長滿意度函數(shù)在實際的貨物運輸過程中，貨物的質(zhì)量會隨著貨物運輸時長的增加而不斷下降，因此貨物運輸時長也會對客戶的滿意度產(chǎn)生影響.用模糊時間窗來反映客戶對于貨物運輸時長的滿意度變化情況，用隸屬度函數(shù)Pki（pki）表示客戶對于貨物運輸時長的滿意度，此時模糊時間窗包含客戶期望貨物運輸時長的時間窗和可接受的貨物運輸時長的時間窗，其中客戶i的期望時間窗和可接受時間窗分別用閉區(qū)間［0，mi］和［0，Mi］（0＜mi＜Mi）表示，如果貨物在期望時間窗內(nèi)到達(dá)則客戶滿意度為100%；如果貨物在期望時間窗之外但在可接受時間窗內(nèi)到達(dá)，則客戶對于貨物運輸時長的滿意度隨著貨物運輸時長的增加而不斷下降.為了確保每個客戶對于貨物運輸時長的滿意度均不低于ω，令M*i=｛pki|Pki（pki）=ω，pki＞mi｝，則M*i=Mi-ω1/γi（Mi-mi），此時客戶可接的貨物運輸時長的時間窗為［0，M*i］（0＜mi＜M*i＜Mi），處理后的客戶對于貨物運輸時長滿意度函數(shù)和圖像分別如式（2）和圖2所示：其中γi為客戶i對于貨物運輸時長的滿意度系數(shù).1.5數(shù)學(xué)模型構(gòu)建根據(jù)以上分析，構(gòu)建的數(shù)學(xué)模型如下：其中式（3）～（6）為目標(biāo)函數(shù)，式（3）表示最大化平均客戶對于車輛到達(dá)時間滿意度；式（4）表示最大化平均客戶對于貨物運輸時長滿意度；式（5）為最小化車輛運輸成本；式（6）為最小化車輛固定損耗成本；式（7）～（10）為車輛在起點和終點的約束，即每輛車必須從起點出發(fā)，完成配送任務(wù)后回到終點進(jìn)行消毒；式（11）和式（12）確保車輛在節(jié)點處保持流守恒；式（13）確保每個客戶有且僅能被服務(wù)一次；式（14）表示每個客戶的貨物運輸時長；式（15）表示車輛容量約束；式（16）、（17）表示車輛到達(dá)第一個客戶節(jié)點以及其他客戶節(jié)點的時間約束；式（18）表示車輛最長行駛時間約束；式（19）和（20）分別表示每個客戶對于車輛到達(dá)時間和貨物運輸時長的最低滿意度約束；式（21）表示決策變量為0-1變量.1.6目標(biāo)函數(shù)處理由于本文建立的為多目標(biāo)優(yōu)化數(shù)學(xué)模型，同時目標(biāo)函數(shù)式（3）、式（4）和式（5）、式（6）之間的數(shù)量級相差較大且求解問題不統(tǒng)一，為了便于求解，做出以下處理：其中式（22）表示將最大化平均客戶對于車輛到達(dá)時間的滿意度轉(zhuǎn)化為最小化平均客戶對于車輛到達(dá)時間的不滿意度；式（23）表示將最大化平均客戶對于貨物運輸時長的滿意度轉(zhuǎn)化為最小化平均客戶對于貨物運輸時長的不滿意度；式（24）表示本文最終處理后的目標(biāo)函數(shù)，首先將目標(biāo)函數(shù)式（22）和式（23）分別乘以對應(yīng)的懲罰系數(shù)使其與目標(biāo)函數(shù)式（5）和式（6）的數(shù)量級保持一致，然后通過加權(quán)的方法，對目標(biāo)函數(shù)式（22）、式（23）、式（5）和式（6）分別賦予權(quán)重系數(shù)w1，w2，w3，從而將本文多目標(biāo)優(yōu)化問題轉(zhuǎn)化為單目標(biāo)優(yōu)化問題.2混合算法設(shè)計遺傳算法（GA）作為啟發(fā)式算法能夠在較短的時間內(nèi)獲得問題的有效解，適合求解復(fù)雜的優(yōu)化問題，具有較好的全局搜索能力和魯棒性，同時考慮到遺傳算法存在依賴初始解、收斂速度較慢、容易陷入局部最優(yōu)等缺點，為了改進(jìn)這一問題，設(shè)計一種改進(jìn)的遺傳算法與大規(guī)模鄰域搜索算法相結(jié)合的混合算法進(jìn)行求解，具體設(shè)計過程如下.2.1改進(jìn)遺傳算法設(shè)計2.1.1染色體編碼及初始種群的生成采用整數(shù)編碼方式進(jìn)行染色體編碼，運用插入啟發(fā)式算法構(gòu)造初始染色體種群.用e代表配送中心可使用的車輛數(shù)，po代表種群規(guī)模，初始種群生成的具體過程如下.隨機選取一個客戶節(jié)點j（1≤j≤n），構(gòu)成客戶序列［j，…，n，…，j+1］，從左到右依次遍歷序列中節(jié)點并插入到車輛路徑中.如果即將插入的客戶節(jié)點的貨物需求量qi與當(dāng)前該條車輛路徑中已插入的客戶節(jié)點的貨物需求量之和大于Q，則新增一條車輛路徑并將當(dāng)前該客戶節(jié)點插入，否則將當(dāng)前客戶節(jié)點插入到當(dāng)前該條車輛路徑中，并按照客戶期望車輛到達(dá)時間窗的下限ei的大小確定當(dāng)前客戶節(jié)點的具體插入位置，即車輛路徑中的客戶節(jié)點按照期望車輛到達(dá)時間窗的下限ei的大小從左到右進(jìn)行排列；如果當(dāng)前車輛路徑數(shù)目為e，則將剩余的尚未插入的客戶節(jié)點全部插入到第e條車輛路徑中.如此循環(huán)操作，直到所有的客戶節(jié)點全部插入到車輛路徑中為止，此時形成VC（VC≤e）條車輛路徑.分別在第1條到第VC車輛路徑的末端加入一個0節(jié)點，將第1條到第VC條車輛路徑從左到右進(jìn)行排列組成一條不完整的染色體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è)計通過對種群中的每一個染色體Chi進(jìn)行解碼操作，并根據(jù)式（24）求得的對應(yīng)的目標(biāo)函數(shù)值為Zi，若染色體Chi為不可行解時，則對Zi賦予一個極大數(shù)M.由于本文目標(biāo)函數(shù)為最小化問題，故令染色體Chi的適應(yīng)度函數(shù)值為fi=1/Zi，fi越大則代表該染色體越接近待求解問題的最優(yōu)解.2.1.4選擇操作在選擇操作的過程中采用精英保留策略、隨機遍歷抽樣法與傳統(tǒng)GA中的輪盤賭法相結(jié)合，精英保留策略為：在每次迭代前，保留當(dāng)前種群中前10%的優(yōu)質(zhì)染色體直接進(jìn)入下一代種群中，這樣有利于提升算法的收斂速度和防止最優(yōu)解的丟失.輪盤賭法的基本思想為：染色體的適應(yīng)度值越大，在輪盤中所占的角度就越大，被選中的概率也就越大.當(dāng)需要選擇出m1個染色體時，輪盤需要轉(zhuǎn)動m1次，為了提升輪盤賭法的選擇效率以及增加被選擇出的染色體的多樣性，加入隨機遍歷抽樣法，即只需要一次生成m1個等間距的指針位置，便可選擇出m1個染色體.選擇操作的具體流程如下.首先保留前10%的優(yōu)質(zhì)染色體直接進(jìn)入下一代種群；然后計算種群中每個染色體被選中的概率pi=fi/∑pox=1fx以及累積概率Pi=∑ix=1px，假設(shè)此時需要選擇出m1個染色體，則指針間距Ga=∑poi=1fi/m1，隨機生成指針的起點位置St（0～Ga之間的隨機數(shù)）；最后計算各個指針的位置，其中St+Ga*ii（0≤ii≤m1-1且ii為自然數(shù)）代表第ii+1個指針指向的位置，直到生成m1個指針為止，指針?biāo)傅奈恢眉礊楸贿x擇的染色體，此時選擇出m1個染色體.假設(shè)種群中有6個染色體，此時需要選擇出5個染色體，則在輪盤賭法的基礎(chǔ)上采用隨機遍歷抽樣法的選擇過程如圖3所示.2.1.5交叉操作在染色體種群中，以一定的交叉概率對選擇出的染色體進(jìn)行交叉操作，本文采用一種新的交叉算子（簡稱隨機片段交叉）進(jìn)行交叉操作.下面舉例說明具體交叉過程如圖4所示：其中1～7為客戶節(jié)點，可使用車輛數(shù)為4.首先隨機選取父代染色體1中的一條車輛路徑（不含空路徑）和父代染色體2中的一條車輛路徑（不含空路徑）進(jìn)行隨機片段交叉操作；然后分別將交叉片段放入染色體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)過選擇和交叉操作后的染色體以較低的概率進(jìn)行變異操作，類似于生物進(jìn)化過程中的基因突變，因此變異的可能性較小.本文變異操作采用互換變異的方法，即隨機選取4個客戶節(jié)點基因進(jìn)行兩兩互換，從而產(chǎn)生新的染色體.2.2大規(guī)模鄰域搜索算法設(shè)計LNSA是由SHAW［17］首次提出的，其主要思想為：使用移除算子從當(dāng)前解中移除若干點，然后使用修復(fù)算子將被破壞的解進(jìn)行修復(fù)，從而希望得到更加優(yōu)質(zhì)的解.在該理論基礎(chǔ)上結(jié)合本文所求問題，進(jìn)行了相應(yīng)的調(diào)整和改進(jìn)，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é)點按照以下策略進(jìn)行移除：每次從C中隨機選擇一個客戶節(jié)點c1，計算c1與in中的剩余的客戶節(jié)點的相關(guān)性，并且按照與c1的相關(guān)性由大到小進(jìn)行排列，從in中選擇出一個與c1相關(guān)性較大的客戶節(jié)點c，將c從in中刪除并且放入C中，重復(fù)該操作S-1次，當(dāng)C中的客戶節(jié)點數(shù)量等于S時停止移除操作；最后將被移除的客戶節(jié)點從當(dāng)前ch中移除，并更新ch.相關(guān)性計算公式如下所示：其中Rij的取值范圍為（0，1）;D′ij的取值范圍為（0，1］，表示歐式距離越近的客戶節(jié)點之間的相關(guān)性就越強；Vij表示當(dāng)節(jié)點i和j在同一條車輛路徑中為1，否則為0；T′ij的取值范圍為（0，1］，表示客戶節(jié)點的期望車輛到達(dá)時間窗的下限差值的絕對值越小，則客戶節(jié)點之間的相關(guān)性就越強.將in中剩余客戶節(jié)點與c1相關(guān)性按照從大到小進(jìn)行排列，如果每次移除都選擇in中相關(guān)性最大的客戶節(jié)點進(jìn)行移除，可能會降低客戶節(jié)點移除的隨機性，因此加入隨機元素D×（n-s），其中（n-s）表示當(dāng)前in中的客戶節(jié)點數(shù)目；當(dāng)算法迭代Ge次仍未得到改進(jìn)時，則令D=D+X（1≤D≤n-S），X和D的值可由算例規(guī)模的大小進(jìn)行設(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個約束：車輛到達(dá)每個客戶節(jié)點的時間不超過客戶節(jié)點對于車輛到達(dá)時間的期望時間窗的上限Li、車輛不超過容量約束以及車輛最長行駛時間約束，則為可行的插入位置.然后，對比C中所有客戶節(jié)點的最優(yōu)插入位置的距離增量，采用最遠(yuǎn)插入啟發(fā)式算法，找出距離增量最大的客戶節(jié)點并插回到車輛路徑中，并更新該條車輛路徑和刪除C中的該客戶節(jié)點.最后，每插回一個客戶節(jié)點則重新尋找C中剩余客戶節(jié)點的最優(yōu)插入位置，循環(huán)上述操作直到C為空集，隨后更新染色體中的每條車輛路徑，通過刪除末端0節(jié)點確保生成的新的染色體chnew的長度為n+e.判斷經(jīng)過LNSA處理前后染色體的目標(biāo)函數(shù)值，如果chnew更優(yōu)，則更新染色體，令ch=chnew，否則不更新.2.3其他操作混合算法每次迭代后進(jìn)行以下處理.2.3.1刪除重復(fù)的染色體當(dāng)求解的問題規(guī)模越小，種群規(guī)模越大時，種群中出現(xiàn)重復(fù)的染色體的可能性就越大，重復(fù)的染色體過多則會影響算法的求解效率和收斂性，因此將種群中重復(fù)的染色體進(jìn)行刪除是十分必要的.2.3.2補足染色體種群當(dāng)刪除種群中重復(fù)的染色體后，隨機生成新的染色體來補足種群規(guī)模，有利于提升算法的求解效率和收斂性.2.4算法終止條件及流程圖當(dāng)混合算法迭代次數(shù)達(dá)到預(yù)設(shè)的值時，終止混合算法的運行，求解流程如圖5所示.3仿真實驗及結(jié)果分析本文利用MATLABR2017b進(jìn)行編程求解，所有數(shù)據(jù)均在Intel（R）Core（TM）i5-4200HCPU@2.80GHz配置的計算機上進(jìn)行仿真實驗，具體如下.3.1算例選取假設(shè)某貨物配送中心的可使用車輛數(shù)為8，向20個客戶節(jié)點配送貨物，貨物配送中心、客戶期望車輛到達(dá)時間窗、各個節(jié)點之間的距離均提前已知，貨物配送中心的坐標(biāo)為（41，40），車輛最大載重量Q=5t，車輛行駛速度為45km/h，其他相關(guān)參數(shù)取值為：αi=0.3，βi=0.8，γi=0.6，φ=0.3，ω=0.3，C1=100元，C2=200元，C3=3元，C4=100元，w1=0.3，w2=0.3，w3=0.4.客戶可接受的車輛到達(dá)時間窗［Ei，Li］為：Ei=ei-0.6，Li=li+0.4，客戶可接受的貨物運輸時長的時間窗［0，Mi］為：Mi=mi+0.6，車輛最長行駛時間為4h，客戶節(jié)點坐標(biāo)以及相關(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，平均客戶對于車輛到達(dá)時間滿意度和貨物運輸時長的滿意度分別為94.15%、97.15%，平均客戶滿意度為95.65%，車輛總行駛路程為545.35km，求解結(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，平均客戶對于車輛到達(dá)時間滿意度和貨物運輸時長的滿意度分別為99.87%、97.15%，平均客戶滿意度為98.51%，車輛總行駛路程為436.25km，求解結(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)解.通過分析進(jìn)一步表明，一方面，傳統(tǒng)遺傳算法在初始種群生成的過程中，雖然隨機生成初始解以保持染色體的多樣性，但是種群中染色體的適應(yīng)度值普遍偏低，甚至部分