英语原文共 23 页
基于模拟退火的蚁群算法在拖轮调度优化中的应用
Qi Xu，1 Jun Mao，1，2 and Zhihong Jin1
（1大连海事大学 交通运输管理学院，辽宁 大连116026
2大连中铁国际集装箱有限公司，辽宁 大连116004）
拖轮作业系统作为整个港口物流系统中船舶的“第一服务站”，是港口物流中最重要的系统之一。本文在分析拖轮作业特点的基础上，将拖轮调度问题作为多处理机任务调度问题。该模型考虑了多种因素，多停泊基地、不同的作业模式和靠泊、移泊、离泊三个作业阶段。以港口所有拖轮的总作业时间最小化为目标，为了解决这一问题，提出了一种基于混合模拟退火的蚁群算法。通过无移泊作业的数值试验，验证了该方法的有效性，并指出拖轮及时返回锚地有可能实现更有效的航行；通过对移泊作业的实验可以看出，目标函数对移泊作业所占的比例最敏感，受拖轮配备情况影响较小，对装卸作业时间不敏感。
一、绪论
集装箱码头是国际物流的重要组成部分，在世界贸易中发挥着重要作用。最近，越来越多的人开始认识到通过集装箱码头进行全球物流业务的重要性。随着集装箱码头吞吐量的增加和港口间竞争的加剧，如何提高集装箱码头的效率成为港口管理者面临的一个重要而紧迫的挑战。集装箱码头最重要的性能指标之一是将各种设备安排在最佳水平，减少船舶周转时间。拖轮是集装箱码头的重要设备之一。
拖轮作业调度的性能直接影响船舶何时可以开始装卸作业以及何时可以离开港口。良好的拖轮作业调度可以降低港口船舶的周转时间。因此拖轮调度问题是港口物流领域需要解决的一个重要问题。
当船舶到达港口时，如果不能立即到达它们的目标泊位，必须在锚地等候。根据相应的规则，进入泊位时船舶需要一定数量的拖轮牵引。此外，在两个泊位之间的移动也需要拖轮牵引。为提高船舶运行效率，拖轮应安排在最佳水平。
根据上述分析，拖轮可以提供三种服务，将船舶拖至泊位，即靠泊；将船只从一个泊位拖至另一个泊位，即移泊；将船舶拖离泊位，即离泊。不是每艘船都会经历所有三种类型的服务，也就是说，移泊操作不是必需的，而停泊和离泊操作对于所有船舶都是必需的。
典型的拖轮操作流程如图1所示。从拖轮开始拖曳船舶到停泊作业结束的持续时间被视为阶段1，拖轮开始拖曳船舶离开第一泊位到该船舶进入第二目标泊位结束的持续时间被视为阶段2，从拖轮开始拖曳船舶到船舶离开港口的持续时间被视为阶段3。
实际上，拖轮调度根据船舶长度为其分配合适的拖轮。根据调度规则，每艘船可以同时有一艘或多艘拖轮为其服务。调度规则的主要思想是，大船应该由大拖轮提供服务，小船应该由小拖轮提供服务；如果有一艘以上相同马力的拖轮可用，可用拖轮之间的分配由一些启发式规则进行。
例如，根据马力单位，港口有六种拖轮，如1200 PS、2600 PS、3200 PS、3400 PS、4000 PS和5000 PS。分配的调度规则如下：
- S1（小于100米）：一艘1200 PS或以上的拖轮，
- S2（100–200米）：两艘2600 PS或以上的拖轮，
- S3（200–250米）：两艘3200 PS或以上的拖轮，
- S4（250–300米）：两艘3400 PS或以上的拖轮，
- S5（大于300米）：两艘4000 PS或以上的拖轮。
从现实世界实践中得出的启发式规则包括：
（1）最短距离拖轮作业原则（TSD）：从所有可用拖轮中挑选距离任务位置最近的拖轮为船舶提供助泊服务；
（2）首艘可用拖轮原则（FAT）：从可用拖轮中挑选最先空闲的拖轮进行作业；
（3）各拖轮任务量均匀原则UWAT：从平衡所有拖轮工作量的角度出发，选择目前工作量最小的拖轮为预定船舶服务。
根据混合流水车间理论，拖轮调度可以看作是一个三阶段多处理器任务调度问题。在调度系统中，拖轮被视为可移动的“机器”，船舶必须依次经历靠泊、移泊(如果存在这种操作)和离泊作业。另一方面，与典型的多处理器任务调度问题相比，拖轮调度问题有其自身的特点。首先，完全相同的拖轮可以提供所有三种类型的服务靠泊、移泊和离泊，这意味着所有三个阶段的机器设置是相同的。在多处理器任务调度问题中，每个阶段的可用机器组都不相同。此外，并不是所有的船舶都必须经历所有阶段，这使得问题不同于典型的多处理器任务调度问题。
总之，拖轮调度问题是一种非常规调度问题，是一个无法用精确方法解决的NP难问题，一些学者已经开始对这一课题进行研究。
Ying和Lin[1]提出了解决多处理器任务调度问题的蚁群算法。Xuan and Tang[2]探索了多处理器任务调度问题的复杂性，设计了一种结合启发式规则的拉格朗日松弛算法来求解多处理器任务调度问题。Liu[3]结合多处理器任务调度问题理论建立了拖轮调度问题的数学模型，并采用混合进化策略算法求解该模型。Liu[4]建立了考虑拖轮最小作业距离的拖轮调度模型，并将混合进化策略算法与粒子群优化算法的性能进行了比较。Wang和Meng[5]采用蚁群优化算法和遗传算法相结合的混合方法解决拖轮分配问题。Wang等人[6]结合现有的调度规则，建立了拖轮分配问题的混合整数模型，分析了拖轮数量和服务能力对船舶周转时间的影响。Liu和Wang[7]认为拖轮作业调度问题是一个具有特殊过程约束的并行机调度问题，并采用基于进化策略的混合算法来解决该问题。Dong等人[8]采用改进的粒子群优化算法结合动态遗传算子求解所建立的拖轮调度模型。Liu和Wang[9]利用粒子群优化算法结合局部搜索方法求解他们提出的拖轮调度模型。
从前面的研究可以看出，学者们已经开始使用多种方法来解决拖轮调度问题，包括遗传算法、蚁群优化算法和粒子群优化算法。然而，大多数文献只考虑了单个作业阶段和单个停泊基地的情况，忽略了拖轮和船舶位置信息对问题难度的影响。这使得模型的表述与现实相去甚远。因此，本文将研究考虑多停泊基地、不同作业模式和三个作业阶段的拖轮调度问题。
论文的其余部分如下：第二节结合多处理器任务调度问题理论，建立拖轮调度模型。第三节提出了一种基于模拟退火的蚁群算法求解该模型，第四节讨论了蚁群算法在集装箱码头的仿真实验。最后，我们在第5节中得出结论并对未来作出展望。
二、拖轮调度问题建模
2.1 假设条件
为表述问题引入以下假设：
（1）计划周期为一天。
（2）考虑靠泊、移泊和离泊三个作业阶段，但并非所有船舶都必须经历移泊作业。对于不需要经历第二次操作的船舶，假设存在虚拟移泊操作，并且该操作的操作时间为0。
（3）所有拖轮的准备时间为0，所有拖轮在0时到达停泊基地；所有要服务的船舶都在0点到达锚地。
（4）港口有三种类型的位置：船舶装卸货物的泊位、船舶在港口入口处与拖轮相遇的地点以及拖轮停泊基地。
（5）港口拖轮调度可采用限制交叉作业模式RCOM和非限制交叉作业模式UCOM两种作业模式。
（6）所有的船享有同样的优先权。
（7）在第一节中提到的拖轮与船舶的配比原则。
（8）所有拖轮的行驶速度相等。
（9）拖轮可根据调度计划，在完成计划期内所有作业后返回停泊基地。
在假设（5）中，RCOM表示所有停泊基地的拖轮在港口都有固定的服务区域，这意味着每个基地中的每个拖轮只能在其相应的服务区域内运行，而UCOM表示所有拖轮都可以在港口的整个区域内运行。
2.2 调度时段的定义
在制定拖轮调度模型之前，应该引入一个名为拖轮调度时段的概念。在实践中，拖轮调度时段用于定义从拖轮离开停泊基地到达其目标地点的时间到拖轮完成一定量的任务后返回基地的时间的持续时间。如图2所示，拖轮m必须执行三项任务，即计划范围内的a、b、c ，在完成任务a后，拖轮直接驶向任务b的起始地点，并在完成任务b后驶回停泊基地。该持续时间可定义为拖轮的第一轮调度，持续3.5小时。到达停泊基地后，拖轮一直待命，直到它驶到任务c的起点。完成任务c后，m又驶回基地。从m再次离开基地到它到达基地的持续时间是持续1.8小时即第二轮调度。根据定义，计划范围内的拖轮m有两轮调度，拖轮m的两轮调度总时长为3.5h 1.8h = 5.3 h。
2.3 符号
（1）相关参数
j，l ：阶段数，j，lisin;J{1，2，3 }，其中1–3代表靠泊、移泊和离泊；
i，k ：船舶编号；
cyi ：描述性二进制参数，船舶i是否将经历移泊作业，如果cyi =1，说明船舶i将经历移泊作业，否则将不会经历作业；
m ：拖轮编号；
M ：所有拖轮的集合；
tam：拖轮m的类型，可能为1–6，分别代表1200PS、2600PS、3200PS、3400PS、4000PS和5000PS；
N ：所有船舶的集合，N {1，2，...，n }；
Si ：船舶i的类型；
Seti ：可供服务于船舶i的拖轮类型集合；
Oij ：船舶i在第j个阶段的作业任务；
CMb：停泊基地b中的拖轮集合，b isin; B， B 是所有停泊基地的集合; 由此可知cup;bisin;B CMb=M；
Mijb：b停泊基地中可对任务Oij 进行作业的拖轮集合; 因此，可以为Oij任务服务的所有基地中的拖轮集合可以表示为 Mij =cup;bisin;B Mijb {m | tam =seti， forall;misin; CMb}；
Ejm ：由拖轮m提供第j阶段助泊作业的船舶集合 ；
LOSij：任务Oij 的起点位置，如果j= 1， LOSij为船舶进出港与拖轮的会合位置 ；如果j=2， LOSij为船舶装卸作业的第一个泊位；如果 j=3， LOSij 为船舶装卸作业的第二个泊位, 如果 cyi=0，则 LOSi3=LOSi2 ；
LOFij：任务Oij 的终点位置，如果j= 1，LOFij 为船舶装卸作业的第一个泊位; 如果j=2，LOFij为船舶装卸作业的第二个泊位，如果 cyi=0，则 LOFi2 =LOFi1; 如果j=3，LOFij 为船舶进出港与拖轮的会合位置；
ST(a，b)：拖轮在位置a和b之间的行驶时间；
pij：任务Oij的作业时间；
tbi：船舶从等待位置到靠泊位置的行驶时间，tbi=ST(LOSi1，LOFi2）；
tei：船舶i在码头的靠泊时间 ；
toai：船舶i在第一个泊位装卸货物的持续时间；
tobi：船舶i在第二个泊位装卸货物的持续时间（如果存在移泊作业）
tui：船舶i在码头的离泊时间；
tli：船舶i从离泊位置到离港位置的行驶时间；
smijkl：拖轮m直接从任务Oij终点位置驶向任务Okl起点位置之间的切换时间；
bpm：拖轮m所属的停泊基地；
H ：一个足够大的正数
（2）决策变量
（3）（3）取决于决策变量的状态变量
TSij：任务Oij的开始时刻；
TFij：任务Oij的完成时刻；
BTm：拖轮在计划时段内从停泊基地的出发时刻；
FTm：拖轮完成计划时段内最后一项任务后返回至停泊基地的时刻；
shmh：拖轮m在计划范围内的计划周期；
gm：拖轮m在计划范围内的计划周期数。
2.4模型
（1）目标函数
在本文中，目标是使拖轮总作业时间最小化，其可以等于所有拖轮的所有调度轮次的总持续时间。因此，我们必须推导出安排轮次的计算方法。
根据调度轮次的定义，决策变量wijm与计划范围
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
