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

在移动性模式的变化中，我们提出了一种针对车辆共享问题的调度方法，考虑了几种替代性运输方式，从具有集中规划的公司角度来看。我们考虑在拥有一个或多个仓库和固定数量的用户（即员工）的公司中共享车辆共享。用户有固定位置和固定的开始和结束时间的约会。车辆必须用于从仓库到仓库的用户全面旅行。我们旨在将车辆分配给用户旅行，以便与其他运输方式相比最大化储蓄。我们首先考虑只使用一种类型的车辆，其次可以使用多种车辆类型。对于第一种情况，我们表明可以将车辆分离问题提出为最低成本问题。其次，如果有多种类型的车辆可用，则可以将问题提出为多商品流问题。这些配方使该问题适用于由于有效的解决方案方法而适用于日常操作。我们根据维也纳的人口，空间和经济数据为两种情况提供了全面的计算研究。我们表明，我们针对此问题的配方在几秒钟内解决了这些实例，这使它们在在线预订系统中可用。在分析中，我们讨论了不同的潜在环境。我们研究了共享车队的最佳组成，受限的运输方式以及目标函数的变化。

双目标多模式共享问题（BIO-MMCP）的目的是确定旅行的最佳运输分配方式，并安排可用汽车和用户的路线，同时最大程度地减少成本并最大程度地提高用户满意度。我们从以用户为中心的角度研究了生物MMCP。由于用户满意度是共享移动性系统中的关键方面，因此我们在第二个目标中考虑用户偏好。用户可以在一天中的不同时间选择并对其首选的运输方式进行排名。通过这种方式，我们可以解释整个计划范围内的不同交通状况。我们研究问题的不同变体。在基本问题中，用户必须实现的任务顺序是预先固定的，旅行时间以及偏好在计划范围上是恒定的。在变体2中，引入了与时间有关的旅行时间和偏好。在变体3中，我们在允许其他路由决策时检查了挑战。变体4集成了变体2和3。在最后一个变体中，我们开发了一种分支和切割算法，该算法嵌入了两个双向目标框架中，即$ \ epsilon $ -constraint方法和一种加权二进制搜索方法。计算实验表明，分支和切割算法的表现优于MIP公式，我们讨论了沿Pareto边境的更改解决方案。

在过去的几十年中，经典的车辆路由问题（VRP），即为车辆分配一组订单并规划他们的路线已经被密集研究。仅作为车辆的订单分配和他们的路线已经是一个NP完整的问题，因此在实践中的应用通常无法考虑在现实世界应用中应用的约束和限制，所谓的富VRP所谓的富VRP（RVRP）并且仅限于单一方面。在这项工作中，我们融入了主要的相关真实限制和要求。我们提出了一种两级策略和时间线窗口和暂停时间的时间线算法，并将遗传算法（GA）和蚁群优化（ACO）单独应用于问题以找到最佳解决方案。我们对四种不同问题实例的评估，针对四个最先进的算法表明，我们的方法在合理的时间内处理所有给定的约束。

列生成是一种用于解决各种优化问题的迭代方法。它将问题分解为两部分：主问题，以及一个或多个定价问题（PP）。该方法采取的总计计算时间在这两个部分之间划分。在路由或调度应用程序中，问题主要在网络上定义，并且PP通常是具有资源约束的NP-难以最短的路径问题。在这项工作中，我们提出了一种基于机器学习的新的启发式定价算法。通过利用先前执行期间收集的数据，目标是减小网络的大小并加速PP，仅保持具有高机会的弧形成为线性松弛解决方案的一部分。该方法已应用于两个特定问题：在公共交通中的车辆和船员调度问题以及时间窗口的车辆路由问题。可以获得高达40％的计算时间的减少。

In the last years, there has been a great interest in machine-learning-based heuristics for solving NP-hard combinatorial optimization problems. The developed methods have shown potential on many optimization problems. In this paper, we present a learned heuristic for the reoptimization of a problem after a minor change in its data. We focus on the case of the capacited vehicle routing problem with static clients (i.e., same client locations) and changed demands. Given the edges of an original solution, the goal is to predict and fix the ones that have a high chance of remaining in an optimal solution after a change of client demands. This partial prediction of the solution reduces the complexity of the problem and speeds up its resolution, while yielding a good quality solution. The proposed approach resulted in solutions with an optimality gap ranging from 0\% to 1.7\% on different benchmark instances within a reasonable computing time.

