Projeto Final de APA (Análise e Projeto de Algoritmos)

Descrição

Este projeto tem como objetivo desenvolver um algoritmo para otimização de alocação de voos em pistas de pouso e decolagem, utilizando uma abordagem gulosa e heurísticas de melhoria. O projeto visa minimizar as penalidades decorrentes de atrasos e conflitos de agendamento.

Contexto do Problema

O projeto consiste na alocação de um conjunto de voos em um número fixo de pistas, de modo a evitar conflitos e minimizar as penalidades associadas aos atrasos. O algoritmo deve encontrar a melhor solução possível para alocar os voos em pistas considerando os tempos de liberação, duração e penalidade.

Estrutura do Projeto

O projeto está organizado da seguinte forma:

projeto-final-apa/
├── src/                                  # Código fonte do projeto
│   ├── main.cpp                          # Função principal do programa
│   ├── greedy_algorithm.cpp              # Algoritmo guloso para alocação de voos
│   ├── neighborhood_moves.cpp            # Movimentações de vizinhança para otimização
│   ├── vnd.cpp                           # Implementação da heurística VND (Variable Neighborhood Descent)
│   ├── instance_reader.cpp               # Leitura das instâncias de dados
│   ├── output_writer.cpp                 # Geração dos arquivos de saída
│   ├── utils.cpp                         # Funções utilitárias
│   └── penalty_calculator.cpp            # Cálculo da penalidade da solução
├── include/                              # Arquivos de cabeçalho (.h)
├── data/                                 # Dados de entrada e saída
│   └── instancias/                       # Arquivos de instância para teste
└── bin/                                  # Arquivos executáveis gerados

Como Compilar e Executar

Compilação

Para compilar o projeto, basta utilizar o comando:

make

Execução

Para executar o programa, utilize:

make run

O programa executará com a instância padrão localizada em:

data/instancias/instancia_1.txt

Limpeza

Para remover arquivos objeto e binários gerados, utilize:

make clean

Formato dos Arquivos de Entrada

O arquivo de entrada segue o formato:

1. Número de voos
2. Número de pistas
3. Tempos de liberação (r)
4. Tempos de processamento (c)
5. Penalidades (p)
6. Matriz de tempos de espera (t)

Exemplo de Arquivo de Entrada:

6
2

5 25 15 40 75 50
15 25 20 30 15 25
55 90 61 120 45 50

0 10 15 8 21 15
10 0 10 13 15 20
17 9 0 10 14 8
11 13 12 0 10 10
5 10 15 20 0 12
5 10 15 20 28 0

Saída do Programa

O programa gera um arquivo de saída com a melhor solução encontrada no seguinte formato:

<valor da solucao>
<lista de voos alocados na pista 1>
<lista de voos alocados na pista 2>
...
<lista de voos alocados na pista m>

Exemplo de Saída:

2800
1 2 5
3 4 6

Tecnologias Utilizadas

• Linguagem: C++
• Sistema de compilação: Makefile

Autores

Projeto desenvolvido como parte da disciplina de Análise e Projeto de Algoritmos (APA).