Coursework for the Optimization Methods course (Master's, Faculty of Information and Communication Technology, Wrocław University of Science and Technology). Three deliverables, one theme — take a hard combinatorial problem and make a metaheuristic's behaviour observable: benchmark it, map it onto a real city, or animate the idea until it clicks.
Start here. This page is the guided tour of all three projects. Each one is self-contained and carries its own detailed README with build steps, results and how-to-run — open the folder for the deep dive.
GitHub's language bar counts bytes, so this repo is easy to misread as "JavaScript" — most of those bytes are generated map-coordinate data, not code. The actual stack:
| Area | Technologies |
|---|---|
| Solvers & benchmarks | C++17 (standard-library only) — the PFSP metaheuristics of first_project and the MDVRP solver of final_project; built with CMake and Make (MinGW g++) |
| Data, experiments, plots | Python 3 — NumPy, pandas, matplotlib, plus OSMnx + NetworkX to build routing instances from OpenStreetMap |
| Interactive web | JavaScript (ES6, no framework) + HTML5 Canvas for the 23 study-guide demos (exam_prep); Leaflet for the route-explorer maps (final_project) |
| Styling & docs | CSS3, Markdown, and a LaTeX / PDF report |
The profile card only ever shows a repo's single top language; the repo's own Languages bar shows the full breakdown above.
| # | Project | What it is | Built with |
|---|---|---|---|
| 1 | first_project | A PFSP metaheuristics benchmark — Greedy, Random Search, GA, Tabu Search and ILS raced on Taillard flow-shop instances, with CSV logs and publication-ready plots | C++17 · Python (matplotlib) |
| 2 | final_project | Multi-Depot Vehicle Routing on real road networks — a genetic-algorithm study with an operator bake-off, a workload-balancing LBBS variant, and an interactive route explorer | C++17 (std-only) · Python · Leaflet |
| 3 | exam_prep | An interactive study guide — 24 chapters from random search to state-of-the-art EAs, with 23 playable canvas demos | Vanilla JS · Canvas |
The course task brief lives at first_project/task0_OM.pdf.
The Permutation Flow Shop Scheduling Problem (PFSP): order a set of jobs on a line of
machines to minimise total flow time. It's NP-hard, so this project builds a small
benchmarking framework and races five strategies on Taillard-style instances
(tai20_5_0 … tai500_20_0): a deterministic Greedy baseline, Random Search, a
Genetic Algorithm, Tabu Search, and Iterated Local Search (NEH init +
insertion local search + perturbation). Each method is repeated across seeds, every run's
convergence is logged to CSV, and generate_plots.py turns the logs into comparison and
sensitivity figures.
ILS (purple) and Tabu Search (blue) drive total flow time well below the Greedy baseline (dotted); the GA plateaus a little higher and Random Search never really converges.
cd first_project
cmake -S . -B build && cmake --build build --config Release # or use the prebuilt pfsp.exe
./pfsp.exe # runs the benchmark → results/
python generate_plots.py # results/plots/*.png→ full details in first_project/README.md
The headline project: Multi-Depot Vehicle Routing solved on instances built from real OpenStreetMap drive networks, where cost is directed shortest-path road distance and capacity is enforced per trip. Three solvers — a nearest-neighbour greedy heuristic, a deliberately blind GA, and LBBS (a workload-balancing GA variant) — are compared through a full-factorial operator bake-off (32 combinations × 10 seeds). A Python instance generator and a standard-library-only C++17 solver meet only at a frozen CSV contract; the results ship as an interactive route explorer and a 32-page report.
The route explorer: real basemap, routes coloured by depot, live stats (distance, trips,
capacity use, feasibility) and a Drive/Evolve animation. Rebuild it with build_maps.py.
cd final_project
pip install -r instance_generator/requirements.txt
python instance_generator/generate_instances.py wroclaw # OSM → CSV contract
cd mdvrp && mingw32-make && cd .. # build the std-only solver
./mdvrp/mdvrp.exe ga wroclaw small . # run a solver
python instance_generator/build_maps.py # → output/maps/index.html→ full walkthrough, results tables and the bake-off in final_project/README.md (architecture spec in final_project/ARCHITECTURE.md)
The theory companion to the two coding projects: a browser app that walks the whole course — Foundations → Genetic Algorithms → Multi-objective → Metaheuristics & Swarm → Permutations, DE & Applications — as 24 chapters, each with a playable canvas demo for the ideas that only make sense in motion (gradient descent, CMA-ES, tournament selection, linkage trees, a Pareto front, a live PSO swarm, and more). No build, no dependencies — open the file.
start exam_prep\index.html # static site, runs offline→ chapter map and demo list in exam_prep/README.md
| Project | You need |
|---|---|
| first_project | C++17 (CMake or MinGW g++) + Python with pandas matplotlib numpy for the plots |
| final_project | C++17 (std-only, no libraries) + Python 3.10+ (osmnx, networkx, pandas, numpy, matplotlib); internet once, for the OSM download and map tiles |
| exam_prep | any modern browser — no build, runs offline |
Compiled .exe binaries and downloaded OSM instance CSVs are intentionally
.gitignored in final_project (platform-specific / regenerated on demand); the committed
output/solutions/* reports are the frozen paper artifacts and pass the repo's own
tools/verify_reports.py and verify_chromosomes.py checks.
.
├── first_project/ ← PFSP benchmark (C++17 + Python plots) · task0_OM.pdf
├── final_project/ ← MDVRP on real roads (C++17 solver + Python generator + map app + report)
├── exam_prep/ ← interactive 24-chapter study guide (static web app)
└── README.md ← you are here
Wrocław University of Science and Technology · FICT. Lectures by M. Przewoźniczek. The final project's authors and citation are listed in final_project/README.md.
- C++17 — implements the PFSP search strategies and the separate standard-library MDVRP solver.
- CMake and Make — build the two native optimisation programs from their respective source layouts.
- OSMnx, NetworkX, pandas, and NumPy — generate road-network routing instances and prepare the solver-facing data contract.
- JavaScript and CSS — power the route explorer that inspects generated MDVRP results in the browser.
- Implementing metaheuristics for flow-shop scheduling and multi-depot routing.
- Designing reproducible experiment inputs, CSV logs, and result-processing workflows.
- Separating a Python instance generator from a native solver through a stable file contract.
- Transforming road-network data into constrained routing instances.
- Creating an interactive viewer for inspecting route assignments and solver output.
MIT (LICENSE).