王建玲，齊紫茜，何 璐

（上海海洋大學(xué) 工程學(xué)院，上海201306）

隨著運輸?shù)陌l(fā)展，物資的流通從單一的車輛配送運輸發(fā)展到了大規(guī)模的車輛配送系統(tǒng)，將多個車輛多個需求地點放在一個系統(tǒng)中進(jìn)行考慮，確定車輛的運輸線路。車輛調(diào)度問題實質(zhì)上是個復(fù)雜的組織優(yōu)化問題，求解的基本方法可分為精確算法和啟發(fā)式法兩大類:精確算法指可以精確地求出最優(yōu)解的算法，計算量隨著問題規(guī)模的增大呈指數(shù)增長，因此其實際應(yīng)用范圍受到了一定的限制，所以專家們主要研究的是高質(zhì)量的啟發(fā)式算法，目前的主要算法有粒子群算法、蟻群算法等。

本文采用基于模型的預(yù)先優(yōu)化法，根據(jù)配送中心和多個配送點，使用螞蟻算法，用matlab軟件仿真出最短路徑。運送時，配送車輛可以根據(jù)預(yù)先優(yōu)化的最短路徑進(jìn)行無返回一站式運輸；并且可以根據(jù)當(dāng)時的路況信息和配送貨物量自動選擇車輛進(jìn)行區(qū)域式的運輸方式，實現(xiàn)車輛動態(tài)調(diào)度。

1 車輛調(diào)度數(shù)學(xué)模型的建立

不失一般性，設(shè)整個蟻群中的螞蟻數(shù)量為m，所需訪問的配送點的數(shù)量為n，城市i與城市j之間的距離為dij（i，j＝1，2，…，n），在t時刻配送點i和配送點j連接路徑上的信息素濃度為τij（t）。初始時刻，各個城市間連接路徑上的信息素濃度相同，不妨設(shè)τij（t）＝0。

螞蟻k（k＝1，2，…，m）根據(jù)各個城市間連接路徑上的信息素濃度決定選擇下一步要轉(zhuǎn)移的配送點，設(shè)為t時刻螞蟻k從配送點i轉(zhuǎn)移到城市j的概率，其計算式為

式中:ηij（t）為啟發(fā)函數(shù)，ηij＝1／dij為螞蟻從配送點i轉(zhuǎn)移到配送點j的期望程度。allowedk（k＝1，2，…，m）為螞蟻k下一步被允許訪問的配送點的集合，參數(shù)m即為蟻群系統(tǒng)中螞蟻的數(shù)量，文中，令它等于配送地點的數(shù)量。開始時，allowedk中有（n－1）個元素，即包括除了螞蟻k出發(fā)的配送點的其他所有配送點，隨著時間的推進(jìn)，allowedk中的元素不斷減少，直至為空，即表示所有城市均訪問完畢。信息啟發(fā)因子α代表螞蟻在運動過程中積累的信息素，α取值范圍為1～2.5，系統(tǒng)中α取值為1。期望啟發(fā)因子β表達(dá)了螞蟻在選擇路徑時相對重要程度，β一般取值范圍為1.5～5，系統(tǒng)中β的取值為5。

在螞蟻釋放信息素的同時，為了不讓螞蟻選擇已經(jīng)訪問過的城市，采用禁忌表來記錄螞蟻k當(dāng)前所走過的城市，各個城市間連接路徑上的信息素逐漸消失。經(jīng)過t時刻，所有螞蟻都完成一次周游，計算每只螞蟻所走過的路徑長度，并保存最短的路徑長度，同時，更新各邊上的信息素。運算式為

式中:Δτkij為第k只螞蟻在城市i與城市j連接路徑上釋放信息素濃度；Δτij為所有螞蟻在城市i與城市j連接路徑上釋放的信息素和濃度之和。參數(shù)p反映了路徑信息素的衰減系數(shù)（亦揮發(fā)系數(shù)和蒸發(fā)系數(shù)），而1－p則反映了信息的殘留量，及持久性系數(shù)。信息殘留因子的最佳值應(yīng)該處于0.4～1.0，本系統(tǒng)中p值取0.5。

針對螞蟻釋放信息素問題，一般選用Antcycle System模型計算釋放的信息素濃度，及螞蟻經(jīng)過的路徑越短，釋放的信息素濃度越高，其Δτij的計算式如下:

式中:Q為常數(shù)，表示螞蟻循環(huán)一次所釋放的信息素總量，即信息素釋放強度，在本文系統(tǒng)中，Q＝100；Lk為第k只螞蟻經(jīng)過路徑的長度。

2 數(shù)值仿真

如圖1為某配送站需配送地點詳圖，配送中心位于坐標(biāo)星號處，橫坐標(biāo)向東為正，縱坐標(biāo)向南為負(fù)，而各數(shù)字所標(biāo)明的地點為22個配送地點，配送中心為配送地編號1，該配送中心坐標(biāo)為（390，－265），各配送地點坐標(biāo)如表1所示，坐標(biāo)原點如圖1所示。

