1.1. 什么是OptaPlanner?

每个组织都面临着规划问题：我们要用有限的有限资源（例如员工、资产、时间和金钱）提供产品或服务。OptaPlanner为规划问题提供优化方案，用更少的资源做更多的事。这被称为约束求解编程（这是运筹学的一部分）。

OptaPlanner 是一个轻量级的、可嵌入的约束求解引擎，用于优化规划问题。它能解决的问题包括：

• 员工排班表：护士、修理工等

• 日程安排：安排会议、预约、维护工作、广告宣传等

• 教育时间表：安排课程、课程、考试、会议演示等

• 车辆路线：规划车辆路线（卡车、火车、船只、飞机等），使用已知的地图工具在多个目的地运送货物及乘客。

• 装箱问题：用物品填充集装箱、卡车、船舶和存储仓库，同样可以规划虚拟资源，如规划如何高效利用云计算资源

• 车间调度：汽车装配线规划、机器队列规划、劳动力任务规划等

• 物品切割：切割纸张、钢材、地毯等物品时减少浪费

• 运动日程安排：为足球联赛、棒球联赛等规划比赛和训练日程

• 财务优化：投资组合优化、风险分散等

image.png

1.2. 什么是规划问题?

image.png

规划问题有一个基于有限资源和特定约束条件的最优目标，这个目标可以包含很多东西，比如：

• 最大化利润 - 最优目标需要将利润最大化

• 最小化生态足迹 - 最优目标需要对环境的影响最小

• 员工或客户满意度最大化 - 最有目标优先考虑员工或客户的需求

实现这些目标的能力取决于可用资源的数量，例如：

• 可用人数

• 可用时间

• 可用预算

• 物理资产，例如机器、车辆、计算机、建筑等等

除数量外，我们还必须考虑与这些资源有关的具体限制，例如一个人工作时长，他们使用某些机器的能力，设备之间的兼容性等等。

从底层上，OptaPlanner将优化启发式和元启发式算法与高效的分数计算加以结合，可以帮助Java™程序员高效地解决约束求解问题。

1.2.1. 规划问题是NP-C问题或NP-H问题

上诉所有问题，都可能是 NP-complete/NP-hard问题（以下简称NP-C/NP-H），这用外行人的话说就是：

• 在合理的时间内验证一个解是否能满足问题的需求，是可行的。

• 要在合理的时间内找到问题的最优解，是不可能的 (*)。

(*) 至少，世界上最聪明的计算机科学家还没有找到这样的通用解。如果人类可以找到NP-C问题中的任意一个解，那么这个解将成为所有NP-C问题的通解。

国外有人发起了一个价值100万美元的悬赏，如果有人能够证明这样的通用解存在或者不存在，就可以拿走这份奖金。

所以规划问题其实非常复杂，想要解决一个规划问题所耗的时间比你想象中的要长很多，因为我们经常用的两套方案对于NP-C/NP-H问题是不够的：

• 暴力算法（即使是更聪明的暴力算法）也会花费巨量的时间。

• 一个快速算法，例如在装箱时，先放入最大的物品 ，将返回一个远不是最优的解决方案。

通过使用先进的优化算法，OptaPlanner确实在合理的时间内找到了此类规划问题的近似最优解。

1.2.2.规划问题有硬约束和软约束

通常，一个规划问题至少有两层约束：

• （负面）硬约束是无能如何都不能打破的负面约束。例如：一名教师不能在同一时间上两堂不同的课。

• （负面）软约束是可以被打破，但是需要尽量避免打破的负面约束。例如：教师A不想在星期五下午上课。

除了负面约束之外，一些问题同样有正面约束：

• 如果可能的话，正面软约束是需要尽量去满足的。例如：教师B想在星期一的早上上课。

一些基本问题（如N皇后问题）只有硬约束。有些问题有三个或更多层次的约束，例如硬约束、中约束和软约束。

