李作志，王育静

（天津工业大学 管理学院，天津 300387）

基于新型粒子群算法的散货港口装载机调度

李作志，王育静

（天津工业大学 管理学院，天津 300387）

以散货港口的装载机为主要研究对象，在考虑车辆的速度、任务位置和运送路径的基础上，建立以最短时间为目标的车辆调度模型，对装载车辆调度问题进行优化研究。在车辆调度优化方面，采用三维向量的编码方式在一种新型的粒子群算法下对模型进行求解，证明算法的有效性，并且利用一种浮动的目标函数得以使装载机的任务量均匀，以求得在实际运行中能帮助散货港口提高工作效率、降低企业总体成本。

散货港口；粒子群算法；装载机调度

1 前言

港口的组成包括进出港口的航道、锚泊设施、通信导航设施、装卸疏运设施、供应服务设施，其中货物装卸是港口最基本的功能，实现运输方式的转换，空间位置的有效转移，从而开始或完成水路运输的全过程。港口货物的装卸要利用港口装卸机械设备，主要包括：起重机（门座式、高架式、龙门式等）、装船机、装载机、汽车吊、轮胎吊、拖车、卡车、叉车等，其中装载机对于散货港口来说更是重中之重，港口管理者越来越认识到装载机调度的重要性，如何提高散货港口装载机的高效率和规范化作业，是一个亟待解决的问题。

目前国内外对港口车辆调度的研究大部分是利用遗传算法进行优化，在粒子群优化算法上的研究并不深入。对于求解车辆调度问题，张维存等人利用主—从级遗传算法建立以缩短顾客停留时间为目标的数学模型，研究了港口散货物流铲车调度的问题[1]；郝志莉等对港口物流中非满载车辆运输距离最短进行调度问题的研究，并利用遗传算法对模型进行求解[2]。在优化粒子群算法方面的研究，姜燕、刘长民等人利用主—从式的粒子群算法在水文模型上进行了参数的优化，并且提出了基于粒子群算法的主从群洗牌演化(MSSE—PSO)的新型算法，提高了计算精度和效率[3]；吴聪等针对标准粒子群优化算法存在的不足，提出一种改进粒子群算法(IPSO)的物流配送车辆调度优化方法，并给出仿真实验对其测试[4]；近期SabanGülcü,Halife Kodaz又提出了一种基于粒子群优化算法的并行算法（PCLPSO），通过对其他粒子群算法的比较测试，发现多个群的主—从式协同合作方式可以提高解决问题的质量和速度，对全局优化问题更加适用[5]。

综上所述，对粒子群算法的优化是许多学者一直在努力的方向，在港口车辆调度中多注重所有车辆的研究，用遗传算法求解也是按照传统的方式进行。通过本文的研究，以装载机为例建立可以实际运用到港口车辆调度的优化模型，并利用新型粒子群算法求解模型，通过加强对装载机的管理，以期提高港口散货物流的管理水平、运作效率和服务水平。

2 粒子群算法

2.1 标准粒子群算法

粒子群算法(Particle Swarm Optimization，简称PSO) 由Kennedy和Eberhart博士于1995年提出，基本概念源于对鸟群捕食行为的研究。群体在D维解空间上搜寻全局最优解，并且每个粒子都有一个适应函数值和速度来调整它自身的飞行方向以保证向食物的位置飞行，在飞行过程中，群体中所有的粒子都具有记忆的能力，能对自身位置、自身经历过的最佳位置（pbest）和种群中最好的粒子位置（gbest）学习，最终接近食物的位置。图1给出粒子速度和位置在第t代和第t+1代的调整示意图，全局最优解在处。

图1 粒子速度和位置调整示意图

图中：t—迭代的时刻；

t+1—下一迭代时刻；

v1—“社会经验”学习引起粒子向gbest方向飞行的速度；

v2—“自身经验”学习引起粒子向pbest方向飞行的速度；

v3—粒子自身具有的速度。

标准粒子群算法的数学描述，假设搜索空间为D维，种群规模为N，第i个微粒个体所处位置为Xi=(xi1,xi2,...,xid)，每个个体的飞行速度为Vi=(vi1,vi2,...,viD)，个体经历过的位置可定义为Si=(si1,si2,...,siD)，第i个粒子截至目前搜索到的最优位置为Pi=(pi1,pi2,...,piD)，整个粒子群迄今为止经过的最优位置为Pg=(pg1,pg2,...,pgD)。所以可以定义为，每个粒子的位置变化可以用如下公式进行表示：

式中：t—当前粒子进化代数；

w—惯性因子，非负数，是控制速度的权重；

c1、c2—加速系数；

r1、r2—介于［0,1］之间的随机数。

2.2 新型的粒子群算法

