调用OR-Tools求解器求解装箱问题

用户1621951

发布于 2021-09-02 14:50:18

1.9K1

发布于 2021-09-02 14:50:18

文章被收录于专栏：数据魔术师数据魔术师

暑假即将进入尾声，不知道小伙伴们有没有做好准备迎接新的学期呢~

今天小编将继续前几篇关于OR-Tools求解器的内容，为大家介绍如何调用该求解器求解装箱问题。

对于OR-Tools求解器还不了解的小伙伴们可以参考往期推文了解这款求解器的强大功能：

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

#01简介

OR-Tools求解器中关于装箱问题的内容大致能分为三种，分别是：

1、The Knapsack Problem：要求将一组具有给定值和大小（如重量或体积）的物品打包到定容量的容器中。如果项目的总尺寸超过容量，则无法全部打包。在这种情况下，问题在于如何选择物品使容器中总价值最大。

2、Multiple Knapsacks：将具有给定值和大小（如重量或体积）的物品打包到固定数量的箱子中，箱子容量各不相同，要求包装物品的总价值最大。

3、The Bin Packing Problem: 与Multiple Knapsacks Problem一样，Bin Packing问题也涉及将物品装入多个箱子中。但是，Bin Packing问题有不同的目标：找到最少的垃圾箱，将容纳所有项目。

#02调用求解器

调用OR-Tools求解器需要导入所需的jar包，导入的具体过程详见往期推文：

调用OR-Tools求解器求解网络流问题

·The Knapsack Problem

1、导入所需要的库

import com.google.ortools.Loader;
import com.google.ortools.algorithms.KnapsackSolver;
import java.util.ArrayList;

2、创建数据

final long[] values = {360, 83, 59, 130, 431, 67, 230, 52, 93, 125, 670, 892, 600, 38, 48, 147,78, 256, 63, 17, 120, 164, 432, 35, 92, 110, 22, 42, 50, 323, 514, 28, 87, 73, 78, 15, 26,78, 210, 36, 85, 189, 274, 43, 33, 10, 19, 389, 276, 312};
final long[][] weights = {{7, 0, 30, 22, 80, 94, 11, 81, 70, 64, 59, 18, 0, 36, 3, 8, 15, 42, 9,0, 42, 47, 52, 32, 26, 48, 55, 6, 29, 84, 2, 4, 18, 56, 7, 29, 93, 44, 71, 3, 86, 66, 31,65, 0, 79, 20, 65, 52, 13}};
final long[] capacities = {850};

weight表示包含物品重量的载体。

values表示包含物品值的载体。

capacities表示一个只有一个入口的载体，背包的容量。

3、创建KnapsackSolver模型

KnapsackSolver solver = new KnapsackSolver(
    KnapsackSolver.SolverType.KNAPSACK_MULTIDIMENSION_BRANCH_AND_BOUND_SOLVER, "test");
final long computedValue = solver.solve();

调用slove()方法完成相应求解

4、按一定格式输出结果

ArrayList<Integer> packedItems = new ArrayList<>();
ArrayList<Long> packedWeights = new ArrayList<>();
int totalWeight = 0;
System.out.println("Total value = " + computedValue);
for (int i = 0; i < values.length; i++) {
  if (solver.bestSolutionContains(i)) {
    packedItems.add(i);
    packedWeights.add(weights[0][i]);
    totalWeight = (int) (totalWeight + weights[0][i]);
  }
}
System.out.println("Total weight: " + totalWeight);
System.out.println("Packed items: " + packedItems);
System.out.println("Packed weights: " + packedWeights);

其中solver.bestSolutionContains(i)方法用于查看那些物品被选择，进入最终结果

·The Multiple Knapsacks

1、导入所需要的库

import com.google.ortools.Loader;
import com.google.ortools.linearsolver.MPConstraint;
import com.google.ortools.linearsolver.MPObjective;
import com.google.ortools.linearsolver.MPSolver;
import com.google.ortools.linearsolver.MPVariable;

