城市物資配送路徑尋優(yōu)的算法比較

潘帥

摘 要：本文圍繞物資運(yùn)送至城市到達(dá)站后選擇何種路線對配送點(diǎn)進(jìn)行配送的問題展開討論。首先，在平面直角坐標(biāo)系中，確定配送點(diǎn)的位置坐標(biāo)，然后通過建立最短巡回徑路模型，設(shè)計(jì)遺傳算法與蟻群算法分別對數(shù)值實(shí)例進(jìn)行求解，得到最短巡回徑路，最后比較這兩種算法對尋求最短巡回徑路問題的求解質(zhì)量與收斂速度。

關(guān)鍵詞：物資配送；平面直角坐標(biāo)系；最短巡回徑路；遺傳算法；蟻群算法

中圖分類號：O224；TP301.6 文獻(xiàn)標(biāo)識碼：A 文章編號：1003-5168（2018）16-0127-04

Comparison of Algorithms for Optimizing Urban Material Distribution Path

PAN Shuai

Abstract： This paper focused on material transportation to choose what route to reach the station delivery point for distribution. First， in the plane right angle coordinate system， the location coordinates of the distribution point were determined， and then the shortest circuit path model was established. The genetic algorithm and the ant colony algorithm were designed to solve the numerical example， and the shortest path was obtained. Finally， the quality and convergence speed of the two algorithms for finding the shortest routing problem were compared.

Keywords： material distribution；planar rectangular coordinate system；shortest tour path；genetic algorithm；ant colony optimization

隨著國家產(chǎn)業(yè)結(jié)構(gòu)調(diào)整的深化與電子商務(wù)的發(fā)展，我國貨源結(jié)構(gòu)發(fā)生了巨大變化。近年來，物資配送的市場份額逐年上升，究其根源，是電子產(chǎn)品、工業(yè)配件、食品、日用品等高附加價值的貨物需求迅猛增加。以蘭州為例，中鐵快運(yùn)股份有限公司的城市到達(dá)站有蘭州站、蘭州西站和中鐵蘭州物流中心等，所有到站貨物進(jìn)行分撥，配送至各配送點(diǎn)，如蘭州西固營業(yè)部、蘭州西站高鐵營業(yè)部、蘭州分公司和蘭州站營業(yè)部等。

眾所周知，地球是一個不規(guī)則的球體，將位于球面的形狀顯示在平面的顯示器上就必然需要一個投影過程，投影之后的坐標(biāo)（用X和Y描述）用于在平面上標(biāo)識POI（POI是“Point of Interest”的縮寫，中文可以翻譯為“興趣點(diǎn)”）[1]。在百度地圖API中，通過經(jīng)度（Longitude）與緯度（Latitude）描述地球上的某個位置，用BMap.MercatorProjection類來完成經(jīng)緯度與平面坐標(biāo)互相轉(zhuǎn)換的計(jì)算。其中，經(jīng)緯度的原點(diǎn)和平面坐標(biāo)系的原點(diǎn)一致，即0°經(jīng)線和地球赤道相交的位置[2]。本文是基于以上方法得出配送點(diǎn)相對于城市到達(dá)站的坐標(biāo)。

1 配送車最短巡回路的問題描述

為了方便尋求最短配送徑路，筆者對所研究問題作出以下假設(shè)：物資運(yùn)送至城市到達(dá)站后，這批物資的體積重量小于等于1輛貨車的標(biāo)準(zhǔn)載重，已知n個需要進(jìn)行配送任務(wù)的配送點(diǎn)相對城市到達(dá)站的平面坐標(biāo)為[xi，yi]，其中，[i=1，2，3，…，n]。此問題的目標(biāo)函數(shù)：配送人員選擇最短的巡回徑路，降低運(yùn)輸成本，保證物資全部送到配送點(diǎn)處[2]。據(jù)此建立數(shù)學(xué)模型。

2 配送車最短巡回路問題的數(shù)學(xué)模型

2.1 貨郎擔(dān)問題

