基于改進(jìn)遺傳算法的末端共同配送車輛路徑優(yōu)化

彭會(huì)萍,李士偉,孫宏進(jìn),曹曉軍

(蘭州財(cái)經(jīng)大學(xué) 絲綢之路經(jīng)濟(jì)研究院,蘭州 730020)

城市快遞配送網(wǎng)絡(luò)的運(yùn)行模式較為單一,物流配送企業(yè)普遍通過劃分包括城市轉(zhuǎn)運(yùn)中心、區(qū)域配送中心、末端配送網(wǎng)點(diǎn)等不同的物流節(jié)點(diǎn)等級(jí)進(jìn)行包裹的運(yùn)輸、配送以及攬收服務(wù).在末端配送網(wǎng)點(diǎn)進(jìn)行配送服務(wù)時(shí)由于配送地址較分散等問題,使得末端配送成本占物流企業(yè)總成本比例較高.隨著電子商務(wù)的發(fā)展,末端配送包裹數(shù)量激增為末端配送網(wǎng)點(diǎn)帶來了較大壓力,城市末端物流共同配送策略研究具有較高應(yīng)用價(jià)值.商務(wù)部、交通運(yùn)輸部等部門多次發(fā)文,要求大中城市積極推進(jìn)城市共同配送[1],近年來共享經(jīng)濟(jì)的思想深入各行各業(yè),共同配送是物流配送行業(yè)的發(fā)展趨勢(shì),在資源共享的基礎(chǔ)上對(duì)車輛行駛路線進(jìn)行合理規(guī)劃,是企業(yè)降低物流成本、提高企業(yè)效益的關(guān)鍵.

在城市末端共同配送方面,提出合理的共同配送策略,科學(xué)調(diào)配車輛進(jìn)行包裹配送,合理的利潤分配和責(zé)任承擔(dān)是需要深入考慮并解決的問題,國內(nèi)外學(xué)者對(duì)共同配送的研究重點(diǎn)各有側(cè)重.王勇等[2]提出充電站和電動(dòng)車共享策略并設(shè)計(jì)3D-K-means時(shí)空聚類算法和多目標(biāo)粒子群算法進(jìn)行求解,其研究方法與結(jié)論對(duì)為多中心共同配送問題提供新思路.孔繼利等[3]在末端共同配送背景下,以快遞共配聯(lián)盟為研究對(duì)象建立相關(guān)定價(jià)博弈模型為共同配送企業(yè)進(jìn)行最佳決策提供理論依據(jù).孫榮庭[4]分析了生鮮農(nóng)產(chǎn)品在實(shí)施共同配送時(shí)面對(duì)的問題,提出了對(duì)應(yīng)的解決策略.李珍萍等[5]通過對(duì)比奶制品企業(yè)進(jìn)行共同配送前后花費(fèi)的成本,驗(yàn)證所其提出的共同配送策略的可行性及設(shè)計(jì)的算法對(duì)共同配送網(wǎng)絡(luò)優(yōu)化的有效性.任騰等[6]設(shè)計(jì)改進(jìn)遺傳算法求解共同配送路徑問題,發(fā)現(xiàn)共同配送能有效提升客戶的滿意度及降低配送車輛的空載率.WANG等[7]設(shè)計(jì)了一種改進(jìn)遺傳算法求解客戶需求拆分以及時(shí)間窗約束下的多倉庫共同接送車輛路徑問題.許茂增等[8]構(gòu)建了Shapley值綜合修正模型用于解決快遞企業(yè)在低配送密度區(qū)域中轉(zhuǎn)站共同配送問題.陸華等[9]從城市視角出發(fā),對(duì)比實(shí)施共同配送前后的城市交通、貨運(yùn)系統(tǒng)的效益變化,驗(yàn)證了共同配送是治理城市的有效途徑.付朝暉等[10]證明了共享物流模式能更合理規(guī)劃車輛路徑,有效避免交叉配送與迂回運(yùn)輸?shù)炔缓侠憩F(xiàn)象.

綜上所述,目前國內(nèi)外學(xué)者已經(jīng)分別對(duì)多配送中心共同配送車輛路徑問題進(jìn)行了分析與研究,并提出了較多求解算法,但在城市區(qū)域配送下的電商訂單涉及到多家物流配送企業(yè)的共同配送的研究較少.此外,共同配送的路徑優(yōu)化問題所處的環(huán)境較為復(fù)雜,考慮的約束比普通的車輛路徑問題更多.本文通過構(gòu)建以車輛固定使用成本、車輛行駛成本和碳排放成本最小為目標(biāo)的數(shù)學(xué)模型,設(shè)計(jì)引入節(jié)約里程算法的遺傳算法進(jìn)行該模型求解,通過仿真實(shí)驗(yàn)證明改進(jìn)的算法的有效性及共同配送策略的優(yōu)越性.

