文档介绍：该【港口集装箱堆场箱位分配问题研究 】是由【科技星球】上传分享，文档一共【12】页，该文档可以免费在线阅读，需要了解更多关于【港口集装箱堆场箱位分配问题研究 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。港口集装箱堆场箱位分配问题研究
 
 
Summary:集装箱堆场箱位分配策略对作业效率和空间利用影响较大,将堆场装卸作业时间成本和堆场空间成本作为优化目标,建立箱位分配的数学模型,分别采用贪心算法、遗传算法进行求解,并与三种传统堆垛方式对比。计算结果表明,贪心算法与遗传算法生成的相对传统堆垛方式优势显著,模型中双优化目标权重系数随堆场拥挤程度变化会有更好的效果。
Keys:集装箱;箱位分配;贪心算法;遗传算法
0引言
目前港口已经可以实现自动化作业,而自动化港口集装箱堆场中箱位如何分配是一个较为重要的问题,高效的分配策略能大大提高作业效率。集装箱进入堆场的箱位分配策略对作业中的搬运距离、翻箱次数以及堆场空间利用影响较大。随着集装箱堆场的规模增大,人工分配箱位计划性差、堆场利用率低、翻箱次数高等缺陷愈发显著,而通过计算机来自动分配可有效改善这些问题。
对于箱位分配策略的研究,主要集中于作业成本的最小化,而不同的研究中采用了不同的目标函数来表征作业成本。在不同的堆码模型中,分别定义了堆场的叠压度、自由度、翻箱量等概念,用于权衡堆垛作业中的作业成本。江南等[1]通过划分堆场集装箱集合,建立了静态码垛模型;关于集装箱的对方顺序定义了全序关系,建立了动态的码垛模型,并设计了对应判定、码箱、取箱算法;再考虑取箱时暂扣空箱,建立了循环箱码垛模型,设计了对应码箱、取箱算法。王金红[2]首先根据运输货物性质划分箱大区,根据物流情况和常见货主划分箱小区;其次,提出大宗货物自由度与零散货物叠压度的定义;在之前基础上,建立了大宗货物集装箱码垛模型和零散货物集装箱码垛模型,设计了堆垛算法,并验证了算法的可行度。谢颖[3]考虑了翻箱的原因、对作业成本和效率的影响,归纳了降低翻箱量的策略,建立了以码箱取箱成本最低为目标的码箱箱位优化模型,并通过模拟仿真验证了模型的可行性。
1问题描述
,为一个码头的简易示意图,港口衔接了海运与陆运两种运输方式。来自海运的集装箱通过岸桥从船舶上卸下后,通过港口内部集卡、AGV等水平搬运设备与堆场门吊进入堆场,等待下一步作业;来自陆运的集装箱直接通过堆场门吊直接进入堆场,等待下一步作业;而在堆场内的集装箱,通过陆运离开则直接由门吊装载至外部集卡、列车等运输工具上,通过海运离开则通过岸桥装载至船舶上。
在如今通信技术较为发达的时代,船舶、列车等运输方式均具备一定的计划性,可以根据计划、天气等因素,对其到达港口的时间进行预测,即可以由此来预测对应集装箱离开堆场的时间,计算出压箱情况下发生翻箱作业的可能性。
人工作业传统堆垛方式主要有垂直式、平铺式、阶梯式三种。
(1)垂直式堆放:集装箱由离列车轨道较远的一侧堆往靠近列车轨道一侧,堆满一栈才队下一栈。这种堆码方式的优点是堆垛较为紧凑,空间利用率高;缺点是容易导致压箱,取箱时需要进行翻箱作业,增加作业成本。
(2)平铺式堆放:集装箱由最下面一层往上堆,堆满一层才开始堆上面一层。这种堆码方式优点是在集装箱不多时取箱方便,不易产生压箱现象;缺点是堆垛不紧凑,空间利用率低,所需面积大。
(3)阶梯式堆放:集装箱以阶梯的方式堆垛,特点介于垂直式与平铺式之间。
2箱位分配模型
(1)待分配箱位的集装箱均为普通集装箱,不考虑特种箱;
(2)引入集装箱属性概念,属性根据集装箱离场情况划分,同批次离开堆场的集装箱属性相同。同属性的集装箱会一起离开堆场或者在上方的优先离开,即同属性箱之间不会发生翻箱作业;
(3)不同属性的集装箱堆叠在同一栈一起称为压箱。产生压箱时,若下面的集装箱先离开堆场,则须进行翻箱作业。
(4)集装箱离开堆场关于时间的概率密度函数可以由统计得知;
(5)待分配集装箱只有40英尺标准集装箱堆垛;
(6)不考虑作业目标箱位的堆垛高度,都视为需要相同时间的堆垛过程;
——允许堆垛的最高层数;
——一次翻箱作业平均时间;
——待分配的第个集装箱;
——集装箱属性;
——集装箱箱位;
——箱位上的集装箱数量
——坐标位置,,其中表示某个坐标,表示沿贝方向、排方向的坐标,表示垛的坐标位置,表示集装箱的来源坐标,表示集装箱的预计离开坐标;
——箱位分配策略,,其中为分配给第个集装箱装卸的箱位;
——时刻尚未离开货场的集装箱,离开货场关于时间的概率密度函数;
——从到搬运预计时间,,其中表示抓取平均时间,表示落箱平均时间,表示起重机沿轨道速度,
表示起重机小车速度;
——空间占用率权重系数;
——暂扣标记;
——判别是否为0函数,。
(1)堆垛的集装箱不会超过最高层数:
(2)保证分配的箱位未被标记,即分配的箱位不处于或者将要处于作业状态:
(1)减少搬运距离
发送箱、中转箱需要考虑与将要装载列车车厢的距离,因为列车采用脱钩甩尾的方式,越靠近最终目的地的集装箱越应放在列车靠前部分,所以考虑减少起重机搬运距离的情况下,集装箱应尽量靠近预计装车位置。
(2)减少翻箱
当集装箱在集装箱下方,且箱属性不同时,集装箱的因要先取集装箱而翻箱概率为,则对于一个即将进入货场的集装箱,预估其翻箱概率为其下方集装箱早于其离开货场的概率,其下方集装箱包括原本货场中同一垛的和将先于其落在这一垛的集装箱,故预计这次落箱后整个货场增加的翻箱时间为:
其中,
(3)减少场地占用
综上,本模型优化目标为:
3模型求解
(1)贪心算法——单箱局部最优
由以上模型描述可知,每个集装箱将要堆放的位置为因变量,目标函数的值受到多个因变量的影响。同时,因变量之间也会互相影响。此外,因变量——集装箱箱位分配策略的变化与目标函数大小变化的之间的数学关系较为复杂,并不直观,即无法通过因变量的变化大致判断目标函数的变化趋势。对于此类数学模型,因变量越多,则求解难度越大,计算复杂度越大。因此将一组多个集装箱的箱位分配问题转化为多组单个集装箱的分配问题,对每个集装箱
分配当前根据模型判断出的最优箱位,由此生成一组集装箱的箱位分配策略。该策略不一定是全局最优解,但一般为相对较优解。
(2)针对箱位优化的遗传算法
本模型的优化对象为集装箱的分配箱位,直接将优化对象作为染色体进行优化,以数学模型中对箱位分配策略的优化目标函数(优劣评估函数)的倒数作为适应度,设计一种遗传算法对模型进行求解。
染色体编码规则:对于个集装箱的堆码问题,染色体分为段,其中每一段为对应集装箱分配的垛位,具体数值由贝号和列号计算得到:(贝号-1)×6+列号,例如:4对应1贝4列,15对应3贝3列,36对应6贝6列。染色体则由个这样的数值组成,如对10个集装箱的堆码问题,染色体{4,15,36,11,25,15,14,36,8,2},代表着堆码策略{1贝4列,3贝3列,6贝6列,2贝5列,5贝1列,3贝3列,3贝2列,6贝6列,2贝2列,1贝2列}。
(3)针对贪心算法求解顺序优化的遗传算法
上一个算法主要存在两个问题:第一,堆场箱位数量较大,解空间过大,找到最优解难度较大;第二,初始化、交叉、变异过程中可能会生成不合格的染色体,需要剔除后重新生成合格的染色体,由此在特定条件下可能导致计算量过大或者死循环。因此,设计对贪心算法求解顺序进行优化的遗传算法,寻找最优顺序来进行贪心算法,获得较优解。
染色体编码规则:对于个集装箱的堆码问题,染色体分为段,其中每一段为对应集装箱进行箱位分配的优先度值,优先度值较小的集装箱先分配
箱位,如对10个集装箱的堆码问题,染色体{,,,,,,,,,},代表着求解顺序{6→5→2→1→10→7→3→9→8→4},按该顺序采用贪心算法进行计算即可得对应箱位分配策略。
将三种传统堆码方式:垂直式堆码、平铺式堆码和阶梯式堆码和上文中描述的两种算法:贪心算法和通过遗传算法优化计算顺序的贪心算法进行模拟仿真对比堆码效果。因为在具体计算中发现采用遗传算法直接对箱位进行优化,优化效果一般且计算时间很长,在算例中并没有分析直接对箱位进行优化的遗传算法,故下文中的遗传算法指的是针对贪心算法计算顺序优化的遗传算法。
(1)五种箱位分配策略对比
,垂直式堆码预计作业所需时间较长,主要原因是预计翻箱率较高,但优点是占用箱位较少;垂直式堆码作业预计翻箱率相对垂直式和阶梯式较低,但占用箱位最多;阶梯式效果介于垂直式与平铺式之间;采用贪心算法求解的堆码策略在预计作业时间、预计翻箱率方面,相对三种传统堆码方式都有很大的优化,占用箱位数方面有所优化;而采用遗传算法优化计算顺序的贪心算法求解结果,相对于贪心算法各方面都有所优化,但优化幅度并不大。
(2)空间利用率权重系数对堆垛效果的影响
空间利用率权重系数在模型中是一个较为重要的参数,其对于时间成本和空间成本的侧重有较大影响,在港口不同时期应采用不同的空间利用率权重系数。