基于启发式算法的自动化跨运车作业调度

尧雨琴,胡志华

(上海海事大学物流研究中心,上海 201306)

基于启发式算法的自动化跨运车作业调度

尧雨琴,胡志华

(上海海事大学物流研究中心,上海 201306)

针对自动化集装箱码头自动化跨运车(automated straddle carrier,ASC)的调度问题,首先建立混合整数规划模型,基于ASC可以独立完成集装箱在岸边和堆场之间的运输作业这一特性,将自动化集装箱码头ASC的作业调度问题转化为同时取货送货问题,并提出一种先完成先执行(first finished first insert,FFFI)启发式算法进行求解,实现集装箱任务分配,确定ASC的作业序列,计算每辆ASC的使用率.最后,通过改变集装箱任务数和ASC数量验证该算法的有效性和可行性.

自动化集装箱码头;自动化跨运车;先完成先执行启发式算法;同时取货送货;调度

随着世界经济的快速发展,集装箱运输方式得到广泛使用,推动了国际贸易量的上升,促进了集装箱港口吞吐量的高速增长.为了提高集装箱码头的运作效率,各大集装箱码头都在建设实施自动化集装箱码头.在卸船作业中,船舶首先停靠在码头为其分配的泊位处,需要卸载的集装箱由岸吊从船舶上拾取至岸桥下岸边的临时堆存区;自动化跨运车(automated straddle carrier,ASC)从岸边堆存区拾取集装箱后运输到堆场,并卸载至堆场特定箱区的特定存放位置.集装箱装船作业的顺序与卸船作业相反.集装箱码头的导航系统要求ASC沿着指定的电磁轨道行进,在碰撞检测等安全和可靠性保证的技术下进行作业.ASC和自动导引车的调度问题类似,二者都是在自动化码头进行作业的无人操作的运输工具.但是ASC运输集装箱时不需要其他设备的辅助,可以独立完成集装箱的运输,具有控制简单的灵活性.本工作针对ASC作业工艺下的作业调度问题,基于ASC可以独立完成集装箱在岸边和堆场之间运输作业的独立性,将ASC的作业调度问题转化为同时取货送货路径问题.

在作业过程中,岸桥和场吊等垂直作业设备、ASC和自动导向车(automated guided vehicle,AGV)等水平作业设备通过调度优化减少设备等待时间,提高码头作业效率.就调度优化问题,Cao等[1]针对集装箱码头堆场卡车和堆场桥吊装载作业的调度问题,建立混合整数规划模型.Homayouni等[2]对自动化集装箱码头的运输设备和存储设备建立整数规划模型,使用遗传算法求解.Gelareh等[3]考虑调度模型的复杂性,基于拉格朗日松弛方法,设计启发式算法求解.梁承姬等[4]将集装箱任务的装卸过程看作岸桥装卸、集卡运输和场桥装卸的三阶段混合Flow Shop调度问题,建立以装卸任务完工时间最小化为目标的混合整数规划模型.

目前常见的水平作业设备有集装箱拖挂车、AGV、ASC等,其中集装箱拖挂车和AGV一般只能完成水平作业,无法直接从地面取走集装箱或将集装箱放置于地面;然而ASC可以直接取走集装箱或将集装箱放置于地面.针对ASC的调度问题,Yuan等[5-6]研究了当ASC在堆场进行运输作业时,综合ASC的路径和任务分配问题建立数学模型.Skinner等[7]用遗传算法求解模型,更加有效地提高了集装箱的装卸效率和ASC使用率.Cai等[8-10]利用基于精确算法的分支定界法和列代法求解自动跨运车的调度问题,建立了不确定条件下ASC调度的多目标规划模型.

基于ASC独立作业的特性,可将ASC的调度问题转化为同时取货送货问题.针对同时取货送货问题,Montan´e等[11]使用禁忌搜索算法对同时取货送货车辆路径问题进行求解.Zhao等[12]考虑有取送货的旅行商问题,并且用混合遗传算法进行求解.姚锦宝等[13]用改进的蚁群算法对同时取货送货车辆路径问题进行求解.贾方方等[14]利用改进的粒子群优化算法对同时取货送货车辆路径问题进行求解.Zachariadis等[15-16]提出一个基于禁忌搜索和导引式局部搜索的混合式启发式算法求解同时取货送货问题.