1 共同配送車輛路徑問題建模

1.1 問題描述與假設(shè)

若干物流配送企業(yè)決定在城市某區(qū)域?qū)嵭心┒斯餐渌?將參與共同配送的各個(gè)企業(yè)末端配送網(wǎng)點(diǎn)相互共享.在進(jìn)行“最后一公里”的配送時(shí),參與共同配送企業(yè)的末端配送網(wǎng)點(diǎn)作為公共末端配送網(wǎng)點(diǎn),各企業(yè)的配送中心可將包裹送往任意公共末端配送網(wǎng)點(diǎn),再由公共末端配送網(wǎng)點(diǎn)對(duì)經(jīng)過K-means聚類后的新服務(wù)區(qū)域安排車輛路線執(zhí)行配送任務(wù).各個(gè)客戶需求點(diǎn)末端配送網(wǎng)點(diǎn)位置與每一個(gè)客戶需求點(diǎn)都只能由一輛車服務(wù)一次,各客戶需求點(diǎn)的需求量己知,各末端配送網(wǎng)點(diǎn)的坐標(biāo)已知且能夠滿足服務(wù)對(duì)象的需求.為便于分析和研究,做出以下假設(shè):

1) 快遞均為經(jīng)過折算后的標(biāo)準(zhǔn)快遞.

2) 未成功配送的快遞不考慮重新配送.

3) 某城市區(qū)域內(nèi)有多個(gè)末端配送網(wǎng)點(diǎn)且擁有充足的配送車輛.

4) 末端配送服務(wù)車輛具有容量限制.

5) 考慮為服務(wù)對(duì)象的收貨需求,暫不考慮寄件需求.

6) 每個(gè)客戶的收貨需求量小于車輛容量.

7) 每個(gè)客戶只能由一輛車提供配送服務(wù).

8) 獨(dú)立配送情形下給客戶的貨物由該客戶歸屬的末端配送網(wǎng)點(diǎn)進(jìn)行貨物配送服務(wù),共同配送情形下由公共末端配送網(wǎng)點(diǎn)進(jìn)行貨物配送服務(wù).

9) 車輛自末端配送網(wǎng)點(diǎn)出發(fā),完成配送任務(wù)后回到原末端配送網(wǎng)點(diǎn).

1.2 模型構(gòu)建

所建模型的變量、集合以及決策變量的定義見表1.

表1 變量符號(hào)及其含義

車輛固定使用成本主要與車輛使用數(shù)目有關(guān),車輛固定使用成本C1定義如下:

C1=kf

(1)

配送車輛在向客戶運(yùn)送包裹的過程中,會(huì)產(chǎn)生油耗成本和保養(yǎng)費(fèi)、折舊費(fèi)等,將車輛運(yùn)送過程中的成本稱作行駛成本.利用負(fù)載估計(jì)法測(cè)算油耗量[11],油耗主要與車輛載重和行駛距離有關(guān)[12],保養(yǎng)費(fèi)、折舊費(fèi)等費(fèi)用主要和行駛距離有關(guān).

單位距離油耗函數(shù)為:

(2)

其中:p0為車輛空載時(shí)單位距離油耗,p*為滿載時(shí)單位距離油耗,Z為車輛自重,X為當(dāng)前車輛載重量.

車輛行駛成本C2定義如下:

(3)

車輛運(yùn)輸過程中燃燒燃料產(chǎn)生二氧化碳,根據(jù)我國碳稅制度對(duì)碳排放成本估算,碳稅成本公式如下:

Cost=碳稅*碳排放量

(4)

碳排放成本C3定義如下:

(5)

基于總配送成本最小化為目標(biāo)建立的共同配送模型如下:

式(1)為目標(biāo)函數(shù)式,計(jì)算最小化的總配送費(fèi)用,包括車輛固定成本C1和車輛行駛成本C2以及碳排放成本C3.

(6)

(7)

(8)

i,j不同時(shí)為0

(9)

(10)

(11)

xij∈{0,1},i,j∈A

(12)

K∈{1,2…,n,…}

(13)

(14)

2 改進(jìn)遺傳算法設(shè)計(jì)

2.1 車輛路徑的編碼與解碼

