线覆盖范围是为环境中的一组一维功能提供服务的任务。这对于检查线性基础设施（例如道路网络，电力线以及石油和天然气管道）很重要。本文通过在图上将其建模为优化问题，解决了空中和地面机器人的单个机器人线覆盖率问题。该问题属于广泛的ARC路由问题，与不对称的农村邮政问题（RPP）密切相关。本文提供了一个整数线性编程公式，并提供了正确的证明。使用最低成本流问题，我们开发近似算法，并保证解决方案质量。这些保证还改善了不对称RPP的现有结果。主要算法将问题分为三种情况，以所需图的结构，即需要维修的特征诱导的图。我们在世界上50个人口最多的城市的道路网络上评估了我们的算法。该算法以改进的启发式增强，在3s内运行，并生成最佳最佳10％以内的解决方案。我们在UNC Charlotte校园路网络上通过商业无人机在实验中展示了我们的算法。

线覆盖范围的问题是找到有效的路由，以通过一个或多个资源约束的机器人覆盖线性特征。线性具有模型环境，例如道路网络，电力线以及石油和天然气管道。我们为机器人定义了两种旅行模式：维修和陷入困境。机器人服务功能如果它执行特定于任务的操作，例如拍摄图像，则它可以遍历该功能；否则，它是无人机的。穿越环境会产生成本（例如旅行时间）和对资源的需求（例如电池寿命）。维修和无人机的成本和需求功能可能具有不同的成本和需求功能，我们进一步允许它们取决于方向。我们将环境建模为图形，并提供整数线性程序。由于问题是NP-HARD，因此我们开发了一种快速有效的启发式算法，即合并 - 默认混合物（MEM）。该算法的建设性属性使得为大图求解了多depot版本。我们进一步扩展了MEM算法，以处理转弯成本和非语言限制。我们在50个道路网络的数据集上对算法进行基准测试，并在道路网络上使用空中机器人进行了实验中的算法。

区域覆盖范围问题是使用安装在机器人（例如无人驾驶汽车（UAV）（UAV）和无人接地车辆（UGV）等机器人上的传感器有效维修给定的二维表面的任务。我们提出了一种新颖的配方，用于生成多个容量受限机器人的覆盖路线，可以根据电池寿命或飞行时间指定容量。遍历环境对具有容量限制的机器人资源产生了需求。我们方法的主要方面是将区域覆盖问题转换为线覆盖范围问题（即线性特征的覆盖范围），然后生成途径，以最大程度地减少旅行的总成本，同时尊重容量约束。我们定义了两种旅行模式：（1）维修和（2）无人机，这与机器人是否执行特定于任务的操作相对应。我们的配方允许对两种模式的单独和不对称的旅行成本和需求。此外，从细胞分解计算出来的细胞，旨在最小化转弯的数量，不需要单调多边形。我们为细胞分解和生成服务轨道开发了新的程序，这些过程可以处理有或没有孔的非符号酮多边形。我们在具有25个室内环境的地面机器人数据集和一个具有300个室外环境的空中机器人数据集上建立了算法的功效。该算法生成的解决方案的成本比最新方法平均低10％。我们还证明了我们在无人机实验中的算法。

本文介绍了相关的弧定向问题（CAOP），其中的任务是找到机器人团队的路线，以最大程度地收集与环境中功能相关的奖励的收集。这些功能可以是一维或环境中的点，并且可以具有空间相关性，即访问环境中的功能可能会提供与相关功能相关的奖励的一部分。机器人在环境环境时会产生成本，并且路线的总成本受到资源限制（例如电池寿命或操作时间）的限制。由于环境通常很大，我们允许多个仓库在机器人必须启动和结束路线的地方。 CAOP概括了相关的定向问题（COP），其中奖励仅与点特征相关联以及ARC定向启动问题（AOP），其中奖励与无空间相关。我们制定了一个混合整数二次程序（MIQP），该程序正式化了问题并提供最佳的解决方案。但是，这个问题是NP-HARD，因此我们开发了一种有效的贪婪的建设性算法。我们用两种不同的应用说明了问题：甲烷气体泄漏检测和道路网络覆盖范围的信息路径计划。

