薛志強(qiáng),游有鵬

(南京航空航天大學(xué) 機(jī)電學(xué)院，江蘇 南京 210016)

0 引 言

滾筒輸送線是由電動(dòng)滾筒、光電傳感器、控制器、條碼識(shí)別模塊等設(shè)備組成的一種傳輸系統(tǒng)，由于其具有可定制化、空間利用率高、成本低等優(yōu)勢(shì)，被廣泛用于物品分揀、生產(chǎn)線連接和物流系統(tǒng)集成等場(chǎng)合[1]。

目前，滾筒輸送線的部件已逐漸標(biāo)準(zhǔn)化，從而形成了更高集成度的滾筒輸送機(jī)，包括直線兩方向傳送輸送機(jī)、圓弧兩方向傳送輸送機(jī)、直角四方向移載輸送機(jī)、兩方向升降輸送機(jī)和斜坡輸送機(jī)等功能模塊。升降輸送機(jī)和斜坡輸送機(jī)使得輸送線可能存在三維多層結(jié)構(gòu)；而直角移載輸送機(jī)模塊擁有4個(gè)方向的傳輸移載功能，是輸送線中的重要節(jié)點(diǎn)模塊，使輸送線更加柔性化。

隨著現(xiàn)代物流系統(tǒng)的發(fā)展，需求更加復(fù)雜化、多樣化，滾筒輸送線系統(tǒng)面臨較多的挑戰(zhàn)。一條輸送線中各個(gè)輸送機(jī)之間構(gòu)成復(fù)雜的拓?fù)潢P(guān)系，需要特殊的數(shù)據(jù)結(jié)構(gòu)來(lái)描述。在復(fù)雜輸送線結(jié)構(gòu)中，從某入口到某出口可能會(huì)出現(xiàn)多條路徑，不同路徑根據(jù)傳送距離、傳送時(shí)間和一定的約束等存在優(yōu)劣之分。如何選擇最優(yōu)的可行輸送路徑，是本文要解決的路徑規(guī)劃問(wèn)題。目前，國(guó)內(nèi)外關(guān)于輸送線路徑規(guī)劃方法的研究，主要基于網(wǎng)格法劃分的環(huán)境模型，運(yùn)算量較大、實(shí)時(shí)性較差[2]。

本文將以滾筒輸送線為對(duì)象，構(gòu)建其環(huán)境模型并進(jìn)行優(yōu)化，充分考慮輸送線系統(tǒng)中的實(shí)際影響因素，引入路徑規(guī)劃算法，解決滾筒輸送線中的路徑選擇問(wèn)題。

1 輸送線結(jié)構(gòu)環(huán)境模型

1.1 輸送線結(jié)構(gòu)建模

滾筒輸送線的模塊之間需建立連接關(guān)系，才能形成完整且流通的輸送線，完成相應(yīng)的功能。這里采用有向圖的數(shù)據(jù)結(jié)構(gòu)來(lái)構(gòu)建輸送線復(fù)雜連接，用鄰接矩陣為圖結(jié)構(gòu)的儲(chǔ)存方式。

假定輸送線有n個(gè)模塊，構(gòu)成圖G=(V,E)的n個(gè)頂點(diǎn)，即V={v0,v1,...,vn-1}，圖的鄰接矩陣是一個(gè)n×n的二位數(shù)組，用A[n][n]表示，且數(shù)組的元素為：

(1)

式中：A[i][j]=1—模塊i和模塊j之間有連接，且連接方向?yàn)閺哪Ki指向模塊j；A[i][j]=0—模塊i和模塊j無(wú)任何方向的連接。

上述無(wú)加權(quán)的有向圖能準(zhǔn)確描述滾筒輸送線的結(jié)構(gòu)，便于上位機(jī)圖形繪制、動(dòng)態(tài)監(jiān)控等，也易于實(shí)現(xiàn)較少模塊輸送線的路徑規(guī)劃。但對(duì)于模塊數(shù)量較大、連接較復(fù)雜的輸送線，基于上述圖結(jié)構(gòu)模型進(jìn)行路徑規(guī)劃變得較為困難，需要對(duì)上述建模方法進(jìn)行適當(dāng)改進(jìn)。

1.2 滾筒輸送線結(jié)構(gòu)模型改進(jìn)

針對(duì)滾筒輸送線的特點(diǎn)與路徑規(guī)劃需求，可以對(duì)上述圖結(jié)構(gòu)模型進(jìn)行適當(dāng)?shù)暮?jiǎn)化與改進(jìn)。事實(shí)上，滾筒輸送線中只有移載輸送機(jī)模塊可以完成3個(gè)或4個(gè)方向的路徑選擇；作為入口或出口的輸送機(jī)模塊是整個(gè)輸送線的結(jié)構(gòu)邊界；而其他模塊只具有傳輸功能，相互連接路徑唯一，不存在路徑選擇。

