2 Μεταφορά Εγγράφων

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

Στο 1^o ερώτημα θέλουμε να χρησιμοποιήσουμε τον ελάχιστο αριθμό φορτηγών για να επισκεφτούμε όλες τις πόλεις έστω και μία φορά. Αρχικά σκέφτηκα να χρησιμοποιήσω έναν πίνακα BEGIN\(\times\)END για κάθε φορτηγό, άρα το αποτέλεσμα που θα έπαιρνα από την AMPL θα ήταν ένας πίνακας Go[TRUCK,BEGIN,END]. Έτσι θα μπορούσα να ορίσω τον πίνακα ως binary και να έχω την τιμή 1 αν το φορτηγό έκανε την διαδρομή row->column. Το πρόβλημα που αντιμετώπισα ήταν ότι δεν μπορούσα έτσι να ελέγξω αν το φορτηγό κάνει συνεχόμενη διαδρομή, δηλαδή αν πάει από το A->B1 μετά να πάει από το B1->Bx.

Κατέληξα λοιπόν να προσθέσω ακόμα μια διάσταση στον πίνακα Go, την διάσταση του χρόνου. Οπότε τώρα έχουμε έναν πίνακα Go[TRUCK,BEGIN,END,TIME] όπου για κάθε TIME το φορτηγό θα κάνει μία κίνηση, δηλαδή για ΤΙΜΕ=1 το φορτηγό θα πάει από A->Bx, και τώρα μπορούμε να δημιουργήσουμε περιορισμό ότι για TIME=2 το φορτηγό θα ξεκινήσει από το τέλος του ΤΙΜΕ=1 το Bx.

Επίσης όπως θα δείτε στην συνέχεια στα Δεδομένα έχει προστεθεί ένας επιπλέον προορισμός E. Αυτό είναι απαραίτητο ώστε ο περιορισμός 7 να μπορεί να ισχύει για το τελευταίο Β που θα επισκεφτεί το φορτηγό.

Τέλος στο Μοντέλο έχουμε 2 objective functions total_distance και num_of_trucks. Η AMPL επιλέγει αυτόματα την πρώτη objective συνάρτηση, αλλά και με την δεύτερη παίρνουμε το ίδιο αποτέλεσμα (την έχω αφήσει για να κάνω display τον αριθμό των φορτηγών).

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

Κάθε φορτηγό μπορεί να κάνει το πολύ 400 χιλιόμετρα
Πρέπει να περάσουμε απ’ όλες τις πόλεις
Αρχή \(\neq\) Τέλος: να μην διαλέξουμε ποτέ μια διαδρομή που η αρχή είναι ίδια με το τέλος (δεν βγάζει φυσικό νόημα, αλλά στην AMPL πρέπει να διευκρινιστεί).
Ξεκίνημα από την αφετηρία: κάθε φορτηγό για TIME=1 πρέπει να ξεκινάει από το Α.
Μια κίνηση την φορά: σε κάθε TIME κάνε μία ή καμία κίνηση.
Μην αφήσεις κενά TIME: αν χρησιμοποιήσεις το TIME=n να έχεις χρησιμοποιήσει πρώτα το TIME=n-1.
Διαδοχικές κινήσεις: αν για ΤΙΜΕ=n: A->B1, τότε για TIME=n+1 B1->Bx.
Μην πας από την αρχή στο τέλος: ο περιορισμός αυτός χρειάζεται γιατί εφόσον για να πάω από το Α στο Ε είναι 0 χιλιόμετρα η AMPL θα κάνει κάθε φορά αυτή την κίνηση ακόμα και σε φορτηγά που δεν χρησιμοποιούμε, ενώ δεν χρειάζεται.

2.3 Δεδομένα AMPL

trucks.dat

set BEGIN := A  B1 B2 B3 B4 B5 B6 B7 B8 B9 B10 B11 B12 B13 B14;
set END := B1 B2 B3 B4 B5 B6 B7 B8 B9 B10 B11 B12 B13 B14 E;
set TRUCK := T1 T2 T3 T4 T5 T6 T7 T8;

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

param distance:  B1    B2    B3    B4    B5    B6    B7    B8    B9   B10  B11  B12  B13  B14  E :=
           A    180    240   085   285   205   235   255   155   120  230  340  220  160  240  0
           B1   000    255   150   125   100   175   235   025   065  095  210  055  135  215  0
           B2   255    000   160   235   160   105   045   245   255  195  225  310  115  050  0
           B3   150    160   000   215   125   150   170   130   110  160  260  200  075  150  0
           B4   125    235   215   000   090   130   195   150   190  050  085  155  155  185  0
           B5   100    160   125   090   000   070   135   110   135  040  135  155  065  120  0
           B6   175    105   150   130   070   000   070   175   200  095  125  225  070  055  0
           B7   235    045   170   195   135   070   000   235   250  165  180  290  110  020  0
           B8   025    245   130   150   110   175   235   000   040  110  225  070  130  215  0
           B9   065    255   110   190   135   200   250   040   000  145  265  100  135  230  0
           B10  095    195   160   050   040   095   165   110   145  000  115  135  105  150  0
           B11  210    225   260   085   135   125   180   225   265  115  000  240  185  175  0
           B12  055    310   200   155   155   225   290   070   100  135  240  000  190  270  0
           B13  135    115   075   155   065   070   110   130   135  105  185  190  000  090  0
           B14  215    050   150   185   120   055   020   215   230  150  175  270  090  000  0 ;

