基于蟻群算法的危險(xiǎn)品物流線路優(yōu)化應(yīng)用研究

摘要:近年來(lái)，隨著石油工業(yè)、化學(xué)工業(yè)、核能源工業(yè)等產(chǎn)業(yè)的快速發(fā)展，作為能源、原材料和消費(fèi)品使用的危險(xiǎn)品的流通量越來(lái)越大，流通范圍越來(lái)越廣。因此，危險(xiǎn)品物流的需求量也越來(lái)越大，它作為一種特殊的專(zhuān)業(yè)物流，正得到較快的發(fā)展。[1]

在物流諸多環(huán)節(jié)中，配送占有重要的地位。該文主要從危險(xiǎn)品的角度出發(fā)，針對(duì)物流配送問(wèn)題中配送路線的選擇進(jìn)行分析研究，考慮實(shí)際中可能出現(xiàn)的約束條件:時(shí)間約束、節(jié)點(diǎn)約束和對(duì)象約束，建立與實(shí)際配送相符合的數(shù)學(xué)模型，將定性問(wèn)題轉(zhuǎn)化為定量問(wèn)題。

蟻群算法具有正反饋、并行計(jì)算、較強(qiáng)的魯棒性等諸多特點(diǎn)，在很多領(lǐng)域有著廣泛的應(yīng)用。利用蟻群算法對(duì)危險(xiǎn)品物流配送優(yōu)化問(wèn)題進(jìn)行求解，是本文的重點(diǎn)研究問(wèn)題之一。通過(guò)對(duì)蟻群算法中各參數(shù)的實(shí)際意義以及參數(shù)改進(jìn)方面進(jìn)行的研究，對(duì)蟻群算法的參數(shù)選擇方面進(jìn)行了改進(jìn)，使其更能適應(yīng)實(shí)際的需要，在此基礎(chǔ)上提出了一種基于蟻群算法的滿足約束條件的危險(xiǎn)品物流配送路線優(yōu)化問(wèn)題的解決方案。

關(guān)鍵詞:危險(xiǎn)品;物流優(yōu)化;蚊群算法

中圖分類(lèi)號(hào):TP311文獻(xiàn)標(biāo)識(shí)碼:A文章編號(hào):1009-3044(2009)25-7192-02

Ant Colony Algorithm Based on the Logistics of the Dangerous Goods Route Optimization Applied Research

DA Yi-shen， CHENG Peng-fei， ZHANG Qian， LI Dao-yong

(Jiangsu University of Science and Technology， Zhengjiang 212003， China)

Abstract: In recent years， with the rapid development of petroleum industry， chemical industry， nuclear energy industry and so on， the turnover of the dangerous goods， which are used as raw and processed materials and consumable， is becoming larger and larger， with an area wider and wider than before. So， the demand of itsphysical distribution is growing more and more. As a specific professional physical distribution，it is developing rapidly.

Among a good many of taches of physical distribution， delivering plays a very important role. This paper will start from the angle of dangerous goods and analysis the choice of different routes which may arises during the delivering. It will also consider the restricting conditions which may occur in practice: time restriction， node restriction and object restriction .Found according to the delivering practically， a maths model will translate the qualitative issues into quantitative issues.

With a lot of characteristics like positive feed back， accounting in parallel，better roustness， Ant colony optimization(ACO) has a wide application in many fields. It is one of the most important researches of this paper to find a solution to the problem of optimizing the delivering of dangerous goods by ACO. In order to meet the practical needs， it improves the parameter choice by the investigation of the practical significance of each parameter during ACO. After that， it proposes the solution of the problem of the optimizing of the delivering route which must satisfy the restricting conditions and base on ACO.

Key words: dangerous goods; optimizing; ant colony optimization(ACO)

