OR-Tools|带你了解谷歌开源优化工具(Google Optimization Tools)

用户1621951

发布于 2021-09-02 14:44:09

10.5K0

发布于 2021-09-02 14:44:09

转眼间暑假已经过去一大半了，大家有没有度过一个充实的假期呢？小编这两天可忙了，boss突然说发现了一个很有趣的开源求解器：OR-Tools。经过一番了解，小编发现它对于为解决优化问题而烦恼的小伙伴真的非常有用，于是赶紧来和大家分享分享。下面让我们一起来看看OR-Tools到底是何方神圣吧！

OR-Tools的介绍

OR-Tools是用于解决组合优化问题的开源软件，它的目的是从众多可能方案中寻求最佳的解决方案，比如解决以下的问题：

线性规划与整数规划(Linear Optimization&Integer Optimization)
网络流问题(Network Flows)
路径规划问题(Routing)
装箱问题(Bin Packing)
调度问题(Scheduling)

OR-Tools的应用范围十分广泛。学习过运筹学的小伙伴们应该对这些问题非常熟悉，线性规划、整数规划以及网络流问题都是课程学习的重点，而路径规划问题、装箱问题和调度问题则同样是运筹学中研究最广泛的问题。一般的求解器都是有针对性地对某一类问题进行求解，相较之下，能解决这么多种问题的OR-Tools简直堪称全能王。

也正是因为OR-Tools涵盖范围之广，小编团队打算在未来一段时间里好好研究这个求解器，并为大家制作一系列相关的精品推文。今天咱们先简单了解一下这个求解器。

1.1

OR-Tools的特点

1. 它具有跨平台性。OR-Tools的核心算法是用C++进行编写的，这使其具有跨平台性。此外，它同样可以用于Python、Java或C#编译过程。

2. 它是面向不同问题的优化工具套件。OR-Tools集合了各种先进的优化算法，它所包含的求解器主要分为约束规划、线性和整数规划、车辆路径规划以及图论算法这四个基本求解器，能够按照优化问题的类型，提供相对应的不同类和接口。例如：对于最简单的线性规划问题，可以使用Linear Solver来解决。

3. 它是开源且开放的。OR-Tools可以免费使用并且公开源代码。此外，OR-Tools还支持第三方求解器，可接入CPLEX等商用求解器以及SCIP等开源求解器。

问题介绍

优化问题类型众多，对于不同类型的问题，需要使用不同的方法和算法来寻求最佳解决方案。在开始解决优化问题之前，需要确定处理问题的类型，然后再据此选择合适的求解器(即寻求最优方案的算法)。接下来就介绍一下OR-Tools解决问题的类型。

2.1

线性规划与整数规划

熟悉运筹学的小伙伴都知道，线性规划是指寻求以一组线性关系为模型的问题的最佳解决方案。混合整数规划则是指某些变量为整数的线性规划问题，这些变量可以是用于表示物品数量的整数变量或者表示决策的布尔型变量(例如是否将某个任务分配给某个工人)。

Google提供了两种解决线性规划问题的方法：

1. MPSolver：MPSolver是OR-Tools所提供的一个包装器，其中包含内置求解器GLOP和几个第三方LP求解器，OR-Tools默认使用GLOP求解器对LP问题进行求解。

2. Google Apps Script提供的线性优化服务。Google Apps Script中的线性优化服务允许开发人员通过调用创建引擎的方法来有选择性地求解线性优化问题(包括LP和MIP)。如果求解LP问题，调用的引擎是GLOP求解器；如果求解MIP问题，则调用的引擎是第三方求解器SCIP。

而为了解决混合整数规划问题，OR-Tools也提供了几种工具：

1.MPSolver：MPSolver接口可用于解决LP问题和MIP问题，因此其中同样包含几个第三方MIP求解器(CBC、SCIP、GLPK、Gurobi)。OR-Tools实际上提供的是统一的求解器接口，内部连接的求解器可以自己配置，默认连接CBC求解器。

