Flight Map Routing Project

Overview

The Flight Map Routing Project is a Python-based application that creates an efficient system for finding optimal flight routes between airports worldwide. Using graph algorithms and real-world flight data, the system provides users with multiple route options ranked by distance, connections, price, and environmental impact.

This project was developed as part of the CSC1108: Data Structures and Algorithms course, aimed at demonstrating practical implementations of fundamental data structures and algorithms in a real-world application.

Key Features

• Multiple Route Finding: Find various flight paths between any two airports in the database
• Advanced Routing Algorithms: Uses modified A* algorithm with Fibonacci heap for efficient pathfinding
• Custom Fibonacci Heap Implementation: Advanced priority queue data structure that significantly improves algorithmic efficiency compared to standard binary heaps
• Multi-criteria Optimization: Routes can be optimized for:
  • Shortest distance
  • Fewest connections
  • Lowest price
  • Most cost-effective path
  • Lowest CO2 emissions
• Interactive UI: User-friendly Streamlit interface with interactive maps
• Multiple Journey Types: Supports one-way, round-trip, and multi-city journeys
• Realistic Cost Models: Integrated pricing models and carbon emission calculations
• Currency Conversion: Automatic conversion between different currencies

Data Structures & Algorithms Used

• Graph Representation: Airports as vertices, flights as edges
• Fibonacci Heap: Priority queue implementation for efficient path finding
• Circular Doubly Linked Lists: For storing Fibonacci heap nodes and children
• A* Algorithm: Modified for K-shortest paths with multiple optimization criteria
• In-Memory Caching: For optimizing distance calculations between airports
• Quicksort: Custom implementation for sorting routes by different criteria

Installation and Setup

Prerequisites

• Python 3.8 or higher
• pip (Python package manager)

Setting Up Virtual Environment

# Create virtual environment
python -m venv venv

# Activate virtual environment
# For Windows
venv\Scripts\activate
# For macOS/Linux
source venv/bin/activate

Installing Dependencies

# Install all required packages
pip install -r requirements.txt

Running the Application

# Start the Streamlit application
streamlit run main.py --server.runOnSave true

The application will open in your default web browser at http://localhost:8501.

Project Structure

flight-routing/
├── main.py                       # Main Streamlit application
├── airport_network.py           # Core network logic and algorithms
├── fibonacci_heap.py            # Fibonacci heap implementation
├── models.py                    # Data models for airports, airlines, etc.
├── configuration.py             # Application configuration
├── sorting.py                   # Custom sorting implementation
├── ui_controller.py             # Interface between UI and backend
├── currency_api.py              # Currency conversion functionality
├── flight_ticket_price_api.py   # Flight pricing API integration
├── page/                        # UI pages
│   ├── single_flight_page.py    # One-way flight search UI
│   ├── return_flight_page.py    # Round-trip flight search UI
│   └── multi_city_page.py       # Multi-city flight search UI
├── static/                      # Static assets
│   ├── styles/                  # CSS styling
│   └── templates/               # HTML templates
├── utils/                       # Utility functions
│   ├── css_loader.py            # CSS loading utilities
│   ├── page_utils.py            # Page-related utilities
│   └── template_loader.py       # Template loading utilities
├── data/                        # Data files
│   └── airline_routes.json      # Airport and route data
└── requirements.txt             # Project dependencies

Algorithm Implementation Details

Modified A* K-Shortest Paths

Our implementation extends the traditional A* algorithm to find multiple optimal paths:

1. Heuristic Function: Uses Haversine distance calculation between coordinates
2. Path Penalties: Applies penalties for stops to balance direct vs. multi-stop routes
3. Optimization Criteria: Integrates multiple factors (distance, time, price, emissions)
4. Fibonacci Heap: Efficient priority queue implementation for fast node extraction
5. Path Reconstruction: Maintains path history for accurate route reconstruction

Dataset

The project uses airport and route data from:

• OpenFlights database (updated till June 2014)
• Jonty Airline Route Data

Additional synthetic data has been added for pricing and flight scheduling.

Future Improvements

• Real-time flight data integration
• Weather-based route optimization
• User accounts and saved routes
• Mobile application development
• Flight booking integration

Contributors

• Lucas Lee Jing Yi
• Lim Tze Kai
• Kieran Sim
• Fahrul Razie Annaqi
• Sheila Lim Yann Tsern
• Tan Yuewen, Sara

Acknowledgments

• OpenFlights for the airport and route data
• Streamlit for the web framework
• Our CSC1108 course instructor for guidance and support