設(shè)有[n]個地點(diǎn)，用[1，2，3，…，n]表示。[Dij]表示由i地至j地的距離。一位銷售員從地點(diǎn)1出發(fā)，然后到剩下的每個地點(diǎn)一次，最后回到地點(diǎn)1。那么其選擇何種行走徑路，能使總線路最短？貨郎擔(dān)問題（Traveling SalespersonProblem）是一種組合最優(yōu)化的問題，其特點(diǎn)是方便描述，但難以解決[4]。

假設(shè)銷售員是從地點(diǎn)1開始出發(fā)的。設(shè)銷售員走到地點(diǎn)i，記為[Ni2，3，…，i-1，i+1，…，n]，表示由地點(diǎn)1到地點(diǎn)i之間中間地點(diǎn)的集合。

[S]表示到達(dá)地點(diǎn)i之前中途所經(jīng)過的地點(diǎn)的集合，則[S?Ni]。

設(shè)[i，S]作為表示過程的狀態(tài)變量。決策為由一個地點(diǎn)到另外一個地點(diǎn)，并定義最優(yōu)值函數(shù)[fki，S]為從地點(diǎn)1開始出發(fā)，經(jīng)由[k]個中間地點(diǎn)的[S]集到地點(diǎn)i的最短徑路距離。故遞推公式為：

[fii，S=minfk-1j，S?j+dji] （1）

其中，[j∈s]，[k=1，2，3，…，n-1]，[i=2，3，…，n]，[S?Ni]。

邊界條件是[f0i，?=d1i]。

[Pk（i，S）]是最優(yōu)決策函數(shù)，表示從地點(diǎn)1出發(fā)，遍歷k個中間地點(diǎn)的[S]集至地點(diǎn)[i]的最短徑路中臨近[i]地前面的地點(diǎn)[5]。

2.2 最短巡回徑路問題的平面坐標(biāo)模型

假設(shè)有[n]個配送點(diǎn)，由集合[R=ri|ri=i，i=1，2，3，…，n]表示[6]。一輛貨車從城市到達(dá)站送往每個配送點(diǎn)處，待配送完畢后再返回。用平面直角坐標(biāo)系來表示點(diǎn)位，將n個配送點(diǎn)所在坐標(biāo)置于直角坐標(biāo)系中，定義決策向量[x]和y分別描述這n個配送點(diǎn)的坐標(biāo)：

[x=xi|xi∈R；i=1，2，3，…，ny=yi|yi∈R；i=1，2，3，…，n] （2）

其中，對于所有的，j有[xi≠xj且yi≠yj]。此外，為構(gòu)造數(shù)學(xué)模型方便，設(shè)以下變量：

[Qij=1， 車輛線路要經(jīng)過i，j0， 車輛線路不經(jīng)過i，j] （3）

則可以得到車輛配送優(yōu)化的數(shù)學(xué)模型。

①車輛總的走行距離[7]：

[minW=i=0nj=0nCijQij ] （4）

②約束條件[8]：

[i=0nQij=1i=1，2，3，…，n （5）]

[j=0nQij=1j=1，2，3，…，n （6）]

[ Cij=xi-xj2+yi-yj212i≠j] （7）

[Qij∈（0，1） （8）]

式中：[W]表示遍歷n個配送點(diǎn)最短巡回徑路的距離；[Cij]表示從配送點(diǎn)i到配送點(diǎn)j的距離。

3 算法模型介紹

3.1 遺傳算法

遺傳算法（Genetic Algorithms）是從一個初始群體出發(fā)，來模擬生物進(jìn)化過程，采用復(fù)制、交叉和變異等手段，在原有基因的基礎(chǔ)上，產(chǎn)生具有更好性能指標(biāo)的下一代解的集合，不斷重復(fù)迭代，直到找到滿意解或者最優(yōu)解為止[9]。求解方法如下[10]。

