摘 要

世界贸易的飞速发展促进了集装箱吞吐量的快速增长，也对港口装卸效率提出了更高的要求。高效的自动化码头逐渐受到青睐，但由于时间、空间资源的限制以及不确定因素的影响，AGV调度系统具有复杂的物流系统特性，合理优化调度系统可以提高装卸效率。本文在考虑了不确定因素影响下AGV迟到或早到等现象，研究AGV调度系统中的多车路径规划问题。

本文提出考虑AGV在运载集装箱和空载运行时两种不同的消耗成本，辅以迟到高惩罚、早到低惩罚的软时间窗元素，以AGV最小作业成本为目标，基于地图模型，采用模拟退火算法和改进A*算法为每个AGV规划无冲突的路径。为验证多AGV路径规划算法的可行性，通过采用编程语言，开发多AGV路径规划算法程序，模拟数据计算求解并对结果进行检验，验证了该算法的合理性。

关键词：AGV，A*算法，模拟退火算法，软时间窗

Abstract

The rapid development of world trade has promoted the rapid growth of container throughput and put forward higher requirements for port handling efficiency. Efficient automated terminals are gradually favored, but due to the limitations of time and space resources and uncertainties, the AGV dispatching system has complex logistics system characteristics, and reasonable optimization of the dispatching system can improve loading and unloading efficiency. In this paper, we consider the phenomenon of AGV late arrival or early arrival under the influence of uncertain factors, and study the multi-vehicle path planning problem in AGV dispatching system.

This paper proposes to consider the two different consumption costs of AGV in carrying containers and no-load operation, supplemented by soft time window elements with late high penalty and early to low penalty, aiming at the minimum operating cost of AGV, based on the map model, using simulated annealing. The algorithm and the improved A* algorithm plan a collision-free path for each AGV. In order to verify the feasibility of the multi-AGV path planning algorithm, the multi-AGV path planning algorithm program was developed by using programming language, the simulation data was solved and the result was tested, and the rationality of the algorithm was verified.

Keywords: AGV, A* algorithm, simulated annealing algorithm, soft time window

目录

摘要 I

Abstract II

第1章 绪论 1

1.1 研究背景及意义 1

1.2 国内外研究现状 1

1.2.1 国外研究现状 1

1.2.2 国内研究现状 1

1.2.3 研究现状小结 2

1.3 研究内容及方法 2

1.3.1 研究内容 2

1.3.2 研究方法 2

1.4 论文结构安排 3

第2章 问题描述及模型建立 5

2.1 问题描述及分析 5

2.2 模型建立 5

2.2.1 符号说明 7

2.2.2 模型建立 8

2.3 本章小结 9

第3章 算法设计 10

3.1 算法选择 10

3.2 算法步骤 12

3.2.1 路径规划算法 12

3.2.2 排序优化算法 13

3.3.3 算法配合 14

3.3 本章小结 15

第4章 模拟数据求解及结果分析 16

4.1 模拟任务数据 16

4.2 计算结果及分析 17

4.3 结果对比 18

4.4 经济性与环保性分析 18

4.5 本章小结 19

第5章 总结与展望 20

5.1 总结 20

5.2 展望 20

参考文献 21

致谢 23

第1章 绪论

1.1 研究背景及意义

随着贸易全球化规模进一步扩大和经济的快速稳步发展。单2019年1月份，全国完成的集装箱吞吐量已达2216万TEU。同时，作为能够有效提高港口作业效率的港口自动化正在全球范围内普及。作为自动化码头中最重要的一环，AGV作为主要的水平运输工具，承担着从岸桥到箱区的卸船运输作业、从箱区到岸桥的船舶装载运输作业以及从箱区到箱区的转场运输作业等任务，必然也伴随着较高的损耗和成本。

作为运行时自由度颇高的AGV，降低其运营成本自然比降低起重机等大型机械的运营成本来的更合理一些。但AGV在运行时作业环境较为复杂，具有高度的动态性、随机性和突发性等不确定因素，这些因素确定了AGV路径规划问题具有高度的复杂性。因此，想要追求在任务开始之前便通过算法规划出最优的AGV运行路线显得有些不合实际。但，如果能够通过不断更新的算法确保AGV在运行时所遵循的路线可以达到当前作业情况下的最小值自然是合理的。

