当前位置:首页 >> 工学 >>

基于蚁群算法的集装箱码头集卡调度研究


基于蚁群算法的集装箱码头集卡调度研究





随着人口的增多,土地资源越来越昂贵,管理者不可能无限制的扩大港口占地面积,在 现有的港口规模下,如何挖掘潜力,改进管理水平,提高港口吞吐能力,是港口管理者面临 的共同问题。国际贸易量的萎缩,航运业的不景气,也迫使港口不断降低成本,以求在有限 的业务量中创造最大的利润空间, 在竞争中获得一席之地。 我国的港口管理水平与发达国家 的现代化港口有较大差距,相同规模的港口,其吞吐量能力远逊于国外,这值得港口管理者 和学者们深思。 单纯依靠增加设备投入虽然能提高集装箱的装卸速度, 但显然不是最经济的 方法,提高集装箱的装卸效率更为重要,因此必须制定合理的集装箱码头装卸工艺流程,包 括堆场规划、装卸机械调配等来提高效率。 由于集装箱码头水平运输系统承担着集装箱在码头内的装卸和运输, 并且集卡调度是一 个非常复杂的工程,而且随着码头集装箱量的增加、集卡数量的增多、集装箱码头的扩建以 及集卡调度规则的不断更新, 必然会导致集卡调度工作的更加复杂化, 因此怎样最大限度的 提高港口集卡运作的效率就成为提高集装箱码头生产率的迫切需要。 本文在充分分析研究背景的前提下, 基于装卸计划已事先拟定这一主要假设, 和集卡不 固定服务于某一岸吊的基本策略, 建立了面向作业面的集卡调度优化模型。 并利用蚁群算法 进行求解,在获得每辆集卡所需执行的任务序列的同时,确定了最合理的集卡配置数量。

关键词: 关键词:集装箱码头;集卡调度;蚁群算法

Abstract
Due to the increasing population and the land resource becoming more and more expensive, it is impossible to expand the port area without limitation. So it becomes a common problem for all port managers that how to tap potential improve management and increase throughout capacity under the existing port size. The port managers are forcing to create more profit in limited business by reducing cost, because of the shrinkage of the international trade and the downturn in the shipping industry. There is a big gap between China’s port management level and that of modern ports in developed countries. For ports of almost same size, our throughout capacity is far less than abroad, which worth being thought by the managers and scholars. Obviously it is not the best way that solely relies on the increase on the equipment investments despite that it can faster the handling speed. It is more vital to increase the handling efficiency of the containers. In order to achieve that, a reasonable container terminal handling process including the yard planning and the machine deployment must be established. The horizontal transport system of container terminal is responsible for the loading, uploading and transport of the containers inside the port, which means the container lorry dispatch is a quite complex mission. What’s more, the increasing amount of containers and lorries, the expanding construction of the terminals as well as the frequently updating of the dispatch rules are making the dispatch job even more complicated. Thus, how to improve the operation efficiency of the container lorry to the maximum extent has become the urgent need to increase the terminal’s productivity. On the basis of fully analyzing the research background, a optimization model of lorry dispatch has been created in this paper. The model was built based on the main assumption that loading scheme has been drawn up in advance. And the there is a basic strategy that lorry is binding to a certain crane. Here I use Ant Colony Algorithm to solve the model, which can find both the optimized task sequence and the appropriate quantity of lorry in need.
Key Words: Container Terminal; Container Lorry Dispatch Optimization; Ant Colony Algorithm

目录
第 1 章 绪论.................................................................. 1 1.1 研究背景 ............................................................. 1 1.2 研究目的和意义....................................................... 2 1.3 本文研究的主要内容及方法 ............................................. 3 第 2 章 集装箱码头生产作业系统概述 ............................................ 3 2.1 集装箱码头装卸设备 ................................................... 3 2.2 集装箱码头基本作业流程 ............................................... 6 3.1 集卡调度策略比较 ..................................................... 7 3.2 面向作业面的集卡调度优化模型 ......................................... 9 3.2.1 问题描述....................................................... 9 3.2.3 模型建立...................................................... 10 第 4 章 蚁群算法求解集卡调度数学模型 ......................................... 12 4.1 蚁群算法简介........................................................ 12 4.2 蚁群算法基本原理 .................................................... 13 4.3 集卡调度模型算法设计 ................................................ 16 4.3.1 构造 TSP 图 .................................................... 17 4.3.2 集卡调度问题与 TSP 问题的区别 .................................. 18 4.3.3 算法设计...................................................... 19 4.3.4 算法步骤...................................................... 23 4.4 算例分析............................................................ 24 4.4.1 案例设计...................................................... 24 4.4.2 模型求解...................................................... 25 第 5 章 结论................................................................. 27 参考文献.................................................................... 28

I

中文译文

第 1 章 绪论
1.1 研究背景
集装箱运输以其高效、便捷、安全等特点,成为现代交通运输工具的重要组成部分,越 来越受到人们的瞩目。相对于传统的件杂货运输,集装箱的优越性体现在以下几点 : (1)提高港口装卸效率,缩短船舶在港时间,加速船舶、货物周转,有巨大的社会宏观 效益; (2)便于联运换装,实现货物“门—门”运输; (3)包装成本低,货物在途时间短,节省货物包装费用; (4)安全可靠,保证货运质量。 国际集装箱运输自 20 世纪 50 年代中期兴起,随着集装箱运输的飞速发展,世界各国港 口相继建造了大量的集装箱多用途和专用码头。 集装箱码头在整个集装箱运输过程中对加速 车船周转,提高货运速度,降低整体运输成本等方面,起着十分重要的作用。在我国,随着 对外贸易的频繁往来,集装箱码头以前所未有的速度和规模飞速发展。自 1995 年以来,港 口集装箱吞吐量以年均 25%以上的速度增长, 2007 年全国海港集装箱吞吐量突破 1 亿 TEU。 面对覆盖全球的经济危机,08 年集装箱吞吐量仍达 1.26 亿 TEU。而在最新的世界集装箱港 口吞吐量排名中,中国占据六席。
[1]

表 1.1 2008 全球集装箱码头吞吐量排名

排名 1 2 3 4 5 6 7 8 9

港口 新加坡(Singapore) 上海(Shanghai China) 香港(HongKong) 深圳(Shenzhen China) 釜山(Busan South Korea) 迪拜(Dubai United Arab Emirates) 广州(Guangzhou China) 舟山(Zhoushan Ningbo China) 鹿特丹(Rotterdam Netherlands)

吞吐量( TEU) 吞吐量(万 TEU) 2992 2801 2430 2142 1342 1200 1100 1084 1083

1

中文译文

10

青岛(Qingdao Shandong China)

1002

与此同时,在现代物流与供应链管理发展的背景下,集装箱码头作业资源调度问题己成 为提升新一轮竞争码头核心竞争能力的关键问题。 加之世界经济危机对航运业造成了巨大的 冲击, 如何在有限的业务中创造出更多的利润, 正成为各大港口在激烈竞争中保全自己所要 思考的重要问题。而在我国,虽然一些集装箱码头,尤其是沿海大型集装箱码头已具备了先 进的生产设施和现场实时控制系统, 但总体来说, 与国外先进的集装箱码头相比还存在一定 差距,主要表现在对码头物流系统的资源配置和路径优化等方面仍以经验管理为主。 码头管理中包括堆场作业,岸边装卸,集卡运输等作业环节。码头作业效率的最重要的 指标是停靠船舶的平均装卸时间。 高昂的租船费用和机会成本使船运公司把平均装卸时间作 为选择停靠码头的主要因素。 而与这一指标密切相关的是岸边桥式起重机单位时间的集装箱 装卸数量。 一般码头会给岸边桥式起重机分配一定数量的集卡, 集卡将装或卸于船舶的集装 箱从堆场运到码头或从码头运到堆场。 如果岸边桥式起重机的集卡数量过少, 会造成岸边出 现等待空闲现象减少作业效率;数量过多,不但增加集卡成本,还导致交通阻塞,也会出现 岸边桥式起重机作业延误, 降低效率的现象。 由此码头需要根据岸边和场区作业的需求来合 理安排集卡数量。 目前国内大多数码头普遍采用的是将 6 或 7 辆集卡固定配备给一个岸边桥 式起重机, 在整个工作流程中这些集卡仅仅为这一个岸边桥式起重机服务。 这种模式是个静 态的分配模式, 集卡将集装箱运送到目的地后又重新返回到岸边桥式起重机边。 但在这种分 配模式下对于集卡的调度非常不灵活, 当船舶停靠的泊位离它装卸的集装箱所在场区之间的 距离非常远时,为了提高岸边桥式起重机的作业效率,就要分配更多的集卡,这样会出现严 重地交通堵塞和成本问题。 同时集卡在来往途中, 会出现一段无效率路程, 即集卡空载运行, 从而出现浪费资源,提高成本的问题。 综合以上分析可以看出在集装箱码头中,岸边桥式起重机和场区之间集卡数量的确定和 调度安排,不仅影响岸边桥式起重机的装卸效率,而且更关系到集装箱码头的成本。一些世 界先进集装箱码头的经验表明,根据岸边和场区作业的需求合理安排集卡数量和运输调度, 对减少交通拥挤,降低运输成本提高作业效率至关重要。