2. CP-SAT：它是使用SAT(satisfiability)方法的约束规划求解器，是原始约束规划求解器(CP Solver)的高级版。为了提高计算速度，CP-SAT求解器仅处理整数，这意味着必须使用整数来定义优化问题，如果从具有非整数项约束的问题开始，则需要将约束乘以一个足够大的整数，以便所有项都是整数。

3. 原始CP求解器：它是约束规划求解器，可用于解决MIP问题，但是它已经被高级CP-SAT所取代。

对于在遇到混合整数规划问题的时候，应该怎样选择求解器，并没有固定的规则，但由于问题的差异性还是存在一定的偏向。MIP求解器更适合于可以设置为标准的LP但带有任意整数变量的问题，CP-SAT求解器则更适合于大多数变量为布尔型的问题。而对于同时具有整数和布尔型变量的典型MIP问题。两种求解器的速度通常是没有明显差异的，可以根据个人喜好进行选择。

2.2

网络流(Network Flows)

相信大家对于网络流问题也并不陌生。许多优化问题都可以转换成网络流问题，用由节点和节点之间的有向弧组成的有向图表示(比如说运输货物时的物流问题、铁路网络系统等)。其中具有代表性的是最大流问题和最小费用流问题。

对于如此重要的网络流问题，OR-Tools 在其graph库中提供了多种求解器，包括最大流求解器(SimpleMaxFlow Solver)、最小费用流求解器(SimpleMinCostFlow solver)等。

需要注意的是，最小费用流求解器还可以用于求解分配问题(assignment)，并且它的求解速度通常比MIP求解器和CP-SAT求解器更快。不过，MIP求解器和CP-SAT求解器能够解决的问题类型更多，大多数情况下，MIP和CP-SAT是最佳选择。

2.3

路径规划问题(Routing)

作为论文研究内容的常客，车辆路径规划同样是最重要的优化应用之一。它的目标是为访问一系列地点的车队找到最佳路线。通常情况下，“最佳”是指总距离最小或成本最低的路线。

最基本的路径规划问题是车辆路径问题(VRP)。而在不同限制条件的约束之下，VRP问题衍生出多种不同类型的变种问题。OR-Tools可以解决的VRP主要包括：

1.旅行商问题(Traveling Salesperson Problem)，经典的路径规划问题，其中只有一辆车。

2.车辆路径问题(Vehicle routing problem)，多车辆的TSP拓展。

3.带容量限制的车辆路径规划问题(VRP with capacity constraints)，其中车辆具有最大容量限制。

4.带时间窗的车辆路径规划问题(VRP with time windows)，车辆必须在指定的时间窗内访问这些位置。

5.带资源限制的车辆路径规划问题(VRP with resource constraints)，例如在仓库（路线的起点）装卸车辆的空间或人员是有限制的。

6.VRP与放弃访问问题(VRP with dropped visits)，其中车辆不需要访问所有位置，但必须为每次放弃的访问支付罚款。

OR-Tools为路径规划问题提供了专门的车辆路径优化库(vehicle routing library)，包含约束求解器、路径索引管理器等专门的接口或类，用于在给定限制的情况下识别出最佳车辆路径。

需要注意的是，对于路径规划类问题，还有其它求解器，例如Concorde致力于对大型的TSP问题寻求最优解，在该领域超越OR-Tools。但是，OR-Tools为解决路由问题提供了更好的平台，这些问题包含了超出TSP问题的约束。

在这里附上Concorde的网址，如果有兴趣，大家可以自行了解：

http://www.math.uwaterloo.ca/tsp/concorde.html

2.4

装箱问题(Bin Packing)

装箱问题的目标是寻求将一组给定尺寸的物品装入具有固定容量的容器中的最佳方法。根据具体目标的不同，装箱问题可分为两类：背包问题(以装入最大总价值的物品为目标)和装箱问题(以容纳所有物品的容器数量最小为目标)。其中背包问题还可细分为多维背包问题(多维度物理量限制)和多背包问题(多个背包)。

