PID 控制框架下的集装箱码头调度算法

李 斌, 杨家其

(1. 武汉理工大学 交通学院,武汉 430063;2. 福建工程学院 交通运输系,福州 350108)

PID 控制框架下的集装箱码头调度算法

李 斌*1,2, 杨家其1

(1. 武汉理工大学 交通学院,武汉 430063;2. 福建工程学院 交通运输系,福州 350108)

集装箱码头物流系统(Container Terminal Logistics Systems,CTLS) 的生产调度是具有强约束巨规模 NP-Hard 性质的多目标组合优化问题,一直是理论研究和生产实践的难点和热点.本文将经典的 PID 控制引入到港口的生产调度中,CTLS 内部复杂的层次性、非线性和动态性被转化为较为简单的线性关系,形成了一种新的调度算法,并利用主动时间窗和 PID 控制的变种形式进一步定义了的多种子控制模式,帮助 CTLS 在允许的时间范围内获取计划调度中的高质量的较优解.最后,通过一个大型集装箱码头的生产实例,从通过能力、任务延迟和负载均衡等方面全面评估了所提调度算法的优劣,并给出了相应的结论.

物流工程; 调度算法;PID 控制; 集装箱码头; 负载均衡

1 引 言

集装箱码头物流系统(Container Terminal Logistics Systems,CTLS) 是典型的离散事件动态系统(Discrete Event Dynamic Systems,DEDS) 、分布式控制系统(Distributed Control Systems,DCS) 和大规模并行处理系统(Massive Parallel Processing Systems,MPPS),其单个环节的生产调度往往就已经是 NP-Hard 问题,其集成生产调度更是极难获取最优解,甚至是较优解[1].更为严重的是,当前大多数研究即使能够利用启发式或智能优化算法获取质量较高的满意解,往往也具有以下的限制:①所提出的算法较为复杂,且往往是比较理想情况下面向港口局部环节某种装卸工艺的抽象模型,缺乏实用性和普适性[2];②较为贴近生产实践的算法,往往也是针对单个作业环节,但计算量大,需要较长的机时来获取较优解,难以在不确定环境下动态寻优,周期性调整[3];③主要考虑 CTLS 的通过能力和船舶在港时间,从港口多条作业线并行任务调度、资源动态重构和综合负载均衡的角度去探讨港口装卸生产的研究还较少,对港口作业中表现出的并行性、局部性和动态性特点重视不够[4].

基于电子系统对 CTLS 这样一个机械自动化系统进行建模和优化是较为可行的一条研究路径[5],尤其是在集装箱船舶日益大型化和高速化,要求 CTLS 装卸作业并行度和协调性不断提升的行业背景下.经典的比例-积分-微分(Proportional-Integral-Derivate,PID) 控制对于 CTLS 这种复杂非线性动态随机系统是其应用较为薄弱的领域,然而它在工业控制中已有多年的应用实践积累,具有较为成熟的理论体系和多种修正改良模式,故期望利用 PID 控制将 CTLS 内部调度决策复杂的层次性、非线性和动态性转化为较为简单的线性关系,提出面向 CTLS 并行作业和负载均衡的调度决策算法,以便为 CTLS 的生产计划和控制决策提供敏捷高效鲁棒和具有一定普适性的综合解决方案.

2 面向 PID 控制的调度决策优化模式

2.1 基于 PID 控制的调度决策体系

CTLS 的服务对象主要是各类到港船舶及其载运的集装箱.此外,由于集装箱船舶的船型对港口的作业组织和调度控制影响极大,故也是生产调度时应重点考虑的因素.有鉴于此,以港口生产的核心资源——泊位为讨论中心,面向离散泊位指派(Discrete Berth Allocation Mode,DBAM) 模式,参照PID 控制的形式定义,从各泊位靠离泊船舶数量、装卸集装箱数量和挂靠港船型等三个维度计算泊位 j 的 实 时 作 业 负 载 系 数 (Real-Time Berth Coefficient of Task Load,RBC_TL)Dj(k), 其 定 义如式(1)和式(2)所示.