这些约束决定了规划问题的分数计算 方法（又名 适配度函数 ），规划问题的每个解都可以用一个分数进行评分。使用OptaPlanner，计分约束是用面向对象的语言编写的，例如Java™ 代码。这样的代码简单、灵活和可扩展。

1.2.3. 规划问题具有巨大的搜索空间

一个规划问题有许多解决方案，以下是解决方案的分类：

• 任何解都是可能解，无论这个解是否打破了多少约束，它都是可能的。规划问题往往有大量的可能解，大部分可能解都毫无价值。

• 不打破任何硬负面约束的解就是可行解，可行解的数量往往与可能解的数量相关，有些问题找不到可行解，每一个可行解都是一个可能解。

• 分数最高的解，就是最优解，规划问题往往只有一个或几个最优解，而且总会至少有一个最优解，即使在没有可行解且最优解不可行的情况下，也总是有分最高的一个解。

• 在给定时间内找到的分数最高的解即最佳解决方案。找到的最佳解决方案是很容易的，如果有足够的时间，最佳解决方案就是最优解。

如果计算正确，可能解的数量是极其庞大的，这非常的反直觉。即使是一个例子中提到的小数据集，大多数情况下，可能解也比已知宇宙中的原子数量(10^80)还要多得多。我们没有找到最佳解决方案的灵丹妙药，所以任何解决规范问题的方案都只能做到验证有限的一部分可行解来求相对最优解。

OptaPlanner支持多种优化算法，可以有效地处理大量可能解。根据场景的不同，有些优化算法会比其他算法表现得更好，但这是不可能提前预知的。使用OptaPlanner时，我们可以通过在几行XML或代码中更改求解器配置，来轻松切换优化算法。

1.3. 运行需求

OptaPlanner是一个开源软件，基于 Apache License 2.0。这个许可非常自由，允许商业使用。参考the layman’s explanation.

OptaPlanner是100%纯Java编写的，运行于Java 11或更高版本上。它很容易与其他java技术集成，OptaPlanner可在Maven中央存储库中找到。

OptaPlanner适用于任何Java虚拟机，并与主要的JVM语言和所有主要平台兼容。

image.png

1.4. 项目治理

1.4.1. OptaPlanner现状

OptaPlanner稳定、可靠、可扩展。它已经通过大量的单元、集成和压力测试，并在世界各地的生产环境中使用。在某些用例中，OptaPlanner可以处理超过50000个变量，每个变量有5000个值，多种约束类型和数十亿个可能的约束匹配。

有关这个项目的一些近况，请参阅发布说明。

1.4.2. 向后兼容性

OptaPlanner的API和实现是分开：

• 公共 API：所有位于org.optaplanner.core.api, org.optaplanner.benchmark.api, org.optaplanner.test.api和 org.optaplanner.persistence…api包下的类，在未来的版本更新中是100% 向后兼容的（特别是小版本发布和热修复版本）。在极少数情况下，在大版本更新中，一些特定的类可能会有一些向后不兼容的更改，这些更改将清楚地记录在升级建议中。

• XML配置：求解器XML配置的所有元素都是向后兼容的，除非你需要用到一些非公共API类。求解器XML配置位于org.optaplanner.core.config和 org.optaplanner.benchmark.config 包下

• 实现类：除API和配置外，其他所有其他类都不向后兼容，大版本和小版本的发布都可能导致实现类的该冻（热修复版本可能不会做更改）。每有此类修改时，都可以在升级建议找到此类相关更改记录以及升级到新版本时如何快速处理。

本文档同样涵盖了一些实现类，使用本文中记录的实现类一般是安全可靠的（除非在本文档中明确说明了是实验性质的），但是我们不能保证这些类的使用未来会100%保持一致。

1.4.3. 社区及技术支持

有关新闻和文章，请查看我们的博客， twitter(包括Geoffrey的twitter)和facebook。

如果你对OptaPlanner满意，发布tweet或博客文章我们将非常高兴。

