基于改進(jìn)遺傳算法的連鎖便利店配送路徑優(yōu)化研究

魏子秋，熊英翔 WEI Ziqiu,XIONG Yingxiang

（河北科技大學(xué) 經(jīng)濟(jì)管理學(xué)院，河北 石家莊 050000）

0 引 言

隨著社會(huì)經(jīng)濟(jì)的不斷發(fā)展和社會(huì)分工的不斷細(xì)化，使得物流業(yè)快速發(fā)展，但是物流成本沒(méi)有得到顯著降低，物流業(yè)中的高消耗、高成本一直是有待解決的問(wèn)題。其中運(yùn)輸費(fèi)用在物流費(fèi)用中的占比接近半成，是物流活動(dòng)中的最主要費(fèi)用。所以想要推動(dòng)物流業(yè)的持續(xù)發(fā)展，務(wù)必要降低物流活動(dòng)中的成本費(fèi)用，降低物流成本費(fèi)用應(yīng)首先從降低運(yùn)輸費(fèi)用開(kāi)始。

配送路徑的選擇直接決定著運(yùn)輸成本和效率，對(duì)配送路徑及其算法進(jìn)行優(yōu)化研究具有重要的意義和價(jià)值。李作山等學(xué)者結(jié)合遺傳算法，針對(duì)企業(yè)車(chē)輛調(diào)度優(yōu)化進(jìn)行研究，基于減少汽車(chē)運(yùn)行耗費(fèi)為目的提出了相關(guān)策略。劉建仁等為了解決城市物流配送路徑規(guī)劃過(guò)程中存在的一些難題，以獲得更優(yōu)的城市物流配送路徑規(guī)劃結(jié)果，在已有的算法基礎(chǔ)上，引入交通擁堵條件，提出考慮交通擁堵的城市物流配送路徑規(guī)劃算法，建立更優(yōu)的城市物流配送路徑規(guī)劃數(shù)學(xué)模型；張瑾等為了解決帶有容量和軟時(shí)間窗約束的雙目標(biāo)生鮮農(nóng)產(chǎn)品冷鏈物流車(chē)輛路徑問(wèn)題，建立了以客戶(hù)滿(mǎn)意度最大化、總成本最小化為目標(biāo)的雙目標(biāo)優(yōu)化模型，在求解過(guò)程中，以蟻群算法為基礎(chǔ)，運(yùn)用ε約束法來(lái)處理雙目標(biāo)模型，并且加入交叉與變異算子，設(shè)計(jì)了遺傳蟻群算法。季琳琳等提出以成本與滿(mǎn)意度為雙目標(biāo)的冷鏈水果運(yùn)輸模型。為了準(zhǔn)確描述顧客滿(mǎn)意度水平，提高冷鏈水果運(yùn)輸服務(wù)的響應(yīng)能力，提出改進(jìn)的滿(mǎn)意度模型；引入灰度白化權(quán)函數(shù)構(gòu)造顧客滿(mǎn)意度不同等級(jí)階段，設(shè)置不同等級(jí)分?jǐn)?shù)將影響滿(mǎn)意度感知的因素劃分成不同等級(jí)，利用調(diào)研數(shù)據(jù)支撐顧客真實(shí)滿(mǎn)意度感知；提出改進(jìn)的遺傳算法（IGA）求解該冷鏈水果運(yùn)輸模型。張肖琳等充分考慮耗油成本、綠色環(huán)保成本，將綠色物流與配送的路徑優(yōu)化結(jié)合起來(lái)，基于綠色環(huán)保視角，通過(guò)在物流配送中引入油耗、污染物排放等因素，構(gòu)建出配送路徑優(yōu)化模型。李丹蓮等為解決單車(chē)場(chǎng)多車(chē)型帶密集半軟時(shí)間窗問(wèn)題，討論解決方案預(yù)防其陷入局部最優(yōu)解，提出多染色體改進(jìn)遺傳算法在減少車(chē)輛運(yùn)輸成本、懲罰成本的目標(biāo)下進(jìn)行最優(yōu)路徑求解；彭勇等為解決帶有時(shí)刻表和時(shí)間窗的雙重約束多式聯(lián)運(yùn)的路徑優(yōu)化問(wèn)題，將運(yùn)輸總成本分解為運(yùn)輸成本和中轉(zhuǎn)成本，建立以總成本最小化為目標(biāo)的數(shù)學(xué)模型，使用蟻群算法對(duì)模型進(jìn)行求解，并在多式聯(lián)運(yùn)網(wǎng)絡(luò)節(jié)點(diǎn)編碼方式和狀態(tài)轉(zhuǎn)移概率公式兩個(gè)方面進(jìn)行了針對(duì)性改進(jìn)；沈麗等綜合考慮貨損成本、固定成本、燃油成本以及碳排放成本和時(shí)間懲罰成本，以其和最小為目標(biāo)，細(xì)化貨損和碳排放來(lái)源，構(gòu)建生鮮產(chǎn)品配送路徑優(yōu)化模型；潘世凌等使用節(jié)約里程法對(duì)成都蘇寧小店的配送路徑進(jìn)行優(yōu)化，求解出最優(yōu)的配送路線(xiàn)，降低物流成本。

