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

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