邵雪松，高雨翔，宋瑞鵬，馮澤龍，帥　率，馬吉科

（1.國網(wǎng)江蘇省電力公司電力科學(xué)研究院國家電網(wǎng)電能計量重點實驗室，江蘇南京210019；2.江蘇方天電力技術(shù)有限公司，江蘇南京211102）

多目標(biāo)復(fù)合AGV調(diào)度系統(tǒng)建模及在電力計量檢定中的應(yīng)用

邵雪松1，高雨翔1，宋瑞鵬1，馮澤龍1，帥率2，馬吉科2

（1.國網(wǎng)江蘇省電力公司電力科學(xué)研究院國家電網(wǎng)電能計量重點實驗室，江蘇南京210019；2.江蘇方天電力技術(shù)有限公司，江蘇南京211102）

提出了一種基于車輛行駛距離、任務(wù)等待時間與搬運任務(wù)優(yōu)先級的自動導(dǎo)引小車（AGV）多目標(biāo)復(fù)合任務(wù)調(diào)度模型，通過調(diào)整不同因素的權(quán)重系數(shù)，動態(tài)調(diào)整模型的性能指標(biāo)；設(shè)計了基于A*算法的AGV調(diào)度系統(tǒng)最短路徑搜索策略，保證了AGV任務(wù)執(zhí)行效率的最大化；調(diào)度模型在超大規(guī)模電力計量檢定數(shù)字化車間中的進行了應(yīng)用，結(jié)果表明該調(diào)度模型與路徑規(guī)劃算法具有良好的適應(yīng)性與可推廣性。

自動導(dǎo)引小車；調(diào)度系統(tǒng)；路徑規(guī)劃；多目標(biāo)復(fù)合；電力計量檢定

自動導(dǎo)引小車（AGV）是依靠電磁、激光、視覺等導(dǎo)航設(shè)備，沿著工作站點之間的導(dǎo)向路徑，在調(diào)度系統(tǒng)的控制下完成一系列運輸、裝配等作業(yè)任務(wù)的自動化智能無人搬運車輛［1］。實際生產(chǎn)環(huán)境中，通過多個AGV協(xié)同作業(yè)，以快速高效地完成系統(tǒng)物料搬運、倉儲運輸?shù)热蝿?wù)。AGV自動運輸系統(tǒng)的調(diào)度，是指以特定的系統(tǒng)參數(shù)為優(yōu)化目標(biāo)，對運輸任務(wù)和車輛進行權(quán)重化排列，在此基礎(chǔ)上確定合理的分配方案，實現(xiàn)運輸任務(wù)和車輛間的最佳匹配，從而達到提升系統(tǒng)整體效率、降低運行成本的目的。

AGV系統(tǒng)作為未來自動化物流的重要組成部分，具有廣闊的發(fā)展前景，調(diào)度技術(shù)作為AGV自動運輸系統(tǒng)的核心技術(shù)，應(yīng)進一步加強其研究。作為一個并發(fā)系統(tǒng)，多個AGV同時運行時必然會帶來沖突、死鎖等問題［2］，將嚴重影響系統(tǒng)運轉(zhuǎn)效率，降低系統(tǒng)運行可靠性。傳統(tǒng)的控制系統(tǒng)一般采用集中調(diào)度策略，多AGV的路徑規(guī)劃算法和任務(wù)調(diào)度過程都在一個中央控制器中實現(xiàn)，當(dāng)系統(tǒng)中AGV數(shù)量增大時，系統(tǒng)的結(jié)構(gòu)和路徑規(guī)劃算法十分復(fù)雜。在AGV系統(tǒng)調(diào)度方面，柳賽男等給出了在遺傳算法的基礎(chǔ)上，考慮工藝路線的調(diào)度算法［3］；雷定猷等從柔性制造系統(tǒng)的角度，考慮不同任務(wù)優(yōu)先級，提出了以最小化路徑總長度為目標(biāo)的調(diào)度模型［4］；金芳等以倉庫運輸系統(tǒng)作為研究對象，研究了排隊理論在AGV調(diào)度中的應(yīng)用［5］；針對混合區(qū)域內(nèi)多AGV的協(xié)調(diào)調(diào)度，也有學(xué)者進行了相關(guān)研究［6］，Kusiak和Cyrus提出了一種最小化空閑運行時間的遺傳算法來解決AGV調(diào)度問題［7］。但是，大多數(shù)調(diào)度策略都是基于“推式策略”（push strategy），不能適應(yīng)生產(chǎn)模式的需求。

