¿Alguien sabe el nombre del siguiente problema?

Question

En un día determinado un número de $N$ vendedores (de la misma empresa) están dispersos al azar en un paisaje con $M$ ciudades. Al día siguiente, el mayor número posible de ciudades debe recibir la visita de un vendedor, sin que dos vendedores vayan a la misma ciudad. A qué ciudad $c_j$ debe cada vendedor $s_i$ ir, con el fin de minimizar la distancia total recorrida por todos los vendedores.

Tenga en cuenta que si $M$ es menor que $N$ algunos vendedores deberían quedarse en su sitio y no ir a ninguna parte. También suponemos que cada vendedor puede llegar a cada ciudad en el tiempo previsto.

También agradecería cualquier indicación sobre algoritmos que resuelvan el problema.

Answer 1

En un comentario, Rahul Narain sugiere que este problema puede considerarse un ejemplo de la problema de asignación . Normalmente se piensa en asignar agentes (vendedores) a tareas, y cada asignación tiene un determinado coste. En este caso, las tareas son ciudades, y los costes vienen determinados por las distancias entre las ubicaciones actuales de los vendedores y sus posibles ciudades de destino.