在這一章節(jié)，我們將用到minizinc， 類似于一個編譯器，但是它提供不同的solver幫助我們解決問題，我們只需要對問題中的限制（binary constraint network）進行描述(1.constant 2.variable 3.constraint)，要求solver 為我們提供滿足解或者最優(yōu)解。
生活中我們會遇到很多資源分配問題，例如
在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.