文中從生產(chǎn)系統(tǒng)實際應(yīng)用需求出發(fā)，重點圍繞AGV調(diào)度系統(tǒng)建模和AGV路徑規(guī)劃，研究多目標(biāo)復(fù)合任務(wù)調(diào)度模型與AGV路徑搜索算法，適應(yīng)復(fù)雜生產(chǎn)場景任務(wù)搬運需求，提高系統(tǒng)整體運行效率。

1　多目標(biāo)復(fù)合任務(wù)調(diào)度模型

1.1多AGV任務(wù)調(diào)度模型分類

在多AGV系統(tǒng)中，任務(wù)調(diào)度決定了搬運任務(wù)執(zhí)行的先后順序和時間長短，任務(wù)調(diào)度算法的合理性和實用性是影響生產(chǎn)系統(tǒng)運行效率的關(guān)鍵因素，目前常用的AGV任務(wù)調(diào)度策略有靜態(tài)任務(wù)調(diào)度模型和動態(tài)任務(wù)調(diào)度模型2種［1］。

對于靜態(tài)調(diào)度模型，所有的搬運任務(wù)已知，在車輛執(zhí)行任務(wù)之前，每一輛車的運行路徑都得到了優(yōu)化確認，離散調(diào)度模型算法簡單，但是任務(wù)環(huán)境適應(yīng)性較差，無法處理實時增加的搬運任務(wù)，同時無法應(yīng)對車輛擁堵、任務(wù)變更、車輛充電等情況，因而多AGV靜態(tài)調(diào)度模型已經(jīng)無法適用生產(chǎn)情況復(fù)雜的搬運需求。多AGV動態(tài)調(diào)度模型實時獲取搬運任務(wù)狀態(tài)和車輛狀態(tài)，根據(jù)搬運任務(wù)需求靈活調(diào)整搬運任務(wù)執(zhí)行順序，從而能夠最小化搬運任務(wù)優(yōu)先級變化、生產(chǎn)任務(wù)變更及車輛停用等不確定因素對生產(chǎn)帶來的影響。動態(tài)調(diào)度模型需要實時更新系統(tǒng)狀態(tài)，在線求解任務(wù)分配方案，系統(tǒng)運算復(fù)雜度隨著選取時間間隔的減小而增大，因此在多AGV動態(tài)調(diào)度算法中，通常根據(jù)實際生產(chǎn)情況確定計算頻率，保證系統(tǒng)動態(tài)響應(yīng)的實時性。

1.2多目標(biāo)復(fù)合調(diào)度模型

多AGV調(diào)度系統(tǒng)多是基于等待時間、隊列長度、系統(tǒng)吞吐量、運行距離、車輛利用率等指標(biāo)所建立?？紤]到實際生產(chǎn)過程中，搬運任務(wù)執(zhí)行效率主要反映在車輛運行距離、任務(wù)等待時間和任務(wù)優(yōu)先級，文中提出一種基于總的行駛距離、等待時間和搬運任務(wù)優(yōu)先級的多AGV任務(wù)調(diào)度模型。目標(biāo)函數(shù)如（1）所示：

式中：m為當(dāng)前任務(wù)數(shù)；k為當(dāng)前可用AGV車數(shù)；xij=1表示第i個任務(wù)被第j輛AGV執(zhí)行，否則xij=0；dij表示第i個任務(wù)被第j輛AGV執(zhí)行產(chǎn)生的路徑長度；ti為當(dāng)前時刻第i個任務(wù)的等待時間；pi為當(dāng)前時刻第i個任務(wù)的優(yōu)先級；u1，u2，u3為權(quán)重系數(shù)。

當(dāng)前復(fù)合調(diào)度模型的權(quán)重系數(shù)尚未有明確的分配理論，難以定量分析權(quán)重系數(shù)的分配方式是否合理，因此文中采用經(jīng)驗法確定權(quán)重系數(shù)，根據(jù)系統(tǒng)表現(xiàn)，動態(tài)調(diào)整權(quán)重比例。

2　路徑規(guī)劃

為了獲取AGV初始位置與搬運起始點和目標(biāo)點之間的最段距離，需要規(guī)劃AGV行駛路徑，同時保證多AGV運行環(huán)境下的行駛暢通。

2.1路徑特征描述

