Router Placement Optimization

Final Round, Hash Code 2017, with optimization algorithms.

Table of Contents

• Getting Started
  • Virtual Environment
  • Installing Dependencies
  • Run the Application
• Inside the Application
  • Main Menu
  • Run Algorithms
  • See Results
  • Legend
• Results
  • The best results with images

Getting Started

Virtual Environment

python3 -m venv venv
source venv/bin/activate

Installing Dependencies

pip install -r requirements.txt

Run the Application

python3 interface.py

Inside the Application

Main Menu

Run Algorithms

• You can select various input files and algorithms, each requiring specific parameters. These parameters can be adjusted using sliders or entered manually. The "Initial Solution" checkbox is enabled by default, as the optimization process typically starts with a pre-generated solution, which is the most time-consuming step.

• You have the option to cancel the execution of the algorithm at any time.

• After the algorithm completes, a pop-up notification is displayed confirming its successful execution.

See Results

• The See Results section is similar to the Run Algorithms section. You can select an input file and algorithm, and then sort the results by highest score, lowest score, or newest first for better analysis and comparison.

• By clicking the View button, a new window opens displaying an image of the solution, allowing for a detailed visualization of the results.

Legend

• For each result we store the file name with the parameters where for:
  • Hill Climb:
    • I stands for Max Iterations
  • Simulated Annealing:
    • T stands for Initial Temperature
    • C stands for Cooling Rate
    • N stands for Number of Iterations
  • Tabu Search:
    • I stands for Max Iterations
    • N stands for Neighborhood Size
    • T stands for Tabu Tenure
  • Genetic Algorithm:
    • P stands for Population Size
    • G stands for Generations
    • M stands for Mutation Rate
    • C stands for Crossover Probability
    • T stands for Tournament Size
    • N stands for Max Neighbor Attempts

Results

The following presents the results for each map and the corresponding time and algorithm. Due to time limitations, these results were obtained until April 6, 2025.

Algorithm	charleston_road	opera	rue_de_londres	lets_go_higher
skeleton_mst	score = 21954815, time = 5.44s	score = 120237124, time = 138.23s	score = 38345420, time = 12.48s	score = 289866922, time = 18003.01s
greedy_skeleton_mst	score = 21961830, time = 61.43s	score = 168480048, time = 5403.03s	score = 56313158, time = ?
simulated_annealing	score = 21956208, time = 150.02s	score = 127835094, time = 602.69s	score = 53242005, time = 150.06s
simulated_annealing_coverage		score = 165920015, time = 635.56s	score = 57210033, time = 152.60s
tabu_search		score = 162758034, time = 636.17s	score = 57885019, time = 152.82s
hill_climb	score = 21956053, time = 150.01s	score = 140740038, time = 605.09s	score = 53340004, time = 150.05s	score = 289870727, time = 189.57s
hill_climb_coverage		score = 162932093, time = 634.08s	score = 57424012, time = 152.56s
genetic_algorithm		score = 144089034, time = 1484.85s	score = 54726020, time = 699.95s

The best results with images

---

@IART_A1_2425