我们研究了合作航空航天车辆路线应用程序的资源分配问题，其中多个无人驾驶汽车（UAV）电池容量有限和多个无人接地车辆（UGV），这也可以充当移动充电站，需要共同实现诸如持续监视一组要点之类的任务。由于无人机的电池能力有限，他们有时必须偏离任务才能与UGV进行集合并得到充电。每个UGV一次可以一次提供有限数量的无人机。与确定性多机器人计划的先前工作相反，我们考虑了无人机能源消耗的随机性所带来的挑战。我们有兴趣找到无人机的最佳充电时间表，从而最大程度地减少了旅行成本，并且在计划范围内没有任何无人机在计划范围内取消收费的可能性大于用户定义的公差。我们将此问题（{风险意识召集集合问题（RRRP））}作为整数线性程序（ILP），其中匹配的约束捕获资源可用性约束，而背包约束捕获了成功概率约束。我们提出了一种求解RRRP的双晶格近似算法。在一个持续监测任务的背景下，我们证明了我们的制定和算法的有效性。

我们介绍了多模式的汽车和乘车共享问题（MMCRP），其中使用一台汽车来涵盖一组乘车请求，同时将发现的请求分配给其他运输方式（MOT）。汽车的路线由一次或多个旅行组成。每次旅行都必须具有特定但不明的驱动程序，以仓库开始，然后以（可能不同的）仓库结束。即使两个骑行没有相同的起源和/或目的地，也允许在用户之间共享骑行。用户始终可以根据各个首选项列表使用其他运输方式。该问题可以作为车辆调度问题提出。为了解决该问题，构建了一个辅助图，在该图中，每次旅行在仓库中的启动和结尾，并覆盖可能的乘车共享，以时空图中的形式建模为弧。我们提出了一种基于列生成的两层分解算法，其中主问题可确保最多只能涵盖每个请求，并且定价问题通过在时间 - 时间中解决一种最短路径问题来生成新的有希望的路线空间网络。报告了基于现实实例的计算实验。基准实例基于奥地利维也纳的人口，空间和经济数据。我们通过在合理时间内基于列生成的方法来解决大型实例，并进一步研究了各种精确和启发式定价方案。

组合优化是运营研究和计算机科学领域的一个公认领域。直到最近，它的方法一直集中在孤立地解决问题实例，而忽略了它们通常源于实践中的相关数据分布。但是，近年来，人们对使用机器学习，尤其是图形神经网络（GNN）的兴趣激增，作为组合任务的关键构件，直接作为求解器或通过增强确切的求解器。GNN的电感偏差有效地编码了组合和关系输入，因为它们对排列和对输入稀疏性的意识的不变性。本文介绍了对这个新兴领域的最新主要进步的概念回顾，旨在优化和机器学习研究人员。

在本文中，我们研究了通过优化的流量路由的路径增加对运输网络的影响。特别是，我们研究了总旅行时间的行为，并考虑了自我利益的路由范式，例如用户平衡（UE）路由以及合作范式，例如经典多商品（MC）网络流量和系统最佳（因此）路由。我们提供了一个正式的框架，用于通过迭代路径添加设计运输网络，引入跨越树和跳跃路径图的概念。使用此形式化，我们证明了运输网络设计的目标函数的多个属性。由于基础路由问题是NP-HARD，因此我们研究了提供近似算法设计保证的属性。首先，尽管Braess的悖论表明，对于在自私路由（UE）下的路径添加（UE）方面，总旅行时间并不是单调的非侵扰，但我们证明，相反，单调性具有合作路由（MC等）。该结果具有重要的含义，即合作社可以充分利用冗余基础设施。其次，我们通过反例证证明，直观的语句``在传输网络中添加路径始终赋予用户更大或平等的好处，而不是将其添加到该网络的超集中'是错误的。换句话说，我们证明，对于所有研究的路由公式，相对于路径添加而言，总旅行时间不是超模型。尽管这种违反直觉结果为算法设计带来了硬度属性，但我们提供了特定的实例，而相反，超模型的属性则具有。我们关于相对于路径增加的总旅行时间的单调性和超模样的研究提供了正式的证明和场景，构成了运输网络设计师的重要见解。

Coverage path planning is a major application for mobile robots, which requires robots to move along a planned path to cover the entire map. For large-scale tasks, coverage path planning benefits greatly from multiple robots. In this paper, we describe Turn-minimizing Multirobot Spanning Tree Coverage Star(TMSTC*), an improved multirobot coverage path planning (mCPP) algorithm based on the MSTC*. Our algorithm partitions the map into minimum bricks as tree's branches and thereby transforms the problem into finding the maximum independent set of bipartite graph. We then connect bricks with greedy strategy to form a tree, aiming to reduce the number of turns of corresponding circumnavigating coverage path. Our experimental results show that our approach enables multiple robots to make fewer turns and thus complete terrain coverage tasks faster than other popular algorithms.