AGV路徑規(guī)劃中通常存在位置沖突、相向沖突和同向沖突3種沖突類型。位置沖突為多輛AGV同時到達同一位置節(jié)點；相向沖突為同一條路徑同時只允許1臺AGV通過，而2輛AGV相向行駛互不相讓發(fā)生沖突；同向沖突為多輛AGV在同一路徑沿相同方向行駛，后面的AGV行駛速度較快，與前面車輛發(fā)生追尾碰撞。針對這3種沖突，在路徑設(shè)置時應(yīng)加以限制，避免沖突發(fā)生。為了提高AGV系統(tǒng)的適應(yīng)性和可靠性，AGV路徑特征描述如下：

（1）每輛AGV同時只能接收一個任務(wù)，在AGV未進入取貨路段之前允許任務(wù)變更，在AGV進入取貨路段之后不允許任務(wù)變更，必需執(zhí)行完當(dāng)前任務(wù)才能接收下一搬運任務(wù)；

（2）每輛AGV行駛速度設(shè)置相同，根據(jù)實際運行情況選擇直線速度、轉(zhuǎn)彎速度；

（3）每輛AGV在駛近目標(biāo)點和駛離目標(biāo)點時的減速度和加速度設(shè)置相同；

（4）每條路段均為單相行駛路線，并且行駛方向固定；

（5）每條路段允許多臺AGV同時運行；

（6）車輛之間設(shè)置行駛安全距離，避免發(fā)生追尾碰撞；

（7）任意2條平行路段之間設(shè)置足夠的行駛間距，避免發(fā)生占道刮擦；

（8）每個路徑交叉區(qū)域均為單車行駛區(qū)域，同一時刻只允許1輛AGV駛?cè)搿?/p>

2.2A*路徑規(guī)劃算法

當(dāng)?shù)貓D環(huán)境已知時，為了求解最短路徑，國內(nèi)外學(xué)者研究了許多算法，比如遺傳算法、神經(jīng)網(wǎng)絡(luò)算法、Dijkstra算法及A*算法等［3］。遺傳算法模擬染色體的遺傳及變異特性，通過編碼隨機選擇初始種群，計算適應(yīng)函數(shù)和選擇率，進而模擬交叉、變異行為，判斷下代是否滿足需求，對于最優(yōu)路徑的求解需要多次迭代，運算復(fù)雜度較高。Dijkstra算法的特點在于采用類似等勢線的逐級擴展搜索策略，只對部分連接節(jié)點進行搜索即可。A*算法作為一種啟發(fā)式搜索算法，加入了一些限定條件，可以有效舍棄一些路徑點，從而增加搜索效率，但是由于A*算法并沒有完全遍歷所有可行解，所得到的結(jié)果不一定是最優(yōu)解。

綜合考慮路徑搜索效率，文中選擇A*算法搜索最短路徑。A*算法可用式（2）描述：

圖1　A*路徑搜索算法流程

從圖1中可以看出，首先將AGV起始位置點設(shè)置為起點k，搜索與起點k相連的路徑點，并計算k與所有路徑點的距離，選擇距離最小的路徑點作為新的搜索起點繼續(xù)執(zhí)行，直到找到目標(biāo)點為止。

3　電力計量檢定車間中的應(yīng)用

文中提出的多AGV復(fù)合指標(biāo)動態(tài)任務(wù)調(diào)度模型在江蘇省電力公司超大規(guī)模電力計量檢定數(shù)字化車間進行了實際應(yīng)用測試。江蘇電能表自動化檢定基地采用“機器人+AGV+檢定裝置”的檢定方案，分布有電能表檢定裝置、自動掛卸表機器人、AGV運輸小車及轉(zhuǎn)接臺等。智能機器人實現(xiàn)自動掛卸表、條碼掃描及視覺定位功能；自動檢定裝置實現(xiàn)自動壓接、翻轉(zhuǎn)及功能檢測；AGV小車完成箱垛的輸送任務(wù)。檢定任務(wù)開始時，智能電能表通過AGV輸送單元從庫房接駁處輸送到檢定單元，智能機器人把電能表從周轉(zhuǎn)箱取出掛到電能表自動化檢定裝置，機器人掛表的同時完成身份識別；電能表自動化檢定裝置完成耐壓測試、功能及誤差檢測，檢定完成后由機器人把電能表下到周轉(zhuǎn)箱；再由AGV輸送到庫房接駁處，送至封印貼標(biāo)線，最后送到自動化庫房。在整個任務(wù)流程中，AGV系統(tǒng)負責(zé)電能表的轉(zhuǎn)接輸送，AGV調(diào)度系統(tǒng)的可靠性和合理性對電能表自動化檢定任務(wù)的執(zhí)行效率起著關(guān)鍵作用［8-12］。