配送是物流中的一個(gè)重要的、直接與消費(fèi)者相連的環(huán)節(jié)。物流配送車(chē)輛的路線優(yōu)化，是物流配送優(yōu)化中的一個(gè)關(guān)鍵環(huán)節(jié)。正確合理地安排車(chē)輛的配送線路，可以有效的減少車(chē)輛的空駛率，有效的增加車(chē)輛的利用率，實(shí)現(xiàn)合理線路運(yùn)輸，從而降低運(yùn)輸成本，節(jié)約運(yùn)輸時(shí)間，提高客戶服務(wù)水平，提高經(jīng)濟(jì)效益，達(dá)到科學(xué)化的物流管理。

本文基于上述背景，通過(guò)運(yùn)用物流配送相關(guān)理論，并結(jié)合物流配送實(shí)際情況，針對(duì)當(dāng)前具有多頻次、小批量、多品種的危險(xiǎn)品物流配送問(wèn)題，在“送”的環(huán)節(jié)上深入研究，期望在配送路徑優(yōu)化方面有所改進(jìn)，從而對(duì)危險(xiǎn)品物流配送提供有價(jià)值的參考。

1 危險(xiǎn)品物流配送路線優(yōu)化研究意義

當(dāng)前危險(xiǎn)品物流配送具有多頻次、小批量、多品種、高效率的特點(diǎn)，因此設(shè)計(jì)合理、有效的車(chē)輛運(yùn)輸路線方案，盡量減少配送里程數(shù)和配送時(shí)間不僅可以減少資源浪費(fèi)，提高企業(yè)的經(jīng)濟(jì)效益和競(jìng)爭(zhēng)力，而且可以更好地為客戶服務(wù)，維護(hù)企業(yè)良好的形象。

一般的配送路線優(yōu)化問(wèn)題的描述為:如何選擇最優(yōu)配送路線，使得投入的運(yùn)輸成本最低，又能滿足客戶的需求。實(shí)際上，由于客戶數(shù)目的巨大，這一問(wèn)題的可行解數(shù)目非常巨大，甚至不可能用類(lèi)似于枚舉法的方法在能夠接受的時(shí)間范圍內(nèi)得到最優(yōu)解或者較優(yōu)解;并且客觀約束條件復(fù)雜而繁多，因此該問(wèn)題已經(jīng)成為一個(gè)公認(rèn)的物流難題。

2 危險(xiǎn)品物流配送路線優(yōu)化的約束條件

危險(xiǎn)品物流配送是近距離，小批量，品種比較復(fù)雜，按用戶需要搭配品種與數(shù)量的服務(wù)體系。從配送中心把貨物送到所需的各個(gè)用戶，有很多種不同的路線選擇方案。合理地選擇配送路線，對(duì)企業(yè)和社會(huì)都具有很重要的意義。進(jìn)行配送路線優(yōu)化時(shí)，必須有明確的目標(biāo)，遵循基本的原則。配送路線方案目標(biāo)的實(shí)現(xiàn)過(guò)程受到很多約束條件的限制，因而必須在滿足約束條件的限制下取得成本最低、路線最短、消耗最小等目標(biāo)。其中常見(jiàn)的約束有:1) 收貨人對(duì)貨物品種、規(guī)格和數(shù)量的要求;2) 收貨人對(duì)貨物送達(dá)時(shí)間或時(shí)間范圍的要求;3) 道路運(yùn)行條件對(duì)危險(xiǎn)品物流配送的制約，如單行道、城區(qū)部分道路對(duì)貨車(chē)通行的限制;4) 車(chē)輛最大行駛里程數(shù)的限制;5) 各種運(yùn)輸規(guī)章的限制等等。

3 危險(xiǎn)品物流配送路線優(yōu)化的蟻群算法分析

3.1 危險(xiǎn)品物流配送路線優(yōu)化的蟻群算法設(shè)計(jì)