①先確定遺傳操作的代數(shù)k與種群規(guī)模n，然后設(shè)置初試代數(shù)k=1，使用隨機(jī)數(shù)法產(chǎn)生n個初始可行解[Xi（1≤i≤n，k=1）]組成初始解群體。

②對當(dāng)代群體中的所有個體[xik]，分別計(jì)算適應(yīng)度[fXik]。

③while（！終止條件）；對于任意個體[Xik]，計(jì)算其生存概率[Pik：]

[Pik=fXik/fXik] （9）

根據(jù)[Pik]的大小，在群體中優(yōu)良的個體進(jìn)行遺傳操作，包括運(yùn)用復(fù)制、交叉和變異等手段得到新一代的解集合，然后使[k=k+1]，轉(zhuǎn)到第②步。

④若滿足條件，結(jié)束操作即可。

3.2 蟻群算法

蟻群算法（ant colony optimization）是模擬螞蟻覓食的過程來對目標(biāo)進(jìn)行搜索，根據(jù)留在徑路上的信息素濃度的高低，按概率選擇接下來將到的地點(diǎn)[11]。徑路上信息素的濃度越高，螞蟻選擇這條徑路的概率就越大。求解方法如下[12]。

①一共m只螞蟻，隨機(jī)放在n個地點(diǎn)中，將第k只螞蟻的禁忌表tabuk的第一個元素設(shè)置為螞蟻k所在的地點(diǎn)，接下來選擇地點(diǎn)表allowedk設(shè)置為除當(dāng)前其所在地點(diǎn)之外的任意地點(diǎn)，設(shè)置各個徑路上的信息素矩陣[m，n]。②每只螞蟻依照各條徑路上的信息素量高低，兩地之間的距離和其他相關(guān)參數(shù)選擇下一個地點(diǎn)。t時刻，螞蟻k在地點(diǎn)i上選擇地點(diǎn)j的概率[Pkij（t）]為：

[Pkijt=ταijtηβijts?allowedkταistηβist ， j∈allowedk 0 ，j∈allowedk] （10）

其中，[α]表征表示信息素重要程度的參數(shù)；[allowedk]表示螞蟻k接下來要經(jīng)過沒有走過的地點(diǎn)；[β]表征啟發(fā)式因子重要程度的參數(shù)，即兩個地點(diǎn)距離的相對重要程度。

如果[allowedk]為0，那么表示完成一次旅行[13]。

③螞蟻選擇一次遍歷的徑路。

m只螞蟻完成一次游歷后，則各條徑路上的信息素濃度依照下式更新：

[τijt+n=ρ?τijt+?τij] （11）

[?τkij=QLi，第k只螞蟻在這次循環(huán)中經(jīng)過ij邊0，第k只螞蟻在這次循環(huán)中沒過ij邊 （12）]

[ ?τij=k=1m?τkij （13）]

其中，[ρ]為信息素的蒸發(fā)系數(shù)，[Li]為本次循環(huán)經(jīng)過路線的長度，Q為信息素增強(qiáng)系數(shù)。

4 數(shù)值實(shí)例

設(shè)某城市到達(dá)站的貨物，由一輛貨車配送到15個配送點(diǎn)處，各位置點(diǎn)處位置平面坐標(biāo)如表1所示。若尋求最短巡回徑路，降低配送成本，完成運(yùn)輸服務(wù)，求最佳配送徑路。

4.1 試驗(yàn)硬件、軟件環(huán)境

試驗(yàn)使用聯(lián)想M40（14-inch）型計(jì)算機(jī)，處理器為2.6GHz Intel（R）Core（TM）i5，內(nèi)存為4GB DDR3，操作系統(tǒng)為Windows7旗艦版，MATLAB版本為R2017a[14]。

4.2 數(shù)據(jù)結(jié)果對比

