遗传算法在码头泊位调度的研 究与应用.pdfVIP

科技前沿 遗传算法在码头泊位调度的研究与应用 官培垄，毕明彦。陈林，梅叶 (1，青 岛港(集团)科技有限公司，山东 青 岛 266011；2，青岛港国际货运物流有 限公司，山东 青岛 266500) 摘 要 ：为更好地优化码头泊位分配，提高泊位利用率，以实现码头泊位利用率最大化为 目标 ，借鉴背包问题的解决方 案 ，将船舶在港时间、作业顺序 、泊位安排 、机械配置、堆场安排等时空因素，结合遗传算法得 出泊位 资源安排的最优解。实 践证明，该算法能有效缓解人工制订泊位计划所造成的考虑不周全、计划不合理等现 象，有效避免 了泊位冲突、极大提高了 码头泊位利用率，提升了码头作业效益和服务水平。 关键词 ：泊位调度 ；背包问题 ；遗传算法 中图分类号：U691 文献标识码：A 文章编号：1673—1069(2016)25—179—2 0 引言 物品的重量 (weight)及其价值 (或收益 profit)分别为 W；0和 现代港 口是 国际物流供应链 的主要环节 ，能够提供快 pl0，背包 的容量 (contain)假设设为 c0，如何选择哪些物品 速 、可靠、灵活的综合物流经营服务是现代港 口的重要标志。 装入背包 ，可以使得在背包的容量约束限制之内所装物品的 泊位是决定港 口码头的一个关键因素，相对于港口其他设施 价值最大? 的投资来说 ，建造一个新的泊位的费用是非常昂贵的，所以， 该问题的模型可以表示为下述0／1整数规划模型 ： 如何在已有泊位数量的基础上 ，合理 的分配泊位已经成为制 —_l 目标函数 ：max gxl，X2…，x)= Cixi 约当前港 口发展的重要 因素。 作为码头重要的作业资源 ，泊位 、泊位计划是码头作业 的基础 ，合理的泊位计划是提高作业效率 、缩短船舶在港时 间的关键 因素。现在全球吞吐量排名前十的港 口，其 24小时 内数量达到几十艘次，因此如何合理安排船舶靠泊顺序和位 置 ，决定了码头岸线资源及堆场、设备、人力资源的合理应用 式 中x为 0—1决策变量 ，x。=1时表示将物品i装入背包 ㈣ v1 ( 程度 ，提高泊位计划的合理性对提升整个码头的通过能力和 中，x。：0时则表示不将其装入背包 中。 服务水平 ，有着至关重要的意义…。 3．2 遗传算法概述 1 当前泊位计划 中存在的问题 遗传算法(GeneticAlgorithms，GA)是在 1975年首次由 美国密西根大学的D。J。Holland教授和他 的同事们借鉴生 当前泊位计划编排的依据主要是根据船公司对码头的 重要程度 ，也就是所谓的 “重点客户重点服务”策略 ；再有就 物界达尔文的 自然选择法则和孟德尔的遗传进化机制基础 是采用所谓的 “先进先出”原则 ，这样会导致 出现物化消耗过 之上提出的。经过 40多年的研究、应用 ，遗传算法已被广泛 大 ，服务效率低下 ，客户满意度不高等问题；除此之外 ，码头 地应用于函数优化 、机器人系统 、模式识别、图像处理 、工业 泊位计划安排的好与坏 ，则主要体现在计划员本身对于码头 优化控制等多个领域。 业务的理解程度 、作业经验是否丰富等方面，而这些则可能 g 背包问题的遗传算法求解 导致作业线路安全隐患或者资源岸线泊位浪费等情况出现。 遗传算法具有 “生成+检测”的特点。其基本流程描述如 总之缺乏必要的理论支持和系统分析 ，从而导致泊位计划的 下 ： 随机性较大，这是 目前泊位计划制定过程 中存在的一个 比较 (1)基 因编码 ： 普遍的问题 。