集裝箱自動(dòng)化碼頭AGV帶時(shí)間約束的路徑規(guī)劃研究

韋燚劉曉東

（1.上海海事大學(xué)物流工程學(xué)院電工理論與新技術(shù)系，上海 201306；2.上海海事大學(xué)物流工程學(xué)院電力電子與電力傳動(dòng)系，上海 201306）

集裝箱自動(dòng)化碼頭AGV帶時(shí)間約束的路徑規(guī)劃研究

韋燚1，劉曉東2

（1.上海海事大學(xué)物流工程學(xué)院電工理論與新技術(shù)系，上海 201306；2.上海海事大學(xué)物流工程學(xué)院電力電子與電力傳動(dòng)系，上海 201306）

近年來(lái)，物流自動(dòng)化發(fā)展迅速和自動(dòng)化導(dǎo)引小車的廣泛應(yīng)用，給集裝箱自動(dòng)化碼頭的發(fā)展指明了方向，AGV路徑優(yōu)化可提高集裝箱自動(dòng)化碼頭的效率，降低碼頭運(yùn)輸成本，使集裝箱的裝卸效率以及堆場(chǎng)的利用率得以大大的提高，具有廣闊的發(fā)展前景。本文針對(duì)帶時(shí)間約束的AGV系統(tǒng)路徑規(guī)劃問(wèn)題，提出一種基于成本的路徑優(yōu)化方法，并進(jìn)行了算例分析，實(shí)例求解表明此種調(diào)度方法可以在規(guī)定運(yùn)輸時(shí)間內(nèi)使運(yùn)輸成本最低。

AGV；時(shí)間約束；路徑優(yōu)化；成本

0 引言

隨著世界貿(mào)易和經(jīng)濟(jì)全球化的發(fā)展，物流自動(dòng)化程度的提高，港口在進(jìn)出口貿(mào)易中扮演著越來(lái)越重要的角色。集裝箱運(yùn)輸成為重要的運(yùn)輸方式，擁有環(huán)保、高效、智能化的優(yōu)越性能的集裝箱自動(dòng)化碼頭更是今后港口運(yùn)輸?shù)陌l(fā)展趨勢(shì)。AGV具有并行作業(yè)、智能化自動(dòng)化、和柔性化的特性，因此能夠很好的滿足港口、碼頭的搬運(yùn)要求，被廣泛應(yīng)用在全球自動(dòng)化和半自動(dòng)化碼頭中，降低了運(yùn)輸成本，提高了碼頭裝卸、調(diào)度效率及港口競(jìng)爭(zhēng)力[1-2]。

由上面的分析可以看出，集裝箱碼頭的運(yùn)輸線路問(wèn)題也是在一些特定的約束條件下在保證完成目的的情況下實(shí)現(xiàn)運(yùn)輸?shù)某杀咀畹?，就是以追求成本最小化為目?biāo)。本文建立混合控制系統(tǒng)模型，提出一種基于成本的帶時(shí)間約束的AGV路徑規(guī)劃方法，并通過(guò)舉例驗(yàn)證該方法的有效性。

1 面向帶時(shí)間約束AGV的路徑規(guī)劃

自動(dòng)導(dǎo)引小車（automated guided vehicle，AGV）是裝有自動(dòng)導(dǎo)引、以電池為動(dòng)力的裝置，能按指定路徑行進(jìn)，可智能地控制運(yùn)行動(dòng)作，具有安全保護(hù)裝置、啟停裝置以及搬載功能，因此能很好的滿足港口、碼頭的搬運(yùn)要求[3-4]。由于其柔性的適應(yīng)能力，AGV已經(jīng)成為現(xiàn)代智能港口運(yùn)輸不可缺少的運(yùn)載工具，是提高港口作業(yè)效率的主要因素之一。

1.1 AGV的分類

AGV 按照控制水平來(lái)分可以分為以下幾種：

1）遙控型：此類AGV 只負(fù)責(zé)執(zhí)行上位機(jī)給予的控制命令。而AGV 本身不具備任何的智能水平，沒(méi)有任何的自主判斷及決策能力。

2）半自主型：此類AGV 具備一定的智能水平，能夠通過(guò)自身的感知從而進(jìn)行基本的信息的決策功能，但是遇到復(fù)雜情況時(shí)，仍然需要人為進(jìn)行干預(yù)。