根據(jù)上述特點(diǎn)，本文將以入口、出口、3個(gè)或4個(gè)方向的移載輸送機(jī)作為節(jié)點(diǎn)，節(jié)點(diǎn)之間的其他輸送機(jī)連接作為加權(quán)路徑，對(duì)輸送線圖結(jié)構(gòu)進(jìn)行簡(jiǎn)化。

在重新構(gòu)建的輸送線圖結(jié)構(gòu)中，節(jié)點(diǎn)與節(jié)點(diǎn)之間可能存在多種不同類型輸送機(jī)連接組合，進(jìn)而形成一條路段通道，路段長(zhǎng)度計(jì)算方法成為首要解決的問(wèn)題。

本文采用輸送機(jī)當(dāng)量來(lái)衡量路徑長(zhǎng)度，計(jì)算方法如下：

(2)

式中：Qij─從i節(jié)點(diǎn)到j(luò)節(jié)點(diǎn)路段上的輸送機(jī)當(dāng)量；m─輸送機(jī)類型總數(shù)；k(1,2,3…,m)─輸送機(jī)類型標(biāo)號(hào)；qk─該路徑上第k類輸送機(jī)的數(shù)量；fk─第k類輸送機(jī)的當(dāng)量換算系數(shù)。

各類輸送機(jī)當(dāng)量換算系數(shù)如表1所示。

表1 各類輸送機(jī)當(dāng)量換算系數(shù)

本研究以直線傳送輸送機(jī)為參考基準(zhǔn)進(jìn)行取值，具體可根據(jù)實(shí)際情況進(jìn)行調(diào)整。

輸送機(jī)當(dāng)量換算系數(shù)取值方法：在相同條件下，多次測(cè)試、計(jì)算并統(tǒng)計(jì)物品通過(guò)各類輸送機(jī)所用時(shí)間與通過(guò)直線傳送輸送機(jī)所用時(shí)間的比值，以各類輸送機(jī)對(duì)應(yīng)的比值數(shù)據(jù)的平均值為其相應(yīng)的當(dāng)量換算系數(shù)。

某一較復(fù)雜輸送線結(jié)構(gòu)簡(jiǎn)化后的例圖如圖1所示。

圖1 輸送線結(jié)構(gòu)簡(jiǎn)化例圖

近100個(gè)輸送機(jī)模塊的輸送線，簡(jiǎn)化后僅有10個(gè)節(jié)點(diǎn)。該圖結(jié)構(gòu)中節(jié)點(diǎn)集合為{①，②，③，④，⑤，⑥，⑦，⑧，⑨，⑩}，路段集合為{1,2,3,4,5,6,7,8,9，10，11，12，13}，箭頭所指為節(jié)點(diǎn)間路段上的物品傳送方向。節(jié)點(diǎn)①、④為入口節(jié)點(diǎn)，節(jié)點(diǎn)③、⑨、⑩為出口節(jié)點(diǎn)，其他節(jié)點(diǎn)都為移載模塊節(jié)點(diǎn)，從而構(gòu)成6組路徑規(guī)劃需求。圖1中，各個(gè)路段號(hào)后括號(hào)內(nèi)的數(shù)字為對(duì)應(yīng)路段的輸送機(jī)當(dāng)量。

如從節(jié)點(diǎn)⑧到節(jié)點(diǎn)⑨的路段12中，輸送機(jī)當(dāng)量為20.5，其計(jì)算方法如下：假設(shè)路段12包含15個(gè)直線傳送輸送機(jī)、2個(gè)直角移載輸送機(jī)、1個(gè)180度圓弧傳送輸送機(jī)、1個(gè)升降輸送機(jī)，則依據(jù)式(2)得其輸送機(jī)當(dāng)量為：15×1+2×0.5+1×1.5+1×3=20.5。

按照上述方法對(duì)復(fù)雜輸送線的結(jié)構(gòu)模型改進(jìn)后，再建立有向圖結(jié)構(gòu)，鄰接矩陣中的值為各個(gè)路段的輸送機(jī)當(dāng)量，節(jié)點(diǎn)自身的輸送機(jī)當(dāng)量為0，節(jié)點(diǎn)之間無(wú)直接連接的輸送機(jī)當(dāng)量為無(wú)窮大。

采用這種改進(jìn)的結(jié)構(gòu)模型可簡(jiǎn)化圖結(jié)構(gòu)和路徑規(guī)劃的難度，因此下文路徑選擇優(yōu)化算法的設(shè)計(jì)將以此為基礎(chǔ)。

2 輸送線的路徑規(guī)劃

2.1 基于Dijkstra算法路徑選擇優(yōu)化設(shè)計(jì)