針對(duì)于車輛路徑問題采取順序?qū)崝?shù)編碼方式,無需進(jìn)行解碼,可以直接得到染色體對(duì)應(yīng)的車輛路線.染色體序列取決于末端配送網(wǎng)點(diǎn)與客戶的服務(wù)先后順序,基因值是末端配送網(wǎng)點(diǎn)編號(hào)和客戶編號(hào),基因數(shù)是末端配送網(wǎng)點(diǎn)數(shù)與客戶數(shù)之和.假設(shè)有8個(gè)客戶,2個(gè)末端配送網(wǎng)點(diǎn),對(duì)其進(jìn)行編碼,1-2編碼設(shè)為車場, 3-10編碼為客戶,一條完整的染色體長度應(yīng)為10,如下所示:

1 4 7 10 3 9 2 6 5 8

該染色體對(duì)應(yīng)的車輛路徑問題即為1號(hào)末端網(wǎng)點(diǎn)按照4-7-10-3-9的順序?yàn)榭蛻舴?wù),2號(hào)車場按照6-5-8的順序?yàn)榭蛻舴?wù).

2.2 種群初始化

初始種群的生成方式以及生成質(zhì)量對(duì)于最終的結(jié)果有重要影響,良好的初始種群可加快算法收斂速度,更高效地獲得最優(yōu)解.若初始種群的大小為M,將節(jié)約里程算法得到的解復(fù)制為M份作為遺傳算法初始解.

2.3 適應(yīng)度函數(shù)

在生物學(xué)中使用適應(yīng)度這個(gè)概念來衡量生物對(duì)于所處環(huán)境的適應(yīng)程度,與此相同在遺傳算法中也通過適應(yīng)度來衡量種群中個(gè)體的優(yōu)劣,個(gè)體的適應(yīng)度值就代表了個(gè)體的適應(yīng)能力,適應(yīng)度函數(shù)通常由目標(biāo)函數(shù)來決定,較大的適應(yīng)度說明該個(gè)體較優(yōu),可以進(jìn)入下一代子種群[13].本文模型中目標(biāo)函數(shù)為配送總成本最小,如式(6)所示,因此適應(yīng)度函數(shù)為應(yīng)取配送總成本的倒數(shù),具體表達(dá)式為:

(15)

2.4 遺傳算子策略選取

1)選擇算子.利用輪盤賭法在當(dāng)前種群中選出部分個(gè)體作為產(chǎn)生子代的父代,對(duì)各個(gè)染色體的個(gè)體適應(yīng)度值進(jìn)行計(jì)算,適應(yīng)度高的個(gè)體被優(yōu)先進(jìn)行選擇并保存進(jìn)下一代.

2)交叉算子.對(duì)種群進(jìn)行選擇操作后隨機(jī)設(shè)置交叉點(diǎn)的位置,交換配對(duì)染色體之間的部分基因.例如染色體上某兩個(gè)基因片段為:

父代個(gè)體1: 1-8-19-6-2-1

父代個(gè)體2: 2-5-10-11-2

交叉后:

父代個(gè)體1: 1-8-10-11-2-1

父代個(gè)體2: 2-5-19-6-2

3)變異算子.變異是指種群中的染色體在進(jìn)行復(fù)制時(shí)有概率使得這一過程中發(fā)生變化,例如染色體上某基因片段為:

個(gè)體i: 2-4-9-8-2

變異后

個(gè)體i*: 2-17-9-8-2

改進(jìn)后算法的流程見圖1.

圖1 CW-GA流程圖

3 算例與結(jié)果分析

3.1 算法驗(yàn)證

為驗(yàn)證設(shè)計(jì)的CW-GA算法的有效性,使用Python對(duì)Solomon數(shù)據(jù)集中的R101算例進(jìn)行仿真實(shí)驗(yàn),算法參數(shù)如下:初始種群M=500,迭代次數(shù)500,變異概率設(shè)為0.1,交叉概率設(shè)為0.8.GA算法與CW-GA的迭代曲線見圖2.對(duì)比圖中算法的迭代結(jié)果可以看出,設(shè)計(jì)的CW-GA算法的收斂速度和最終結(jié)果明顯優(yōu)于傳統(tǒng)GA算法.從迭代曲線的變化趨勢(shì)對(duì)比分析,CW-GA算法在迭代初期迅速找到最優(yōu)解,在迭代100次左右趨于收斂;而傳統(tǒng)GA算法在算法終止后未找到優(yōu)秀解,在迭代過程一直處于波動(dòng)狀態(tài).收斂速度較慢且收斂結(jié)果較差.CW-GA迭代500次找到的解為1 514.79,傳統(tǒng)GA的解為2054.46.兩者差距較大.說明所設(shè)計(jì)的算法在求解性能上較優(yōu).

