考慮執(zhí)行任務(wù)均衡的倉儲多自動引導(dǎo)車路徑優(yōu)化方法

董亞倩，楊 帆，翟藝穎

（云南電網(wǎng)有限責(zé)任公司大理供電局物流服務(wù)中心，大理 671000）

0 引言

自動引導(dǎo)車是以電池作為動力支持的自動化軌道行駛設(shè)備，可在激光元件的作用下，沿預(yù)設(shè)路徑前行，由于整個行進過程并沒有駕駛?cè)藛T的配合，所以車輛主體上必須設(shè)置裝配機械、移載元件等多種輔助性機構(gòu)設(shè)備。對于倉儲運輸體系而言，一個完整的引導(dǎo)車控制系統(tǒng)同時包含核心計算機、導(dǎo)航設(shè)備、充電設(shè)備等多種應(yīng)用元件，其主要工作原理表現(xiàn)為在核心計算機接收到監(jiān)控調(diào)度指令后，引導(dǎo)車輛可以準(zhǔn)確按照既定路徑行駛，當(dāng)其順利到達任務(wù)位置后，導(dǎo)航設(shè)備自動向核心主機反饋結(jié)束指令，從而實現(xiàn)一次完整的任務(wù)執(zhí)行流程[1]。在行進過程中，整個控制系統(tǒng)的自動化程度極高，且由于充電樁設(shè)備的存在，引導(dǎo)車可就近選擇充電位置，從而滿足車輛所需的電力供應(yīng)需求。為適應(yīng)多變的行進路線，一條運輸路徑中有可能同時存在多個轉(zhuǎn)彎節(jié)點，而當(dāng)自動引導(dǎo)車通過這些節(jié)點時，為保證車輛行駛的絕對安全性，其實時行進速度也會出現(xiàn)明顯下降的表現(xiàn)情況，這就導(dǎo)致引導(dǎo)車在單一路徑內(nèi)的運行時間不斷延長，并最終造成倉儲運輸任務(wù)的完成速率受到影響。為解決上述問題，提出考慮執(zhí)行任務(wù)均衡的倉儲多自動引導(dǎo)車路徑優(yōu)化方法。

1 基于執(zhí)行任務(wù)均衡算法的引導(dǎo)車選址建模

在執(zhí)行任務(wù)均衡算法作用下，倉儲多自動引導(dǎo)車選址建模包含最小調(diào)度生成樹建立、選址任務(wù)分配、干擾度計算三個處理流程，具體操作流程如下。

1.1 任務(wù)調(diào)度最小生成樹

為使倉儲多自動引導(dǎo)車的實際行進路徑與預(yù)設(shè)路徑保持一致，應(yīng)在分配執(zhí)行任務(wù)時，挖掘與調(diào)度節(jié)點相關(guān)的深度信息，并在滿足車輛選址需求的基礎(chǔ)上，建立完整的任務(wù)調(diào)度最小生成樹結(jié)構(gòu)。所謂任務(wù)調(diào)度最小生成樹是支配倉儲多自動引導(dǎo)車行進路徑的最基礎(chǔ)執(zhí)行結(jié)構(gòu)，一般來說，與不同引導(dǎo)車輛相關(guān)的生成樹結(jié)構(gòu)形式也有所不同?；旧闪鞒虨椋寒?dāng)倉儲多自動引導(dǎo)車接收到行進任務(wù)時，執(zhí)行主機首先查找是否有生成樹節(jié)點能夠滿足該條路徑內(nèi)的車輛調(diào)度需求，如果有，則直接安排行進路徑，若果沒有，則繼續(xù)構(gòu)建下級生成樹節(jié)點。其次，執(zhí)行主機繼續(xù)執(zhí)行上述步驟，直至已生成樹節(jié)點能夠完全滿足該條路徑內(nèi)的車輛調(diào)度需求。最后，計數(shù)路徑內(nèi)的轉(zhuǎn)彎節(jié)點數(shù)量，對引導(dǎo)車運行時間進行有效控制。具體判別流程如下。

根據(jù)任務(wù)調(diào)度最小生成樹結(jié)構(gòu)，可排除非必要轉(zhuǎn)彎節(jié)點對倉儲多自動引導(dǎo)車行進時間造成的影響，從而為車輛行進路徑的可靠選址提供了可能。

1.2 選址任務(wù)分配

考慮到執(zhí)行任務(wù)的均衡處理原則，在安排倉儲多自動引導(dǎo)車行進路徑時，為每個節(jié)點選址任務(wù)都分配了不同的優(yōu)先級條件，且由于行進路徑及行進方向的不同，與每個優(yōu)先級條件所匹配的選址節(jié)點類型也有所不同。

