Problemi periodici di instradamento dei veicoli: Soluzione di un caso di studio

10 1.3 Periodic Vehicle Routing Problem (PVRP) Il Periodic Vehicle Routing Problem (PVRP) è una generalizzazione del classico problema di VRP, che estende la costruzione delle rotte da un singolo giorno ad un orizzonte temporale di piø giorni, durante il quale ciascun cliente deve essere rifornito esattamente un determinato numero di volte, individuato dalla frequenza di servizio, con il vincolo però di essere visitati al piø una sola volta per ciascun giorno. Sono molte le applicazioni reali nelle quali la distribuzione deve essere pianificata su un determinato periodo di tempo, durante il quale però i nodi non devono essere serviti ogni giorno ma solo in alcuni. Ad esempio alcuni tipi di distribuzione della posta, la rimozione della neve per le strade, la raccolta dei rifiuti e il rifornimento di carburanti. Queste ed altre applicazioni possono essere descritte utilizzando questo tipo di modello. I vincoli operativi ai quali in generale il problema può essere sottoposto sono i seguenti: 1. in ciascun giorno ogni veicolo parte dal deposito centrale e vi ritorna alla fine del suo servizio; 2. ogni cliente viene visitato al piø da un solo veicolo ogni giorno e al piø una sola volta ogni giorno; 3. un veicolo può visitare piø clienti, ma la domanda totale da soddisfare non può eccedere la sua portata massima; 4. il numero di veicoli utilizzati non può essere superiore al numero di veicoli disponibili; 5. il tempo di utilizzo giornaliero di ogni veicolo non può eccedere dal limite fissato; 6. ciascun cliente deve essere visitato esattamente un numero di volte fissato come sua frequenza di servizio; 7. si tenta di minimizzare il costo totale dei viaggi. Come vedremo successivamente associamo a ciascun cliente un indice numerico i che consente di individuare esattamente quel cliente, in questo modo possiamo indicare gli ulteriori parametri che riguardano il cliente associandogli tale indice. Nel rispetto di questi vincoli il PVRP pianifica le rotte su un orizzonte temporale di t giorni, associando a ciascun cliente i una combinazione di visita r scelta in un