1.2 研究目的和意义
根据码头资源的类型不同,码头运作效率的研究主要包括以下几个方面:锚地和泊位资 源的优化配置研究、 装卸设备的优化配置研究、 堆场资源的优化配置研究和物流路径优化研 究等。

2

中文译文

集装箱码头实现的吞吐量都需要通过水平运输系统,即集卡来实现转运运输,集卡数量 众多,任务量巨大,因而每辆集卡每次运输的微小成本降低,都可以形成可观的利润空间。 且传统的面向作业线静态分配策略仍有很大的优化空间。 此外, 现代化的计算机管理系统和 方便快捷的通信系统为实现集卡的精确优化配置提供了强有力的硬件支撑, 使得动态分配具 备了良好的可操作性。 通过对集卡调度进行优化, 一方面可以减少运输过程中的空载里程, 即无效的运行里程, 从而有效降低油耗成本和车辆磨损成本; 另一方面可以减少所需占用的集卡数量, 从而降低 购置车辆的资金投入。 这对于处于激烈竞争中尤其是自身吞吐量接近饱和的集装箱码头具有 重要的经济意义。

1.3 本文研究的主要内容及方法
在集装箱码头集卡调度研究领域已经基本形成一种共识,即面向“作业面”的动态集卡 分配方式与面向 “作业线”的静态集卡分配方式相比, 可以在使用更少集卡的情况下完成相 同任务量, 同时可以大大减少集卡空载的路程从而有效降低运行成本。 然而目前多采用仿真 模型来确定集卡数量, 实现对不同集卡调度策略效果的对比, 采用数学模型进行研究的的相 对较少。 本文建立了面向“作业面”的集卡调度优化模型。集卡调度问题属于典型的 NP-hard 问 题, 这一类问题通常需要使用启发式搜索算法进行求解, 文中借鉴了蚁群算法在指派问题和 车辆路径问题(VRP)研究中的应用 ,对集卡调度模型进行求解。在一次求解中同时解决集 卡数量问题和集卡任务分配问题。 有别于以往蚁群算法应用于集卡调度问题时将岸区、 堆场 等空间上的节点作为研究对象 ,本文以装卸任务为节点构造 TSP 图。基于装卸任务计划已 知这一假设,针对集卡必须顺序执行装卸任务的约束条件,设计了“正序”“倒序”两阶段 、 的蚂蚁遍历策略。 对解决 VRP 问题时用到的近似解可行化算法进行改进, 设计了可用于集卡 调度问题的近似解可行化算法。
[3] [2]

第 2 章 集装箱码头生产作业系统概述
2.1 集装箱码头装卸设备
集装箱码头是集装箱运输的枢纽,它外接海洋的国际远洋运输航线,内连国内的铁路、 公路、水路等运输线路。因此,集装箱码头是各种运输方式衔接的换装点和集散地。集装箱 码头在整个集装箱运输过程中具有重要的地位 。
[4]

3

中文译文

图 2.1 集装箱码头枢纽

集装箱装卸工艺是指将集装箱从船舶上卸到码头上,然后水平搬运至堆场,在堆场进行 堆放后,再输运出去,或将集装箱从内陆集运至码头堆场堆放,然后水平搬运至码头前沿再 装到船上的全过程中的机械组合和流程。 因此, 集装箱码头装卸机械是集装箱码头的重要组 成部分。集装箱码头主要有三类装卸机械: 1.岸边装卸机械 岸边装卸机械是直接用于岸边集装箱船舶装卸的机械。目前主要使用的是岸边桥式起重 机,以下简称岸桥。岸桥可以分为单吊岸桥和双吊岸桥两种类型。单吊岸桥由人工操作,一 次只能吊一个 20TEU 的集装箱。双吊岸桥能同时吊起两个 20TEU 的集装箱。目前,集装箱码 头多使用单吊岸桥。 双吊岸桥仅在少数的码头使用。 岸桥的最大效率取决于它起重机的类型, 作业效率为每小时完成 50 一 60 个吊次的装卸作业。 然而在实际中, 岸桥的作业效率还取决 于操作司机的技术熟练程度以及外部环境,正常情况下,岸桥的作业效率为每小时完成 22 一 35 个吊次的装卸作业。 2.堆场装卸机械 堆场装卸机械是用于堆场车辆装卸及堆码集装箱的机械,包括堆场龙门起重机等。堆场 龙门起重机,以下简称场桥,是集装箱堆场车辆装卸及堆码箱作业的主要机型。因其形状像 “门” ,故俗称为龙门起重机、场桥。龙门吊有轮胎式和轨道式两种。轨道式龙门吊采用钢 质车轮(像列车轮),像岸桥一样,轨道式龙门起重机只能沿固定轨道移动,因而其在码头排 场的作业范围是固定的。轮胎式龙门起重机采用的是橡胶轮胎,可以改变运动路线,即可以

4

中文译文

方便地从一个作业位置移到另一个作业位置。 它适合于码头作业量不是很大的码头作业。 龙 门起重机的跨距(即“门”的宽度)为 6 行集装箱加一条集卡道的宽度,可堆码集装箱的高度 为 4 一 8 层。

2.1 设备工艺表

装卸阶段 码头前沿

操作内容 装、卸船 码头—堆场

采用设备 岸边集装箱起重机(岸桥)

水平运输

场—拆装箱库 堆场—铁路装卸线 堆场冲洗、修箱场 装、卸车

集装箱牵挂车(集卡)

堆场作业

拆、码垛 集装箱装卸车

轮胎式集装箱龙门吊起重机 正面吊运车 叉车 叉车(箱内作业叉车) 集装箱叉车车

拆装箱库

拆装箱 拼箱货装卸车 其他

3.水平运输机械 水平运输机械是主要用于运输和搬运集装箱的机械,有牵引车、挂车和跨运车。跨运车 是可以承担码头前沿与堆场之间的集装箱水平运输, 以及堆场的堆码和进出场集装箱集卡装 卸作业的主要设备。 它以门形车架跨在集装箱上由装有集装箱吊具的液压升降系统吊起集装 箱,进行搬运和堆码。集装箱跨运车堆码和通过集装箱的层数,与整个集装箱码头及堆场的 堆存面积、工艺条件有关。目前通常采用堆码 2 一 3 层集装箱。 集装箱牵挂车,以下简称集卡,是非自动化集装箱码头水平运输集装箱的主要设备,它 由牵引车和挂车两部分组成。码头堆场上,根据其工艺要求通常采用单头半挂形式,近几年 大型集装箱码头为提高作业效率,降低人工成本,已开始采用多挂方式,一台牵引车拖挂 4 一 5 台挂车,也就是俗称的多挂集卡。单挂集卡是是本论文的主要研究对象。 自动导引车,通常称 AGV,是自动化集装箱码头水平运输的主要设备,是一种无人驾驶 搬运车,它可以按照监控系统下达的指令,根据预先设计的程序,依照车载传感器确定的位 置信息,沿着指定的行驶路线和停靠位置自动行驶。由于这种自动化设备的投资成本较大, 而未能受到我国码头投资者的青睐。
5

中文译文