式(1)在定义 RBC_TL 的同时,其实也给出了基于 PID 控制的 CTLS 调度决策的基本框架,式(2)则是对式(1)中的比例系数进行了归一化处理.式(1)中靠离泊船舶的情况可认为是主要的线性控制部分,即比例控制部分;船舶的最终物流服务是由集装箱的装卸所体现的,故集装箱作业可认为是积分控制;泊位服务的船型从另一个侧面反映了泊位的接待船舶状况,由于处理亲和性和存储局部性等原因,该指标对该泊位未来的服务船舶会具有一定的预见,故是微分控制.

集装箱码头物流服务调度是基于代价和性能的综合调度,其需要一方面考虑 CTLS 对通过能力和任务延迟的性能要求,同时也要兼顾装卸生产时在并行控制和资源重构的服务代价,因此希望各泊位能够负载均衡,即 RBC_TL 达到动态平衡,以获得良好的系统表现.

2.2 基于 PID 控制的调度决策算法

在前述的面向 PID 控制的调度决策框架下,由于其比例控制、积分控制和微分控制部分分别是针对泊位服务船舶的不同属性而由离散动态事件的驱动,实时计算 RBC_TL,这与传统 PID 控制针对单一属性进行计算控制还是有很大的区别和拓展的.故在此基础上,对各个关键服务属性再次应用PID 控制思想,即对比例控制、积分控制和微分控制部分分别应用 PID 控制形式定义,得到基于 PID控制的调度决策算法如式(3)-式(7)所示,其具体调度作业决策框图如图1 所示.该PID控制模式本质是传统的面向离散位置式的PID调度策略(Discrete Positional PID Scheduling Mode) 在 CTLS生产调度中的应用,故以下简称 DS_PID_SM.

图1 面向 PID 控制的集装箱码头调度决策模式Fig.1 Container terminal scheduling mode based on PID control

L1(k) 是从码头泊位接待船舶数量的粒度去看待泊位服务情况.比例项指的是泊位当前是否有正在服务的船舶,其数值定义如式(4) 所示;积分项代表控制周期内该泊位已服务的船舶数量;微分项则是控制周期内正在等待该泊位服务的船舶数量,代表未来该泊位的忙闲状况.

L2(k) 是从码头泊位装卸集装箱数量的粒度去看待泊位服务情况.比例项指的是泊位当前亟需装卸的集装箱负载,其数值定义如式(6) 所示;si表示正在靠泊船舶在本港作业的全部集装箱数量, mi代表当前作业船舶剩余等待服务的集装箱数量;积分项代表控制周期内该泊位已装卸服务完毕的集装箱数量;微分项则是控制周期内正在等待该泊位服务的船舶亟待装卸的集装箱数量,代表未来该泊位的集装箱作业情况.

L3(k) 是从码头泊位服务船型的粒度去评估泊位服务情况.比例项指的是泊位当前服务船舶的船型类别(包括由拖轮正在辅助靠泊,准备作业的船舶的船型类别),如果没有当前服务船舶则为 0;积分项代表控制周期内该泊位已服务船舶的平均级别;微分项则是控制周期内等待该泊位服务船舶的平均级别,代表未来该泊位的大致服务船型类别.

对于上述的 DS_PID_SM,需要格外强调的有如下两点:

(1)与经典 PID 控制不同的是,DS_PID_SM 是通过计算各泊位的 RBC_TL,综合考虑各泊位和设备的负载均衡、任务延迟、通过能力、亲和性和局部性,以动态提高系统作业的并行性和资源利用率为主要目标,而不是简单地寻求系统输出的稳定性(当然也是算法的目的之一).

(2)由于泊位靠离泊船舶数量、装卸集装箱数量,以及服务船型间存在较大的数量差异(对于大型集装箱码头有 103量级甚至更大的差别),故对三个 PID 控制子计算的共 9 个参数,不再进行归一化处理,而只是定义其值在[0,1]之间.

2.3 基于 PID 控制的调度决策子模式