降低AGV在作业过程中的总成本有助于港口减少运营成本、提高AGV装卸作业效率、实现从岸桥到箱区有限区域的最大化合理利用，进而有助于港口降低服务成本，提高市场竞争力。因此，研究AGV路径规划问题对降低自动化码头的运营成本具有一定的实际意义。

1.2 国内外研究现状

1.2.1 国外研究现状

国外针对港口AGV的路径研究起步较早，涉及方面也较为宽泛。如Errico等^[1]建立了基于硬时间窗并将在服务时间上加入随机函数，结合拓扑学内容采用分支法和隔平面法规划AGV的路径。Hamed等^[2]针对多AGV路径规划和调度问题，提出软时间窗的概念，通过分别建立提前期和延迟期的约束函数，将问题转化为求解最小惩罚函数的问题。Tatsushi等^[3]，针对多AGV路径规划问题中常见的碰撞问题，建立基于AGV移动延迟引起的AGV路径冲突的概率分布函数，并有效应用于动态运输环境下的仿真，可得到最理想情况下的AGV系统运行时间。车辆任务优先顺序在路径规划中也起到了不小的影响。因此对这方面的研究也有不少，如：Marinakis^[4]对粒子算法修改，使其在对求解离散优化问题有更好的效果，并通过实例确认该算法在求解带容量限制的选址与路径优化问题上具有很好的优秀度。

1.2.2 国内研究现状

国内对相关研究起步较晚，但随着自动化码头在国内港口物流的作用越来越明显，相关的研究正如火如荼。如：朱龙彪等人^[5]通过引入优先级概念，按照经验函数给与AGV路径规划顺序，最后在时间窗模型上进行初始解的排布优化，解决了最短时间无冲突AGV停车路径规划，并具有较好的鲁棒性和柔性。杨勇生等人^[6]在软时间窗的模型中遍历所有可行解，通过在可行解中进行比较得出最优解，模拟AGV的实时作业路径证明该算法的有效性，能够有效提高码头作业效率。徐镇华等人^[7]在离线规划AGV路径规划研究中加入时间窗模型，在线实时监控并改变AGV路径规划优先级，有效避免了AGV在运作过程中的碰撞。在相关的研究中吴艳群^[7]等人提出了一种改进模拟退火算法，在三种制约条件下：车辆最大载重量、车辆最大行驶距离具有较高的求解速度，寻路能力等特点。

1.2.3 研究现状小结

整体而言，国内外对多AGV路径规划已有不少研究，但主要集中在以总时间或总行驶路程最小为优化目标函数。但对于以最小成本为目标的研究较少，对AGV在不同工作模式下的区分也很少。

1.3 研究内容及方法

1.3.1 研究内容

本文主要研究内容为带软时间窗的多AGV路径规划。明确任务目标后，研究内容细分为以下几条：

（1）调查分析港口AGV实际工作流程和AGV工作场地；调查AGV到达岸桥时间窗为软时间窗限制下提前到达和延后到达产生的惩罚成本；调查AGV在不同的工作模式，如：平稳运行、加减速、空载和装载集装箱运输等不同运行模式下产生的损耗成本。

（2）分析AGV在进行装卸工作中产生的各项费用来源，结合上一步所做工作结果，建立以总成本为最低的AGV路径规划模型；

（3）研究在某个时间节点时，AGV运营的总成本最低，总成本包含软时间窗模型下的惩罚成本和AGV在行驶时产生的损耗成本。

（4）通过之前的调查总结数据规律，生成合理的数据模拟实际运作状况。

（5）将模拟数据带入模型求解并分析，与之前的路径规划算法相比较。验证模型确实有降低AGV运作时总成本的结论。

1.3.2 研究方法

在只考虑从船舶上卸载集装箱任务的情况下，单个AGV的运行模式框图如图1-1所示。

开始

系统是否安排后续任务

结束

N

Y

图1.1 AGV运行模式框图

而本模型为多AGV路径规划，在给AGV规划路线时，不仅需要安排一条较路程的路线，还要保证AGV在运行时不会发生碰撞的状况。综合考虑常用的路径规划算法，本文采用具有鲁棒性好、快速响应特点的A*算法作为给单个AGV路径规划的算法。

多AGV路径规划算法常使用两步骤的方式，先给AGV安排路径规划的顺序，再给单个AGV安排路径，本文选用模拟退火算法作为AGV任务顺序的优化算法。

