Sistema de Despacho de Transporte por Aplicativo - CabeAí

Este repositório contém a implementação do Trabalho Prático 2 (TP2) da disciplina de Estruturas de Dados (DCC205/DCC221) do DCC-UFMG, referente ao semestre 2025/2.

📖 Sobre o Projeto

O objetivo é implementar um sistema de despacho de corridas para uma empresa fictícia de transporte por aplicativo, a "Cabe Aí".

A principal funcionalidade do sistema é a implementação de uma simulação de eventos discretos para processar demandas de corrida (pedidos de clientes). Além de alocar veículos, o sistema investiga e oferece corridas compartilhadas em tempo real.

A lógica para combinar corridas e criar um compartilhamento é baseada em um conjunto de critérios:

• Capacidade do veículo ($\eta$): Número máximo de passageiros por corrida compartilhada, limitando quantas demandas podem ser combinadas.

• Intervalo de tempo entre as partidas ($\delta$): Janela de tempo, a partir da primeira demanda do grupo, para considerar candidatas à combinação.

• Distância entre origens ($\alpha$): Distância máxima entre origens de pares de corridas combinadas, exigida conjuntivamente para todos os pares no grupo.

• Distância entre destinos ($\beta$): Distância máxima entre destinos de pares de corridas combinadas, exigida conjuntivamente para todos os pares no grupo.

• Eficiência mínima da corrida compartilhada ($\lambda$): Limiar mínimo da eficiência da corrida combinada. A eficiência mede a fração do deslocamento "útil" em relação à distância total percorrida (coleta + corrida). Por exemplo, uma corrida útil de 8km que exige um deslocamento total de 10km (incluindo coletas) tem uma eficiência de 80%.

Lógica de Combinação de Corridas

O algoritmo básico para formar corridas compartilhadas segue os seguintes passos para cada demanda ($c_0$)​ recebida:

1. Identificar Candidatas: Buscar todas as corridas ($c_1$...$c_n$) que ocorrem dentro do intervalo de tempo $\delta$ a partir de $c_0$. O número de corridas combinadas ($n+1$) não pode exceder a capacidade $\eta$.

2. Iniciar Conjunto: O conjunto de corridas a combinar, ($C$), começa apenas com $C={c_0}$.

3. Avaliar Candidatas: Para cada candidata ($c_i$) (que já satisfaz o critério de tempo $\delta$):

   3.1 Verificar Distâncias: Checar se $c_i$ satisfaz os critérios $\alpha$ (origens) e $\beta$ (destinos) em relação a todas as corridas já presentes em $C$.

   3.2 Verificar Eficiência: Se as distâncias forem válidas, ($c_i$) é temporariamente adicionada a $C$. A rota $r$ é recalculada (na versão básica, a ordem de coleta e entrega segue a ordem das demandas, $c_0$, $c_1$, ...). Em seguida, verifica-se se a eficiência da nova rota $r$ ainda é maior que $\lambda$.

   3.3 Falha: Se ($c_i$) falhar em qualquer um dos critérios (distância ou eficiência), ela é removida de $C$ e a formação da corrida $r$ é concluída, não avaliando mais candidatas para este grupo.

4. Agendar Corrida: Ao final da avaliação, a corrida $r$ definida (seja individual ou combinada) é adicionada ao conjunto de corridas $R$ e seu primeiro evento (a primeira coleta) é agendado no simulador.

Simulação de Eventos Discretos (SED)

A simulação processa as demandas de entrada, que são conhecidas antecipadamente. O sistema opera como uma Simulação de Eventos Discretos (SED), modelando a operação como uma sequência de eventos no tempo (como coletas e entregas). O simulador processa eventos em ordem estritamente cronológica , saltando o relógio diretamente para o próximo evento agendado. Após a execução de cada evento, o estado do sistema e as estatísticas são atualizadas.

🏗️ Estrutura e Componentes (TADs)

O projeto é modularizado em Tipos Abstratos de Dados (TADs) principais, conforme especificado no documento do trabalho:

