基于蚁群算法的泊位调度优化与仿真
开篇：润墨网以专业的文秘视角，为您筛选了一篇基于蚁群算法的泊位调度优化与仿真范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！
摘要：在全球贸易经济聚焦在中国的同时，港口的吞吐能力成为目前港口业的主要矛盾。提高泊位这个环节的运作能力，减少船舶在港时间，增加港口的吞吐能力成为主要研究对象。本文采取仿真模型与优化算法相结合的研究方法，把泊位调度问题转化为旅行商问题，建立了一个泊位岸桥协调调度，通过蚁群算法建立数学模型，使船舶在港时间最短为目标建立函数，求得最佳调度方案。用ProModel建立船舶到港停泊及离港仿真模型。验证泊位调度优化的有效性，以便指导港口实际的泊位调度。
关键词：蚁群算法；泊位调度；ProModel仿真模拟
中图分类号：TP18 文献标识码：A文章编号：1007-9599(2012)01-0000-02
Berth Scheduling Optimization and Simulation Based on Ant Colony Algorithm
Wang Minchuan1,Yuan Bin,2
(1.Radio and Television University of Zhengzhou,Zhengzhou450007, China;2. Henan Polytechnic,Zhengzhou450000,China)
Abstract:In global trade and economic focus in China at the same time, the port handling capacity of the port industry is currently the principal contradiction.Berths in this part of the operational capabilities,reduce ship in Hong Kong time,to increase port capacities to become the main object of study.Take the simulation model and optimization algorithm combining research methods in this article,the berth scheduling problem into the traveling salesman problem,the establishment of the coordinated scheduling of a berth quay crane,through a mathematical model of ant colony algorithm,so that the ship established with the objective function is the shortest time in Hong Kong obtain the optimal scheduling scheme. Build ships to berthing and departure simulation model using ProModel. Verify the effectiveness of berth scheduling optimization to guide the port berth scheduling.
Keywords:Ant colony algorithm;Berth scheduling;ProModel simulation
一、绪论
航空港作为一个重要的交通枢纽，是连接世界贸易的重要环节之一。在全球贸易经济聚焦在中国的同时，港口的吞吐能力成为目前港口业的主要矛盾。加速港口建设，提高工作效率，成为当前港口泊位研究的热门问题。港口的泊位服务系统比较复杂，它不仅需要各种资源的高效利用，还需要各个环节高度协调、配合。
二、研究方法和技术
（一）基于蚁群的算法。我们把模拟蚂蚁寻找路径的不同方式总结出一种仿生算法成为蚁群算法。这个算法是通过候选解组成群体来寻求最优解的进化过程,他的优势在于在一定规则基础上，减少冗长的编程过程，求得最优解。
蚁群算法我们可以把它理解为旅行商问题，在n个城镇之间，确定一条必须经过各城市的最短路线。各个蚂蚁都是有如下特征：蚂蚁在从城市a到城市b的运动过程中，在边(a,b)上释放一种信息素轨迹，把选择下一个城市作为概率，建立两城市间距离和连接两城市的路径上有轨迹量的函数。
假定各条线路上的信息素量在初始时间相等，在运动过程中的转移方向根据各条路径上的信息素量来决定。在m时刻，蚂蚁k在城市a选择城市b的转移概率 (m) 为：
(m)=
经过一次循环，n个时刻，信息素量根据下式调整
Τab(n+1)=ρ▪τab(m)+ τab(m,m+1)(2.2)
τab(m,m+1)= (2.3)
（注：Τab为边(a,b)上的信息素强度； τab为蚂蚁k在边(a,b)上在单位长度上留下的轨迹信息素量。）
在该系统中，取得全局最优解的路径才允许释放信息素，这样的搜索过程更具有指导性。目前常用的信息素量更新模型有以下几种：蚁密模型、蚁量模型、蚁周模型。
（二）过程仿真方法。仿真是通过计算机运行仿真模型，观察仿真运行过程并统计仿真结果，根据仿真输出参数，评价并推断实际系统的真实性能。模型、系统和仿真构成了计算机仿真的三要素。系统仿真技术是以计算机作为载体，对活动的过程进行模拟并得到结果，为人们的决策提供支持。通过计算机仿真来对港口工作流程进行模拟，是根据不同的港口条件，模拟仿真港口的运行情况。并根据模拟仿真得到的数据，来为港口建设提供相关的依据。
ProModel是由美国ProModel公司开发出来用于构造多种生产、服务和系统模型的仿真工具。这个系统可以很精确地建立一个能够把经营过程以及其资源配置之间的随机、互相依赖和不确定性统一起来的模型，具有对连续或离散事件的、动态的和随机的分析功能。它提供了一个人机交互系统，通过设定相应操作过程，就可以完成一个简单的仿真。ProModel的基本仿真元素由结构部件及运算元素两个部分组成。在这个系统中通过设定相关参数、变量以及选取规则，并通过系统中各个环节的运行情况，测试各个流程的可行性。
（一）数学建模。在本模当中，我们将泊位视为一个离散的静态的泊位系统。在开始的时间，所有船舶到港时间都已经确定，都将考虑到下一个分配的时间段当中。根据船舶停泊的物理限制。检查泊位是否空闲，当泊位空闲时，分配岸桥开始卸货服务，若不空闲，则在锚地等待。本模型的目标是船舶在港时间最短。本文的最优化目标可写成
min Tkjs-Taj+Tkj)XijYkj (3.1)
（二）算法的参数设定：1.蚂蚁数量：设m是蚂蚁的数量，蚂蚁数量的选择宜选取m= ~n/2之间，当某个泊位空闲时，系统开始选择下一个节点。2.状态转移概率：系统根据下一个可选的信息量来计算下一步的转移概率。 (z)表示在z时刻船舶k在a点出发选择b船舶的选择概率：(z)= (3.2)。3.信息素更新规则：根据分析，蚁周模型的效果最好。信息素更新公式如下：
τij(t+n)=(1-ρ)?τij(t)+ τij(t) (3.3)
（三）实例仿真。本文以某港口一天内到港的船舶分配泊位实际情况为例。确定该港口的泊位、抵港时间及服务时间。假设该码头有8个岸桥，为3个泊位公用。在1天内，该码头有6条船抵港并已于当日离港，每个泊位旁边均匀分布有岸桥。在此，3号泊位固定有2台岸桥，1号和2号岸桥分别固定有3台岸桥。平均卸货速度为35箱/小时。
优化方法如下，本问题的规模为n=6，根据选取方案，假设蚂蚁个数m=3，信息启发因子β=1，迭代次数NC=20，期望启发因子α=1.5，ρ(t0)=0.84，信息总量Q=100，ρmin=0.0011，结合船舶抵港时间，得出泊位1有1号、3号船；泊位2有2号、6号船；泊位3有5号、4号船。优化后，所有船舶在港时间为44.68h。
蚁群算法的收敛过程如下图：
蚁群算法收敛过程图
从图3.1可知，利用蚁群算法求解泊位岸桥调度问题的进化速度很快。通过比较可以看到基于蚁群算法的调度方案能够有效的缩短所有船舶在港时间。
四、调度仿真
（一）建立泊位系统仿真模型。建立基本模型元素：实体（Entities）、站点（Location）、资源（Resource）、属性（Attributes）、实体到达频率（Arrivals）、变量(Variables)以及本地变量（count）。
（二）仿真模型设计方法。根据设定优化分配方案，船到港后，结合船舶的属性，为船舶提供合适的泊位资源。如果没有空闲泊位则在锚地等待，如果泊位有空闲，则停靠在空闲泊位，并等待岸桥进行装卸作业，岸桥对其装卸作业完成，船舶离开释放泊位和岸桥资源。仿真模型的基本设计过程：到港、等待、进港、卸货、离开。根据模型运行单位不同，我们将对两种情况对泊位调度进行仿真模拟，具体分为：对同一批船舶到港过程来说，分别按照先来先服务原则分配泊位和蚁群算法调度方案分配泊位两种方案安排停泊。
（三）基于先来先服务分配原则。先来先服务分配原则是将船舶的到港时间、船长、装卸量及吃水深度等相关属性输入到设计好的仿真模型中。等船只到达锚地后，再根据船只的类型确定泊位，假如有多个泊位同时符合停泊要求，就随机选择空闲泊位。统计得出的所有船舶的平均等待时间为8.25小时。
（四）基于蚁群算法调度分配方案。该分配方案用ProModel系统进行仿真。船只到港后，有泊位则直接到相应的泊位上停泊、卸货；无泊位则等待，等有泊位后，再到泊位上卸货。系统运行20天，得出结果：蚁群算法调度分配方案，船只平均等待时间为7.77小时。
（五）结论分析。通过2种策略的实验分析，我们知道按照基于蚁群算法调度方案分配，所有船舶在港时间较短。经过2种方案的对比，可以看出基于蚁群算法调度方案分配方案，所有船舶等待的空闲时间较短，同理可推出每条船的平均在港时间都比先到先服务的方案得到的时间短。
五、结论
本文通过对到港船只的整个作业的分析，通过蚁群算法建立模型，将岸桥调度作为主要因素放到泊位调度的研究中，建立在港时间最短的目标函数，求得最佳调度方案。但是采取蚁群算法模型的计算量比较大，对大港口的优化和控制能力有待提高。同时在该模型中，我们没有设置维修和保养的时间。在以后的研究中，可以将整个港口为研究对象，加入工人的工作经验，使之更符合实际情况，便于指导港口实际工作。
参考文献：
[1]王素明.基于蚁群算法的港口调度问题研究:（硕士学论文）.沈阳:辽宁科技大学,2008
[2]Lai K K, Shih K. A study of container berth allocation[J].Journal of Advanced Transportation, 1992, 26:45-60
[3]韩笑乐,陆志强等.具有服务优先级别的动态离散泊位调度优化[J].上海交通大学学报,2009.6:902-905
[4]李强,杨春霞等.集装箱码头泊位生产调度均衡优化[J].沈阳建筑大学学报(自然科学版)2008.11:1132-1136