物流运营商最近提出了一项技术，可以帮助降低城市货运分销中的交通拥堵和运营成本，最近提出了移动包裹储物柜（MPLS）。鉴于他们能够在整个部署领域搬迁，因此他们具有提高客户可访问性和便利性的潜力。在这项研究中，我们制定了移动包裹储物柜问题（MPLP），这是位置路由问题（LRP）的特殊情况，该案例确定了整天MPL的最佳中途停留位置以及计划相应的交付路线。开发了基于混合Q学习网络的方法（HQM），以解决所得大问题实例的计算复杂性，同时逃脱了本地Optima。此外，HQM与全球和局部搜索机制集成在一起，以解决经典强化学习（RL）方法所面临的探索和剥削困境。我们检查了HQM在不同问题大小（最多200个节点）下的性能，并根据遗传算法（GA）进行了基准测试。我们的结果表明，HQM获得的平均奖励比GA高1.96倍，这表明HQM具有更好的优化能力。最后，我们确定有助于车队规模要求，旅行距离和服务延迟的关键因素。我们的发现概述了MPL的效率主要取决于时间窗口的长度和MPL中断的部署。

我们考虑了提高柱生成效率（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路线松弛可以显着提高定价的计算速度。

在本文中，我们研究了电子商务运营商面临的顺序决策问题，与何时从中央仓库发送车辆以服务于客户请求，并在哪个命令下提供服务，假设是在到达仓库的包裹是随机且动态的。目的是最大化在服务时间内可以交付的包裹数。我们提出了两种解决此问题的强化学习方法，一种基于策略函数近似（PFA），第二种基于值函数近似（VFA）。两种方法都与前景策略相结合，其中未来发布日期以蒙特卡洛的方式进行采样，并使用量身定制的批处理方法来近似未来状态的价值。我们的PFA和VFA很好地利用了基于分支机构的精确方法来提高决策质量。我们还建立了足够的条件，可以将最佳策略的部分表征并将其集成到PFA/VFA中。在基于720个基准实例的实证研究中，我们使用具有完美信息的上限进行了竞争分析，我们表明PFA和VFA的表现极大地超过了两种替代近视方法。总体而言，PFA提供最佳解决方案，而VFA（从两阶段随机优化模型中受益）在解决方案质量和计算时间之间取得了更好的权衡。

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

在带有电动车队的乘车系统中，充电是一个复杂的决策过程。大多数电动汽车（EV）出租车服务要求驾驶员做出利己主义决定，从而导致分散的临时充电策略。车辆之间通常缺乏或不共享移动性系统的当前状态，因此无法做出最佳的决定。大多数现有方法都不将时间，位置和持续时间结合到全面的控制算法中，也不适合实时操作。因此，我们提出了一种实时预测性充电方法，用于使用一个名为“闲置时间开发（ITX）”的单个操作员进行乘车服务，该方法预测了车辆闲置并利用这些时期来收获能量的时期。它依靠图形卷积网络和线性分配算法来设计最佳的车辆和充电站配对，以最大程度地提高利用的空闲时间。我们通过对纽约市现实世界数据集的广泛模拟研究评估了我们的方法。结果表明，就货币奖励功能而言，ITX的表现优于所有基线方法至少提高5％（相当于6,000个车辆操作的$ 70,000），该奖励奖励功能的建模旨在复制现实世界中乘车系统的盈利能力。此外，与基线方法相比，ITX可以将延迟至少减少4.68％，并且通常通过促进顾客在整个车队中更好地传播乘客的舒适度。我们的结果还表明，ITX使车辆能够在白天收获能量，稳定电池水平，并增加需求意外激增的弹性。最后，与表现最佳的基线策略相比，峰值负载减少了17.39％，这使网格操作员受益，并为更可持续的电网使用铺平了道路。

