集装箱码头泊位计划的鲁棒优化模型.pdf

第 卷 第 期运 筹 与 管 理 ， 年 月 收稿日期：- - 基金项目：国家自然科学基金资助项目（， ）；教育部“新世纪优秀人才支持计划”（- - ） 作者简介：曾庆成 （- ），男，教授，工学博士，研究方向，港口与物流系统优化。 集装箱码头泊位计划的鲁棒优化模型 曾庆成 ， 赵孝峰 ， 胡祥培 ， 杨忠振 （ 大连海事大学 交通运输管理学院，辽宁 大连 ； 大连理工大学 系统工程研究所，辽宁 大连 ） 摘 要：针对集装箱码头作业中的不确定性因素，构建泊位计划的鲁棒优化模型与算法，目的是降低不确定性因 素对集装箱码头作业系统的影响。 首先，提出泊位计划鲁棒性度量指标，利用算例对各指标的效果进行分析。 在此基础上，设计泊位计划鲁棒优化的两阶段优化算法。 算法的第一阶段不考虑泊位计划的鲁棒性，以船舶总 延误时间最小为目标；算法的第二阶段以所选择的鲁棒性指标最大为目标，以第一阶段获得的船舶总延误时间 为约束条件，获得鲁棒调度方案。 最后，研究作业资源（装卸桥数量）的变化对泊位计划鲁棒性的影响。 算例分 析表明，权重松弛量是有效的度量泊位计划鲁棒性的指标，两阶段算法可以有效解决泊位计划鲁棒优化问题。 关键词：物流工程；泊位计划；鲁棒优化；集装箱码头 中图分类号： 文章标识码： 文章编号：- （）- - Robust Optimization Model for Berth Planning Problem in Container Terminals - ， - ， - ， - （ School of Transport Management， Dalian Maritime University， Dalian ， China； Institute of Systems Engineering， Dalian University of Technology， Dalian ， China） Abstract： ， ， ， ， - - ： - ， ， （ ） - - Key words： ； ； ； 引言 泊位是集装箱码头的重要作业资源，合理的泊位计划是提高码头生产效率，减少船舶延误的重要因 素。 但在集装箱码头作业过程中存在各种不确定性因素，如作业事故、设备故障等。 这些事件的发生可能 会打乱原有泊位计划，对正常作业造成巨大干扰，引起大量的额外成本。 因此，如何有效地处理这些不确 定性因素，减少其对码头作业系统的影响，已成为集装箱码头作业调度领域的重要问题。 本文拟在泊位计划制定阶段，通过提高泊位计划的鲁棒性，降低不确定性对集装箱码头作业系统的影 响。 为此，需要解决两方面的问题：一是如何选择鲁棒性度量方法与指标；二是如何在调度方案鲁棒性与作 业成本之间做出平衡。 本文首先在不考虑不确定性因素的情况下，建立泊位分配模型，然后，建立泊位计划 鲁棒性度量方法，设计优化泊位分配方案的两阶段算法，研究泊位计划鲁棒性与作业资源投入的关系。 国内外研究现状 国内外学者针对泊位分配问题开展了大量的研究，代表性研究如， 等 、 和 等 建立的离散型泊位分配模型，以及 等 ， 和 等 建立的连续泊位分配模型。 由于泊位分配与 装卸桥调度相互影响，船舶作业时间在很大程度上取决于装卸桥的分配，而装卸桥的调度也要依据泊位计 划，受泊位计划的约束。 因此，一些研究关注泊位与装卸桥的集成调度问题。 如 和 建立了同 时优化船舶停泊位置、停泊时间、以及装卸桥配置的混合整数规划模型。 等 采用离散泊位分配方 法，建立了泊位计划与装卸桥调度模型。 等 建立了泊位分配- 装卸桥调度模型，与前两个模型不同 的是，模型中考虑了装卸桥配置数量对装卸桥平均作业效率的影响。 上述研究主要面向确定性环境，近年来，不确定性环境下泊位与装卸桥调度问题受到越来越多的关 注。 一种方法是在泊位计划阶段，通过考虑不确定性因素，提高调度方案抵御不确定性干扰的能力。 如， 等 考虑船舶到达时间、装卸桥作业时间不确定性的基础上，建立了泊位分配- 装卸桥调度模型，目 的是获得泊位与装卸桥的鲁棒调度方案。 周鹏飞和康海贵 基于随机规划方法，构建了随机环境下泊 位- 岸桥分配模型。 和 建立的泊位分配的多目标模型，同时优化作业成本和泊位计划的鲁 棒性。 另一种方法是研究不确定性干扰事件发生后，如何调整泊位计划，以减小干扰事件的影响。 如曾庆 成等 分析了干扰事件对泊位分配与装卸桥调度的影响，建立了集装箱码头泊位分配- 装卸桥调度的干 扰管理模型。 虽然这两种方法分别从事前与事后角度处理不确定性因素，但事实上，二者是相互联系的。 如在泊位 计划制定阶段，可以通过提高鲁棒性，减低方案调整的难度和调整的成本；而干扰事件的分析与评价，也有 利于鲁棒调度策略的制定。 鲁棒调度作为研究不确定环境下生产调度问题的一种重要方法，近年来受到 国内外学者的广泛关注，出现了大量的研究成果（ 等 ），但由于不同鲁棒调度问题差异较大，其鲁棒 调度模型与策略存在较大差异。 尽管泊位计划鲁棒调度已有一些研究成果（ 等 ），但泊位计划的鲁 棒性度量、以及泊位计划鲁棒性与成本之间的权衡等问题还需要进一步研究，这些都是泊位计划鲁棒调度 中的关键问题。 泊位分配模型 采用连续型泊位分配方法，同时优化泊位分配与装卸桥调度计划，即优化每艘船舶的停泊位置、停靠 时间、以及装卸桥配置数量。 模型参数与变量假设如下： 模型参数： L：泊位岸线总长度，将岸线划分为若干以 米为单位的单元； N：一定时期内停靠船舶的总数； Q：装卸桥配置总数； T：以小时为单位的若干时间点的集合； ai：船舶 i 预计到港时间； di：船舶 i 预计离港时间，此时间通常由船公司与码头协议确定； li：船舶 i 的长度，以 米单元数量表示； q L i：同时服务于船舶 i 的最小装卸桥数量； q U i：可同时服务于船舶 i 的最大装卸桥数量； wi：完成船舶 i 作业需要的装卸桥总台时数； M：一足够大的常数。 决策变量： 运 筹 与 管 理 年第 卷 xi：船舶 i 的停靠位置； yi：船舶 i 的停靠时间； ei：船舶 i 作业完成时间； ritq 在 t 时刻分配给船舶 i 的装卸桥数为 q； 其他 Z x ij 船舶 i 停靠在 j 的左侧； 其他 Z y ij 船舶 i 先于 j 停靠； 其他 假设泊位水深能充分满足船舶停靠要求，装卸桥单位作业效率不受同时作业装卸桥数量的影响。 于 是，泊位分配模型可以表示为： N i （，eidi）（） iNqRiq r itq尘 Q，橙t T （） z x ijz x jiz y ijz y ji辰，橙i，j ，N，i j （） qRir itqrit，橙i ，N，橙t T （） tT riteiyi，橙i ，N（） qRitT q ritq辰 wi，橙i ，N（） xili尘 xjM（ z x ij），橙i，j ，N，i j （） ei尘 yjM（ z y ij），橙i，j ，N，i j（） yi辰 ai，橙i ，N（） xi ，L li，橙i ，N（） Ri （q L，qU i），橙i ，N（） z x ij，z y ij，or ，橙i，j ，N，i j （） 式（）为目标函数，表示最小化船舶延误时间。 式（）表示装卸桥数量约束，式（）避免两艘船舶之间 在停靠时间与停靠位置上的冲突，式（） （）表示每艘船舶作业开始与结束时间的关系，式（）表示两艘 船舶停靠位置之间的关系，式（）表示两艘船舶停靠时间的关系，式（）保证每艘船舶在其到港时间之后 停靠，式（）保证每艘船均停靠在岸线范围内，式（）表示分配给每艘船舶的最大与最小装卸桥数。 泊位计划鲁棒性度量 3 1 鲁棒性度量指标 鲁棒性度量是优化鲁棒调度方案的基础，在优化调度方案时，通过优化鲁棒性度量指标，可以提高调 度方案吸收不确定性干扰的能力。 目前，机器调度领域的鲁棒性度量问题得到了较多的研究 ，主要的 方法包括基于后悔值、最差情景、领域度量、松弛度量等方法。 本文基于松弛度量方法，提出以下泊位计划 鲁棒性的度量指标： （）平均松弛 在泊位计划中，某一艘船舶作业的松弛量定义为在不影响后续船舶作业开始时间的前提下，其作业开 始时间的最大延误量。 si LSi ESi（） 其中，si表示在泊位计划中，船舶 i 的松弛量，ESi表示船舶 i 作业最早开始时间，LSi表示在不影响后 续船舶的情况下，船舶 i 作业最晚开始时间。 于是，泊位计划的松弛量可以表示为： 第 期 曾庆成，等： 集装箱码头泊位计划的鲁棒优化模型 RM N i si（） （）权重松弛量 RM假定每艘船舶具有相同的权重，事实上，后续作业任务多的船舶，其延误造成的影响大于后续作 业任务较少的船舶，因此，用权重松弛量考虑后续作业船舶量的影响： RM N i NSisi（） 其中，NSi表示船舶 i 的后续作业船舶数，可以表示为： NSi N i Z y ij （） 另外，可以以船舶的作业量作为权重，设置一下两个指标： RM N i wisi（） RM N i NSiwisi（） （）松弛函数 上述 个度量指标假设每单位的松弛量的边际影响相同，这可能会过分高估某些任务松弛的影响，尤 其是当某作业任务松弛量非常大时。 为此，采用松弛效用函数度量，即： RM N i NSie si （） 同时，可以采用有效松弛量度量（RM），其中，frac 表示比例系数。 当某一作业任务的松弛量较小时， 将其计算到总松弛量中，而当某一作业任务松弛量较大时，只将其潜在的有效部分计算到总松弛量中，即： RM N i （si，wifrac）（） 另外，以 - （i）变量代替 si进行度量，当泊位计划中船舶 i 存在松弛量时，i ，否则 。 其计算 公式如式（）所示： RM N i i（） （）其它指标 另外，结合按照以上方法，设置以下指标： RM N i （si，wifrac） NSi（） RM N i iNSi （） RM Var（SD） SD （） 其中， SDisi wi，SD N i SDi n 。 3 2 指标评价方法 首先，对于通过泊位分配模型（） （）获得的泊位计划方案，计算其船舶总延误时间（即计划延误 时间）。 然后，利用模特卡罗发生成多个仿真情景，计算这些情景下船舶总延误时间（即实际延误时间）， 以及鲁棒性指标 RMi（i ，）。 最后，计算鲁棒性指标与 PM，PM之间的相关性，选择相关性大的 指标作为泊位计划鲁棒性度量指标。 其中，PM表示在所有的仿真情景中，船舶实际延误小于计划延误的比例，即，PM （实际延误大于 计划延误的情景） 情景总数；PM表示船舶实际延误与计划延误之间的差异，即，PM （平均实际延误 运 筹 与 管 理 年第 卷 计划延误） 计划延误 具体评价方法过程如下： （）泊位分配方案产生 首先，求解式（） （）所示泊位分配模型，获得初始泊位分配方案。 然后，变化每艘船舶的松弛量 Nf 次，每次将变化后的松弛量输入模型（） （）求解，获得调度方案。 这里，通过变化 wi的方式改 变松弛量，即 wi wi（ ）。 按照以上方法产生 Nf 个泊位分配方案，计算每个方案的鲁棒性指标值 RMi（i ，）。 （）蒙特卡罗仿真 对于每一个由步骤（）获得的泊位分配方案，按照正态分布产生每艘船舶作业的时间 pi，其中， 珋 pi ei yi，变异系数 CV 。 计算每艘船舶作业实际开始与结束时间，以及总延误时间。 重复此步骤 Nr 次。 表1 RMi与 PMi之间相关性（R 2） PM l PM X RM ? RM ? RM ? RM ? RM ? RM ? RM ? RM ? RM ? RM ? （）相关性计算 计算上述步骤产生的 Nr Nf 个情景的 PM，PM以及 RMi（i ，）与 PM，PM的相关性，选择相关性大的 RMi作为泊位计 划鲁棒性度量指标。 3 3 评价结果 选择天津某集装箱码头 天船舶到港数据（共有 艘到港船 舶）进行分析，此码头岸线长度 米，共配置装卸桥 台，装卸桥 平均效率为 次 小时。 假设 Nf，Nr 分别为 次、 次，步长 为 ，frac 为 。 计算得到 RMi与PMi之间的决定系数（R ）如表 所示。 结果表明，RM 具有最大的决定系数 R ，另外，RM ，RM，RM 也与 PMi之间具有较高的相关性。 泊位计划的鲁棒优化算法 4 1 算法设计 选择与 PMi相关性最大的指标 RM泊位计划鲁棒性的度量指标，通过最大化 RM获得鲁棒调度方 案，其优化过程通过两阶段算法实现： （）第一阶段 不考虑泊位计划的鲁棒性，以船舶总延误时间（C）最小为目标函数优化泊位计划，即通过求解式 （） （）获得泊位计划方案。 （）第二阶段 鲁棒性度量指标 RM最大化为目标函数，以第一阶段获得的船舶总延误时间 C以及式（） （） 为约束条件，获得鲁棒调度方案。 同等条件下，作业资源（如装卸桥数量）的增加会使 RM增加，从而提高调度方案的鲁棒性。 为了提 高调度方案的鲁棒性，在第二阶段求解中，考虑变化装卸桥数量，即 Q （ ）Q。 另一方面，装卸桥的 增加会增加作业成本，需要在调度方案的鲁棒性与作业成本之间做出平衡。 为此，通过变化装卸桥数量， 分析装卸桥配置数量与泊位计划鲁棒性 RM，以及泊位计划实施效果 PM的关系。 以第一阶段获得的 C为约束，通过变化装卸桥数量分析，可以为实际调度人员平衡鲁棒性和作业成本间的关系提供依据。 在算法第一、二阶段，分别采用基于拉格朗日松弛的算法求解，式（） （）模型的拉格朗日松弛表 述为： （） N i （eidi） N i tT it（ qRiq r itqQ） N i x i（ N j z x ij） N i y i（ N j z y ij） （） 其中，约束条件为式（） （），it， x i， y i辰。 拉格朗日乘数 it， x i， y i和约束条件（） （）相 第 期 曾庆成，等： 集装箱码头泊位计划的鲁棒优化模型 关。 采用次梯度算法（ 等 ）求解变化后的模型。 首先将模型 变换为模型 ， （） it，xi，yiL （） L N i （eidi） N i tT it（ qRiq r itqQ） N i x i（ N j z x ij） N i y i（ N j z y ij）（） 约束条件同样为式（） （）。 采用次梯度法求解的过程即寻找最优的 倡 it， x倡 i， y倡 i的过程，对于 每一给定的 it， x i， y i，通过求解 获得评价值 L，作为决定 it， x i， y i搜索方向的依据，通过循环获得最 优的 倡 it， x倡 i， y倡 i，以及泊位计划方案。 4 2 算例分析 首先，利用 中的案例，分析装卸桥配置数量对泊位计划鲁棒性（RM）的影响。 假设初始状态（即 装卸桥数为 台）下，通过两阶段算法获得的调度方案的鲁棒性为 RM ，计算在增加装卸桥配置数量的情 况下，调度方案鲁棒性的变化。 结果如图 所示。 结果表明，随着装卸桥数量的增加，泊位计划鲁棒性随 之提高。 图 装卸桥数量与泊位计划鲁棒性关系 图 装卸桥数量与泊位计划方案效果关系 其次，分析装卸桥配置数量与泊位计划方案效果（采用指标 PM度量）的关系，通过两阶段算法，获得 不同装卸桥数量情况下的泊位计划方案，分别假设船舶作业时间的变异系数 CV 等于 、 、 ，计算 PM，得到图 所示的结果。 从图 可以看出，随着装卸桥数量的增加，泊位计划方案的 PM值随之增加，即船舶按照泊位计划完 成作业的比例增加。 这说明，装卸桥数量的增加，提高了泊位计划的鲁棒性。 另一方面，随着装卸桥数量 的继续增加，PM值改进的速度越来越慢。 在实际应用中，决策者需要在作业资源投入与泊位计划鲁棒性之间做出平衡。 这里，以下模型决定装 卸桥投入数量： cEC（ ） c N i qRitT q ritq（） iNqRi q ritq尘 Q（ ），橙t T（） 其中，c表示如果船舶没有在规定时间完成作业，其单位延误时间的惩罚成本，c表示装卸桥单位台 时的成本，EC（ ）表示在投入 Q（ ）台装卸桥情况下，考虑船舶作业时间的不确定性，船舶延误 时间的期望值。 由于装卸桥数量为整数值，因此这里 为离散变量，即 Q（ ）为整数的取值。 假设 c 元 艘，c为 元 小时。 在实际中，c结合集装箱码头与船公司签订的作业合同确 定。 利用图 中数据计算可得，CV 取值 时，最优装卸桥配置数量分为 台，CV 取值 与 时，装 卸桥配置数量为 台。 结论 为了降低不确定性因素