2.2 集装箱码头基本作业流程
集装箱港口的作业流程从集装箱流的角度来看,可以分为进口流程和出口流程。 一、集装箱港口进口业务流程 1、进口卸船计划:由调度室根据船舶近期计划安排船舶靠泊,并依照卸船堆场计划等 安排卸船机械; 2、进口卸船:根据进口卸船计划来实时调度组织卸船。把要在本码头进行卸船的集装 箱从船上卸下后,根据场地位置进行场地位置确认落箱。 3、堆场作业:包括安排驳箱、移箱、提箱作业。驳箱主要是安排集装箱的驳运疏港, 了解箱子在各堆场的分布情况以便对集装箱进行跟踪。移箱作业主要是为了提高堆场堆存 率,掌握集装箱运转动态,更好地安排下一次装卸作业,提高装卸作业效率。 4、出场作业:货主根据相应的单证到集装箱客户服务区办理提箱手续后,由外集卡到 集装箱前方堆场进行提箱,然后经过道口出场。由于当前集装箱堆场的空间资源紧张,对那 些堆放超过一定期限的集装箱要进行疏港作业。 二、集装箱港口出口业务流程 在集装箱出口货运业务中,码头主要负责以下作业,具体流程为: 1、集港:集装箱港口根据船舶的船期确定集港时间,货主在办理好所有的出口业务单 证,把集装箱经过集装箱码头的道口拉入集装箱堆场落箱,等待装船。 2、装船前准备:集装箱码头根据船期和在场箱的情况,进行装船前准备,主要有箱子 的归并和移箱处理,主要是为了能够在集装箱装船作业时能够快速装船。 3、船舶配载:箱管根据船期及船公司或船代的出口预配船图,对出口在场箱进行船舶 配载,同时得到船方大副的同意签字后,准备装船。 4、出口装船:含装船前的业务上的准备工作与实际装船作业。装船前的预备工作主要 是进行码头船舶预配载。实际装卸船作业由调度室指挥,机械队操作,集装箱由集卡拖运至 码头由集装箱装卸桥装船,并由内外理进行装船确认。

6

中文译文

第 3 章 集卡调度数学模型
3.1 集卡调度策略比较
在集装箱码头装卸作业过程中,集卡的调度策略有两种:面向作业线和面向作业面。在 采用作业线调度策略时,每辆集卡固定地静态服务于某一岸桥,集卡的行车路线相对固定, 循环过程中,半圈为重载,半圈为空载,空载造成集卡能耗和时间浪费,极大地影响了集卡 的效率发挥。而在采用作业面调度策略时,每辆集卡并非静态地拘泥服务于某台岸桥,而是 灵活地动态的服务于有需要的岸桥。 面向作业面的调度策略又分为面向小作业面和面向大作 业面: 面向小作业面是指将服务于同一艘船的集卡形成一个队列, 队列中的集卡仅服务于该 船舶的岸桥; 面向大作业面是指将码头中所有工作的集卡形成一个队列, 服务于所有船舶作 业的岸桥。 本文是针对面向小作业面的调度策略所做的研究。单船作业开始时,岸桥分配计划员会 将单船作业时所需岸桥的数目确定, 每台岸桥所对应装卸集装箱的数目以及顺序均由配载计 划员确定。 堆场计划员负责集装箱所在箱区以及在箱区中的排列。 3.1 为单船作业下集卡 图 静态服务于岸桥的拖运行驶路线图,集卡 1 固定服务于岸桥 1,集卡 2 固定服务于岸桥 2, 这种调度策略虽然简单易操作, 但是会造成码头成本增加和效率低下的问题。 与这种低效率 的集卡静态调度策略相比, 另外一种策略要优越得多, 如图 3.2, 当岸桥 2 在卸载集装箱时, 集卡 1 将这个集装箱运到堆场中它所要堆存的箱区后, 集卡 1 不再回到离它现在所在地点很 远的岸桥 2,而是继续前进到离它现在所在地点很近的将要出口的集装箱堆存点,将该集装 箱运到另一个正在进行装箱作业的岸桥 1。在这种策略下,单船作业的集卡能够动态灵活地 服务于作业岸桥,极大地减少集卡的空载路程,提高集卡的利用率,而且集卡的行走时间会 随着任务分配方案的不同而有所不同。

7

中文译文

船舶

岸桥 1

集卡 1

集卡 1

岸桥 2

箱区

箱区

单船作业下集卡静态服务于岸桥 图 3.1 单船作业下集卡静态服务于岸桥

船舶

岸桥 1

集卡 1

集卡 1

岸桥 2

箱区

箱区

单船作业下集卡动 图 3.2 单船作业下集卡动态服务于岸桥

由于运输过程中集卡行驶路线的复杂性使得这种动态调度的模式没有在集装箱码头作 业中流行起来。我国国内集装箱码头普遍采用“作业线”生产方式进行船舶装卸作业,作业 机械的配置大约为一台岸桥对应两台场桥,6 一 7 辆集卡固定为一台岸桥服务,无论岸桥如 何空闲, 这些集卡不会脱离该岸桥, 也不论该岸桥多么忙碌, 即使出现岸桥等待集卡的现象,

8

中文译文

也不会有新的集卡加入。 随着国内集装箱码头之间的竞争激烈程度加剧, 码头管理者开始逐 渐意识到“作业面”生产方式的优越性,该生产方式能够根据现场作业任务实时的分配集卡 所需服务的岸桥,提高集卡和岸桥的利用率,降低码头作业成本。

3.2 面向作业面的集卡调度优化模型
3.2.1 问题描述 所谓集卡调度问题,是指在岸桥的计划任务确定后给出与岸桥配套的集卡的作业计划, 使得岸桥按时无误地工作,并尽量降低无效的运行里程,从而提高港口的作业效率。对于一 项装卸任务而言,其有效运行里程是固定的,即集卡装载卸船(装船)货物从岸区(堆场) 到指定堆场(岸区)的距离。而无效运行里程,即集卡从其先行任务的结束地点到后继任务 的开始地点之间的距离,是可以优化的。通过优化集卡的任务分配,使得全部集卡的空载里 程之和最小,是模型的主要目标。模型的建立基于以下假设: (1)如前面叙述提到的,单挂集卡是本论文的主要研究对象。 (2)各岸桥的任务必须严格按照事先计划设定的顺序执行。在集装箱港口装卸作业过程 中,为保证船舶的稳定性和安全性,港口管理者都会事先制定相应的装卸顺序单,并得到船 方的确认,并且该计划一旦制定后港方不能随意修改。因此该假设是符合实际情况的。 (3)在装卸过程中,岸桥比集卡具有更高的优先考虑级别,也就是在集卡分配过程中, 可以出现集卡等待岸桥,但不允许出现岸桥等待集卡。在现实情况下,岸桥的购置成本要远 远高于集卡的购置成本, 因此在港口作业过程中应该充分利用岸桥, 通过调节集卡来适应岸 桥的需求,而不能本末倒置。 (4)在集卡的工作中,集卡的某些作业需要堆场机械的配合。模型假定场桥总是能够及 时服务于集卡,保证集卡及时服务于岸桥。如果堆场计划员将堆场计划做的较好时,就不会 出现集卡等待场桥的情况, 同时可以通过调整场桥的配置来实现, 所以这种假设存在着一定 的合理性 。 (5)不考虑堆场中的交通拥挤、堵塞情况。 3.2.2 符号定义 在对集装箱码头的集卡调度优化时, 除了考虑集卡本身的作业因素外, 还必须考虑岸桥 的作业因素,例如岸桥何时需要集卡的服务,而此时是否有空闲的集卡,空闲的集卡离岸桥 的距离多远,与此同时,堆场中也有集装箱需要作业,这时有没有空闲的集卡可以作业,空 闲集卡是去服务岸桥还是去服务堆场的集装箱等等。 本文中为了方便模型的描述, 将集卡把一个集装箱从岸边(或堆场)运输到堆场(或岸边) 的过程定义为一个调度任务。 这个调度任务的起始点为岸边(或堆场), 终点为堆场(或岸边)。 船舶作业之前, 岸桥的装卸作业已经由配载计划做好, 所以每台岸桥的装卸量以及作业 的集装箱顺序都是已知的, 同时己知岸桥的平均装卸效率, 即岸桥处理一个集装箱的平均时
9
[5]

中文译文

间是多少。这样针对这台岸桥的每一个集装箱,我们都知道该集装箱的开始作业的时间、开 始作业的地点、完成作业的时间以及完成作业的终点(岸区或是堆场中)。 每两个调度任务之间的距离也是已知的。 为了打破集卡固定服务一个岸桥的模式, 将所 有岸桥作业的集装箱综合起来考虑, 并按照它们作业的开始时间排序。 运用这样的思想岸桥 的作业因素转变为时间因素,约束到集卡作业中,便于建立集卡的调度优化模型。 建立集卡的调度优化模型时首先定义如下符号: p:调度的集卡,假设计划周期内所需集卡的总数为 N,p=1,2,…,N; M:计划周期内所有调度任务的总和;

