基于蟻群算法的車輛調(diào)度問題

1、第 1 6卷第 6期 2 0 1 4 年 1 2月 交 通 科 技 與 經(jīng) 濟(jì) Te c h n o l o g y8 LE c o n o myi nAr e a so fC o mmu n i c a t i o n sVo 1 ． 1 6。 No ． 6De e ．， 2 0 1 4基 于 蟻群 算 法 的 車輛 調(diào) 度 問題 王建玲 ， 齊紫茜 ， 何 璐 ( 上海海洋 大學(xué) 工程學(xué)院 ， 上海 2 0 1 3 0 6 )摘 要

2、 ： 根據(jù)蟻群算法 的基本原理和數(shù)學(xué)模型算法 ， 對(duì) 實(shí)際配送 問題進(jìn)行 分析 ， 給 出解 決方案 。選 用 m a t l a b 軟件對(duì) 實(shí)例進(jìn)行 仿真 ， 仿 真出無返 回式 的配送最短路徑 ； 將最 短路徑進(jìn) 行分 區(qū)域優(yōu)化 ， 實(shí)現(xiàn) 由路 況信息 和實(shí)際需要 調(diào)配 多 輛 車配送 的動(dòng)態(tài)問題 。關(guān)鍵 詞 ： 車輛動(dòng)態(tài)調(diào)度 ； 蟻群算法 ； ma t l a b 仿真 中圖分 類號(hào) ： U4 9 2 ． 2 2文獻(xiàn)標(biāo) 志碼 ：

3、 A 文章編號(hào) ： 1 0 0 8 — 5 6 9 6 ( 2 0 1 4 ) 0 6 — 0 0 3 7 — 0 3Re s e a r c ho nVe hi c l eS c h e d u l i n gPr o b l e m Ba s e do nAn tCo l o n yAl g o r i t hm WANGJ i a n — l i n g ，QIZ i — x i ，HEL u( S h a n g h a i

4、Oc e a nUn i v e r s i t yCo l l e g eo fEn g i n e e r i n g，S h a n g h a i2 0 1 3 0 6 ，Ch i n a )Ab s t r a c t ： A c c o r d i n gt ot h eb a s i cp r i n c i p l ea n dm a t h e m a t i c a lm o d e lo fa n tc o l o

5、 n ya l g o r i t h m ，wes t u d yo nt h ed e l i v e r yp r o b l e m a n dg i v et h es o l u t i o n ． Us i n gM ATL AB s o f t wa r et os i m u l a t et h ee x a mp l e ，n or e t u r nt y p ed i s t r i b u t i o n

6、o ft h es h o r t e s tp a t hi sf i n e d ；t h es h o r t e s tp a t hp a r t i t i o n e dd o ma i no p t i mi z a t i o n，i no r d e rt or e a l i z eo fd y n a mi cv e h i c l es c h e d u l i n gb a s e do nt h er o

7、 a dc o n d i t i o ni n f o r ma t i o na n dt h ea c t u a ln e e d s ．Ke ywo r d s ： d y n a mi cv e h i c l es c h e d u l i n g；a n tc o l o n ya l g o r i t h m ；ma t l a bs i mu l a t i o n隨著運(yùn)輸?shù)陌l(fā)展 ， 物資 的流通從單 一的車輛配

8、 送運(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ā)式算法 ，

9、目前的 主要算法有粒子群算法 、 蟻群算法等。本文采用基于模型的預(yù)先優(yōu)化法 ， 根據(jù)配送 中心和多個(gè)配送點(diǎn) ， 使用螞蟻算法 ， 用 ma t l a b軟件仿 真出最短路徑。運(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)度 。收稿 日期 ： 2 0 1 4 — 0 9 — 1 6作者簡介 ： 王建玲 ( 1

10、9 7 7 一) ， 女 ， 講師 ， 博士 ， 研究 方向 ： 最優(yōu)化理論 1 車輛調(diào)度數(shù)學(xué)模型的建立 不失一般性 ， 設(shè)整個(gè)蟻群中的螞蟻數(shù)量為 m， 所 需訪問的配送點(diǎn) 的數(shù)量為 ， 城市 i 與城市 之間的距離為 d(， J = = = 1 ， 2 ， ?，) ， 在 t 時(shí)刻配送點(diǎn) i 和配 送點(diǎn) 連接路徑上 的信息素濃度為 rf ( ￡ ) 。初始時(shí) 刻 ， 各個(gè)城市間連接路徑上 的信息素濃度相 同， 不 妨 設(shè) ( ￡ )

