Desenvolvemos um algoritmo que, dependendo do horário de check-in de alguns trabalhadores e do local onde moram, calcula a maneira de agrupá-los em alguns veículos e a rota que deve ser seguida pelos veículos para levá-los ao local de trabalho. Isso foi realizado usando o algoritmo TSP (Traveling Salesman Problem) e algumas outras customizações.
Queremos ir além e melhorá-lo. Por enquanto, a capacidade de assentos dos veículos é fixada em 4 (5 vagas, mas uma ocupada pelo motorista) e queremos tornar esse valor "variável". Em outras palavras, queremos, antes da execução do algoritmo principal, determinar as combinações de veículos (e seus assentos livres) que podem ser necessários. É importante saber que, quando falo em veículos, falo sobre tipos de veículos, por exemplo, o Veículo A tem 4 assentos, o Veículo B tem 7 assentos e assim por diante. Então, não estou falando de ter um Audi A8 de 5 lugares, o Seat Ibiza de 5 lugares, um ônibus de 20 lugares, por exemplo.
Até agora, o que eu pensei foi o seguinte:
- Determinar grupos de trabalhadores.
- Determine quantos veículos serão necessários e seus assentos (gratuitos). É o que estou perguntando nessa pergunta [a].
- O usuário seleciona a combinação preferida e continua.
- Aplique o algoritmo já desenvolvido usando a combinação de veículos e veja se ele alcança uma solução viável.
Minha pergunta é como desenvolver o algoritmo [a]. O exemplo a seguir mostra o resultado da execução de [a]:
Imagine que temos as seguintes pessoas para agrupar em veículos de 4, 7, 10 lugares gratuitos.
Após a execução de [a], teremos como resultado:
- G3 (2 trabalhadores): Um veículo de 4 lugares livres (veículos com mais lugares livres são descartados).
- G2 (2 trabalhadores): um veículo com 4 lugares livres (veículos com mais lugares livres são descartados).
G1 (9 trabalhadores):
- Opção A: 3 veículos de 4 lugares.
- Opção B: 1 veículo de 4 lugares e outro de 7.
- Opção C: 2 veículos de 7 lugares.
- Opção D: um veículo de 10 lugares.
Eu pensei em uma aproximação:
- Crie os tipos de veículos e adicione-os a uma lista classificada (o critério de classificação deve ser os assentos).
- Para cada grupo de trabalhadores, faça:
- Calcular combinações [b].
- Imprimir resultados na tela.
Portanto, o principal problema é como desenvolver [b].
Alguma sugestão? Desculpe se eu me expliquei mal.
fonte
Respostas:
Eu vim com uma solução possível: use o Problema de Satisfação de Restrições para resolvê-lo.
Haverá uma restrição por grupo, da seguinte maneira:
quantidade de trabalhadores do grupo <= soma por cada veículo (quantidade de veículo X assentos do veículo)
A única variável é a quantidade do veículo, o restante são constantes. Portanto, no meu exemplo, haveria as seguintes restrições:
9 <= 4x + 7y + 10z
2 <= 4a + 7b + 10c
2 <= 4j + 7k + 10i
Encontrei várias bibliotecas (JaCoP, Drools e OptaPlanner) e atualmente estou usando a primeira. Mas não sei como definir essas restrições corretamente ...
fonte