在这一章节，我们将用到minizinc， 类似于一个编译器，但是它提供不同的solver帮助我们解决问题，我们只需要对问题中的限制（binary constraint network）进行描述(1.constant 2.variable 3.constraint)，要求solver 为我们提供满足解或者最优解。
生活中我们会遇到很多资源分配问题，例如
在departure point， 有两种不同类型的车，一种只运常温货物，一种可以运常温和低温货物。每辆车都有各自的capacity
如今送货到很多家商店，每个商店都有对于货物的不同需求。
对于不同的问题条件，请给出不同的解决方案。
2.Given the same data as for Question 1, find not only the allocation of goods to trucks but also for each truck a sequence of places to be visited, starting and finishing at the depot and in between visiting the customers to whom it makes deliveries. This sequence should not visit the same customer twice, and it should not visit a customer to whom the truck does not deliver anything.
Answer:
include "alldifferent.mzn";
int: C; % Number of customers
int: T; % Number of trucks
int: G; % Number of goods types
int: MAXCAP; % Upper bound on truck capacity
set of int: trucks = 1..T; % Set of trucks
set of int: customers = 0..C; % Set of customers. Includes depot as customer 0
set of int: goods = 1..G; % Set of goods types
int: chilled = 1; int: ambient = 2; % Good types
set of int: times = 0..C+1; % Enough times to visit each customer once and depot twice if needed
array[trucks] of int: cap; % Capacity of trucks
array[trucks] of bool: refrig; % Whether or not trucks are refrigerated
array[goods,customers] of int: order; % Number of units of goods types ordered by customers
% Insert your variables and constraints here
var trucks: truck_id; % id of a specific car
var customers: customer_id; % id of a specific customer
var goods : goods_value; % whether there is a good on a truck, 1: yes, 0:no.
array [ trucks, customers] of var 0..MAXCAP: chilled_amount; % an array of ( truck_id, customer_id) means how many chilled goods a truck carry to a customers.
array [ trucks, customers] of var 0..MAXCAP: ambient_amount; % an array of ( truck_id, customer_id) means how many ambient goods a truck carry to a customers.
array [ trucks, customers] of var times: time_index; % an array of ( truck_id, customer_id) means the sequence of a truck moving to a customers.
predicate all_not_0_different( array[int,int] of var times:s, var int: x, var int:y) = forall(x in trucks)(forall(y in customers)(if s[x,y] !=0 then forall([s[x,y] != s[x,z]|z in customers where y!=z]) else true endif )); % define a predicate let a truck has different visiting index to customers
constraint forall (truck_id in trucks)(if refrig[truck_id] = true then cap[truck_id] >= sum(customer_id in 1..C)(chilled_amount [truck_id, customer_id] + ambient_amount [truck_id, customer_id] ) else cap[truck_id] >= sum(customer_id in 1..C)(ambient_amount [truck_id, customer_id] + chilled_amount [truck_id, customer_id]) endif); % check the truck is not overfilled.
constraint forall (customer_id in customers)(order[ambient, customer_id]= sum(truck_id in 1..T)( ambient_amount[truck_id, customer_id]));% check whether all the ambient order have been achieved.
constraint forall (customer_id in customers)(order[chilled, customer_id] = sum(truck_id in 1..T)( chilled_amount[truck_id, customer_id])); % check whether all the chilled order have been achieved.
constraint forall(y in 1..T)(if refrig[y] =false then forall(z in 1..C)(chilled_amount[y, z] = 0 ) else true endif); % make sure all the ambient trucks take the ambient goods.
constraint forall(truck_id in trucks)(forall(customer_id in customers)(if chilled_amount [truck_id, customer_id] = 0 /\ambient_amount [truck_id, customer_id] = 0 then time_index[truck_id, customer_id] = 0 else time_index[truck_id, customer_id] != 0 endif)); % if the truck has no goods then it can not visit any customer (value of its time_index should be 0).
constraint all_not_0_different(time_index,truck_id, customer_id); % a truck whose the order of different customers should be different.
% In question Q2, we are only finding a satisfying solution
solve satisfy;
% Write a Minizinc output item to print the solution in the desired format for Q2
output
[show(T), "\t", show(C), "\n" ]++
[ if fix(time_index[truck_id, customer_id]) !=0 then
show(truck_id) ++"," ++
show(time_index[truck_id, customer_id])++","++
show(customer_id) ++"," ++
show(chilled_amount[truck_id, customer_id])++","++
show(ambient_amount[truck_id, customer_id]) ++"\n" else "" endif |truck_id in 1..T, customer_id in 1..C ];
Solution:
nb_trucks, nb_customers (not including the depot)
[truck_id, time_id, customer_id, chilled_goods_units_delivered, ambient_goods_units_delivered]*
%input:
C = 3;
T = 4;
G = 2;
MAXCAP = 10;
% Details of the truck types
cap = [ 7, 8, 8, 10];
refrig = [ false, false, true, true];
% Orders placed by the customers.
order = array2d(goods,customers,
[| 0, 0, 4, 10,
| 0, 4, 8, 7 |]);
%output:
4,3,,,
1,1,3,0,7
2,2,1,0,4
2,1,2,0,4
3,1,2,4,4
4,1,3,10,0
%input
C = 3;
T = 6;
G = 2;
MAXCAP = 10;
% Details of the truck types
cap = [ 5, 5, 7, 7, 6, 10];
refrig = [ false, false, true, true, false, false];
% Orders placed by the customers.
order = array2d(goods,customers,
[| 0, 0, 4, 10,
| 0, 4, 8, 7 |]);
%output
6 3
1,1,3,0,5
2,1,2,0,5
3,2,2,4,0
3,1,3,3,0
4,1,3,7,0
5,2,2,0,3
5,1,3,0,2
6,1,1,0,4
%input:
C = 4;
T = 12;
G = 2;
MAXCAP = 6;
% Details of the truck types
cap = [ 5, 5, 5, 5, 5, 5, 5, 4, 4, 4, 4, 6 ];
refrig = [ false, false, false, false, true, true, true, false, false, true, true, false ];
% Orders placed by the customers.
order = array2d(goods,customers,
[| 0, 2, 0, 4, 10,
| 0, 3, 2, 4, 7 |]);
%output
12 4
1,1,3,0,3
2,1,4,0,5
3,3,2,0,2
3,2,3,0,1
3,1,4,0,2
4,1,1,0,3
5,1,3,4,0
6,1,4,5,0
7,1,4,5,0
10,1,1,2,0
论述：
Time consumption (FD solver):
For 4-3: 58 msec,
For 6-3: 74 msec,
For 12-4: 322 msec,
For 21-8: Cannot finish in 1 min.
In this question, I give 4 limitations and 2 new limitation.
- the truck is not overfilled.
- all the ambient orders have been achieved.
- all the chilled orders have been achieved.
- all the ambient trucks can only take the ambient goods.
1.the truck has no goods then it cannot visit any customer.
2.a truck whose the order of different customers should be different.
I also define a predicate let a truck has different visiting index to customers.
Because of my data structure, I do not need to limit that the same customer should not be visited twice by one truck.