本工作研究了自动化集装箱码头自动化跨运车的作业调度问题,基于ASC独立作业这一特性,将ASC的作业调度问题转化为同时取货送货问题,提出先完成先执行(first finished first insert,FFFI)启发式算法进行求解,对任务进行分配并确定每辆ASC的作业序列.最后通过改变ASC数量、任务数论证所提出算法的有效性.

1 问题描述

随着科学技术的快速发展和劳动力成本的提高,自动化码头得到重视.目前,中国各大港口已开展自动化集装箱码头的建设,已经建有数十个不同规模的自动化集装箱码头.由于ASC的作业工艺和作业系统具有易于实施和控制的特点,已在澳大利亚布里斯班等多个集装箱码头得到推广应用.本工作考虑基于ASC的自动化集装箱码头的作业工艺,将ASC的作业调度问题转化为同时取货送货问题.

图1是基于自动化跨运车的自动化集装箱码头平面图.在集装箱运输过程中,ASC可以直接取走集装箱或将集装箱放置于地面,不需要其他设备辅助,可以独立完成集装箱在岸边和堆场之间的装卸搬运作业.基于ASC作业工艺的特点,集装箱卸船作业可以看作是一个送货过程,集装箱装船作业是一个取货过程,从而可将ASC的集装箱运输过程转化为同时取货送货问题.在使一定数量的ASC完成现有任务的前提下,本工作以最小化完工时间为目标建立混合整数规划模型,提出FFFI启发式算法求解并确定ASC的作业序列,记录每辆ASC的完工时间,计算ASC的使用率,最后论证所提出算法的有效性.

图1 基于ASC的垂岸式自动化集装箱码头Fig.1 A shore-based ASC vertical container terminal automation

2 模型

2.1 符号

2.2 模型

针对自动化集装箱码头ASC的调度问题,以最小化完工时间为目标建立混合整数规划模型,模型的目标函数与约束条件如下.

目标函数式(1)是最小化完工时间fM.fM是由每个任务的开始工作时间和完成时间决定的(见式(2)).在分配每辆ASC的作业序列时,需要考虑每个任务的开始时间,以免发生时间重叠.对任意跨运车v安排的作业任务序列,如果在完成对任务i的作业后紧接着对任务j作业,即xijv=1,那么要求满足zj>zi+Tij+T,即zj>xijv(zi+Tij+T).线性化后得到式(3).式(4)和(5)约束任务i∈I的开始时间,任务i∈I的开始时间在其预定的最早开始时间后进行(见式(4)).分配给车辆v∈V的任务i∈I在ASC的有效工作时间内进行(见式(5)).对任意ASC和任意非虚拟任务,满足该任务在任务网络中的流约束(见式(6)).通过式(7)约束每个任务只可以由一辆ASC完成,对于任意ASC,从虚拟任务出发到虚拟任务后完成运输,仅负责一个作业序列,约束如式(8)所示.对于每辆车都是从虚拟任务出发到虚拟任务后完成运输,约束如式(9)和(10)所示.

混合整数规划模型中的各种约束条件会导致时间复杂度成立方级数增长,限制了问题的求解规模.混合整数规划模型可以求出最优解,但是在实际运用中并不适宜.基于ASC独立运作的特性,本工作提出FFFI启发式算法对ASC装卸作业任务进行求解.

3 FFFI算法

FFFI算法是一种启发式算法,ASC首先选取最近的集装箱任务来执行,执行完任务的ASC从剩下的任务中选取最近的一个任务,直到完成所有的任务.

N为节点总数,即岸吊的位置以及堆场中的各个存放点和放置点;Q为任务集合, Q={(i,j)|i,j∈N,i≠j};V为ASC的集合;Pv表示ASC的初始位置;Cij表示任意两点之间的距离,并且用直角距离进行计算;Cij=|Xi−Xi|+|Yi−Yi|,∀i,j∈N,i≠j;Sv为每辆ASC的作业序列;Ev为ASC当前的位置;Op是任务p的集装箱存放点;Cp是任务p的执行时间;Dv为车子v的完工时间;CSO(v,p)为车子v完成任务p后的时间.

步骤4如果未完成任务集非空,转到步骤2.

