起重机调度—运筹学.doc

j 0 U；第三章 堆场龙门吊调度问题3.1 引言集装箱港口作为现代物流的一个重要环节，在全球物流系统和国际贸易中起着重要的作用。在港口堆场中，集装箱装卸操作都是由龙门吊完成，龙门吊在港口集装箱操作流程中起了至关重要的作用。假若没有一个合理的龙门吊作业调度计划，集卡可能会长时间的在堆场中等待，装卸桥也会因为集卡的不能到来而处于等待状态。这种等待会降低装卸桥的工作效率，从而导致整个港口的效率的降低，因此合理安排龙门吊的调度计划十分重要。在集装箱港口中，堆场被划分很多个箱区，每个箱区一般由 20 到 30 个贝位构成，每个贝位一般存放 4 层 6 排集装箱。堆场内的龙门吊主要分为轨道式和轮胎式两大类。受港口地质条件、设备投资、作业环境的影响，轮胎式龙门吊(Rubber Tire Gantry Crane，RTGC)是大多数集装箱码头堆场作业的首选设备在堆场内，龙门吊进行集装箱作业如图 3-1 所示。在集装箱进港作业时，龙门吊从集卡上卸载集装箱把它放在堆场合适的位置堆存；在集装箱出港作业时，龙门吊把堆垛的集装箱放在通道内的集卡上，集卡运送到岸边装卸桥处将其装船等待出港。图 3-1 龙门吊作业示意图 由于龙门吊是贵重设备，港口不可能为每个箱区都固定配置一定数量的龙门吊，并且由于堆场内各箱区作业量不平衡，因此龙门吊在作业过程中需要在箱区之间移动。图3-2 表示堆场箱区之间的龙门吊的移动。堆场箱区宽为 6 个标箱宽度加上 1 个集卡通道，约等于龙门吊的跨度。箱区长根据堆场的实际面积决定，通常为 30TEU 长度，堆垛高度由龙门吊的作业能力决定，一般为 4 层到 5 层。当龙门吊在两个箱区之间移动时，如果两个箱区相邻且共线，例如 1 箱区和 2 箱区，龙门吊不需要转弯，沿直线即可从一个箱区移到另一个箱区；如果两个箱区处于平行位置，例如 1 箱区和 3 箱区，龙门吊从一个箱区移到另一个箱区需要两次旋转 90 度，加之龙门吊体积大，动作缓慢，需要一定的作业时间和作业空间。图 3-2 龙门吊移动示意图3.2 问题描述3.2.1 龙门吊调度问题堆场内龙门吊的调度问题是根据集装箱堆场内不同龙门吊具有不同处理能力和它们在堆场内箱区之间移动需花费时间的特点，分配若干龙门吊去完成若干装卸任务，目标是使龙门吊完成所有装卸任务的用时最短，即确定一个任务分配和任务排序方案，使得在所有龙门吊中完成所分配装卸任务用时最长的龙门吊所花费的工作时间最小。我们假设一个箱区内所有需要处理的集装箱为一个“任务”，按照这些任务所在的箱区进行编号由于堆场内龙门吊比较分散，所以本文忽略因为几台龙门吊处于共线位置导致任务冲突所带来的等待时间。3.2.2 符号表示假设X 表示堆场内龙门吊的数量；t 表示堆场内龙门吊的序号，tB=1,2,，X；Y 表示堆场内任务的数量；j,k 表示了堆场内任务的序号。这些任务以它们所在箱区的序号递增的顺序排序，kU=1,2,Y，j 0 U；Zj表示第 j 个任务中包含的集装箱数量，j 0 U；M 表示总共需要装卸的集装箱数量；j 0 Udtjk表示第 t 台龙门吊从第 j 个任务到第 k 个任务的移动时间，即从第 j 个箱区到第k 个箱区的移动时间，其中 j 0 YU，kU，dtok 表示第 t 台龙门吊从起始位置到第 k 个箱区的移动时间，为了处理问题方便，假设每台龙门吊在处理完分配给它的最后一个任务需要回到其起始位置，dtjo 表示第 t 台龙门吊在完成分配给它的最后一项任务 j 后回到其起始位置。设dt00=0；Ctk 表示第 t 台龙门吊所服务第 k 个任务的服务时间，kU；Rtjk 决策变量，如果第 t 台龙门吊从第 j 个任务移动到第 k 个任务，则Rtjk =1，否则，R tjk=0，其中 j 0 U，kU。如果第 t 台龙门吊从起始位置到第 k 个箱区，R tok=1，否则Rtok=0。如果第 t 台龙门吊从第 j 个箱区回到起始位置，Rtjo =1，否则Rtjo =0。设Rt00 =0。3.2.3 模型的建立数学模型为：目标函数(3.1)表示所有龙门吊完成所有装卸任务时所用的时间最少，即求在所有龙门吊中完成所分配装卸任务并回到起始位置花费时间最长的龙门吊所用时间的最小值。完成一个任务所用时间包括龙门吊从上一个任务到目标任务的移动时间和龙门吊完成该任务的工作时间，即d tjk+Ctk ；约束条件(3.2)表示龙门吊装卸任务所包含的集装箱总数等于需要装卸的集装箱总数；约束条件(3.3)表示Rtjk 只能取 0 或 1；约束条件(3.4)表示对dtjk ，Ctk ，Rtjk 进行非负约束；约束条件(3.5)表示龙门吊必须完成所有的装卸任务；约束条件(3.6)表示一个箱区的装卸任务只能由一台龙门吊负责完成；约束条件(3.7)表示一台龙门吊一次只能移进一个箱区；约束条件(3.8)表示一台龙门吊一次只能从一个箱区移出。3.3.1 基本原理蚁群算法是一种通过信息素的逐渐积累和更新而逐渐收敛的路径优化算法。该算法有如下主要特点：1、正反馈机制，经过蚂蚁越多的路径，后续蚂蚁选择该路径的可能性就越大，通过信息素的不断更新最终收敛于最优路径上。2、分布式并行计算能力，算法在全局的多点同时进行解的搜索，具有本质上的并行性，易于并行实现。由于蚁群算法的以上特点，本章设计蚁群算法来对数学模型进行求解。3.3.2 单只蚂蚁行走路径的确定由于多台龙门吊调度问题的特殊性，需要由单只蚂蚁确定多台龙门吊的行走路径，所以需要蚂蚁在多台龙门吊之间相互跳跃。决定蚂蚁在哪一台龙门吊为其分配任务是由龙门吊完成当前所分配的所有任务的时间所决定的，即哪一台龙门吊完成当前所分配所有任务的时间最少，蚂蚁就可以跳到此龙门吊上，来决定这台龙门吊下一装卸任务。确定蚂蚁在哪一条龙门吊后，根据蚂蚁现在所在箱区和转移概率公式决定这一台龙门吊的下一个箱区。按照此规则不断进行，直到堆场所有装卸任务完成以后，从而得到一只蚂蚁确定的龙门吊调度方案。例如，假设有两台龙门吊，5 个箱区装卸任务。5 个箱区之间的移动时间如表 3-1所示，两台龙门吊完成装卸任务所需要的时间如表 3-2 所示设 T1 为龙门吊 1 完成当前所分配所有装卸任务所需要的时间，T2 为龙门吊 2 完成当前所分配所有装卸任务所需要的时间。开始时，蚂蚁随机分配在龙门吊 1 的箱区 1，T1=8，这时由于龙门吊 2 没有分配任务，所以 T2=0。由于 T1T2，所以蚂蚁分配到龙门吊 2 进行装卸任务调度。由于龙门吊 2 此时没有分配任务，所以随机分配任务 2，这是 T2=10。T1T2，所以蚂蚁分配到龙门吊2进行装卸任务调度。蚂蚁在箱区 2，按照以上规则决定龙门吊 2 移动的下一箱区。循环执行，直到所有的任务全部分配完成，这时得到一只蚂蚁确定的龙门吊调度方案3.3.3 路径选择概率初始时将蚂蚁k置于堆场初始位置，蚂蚁是依据一定的选择概率在各箱区间行进的。当蚂蚁k所在的第t台龙门吊在c时刻行进到箱区i时，根据蚁群算法思想，在集装箱箱区i向下一集装箱箱区j前进的选择概率为：其中tij 表示在第 t 台龙门吊在从集装箱箱区 i 到下一集装箱箱区 j 这条路径上的信息素；tij 表示第 t 台龙门吊从集装箱箱区 i 向下一集装箱箱区 j 的能见度，即tij =1/( dij+Ctj)；dij表示龙门吊从集装箱箱区 i 向下一集装箱箱区 j 的移动时间，此移动时间是由箱区之间的位置决定的，和龙门吊没有关系。Ctj 表示第 t 台龙门吊在箱区 j 的作业时间；allowed k表示第 k 只蚂蚁未访问过的集装箱箱区集合。m是蚂蚁的总数，tkij表示在第k只蚂蚁所确定的龙门吊行走策略中，第t台龙门吊在从集装箱箱区i到下一集装箱箱区j这条路径上留下的信息素。如果第t台龙门吊经过集装箱箱区i到下一集装箱箱区j这条路径，则tij =Q/Ltk 否则，tkij =0。其中Q为常数，Ltk是在第k只蚂蚁所确定的龙门吊行走策略中，第t台龙门吊完成所有分配的装卸任务并回到堆场起始位置的时间。以下给出蚁群算法的步骤，算法流程图如图3-4所示。第一步初始化参数。设置迭代次数counter=0,最优解best solution=极大数，设置最大迭代次数Ncmax，为信息素赋初始值，确定蚂蚁的数量m及其它参数。第二步将m只蚂蚁放在不同的箱区上。第三步每一只蚂蚁按照3.3.2的方法确定龙门吊调度方案。第四步所有的蚂蚁得到各自的调度方案以后，对得到的结果做局部寻优。如果局部解优于最优解，则最优解=局部解。第五步按照3.3.4信息素更新公式更新信息素。第六步counter+。如果counterNcmax，返回第二步；否则结束，输出结果。信息启发因子表示信息轨迹的重要性越大，该蚂蚁选择过的这条路径就越受其它蚂蚁欢迎，容易被其他蚂蚁选择；期望启发因子b 代表了启发信息在路径选择时的重要性；启发函数 ( )4.3 蚁群算法的参数选取M. Dorigo 等人最早开始对 a 、 b 、 r、 m等主要参数进行研究3，但目前还没有能够快速确定最佳参数组合的通用方法。目前用的最多的参数选取范围为：0 a 5;0 b 5;0.1 r 0.99;10 Q 10000，这些参数的确定都是以 Ant-Cycle为模型的。4.3.1 信息挥发因子当其他参数都一样时，信息挥发因子的选择对算法性能有很大的影响。在0.10.99 之间， r 越小，循环次数就越高，近似成反比；当 r 0.1时，迭代次数会迅速增大。原因是当r 较小时，边上堆积的信息量过多，会导致正反馈机制产生负面效应，收敛变慢；反之，当1 - r较小时，正反馈作用增强，最优路径得不到 “注意”。另外，当蚂蚁数目较少时，1 - r太大或太小，也会导致搜索的效率低下，所以1 - r的最佳取值和其他参数有关。4.3.2 蚂蚁数目蚂蚁能够完成一些高难度的任务，主要是因为蚂蚁个体之间相互协作、相互交流，内部组织高度有序。但是，蚂蚁过多却会适得其反，形成负面效应；而蚂蚁过少，有可能有的路径一直没被搜索到，解的稳定性不好。所以，蚂蚁数目的选取要恰当。M. Dorigo 针对如何选取适当的蚂蚁数目 m ，以 Ant-Cycle 为例，设计了一组试验，试验中主要参数分别取 Q = 50, a = 1, b = 4, r= 0.5，从试验的结果来看，当n是m 的 1.5 倍左右时，试验结果较好，其中n为城市个数464.3.3 启发因子启发因子是通过实验来确定的。其中，信息启发因子a 越大，说明路径上的信息素对蚂蚁下一步的选择影响就越大，正反馈将会很明显。在实验 Eil51TSP 中，采用 Ant-Cycle 为载体，其他参数分别为 m = 30,Q = 50, b = 4, r= 0.5，当相邻两次所找的最优解的差别小于1 1000时，循环结束，通过试验中a 和循环次数的关系，可以看出，a 选择的大小影响蚁群算法的表现，且当 a 1.0,4.0时，算法性能较好。而对期望启发因子b 来说，其值越大，较短路径对蚂蚁的吸引就越大，随机搜索减弱，搜索易集中在局部最优附近。在实验 Eil51TSP 中，仍采用相同的模型和停止条件，其他参数分别为 m = 30,Q = 150, a = 1, r= 0.5，从实验结果可以直观地看出当 3.0,4.5时，蚁群算法的综合求解性能较好。4.3.4 信息强度在 Ant-Cycle 中，全局信息得到充分的开发利用，蚂蚁遍历一圈后释放的信息总量为Q。Q越大，蚂蚁所选择过的那些路径上面的信息堆积就越迅速，提高了收敛速度。在 Eil51TSP 试验中，设置 m = 30,b = 5, 1, r= 0.5，仍采用同样的模型和停止条件，实验结果表明：当 Q 7000时，算法的整体性能较差。ijd 表示城市 i 与城市 j 之间的距离，对蚂蚁 k 而言，ijd 越小，则ij 越大，kijp 也就越大，很显然，该启发函数表示蚂蚁从元素(城市