欢迎在这里提出公众问题，同样环境在我们的问题追踪器中提bug和功能请求。非常欢迎你在GitHub上提Pull请求，我们优先处理。你开源你的改进代码，获取同行评审们的认可，开源项目可以基于你的提交进行改进。

Red Hat通过雇佣本项目核心团队的形式来资助OptaPlanner开发，如需企业支持和咨询，请查看这些服务。

1.4.4. 与KIE的关系

OptaPlanner是KIE项目组的一部分。它定期发布(通常每3周发布一次)。

请参阅体系结构概述，以了解与Drools的可选集成的更多信息。

1.5. 下载并运行示例

1.5.1. 获取发行版ZIP并运行示例

现在试试吧:

1. 从OptaPlanner网站下载OptaPlanner的发布压缩包并解压缩。

2. 打开目录examples并运行脚本。
   Linux或Mac:

$ cd examples
$ ./runExamples.sh

Windows:

$ cd examples
$ runExamples.bat

image.png

示例GUI应用程序将打开，选一个示例试试吧：

image.png

OptaPlanner并没有依赖第三方的GUI库，这个程序同样可以在服务器或移动端JVM中运行。

1.5.2. 在IDE中运行示例

在IntelliJ IDEA, VSCode或Eclipse中运行示例:

1. 打开文件examples/sources/pom.xml作为一个新项目，maven将负责其余的工作。

2. 运行项目中的示例。

1.5.3. 通过Maven、Gradle或者Ant使用OptaPlanner

OptaPlanner jar可以在Maven中央仓库（以及JBossMaven仓库中的快照）中获得。

如果你使用Maven，在pom.xml中添加一个依赖optaplanner-core:

<dependency>
  <groupId>org.optaplanner</groupId>
  <artifactId>optaplanner-core</artifactId>
  <version>...</version>
</dependency>

或者更好的做法是在dependencyManagement中导入optaplanner-bom，以避免在以后添加其他optaplanner依赖项时重复版本号:

<project>
  ...
  <dependencyManagement>
      <dependencies>
          <dependency>
              <groupId>org.optaplanner</groupId>
              <artifactId>optaplanner-bom</artifactId>
              <type>pom</type>
              <version>...</version>
              <scope>import</scope>
          </dependency>
      </dependencies>
  </dependencyManagement>
  <dependencies>
      <dependency>
        <groupId>org.optaplanner</groupId>
        <artifactId>optaplanner-core</artifactId>
      </dependency>
      <dependency>
        <groupId>org.optaplanner</groupId>
        <artifactId>optaplanner-persistence-jpa</artifactId>
      </dependency>
      ...
  </dependencies>
</project>

如果你使用Gradle，在build.gradle中添加一个依赖optaplanner-core:

dependencies {
  implementation 'org.optaplanner:optaplanner-core:...'
}

如果你仍在使用ANT，请从下载压缩包的二进制目录复制类路径中的所有jar。

下载压缩包的二进制目录包含的jar文件比optaplanner-core实际使用的jar文件多得多。它还包含其他模块使用的jar，比如optaplanner-benchmark。

检查maven存储库pom.xml文件，确定optaplanner-core等的最小依赖集。

1.5.4. 通过源码编译OptaPlanner

先决条件

• 安装并配置Git

• 在GitHub上使用HTTPS或SSH进行身份验证

  • 参见GitHub了解更多关于设置和验证Git的信息。

• 安装并配置Maven

从源代码构建并运行示例。

1. 从GitHub克隆optaplanner(或者下载zipball):)

$ git clone https://github.com/kiegroup/optaplanner.git

2. 使用Maven进行编译

$ cd optaplanner
$ mvn clean install -DskipTests

首次运行时，因为需要下载必要的jar包，因此Maven可能会消耗较长时间进行编译。

3. 启动示例

$ cd optaplanner-examples
$ mvn exec:java

4. 用你喜欢的IDE修改源码