疏散计划是灾难管理的关键部分，其目标是将人员搬迁到安全和减少伤亡。每个疏散计划都有两个基本组件：路由和调度。但是，这两个组件与目标的联合优化，例如最大程度地减少平均疏散时间或疏散完成时间，这是一个计算问题上的问题。为了解决它，我们提出了MIP-LNS，这是一种可扩展的优化方法，将启发式搜索与数学优化结合在一起，并可以优化各种目标函数。我们使用来自德克萨斯州休斯敦的哈里斯县的现实世界道路网络和人口数据，并应用MIP-LNS来查找该地区的疏散路线和时间表。我们表明，在给定的时间限制内，我们提出的方法在平均疏散时间，疏散完成时间和解决方案的最佳保证方面找到了比现有方法更好的解决方案。我们在研究区域进行基于代理的疏散模拟，以证明解决方案的功效和鲁棒性。我们表明，即使撤离人员在一定程度上偏离了建议的时间表，我们的规定疏散计划仍然有效。我们还研究了疏散计划如何受到道路故障的影响。我们的结果表明，MIP-LN可以使用有关道路估计截止日期的信息，以成功，方便地撤离更多人，以提出更好的疏散计划。

Pearl's Do Colculus是一种完整的公理方法，可以从观察数据中学习可识别的因果效应。如果无法识别这种效果，则有必要在系统中执行经常昂贵的干预措施以学习因果效应。在这项工作中，我们考虑了设计干预措施以最低成本来确定所需效果的问题。首先，我们证明了这个问题是NP-HARD，随后提出了一种可以找到最佳解或对数因子近似值的算法。这是通过在我们的问题和最小击球设置问题之间建立联系来完成的。此外，我们提出了几种多项式启发式算法来解决问题的计算复杂性。尽管这些算法可能会偶然发现亚最佳解决方案，但我们的模拟表明它们在随机图上产生了小的遗憾。

近年来，在平衡（超级）图分配算法的设计和评估中取得了重大进展。我们调查了过去十年的实用算法的趋势，用于平衡（超级）图形分区以及未来的研究方向。我们的工作是对先前有关该主题的调查的更新。特别是，该调查还通过涵盖了超图形分区和流算法来扩展先前的调查，并额外关注并行算法。

In the Priority $k$-Center problem, the input consists of a metric space $(X,d)$, an integer $k$, and for each point $v \in X$ a priority radius $r(v)$. The goal is to choose $k$-centers $S \subseteq X$ to minimize $\max_{v \in X} \frac{1}{r(v)} d(v,S)$. If all $r(v)$'s are uniform, one obtains the $k$-Center problem. Plesn\'ik [Plesn\'ik, Disc. Appl. Math. 1987] introduced the Priority $k$-Center problem and gave a $2$-approximation algorithm matching the best possible algorithm for $k$-Center. We show how the problem is related to two different notions of fair clustering [Harris et al., NeurIPS 2018; Jung et al., FORC 2020]. Motivated by these developments we revisit the problem and, in our main technical contribution, develop a framework that yields constant factor approximation algorithms for Priority $k$-Center with outliers. Our framework extends to generalizations of Priority $k$-Center to matroid and knapsack constraints, and as a corollary, also yields algorithms with fairness guarantees in the lottery model of Harris et al [Harris et al, JMLR 2019].

重新配置图中的两个最短路径意味着通过一次改变一个顶点来修改一个最短的路径，使得所有中间路径也是最短路径。这个问题有几个自然应用，即：（a）改造道路网络，（b）在同步多处理设置中重新排出数据包，（c）运输集装箱存货问题，以及（d）列车编组问题。在作为图形问题的建模时，（a）是最常规的情况而（b），（c）和（d）是对不同图形类的限制。我们表明（a）是棘手的，即使对于问题的轻松变体也是如此。对于（b），（c）和（d），我们提出了有效的算法来解决各自的问题。我们还将问题概括为当最多$ k $（对于固定整数$ k \ geq k \ ge $ k \ geq 2 $）一次连续的顶点一次可以一次更改。

Despite recent progress on trajectory planning of multiple robots and path planning of a single tethered robot, planning of multiple tethered robots to reach their individual targets without entanglements remains a challenging problem. In this paper, we present a complete approach to address this problem. Firstly, we propose a multi-robot tether-aware representation of homotopy, using which we can efficiently evaluate the feasibility and safety of a potential path in terms of (1) the cable length required to reach a target following the path, and (2) the risk of entanglements with the cables of other robots. Then, the proposed representation is applied in a decentralized and online planning framework that includes a graph-based kinodynamic trajectory finder and an optimization-based trajectory refinement, to generate entanglement-free, collision-free and dynamically feasible trajectories. The efficiency of the proposed homotopy representation is compared against existing single and multiple tethered robot planning approaches. Simulations with up to 8 UAVs show the effectiveness of the approach in entanglement prevention and its real-time capabilities. Flight experiments using 3 tethered UAVs verify the practicality of the presented approach.