在初始化的時(shí)候，m只螞蟻被放置在不同的城市上，賦予每條邊上的信息素濃度為tijk(0)=C(C為常數(shù))，即各路徑上信息量相等。每個(gè)螞蟻的batulist的第一個(gè)元素賦值為它所在的城市。當(dāng)螞蟻們完成了一次完整的尋徑過(guò)程后，計(jì)算tijk，并且更新每條邊上的信息素濃度。然后開(kāi)始新一輪的循環(huán)。[2]當(dāng)循環(huán)的次數(shù)達(dá)到事先定義好的NCmax時(shí)或者所有的螞蟻都選擇了同一種路徑方式時(shí)，整個(gè)程序終止。

Ant-cycleSystem模型程序的代碼如下:

Step 1:

初始化:

Sett=0，NC=0 每條邊上的tijk (0)=0并且Δτj=0放置m 只螞蟻到n 個(gè)城市上

Step 2:

令S=1，(s是 tabulist 的下標(biāo))

Fork=1to m do

把第k只螞蟻的初始城市號(hào)碼放置到takuk(S)中

Step 3:

Repeatuntiltabulistisfull

Set S=S+1

For k=1 to m do

根據(jù)概率pijk來(lái)選擇下一步應(yīng)該到達(dá)的城市，將第k只螞蟻移到城市j

并將j插入到takuk(S)中

Step 4:

For k=1 to m do

計(jì)算第k只螞蟻的總路徑長(zhǎng)度Ls更新找到的最短路徑

For k=1 to m do

更新邊上的信息素濃度

Step 5:

對(duì)每一條邊計(jì)算τ(t+n)

Sett=t+n

SetNC=NC+l

Set Δτij =0

Step 6:

IfNC

Then 清空所有的Tabulist

Go to Step2

打印出最短路徑

終止整個(gè)程序

3.2 危險(xiǎn)品物流配送路線優(yōu)化的蟻群算法流程圖

如圖1，如果程序終止于NC次循環(huán)后，這個(gè)算法的復(fù)雜度為0(NC·n2·m)。實(shí)際上，第一步的復(fù)雜度為0(n2+m)，第二步的復(fù)雜度為0(m)，第三步和第四步的復(fù)雜度為0(n2·m)，第五步的復(fù)雜度為0(n2)，第六步的復(fù)雜度為0(n·m)。實(shí)驗(yàn)證明m一般取值與n為同一數(shù)量級(jí)。因此整個(gè)算法的復(fù)雜度為0(NC·n3)。[3]

4 危險(xiǎn)品物流物流配送路線優(yōu)化問(wèn)題的蟻群算法文字描述

輸入:地圖上的n個(gè)節(jié)點(diǎn)，路徑ij的長(zhǎng)度為Zji，路徑ij的時(shí)間消耗為T(mén)ji。

輸出:尋找一條滿足時(shí)間約束的最短回路。

在選擇策略方面，主要是參照蟻群系統(tǒng)(ACS)中的隨機(jī)選擇概率:

在螞蟻選擇下一城市之前，將選擇情況分為“利用已知信息”和“搜索”兩部分進(jìn)行:另外，在啟發(fā)式信息η方面，不再根據(jù)兩點(diǎn)間的距離來(lái)確定，而是根據(jù)時(shí)間權(quán)值和道路權(quán)值兩部分來(lái)確定。[4]

在信息素更新方面，主要參照最值蟻群算法(MMAS)思想，限定了信息量的上下值[τmin， τmax]，避免某條路徑的信息量遠(yuǎn)大于其他路徑，提高局部搜索能力。在判斷是否存在可行解方面，先將有時(shí)間約束的節(jié)點(diǎn)挑選出來(lái)，計(jì)算是否存在一個(gè)可行解，如果不存在可行解，那么對(duì)于選定的所有節(jié)點(diǎn)來(lái)說(shuō)，也就不存在可行解了;如果存在可行解，再進(jìn)行全局的搜索。

