集装箱码头装卸调度仿真优化模型与算法.doc

《集装箱码头装卸调度仿真优化模型与算法.doc》由会员分享，可在线阅读，更多相关《集装箱码头装卸调度仿真优化模型与算法.doc（8页珍藏版）》请在三一文库上搜索。

1、精品论文集装箱码头装卸调度仿真优化模型与算法曾庆成，张笑菊（大连海事大学交通运输管理学院，大连 116026）5摘要：集成优化算法的智能决策机制与仿真模型的评价功能，提出集装箱码头装卸调度仿真 优化法。为提高仿真优化的计算效率，设计基于遗传算法与神经网络的混合优化算法。通过遗传算法搜索装卸调度方案；采用仿真模型评价调度方案；在运行仿真模型前，通过神经网 络模型预测目标函数值，过滤明显劣质解，从而减少仿真模型运行次数，减少模型评价计算10量。最后，通过算例分析验证了模型与算法的有效性。关键词：物流工程；仿真优化；集装箱码头中图分类号：U691文献标识码：ASimulation Optimizat

2、ion Model and Algorithm for15Operation Scheduling Problem in Container TerminalsZeng Qingcheng, Zhang Xiaoju(Transportation Management College,Dalian Maritime University ,Dalian 116026) Abstract: Integrating the intelligent decision mechanism of optimization algorithm and evaluation function of simu

3、lation model, a simulation optimization method for operation scheduling in20container terminals is proposed. To improve the computation efficiency, a hybrid optimization algorithm based on genetic algorithm and neutral network is designed. In this method, loading andunloading sequence is initialized

4、 according to certain dispatching rule; then the sequence is improved by genetic algorithm; and simulation model is used to evaluate objective function of a given scheduling scheme. Before running simulation model, neutral network is used to predict25objective function and filter out potentially bad

5、 solutions, thus to decrease the times of running simulation model. Numerical tests show that simulation optimization method can solve the scheduling problem of container terminals efficiently. And the proposed hybrid algorithm can improve the computation efficiency of simulation optimization.Key wo

6、rds: Logistics engineering; Simulation optimization; Container terminals300引言随着集装箱港口吞吐量的迅速增加，码头内作业调度的复杂性随之增加，需要与之相适 应的调度模型与方法支持。为此，国内外学者针对集装箱码头调度问题开展了大量的研究， 总结起来，可以分为数学模型与仿真模型两方面。35在数学模型方面，国内外研究人员针对作业系统各环节建立了优化模型并设计了相应的 优化算法，主要包括：装卸桥调度模型1- 3、集卡调度与路径优化4、龙门吊配置与调度模 型5- 8、堆存优化模型9- 10等。为反映各环节之间的关系， Bish1

7、1同时考虑将装卸桥作业 顺序、车辆调度与堆存位置选择问题；chen12建立了装卸调度中各环节整体优化模型，并设 计了基于禁忌搜索算法的求解方法；康海贵13同时优化装卸中龙门吊与集卡的模型。这些40方法提高了调度的整体性，但是，如何有效处理各种约束条件和复杂的相互关系；如何提高 模型求解效率，一直是其中没有得到较好解决的难题。集装箱码头作业调度问题涉及众多的变量与约束条件，解析模型在处理模型与计算的复 杂性方面，尤其在考虑系统不确定性与随机因素时，常常面临或模型过于简化、或计算过于基金项目：高等学校博士点基金（20092125120001）作者简介：曾庆成（1978-）男，教授，主要研究方向：系

8、统仿真与优化. E-mail: - 8 -复杂的问题。因此，仿真模型被应用于集装箱码头作业调度问题。如 Maurizio14建立了集装45箱码头作业系统仿真模型，为装卸作业调度提供决策支持。张海霖15借鉴柔性制造系统生产调度问题的研究方法，利用 WITNESS 仿真工具对比了两种集装箱集疏运调度模式。张 婕姝16建立了集装箱码头生产调度计算机仿真模型，对调度方案进行评价选择。通过仿真可以对调度方案的结果进行评价，但仿真模型自身不提供优化搜索功能，需要 手动变化输入后运行仿真模型寻找更优的调度方案。因此，本文集成优化算法与仿真模型，50提出集装箱港口装卸调度仿真优化法，以增强仿真的智能决策机制、