2、创建数据

 static class DataModel {
    public final double[] weights = {48, 30, 42, 36, 36, 48, 42, 42, 36, 24, 30, 30, 42, 36, 36};
    public final double[] values = {10, 30, 25, 50, 35, 30, 15, 40, 30, 35, 45, 10, 20, 30, 25};
    public final int numItems = weights.length;
    public final int numBins = 5;
    public final double[] binCapacities = {100, 100, 100, 100, 100};
  }

与上一个算例有所不同的是，在本算例中共有5个箱子，它们的容量都为100。

3、创建MPSolver模型

MPSolver solver = MPSolver.createSolver("SCIP");
if (solver == null) {
  System.out.println("Could not create solver SCIP");
  return;
}

4、创建变量

MPVariable[][] x = new MPVariable[data.numItems][data.numBins];
for (int i = 0; i < data.numItems; ++i) {
  for (int j = 0; j < data.numBins; ++j) {
    x[i][j] = solver.makeIntVar(0, 1, "");
  }
}

此处二维矩阵x[i][j]用于记录物品的位置,其中i表示物品的索引，j表示箱子的索引，若x[i][j]的值为1，则物品i在箱子j中，若为0，则表示不在。

5、定义约束

for (int i = 0; i < data.numItems; ++i) {
  MPConstraint constraint = solver.makeConstraint(0, 1, "");
  for (int j = 0; j < data.numBins; ++j) {
    constraint.setCoefficient(x[i][j], 1);
  }
}
for (int j = 0; j < data.numBins; ++j) {
  MPConstraint constraint = solver.makeConstraint(0, data.binCapacities[j], "");
  for (int i = 0; i < data.numItems; ++i) {
    constraint.setCoefficient(x[i][j], data.weights[i]);
  }
}

约束一：每个物品最多只能放在一个垃圾箱中。此约束要求x[i][j]的总和<= 1。

约束二：每个垃圾箱中包装的总重量不能超过其容量。此约束的设定要求放在垃圾箱中的物品的重量之和<=垃圾箱的容量。

6、计算各箱子的总价值

MPObjective objective = solver.objective();
for (int i = 0; i < data.numItems; ++i) {
  for (int j = 0; j < data.numBins; ++j) {
    objective.setCoefficient(x[i][j], data.values[i]);
  }
}
objective.setMaximization();
final MPSolver.ResultStatus resultStatus = solver.solve();

objective.setCoefficient(x[i][j], data.values[i])方法检查物品i是否在箱子j中，若在，则箱子的总价值增加。

7、按一定格式输出结果

if (resultStatus == MPSolver.ResultStatus.OPTIMAL) {
  System.out.println("Total packed value: " + objective.value() + "\n");
  double totalWeight = 0;
  for (int j = 0; j < data.numBins; ++j) {
    double binWeight = 0;
    double binValue = 0;
    System.out.println("Bin " + j + "\n");
    for (int i = 0; i < data.numItems; ++i) {
      if (x[i][j].solutionValue() == 1) {
        System.out.println(
            "Item " + i + " - weight: " + data.weights[i] + "  value: " + data.values[i]);
        binWeight += data.weights[i];
        binValue += data.values[i];
      }
    }
    System.out.println("Packed bin weight: " + binWeight);
    System.out.println("Packed bin value: " + binValue + "\n");
    totalWeight += binWeight;
  }
  System.out.println("Total packed weight: " + totalWeight);
} else {
  System.err.println("The problem does not have an optimal solution.");
    }
  }

·The Bin Packing Problem

1、导入所需要的库

import com.google.ortools.Loader;
import com.google.ortools.linearsolver.MPConstraint;
import com.google.ortools.linearsolver.MPObjective;
import com.google.ortools.linearsolver.MPSolver;
import com.google.ortools.linearsolver.MPVariable;

2、创建数据

static class DataModel {
    public final double[] weights = {48, 30, 19, 36, 36, 27, 42, 42, 36, 24, 30};
    public final int numItems = weights.length;
    public final int numBins = weights.length;
    public final int binCapacity = 100;
  }