车辆能否在顾客安排的时间窗之外进行服务即为区分软时间窗和硬时间窗的规则。但软时间窗模式下车辆在应许的时间窗外对客户进行服务仍需受到惩罚，距离应许的时间窗越远，受到的惩罚越大。因此，本文所建立的模型即为在AGV运行过程中给每一辆AGV规划出合理的路径使得总成本（总成本=固定成本 路径损耗成本 惩罚成本）最低。

为证明本模型具有实际意义，还需要通过数据模拟AGV运行时的任务，通过实例计算并证明本算法在减少总成本上具有一定的价值。

1.4 论文结构安排

本文主要针对自动化集装箱码头AGV调度系统进行研究，通过考虑在AGV运输过程中，可能受到不确定因素影响，而造成AGV迟到或早到的现象，提出考虑迟到、早到惩罚的以AGV最小作业成本为目标建立数学模型，改进设计模拟退火算法和A*算法对建立的非线性混合整数规划模型进行求解，并进行实例求解，对数学模型及算法进行验证。文章一共分为五个部分，每章内容如下：

第1章：绪论。介绍本文研究背景及意义、国内外研究现状，指出目前研究中存在的不足。阐述本文的主要研究内容、研究思路和各章节的主要内容。

第2章：问题描述及模型建立。首先对AGV调度问题进行分析，给出本文的具体研究背景，提出当前AGV任务调度中存在的问题，阐述研究AGV调度的必要性。在对问题分析的基础上，建立考虑AGV调度比确定因素影响的非线性混合整数规划模型，并说明所建模型中参数的含义及约束条件。

第3章：模型求解算法设计。根据所建立的调度模型，提出采用两阶段算法对模型进行求解。首先采用模拟退火算法优化AGV任务的排列顺序；然后采用A*算法按照优化结果的任务顺序，依次给AGV规划其行驶路径。

第4章：算例实验及结果分析。通过设计的案例，运用提出的改进算法对模型对进行求解。再对求解结果进行分析，验证本文建立的模型和提出算法的有效性。

第5章：总结与展望。总结本文的研究内容，找出研究中的不足，指出未来的研究方向。

第2章 问题描述及模型建立

2.1 问题描述及分析

自动化集装箱码头包括场桥、水平运输作业区域和堆场等区域。在只考虑卸船作业时，任取工作中的一个时间点，对单个AGV而言，其主要任务可以分为两类，一类为前往岸桥进行集装箱装载工作，一般对AGV的到达有着时间窗的要求；另一类为完成集装箱的装载后前往箱区进行卸载存放的任务，此时AGV为负载状态，应当适当给予路径规划上的优先度。在时间窗上的设定，一般为依据任务的先后顺序，确定AGV到达岸桥进行取箱的时间段要求，如果在规定的时间段之外AGV达到岸桥进行取箱作业，那么将会受到惩罚，用惩罚成本来度量，即软时间窗模型。另一方面，AGV在对集装箱装载模式下运行和空载模式下运行产生的损耗有着较大的区别，因此AGV的路径行驶成本需要分开计算。

对多个AGV进行路径规划时，AGV规划路径的顺序对最终规划有着较大的影响，在不考虑AGV停车等待的情况下，不合理的AGV路径规划顺序甚至会导致AGV相碰撞或无合理路径规划解。而一般不应考虑AGV停车等待状况，因为AGV运作场地已经充满了突发性和不确定性因素，停车等待往往会造成更大的堵塞情况，耽误整体AGV运输效率。常用的AGV路径规划常采用的是按照一种标准来判定AGV的优先级，再按照优先级给予AGV排序，但常常没有办法判定一个前往岸桥且已经晚点的AGV和一个承载集装箱前往箱区的优先度孰高孰低。因此应该采用较为成熟的排序算法如模拟退火算法对AGV任务进行优化排序，从而得到总成本（惩罚成本与路径成本之和）最低。

与传统码头不同，为了便于AGV的行驶，减少AGV的降速转向运动行为，要求AGV运行场地因地制宜地待用合理的装卸工艺。大部分自动化码头的布局方式为垂岸式布局，能有效缩短AGV加减速时间，提高AGV运行时的平均速度，从而降低AGV完成单项任务时间，提高AGV运行效率。

2.2 模型建立

本文所建立模型基于带软时间窗的路径规划问题（VRPSTW）的基础上，结合自动化码头路径安排特点和自动化码头作业特点，建立自动化码头AGV路径规划地图模型。在每个AGV与任务已被分配的条件下，根据码头承担船舶卸货状态中AGV所处周围位置及其被分配到的任务，优化求解得出给各任务对应AGV规划路线的最佳顺序，并给每一个AGV安排一条无碰撞路径，并使得最终规划路径结果为总成本最低路径。