基于蟻群算法原理，解決上述問題一般需要以下幾個步驟，如圖2所示。

圖1 某配送站需配送地點詳圖

表1 各配送地點坐標(biāo)

圖2 蟻群算法原理步驟

1）初始化各參數(shù)。計算時，需要對相關(guān)的參數(shù)進(jìn)行初始化，如果蟻群的規(guī)模（螞蟻數(shù)量）m、信息素重要程度因子α、啟發(fā)函數(shù)重要程度因子β、信息素?fù)]發(fā)因子p、信息素釋放總量Q、最大迭代次數(shù)和迭代次數(shù)初值。

2）構(gòu)建解空間。將各個螞蟻放置于不同出發(fā)點，對每個螞蟻k（k＝1，2，…，m），按照第一個概率函數(shù)計算其下一個待訪問的配送點，直到所有螞蟻訪問完所有配送點。

3）記錄本次迭代最佳路徑。

4）計算各個螞蟻經(jīng)過的路徑長度Lk（k＝1，2，…，m），記錄當(dāng)前迭代次數(shù)中的最優(yōu)解，即是所求的最短路徑。

5）根據(jù)信息素濃度更新Δτkij計算式。

6）判斷是否終止。若iter＜iter＿max，令iter＝iter＋1，清空螞蟻經(jīng)過的記錄表，并返回步驟2）；否則，終止計算。

7）結(jié)果輸出與結(jié)果分析。用一輛車進(jìn)行配送，根據(jù)現(xiàn)實環(huán)境，會出現(xiàn)路況堵塞或是配送量較大等情況。當(dāng)路況堵塞時，排在后面的配送點不能夠及時收到貨物，或是配送量較大時，一輛貨車不能夠裝載足夠的貨物。這里，需要采用3輛車的配送方式。

運用上述運算方法進(jìn)行多輛車分區(qū)域路徑優(yōu)化，各個螞蟻仍然均以配送中心為起始點進(jìn)行最短路徑迭代。為了更直觀的對結(jié)果進(jìn)行觀察和分析，以圖形的形式將最短路徑的配送順序顯示出來。如圖3所示，3輛車配送的路徑優(yōu)化，如圖4所示，3輛車各自的最短路程和平均路徑。

圖3 3輛車配送最短路徑仿真示意

圖4 3輛車配送最短路徑與平均路徑示意

由仿真線路圖和最短路徑迭代顯示來看:

當(dāng)采取3輛車的配送方式，系統(tǒng)將配送點分為三個部分，進(jìn)行分區(qū)域的3輛車的配送方式。

第1輛車的配送路線為:配送地1→配送地5→配送地6→ 配送地7→ 配送地8→配送地4→ 配送地2→ 配送地3→ 配送地9→ 配送地1。

配送的最短距離為:970.286 1km

第2輛車的配送路線為:配送地1→ 配送地14→ 配送地10→ 配送地11→ 配送地12→ 配送地13→ 配送地20→ 配送地15→ 配送地1。

配送的最短距離為:950.456 0km

第3輛車的配送路線為:配送地1→ 配送地16→ 配送地17→ 配送地18→ 配送地23→ 配送地22→ 配送地21→ 配送地19→ 配送地1。

配送的最短距離為:761.726 4km

所以，兩輛車配送最短路徑總長度為2.682 5×103km。

3 結(jié) 語

本文采用無返回式的一站式運輸，保證最短路徑的同時，大大提高了運輸效率，節(jié)約了運輸時間和運輸成本。并且根據(jù)路況信息，選擇多輛車的分區(qū)域運輸方式，完成動態(tài)調(diào)度，在保證路況信息的同時，更合理地完成配送。

［1］吳斌，倪衛(wèi)紅，樊樹海等.放式動態(tài)網(wǎng)絡(luò)車輛路徑問題的粒子 群 算 法 ［J］.計 算 機 集 成 制 造 系 統(tǒng)，2009，15:1788－1794.

［2］段海濱.蟻群原理算法及其應(yīng)用［M］.北京:科學(xué)出版社，2005:12－35.

［3］馬良，朱剛，寧愛兵.蟻群優(yōu)化算法［M］.北京:科學(xué)出版社，2008:2.

［4］吳斌，邵建峰，方葉祥，等.基于客戶滿意度的開放式車輛路徑 問 題 研 究 ［J］.計 算 機 工 程，2009，35（17）:193－194，197.

［5］劉冉，江志斌，耿娜，劉天堂.半開放式多車場車輛路徑問題［J］.上海交通大學(xué)學(xué)報，2010（11）:1539－1545.

［6］王洪雪，雷黎黎.集裝箱堆場箱位最優(yōu)分配［J］.交通科技與經(jīng)濟，2013，15（1）:50－53.

［7］周佳，沈巖，夏宇，等.智能交通最短路徑Dijkstra模糊動態(tài)方法分析［J］.交通科技與經(jīng)濟，2014，16（4）:9－12.