Keliaujančio pirklio uždavinio Lietuvos miestams sprendimas

Jau kuris laikas domiuosi OR-Tools programinės įrangos rinkiniu, skirtu spręsti įvairius optimizacijos uždavinius. Keliaujančio pirklio uždaviniui spręsti skirtas algoritmas buvo pirmasis, kurį išmėginau. Šiame įraše pateikiamas Keliaujančio pirklio uždavinio 103 Lietuvos miestams sprendimas, t. y. trumpiausias kelias, kuriuo važiuojant galima aplankyti visus šiuos miestus. GitHub lt-towns-tsp svetainėje galima parsisiųsti skaičiavimui naudotą programos kodą. Skaičiavimui buvo panaudoti mano ankstesniame įraše pateikta atstumų tarp Lietuvos miestų lentelė. Sprendinio aukštos rezoliucijos žemėlapį galima peržiūrėti paspaudus šią nuorodą.

Taigi, norint trumpiausiu keliu apvažiuoti 103 Lietuvos miestus ir grįžti į miestą, nuo kurio prasidėjo kelionė, reiktų nuvažiuoti apie 2645 km., o miestus reiktų aplankyti tokia eilės tvarka:

  • Vilnius
  • Grigiškės
  • Lentvaris
  • Trakai
  • Rūdiškės
  • Baltoji Vokė
  • Šalčininkai
  • Eišiškės
  • Varėna
  • Daugai
  • Alytus
  • Simnas
  • Druskininkai
  • Veisiejai
  • Lazdijai
  • Kalvarija
  • Marijampolė
  • Kazlų Rūda
  • Vilkaviškis
  • Virbalis
  • Kybartai
  • Kudirkos Naumiestis
  • Šakiai
  • Gelgaudiškis
  • Jurbarkas
  • Smalininkai
  • Tauragė
  • Panemunė
  • Pagėgiai
  • Šilutė
  • Priekulė
  • Neringa
  • Klaipėda
  • Gargždai
  • Kretinga
  • Palanga
  • Skuodas
  • Salantai
  • Plungė
  • Rietavas
  • Šilalė
  • Skaudvilė
  • Kelmė
  • Tytuvėnai
  • Raseiniai
  • Ariogala
  • Vilkija
  • Ežerėlis
  • Kaunas
  • Garliava
  • Prienai
  • Birštonas
  • Jieznas
  • Kaišiadorys
  • Žiežmariai
  • Elektrėnai
  • Vievis
  • Širvintos
  • Molėtai
  • Utena
  • Anykščiai
  • Troškūnai
  • Kavarskas
  • Ukmergė
  • Jonava
  • Kėdainiai
  • Ramygala
  • Panevėžys
  • Šeduva
  • Radviliškis
  • Šiauliai
  • Kuršėnai
  • Užventis
  • Varniai
  • Telšiai
  • Seda
  • Mažeikiai
  • Viekšniai
  • Venta
  • Akmenė
  • Naujoji Akmenė
  • Žagarė
  • Joniškis
  • Pakruojis
  • Linkuva
  • Joniškėlis
  • Pasvalys
  • Biržai
  • Vabalninkas
  • Subačius
  • Kupiškis
  • Pandėlys
  • Rokiškis
  • Obeliai
  • Dusetos
  • Zarasai
  • Visaginas
  • Dūkštas
  • Ignalina
  • Švenčionėliai
  • Švenčionys
  • Pabradė
  • Nemenčinė
  • Vilnius