公共泊位系统中通过遗传算法制定的泊位调度计划【DOC精选】.doc

公共泊位系统中通过遗传算法制定的泊位调度计划 简介： 大多数港口的集装箱泊位被船舶运营商租赁出去，为了让他们直接参与和负责集装箱的处理过程,从而获得更高的生产力。然而这种方法适用的情况是有大量船舶挂靠港口，集装箱作业量大且稳定。如果船舶和集装箱的数量不足，就不可能会节约成本。在过去的几年里日本的港口收费一贯的高于其他的主要枢纽港口，一部分增加的成本是由于相对较小的港口货运量却过多投资的缘故。 在上述背景下，,通过引入公共泊位系统来限制泊位数量是很有意义的。在此系统中的泊位分配，即为到港船只的装卸作业分配泊位，在使周转时间最小化的过程中起重要作用，这是因为一个特定的船舶装卸时间在每一个泊位不一定是相同的。虽然公共泊位系统不受大多数国家的大型集装箱港口的欢迎,但土地稀缺的港口仍在使用它，如新加坡、香港和釜山等。 本文的目的是为解决泊位分配问题开发一个遗传算法(GA)，Imai等人对待所谓的静态泊位分配问(SBAP) 如下，给定一组船只在规划周期的开始准备接受服务，找到一组作业，来使包括等待接受服务时间在内的时间总和最小化。这个问题可以简化成一个经典的二维分配问题(或加权两偶匹配问题)，可以通过多项式解决。动态泊位分配问题(DBAP)是SBAP的一般化情况，是对待船舶在规划周期的开始后，附带准备时间等待接受服务。DBAP不知道要解决有界多项式的时间，因此,为解决DBAP提议采用基于拉格朗日松弛法的启发式。 DBAP假定每个泊位每次只服务一只船，事实上,它可以服务多个船只，只要泊位长度不小于船舶总长度(包括一些限额)。稍后将显示,这种服务假设下的DBAP，可以作为一个非线性规划制定。为了促进解决这类DBAP，我们使用遗传算法GAs。 大多数港口研究将他们的注意力集中在战略和战术问题上。由于大量的集装箱泊位是由具体的航运公司私营的,很少研究是关于在公共泊位系统进行泊位调度。 Lai和Shih出于为使香港HIT码头的泊位更有效的使用，对泊位分配问题提出一些启发式算法。尽管我们的问题并非如此，他们的问题假设先到先得（FCFS）的分配策略,因此他们的解决方案可能不如我们的好。 Brown等人视船舶为停在军港，他们确定使船舶在港总收益最大化的，船到港作业的最佳集合，军港的泊位计划和商业港口泊位计划有着重要的区别，前者是寻求适当的服务时发生移泊，新到达的船舶必须分配给一个已经在服务船舶的泊位。这种处理方法在商港不大可能。考虑到移泊和其他与商港不相关的因素。从而使军港的问题不适合商业港口。 Imai等人考虑商业港口的泊位分配问题，大多数服务队列一般根据先到先得（FCFS）原则处理。他们得出结论，为了得到高效的港口生产力，最理想的船到泊位的任务分配，应该建立一个不考虑先到先得原则的机制。然而，这可能会导致一些船舶对服务序列不满。为了结合这泊位性能和服务序列的满意度两个标准来评估，他们开发出一个启发式算法，来找出一组不算差的解决方案，使泊位性能最大化以及服务序列的不满最小化。但是他们的服务原则不适用于动态分配。 遗传算法正在越来越多的用于解决棘手的问题，如NP难问题。大多数的机器调度问题属于这类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船的吃水深度，包括停泊的安全垂直距离 Lj是j船的长度，包括水平安全长度 当j船在i泊位接受服务时Xij=1，否则Xij=0 当j’船在同一泊位正在接受服务时，j船也开始他的服务时Yjj’=1，否则Yjj’=0 mj是j船开始接受服务的时间 在DBAP的公式中，决策变量是Xij，Yjj’和mj。公式（1）使是船只造成的总服务时间最小化。约束方程（2）保证每条船必须在某一泊位，接受且只接受一次服务。约束集合（3）保证当船舶到达后肯定会受到服务。约束方程（4）保证j船的吃水（包括安全距离）不会超出分配泊位的水深。约束方程（7）保证j船和j’船的全长（包括安全距离）不超过i泊位的码头长度。 约束方程（6）和（7）表示的是j船和j’船在同一泊位接受服务。在这些约束当中，mj+ΣCijXij表示j船的离开时间，而mj’+ΣCij’Xij’表示j’船的离开时间。因此mj+ΣCijXij- mj’（11