bi :调度任务 i 的开始时间, i∈M;
fi :集卡完成调度任务 i 所需要的时间, i∈M;

tij :集卡从调度任务 i 释放集卡到调度任务 j 开始占用集卡所需要的时间,即集卡的无
效作业时间, i, j ∈M。 本文引入如下决策变量:

xij ∈ {0,1} ,当 xij =1 时表示调度任务 i 和调度任务 j 由同一辆集卡相继完成;
y pi ∈ {0,1} ,当 y pi =1 时表示集卡 p 首先从调度任务 i 开始执行;

z ip ∈ {0,1} ,当 zip =1 时表示集卡 p 在完成调度任务后结束工作。
3.2.3 模型建立 基于以上所定义的符号以及决策变量,建立如下的集卡调度优化模型: o.b. (3.1) s.t. min

f = ∑∑ xij dij
i =1 j =1

M

M

∑y
i =1

M

pi

=1

p∈N

(3.2)

∑z
i =1

M

ip

=1

p∈N

(3.3)

∑ xij + ∑ y pj = 1
i =1 p =1

M

N

j∈M

(3.4)

10

中文译文
M N

∑x +∑z
i =1 ij p =1

ip

=1

j∈M

(3.5)

∑x
i =1

M

ij

(bi + f i + tij ) < b j

j∈M

(3.6)

xij ∈ {0,1}
(3.7)

i, j ∈M i ∈M, p∈N i ∈M, p∈N

y pi ∈ {0,1}
(3.8)

z ip ∈ {0,1}
(3.9) 其中,

(3.1)为模型的目标函数,追求所有集卡的无效作业里程最短;(3.2)~(3.9)为模型的 约束条件: (3.2)保证所有的集卡开始作业一次且仅一次; (3.3)保证所有的集卡结束作业一次且仅一次; (3.4)保证所有的调度任务开始一次且仅一次; (3.5)保证所有的调度任务结束一次且仅一次; (3.6)是两个调度任务能成为相继作业,在时间上所需满足的条件,该约束条件来源于 前述的岸桥作业因素。 (3.7)~(3.9)保证变量为 0-1 变量。 通过对集卡调度优化模型的求解,可以得到集卡调度的优化方案,从而使得所有集卡 的无效作业里程最短。

11

中文译文

第 4 章 蚁群算法求解集卡调度数学模型
通常,对集卡动态调度模型的求解是建立在指定集卡数量的前提下进行的,如《集装箱 码头调度问题研究》 在给定集卡数量的情况下进行优化, 而未考虑集卡数量的优化。 《集 而 装箱码头堆场拖车动态调度问题研究》 将这一问题分解为数量配置模型和动态调度模型分 别求解; 对动态调度模型采用遗传算法求解, 并利用数量配置模型得到的车辆数作为条件之 一。本文借鉴蚁群算法在 VRP 问题中的应用,求解集卡调度模型,在获得最优路径的同时兼 顾集卡数量最小这一目标。
[13] [15]

4.1 蚁群算法简介
蚁群优化(ACO,Ant Colony Optimization )算法是由意大利学者 Colomi A、Dorigo M 和 Maniezzv 于 1991 年提出来的 ,是一种新型的模拟进化算法。蚁群算法是通过对自然界 蚂蚁在觅食过程中的寻路方式进行模仿而得出的一种优化算法。 自然界中的蚂蚁在觅食的过 程中会在自身爬行过的路径上留下“信息素”来记录路径,同时在选择路径的时候也是根据 之前蚂蚁在该路径留下的“信息素”浓度来判断,浓度越高,则选择的可能性越大。从蚁巢 到食物的所有路径中,路径越短,则相同时间内通过的蚂蚁也就更多,这样在该路径上所留 下的信息素浓度也就更高, 蚂蚁选择这条路径的可能性就越大, 这就形成了一种信息的正向 反馈机制,如图所示:
[6]

12

中文译文

图 4.1 蚁群算法

蚁群算法是基于蚂蚁觅食的过程建立的。 在图 4.1(a)中, 一群蚂蚁从一个未经历过的分 岔口开始出发,最初所有蚂蚁随机选择路径行进。假设两条路径各被一半的蚂蚁选中。每只 蚂蚁在行进过程中会在路径上留下外激素以提示后到的蚂蚁如何选择路径, 途中的虚线表示 蚂蚁留下的外激素数量。如图 4.1(b),由于路径一比路径二短,所以同一时间内,走过路 径一的蚂蚁比走过路径二的蚂蚁多, 因此路径一上留下的外激素也就多。 由于外激素数量对 蚂蚁选择路径的影响, 经过很短的时间, 外激素数量的差异就大的足以影响新来的蚂蚁的决 策。如图 4.1(c),由于这样的正反馈,选择路径一的蚂蚁越来越多。最终所有的蚂蚁都会 选择路径一。人工蚁群算法依此原理,在一组节点中寻找出一条代价最小的路径。每只人工 蚂蚁根据状态转换规则反复地选择为访问过的城市,通过这种方式来完成一次完整的旅程。 一旦所有的蚂蚁都完成了旅程, 系统就会使用一种全局的外激素更新规则, 根据路径被选择 的情况更新所其上的外激素数量。算法不断迭代直至达到终止条件搜索到最优解。

4.2 蚁群算法基本原理
由于蚁群算法的思想是模仿蚂蚁寻找最短路的机制,因此该算法最早是应用在了旅行商 (TSP)问题上,而 TSP 问题又具有广泛的代表意义和应用前景,许多现实问题,均可抽象为 TSP 问题进行求解 。接下来就以蚁群算法如何解决 TSP 问题介绍算法的基本原理。在解决
[7]

13

中文译文

TSP 问题时所设置的人工蚂蚁具有一些特点: (1)选择路径时,偏向于选择信息素浓度高的路径; (2)一般的,某条路径越短,则该路径上信息素增加得就越快; (3)蚂蚁是通过遗留在路径上的信息素来相互影响的。 以上三个特点是人工蚂蚁模仿自然界中真实蚂蚁的性质而得来的,在解决实际问题中, 人工蚂蚁往往根据问题设置一些特有的性质。解决 TSP 问题的人工蚂蚁还具有以下特性: (4)蚂蚁能识别要遍历的所有节点之间的距离; (5)所有的蚂蚁都能记住先前所走过的节点(这种记忆在每次新的循环开始都清空)。 设 bi ( t ) 表示 t 时刻位于元素 i 的蚂蚁数目, τ ij (t ) 表示 t 时刻路径(ij)上的信息量,n 表示 TSP 规模,m 为蚁群中蚂蚁的总书目,则 m =

∑ b (t ) 。初始时刻,各条路径上的信息
i =1 i

n

量相等,并设 τ ij (0) = const 。蚂蚁 k(k=1,2,……,m)来记录蚂蚁 k 当前所走过的城市,集合 随着 tabuk 进化过程动态调整。在搜索过程中,蚂蚁根据各条路径上的信息量及路径的启发 信息来计算状态转移概率:

τ (t ) α i η (t ) β ij ij , 若j ∈ allowed k α β k pij (t ) = ∑ [τ is (t )] i[ηis (t )] sallowed k 0, others
(4.1) 上式中, allowed k = {C tabuk } ,等式左边 pij (t ) 表示 t 时刻,蚂蚁 k 由位置 i 转移
k

到位置 j 的概率,ηij (t ) 为启发函数,在 TSP 问题中,其表达式如下:

ηij (t ) =

1 dij

(4.2)

d 对于蚂蚁 k 而言, ij 越小, ηij (t ) 越大,pij (t ) d 则 式中, ij 表示相邻连个城市之间的距离。
k

也就越大。显然,该启发函数表示蚂蚁从元素(城市)i 转移到(城市)j 的期望程度。

α 为信息启发式因子,表示轨迹的相对重要性,反映了蚂蚁在运动过程中所积累的信息
在蚂蚁运动是所起的作用,其值越大,则该蚂蚁越倾向于选择其他蚂蚁经过的路径,蚂蚁之
14

中文译文

