谷歌或工具的箱子包装问题:难以添加限制，使得所有装在箱子里的物品必须有相同的交货目的地

Question

正如标题所示，我正在使用Google OR Tools来解决垃圾箱包装问题。我想要求所有装进指定卡车的订单都有相同的交货目的地。以下是我实现这一点的尝试，但似乎没有奏效：

# x[i, j] = 1 if item i is packed in bin j
x = {}
for i in data['orders']:
for j in data['trucks']:
x[(i, j)] = solver.IntVar(0, 1, 'x_%i_%i' % (i, j))
data['trucks'] = [0, 1, 2, 3, ...]
data['orders'] = [0, 1, 2, 3, ...]
data['delivery_county_id'] = [8, 8, 8, 1, 3, 2, ...]
from itertools import groupby
# Checks if all elements of list are equal
def all_equal(iterable):
g = groupby(iterable)
return next(g, True) and not next(g, False)
for j in data['trucks']:
solver.Add( all_equal ( [ x[(i, j)] * data['delivery_county_id'][i] for i in data['orders'] if x[(i, j)] == 1 ] ) == True )

奇怪的是，当我执行代码时，我没有得到任何错误，但我的约束没有得到遵守。我不知道为什么。任何帮助或建议都将不胜感激！

Answer 1

我没有一个可以工作的Python安装，但这就是在c#中完成的方法：

public void initModel(CpModel model)
{
// Make up some data for the counties of the orders
deliveryCountyId = new int[nOrders];
for (int order = 0; order < nOrders; order++)
{
deliveryCountyId[order] = order % nCounties;
}
// Boolean variables for item shipped by truck
x = new IntVar[nOrders, nTrucks];
for (int order = 0; order < nOrders; order++)
{
for (int truck = 0; truck < nTrucks; truck++)
{
x[order, truck] = model.NewBoolVar($"Item {order} (county {deliveryCountyId[order]}) in truck {truck}");
}
}
// Boolean variables for truck carrying an item for county
y = new IntVar[nTrucks, nCounties];
for (int truck = 0; truck < nTrucks; truck++)
{
for (int county = 0; county < nCounties; county++)
{
y[truck, county] = model.NewBoolVar($"Truck {truck} has item for county {county}");
}
}
// Each item must be shipped by exactly one truck
for (int order = 0; order < nOrders; order++)
{
List<IntVar> trucksForThisItem = new List<IntVar>();
for (int truck = 0; truck < nTrucks; truck++)
{
trucksForThisItem.Add(x[order, truck]);
}
model.Add(LinearExpr.Sum(trucksForThisItem) == 1);
}
// Compute which counties are in each truck
for (int truck = 0; truck < nTrucks; truck++)
{
for (int county = 0; county < nCounties; county++)
{
List<IntVar> ordersForCountyAndTruck = new List<IntVar>();
{
for (int order = 0; order < nOrders; order++)
{
if (deliveryCountyId[order] == county)
{
ordersForCountyAndTruck.Add(x[order, truck]);
}
}
}
if (ordersForCountyAndTruck.Count > 0)
{
model.AddMaxEquality(y[truck, county], ordersForCountyAndTruck);
}
else
{
model.Add(y[truck, county] == 0);
}
}
}
// Each truck may carry items for only one county
for (int truck = 0; truck < nTrucks; truck++)
{
List<IntVar> countiesPerTruck = new List<IntVar>();
for (int county = 0; county < nCounties; county++)
{
countiesPerTruck.Add(y[truck, county]);
}
model.Add(LinearExpr.Sum(countiesPerTruck) <= 1);
}
}
}

您可以在Python中轻松地表达等效的方法调用。

Answer 2

我使用过Google ortool的CP-SAT解算器(python(。请参阅下面的代码，我已经添加了所需的约束

import random
from ortools.sat.python import cp_model as cp
trucks = list(range(1, 9))
orders = list(range(1, 51))
delivery_county_id = [random.randint(1, 8) for _ in orders]
order_country = list(zip(orders, delivery_county_id))
model = cp.CpModel()
dv_order_truck = {}
for ord_cntry in order_country:
for trck in trucks:
dv_order_truck[(ord_cntry, trck)] = model.NewBoolVar("")

# one order in one truck only
for ord_cntry in order_country:
model.Add(sum(dv_order_truck[(ord_cntry, trck)] for trck in trucks) == 1)

# all orders packed into a given truck have the same delivery destination
dv_truck_country = {}
for trck in trucks:
for cntry in set(delivery_county_id):
dv_truck_country[trck, cntry] = model.NewBoolVar("")

for trck in trucks:
for cntry in set(delivery_county_id):
orders_inTruck_cntry = [v for k,v in dv_order_truck.items() if k[1] == trck and k[0][1] == cntry]
model.AddMaxEquality(dv_truck_country[trck, cntry], orders_inTruck_cntry)

for trck in trucks:
model.Add(sum(dv_truck_country[trck, cntry] for cntry in set(delivery_county_id)) == 1)

solver = cp.CpSolver()
solver.Solve(model)
# inspect the solution
solution = [(ord_cntry, trck) for ord_cntry in order_country for trck in trucks if solver.Value(dv_order_truck[(ord_cntry, trck)]) > 0]
sorted(solution, key = lambda x : x[0][1],reverse=True)