Problema del viatjant de comerç
From Wikipedia, the free encyclopedia
El problema del viatjant de comerç és el problema d'optimització de trajectòries donat per l'enunciat següent: donat un conjunt de nodes, es tracta de trobar l'ordre de visites a seguir per tal de definir una trajectòria que passi un sol cop per a cada node i de manera que la distància total recorreguda sigui la més curta possible.[1][2] S'usa en el sector públic per al disseny de xarxes de serveis i de transports i la planificació logística pública i privada. Es pot resoldre a mà amb la teoria de grafs i algunes matrius, però és més ràpid, sobretot si intervenen molts nodes o punts de pas, fer-ho amb un senzill programa informàtic. Es va plantejar, com el seu nom indica, per a planificar la millor ruta que hauria de fer un comerciant que volgués passar a veure una llista de clients. A més d'en l'enginyeria, s'estudia com a exemple també, tot i que sense aplicar-lo a la vida real, en altres camps que no hi tenen res a veure, com per exemple, a teoria de la informàtica.[3]
El problema del viatjant de comerç es presenta en moltes aplicacions pràctiques, per exemple en el disseny d'una línia de metro, en logística o en el disseny del circuit integrat de microxips. Encara apareix més sovint com a subproblema, per exemple en el problema de la distribució de mercaderia, en el problema de la planificació de la ruta per donar servei als clients o per donar servei en una avaria o en la seqüenciació del genoma. Els termes de "ciutat" i "distància" no s'han d'agafar al peu de la lletra. Per exemple, el concepte "ciutats" pot representar les ciutats dels clients a visitar o les cadenes d'ADN, mentre que la "distància" pot significar tant el temps que es triga a fer el viatge, els costos o el grau de concordança entre dues cadenes d'ADN. En moltes aplicacions pràctiques primer s'ha de tenir en les restriccions com les dels marges de temps o recursos restringits cosa que complica considerablement la solució del problema.
El problema del viatjant de comerç pertany a la classe de problemes NP-complets de la teoria de complexitat computacional. Per tant es creu que el temps de computació que cada algorisme determinista dona com a solució òptima per aquest problema, en el millor dels casos té un creixement exponencial encara que depèn del nombre de ciutats. Per a poques ciutats, la quantitat que cal l'algorisme pot fer que el càlcul ja sigui impracticable degut a l'enormitat del temps de computació.[4]