集装箱堆场分配与自动化装载小车路径联合优化

　　摘要：为研究自动化装载小车（Automated Lifted Vehicle，ALV）在自动化集装箱码头的作业状况，首先考虑ALV自行装卸集装箱的能力，其次考虑卸船集装箱的堆场分配与ALV的路径联合优化问题，以每个集装箱在时间窗内完成装卸任务为目标建立混合整数规划模型，最后通过比较不同实验条件下求出的最优目标延迟时间和计算机运行时间，得出整个操作过程中ALV数、集装箱数和堆场子箱区数这三者之间的关系，数值实验表明：当集装箱数和ALV数一定时，随着装卸箱比例的增大，目标延迟时间和模型运算时间呈相同的变化趋势，即在既有装船箱又有卸船箱时应优先分配ALV满足装船箱的运输；当集装箱数一定时，随着ALV数的增加，目标延迟时间和模型运算时间逐步减少；当ALV数一定时，随集装箱数的增加，目标延迟时间和模型运算时间增加.
　　关键词：路径优化；集装箱堆场分配；自动化装载小车（ALV）
　　中图分类号：U653.7；U691.3
　　文献标志码：A
　　0 引言
　　集装箱码头是港口资源的重要集散地，它是连接陆路与水路运输的重要桥梁.在自动化集装箱码头用于集装箱操作的设备主要有3种：岸桥（QuayCrane，QC）、自动化装载小车（Automated Lifted Ve-hicle，ALV）和场桥（Yard Crane，YC）.在传统的装卸船操作中，若三种设备之间衔接不协调，则会造成设备之间等待的现象，如当岸桥从船上完成提箱时，若集卡未到达岸边，则出现岸桥等待集卡的情况.
　　但是，ALV在完成水平运输时可以减少等待时间.当岸桥完成提箱且ALV未到达岸边时，岸桥可以先将集装箱放在岸边的缓冲区，然后继续其他操作，而当ALV到达缓冲区时可以自行提箱完成水平运输，这样可以保证岸桥效率最大化，另外，当场桥正在提放集装箱时，ALV到堆场时可以自行将集装箱卸到堆场内的缓冲区，等待场桥在空闲时完成堆存.使用ALV作为运输设备，还可以降低工作人员的劳动强度，减少因工人操作不当而出现的失误，降低码头运营成本，
　　目前已有很多关于集卡的研究.BISH等研究自动引导车（Automated Guided Vehicle，AGV）和堆场分配问题，并考虑岸桥的装卸调度使其在算法上进一步完善，增加了分析性能研究.CAO等整合堆场内集卡与场桥的调度建立混合整数规划模型，但只考虑进口集装箱，运用组合分解方法求解模型.TANG等针对岸桥与集卡的联合调度问题建立混合整数规划模型，目标是最小化总工作时间，并用改进的粒子群算法解决单向进口箱和双向集装箱问题.秦天保等针对集装箱岸桥与集卡集成调度问题，以卸船完工时间最小化为目标，提出考虑任务顺序约束的岸桥与集卡联合调度的混合整数规划模型和约束规划模型，设计新的下界求法.曹庆奎等针对港口的集卡拥堵问题，探讨影响集卡作业效率的因素和集卡路径构成成本，建立面向＂作业面＂的港口集卡路径成本优化模型，利用遗传算法从集卡路径收敛、可变成本、惩罚成本和总成本变化等4个方面寻找最优解并进行对比.韩晓龙等针对集卡调度，考虑同一时段集装箱的装卸作业情况，以集卡运作时间最小为目标建立动态优化模型. LEE等为集装箱码头集卡车队调度建立混合整数规划模型，比较几种遗传算法的变体，并证明变体最优，王军等一引在＂作业面＂作业模式下，综合考虑岸桥作业时间、场桥作业时间的基于时间最短的集卡调度模型，解决对不同船舶同时进行装卸船作业的前提下集装箱码头集卡作业路径选择问题.曾庆成等运用系统工程优化理论，提出混合交叉作业集成调度方法和同步优化技术，以泊位分配、设备配置、集卡行驶路径为决策变量，以集装箱码头最小运营成本为目标函数，建立三阶段集成调度优化模型，并设计双层遗传求解算法.李浩渊根据不同时段的装卸任务量进行集卡的动态配置，运用仿真模型和优化算法，求解在满足码头作业效率的前提下集卡的平均等待时间，任大伟等从整体调度的角度分析整个码头作业面的动态调度方案，提出一种新的集卡动态调度路径的自适应蚁群算法.康志敏在动态＂作业面＂调度模式下，同时进行装卸作业，把集装箱在前沿和堆场之间的转移看作一个调度任务，建立以无效等待时间最少为目标的AGV调度优化模型，并利用遗传算法求解.
　　关于ALV的调度问题的研究较少.NGUYEN等根据时间窗约束为ALV分配集装箱，并设计相关算法获得最优解.VIS等、YANG等等通过仿真比较不同自动化运输设备的绩效，主要是AGV与ALV之间的比较.
　　ALV是一种新型设备，目前关于该设备的研究较少，该设备具有自行提箱和卸箱的功能，能充分发挥岸桥和场桥的功能，并且减轻码头工人的劳动强度，避免操作上出现失误，本文将结合集装箱堆场分配考虑ALV运输路径优化，为未来研究相关问题提供参考，首先确定卸船集装箱的位置去向，然后根据每个集装箱的初始位置和目的位置分配ALV，最后根据每辆ALV分配任务确定ALV的装卸顺序，使任务尽可能在时间窗内完成，也就是说使产生的总延迟时间最小.
　　1 问题描述
　　一般来说，码头上通常是几辆集卡同时服务一台岸桥，充分满足岸桥的作业效率.如一台岸桥要卸30个集装箱，那么由6辆集卡轮流运输完成任务，造成集卡的效率较低，空载率较高，针对这种现状，本文在多辆集卡同时服务多台岸桥的基础上，充分利用ALV的自行提箱和卸箱功能，减少等待时间，最大化满足岸桥效用.如ALV在完成运输装船箱之后，等待岸桥提供卸船箱（或直接装载暂堆存在岸边缓冲区的卸船箱）或者空载到另一台岸桥的位置装载卸船箱（或装载暂堆存在岸边缓冲区的卸船箱），然后运输卸船箱到目的堆场位置，此时，ALV没有产生等待或只空载运输一台岸桥到另一台岸桥的距离，能充分发挥岸桥的效用，实现ALV自行提箱和卸箱，有效降低工人劳动强度，减少码头的运营成本，避免码头出现罢工等状况，相对加快港口货物吞吐，提高码头的整体效益.
　　另外，堆场箱区通常只能配备一台或两台场桥，为避免出现箱区繁忙程度不均等现象，通常为每艘船在堆场内预留几个分散的子箱区堆存从该船卸下来的集装箱，如图1所示：编号为6，22，35和95的子箱区是为船1预留的，而编号为8，13，100和103的子箱区是为船2预留的，这样可以最大化场桥的使用率，另外，装船箱在堆场堆存的位置和岸边装船位置已经确定；对于卸船箱，它们选择不同的目的子箱区，造成ALV完成两个连续运输任务的距离不同，影响码头效益，因此，针对卸船箱的堆场分配和ALV高效运输，考虑卸船箱堆场分配与ALV运输路径联合优化问题，最大化地利用堆场和满足码头水平运输，提高码头综合效益. 
　　   2 模型分析
　　假设：所有的ALV具有相同的属性，并且每辆ALV -次只能运输一个集装箱；与传统的集卡分配策略不同，本文采用ALV运输策略满足分配过程，即通过一辆ALV服务多台岸桥提高ALV与岸桥之间的协调配合能力和充分发挥ALV具备的自提自卸功能，优化码头效益.
　　2.1 模型参数
　　2.2 决策变量
　　如果把任务i分给子箱区k，则Xik=1，否则Xik=0；如果第r辆ALV运输完任务i后马上运输任务j，则Yijr=1，否则Yijr=O；如果任务i是分配给第r辆ALV运输的，则Zir=1，否则Zir=0；Wi为开始服务任务i的时间；mi为完成任务i的时间；di为任务i的延迟时间；ti为任务i的运输时间；sij为ALV从任务i的目的地到任务j的初始位置的空载运输时间.
　　惩罚因子α表示尽可能使装船箱在最晚完成时间之前完成装船，如果没有完成装船将产生惩罚值.惩罚因子β表示尽可能使卸船箱i在最早能够开始运输时就开始运输，避免卸船箱在岸边堆存时间过长，影响整个码头效率，由于装船箱在岸边产生的影响远远大于卸船箱，因此将α设为0.9，β设为0.1，α十β=1.
　　式（1）表示目标是使产生的总惩罚值最小，也就是使超出时间窗范围外的延迟时间最短；式（2）表示一个集装箱只能存放在一个子箱区内；式（3）-（5）表示每辆ALV的作业箱量平衡；式（6）表示每个任务只分配给一辆ALV运输；式（7）表示如果使用这辆ALV，那么它一定会有前项任务，保证运输量平衡；式（8）表示作业任务的先后顺序；式（9）表示每个任务的开始时间必须晚于它可以开始作业的时间；式（10）表示每个任务的完成时间；式（II）表示每个任务的装卸延迟时间；式（12）和（13）表示任务的操作时间；式（14）和（15）表示一辆ALV在一个任务到另一个任务之间的准备时间；式（16）-（18）表示0-1整数约束；式（19）-（22）为非负约束.
　　2.3 线性转换
　　从数学模型可以直观地看出，约束（15）是非线性约束，不便于以后的计算，为减少计算时间，提高模型的可行性，要把非线性约束转换成线性约束：3数值实验
　　3.1 案例分析
　　通过简单的实例描述本文研究的问题，分配卸船箱的堆场子箱区，完成ALV在简单运输过程中的路径优化.表l描述ALV在整个运输过程中的路径优化和堆场分配，
　　根据FIFO规则得出编号为2的ALV按3―5―7―8的顺序运输路径最优，则ALV在码头上的运输路径为0-5-b-4-b-b-15-a-5-0（总行走路程为2800m）.与表2中的最优路径对比可以明显看出，该模型通过合理分配卸船箱的位置能够优化ALV的运输路径，减少ALV的运输路程，使码头总体效益最优，
　　3.2 数值实验
　　采用处理器为Intel（R） Core（TM）2 Duo CPUT6570@2.10GHz的计算机，利用软件Cplex10.0.O求解模型得出结果，
　　所有的实验数据是根据实际情况随机产生的，主要用于验证模型的正确性并分析实验得出结论，在（1s，200s）之间产生时间窗，即产生最早可以开始时间和最晚允许完成时间，设定ALV在场内运行的速度为10m/s.简化上海洋山港自动化码头的堆场布局，在（O，650m）与（O，350m）之间建立二维坐标，设定30个子箱区，并且设定岸桥数为2.只考虑装卸箱在岸边的延迟所造成的惩罚值，这是因为岸桥是码头作业中的瓶颈，需要优先满足岸桥作业，如果装船箱超出最晚允许完成时间完成装船，则它影响后续操作，甚至波及码头的效益；如果卸船箱未及时在最早可能开始时间内被ALV运输，将导致其占用岸边缓冲区的时间太长，也会影响后续作业，
　　设计多组实验用以分析评估模型的正确性，结果见表3.图2-4分别从不同角度比较各组实验，分析ALV数与任务数之间的关系.
　　图2总共分为3组数据，总体上看，目标延迟时间和模型运算时间波动比较大，整体呈相同的变化趋势，当ALV数一定时，随着任务数的增加，目标延迟时间和模型运算时间呈增加趋势，但当任务数为9或10时目标延迟时间反而减少的情况，这是不正常的，在分析中将这两列数据作为异常情况排除.
　　在任务数相同的情况下不同的ALV数对目标延迟时间和模型运算时间的影响见图3.整体上看，任务数相同时，随着ALV数的增加，由于每辆ALV相对运输的任务数在逐渐减少，目标延迟时间不断减少，且模型在分配集装箱堆场箱区时所用时间较少，故模型运算时间减少.从图3可明显看出，目标延迟时间呈现凹字型结构，在任务数比较少和比较多的情况下产生的目标延迟时间都比较长，当任务数为9或10时，ALV运输时产生的目标延迟时间较少，这可能是由于初始值比较优越，在分析中可将其作为异常情况排除，
　　在任务数一定的情况下不同的装船箱数与卸船箱数比例对目标延迟时间和模型运算时间的影响见图4.从横向上看，随着ALV数增加，相等装卸箱比例条件下，目标延迟时间和模型运算时间呈减少趋势，但是在ALV数为4且装卸箱比例较大时目标延迟时间和模型运算时间明显比ALV为3时长，这是因为对于少量集装箱任务，分配ALV过多反而会造成模型在优化ALV的运输路径时产生更长的目标延迟时间；从纵向上看，当任务数和ALV数一定时，装卸箱比例增加，导致优化ALV的运输路径较慢且目标延迟时间较长，因此，在任务数和ALV数一定时，ALV应优先满足装船箱的运输.
　　4 结束语
　　研究自动化码头的集装箱堆场分配与ALV路径联合优化问题，充分结合现代化码头边装边卸的模式，减少ALV的空载运输.利用ALV的自装自卸优势，大大提高港口设备利用率，并结合卸船箱的位置分配，优化ALV的运输路径，提高堆场利用率，
　　本文通过比较不同集装箱任务数、ALV数和堆场子箱区数的模式组合，得出结论：当集装箱任务数和ALV数一定时，随着装卸箱比例的增大，目标延迟时间和模型运算时间也呈相同的变化趋势，因此，在既有装船箱又有卸船箱时应优先分配ALV满足装船箱的运输；当集装箱任务数一定时，随着ALV数的增加，目标延迟时间和模型运算时间在逐步减少；当ALV数一定时，随着集装箱任务数的增加，目标延迟时间和模型运算时间也增加，本文研究协调优化ALV的运输路径和集装箱的箱区分配，具有一定的理论应用价值，可为今后的相关研究提供参考.