電能表自動化檢定AGV路線區(qū)域分布如圖2所示，檢定區(qū)根據(jù)區(qū)域位置劃分為4個區(qū)：A區(qū)、B區(qū)、C區(qū)、D區(qū)，A區(qū)設(shè)置A1-A5共5條檢定線，B區(qū)設(shè)置B1-B9共9條檢定線，C區(qū)設(shè)置C1-C4共4條檢定線，D區(qū)設(shè)置D1-D4共4條檢定線，其中A5線、B1線、B9線、C1線、C4線、D1線、D4線為AGV單邊輸送路線，其余2條檢定線共用1條輸送路線，AGV雙邊伸叉輸送。為避免相向沖突，每條輸送路徑的AGV行駛方向固定，如圖中黃色箭頭所示。

圖2　電能表自動化檢定AGV路線區(qū)域分布

檢定區(qū)包含253個取貨工位，253個送貨工位；接駁區(qū)負責(zé)檢定區(qū)和倉儲庫房的轉(zhuǎn)運接駁，包含3個取貨工位和3個送貨工位；充電區(qū)設(shè)置4個充電站點，當(dāng)AGV電量小于設(shè)定閾值時，車輛自動觸發(fā)充電任務(wù)。此外，檢定區(qū)內(nèi)設(shè)置了若干臨時待命點，當(dāng)車輛處于空閑狀態(tài)時會自動前往待命點等待任務(wù)分配。臨時待命點根據(jù)區(qū)域繁忙程度和車輛行駛便捷性分配，如接駁區(qū)承擔(dān)了整個檢定區(qū)的電能表轉(zhuǎn)接任務(wù)，吞吐量高，因此在接駁區(qū)設(shè)置了5個臨時待命點，以保證接駁任務(wù)能夠及時搬運。AGV系統(tǒng)共配置了12輛AGV小車，為了避免車輛在路徑交叉口處出現(xiàn)死鎖和碰撞，為每個交叉口劃分唯一車輛通行區(qū)域，同一時刻只允許1輛AGV通行，其余車輛原地等待。

圖3為某一時刻生產(chǎn)環(huán)境中AGV系統(tǒng)測試任務(wù)分布情況。對于當(dāng)前系統(tǒng)緩存里所有AGV任務(wù)，調(diào)度系統(tǒng)根據(jù)任務(wù)位置、任務(wù)優(yōu)先級與任務(wù)等待時間自動搜索需要先執(zhí)行的AGV任務(wù)。這種多目標(biāo)復(fù)合調(diào)度模型能保證AGV任務(wù)得到及時執(zhí)行，確保在整個生產(chǎn)系統(tǒng)AGV數(shù)量最小配置下任務(wù)執(zhí)行效率最大化。

圖3　AGV任務(wù)分布與列表

考慮車輛等待時間、隊列長度、系統(tǒng)吞吐量、運行距離、車輛利用率等因素。將AGV多目標(biāo)復(fù)合調(diào)度模型與基于時間優(yōu)先的通用調(diào)度策略任務(wù)執(zhí)行能力進行比較，在正常8 h滿負荷生產(chǎn)條件下，多目標(biāo)復(fù)合調(diào)度策略AGV執(zhí)行搬運次數(shù)1386次，完成單相電能表檢定32 080只，三相電能表檢定3389只；時間優(yōu)先調(diào)度策略AGV執(zhí)行搬運次數(shù)1155次，完成單相電能表檢定26 661只，三相電能表檢定3106只?？梢姡瑫r間優(yōu)先調(diào)度的AGV任務(wù)執(zhí)行效率僅為多目標(biāo)復(fù)合調(diào)度下AGV任務(wù)執(zhí)行效率的83%。

4　結(jié)束語

針對AGV系統(tǒng)調(diào)度及路徑規(guī)劃，提出了基于車輛行駛距離、任務(wù)等待時間和搬運任務(wù)優(yōu)先級的AGV多目標(biāo)復(fù)合任務(wù)調(diào)度模型，解決了實際生產(chǎn)中搬運效率與緊急任務(wù)的處理需求。綜合考慮車輛沖突、死鎖，運行安全性等因素，采用A*算法進行AGV路徑規(guī)劃，求解AGV最短路徑，具有較強的實用性。文中提出的AGV任務(wù)調(diào)度模型與路徑規(guī)劃算法在超大規(guī)模電力計量數(shù)字化車間取得了較好的應(yīng)用效果，具有一定的推廣應(yīng)用價值。

