optimizationgurobior-toolsmixed-integer-programming
Mixed Integer Programming - Problem of Writing Constraints in A Resource Allocation Problem
There are a number of orders, which needs to be shipped. For each order, there may be 1 to 3 route options. The problem here is to find out the best allocation (combination) of orders among these routes.
Assumptions:
Suppose the full capacity and per km transport cost for each type of truck are:
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);
Suppose all routes has 3 number of transit times to reach the destination, then:
transit cost of each route = transit times*order quantity allocated to this route*4.5
Suppose transport cost of route is based on number of trucks used and the travling distance, then:
transport cost of each route = number of trucks allocated to this route*route distance
// Variables
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
Objective Function:
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
Subject to:
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
This is how the input date may look like:
This is the CSV formate of the input data:
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,,,,
The optimization result might look like this:
My questions: I am not sure how to write the constraints 2,3,5,6. In particular, I am not sure how to
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
An MIP code example using Google OR tools or Gurobi python would be helpful.
Solution
Since no one offers a suggested solution I have worked out a solution on my own.
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("");
}