《公共泊位系统中通过遗传算法制定的泊位调度计划》由会员分享，可在线阅读，更多相关《公共泊位系统中通过遗传算法制定的泊位调度计划（3页珍藏版）》请在金锄头文库上搜索。
1、公共泊位系统中通过遗传算法制定的泊位调度计划简介： 大多数港口的集装箱泊位被船舶运营商租赁出去，为了让他们直接参与和负责集装箱的处理过程,从而获得更高的生产力。然而这种方法适用的情况是有大量船舶挂靠港口，集装箱作业量大且稳定。如果船舶和集装箱的数量不足，就不可能会节约成本。在过去的几年里日本的港口收费一贯的高于其他的主要枢纽港口，一部分增加的成本是由于相对较小的港口货运量却过多投资的缘故。在上述背景下，,通过引入公共泊位系统来限制泊位数量是很有意义的。在此系统中的泊位分配，即为到港船只的装卸作业分配泊位，在使周转时间最小化的过程中起重要作用，这是因为一个特定的船舶装卸时间在每一个泊位不一定是相
2、同的。虽然公共泊位系统不受大多数国家的大型集装箱港口的欢迎,但土地稀缺的港口仍在使用它，如新加坡、香港和釜山等。 本文的目的是为解决泊位分配问题开发一个遗传算法(GA)，Imai等人对待所谓的静态泊位分配问(SBAP) 如下，给定一组船只在规划周期的开始准备接受服务，找到一组作业，来使包括等待接受服务时间在内的时间总和最小化。这个问题可以简化成一个经典的二维分配问题(或加权两偶匹配问题)，可以通过多项式解决。动态泊位分配问题(DBAP)是SBAP的一般化情况，是对待船舶在规划周期的开始后，附带准备时间等待接受服务。DBAP不知道要解决有界多项式的时间，因此,为解决DBAP提议采用基于拉格朗日松
3、弛法的启发式。 DBAP假定每个泊位每次只服务一只船，事实上,它可以服务多个船只，只要泊位长度不小于船舶总长度(包括一些限额)。稍后将显示,这种服务假设下的DBAP，可以作为一个非线性规划制定。为了促进解决这类DBAP，我们使用遗传算法GAs。 大多数港口研究将他们的注意力集中在战略和战术问题上。由于大量的集装箱泊位是由具体的航运公司私营的,很少研究是关于在公共泊位系统进行泊位调度。 Lai和Shih出于为使香港HIT码头的泊位更有效的使用，对泊位分配问题提出一些启发式算法。尽管我们的问题并非如此，他们的问题假设先到先得（FCFS）的分配策略,因此他们的解决方案可能不如我们的好。 Brown等
4、人视船舶为停在军港，他们确定使船舶在港总收益最大化的，船到港作业的最佳集合，军港的泊位计划和商业港口泊位计划有着重要的区别，前者是寻求适当的服务时发生移泊，新到达的船舶必须分配给一个已经在服务船舶的泊位。这种处理方法在商港不大可能。考虑到移泊和其他与商港不相关的因素。从而使军港的问题不适合商业港口。 Imai等人考虑商业港口的泊位分配问题，大多数服务队列一般根据先到先得（FCFS）原则处理。他们得出结论，为了得到高效的港口生产力，最理想的船到泊位的任务分配，应该建立一个不考虑先到先得原则的机制。然而，这可能会导致一些船舶对服务序列不满。为了结合这泊位性能和服务序列的满意度两个标准来评估，他们开
5、发出一个启发式算法，来找出一组不算差的解决方案，使泊位性能最大化以及服务序列的不满最小化。但是他们的服务原则不适用于动态分配。 遗传算法正在越来越多的用于解决棘手的问题，如NP难问题。大多数的机器调度问题属于这类NP难问题，几项研究应经成功地将遗传算法应用于机器调度问题。Chan 和 Imai为多个船舶靠泊的泊位分配问题，开发了一个基于遗传算法的启发式。模型： DBAP做出如下假设： （a） 每条船必须在某一泊位，接受且只接受一次服务 （b） 船只必须在一个满足该船物理条件（水深和码头长度）的泊位接受服务, （c） 每条船的装卸时间取决于他所在的泊位。 i（=1，I）B是一组泊位 j（=1，J
6、）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、超出分配泊位的水深。约束方程（7）保证j船和j船的全长（包括安全距离）不超过i泊位的码头长度。约束方程（6）和（7）表示的是j船和j船在同一泊位接受服务。在这些约束当中，mj+CijXij表示j船的离开时间，而mj+CijXij表示j船的离开时间。因此mj+CijXij- mj（11）代表j船的开始服务时间与j船的离开时间的差别， mj+CijXij- mj（12）代表j船的开始服务时间与j船的离开时间的差别。因此，如果j船和j船在同一特定港口有重叠部分，方程（11）（12）都是正值，否则其中一个为负值。它的合理性描述如下：如果j船在j船开始服务前已经结束服务了，方程（11）为负，方程（12）
8、为正。如果他们以相反的顺序提供服务，那方程（11）为正，方程（12）为负。因此如果Yjj=1，那么约束方程（6）的左半部分0，约束方程（7）的左半部分=0。否则约束方程（6）的左半部分=0，约束方程（7）的左半部分0。 过程： T表示在一个子问题里面分配给泊位的船舶的数量。k表示在泊位服务序列的位置， S(k)表示在第k个为止接受服务的船舶。L(S(k)表示S(k)的长度。假设在某一作业时间有pl艘serviced ship，然后最后一艘离开的船用V(1)表示，剩余其他的serviced ship按离开的相反的顺序记为V(2)、V(3)V(pl)。（即倒数第二艘离开的为V(2)以此类推）。需注
9、意,如果没有观察到几项服务同时发生,将pl设置为1。 Step 1.让k=1 Step 2.如果kT，终止。否则让i=1，并且在子问题和上代子问题中为S(k)找到serviced ship。在serviced ship中选择最后离开的船表示为V(1)。 Step 3.如果所有的serviced ship都检查完毕，就执行下面过程： 让pl=i，m=1.将V(i)（i=1，pl）带入上面提到的与离开时间相逆的序列。 跳转到Step 5. 否则，从serviced ship中随意地选出一艘，跳转到Step 4. Step 4.选出来的船定为j船，如果为j船和V(1)的服务重叠了，让i=i+1，V(i)=j，跳回Step 3. Step 5.如果mpl，让S(k)到达后就开始它的服务，并且跳到Step 9.Step 6.如果 泊位长度（即如果，服务重叠的船舶和S(k)船的总长度不超过泊位长度），跳转到Step 8.否则设置clock time =V(m)的离开时间，跳转到Step 7. Step 7.如果S(k)在clock time之前到达，就在clock time时开始服务。否则在其到达时间就开始服务。跳转到Step 9. Step 8.让m=m+1，跳转到Step 5. Step 9.让k=k+1，跳转到Step 2.