［1］白帥福.基于混合區(qū)域控制模型的多AGV系統(tǒng)調(diào)度研究［D］.南京：南京航空航天大學(xué)，2011.

［2］任小龍，溫浩宇，李華.基于無向Petri網(wǎng)的多AGV最優(yōu)路徑方法研究［J］.西安電子科技大學(xué)學(xué)報，2008，35（3）：517-522.

［3］柳賽男，柯映林.一種解決有AGV小車約束的車間智能調(diào)度問題的算法［J］.中國機械工程，2007，18（15）：1810-1813.

［4］雷定猷，張?zhí)m.AGV系統(tǒng)的調(diào)度優(yōu)化模型［J］.科學(xué)技術(shù)與工程，2008，8（1）：66-69.

［5］金芳，方凱，王京林.基于排隊論的AGV調(diào)度研究［J］.儀器儀表學(xué)報，2004，25（4）：844-846.

［6］朱琳，范秀敏，何其昌.柔性生產(chǎn)系統(tǒng)配料區(qū)多自動導(dǎo)航小車調(diào)度優(yōu)化［J］.計算機集成制造系統(tǒng)，2012（6）：1168-1175.

［7］KUSIAK A，CYRUS JP.Routing and Scheduling of Automated Guided Vehicles［J］.International Journal of Flexible Manufacturing Systems，1995，9（4）：35-42.

［8］黃奇峰，蔡奇新，鄭飛.超大規(guī)模智能電能表自動化檢測研究與仿真［J］.電測與儀表，2013，50（5）：91-94.

［9］劉建，黃奇峰，王忠東，等.基于PlantSimulation的AGV輸送系統(tǒng)仿真分析及其應(yīng)用［J］.現(xiàn)代制造工程，2013（11）：13-15，19.

［10］邵雪松，蔡奇新，黃奇峰，等.電能表自動化檢定機器人可靠掛卸表方案設(shè)計與實現(xiàn)［J］.電測與儀表，2014，51（16A）：151-155.

［11］黃奇峰，王忠東，蔡奇新，等.電能表自動化檢定壓接過程動力學(xué)仿真分析［J］.科技咨詢，2013（33）：109-110.

［12］許海清，黃敏.淺談電力大數(shù)據(jù)對信息運行的影響［J］.江蘇電機工程，2015，34（2）：62-65.

Multi-target Com pounded AGV Scheduling System M odeling and App lication in Electric Power Metering Calibration

SHAO Xuesong1，GAO Yuxiang1，SONGRuipeng1，F(xiàn)ENG Zelong1，SHUAIShuai2，MA Jike2
（1.State Grid Key Laboratory of Electric Energy M etering，StateGrid Jiangsu Electric Pow er Com pany Electric Pow er Research Institute，Nanjing 210019，China；2.Jiangsu Fangtian Electric Technology Co.Ltd.，Nanjing211102，China）

This subm ission proposesamulti-target compounded AGV（Automated Guided Vehicle）scheduling system model based on the driving distance，the taskwaiting timeand the task priority.Themodel'sperformance indicator can beoptimized automatically through adjusting theweight coefficientsof different factors.In order to ensure themaximum efficiency of AGV task execution，the shortest path search strategy is designed according to the A*algorithm.The AGV schedulingmodel is tested in the electric pow ermetering digitalw orkshop.The results show that the proposed method has good adaptability and replicability.

AGV；scheduling system；path planning；multi-target com pounded；electric powermetering calibration

TP391.9，TM 743

A

1009-0665（2016）05-0024-04

邵雪松（1987），男，安徽淮南人，博士，從事自動控制和電能表自動化檢定技術(shù)研究工作；

高雨翔（1989），男，江蘇南京人，工程師，從事電測量技術(shù)和自動控制技術(shù)研究工作；

宋瑞鵬（1988），男，河南新鄉(xiāng)人，工程師，從事電力計量檢定技術(shù)研究工作；

馮澤龍（1981），男，江蘇南京人，工程師，從事電力計量和自動控制技術(shù)研究工作；

帥率（1984），男，江蘇南京人，助理工程師，從事電力信息化系統(tǒng)設(shè)計研究工作；

馬吉科（1980），男，甘肅蘭州人，從事電力計量檢定控制研究工作。

2016-07-01；

2016-07-09