TSP — Problém obchodního cestujícího

Webová aplikace, která genetickými algoritmy hledá nejkratší okružní trasu přes zadaná města a celý průběh optimalizace vykresluje v reálném čase do plátna. Běží celá v prohlížeči — žádný server, žádná instalace.

▶︎ Živá verze: www.saiko.cz/tsp · 📄 Dokumentace (PDF)

Modernizovaná (TypeScript + Canvas) verze mého původního Java projektu z roku 2006. Původní Java aplikace zůstává pro referenci v adresáři OLD/.

---

Co to umí

• 4 genetické algoritmy k porovnání (viz níže)
• Živá vizualizace — trasa se překresluje, jak se zkracuje; výpočet běží ve Web Workeru, takže UI zůstává plynulé
• 12 map — reálná česká města (20–192, souřadnice v S‑JTSK) i geometrické „fraktální" mapy (kruh, spirála, čtverec, trojúhelník, čára)
• Nastavitelné parametry — velikost populace, míra mutace, růst populace, podmínka zastavení (max. „stáří" nejlepšího řešení), RMS cena
• Automatické zastavení, jakmile se nejlepší trasa přestane zlepšovat
• Export — PNG mapy a JSON s výslednou trasou

Genetické algoritmy

Každý engine staví na předchozím a přidává jednu schopnost:

Engine	Princip
Simple mutation	Náhodné prohazování měst, přežívá lepší polovina populace
Mutation + 2‑opt	Mutace + lokální heuristika 2‑opt (odstraňování křížení hran)
Greedy crossover	Křížení dvou rodičů podle levnější následující hrany
Greedy crossover + 2‑opt	Křížení + 2‑opt — nejsilnější kombinace

Cena trasy se počítá buď jako vzdálenost, nebo (volba RMS) jako její druhá mocnina — to penalizuje pár dlouhých úseků víc než mnoho krátkých.

Spuštění

npm install
npm run dev       # vývojový server na http://localhost:5173/
npm run build     # produkční build do dist/ (statické soubory)
npm run preview   # náhled produkčního buildu

Výsledek npm run build je čistě statický — nahraješ ho kamkoli (GitHub Pages, Netlify, …). base: "./" zajišťuje funkčnost i na sub‑cestě.

Galerie

Genetický algoritmus rekonstruuje strukturu mapy — u geometrických map je to obzvlášť názorné (zelená jsou města, červené startovní, bílá výsledná trasa):

Kruh (120)	Spirála (263)

Reálná mapa 192 českých měst:

Architektura

src/
  model/problem.ts     města + předpočítané matice vzdáleností / cen, délka trasy
  engines/engine.ts    4 enginy + heuristika 2‑opt a greedy crossover (žádné DOM)
  worker/ga.worker.ts  genetická smyčka na pozadí (start/pause/stop, auto‑stop)
  render/renderer.ts   vykreslování do Canvasu (fit transform, HiDPI)
  maps.ts              seznam map + parser CSV
  main.ts              propojení UI ↔ worker ↔ renderer
public/maps/*.csv      mapy měst

Stack: TypeScript (strict) + Vite + HTML5 Canvas, bez běhových závislostí. Genetický algoritmus běží v samostatném vláknu (Web Worker), hlavní vlákno jen překresluje aktuální nejlepší trasu přes requestAnimationFrame.

Korektnost enginů ověřuje headless test scripts/verify.ts (npx tsx scripts/verify.ts); screenshoty do docs/ generuje scripts/screenshots.mjs (headless Chromium / Playwright).

Původní Java verze

V OLD/ je původní desktopová aplikace (Java 8, Swing, Maven, PDF/XML reporty přes iText). Vznikla v roce 2006 a obsahuje stejné čtyři algoritmy i mapy. Historie souborů je zachována (přesun přes git mv).

Licence

GPL‑3.0‑or‑later · © Dušan Saiko