OR-Tools为典型的背包问题提供了专门的背包问题求解器(knapsack solver)，而多背包问题和装箱问题需要使用通用的混合整数规划求解器(MIP)来求解。需要注意的是，背包问题求解器与CP-SAT一样，只能对整数进行运算，程序中的数据只能包含整数，如果包含非整数，则需转换成整数。

2.5

调度问题(Scheduling)

调度问题对于管理的作用不可忽视，要让管理大量运营工作的公司正常运作，就需要在特定时间为任务分配人员和资源，以定期解决调度问题。主要有员工排班和车间作业调度(JSP)这两种调度问题。员工排班是组织在时间表和人员配置要求约束下为员工创建合理的工作安排。而车间作业问题是一种常见的在多台机器上处理多个作业的调度问题。

事实上，无论是员工排班问题中找到满足所有约束的时间表，还是车间作业问题中要得到任务严格按照顺序完成的调度时间，在计算上都是比较困难的。而OR-Tools为解决此类问题提供了强大的技术支撑，它所提供的CP-SAT求解器为这类问题的解决提供了极大的便利。同时我们可以发现，CP-SAT求解器能够解决混合整数规划问题、分配问题以及调度问题，可以说是应用范围十分广泛的求解器。

编程范例

OR-Tools是用C++编写的，但也可以与Python、Java或C#一起使用，分别使用适用于不同编程语言的OR-Tools即可。

对于每种编程语言来说，设置和解决问题的基本步骤是相同的：

· 导入所需的库

· 声明求解器

· 创建变量

· 定义约束

· 定义目标函数

· 调用求解器并显示结果

3.1

如何运用OR-Tools进行编程

我们先来看看应该怎样安装它吧。大家可以根据习惯的编程语言和电脑的系统配置，直接在官网上进行下载。

官网网址：

https://developers.google.cn/optimization

下载地址：

https://developers.google.cn/optimization/install

其中Python的安装方式区别于C++、Java以及C#。如果是安装Python的OR-Tools，你可以直接通过python -m pip install --upgrade --user ortools命令来获取。如果需要安装其他语言的OR-Tools，可以通过点击官网中的链接进行下载。

以Java为例，我们用IDEA来运行代码，需要通过maven导入求解器的类，maven中的pom.xml文件能够声明项目所依赖的jar包及其坐标信息。所以创建文件的步骤应该为：

首先创建maven项目文件

再将所需要的pom.xml移入项目替换掉原本生成的pom.xml

最后是在src部分创建类进行编程。如果想要运行范例中的代码，则可直接在IDEA中打开并运行。

3.2

实例操作

我们来看一个简单的TSP问题的例子：

（1）导入所需要的库

import static java.lang.Math.abs;
import com.google.ortools.Loader;
import com.google.ortools.constraintsolver.Assignment;
import com.google.ortools.constraintsolver.FirstSolutionStrategy;
import com.google.ortools.constraintsolver.RoutingIndexManager;
import com.google.ortools.constraintsolver.RoutingModel;
import com.google.ortools.constraintsolver.RoutingSearchParameters;
import com.google.ortools.constraintsolver.main;
import java.util.function.LongBinaryOperator;
import java.util.logging.Logger;

（2）创建数据

static class DataModel {
    public final int[][] locations = {
        {4, 4},{2, 0},{8, 0},{0, 1},
        {1, 1},{5, 2},{7, 2},{3, 3},
        {6, 3},{5, 5},{8, 5},{1, 6},
        {2, 6},{3, 7},{6, 7},{0, 8},
        {7, 8},
    };
    public final int vehicleNumber = 1;//车辆数为1
    public final int depot = 0;//起点位置为0
    public DataModel() {
      //将坐标轴等比放缩为114m x 80m
      for (int[] element : locations) {
        element[0] *= 114;
        element[1] *= 80;
      }
    }
  }

