（计算机软件与理论专业论文）基于资源约束的堆场集装箱出口箱作业调度规划系统.pdf

中山大学硕士学位论文基于资源约束的堆场集装箱出口箱作业调度规划系统 基于资源约束的堆场集装箱出口箱作业规划系统 专业：计算机软件与理论 硕士生：甘纯 指导老师：姜云飞教授 摘要 本文在实际项目的基础上，总结堆场实际出口箱作业的业务流程，提取涉及 到的资源约束和领域规则，将基于资源约束的机器调度和启发式搜索的思想应用 到实际调度规划系统中。 实际问题中没有纯规划也没有纯调度，本文在c r p 问题和调度问题模型的 思想上，给出调度的四个基本要素，建立调度模型，同时分析出集装箱的类型， 给出规划动作集合，给出调度规划系统的模型和启发式求解算法。本文主要分两 个部分工作：出口箱的装船序列和移箱寻堆位。出口箱装船质量影响码头的工作 效率，本文研究在规则指导下如何进行智能化发箱。移箱寻堆位是目前国内外学 者均没有考虑到的一个问题，本文在码头资源约束和时间调度约束的限制下，给 出一次性寻找合适堆位的算法，有效地给实际码头堆场节约了成本，提高了效率。 关键词：集装箱出口作业，资源约束，机器调度，移箱，规划 m 中山大学硕士学位论文 基于资源约束的堆场集装箱出口箱作业调度规划系统 s c h e d u l i n ga n dp l a n n i n gs y s t e mf b ro u t b o u n dc o n t a i n e r sb a s e do n r e s o u r c ec o n s t r a i n t m a j o r ：c o m p u t e rs o 脚a r ca n dt l l e o r y n a m e ：c h u ng a n s u p e i s o r ：p r o f e s s o r l n f c ij i a n g a b s t r a c t m yt h e s i si s f b c i l so nt h es t u d yo fi n t e l l i g e n ts e n d - o u t0 r d e ra 1 1 dt h et u m i n g c o n t a i n e rp l a c eb a s e dt h ea c t u a l s y s t e m m yt h e s i ss u m m a r i z et h eo u t b o u n d c o n t a i n e r sb u s i n e s sn o w - c h a n ，g e t t i n gt h ec o n s t r a i n tr e s o u r c e s 柚di n d u s t r ym l e s i ti s a p p l yt h et h e o r ) ro ft h em a c h j n es c h e d u l i n gb a s e do nr e s o u r c ec o n s t r a i n t 柚dl o c a l s e a r c ht ot h ea c t u a lp l a m l i n gs y s t e m t h e r eh a v en o t ”p u r cp l a n ”p r o b l e mo r ”p u r cs c h e d u l i n 矿p r o b l e mi nt h er e a l w o r l d ，t h et h e s i sw h i c hi sb a s e do nt h ei d e ao fc r pp r o b l e ma n ds c h e d u l i n gp r o b l 锄 m o d e l ，g i v i n gt h ek e ye l e m e n t ，e s t a i b l i s h i n gt h em o d e l ，a n a l ) 亿i n gt h et y p eo fo u t b o u n d c o n t a i n e r s ，百v i n gt h ep l 砌n ga c t i o n ss e t ，b u i l d i n gt h em o d e lo fs c h e d u l i n g 柚d p l a n n i n gs y s t e m ，g i v i n gt h es o l v i n ga l g o r i t h m t h ep i v o t a lt a s ki si n c l u d i n gt w 0 s e c t i o n s t h eo n ep a ni sg i v i n gt h ec a i g os h i p p i n go r d e rb yt h ep r e - s t o w a g ep l a n ，i fi t h 弱t h ep r e - s t o w a g ep l a n a n o t h e rs e c t i o ni s 舀v i n gt h ep o s i t i o nw h e r et h et u m i l l g c o n t a i n e rw o u l dp l a c e 7 i h ec a r 9 0s h i p p i n gq u a l i t ya n de m c i e n c yi si e l a t e dw i t ht h e c o s ta n dr e p o no fd o c k t h es y s t e mi s 酉v i n gt h ei n t e l l i g c n ts e n d o u to r d e ro f o u t b o u n dc o n t a i n e r ，a n df i n i s h i n gt h es t o w a g eo ft u m i n gc o n t a i n e r s ni sas a m p l e i i l t e l l i g e n tp l a n n i n ga n ds c h e d u l i n gs y s t e m0 fo u t b o u n dc o n t a i n e rw o u l ds a v ec o s to f d o c k 觚di m p r o v et h ee f f i c i e n c y k 沁y w o r d s ： o u t b o u n d c o n t a i n e r ， r e s o u r c e c o n s t r a i n t ， m a c h i n e s c h e d u l i n g ， c o n t a i n e r t r a i l s p o s i t i o n ，p l a n n i n gs y s t e m i v 论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进行研究工 作所取得的成果。除文中已经注明引用的内容外，本论文不包含任何其他个人 或集体已经发表或撰写过的作品成果。对本文的研究做出重要贡献的个人和集 体，均已在文中以明确方式标明。本人完全意识到本声明的法律结果由本人承 担。 学位论文作者签名：昔心 日期甜年，月衫日 学位论文使用授权声明 本人完全了解中山大学有关保留、使用学位论文的规定，即：学校有权保留学 位论文并向国家主管部门或其指定机构送交论文的电子版和纸质版，有权将学 位论文用于非赢利目的的少量复制并允许论文进入学校图书馆、院系资料室被 查阅，有权将学位论文的内容编入有关数据库进行检索，可以采用复印、缩印 或其他方法保存学位论文。 学位论文作者签名：甘铀 日期：捌年，月夕平日 导师签 日期：埘年，月群日 中山大学硕士学位论文 基于资源约束的堆场集装箱出口箱作业调度规划系统 1 1 研究的背景 1 1 1 问题的提出 第1 章绪论 随着经济全球化发展，全球集装箱运输快速发展，我国由于经济的迅猛发展， 集装箱的吞吐量也在逐年增加，随着集装箱运输的快速发展，集装箱港口的建设 也有了极大的发展。由于海陆运输工具之间的衔接，以及进出海关的需要，绝大 部分集装箱在装船前或者卸船后均需要在码头存放一段时间，集装箱堆场就是用 来暂时存放这些集装箱。装载集装箱的船舶向大型化、高速化方向发展给港口带 来巨大发展的同时也给码头的堆场和集装箱的调度带来了巨大的压力【3 6 1 。集装箱 港口中的资源主要作业在传统的情况下，调度员根据个人经验和资源状态进行作 业调度，这种方式有多个不足，调度作业和资源使用率依赖于个人经验和熟练程 度，难于协调资源冲突。为了有效地利用堆场资源，尽可能的降低不确定性因素 对堆场的影响，优化和整合码头堆场资源，最大化最优化安排堆场的空间，合理 安排泊位和吊机，以及吸车、渡柜车等稀缺资源就成了码头堆场管理的首要任务， 但是由于系统内外环境和堆放时等不确定性关系的影响，想完美的完成任务又显 得至为困难。而对于小堆场这些问题则更为严重，制约的因素更多，机械设备的 落后以及堆场堆区的范围限制，更加要求智能化和现代化以及经济化的管理后方 堆场和规划稀缺资源的分配。 1 1 2 港口的主要业务介绍 存放集装箱的区间称为堆场，堆场又分前方堆场和后方堆场，前方堆场位于 码头前沿和后方堆场之间，是为了加快装船效率，提前存放需要出口的集装箱， 只是临时堆放，通常不超过半天。后方堆场主要是指存储和保管所有进出堆场的 集装箱，前后方堆场没有严格区分，通常按照地理位置划分【1 8 3 6 1 。全球集装箱的 规格主要分两种，长柜和短柜，主要是根据集装箱的长度区分，集装箱的宽度和 高度是基本统一标准的，一个长柜的长度是短柜的两倍，即一个放置长柜的位置 中山大学硕士学位论文 基于资源约束的堆场集装箱出口箱作业调度规划系统 可以放置两个短柜。图1 1 给出了集装箱码头堆场的一般化空间示意图【3 0 1 。 主要用到的相关业务名词如下： 吊机，是码头的核心，也是最稀缺的资源，用于将集装箱从岸边装到船舶上， 或者从船舶上将集装箱卸到岸边。吊机根据起吊能力和吊臂区分称龙门吊和普通 吊机，龙门吊能够随意的在前后方堆场和船舶之间进行作业，而普通吊机则只能 在前方堆场和船舶之间进行作业。普通吊机也要根据能力和吊臂长度来决定将前 方堆场的集装箱吊至大船上还是小船上。 吸车，是码头的机械设备，用于将集装箱从位置上卸下放置在渡柜车上或者 从渡柜车上提取集装箱至最近的位置，吸车的限制很多，不能任意提取集装箱， 只能提取靠吸车的吸臂最近最高位置上的集装箱。 渡柜车：只在码头内部工作的拖车，承担从堆场到码头前沿的集装箱运输， 渡柜车能放置一个长柜或者两个短柜。通常渡柜车只是承担运输作用，一个集装 箱的移动需要协调渡柜车、吸车资源一起作业。 泊位：在港口内给装卸集装箱的船舶停靠留的位置。 重柜：装有货物的集装箱。 吉柜：未装货物的集装箱。 泊位 前方堆场 后方堆场 闸门 图1 1 集装箱码头堆场空间示意图 2 中山大学硕士学位论文基于资源约束的堆场集装箱出口箱作业调度规划系统 港口的主要作业主要包括：港内车辆的调度，泊位的分配，吊机的分配，堆 场空间的分配。跟集装箱堆场空间相关的作业关系可归纳为5 大类：卸船作业、 装船作业、提箱作业、收箱作业、场内移箱。卸船作业是指船舶到港后，将集装 箱卸下至后方堆场的具体堆位；装船作业是指将在后方堆场中找到需要出口的集 装箱从后方堆场移至前方堆场并装船；提箱作业是指客户根据单据从堆场找到货 柜并出闸；收箱作业是指根据客户需要将需要出口的集装箱从闸门外运进码头堆 场，放置在后方堆场的某个具体位置；而场内移箱则是在四大类作业的执行过程 中产生的，偶尔有客户或者堆场实际需求，则会场内移箱。 1 2 研究的方向 1 2 1 国内外的研究方向 目前关于调度问题主要有两个方面的研究，一个是采用数学的方式，从运筹 学角度给出模型，另一种采用越的方式研究。目前国内外学者对集装箱码头堆 场调度研究分了很多层面和角度，主要是根据码头作业的不同类型来进行研究和 优化资源的分配。主要集中在堆场空间的利用率以及港口内车辆调度的研究【矧。 基于资源约束的规划的研究主要有l b m a nb a n a l 【的将调度和规划问题整合起来， 对时间和资源统一建模的一种规划研究【8 】( m o d e lp l a 皿i n g 觚ds c h e d u l i n g p r o b l e m sw i t ht i m e 锄dr e s o u 觥) ；r e c o u r s e i p p 方法，是用r t m 表示资源的取 值界限，p p 是在图规划的基础上的相对完备的处理数值资源的方法【1 5 】。在实 际项目中调度和规划是紧密联系的，规划和资源调度的结合是目前研究的一个热 点方向【2 1 。但是由于调度和规划的复杂性，调度和规划结合起来目前只是更多的 在理论层面上研究，智能系统远远不能胜任实际复杂情况，只能简化模型来应用 资源约束的思想，实际上彭祥云在文献【3 】中就提出了将资源约束的思想应用到 实际系统中。基于资源约束的问题是基于约束问题的子问题，基于约束的规划的 研究是实现规划的灵活性的必要【5 7 ，3 2 1 。关于堆场的空间利用率研究主要分两个层 次，第一层次是堆场区级分配，包括确定分配给到港船舶的堆场区数和确定堆场 区段中的箱量，第二个层次是箱位级分配，即为每个进场货柜或者移动货柜确定 具体的箱位，大多数研究者集中在第一层次，m 对出口箱用分组堆垛的策略， 在分配空间平衡的约束下，以水平运输距离和堆场吊装成本最小为目标建立了确 3 中山大学硕士学位论文基于资源约束的堆场集装箱出口箱作业调度规划系统 定堆场区段中的箱型6 ，1 2 1 3 ，1 4 1 。而对于第二个层次上的问题求解，王晓在文献 2 8 提出了一种在实际的港口应用中出口箱装船调度算法以及倒箱问题的建模，以及 大连理工大学周鹏飞的博士论文中提出了一种未确定性规划方法，这些都是通过 运筹学从数学规划的方法求解【3 0 1 。但是当运用这些理论到不同的实际问题中时， 在调度的过程中会出现很多不确定性和不完备性，所以很多时候转向研究规划。 国内外用比较成型的算法引入到调度和规划结合系统中来，如粗糙集方法，混合 优化的方法，遗传算法等【2 5 2 9 捌。目前国内外学者主要研究在于减少倒箱率而放 置集装箱，并没有在已经确定移箱的集装箱的堆位放置上面有相关研列2 7 3 5 1 。本 文从实际项目出发，初步探讨出口箱的调度规划以及在任何情况下出现移箱之后 的集装箱的箱位分配问题 1 2 2 本文的研究方向和主要工作 论文是在进行大量实际的小集装箱堆场调研后，针对目前一些小港口的实际 情况，总结堆场集装箱的理货员的人工调度经验和堆场不确定性因素，提取各种 约束资源，研究小堆场环境下基于资源约束的集装箱出口箱调度规划模型，目的 是在出口装船时提供集装箱所在位置，同时根据出口装船规则以及规则优先级找 到最近的吊机，给出一个提单中所有出口箱的出口装船顺序，给出吊机下同时如 果需要额外移箱则根据最少倒箱量原则得出需要移箱的柜子，同时必须根据堆场 码头的集装箱目前存储情况，将需要倒箱的作业在附近搜寻一个空位置一次性放 置，不能多次移动倒箱的集装箱。这样就能减轻人工调度的负担、消除集装箱箱 位的纪录误差、提高堆场利用率、减少不合理的集装箱移动、提高人力资源的工 作效率，降低港口作业的工作成本，提升整个港口的作业能力。 论文在前人的研究成果之上，在实际港口集装箱装卸作业项目基础上，研究 实际集装箱堆场资源的分配和规划，基于资源约束和启发式搜索算法相结合的规 划思想，在资源的分配上采用优先级分派原则，在搜索中通过约束表达引导搜索 的启发式信息，实行规则控制下的启发式搜索，给出出口箱的规划调度次序以及 稀缺资源的分配，提高了出口箱作业的调度效率。并且首次考虑在额外移动箱之 后，额外移动的集装箱应该一次性放置的位置，目前基于堆区的分配主要在于进 口箱的堆区分配，而对于在进出堆场时产生的额外移动箱的放置没有考虑，本文 4 中山大学硕士学位论文 基于资源约束的堆场集装箱出口箱作业调度规划系统 通过领域规则大幅减少搜索空间，同时利用贪婪算法给出近似的最优的解。解决 了实际堆场出口箱在资源约束的情况下的出口调度规划。 1 3 文章结构 本文主要分五个章节，具体结构如下： 第1 章绪论，介绍了本课题提出的背景，给出了港口的主要业务背景知识， 给出目前国内外研究方向，本文的研究方向和主要工作、创新之处以及文章结构。 第2 章介绍本文的资源约束和规划、机器调度的背景知识。主要介绍智能规 划以及规划和调度结合起来的背景知识，同时介绍了需要用到的局部启发式搜索 和贪婪算法思想。 第3 章介绍本文在分析现场和资源的情况下，给出的出口箱作业的模型，主 要包括对出口箱作业流程进行介绍，分析系统涉及到的资源和约束规则，定义问 题，对系统的两部分分别建立模型，给出求解算法。 第4 章给出整个出口箱作业调度系统的实现过程，包括功能模块图、算法、 以及系统设计、详细设计、系统实际应用效果以及与原系统的对比分析结果。 第5 章小结，对本文所阐述的内容进行了总结，并对进一步的研究工作进行 了展望。 中山大学硕士学位论文基于资源约束的堆场集装箱出口箱作业调度规划系统 第2 章基于资源约束的调度规划研究 本章主要介绍解决实际问题需要主要的思想和拟打算采用的算法策略，也根 据实际堆场的简化原则设计了一些实例。 2 1 规划和资源调度 2 1 1 智能规划 智能规划( p l a n n i n 曲对周围环境进行认识与分析，根据自己要实现的目标， 对若干可供选择的动作及所提供的资源限制进行推理，从所给出的初始状态开 始，综合制定出实现目标的规划( p l a n ) 【2 ，4 1 。 智能规划研究的主要目的是建立起高效实用的智能规划系统。该系统的主要 功能可以描述为：给定问题的状态描述、对状态描述进行变换的一组操作、初始 状态和目标状态。智能规划系统能够给出从初始状态变到目标状态的一个操作序 列，其复杂性和所处的环境以及a g e n t 的功能有关。 为了简化规划问题，传统的规划一般都做出如下假设：1 、环境的状态的改 变完全是由a g e n t 的动作的效果造成的，排除了其他可能的影响和干扰。2 、a g e n t 的动作的效果是完全确定的。3 、a g e n t 能够感知环境和它的动作的效果。人们 把具有上述假设的规划问题叫做经典规划问题。 1 9 6 9 年，g r e e n 通过归结定理证明的方法来进行规划求解，并且设计了q a 3 系统【1 0 】，这一系统被大多数的智能规划研究人员认为是第一个规划系统，原因就 在于他是第一个面向现实中的规划问题提出的规划系统；1 9 7 1 年，f i k e s 和n i l s s o n 设计的s t r i p s 系统，在智能规划的研究中具有重大的意义和价值，他的突出贡献 是引入了s t r i p s 操作符的概念，使得原来很神秘的规划问题求解变得明朗清晰 起来【1 1 l ；此后到1 9 7 7 年先后出现了h a c k e r 、w a r p l a n 、i n t e r p u 蝌、 a b s t r i p s 、n o a h 、n o n u n 等规划系统i 4 。 最初的经典规划还有一些细节的约束，例如动作执行的时间是原子时间、瞬 间完成的。但随着智能规划研究日益具有应用性，经典规划中添加不少实用元素， 例如动作可以有瞬间动作和持续动作之分，添加时序和资源约束，具有各种目标 6 中山大学硕士学位论文基于资源约束的堆场集装箱出口箱作业调度规划系统 优化策略等。 经典规划主要包括半序规划，基于逻辑的规划方法，非层次规划方法和层次 规划方法。随着研究的深入，传统的经典规划方法不能满足实际情况的需要，于 是出现了很多非经典智能规划，也称为现代智能规划，主要有图规划、基于启发 式搜索的规划方法、基于逐步细化的分层规划方法、基于约束可满足的规划方法 以及基于模型检测的规划方法等【2 3 1 1 。基于启发式信息的规划系统主要是在当前 智能规划研究领域中无关的启发信息的抽取技术是基于实现目标的动作数量，对 要解决的问题p 放宽到一个比较简单的问题p ，抽取技术就是基于p i 来评估。 b o n e t 提出的向前搜索的一个放宽方法就是将操作的删除边忽略，对于每个状态 s ，得到在放宽了的问题p t 的启发函数j i l ( s ) 就可以作为原有问题p 的启发函数 j l l 卓( 5 ) 的下限，这样j i l ( s ) 就可以作为合适的启发函数作用在原有问题p 上【4 ，2 2 1 。 2 1 2 规划和调度 调度( s c h e d u l i n g ) 是指怎样在有限的时间内利用有限的资源完成一个给定的 动作序列。资源是一种在动作执行过程中需要利用或消耗的实体( 如工具、机器 等) 一个动作可以选择多种可选资源，一种资源也可以分配给多个动作。一个调 度解必须满足一系列约束( 如限期、动作的先后关系，资源的类型和数量、资源 的可用性v 1 6 ，1 7 1 。 上世纪5 0 年代初，欧美国家工程的生产线调度和管理对调度问题的研究提 出了迫切要求，调度问题的研究和智能规划同时，但早期对调度的研究限于数学 方法，直到8 0 年代初c 0 0 k 等理论专家证明，绝大多数调度问题是n p h a r d 问 题，于是寻求智能化的技术解决调度问题，出现了智能调度渊s c h e d u l i n g ) 【9 捌。 随着智能规划的研究成果在实际生产中发挥出巨大的作用，研究者们把已有的算 法改进优化应用在智能调度问题上，在实际问题中规划和调度联系非常紧密，实 际问题中没有纯调度，即任务中需完成的动作集合是已知的，也没有纯规划，即 关于动作的资源分配没有太多的选择，动作的并发和资源共享的情况不多。一个 调度规划有两个部分组成：1 、做什么；2 、何时并且如何做，规划考虑的是做什 么，调度考虑的是何时做和如何做【l 2 j 。规划与调度之间的关系如图2 1 所示。 7 中山大学硕士学位论文基于资源约束的堆场集装箱出口箱作业调度规划系统 做什么何时并且如何做 目标日匝d 嘲作集日圈日调度的规划 图2 1 调度和规划关系 1 、调度问题的模型 一个调度问题的框架主要有以下要素组成：一个资源集合以及他们未来的可 用性；一个需要执行的动作集合和他们的资源需求；一个动作和资源的约束集合 和一个费用函数f 【1 0 1 。一个调度就是找到结果变量的一个实例化使得满足所有的 资源需求和约束，一个最优的调度是使费用函数f 最小化。根据资源的特性、动 作的类型以及资源需求、约束的类型以及调度问题中不确定性的模拟方法，调度 问题可以被分成多种类型1 3 1 1 。 ( 1 ) 从动作方面考虑：调度中的动作a 有资源需求和时间需求。时间表示方 式为起始时间s ( a ) 、终止时间e ( a ) 和执行时间d ( a ) 。s ( a ) 和e ( a ) 有上下界： s ( a ) 【s ，l 加( a ) ，s ，獬( a ) 】，e ( a ) 【绷n ( a ) ，e 一( a ) 】。调度根据动作分成两种类型：抢占 式调度和非抢占式调度。 非抢占式：即动作必须连续执行，不能中断，所用时间为d ( a ) = e ( a ) 一s ( a ) 。 抢占式：即动作可以在分开的一系列时段内执行，即指动作可被中断和恢复， 当动作中断时，释放资源将其分配给其他动作。每个时段所需时间为出( a ) ，总共 所需时间为罗d ；( a ) = e ( a ) 一s ( a ) 。 筒 ( 2 ) 从资源角度考虑：资源分成两类，可重复性资源和消耗性资源。重复性 资源是当动作完成或者中断时，该类资源被释放，没有任何变化。例如在d w r 领域中的起重机【2 】即是重复性资源。可重复性资源r 有总容量q ，和当前时刻t 的使用值z r ( t ) 【o ，q ，】。若动作a 在执行期间需要数量为q 的资源r ，则：在 s ( a ) 时刻，r 的当前值减少q ；在e ( a ) 时刻，其当前值又增加相同的数量。对给定 调度，函数z r ( t ) 称为r 的资源分布。可重复资源可以是离散的也可以是连续的。 特殊的是如果q r = 1 则表示一元的离散资源【2 3 1 。图2 2 表示可重复性资源分布。 消耗性资源是在动作的执行过程中被消耗，如能量、燃料等。消耗性资源可 以是由其他动作产生。该类资源r 有最大容量q ，和当前值乙( t ) 【o ，q ，】。动作 8 中山大学硕士学位论文基于资源约束的堆场集装箱出口箱作业调度规划系统 a 把资源r 的当前值减少q ，如果资源消耗在瞬间完成，可以用一个在时刻s ( a ) 的阶梯函数表示：如果资源消耗在动作执行期间持续完成，则可以用一个在时刻 s ( a ) 的到e ( a ) 的区间的线性函数表示。动作产生q 的数量的资源r 也可以做类似 表示：z r 在e ( a ) 时刻增加q ，或以一个从s ( a ) 的到e ( a ) 的区间的线性函数增加q 。 图2 3 表示消耗性资源分布。 z r r e q u i r e 伽，r ，掣) 二二二= r e q u i r e ( a l 2 ，r ，q 2 ) = = 二 图2 2 可重复性资源分布 c o n s u m e 似，r q j ) = = 二 r ，呐苫叫叫峨唧 图2 - 3 消耗性资源r 分布 2 、调度问题的费用函数 调度动作使用资源的花费可以是固定的，也可以是一个函数，函数是动作所 要求资源的数量和持续时间之间的关系。资源也可以有附加的启动费用。调度的 评价标准是使各种费用函数取最小值，并且( 或) 调度的时间最短【引。 常用的评价函数有： 调度的跨度( m a k e s p a n ) 或最大结束时间，f m a x “e ( 孤) i 趾a ； 加权的总完成时间，即f - 罗w i e ( a j ) ，常量是动作a f 的权值； 最大的延期，即f = m ) ，f ，是动作撕延期完成时与最终期限d a f 的距离， 9 中山大学硕士学位论文基于资源约束的堆场集装箱出口箱作业调度规划系统 即m = m a ) 【 0 ，e ( 曲- 血 ； 延期动作数，即t j ) 0 的动作数； 延期动作的加权和，即f = 罗w ；u ；，若动作出延期则m = 1 ，否则m = o ； 筒 调度的总费用。 2 、机器调度 机器调度是一般性调度问题，包括f l o w - s h o p 、叩e n s h o p 和j o b s h 叩三类。 机器是一种单位容量的资源，在某时刻可利用或不可利用。任务( j o b ) 是动作a ， 舭，舭的一部分序列集。机器调度中有n 个任务和m 台机器，一个调度给任务 j 中的每个动作舭指定机器i 以及i 处理相应动作的时间段。一台机器不能同时 执行两个动作，一个任务也不能同时被两台机器处理。即对应于同一机器或同一 任务的两个时段不能重叠【硼。 单一状态机器调度有以下机器类型：等同并行机器，即处理任务j 的时间p 独立于分配给j 的机器；均衡并行机器，机器i 有特定的速度；无关并行机器，n 个任务用m 台机器处理，不同的组合有不同的处理时间。多状态机器调度中， 一个任务对应多个动作，各动作需要一定的机器。主要有，f l o w s h o p 问题，指 各任务j 严格对应m 个动作，动作即由机器i 执行，且各动作必须按照1 ，m 的顺序执行；o p e n s h o p 问题，与n o w s h o p 问题类似，但是任务j 的m 个动作可 以按照任意顺序执行；j o b - s h o p 问题，每个任务有多个动作，各动作需要若干特 定机器且需要按顺序执行1 9 l 。 机器调度问题形式化的被定义：a i b l 丫。 其中：a 表示问题的类型，p 、u 、r 、f 、o 、j 分别对应单一状态机的三种 机器类型和多状态机的三种类型；b 表示任务的特性；丫给出目标函数。 2 1 3 资源调度 1 、规划和机器调度 一些规划问题可以表示成机器调度问题，规划关注需要执行哪些动作，调度 关注在何时分配何种机器给何种任务。在这里规划中的动作的执行者就是被认定 为机器。考虑某个d w r 的问题，这个d w r 系统是实际堆场问题的一个简化【2 j 。 例2 1 ，用形式化方式描述下列问题：利用m 个相同的机器人在不同的位置 1 0 中山大学硕士学位论文基于资源约束的堆场集装箱出口箱作业调度规划系统 之间运送n 个集装箱。 解：一台机器就是一个机器人，一个任务记为c o n t a i n e r t r 锄s p o r t a t i o n ( c ，l ，l ) ， 是把集装箱从位置1 移动到位置l 。假设一项任务由一个机器人完成。为完成任 务，机器人必须到达位置l ，抓起并装载集装箱c ，移动到位置l ，卸下集装箱c 。 任务的持续时间是机器人从l 移动到l 的时间加上装载和卸载的时间，定义启动时 间为嘲。对调度的最小加权完成时间感兴趣，于是该问题被描述成， p ir j 6 j i w j e ( a j ) 。其中巧表示任务j 的间隔时间，m 表示最终期限。 j 。l 如果考虑任务间的优先约束来处理集装箱的排列顺序，假设c 在c 上面，则 c 的运输任务必须在c 之前，同时还需要考虑在两个位置之间运送的不需要移动 的集装箱的干扰，即移箱操作。这样需要加入特别任务，u n s t a 凼( c ，p ) ( 从位置p 上移走c ) 以及s t a c k ( c ，p ) 。而在s t a c k ( c ，p ) 还需要考虑位置的可用范围，即有多 少个位置可以利用，此也是资源的约束条件【9 1 。 2 、资源约束的规划 下面考虑带资源变量约束的动作【8 一。 定义2 1 ：当总量为q 的资源变量z 的一个时态断言是三种之一，当数量q 的资源z 在t 时刻被借用时，当数量q 的资源z 在t 时刻被释放，当数量q 的资 源z 在【t ，t 】被使用时，这三种时态断言分别表示为：z t ：一q ，z t ：+ q ，z 【t ，t 】：q 。 例2 2 ，根据定义2 1 给出d w r 系统中带资源变量的m o v e 操作。 解：每个集装箱的位置被描述成一种资源，数值取决于位置上可利用的位置 总数。记s p a c e ( 1 ) 为位置l 上对应的资源变量，即在位置l 上可用的位置个数。 m o v e 操作的功能是机器人从位置l 移动到位置l ，当机器人离开位置l 时，l 上 的可用位置s p a c e ( 1 ) 比执行m o v e 操作之前多一个，当机器人到达l 位置后，s p a c e ( 1 ) 比执行m o v e 操作之前少一个可用位置。m o v e 的形式化描述如下： m o v e ( ，r ，l ，t j ，t 2 ，r ，l ，l ) = r o b o t l o c a t i o n ( r ) l ：( 1 ，r o u t e s ) ， r o b o t - i o c a t i o n ( r ) 【l ，l 】：r o u t e s ，r o b o t l o c a t i o n ( r ) t e ：( 1 ，r o u t e s ) ， s p a c e ( 1 ) t 1 ：+ 1 ，s p a c e ( 1 ) t 2 ：1 ，b n t 2 l ，a d j a c e n t ( 1 ，l ) ) 其中l 为初始时间，n 为机器人开始移动时间，t 2 为到达位置l 时间，l 为结束时间。上述问题描述可以看到，规划和调度的结合目前是解决实际问题的 一个方向，而对于资源的约束处理则是基于资源的规划的一个研究方向【1 5 】。 中山大学硕士学位论文基于资源约束的堆场集装箱出口箱作业调度规划系统 2 2 搜索策略及算法策略 由于实际堆场系统很复杂，状态空间很大，这个时候搜索状态空间的搜索策 略就至为重要，对于本规划系统主要用到局部启发式搜索算法和贪婪算法。 2 2 1 局部启发式搜索 启发式信息：针对要求解的问题所聚集的有关资料，分析结果及与问题求解 相关的特性信息。启发信息是综合了人的经验以及推理性常识等智能，得到的有 利于找到问题界的较为完善的控制信息与知识。使用启发信息来控制搜索方向和 路径的方式及称为启发式搜索【l l 。启发式搜索在搜索过程中有充分的启发信息作 引导，有较完善的控制性知识作依据，具有较高的效率。 启发式搜索的估价函数：从问题节点到目标节点的所耗费查找的全部代价， 有两部分组成f ( n ) = g ( n ) + h ( n ) ，g ( n ) 表示已经搜索到的某个节点耗费的代价，h ( n ) 表示从当前节点开始到目标节点所耗费的代价。g ( n ) 值是确定的，h ( n ) 是可以积 极争取按照期望来改变的部分，称为启发函数。启发式搜索分为局部启发式搜索 和全局启发式搜索。局部启发式搜索的思想是：当一个节点x 被扩展以后，按f 伍) 对每一个子节点计算估价值，并选择最小者作为下一个要考查的节点。全局择优 搜索是每次都从生成节点的全体节点中选择一个估价值最小的节点。启发式搜索 中最重要的是选择一个好的启发函数。根据本文实际堆场需要，按照简化原则设 计如下例子。 例2 3 有如图2 4 描述的初始状态的游戏，其中c 表示要出口的货柜，r 表示不出口的货柜，e 表示为空位。该游戏玩法是：1 ) 当把货柜移至空位的费用 为1 ；2 ) 一个将出口货柜最多跳过两个货柜进入空位置，费用为跳过的货柜数加 1 。 图2 4 初始状态 要求所有的出口柜c 都在不出口的货柜r 的右边。请设计启发函数h ( n ) 。 解：根据要求，c 都不在r 的右边，那么在r 左边的c 越少越接近目标， 中山大学硕士学位论文基于资源约束的堆场集装箱出口箱作业调度规划系统 因此可以用r 左边的c 的个数作为h ( x ) ，h ( x ) = 每个r 左边c 个数的总和。假 设某个状态如图2 5 所示，则该时刻的h ( x ) = 2 + 2 + 3 = 7 。 图2 5 某时刻的状态 根据后面实际的需要主要介绍局部启发式搜索过程，首先定义两个数据结 构，o p e n 表，用于存放刚生成的节点，c l o s e d 表：用于存放将要扩展或者已 经扩展的节点。则局部启发式搜索算法的过程如下： ( 1 ) 将初始节点s d 放入o p e n 表，计算f 圆d ) ； ( 2 ) 如果o p e n 表为空，则问题无解，退出； ( 3 ) 把o p e n 表的第一个节点n 取出放入c l o s e d 表； ( 4 ) 考查节点n 是否为目标节点，若是，则求得了问题的解，退出； ( 5 ) 若节点n 不可扩展，则转( 2 ) 步； ( 6 ) 扩展n ，用估价函数f ( x ) 计算每个子节点的估价值按照估价从小到大的 顺序依次放到o p e n 表的首部，为每个字节点配置指向父节点的指针，转( 2 ) 步。 2 2 2 贪婪算法 从某一个给定的集合中选出一个子集，满足题目所给的要求，这个子集就是 一个可行解。可行解不一定是唯一解。贪婪算法把可行的工作分阶段来完成。在 各个阶段，选择在某些意义下世局部最优解的方案，希望从各个阶段的局部最优 选择，能够得到整体最优。但是，贪婪算法不是每次都能产生整体最优解。贪婪 算法在每个阶段都保持局部最优，而各个阶段结果合起来，总的结果可能不是最 优。如求最短路经的算法，求从起点到目标节点的最短路经用的就是贪婪算法【了丌。 能够使用贪婪算法的问题都有两个重要的性质，贪婪选择性质和最优子结构 性质。贪婪选择性质是指所求问题的整体最优解可以通过一系列局部最优的选 择，即贪心选择来达到。贪婪算法只是在当前状态下做出最好选择，为局部最优 选择，然后再去解这个选择后产生的相应的子问题。贪婪算法所做的贪婪选择可 以依赖于以往的选择，但不依赖于将来所做的选择，也不依赖于子问题的解。最 优子结构性质是指当一个问题的最优解包含着它的子问题的最优解。 1 3 中山大学硕士学位论文基于资源约束的堆场集装箱出口箱作业调度规划系统 第3 章堆场出口箱作业分析及建模 集装箱码头企业是特殊的生产企业，生产调度主要是日常优化资源的调度管 理，码头经营企业对其资源进行优化调度，使企业在有限的资源约束条件下取得 最大的经济效益。出口箱作业既是装船作业，是码头五大作业中的一个，是根据 实际需要按照出口舱单表给出所有出口集装箱的调度顺序，将集装箱从后方堆场 发到前沿堆场，是码头堆场管理的不可缺少的一个环节。 本章将分析实际堆场中的出口集装箱作业流程，总结实际堆场搬运规则和约 束资源，同时进行建模，设计解决算法。 3 1 出口箱作业流程描述 根据对实际码头的调研，出口货物的流程如图3 1 所示。 图3 1 出口箱作业流程 1 4 中山大学硕士学位论文基于资源约束的堆场集装箱出口箱作业调度规划系统 从出口箱作业流程可知出口货物作业包括两个部分，一部分是从工厂进入到 堆场，另一部分是在海关确认放行后从堆场装船。其中关于工厂进入堆场的问题 本文不讨论，出口箱装船作业为本文的主要研究对象，即研究在有限时间内有限 资源下如何快速装船，保证最少的额外移箱量。 集装箱需要及时( 通常是提前) 从堆场搬到码头旁边，然后在船靠岸后将集装 箱装入船舶。装船主要涉及的问题有：应该提前搬运哪些集装箱到哪个吊机旁边； 在前方堆场又如何堆放；出口集装箱提前搬运的业务规则有哪些；如何最优化集 装箱提前搬运的效果；搬运中出现额外移箱怎么办。 根据提出的问题将出口箱作业分成两部分，一部分称为出口箱装船作业，这 部分作业是出口箱最重要的部分，出口箱通过货主送货或者码头到厂装货，线性 的、离散的一个一个地进入堆场，之后根据出口舱单信息集中一次性装船出口， 而在出口之前，为了提高效率，在吊机资源和吸车、渡柜车等资源允许的前提下， 提前移动一部分货柜到前方堆场，在船舶正式装船离港之前全部堆放在前方堆 场，并装上船舶。 另一部分称为额外移箱作业，在1 1 1 章节中已经介绍了码头拥有5 大类作 业，其中这5 大类作业中，集装箱的场内移箱可以是另外4 大类作业的关联作业， 也可以是独立作业。本文讨论的额外移箱作业即是集装箱场内移箱作业，除出口 箱作业需要这部分，其他3 类作业也需要这部分，故本文将额外移箱作为一个单 独的部分进行分析，同时也和出口箱装船作业部分一起构成出口箱作业流程的一 部分。 3 1 1 出口箱装船作业 从目前码头的实际情况和作业的规范性来说，出口装船的主要流程如图3 2 所示，而图3 3 ，图3 4 是对图3 2 中的o p 操作进行展开描述。 各个部门和人员所负责的工作职责在下文中介绍，其中码头业务组中最重要 的是前方理货员、现场理货员，而工班、吸车司机、渡柜车司机主要是服从命令 做一些装卸工作和机械操作，所以下文中不详细介绍简单的工作，只介绍前方理 货员和现场理货员的业务职责。 中山大学硕士学位论文基于资源约束的堆场集装箱出口箱作业调度规划系统 1 、船公司的主要职能 ( 1 ) 根据船公司的计划得到提前出口计划表，新建出口舱单；输入航次，进 出港名和时间等资料，录入出口箱信息，生成出口箱作业。通过提单申请货柜交 接单，来提集装箱出码头装货； ( 2 ) 确认舱单录入正确后，提交舱单给码头业务部门。 2 、码头业务部门业务员的主要职能 ( 1 ) 审核出口舱单与实际仓单是否一致，一致则继续下一步，否则将出口舱 单返回给船公司； ( 2 ) 核实舱单货柜的放行情况和收费情况，等待船代公司清关确认后，然后 向中控室提交出口装船作业申请； ( 3 ) 确认后的舱单，若在作业过程中发现一些非正常情况需要变更舱单，做 反确认操作，录入相应权限用户密码，进行变更舱单编辑，保存。 3 、码头中控室的主要职能 ( 1 ) 在作业调度平台上接收到出口装船作业申请，录入作业人员安排明细； ( 2 ) 现场理货员到中控室来取出口计划表时，根据出口箱数据库得到出口箱 在前方堆场的位置信息以及码头业务组提供的作业能力和吊机装载能力生成出 口计划表； ( 3 ) 可以根据理货员要求对生成的调度计划表进行修改，可以查看计划表相 关信息，并可以打印计划表； ( 4 ) 根据现场理货员反馈的箱体状态记录，在系统中录入反馈后的堆场实际 堆存信息； ( 5 ) 确认装船完毕，更新数据库，清空堆场相应箱位。 4 、现场理货员 ( 1 ) 根据出口计划表信息，在后方堆场标记出口货柜，等待海关抽检； ( 2 ) 根据现场资源，在有能力有时问的情况下，协调吸车司机、渡柜车司机 提前搬运出口货柜至前方堆场，根据实际需要，随时反馈给中控室和前方理货员 已经提前搬动的货柜位置信息； ( 3 ) 在出口装船的时间限制内，确认出口舱单上的所有货柜均己移动至前方 堆场，并将最后搬运的位置信息反馈给前方理货员。 1 6 中山大学硕士学位论文 基于资源约束的堆场集装箱出口箱作业调度规划系统 5 、前方理货员 ( 1 ) 根据现场理货提供的位置信息在前方堆场标记出口箱位置； ( 2 ) 根据出口船舶提供的船舶配载图、货柜位置信息和吊机装载情况，指挥 放箱至船舶上，保证船舶载重平衡； ( 3 ) 完成作业后，将信息反馈给中控室。 图3 2 出口装船业务流程图 1 7 中山大学硕士学位论文 基于资源约束的堆场集装箱出口箱作业调度规划系统 上图3 2 中o p 操作展开描述，根据码头业务组中的现场理货员和前方理货 员职责不同分别论述，对应图3 3 和图3 4 。这两类理货员可以并发工作，但是 注意到出口装船的最后时间期限。 图3 - 3 现场理货员业务流程 3 1 2 额外移箱作业 图3 - 4 前方理货员业务流程 在集装箱的进出场作业中，由于集装箱堆放的不合理性，经常引发额外移箱， 在出口作业中，由于出口箱是分散进堆场、集中装船，就会导致在进入堆场的时 候放置的位置分散，从而引起在统一装船时需要移动那些不需要装船的集装箱， 虽然有很多国内外学者研究出各种方法堆放集装箱以减少