田帥輝 歐麗英

摘? 要：城市居民小批量、個性化、便利化、高效化等配送需求以及日益擁堵的城市交通對城市配送效率提出更高的挑戰(zhàn)。針對城市配送路徑優(yōu)化問題，以平均配送時間與總配送費用帕累托最優(yōu)為目標，構(gòu)建考慮時間窗的城市配送車輛路徑優(yōu)化模型，對遺傳算法進行改進，在標準遺傳算法的基礎上加入篩選算子和擇優(yōu)算子并適當改進初始種群設計和選擇、交叉算子，最后通過算例驗證模型的可行性和改進算法的有效性。結(jié)果表明改進后的遺傳算法在求解考慮時間窗的車輛路徑優(yōu)化模型時，相較于標準的遺傳算法的尋優(yōu)能力有顯著優(yōu)勢。

關鍵詞：改進遺傳算法;時間窗;多目標優(yōu)化;城市配送

中圖分類號：F272.14??? 文獻標識碼：A

Abstract： The distribution needs of urban residents， such as small batch， individualization， convenience， high efficiency and increasingly congested urban traffic， pose a higher challenge to the efficiency of urban distribution. Aiming at the problem of urban distribution routing optimization， taking the Pareto optimization of average distribution time and total distribution cost as the objective， a vehicle routing optimization model with time windows for urban distribution considering time window is construct， and the genetic algorithm is also improved， which is added screening operator and optimizing operator on the basis of standard genetic algorithm， and the initial population design and selection， crossover operator is improved appropriately. Finally， the feasibility of the model and the effectiveness of the improved algorithm are verified by an example. The results show that the improved genetic algorithm has significant advantages over the standard genetic algorithm in solving the vehicle routing optimization model with time windows.

Key words： improved genetic algorithm; time window; multi-objective; urban distribution

0? 引? 言

近年來，隨著電子商務、O2O、新零售等新型商業(yè)模式的迅猛發(fā)展，全國城市配送市場規(guī)模已突破萬億，預計2021年將超過2萬億。同時，我國城市居民的消費需求呈現(xiàn)小批量、個性化、多樣化、便利化、高效化等特征，這對城市配送效率提出了更高的要求和挑戰(zhàn)。

圍繞城市配送路徑優(yōu)化，國內(nèi)外學者進行了深入的研究。關于城市配送路徑優(yōu)化，部分學者從優(yōu)化算法的角度進行研究。其中，吳聰[1]令遺傳算法交叉系數(shù)和變異系數(shù)隨適應度的大小、迭代次數(shù)和進化過程中個體未改變的數(shù)目自適應調(diào)整;羅勇[2]提出對遺傳算法算子進行改進;申艷光[4]、胡鐘駿[5]等則將遺傳算法與其他算法進行結(jié)合，結(jié)合其他算法的優(yōu)勢來彌補遺傳算法的不足。同時由于車輛路徑問題（Vehicle Routing Problem， VRP）在現(xiàn)實情況下會受到多方面因素的影響，部分學者在考慮該問題時從多目標進行優(yōu)化[6-8]。隨著顧客對配送時效的要求日益提高，時間成為影響消費者滿意度的一個至關重要的因素，國內(nèi)外研究學者也紛紛將時間作為重要目標之一運用蟻群算法[9]、粒子群算法[10-11]、遺傳算法和一些混合算法等進行路徑優(yōu)化;就遺傳算法而言，侯玉梅[12]、Tas[13]等強調(diào)軟時間窗對物流配送優(yōu)化所起到的關鍵作用。這些研究強調(diào)了不同算法下的時間限定，從以上分析可以發(fā)現(xiàn)，目前大多數(shù)研究運用遺傳算法進行配送路徑優(yōu)化側(cè)重于結(jié)合其他算法的優(yōu)勢，而從多目標優(yōu)化出發(fā)，強調(diào)時間窗和載重約束，通過添加新的遺傳算法算子進行改進相對較少。因此本文結(jié)合實際情景，在強調(diào)時間和成本兩個目標在城市配送路徑優(yōu)化的重要性上對遺傳算法進行優(yōu)化，受人工培育豌豆的啟發(fā)優(yōu)化尋優(yōu)過程，結(jié)合實際條件約束，改進相應的算法步驟并添加相關的算子，在充分利用遺傳算法全局搜索特性的同時，使其在解決有時間窗車輛路徑問題（Vehicle Routing Problems with Time Windows，VRPTW）問題時尋優(yōu)能力更佳，得到更有效可靠的解。通過和標準遺傳算法的尋優(yōu)結(jié)果進行對比，驗證改進后的遺傳算法具有更強的尋優(yōu)能力。