本模型出现的场地区域有：海侧的岸桥装卸区、岸桥下车道、AGV高速行驶区、缓冲区和装卸AGV集装箱场桥所在路侧。其中岸桥为单小车岸桥，为减少AGV的碰撞情况发生，对道路做出单向行驶的设定。码头断面图如图2.1所示；所建立地图模型如图2.2所示。其中AGV行驶道路的方向如图中箭头所指方向。

其中具体假设条件如下：

1. 忽略岸桥、场桥等设备在物理因素上影响，忽略天气和人为因素等突发现象；
2. 地图上所有路线均为单向、单行道路。忽略非AGV车辆对路径规划的影响；
3. 采用节点模拟港口AGV运行路线上的引导磁钉；
4. 每一辆AGV有且仅有一项任务。
5. AGV行驶速度取平均值并保持匀速率行驶，不考虑突发情况。

图2.1 码头断面图

图2.2 地图模型

2.2.1 符号说明

1. 集合

：路径网络中所有节点的集合，用表示，；

：岸桥节点，；

：箱区节点，；

：目的地为岸桥节点的任务集合；

：目的地为箱区节点的任务集合

：任务集合，同时每一个任务都有且只有一个对应的AGV；

：初始任务队列，为一个有序队列；

：经过n次模拟退火算法迭代的任务队列，为一个有序队列；

：表示在对第辆AGV进行路径规划时，在时间节点，地图上节点的对应的AGV通过次数。

1. 权重因子

：AGV在规定的时间窗之前到达岸桥进行服务时对应的惩罚因子；

：AGV在规定的时间窗之后到达岸桥进行服务时对应的惩罚因子；

：前往箱区节点（B）的承载的AGV的行驶距离对应的权重因子；

：前往岸桥节点（Q）的空载的AGV的行驶距离对应的权重因子。

1. 参数

：时间节点

：节点到节点之间的距离

：AGV的行驶速度；

：任务对应的AGV到达岸桥的时间窗，；表示任务对应的AGV无惩罚成本到达岸桥并提供服务的最早时刻；表示任务对应的AGV无惩罚成本到达岸桥并提供服务的最晚时刻；

：AGV到达任务目的地的时刻；

：第k项任务对应AGV等待时间；

：第k项任务对应岸桥等待时间；

：退火算法中退火起始温度；

：退火算法中退火终止温度；

：退火算法中降温速度；

：退火算法中最大内迭代次数；

：退火算法中接收较差解的概率系数。

1. 决策变量

：表示在给第辆车进行路径规划时，如果在时刻t通过了节点i，那么为1，否则为0；

：表示如果第辆AGV依次通过节点和节点时，则为1，否则为0。

：表示当第辆AGV完成其对应的任务时，为1，否则为0；

2.2.2 模型建立

为解决自动化码头基于软时间窗的AGV路径规划问题，本文建立了如下的混合整数规划模型，式（2-1）为目标函数，包含两部分，第一部分为AGV的路径成本之和，包括前往岸桥和前往箱区的AGV的路径成本；第二部分为AGV在其任务对应的时间窗之外到达所产生的惩罚成本。

s.t.

式（2-2）和式（2-3）表示完成任务的AGV在同一节点上最多经过一次，防止AGV在地图上陷入局部循环，是车辆路径规划约束条件；式（2-4）表示每一个任务都被其对应的AGV所完成，即，所有的AGV都被按照顺序规划了一条路径。

在软时间窗模型中，在任务分配的时间之内进行服务可以免于惩罚，在任务分配的时间之外进行服务亦不至于拒收服务，但仍需要支出一定惩罚成本。如图2.3所示，横坐标为时间，纵坐标为需要支出的惩罚成本。在本文所建立的模型中，同为偏离时间窗到达岸桥，在较小时间范围内，提前到达受到的惩罚比延后到达受到的惩罚较小，但当偏离时间较大时，提前到达受到的惩罚较大，因其提前较长时间到达岸桥，却仍需等待岸桥工作，此时会延长AGV的等待时间，降低AGV的工作效率。如果想要减少岸桥对AGV的等待时间，只需要增大延后达到时的惩罚成本因子。由此可见软时间窗相较于硬时间窗具有更高的灵活性。当然，具体惩罚因子的值需要根据实际需求确定。