Algoritmo de agrupamiento

8

Hemos desarrollado un algoritmo que, según el tiempo de check-in de algunos trabajadores y su lugar de residencia, calcula la forma de agruparlos en algunos vehículos y la ruta que deben seguir los vehículos para llevarlos al lugar de trabajo. Esto se ha logrado utilizando el algoritmo TSP (Travelling Salesman Problem) y alguna otra personalización.

Queremos ir más allá y mejorarlo. Por el momento, la capacidad de los asientos de los vehículos está fijada en 4 (5 lugares pero uno ocupado por el conductor) y queremos que esta cantidad sea "variable". En otras palabras, queremos determinar, antes de la ejecución del algoritmo principal, las combinaciones de vehículos (y sus asientos libres) que pueden ser necesarios. Es importante saber que cuando hablo de vehículos, hablo de tipos de vehículos, por ejemplo, el Vehículo A tiene 4 asientos, el Vehículo B tiene 7 asientos, y así sucesivamente. Así que no estoy hablando de tener un Audi A8 de 5 asientos, Seat Ibiza de 5 asientos, un Bus de 20 asientos, digamos.

Hasta ahora, lo que he pensado es lo siguiente:

  1. Determinar grupos de trabajadores.
  2. Determine cuántos vehículos se necesitarán y sus asientos (libres). Eso es lo que hago en esa pregunta [a].
  3. El usuario selecciona la combinación preferida y continúa.
  4. Aplique el algoritmo que ya está desarrollado utilizando la combinación de vehículos y vea si alcanza una solución factible.

Mi pregunta es cómo desarrollar el algoritmo [a]. El siguiente ejemplo le mostrará el resultado de la ejecución de [a]:

Imagine que tenemos las siguientes personas para agrupar en vehículos de 4, 7, 10 asientos gratis. ingrese la descripción de la imagen aquí

Después de la ejecución de [a], tendremos como resultado:

  • G3 (2 trabajadores): un vehículo de 4 asientos libres (se descartan los vehículos con más asientos libres).
  • G2 (2 trabajadores): un vehículo de 4 asientos libres (se descartan los vehículos con más asientos libres).
  • G1 (9 trabajadores):

    • Opción A: 3 vehículos de 4 asientos.
    • Opción B: 1 vehículo de 4 asientos y otro de 7.
    • Opción C: 2 vehículos de 7 plazas.
    • Opción D: un vehículo de 10 asientos.

He pensado en una aproximación:

  • Cree los tipos de vehículos y agréguelos a una lista ordenada (el criterio de clasificación debe ser los asientos).
  • Para cada grupo de trabajadores, haga:
    • Calcular combinaciones [b].
  • Imprimir resultados en pantalla.

Entonces, el principal problema es cómo desarrollar [b].

¿Alguna sugerencia? Lo siento si me he explicado mal.

russellhoff
fuente
1
¿No debería ser el conductor parte del grupo? Según su descripción, parece que él / ella solo está conduciendo el automóvil. ¿Los conductores son solo conductores dedicados o son parte de los trabajadores?
nulo
3
Yo diría que simplemente lo estás haciendo mal. La base del algoritmo debe ser llenar todos los vehículos menos el último. Se corrigió el tamaño del grupo en un gran agujero en esta optimización.
paparazzo
1
Podría ser una buena idea mirar la literatura sobre el "problema del tamaño de la flota y el enrutamiento de vehículos mixtos", que es hasta donde puedo decir el problema que está tratando de resolver
Renaud M.
1
@russellhoff No sé sobre JaCoP, pero probablemente quieras probar las herramientas OR. Es otro solucionador de CP, que tiene una API Java (dadas las bibliotecas que está enumerando, parece ser importante), que parece proporcionar cierta "especialización" para los problemas de enrutamiento de vehículos. Si le echas un vistazo a los ejemplos que ofrecen, probablemente puedas encontrar algo que puedas adaptar (también puedes echar un vistazo a developers.google.com/optimization/routing/tsp )
Renaud M.
1
"TSP (Traveling Salesman Problema) algoritmo" - No estoy al tanto de que no es un algoritmo específico para la solución de TSP. AIUI, la solución más común es el recocido simulado, pero creo que hay otros enfoques también ...
Jules

Respuestas:

2

Se me ocurrió una posible solución: utilice el problema de satisfacción de restricciones para resolverlo.

Habrá una restricción por grupo, como sigue:

cantidad de trabajadores del grupo <= suma por cada vehículo (cantidad del vehículo X asientos del vehículo)

La única variable allí es la cantidad del vehículo, el resto son constantes. Entonces, en mi ejemplo, habría las siguientes restricciones:

9 <= 4x + 7y + 10z
2 <= 4a + 7b + 10c
2 <= 4j + 7k + 10i

Encontré varias bibliotecas (JaCoP, Drools y OptaPlanner), y actualmente estoy usando la primera. Pero no sé cómo definir estas restricciones correctamente ...

russellhoff
fuente