1? 模型構(gòu)建

1.1? 問題描述及符號說明

帶軟時間窗的多目標城市配送車輛路徑優(yōu)化問題（多目標VRPTW）描述為（如圖1所示）：某城市配送中心擁有Kk∈K輛型號規(guī)格完全一樣的配送車輛，其最大載重量G完全相同，且城市配送中心貨物充足?，F(xiàn)有Mi，j∈M個客戶需要服務，i，j=0時表示城市配送中心，且客戶i的需求量g、客戶規(guī)定的時間窗et，lt、城市配送中心與各顧客之間距離d（直線距離）均已知。配送車輛未在時間窗內(nèi)送達將受到相應的懲罰，懲罰成本與該客戶的配送費用成正相關。通過合理的調(diào)度方案使得城市配送車輛平均配送時間和配送成本達到帕累托最優(yōu)。

成本：H為車輛k的固定使用成本;f為每升油的燃燒成本（L/元）;p為向客戶收取的貨物單位重量運費（t/千元）;C為總配送車輛的固定成本;C為總運輸費用，其跟運輸距離有關;C為總超出時間窗懲罰成本;C為總配送成本;C為最大預計消耗的配送成本。

時間：t為配送車輛k到達客戶i的時間，t為配送車輛k從城市配送中心出發(fā)的時間;u為單位貨物卸貨所需時間

（t/h）;t為車輛k從客戶i到客戶j所用時間;T為完成本次配送任務配送車輛平均所用時間;T為每輛配送車平均最大預計消耗的配送時間。

車輛載重及油耗：g為車輛k從客戶i到客戶j配送中的載貨重量;O為車輛k從客戶i到客戶j配送中的單位距離耗油量（km/L），與車輛當前承載重量有關;O為車輛空載時的單位距離耗油量;O為車輛滿載時車輛自重和最大承載重量的單位距離耗油量。

權(quán)重：u為提前到達的時間懲罰權(quán)重;u為延后到達的時間懲罰權(quán)重;u為時間系數(shù)，配送中心可根據(jù)顧客對時間的重視程度分配相應的權(quán)重;u為成本系數(shù)，配送中心可根據(jù)顧客對成本的重視程度分配相應的權(quán)重。

決策變量：x表示車輛k是否從客戶i到客戶j，如果是，則為1，否為0;y表示車輛k是否到客戶i，如果是，則為1，否為0。

1.2? 基本假設

考慮到現(xiàn)實情況，針對城市配送車輛配送環(huán)境做出如下假設：

（1）只有一個城市配送中心，城市配送中心不會出現(xiàn)缺貨;

（2）所有客戶所需的商品均由城市配送中心供給，客戶之間不存在相互調(diào)配的情況;

（3）配送車輛的起點和終點均為城市配送中心;

（4）車輛在配送時路況穩(wěn)定，不會出現(xiàn)擁堵情況，車輛勻速行駛，行駛速度為v;

（5）各客戶的需求量確定并且保持穩(wěn)定不會變動;

（6）一輛車可以配送多個客戶，但一個客戶只能由一輛車提供服務，顧客的需求必須滿足;

（7）單位距離油費與車輛當前載重呈線性關系。

1.3? 構(gòu)建多目標VRPTW數(shù)學模型

minZ=u+u????????????????????????????????????????? （1）

s.t.

G≥gy， k∈K???????????????????????????????????????????? （2）

T=lt-et， i=0??????????????????????????????????????????????? （3）

T≥T????????????????????????????????????????????????????? （4）

C∑gp， i∈M?????????????????????????????????????????????? （5）