控制周期的长短对于调度决策性能意义重大,直接决定 CTLS 过去和未来作业状况对当前调度影响的广度和深度.于是可将控制周期视为 CTLS调度决策的一个主动时间窗(Active Time Window, ATW),它与传统到港船舶的在港时间窗相对应,是集装箱码头为提高调度效率,主动而有目的选取的一个周期,可以是常数,也可以自适应变化.对于DS_PID_SM,当控制周期与计划周期相同时,将其定义为 DS_PID_SM_PP(计划周期),而当控制周期与计划周期不同时,将其定义为 DS_PID_SM_CP (自定义周期).引进 ATW 后,DS_PID_SM 的控制周期可以依据具体港口配置和作业负载的不同而选取,具有较高的时效性和柔性,更方便 CTLS 根据自身情况进行适当调整,以利于滚动周期计划和控制决策方案的生成,从而更好地应对系统作业过程中的动态性和不确定性.

3.1 实验场景

本节以 AnyLogic 6.9.0 和 SQL Server 2012 为计算实验和仿真分析平台.集装箱码头的平面布局、设备配置及到港船型如文献[5]所述,码头前沿共有7个大型深水泊位.码头投产的第一个完整年度中集装箱班轮到港规律符合爱尔朗8阶分布,码头的月航班密度平均为 166 艘.挂靠港口服务的主要是较大的支线喂给船舶和国际干线主流航运船舶.此外,虽然该集装箱码头主要服务于班轮,但是由于一个集装箱枢纽港往往有多个码头,因此该码头还需要接待因各种情况临时调配到码头进行作业的船舶,在本文的实验中,假设因各种不确定事件而临时调配到该码头的船舶服从正态分布,月均5艘左右.

根据港口实地调研,设置 CTLS 面向不同船型时,各作业环节的耗时(设置在一定的范围内随机波动),亦随机设置各个作业箱的在堆场中的源/目标箱区.分别选取以月(720 小时)、季度(2 160小时) 、半年(4 320 小时) 和 1 年(8 640 小时) 为周期进行四组仿真实验.当采用纯粹平均的随机泊位指 派 策 略 (Average Randomized Berth Allocation Mode,ARBAM) 时,其 VV&A 实验结果如表1 所示.可以看出,该集装箱码头已达到其设计吞吐能力.如果继续采用 ARBAM 策略,增大港口作业负载,以季度为周期,同样每组各进行 100 次试验,其仿真结果如表2所示.

由表2的实验数据可以看出,无论是单独增加航班密度,还是仅仅提升单船装卸箱量,一旦作业负载接近翻番,尤其是挂靠班轮密度增加时,集装箱码头就疲于应付.由于国际贸易间交易量的稳定性,大幅增加单船装卸箱量已不太可能,加强与航运公司的合作,才是当前各大港口重点努力的方向,因此该种负载调整模式也是随后实验的重点.此外,当前集装箱枢纽港经常会面临 200% 的作业负载,因此ARBAM 显然不符合现代港口物流的需求.

表1 VV&A 仿真实验结果Table1 The simulation result for VV&A

表2 性能测试仿真结果__Table2 The simulation result of performance testing

3.2 通过能力分析

基于多处理器计算机操作系统中处理亲和性的理念,融合前述的 PID 调度策略,对 CTLS 进行如下的调度定义:将 7 个泊位进行 5+2 的配备,其中参考文献[5]表1 中的前 4 种船型优先靠泊 6、7号泊位,而超巴拿马的 5 种船型则重点停靠 1-5号泊位,同时依照各泊位服务及待服务的船舶数量对各泊位依据调度算法进行排序,将新到港的船舶分配到负载较轻的泊位中.各类船型进行泊位指派时具有一定的亲和性,但不是绝对的,一旦指定的泊位集合负载过重,就会被指派到其它的泊位进行作业,其中重点针对 1-5 号泊位应用 DS_PID_SM调度策略.

依据上述的港口生产实例,采用不同的负载调整模式,以季度为计算实验周期,各进行 100 次仿真实验.首先面向 DS_PID_SM_PP,随意选取一组参数,进行计算.然后,设置同样的算法参数,控制周期设定为 720.0,面向 DS_PID_SM_CP(以下简称为全参数模式),进行计算.最后,由于工业控制中 PID 控制模式往往会蜕化为 PI 形式,于是将前述 DS_PID_SM_CP 模式简化为一种 DS_PID_SM_ CP(PI形式),同样随意设置一组参数(但与前两种模式参数不同),限于篇幅,仅给出第一组实验的相关数据,如表3所示.

