集装箱堆场箱位分配

1、兰州交通大学 2010 年管理运筹学大赛论文 题目： 集装箱堆场箱位分配 组长姓名: 李欣娜 论文编号： 学校统一编号， 个人不得填写 参赛人 1： 姓名 李欣娜 学院 交通运输学院 班级 信息管理与信息系统 08 参赛人 2： 姓名 刘亚丽 学院 交通运输学院 班级 交通运输 082 参赛人 3： 姓名 沈斌 学院 交通运输学院 班级 信息管理与信息系统 08 参赛人 4： 姓名 路明昭 学院 交通运输学院 班级 信息管理与信息系统 08 参赛人 5： 姓名 学院 班级 论文编号： 学校统一编号， 个人不得填写 目 录 （一）摘要 .5 （二）引言 .5 一、研究背景.5 二、研究的目的和意

2、义.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 集装箱堆场箱位分配 （一）摘要 港口码头与铁路集装箱办理站的集装箱堆场主要办理集装箱的发送，到达和 中转作业，组织集装箱门到门运输。堆场内每天到达的集装箱数量很大，而大多 数堆场面积是有限的，因此起重机要频繁的进行装卸作业，为此，要求

3、堆场作业 应优化箱位分配使得起重机作业次数最少。本文根据实际情况建立了以提箱时间 为制约因素,以起重机作业次数最少为目标的集装箱后方堆场箱位分配模型,并针 对模型采用了群体智能搜索算法的解决方案。. 首先分析了该问题中的种种不确定性因素，并按照自己的理解进行了合理的 假设以简化问题。并通过分析说明落箱作业的影响因素包含了提箱作业时要考虑 的影响因素。详细介绍了落箱作业的作业模式，作业规则和作业过程，提出了基 于规则的推理过程来解决堆场箱位分配问题并通过推理机制得到合理的放箱位置。 接着分析了提箱作业优化问题，将其归结为一个最优箱位最小次数搜索的决策问 题，建立了箱位分配优化的数学模型，该模型以

4、总作业次数最少为目标，通过智 能搜素的方法对问题进行求解。最后，本文对以 5 天内，10 个箱位，2 层为例的 具体模型，计算了最优解，表明了模型的最优性和算法的可行性。从而也说明了 基于规则推理过程设计的合理性。实现了起重机的总的作业次数最少的目的。 关键词： 集装箱堆场； 作业规则；箱位分配；群体智能搜索； （二）引言 一、研究背景 当今世界上 60%以上的海路运输采用集装箱运输的方式，特别是在某些经济 发达的国家之间，集装箱化已达到 100%1。随着世界贸易的增长，集装箱运输量 持续增加，集装箱港口作为集装箱海路运输的起点和终点，同时也是衔接海路与 陆路的枢纽，港口之间的竞争越来越激烈，

5、地理位置较近的港口之间表现得尤为 突出。 集装箱运输量的增加，使得集装箱船舶大型化趋势日益明显，最近建造的 PoNLMondriaan 的容量己达到 8450 TEU2。大型船舶的投入使用，使得集装箱码 头的作业效率成为集装箱运输的瓶颈，如何提高集装箱码头的作业效率以适应集 装箱运输的发展己经成为许多国家的重要研究课题。 随着我国对外贸易的持续增长，集装箱运输量保持着较高的增长速度，2006 年 1 至 11 月，全国主要港口累计完成国际标准集装箱吞吐量 8354.32 万 TEU，比 去年同期增长 233%。其中沿海港口完成 7790.07 万 TEU，比去年同期增长 223%; 内河港口完

6、成 564.25 万 TEU，比去年同期增长 38.5%。据预测，到 2010 年，中 国港口集装箱吞吐量将达到 1.5 亿 TEU3。如此快速的增长为我国的集装箱港口 带来了巨大的机遇和挑战，除了加大力度建设新的码头之外，在现有的港口规模 下，如何挖掘潜力，改进管理水平，提高生产效率，是港口面临的共同问题。而 且，我国的港口管理水平与发达国家的现代化港口有较大的差距，相同规模的港 口，其吞吐能力远逊于国外，单纯地依靠增加设备投入并不是最经济的办法4， 因此提高港口的管理水平，研究更合理的码头装卸工艺流程也是当务之急。 二、研究的目的和意义 随着我国集装箱码头吞吐量的快速增长，集装箱码头对堆场

