滾筒輸送線路徑規(guī)劃方法研究*

薛志強,游有鵬

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

0 引 言

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

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

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

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

1 輸送線結構環(huán)境模型

1.1 輸送線結構建模

滾筒輸送線的模塊之間需建立連接關系，才能形成完整且流通的輸送線，完成相應的功能。這里采用有向圖的數(shù)據(jù)結構來構建輸送線復雜連接，用鄰接矩陣為圖結構的儲存方式。

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

(1)

式中：A[i][j]=1—模塊i和模塊j之間有連接，且連接方向為從模塊i指向模塊j；A[i][j]=0—模塊i和模塊j無任何方向的連接。

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

1.2 滾筒輸送線結構模型改進

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

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

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

本文采用輸送機當量來衡量路徑長度，計算方法如下：

(2)

式中：Qij─從i節(jié)點到j節(jié)點路段上的輸送機當量；m─輸送機類型總數(shù)；k(1,2,3…,m)─輸送機類型標號；qk─該路徑上第k類輸送機的數(shù)量；fk─第k類輸送機的當量換算系數(shù)。

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

表1 各類輸送機當量換算系數(shù)

本研究以直線傳送輸送機為參考基準進行取值，具體可根據(jù)實際情況進行調整。

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

某一較復雜輸送線結構簡化后的例圖如圖1所示。

圖1 輸送線結構簡化例圖

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

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

按照上述方法對復雜輸送線的結構模型改進后，再建立有向圖結構，鄰接矩陣中的值為各個路段的輸送機當量，節(jié)點自身的輸送機當量為0，節(jié)點之間無直接連接的輸送機當量為無窮大。

采用這種改進的結構模型可簡化圖結構和路徑規(guī)劃的難度，因此下文路徑選擇優(yōu)化算法的設計將以此為基礎。

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

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

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

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

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

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

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

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

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

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

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

(3)

式中：dij─節(jié)點i到節(jié)點j的路段長度；djg─節(jié)點j到目標節(jié)點g之間的路段長度。

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

(4)

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

當所有的螞蟻在輸送線圖結構上完成一次路徑選擇后，需要對各路徑上的信息素進行更新，即：

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

(5)

(6)

(7)

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

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

采用蟻群算法求解輸送線最短加權路徑及長度流程圖，如圖3所示。

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

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

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

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

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

(1)某個物品必須經(jīng)過輸送線中的某個節(jié)點進行特殊處理；

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

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

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

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

2.4 實例分析

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

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

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

3 結束語

本文分析了滾筒輸送線的環(huán)境模型，提出了以輸送機當量衡量路徑長度的計算方法，并對較復雜輸送線的結構模型進行了改進。

研究的結果表明：

(1)改進后的結構模型簡化了圖結構，并降低了路徑規(guī)劃的難度；

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

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