问题：
混合整数规划——资源分配问题中的约束写入问题
毛越
有许多订单需要发货。对于每个订单，可能有1到3个路线选项。这里的问题是找出这些路线中订单的最佳分配（组合）。
假设：
假设每种类型卡车的全部运力和每公里运输成本为：
7.6(size) -> 5300(weight), 4.4(cost per km);
9.6(size) -> 7100(weight), 4.81(cost per km);
15(size) -> 12000(weight), 6.34(cost per km);
假设所有路线都有3次到达目的地的中转时间，那么：
transit cost of each route = transit times*order quantity allocated to this route*4.5
假设路线的运输成本基于使用的卡车数量和运输距离，那么：
transport cost of each route = number of trucks allocated to this route*route distance
//变量
x[j] -> 0-1 variables, if route x1,x2,x3....xj is used.
a[i][j] -> is the weight proportion of order i allocated to route j
t[j][s] -> truck number of certain size needed for each routes
目标函数：
Min (total tranpsort cost + total transit cost) -> MinΣ(x[j]*t[j][s]*Distance[j]*Cost[j] + x[j]*a[i][j]*OrderQuantity[i]*TransitTimes
受制于：
1. if a[i][j] is the proportion of weight allocation among the feasible routes of an order, then:
a1+a2+a3 = 1
2. orders combined together must choose the same route
3. orders combined together must be the same route type
4. all orders must be allocated to one or more trucks and shipped
5. the chosen of the truck size must be within the truck options for each route
6. total weight loaded on the truck must not exceed the total capacity of the truck
这是输入数据的CSV格式：
OrderID,Order_Category,Quantity,Weight,Route1,Route1_Distance,Route1_Type,Route1_TruckOption,Route2,Route2_Distance,Route2_Type,Route2_TruckOption,Route3,Route3_Distance,Route3_Type,Route3_TruckOption
1,B,2000,4000,010W,2000,1,13.5-15,010WE,1750,1,13.5-15,022X,2200,1,13.5-15
2,B,4000,8000,010W,2000,1,13.5-15,010WE,1750,1,13.5-15,022X,2200,1,13.5-15
3,B,1000,2000,010W,2000,1,13.5-15,010WE,1750,1,13.5-15,022X,2200,1,13.5-15
4,B,3500,7000,010WE,1750,1,13.5-15,022X,2200,1,13.5-15,,,,
5,B,2500,5000,020WB,2100,1,13.5-15,022X,2200,1,13.5-15,,,,
6,B,2500,5000,311W,1500,1,13.5-15,022X,2200,1,13.5-15,,,,
7,B,1000,2000,755WF,3500,2,7.6-9.6,755WE,3300,2,7.6-9.6,,,,
8,C,1000,2000,471W,3200,1,13.5-15,010WE,1750,1,13.5-15,022X,2200,1,13.5-15
9,C,1500,3000,471W,3200,1,13.5-15,010WE,1750,1,13.5-15,022X,2200,1,13.5-15
10,C,2000,4000,769WX,2750,2,7.6-9.6,663WA,2600,2,7.6-9.6,,,,
11,C,1000,2000,769WX,2750,2,7.6-9.6,754W,2900,2,7.6-9.6,663WA,2600,2,7.6-9.6
12,C,2000,4000,769WX,2750,2,7.6-9.6,755WE,3100,2,7.6-9.6,,,,
优化结果可能如下所示：
我的问题：我不知道如何编写约束2、3、5、6。特别是，我不知道如何
1). model the relationship between weight allocated and the associated truck quantity and selection of suitable size;
2) make sure orders combined using the same route and same route type
使用Google OR工具或Gu内罗毕python的MIP代码示例会很有帮助。
共有1个答案
徐丰茂
由于没有人提供建议的解决方案，我已经自己制定了一个解决方案。
public static void TruckAllocation() {
Loader.loadNativeLibraries();
// Data
// Dict<orderID, feasible paths)
Map<Integer, List<String>> myPath = new HashMap<Integer, List<String>>();
List<String> order1 = Arrays.asList("010W", "010WE", "022X");
List<String> order2 = Arrays.asList("010W", "010WE", "022X");
List<String> order3 = Arrays.asList("010W", "010WE", "022X");
List<String> order4 = Arrays.asList("010WE", "022X");
List<String> order5 = Arrays.asList("020WB", "022X");
List<String> order6 = Arrays.asList("331W", "022X");
List<String> order7 = Arrays.asList("755WF", "755WE");
List<String> order8 = Arrays.asList("010WE", "022X");
List<String> order9 = Arrays.asList("010WE", "022X");
List<String> order10 = Arrays.asList("663WA");
List<String> order11 = Arrays.asList("754W", "663WA");
List<String> order12 = Arrays.asList("755WE");
myPath.put(0, order1);
myPath.put(1, order2);
myPath.put(2, order3);
myPath.put(3, order4);
myPath.put(4, order5);
myPath.put(5, order6);
myPath.put(6, order7);
myPath.put(7, order8);
myPath.put(8, order9);
myPath.put(9, order10);
myPath.put(10, order11);
myPath.put(11, order12);
// Dict<pathname, truck options)
Map<String, List<Double>> truckOption = new HashMap<String, List<Double>>();
// List<Double> _010W = Arrays.asList(8500.0, 12000.0);
// List<Double> _010WE = Arrays.asList(8500.0, 12000.0);
// List<Double> _020WB = Arrays.asList(8500.0, 12000.0);
// List<Double> _311W = Arrays.asList(8500.0, 12000.0);
// List<Double> _755WF = Arrays.asList(5300.0, 7100.0);
// List<Double> _471W = Arrays.asList(8500.0, 12000.0);
// List<Double> _769WX = Arrays.asList(5300.0, 7100.0);
// List<Double> _022X = Arrays.asList(8500.0, 12000.0);
// List<Double> _755WE = Arrays.asList(5300.0, 7100.0);
// List<Double> _663WA = Arrays.asList(5300.0, 7100.0);
// List<Double> _754W = Arrays.asList(5300.0, 7100.0);
List<Double> _010W = Arrays.asList(13.5, 15.0);
List<Double> _010WE = Arrays.asList(13.5, 15.);
List<Double> _020WB = Arrays.asList(13.5, 15.);
List<Double> _311W = Arrays.asList(13.5, 15.);
List<Double> _755WF = Arrays.asList(7.6, 9.6);
List<Double> _471W = Arrays.asList(13.5, 15.);
List<Double> _769WX = Arrays.asList(7.6, 9.6);
List<Double> _022X = Arrays.asList(13.5, 15.);
List<Double> _755WE = Arrays.asList(7.6, 9.6);
List<Double> _663WA = Arrays.asList(7.6, 9.6);
List<Double> _754W = Arrays.asList(7.6, 9.6);
truckOption.put("010W", _010W);
truckOption.put("010WE", _010WE);
truckOption.put("020WB", _020WB);
truckOption.put("311W", _311W);
truckOption.put("755WF", _755WF);
truckOption.put("471W", _471W);
truckOption.put("769WX", _769WX);
truckOption.put("022X", _022X);
truckOption.put("755WE", _755WE);
truckOption.put("663WA", _663WA);
truckOption.put("754W", _754W);
// Dict<pathname, distance)
Map<String, Integer> dist_matrix = new HashMap<String, Integer>();
dist_matrix.put("010W", 2177);
dist_matrix.put("010WE", 2177);
dist_matrix.put("020WB", 2177);
dist_matrix.put("311W", 1749);
dist_matrix.put("755WF", 77);
dist_matrix.put("471W", 2450);
dist_matrix.put("769WX", 3);
dist_matrix.put("022X", 2125);
dist_matrix.put("755WE", 77);
dist_matrix.put("663WA", 33);
dist_matrix.put("754W", 372);
List<String> pathName = new ArrayList();
List<Double> truckOpt = new ArrayList();
List<String> routes = Arrays.asList(
"010W",
"010WE",
"020WB",
"311W",
"755WF",
"471W",
"769WX",
"022X",
"755WE",
"663WA",
"754W");
List<Double> wgt = Arrays.asList(
4000.0,
8000.0,
2000.0,
7000.0,
5000.0,
5000.0,
2000.0,
2000.0,
3000.0,
4000.0,
2000.0,
4000.0
);
List<Double> qty = Arrays.asList(
2000.0,
4000.0,
1000.0,
3500.0,
2500.0,
2500.0,
1000.0,
1000.0,
1500.0,
2000.0,
1500.0,
2000.0
);
for (String s: routes) {
List<String> temp = Collections.nCopies(10, s);
pathName.addAll(temp);
for (Double i: truckOption.get(s)) {
List<Double> cap = Collections.nCopies(5, i);
truckOpt.addAll(cap);
}
}
int numOrder = 12;
int numTruck = truckOpt.size();
System.out.println("Route size: " + routes.size());
System.out.println("truckOpt size: " + numTruck);
// Solver
// Create the linear solver with the SCIP backend.
MPSolver solver = MPSolver.createSolver("SCIP");
// Variables
// x[i][j] is an array of 0-1 variables, which will be the proportion
// of order i is assigned to path j's truck n.
MPVariable[][] x = new MPVariable[numOrder][numTruck];
for (int i = 0; i < numOrder; i++) {
String name = "wgt: " + wgt.get(i) + " feasible route: " + String.valueOf(myPath.get(i));
for (int j = 0; j < numTruck; j++) {
x[i][j] = solver.makeNumVar(0, 1, name);
// x[i][j] = solver.makeNumVar(0, 1, "");
System.out.println("x_" + i +"-"+ j);
}
}
// y[j][n] is an array of 0-1 variables, which indicates if truck j is opened.
MPVariable[] y = new MPVariable[numTruck];
for (int j = 0; j < numTruck; j++) {
// System.out.println("uy[j]: " + j);
// String name = String.valueOf(truckOpt.get(j));
String name = pathName.get(j) + "-" + String.valueOf(truckOpt.get(j)) + "-"
+ String.valueOf(GetTruckCost(truckOpt.get(j)));
y[j] = solver.makeIntVar(0, 1, name);
System.out.println("y[j]: " + y[j].name());
// System.out.println("dy[j]: " + j);
}
System.out.println("pathName: " + pathName);
System.out.println("truckOption: " + truckOpt);
// Constraints
// Each order is assigned to at least one or all paths' trucks.
for (int i = 0; i < numOrder; ++i) {
// MPConstraint constraint = solver.makeConstraint(1, numTruck, "");
MPConstraint constraint = solver.makeConstraint(1, 1, "");
for (int j = 0; j < numTruck; ++j) {
List<String> my_path = new ArrayList<String>();
my_path.addAll(myPath.get(i));
// System.out.println("my path: " + my_path);
if (my_path.contains(GetProperty(y[j].name(),0))) {
constraint.setCoefficient(x[i][j], 1);
// System.out.println("true");
}
else {
constraint.setCoefficient(x[i][j], 0);
// System.out.println("false");
}
}
}
// all orders loaded cannot exceed the loaded truck's full capacity.
double infinity = java.lang.Double.POSITIVE_INFINITY;
for (int j = 0; j < numTruck; ++j) {
MPConstraint constraint = solver.makeConstraint(-infinity, 0, "");
for (int i = 0; i < numOrder; ++i) {
constraint.setCoefficient(x[i][j], wgt.get(i));
constraint.setCoefficient(y[j], -GetFullCap(Double.parseDouble(GetProperty(y[j].name(),1))));
// System.out.println("wij_wgiht: "+wgt.get(i)+ " truck capcaity: "
// + GetFullCap(Double.parseDouble(GetProperty(y[j].name(),1))));
}
}
// all trucks can be 0 (not open) or numTruck (all open).
for (int j = 0; j < numTruck; ++j) {
MPConstraint constraint = solver.makeConstraint(0, numTruck, "");
constraint.setCoefficient(y[j], 1);
}
// Objective
MPObjective objective = solver.objective();
for (int j = 0; j < numTruck; ++j) {
double cof = Double.parseDouble(GetProperty(y[j].name(),2))*dist_matrix.get(GetProperty(y[j].name(),0));
objective.setCoefficient(y[j], cof);
}
objective.setMinimization();
// Solve
MPSolver.ResultStatus resultStatus = solver.solve();
// Print solution.
// Check that the problem has a feasible solution.
if (resultStatus == MPSolver.ResultStatus.OPTIMAL
|| resultStatus == MPSolver.ResultStatus.FEASIBLE) {
System.out.println("Total cost: " + objective.value() + "\n");
for (int i = 0; i < numOrder; ++i) {
for (int j = 0; j < numTruck; ++j) {
// Test if x[i][j] is 0 or 1 (with tolerance for floating point
// arithmetic).
if (x[i][j].solutionValue() > 0.0000001) {
System.out.println(
"Order " + i + " -> weight: " + x[i][j].name()
);
System.out.println(
"Order " + i + " assigned to truck " + j + "-> " + y[j].name() + ". weight = " + Double.valueOf(String.format("%.2f", x[i][j].solutionValue()*wgt.get(i))));
System.out.println(
"Order " + i + " assigned to truck " + j + ". % = " + Double.valueOf(String.format("%.2f", x[i][j].solutionValue())));
System.out.println("---------------");
System.out.println("");
}
}
}
// for (int j = 0; j < numTruck; ++j) {
// System.out.println(
// "truck " + j + ". isopen? " + y[j].solutionValue());
// }
}
else {
System.err.println("No solution found.");
}
System.out.println("");
System.out.println("");
System.out.println("");
}
类似资料：
-
问题内容： 是否有适用于Python的混合整数线性编程（MILP）求解器？ GLPK python可以解决MILP问题吗？我读到它可以解决混合整数问题。 我是线性编程问题的新手。因此，如果混合整数编程与混合整数线性编程（MILP）不同，我会很困惑，无法真正区分。 问题答案： Pulp 是一个python建模接口，可连接到 CBC （开源）， CPLEX （商业）， Gurobi （商业）， XPR
-
我想为VRP创建一个过度约束规划的增量分数。我创建了一个传统的虚拟车辆，其中包括所有计划外的客户。 示例： Optaplanner将Customer1从Vehicle1移动到Vehicle2: 当我得到AfterVariableChanged：previousStandstill(Customer1)时，在Customer.getVehicle（）中，我有旧车辆的价值，我不知道是否需要添加软成本（
-
在这里使用谷歌云。我刚刚从GCP向Terraform导入了一个项目资源。我看到了以下问题- 资源没有全面导入。资源项目有多个参数需要设置——每个参数都是自己的资源。正如您在下面看到的，有. project来命名项目，new_service_project将其转换为服务项目，以及该项目的每个启用的API的.project_service[n]。 所有这些都必须手动完成，并通过运行以下单独的命令分别完
-
我刚开始使用约束布局，我在编译设计文件时遇到断言错误，这个问题就会单独出现。解决此问题的正确方法是什么？我搞砸了洞日。这是我的XML设计。 和我的错误日志： java.lang.AssertionError：在Android.Support.Constraint.Solver.Widgets.Guideline.GetAnchor（Guideline.java:159)在Android.Suppo
-
我是android编程的新手，我还不知道很多事情。我在这里试图实现的是这样的东西。如果用户没有互联网连接，广告不会显示，或者如果广告由于某种原因没有加载，那么广告不会显示。但布局保持不变，这意味着广告空间是空的。我所做的是在一个相对的布局内扭曲广告视图，然后创建了一个函数，检查广告是否被加载，然后改变布局的可见性，这似乎工作，并解决了当广告不加载时的空白问题。但我认为这不是最好的方法，必须有更好的
-
几天前，我在读关于分数背包问题的贪婪算法和动态规划的书，我发现这个问题可以用贪婪方法得到最优解。谁能给出一个例子或解决方案来解决这个问题的动态规划方法？ 我知道贪婪方法是解决这个问题的最好方法，但我想知道动态规划是如何解决这个问题的。