ANALISI ED APPLICAZIONI DEL MULTICOMMODITY NETWORK FLOW PROBLEM

Il multicommodity network flow problem riguarda la gestione di più componenti, le quali possono essere robot, mezzi o altre risorse; queste componenti sono autonome, ma devono lavorare insieme per poter svolgere tutte le attività necessarie alla risoluzione del problema. Questo tipo di problema riguarda i campi più svariati: gestione di magazzini automatizzati, di linee di trasporto, gestione dei problemi di ottimizzazione dei processi decisionali. Lo scopo della tesi è quello di trovare un modo per far coesistere più entità autonome, le quali devono collaborare per riuscire a svolgere tutti i compiti, senza però che le varie parti in gioco entrino in contrasto tra di loro, ovvero senza che le parti vadano ad ostacolarsi l’un l’altra, e per fare ciò si va alla ricerca di un algoritmo risolutivo, il quale permetta di ottenere una soluzione ottimale, la quale deve essere utilizzabile per più tipi di problemi che si possono dover affrontare. I metodi analizzati in questo lavoro sono definiti esatti, e sono il node-arc form e l’arc-path form. In questo lavoro andremo a definire entrambi i metodi, ma andremo ad implementare un algoritmo risolutivo solamente per il metodo del node-arc form. I problemi esaminati vengono risolti tramite un algoritmo basato sulla programmazione lineare intera mista. Dopo aver definito le diverse variabili previste dalla formulazione del metodo node-arc si è trovato un algoritmo il quale permette di trovare una soluzione lineare che ottimizzi il problema in questione, il quale può riguardare il trasporto merci, l’organizzazione di linee di trasporto o comunque sia qualunque cosa di cui vogliamo gestire il movimento in un dato spazio.