Esercizio TSP-TW

Esercizio 1

Una infermiera deve visitare a casa dei pazienti. Ogni paziente va visitato in una determinata fascia oraria. Il file pazienti.pl contiene per ogni paziente un fatto

dove

• ID è un numero intero che identifica univocamente il paziente
• OrarioMinimo e OrarioMassimo sono il minimo e massimo orario in cui deve avvenire la visita.

Il file pazienti.pl contiene inoltre, per ogni coppia di pazienti (diversi) un fatto

che indica quanto tempo è necessario per andare dal domicilio del Paziente1 a quello del Paziente2.

L'infermiera parte dall'ospedale e alla fine della giornata ritorna all'ospedale, indicato nel file pazienti.pl dall'identificatore 0.

Si scriva un programma CLP(FD) che calcola qual è il tragitto ottimale dell'infermiera, in modo da minimizzare il tempo totale impiegato dall'infermiera.

Si supponga per semplicità che la visita sia istantanea (abbia durata nulla) e che l'infermiera non possa effettuare pause fra una visita e l'altra, ma riparta immediatamente per la destinazione successiva (il prossimo paziente o l'ospedale, se si sono già visitati tutti i pazienti).

Si risolva il problema anche con i file pazienti15.pl e pazienti15b.pl

Esercizio 2

Provare a risolvere il problema sia con il modello delle permutazioni (o delle posizioni), sia con il modello dei successori.

Per risolvere il problema con il modello dei successori, è necessario usare il vincolo circuit, che è definito solo per la libreria ic (e non per fd). Il vincolo circuit non accetta che ci sia un nodo con indice 0: i nodi devono partire da 1. Per questo, consiglio di usare il file pazientis.pl, in cui l'ospedale è indicato dal nodo 1.

Per il ritorno all'ospedale alla fine del tour, una possibilità è duplicare il nodo dell'ospedale e metterlo sia all'inizio, sia alla fine del tour. Per semplificare la preparazione dei dati da parte degli studenti, nel file pazientis.pl vengono riportate anche le distanze per arrivare ad un nodo 12: questo rappresenta nuovamente l'ospedale.

Nella lista risultato, è quindi sufficiente mettere nella posizione 12 il valore 1.