目前各位學(xué)者對(duì)遺傳算法解決物流配送路徑方面的研究已取得一定的成果，但是針對(duì)有較強(qiáng)的送貨時(shí)間窗限制的零售小店的配送路徑優(yōu)化相對(duì)較少，本文針對(duì)此問(wèn)題進(jìn)行研究。

1 構(gòu)建數(shù)學(xué)模型

1.1 模型描述

本文所研究的連鎖超市配送路徑問(wèn)題可描述為：有一個(gè)配送中心（=0）為個(gè)小店進(jìn)行配送（=1,2,…,），需要輛配送車(chē)才能完成配送任務(wù)。為方便建立數(shù)學(xué)模型，做出以下假設(shè)：（1）配送活動(dòng)以配送中心為起點(diǎn)，且最終要返回配送中心；（2）配送車(chē)輛額定載重量需大于或等于車(chē)輛配送路線(xiàn)上的客戶(hù)需求總量；（3）一位需求客戶(hù)只能被一輛配送車(chē)服務(wù)一次；（4）配送所用的運(yùn)輸車(chē)裝載噸位相同。

再假設(shè)表示總的配送費(fèi)用；C表示運(yùn)輸車(chē)每次運(yùn)輸?shù)膯挝还潭ㄟ\(yùn)輸費(fèi)用；C表示單位變動(dòng)運(yùn)輸費(fèi)用；d表示小店到小店的距離；x表示小店到小店使用配送車(chē)進(jìn)行配送；P、P表示配送車(chē)早到等待成本和晚到懲罰成本；P表示配送車(chē)輛超重懲罰系數(shù)；ET、LT表示小店的最早和最晚到達(dá)時(shí)間；S表示配送車(chē)輛到達(dá)小店的時(shí)間；T表示配送車(chē)到達(dá)小店處的服務(wù)時(shí)間；T表示配送車(chē)從第個(gè)小店到第個(gè)小店的行駛時(shí)間；D表示第個(gè)小店的需求量；表示每輛配送車(chē)最多裝載貨物的數(shù)量。配送的限制條件如下：

配送車(chē)輛不能超載，要小于或等于車(chē)輛的最大裝載量：

配送車(chē)的行駛方向和配送開(kāi)始起點(diǎn)和到達(dá)服務(wù)地點(diǎn)需要具有唯一性：

小店的需求，只能由配送車(chē)輛為其配送：

配送車(chē)到達(dá)小店的時(shí)間窗限制：

配送車(chē)到達(dá)小店的時(shí)間與到達(dá)前一個(gè)小店處的時(shí)間關(guān)系：

決策變量取整數(shù)變量0或1：

在考慮以上假設(shè)和限制條件后下，以總的配送費(fèi)用最小為目標(biāo)建立帶時(shí)間窗的物流配送路徑化模型：

1.2 染色體編碼

由于配送中心要通過(guò)配送車(chē)輛來(lái)向多個(gè)小店配送，因此選擇使用自然數(shù)來(lái)進(jìn)行編碼，以求提高求解過(guò)程中的計(jì)算效率。將配送中心編碼為0，配送的個(gè)小店隨機(jī)編碼為1,2,…,，配送車(chē)完成配送任務(wù)后要回到配送中心，完成一條配送路線(xiàn)即可編碼的染色體長(zhǎng)度是＋＋1。

1.3 初始群體設(shè)定

為了避免可能過(guò)早的陷入局部最優(yōu)解而出現(xiàn)早熟現(xiàn)象，初始群體中設(shè)計(jì)的染色體數(shù)量要足夠的多，而且初始群體應(yīng)該要具有廣泛代表性的特點(diǎn)。因此，配送路徑問(wèn)題的初始種群考慮以配送車(chē)的額定裝載數(shù)量及需求商的需求量表示一組編碼長(zhǎng)度的限制條件，依次表示每輛配送車(chē)配送的需求商編碼，不同配送車(chē)配送的需求商編碼之間用0相連，形成初始染色體。

