集卡调度中的关键问题

    颜银慧

    

    【摘 要】 为提高集装箱码头集卡调度的有效性，通过分析其现有的研究成果，结合码头实际作业需求，提出集卡调度中的关键问题并给出解决方法，并从精细化管理的角度出发，首次提出集卡运行总成本的评价指标，用以评价集卡调度的有效性。

    【关键词】 集卡；调度；重载率；评价指标

    0 引 言

    随着港口竞争的不断加剧，如何提高码头作业设备利用率，降低作业成本已经成为码头公司提高服务水平、提升自身竞争力的重要研究课题。船舶在码头的停留时间和完成装卸作业的时间是衡量码头作业水平的重要指标，而该指标与码头作业设备的作业效率息息相关。集装箱卡车（简称集卡）作为连接码头水平运输和垂直运输的桥梁，其作业效率对整个码头的作业效率有着至关重要的影响。因此，集装箱码头的集卡调度问题已经成为国内外研究热点之一。

    NG等[1]以集卡总体作业耗时最小化为目标，将集卡调度问题转化为混合整数规划MIP问题，采用遗传算法进行求解；XUE等[2]从码头的实际作业出发，考虑装卸船作业的先后顺序，通过建立混合整数规划模型，运用两阶段算法即蚁群算法（Ant Colony Optimization）和贪婪算法（Greedy Algorithm），为集卡分配作业指令；BISH等[3]基于码头的作业规则，采用启发式算法动态地给集卡指派作业任务。

    集卡调度问题属于NP难问题，而穷举法过于耗时，因此许多学者提出各种近似的方法来求解集卡调度问题，以不断提升调度算法的性能和优化效果。

    1 集卡调度中的关键问题

    集装箱码头的常规作业主要包括装船、卸船、堆场移箱作业和进提箱作业。码头作业的常用设备包括岸桥、场桥和集卡等。卸船作业的基本流程为：岸桥将集装箱从船上卸到岸边的集卡上，然后集卡将该集装箱运至堆场指定位置，再由堆场的场桥从集卡上将集装箱吊起放至堆场指定位置。装船作业流程则与卸船作业流程相反。

    在传统的调度模式下，码头调度人员为单个工作点（如对应一辆岸桥）固定分配一批集卡，通常为5～7辆，并独享该工作点下的所有集卡资源。但在这种调度模式下，各个工作点忙闲程度不一，需要集卡的工作点得不到集卡资源，容易出现集卡载着集装箱从堆场到岸边，最后空车返回堆场，造成集卡空载率（距离）较高（约为50%），利用率较低。

    现有的调度算法很难在生产环境中得到应用，主要有以下原因：（1）算法耗时过长，往往超过1 min（以30辆集卡为例），很难满足码头作业的实时性要求；（2）调度的首要目标是保证船舶作业按时完成，实现船舶按时离泊，码头的作业能否按时完成，取决于岸桥的作业效率和岸桥、场桥以及集卡的协同作业，而现有的调度算法通常假设岸桥/场桥数量足够，完全能够满足集卡的作业需求，即集卡在岸桥/场桥下不需要等待。

    集卡调度问题可以简化为传统的配对问题，即合理地为集卡与指令进行配对。据了解，基于运用成本最小原则，集卡指令配对模型已为业界一些领先的集装箱码头操作管理系统供应商所采用。本文基于集卡指令配对模型，从码头的实际需求出发，探讨集卡调度中的一些关键问题：

    （1）由于码头作业的复杂性，在实际作业场景中，设备的作业时间和状态变化较大，要求调度算法必须根据实际作业情况的变化，动态地为集卡分配指令。

    （2）调度算法的实时性。在码头的实际作业过程中，要求调度算法实时地为集卡分配指令，通常分配时间（计算周期）应小于2 s。在设计调度算法时，可以充分利用相邻两次计算的相似性，即当次计算可以利用上一次计算信息，缩短算法的计算时间，满足实时性需求。针对集卡调度，可采用改进的Dynamic Hungarian Algorithm算法。

    （3）在集卡指令配对模型中，集卡完成作业指令的代价计算是调度算法的核心部分。如果仅仅考虑集卡参与作业所需要行使的路程，往往导致工作点距离作业箱区较近的岸桥分配的集卡较多，甚至出现拥堵，从而出现岸桥忙闲不一，造成集卡资源浪费。为此，需要考虑岸桥/场桥是否需要集卡，即集卡能否准时到达岸桥/场桥下，尽量使需要集卡的岸桥/场桥能够得到集卡。

    针对集卡完成作业指令的3种场景进行相应的分析，结果如表1所示。

    通过对以上3种场景的分析来看，集卡完成作业指令最为合适的代价计算应是集卡运输时间、集卡早到时间和集卡晚到时间三者的加权总和，即 €%[ €准ㄐ惺皇奔洌？€%d €准ㄔ绲绞奔洌？€%e €准ㄍ淼绞奔洌渲？€%[， €%d， €%e为权重参数。为了减少集卡早到和晚到情形的出现， €%d和 €%e应满足 €%d>€%[和 €%e>€%[。在实际码头应用中，需要结合码头的实际情况不断摸索和总结，设置合理的参数，以达到最优的调度效果。

    2 集卡调度的评估

    为评估集卡调度的有效性，业界有些专家提出以下评价指标：重载率（时间维度）、重载率（距离维度）、重来重去率。各指标的定义如下：

    重载率（时间）=重载时间/集卡运行时间

    重载率（距离）=重载距离/集卡行驶距离

    重来重去率=集卡背重箱次数/集卡背箱总次数

    事实上，集卡重车在堆场或者岸边等待可提高集卡重载率（时间），但重载率高不一定能够反映集卡调度效果好。在岸边完成装船作业的集卡通过等待直至获得卸船作业任务，以此提高重来重去率，但也有可能导致岸边集卡过多，造成交通拥堵。

    基于精细化管理角度，应从集卡本身出发，以集卡成本来评估集卡调度的优劣。在码头作业中，集卡运行成本由以下部分构成：集卡空车运行成本、集卡空车等待成本、集卡重车运行成本和集卡重车等待成本等。通过无线射频识别（RFID）技术或者集卡司机按键确认到达等手段，码头可以记录集卡到达目标作业的时间，统计出集卡空车运行时间（T空运）、集卡空车等待时间（T空等）、集卡重车运行时间（T重运）和集卡重车等待时间（T重等）；根据历史经验数据和集卡行业相关信息，码头可获得单位时间内集卡空车运行油耗（C空运）、集卡空车等待油耗（C空等）、集卡重车运行油耗（C重运）和集卡重车等待油耗（C重等）。因此，码头集卡运行的总成本M总=T空运€證空运+T空等€證空等+T重运€證重运+T重等€證重等。在作业任务一定的条件下，同时确保岸桥作业效率，集卡运行的总成本可以用来衡量集卡调度的优劣。

    3 结 语

    集卡调度是码头作业设备调度的核心问题之一。如何评估集卡调度的有效性，需要建立科学的评估指标。当前业界评估指标存在缺陷，因此，从精细化管理角度出发，本文首次提出集卡运行总成本的评估指标，并给出相应的计算公式，而对于设计合理的集卡调度系统及运用本文提出的集卡调度评估指标来不断优化系统将是下一步研究方向。

    参考文献：

    [1] NG W C，MAK K L，ZHANG Y X.Scheduling trucks in container terminals using a genetic algorithm [J].Engineering Optimization，2007，39（1）：33-37.

    [2] XUE Z J，ZHANG C R，MIAO L X，et al.An ant colony algorithm for yard truck scheduling and yard location assignment problems with precedence constraints [J].Journal of Systems Science and Systems Engineering，2013，22（1）：21-37.

    [3] BISH E K，CHEN F Y，LEONG Y T，et al.Container terminal and cargo systems [M].Berlin：Springer Berlin Herdelberg，2007.