輸送線的功能是將物品從特定的入口送入，經(jīng)過(guò)一定的路徑送達(dá)特定的出口。為了提高輸送能力，需要獲取從特定入口到特定出口的最短路徑。

Dijkstra算法是求解單源最短路徑規(guī)劃的經(jīng)典算法[3-4]，將其用于輸送線的最短路徑規(guī)劃的流程如圖2所示。

圖2 迪杰斯特拉算法求解輸送線最短路徑流程圖

以圖1為例，假定需計(jì)算從入口①到出口⑩的最短路徑，首先建立圖結(jié)構(gòu)鄰接矩陣所對(duì)應(yīng)的二維數(shù)組Edge[10][10]。

為求解最短路徑及長(zhǎng)度，需要設(shè)置并計(jì)算3個(gè)一維數(shù)組：數(shù)組dist[10]表示當(dāng)前從節(jié)點(diǎn)①到其他節(jié)點(diǎn)的最短路徑長(zhǎng)度(初始值為Edge中的第一行)；數(shù)組source[10]表示當(dāng)前節(jié)點(diǎn)是否已被檢測(cè)(0為未檢測(cè)，1位已檢測(cè)，初始時(shí)候只有節(jié)點(diǎn)①對(duì)應(yīng)的值為1，其他都為0)；數(shù)組path[10]表示從節(jié)點(diǎn)①到某節(jié)點(diǎn)的最短路徑上該節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)序號(hào)，最后可以采用倒向追蹤法來(lái)確定最短路徑上的各個(gè)節(jié)點(diǎn)[5-6]。

對(duì)于規(guī)模較小的圖結(jié)構(gòu)，應(yīng)用Dijkstra算法求解輸送線的最短路徑較方便；而當(dāng)簡(jiǎn)化后的圖結(jié)構(gòu)仍然比較復(fù)雜時(shí)，啟發(fā)式智能算法則具有更好的實(shí)時(shí)性和魯棒性。

2.2 基于蟻群算法的路徑選擇優(yōu)化設(shè)計(jì)

蟻群算法是依據(jù)螞蟻種群總是能找從巢穴到食物之間的最短路徑而提出的一種啟發(fā)式算法，不僅與輸送線的最短路徑模型類似，而且具有良好的實(shí)時(shí)性，便于實(shí)現(xiàn)動(dòng)態(tài)路徑規(guī)劃。

蟻群算法中路徑選擇含有貪心規(guī)則的不利因素，引入選擇概率來(lái)避免完全貪心規(guī)則而陷入局部最優(yōu)，而啟發(fā)函數(shù)對(duì)路徑選擇概率有較大的影響。通常，傳統(tǒng)蟻群算法采用距離啟發(fā)函數(shù)ηij(t)=1/dij，這種啟發(fā)函數(shù)容易使得螞蟻貪圖當(dāng)前的一小步，進(jìn)而選擇偏離目標(biāo)方向的節(jié)點(diǎn)。依據(jù)輸送線圖結(jié)構(gòu)的節(jié)點(diǎn)松散、路徑靜態(tài)等特點(diǎn)，對(duì)啟發(fā)函數(shù)進(jìn)行改進(jìn)，增加目標(biāo)節(jié)點(diǎn)對(duì)選擇下一節(jié)點(diǎn)的影響，改進(jìn)后的啟發(fā)函數(shù)如下：

(3)

式中：dij─節(jié)點(diǎn)i到節(jié)點(diǎn)j的路段長(zhǎng)度；djg─節(jié)點(diǎn)j到目標(biāo)節(jié)點(diǎn)g之間的路段長(zhǎng)度。

將式(3)引入到蟻群算法中，得到螞蟻k在t時(shí)刻由節(jié)點(diǎn)i轉(zhuǎn)移到節(jié)點(diǎn)j的概率，如下式所示：

(4)

式中：τij(t)—t時(shí)刻在路段(i,j)上的信息量(初始狀態(tài)下各路徑上的信息量都相等，為常數(shù))；α—信息素啟發(fā)因子(衡量信息量對(duì)是否選擇該路徑的影響程度)；β—期望啟發(fā)因子(衡量啟發(fā)信息對(duì)螞蟻選擇路徑的影響程度)；allowedk—螞蟻k可選擇節(jié)點(diǎn)的集合[7]。

當(dāng)所有的螞蟻在輸送線圖結(jié)構(gòu)上完成一次路徑選擇后，需要對(duì)各路徑上的信息素進(jìn)行更新，即：

τij(t+n)=(1-ρ)·τij(t)+Δτij

(5)

(6)

(7)

式中：Q—信息素加強(qiáng)系數(shù)；Lk—第k只螞蟻在本次迭代中所走過(guò)的路徑長(zhǎng)度[8-9]。

