王建玲，齊紫茜，何 璐

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

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

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

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

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

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

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

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

式中:Δτ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ì)算釋放的信息素濃度，及螞蟻經(jīng)過的路徑越短，釋放的信息素濃度越高，其Δτij的計(jì)算式如下:

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

2 數(shù)值仿真

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

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

圖1 某配送站需配送地點(diǎn)詳圖

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

圖2 蟻群算法原理步驟

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

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

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

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

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

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

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

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

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

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

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

當(dāng)采取3輛車的配送方式，系統(tǒng)將配送點(diǎn)分為三個(gè)部分，進(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é) 語

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

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

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

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

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

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

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

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