Aplicaciones
Transporte de mercancías y similares
La aplicación más obvia del TSP es justo el planteamiento del que nace. Imaginemos que tenemos que repartir mercancías en una serie de ciudades y no queremos tener que pasar dos veces por la misma. Tratando las ciudades como vértices de un grafo, las carreteras que las unen como aristas y tomando la distancia que las separa como costes del problema ya tenemos planteado nuestro TSP.
Taladrado de placas de circuitos
Una aplicación directa del TSP es el problema del taladrado de placas de circuito impresas -Printed Circuit Boards, PCBs -. Para conectar dos conductores o insertar partes del circuito se taladran una serie de agujeros en la placa del circuito. Estos agujeros pueden tener distintos tamaños y para realizarlos la máquina tiene que desplazarse para cambiar la broca. Este cambio de broca, evidentemente, consume tiempo de producción y aunque la heurística nos dice que lo más sencillo es realizar todos los agujeros del mismo diámetro y después cambiar de broca, el problema puede ser tratado como un TSP y vemos que se obtienen mejores resultados.
Para formularlo correctamente debemos considerar como nodos -o ciudades- los puntos a taladrar y la ponderación de los arcos el tiempo que el taladro tardaría en cambiar de broca y alcanzar el siguiente objetivo, tomando como punto de partida la posición de reposo del taladro.
Orden de recogida en un almacén
Este problema se asocia con el tratamiento del material de un almacén. Asumiendo que llega al almacén un pedido de un cierto número de objetos almacenados y que un vehículo tiene que recoger todos estos elementos para llevárselos al cliente, podemos apreciar una relación directa con el TSP si consideramos como nodos los puntos del almacén donde se encuentran los objetos del pedido y la ponderación de los arcos como el tiempo que tardaría el vehículo en ir de un punto al otro.
Cristalografía de rayos-X
El análisis de estructuras cristalinas es una importante aplicación del TSP. En este caso un difractómetro de rayos-X se utiliza para medir la intensidad de la refracción de los rayos-X en el cristal desde varias posiciones. Estas mediciones se pueden realizar en un tiempo breve, pero en comparación lo que consume más tiempo es la colocación del instrumento de medición en las distintas posiciones necesarias. Como el orden en el que se realicen las mediciones no afectan al resultado del experimento, tratándolo como un TSP podemos reducir significativamente el tiempo que tarda en realizarse.