集装箱自动化码头AGV带时间约束的路径规划研究

韦燚刘晓东

（1.上海海事大学物流工程学院电工理论与新技术系，上海 201306；2.上海海事大学物流工程学院电力电子与电力传动系，上海 201306）

集装箱自动化码头AGV带时间约束的路径规划研究

韦燚1，刘晓东2

（1.上海海事大学物流工程学院电工理论与新技术系，上海 201306；2.上海海事大学物流工程学院电力电子与电力传动系，上海 201306）

近年来，物流自动化发展迅速和自动化导引小车的广泛应用，给集装箱自动化码头的发展指明了方向，AGV路径优化可提高集装箱自动化码头的效率，降低码头运输成本，使集装箱的装卸效率以及堆场的利用率得以大大的提高，具有广阔的发展前景。本文针对带时间约束的AGV系统路径规划问题，提出一种基于成本的路径优化方法，并进行了算例分析，实例求解表明此种调度方法可以在规定运输时间内使运输成本最低。

AGV；时间约束；路径优化；成本

0 引言

随着世界贸易和经济全球化的发展，物流自动化程度的提高，港口在进出口贸易中扮演着越来越重要的角色。集装箱运输成为重要的运输方式，拥有环保、高效、智能化的优越性能的集装箱自动化码头更是今后港口运输的发展趋势。AGV具有并行作业、智能化自动化、和柔性化的特性，因此能够很好的满足港口、码头的搬运要求，被广泛应用在全球自动化和半自动化码头中，降低了运输成本，提高了码头装卸、调度效率及港口竞争力[1-2]。

由上面的分析可以看出，集装箱码头的运输线路问题也是在一些特定的约束条件下在保证完成目的的情况下实现运输的成本最低，就是以追求成本最小化为目标。本文建立混合控制系统模型，提出一种基于成本的带时间约束的AGV路径规划方法，并通过举例验证该方法的有效性。

1 面向带时间约束AGV的路径规划

自动导引小车（automated guided vehicle，AGV）是装有自动导引、以电池为动力的装置，能按指定路径行进，可智能地控制运行动作，具有安全保护装置、启停装置以及搬载功能，因此能很好的满足港口、码头的搬运要求[3-4]。由于其柔性的适应能力，AGV已经成为现代智能港口运输不可缺少的运载工具，是提高港口作业效率的主要因素之一。

1.1 AGV的分类

AGV 按照控制水平来分可以分为以下几种：

1）遥控型：此类AGV 只负责执行上位机给予的控制命令。而AGV 本身不具备任何的智能水平，没有任何的自主判断及决策能力。

2）半自主型：此类AGV 具备一定的智能水平，能够通过自身的感知从而进行基本的信息的决策功能，但是遇到复杂情况时，仍然需要人为进行干预。

3）自主型：按照工作人员预先设置的要求，根据已知的外界环境信息进行规划整理，寻找到最优路径，在前进过程中通过不断地感知信息，重新规划使自己不断进行调整，进而判断决策，能够顺利完成指定任务。

1.2 AGV的导引方式

根据导引方式的不同可以将AGV分为线路导引AGV、非线路导引AGV 两种。线路导引是指在AGV 前进线路上设置导向信息标志，如色带、导引线、电磁导线、磁钉等，通过车上设置的传感器来识别并追踪导向信息前进。非线路导引一般采用坐标定位原理，一边前进一边实时地探测AGV自身所处环境的实际位置。下面介绍几种常用的导引方式。

（1）坐标导引：将AGV 所在的环境区域划分成若干的小坐标区域，通过对小坐标区域的计数实现导引，但此种方法的地面安装量较大，而且精度较低，在精度要求较高时，便不能满足要求。

（2）惯性导引：即在AGV 上安装陀螺仪，在其前进区域内安装相应的定位块，控制器通过计算陀螺仪的偏差信号，采集地面定位块信号来确定AGV 的位置和方向。

