Tengo un problema que se ha reducido efectivamente a un Problema del Vendedor Viajero con múltiples vendedores. Tengo una lista de ciudades para visitar desde una ubicación inicial, y tengo que visitar todas las ciudades con un número limitado de vendedores.
Estoy tratando de idear una heurística y me preguntaba si alguien podría echar una mano. Por ejemplo, si tengo 20 ciudades con 2 vendedores, el enfoque que he pensado adoptar es de dos pasos. Primero, dividiría las 20 ciudades al azar en 10 ciudades para 2 vendedores cada una, y encontraría el recorrido de cada una como si fuera independiente durante unas cuantas iteraciones. Después, me gustaría intercambiar o asignar una ciudad a otro vendedor y encontrar el recorrido. Efectivamente, sería un problema de TSP y luego de mínimo makespan. El problema con esto es que sería demasiado lento y la generación de un buen vecindario para intercambiar o asignar una ciudad es difícil.
¿Puede alguien aconsejarme cómo podría mejorar lo anterior?
EDITAR:
Se conoce la geolocalización de cada ciudad y los vendedores empiezan y terminan en los mismos lugares. El objetivo es minimizar el tiempo máximo de viaje, lo que lo convierte en una especie de problema de duración mínima. Así, por ejemplo, si el vendedor 1 tarda 10 horas y el vendedor 2 tarda 20 horas, el tiempo máximo de viaje sería de 20 horas.