从上述多组实验可以看出,DS_PID_SM_PP 和DS_PID_SM_CP(PI 形式) 的通过能力和吞吐量明显优于 ARBAM,只有 DS_PID_SM_CP(全参数)的性能表现略低于 ARBAM,但是当航班密度增加125%及其以上时,其性能也明显优于 ARBAM.当面向 DS_PID_SM 时,CTLS 的物流服务具有明显的临界点效应,当航班密度从 130%增加到 135% 时,未服务的船舶和集装箱数量激增,系统堵塞现象突然变得十分严重.同时,对于 DS_PID_SM_PP 和 DS _PID_SM_CP(PI 形式) 策略,当负载从 130% 继续增加时,平均服务的船舶数量和装卸箱量非但没有增加,而且有下降的趋势.DS_PID_SM_CP( 全参数)之所以没有出现类似的情况,是因为其调度效果较差,系统能力未充分发挥,但如果继续增加负载,也会出现类似的情况.

表3 面向 DS_PID_SM_PP 的仿真实验Table3 The simulation result based on DS_PID_SM_PP

3.3 综合性能评估

本节面向 DS_PID_SM 调度算法,针对上述仿真实验在任务延迟和负载均衡方面的性能进行分析.首先在航班密度翻倍的情况下,对前述ARBAM 和 DS_PID_SM 共四种调度策略的任务延迟时间进行对比讨论.从各组实验中选取最接近于平均值的一组 数据 (每组大约1030-1050艘 船舶),选取计算实验中作业稳态的500艘船舶,其任务延迟时间如图2所示,可以看出通过能力表现最好的两组策略也是任务延迟状况最好的两组策略,即任意参数下 DS_PID_SM_PP 和 DS_PID_SM_ CP(PI形式)的表现较好,尤其是 DS_PID_SM_CP (PI形式).值得重点提出的还有这两种策略模式下,船舶在港时间被限制在一个较狭窄的区间内,使得船舶的任务延迟能够有较好的预估,这为港口的生产计划带来了很大的便利.此外,在较差的两种策 略 中,DS_PID_SM_CP( 全参数) 也 好 于ARBAM.

图2 航班密度翻倍情况下各种调度策略的任务延迟对比Fig.2 Comparisons on task latency under the conditions of doubling liner intensity

当航班密度增加 125% 时,CTLS 的通过能力尚可以接受,其各个泊位平均的靠离泊船舶数量、装卸集装箱数量和服务船型类别(即 PID 控制的三个维度)分别如图3 和图4 所示.三种调度模式DS_PID_SM_PP、DS_PID_SM_CP(全参数) 和 DS_ PID_SM_CP(PI形式)中的前两种在 PID 控制的三个维度中均表现出了良好的均衡负载性;而 DS_ PID_SM_CP(PI形式)仅在服务船型类别这个维度拥有较好的负载均衡性,而在接待船舶和装卸集装箱数量方面其负载均衡性均较差,这说明 CTLS 作业中的动态均衡性较静态均衡性更为重要(从仿真过程中也可以清楚地看出),但是其综合效果最好,且其服务的船型实现了较好的均衡性,这也从一个侧面证明了服务船型对港口作业的重要性,以及从这个维度去维护泊位负载平衡的必要性,这是DS_PID_SM 一个值得重点关注的特性.

从上述的多组实验和多维分析可以看出,DS_ PID_SM 有望在通过能力、任务延迟和负载均衡等方面全面改善 CTLS 的综合性能.在实验过程中,也可以看出 DS_PID_SM 的一些不足和弊端:

(1)为贴近港口作业的实际情况,在设计与实现计算实验时,在各个调度和作业环节中均包含了一定的随机性处理,同时由于到港船舶的不确定性,使得在仿真模型应用调度算法时,系统性能具有一定的波动性,即未服务的船舶和集装箱数量的标准偏差较大,这使得 DS_PID_SM 调度算法在应用到港口实践中时会欠缺必需的鲁棒性,这是后期需要重点去改进的.