• Demanda: Representa a solicitação de um cliente. Contém ID, tempo, origem, destino e o estado atual da corrida (ex: demandada, individual, combinada, concluída) .
• Parada: Armazena informações de uma parada específica, incluindo suas coordenadas, o tipo (embarque ou desembarque) e a qual demanda (passageiro) se refere .
• Trecho: Descreve o deslocamento entre duas paradas. Inclui as paradas de início e fim, tempo, distância e a natureza do trecho (coleta, entrega ou deslocamento).
• Corrida: Agrega uma ou mais demandas que foram combinadas (ou uma única, se for individual). Contém a lista de trechos que compõem a rota, a duração total, a distância e a eficiência.
• Escalonador: O núcleo da simulação de eventos discretos. É implementado como uma fila de prioridade (sugerido min-heap) que gerencia e processa os eventos (paradas) em ordem estritamente cronológica .

📁 Estrutura de Arquivos

A estrutura do repositório segue o modelo exigido para a entrega do TP:

.
├── bin
│   └── tp2.out
├── include
│   ├── corrida.h
│   ├── demanda.h
│   ├── escalonador.h
│   ├── parada.h
│   └── trecho.h
├── Makefile
├── obj
│   ├── corrida.o
│   ├── demanda.o
│   ├── escalonador.o
│   ├── main.o
│   ├── parada.o
│   └── trecho.o
├── README.md
└── src
    ├── corrida.cpp
    ├── demanda.cpp
    ├── escalonador.cpp
    ├── main.cpp
    ├── parada.cpp
    └── trecho.cpp

• src/: Contém os arquivos de código-fonte (.cpp).
• include/: Contém os arquivos de cabeçalho (.h).
• obj/: Diretório para onde vão os arquivos objeto (.o) gerados durante a compilação.
• bin/: Diretório onde o executável final é colocado.
• Makefile: Script de compilação do projeto.

🛠️ Compilação

O projeto utiliza um Makefile para gerenciar a compilação. Para compilar o sistema, execute o seguinte comando na raiz do diretório:

make all

Este comando compilará todos os arquivos-fonte, colocará os arquivos objeto em obj/ e criará o executável final tp2.out dentro da pasta bin/.

▶️ Execução

O programa é executado via linha de comando. Ele lê os parâmetros da simulação e a lista de demandas da entrada padrão (stdin).

Para executar o programa, você deve redirecionar um arquivo de entrada:

./bin/tp2.out < /caminho/para/seu/arquivo_de_entrada.txt

📥 Formato do Arquivo de Entrada

O arquivo de entrada deve seguir rigorosamente a especificação:

<eta>       // capacidade do veículo 
<gama>      // velocidade do veículo 
<delta>     // intervalo temporal máximo entre corridas combinadas 
<alfa>      // distância máxima entre origens de corridas combinadas 
<beta>      // distância máxima entre destinos de corridas combinadas 
<lambda>    // eficiência mínima da corrida combinada 
<numdemandas> // número de demandas a serem simuladas 
<iddemanda1> <tempo1> <origem1_x> <origem1_y> <destino1_x> <destino1_y> 
...
<iddemandan> <tempon> <origemn_x> <origemn_y> <destinon_x> <destinon_y> 

📤 Formato da Saída

A saída do programa é impressa na saída padrão (stdout). Para cada corrida concluída (seja ela individual ou combinada), o programa imprime uma única linha com as seguintes informações:

1. Tempo de conclusão da corrida
2. Distância total percorrida
3. Número de paradas
4. Sequência de coordenadas (x y) associadas às paradas

⚙️ Requisitos e Restrições Técnicas

• Linguagem: C++11.
• Restrição Principal: É terminantemente vetado o uso de estruturas de dados pré-implementadas pelas bibliotecas-padrão da linguagem (STL), como vector, list, queue, stack, etc.. Todas as estruturas de dados (notavelmente a fila de prioridade do escalonador) devem ser implementadas "do zero".
• Permitido: O uso do tipo string , bibliotecas de tratamento de exceções e de gerenciamento de memória é permitido.