11、一0 。螞蟻 k ( 走 一1 ， 2 ， ?，) 根據(jù)各個(gè)城市間連接路 徑上的信息素濃度決定選擇下一步要轉(zhuǎn) 移的配送 點(diǎn) ， 設(shè) ( ￡ ) 為 t 時(shí)刻螞蟻 k 從配送點(diǎn) i 轉(zhuǎn)移到城市 J的概率 ， 其計(jì)算式為 ( ￡ )： = =： [] !∑ [( ￡ ) ] 。 [( ￡ ) ] ps C -a l l o we d k0 ， 否 則．，∈ a l l o we d k ；( 1 )式中： 珈() 為啟發(fā)函數(shù)，=l ／ d

12、o 為螞蟻從配送點(diǎn) i轉(zhuǎn)移 到配送 點(diǎn) J的期 望程 度。a l l o w e d( 志 一1 ， 2 ，? ， r n ) 為螞蟻 k下一步被允 許訪 問的配送點(diǎn) 的集 第 6 期 王建玲 ， 等 ： 基于蟻群算法的車輛調(diào)度 問題 ·3 9·表 1 各配送地點(diǎn)坐標(biāo) 配送地編號(hào) 1 21 31 4l 51 61 7l 81 92 02 12 2圖 2 蟻群算法 原理 步驟 1 ) 初始化各參數(shù)。計(jì)算時(shí) ， 需

13、要對(duì)相關(guān) 的參數(shù) 0進(jìn)行初始化， 如果蟻群的規(guī)模( 螞蟻數(shù)量)、 信息素 ， -5重要程度因子 a 、 啟 發(fā)函數(shù)重要程度 因子 、 信息素 寫． 1 5 0揮 發(fā) 因 子戶 、 信 息 素 釋 放 總 量Q 、 最 大 迭 代 次 數(shù) 和 迭辱- ， 2 0代次數(shù)初值。饔 ． 3 0 02 ) 構(gòu)建解 空 間。將 各個(gè)螞 蟻放置 于不 同出發(fā) 鬈 。 3 5 0點(diǎn)， 對(duì)每個(gè)螞蟻k ( 志 一1 ， 2 ， ?，) ， 按照第一個(gè)

14、概率 ． j函數(shù)計(jì)算其下一個(gè)待訪 問的配送點(diǎn) ， 直到所有螞蟻 一 5 0 0訪問完所有配送點(diǎn)。3 ) 記錄本次迭代最佳路徑 。4 ) 計(jì)算各個(gè)螞蟻經(jīng)過的路徑長度 ( 志 一1 ， 2 ，? ， m) ， 記錄當(dāng)前迭代次數(shù)中的最優(yōu)解 ， 即是所求 的 最短路徑 。5 ) 根據(jù)信息素濃度更新 △ 磚計(jì)算式 。6 ) 判斷是否終止 。若 i t e r ~ i t e r — ma x ， 令i t e r =i t e r 4 - 1

15、 ， 清空螞蟻經(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è)螞蟻仍然均 以配

16、送 中心為起始點(diǎn)進(jìn)行最短 路徑迭代。為了更直觀的對(duì)結(jié)果進(jìn)行觀察和分析 ，以圖形 的形式 將最 短路徑 的配 送順 序顯示 出來 。如圖 3 所示 ， 3 輛車配送 的路徑優(yōu)化 ， 如圖 4 所示 ， 3輛車各 自的最短路程和平均路徑 。城市橫坐標(biāo)， k m圖 33輛車配送最短路徑仿真示意 ．1l O ： Ov ,一90r _ _ ———— —————— ———— ——一褪 l9 0 0 }8 5 0 }》。 。? ～ ? ～ ，?