FFFI算法的时间复杂度为O(n2),空间复杂度为O(n);混合整数线性规划(mixed-integer linear programming,MILP)的约束条件较多,其时间复杂度为O(6n3),空间复杂度为O(2n).时间复杂度、空间复杂度会限制问题的求解规模.对比MILP和FFFI算法可知,FFFI算法的求解规模更大,执行时间更短,有效性更好.

4 算例

4.1 实验设计

表1是所设计的同时取货送货问题实验场景.有8个集装箱运输任务,任务的具体信息如表2所示.图2是取货送货布局,其中编号1～10是堆场中的10个存放集装箱的位置,编号11～20是岸吊下的集装箱存放区.将自动化集装箱码头的装船任务看作送货,卸船看作取货,则自动化集装箱码头的ASC作业调度问题转化为同时取货送货问题.

表1 实验场景Table 1 Experimental scenario

表2 任务数据集Table 2 Tasks’data set

图2 取货送货布局Fig.2 Pickup and delivery layout

图3 结果数据集Fig.3 Results’set

图4 ASC的作业序列Fig.4 ASC’s sequence

图5 ASC的使用率Fig.5 ASC’s usage

表3 结果数据Table 3 Results’data

图6 实验3求解的ASC使用率Fig.6 ASC’s usage of Experiment 3

(1)在实验1中,对如图2所示的8个任务集用一辆集卡进行运输的同时取货送货的问题,用任意方法对同时取货送货问题进行求解,得到的结果如图3所示.用FFFI算法进行求解得到的集卡的作业序列为1—2—5—3—6—4—8—7,距离为71 m;由图3得出的结论是完成所有任务后集卡行驶的距离最小值为71 m,最大值为110 m.该结果与通过FFFI算法得到的结果一致,二者结果对比可以充分说明FFFI算法的有效性.

图7 实验4求解的ASC使用率Fig.7 ASC’s usage of Experiment 4

(2)实验2将自动化集装箱码头的ASC作业调度问题转化为同时取货送货问题,用启发式算法对自动化集装箱码头的自动化跨运车作业调度问题进行求解,得到的ASC的作业序列如图4所示,每辆ASC的使用率如图5所示.表3是对ASC的完工时间、作业序列、使用率的统计数据.由图5可得出结论,ASC的使用率较高,都在80%以上,论证了所提出算法在实际问题中应用的有效性.

(3)通过改变任务总数得到不同ASC的使用率如图6所示.从图6中可以看出,不同任务数下ASC的使用率在85%～100%之间,大部分在90%以上,可见ASC的使用率是比较高的,说明所提出算法非常适用于实际问题,对大规模的任务进行分配时也是有效的.

(4)改变ASC的数量,在任务总数为200的情况下,各个ASC的使用率如图7所示.从图7可以清楚地看出,ASC使用率基本都在90%以上,这些数据充分说明了所提出算法在实际问题中具有效性.

根据以上4种实验可以得到结论,在不同情景、不同规模下应用FFFI算法求解得到的ASC的使用率均较高,充分论证了FFFI算法在自动化集装箱码头ASC调度问题应用中的有效性.

5 结束语

本工作针对自动化集装箱码头的自动化跨运车的作业调度问题,建立了混合整数规划模型,将作业调度问题转化为同时取货送货问题,并提出FFFI算法进行求解.首先,对同时取货送货问题进行求解,并且对FFFI算法进行论证,对实验数据进行统计分析所得到的结论,证明了FFFI算法的高效性;然后,将自动化集装箱码头的自动化跨运车作业调度问题转化为同时取货送货问题进行求解;最后,对不同规模下的作业调度问题进行求解,证实了FFFI算法在实际问题中应用的有效性和可行性.但是,在求解过程中没有考虑到各个作业任务的时间限制,未来可以在算法中考虑这方面因素进行更深入的研究.

[1]Cao J X,Lee D H,Chen J H,et al.The integrated yard truck and yard crane scheduling problem：Benders’decomposition-based methods[J].Transportation Research Part E：Logistics and Transportation Review,2010,46(3)：344-353.

[2]Homayouni S M,Tang S H,Motlagh O.A genetic algorithm for optimization of integrated scheduling of cranes,vehicles,and storage platforms at automated container terminals[J].Journal of Computational and Applied Mathematics,2014,270：545-556.