（3）电磁导引：电磁导引是使用范围比较广的一种导引方式，它类似于有线导引，即在AGV前进道路的地下铺设金属线，给金属线上加上相应的频率，在AGV 上进行导引频率的解码，从而控制AGV 的前进方向。该导引方式的路线不易更改，其柔性相应较低。

（4）激光导引：激光导引是在AGV 前进道路的周围安装激光反射板，激光反射板定位准确，AGV上通过发射激光束，激光束遇到反射板后发生反射，AGV 通过采集反射回的激光束进行计算，确定当前AGV 的实时位置及其方向。

（5）视觉导引：采用摄像头捕捉AGV 前进区域的环境信息，用微处理器进行图像识别，此种导引技术在军用领域有广泛的研究。

通过以上分析可以看出，不同类型的AGV 对运行路径的规划和优化具有一定的区别，对自主控制能力较强的AGV 来说，其路径的控制主要是由小车本身来完成的，而自主控制能力较弱的AGV 主要依靠地面控制站的路径规划和控制。

在研究集装箱自动化码头小车的调度时，一般分为协调堆场和协调码头前沿的两大种调度类型。该混合控制系统模型研究的是在不同贝位集装箱装卸时的调度问题，为每个AGV寻找合适的路径以及行驶速度，使其满足各自约束条件，以装箱为例。为了研究方便，把码头堆场上的一些设施看成质点以此来构造一个模型[5-6]。在建立混合控制系统模型前，定义一下数学符号意义：

（1）建立有向图G=（V，E），每个顶点v∈V是二维或者三维空间里的一个节点，节点v1到节点v2是一条大致平滑的弧线 e1。

（2）有限集合Δ={1，…，A}是有向图G上AGV的集合，每一台AGV如果小车沿着G上路径行驶，则该小车的坐标由所在弧线坐标给定。

（3）对于自动导引小车α1，其起点坐标为，终点坐标为，从起点到终点的行驶时间为。表示小车起点所处的弧线，表示小车终点所处的弧线，为其行驶路径

所述AGV路径优化控制方法是一种面向时间约束的控制策略，目的是使成本最小化，其具有一定约束条件：每台AGV的行驶时间一定，起始和终点一定，并且在规定的速度范围之内，求解出最小成本消耗的控制策略。

图1 AGV交通网络及初始位置Fig.1 Transpotation network and original position of AGV

2 仿真试验与分析

为了验证AGV路径优化算法的正确性和有效性，用SQP（序列二次规划）求解，对AGV进行仿真试验。两台移动的AGV，分别为α1和α2，从起点到终点有两条路径，如图1（每格代表2海里）：

则可求解得4种模式两台AGV的运行速度（图2、3、4、5）、到规定时间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

当k=1即ρk（1）时，ρ=21.2，两台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 结束语

本文针对AGV待时间约束的特性，建立了AGV小车混合控制系统模型，提出了基于成本的AGV小车路径优化方法，减小了AGVS的成本消耗，并仿真验证了AGV小车混合控制算法的正确性和有效性，能较好较快求解出少量AGV的最低成本消耗，给出最优控制模式。然而其运用范围具也有一定的局限性，具有时间约束和AGV车速约束。随着AGV数量的增大，系统通讯协调过程将会变得复杂，还会带来系统实时性的问题，有待于模型运作机制的进一步改进。

［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控制的智能小车设计［J］.新型工业化，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］ 刘诗韵，黄惠芬.PCB电源板构形蜘蛛网电源分配网络设计［J］.新型工业化，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］.武汉：武汉理工大学，2005.

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

［6］ 杨大奔.基于GAAA算法的码头集卡优化调度研究［D］.大连：大连海事大学，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］ 郑炳坤，赖乙宗，叶峰.磁导航AGV控制系统的设计与实现［J］.自动化与仪表，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］ 李强，胡泽，葛亮.利用电磁导航的AGV设计［J］.现代电子技术，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.

本文引用格式：韦燚，刘晓东. 集装箱自动化码头AGV 带时间约束的路径规划研究［J］. 新型工业化，2016，6（2）：41-45.