3 Μεταφορά Εμβολίων

3.1 Τρόπος Σκέψης

Στο 2^ο ερώτημα ζητείτε να βρεθεί η πιο σύντομη σε χρόνο διαδρομή που περνάει απ’ όλες τις πόλεις και επιστρέφει στην πρωτεύουσα. Έχοντας ήδη κάνει το 1^ο ερώτημα, μπορούμε να τροποποιήσουμε ελάχιστα το μοντέλο μας για να είναι λειτουργικό σε αυτό το πρόβλημα.

Περνάμε λοιπόν τα νέα δεδομένα αλλά αυτή την φορά ορίζουμε μόνο ένα φορτηγό, αφού μας δίνεται ότι τα 5 φορτηγά θα φύγουν κομβόι. Στο μοντέλο θα αντικαταστήσουμε τον πίνακα distance με minutes καθώς και θα αλλάξουμε τον περιορισμό για την εκκίνηση από την αφετηρία ώστε να εννοούμε να χρησιμοποιηθεί κάθε διαθέσιμο φορτηγό (στην περίπτωση μας είναι μόνο 1).

3.2 Περιορισμοί

Έχουμε μόνο έναν νέο περιορισμό:

Επιστροφή στην πρωτεύουσα: θέλουμε η κίνηση που θα γίνει στο τελευταίο TIME να έχει προορισμό την πρωτεύουσα (που έχει ονομαστεί και A και Ε)

3.3 Δεδομένα AMPL

trucks2.dat

set BEGIN := A  B1 B2 B3 B4 B5 B6;
set END := B1 B2 B3 B4 B5 B6 E;
set TRUCK := T1 ;

param start:= A;
param end:= E;

param minutes:  B1     B2    B3    B4    B5    B6     E   :=
           A    786    549   657   331   559   250   000
           B1   000    668   979   593   224   905   786
           B2   668    000   316   607   472   467   549
           B3   979    316   000   890   769   400   657
           B4   593    607   890   000   386   559   331
           B5   224    472   769   386   000   681   559
           B6   905    467   400   559   681   000   250 ;

3.4 Mοντέλο AMPL

trucks2.mod

set BEGIN ordered;
set END ordered;
set TRUCK ordered;

set BEE = BEGIN inter END ordered;

set TIME = {1..card(BEE)+1} ordered;

param start symbolic in BEGIN;
param end symbolic in END;

param minutes {BEGIN, END} >= 0 integer;

var Go {TRUCK, BEGIN, END, TIME} binary;

# minimizing total minutes on road
minimize total_time:
  sum {t in TRUCK, b in BEGIN, e in END, n in TIME} (Go[t,b,e,n] * minutes[b,e]);

# visit every town
subject to go_at_least_once {e in END}:
  sum{t in TRUCK, b in BEGIN, n in TIME} Go[t,b,e,n] >= 1;

# avoid chosing distance[i,j]=0 where i==j
subject to end_equals_begin {t in TRUCK, i in BEE, n in TIME}:
  Go[t,i,i,n] = 0;

# every truck should start from A
subject to start_from_a {t in TRUCK}:
  sum{e in END} Go[t,start,e,1] = 1;

# make only one move for every TIME
subject to every_time_move_once {t in TRUCK, n in TIME}:
  sum{b in BEGIN, e in END} Go[t,b,e,n] <= 1;

# move from time 1 to time 2 1->2->3
subject to move_in_order {t in TRUCK, n in 1..last(TIME)-1}:
  sum{b in BEGIN, e in END} Go[t,b,e,n] >= sum{b in BEGIN, e in END} Go[t,b,e,n+1];

# if you move from A->B2 the next move should start from B2
subject to continuous_movement {t in TRUCK, n in 2..last(TIME), b in BEE}:
  sum{e in END} Go[t,b,e,n] = sum{i in BEGIN} Go[t,i,b,n-1];

# never go from start to end (A->E)
subject to ae {t in TRUCK, n in TIME}:
  Go[t,start,end,n] = 0;

# the last move you make should end at E
subject to finishAtE {t in TRUCK}:
  sum{b in BEGIN} Go[t,b,end,last(TIME)] = 1;

3.5 Αποτελέσματα

Τρέχουμε τις εξής ενοτλές:

trucks2.ampl

reset;
model trucks2.mod;
data trucks2.dat;
option solver cplex;
#option display_round 0;
option show_stats 1;
option omit_zero_rows 1;
#option omit_zero_cols 1;
solve;
display Go;
display total_time;

Table 2.1: Results (ampl output)
Truck	From	To	Time	Go
T1	A	B4	1	1
T1	B1	B2	4	1
T1	B2	B3	5	1
T1	B3	B6	6	1
T1	B4	B5	2	1
T1	B5	B1	3	1
T1	B6	E	7	1

Το format του πίνακα Go είναι ίδιο με προηγουμένως, και βρίσκουμε ότι χρειαζόμαστε τουλάχιστον 2575 λεπτά για να πάμε σε όλες τις πόλεις και να γυρίσουμε στην πρωτεύουσα.

Διαδρομή: A -> B4 -> B5 -> B1 -> B2 -> B3 -> B6 -> A