Tengo un problema que se ha reducido efectivamente a un problema de vendedor ambulante con varios 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 encontrar 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 pensé en adoptar es un enfoque de 2 pasos. Primero, dividiría las 20 ciudades al azar en 10 ciudades para 2 vendedores cada una, y encontraría el recorrido para cada una como si fuera independiente por unas pocas iteraciones. Después, me gustaría intercambiar o asignar una ciudad a otro vendedor y encontrar el recorrido. Efectivamente, sería un TSP y luego un problema mínimo de makepan. El problema con esto es que sería demasiado lento y es difícil generar una buena vecindad para intercambiar o asignar una ciudad.

¿Alguien puede dar un consejo sobre cómo podría mejorar lo anterior?

EDITAR

La ubicación geográfica de cada ciudad es conocida, y los vendedores comienzan y terminan en los mismos lugares. El objetivo es minimizar el tiempo máximo de viaje, lo que hace que este tipo de problema sea mínimo. Entonces, por ejemplo, si vendedor1 toma 10 horas y vendedor2 toma 20 horas, el tiempo de viaje máximo sería 20 horas.