C≥C??????????????????????????????????? ??????????????????（6）

C=H+Ofdx+pgymaxet-t-ug， 0u+maxt-lt， 0u， j≠i???????????? （7）

T=+， j≠i??????????????????????????????? （8）

C=H?????????????????????????????????????????????? （9）

C=Ofdx， j≠i????????????????????????????????????? （10）

O=O-O+O， i，j∈M， j≠i， k∈K???????????????????????????????? （11）

g=gy-gy， k∈K?????????????????????????????????????? （12）

C=pgymaxet-t-ug， 0u+maxt-lt， 0u????????????????????????? （13）

t=maxet， t+ugy+xt， j∈M， i≠j， k∈K???????????????????????????? （14）

t≤lt， i=0， k∈K????????????????????????????????????????? （15）

t=， i，j∈M， j≠i??????????????? ?????????????????????????（16）

x=1， j∈M， j≠i?????????????????????????????????????? （17）

y=1， j∈M， j≠0???????????????????????????????????????? （18）

x=x， j=0， k∈K?????????????????????????????????????? （19）

式（1）表示總目標函數(shù)，為城市配送車輛平均配送時間和配送總成本在無量綱化后加權(quán)之和最小;式（2）表示每次配送中心給車輛安排的配送貨物重量不能超過車輛的最大載重量;式（3）表示平均最大預計消耗的配送時間由城市配送中心提供服務的時間區(qū)間決定;式（4）表示實際消耗的平均配送時間不能大于平均最大預計消耗的配送時間;式（5）表示最大預計消耗的配送費用等于配送所獲得的收入;式（6）表示實際消耗的配送總成本不能大于配送所獲得的收入;式（7）表示配送總成本，由總配送車輛固定使用費用、總運輸費用、總超出時間窗懲罰費用組成;式（8）表示平均配送時間;式（9）表示總配送車輛固定使用費用，包括所有使用車輛及其配送貨物的保險費用、車輛的維護、司機的工資、路橋費等;式（10）表示總運輸費用及完成所有配送任務后，配送車輛所產(chǎn)生的燃油費;式（11）表示配送車輛的單位距離耗油量，與車輛當前載貨重量成正相關;式（12）表示配送車輛當前載貨重量，及該配送車輛從配送中心出發(fā)時的載貨重量減去已經(jīng)完成配送的客戶需求總和;式（13）表示總超出時間窗懲罰費用，在車輛配送過程中，如果提前到達客戶點可先進行卸貨再計算等待時間，且不考慮“配送車輛到達客戶點未超出客戶時間窗，但加上卸貨時間超過客戶時間窗，因而索賠客戶超出時間窗的卸貨時間的懲罰費用”的情況;式（14）表示配送車輛到達客戶點的時間，配送車輛只能在客戶時間窗內(nèi)進行交付行為，即如果配送車輛到達客戶點并完成卸貨，依舊未達到客戶起始服務時間，必須等到客戶起始服務時間后才能前往下一個客戶點;式（15）表示配送車輛完成配送任務返回城市配送中心的時間不能大于城市配送中心提供服務的終點時刻;式（16）表示配送車輛從一個客戶點到另一個客戶點勻速行駛所耗時間;式（17）每一位客戶都需要被服務;式（18）表示一位客戶只由一輛配送車提供服務;式（19）表示配送車輛從配送中心發(fā)出，完成配送任務后返回配送中心。

2? 算法設計

2.1? 遺傳算法改進思路

本文基于標準遺傳算法，通過模仿人工培育豌豆的過程，對遺傳算法進行一定改進，基本思路如下：

步驟1：在初始種群設計和適應度計算間和變異完成后加入篩選環(huán)節(jié)，及將含需求基因的豌豆挑選出來進行培育;

步驟2：在適應度計算和選擇之間加入擇優(yōu)環(huán)節(jié)，將優(yōu)秀的個體進行自花授粉，將次優(yōu)的個體異花傳粉，將劣勢的個體淘汰;

步驟3：讓初始種群數(shù)作為環(huán)境最大容納量，這樣更容易觀察種群平均適應度的變化情況;

