Cos’è il problema del commesso viaggiatore?
Il “problema del commesso viaggiatore” è un esempio di problema NP-completo per cui non è stata trovata una risoluzione migliore ma una buona soluzione che si avvicina alla più efficiente.
Il problema
Consideriamo un’impresa di spedizioni che abbia un magazzino centrale. Tutte le mattine ciascun autocarro viene caricato presso il magazzino e poi indirizzato alle varie destinazioni per consegnare le merci. Alla fine della giornata ogni autocarro deve ritornare al magazzino per essere pronto per il giorno successivo. Per ridurre i costi, l’azienda intende scegliere un ordine di fermate per le consegne che consenta a ciascun autocarro di percorrere la distanza minima. Non esiste un algoritmo efficiente. Sotto opportune ipotesi, tuttavia, sono noti degli algoritmi efficienti che forniscono una distanza complessiva che non è molto diversa da quella minima.