（3）创建距离矩阵，这里的距离是指曼哈顿距离

  //获取两个位置之间的曼哈顿距离
  static class ManhattanDistance implements LongBinaryOperator {
    public ManhattanDistance(DataModel data, RoutingIndexManager manager) {
      // 预先计算位置之间的距离，以进行距离回调
      distanceMatrix = new long[data.locations.length][data.locations.length];
      indexManager = manager;
      for (int fromNode = 0; fromNode < data.locations.length; ++fromNode) {
        for (int toNode = 0; toNode < data.locations.length; ++toNode) {
          if (fromNode == toNode) {
            distanceMatrix[fromNode][toNode] = 0;
          } else {
            distanceMatrix[fromNode][toNode] =
                (long) abs(data.locations[toNode][0] - data.locations[fromNode][0])
                + (long) abs(data.locations[toNode][1] - data.locations[fromNode][1]);
          }
        }
      }
    }
    @Override
    public long applyAsLong(long fromIndex, long toIndex) 
{
      //将路径变量索引转换为距离矩阵节点索引
      int fromNode = indexManager.indexToNode(fromIndex);
      int toNode = indexManager.indexToNode(toIndex);
      return distanceMatrix[fromNode][toNode];
    }
    private final long[][] distanceMatrix;
    private final RoutingIndexManager indexManager;
  }

（4）创建索引管理器和routing模型

final DataModel data = new DataModel();// 实例化数据
    //创建索引管理器
    RoutingIndexManager manager =
        new RoutingIndexManager(data.locations.length, data.vehicleNumber, data.depot);

    RoutingModel routing = new RoutingModel(manager);//创建路由模型

（5）创建距离回调

final int transitCallbackIndex =
        routing.registerTransitCallback(new ManhattanDistance(data, manager));

（6）设置路径费用

在此示例中，弧成本计算器是transit_ callback_index，它是求解器对距离回调的内部引用，这意味着任何两个位置之间的旅行成本只是它们之间的距离。

routing.setArcCostEvaluatorOfAllVehicles(transitCallbackIndex);

（7）设置搜索参数

设置默认搜索参数并寻找第一个解决方案的启发式方法:

RoutingSearchParameters searchParameters =
        main.defaultRoutingSearchParameters()
            .toBuilder()
            .setFirstSolutionStrategy(FirstSolutionStrategy.Value.PATH_CHEAPEST_ARC)
            .build();

该代码将第一个解决方案策略设置为PATH_CHEAPEST_ARC，它通过重复添加不通向先前访问过的节点（仓库除外）的权重最小的边为求解器创建初始路径。

（8）添加解决方案打印机

显示求解器返回解的函数如下所示。该函数从解决方案中提取行驶路径和距离并将其打印到控制台。

  static void printSolution(
      DataModel data, RoutingModel routing, RoutingIndexManager manager, Assignment solution) {
    //解决方案的费用
    logger.info("Objective : " + solution.objectiveValue());
    //检查解决方案
    logger.info("Route for Vehicle 0:");
    long routeDistance = 0;
    StringBuilder route = new StringBuilder();
    long index = routing.start(0);
    while (!routing.isEnd(index)) {
      route.append(manager.indexToNode(index)).append(" -> ");//行驶路径
      long previousIndex = index;//起始节点
      index = solution.value(routing.nextVar(index));//终止节点
      routeDistance += routing.getArcCostForVehicle(previousIndex, index, 0);//总距离
    }
    route.append(manager.indexToNode(routing.end(0)));
    logger.info(route.toString());
    logger.info("Distance of the route: " + routeDistance + "m");
  }

（9）求解并打印解

最后，调用求解器并打印解决方案：

  //获取解决方案
    Assignment solution = routing.solveWithParameters(searchParameters);

    // 将解决方案打印到控制台
    printSolution(data, routing, manager, solution);

运行程序，最终结果是：