2.4 Mοντέλο AMPL

trucks.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 distance {BEGIN, END} >= 0 integer;

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

# minimizing total distance also minimizes the number of trucks
minimize total_distance:
  sum {t in TRUCK, b in BEGIN, e in END, n in TIME} (Go[t,b,e,n] * distance[b,e]);

# minimizing the number of trucks also minimizes the total distance
minimize num_of_trucks:
  sum{t in TRUCK,e in END} Go[t,start,e,1];

# 400km per truck
subject to kilometre {t in TRUCK}:
  sum{b in BEGIN, e in END, n in TIME} (Go[t,b,e,n] * distance[b,e]) <= 400;

# 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 choosing 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{b in BEE, e in END} Go[t,b,e,1] = 0;

# 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;

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

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

trucks.ampl

reset;
model trucks.mod;
data trucks.dat;
option solver cplex;
option show_stats 1;
option omit_zero_rows 1;
objective total_distance;
solve;
display Go;
display total_distance;
display num_of_trucks;

Table 2.1: Results (ampl output)
Truck	From	To	Time	Go
T1	A	B9	1	1
T1	B1	B12	4	1
T1	B8	B1	3	1
T1	B9	B8	2	1
T1	B12	E	5	1
T2	A	B3	1	1
T2	B2	E	7	1
T2	B3	B13	2	1
T2	B6	B14	4	1
T2	B7	B2	6	1
T2	B13	B6	3	1
T2	B14	B7	5	1
T8	A	B5	1	1
T8	B4	B11	4	1
T8	B5	B10	2	1
T8	B10	B4	3	1
T8	B11	E	5	1

Στον πίνακα Go στην 1^η στήλη βλέπουμε τον αριθμό του φορτηγού, στην 2^η από που ξεκίνησε και στην 3^η που πήγε. Στην 4^η

στήλη φαίνεται η στιγμή που έκανε το φορτηγό την συγκεκριμένη διαδρομή, άρα βλέποντας την 4^η στήλη μπορούμε εύκολα να βρούμε την πορεία του φορτηγού.

Άρα χρησιμοποιήσαμε 3 φορτηγά και κάναμε σύνολο 970 χιλιόμετρα. Διαδρομές:

T1 A -> B3 -> B13 -> B6 -> B14 -> B7 -> B2
T2 A -> B5 -> B10 -> B4 -> B11
T8 A -> B9 -> B8 -> B1 -> B12

Truck	From	To	Time	Go
T1	A	B9	1	1
T1	B1	B12	4	1
T1	B8	B1	3	1
T1	B9	B8	2	1
T1	B12	E	5	1
T2	A	B3	1	1
T2	B2	E	7	1
T2	B3	B13	2	1
T2	B6	B14	4	1
T2	B7	B2	6	1
T2	B13	B6	3	1
T2	B14	B7	5	1
T8	A	B5	1	1
T8	B4	B11	4	1
T8	B5	B10	2	1
T8	B10	B4	3	1
T8	B11	E	5	1

Truck	From	To	Time	Go
T1	A	B9	1	1
T1	B1	B12	4	1
T1	B8	B1	3	1
T1	B9	B8	2	1
T1	B12	E	5	1
T2	A	B3	1	1
T2	B2	E	7	1
T2	B3	B13	2	1
T2	B6	B14	4	1
T2	B7	B2	6	1
T2	B13	B6	3	1
T2	B14	B7	5	1
T8	A	B5	1	1
T8	B4	B11	4	1
T8	B5	B10	2	1
T8	B10	B4	3	1
T8	B11	E	5	1

Truck	From	To	Time	Go
T1	A	B9	1	1
T1	B1	B12	4	1
T1	B8	B1	3	1
T1	B9	B8	2	1
T1	B12	E	5	1
T2	A	B3	1	1
T2	B2	E	7	1
T2	B3	B13	2	1
T2	B6	B14	4	1
T2	B7	B2	6	1
T2	B13	B6	3	1
T2	B14	B7	5	1
T8	A	B5	1	1
T8	B4	B11	4	1
T8	B5	B10	2	1
T8	B10	B4	3	1
T8	B11	E	5	1