Nevicata improvvisa

Nel paese dell'ottimismo, il ministro delle nevicate deve far fronte a una improvvisa catastrofe meteorologica che ha completamente bloccato la rete stradale. La rete stradale è rappresentata da un grafo orientato $G=(N,A)$ (connesso), e per ciascun arco $(i,j)\in A$ è noto il tempo $t_{ij}$ di percorrenza da parte di uno spazzaneve. Per semplicità si assume che il tempo di percorrenza da parte dello spazzaneve sia uguale sia che la strada sia innevata o che sia già stata pulita. Lo spazzaneve deve far rientro alla base, situata in corrispondenza del nodo 0. Formulare il problema di individuare l'itinerario dello spazzaneve che minimizza il tempo complessivo necessario a percorrere tutte le strade almeno una volta (equivalente a minimizzare il tempo impiegato a percorrere le strade più di una volta).

Leggi i suggerimenti <>

Variante 1

Come cambia la formulazione se il tempo di percorrenza di una strada sgombra è la metà rispetto al tempo di percorrenza della stessa strada innevata?

Leggi i suggerimenti <>

Variante 2

Come cambia la formulazione se i mezzi a disposizione sono due e si vuole minimizzare il tempo di fine dell'intero lavoro?

Leggi i suggerimenti <>