1.4 適應(yīng)度函數(shù)構(gòu)造

在遺傳算法求解過(guò)程中，為了選擇優(yōu)秀的染色體，需構(gòu)造適應(yīng)度函數(shù)，用來(lái)作為評(píng)判個(gè)體好壞的標(biāo)準(zhǔn)。通過(guò)適應(yīng)度函數(shù)值觀(guān)察，適應(yīng)度函數(shù)值越大，說(shuō)明染色體適應(yīng)度越好，也就代表該染色體越優(yōu)秀，所以該配送方案在實(shí)際需要解決的問(wèn)題中被選擇的概率較大。由于建立的目標(biāo)函數(shù)是求配送費(fèi)用最小，在此采用界限構(gòu)造法來(lái)構(gòu)造適應(yīng)度函數(shù)，適應(yīng)度函數(shù)表示如下，其中是當(dāng)前所有代目標(biāo)函數(shù)（）的最大值。

1.5 遺傳算子設(shè)計(jì)

遺傳算子分別包括選擇、變異和交叉幾種形式，設(shè)計(jì)操作算子可以讓遺傳算法具有強(qiáng)大的搜索功能。在遺傳算法中，通過(guò)計(jì)算過(guò)適應(yīng)度，得出適應(yīng)度函數(shù)值，并選擇其中適應(yīng)度值第一的和第二的個(gè)體進(jìn)入下一代，之后通過(guò)輪盤(pán)賭的方式將適應(yīng)度值排在后面的染色體復(fù)制個(gè)體進(jìn)入下一代，進(jìn)行選擇。這樣可以通過(guò)選擇算子來(lái)篩選出更好的染色體進(jìn)入到下一代中，避免過(guò)早收斂。在選擇操作中將染色體根據(jù)交叉概率進(jìn)行交叉配對(duì)，而適應(yīng)度值排在第一和第二的染色體則不需要。其中的交叉操作考慮采用雙切點(diǎn)交叉方法進(jìn)行。另外，變異操作可以通過(guò)變異令染色體中的基因發(fā)生改變，增加種群的多樣性，是遺傳算法的輔助性操作，可以采用在染色體上隨機(jī)選取兩個(gè)非零的基因進(jìn)行交換位置來(lái)實(shí)現(xiàn)變異。

2 算法實(shí)例

在石家莊范圍內(nèi)的蘇寧小店如今已有100多家門(mén)店，在此只考慮店面規(guī)模較大，每日營(yíng)業(yè)額較高的八家小店。藁城物流配送中心負(fù)責(zé)向石家莊的八家蘇寧小店配送商品。為方便區(qū)分記錄，表示藁城物流配送中心，P表示配送中心周?chē)枰渌偷拈T(mén)店。需求量見(jiàn)表1，車(chē)輛配載量為2t。

表1 石家莊8家蘇寧小店每日需求量及服務(wù)信息

2.1 配送線(xiàn)路管理現(xiàn)狀

蘇寧云商集團(tuán)股份有限公司采用掃描分析法為門(mén)店商品制定配送路線(xiàn)。

根據(jù)表1，假設(shè)直線(xiàn)從開(kāi)始順時(shí)針旋轉(zhuǎn)，計(jì)算如下所示：第一條線(xiàn)路包含的門(mén)店有、、、，車(chē)輛配送量=0.34+0.67+0.52+0.32=1.85t；總運(yùn)輸距離=23.5+3.6+3.3+5.4+27.8=63.6km。第二條線(xiàn)路包含的門(mén)店有、、，車(chē)輛配送量=0.41+0.56+0.71=1.67t；總運(yùn)輸距離=31.5+6+5.1+21.6=64.2km。第三條路線(xiàn)包含的門(mén)店表示，車(chē)輛配送量=0.46t；總運(yùn)輸距離=22.6+22.6=45.2km。

2.2 配送優(yōu)化分析

通過(guò)對(duì)蘇寧小店物流配送現(xiàn)狀的案例分析，得出相關(guān)參數(shù)，如表2所示。

表2 基礎(chǔ)參數(shù)

