Courses » Distributed Systems » 2012-2013 (LM) » Projects » Ricerca ottimizzata dei PDI (Punti d'Interesse)

Ricerca ottimizzata dei PDI (Punti d'Interesse)

  • Stefano Morganti
In generale si tratta di creare dei coordinatori (agenti) in Jade che gestiscono le richieste concorrenti dei navigatori auto ed inoltre devono catalogare le informazioni sui PDI.

La soluzione proposta è specifica per i PDI delle stazioni di servizio, ma può essere adattata a qualsiasi tipo di PDI.

Sistema per ottimizzare la ricerca delle stazioni di servizio per Navigatore Auto.

Problema: determinare il distributore di carburante più conveniente, considerando oltre al prezzo del carburante, la spesa per raggiungere il distributore. Si tiene conto anche dell’affollamento delle stazioni di servizio, cercando di limitare le code di attesa. Bisogna anche verificare gli orari di apertura e chiusura.

Il sistema prevede che i distributori siano tutti registrati presso un coordinatore, che avrà il compito di fornire il servizio al navigatore delle automobili che lo interrogano. Il sistema prevede n coordinatori, uno per regione (considerando l’ltalia). Volendo si può aggiungere San Marino. E’ necessario anche un coordinatore centrale che sarà il gestore dei coordinatori regionali, confrontando i risultati fra regioni limitrofe.

Ogni coordinatore ha il controllo dei distributori presenti nella zona. Ogni distributore deve indicare il prezzo dei carburanti , il numero di postazioni, l’orario di apertura e chiusura e la sua posizione (coordinate gps).

Il software del navigatore, alla richiesta di una stazione di servizio, dovrà sapere dove si trova il distributore più conveniente e calcolare il percorso per raggiungerla.

  1. L’autista richiede al navigatore che vuole raggiungere la stazione di rifornimento.
2. Il navigatore richiama il servizio del coordinatore centrale.

3. Il coordinatore restistuirà le coordinate gps della stazione di servizio.

4. Calcolo del percorso.

Il coordinatore centrale richiama il coordinatore regionale in base alla richiesta ricevuta. La richiesta deve indicare la posizione attuale del veicolo. Se la posizione ha due regioni limitrofe (direi entro 10 km) allora deve restituire la stazione più conveniente tra le due regioni.

Il coordinatore regionale gestisce il servizio. Quindi riceve le richieste concorrenti:

  1. Per ogni richiesta, si crea una lista dei possibili distributori nel raggio di 10 km (si esclude il distributore se ha più di 5 richieste in coda lo e se sarà chiuso all’arrivo).
2. Per ogni distributore si leggono i prezzi applicati del carburante richiesto (la richiesta deve indicare il tipo di carburante: benzina, diesel o gpl) e la distanza dalla posizione richiesta.

3. Per ogni distributore si fa un calcolo: si calcolano quanti litri di carburante servono per raggiungere la stazione e si moltiplicano per il prezzo al litro + il costo del rifornimento richiesto. Per ogni distributore otterrò la spesa.

4. Si sceglie la stazione più conveniente, cioè dove si spende meno.

Come gestire l’uso concorrente delle postazioni dei distributori?

L’accesso alle postazioni ha la seguente politica, chi prima arriva si serve, gli altri si mettono in coda. Le richieste dei navigatori vengono registrate in un buffer limitato per non eccedere con le richieste contemporanee alla stessa risorsa. Il valore limite del buffer potrebbe essere di 5 richieste. Quindi esiste una specie di prenotazione della postazione che riserva la postazione per un certo utente in certo istante. La macchina impiega 5 min per raggiungerla, 2 minuti prima di arrivare, segnala il suo arrivo, mette una richiesta in coda. Il primo che arriva , se ci sono postazioni libere, si serve, e cancella la richiesta di rifornimento; altrimenti si mette in coda.

Ogni distributore quindi deve indicare il proprio stato (numero di richieste in corso, aperto o chiuso).

Problemi

Un’auto potrebbe mettere la richiesta nel buffer , ma non arrivare mai nella stazione di rifornimento. Quindi la sua richiesta rimarebbe sospesa nel buffer per sempre. E’ necessario fissare un tempo massimo di validità della richiesta. Se per qualche motivo, il distributore richiesto non è più attivo (ad esempio ha finito il carburante), deve segnalare al coordinatore regionale il suo cambio di stato. Al suo cambio di stato, deve partire una segnalazione ai navigatori, che faranno il ricalcolo della stazione di servizio più conveniente. Potrebbe anche accadere che il distributore sia preso d’assalto da tanti utenti che non utilizzano questo sistema, in questo caso, potrebbe essere necessario segnalarlo al coordinatore regionale, che bloccherà le prossime richieste su questa stazione.