Hispanopedia WikiEl problema del comprador viajero ( TPP ) es un problema NP-hard estudiado en la investigación de operaciones y la informática teórica . Dada una lista de mercados, el costo de viajar entre diferentes mercados y una lista de bienes disponibles junto con el precio de cada uno de esos bienes en cada mercado, la tarea es encontrar, para una lista dada de artículos, la ruta con el costo combinado mínimo de compras y viaje. El problema del vendedor viajero (TSP) es un caso especial de este problema.
Relación con el problema del viajante de comercio (TSP)
El problema puede verse como una generalización del problema del viajante, que puede verse como el caso especial de TPP donde cada artículo está disponible en un solo mercado y cada mercado vende solo un artículo. Dado que TSP es NP-hard, TPP es NP-hard. [1]
Solución de TPP
Los enfoques para resolver el problema del comprador viajero incluyen la programación dinámica [2] y los algoritmos de búsqueda tabú . [3]
Véase también
Referencias
- ^ "Heurística para el problema del comprador viajero" (PDF) . Archivado desde el original (PDF) el 24 de septiembre de 2015.
- ^ "Un enfoque de programación dinámica para un problema de comprador viajero con restricciones adicionales" (PDF) . Archivado desde el original (PDF) el 2019-09-29.
- ^ "Un enfoque de búsqueda tabú para resolver el problema de las compras itinerantes" (PDF) . Archivado desde el original (PDF) el 10 de junio de 2016.