遺傳算法的相關(guān)參數(shù)表示初始種群規(guī)模為50，時(shí)間窗懲罰系數(shù)P為200，P為200，超重懲罰系數(shù)為15 000，進(jìn)化代數(shù)為600。用MATLAB編程，通過(guò)20次迭代之后，得到最優(yōu)配送路徑，如圖1所示。

圖1 優(yōu)化后配送路線(xiàn)圖

2.3 優(yōu)化前后對(duì)比

本文主要以蘇寧藁城物流配送中心表示研究對(duì)象，實(shí)際情況調(diào)查發(fā)現(xiàn)：滿(mǎn)配載為2t的微型貨車(chē)使用時(shí)的維修資金為15元/d，閑置時(shí)的維修資金為10元/d，其中油耗為1.3L/km，油價(jià)為5.78元/L，每個(gè)送貨司機(jī)的固定工資表示150元/d，配送費(fèi)30元/趟，根據(jù)本文假設(shè)藁城基地負(fù)責(zé)此次配送的微型貨車(chē)有3輛，送貨司機(jī)3名。

涉及成本計(jì)算公式：運(yùn)輸成本=總運(yùn)輸距離×油耗×油價(jià)；

人工成本=司機(jī)固定成本×人數(shù)+配送費(fèi)×路線(xiàn)；

運(yùn)輸車(chē)維修成本=貨車(chē)使用的維修資金×使用的車(chē)輛數(shù)+貨車(chē)閑置時(shí)的維修資金×未使用的車(chē)輛數(shù)（單位：元）。

對(duì)蘇寧小店物流配送路徑基于遺傳算法進(jìn)行優(yōu)化，將優(yōu)化后的結(jié)果與之前的路徑進(jìn)行對(duì)比分析，結(jié)果如表3所示：

表3 優(yōu)化前后對(duì)比

通過(guò)裝載對(duì)比分析，發(fā)現(xiàn)原先蘇寧小店使用的掃描法消耗作業(yè)偏多，不能充分利用車(chē)輛裝載能力，浪費(fèi)較多的人力與物力，最終影響公司的市場(chǎng)競(jìng)爭(zhēng)優(yōu)勢(shì)；通過(guò)運(yùn)輸距離的對(duì)比分析，發(fā)現(xiàn)優(yōu)化前的總運(yùn)輸距離比優(yōu)化后的總運(yùn)輸距離遠(yuǎn)了50.1km，優(yōu)化前配送路線(xiàn)的運(yùn)距過(guò)長(zhǎng)，也會(huì)對(duì)城市的交通增加壓力；通過(guò)優(yōu)化前后的成本分析，發(fā)現(xiàn)優(yōu)化后比優(yōu)化前使用的配送費(fèi)少414.35元作業(yè)成本，且因優(yōu)化后只有兩條配送路線(xiàn)，需要使用的車(chē)輛2輛，司機(jī)2人，剩下一輛微型貨車(chē)和司機(jī)一名，可以作為其他作業(yè)備選資源，也可以進(jìn)行人員裁員與貨車(chē)出租，減少不必要資源占用。

優(yōu)化后發(fā)現(xiàn)在車(chē)輛配載、運(yùn)輸距離和配送成本等方面都有顯著成效，雖然單單考慮遺傳算法在整個(gè)物流配送線(xiàn)路的問(wèn)題上是不全面的，計(jì)算也不是最優(yōu)的路線(xiàn)，但卻是一個(gè)比較合理的路線(xiàn)，能夠在極快的時(shí)間內(nèi)求出一個(gè)比較優(yōu)秀的方案，顯然使用遺傳算法在物流配送路線(xiàn)規(guī)劃上比較經(jīng)濟(jì)，所以建議蘇寧云商集團(tuán)股份有限公司在以后的蘇寧小店物流配送線(xiàn)路規(guī)劃上使用遺傳算法代替目前使用的掃描分析法。

3 總 結(jié)

物流配送路徑優(yōu)化問(wèn)題一直是連鎖超市較為關(guān)注的問(wèn)題，配送路徑是否合理對(duì)連鎖超市物流費(fèi)用及物流服務(wù)質(zhì)量均有很大的影響。本文針對(duì)連鎖超市的特點(diǎn)，建立了帶時(shí)間窗的配送路徑優(yōu)化模型，運(yùn)用改進(jìn)遺傳算法進(jìn)行了配送路徑優(yōu)化求解。實(shí)例應(yīng)用結(jié)果表明，本文所建立的模型和設(shè)計(jì)的求解方法能較好的優(yōu)化配送路徑，為物流決策者提供合理的優(yōu)化方案。