标准的粒子群算法虽然应用比较广泛，但是也存在一些缺陷，比较明显的有两点：其一，是收敛速度慢；其二，是容易陷入局部最优化。本文经过对该算法资料的大量收集与研究，对其进行了一定的改善，以达到满足实际车辆调度的应用。

基于种群互惠共生和共栖的思想，考虑到多群体协同进化，设计出一种新型粒子群算法模型，在该模型中利用一个主（master）—从（slave）式的结构来模拟共生群体之间的关系。整个种群被分为Z个子群（共生群体），其中Zm为主群（master swarm）数，Zs为从群（slave swarm）数，每个子群均包含相同的个体数，在搜索过程中各子群独立进化负责在解空间中全局广度搜索，而主群根据其共生群体（从群或其他主群）的经验负责局部精确搜索，共生群体间的信息传递，在一定程度上避免了个体信息误判造成的陷入局部最优的危险[6]。

根据不同的主、从群数设置，可以表示不同共生模式，本文以Zm∈[1,Z)，ZS=Z-Zm为例，即部分个体参与信息交流的共栖模式，来说明主-从式粒子群算法的计算原理。对种群进行分群后，每一个从群在迭代过程中利用标准的粒子群算法独立更新速度和位置，在状态更新之前把它们迄今为止发现的pbest发送给某一主群，此主群根据获得的所有pbest及其他主群中最好个体信息进行速度和位置的更新，更新方程如下：

式中：M—主群；

以上方程是一种协作型的主—从式粒子群算法，在这种更新机制中，主群中的每个粒子根据自己的经验，自身群体中其他粒子的经验，再加上从群中的最好经验进行速度和位置更新，通过多方考虑在一定程度上避免了陷入局部最优化。

3 装载机调度的数学模型

3.1 问题描述

经调查得知，港口车辆调度存在以下问题：调度基本处于人工方式，有很多不完善之处；车辆载货行驶至相应任务目标位置后空载返回；在实际港口装卸作业中，来港船只所装卸货物不可能正好是装卸车辆满载的整数倍，可能造成车辆非满载行驶的资源浪费。本文在以上问题的基础上，利用新型粒子群算法对港口装载车辆进行合理的调度，为每个任务选择最合适的装载车辆，为装载车辆选择最合适的行驶路线，以及满足车辆最佳的装载顺序，以达到充分的利用资源，提高效率节约成本的目的。

3.2 前提假设

（1）车辆调度刚开始时，所有的装载机都可使用，所处位置为车库；

（2）装载机完成一次任务后就停在任务目标位置，新任务的起始位置就是上一任务目标位置，所有任务完成后车辆返回车库；

（3）堆场和泊位的位置及相关信息已知；

（4）泊位卸船的货物优先级相同，无先后之分；

（5）每条路径均顺畅，不会产生交通堵塞和拥挤等情况。

3.3 数学模型

根据散货港口的实际情况，本文着重以在船舶装卸过程中每辆装载机行驶总时间T最小为目标对装载机进行调度，建立装载机调度的优化模型如下：

（1）决策变量：Pjkab，Qjkbc

（2）目标函数：

（3）约束条件：

（4）变量描述：j港口装载机编号(j=1,2,...,J)；k等待装卸的任务编号(k=1,2,...,K)；a装载机当前位置(a=1,2,...,A)；b需要装卸的任务位置(b=1,2,...,B)；c装卸任务的目标位置(c=1,2,...,C)；vj装载机j的速度，vj∈(0,45)；Pjkab第k个任务由第j辆装载机从当前位置a到任务位置b的距离；Qjkbc任务位置b到任务目标位置c的距离。

上述目标函数（5）表示任务过程中装卸车辆行驶的时间，包括两部分：一是第k个任务由第j辆装载机从当前位置a到达任务位置b所用时间；二是任务位置b到任务目标位置c所用时间。关于装载机、任务位置及任务目标位置的确定，是通过装载机的车载设备读取，当位置确定后它们之间的距离也就确定了。调度的目的是求这两部分行驶时间最短，每次迭代以用时最长的那辆装载机任务为目标函数，此时目标函数是变动的，即哪个装载机用时长就优化哪个，从而使任务整体的运输时间最优。

在上述约束条件中，式（6）表示对装载机的调度必须满足完成所有装卸任务；式（7）表示所有装卸任务之间的距离不小于零；式（8）表示装载机新任务的起始位置就是上一任务的目标位置；式（9）表示第j辆装载机所用时间与第j+1辆差的绝对值小于ξ，目的是让每个装载机的任务执行时间均衡。

4 装载机调度问题的算法实现

4.1 粒子的编码和解码

装载机调度问题模型建立以后，面临着两大问题需要解决，一是将装载机分配到装卸任务位置，二是各装载机与装卸任务的顺序安排。根据装载机调度问题的基本思路，提出了新型粒子群算法即主-从式的粒子群算法来求解该调度问题。假设装卸任务总数为K，装载机总数为J，构建一个粒子长度为K的三维粒子，其中第一维表示装卸任务；第二维表示装载机任务分配；第三维表示装载机作业顺序。三维粒子的表示方法见表1。

