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:
- Determinar grupos de trabajadores.
- Determine cuántos vehículos se necesitarán y sus asientos (libres). Eso es lo que hago en esa pregunta [a].
- El usuario selecciona la combinación preferida y continúa.
- 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.
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.
fuente
Respuestas:
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 ...
fuente