Optimalaus maršruto paieška yra viena iš pagrindinių informatikos problemų, dar vadinama orientacija erdvėje. Ji susijusi su trumpiausio arba efektyviausio kelio tarp dviejų taškų paieška ir yra plačiai pritaikoma įvairiose srityse, nuo robotikos iki transporto logistikos. Maršruto paieškos algoritmai yra vieni iš geriausiai žinomų ir dažniausiai naudojamų algoritmų.
Maršruto paieškos algoritmų taikymas ir sudėtingumas
Maršruto paieškos algoritmai naudojami robotikoje siekiant padėti autonominiams robotams orientuotis sudėtingoje aplinkoje. Vaizdo žaidimuose šie algoritmai valdo ne žaidėjo valdomų veikėjų (NPC) judėjimą. Kompiuteriniuose tinkluose jie naudojami greičiausiam duomenų perdavimo maršrutui tarp skirtingų tinklo mazgų rasti. Logistikoje maršruto parinkimas reiškia geriausio prekių gabenimo maršruto paiešką, leidžiančią sumažinti išlaidas ir kelionės laiką, kartu užtikrinant produktų saugumą. Maršruto paieškos algoritmai optimizuoja pristatymo transporto priemonių maršrutus, naudojami atsargų ir sandėlių valdymui, siekiant optimizuoti prekių išdėstymą bei užtikrinti, kad prekės būtų sandėliuojamos optimaliose vietose. Jie taip pat optimizuoja visą tiekimo grandinę nuo jos pradžios iki pristatymo.
Maršruto paieška žaidimuose ir tinkluose
Maršruto paieška yra itin svarbi technologija, leidžianti kurti įtraukiančius ir realistiškus žaidimų pasaulius, nes ji leidžia ne žaidėjo valdomiems personažams (NPC) ir vienetams judėti žaidimo pasaulyje efektyviai ir realistiškai. Ji naudojama priešų NPC elgesiui valdyti ir draugiškų vienetų judėjimui žaidimo pasaulyje kontroliuoti. Kelių paieškos algoritmai taip pat naudojami procedūriniam žemėlapių ar lygių generavimui. Tinklo maršrutizavime maršrutų paieška naudojama siekiant rasti optimalius duomenų paketų perdavimo maršrutus tinkle. Šie algoritmai leidžia tinklo administratoriams pagerinti tinklo našumą, atsižvelgiant į konkrečias aplinkybes, optimizuoti tinklo srautą ir sumažinti perkrovą.
Paslaugų kokybė ir patikimumas
Maršruto paieškos algoritmai taip pat naudojami tinklo srautui prioritetizuoti pagal paslaugų kokybės (QoS) reikalavimus. Pavyzdžiui, laiko atžvilgiu kritiškiems duomenims, tokiems kaip balso perdavimas per IP (VoIP) ar vaizdo srautai, suteikiamas prioritetas maršrutuojant per tinklą. Specialiai pritaikyti maršruto paieškos algoritmai naudojami tinklo srautui paskirstyti tarp kelių maršrutų. Be to, jie taikomi alternatyviems duomenų srauto maršrutams rasti tinklo gedimų atveju.
Maršruto paieška transporte
Transporto srityje maršruto paieška naudojama eismo srautams optimizuoti ir spūstims mažinti. Maršruto paieškos algoritmai padeda eismo inžinieriams projektuoti efektyvius eismo tinklus ir kurti strategijas eismo srautams gerinti. Jie naudojami optimaliems transporto priemonių maršrutams planuoti, išvengiant spūsties zonų. Šviesoforų optimizavimas gali būti atliekamas eismo signalų perjungimui optimizuoti, remiantis eismo modeliais ir eismo paklausa. Įvykių valdymas apima alternatyvių transporto priemonių maršrutų nustatymą avarijų ar kelių uždarymų atveju. Maršruto paieškos algoritmai taip pat gali būti naudojami viešojo transporto maršrutams ir tvarkaraščiams optimizuoti.
Maršruto paieškos sudėtingumas
Maršruto paieškos sudėtingumas kyla dėl konkrečios užduoties erdvės apribojimų. Tai reiškia, kad maršruto paieškos algoritmai turi atsižvelgti į visas kliūtis, trukdančias tiesioginiam keliui, ir su judėjimu erdvėje susijusias sąnaudas. Sąnaudos gali būti daugialypės, pavyzdžiui, kompromisas tarp energijos požiūriu palankesnių maršrutų, kuriems reikia daugiau laiko, ir greitesnių maršrutų, kuriems reikia daugiau energijos. Tam tikrais atvejais į maršrutą turi būti įtraukti apibrėžti taškai, o maršruto paieškos algoritmai užtikrina, kad vartotojas, judėdamas erdvėje, nevaikščiotų ratu.
Dinaminio programavimo metodas ir ITS
Šio straipsnio tikslas - aprašyti, kaip dinaminio programavimo metodas pritaikomas optimaliam maršrutui nustatyti naudojant Lietuvos žaliojo koridoriaus, kuris išsiskiria mažesne aplinkos tarša vežant įvairiarūšius krovinius, topologinio žemėlapio ir intelektinių transporto sistemų (ITS) įrenginių duomenis realiu laiku. Straipsniu siekiama pritaikyti dinaminio programavimo metodą optimaliam maršruto nustatymui, naudojant realaus laiko duomenis iš ITS įrangos. Tam tikslui buvo pritaikytas VBA kodas Bellmano-Fordo metodui spręsti optimalų maršrutą, atsižvelgiant į laiko, atstumo ir išmetamųjų teršalų kiekio optimalumo kriterijus.
Pradedančiųjų vadovas dinaminiam programavimui
Maršrutų planavimo evoliucija
Efektyvus maršruto planavimas - viena svarbiausių vežėjų darbo dalių, turinčių nemenką įtaką veiklos pelningumo rodikliams. Todėl amžių sandūroje smarkiai tobulėti ėmusios ryšio ir duomenų apdorojimo technologijos transporto sektoriuje buvo pasitiktos su išskėstomis rankomis. Proveržis šiose srityse leido sparčiai pagerinti ir vežėjų darbo įrankius, o dabartinių sistemų naudotojams ankstesnės kartos priemonės jau kelia šypseną. Kaip pažymi „VilniusTech“ universiteto Logistikos ir transporto vadybos katedros vedėjas doc. dr. Darius Bazaras, IT technologijų vystymasis buvo vienas kertinių pastarųjų dviejų dešimtmečių transporto sektoriaus rentabilumo augimo veiksnių. „Ypač pastaraisiais dešimtmečiais jos padėjo vežėjams gerokai greičiau priimti tikslesnius ir labiau pasiteisinančius sprendimus. Be to, modernios technologijos išlaisvino žmones nuo būtinybės priimti daugybę smulkiareikšmių sprendimų ir leido koncentruotis į svarbesnes sritis“, - sako mokslininkas.
Pirmosios paieškos ir matematiniai modeliai
Pirmieji linijiniai pervežimai planuoti paprasčiausiai pasirenkant trumpiausią kelią tarp pakrovimo ir iškrovimo vietų. Tiesa, jau tada vežėjai galėjo atsižvelgti į keletą kriterijų: važiuoti lėčiau trumpiausiu keliu arba rinktis ilgesnį, bet saugesnį ir kokybiškesnį maršrutą, kuriame galima išvystyti didesnį greitį. Anot D. Bazaro, sudėtingesnės apimties maršrutų planavimo uždaviniai imti spręsti atsiradus poreikiui išvežioti smulkesnes siuntas. Konkrečiai tai buvo būdinga pašto tarnyboms, ieškojusioms, kaip iš vieno išsiuntimo taško aplankyti keletą vartotojų didelės aprėpties geografinėje erdvėje. „Kildavo klausimas: o kaipgi apskaičiuoti, kokia seka labiau apsimoka aplankyti visus gavėjus per vieną kelionę? Taip prasidėjo optimizavimo paieškos. Pirmiausia buvo bandoma rasti trumpiausią kelią tarp taškų“, - prisimena pašnekovas.
Mokslininko teigimu, ieškant optimalaus maršruto, imti taikyti įvairūs iš anksčiau žinomi matematiniai modeliai. Vienas iš jų -
keliaujančio pirklio uždavinio sprendimo metodas
- turėjo aiškią prioritetinę nuostatą: visus taškus reikia aplankyti trumpiausiu keliu. Kitas - paprastas ir veiksmingas grafinis metodas, kuriam pakako tik ilgos liniuotės ir kokybiško žemėlapio. „Žemėlapyje fiksuojame išsiuntimo tašką ir visus nuo jo į viršų lankomus taškus. Tuomet vienu liniuotės galu sujungiame išsiuntimo tašką, o kitas jos galas turi būti laisvas, bet visi lankomi taškai turėtų atsidurti vienoje liniuotės pusėje. Sukame liniuote ratu pagal laikrodžio rodyklę: taškų palindimo po liniuote eiliškumas ir atitiks jų aplankymo eiliškumą. Tuo eiliškumu taškus sujungiame oro linija - dažniausiai ji yra žiedas, o žiedinis maršrutas yra optimalus trumpiausio maršruto pavyzdys. Tą oro liniją mes transformuojame į kelių bei gatvių tinklą ir gauname trumpiausią maršrutą, kuriuo aplankome visus reikalingus taškus sugaišdami mažiausiai laiko ir sąnaudų“, - atskleidžia D. Bazaras.
Sudėtingi maršrutų optimizavimo uždaviniai ir modernios technologijos
Vystantis pramonei, atsirado galybė kitokių probleminių aspektų ir maršrutų optimizavimo kriterijų, privertusių specialistus padėti į stalčius liniuotes bei žemėlapius ir pasitelkti šiuolaikines informacines technologijas. Kartais už patį pristatymo faktą svarbesnis tampa jo laikas. Maršrute gali atsirasti daugybė transporto kliūčių, todėl išaugo poreikis vertinti uždarytus kelius ir jų ar tiltų remontus, srauto judėjimo greičius. Rūpesčių gali sukelti ir daugiau dalykų. Galbūt pasirinktas trumpesnis ar patogesnis kelias, tačiau važiuojama per šalis, kuriose didžiausios kelių rinkliavos. Taip pat atsirado būtinybė įvertinti degalų kainas, atsižvelgiant į jų struktūros niuansus. Kartais netgi gera degalų kaina gali būti apgaulinga iliuzija: kitoje šalyje brangesnis kuras tampa pigesnis, įvertinus grąžintinus akcizus ir įvairias nuolaidas. „Kitaip sakant, turime daugiakriterį optimizavimo uždavinį, kurį būtina spręsti modernesniais būdais - vienas matematinis modelis tokių užduočių jau nebepaveža. Reikia remtis įvairių metodų visuma, panaudoti dirbtinį intelektą ir didžiuosius duomenis“, - teigia D. Bazaras.
Tokiems uždaviniams spręsti vežėjai renkasi šiuolaikinius maršrutų planavimo įrankius - programinės įrangos sistemas, kurios, įvedus visus svarbius kriterijus ir nustačius jų prioritetus, pateikia optimalų kelionės pasiūlymą. Naudojami įvairūs įrankiai, o vežėjai dažnai pasitelkia mobilumo paslaugų ir mokėjimų keliuose platformų, kaip antai „DKV Mobility“, sistemas, kurios siūlomos kaip platesnės paslaugos dalis. Pavyzdžiui, naudojantis „DKV Live“ realiojo laiko išmaniuoju skaitmeniniu asistentu su „DKV Maps“ įrankiu, koreguojant maršrutą galima įvertinti, ar norimos degalinės bus pakeliui, o jeigu tektų nusukti - ar papildomi kilometrai ir jiems skirtas laikas pasiteisins ekonomiškai. Pagal pageidaujamus parametrus nušlifuojamas galutinis maršrutas, kuris jau vykstant kelionei gali būti tebetobulinamas, atsižvelgiant į aktualias aplinkybes, ir pateikiamas vairuotojui realiuoju laiku.
Pradedančiųjų vadovas dinaminiam programavimui
Realiojo laiko duomenų proveržis ir ateities perspektyvos
D. Bazaras prisimena, kad pirmieji maršrutų planavimo programiniai įrankiai pradėti naudoti dar nepriklausomybės atgavimo pradžioje. Tačiau visi jie turėjo vieną opią problemą - jeigu programėlės nebūdavo prijungtos prie aktualios duomenų bazės, jos neįvertindavo realiojo laiko kriterijaus. Perversmas įvyko išplėtojus „Google Maps“ programėlę ir jos veiklos modelį pritaikius kitų gamintojų programinėje įrangoje. Nuolat realiuoju laiku atnaujinami duomenys tapo kertine šiuolaikinių maršrutų planavimo įrankių ašimi. O didžiųjų duomenų analizė ir spartus informacijos perdavimas naudojant skaitmeninę debesiją leidžia ir toliau didinti jų funkcionalumą.
Pavyzdžiui, optimizuoti maršrutą galima realiuoju laiku įvertinant vis daugiau naujų kriterijų. Štai „DKV Mobility“ naudotojams skirtoje platformoje pagal pateiktus parametrus įmanoma pasiskaičiuoti, kiek kainuoja nuvažiuoti norimą atstumą, vertinant kelių rinkliavų kaštus. Vienose šalyse mokesčių tarifą lemia sąstato svoris, kitose - ašių skaičius, trečiose gali būti vertinama viskas kartu ir dar atsižvelgiama į vilkiko variklio „Euro“ klasę. Pateikus šiuos duomenis, planavimo įrankis apskaičiuoja, kiek kainuos įveikti konkretų atstumą ir kiek laiko tam prireiks. Kitas siūlomas svarbus šių dienų kriterijus - galimybė pagal įvestą transporto priemonės informaciją nustatyti numatomą maršrute išmesti CO2 kiekį. Šis rodiklis svarbus vis platesniam vežėjų užsakovų ratui - jie gali lengviau pasiekti savo tvarumo tikslus investuodami į tam tikrus reikalavimus atitinkančias transporto paslaugas. „Iš esmės daugybė įmonių dėl to dabar siekia naudoti programinę įrangą, susietą su aktualaus laiko informacija. Jeigu tokia įranga deramai veikia, ji labai tinka maršrutams planuoti, nes apima du svarbiausius dalykus: optimizavimą pagal pasirinktus kriterijus ir realiojo laiko faktorių“, - pabrėžia D. Bazaras.
Žmogaus vaidmuo technologijų amžiuje
Nors gali pasirodyti, kad tobulėjant technologijoms reikia vis mažesnio žmogaus įsikišimo, mokslininkas neskuba su tuo sutikti. Jo teigimu, nemaža atsakomybė vis dar tenka ir transporto vadybininkui, turinčiam kritiškai vertinti visą gaunamą informaciją. „Tiesiog reikalingos kompetencijos šiek tiek pasikeitė. Prieš tris keturis dešimtmečius transporto vadybininkas turėjo valdyti kelis darbo priemonių blokus: dirbti su žemėlapiais, išmanyti įvairiausius žinynus, katalogus bei teisės aktus. Dabar visai tai tam tikra prasme atitinka duomenų bazių valdymą. Anksčiau vadybininko valdomos ryšio priemonės apėmė telefonus, faksus ir pan. Dabar gi matome didesnį poreikį išmanyti IT sistemas“, - atskleidžia pašnekovas.
Maršrutų optimizavimas transporto valdymo sistemose
Maršrutų optimizavimas yra vienas iš esminių veiksnių krovininio transporto ir krovinių gabenimo efektyvumo užtikrinimui. Įmonės, kurios užsiima transportavimu ir logistikos paslaugomis, gali pasinaudoti transporto valdymo sistemos „Terra Logistics“ suteikiama nauda, siekdamos pagerinti kelionės maršruto planavimą ir optimizuoti maršrutų planavimo programas. Viena iš svarbiausių funkcijų yra maršrutų paieška, kuri leidžia rasti optimalų maršrutą pagal įvairius kriterijus. Naudojant maršrutų planavimo modulį, galima stebėti skirtingas veiklas, tokias kaip pristatymo terminai, krovinio dydis ir svoris, eismo sąlygos bei transporto priemonių apribojimai keliuose. Be to, transporto valdymo sistema suteikia galimybę atlikti greičiausio maršruto paiešką, kuri leidžia rasti trumpiausią kelionės maršrutą, vengiant eismo spūsčių ir kelių darbų zonų. Maršrutų optimizavimas taip pat leidžia įmonėms planuoti ir valdyti transporto maršrutus efektyviau. Naudojant transporto valdymo sistemą, įmonės gali stebėti krovinio judėjimą realiu laiku, atnaujinti maršrutus, pasiekti didesnį veiksmingumą ir sumažinti tuščių vežimų skaičių. Galima teigti, kad maršrutų optimizavimas naudojant transporto valdymo sistemą yra nepakeičiamas įrankis įmonėms, turinčioms nuosavą transporto parką.
tags: #optimalaus #marsruto #nustatymas #taikant #belmano #ir