在路徑安排初期，倉儲任務(wù)調(diào)度主機根據(jù)執(zhí)行任務(wù)均衡算法，建立必要的選址任務(wù)分配網(wǎng)絡(luò)體系，再根據(jù)最小生成樹的執(zhí)行步長值，確定多自動引導(dǎo)車在經(jīng)過關(guān)鍵選址節(jié)點時的行進速度水平[2]。在引導(dǎo)車行進過程中，每個選址節(jié)點處的執(zhí)行任務(wù)信息都具備自主更新的能力，一般來說，若當(dāng)前更新信息完全與引導(dǎo)車的行進需求相匹配，則可認(rèn)為車輛當(dāng)前行進速率已達最大值。

設(shè)Vi表示轉(zhuǎn)彎節(jié)點j處的行進干擾度，Pl表示轉(zhuǎn)彎節(jié)點j處的引導(dǎo)車行進路徑選址系數(shù)，μ表示控制參數(shù)項，聯(lián)立上述物理量，可將考慮執(zhí)行任務(wù)均衡的倉儲多自動引導(dǎo)車選址任務(wù)分配標(biāo)準(zhǔn)定義為：

式中，Kl表示轉(zhuǎn)彎節(jié)點j處的車輛執(zhí)行任務(wù)優(yōu)先級，Dj表示引導(dǎo)車單一路徑內(nèi)的轉(zhuǎn)彎節(jié)點選址強度值。為了避免倉儲多自動引導(dǎo)車的行進路徑成為一個閉環(huán)，兩個轉(zhuǎn)彎節(jié)點處的所有選址任務(wù)指標(biāo)取值均不能相等。

1.3 干擾度計算

與任務(wù)調(diào)度最小生成樹結(jié)構(gòu)中的其他參量指標(biāo)不同，干擾度系數(shù)在倉儲多自動引導(dǎo)車行進路徑中的所有轉(zhuǎn)彎節(jié)點之間都是完全公開共享的。因此，為保證干擾度系數(shù)的絕對統(tǒng)一性，應(yīng)根據(jù)已知的選址任務(wù)分配原則，對相關(guān)參量指標(biāo)的取值結(jié)果進行嚴(yán)格約束。

1）轉(zhuǎn)彎節(jié)點自身干擾程度

在倉儲多自動引導(dǎo)車行進路徑中，轉(zhuǎn)彎節(jié)點每隔一段時間就會向車載主機發(fā)送一個干擾指令，一方面對于車輛行駛起到提醒作用，另一方面也便于執(zhí)行任務(wù)調(diào)度主機對整條引導(dǎo)車行進路徑進行管控[3]。在此過程中，轉(zhuǎn)彎節(jié)點所發(fā)出干擾指令的傳輸強度就被稱為轉(zhuǎn)彎節(jié)點的自身干擾程度，具體計算表達式如下：

其中，ΔT表示單位間隔時長，Q1表示引導(dǎo)車行進任務(wù)的單位增量，表示行進指令的輸出量均值，χ表示倉儲多自動引導(dǎo)車行進路徑內(nèi)的導(dǎo)向量指標(biāo)。

2）被動性干擾條件

在引導(dǎo)車行進路徑中，被動性干擾存在于相鄰轉(zhuǎn)彎節(jié)點之間，一般來說，兩個節(jié)點之間的物理距離越遠，它們之間的被動干擾互動能力也就越強。計算定義式如下：

上式中，Q2表示因執(zhí)行任務(wù)均衡算法帶來的引導(dǎo)車行進速率增量，A∧表示行進任務(wù)信號特征值，β表示倉儲多自動引導(dǎo)車路徑中的車輛行進規(guī)劃系數(shù)，c0表示倉儲多自動引導(dǎo)車的初始行進能力。

聯(lián)立式(2)、式(3)，可將考慮執(zhí)行任務(wù)均衡的倉儲多自動引導(dǎo)車行進干擾度計算結(jié)果表示為：

式中，x表示考慮執(zhí)行任務(wù)均衡的引導(dǎo)車行進路徑規(guī)劃標(biāo)度值，表示行進量提取系數(shù)。在執(zhí)行任務(wù)均衡算法作用下，倉儲多自動引導(dǎo)車的選址建模處理必須以參考干擾度計算結(jié)果作為核心參考條件。

2 倉儲多自動引導(dǎo)車的行進路徑優(yōu)化

在執(zhí)行任務(wù)均衡算法的基礎(chǔ)上，按照路徑區(qū)域劃分、行進節(jié)點標(biāo)注、關(guān)聯(lián)優(yōu)化規(guī)則制定的執(zhí)行流程，完成對倉儲多自動引導(dǎo)車行進路徑的優(yōu)化與處理。

2.1 路徑區(qū)域劃分