Bin Packing Problem 中的箱子数量是不限的。

3、创建MPSolver模型

MPSolver solver = MPSolver.createSolver("SCIP");
if (solver == null) {
  System.out.println("Could not create solver SCIP");
  return;
}

4、创建变量

MPVariable[][] x = new MPVariable[data.numItems][data.numBins];
for (int i = 0; i < data.numItems; ++i) {
  for (int j = 0; j < data.numBins; ++j) {
    x[i][j] = solver.makeIntVar(0, 1, "");
  }
}
MPVariable[] y = new MPVariable[data.numBins];
for (int j = 0; j < data.numBins; ++j) {
  y[j] = solver.makeIntVar(0, 1, "");
}

与Multiple Knapsacks 问题一样，二维矩阵x[i][j]用于记录物品的位置,其中i表示物品的索引，j表示箱子的索引，若x[i][j]的值为1，则物品i在箱子j中，若为0，则表示不在。

5、定义约束

double infinity = java.lang.Double.POSITIVE_INFINITY;
for (int i = 0; i < data.numItems; ++i) {
  MPConstraint constraint = solver.makeConstraint(1, 1, "");
  for (int j = 0; j < data.numBins; ++j) {
    constraint.setCoefficient(x[i][j], 1);
  }
}
for (int j = 0; j < data.numBins; ++j) {
  MPConstraint constraint = solver.makeConstraint(0, infinity, "");
  constraint.setCoefficient(y[j], data.binCapacity);
  for (int i = 0; i < data.numItems; ++i) {
    constraint.setCoefficient(x[i][j], -data.weights[i]);
  }
}

约束一：每个物品必须放在一个垃圾箱中。此约束的设定要求当i保持不变时，x[i][j]的总和等于 1。

约束二：每个垃圾箱中包装的总重量不能超过其容量，与Multiple Knapsacks 类似。

6、调用slove()方法解决问题

MPObjective objective = solver.objective();
for (int j = 0; j < data.numBins; ++j) {
  objective.setCoefficient(y[j], 1);
}
objective.setMinimization();
// [START solve]
final MPSolver.ResultStatus resultStatus = solver.solve();

7、输出解决方案

if (resultStatus == MPSolver.ResultStatus.OPTIMAL) {
  System.out.println("Number of bins used: " + objective.value());
  double totalWeight = 0;
  for (int j = 0; j < data.numBins; ++j) {
    if (y[j].solutionValue() == 1) {
      System.out.println("Bin " + j);
      double binWeight = 0;
      for (int i = 0; i < data.numItems; ++i) {
        if (x[i][j].solutionValue() == 1) {
          System.out.println("Item " + i + " - weight: " + data.weights[i]);
          binWeight += data.weights[i];
        }
      }
      System.out.println("Packed bin weight: " + binWeight);
      totalWeight += binWeight;
    }
  }
  System.out.println("\nTotal packed weight: " + totalWeight);
} else {
  System.err.println("The problem does not have an optimal solution.");
}
// [END print_solution]
  }

#03其他装箱问题

细心的小伙伴可能会发现，小编介绍的这三种装箱问题都是属于一维装箱问题，它们将物品的大小以体积这一个变量表示。这当然与现实中遇到的问题会有一定区别。在现实中，物品都是有长、宽、高的，单纯将体积相加判断箱子是否装下显然存在一定的误差。

下面，小编将简单介绍一下二维、三维的装箱问题即所用的方法。

· 二维装箱问题

在本问题中我们解决问题的前提是假设所有物品为矩形(rectangular)，二维装箱问题需要考虑箱子中的物品应该如何摆放才能使箱子容纳更多的物品。

二位装箱问题的一种解决思路是基于BL法。Baker et al.[3] (1980)提出了The bottom-left (BL) 法，即将物品尽量向左向下推。自此以后，不少基于BL法的算法都纷纷出现。例如，Hopper and Turton [4](2001)在BL法的基础上运用启发式算法，同时尝试了不同种矩形放置向左下方向的顺序，去其中最优解，这种方法叫做bottom-left-decreasing (BLD)。