7、装卸效率要求越 来越高。人们往往追求先进的设施、设备，忽略高效的基础生成组织管理。 硬件设施设备属于一种长期投资，投入成本高、回收慢，因此，必须在现有的装 卸技术和硬件设施的基础上实现更高的作业效率，才能在市场竞争中占有主动地 位。 堆场管理是码头生成的一个重要环节，装卸速度的提高很大程度上取决于码 头堆场箱区、箱位安排的合理性。合理安排箱区和箱位，不仅能减少翻箱率，减 少岸桥等箱的时间，提高码头装卸速度，而且还能最大限度的提高堆场利用率和 码头通过能力，降低码头生产成本。 （三）正文 一、集装箱堆场的概念 港口码头与铁路集装箱办理站的集装箱堆场主要办理集装箱的发送、到达和 中转作业，组织集装

8、箱门到门运输。堆场内每个箱区有若干个箱位共存放集装箱， 每个箱位从下到上可依次堆放集装箱，能堆放集装箱的数量叫做层数，按由下到 上的顺序编号，如图 1 所示。 2 层 1 层 箱位 1箱位 2箱位 3 图 1 箱区内箱位与层示意图 二、产生集装箱倒箱的原因 由于堆场计划做的不好和码头不可控制的随机因素的影响等原因，堆场常会 发生倒箱。倒箱的原因5主要有以下几点： 1) 不同船名、航次的重箱混合进场。许多船公司先把重箱收进场，然后根 据情况给出船名、航次，这样就可能产生不走船压走船的现象。为顺利进行装船 作业，需将走船的集装箱取出，放至适当位置。 2) 船公司临时改变某集装箱的航次或目的港。码头

9、必须修改装卸船计划，导 致部分集装箱必须倒箱。 3) 不同重量级的集装箱混合堆放。码头接受的重箱进场时随机的，从而导致 轻箱压重箱、轻重箱混合在一起的现象。为了保持集装箱船舶的稳定和纵向强度， 充分利用集装箱船舶箱位，需在装船前倒箱。 4) 为防止中途挂港船上倒箱，集装箱班航线中途挂靠港较多，根据集装箱船 舶中途挂靠港顺序和集装箱到达各挂靠港的情况，考虑途中挂靠港的装卸情况， 码头装船时，防止产生后挂港集装箱压前挂港集装箱，堆场必须对集装箱按到港 顺序进行调整，从而产生堆场倒箱。 5) 特殊箱型的重箱由于在船上比较有固定的位置，装卸作业前必须在堆场内 单独堆放，以便于装箱，从而导致倒箱，如冷藏

10、箱、危险箱、框架箱、高箱等。 6) 进口重箱发放给收货人或内陆承运人时，所产生的倒箱也是比较常见的， 因为他们来码头提箱是陆续和随机的，不可避免地要产生倒箱。 三、箱位分配作业知识 在出口集装箱的箱位分配问题中， 根据堆场管理原则和作业设备的特点， 可得到多种关于作业的知识6。按其作用可分为分配区域划分规则、 堆垛作业 模式和设备作业规则。 1.分配区域划分规则 堆场集装箱的堆放一般遵循 PSCW 原则， 即对同一目的港（port.） ，同一尺 寸 （size） 、 同一种类（category）的集装箱，按重量级别（weight）堆放 在堆场的同一贝上， 满足 PSCW 原则的集装箱集合为同类

11、箱组。按照这一原则， 可以得到相应的分配区域划分规则， 将同类箱组放在同一区域。 2.堆垛作业模式 堆垛作业模式7（以下简称模式） 指的是， 对于街中的任意一个贝的各行， 集装箱堆垛作业的方向及先后次序。常见的堆垛作业模式有从小行到大行、 从 大行到小行、 从中间到两边，如图 2 所示。 165432 行 层 (a)从小行到大行 165432 行 层 (b)从大行到小行 165432 行 层 (c)从中间到两边 图 2 堆垛作业模式 四、集装箱堆场箱位分配模型 为了提高箱区分配的有效性，除了要考虑当天的进场箱信息外，还需要充分 利用未来一段时间的信息。因进口箱在码头的存放时间都不超过 5 天。

12、因此，本 文选择 5 天作为箱位分配的决策周期，并将每天划分成 6 个时段。此外，由于信 息每天都在不断地更新，堆场分配方案也将随之发生变化，堆场空间分配计划需 要滚动更新，因此本文选用滚动式堆场箱位分配计划，如图 3 所示。 第一天第二天 第三天 第四天第五天第六天第七天 16121824303642 第一规划时间段 第二规划时间段 图 3 堆场箱区段滚动分配 1.模型假设 集装箱堆场箱位分配模型基于以下假设：1）倒箱只发生在同一箱区中；2） 同一箱区中只放同一类型的箱子，即不考虑集装箱的尺寸、轻重等因素的影响； 3）货主必须在约定时间内提箱；4）该模型的堆场仅有一个箱区。5)所提到的时 间

