田帥輝 歐麗英

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

關(guān)鍵詞：改進(jìn)遺傳算法;時(shí)間窗;多目標(biāo)優(yōu)化;城市配送

中圖分類號(hào)：F272.14??? 文獻(xiàn)標(biāo)識(shí)碼：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? 引? 言

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

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

1? 模型構(gòu)建

1.1? 問(wèn)題描述及符號(hào)說(shuō)明

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

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

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

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

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

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

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

1.2? 基本假設(shè)

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

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

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

（3）配送車輛的起點(diǎn)和終點(diǎn)均為城市配送中心;

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

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

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

（7）單位距離油費(fèi)與車輛當(dāng)前載重呈線性關(guān)系。

1.3? 構(gòu)建多目標(biāo)VRPTW數(shù)學(xué)模型

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

2? 算法設(shè)計(jì)

2.1? 遺傳算法改進(jìn)思路

本文基于標(biāo)準(zhǔn)遺傳算法，通過(guò)模仿人工培育豌豆的過(guò)程，對(duì)遺傳算法進(jìn)行一定改進(jìn)，基本思路如下：

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

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

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

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

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

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

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

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

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

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

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

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

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

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

P=P-， P≥0，當(dāng)P？芻0時(shí)，P=0???????? ?????????????????（21）

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

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

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

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

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

步驟2：找出父代2中對(duì)應(yīng)父代1交叉片段的編號(hào)順序，作為父代2的交叉片段;

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

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

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

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

3? 實(shí)驗(yàn)結(jié)果與分析

3.1? 實(shí)驗(yàn)數(shù)據(jù)

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

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

3.2? 實(shí)驗(yàn)結(jié)果

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

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

圖9和圖10分別表示改進(jìn)遺傳算法和標(biāo)準(zhǔn)遺傳算法解決上述問(wèn)題時(shí)的最優(yōu)車輛路徑。

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

通過(guò)對(duì)標(biāo)準(zhǔn)遺傳算法和改進(jìn)遺傳算法相比，如表4所示?？梢园l(fā)現(xiàn)，改進(jìn)遺傳算法在解決算例中20位客戶配送問(wèn)題時(shí)要比標(biāo)準(zhǔn)遺傳算法具有更強(qiáng)的尋優(yōu)能力，可以達(dá)到同時(shí)對(duì)行駛距離、時(shí)間和成本優(yōu)化的目的。

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

4? 結(jié)束語(yǔ)

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

參考文獻(xiàn)：

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

[2] 羅勇，陳治亞. 基于改進(jìn)遺傳算法的物流配送路徑優(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]. 計(jì)算機(jī)技術(shù)與發(fā)展，2018，28（3）：192-196.

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

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

[7] 葛顯龍，譚柏川，吳寧謙. 基于碳交易機(jī)制的帶時(shí)間窗車輛路徑問(wèn)題與算法研究[J]. 管理工程學(xué)報(bào)，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] 曹倩，邵舉平，孫延安. 基于改進(jìn)遺傳算法的生鮮農(nóng)產(chǎn)品多目標(biāo)配送路徑優(yōu)化[J]. 工業(yè)工程，2015，18（1）：71-76.

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

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

[12] 侯玉梅，賈震環(huán)，田歆，等. 帶軟時(shí)間窗整車物流配送路徑優(yōu)化研究[J]. 系統(tǒng)工程學(xué)報(bào)，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.