在这一章节，我们将用到minizinc， 类似于一个编译器，但是它提供不同的solver帮助我们解决问题，我们只需要对问题中的限制（binary constraint network）进行描述(1.constant 2.variable 3.constraint)，要求solver 为我们提供满足解或者最优解。
生活中我们会遇到很多资源分配问题，例如
在departure point， 有两种不同类型的车，一种只运常温货物，一种可以运常温和低温货物。每辆车都有各自的capacity
如今送货到很多家商店，每个商店都有对于货物的不同需求。
对于不同的问题条件，请给出不同的解决方案。
3.This part is as for Question 2, but this time we require a solution that minimises the total cost. This means you must take into account the distance each truck travels, and the cost running each particular truck to compute the total cost of the solution. Both the distances between each pair of customers or the depot (in Km), and the running cost of each truck (in cents per Km) are now given in the data files.
Answer：
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
array[trucks] of int: centsPerKm; % Cost of running trucks (in cents per km)
array[customers,customers] of int: D; % Distances between customers (including the depot)
var int: tot_cost; % Total cost of the solution
% Insert your other 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.
array [ trucks, customers] of var int: a_truck_journey; % store each truck’s distance of different running stages(from one customer to other one). The truck that did not leave starting point should have 0 value.
array [ trucks, customers] of var int : last_customer; % record the last customer of a truck.
array [trucks] of var int: back_distance; % store the distance of a truck going back from the last customer to depot.
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 a different visiting index of different 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.
constraint forall(truck_id in trucks)(forall(customer_id in customers)(if time_index[truck_id, customer_id] != 0 then
if time_index[truck_id,customer_id] =1 then % if the truck visits this customer in the first order.
a_truck_journey[truck_id,customer_id] = D[0, customer_id] else
if time_index[truck_id,customer_id] = 2 then % if the truck visits this customer in the second order.
a_truck_journey[truck_id,customer_id] = D[last_customer[truck_id,customer_id],customer_id] /\ time_index[truck_id, last_customer[truck_id,customer_id]] = 1 else
if time_index[truck_id,customer_id] = 3 then % if the truck visits this customer in the third order.
a_truck_journey[truck_id,customer_id] = D[last_customer[truck_id,customer_id],customer_id] /\ time_index[truck_id, last_customer[truck_id,customer_id]] = 2 else
a_truck_journey[truck_id,customer_id] = D[last_customer[truck_id,customer_id],customer_id] /\ time_index[truck_id, last_customer[truck_id,customer_id]] = 3 endif % the truck visits this customer in the 4th order.
endif
endif
else a_truck_journey[truck_id,customer_id] = 0 endif)); % store each truck’s distance of different running stages(from one customer to other one). The truck that did not leave starting point should have 0 value.
constraint forall(truck_id in trucks)(forall([
if time_index[truck_id, z] = 3 then % if the final customer(z) of a truck is visited in the third order.
back_distance[truck_id] = D[z, 0] else
if time_index[truck_id, x] = 2 then % if the final customer(x) of a truck is visited in the second order.
back_distance[truck_id] = D[x, 0] else
if time_index[truck_id, y] = 1 then % if the final customer(y) of a truck is visited in the first order.
back_distance[truck_id] = D[y, 0] else
back_distance[truck_id] = 0 endif % the truck did not leave start point, then value of back_distance should 0
endif
endif|z , x, y in customers where y< x/\x < z])); % limit the back_distance of each truck
constraint tot_cost = sum(truck_id in trucks)(sum(customer_id in customers)(a_truck_journey[truck_id,customer_id]*centsPerKm[truck_id]) + back_distance[truck_id]*centsPerKm[truck_id]) div 100; % calculate the total cost
% In question Q3, we are optimising the total cost
solve minimize tot_cost;
% Write a Minizinc output item to print the solution in the desired format for Q3
output
[show(T)++" "++ show(C)++" "++show(tot_cost)++ "\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), tot_cost (in dollar)
[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];
centsPerKm = [ 267, 280, 304, 330];
% Distances between places. Place 0 is the depot
D = array2d(customers,customers,
[ 0, 877, 896, 573,
877, 0, 79, 296,
895, 79, 0, 372,
572, 296, 372, 0 ]);
% Orders placed by the customers.
order = array2d(goods,customers,
[| 0, 0, 4, 10,
| 0, 4, 8, 7 |]);
%output：
4 3 12341
1,3,1,0,4
1,1,2,0,1
1,2,3,0,2
2,1,2,0,3
2,2,3,0,5
3,1,2,4,4
4,1,3,10,0
----------
4 3 10941
1,1,3,0,7
2,1,2,0,8
3,1,3,8,0
4,3,1,0,4
4,1,2,4,0
4,2,3,2,0
----------
==========
% 双虚线表示optimal solution
% 单虚线表示satisfying solution
论述：
Time consumption (FD solver):
For 4-3: 1m 25s, if we use Gecode(bundled), then it is 198 msec.
For 6-3: Cannot finish in 1 min, if we use Gecode(bundled), then it is 3s 172 msec.
For 12-4: Cannot finish in 1 min.
For 21-8: Cannot finish in 1 min.
for all, the satisfied solutions can be found quickly.
In this question, I give 6 limitations and 2 new limitations.
- 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.
- the truck has no goods then it cannot visit any customer.
- a truck whose the order of different customers should be different.
1.A new array, which store each truck’s distance of different running stages(from one customer to other one). The truck that did not leave starting point should have 0 value.
2.A new array, which store the distance of a truck going back from the last customer to depot. The truck that did not leave starting point should have 0 value.
tot_cost (dollar)= (the sum of each truck’running distance) * cost of cents per km / 100.
the sum of each truck’running distance = distance between depot and the first customer + distance between customers + distance between last customer and depot
