图2 基于曲线型软时间窗的惩罚成本函数

式（6）表示在曲线型软时间窗的约束下，AGVm执行完任务i的时刻tim所对应的惩罚成本。如图2所示，若AGVm在t'a时刻之前送达，单位时间所需承担的惩罚成本为cp1，同时还需要承担[t'a,ta]时间段所产生的惩罚成本；若AGVm在[t'a,ta]时间段内送达，单位时间所需承担的惩罚成本为cp2；若AGVm在[ta,tb]时间段内送达，惩罚成本为0；若AGVm在[tb,t'b]时间段内送达，单位时间所需承担的惩罚成本为cp3；若AGVm在t'b时刻以后送达，对应的单位时间所需承担的惩罚成本为cp4，同时还需承担[tb,t'b]时间段所产生的惩罚成本。
式中，α和β为提前送达和延迟送达的成本惩罚权重，分别取值为0.1和0.8[12]。

1.4约束条件

其中，式（7）表示任何时刻一台堆垛机只能被分配一个任务；式（8）表示任意时刻同一任务只能被分配给一个加工工位；式（9）表示两台相位相冲突的AGV不能同时通过路口；式（10）表示每个任务在同一时刻只能由一台AGV执行；式（(1)表示每个任务在任意时刻只能分配给一个堆垛机；式（12）表示机械手开始处理的时刻不得早于AGV将物料送达机械手所在交接点的时刻：式（13）表示任务被完成的时刻；式（14）表示只有在堆垛机将物料卸载在交接点后，AGV才能开始执行任务；式（巧）表示每台AGV待执行的任务需依次排序执行：式（16）表示参数的非负限制。

2.AGV路口避碰规则

路口碰撞可分为相向冲突、路口冲突和节点占用冲突三种[13]。传统路口避碰为题大多赋予AGV不同级别的优先级，按优先级高低依次通过，单次只能通过一辆AGV[13]。本文研宄中，为使AGV避碰环节更贴近实际，AGV在行驶过程中经过某交叉路口时，根据传感器和RFID采集的数据，分析当前路口的通行情况和路口AGV行驶信息，通过检测每辆AGV的行驶方向，判断多辆AGV的是否可同时通行，并对相冲突的AGV进行优先级调整，使路口可同时通行多辆AGV，有效减少等待时间和碰撞情况的产生。

2.1 AGV冲突类型检测

AGV行驶临近交叉路口时，根据传感器和RFID采集的数据，控制系统对AGV位置和时间状态进行更新，检测并分析在即将驶入的路口是否会发生冲突及其冲突类型。
检测中参数定义如下：
1)λbm为表示AGVm到达节点h的时间；
2）εhm为表示AGVm在节点h的停留时间；
3）θ为表示冲突检测时的安全时间间隔阈值；
4）Kmh为节点h的识别码，且该节点在AGVm的规划行驶路径中；
5）Kmh-1<Kmh<Kmh+1为AGVm通过的节点顺序。
冲突检测模型如下：
1）相向冲突
若检测过程中满足以下关系式(17)、式(18)、式(19)，则AGV在路口将发生相向冲突。

2）路口冲突
若检测过程中满足以下关系式（20）和式（21），则AGV在下一路凵将发生路口冲突。

3）节点占用
若检测过程中满足以下关系式（22）和式（23），则AGV在下一路口将发生节点冲突。

2.2 路口冲突AGV的优先级动态调整

如图3所示，AGVm行驶至交叉路口时，每辆AGVm均有gs、tl、tr三种行驶方向的可能性，分别代表直行、左转、直行，在路口设置互容和不容两种通行相位，处于互容相位的多辆AGV可在不碰撞的情况下同时通过，处于不容相位的多辆AGV不能同时通过路口，（假设路口的转弯半径可同时容纳两辆互容相位的AGV同时通过）。比如AGVtrm1则表示AGVm1在路口右转，则与AGVtlm2、AGVtrm2、AGVtrm3、AGVgsm2、AGVtrm4、AGVgsm4是互容相位，可同时通过路口，与AGVgsm2、AGVtlm3、AGVtlm4是不容相位，不可同时通过路口，其通过路口顺序需根据优先级调整确定。

图3 AGV在路口的冲突相位图

在交叉路口处于不容相位的AGV，为保证各AGV之间有明确的优先关系，通过赋予AGV优先级来确定通路口的先后顺序，其依据是根据理论上AGV完成正在执行任务的剩余时间，值越小，则AGV优先级越大，不同的优先级以增幅A来确定，若是空载车辆，优先级则设为最低。
其中：

式中，rest（Ti)表示任务i的剩余完工时间；Number(k)表示当前路口排队不容相位排队通行的车辆数。

2.3 双路囗路径容量检测

为减少双路口之间路径的堵塞现象，当AGV即将抵达双路口路径时，在检测交叉路口冲突情况的同时，检测双路口之间路径堵塞情况，评估当前是否可以进入该路径而不造成堵塞，如图4所示，评估标准为路径剩余可容纳的车辆数：
N(s)=F[ s ]-Y(s)       (25)

图4 双路口路径容量检测示意图

式中，N（s）为路径s的剩余可容纳的车辆数；F（s）为路径可容纳车辆的额定容量，取值向下取整；Y(s)为路径s中己进入的车辆数；ls为路径s的长度；
lAGVm为AGVm的长度，θ为行车过程中的最小安全距离。
当N（s）＜1时，将禁止AGV通过交叉路口，等待直至有AGV从路径驶出。

3 粒子群算法

PSO是Kennedy和Eberhart受鸟群群体运动的启发于1995年提出的一种新的群智能优化算法[14]，通过粒子间的信息共享，协作完成寻优任务，具有记忆性强、效率
高和搜索速度快等特点，但易陷入局部最优，即局部寻优能力强，全局寻优能力弱[15]。本文对粒子群算法进行优化，采用动态惯性权重和引入遗传算法中的自适应变异概率，避免算法后期陷入局部最优，提升算法的收敛能力和收敛精度，算法流程如图5所示。

图5优化自适应粒子群算法流程图

3.1 PSO算式

设求解模型的维度为D维，有1个粒子，粒子群为L={p1,p2,…,pi,…,pl}速度表示为V={v1,v2,…,vi,…,vD}，位置表示为X={x1,x2,…,xi,…,xD}，pbesti表示粒子i经过的最佳位置，gbesti表示所有粒子经历过的最佳位置。PSO算法的粒子i的第D维速度更新公式为式(27)，粒子i的第D维位置公式为式(28)：

式中，vkid表示粒子i进行第k次迭代时速度矢量的第D维分量；vkid表示粒子i进行第k次迭代时位置矢量的第D维分量；c1，c2表示学习因子加速度，其值为常数；r1，r2为取值范围为[0,1]的两个随机参数；w表示惯性权重，取值非负，用来调节对解空间的搜素范围。
惯性权重表示粒子i的先前速度对当前速度的影响。全局寻优能力与其值成正比，局部寻优能力与其值成反比；反之，粒子局部寻优能力强，全局寻优能力弱。即，值过大，则容易错过最优解；值过小，则算法收敛速度慢或是容易陷入局部最优解。当问题空间较大时，为了在搜素速度和搜索精度之间达到平衡，故本文采用动态惯性权重式(29)，使算法在迭代初期有较高的全局搜索能力以得到合适的种子，而在后期有较高的局部搜索能力以提高收敛精度，随着迭代次数地增加，w不断减小，进而使算法在初期有较强的全局收敛能力，而后期有较强的局部收敛能力。