集装箱堆场箱位分配
兰州交通大学
2010年管理运筹学大赛论文
题目:
组长姓名: 李欣娜
论文编号:
参赛人1: 姓名 李欣娜
学院 交通运输学院 班级 信息管理与信息系统08
参赛人2: 姓名 刘亚丽
参赛人3:参赛人4:参赛人5:学院 交通运输学院 班级 交通运输082
姓名 沈斌
学院 交通运输学院 班级 信息管理与信息系统08
姓名 路明昭
学院 交通运输学院 班级 信息管理与信息系统08
姓名
学院 班级
论文编号:
目 录
(一)摘要 .......................................................... 5 (二)引言 .......................................................... 5 一、研究背景 ....................................................... 5 二、研究的目的和意义 ............................................... 6 (三)正文 .......................................................... 6 一、集装箱堆场的概念 ............................................... 6 二、产生集装箱倒箱的原因 ........................................... 7 三、箱位分配作业知识 ............................................... 8 1.分配区域划分规则 ............................................... 8 2.堆垛作业模式 ................................................... 8 四、集装箱堆场箱位分配模型 ......................................... 8 1.模型假设 ....................................................... 9 2.模型建立 ....................................................... 9 3.算法流程图 .................................................... 11 五、算法实例 ...................................................... 12 1.程序代码 ...................................................... 13 2.程序结果 ...................................................... 18 3.说明 .......................................................... 18 (四)结论 ......................................................... 18 (五)参考文献 ..................................................... 18
集装箱堆场箱位分配
(一)摘要
港口码头与铁路集装箱办理站的集装箱堆场主要办理集装箱的发送,到达和中转作业,组织集装箱门到门运输。堆场内每天到达的集装箱数量很大,而大多数堆场面积是有限的,因此起重机要频繁的进行装卸作业,为此,要求堆场作业应优化箱位分配使得起重机作业次数最少。本文根据实际情况建立了以提箱时间为制约因素,以起重机作业次数最少为目标的集装箱后方堆场箱位分配模型,并针对模型采用了群体智能搜索算法的解决方案。.
首先分析了该问题中的种种不确定性因素,并按照自己的理解进行了合理的假设以简化问题。并通过分析说明落箱作业的影响因素包含了提箱作业时要考虑的影响因素。详细介绍了落箱作业的作业模式,作业规则和作业过程,提出了基于规则的推理过程来解决堆场箱位分配问题并通过推理机制得到合理的放箱位置。接着分析了提箱作业优化问题,将其归结为一个最优箱位最小次数搜索的决策问题,建立了箱位分配优化的数学模型,该模型以总作业次数最少为目标,通过智能搜素的方法对问题进行求解。最后,本文对以5天内,10个箱位,2层为例的具体模型,计算了最优解,表明了模型的最优性和算法的可行性。从而也说明了基于规则推理过程设计的合理性。实现了起重机的总的作业次数最少的目的。
关键词: 集装箱堆场; 作业规则;箱位分配;群体智能搜索;
(二)引言
一、研究背景
当今世界上60%以上的海路运输采用集装箱运输的方式,特别是在某些经济发达的国家之间,集装箱化已达到100%[1]。随着世界贸易的增长,集装箱运输量持续增加,集装箱港口作为集装箱海路运输的起点和终点,同时也是衔接海路与陆路的枢纽,港口之间的竞争越来越激烈,地理位置较近的港口之间表现得尤为突出。
集装箱运输量的增加,使得集装箱船舶大型化趋势日益明显,最近建造的
PoNLMondriaan的容量己达到8450 TEU[2]。大型船舶的投入使用,使得集装箱码头的作业效率成为集装箱运输的瓶颈,如何提高集装箱码头的作业效率以适应集装箱运输的发展己经成为许多国家的重要研究课题。
随着我国对外贸易的持续增长,集装箱运输量保持着较高的增长速度,2006年1至11月,全国主要港口累计完成国际标准集装箱吞吐量8354.32万TEU,比去年同期增长233%。其中沿海港口完成7790.07万TEU,比去年同期增长223%;内河港口完成564.25万TEU,比去年同期增长38.5%。据预测,到2010年,中国港口集装箱吞吐量将达到1.5亿TEU[3]。如此快速的增长为我国的集装箱港口带来了巨大的机遇和挑战,除了加大力度建设新的码头之外,在现有的港口规模下,如何挖掘潜力,改进管理水平,提高生产效率,是港口面临的共同问题。而且,我国的港口管理水平与发达国家的现代化港口有较大的差距,相同规模的港口,其吞吐能力远逊于国外,单纯地依靠增加设备投入并不是最经济的办法[4],因此提高港口的管理水平,研究更合理的码头装卸工艺流程也是当务之急。
二、研究的目的和意义
随着我国集装箱码头吞吐量的快速增长,集装箱码头对堆场装卸效率要求越来越高。人们往往追求先进的设施、设备,忽略高效的基础——生成组织管理。硬件设施设备属于一种长期投资,投入成本高、回收慢,因此,必须在现有的装卸技术和硬件设施的基础上实现更高的作业效率,才能在市场竞争中占有主动地位。
堆场管理是码头生成的一个重要环节,装卸速度的提高很大程度上取决于码头堆场箱区、箱位安排的合理性。合理安排箱区和箱位,不仅能减少翻箱率,减少岸桥等箱的时间,提高码头装卸速度,而且还能最大限度的提高堆场利用率和码头通过能力,降低码头生产成本。
(三)正文
一、集装箱堆场的概念
港口码头与铁路集装箱办理站的集装箱堆场主要办理集装箱的发送、到达和中转作业,组织集装箱门到门运输。堆场内每个箱区有若干个箱位共存放集装箱,每个箱位从下到上可依次堆放集装箱,能堆放集装箱的数量叫做层数,按由下到
上的顺序编号,如图1所示。
图1 箱区内箱位与层示意图
二、产生集装箱倒箱的原因
由于堆场计划做的不好和码头不可控制的随机因素的影响等原因,堆场常会发生倒箱。倒箱的原因[5]主要有以下几点:
1) 不同船名、航次的重箱混合进场。许多船公司先把重箱收进场,然后根据情况给出船名、航次,这样就可能产生不走船压走船的现象。为顺利进行装船作业,需将走船的集装箱取出,放至适当位置。
2) 船公司临时改变某集装箱的航次或目的港。码头必须修改装卸船计划,导致部分集装箱必须倒箱。
3) 不同重量级的集装箱混合堆放。码头接受的重箱进场时随机的,从而导致轻箱压重箱、轻重箱混合在一起的现象。为了保持集装箱船舶的稳定和纵向强度,充分利用集装箱船舶箱位,需在装船前倒箱。
4) 为防止中途挂港船上倒箱,集装箱班航线中途挂靠港较多,根据集装箱船舶中途挂靠港顺序和集装箱到达各挂靠港的情况,考虑途中挂靠港的装卸情况,码头装船时,防止产生后挂港集装箱压前挂港集装箱,堆场必须对集装箱按到港顺序进行调整,从而产生堆场倒箱。
5) 特殊箱型的重箱由于在船上比较有固定的位置,装卸作业前必须在堆场内单独堆放,以便于装箱,从而导致倒箱,如冷藏箱、危险箱、框架箱、高箱等。
6) 进口重箱发放给收货人或内陆承运人时,所产生的倒箱也是比较常见的,因为他们来码头提箱是陆续和随机的,不可避免地要产生倒箱。
三、箱位分配作业知识
在出口集装箱的箱位分配问题中, 根据堆场管理原则和作业设备的特点, 可得到多种关于作业的知识[6]。按其作用可分为分配区域划分规则、 堆垛作业模式和设备作业规则。 1.分配区域划分规则
堆场集装箱的堆放一般遵循 PSCW原则, 即对同一目的港(port.),同一尺寸 (size) 、 同一种类(category)的集装箱,按重量级别(weight)堆放在堆场的同一贝上, 满足PSCW原则的集装箱集合为同类箱组。按照这一原则, 可以得到相应的分配区域划分规则, 将同类箱组放在同一区域。 2.堆垛作业模式
堆垛作业模式[7](以下简称模式) 指的是, 对于街中的任意一个贝的各行, 集装箱堆垛作业的方向及先后次序。常见的堆垛作业模式有从小行到大行、 从大行到小行、 从中间到两边,如图2所示。
图2 堆垛作业模式
四、集装箱堆场箱位分配模型
为了提高箱区分配的有效性,除了要考虑当天的进场箱信息外,还需要充分利用未来一段时间的信息。因进口箱在码头的存放时间都不超过5天。因此,本文选择5天作为箱位分配的决策周期,并将每天划分成6个时段。此外,由于信息每天都在不断地更新,堆场分配方案也将随之发生变化,堆场空间分配计划需要滚动更新,因此本文选用滚动式堆场箱位分配计划,如图3所示。
第一规划时间段
1 6 12 18 24 30 36 42
第一天 第二天
第三天
第四天 第五天 第六天 第七天
第二规划时间段
图3 堆场箱区段滚动分配
1.模型假设
集装箱堆场箱位分配模型基于以下假设:1)倒箱只发生在同一箱区中;2)同一箱区中只放同一类型的箱子,即不考虑集装箱的尺寸、轻重等因素的影响;3)货主必须在约定时间内提箱;4)该模型的堆场仅有一个箱区。5)所提到的时间均以小时计。 2.模型建立
本模型选取从小行到大行以及混合作业模式,遵循小时间箱压大时间箱的原则,采用群体智能搜索方式,对集装箱进行最优箱位分配,目的是起重机的作业次数最少,即倒箱次数最少。
1)假设有一个n×m的堆场,n表示层,m表示箱位,对堆场箱位进行编号。如图4所示。
图4 堆场编号示意图
2)考虑倒箱操作时所需要临时专用的箱位,则该堆场最多能容纳n(m-1)+1个箱子,即有n-1个箱位留于倒箱操作时用。
3)箱位选择模式及规则匹配
模式及规则匹配过程在方向上遵循堆垛作业模式,在作业顺序上按照设备作业模板执行,采取从小行到大行作业模式和混合作业模板进行箱位匹配。
(1)模板最小序号所在行和作业起始行对齐(图5(a))。若行已放满箱,模板右移一位(b),知道模板最小序号所在位没有放满箱,匹配成功(c)。假设模板区域内所有箱位均带有1~12作业顺序号。
(2)根据堆场状态和作业设备能力,选出可以分配的箱位,如图5(c)中序号为4、6、8的箱位。
空位 已放箱位置 符合分配条件位置
图5 模板匹配过程(从小行到大行)
4)用二元函数fx,y表示箱位是否为空,x为第i箱位,y为第j层,记
1
fx,y
0
空箱位满箱位
由于堆场对倒箱作业要进行预留n-1个箱位,则不妨规定在m×n的堆场中,第m个箱位,第2层至第n层为倒箱作业的预留箱位,在后续搜寻过程中,该预留箱位设为满箱位。
设当fx,y0时,箱位上的集装箱的等待时间为
tij
(i=1,2,…,m;j=1,2,…,n);设下一个进场的集装箱在堆场等待货主提箱的等待时间为tk。
当集装箱进入堆场时,检查堆场中是否存在空箱位,若不存在空箱位,则该集装箱不允进入堆场,在堆场外等候,直至堆场内有集装箱被货主提取,产生空箱位时,该集装箱方可进入堆场。
当集装箱进入堆场时,若存在空箱位,采用图5所示的箱位的模板匹配方式寻找出可以分配的空箱位,即fx,y1。
(1)当y>1时,对fx,y1时中的y取最小值,即min y,则可得出位于最低层的空箱位,并且可以知道第y层以下的箱位为满箱位。
设当y = min y时,f(x,y1)=1箱位为ai(j-1)中的集装箱的等待时间为ti(j-1) ①若tk1;
②若tk> ti(j-1),搜寻下一个y>1,满足fx,y1的空箱位,并将该集装箱放于搜寻到的空箱位;
③若tk> ti(j-1),不存在下一个y>1且满足fx,y1的空箱位,则转向(2); (2)当y = 1时,对fx,y1时中的x取最小值,即min x,则可得出第一层中具有最小箱位号的空箱位,并且可以知道第x箱位以后的箱位为空箱位。设该满足函数fx,y1且x = min x且y = 1的箱位为ap1(p = 1,2,…,m),并将该集装箱放于此箱位ap1。
5)对货主提箱后的堆场箱位分配模型
当货主在约定时间内来提箱时,将会产生新的空箱位,并且同时对堆场中的集装箱的等待时间进行更新。由于我们将一天划分为6个阶段,即每个阶段为4小时。
①若存在这样一个箱位ak1,其满足fx,y0且y = 1,其等待时间ak1 4,该箱位暂时不动。
②对进场集装箱k,其等待时间为tk,对该箱采用4)方法寻找箱位,若不存在这样的箱位,则寻找堆场中满足fx,y0的箱位,箱位中集装箱等待时间为t,且t满足下列条件:
条件:t大于且逼近于tk,即满足limt = tk,设有这样的箱位r个,则对这r
ttk
个箱位上层的满足fx,y0的箱位的等待时间求和,取mint的箱位列,设满足条件1的箱位为apq,并分别对其上层的集装箱采取4)方法重新分配箱位,然后将新到场的集装箱k放于apq的上一层,即箱位ap(q+1)。 3.算法流程图
综上所述,可以得到对集装箱堆场箱位分配的算法流程图,如图6所示。
图6 算法流程图
五、算法实例
本文以5天内,10个箱位,2层为例,在Eclipse环境下实现了群体智能搜索的算法,并编写程序模拟了堆场堆箱的实际情况。将每天划分为6个时段,5天共30个时段。随机对堆场进行初始化,使得堆场既存在空箱位,也存在满箱位,堆
场内的集装箱的等待时间随机产生,同时随机产生进入堆场的集装箱,其等待时间随机确定,等待时间到达,模拟货主提箱,对堆场箱位及堆场中集装箱的等待时间进行更新,最终得到第30个时段结束时,堆场内集装箱的分布情况、集装箱最终的等待时间以及在此30个时段内,起重机的总作业次数。 1.程序代码
2.程序结果
程序模拟结果如图7所示
图7 程序模拟结果
3.说明
首先,由于最初对堆场箱位是随机分配的,并且来箱提箱均为随机给定,故该程序模拟,是在这种不确定的随机因素下产生的最少作业次数及堆场箱位的最优分配结果,该结果并不代表若来箱提箱是确定的情况下产生的最优解。其次,堆场的箱位分配是一个连续的、没有终点的模拟过程,而该程序仅模拟出5天内的堆场箱位分配,故该结果为5天内堆场箱位的最优分配以及起重机的最少作业次数。
(四)结论
本文对针对一个阶段、一个箱区的堆场箱位分配特点设计了一种基于群体智能搜索算法的模型。该模型能够对到达堆场的集装箱进行最优箱位的分配,并且保证了集装箱进入堆场以及货主来提箱的过程中起重机的操作作业次数最少,从而提高了堆场作业的效率,降低了成本。
(五)参考文献
[1] Steenken D,Vo βS,Stahlbock R.Container terminal operation and operations research—a classification and literature review.OR Spectrum,2004,26:3~49
[2] Rommert Dekker,Parick Voogd,Eelcovan Asperen.Adcanced methods for container stacking.OR Spectrum,2006,28:563~586 [3] http://news.sol.com.cn/…
[4] 陈戌源.集装箱码头业务管理.大连:大连海事大学出版社,1998 [5] 计三有,高悦文 集装箱堆场减少倒箱率方法研究,2006
[6] 朱玉伟,拾兵,黄勇,等.基于IDL与VB的遥感数据提取[J].计算机应用研究,2006,23(3):181-182,201
[7] 沈剑锋,金淳,高鹏.基于知识的集装箱堆场箱位分配计划研究,2007(09)