间的协作越强; β 为期望启发式因子,表示能见度的相对重要性,反映了蚂蚁在运动过程 中启发信息在蚂蚁选择路径中的受重视程度, 其值越大, 则该状态转移概率越接近贪心法则。 为了避免残留信息素过多引起残留信息淹没启发信息,在每只蚂蚁走完一步或者完成对 虽有 n 个城市的遍历(也即一个循环结束)后, 要对残留信息进行更新处理。 这种更新策略模 仿了人脑记忆的特点, 在新信息不断存入大脑的同时, 存储在大脑中的旧信息随着时间的推 移逐渐淡化,甚至忘记。由此 t + n 时刻在路径(i,j)上的信息量可按如下规则进行更新:

τ ij (t + n) = (1 ρ )iτ ij (t ) +△τ ij (t )
(4.3)

△τ ij (t ) = ∑ △τ ij k (t )
k =1

m

(4.4) 式中, ρ表示信息素挥发系数, 1-ρ表示信息素残留因子, 则 为了防止信息的无限积累,

1) ρ的取值范围为: ρ [ 0, ; △τ ij (t ) 表示本次循环中路径(i,j)上的信息素增量,初始时
刻 △τ ij (0)=0 , △τ ij (t ) 表示第 k 只蚂蚁在本次循环中留在路径(i,j)上的信息量。
k

根据信息素更新策略的不同,Dorigo M 提出了三种不同的基本蚁群算法模型,分别称之 为 Ant-Cycle 模型、Ant-Quantity 模型及 Ant-Density 模型,其差别在于 △τ ij (t ) 求法的不
k

同。 在 Ant-Cycle 模型中

Q , 若第k只蚂蚁在本次循环经过(i,j) △τ ij (t )= L k 0, others
k

(4.5) 式中,Q 表示信息素强度,它在一定程度上影响算法的收敛速度;L k 表示第 k 只蚂蚁在 本次循环中所走路径的总长度。 在 Ant-Quantity 模型中

Q , 若第k只蚂蚁在t和t +1之间经过(i,j) △τ ij k (t )= d ij 0, 否则

15

中文译文

(4.6) 在 Ant-Density 模型中

Q, 若第k只蚂蚁在t和t +1之间经过(i,j) △τ ij k (t )= 否则 0,
(4.7) 区别:式(4.6)和式(4.7)中利用的是局部信息,即蚂蚁完成一部后更新路径是上的 信息素;而式(4.5)中利用的是整体信息,即蚂蚁的完成一个循环后更新所有路径上的信 息素,在求解 TSP 时性能更好,因此通常采用式 1 作为蚁群算法的基本模型。 具体算法步骤如下: (1)参数初始化。令时间 t=0 和循环次数 Nc=0,设置最大循环次数 Ncmax,将 m 蚂蚁置于 n 个元素(城市)上,令有向图上每条边(i,j)的初始化信息量 τ ij (0) = const ,其中 const 表示常数,且初始时刻 △τ ij (0)=0 。 (2)循环次数 Nc←Nc+1。 (3)蚂蚁的禁忌表索引号 k=1。 (4)蚂蚁数目 k←k+1。 (5) 蚂 蚁 个 体 根 据 状 态 转 移 概 率 公 式 计 算 的 概 率 选 择 元 素 ( 城 市 )j 并 前 进 , j ∈ {C-tabuk}。 (6)修改禁忌表指针,即选择好之后将蚂蚁移动到新的元素(城市),并把该元素(城市) 移动到该蚂蚁个体的禁忌表中。 (7)若存在蚂蚁没有完成遍历,即 k<m,则跳转至第(4)步,否则执行第(8)步。 (8)根据更新法则对每条路径上的信息量进行更新。 (9)若满足结束条件,即如果循环次数 Nc≥Ncmax,则循环结束并输出程序技术结果,否 则清空禁忌表并跳转到第(2)步。

4.3 集卡调度模型算法设计
本文所建立的集卡调度模型是面向“作业面”装卸工艺的,集卡在作业过程中是动态分 配的,并不固定的为某一个岸桥服务。同时本文假设在集卡作业期间,有装卸要求的船舶的 数量、位置及需求箱量是固定不变的,而堆场内的集装箱的位置也是固定不变的,各堆场之 间及堆场与岸区之间的距离已知。 各岸桥的任务必须严格按照事先计划设定的顺序执行。 在
16

中文译文

装卸过程中,岸桥比集卡具有更高的优先考虑级别,也就是在集卡分配过程中,可以出现集 卡等待岸桥,但不允许出现岸桥等待集卡。模型假定场桥总是能够及时服务于集卡,保证集 卡及时服务于岸桥。集卡全部为单挂集卡。不考虑堆场中的交通拥挤、堵塞情况。 4.3.1 构造 TSP 图 在实际运行中,集卡根据分配好的任务串在各场地和岸区之间穿行,包含满载和空载两 种不同的状态,根据任务的执行顺序和任务所涉及的场区,合理的安排任务串,可以减少集 卡空载里程从而达到优化节约降低成本的目的。 集卡调度问题可以看作特殊的 TSP 问题,即将每一个任务看作 TSP 问题的中城市元素, 两个任务元素(城市)之间的距离体现为从先行任务的结束地点到后继任务的开始地点之间 的距离,也就是集卡在任务元素之间交替的空载距离。但由于任务的装卸顺序已经固定,因 此在由任务点组成的 TSP 图中, 只包含由执行序列中排在前面的任务指向排在后面任务的有 向路径, 即集卡只能顺序选择任务而不能倒序选择; 同时, 由于任务转移需要消耗空载时间, 集卡必须在有足够时间由一个任务结束地点转移到另一个任务的开始地点的情况下才能选 择这两个任务相继完成,形成一个相继连接。即模型约束式(3.6) 。

图 4.2 TSP 图

由此得到集卡调度模型的 TSP 图 G=(C, L), 其中 C={C1,C2,……, n}是 n 个任务的集合, L={Lij|Ci,Cj∈C}是集合 C 中元素(任务)可行连接的集合,dij(i,j=1,2,……,n)是 Lij 的 距离,即

任务i结束点到任务j开始点距离 bi +fi +tij <bj d ij = Q bi +fi +tij ≥ bj
(4.8)

17

中文译文

式中 bi +si +tij <bj 表示两任务在时间上可以相继执行, 此时两任务的转移距离即为先行 任务 i 的结束地点(堆场或岸区)到后继 j 开始地点的距离(堆场或岸区);Q 为一个足够大的 常数,以避免在算法中蚂蚁个体选择不可相继执行的任务组合。 4.3.2 集卡调度问题与 TSP 问题的区别 尽管已经将集卡调度模型转化为 TSP 图,以使蚁群算法得以进行,集卡调度问题与 TSP 仍有许多不同之处。与经典 VRP 问题类似,集卡调度问题可以看作路径受限的 TSP 问题,即 受约束条件的限制,单独一个集卡(车辆)不能遍历全部节点。在集卡调度问题中,由于有 时间约束的存在,集卡从时间允许的任务中选择后继点,而在 VRP 问题中,车辆则受到了载 货量和最大行驶里程的限制,单独一辆车只能满足部分客户的需求。集卡调度问题与 TSP 问题在运用蚁群算法时的区别主要体现在以下三个方面 : (1)子路径构造的区别。 在 TSP 中, 每只蚂蚁均要经过所有的节点; 而在集卡调度问题中, 由于时间条件的限定, 每只蚂蚁无法遍历所有节点。因此,在求解集卡调度问题的每次迭代中,每只蚂蚁移动的次 数是不确定的, 只能将是否还存在可行后继节点(先行节点)作为路径完成的标志。 路径构造 分为正序和倒序两个阶段。正序阶段,蚂蚁从起始节点向时间在后的节点转移,直至无法找 到符合条件的后继节点。倒序阶段,蚂蚁从起始节点向时间在前的节点转移,直至无法找到 符合条件的先行节点,进入此阶段时的任务元素距离 dij 以 dji 代替(i>j)。 (2) allowed k 的区别。
[2]

allowed k 的确定是蚂蚁构造路径过程中以个十分关键的问题。在 TSP 问题中,蚂蚁转
移时只需考虑路径距离和信息量; 而在集卡调度问题中, 蚂蚁转移是不但需要考虑上述问题, 还需要考虑时间的上可串行性。通过在 d ij 中引入极大常数 Q 可以很好的解决这一问题,Q 使得此路径上的的能见度ηij (t ) 趋近于 0,从而使转移概率趋近于 0,算法运行中,蚂蚁会 自动放弃时间上不可串行的任务组合。 (3)可行解结构的区别。 在 TSP 问题中,每只蚂蚁所构造出来的路径均是一个可行解;而在集卡调度问题中,每 只蚂蚁所构造的路径仅是可行解的“零部件” ,个蚂蚁所构成的路径可能能够组合成一些可 行解,也可能一个可行解都得不到。因此,研究如何设计算法以尽量避免无可行解现象的出 现以及如何获取可行解是蚁群算法在解决集卡调度问题时的关键。
18

中文译文

4.3.3 算法设计 鉴于集卡调度问题与 VRP 问题的相似性,本文借鉴自适应蚁群算法在 VRP 问题中的应用 来求解集卡调度模型。其设计思路是:以求解 TSP 的蚁群算法为基础,充分考虑集卡问题的 具体要求,对算法选择机制、更新机制以及协调机制做进一步改进,引入自适应的转移策略 和信息素更新策略,以克服基本蚁群算法计算时间长、易出现停滞等缺陷。 1、转移规则
[8,9]

借鉴 Dorigo M 的 Ant-Q 算法思想,采用确定性选择和随机性选择相结合的选择策略, 并在搜索过程中动态调整状态转移概率。具体而言,Ant-Q System 使用了自适应伪随机比 率选择规则,即对位于节点 r 的蚂蚁 k 按照下式选择下一节点 s

arg max AQ ( r , u ) α i HE ( r , u ) β , 若q ≤ q 0 s = u∈allowedr 转移概率公式p k ( r,s ), others
(4.9)

{

}

AQ ( r , s ) α i HE ( r , s ) β , 若s ∈ J k (r ) α β pk ( r , s ) = ∑ AQ ( r , u ) i HE ( r , u ) u∈J k ( r ) 0, others
(4.10) 式中, q0 是区间[0,1]内的一个随机数; J k ( r ) 表示待选择的节点集合; HE ( r , u ) 表 示启发式信息,信息量 AQ 值按照如下规则进行更新

AQ ( r , s ) ← (1 δ )i AQ ( r , s ) + δ i △ AQ ( r , s ) + γ i max AQ ( s, u )
u∈allowed r

(

)

(4.11) 信息素增量 △ AQ ( r , s ) 的求法采用本次迭代最优(interation-best)法:

W Lk ib , 若(r,s)为蚂蚁kib 所经过的路径 △ AQ ( r , s ) = others 0,
(4.12) 表示只有与本次迭代最优解相对应的 AQ 值才可以得到强化。 根据以上的转移规则,在蚂蚁选择后继节点的过程中可能存在这样的情况发生,所选择 的两个相邻任务之间的序号跨度过大, 如在选择任务 1 后选择任务 100。 当这种情况发生时, 该集卡虽然没有增加空载历程, 却会长时间处于闲置等待状态, 这在实际生产中是不可接受
19

中文译文

的。算法中接受这样的解,会造成蚂蚁智能体的浪费。为避免这样的解路径出现,对任务转 移的跨度进行限制。

SP =

2 × ( S max V ) + Uload + Load Uload

(4.13) 式中 SP 为所求最大跨度,即允许集卡选择任务的最大差值,单位:个; S max 为所有堆 场及岸区间距离的最大值; 车辆行驶速度; V Load 为岸桥工作速度; Uload 为场桥工作速度。 2、信息素更新规则 蚂蚁吸引力 设经过节点 i 的蚂蚁数目为 R,经过有向弧段(i,j)的蚂蚁数目为 r,则称 r/R 为有向弧段(i,j)的蚂蚁吸引力。 在进行信息素局部更新时,若每次施放的信息量 Q 为常量,则有向弧段(i,j)的蚂蚁吸 引力越大,经过弧段(i,j)的蚂蚁数目就越多,从而局部更新的次数就越多。久而久之,会 导致弧段信息量差距过大,限制了算法搜索的全局性。因此,随着算法搜索状态的变化,Q 值应不断调整。 其调整原则是, 路径的蚂蚁吸引力越大, Q(t)越小。 则 不妨设 Q(t)=Q(1-r/R), 并且若 R=0,则 Q(t)=Q。 假设第 k 只蚂蚁在第 q 次迭代中的第 f 次转移是经过有向弧段(i,j),在此之前共有 Rk 只蚂蚁经过 i 点,其中有 rk 只蚂蚁选择了有向弧段(i,j)。算法的全局更新规则与求解 TSP 是类似,而局部更新规则设计如下
new old τ ij = (1 ρ )τ ij +△τ ij , i, j, 且i ≠ j

(4.14)

△τ ij = ∑ △τ ij k
k =1

m

(4.15)

△τ ij

k

rk Q 1 = Rk 0,

, 若蚂蚁k从i移动到j others

(4.16) 3、可行解问题的研究 在集卡调度问题中,每只蚂蚁所构造的路径只是可行解的一个组成部分,各蚂蚁所构造 的路径可能能够组合成一些可行解,也可能一个可行解也得不到。若经常得不到可行解,则
20

中文译文

会造成大量的计算时间浪费。这里可以采取以下策略。 (1)大蚂蚁策略: 增加算法的蚂蚁数目 M, 扩大组合范围, 从而增加可行解产生的可能性。 (2)蚂蚁初始分布均匀策略:在每次迭代前,将蚂蚁随机均匀分布于各个节点,从而增 加发现可行解的机会。 (3)近似解可行化策略:前两种策略的目的都是为了提高个蚂蚁所构造的子路径组合成 可行解的可能性,是一些针对无可行解的事前预防措施。然而,当问题规模较大时,会有大 量的蚂蚁所找到的路径是相同的, 使得实际上真正起作用的蚂蚁数目大大减少, 从而严重影 响产生可行解的可能性。针对这一问题,这里采用近似解可行化策略,即在找不到可行解的 情况下, 选择一些与可行解接近的非可行解作为解决问题的近似解, 再按照某一规则将近似 解转变成可行解的过程。近似解可行化策略本质上是一种事后性的处理措施。显然,采取这 种措施后,一般可确保至少得到所求问题的一个可行解。 4、近似解的获取 记 CNT(tabuk)为 tabuk 中的节点数。 子回路互异 若 vi ≠ v j,vi ∈ tabuk,v j ∈ tabuk ',i ≠ 0,j ≠ 0, k ≠ k ,则称子回路
'

tabuk 和 tabuk ' 互异,记为 tabuk ∩ tabuk ' =Φ ,即两个子路径无相同节点。
易知,任意数量的子路径构成的集合必属于可行解、未满非可行解、溢出非可行解以及 混合非可行解等四种情形之一。 可行解 所谓可行解是这样一种集合,该集合的元素是两两互异的子路径,并包括所有 节点即 S1 = tabur r = 1, 2, , R, tabur ∩ tabur ' = Φ, r ≠ r ,
'



∑ CNT (tabu ) = N N 为图
r =1 r

R



中节点总数。 未满非可行解 未满非可行解由两两互异的子回路组成,并存在一个或多个节点未在该 解的路径中 S 2 = tabur r = 1, 2, , R, tabur ∩ tabur ' = Φ, r ≠ r ,
'



∑ CNT (tabu ) < N
r =1 r

R



记 Lg ( S 2 ) 为 S2 中所包含的节点数。显然, Lg ( S 2 ) 越大,未满非可行解越接近可行解。 设 S2 为未包含的节点集,则显然有 Lg ( S 2 ) + Lg S 2 = N 。将那些在所有未满非可行解中 具有最大 Lg ( S 2 ) 的未满非可行解称为最大未满非可行解。 溢出非可行解 溢出非可行解虽然包含了所有节点,但它存在某些子路径不互异,即存
21

( )

中文译文

在公共节点。S3 = tabur r = 1, 2, , R, tabur ∩ tabur ' = Φ, r ≠ r ,
'



∑ CNT (tabu ) > N
r =1 r

R



记 L p ( S3 ) 为溢出非可行解 S3 中的公共节点数。 公共节点数的计算方法为比较任意连个不互 异的子路径,计算相同节点数,公共节点数为所有这些节点数量的累加,进而有

∑ CNT (tabu ) = N +L ( S )
r =1 r p 3

R

(4.17) 因此 L p ( S3 ) 越小,溢出非可行解越接近可行解。显然,当 L p ( S3 ) =0 时,溢出非可行 解就变为可行解了。将那些在所有溢出非可行解中具有最小 L p ( S3 ) 的溢出非可行解称为最 小溢出非可行解 混合非可行解 混合非可行解是指未包括所有节点,并存在某些子路径不互异的解,即
R S 4 = tabur r = 1, 2, , R, tabur ∩ tabur ' = Φ, r ≠ r ' , ∑ CNT (tabur ) ≠ N r =1

近似解 将所有最大未满非可行解和最小溢出非可行解称为近似解。按该定义,虽然当 算法不存在可行解时, 从理论上并不能保证一定存在近似解, 但实践中同时不存在溢出非可 行解和未满非可行解情况的可能性非常小,因此几乎不对近似解的获取产生影响。 5、近似解的可行化 在获得近似解后, 接下来的问题是如何将近似解转变为可行解。 对于最大未满非可行解, 可行化策略就是采用某种方法将未在路径中的点插入到现有路径中。易知, S2 中的点只能 插入到时间允许的两个任务之间。若要将任务 k 插入到已在路径上的弧段(i,j)中间,需要 满足如下条件: 1) i<k<j 2)