在既定路徑區(qū)域中，根據(jù)執(zhí)行任務(wù)均衡算法對相關(guān)引導(dǎo)車行進數(shù)據(jù)進行處理，從而得到完整的選址節(jié)點分布集合。一般來說，單一路徑內(nèi)包含的轉(zhuǎn)彎節(jié)點數(shù)量越多，集合結(jié)構(gòu)中待處理數(shù)據(jù)的存儲量也就越多。對于倉儲多自動引導(dǎo)車來說，路徑區(qū)域劃分是選址節(jié)點集合建立的逆運算過程，在處理過程中，任務(wù)調(diào)度主機可根據(jù)轉(zhuǎn)彎節(jié)點所處實時位置，對引導(dǎo)車行進速度進行控制，并可以此為基礎(chǔ)，推斷車輛的單位行進能力，從而將整個路徑區(qū)域劃分成多個小模塊結(jié)構(gòu)，也便于對車體行進路徑進行后續(xù)的優(yōu)化處理[4]。

規(guī)定c1、c2、...、cn表示n個不同的轉(zhuǎn)彎節(jié)點定義系數(shù)，在倉儲多自動引導(dǎo)車路徑優(yōu)化的處理過程中，系數(shù)n的取值始終從自然數(shù)1開始，聯(lián)立式(4)，可將倉儲多自動引導(dǎo)車的行進路徑區(qū)域劃分標(biāo)準(zhǔn)定義為：

其中，λ表示定值判別條件。為有效控制引導(dǎo)車在單一路徑內(nèi)的運行耗時，每一路徑區(qū)域內(nèi)所包含的轉(zhuǎn)彎節(jié)點數(shù)量都不宜過多。

2.2 行進節(jié)點標(biāo)注

在既定路徑區(qū)域內(nèi)，倉儲多自動引導(dǎo)車的行進節(jié)點標(biāo)注就是將常規(guī)路徑節(jié)點與外部轉(zhuǎn)彎節(jié)點完全區(qū)分開來。為更好順應(yīng)執(zhí)行任務(wù)均衡算法的應(yīng)用需求，相鄰路徑區(qū)域之間可進行自發(fā)的行進計劃交換，一方面可將轉(zhuǎn)彎節(jié)點完全規(guī)劃至既定路徑范圍之外，另一方面也可將目標(biāo)節(jié)點聚合在一起，從而節(jié)省倉儲多自動引導(dǎo)車的實際運行時長。具體的行進節(jié)點標(biāo)注原理如圖2所示。

圖1 任務(wù)調(diào)度最小生成樹構(gòu)建流程圖

圖2 倉儲多自動引導(dǎo)車的行進節(jié)點標(biāo)注原理

在執(zhí)行任務(wù)均衡算法作用下，倉儲多自動引導(dǎo)車的行進必須按照節(jié)點標(biāo)注原則，這也是確保車輛能夠快速通過單一路徑的必要執(zhí)行環(huán)節(jié)。

2.3 關(guān)聯(lián)優(yōu)化規(guī)則

關(guān)聯(lián)優(yōu)化規(guī)則制定是倉儲多自動引導(dǎo)車路徑優(yōu)化處理過程中的關(guān)鍵執(zhí)行環(huán)節(jié)，可根據(jù)車輛行進距離、單位行進速率等指標(biāo)，對現(xiàn)有路徑的合理性進行判斷。所謂關(guān)聯(lián)優(yōu)化規(guī)則是指在原有行進路徑的基礎(chǔ)上，通過定標(biāo)處理等方式，對路徑區(qū)域中的不合理成分進行修改，不但能夠控制倉儲多自動引導(dǎo)車完整通過轉(zhuǎn)彎節(jié)點所需的消耗時長，也可以較好滿足執(zhí)行任務(wù)均衡分配的實際應(yīng)用需求[5]。設(shè)G1、G2表示兩個不同的行進節(jié)點定義項，在執(zhí)行任務(wù)均衡算法的作用下，G1≠G2的不等式條件恒成立。ξ表示既定的引導(dǎo)車調(diào)度系數(shù)，聯(lián)立式(5)，可將考慮執(zhí)行任務(wù)均衡的倉儲多自動引導(dǎo)車關(guān)聯(lián)路徑優(yōu)化規(guī)則表示為：

上式中，φ、δ表示兩個不同的引導(dǎo)車路徑優(yōu)化指標(biāo)向量。根據(jù)執(zhí)行任務(wù)均衡原則，可以實現(xiàn)對原有倉儲多自動引導(dǎo)車行進路徑的優(yōu)化處理，從而有效控制引導(dǎo)車在單一路徑內(nèi)的運行時長。

3 實例分析