9、解决传统优化方法无法 处理复杂系统模型描述的问题，为提高仿真优化的计算效率，设计基于遗传算法与支持向量 机的混合优化算法。1装卸调度优化模型集装箱码头装卸作业可以分为三个阶段，如对于出口集装箱，在堆场内龙门吊将集装箱55装上集卡；集卡完成集装箱从堆场至岸边的运输；在岸边，集装箱由装卸桥装至船上。因此,可以将集装箱码头装卸作业视为三级的 flow shop 问题，建立改进混合流水线模型。以 N 表示装船或卸船集装箱(作业任务)的集合； n 为集装箱的数量；i, j 分别表示第i, j 个集装箱； s = 1,2,3 为阶段编号； m 表示设备种类编号； M is 表示第 s 阶段作业设备的集合，

10、 ms 表示其数量； Em 表示可能在设备 m 上作业的集装箱集合； B 表示具有先后顺序60约束的集装箱对，例如：集装箱 i 要先于集装箱 j 作业； pis 表示集装箱 i 在 s 阶段的作业时 间； wijs 表示 s 阶段 集装箱 i 与 j 之间的作业准备时间； G 为一足够大的常数。当 s 阶段集装箱 i 由设备 m 作业时， xism = 1, 否则 xism = 0 ；当 s 阶段集装箱 i 与 j 由同一设备 m 作业时， yijsm = 1 , 否则 yijsm= 0 ；当 s 阶段集装箱 i 与 j 是前后连续的作业任务，并且由同一设备 m 作业， zijsm = 1 ,

11、 否则 zijsm = 0 ； tis 表示 s 阶段集装箱 i 作业开始时65间； Cm a x 表示完成最后一个集装箱作业的时间。于是，模型可表示为：min Cm ax = max( tis + pis )(1)s.t. xism = 1 ,mM is i N , s 1,2,3(2)tis 0 ,i N , s 1,2,3(3)tis + pis ti ( s +1) ,i N , s 1,2,3(4)70yijsm = y jism ,i, j Em , s 1,2,3, m M ij(5)yijsm 0.5( xism + x jsm ) yijsm + 0.5 ,i, j Em ,

12、 s 1,2,3, m M ij(6) zijsm 1 ,jEm z jism 1 ,jEmi Em , s 1,2,3, m M iji Em , s 1,2,3, m M ij(7)(8)xism 0.5( zijsm + z jism ) xism - 0.5 ,i, j Em , s 1,2,3, m M ij(9)75ti ( s +1) + sijs t js + H (1 - zijsm ) ,i, j Em , s 1,2,3, m M ij(10)tis t js ,i, j B, s 1,2,3(11)xism , yijsm , zijsm = 0,1(12)式(1)为目

13、标函数，目的是使总作业时间最小；式(2)保证每个集装箱在每阶段由一台设 备完成；式 (3)保证所有集装箱作业开始时间均在系统开始作业之后；式(4)定义了每个集装80箱在不同阶段作业开始时间的关系；式(5)-(6)保证当 xism = x jsm = 1 时， yijsm = y jism = 1 ； 式 (7)-(8)保证在每台设备作业序列中，每个集装箱最多有一个前序作业任务与后续作业任务； 式(9)定义了两个作业任务之间的关系； 式(10) 定义了每个作业任务得开始时间；式(11) 定义了有优先顺序的集装箱对； 式(12) 是变量取值约束。 目前的研究表明，两阶段的混合流水线问题属于 NP-

14、hard 问题，式(1)-(12)所示的调度模85型同样属于 NP-hard 问题。随着问题规模的增加，在有效的计算时间内很难获得精确的最优 解，因此启发式算法广泛应用于求解其近似最优解或满意解。由于约束条件众多，而且连续 的两个设备之间没有缓冲，在计算每个调度方案评价值时需要计算装卸桥、集卡与龙门吊的 等待与延误时间。同时作业中存在多种随机因素，如设备故障、作业时间变化等。因此，准 确合理地获得每个调度方案的评价值比较困难。本文集成优化算法与仿真模型，利用解决方90案评价的问题，同时利用优化算法提高仿真的智能性。2仿真优化模型集装箱港口装卸调度仿真优化模型如图 1 所示，此模型包括两个相对独

15、立的模块，仿真 模块与优化模块。优化模块用于搜索调度方案、优化仿真模块的输入参数；仿真模块用于获 得调度方案的评价值。当优化模块运行时，由优化算法产生一系列可行设计变量，通过数据95接口输入到仿真模块；仿真模块利用这些输入信息调整仿真参数，运行仿真后将仿真结果返 回到优化模块；优化模块根据仿真结果调整搜索最优解的方向。通过反复循环获得最优的设 计变量与调度方案。初始化调度方案调度优化模块启发式算法调度仿真模块输入变量与参数运行仿真输出仿真结果是 更新当前最优解是否优于上次 结果?否满足结束准则 ?否是输出仿真优化 最优调度方案图 1 集装箱港口装卸调度仿真优化模型100105110115Fig