3）自主型：按照工作人員預(yù)先設(shè)置的要求，根據(jù)已知的外界環(huán)境信息進(jìn)行規(guī)劃整理，尋找到最優(yōu)路徑，在前進(jìn)過(guò)程中通過(guò)不斷地感知信息，重新規(guī)劃使自己不斷進(jìn)行調(diào)整，進(jìn)而判斷決策，能夠順利完成指定任務(wù)。

1.2 AGV的導(dǎo)引方式

根據(jù)導(dǎo)引方式的不同可以將AGV分為線路導(dǎo)引AGV、非線路導(dǎo)引AGV 兩種。線路導(dǎo)引是指在AGV 前進(jìn)線路上設(shè)置導(dǎo)向信息標(biāo)志，如色帶、導(dǎo)引線、電磁導(dǎo)線、磁釘?shù)?，通過(guò)車上設(shè)置的傳感器來(lái)識(shí)別并追蹤導(dǎo)向信息前進(jìn)。非線路導(dǎo)引一般采用坐標(biāo)定位原理，一邊前進(jìn)一邊實(shí)時(shí)地探測(cè)AGV自身所處環(huán)境的實(shí)際位置。下面介紹幾種常用的導(dǎo)引方式。

（1）坐標(biāo)導(dǎo)引：將AGV 所在的環(huán)境區(qū)域劃分成若干的小坐標(biāo)區(qū)域，通過(guò)對(duì)小坐標(biāo)區(qū)域的計(jì)數(shù)實(shí)現(xiàn)導(dǎo)引，但此種方法的地面安裝量較大，而且精度較低，在精度要求較高時(shí)，便不能滿足要求。

（2）慣性導(dǎo)引：即在AGV 上安裝陀螺儀，在其前進(jìn)區(qū)域內(nèi)安裝相應(yīng)的定位塊，控制器通過(guò)計(jì)算陀螺儀的偏差信號(hào)，采集地面定位塊信號(hào)來(lái)確定AGV 的位置和方向。

（3）電磁導(dǎo)引：電磁導(dǎo)引是使用范圍比較廣的一種導(dǎo)引方式，它類似于有線導(dǎo)引，即在AGV前進(jìn)道路的地下鋪設(shè)金屬線，給金屬線上加上相應(yīng)的頻率，在AGV 上進(jìn)行導(dǎo)引頻率的解碼，從而控制AGV 的前進(jìn)方向。該導(dǎo)引方式的路線不易更改，其柔性相應(yīng)較低。

（4）激光導(dǎo)引：激光導(dǎo)引是在AGV 前進(jìn)道路的周圍安裝激光反射板，激光反射板定位準(zhǔn)確，AGV上通過(guò)發(fā)射激光束，激光束遇到反射板后發(fā)生反射，AGV 通過(guò)采集反射回的激光束進(jìn)行計(jì)算，確定當(dāng)前AGV 的實(shí)時(shí)位置及其方向。

（5）視覺(jué)導(dǎo)引：采用攝像頭捕捉AGV 前進(jìn)區(qū)域的環(huán)境信息，用微處理器進(jìn)行圖像識(shí)別，此種導(dǎo)引技術(shù)在軍用領(lǐng)域有廣泛的研究。

通過(guò)以上分析可以看出，不同類型的AGV 對(duì)運(yùn)行路徑的規(guī)劃和優(yōu)化具有一定的區(qū)別，對(duì)自主控制能力較強(qiáng)的AGV 來(lái)說(shuō)，其路徑的控制主要是由小車本身來(lái)完成的，而自主控制能力較弱的AGV 主要依靠地面控制站的路徑規(guī)劃和控制。

在研究集裝箱自動(dòng)化碼頭小車的調(diào)度時(shí)，一般分為協(xié)調(diào)堆場(chǎng)和協(xié)調(diào)碼頭前沿的兩大種調(diào)度類型。該混合控制系統(tǒng)模型研究的是在不同貝位集裝箱裝卸時(shí)的調(diào)度問(wèn)題，為每個(gè)AGV尋找合適的路徑以及行駛速度，使其滿足各自約束條件，以裝箱為例。為了研究方便，把碼頭堆場(chǎng)上的一些設(shè)施看成質(zhì)點(diǎn)以此來(lái)構(gòu)造一個(gè)模型[5-6]。在建立混合控制系統(tǒng)模型前，定義一下數(shù)學(xué)符號(hào)意義：