圖2 目標(biāo)值迭代圖

3.2 仿真實(shí)驗(yàn)

為驗(yàn)證提出的共同配送方案有效性進(jìn)行實(shí)例仿真.某區(qū)域有兩家物流公司四個(gè)末端配送網(wǎng)點(diǎn),分別向20個(gè)客戶需求點(diǎn)進(jìn)行電商產(chǎn)品訂單配送.兩個(gè)物流公司的客戶高度重疊.末端配送網(wǎng)點(diǎn)坐標(biāo)與各客戶節(jié)點(diǎn)的坐標(biāo)、需求量見表2、3.

表2 配送網(wǎng)點(diǎn)坐標(biāo)

表3 客戶信息表

利用上文設(shè)計(jì)的遺傳算法進(jìn)行模型求解,算法參數(shù)設(shè)置:種群規(guī)模為500,設(shè)置終止條件為迭代500次后停止,染色體變異、交叉概率設(shè)為0.1和0.8,仿真實(shí)驗(yàn)參數(shù)設(shè)置見表4.

表4 仿真實(shí)驗(yàn)參數(shù)設(shè)置

3.3 結(jié)果分析

利用所設(shè)計(jì)的CWGA算法求解獨(dú)立配送策略,仿真得到的A、B企業(yè)獨(dú)立配送最優(yōu)配送車輛路徑結(jié)果見圖3.

圖3 A、B獨(dú)立配送車輛路徑

利用K-means聚類算法根據(jù)客戶到末端配送網(wǎng)點(diǎn)的距離進(jìn)行客戶歸屬劃分,劃分結(jié)果見圖4(A).選擇距離聚類中心較近的末端配送網(wǎng)點(diǎn)作為該聚類客戶的末端配送網(wǎng)點(diǎn),在考慮聚類的基礎(chǔ)上利用改進(jìn)后遺傳算法求得共同配送車輛路徑結(jié)果見圖4.仿真結(jié)果中獨(dú)立配送和共同配送方案所用配送車輛路徑信息見表5.共同配送前后成本變化見表6.

圖4 基于客戶聚類的A、B共同配送車輛路徑

表5 配送車輛路徑

表6 共同配送前后成本變化

通過表5可知,共同配送之后使用的車輛數(shù)量并未減少,因共同配送需要滿足A、B客戶的需求,每輛車的服務(wù)客戶數(shù)量降低,可以更快地完成配送任務(wù)減少后續(xù)客戶等待時(shí)間,且客戶能夠同時(shí)取得A、B企業(yè)需配送的貨物,方便用戶取件,對(duì)配送企業(yè)而言更容易協(xié)調(diào)滿足不同客戶的時(shí)間窗要求.

從表6可以看出, 共同配送總成本相比獨(dú)立配送時(shí)總成本節(jié)約了854.08元,其優(yōu)化比率為26.13%,車輛行駛成本優(yōu)化比率高達(dá)37.00%.碳排放成本優(yōu)化比率為36.98%.此外,從圖5可知,共同配送后的車輛的油耗以及配送行駛距離也有大幅度降低.只有車輛使用成本在共同配送前后未發(fā)生變化.說明共同配送可以有效優(yōu)化車輛行駛成本和碳排放成本,降低物流配送企業(yè)的運(yùn)營成本.

圖5 獨(dú)立配送與共同配送差別

4 結(jié) 語

本文對(duì)城市末端共同配送進(jìn)行分析,在基于物流企業(yè)末端網(wǎng)點(diǎn)共享的基礎(chǔ)上,構(gòu)建以包括車輛使用成本、運(yùn)輸成本和碳排放成本最小化為目標(biāo)的共同配送車輛路徑問題模型.設(shè)計(jì)一種基于節(jié)約里程算法的遺傳算法進(jìn)行模型的求解,采用節(jié)約里程算法的解作為遺傳算法的初始解,有效提高了初始解的質(zhì)量,并通過公開的數(shù)據(jù)集算例驗(yàn)證了算法的有效性;在成本對(duì)比分析中,根據(jù)現(xiàn)實(shí)生活中包裹配送情況建立的共同配送模型求解得到的物流總成本花費(fèi)有大幅下降,將該策略大規(guī)模應(yīng)用到現(xiàn)實(shí)生活可幫助企業(yè)實(shí)現(xiàn)降本增效.