13、均以小时计。 2.模型建立 本模型选取从小行到大行以及混合作业模式，遵循小时间箱压大时间箱的原 则，采用群体智能搜索方式，对集装箱进行最优箱位分配，目的是起重机的作业 次数最少，即倒箱次数最少。 1）假设有一个 nm 的堆场，n 表示层，m 表示箱位，对堆场箱位进行编号。 如图 4 所示。 anman2an1 a21 a12a11 a2ma22 a1m 图 4 堆场编号示意图 2）考虑倒箱操作时所需要临时专用的箱位，则该堆场最多能容纳 n(m-1)+1 个箱子，即有 n-1 个箱位留于倒箱操作时用。 3）箱位选择模式及规则匹配 模式及规则匹配过程在方向上遵循堆垛作业模式，在作业顺序上按照设备作

14、 业模板执行，采取从小行到大行作业模式和混合作业模板进行箱位匹配。 （1）模板最小序号所在行和作业起始行对齐（图 5（a） ） 。若行已放满箱， 模板右移一位（b） ，知道模板最小序号所在位没有放满箱，匹配成功（c） 。假设 模板区域内所有箱位均带有 112 作业顺序号。 （2）根据堆场状态和作业设备能力，选出可以分配的箱位，如图 5（c）中 序号为 4、6、8 的箱位。 4 12107 2 118 31 95 6 层 行1 2345 (a)模板匹配起始状态 12107 1184 1 952 63 层 行1 2345 (b)模板右移一行 107 84 52 316 9 11 12 层 行1 2

15、345 (c)匹配结果 空位 已放箱位置 符合分配条件位置 图 5 模板匹配过程（从小行到大行） 4）用二元函数表示箱位是否为空，为第 i 箱位，为第 j 层，记yxf,xy 满箱位 空箱位 0 1 ,yxf 由于堆场对倒箱作业要进行预留 n-1 个箱位，则不妨规定在 mn 的堆场中， 第 m 个箱位，第 2 层至第 n 层为倒箱作业的预留箱位，在后续搜寻过程中，该预 留箱位设为满箱位。 设当时，箱位上的集装箱的等待时间为0,yxf tij（i=1,2,m;j=1,2,n） ；设下一个进场的集装箱在堆场等待货主提箱的等 待时间为 tk。 当集装箱进入堆场时，检查堆场中是否存在空箱位，若不存在空

16、箱位，则该 集装箱不允进入堆场，在堆场外等候，直至堆场内有集装箱被货主提取，产生空 箱位时，该集装箱方可进入堆场。 当集装箱进入堆场时，若存在空箱位，采用图 5 所示的箱位的模板匹配方式 寻找出可以分配的空箱位，即。1,yxf （1）当 y1 时，对时中的 y 取最小值，即 min y，则可得出位于最1,yxf 低层的空箱位，并且可以知道第 y 层以下的箱位为满箱位。 设当 y = min y 时，=1 箱位为 ai(j-1)中的集装箱的等待时间为 ti(j-) 1,(yxf 1) 若 tk1； 若 tk ti(j-1)，搜寻下一个 y1，满足的空箱位，并将该集装箱1,yxf 放于搜寻到的空箱

17、位； 若 tk ti(j-1)，不存在下一个 y1 且满足的空箱位，则转向（2） ；1,yxf （2）当 y = 1 时，对时中的 x 取最小值，即 min x，则可得出第一1,yxf 层中具有最小箱位号的空箱位，并且可以知道第 x 箱位以后的箱位为空箱位。设 该满足函数且 x = min x 且 y = 1 的箱位为 ap1（p = 1,2,m） ，并将1,yxf 该集装箱放于此箱位 ap1。 5）对货主提箱后的堆场箱位分配模型 当货主在约定时间内来提箱时，将会产生新的空箱位，并且同时对堆场中的 集装箱的等待时间进行更新。由于我们将一天划分为 6 个阶段，即每个阶段为 4 小时。 若存在这样

18、一个箱位 ak1，其满足且 y = 1，其等待时间 ak1 4，该箱位暂时不动。 对进场集装箱 k，其等待时间为 tk，对该箱采用 4）方法寻找箱位，若不存 在这样的箱位，则寻找堆场中满足的箱位，箱位中集装箱等待时间为0,yxf t，且 t 满足下列条件: 条件：t 大于且逼近于 tk，即满足t = tk，设有这样的箱位 r 个，则对这 ktt lim r 个箱位上层的满足的箱位的等待时间求和，取 min的箱位列，设0,yxf t 满足条件 1 的箱位为 apq，并分别对其上层的集装箱采取 4）方法重新分配箱位， 然后将新到场的集装箱 k 放于 apq的上一层，即箱位 ap(q+1)。 3.算