步驟4：適當?shù)馗倪M了初始種群設計和選擇、交叉算子使其更加符合實際情況。

2.2? 改進的遺傳算法實現(xiàn)步驟

（1）編碼方式。本文采用十進制編碼方式，城市配送中心使用k輛大小型號一致的配送車輛為N個客戶配送貨物。其中配送中心用0表示，客戶點用1，2，3，…，N表示。由于配送車輛是同一時間為每個客戶配送貨物且一次完成，所以配送車輛數(shù)量決定配送子路徑的數(shù)量，因此一條染色體的長度為K+N+1，例如一條染色體的編碼為“0 5 6 0 10 8 4 0 2 1 9 7 0 3 0”，表示4輛配送車輛同時為10個客戶點配送貨物，配送子路徑：

0→5→6→0，0→10→8→4→0，0→2→1→9→7→0，0→3→0

（2）初始種群設計。產(chǎn)生初始種群數(shù)POP *客戶數(shù)M的矩陣，矩陣的每一行都是1到M的隨機不重復的數(shù)字，其中POP也是該種群的環(huán)境最大容納量。計算每一輛車的預計承重量G， G≤G， G=∑g/K/Φ2， Φ2=0.9544，再將客戶點的矩陣轉(zhuǎn)換為客戶點需求矩陣，然后在矩陣的每一行中從左到右累加得到S， x∈M， S=0，x表示列數(shù)，S表示0到x列客戶需求量之和。當時，S=S-S，并在x列和x+1列間插0。

（3）種群篩選算子。對插0后的矩陣，進行每一條染色體中每一輛車貨物載重量Gk∈K的統(tǒng)計，其中G=S，一旦一條染色體中出現(xiàn)貨物載重量大于車輛最大承重量時，及G？酆G時，刪除該染色體。

（4）適應度計算。在遺傳算法中，適應度的高低決定了種群中個體性能的優(yōu)劣，一般情況下，適應度越大的個體其性能越優(yōu)秀。本文將目標函數(shù)Z的倒數(shù)作為適應度，及第y行染色體的適應度f=， y∈YS，YS表示經(jīng)過種群篩選后的染色體的數(shù)量。

（5）擇優(yōu)算子。通過模擬人工培養(yǎng)豌豆授粉的過程，將優(yōu)秀的個體進行自花授粉，將次優(yōu)的個體異花傳粉，將劣勢的個體淘汰。將已經(jīng)按適應度從大到小的順序排列好的矩陣，選出排在矩陣前面5%的染色體作為自交個體，將剩余的染色體進入選擇階段。自交個體自交生成2倍于自身數(shù)量的個體，直接進入變異階段。生成2倍于自身數(shù)量的個體是為了減少變異對優(yōu)秀基因的損壞，盡可能的保護優(yōu)秀基因。

（6）選擇算子。輪盤賭法是一個十分實用的選擇方法，但這種方法存在選擇概率高的個體被多次選出的情況，這可能較大的削減了種群的規(guī)模，降低了種群的多樣性，陷入局部最優(yōu)的可能性較大。因此本文將在輪盤賭法的基礎上進行改進，即第y條染色體被選出進入交叉階段的概率為：

P=， y∈YX????????????????????????????????????? （20）

YX表示進入選擇階段染色體的數(shù)量，ci表示當前染色體被重復選中的總次數(shù)，例如：在第y條染色體前，只有第r條染色體被選中2次和第q條染色體被選中3次，此時ci=3; r，q∈YX。然后生成一個0到1的隨機數(shù)？鄣，當P？芻？鄣≤P時，染色體y被選中。此時染色體再次被選中的概率為：

P=P-， P≥0，當P？芻0時，P=0???????? ?????????????????（21）

其中：等式右邊的P表示染色體y前一次被選中的概率，f表示所有進入選擇階段中的染色體最大的適應度，表示所有進入選擇階段中的染色體平均適應度。然后執(zhí)行H次輪盤操作，并將其中重復的染色體除去重復部分。

H=YX/P， P=1-?????????????????????????????????? （22）

其中：P表示適應度最大值到平均適應度的染色體數(shù)量占進入交叉階段染色體數(shù)量的比例。

