以最小价格和旅行距离购买购物清单上的所有商品

Question

我有一个我想买的20件商品的清单I =(1，…，20)，镇上有5家超市j =(1，…，5)，有两个给定条目:

Cij: the price of item "i" in supermarket "j"
Dj: the cost to travel between my house and the supermarket "j"

为了方便，我想在最多2个市场购买所有的商品(所有的商品都在所有的市场)。在逛了一趟市场之后，我总是回到家里，我如何制定一个整数线性问题模型来最小化我的成本

?

Answer 1

在MiniZinc中实现的一个简单的milp模型(为了简单起见，只有三个项目)。模型中，x_ij表示商品j是否从商店i购买，z_i表示是否到过商店i。

int: Stores = 5;
int: Items = 3;
set of int: STORE = 1..Stores;
set of int: ITEM = 1..Items;
array[STORE,ITEM] of int: C = [| 5, 4, 5
| 3, 2, 5 
| 5, 5, 2 
| 8, 1, 5 
| 1, 8, 2 |];
array[STORE] of int: D = [5, 4, 5, 2, 3];

array[STORE,ITEM] of var 0..1: x;
array[STORE] of var 0..1: z;
% visit at most two shops
constraint sum(i in STORE)(z[i]) <= 2;
% buy each item once
constraint forall(j in ITEM)
(sum(i in STORE)(x[i,j]) = 1);
% can't buy from a shop unless visited
constraint forall(i in STORE)
(sum(j in ITEM)(x[i,j]) <= Items*z[i]);
var int: cost = sum(i in STORE)(2*D[i]*z[i]) + sum(i in STORE, j in ITEM)(C[i,j]*x[i,j]);
solve minimize cost;
output ["cost=(cost)n"] ++ 
["x="] ++ [show2d(x)] ++
["z="] ++ [show(z)];

运行了:

cost=14
x=[| 0, 0, 0 |
0, 0, 0 |
0, 0, 0 |
0, 1, 0 |
1, 0, 1 |]
z=[0, 0, 0, 1, 1]