表1 三维粒子的编码

在上述三维粒子表示中，粒子位置向量xjk被限制在[1，J+ 1）的范围内，考虑实际情况对于装载任务k所对应的粒子位置向量xjk进行取整，即操作函数为INT（xjk），INT（xjk）∈[1,J]，可知，装载任务k就由装载机INT（xjk）来完成，这样就得到J辆装载机在各装载任务K上的分配方案，对于车辆j的作业顺序，解码时通过yjk的大小对同一装载机的任务按照编号进行粒子向量从小到大排序，从而确定装载机的作业顺序，通过以上解码可得到调度问题的一个解。由此可见，通过以上操作就可以在粒子位置与调度问题解之间建立映射关系，如图2、图3所示。

图2 粒子位置与装载机任务分配的映射更新关系

图3 粒子位置和装载机作业顺序的映射更新关系

从上述表示方法中，可以看出粒子位置与调度解的映射关系解码过程很简单，在实际应用中需要在算法的初始阶段对生成的初始方案进行判断，如果有不满足现实调度情况的粒子就重新初始化该粒子。

4.2 新型粒子群算法的伪代码

针对前面的新型粒子群算法[6]，利用MATLAB7.14 (R2012a)运行环境进行算法流程的编制，其中新型粒子群算法的伪代码如下：

5 实例仿真及分析

5.1 数据来源

为更好的验证新型粒子群算法的有效性和MATLAB编制程序的可行性，下面对散货港口中的装载机调度进行动态的仿真实验。粒子群算法的粒子数为20，为了更好的优化结果，在先前研究者的基础上，对初始参数进行设置：学习因子c1= c2=2.05，c3=2；惯性权重的设置是线性下降的，随着迭代次数的增加从0.9下降到0.4；实验中总子群数Z=4，即其中主群Zm=1，Zs=3，是共生群体的规模；最大迭代次数为200次。仿真对象为：4个装卸任务，3辆装载机，装载机在厂区行驶速度小于50km/h，每个任务的位置、任务的目标位置及装载机的位置和速度通过车载设备传输到港区的数据回传系统当中，采集数据获得信息，位置信息用坐标表示，港区在（100，100）范围内，图上1cm代表实际50m。在进行车辆的调度中，除了需要考虑装载机和任务的位置之外，还要考虑装载机在调度时是否在作业中，以及作业时间。以下表2、表3是仿真所需要提供的数据。

表2 港区装载机的行驶速度

表3 数据采集获得的相关数据

表中坐标位置已知，装载机车库的位置编号0坐标为（40，54），假设两个坐标分别为（a，b）和（c，d），可得两个位置的距离为：D= (a-c)2+(b-d)2。所有装卸任务和任务目标位置的平面分布如图4所示。

图4 装卸任务和目标位置的平面分布图（单位：cm）

5.2 结果分析

仿真实验中首先验证了新型粒子群算法比标准的粒子群算法的优越性，在同一台计算机上用同一MATLAB版本进行多次计算,发现新型的粒子群算法有着较快的收敛速度和求解精度，这一点从图5迭代200次的结果可以看出。而从计算结果还可知，最优车辆调度方案为：

装载机1：0→1→1’→0

装载机2：0→2→2’→3→3’→0

装载机3：0→4→4’→0

经过多次计算求得装载机调度问题的最优方案所用时间是0.76h，最优函数值随函数迭代次数变化的曲线如图5所示。从图5中可以明显看出，采用本文所提出的新型粒子群算法能够快速准确的求出三维粒子群编码的车辆调度问的最优方案，并且搜索到最优值的效率和准确度都优于标准粒子群算法，因此为求解港区装载机问题提供了一种新的方法。

Study on Loader Deployment in Bulk Harbors Based on Innovative PSO

Li Zuozhi,Wang Yujing
(School of Management,Tianjin Polytechnic University,Tianjin 300387,China)

In this paper,with the loading machines at the bulk harbors as the object,and on the basis of the consideration of the vehicle speed,task location and transport route,we built the vehicle dispatching model aiming at the shortest operation time,solved it using a newly developed PSO,which proved the validity of the algorithm,and at the end,used a floating objective function to spread out the task volume of the loading machines to improve the operational efficiency of the ports and reduce their overall costs.

bulk harbor;PSO;loading machine deployment

U653.923

A

1005-152X(2015)11-0130-04

10.3969/j.issn.1005-152X.2015.11.036

2015-09-28

李作志（1975-），男，天津人，天津工业大学管理学院副教授，主要研究方向：管理科学与工程、资源经济及管理；王育静（1991-），女，山东济南人，天津工业大学管理学院硕士研究生，主要研究方向：物流工程。