另一种较为普遍的方法是基于某些算法同时选择该放置哪个物品以及该物品应放置在哪里。例如，Asık and Özcan[5]于2009年提出的一种新的双向最佳配合(bidirectional best-fifit)启发式算法。

还有一些算法并不基于以上方法，例如Leung et al. [6]于2012年提出的hybrid simulated annealing (HSA) 算法，它先用贪婪算法求出最初解，再利用模拟退火算法求出较优解。

·三维装箱问题

三维装箱问题相较于二维，并没有二维装箱问题发展得那么完善。Bortfeldt and Gehring[7]于1999年提出了用禁忌算法和遗传算法解决三维装箱问题的方法。

Karabulut and Inceog˘lu[8]提出了基于the deepest-bottommost-leftmost fill 原则的遗传算法。这个deepest-bottom most-leftmost fill原则翻译过来就是最深最底最左原则，类似于二维装箱问题中的BL法。

在现存的各种算法中，Allen et al.[9]于2011年提出的混合放置法在基准测试中表现较好，这个方法结合最优满足法(best-fit method)与禁忌搜索算法。感兴趣的小伙伴可以了解一下哦。

#Reference

【1】 Lijun Wei, Wee-Chong Oon, Wenbin Zhu, Andrew Lim, 2011. A reference length approach for the 3D strip packing problem, European Journal of Operational Research, 37-47.

【2】Lijun Wei, Wee-Chong Oon, Wenbin Zhu, A skyline heuristic for the 2D rectangular packing and strip packing problems, 2012. Andrew Lim, European Journal of Operational Research, 337-346.

【3】Baker, B.S., Coffman, E.G., Rivest, R.L., 1980. Orthogonal packings in two dimensions. SIAM Journal on Computing 9, 846–855.

【4】Hopper, E., Turton, B.C.H., 2001. An empirical investigation of meta-heuristic andheuristic algorithms for a 2D packing problem. European Journal of Operational Research 128, 34–57.

【5】Asık, O., Özcan, E., 2009. Bidirectional best-fifit heuristic for orthogonal rectangularstrip packing. Annals of Operations Research 172, 405–427.

【6】Leung, S.C.H., Zhang, D., Zhou, C., Wu, T., 2012. A hybrid simulated annealingmetaheuristic algorithm for the two-dimensional knapsack packing problem. Computers & Operations Research 39, 64–73 [Special Issue on Knapsack Problems and Applications.].

【7】Bortfeldt, A., Gehring, H., 1999. Two metaheuristics for strip packing problems. In: Proceedings band der 5th International Conference of the Decision SciencesInstitute, Athen, 1153–1156.

【8】Karabulut, K., _Inceog˘lu, M.M., 2005. A hybrid genetic algorithm for packing in 3dwith deepest bottom left with fifill method. In: Yakhno, T. (Ed.), Advances ininformation systems, Lecture Notes in Computer Science, 441–450.

【9】Allen, S.D., Burke, E.K., Kendall, G., 2011. A hybrid placement strategy for the threedimensional strip packing problem. European Journal of Operational Research 209, 219–227.

欲下载相关代码，请移步留言区

- END -

文案&排版：王思涵（华中科技大学管理学院本科一年级）

指导老师：秦虎老师（华中科技大学管理学院）

审稿：周航（华中科技大学管理学院本科二年级）

如对文中内容有疑问，欢迎交流。PS：部分资料来自网络。

如有需求，可以联系：

秦虎老师（华中科技大学管理学院：tigerqin1980@qq.com）

王思涵（华中科技大学管理学院本科一年级：2278159431@qq.com）

周航（华中科技大学管理学院本科二年级：zh20010728@126.com）

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2021-08-26，如有侵权请联系 cloudcommunity@tencent.com 删除