Closed marcello-zampella closed 4 years ago
marcello-zampella
commented
4 years ago Ho ripensato alla proposta e trovo che per il viaggio "breve" si potrebbe evitare l'algoritmo ricorsivo utilizzando l'algoritmo di dijkstra. Perciò ho pensato di inserire un ulteriore vincolo, permettendo all'utente di scegliere il numero massimo di cambi permessi.
fulcorno
commented
4 years ago Il problema proposto è relativamente semplice, ma adatto in termini di complessità e di dati utilizzati. Occorre però precisare che non basta trovare un percorso di peso minimo tra i vertici, ma bisogna anche tenere conto degli orari delle corse. Può darsi che un percorso più lungo sia più conveniente perché prende una linea le cui corse passano ogni 60 minuti anziché ogni 15. Quindi il grafo dovrà probabilmente essere un multi-grafo (tra ogni coppia di vertici ci sono tutte le corse che possono passare), oppure servono ulteriori strutture dati di appoggio. Dijstra non è certamente accettabile. Attenzione anche a quali corse scegliere nella ricorsione: si dovranno considerare solo le "prossime" corse (se un mezzo della linea 3 passa alle 12:20, non mi interessa il passaggio successivo della stessa linea), quindi l'albero di ricorsione non dovrebbe crescere troppo.
Con queste precisazioni, la proposta è accettata.
Studente proponente
s246314 Zampella Marcello
Titolo della proposta
Applicazione per cammino minimo azienda di trasporti AMAT
Descrizione del problema proposto
L'applicazione si pone l'obbiettivo di trovare il cammino minimo tra due punti della città di Taranto, muovendosi solo attraverso le linee dell'azienda di trasporti AMAT. L'idea, quindi, è quella di trovare tutti i percorsi effettuabili dalla fermata iniziale a quella finale attraverso un algoritmo ricorsivo e trovare quello a costo minore. La scelta del costo sarà effettuata dall'utente, che potrà scegliere tra il percorso a tempo minore o quello con meno cambi.
Descrizione della rilevanza gestionale del problema
L'azienda di trasporti per essere il più efficiente possibile deve ridurre al minimo il tempo che il cliente deve aspettare affinché il servizio gli sia fornito (raggiungere un determinato punto). A tal fine, non è solo necessario che questa impieghi le sue risorse il meglio possibile, ma anche che il cliente sia pienamente cosciente dei percorsi effettuati. Inoltre l'applicazione nella sua implementazione più completa potrebbe tenere traccia dei percorsi effettuati dagli utenti, migliorando l'impiego di risorse e riducendo i costi.
Descrizione dei data-set per la valutazione
I data-set non sono disponibili in rete, per averli ho dovuto contattare l'azienda e ricavare da ciò che mi hanno mandato le informazioni utili. La responsabile mi ha comunque detto che queste informazioni sono di pubblico dominio, le ho rese disponibili su drive: https://drive.google.com/drive/folders/15rZbtVepTnLgpnpSzmVt56zHqrGO4I10?usp=sharing Il data-set è stato suddiviso in 4 file, a seconda che l'orario di interesse sia estivo o invernale, feriale o festivo. Ogni file è composto da 16 colonne -id_pserv: identificativo univoco dell'orario (estivo/invernale - feriale/festivo) X -id_corsa: identificativo univoco della corsa X -codice_linea: il numero della line X -identificativo: numero della linea + indicazione se è andata o ritorno -direzione: due valori: 2 per il ritorno, 1 per l'andata X -num_fermata: numero progressivo delle fermate a cui l'autobus si ferma -id_fermata: identificativo univoco della fermata X -Codice_località: codice univoco della località X -Desc_stazionamento: nome della località X -codice_tratta: identificativo univoco di un tratto di strada -km_tratta: lunghezza di un tratto di strada -ora_partenza: orario di partenza della corsa -ora_arrivo: orario di arrivodella corsa -tempo_percorrenza: intervallo di tempo dal momento di inizio della corsa -tempo_pass_hm: tempo di passaggio (HH:MM) -tempo_pass_hms: tempo di passaggio (HH:MM:SS) X Le informazioni in questione sono eccessive e ridondanti, a mio parere sono utili solo una parte (segnate con la X) e costruirei il database con le 4 tabelle divise, scegliendo la tabella in base al giorno impostato dal calcolatore dell'utente.
Descrizione preliminare degli algoritmi coinvolti
Descrizione preliminare delle funzionalità previste per l’applicazione software
L'applicazione prevederà un'interfaccia attraverso la quale l'utente potrà selezionare una via di partenza ed una di destinazione, in base a queste saranno poi scelte le rispettive fermate. In seguito l'utente deciderà l'orario di partenza o di arrivo e il tipo di viaggio, quindi più comodo (minor cambio di mezzi, a discapito del tempo impiegato), o più veloce. In ogni caso se ci dovessero essere percorsi ugualmente comodi verrebbe scelto quello più veloce e viceversa. In seguito sarà riportato il percorso scelto, indicando all'utente a che ora recarsi alla fermata, quale bus prendere, eventualmente dove scendere e quale linea aspettare e il tempo di percorrenza totale (quindi l'ora di arrivo).