選取圖1所示倉儲多自動引導(dǎo)車元件作為實驗對象，在其行進路徑中，隨機選取兩個轉(zhuǎn)彎節(jié)點作為測試位置，即節(jié)點“1”、節(jié)點“2”。

具體實驗流程如下：

步驟一：利用常規(guī)方法對所選取引導(dǎo)車行進行為進行控制，將記錄所得數(shù)據(jù)信息作為對照驗組變量；

步驟二：利用考慮執(zhí)行任務(wù)均衡的優(yōu)化方法所選取引導(dǎo)車行進行為進行控制，將記錄所得數(shù)據(jù)信息作為實驗組變量；

步驟三：令實驗組、對照組前行距離完全相等，分析引導(dǎo)車完整通過轉(zhuǎn)彎節(jié)點“1”、“2”所需消耗時長的具體變化情況。

圖3 倉儲多自動引導(dǎo)車的行進路線

倉儲多自動引導(dǎo)車完整通過轉(zhuǎn)彎節(jié)點所需的消耗時長，能夠反映車輛在單一路徑內(nèi)的行進速率，從而驗證所選取路徑的應(yīng)用可行性。一般來說，消耗時長越短，車輛在單一路徑內(nèi)的行進速率就越快，該條路徑的應(yīng)用可行性也就越強，反之則越弱。

圖4記錄了實驗組、對照組引導(dǎo)車完整通過轉(zhuǎn)彎節(jié)點“1”所需消耗時間的數(shù)值變化情況。

圖4 消耗時間（轉(zhuǎn)彎節(jié)點“1”）

上圖中記錄了7組不同的實驗結(jié)果。

實驗組：在整個實驗過程中，實驗組消耗時間在第5組別時取得最大值12s，在第6組別時取得最小值10s，在第1組、第3組、第7組時取值眾數(shù)值11.2s，全局最大值與全局最小值之間的物理數(shù)值差為2s，相較于實驗組耗時均值11.3s來說，該差值結(jié)果較小，對于整體耗時情況的影響能力不大。

對照組：在整個實驗過程中，對照組消耗時間在第2組別時取得最大值14s，在第1組別時取得最小值11.8s，在第3組、第4組、第6組時取值眾數(shù)值13.1s，全局最大值與全局最小值之間的物理數(shù)值差為2.2s，略大于實驗組極值差，故可認(rèn)為該差值結(jié)果對于整體耗時情況的影響能力略高于實驗組。

下圖記錄了實驗組、對照組引導(dǎo)車完整通過轉(zhuǎn)彎節(jié)點“2”所需消耗時間的數(shù)值變化情況。

圖5 消耗時間（轉(zhuǎn)彎節(jié)點“2”）

實驗組：在整個實驗過程中，實驗組消耗時間在第5組、第4組、第5組、第6組時取得最大值5.1s，與其眾數(shù)值結(jié)果相同，在第7組別時取得最小值4.4s，全局最大值與全局最小值之間的物理數(shù)值差為0.7s，相較于實驗組耗時均值4.9s來說，該差值結(jié)果較小，對于整體耗時情況的影響能力不大。

對照組：對照組消耗時間在第5組別時取得最大值9.4s，在第1組別時取得最小值4.6s，在整個實驗過程中，對照組耗時不存在明顯的眾數(shù)值結(jié)果，全局最大值與全局最小值之間的物理數(shù)值差為4.8s，遠高于實驗組差值，故可認(rèn)為該差值結(jié)果對于整體耗時情況的影響能力遠高于實驗組。

綜上可知，在考慮執(zhí)行任務(wù)均衡優(yōu)化方法的作用下，倉儲多自動引導(dǎo)車在通過轉(zhuǎn)彎節(jié)點“1”、轉(zhuǎn)彎節(jié)點“2”所需的消耗時長得到了較好控制，這不但提升了車輛在單一路徑內(nèi)的行進速率，也驗證了所選取路徑的應(yīng)用可行性。

4 結(jié)語

在執(zhí)行任務(wù)均衡算法的作用下，倉儲多自動引導(dǎo)車路徑優(yōu)化方法在原始行進路徑的基礎(chǔ)上，設(shè)置了全新的任務(wù)調(diào)度最小生成樹，又通過選址任務(wù)分配的處理方式，對干擾度系數(shù)值進行準(zhǔn)確計算，由于關(guān)聯(lián)性規(guī)則的存在，所有可能經(jīng)過的行進節(jié)點都可以被清晰標(biāo)注，這也有效避免了風(fēng)險性行進行為的出現(xiàn)。對于同一路徑內(nèi)的轉(zhuǎn)彎節(jié)點來說，引導(dǎo)車完全通過這些節(jié)點的消耗時間得到了有效控制，這也與選取可行性行進路徑的初衷完全相符。