在遺傳算法中，采用個體編碼方式為實(shí)數(shù)編碼，初始化的遺傳參數(shù)設(shè)置為：初試種群大小為30，染色體基因個數(shù)為16，群體進(jìn)化次數(shù)為400代（即迭代次數(shù)），交叉率為0.8，變異率為0.2，使用基于適應(yīng)度比例的選擇策略，即適應(yīng)度越好的個體被選中的概率越大，且保存適應(yīng)度最高的個體[15]；在蟻群算法中，設(shè)置初試的參數(shù)為：螞蟻總數(shù)是30只，信息素重要程度設(shè)置為1，最大迭代次數(shù)為400代，信息素蒸發(fā)系數(shù)為1，信息素增強(qiáng)系數(shù)為100[16]。

兩種算法結(jié)果對比如表2所示[17]。

兩種算法的最短巡回徑路圖與收斂曲線圖如圖1和圖2所示。

5 結(jié)語

遺傳算法與蟻群算法都是新型的模擬進(jìn)化算法。遺傳算法的特點(diǎn)是操作簡單，使用方便，全局搜索能力強(qiáng)，但容易過早收斂，費(fèi)時且在進(jìn)化后期搜索效率較低；蟻群算法是一種正向反饋的方法，促進(jìn)整個求解過程向著最優(yōu)方向前進(jìn)，具有較強(qiáng)的魯棒性。由以上對比可知，蟻群算法對城市物資配送路徑尋優(yōu)問題的求解質(zhì)量更高，收斂速度更快。

參考文獻(xiàn)：

[1]楊浩.鐵路運(yùn)輸組織學(xué)[M].北京：中國鐵道出版社，2001.

[2]汝宜紅.物流學(xué)導(dǎo)論[M].北京：清華大學(xué)出版社，2010.

[3]高自友，孫會君.現(xiàn)代物流與交通運(yùn)輸系統(tǒng)[M].北京：人民交通出版社，2003.

[4]徐帆.鐵路快捷貨物門到門運(yùn)輸組織研究[M].成都：西南交通大學(xué)，2015.

[5]徐天亮.運(yùn)輸與配送[M].北京：物質(zhì)出版社，2012.

[6]燕忠.基于蟻群優(yōu)化算法的若干問題的研究[D].南京：東南大學(xué)，2005.

[7]侯文靜，馬永杰.求解TSP的改進(jìn)蟻群算法[J].計(jì)算機(jī)應(yīng)用研究，2010（6）：2087-2089.

[8]王銀年.遺傳算法的研究與應(yīng)用[D].無錫：江南大學(xué)，2009.

[9]吳慶洪，張穎，馬宗民.蟻群算法綜述[J].微計(jì)算機(jī)信息，2011（3）：1-2.

[10]劉利強(qiáng)，戴運(yùn)桃，王麗華.蟻群算法參數(shù)優(yōu)化[J].計(jì)算機(jī)工程，2008（11）：208-210.

[11]王超學(xué)，崔杜武，王竹榮，等.一種求解TSP的高效遺傳算法[J].西安理工大學(xué)學(xué)報，2006（1）：37-41.

[12]王連山.關(guān)于遺傳、蟻群、禁忌搜索算法的比較[J].電腦編程技巧與維護(hù)，2009（24）：18-21.

[13]楚艷娟.基于定位路徑問題的配送網(wǎng)絡(luò)規(guī)劃研究[D].濟(jì)南：山東大學(xué)，2008.

[14]梁棟，洪雁.我國鐵路快捷貨運(yùn)產(chǎn)品設(shè)計(jì)及組織優(yōu)化的探討[J].鐵道經(jīng)濟(jì)研究，2013（2）：15-19.

[15]王涵.物流企業(yè)配送網(wǎng)絡(luò)區(qū)域劃分研究[D].成都：西南交通大學(xué)，2012.

[16]陳俊勇.中國現(xiàn)代大地基準(zhǔn)——中國大地坐標(biāo)系統(tǒng)2000（CGCS2000）及其框架[J].測繪學(xué)報，2008（3）：269-271.

[17]邊少鋒，柴洪洲，金際航.大地坐標(biāo)系與大地基準(zhǔn)[M].北京：國防工業(yè)出版社，2005.