公共泊位系统中通过遗传算法制定的泊位调度计划

《公共泊位系统中通过遗传算法制定的泊位调度计划》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、公共泊位系统中通过遗传算法制定的泊位调度计划简介：大多数港口的集装箱泊位被船舶运营商租赁出去，为了让他们直接参与和负责集装箱的处理过程,从而获得更高的生产力。然而这种方法适用的情况是有大量船舶挂靠港口，集装箱作业量大且稳定。如果船舶和集装箱的数量不足，就不可能会节约成本。在过去的几年里日本的港口收费一贯的高于其他的主要枢纽港口，一部分增加的成本是由于相对较小的港口货运量却过多投资的缘故。在上述背景下，,通过引入公共泊位系统来限制泊位数量是很有意义的。在此系统中的泊位分配，即为到港船只的装卸作业分配泊位，在使周

2、转时间最小化的过程中起重要作用，这是因为一个特定的船舶装卸时间在每一个泊位不一定是相同的。虽然公共泊位系统不受大多数国家的大型集装箱港口的欢迎,但土地稀缺的港口仍在使用它，如新加坡、香港和釜山等。本文的目的是为解决泊位分配问题开发一个遗传算法(GA)，Imai等人对待所谓的静态泊位分配问(SBAP)如下，给定一组船只在规划周期的开始准备接受服务，找到一组作业，来使包括等待接受服务时间在内的时间总和最小化。这个问题可以简化成一个经典的二维分配问题(或加权两偶匹配问题)，可以通过多项式解决。动态泊位分配问题(DB

3、AP)是SBAP的一般化情况，是对待船舶在规划周期的开始后，附带准备时间等待接受服务。DBAP不知道要解决有界多项式的时间，因此,为解决DBAP提议采用基于拉格朗日松弛法的启发式。DBAP假定每个泊位每次只服务一只船，事实上,它可以服务多个船只，只要泊位长度不小于船舶总长度(包括一些限额)。稍后将显示,这种服务假设下的DBAP，可以作为一个非线性规划制定。为了促进解决这类DBAP，我们使用遗传算法GAs。大多数港口研究将他们的注意力集中在战略和战术问题上。由于大量的集装箱泊位是由具体的航运公司私营的,很少研究

4、是关于在公共泊位系统进行泊位调度。Lai和Shih出于为使香港HIT码头的泊位更有效的使用，对泊位分配问题提出一些启发式算法。尽管我们的问题并非如此，他们的问题假设先到先得（FCFS）的分配策略,因此他们的解决方案可能不如我们的好。Brown等人视船舶为停在军港，他们确定使船舶在港总收益最大化的，船到港作业的最佳集合，军港的泊位计划和商业港口泊位计划有着重要的区别，前者是寻求适当的服务时发生移泊，新到达的船舶必须分配给一个已经在服务船舶的泊位。这种处理方法在商港不大可能。考虑到移泊和其他与商港不相关的因素。从

5、而使军港的问题不适合商业港口。Imai等人考虑商业港口的泊位分配问题，大多数服务队列一般根据先到先得（FCFS）原则处理。他们得出结论，为了得到高效的港口生产力，最理想的船到泊位的任务分配，应该建立一个不考虑先到先得原则的机制。然而，这可能会导致一些船舶对服务序列不满。为了结合这泊位性能和服务序列的满意度两个标准来评估，他们开发出一个启发式算法，来找出一组不算差的解决方案，使泊位性能最大化以及服务序列的不满最小化。但是他们的服务原则不适用于动态分配。遗传算法正在越来越多的用于解决棘手的问题，如NP难问题。大多

6、数的机器调度问题属于这类NP难问题，几项研究应经成功地将遗传算法应用于机器调度问题。Chan和Imai为多个船舶靠泊的泊位分配问题，开发了一个基于遗传算法的启发式。模型：DBAP做出如下假设：（a）每条船必须在某一泊位，接受且只接受一次服务（b）船只必须在一个满足该船物理条件（水深和码头长度）的泊位接受服务,（c）每条船的装卸时间取决于他所在的泊位。i（=1，…I）∈B是一组泊位j（=1，…J）∈V是一组船Cij是j船在i泊位的装卸时间Aj是j船到港时间WDi是泊位水深QLi是i泊位的码头长度Dj是j船的吃水

7、深度，包括停泊的安全垂直距离Lj是j船的长度，包括水平安全长度当j船在i泊位接受服务时Xij=1，否则Xij=0当j’船在同一泊位正在接受服务时，j船也开始他的服务时Yjj’=1，否则Yjj’=0mj是j船开始接受服务的时间在DBAP的公式中，决策变量是Xij，Yjj’和mj。公式（1）使是船只造成的总服务时间最小化。约束方程（2）保证每条船必须在某一泊位，接受且只接受一次服务。约束集合（3）保证当船舶到达后肯定会受到服务。约束方程（4）保证j船的吃水（包括安全距离）不会超出分配泊位的水深。约束方程（7）保证

8、j船和j’船的全长（包括安全距离）不超过i泊位的码头长度。约束方程（6）和（7）表示的是j船和j’船在同一泊位接受服务。在这些约束当中，mj+ΣCijXij表示j船的离开时间，而mj’+ΣCij’Xij’表示j’船的离开时间。因此mj+ΣCijXij-mj’（11）代表j’船的开始服务时间与j船的离开时间的差别，mj’+ΣCij’Xij’-mj（12）代表j船的开始服务时间与j’船的离开时间的差别。