末端配送路徑優(yōu)化研究

劉 培 （河北工業(yè)大學，天津 300400）

電子商務的飛速發(fā)展推動了我國快遞業(yè)的高速發(fā)展，據(jù)國家郵政局發(fā)布的《2017年中國快遞發(fā)展指數(shù)報告》顯示，2017年我國所有電商及物流企業(yè)完成的包裹總量達到400.6億件，同比增長28.1%，2011～2016年，中國快遞行業(yè)業(yè)務總量保持著高速增長的趨勢[1]。包裹量的劇增，給末端配送帶來了挑戰(zhàn)[2]。

1 末端配送路徑優(yōu)化建模

考慮到末端配送車輛存在車載量和行駛里程的約束，建立多約束車輛路徑模型（VRPMC），建立模型前做出如下假設：

（1）快遞員駕駛相同的車輛，且有相同載貨量的限制。

（2）所有車輛滿電下的行駛里程一樣，忽略車輛充電時間。

（3）每個需求點的配送任務必須由一輛車一次性完成。

數(shù)學模型如下：

上述模型中，m為車輛數(shù)，Q為車載量，Dist為最大行駛里程，dij兩點間的距離，xijk為0-1變量，若車輛k從點i到點j，則為1，否則為0，yik：0-1變量，若車輛k服務顧客i，則為1，否則為0。

式（1）表示模型的目標是總行駛路程最短；式（2）表示車輛的載貨量約束：式（3） 表示滿足最大行駛里程約束；式（4）表示每位顧客點的運輸僅由一輛車來完成。

2 改進蟻群算法

針對蟻群算法容易早熟、停滯的情況[3]，引入遺傳算法操作算子進行改進。用這個改進的混合蟻群算法來解決多約束車輛路徑問題。

（1）復制：將復制應用到蟻群算法中，完成一代的搜索之后，把目前父代中最優(yōu)秀的個體復制下來，保存到子代中，這樣優(yōu)秀父代個體的信息素仍然可以積累在子代中。

（2）編碼：編碼是交叉、變異的基礎，所以先對車輛和需求點進行編碼。

（3）交叉：蟻群算法中引入交叉，能夠擴大搜索范圍，防止算法陷入局部最優(yōu)。蟻群算法每次迭代完，對產生的最優(yōu)解和次優(yōu)解進行編碼交叉操作。

（4）變異：變異可增加種群多樣性，也可提升算法效率。應用到蟻群算法中是指在交叉結束后，對種群中最好的個體采取變異操作。

改進后的算法步驟如下：

Step1：算法相關參數(shù)初始化；

Step2：為客戶點及配送網(wǎng)點進行編碼；

Step3：隨機選取一輛車從配送網(wǎng)點出發(fā)，并建立限重、限距存儲器；

Step4：根據(jù)概率及約束條件選擇下一步的地點；選出一輪迭代中距離最短和第二短的路徑，進行交叉、變異、復制，并擇優(yōu)賦給下一輪迭代；

Step5：更新信息素；

Step6：重復step3、step4、step5，進行多次迭代。

3 實例分析

本文以CN企業(yè)上海市的配送任務為例。客戶點的數(shù)據(jù)信息如表1。

表1 客戶點經緯度及需求量

用第2節(jié)建立的模型及算法進行求解，得出的最優(yōu)解為87.991km，共需3輛車，最優(yōu)配送方案為：車輛1：0→6→2→8→10→3→0；車輛 3：0→5→0；車輛 3：0→9→4→7→1→0。

4 結論與展望

本文設計了GA+ACO的混合算法來求解多約束車輛路徑模型。使用matlab軟件運行算法，對模型進行求解，得出了最優(yōu)的車輛配送方案。未來希望將實際的交通狀況考慮進去，如交通擁情況。