Visão Geral

Este projeto contém três scripts principais: sot, run e pre_process.

sot

O script sot é responsável por resolver um problema de fluxo máximo com custo mínimo e um problema de mochila. A seguir, explico como o grafo é montado, o objetivo do fluxo máximo e a utilização do problema da mochila.

Montagem do Grafo

O grafo é criado na função create_graph(matrix_corridors, matrix_orders). Ele é um grafo direcionado (nx.DiGraph) e é composto pelos seguintes elementos:

• Nó de origem (source): Representa a origem do fluxo.
• Nós de pedidos (pedido_X): Cada pedido é representado por um nó, onde X é o índice do pedido.
• Nós de itens (item_X): Cada item é representado por um nó, onde X é o índice do item.
• Nós de corredores (corridor_X): Cada corredor é representado por um nó, onde X é o índice do corredor.
• Nó de destino (sink): Representa o destino final do fluxo.

As arestas do grafo são adicionadas da seguinte forma:

• Arestas da origem para os pedidos: Cada pedido tem uma aresta que vai do nó source para o nó pedido_X, com capacidade igual à quantidade total do pedido.
• Arestas dos pedidos para os itens: Cada pedido tem uma aresta que vai do nó pedido_X para o nó item_X, com capacidade igual à quantidade do item no pedido.
• Arestas dos itens para os corredores: Cada item em um corredor tem uma aresta que vai do nó item_X para o nó corridor_X, com capacidade igual à quantidade do item no corredor.
• Arestas dos corredores para o destino: Cada corredor tem uma aresta que vai do nó corridor_X para o nó sink, com capacidade infinita.

Objetivo do Fluxo Máximo

O objetivo do fluxo máximo com custo mínimo é encontrar a quantidade máxima de fluxo que pode ser enviada do nó source para o nó sink com o menor custo possível. O custo é determinado pelo peso das arestas. No contexto deste script, o fluxo representa a quantidade de itens que podem ser transportados através dos corredores, e o custo mínimo garante que o número de corredores utilizados seja minimizado.

Escolha Arbitrária de Caminho Aumentador

• Latência (LATENCY): A função possui um esquema de latência definido como LATENCY = max(int(0.05 * o * a), 20), onde o é o número de pedidos e a é o número de itens. Esse valor indica a quantidade de interações em max_flow_min_cost após as quais a prioridade dos vértices deve ser atualizada. Esse esquema de latência é uma tentativa de reduzir o custo de tempo, já que não esperamos uma resposta ótima imediata.

TODO: Definir melhor os valores de o e a para diferentes cenários de uso, considerando a variação no número de pedidos e itens.

• Critérios de Prioridade: Os critérios podem incluir a quantidade de itens em um corredor, a urgência de um pedido ou a capacidade disponível de um item.

• Implementação: A função percorre o grafo em busca de caminhos que aumentem o fluxo total, priorizando os elementos de acordo com os critérios definidos.

• Critérios de Prioridade: Os critérios podem incluir a quantidade de itens em um corredor, a urgência de um pedido ou a capacidade disponível de um item.

• Implementação: A função percorre o grafo em busca de caminhos que aumentem o fluxo total, priorizando os elementos de acordo com os critérios definidos.

Essa abordagem permite uma flexibilidade maior na otimização do fluxo, adaptando-se às necessidades específicas do problema e melhorando a eficiência do transporte de itens através dos corredores.

Exemplo de Uso

Para executar o script, você deve fornecer o caminho para um arquivo de entrada que contém os dados dos pedidos e corredores. O comando para executar o script é:

python sot.py caminho/para/arquivo_de_entrada

O script lê os dados do arquivo, monta o grafo, calcula o fluxo máximo com custo mínimo, resolve o problema da mochila e imprime os resultados.

run

O script run lida com a automação da chamada de outros códigos Python. Ele permite executar testes em um conjunto de arquivos com uma opção para limitar o número de arquivos processados.

Exemplo de Uso

Para executar o script, forneça o caminho para o diretório de dados e, opcionalmente, o número de arquivos a serem processados. Exemplo:

python run.py -n 5

Neste exemplo, o script processará até 5 arquivos do diretório de dados. Se o argumento -n não for fornecido, todos os arquivos no diretório serão processados.

Como Executar

python main.py [FLAGS]

Flags Disponíveis

• --run-only-sot: Executa apenas o script sot.py para gerar soluções, sem rodar checker.py.
• --no-new-test: Impede a execução automática de novos testes caso a solução correspondente não seja encontrada.

Funcionamento

1. O script percorre os arquivos de entrada e verifica se há uma solução correspondente na pasta possible_solution.
2. Se --run-only-sot for passado, apenas sot.py será executado e seus logs serão salvos.
3. Caso contrário, se a solução existir, checker.py validará a solução.
4. Se a solução não existir e --no-new-test não for passado, o usuário pode optar por gerar e validar a solução executando sot.py manualmente.