Airport Scheduling Problem (ASP)

This project solves the Airport Scheduling Problem (ASP) with independent runways, focusing on optimizing aircraft scheduling to improve efficiency and minimize conflicts.

🏆 Winner of the Copa APA 2024.2 (Team "Prova Surpesa (01/04)") A competition held between 27 undergraduate students from the Computer Science Center of the Federal University of Paraíba (CI/UFPB), where our algorithm won 1st place!

TODO

• Instance parser
• Feasibility check
• Constructive procedure
• Local search
• Perturbation
• Methaheuristic

Methaheuristics

• GRASP (Greedy Randomized Adaptative Search Procedure)
• GILS (GRASP Iterated Local Search)

Constructive procedure

• Cheapest Insertion
• Other

Local search

• VND (Variable Neighborhood Search) [MANDATORY]
• RVND (Randomized Variable Neighborhood Search)

Neighborhood

• INTRA-SWAP: swap two flights in the same runway
• INTER-SWAP: swap two flights in different runways
• INTRA-MOVE: move flight to different position in the same runway
• INTER-MOVE: move flight to a different runway

Perturbation

• RANDOM-INTER-SWAP: swap two random blocks of flights in different runways

Getting started

Prerequisites

• Meson Build System
• C++ 17

How to build the project

1. Setup release and debug builds:

meson setup build --buildtype=release
meson setup build_debug --buildtype=debug

2. Compile build:

meson compile -C <build or build_debug>

3. Run:

From the root directory:

./<build or build_debug>/src/asp <instance file path>

How to contribute

1. Create a branch with a name that describes the feature added:

git checkout -b <branch-name>

2. After the implementation of the feature, commit your changes with a semmantic commit message:

git add .
git commit -m "feat: <changes made>"

3. Then push local changes to the remote repository:

git push origin <branch-made>

4. In the remote repository, create a pull request.