（1）建立有向圖G=（V，E），每個(gè)頂點(diǎn)v∈V是二維或者三維空間里的一個(gè)節(jié)點(diǎn)，節(jié)點(diǎn)v1到節(jié)點(diǎn)v2是一條大致平滑的弧線 e1。

（2）有限集合Δ={1，…，A}是有向圖G上AGV的集合，每一臺(tái)AGV如果小車沿著G上路徑行駛，則該小車的坐標(biāo)由所在弧線坐標(biāo)給定。

（3）對(duì)于自動(dòng)導(dǎo)引小車α1，其起點(diǎn)坐標(biāo)為，終點(diǎn)坐標(biāo)為，從起點(diǎn)到終點(diǎn)的行駛時(shí)間為。表示小車起點(diǎn)所處的弧線，表示小車終點(diǎn)所處的弧線，為其行駛路徑

所述AGV路徑優(yōu)化控制方法是一種面向時(shí)間約束的控制策略，目的是使成本最小化，其具有一定約束條件：每臺(tái)AGV的行駛時(shí)間一定，起始和終點(diǎn)一定，并且在規(guī)定的速度范圍之內(nèi)，求解出最小成本消耗的控制策略。

圖1 AGV交通網(wǎng)絡(luò)及初始位置Fig.1 Transpotation network and original position of AGV

2 仿真試驗(yàn)與分析

為了驗(yàn)證AGV路徑優(yōu)化算法的正確性和有效性，用SQP（序列二次規(guī)劃）求解，對(duì)AGV進(jìn)行仿真試驗(yàn)。兩臺(tái)移動(dòng)的AGV，分別為α1和α2，從起點(diǎn)到終點(diǎn)有兩條路徑，如圖1（每格代表2海里）：

則可求解得4種模式兩臺(tái)AGV的運(yùn)行速度（圖2、3、4、5）、到規(guī)定時(shí)間AGV的位置（圖6、7、8、9）及4種模式的成本消耗。

圖2 模式θ1下的AGV速度（kts）Fig.2 The speed of each AGV in model θ1（kts）

圖3 模式θ2下的AGV速度（kts）Fig.3 The speed of each AGV in model θ2（kts）

圖4 模式θ3下的AGV速度（kts）Fig.4 The speed of each AGV in model θ3（kts）

圖5 模式θ4下的AGV速度（kts）Fig.5 The speed of each AGV in model θ4（kts）

表1 四種控制模式Tab.1 Four control models

當(dāng)k=1即ρk（1）時(shí)，ρ=21.2，兩臺(tái)AGV的位置如圖6、7、8、9：

圖6 模式θ1下的AGV位置Fig.6 The position of each AGV in model θ1

圖7 模式θ2下的AGV位置Fig.7 The position of each AGV in model θ2

圖8 模式θ3下的AGV位置Fig.8 The position of each AGV in model θ3

圖9 模式θ4下的AGV位置Fig.9 The position of each AGV in model θ4

4種模式的成本總消耗如表2：

由表可看出，4種控制方案中，符合成本最低要求的是控制模式θ4。

表2 各控制模式的總成本Tab.2 The total cost of each control model

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

本文針對(duì)AGV待時(shí)間約束的特性，建立了AGV小車混合控制系統(tǒng)模型，提出了基于成本的AGV小車路徑優(yōu)化方法，減小了AGVS的成本消耗，并仿真驗(yàn)證了AGV小車混合控制算法的正確性和有效性，能較好較快求解出少量AGV的最低成本消耗，給出最優(yōu)控制模式。然而其運(yùn)用范圍具也有一定的局限性，具有時(shí)間約束和AGV車速約束。隨著AGV數(shù)量的增大，系統(tǒng)通訊協(xié)調(diào)過(guò)程將會(huì)變得復(fù)雜，還會(huì)帶來(lái)系統(tǒng)實(shí)時(shí)性的問(wèn)題，有待于模型運(yùn)作機(jī)制的進(jìn)一步改進(jìn)。