我们研究了大规模实时乘车系统的优化，并提出了一种模块化设计方法，用于乘车共享的组件算法（CAR）。我们评估了一套多种汽车（总共14辆），重点是乘车共享的关键算法组件。我们采用一种多目标方法，评估了与全球效率，复杂性，乘客，驾驶员和平台激励措施有关的12个指标，以在各个方面非常类似于现实，重点介绍了能力二的工具。据我们所知，这是迄今为止最大，最全面的评估。我们（i）确定在全球，乘客，驾驶员或平台指标上表现良好的汽车，（ii）证明，轻巧的搬迁计划可以显着提高服务质量高达$ 50 \％\％$，并且（iii）强调了一种实用的，一种实用的，在所有指标中都能很好地运行，可扩展的启动汽车。

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

我们研究了在国内捐助服务服务中引起的车辆路由问题的随机变体。我们考虑的问题结合了以下属性。就客户是随机的，但不仅限于预定义的集合，因此请求服务的客户是可变的，因为它们可能出现在给定的服务领域的任何地方。此外，需求量是随机的，并且在拜访客户时会观察到。目的是在满足车辆能力和时间限制的同时最大化预期的服务需求。我们将此问题称为VRP，具有高度可变的客户基础和随机需求（VRP-VCSD）。对于这个问题，我们首先提出了马尔可夫决策过程（MDP）的配方，该制定代表了一位决策者建立所有车辆路线的经典集中决策观点。虽然结果配方却很棘手，但它为我们提供了开发新的MDP公式的地面，我们称其为部分分散。在此公式中，动作空间被车辆分解。但是，由于我们执行相同的车辆特定政策，同时优化集体奖励，因此权力下放是不完整的。我们提出了几种策略，以减少与部分分散的配方相关的国家和行动空间的维度。这些产生了一个更容易解决的问题，我们通过加强学习来解决。特别是，我们开发了一种称为DECQN的Q学习算法，具有最先进的加速技术。我们进行了彻底的计算分析。结果表明，DECN的表现大大优于三个基准策略。此外，我们表明我们的方法可以与针对VRP-VCSD的特定情况开发的专业方法竞争，在该情况下，客户位置和预期需求是事先知道的。

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

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

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

在本文中，我们介绍了有关典型乘车共享系统中决策优化问题的强化学习方法的全面，深入的调查。涵盖了有关乘车匹配，车辆重新定位，乘车，路由和动态定价主题的论文。在过去的几年中，大多数文献都出现了，并且要继续解决一些核心挑战：模型复杂性，代理协调和多个杠杆的联合优化。因此，我们还引入了流行的数据集和开放式仿真环境，以促进进一步的研发。随后，我们讨论了有关该重要领域的强化学习研究的许多挑战和机会。

In this paper we deal with a complex real world scheduling problem closely related to the well-known Resource-Constrained Project Scheduling Problem (RCPSP). The problem concerns industrial test laboratories in which a large number of tests has to be performed by qualified personnel using specialised equipment, while respecting deadlines and other constraints. We present different constraint programming models and search strategies for this problem. Furthermore, we propose a Very Large Neighborhood Search approach based on our CP methods. Our models are evaluated using CP solvers and a MIP solver both on real-world test laboratory data and on a set of generated instances of different sizes based on the real-world data. Further, we compare the exact approaches with VLNS and a Simulated Annealing heuristic. We could find feasible solutions for all instances and several optimal solutions and we show that using VLNS we can improve upon the results of the other approaches.

随着优化软件的显着改进，几十年前似乎棘手的大规模问题的解决方案现在已成为日常任务。这将更多的现实应用程序纳入了优化器的范围。同时，解决优化问题通常是将解决方案付诸实践时较小的困难之一。一个主要的障碍是，可以将优化软件视为黑匣子，它可能会产生高质量的解决方案，但是当情况发生变化时，可以创建完全不同的解决方案，从而导致对优化解决方案的接受率低。这种可解释性和解释性的问题在其他领域（例如机器学习）引起了极大的关注，但在优化方面却不那么关注。在本文中，我们提出了一个优化框架，以得出本质上具有易于理解的解释性规则的解决方案，在哪些情况下应选择解决方案。我们专注于代表解释性规则的决策树，我们提出了整数编程公式以及一种启发式方法，以确保我们的方法即使在大规模问题上也适用。使用随机和现实世界数据的计算实验表明，固有的可解释性成本可能很小。