最近在组合问题中寻找多样化的解决方案，最近受到了相当大的关注（Baste等人2020; Fomin等人2020; Hanaka等。2021）。在本文中，我们研究了以下类型的问题：给出了整数$ k $，问题询问了$ k $解决方案，使得这些解决方案之间的成对和汉明距离的总和最大化。这种解决方案称为各种解决方案。我们介绍了一种用于查找加权定向图中的多样性最短$ ST $ -Paths的多项式时间算法。此外，我们研究了其他经典组合问题的多样化版本，如不同的加权麦芽碱，不同加权树丛和多样化的双链匹配。我们表明这些问题也可以在多项式时间内解决。为了评估我们寻找多样性最短$ ST $ ST -Paths的算法的实际表现，我们进行了合成和现实世界的计算实验。实验表明，我们的算法在合理的计算时间内成功计算了各种解决方案。

我们考虑了提高柱生成效率（CG）方法的方法，以解决车辆路由问题。我们介绍了CG配方中常用的NG-Route松弛度和降低状态空间松弛（DSSR）的替代/补充，我们引入了局部区域（LA）路线。 LA路线是NG路由的子集和基本路线的超级集合。通常，CG的定价阶段必须产生基本路线，这些路线是没有重复客户的路线，使用可能在计算上昂贵的流程。非元素路线至少访问至少一个客户，创建一个周期。 LA路线以允许有效定价的方式放松成为基本途径的约束。从NG-Route放松方面，最好理解LA路线。 NG路由是允许在空间中具有非定位循环的路线。这意味着周期中至少有一个中间客户（称为断路器）必须考虑到周期中的起始客户在空间上远离。使用一组特殊索引来描述LA路线，该特殊索引与从开始到路线尽头的路线上的客户相对应。 LA路线的松弛进一步限制了一组允许的周期，除了强制执行断路器必须位于特殊索引中，该循环均超出了NG路由，其中​​一组特殊索引被递归地定义为如下。该路线中的第一个特殊索引是索引1，这意味着它与路线中的第一个客户关联。 K'th特殊索引对应于K-1第三个特殊索引之后的第一个客户，该索引并非被认为是（在空间上被认为是远离K-1'TEXPATEX的客户）的邻居。我们证明，与标准DSSR相比，LA路线松弛可以显着提高定价的计算速度。

Graph clustering is a fundamental problem in unsupervised learning, with numerous applications in computer science and in analysing real-world data. In many real-world applications, we find that the clusters have a significant high-level structure. This is often overlooked in the design and analysis of graph clustering algorithms which make strong simplifying assumptions about the structure of the graph. This thesis addresses the natural question of whether the structure of clusters can be learned efficiently and describes four new algorithmic results for learning such structure in graphs and hypergraphs. All of the presented theoretical results are extensively evaluated on both synthetic and real-word datasets of different domains, including image classification and segmentation, migration networks, co-authorship networks, and natural language processing. These experimental results demonstrate that the newly developed algorithms are practical, effective, and immediately applicable for learning the structure of clusters in real-world data.

无人驾驶飞机（UAV）是飞机，其飞行可以完全自主，而无需任何人为干预。自然灾害管理是可以使用无人机的最有用和最有前途的领域之一。在本文中，我们专注于紧急情况，并提出使用无人机机队，以帮助营救团队个性化受影响区域内需要帮助的人。我们将这种情况建模为原始图理论问题，称为多部门多行车路由问题，总完成时间最小化（MDMT-VRP-TCT）；我们经历了一些与之相似的文献研究中已经研究的问题，并突出了差异，提出了作为MILP作为MILP的数学表述，设计了一种数学框架来快速解决大型实例，并在实验中测试其性能。除了提出的应用程序之外，我们的解决方案在任何情况下都必须解决多部多行车路由问题的任何情况。

本文介绍了经典懒惰的概率路线图算法（Lazy PRM）的修订，该算法是由配对PRM和一种新颖的分支和切割（BC）算法产生的。切割是动态生成的约束，这些约束在PRM选择的几何图上施加的最低成本路径。削减消除无法映射到满足适当定义运动学约束的平滑计划中的路径。我们通过在最低成本路径中将花键拟合到顶点来生成候选平滑计划。使用最近提出的算法对计划进行了验证，该算法将它们映射到有限的痕迹中，而无需选择固定的离散步骤。痕量元素准确地描述了计划交叉约束边界何时模拟算术精度。我们使用我们最近提出的谷仓基准的方法评估了几个计划者，我们报告了方法可扩展性的证据。