本文为美国德克萨斯农工大学（作者：JIANGLEI QIN）的硕士论文，共44页。

在过去的十年里，无人驾驶车辆（UVs）在军事和民用领域得到了广泛的应用。无人车路径规划在有效利用现有资源（如无人车和传感器）方面发挥着重要作用。本文的主要目的是解决单辆无人车的两种路径规划问题。我们考虑的两个问题是配额问题和预算问题。在配额问题上，车辆必须访问足够数量的目标，以满足途中总奖励的配额要求。在预算问题中，车辆必须遵守无人车行驶距离的限制。我们使用一种实用的启发式方法（称为奖励乘子法）来解决这两个问题。该方法首先使用原始对偶算法将目标分配给无人车，然后应用Lin – Kernighan启发式（LKH）方法生成无人车指定目标的路线。我们在两种不同的车型上测试了这种方法。一种模型是简单的车辆，它可以在不限制转弯半径的情况下向任何方向移动。另一个模型是Reeds-Shepp车辆，我们还利用多商品流公式对C++中的两个问题进行了建模，并利用CPLEX技术解决了它们的优化问题。

Unmanned Vehicles (UVs) have beensignificantly utilized in military and civil applications over the last decade.Path-planning of UVs plays an important role in effectively using the availableresources such as the UVs and sensors as efficiently as possible. The mainpurpose of this thesis is to address two path planning problems involving asingle UV. The two problems we consider are the quota problem and the budgetproblem. In the quota problem, the vehicle has to visit a sufficient number oftargets to satisfy the quota requirement on the total prize collected in thetour. In the budget problem, the vehicle has to comply with a constraint of thedistance traveled by the UV. We solve both these problems using a practicalheuristic called the prize-multiplier approach. This approach first uses aprimal-dual algorithm to first assign the targets to the UV. The Lin –Kernighan Heuristic (LKH) is then applied to generate a tour of the assignedtargets for the UV. We tested this approach on two different vehicle models.One model is a simple vehicle which can move in any direction without aconstraint on its turning radius. The other model is a Reeds-Shepp vehicle. Wealso modeled both problems in C++ using the multi-commodity flow formulations,and solved them to optimality by using the Concert Technology of CPLEX.

1 引言

1.1 研究动机

1.2 问题描述

1.3 文献回顾

1.4 全文概述

2 问题建模

2.1 一般模型

2.2 配额问题建模

2.3 预算问题建模

3 启发式算法

3.1 实现启发式算法的一般思路

3.2 获奖树问题简介

3.3 配额问题的奖励乘子法

3.4 预算问题的奖励乘子法

4 仿真结果

4.1 配额和预算问题的输入数据

4.2 仿真结果与分析

5 结论与未来工作展望

更多精彩文章请关注公众号：