［1］ LunaR. An efficient and complete approach for cooperative path-findin［A］.National Conference on Artifical Intelligence［C］.2011：1804-1805.

［2］ HuJ，PrandiniM，SastryS.Optimal coordinated motions of multiple agents moving on a place［J］.USA：SIAM L Control and Optimation，2003，42（10）：637-668.

［3］ 劉迪，陸檑，朱曉非，等.基于MSP430控制的智能小車設(shè)計(jì)［J］.新型工業(yè)化，2014，4（3）：70-73. LIU D，LU L，ZHU X F，et al. The design of intelligent vehicle based on MSP430 control［J］.The Journal of New Industrialization，2014，4（3）：70-73.

［4］ 劉詩(shī)韻，黃惠芬.PCB電源板構(gòu)形蜘蛛網(wǎng)電源分配網(wǎng)絡(luò)設(shè)計(jì)［J］.新型工業(yè)化，2011，1（6）：54-64. LIU S Y，HUANG H F.Construct optimization of spider tree for PCB power plane［J］.The Journal of New Industrialization，2011，1（6）：54-64.

［5］ 邱躍龍.集裝箱自動(dòng)化碼頭物流系統(tǒng)規(guī)劃與仿真［D］.武漢：武漢理工大學(xué)，2005.

QIU Y L.Design and simulation of logistics system on automated container terminals［D］.WuHan：Wuhan University of Technology，2005.

［6］ 楊大奔.基于GAAA算法的碼頭集卡優(yōu)化調(diào)度研究［D］.大連：大連海事大學(xué)，2010.

YANG D B.GAAA Algorithm-based optimized dispatch for container thrucks in container terminals［D］.DaLian：Dalian Maritime University，2010.

［7］ SussmannH.A maximum principle for hybrid optimal control problems［A］.The 38thIEEE Conference on Decision and Control［C］.1999：425-430.

［8］ 鄭炳坤，賴乙宗，葉峰.磁導(dǎo)航AGV控制系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)［J］.自動(dòng)化與儀表，2014，29（3）：6-10.

ZHENG B K，LAI Y Z，YE F. Design and implementation of the magnetic navigation AGV control system［J］. Automation and instrumentation，2014，29（3）：6-10.

［9］ 李強(qiáng)，胡澤，葛亮.利用電磁導(dǎo)航的AGV設(shè)計(jì)［J］.現(xiàn)代電子技術(shù)，2012，35（12）：79-81.

LI Q，HU Z，GE L.AGV design using electromagnetic navigation［J］.Modern Electronics Technique，2012，35（12）：79-81.

［10］ Vis I F. Survey of research in the design and control of auto-mated guided vehicle systems［J］. European Journal of Operational Research，2006，170 （3） ：677-709.

Research of Routing Schedule of AGV in Automated Container Terminal and Subject to Time Constraints

WEI Yi1, LIU Xiao-dong2
(1.Department of Power Electronics and Electric Power Transmission, School of Logistics Engineering, Shanghai Maritime Univeristy, Shanghai 201306, China; 2.Department of Electrical Engineering Theory and New Technology, School of Logistics Engineering, Shanghai Maritime Univeristy, Shanghai 201306, China)

Recently, fast development of logistics automation and automated guided vehicle pointed out the direction to thedevelopment of automated container terminal.AGV path optimization which can improve the efficiency of automated container terminal， reduce the dock transport cost， improve the efficiency of loading and utilization of storage yard has a broad development prospects[1].Aiming at the problem of AGV system route schedule with time constraints， a kind ofrouteoptimization methodwhich is based on cost has been put forwardand the example analysis has been carried on.Last, the solution that scheduling method which make the lowest cost oftransportation within the transport time required has been shown in the instances.

AGV；Time consraints；Route optimization；Cost

10.3969/j.issn.2095-6649.2016.02.007

WEI Yi， LIU Xiao-dong. Research of Routing Schedule of AGV in Automated Container Terminal and Subject to Time Constraints[J]. The Journal of New Industrialization， 2016， 6（2）: 41-45.

本文引用格式：韋燚，劉曉東. 集裝箱自動(dòng)化碼頭AGV 帶時(shí)間約束的路徑規(guī)劃研究［J］. 新型工業(yè)化，2016，6（2）：41-45.