[3]Gelareh S,Merzouki R,McGinley K,et al.Scheduling of intelligent and autonomous vehicles under pairing/unpairing collaboration strategy in container terminals[J].Transportation Research Part C：Emerging Technologies,2013,33：1-21.

[4]梁承姬,张松波.集装箱港口装卸作业设备集成调度[J].辽宁工程技术大学学报(自然科学版),2015, 34(2)：262-266.

[5]Yuan S,Skinner B T,Huang S D,et al.Mathematical modelling of container transfers for a fleet of autonomous straddle carriers[C]//IEEE International Conference on Robotics and Automation.2010：1261-1266.

[6]Yuan S,Skinner B T,Huang S D,et al.A job grouping approach for planning container transfers at automated seaport container terminals[J].Advanced Engineering Informatics,2011, 25(3)：413-426.

[7]Skinner B T,Yuan S,Huang S D,et al.Optimisation for job scheduling at automated container terminals using genetic algorithm[J].Computers&Industrial Engineering,2013, 64(1)：511-523.

[8]Cai B,Huang S D,Liu D,et al.Optimisation model and exact algorithm for autonomous straddle carrier scheduling at automated container terminals[C]//2011 IEEE/RSJ International Conference on Intelligent Robots and Systems.2011.

[9]Cai B,Huang S D,Liu D,et al.Multiobjective optimization for autonomous straddle carrier scheduling at automated container terminals[J].Transactions on Automation Science and Engineering,2013,10(3)：711-724.

[10]Cai B,Huang S D,Liu D,et al.Rescheduling policies for large-scale task allocation of autonomous straddle carriers under uncertainty at automated container terminals[J].Robotics and Autonomous Systems,2014,62(4)：506-514.

[11]Montan´e F A T,Galv˜ao R D.A tabu search algorithm for the vehicle routing problem with simultaneous pick-up and delivery service[J].Computers&Operations Research,2006,33(3)： 595-619.

[12]Zhao F G,Sun J S,Li S J,et al.A hybrid genetic algorithm for the traveling salesman problem with pickup and delivery[J].International Journal of Automation and Computing,2009,6(1)： 97-102.

[13]姚锦宝,夏禾,贺兴东,等.同时取货送货车辆路径问题的改进的蚁群算法[J].技术与方法,2010(S1)： 76-78.

[14]贾方方,孔德成.同时取送货车辆路径问题的改进粒子群优化算法[J].技术与方法,2012,19： 108-111.

[15]Zachariadis E E,Tarantilis C D,Kiranoudis C T.A hybrid metaheuristic algorithm for the vehicle routing problem with simultaneous delivery and pick-up service[J].Expert Systems with Applications,2009,36(2)：1070-1081.

[16]Zachariadis E E,Kiranoudis C T.A local search metaheuristic algorithm for the vehicle routing problem with simultaneous pick-ups and deliveries[J].Expert Systems with Applications,2011,38(3)：2717-2726.

本文彩色版可登陆本刊网站查询：http：//www.journal.shu.edu.cn

Scheduling of automated straddle carrier based on heuristic algorithm

YAO Yuqin,HU Zhihua
(Logistics Research Center,Shanghai Maritime University,Shanghai 201306,China)

For automatic scheduling of automated straddle carrier(ASC)of a container terminal,a mixed integer programming model is established.Considering that ASC can be done in a separate container transport between the shore and yard work independently, this paper turns the ASC container terminal scheduling into a simultaneous pickup and delivery problem,and proposes a first finished first insert(FFFI)heuristic algorithm to solve it.Thus the sequence of ASC is assured.Utilization per ASC is calculated.With the numbers of tasks and ASCs changed,utilization of ASC is calculated to verify effectiveness of the algorithm.

automated container terminal;automated straddle carrier(ASC);first finished first insert(FFFI)heuristic algorithm;simultaneous pickup and delivery;scheduling

U 695. 2;F 252

A

1007-2861(2017)03-0443-09

10.12066/j.issn.1007-2861.1688

2015-06-12

国家自然科学基金青年基金资助项目(71101088);国家自然科学基金面上资助项目(71471109)

胡志华(1977—),男,教授,博士生导师,博士,研究方向为港航与物流运作优化. E-mail：zhhu@shmtu.edu.cn