根據(jù)輸送線圖結(jié)構(gòu)的實(shí)際情況，本研究對(duì)蟻群算法中的參數(shù)進(jìn)行取值，值的選擇因模型而異，需要不斷調(diào)整找到平衡點(diǎn)，進(jìn)而求出最優(yōu)路徑。

采用蟻群算法求解輸送線最短加權(quán)路徑及長(zhǎng)度流程圖，如圖3所示。

圖3 蟻群算法求解輸送線最優(yōu)路徑流程圖

禁忌表用于記錄當(dāng)前已知的不可能在最優(yōu)路徑上的節(jié)點(diǎn)，信息量表用于記錄各個(gè)節(jié)點(diǎn)的信息素。

需要注意的是，盡管蟻群算法比Dijkstra算法更適合于規(guī)模較大的路徑規(guī)劃，且具有良好的實(shí)時(shí)性和魯棒性，但參數(shù)選擇不當(dāng)仍能會(huì)影響求解。

2.3 實(shí)際工況約束下的輸送線路徑規(guī)劃策略

在裝配生產(chǎn)線等輸送線系統(tǒng)中，某些工況需要對(duì)最短路徑進(jìn)行修正，主要?dú)w納為以下兩類：

(1)某個(gè)物品必須經(jīng)過(guò)輸送線中的某個(gè)節(jié)點(diǎn)進(jìn)行特殊處理；

(2)當(dāng)前最短路徑上某個(gè)路段通行壓力較大。

針對(duì)第一類情況，如果路徑必須包含某節(jié)點(diǎn)N，對(duì)2.1和2.2中的算法修正策略如下：先求解從起點(diǎn)到節(jié)點(diǎn)N的最短路徑及長(zhǎng)度，再求解從節(jié)點(diǎn)N到終點(diǎn)的最短路徑及長(zhǎng)度，最后進(jìn)行拼接組合即可。該處理策略可以擴(kuò)展應(yīng)用于必須包含多個(gè)節(jié)點(diǎn)的路徑規(guī)劃問(wèn)題。

針對(duì)第二類情況，如果當(dāng)前搜索到的最短路徑上的路段P(i,j)較為擁堵，對(duì)2.1和2.2中的算法修正策略如下：可以根據(jù)擁堵的情況，通過(guò)適當(dāng)?shù)臋?quán)數(shù)來(lái)增加路段P(i,j)的路段長(zhǎng)度(Dijkstra算法中增加Edge[i][j]的值；蟻群算法增加dij的值)。這種處理策略可以增加選擇其他較通暢路徑的概率，進(jìn)而達(dá)到最短路徑修正的目的[10-11]。

具體應(yīng)用中，兩算法的選擇還需結(jié)合輸送線規(guī)模和算法的具體特點(diǎn)：規(guī)模較小的輸送線采用Dijkstra算法，規(guī)模較大的輸送線優(yōu)先用蟻群算法；去蟻群算法無(wú)法求得最優(yōu)路徑的情況下，再用Dijkstra算法重新求解。

2.4 實(shí)例分析

本研究以圖1所示系統(tǒng)為例，采用Dijkstra算法和蟻群算法分別求解圖1中從入口節(jié)點(diǎn)①到出口節(jié)點(diǎn)⑩的最優(yōu)路徑，再加入2.3小節(jié)中兩種約束，對(duì)路徑重新規(guī)劃，分別得出最優(yōu)結(jié)果，如表2所示(Dijkstra簡(jiǎn)寫(xiě)為Dij)。

表2 輸送線最優(yōu)路徑規(guī)劃算法結(jié)果驗(yàn)證

由表2可知：兩種算法的求解具有相同的結(jié)果，且為實(shí)際最優(yōu)路徑。

3 結(jié)束語(yǔ)

本文分析了滾筒輸送線的環(huán)境模型，提出了以輸送機(jī)當(dāng)量衡量路徑長(zhǎng)度的計(jì)算方法，并對(duì)較復(fù)雜輸送線的結(jié)構(gòu)模型進(jìn)行了改進(jìn)。

研究的結(jié)果表明：

(1)改進(jìn)后的結(jié)構(gòu)模型簡(jiǎn)化了圖結(jié)構(gòu)，并降低了路徑規(guī)劃的難度；

(2)針對(duì)最短路徑選擇問(wèn)題，分別采用較為經(jīng)典的Dijkstra算法和啟發(fā)式的改進(jìn)蟻群算法進(jìn)行求解，分析了兩種算法的適用場(chǎng)合；

(3)針對(duì)輸送線應(yīng)用的兩種實(shí)際工況，提出了相應(yīng)的動(dòng)態(tài)修正策略，為解決這兩類約束下滾筒輸送線路徑最優(yōu)規(guī)劃提供了有效的解決方案，也可為其他類型輸送線的路徑規(guī)劃提供借鑒。