（7）交叉算子。由于種群篩選步驟的篩選力度較大，一旦染色體出現(xiàn)超載情況，就會被刪除，所以采用一種盡量避免超載的交叉方案。步驟如下：

步驟1：將符合交叉概率p的隨機父代1和父代2中，從父代1隨機選出一輛車的行駛路徑作為交叉片段（不包括0）;

步驟2：找出父代2中對應父代1交叉片段的編號順序，作為父代2的交叉片段;

步驟3：將父代1的交叉片段與父代2的交叉片段進行互換，生成子代1和子代2;

步驟4：重復步驟1到3，直到生成YB條染色體停止交叉，YB=P-2*5%*YS， P表示環(huán)境最大容納量，YS表示經(jīng)過種群篩選后的染色體的數(shù)量。交叉操作、交叉結(jié)果具體過程圖3所示。

（8）變異算子。在染色體滿足變異概率p時，從2，N+K中隨機選出兩個不相同且不為0的數(shù)字，將數(shù)字對應的染色體基因碼進行互換，生成新的染色體。變異具體過程圖4所示。

（9）種群篩選算子。將完成變異的矩陣轉(zhuǎn)換為客戶點需求矩陣，在對每一條染色體的每一輛車貨物載重量Gk=1，2，3，…，K進行統(tǒng)計，一旦一條染色體中出現(xiàn)貨物載重量大于車輛最大承重量時，即G？酆G時，刪除該染色體。

3? 實驗結(jié)果與分析

3.1? 實驗數(shù)據(jù)

一個城市配送中心為20個客戶提供配送服務，配送車輛最大載重為2t，車輛配送行駛平均速度為40km/h，車輛固定租賃費用為500元，油費為7元/L，每噸貨物卸貨時間為0.001kg/h，重量的運費為1元/kg，車輛空載時耗油量為1L/km，車輛滿載時耗油量為2L/km，超出時間窗懲罰系數(shù)為0.3，提前時間窗懲罰系數(shù)為0.1。配送中心和客戶點的坐標、客戶需求量、服務客戶的時間窗如表1所示。

改進遺傳算法參數(shù)設定：種群規(guī)模為1 000，迭代次數(shù)為1 000，擇優(yōu)概率為0.05，變異概率為0.1。

3.2? 實驗結(jié)果

本實驗采用MATLAB R2015（b）實現(xiàn)，在Intel（R）Core（TM）i5-6 200U CPU 2.4GHz，內(nèi)存8G的電腦上重復運行多次。種群內(nèi)個體適應度整體進化過程如圖5所示，由適應度最大值進化曲線發(fā)現(xiàn)種群最佳適應度在150代之前增長迅速，在200代左右趨近于穩(wěn)定。由適應度平均進化曲線發(fā)現(xiàn)在150代內(nèi)適應度平均值穩(wěn)步上升并在250代后趨近于穩(wěn)定并略低于適應度最大值。隨著種群的迭代總成本和總時間的變化曲線如圖6所示。

如圖7和圖8所示，使用改進遺傳算法和標準遺傳算法同時解決上述問題時。改進后的遺傳算法收斂速度明顯增快并且能優(yōu)化整個種群平均適應度以避免局部最優(yōu);相比標準遺傳算法在解決上述問題時則容易陷入局部最優(yōu)導致不能得到最優(yōu)解。

圖9和圖10分別表示改進遺傳算法和標準遺傳算法解決上述問題時的最優(yōu)車輛路徑。

表2和表3分別表示標準遺傳算法和改進遺傳算法解決上述問題的最終數(shù)據(jù)結(jié)果，分析表明標準遺傳算法在解決多目標問題上不能同時兼顧路徑長度、時間和懲罰成本，在數(shù)據(jù)方面有比較大的波動。改進后的遺傳算法對路徑長度、時間和懲罰成本同時進行優(yōu)化，數(shù)據(jù)趨于穩(wěn)定。