16、.1 Simulation optimization model for operation scheduling problem in container port在仿真优化模型中，初始化调度方案就是初始化集装箱装卸顺序。在装卸的每个阶段， 分别按照一定的分配规则配置作业设备。在装卸作业的第一阶段，根据 FAM (first availablemachine)规则，分配集装箱给最早空闲，即最先完成已分配任务的设备。由于存在阻塞约束， 集装箱在某阶段完成作业后必须尽快转移到下一阶段，因此，集装箱在第 2-3 阶段的分配采用先到先服务(FCFS, first come first served)

17、。以 Arena 仿真软件作为仿真开发平台，Arena 集合了高层仿真器的易用性与仿真语言的 灵活性，同时可以与 Visual Basic 和 Visual C+很好进行集成，增强建模能力。以 Visual Basic6.0 作为仿真优化的集成环境，优化算法程序采用 Visual Basic6.0 编写，仿真模块基于 Arena7.0 开发，以 Visual Basic 程序控制仿真模块的运行与参数、输出结果。3混合优化算法3.1算法流程在仿真优化过程中，运行仿真模块需要大量的时间，因此，计算耗时是仿真优化面临的 主要问题之一。本文设计基于遗传算法(GA)与神经网络(NN)的混合优化算法，通过

18、遗传算 法搜索装卸调度方案；采用仿真模型评价调度方案；在运行仿真模型前，通过 NN 预测目标 函数值，过滤明显劣质解，从而减少仿真模型运行次数，减少模型评价计算量。算法流程如 图 2 所示：初始化种群(装卸顺序)运行仿真模块，计算每个 染色体的适应函数是否满足 结束准则?是最优解否选择、交叉与变异操作由 NN 预测适应函数(目标函数, f(x)NN 训练f(x) - f(x*)d是放弃 x否运行仿真模块调度方案的评价结果图 2 基于混合优化算法的仿真优化法流程120125130Fig.2 Flow chart of simulation optimization based on hybrid

19、 optimization algorithm在优化过程中，通过神经网络获得目标函数预测值 f ( x) ，同时过滤掉明显的劣解。如 果 f ( x) - f ( x* ) d ，放弃解 x ；否则计算目标函数值 f (x) ，继续 GA 的当前循环，其中 x* 为当前的最优解，d 的取值决定了预测误差，d 越大，算法收敛速度快，但精确性较低。在仿真优化的初始阶段，没有训练 NN 的样本数据，此时不启动 NN 的预测功能，随着搜索过程的继续，反馈到 NN 中的训练样本不断增加，NN 也得到不断训练，当 NN 训练满 足预测要求时，启动或触发 NN 的预测与过滤功能。3.2遗传算法主要操作步骤(

20、1) 编码方式。编码方式不同影响遗传算子的运算方法，同时影响运行效率。采用十进 制对染色体进行编码，每个染色体代表一个装卸序列，染色体中每个正整数代表一个作业任 务(集装箱)。(2) 初始种群的生成。分别采用两种启发式算法获得初始装卸顺序，即 LPT (longestprocessing time)，SPT (shortest processing time)。LPT 规则将所有集装箱按照总作业时间升序 排列；而 SPT 规则将所有集装箱按照总作业时间降序排列。首先利用 LPT 或 SPT 规则产生一 初始解，然后随机两个集装箱进行交换，产生 M 个体，组成初始种群。(3)适应值计算。适应函数

21、表明个体或解得优越性，对于本文求解最小值问题，目标函数值 C m a x 到搜索空间中对应个体的适应函数值得转化方法可以表示为：F ( x) = CM - Cm ax(13)135其中 CM 根据问题的规模设定，保证 F ( x) 0 。(4) 选择操作。选择操作就是确定如何从父代群体中按照某种方法将个体遗传到下一代群体的一种遗传运算。父代中的个体 x i 被选择的概率 p( xi ) 为：p( xi ) =F ( xi )M F ( xi )i =1, i = 1,2,.,M(14)140145(5)交叉操作。采用单点交叉算子，在个体编码串中以交叉概率 pc 随机设置一个交叉点， 继承一个父

22、体交叉点左侧的基因，从另一父体按照从左到右的顺序以满足基因不重复的原则 获得剩余基因。(6)变异操作。以变异概率 pm 随机选择染色体中两个基因，然后对其进行交换。(7)结束准则。分别设定不同的结束时间作为混合优化算法的结束准则，达到设定时间 后算法循环终止，以便于比较算法改进前后的计算效率。3.3神经网络设计本文采用基本的 BP 神经网络(如图 3 所示)，网络包括输入层、隐含层与输出层。其学 习过程由正向传播和反向传播两部分组成，正向传播是输入模式从输入层经隐层处理传向输 出层； 反向传播是误差信号从输出层向输入层传播并沿途调整各层连接权值及各层神经元 的阈值，以使误差信号不断减小。SET

23、1SET2.SET3.PCmax输入层隐含层输出层150155图 3 BP 神经网络结构Fig.3 Structure of neutral network输入单元数为 4，为定义输入单元，引入“准备时间”概念。准备时间是在每个阶段， 每台作业设备从完成某作业任务到可以开始下一作业任务所需要的最小时间。因为在集装箱码头作业中，存在集卡、龙门吊与装卸桥的空驶，如集卡将装船集装箱运至岸边后，要空驶回堆场进行下一次作业，这里将此时间定义为准备时间。假设 SETijs 表示在 s 阶段，集装箱 i, j间的准备时间，那么，根据给定的装卸顺序可以计算出每个阶段的总“准备时间”：SETs =SETijs

24、， i i , jNj, s = 1,2,3(15)同时，定义：N3P = pis(16)i =1s=1160于是，4 个输入单元分别是 SET1，SET2，SET3 和 P。输出单元数设为 1，即总作业时间 Cmax。利用 Levenberg-Marquardt 回传函数训练网络， 隐含层单元数设为 7，学写速率为 0.1，精度为 0.02，经过 60 组数据训练 2000 次后启动 NN165170175180185的预测与过滤功能。4算例分析首先，在基于“作业线”的方式下验证仿真优化法的有效性，在基于“作业线”的调度法情 况下，集卡不能在不同“作业线”之间动态分配，集卡在将进口集装箱运到

25、堆场后只能直接空 驶返回固定的装卸桥运送下一集装箱。对比四种基于遗传算法的仿真优化算法，其中 GN-LPT, GN-SPT 为本文设计的混合优化算法。(1) GN-LPT：应用 LPT 规则产生初始解；采用 GA 算法搜索解空间；NN 预测目标函 数、过滤劣解。(2) GN-SPT：应用 SPT 规则产生初始解；采用 GA 算法搜索解空间；NN 预测目标函数、过滤劣解。(3) GA-LPT：应用 LPT 规则产生初始解；采用 GA 算法搜索解空间。(4) GA-SPT：应用 SPT 规则产生初始解；采用 GA 算法搜索解空间。假设有 3 台装卸桥、2 台龙门吊与 3 辆集卡进行卸船作业；装卸桥

26、、龙门吊作业时间分别服从 U(100,150) s 与 U(40,70)s 的标准分布；堆存位置由程序随机产生，由堆存位置决定 集卡的运输时间。假设装船集装箱数量为 400，计算时间分别设置为 60，90，120 分钟，种 群数量为 50，程序在 IV 1.7GHZ CPU，512MB 内存的计算机上运行，结果如表 1 所示：表 1 表明，四种算法获得的解与初始方案相比都有明显的提高。当计算时间设定为 60，90 分钟时，GN-LPT 与 GN-SPT 获得的解优于 GA-LPT 与 GA-SPT 获得的解；当计算时间 设定为 120 分钟时，二者之间没有明显的差别。这是在算法 GN-LPT

27、与 GN-SPT 中，由于加 入了 NN 的预测与过滤功能，减少了仿真运行次数，减少了计算时间。GN-LPT 与 GN-SPT 相比，求解质量较高，这说明初始解影响算法的求解质量。表 1 不同仿真优化算法结果对比Tab.1 The comparison between two simulation optimization algorithms仿真优化结果：Cmax (分钟)算法Cmax (分钟)计算时间(60min)计算时间(90min)计算时间(120min)GN-LPT357.16GN-SPT368.83GA-LPT357.16GA-SPT368.83306.40306.14306.09

28、307.27306.93306.84326.74310.84305.57331.56314.02306.48190其次，利用所设计的仿真优化模型对比基于“作业线”与基于“作业面”的两种调度方 法，在“作业面”方式下，集卡不再为固定的装卸桥服务，而是根据现场作业任务实时分配。假设卸船集装箱数为 400，基于 GN-LPT 算法进行仿真，结果如表 2 所示。从表 2 可以 看出，基于“作业面”的调度方法可以降低总作业时间，提高集卡利用率，因为在此方法下， 集卡可以在不同“作业线”间共享，因此在集卡数量相同情况下可以降低装卸桥与集卡的等 待时间。另外，基于“作业面”的调度法较基于“作业线”的调度法计

29、算时间长，这说明了 基于“作业面”的调度法相对复杂。表 2 不同作业调度法的对比Tab.2 The comparison between different scheduling schemes调度方法Cmax (分钟)装卸桥利用率 (%)集卡利用率 (%)计算时间 (min)基于作业线306.4090.4072.8760基于作业面290.1895.3383.541101952002055结论本文研究集装箱港口装卸调度问题，建立了仿真优化模型；为提高计算效率，设计了混 合优化算法；最后，应用算例验证了模型与算法的有效性。计算结果表明混合优化算法可以 提高仿真优化的计算效率；同时，不同获得初始解

30、的方法对算法结果具有较大的影响。由于 本文建立的调度模型同时考虑装卸桥、集卡、龙门吊的作业序列问题，因此与分别优化各环 节的模型相比可以提高作业中各环节的协调性与整体作业效率。仿真优化考虑了作业中的不确定与随机因素，同时可以处理调度模型中复杂约束条件， 因此可以更有效处理实际调度问题。仿真优化法主要的问题之一是计算时间长，本文设计的 混合优化算法在很大程度上提高了计算效率，但仍需要通过进一步提高计算效率。另外，本 文中第 2-3 阶段分配规则采用“先到先服务”的准则，进一步研究可以采用加强学习算法获 得系统在不同状态下应采取的分配准则。参考文献 (References)210215220225

31、2302351 Kim Kap Hwan. A crane scheduling method for port container terminalsJ. European Journal of operational research,2004, 156, 752-768.2 Daganzo Carlos F. The crane scheduling problem, Transportation Research Part B, 1989, 23, 159-175.3 Lee Der-Horng, Wang Hui Qiu, Miao Lixin. Quay crane schedul

32、ing with non-interference constraints in port container terminalsJ. Transport Research Part E (2006), doi:10.1016/j.tre.2006.08.001.4 Nishimura Etsuko, Imai Akio, Stratos. Yard trailer routing at a maritime container terminalJ, TransportationResearch Part E, 2005, 41, 53-76.5 Kim Kap Hwan, Lee Keung

33、 Mo, Hwang Hark. Sequencing delivery and receiving operations for yard cranes in portcontainer terminalsJ. International Journal of Production Economics, 2003, 84, 283-292.6 Linna Richard, Liu Ji-yin, Wan Yat-wah. Rubber tired gantry crane deployment for container yard operationJ. Computers & Indust

34、rial Engineering 2003, 45, 429-4427 Ng W.C. Crane scheduling in container yards with inter-crane interferenceJ. European Journal of OperationalResearch 2005,164,64-78.8Zhang Chuqian, Wan Yat-waha, Liu Jiyin. Dynamic crane deployment in container storage yardsJ. Transportation Research Part B 2002, 3

35、6, 537-555.9 Zhang Chuqian. Storage space allocation in container terminalsJ. Transportation Research Part B,2003,37(10): 883-90310 Kim K H. Park Kang Tae. A note on a dynamic space-allocation method for outbound containersJ. European Journal of Operational Research, 2003,148(1): 92-101.11 Bish Ebru

36、 K. A multiple-crane-constrained scheduling problem in a container terminalJ, European Journalof Operational Research, 2003,144(1): 83-107.12 Chen Lu, Bostel Nathalie, Dejax Pierre et al. A tabu search algorithm for the integrated scheduling problem of container handling systems in a maritime termin

37、alJ, European Journal of Operational Research,2007,181(1):40-58.13 康海贵, 周鹏飞. 集装箱船舶装卸作业时起吊设备_车辆的规划研究. 大连理工大学学报, 2006,Vol. 46,No. 3 372-37914 Maurizio Bielli, Azedine Boulmakoul et al. Object oriented model for container terminal distributed simulation. European Journal of Operational Research 2006, 175,1731-1751.15 张海霖, 江志斌, 许泓. 集装箱港口集疏运调度系统作业模式的仿真分析. 上海交通大学学报. 2006,40(6)1024-1030.16 张婕姝. 集装箱生产调度仿真模型. 上海海事大学报.2005,26(2)42-46