bi +si +tik <bk

bk +sk +tkj <bj

插入后的代价值为:

S ij , k = dik + d kj d ij

( )

显然, S ij , k 越小说明将任务 k 插入(i,j)之间的后增加的空载里程越小。设计近似 解可行化的步骤如下:

( )



22

中文译文

(1)将 S2 中的节点插入到 S2 中允许插入的弧段中间,为计算方便仅考虑满足约束(1)即 i<k<j 得到代价集合 M= S ij , k vk ∈ S 2 , ij ∈ S 2 , i < k < j 。 (2)将 M 中 S ij , k 按从小到大顺序排列。 (3)若 M = Φ , 则算法终止, 此时有 S 2 = Φ ; 否则取 M 中第一项 S ij , k 插入已有路径, 转步骤(4)。 (4)更新路径信息,将 k 插入路径。 S 2 = S 2 ij + ik , kj , S 2 = S 2 {k } ,删除 M 中 所有包含 ij 或包含 k 的 S ij , k 值;转步骤(1)。 4.3.4 算法步骤 (1)初始化各参数,输入基础数据,计数器 Nc=0。 (2)将 M 只蚂蚁随机均匀的放到 N 个节点上,得到节点 i 的蚂蚁集 Si 和蚂蚁数量 bi ,初 始化 tabuk 以及 allowed k ,令 l =0(已完成任务的蚂蚁数量);蚂蚁的过程变量初始值 Pro[k]=1 (3)在节点 i 取蚂蚁 k,按转移规则确定后继节点 j,若存在可选后继节点,更新 tabuk ,

