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

摘要：針對當(dāng)前車輛路徑問題中較少考慮客戶滿意度的情況，構(gòu)建了基于具有一定的參考意義.輛路徑問題中考慮客戶滿意度是十分必要的.法求解帶時間窗的取送貨問題.混合算法進行求解，通過選取算例并與傳統(tǒng)遺線使得目標(biāo)函數(shù)達到最優(yōu).1)運輸車輛為同一類型，不同客戶之間的貨物種類相同，車輛勻速行駛，2)每個客戶的位置、時間窗、貨物需求量、以及配送中心位置均已知.V:所有節(jié)點集合，V={0,1,…dj:節(jié)點i到節(jié)點j的歐式距離；si:車輛在客戶節(jié)點i花費的服務(wù)時間；aki:車輛k到達客戶節(jié)點i的時間；pu:車輛k運輸客戶節(jié)點i的貨物時長；[ei,l]:客戶i對車輛到達時間的期望時間窗；[0,mi]:客戶i[0,M]:客戶i對于貨物運輸時長的可接受時間窗；Aki(ak):客戶i對于車輛k的到達時間滿意度函數(shù)；Pk(pki):客戶i對于車輛k的貨物運輸時長滿意度函數(shù)；x*j:當(dāng)車輛k從節(jié)點i到節(jié)點j時，x*j=1,否則為0;wi,wz,w?為相關(guān)目標(biāo)函數(shù)權(quán)重.間窗內(nèi)到達則客戶對于車輛到達時間的滿意度為100%,當(dāng)車輛在客戶期望時間(ak)=φ,0<an<ei},Li={ak|Ak(an)=φ,aw>li},則E^L=L-φ1β(L-l),此時客戶對于車輛到達時間的可接受時間窗為[E',L](Ei<E';<L^<Li)處理后的客戶對于車輛到達時間滿意度函數(shù)和圖像分別如式(1)和圖1所示：其中a,βi為客戶i對于車輛到達時間的滿意度系數(shù).對于貨物運輸時長的滿意度變化情況，用隸屬度函數(shù)Pki(pki)表示客戶對于貨閉區(qū)間[0,mi]和[0,M](0<mi<Mi)表示，如果貨物在達則客戶滿意度為100%;如果貨物在期望時間窗之外但在可接受時間窗內(nèi)到達，保每個客戶對于貨物運輸時長的滿意度均不低于w,令Mi={pa|Pa(pa)=w,pu>m},則M'=M-w1Y;(M-m),此時客戶可接的貨物運輸時長的時間窗為[0,M'](0<mi<M'<M),處理后的客戶對于貨物運輸圖像分別如式(2)和圖2所示：其中式(3)～(6)為目標(biāo)函數(shù)，式(3)表示最大化平均客戶對于車輛到達時間滿意度；式(4)表示最大化平均客戶對于貨物運輸時長滿意度；式(5)為最小化車輛運輸成本；式(6)為最小化車輛固定損耗成本；式(7)～(10)點進行消毒；式(11)和式(12)確保車輛在節(jié)點處保持流守恒；式(13)確保每個客戶有且僅能被服務(wù)一次；式(14)表示每個客戶的貨物運輸時長；式(15)表示車輛容量約束；式(16)、(17)表示車輛到達第一個客戶節(jié)點以及其他客戶節(jié)點的時間約束；式(18)表示車輛最長行駛時間約束；式(19)和(20)分別表示每個客戶對于車輛到達時間和貨物運輸時長的最低滿意度約束；式(21)表示決策變量為0-1變量.由于本文建立的為多目標(biāo)優(yōu)化數(shù)學(xué)模型，同時目標(biāo)函數(shù)式(3)、式(4)和式(5)、式(6)之間的數(shù)量級相差較大且求解問題不統(tǒng)一，為了便于求解，其中式(22)表示將最大化平均客戶對于車輛到達時間的滿意度轉(zhuǎn)化為最小化平均客戶對于車輛到達時間的不滿意度；式(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ù)wi,wz,w?,從而將本文多目標(biāo)優(yōu)化問題轉(zhuǎn)化為單目標(biāo)優(yōu)化問題.解，具體設(shè)計過程如下.過程如下.隨機選取一個客戶節(jié)點j(1≤jsn),構(gòu)成客戶序列[j,…,n,…,j+1],戶節(jié)點全部插入到車輛路徑中為止，此時形成VC(VC≤e)條車輛路徑.分別在第1條到第VC車輛路徑的末端加入一個0節(jié)點，將第1條到第VC條車輛路徑從左到右進行排列組成一條不完整的染色體cr,并判斷cr長度是否為n+e,如果不是，則在當(dāng)前cr的末端加入0節(jié)點，直到cr的長度為n+e時停止0節(jié)點的循環(huán)上述操作，直到生成的染色體數(shù)量為po時停止提取染色體中的每條車輛路徑，其中第一個0節(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條車輛路徑為空路徑.直到染色體中的所有車輛路徑(不含空路徑)提取完成.通過對種群中的每一個染色體Chi進行解碼操作，并根據(jù)式(24)求得的對應(yīng)的目標(biāo)函數(shù)值為Z,若染色體Chi為不可行解時，則對Z賦予一個極大數(shù)M.由于本文目標(biāo)函數(shù)為最小化問題，故令染色體Chi的適應(yīng)度函數(shù)值為f=1/Z,f盤賭法相結(jié)合，精英保留策略為：在每次迭代前，保留當(dāng)前種群中前10%的優(yōu)就越大，被選中的概率也就越大.當(dāng)需要選擇出m?個染色體時，輪盤需m?次，為了提升輪盤賭法的選擇效率以及增加被選擇出的染色體的多樣性入隨機遍歷抽樣法，即只需要一次生成m?個等間距的指針位置，便可選擇出首先保留前10%的優(yōu)質(zhì)染色體直接進入下一代種群；然后計算種群中每個染色體被選中的概率pi=f/ZP?=fx以及累積概率P=Zx-1px,假設(shè)此時需要選擇出m1個染色體，則指針間距Ga=Z?=1之間的隨機數(shù));最后計算各個指針的位置，其中St+Ga*ii(O≤ii≤m1-1且ii為自然數(shù))代表第ii+1個指針指向的位置，直到生成m1個指針為止，指針?biāo)傅奈恢眉礊楸贿x擇的染色體，此時選擇出m?個染色體.假設(shè)種群中有6個染色體，此時需要選擇出5個染色體，則在輪盤賭法的基礎(chǔ)上過程如圖3所示.采用一種新的交叉算子(簡稱隨機片段交叉)進行交叉操作.下面舉例說明具體交叉過程如圖4所示：其中1～7為客戶節(jié)點，可使用車輛數(shù)為4.首先隨機選取父代染色體1中的一條車輛路徑(不含空路徑)和父代染色體2中的一條車輛路徑(不含空路徑)進行隨機片段交叉操作；然后分別將交叉片段放入染色體1和2的首端，并刪除父代染色體1和2中與交叉片段相同的客戶節(jié)點；最后在父代染色體1和2的末端刪除1個0節(jié)點保持染色體的長度不變，此時生成兩體.具體求解流程如下.首先從in中隨機選取一個客戶節(jié)點c并放入C中作為第一個元素，隨后將的客戶節(jié)點c,將c從in中刪除并且放入C中，重復(fù)該操作S-1次，當(dāng)C中的客戶節(jié)點數(shù)量等于S時停止移除操作；最后將被移除的客戶節(jié)點其中R的取值范圍為(0,1);D的取值范圍為(0,1),表示歐式距離為1,否則為0;T的取值范圍為(0,1),表示客戶節(jié)點的期望車輛到達時間窗的下限差值的絕對值越小，則客戶節(jié)點之間的將in中剩余客戶節(jié)點與Ct相關(guān)性按照從大到小進行排列，如果每次移除都因此加入隨機元素Dx(n-s),其中(n-s)表示當(dāng)前in中的客戶節(jié)點數(shù)目；當(dāng)算例規(guī)模的大小進行設(shè)定，即D值越小，則被移除的客戶節(jié)點的相關(guān)性就越強.首先，提取當(dāng)前ch中的每條車輛路徑(不含空路徑),尋找C中的每一個3個約束：車輛到達每個客戶節(jié)點的時間不超過客戶節(jié)點對于車輛到達時間的期然后，對比C中所有客戶節(jié)點的最優(yōu)插入位置的距離增量，采用最遠(yuǎn)插入輛路徑和刪除C中的該客戶節(jié)點.循環(huán)上述操作直到C為空集，隨后更新染色體中的每條車輛路徑，通過刪除末端0節(jié)點確保生成的新的染色體chnew的長度為n+e.判斷經(jīng)過LNSA處理前后染重復(fù)的染色體進行刪除是十分必要的.5所示.(TM)i5-4200HCPU@2.80配送中心的坐標(biāo)為(41,40),車輛最大載重量Q=5t,車輛行駛速度為45km/h,時間窗[0,Mi]為：Mi=mi+0.6,車輛最長行駛時間為4h,客戶節(jié)點坐標(biāo)以及相關(guān)信息如表1所示.變異概率分別為0.9、0.9、0.1,種群規(guī)模和最大迭代次數(shù)分別為100、100.由圖6可得傳統(tǒng)遺傳算法求得的最優(yōu)車輛配送路徑為7條，分別為對于車輛到達時間滿意度和貨物運輸時長的滿意度分別為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→10→5→15→18→0,平均客戶對于車輛到達時間滿意度和貨物運輸時長的滿意度分別為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)解.通過分析進一步表明，一方面，傳統(tǒng)遺傳算法在初始種群生成的過程中，雖然隨機生成初始解以保持染色體的多樣性，但是種群中染色體的適應(yīng)度值普遍偏低，甚至部分染色體為不可行解，從而導(dǎo)致了算法的尋優(yōu)能力下降，也更容易過早地陷入局部最優(yōu)；而在生成初始種群的過程中，加入插入啟發(fā)式算法并保持節(jié)點插入的隨機性，使得初始種群的染色體質(zhì)量得到了有效提升，不僅保證了種群中染色體的多樣性，而且有利于提升算法的收斂速度.另一方面，在選擇操作的過程中，加入