(2)PID 控制的参数整定是其应用的核心问题之一,从仿真实验中就可以看出 DS_PID_SM 的参数设置(13 个参数)及算法的具体模型(如是否可以简化为 PI形式)对于 CTLS 的性能至关重要,如何寻找 DS_PID_SM 的参数组合是下一步需要重点研究的问题.

图3 航班密度 225%情况下各泊位平均通过能力和吞吐量Fig.3 Average traffic capacity and throughout for each berth under 2.25 liner intensity

图4 航班密度 225%情形下各泊位平均服务船型Fig.4 Average service vessel type for each berth under 2.25 liner intensity

4 研究结论

随着当前港航业的服务需要,集装箱船舶在速度和规模上持续升级,带动 CTLS 在装卸工艺和设备配置亦不断跟进,这些对原本就已经高度复杂的集装箱码头生产调度问题在求解规模、约束条件、目标定义和并行控制等方面提出了新的挑战.同时,由于天气、潮汐等不可控因素,以及装卸作业生产过程中的人为原因,相关的不确定性和动态性进一步加剧了在 CTLS 的非线性和复杂性.本文提出的面向 PID 控制的调度决策算法旨在将上述港口作业中的复杂性通过将港口作业关键属性的线性组合转化为一种相对简单的可度量定义,进而在控制决策允许的时间范围内帮助港口调度人员获取高质量的满意解,从而形成敏捷鲁棒的滚动周期型生产计划和实时调度控制方案.

[1] Miguel A Salido,Mario Rodriguez-Molins,Federico Barber. A decision support system for managing combinatorial problems in container terminals[J].Knowledge-Based Systems,2012,29:63-74.

[2] Haipeng Zhang,Kap Hwan Kim.Maximizing the number of dual-cycle operationsofquay cranesin container terminals[J].Computers&Industrial Engineering, 2009,56(3):979-992.

[3] Der-Horng Lee,Jian Gang Jin.Feeder vessel management at container transshipment terminals[J].Transportation Research Part E,2013,49(1):201-216.

[4] Frank Meisel,Matthias Wichmann.Container sequencing for quay cranes with internal reshuffles[J]. OR Spectrum,2010,32(3):569-591.

[5] 李斌,杨家其. 面向负载均衡的集装箱码头生产调度决策[J]. 系统仿真学报,2013,25(9):2222-2229. [LI B,YANG J Q.Modeling and simulation of logistics service scheduling at container terminals with framework of load balancing[J].Journal of System Simulation, 2013,25(9):2222-2229.]

A Scheduling Algorithm for Container Terminals within PID Control Framework

LI Bin1,2,YANG Jia-qi1
(1.School of Transportation,Wuhan University of Technology,Wuhan 430063,China; 2.Department of Transportation,Fujian University of Technology,Fuzhou 350108,China)

The scheduling in container terminal logistics systems(CTLS) is the multi-objective combinatorial optimization problems with strong constraints,giant problem space and NP-Hard difficulty, which is the hot and difficult issue in the theory and practice.The classic PID control thinking is introduced into the scheduling in CTLS.The complex hierarchy,nonlinear and dynamic in CTLS is transformed to be a relatively simple linear relationship that forms the nucleus of a new scheduling algorithm.At the same time, the philosophy of active time window and the variation of PID control are exploited to define the diversified subschema,which assist CTLS to obtain the superb satisfactory solutions in the allowed range of time.At last,the algorithm is performed and evaluated from the perspective of traffic capacity,task latency and load balancing by a case of large-scale container terminal,and the merits are mentioned.

logistics engineering;scheduling algorithm;PID control;container terminals;load balancing

1009-6744(2014)01-0124-07

TP29

A

2013-09-27

2013-10-24录用日期:2013-11-25

国家自然科学基金(61304210);中国博士后科学基金面上资助项目(2012M511695);教育部人文社会科学研究青年基金资助项目(11YJC630089);福建省自然科学基金资助项目(2012J05108);福建省高校杰出青年科研人才培养计划项目(JA122685).

李斌(1979-),男,湖北武汉人,在站博士后,副教授.*通讯作者:mse2007_lb@whut.edu.cn