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

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

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

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

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

（2）所有車(chē)輛滿(mǎn)電下的行駛里程一樣，忽略車(chē)輛充電時(shí)間。

（3）每個(gè)需求點(diǎn)的配送任務(wù)必須由一輛車(chē)一次性完成。

數(shù)學(xué)模型如下：

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

式（1）表示模型的目標(biāo)是總行駛路程最短；式（2）表示車(chē)輛的載貨量約束：式（3） 表示滿(mǎn)足最大行駛里程約束；式（4）表示每位顧客點(diǎn)的運(yùn)輸僅由一輛車(chē)來(lái)完成。

2 改進(jìn)蟻群算法

針對(duì)蟻群算法容易早熟、停滯的情況[3]，引入遺傳算法操作算子進(jìn)行改進(jìn)。用這個(gè)改進(jìn)的混合蟻群算法來(lái)解決多約束車(chē)輛路徑問(wèn)題。

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

（2）編碼：編碼是交叉、變異的基礎(chǔ)，所以先對(duì)車(chē)輛和需求點(diǎn)進(jìn)行編碼。

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

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

改進(jìn)后的算法步驟如下：

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

Step2：為客戶(hù)點(diǎn)及配送網(wǎng)點(diǎn)進(jìn)行編碼；

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

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

Step5：更新信息素；

Step6：重復(fù)step3、step4、step5，進(jìn)行多次迭代。

3 實(shí)例分析

本文以CN企業(yè)上海市的配送任務(wù)為例?？蛻?hù)點(diǎn)的數(shù)據(jù)信息如表1。

表1 客戶(hù)點(diǎn)經(jīng)緯度及需求量

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

4 結(jié)論與展望

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