基于改進遺傳算法的末端共同配送車輛路徑優化

彭會萍,李士偉,孫宏進,曹曉軍

(蘭州財經大學 絲綢之路經濟研究院,蘭州 730020)

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

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

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

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

1.1 問題描述與假設

若干物流配送企業決定在城市某區域實行末端共同配送,將參與共同配送的各個企業末端配送網點相互共享.在進行“最后一公里”的配送時,參與共同配送企業的末端配送網點作為公共末端配送網點,各企業的配送中心可將包裹送往任意公共末端配送網點,再由公共末端配送網點對經過K-means聚類后的新服務區域安排車輛路線執行配送任務.各個客戶需求點末端配送網點位置與每一個客戶需求點都只能由一輛車服務一次,各客戶需求點的需求量己知,各末端配送網點的坐標已知且能夠滿足服務對象的需求.為便于分析和研究,做出以下假設:

1) 快遞均為經過折算后的標準快遞.

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

3) 某城市區域內有多個末端配送網點且擁有充足的配送車輛.

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

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

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

7) 每個客戶只能由一輛車提供配送服務.

8) 獨立配送情形下給客戶的貨物由該客戶歸屬的末端配送網點進行貨物配送服務,共同配送情形下由公共末端配送網點進行貨物配送服務.

9) 車輛自末端配送網點出發,完成配送任務后回到原末端配送網點.

1.2 模型構建

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

表1 變量符號及其含義

車輛固定使用成本主要與車輛使用數目有關,車輛固定使用成本C1定義如下:

C1=kf

(1)

配送車輛在向客戶運送包裹的過程中,會產生油耗成本和保養費、折舊費等,將車輛運送過程中的成本稱作行駛成本.利用負載估計法測算油耗量[11],油耗主要與車輛載重和行駛距離有關[12],保養費、折舊費等費用主要和行駛距離有關.

單位距離油耗函數為:

(2)

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

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

(3)

車輛運輸過程中燃燒燃料產生二氧化碳,根據我國碳稅制度對碳排放成本估算,碳稅成本公式如下:

Cost=碳稅*碳排放量

(4)

碳排放成本C3定義如下:

(5)

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

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

(6)

(7)

(8)

i,j不同時為0

(9)

(10)

(11)

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

(12)

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

(13)

(14)

2 改進遺傳算法設計

2.1 車輛路徑的編碼與解碼

針對于車輛路徑問題采取順序實數編碼方式,無需進行解碼,可以直接得到染色體對應的車輛路線.染色體序列取決于末端配送網點與客戶的服務先后順序,基因值是末端配送網點編號和客戶編號,基因數是末端配送網點數與客戶數之和.假設有8個客戶,2個末端配送網點,對其進行編碼,1-2編碼設為車場, 3-10編碼為客戶,一條完整的染色體長度應為10,如下所示:

1 4 7 10 3 9 2 6 5 8

該染色體對應的車輛路徑問題即為1號末端網點按照4-7-10-3-9的順序為客戶服務,2號車場按照6-5-8的順序為客戶服務.

2.2 種群初始化

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

2.3 適應度函數

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

(15)

2.4 遺傳算子策略選取

1)選擇算子.利用輪盤賭法在當前種群中選出部分個體作為產生子代的父代,對各個染色體的個體適應度值進行計算,適應度高的個體被優先進行選擇并保存進下一代.

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

父代個體1: 1-8-19-6-2-1

父代個體2: 2-5-10-11-2

交叉后:

父代個體1: 1-8-10-11-2-1

父代個體2: 2-5-19-6-2

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

個體i: 2-4-9-8-2

變異后

個體i*: 2-17-9-8-2

改進后算法的流程見圖1.

圖1 CW-GA流程圖

3 算例與結果分析

3.1 算法驗證

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

圖2 目標值迭代圖

3.2 仿真實驗

為驗證提出的共同配送方案有效性進行實例仿真.某區域有兩家物流公司四個末端配送網點,分別向20個客戶需求點進行電商產品訂單配送.兩個物流公司的客戶高度重疊.末端配送網點坐標與各客戶節點的坐標、需求量見表2、3.

表2 配送網點坐標

表3 客戶信息表

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

表4 仿真實驗參數設置

3.3 結果分析

利用所設計的CWGA算法求解獨立配送策略,仿真得到的A、B企業獨立配送最優配送車輛路徑結果見圖3.

圖3 A、B獨立配送車輛路徑

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

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

表5 配送車輛路徑

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

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

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

圖5 獨立配送與共同配送差別

4 結 語

本文對城市末端共同配送進行分析,在基于物流企業末端網點共享的基礎上,構建以包括車輛使用成本、運輸成本和碳排放成本最小化為目標的共同配送車輛路徑問題模型.設計一種基于節約里程算法的遺傳算法進行模型的求解,采用節約里程算法的解作為遺傳算法的初始解,有效提高了初始解的質量,并通過公開的數據集算例驗證了算法的有效性;在成本對比分析中,根據現實生活中包裹配送情況建立的共同配送模型求解得到的物流總成本花費有大幅下降,將該策略大規模應用到現實生活可幫助企業實現降本增效.