{( )




}

( )



( )



{} {


}



( )



Si , bi ,转(5)。若不存在可选后继节点,置控制变量 Pro[k]=2,转(4)。
(4)从蚂蚁 k 初始点反向搜寻先行节点,置 d ij = d ji ,按转移规则选择先行节点 j。若存 在可选先行节点,更新 tabuk , Si , bi 。若不存在可选先行节点,则 l ++。 (5)更新 S j ,重复(3)到(5),直到 bi =0。 (6)在所有蚂蚁都移动一次之后,按局部更新规则进行信息素更新。 (7)更新所有节点的 bi , 若所有节点上蚂蚁数量 bi =0 或 l =M,跳转至(8), 否则跳转至(3)。 (8)由 tabuk 生成路径集 L = { L1 , L2 , …,LM } ,寻找可行解,得到可行解集

A = { A1 , A2 , , Ap } 若未发现可行解,则采取近似可行化策略,并跳转至(9)。
(9)计算本次搜索得到的最优路径 L ( q ) ,并得到亲近为止的最优路径,
*

L* = min {L* ( q ) , L* } ,按全局更新规则进行信息素更新。

23

中文译文

(10)若 Nc≥Ncmax,则算法终止,并输出 L ;否则,Nc++,并跳转至(2)。

*

4.4 算例分析
4.4.1 案例设计 已知某靠泊集装箱船舶需要装卸的进口集装箱和出口集装箱总量分别为 h=100 和 m=125,使用两个岸桥(图 4.3)来进行船舶的装卸作业,其中岸桥 1 的前 90 个作业为进口集 装箱作业,后 25 个作业为出口集装箱作业;岸桥 2 的前 10 个作业为进口集装箱作业,后 100 个作业为出口集装箱作业。一般在码头进行靠泊集装箱船作业时,先进行卸下进口集装 箱作业,再进行装载出口集装箱作业,所以对于岸桥中的作业来说,进口集装箱作业都是排 在前面。 同时为了能够让船舶作业中间出现进出口集装箱混和作业的现象, 便于动态调度集 卡, 设置岸桥 1 在岸桥 2 作业 5 分钟后才开始作业。 设集卡平均行驶速度为 18Km/h, 5m/s, 即 空载与满载情况下速度相同。

船舶

岸桥 1

岸桥 2

卸载

卸载

装载 时间 t 装载

图 4.3 案例设计

不同的集装箱码头进出口集装箱在堆场的箱区安排不同, 一些码头采取进出口集装箱混 合堆存的原则,既同一箱区既堆存出口集装箱(装上船的集装箱)也堆存进口集装箱(卸下 船的集装箱) ;而一些码头采用进出口集装箱分别堆存的原则,即一个箱区内只能堆存进口 集装箱或只能堆存出口集装箱。本文对第二种情况进行研究。 进出口集装箱分别堆存在码头四个箱区中, 四个箱区到岸边的距离以及箱区之间的距离 见表 4.1。其中箱区 1 和箱区 2 用来堆存出口集装箱,而箱区 3 和箱区 4 用来堆存进口集装
24

中文译文

箱,并随机生成集装箱所在的箱区。