19、法流程图 综上所述，可以得到对集装箱堆场箱位分配的算法流程图，如图 6 所示。 图 6 算法流程图 对堆场箱位编号，并初始化 参数，等待到场集装箱k 计算到场集装箱等待时间tk f(x,y) 1 y 1，取min y，设f（x,min y）的箱位为aij 箱位ai(j-1)的等待时间为ti(j-1) tk 1的箱位 设f（min x,y）的箱位为ap1 第一个寻找到的箱位为 集装箱k的最优箱位 否 存 在 集装箱的最优箱位为ap1 不进入堆场，等待货主提箱 后产生的空箱位 0 货主提箱 y = 1的箱位 寻找满足等待时间 t=tk 的箱位 满足条件的箱位其上 层箱位等待时间求和 找到具有最小时

20、间和的 箱位列，对其上箱位分 别寻找最优箱位 将集装箱k放到具有最 小时间和所在箱位列的 箱位的上一层箱位 不 存 在 是 否 五、算法实例 本文以 5 天内，10 个箱位，2 层为例，在 Eclipse 环境下实现了群体智能搜 索的算法，并编写程序模拟了堆场堆箱的实际情况。将每天划分为 6 个时段，5 天共 30 个时段。随机对堆场进行初始化，使得堆场既存在空箱位，也存在满箱 位，堆场内的集装箱的等待时间随机产生，同时随机产生进入堆场的集装箱，其 等待时间随机确定，等待时间到达，模拟货主提箱，对堆场箱位及堆场中集装箱 的等待时间进行更新，最终得到第 30 个时段结束时，堆场内集装箱的分布情况

21、、 集装箱最终的等待时间以及在此 30 个时段内，起重机的总作业次数。 1.程序代码 package package01; import java.util.Random; class Suijishu int T=0;int Tmax=5; int count=0; int s=new int 210; int b=new int20; public void Generate() double t1=Math.random()*10; Random r=new Random(long)t1); for(int i=0;i20;i+) bi=(int)(r.nextDouble()*10+1

22、); public void Move() for(int i=0;i9;i+) s0i=bi; for(int j=0;j9;j+) s1j=bj+9; for(int i=0;i9;i+) if(s1i=0) s1i=s0i; while(TTmax) for(int i=0;i2;i+) for(int j=0;j10;j+) sij=sij-1; if(sij=0) /接走 sij=0; count+; for(int m=0;m2;m+) for(int n=0;n9;n+) if(smn=0) /接受箱子 smn=(int)(Math.random()*10); count+; i

23、nt max=s00;int q=0; for(int i=0;imax) max=s0i; q=i; /取最大的放在 空位 for(int e=0;es1i) for(int j=i;j10;j+) if(s0j=0) if(s0is1j) s0j=s0i; s0i=0; count+; else if(s1j=0) s1j=s0i; s0i=0; count+; else if(s0i=0) for(int j=i;j10;j+) if(s0js1j) s0i=s0j; s0j=0; count+; if(s0j=0) if(s1j=s1i) s0i=s1j; s1j=0; count+;

24、 else s0j=s1i; s1i=0; count+; T+; for(int i=0;i10;i+) if(s1i=0) s1i=s0i; s0i=0; System.out.println(箱垛的样式： ); for(int i=0;i2;i+) for(int j=0;j10;j+) System.out.print(sij+ ); System.out.println( ); System.out.println(起重机最少作业次数：+count ); public class jizhuangxiang public static void main(String args) S

25、uijishu ss= new Suijishu(); ss.Generate(); ss.Move(); int max=s00;int q=0; for(int i=0;imax) max=s0i; q=i; /取最大的放在空位 for(int e=0;es1i) for(int j=i;j10;j+) if(s0j=0) if(s0is1j) s0j=s0i; s0i=0; count+; else if(s1j=0) s1j=s0i; s0i=0; count+; else if(s0i=0) for(int j=i;j10;j+) if(s0js1j) s0i=s0j; s0j=0;

26、 count+; if(s0j=0) if(s1j=s1i) s0i=s1j; s1j=0; count+; else s0j=s1i; s1i=0; count+; T+; for(int i=0;i10;i+) if(s1i=0) s1i=s0i; s0i=0; System.out.println(箱垛的样式： ); for(int i=0;i2;i+) for(int j=0;j10;j+) System.out.print(sij+ ); System.out.println( ); System.out.println(起重机最少作业次数：+count ); public class jizhuangxiang public static vo