通過對標準遺傳算法和改進遺傳算法相比，如表4所示。可以發(fā)現(xiàn)，改進遺傳算法在解決算例中20位客戶配送問題時要比標準遺傳算法具有更強的尋優(yōu)能力，可以達到同時對行駛距離、時間和成本優(yōu)化的目的。

計算結(jié)果分析表明相比標準遺傳算法，改進后的遺傳算法在車輛行駛距離節(jié)約14.2%，時間節(jié)約6%，成本節(jié)約6.3%，總利潤增加7.9%。綜上所述，改進后的遺傳算法在解決城市配送多目標優(yōu)化問題上有一定的優(yōu)勢。

4? 結(jié)束語

本文針對城市配送問題，通過建立多目標VRPTW模型，考慮車輛載重限制，對時間、成本這兩個目標同時進行優(yōu)化求解。針對標準遺傳算法在解決大規(guī)模VRPTW問題時容易陷入局部最優(yōu)，通過加入種群篩選和擇優(yōu)兩個算子加大了遺傳算法的尋優(yōu)力度;改進的選擇算子在選擇出優(yōu)秀個體的同時，也保證了父代規(guī)模;改進交叉方式在盡量避免超載的同時，又保證了種群多樣性避免出現(xiàn)局部最優(yōu)。最后通過對比實驗結(jié)果驗證改進后的遺傳算法具有更強的尋優(yōu)能力，可以有效地解決大規(guī)模VRPTW問題。但本文未考慮“雙11”、“618”等重要電商節(jié)日時出現(xiàn)客戶數(shù)量和配送量劇增的現(xiàn)實情況，后續(xù)的研究中會加以改進。

參考文獻：

[1] 吳聰，陳侃松，姚靜. 基于改進自適應遺傳算法的物流配送路徑優(yōu)化研究[J]. 計算機測量與控制，2018，26（2）：236-240.

[2] 羅勇，陳治亞. 基于改進遺傳算法的物流配送路徑優(yōu)化[J]. 系統(tǒng)工程，2012，30（8）：118-122.

[3]? Esam T Y， Masri A， et al. An Adaptive Hybrid Algorithm for Vehicle Routing Problems with Time Windows[J]. Computers and Industrial Engineering， 2017（113）：382-391.

[4] 申艷光，張玲玉，劉永紅. 基于混合遺傳算法的物流路徑優(yōu)化方法研究[J]. 計算機技術與發(fā)展，2018，28（3）：192-196.

[5] 胡鐘駿，周泓. 改進遺傳算法的需求可拆分車輛路徑優(yōu)化研究[J]. 計算機仿真，2018，25（3）：80-83.

[6] 金仙力，李金剛. 基于遺傳算法的多目標路徑優(yōu)化算法的研究[J]. 計算機技術與發(fā)展，2018，28（2）：54-58.

[7] 葛顯龍，譚柏川，吳寧謙. 基于碳交易機制的帶時間窗車輛路徑問題與算法研究[J]. 管理工程學報，2018，32（4）：141-148.

[8]? Ahmed F， Deb K. Multi-objective Optimal Path Planning Using Elitist Non-dominated Sorting Genetic Algorithms[J]. Soft Computing， 2013，17（SI）：1283-1299.

[9] 曹倩，邵舉平，孫延安. 基于改進遺傳算法的生鮮農(nóng)產(chǎn)品多目標配送路徑優(yōu)化[J]. 工業(yè)工程，2015，18（1）：71-76.

[10] 劉瀾，吳金卓，胡鴻. 交通限制和軟時間窗條件下的車輛路徑問題及其蟻群算法改進[J]. 物流科技，2016，35（9）：92-96.

[11] 周蓉，沈維蕾，劉明周，等. 帶時間窗裝卸一體化車輛路徑問題的混合離散粒子群優(yōu)化算法[J]. 中國機械工程，2016，27（4）：495-502.

[12] 侯玉梅，賈震環(huán)，田歆，等. 帶軟時間窗整車物流配送路徑優(yōu)化研究[J]. 系統(tǒng)工程學報，2015，30（2）：240-249.

[13]? DUYGU T， OLA J， TOM V W. A Vehicle Routing Problem with Flexible Time Windows[J]. Computers and Operations Research， 2014，52：39-54.