在判斷是否存在可行解方面，先將有時(shí)間約束的節(jié)點(diǎn)挑選出來(lái)，計(jì)算是否存在一個(gè)可行解，如果不存在可行解，那么對(duì)于選定的所有節(jié)點(diǎn)來(lái)說(shuō)，也就不存在可行解了;如果存在可行解，再進(jìn)行全局的搜索。

在這里，該算法描述是基于蟻群算法(針對(duì)TSP問(wèn)題)描述而來(lái)，不同點(diǎn)有如下幾個(gè)方面:[5]

1) 道路節(jié)點(diǎn)不再?zèng)]有限制，而是加入了時(shí)間和節(jié)點(diǎn)的限制條件，此時(shí)節(jié)點(diǎn)間不再是對(duì)稱(chēng)的。

2) 蟻群算法中TabuList存放的是已走過(guò)的城市列表，而在這里它存放的是該節(jié)點(diǎn)可到達(dá)的城市列表相關(guān)信息。從而打破了每個(gè)節(jié)點(diǎn)只走一次的限制。

3) 參數(shù)的設(shè)定，不再是采用定性的參數(shù)，而采用變參的形式，從而更能反映微觀信息的變化。

5 結(jié)論

該文基于蟻群算法，實(shí)現(xiàn)了危險(xiǎn)品物流配送路線問(wèn)題的優(yōu)化。通過(guò)對(duì)危險(xiǎn)品物流配送模式的研究，詳細(xì)地分析了在物流配送過(guò)程中可能出現(xiàn)的種種約束條件，并在此基礎(chǔ)上，論證該算法在路線優(yōu)化的有效性、適用性，在節(jié)點(diǎn)約束和時(shí)間約束的條件下，得到較為滿意的配送路線[6];結(jié)合實(shí)例討論了蟻群算法及其性能，并通過(guò)蟻群算法的參數(shù)分析，指出了蟻群算法用于危險(xiǎn)品物流配送路線優(yōu)化時(shí)的優(yōu)劣，結(jié)合實(shí)例，驗(yàn)證了該算法的有效性，說(shuō)明該算法具有一定的尋優(yōu)能力，為危險(xiǎn)品物流配送路線優(yōu)化問(wèn)題提供了參考依據(jù)。其中難點(diǎn)在于:

1) 蟻群算法的參數(shù)設(shè)計(jì)。蟻群算法參數(shù)的選擇往往對(duì)問(wèn)題求解有很大的影響，由于參數(shù)的設(shè)置往往根據(jù)實(shí)驗(yàn)得到，如何設(shè)置參數(shù)，使蟻群算法在物流配送優(yōu)化問(wèn)題中求解性能更好。

2) 在實(shí)現(xiàn)算法的過(guò)程中，采取何種既能滿足約束條件又能提高計(jì)算性能的數(shù)據(jù)結(jié)構(gòu)。

參考文獻(xiàn):

[1] 王艷華.危險(xiǎn)化學(xué)品道路運(yùn)輸系統(tǒng)危險(xiǎn)性分析[J].中國(guó)安全科學(xué)學(xué)報(bào)， 2005.15(2):8-12.

[2] 尹曉峰，杜艷萍.車(chē)輛路徑問(wèn)題的蟻群算法研究[J].2005，26(4):82-182.

[3] 張強(qiáng)，荊剛，陳建玲.車(chē)輛路線問(wèn)題研究現(xiàn)狀已發(fā)展方向[J].交通科技，2004(1):60-62.

[4] 楊勇，胡上序.蟻群算法求解連續(xù)空間優(yōu)化問(wèn)題[J].控制與決策，2003，18(5):573-576.

[5] 莊昌文，基于協(xié)同工作方式的一種蟻群布線系統(tǒng)[J].半導(dǎo)體學(xué)報(bào)，999，20(5):400-406.

[6] 侯立文，蔣馥，一種基于螞蟻算法的交通分配方法及其應(yīng)用[J].上海交通大學(xué)學(xué)報(bào)，2001，35(6):930-933.