距离参数(单位: 表 4.1 距离参数(单位:米)

岸边 箱区 1 箱区 2 箱区 3 箱区 4 670 560 600 800

箱区 1

箱区 2

箱区 3

1200 600 50 600 550 300

岸桥的平均装卸效率为 1.7 分钟。由此推算出各个调度任务的起始时间和结束时间,见 附录 A 时间数据表。表中列出了每个调度任务的开始时间,结束时间以及所在箱区。其中 所在箱区的信息暗含了调度任务的开始地点以及结束地点。例如集装箱 1 堆存在箱区 4,而 箱区 4 是存放进口集装箱,所以集装箱 1 作业的开始地点在岸桥,结束地点在箱区 4。同时 结合表中的信息以及箱区之间的距离, 能够计算出集卡在调度任务之间所需行走的距离以及 花费的时间。 4.4.2 模型求解 按照上述设计采用自适应 Ant-Q System 算法求解。对数据进行预处理生成包含 225 个 任务节点的 TSP 图。依据堆场岸区距离矩阵和车辆运行速度得到任务距离矩阵。其他参数 设置如下: α =1 , β =2 , ρ =0.1 , q 0 = 0.9 算法最大迭代次数为 15000 次。使用 Matlab 软件求解,最终得到由个子路径构成的解,即共需 8 辆集卡一同作业。最终任务序列串入如 下表所示:

表 4.2 任务序列

集卡 编号 1

任务 数量 31

任务编号串 1→4→10→18→21→30→34→42→47→54→60→66→81→96→101→110→ 119→128→132→142→145→151→159→172→176→184→195→200→208→ 212→216

2

29

2→6→13→19→24→36→41→48→53→63→67→74→77→88→92→107→111 →117→127→146→155→164→170→179→187→201→207→217→224

3

31

3→8→17→27→35→50→55→78→90→93→99→104→109→118→126→130 →133→140→144→150→153→160→163→173→183→188→198→206→211 →218→220

4

29

5→12→20→31→38→52→58→70→75→79→83→94→100→112→115→122
25

中文译文

→125→129→136→139→143→147→154→161→177→181→194→199→215 5 27 7→16→26→29→39→45→51→59→69→76→85→89→102→108→121→126 →138→152→158→167→175→180→190→205→209→222→225 6 26 9→15→44→49→56→64→71→86→97→103→114→120→124→131→141→ 149→156→165→169→178→185→189→193→202→214→221 7 24 14→22→25→32→37→46→57→61→68→73→84→87→98→105→116→135 →162→168→171→182→192→197→203→210 8 28 11→23→28→33→40→43→62→65→80→82→86→91→95→106→113→134 →137→148→157→166→174→186→191→196→204→213→219→223 该方案在确保岸桥持续作业不等待集卡的前提下尽可能的减少空载里程, 同时使参与作 业的集卡数量最小。

26

中文译文

第 5 章 结论
在经济危机席卷全球,贸易保护主义抬头,航运经济不景气的大背景下,通过更为精细 科学的优化管理降低成本, 从有限的业务量中创造出最大化的利润空间, 已经成为码头管理 者在激烈竞争中得以立足和发展的重要环节。 我国集装箱码头吞吐量增长迅速, 中国港口将 主导亚洲的集装箱运输市场, 集装箱运输的中国时代将随之到来。 然而对码头内部资源的优 化配置却远远落后于国际上其他大型码头。 本文针对针对国内集装箱港口仍有很大优化空间的码头水平运输系统集卡调度问题进 行研究, 建立了单船作业下, 面向作业面的集卡调度优化模型。 运用蚁群算法进行模型求解, 求解过程中,建立了以任务为节点的 TSP 图,借鉴了蚁群算法在求解 VRP 问题中所用到的 子路径组合可行解的方法, 同时确定最优集卡数量和最优集卡任务序列。 不同于以往研究中 将数量配置模型和集卡路径优化分开研究的方式, 本文所给出的求解算法在一次求解中同时 获得任务序列和所需集卡数量。 给出的数值算例表明, 本文的模型在确保岸桥的计划任务无 延迟完成的情况下,能够大大减少集卡的空载里程。 同时,本论文也存在着许多不足。由于时间、能力和条件有限,本论文在建立模型时还 有诸多的因素被忽略,如集装箱尺寸的因素,岸桥与岸桥之间的相互距离等,还有许多工作 有待于进一步研究和完善。 希望本论文的研究能够为集装箱码头内部运作实践提供有益的思 路和指导。 针对本论文的不足以及目前集装箱码头运作管理中存在的一些问题, 以及计算机 在集装箱码头经营管理中的诸多优点,可进行下一步的研究工作有: (l)考虑多船作业时拖车调度的问题研究。集装箱码头在进行装卸作业的时候会出现多 条船同一时间作业的现象, 如果能将不同船舶分配的拖车联合起来调度, 实现拖车满场跑的 状态, 则能更好地提高集装箱码头地整体作业效率。 但是多船作业需要考虑比单船作业更多 的因素,所以问题更为复杂。 (2)综合岸桥,拖车和场桥的问题研究。普遍的集装箱码头装卸工艺为岸桥—拖车—场 桥。岸边的集装箱由岸桥负责,堆场的集装箱由场桥负责,而拖车联系着岸边和堆场。这三 者相互影响相互制约,将其同时考虑将更为全面。 (3)不同类型水平运输工具的数量配置和调度优化问题研究。有些集装箱码头将多种水 平运输工具混合使用:单容量的拖车,多容量的拖车,跨运车等。这样如何混合搭配不同类 型的车辆,如何调度就变得比较重要。

27

中文译文

参考文献
[1]宗蓓华,真虹. 港口装卸工艺学[M].北京:人民交通出版社,2003 [2]刘志硕,申金升,柴跃进. 基于自适应蚁群算法的车辆路径问题研究[J].控制决 策,2005,20(5):562-566. [3] 葛盼盼,王继荣,李军等. 基于蚁群算法的码头集装箱卡车路径优化研究[J].物流 科技,2008,12:26-28. [4] Dirk Steenken, Stefan Vo, and Robert Stahlbock. Container terminal operation and operations research-a classification and literature review[J].OR Spectrum,2004,26:3-49. [5] Etsuko Nishimura,Akio Imai,Stratos Papadimitriou.Yard trailer routing at a maritime container terminal:[J].Transportation Research Part E41,2005,53-76. [6]ColoriniA, Dorigo M, ManiezzoV. Distributed optimization by Ant Colonies. lst Euro Pean Conferenee Artifieial Life,Pans. Elsevier, Franee, 1991. [7]段海滨. 蚁群算法原理及其应用[M].北京:科学出版社,2005 年. [8]Gambardella L M, Dorigo M. Ant-Q: a reinforcement learning approach to the traveling salesman problem. Proceeding of the 12th International Conference on Machine Learning, 1995, 250~260. [9] Dorigo M, Gambardella L M. A study of some properties of Ant-Q. Proceeding of the 4th international Conference on Parallel Problem Solving from Nature, 1996, 656~665. [10]Bullnheimer B, Hartl R F, Strauss C. An improved ant system algorithm for the vehicle routing problem. Technical Report POM-10/97, Institute of Management Science, University of Vienna, Austria,1997, Ann. Oper. Res. 89,1999. [11]Bullnheimer B, Hartl R F, Strauss C. Applying the ant system to the vehicle routing problem. Meta-heuristics: Advances and Trends in Local Search Paradigms for Optimization, Kluwer Academic Publishers, Boston, MA, 1999, 285~296. [12]Gambardella L M, Taillard E, Agazzi G. MACS-VRPTW: a multiple ant colony system for vehicle routing problems with time windows. New Ideas in Optimization, McGraw-Hill, London, UK, 1999, 63~76. [13]陈瑜. 集装箱码头堆场拖车动态调度问题研究[D].硕士,四川大学,2006 年.
28

中文译文

[14]陈方鼎. 基于群体智能算法的集装箱码头集卡调度研究[D].硕士,大连海事大学, 2008 年. [15]林艺明. 集装箱码头调度问题研究[D].硕士,上海海事大学,2007 年. [16]胡强. 集装箱码头物流系统性能分析与仿真[D].硕士,武汉理工大学,2005 年. [17]黄茹. 一种解决指派问题的蚁群算法[J].西安邮电学院学报,2006 年,11(3):106-1

29


赞助商链接
相关文章:
集装箱码头泊位、岸桥和集卡协同调度优化研究
集装箱码头泊位、岸桥和集卡协同调度优化研究_交通运输_工程科技_专业资料。专业...然后以经典的遗传算法为基础,对数学模型进行求解; 最后,以国内某港口的实际数据...
基于动态蚁群算法的集装箱国际多式联运路径优化研究
基于动态蚁群算法的集装箱国际多式联运路 径优化研究 ? 2013-02-07 17:12:...各个目的港集装箱码头, 在目的港卸下后通过各种方式将集装 箱运到沿海的支线...
蚁群算法报告
蚁群算法实例--集装箱码头船舶调度 模型 2.1 集装箱码头船舶调度流程图程序 开始 1.计算俩个船舶之间的时间间隔 2.初始化信息素 3.设置相关参数和变量 设置...
集装箱码头AGV概述
研究 重点主要集中在自动化码头 AGV 调度系统上,该系统十分利于调度算法的实施,...柏林科技大学的 HansOtto 等探讨了进口集装箱装载和卸载操作时集卡的最优路径...
节能减排示范项目--集装箱码头集卡全场智能调度系统
节能减排示范项目--集装箱码头集卡全场智能调度系统_经管营销_专业资料。集装箱码头资源管理资料今日推荐 88份文档 2014全国高考状元联手分享状元笔记 ...
毕业论文-基于改进蚁群算法的云计算任务调度研究
毕业论文-基于改进蚁群算法的云计算任务调度研究_理学_高等教育_教育专区。学科分类号 110 黑龙江科技大学本科学生毕业论文题 目 基于改进蚁群算法的云计算任务调度...
英文论文翻译-关于集装箱转运中心集卡的调度算法
集卡的工作序列.本实验结果显示了基于最 小成本流的遗传算法优于邻域搜索算法....(2006)对集装箱自动码头的自动搬运车调度策略进行仿真研究,并 用可扩展仿真模型...
怀化论文网代理发表职称论文发表-水库优化调度决策动态...
采用新型蚁群算法的 UAV 动态航迹规划 14……面向突发干扰情景的生产重调度研究...基于改进模拟植物生长算法的集装箱码头插船调度优化 41……背包问题的动态规划...
起重机调度—运筹学
假若没有一个合理的龙门吊作业调度计划,集卡可能会长...进到箱区 i 时,根据蚁群算法思想,在集装箱箱区 ...、 ? 、 ?、 m 等主要参数进行研究 [3] ,但...
基于蚁群算法的VRPTW问题优化研究附属材料 - 副本_图文
基于蚁群算法的VRPTW问题优化研究附属材料 - 副本_管理学_高等教育_教育专区。...而合理的配送路径优化能够有效利用现 有资源进行车辆调度,从而缩减成本,实现利润...
更多相关标签: