Matematika prieš eismo spūstis: Pinavija: Apylankos į naudą. Vartiklis

Stanislovas Buteliauskas, generolo Jono Žemaičio Lietuvos karo akademijoje dėstantis transporto vadybą, sukūrė ir užpatentavo naujo tipo sankryžą, Nuo įprastų žiedinių sankryžų sumanytoji skiriasi tuo, kad ja važiuojančių automobilių srautai nesikerta. Būdama dviejų lygių, ji garantuoja tokią pat eismo kokybę kaip keturių lygių daugiaaukštė sankryža.

… pastačius įprastą sankryžą po poros dešimtmečių ją tenka rekonstruoti. Mat vos tik tam tikroje vietoje pagerėja važiavimo sąlygos, ima intensyvėti ir eismas.

„Mūsų sankryžoje didesni automobilių srautai nebaisūs, nes visomis kryptimis suformavus po 2 eismo juostas „Pinavija" tampa bene dvigubai laidesnė už kelią. Įprasta sankryža yra 3-4 kartus mažiau laidi už kelią", - aiškina S. Buteliauskas.

Kad būtų paprasta apskaičiuoti, ar tam tikroje vietoje verta statyti „Pinaviją", pasitelkti Vilniaus universiteto (VU) matematikai. Rimvydas Krasauskas, VU Matematikos ir informatikos fakulteto docentas, sukūrė algoritmą; jis padeda pritaikyti „Pinaviją" konkrečioms sąlygoms, apskaičiuoti preliminarią kainą.

Cituota pagal: A. Ranonytė. Kelius supynė į saugesnę sankryžą, Verslo žinios, 2009 09 25, Nr 184 (3084)

Pravažiavimų uždarymas ir šviesoforų išjungimas gali pagreitinti važiavimą mieste.

Tradicinis transporto valdymas laiko, kad, išlikus tam pačiam transporto priemonių kiekiui, daugiau kelių reiškia transporto srauto sumažėjimą. Todėl jie nustebo, kai Seule, vietoje šešių juostų greitkelio įrengus miesto parką, eismo padėtis mieste pagerėjo.

Tačiau tai paaiškina matematika, teigianti: tinkle, kuriame visos judančios esybės racionaliai ieško efektyviausio kelio, papildomi pralaidumai gali sumažinti bendrą tinklo efektyvumą. Seulas įrodė atvirkščia teiginį: pralaidumų sumažinimas padidino efektyvumą. Sankryza

Ši matematinė prielaida nustatyta dar 7-me dešimtm. Ir jos ištakos yra 3-io dešimtm. ekonominėje teorijoje, tačiau pati koncepcija niekada nebuvo patraukli transportininkams. Tačiau 21 a. ekonominės ir aplinkos apsaugos problemos šiai idėjai įkvepia naują kvapą: ribojant automobiliams skirtą vietą galima pagreitinti važiavimą daugeliui žmonių.

2008 m. rugsėjo mėn. „Physical Review Letters" M. Gastneris⁴⁾ su kolegomis, panaudodami hipotetinius ir realius kelių tinklus aiškina, kad vairuotojai, ieškantys trumpiausio kelio, neretai patenka į vadinamąją Nešo pusiausvyrą, kai nė vienas atskiras vairuotojas negali nieko pagerinti iš savo pusės. Mat Nešo pusiausvyra yra mažiau efektyvi nei pusiausvyra, kai vairuotojai elgiasi nesavanaudiškai (o visos grupės labui). „Anarchijos kaina" yra matas, apibrėžiantis neefektyvumą vairuotojams elgiantis savanaudiškai – ir ji gali būti labai aukšta (vairuotojai gali kelyje sugaišti per 30% daugiau laiko).

Sprendimas gali būti kai kurių kelių uždarymas. Mat tai apsunkina trumpiausio (ir savanaudiškiausio) kelio pasirinkimą atskiriems vairuotojams. Jie ima aklai ieškoti kitų alternatyvų. Kita „anarchija", pagreitinanti pravažiavimus, yra „nevaldomos gatvės". Tai šviesoforų išjungimas, kelių sužymėjimų panaikinimas. Šiaurės Europoje, kur tai įprasta, taip padidinamas saugumas kelyje bei transporto srautų greitis. Mat eismo reguliavimo nebuvimas padidina vairuotojų atsakomybės už savo veiksmus jausmą, tad jis daugiau stebi kelią, pėsčiuosius, kitus vairuotojus ir nejučia važiuoja lėčiau. Kaip pavyzdį, galima pateikti Kairą Egipte, kur, atrodytų, gatvėse tvyro visiškas chaosas, tačiau niekada nesimato avarijų.

Gali padėti ir naujos strategijos automobilių parkavimo srityje. Iki šiol buvo reikalaujama miesto rajonuose palikti minimalų plotą automobilių parkavimui. Dabartinė ekonominė situacija ir visuotinis klimato atšilimas verčia peržiūrėti tokius reikalavimus. Kai sunkiau rasti vietą pastatyti automobiliui, dalis gyventojų ima dažniau važinėti dviračiais ar vaikščioti pėsčiomis – o tai sumažina transporto srautus.

Nesuskaičiuojamos valandos praleidžiamos transporto spūstyse. Ypač erzina tos, kurios susidaro be jokios aiškios priežasties – nėra avarijos, sustojusio automobilio, nėra remonto darbų... Tokios spūstys gali susidaryti esant gausiam automobilių kiekiui, kai net nežymus trikdis (staigesnis stabdymas, pernelyg mažas tarpas tarp automobilių...) gali staiga išsilieti savaiminį visuotinį kamštį.

MIT matematikai sukūrė modelį, paaiškinantį kaip ir kokiomis aplinkybėmis susidaro tokios spūstys. Apie tai jie paskelbė „Physical Review", 2009 m. gegužės 26 d. Jų atradimas gali padėti kelininkams projektuojant kelius, kad juose tokių spūsčių susidarymas būtų minimizuotas.

Jų tyrimas parodė, kad tokias eismo spūstis galima aprašyti lygtimis, labai panašiomis į tas, kurios aprašo sprogimų sukeltas bangas. Skysčių mechanikoje naudojamos lygtyse eismo kamštis yra tarsi save atgaminanti vieniša banga. Kai toks kamštis susidaro, jį pašalinti beveik neįmanoma – belieka laukti, kol jis pats savaime nusilps. Tačiau galima taip suprojektuoti kelius, kad tikimybė tokiems kamščiams susidaryti būtų kuo mažesnė. Be to tasai modelis gali padėti nustatyti saugaus eismo greičio ribojimus bei taškus, kuriuose tokių kamščių susidarymo tikimybė yra didžiausia.

Masačūsetso Technologijų instituto komanda ėmėsi šio uždavinio 2008-ais, kai japonų tyrinėtojai eksperimentiškai parodė, kaip susidaro kamščiai žiediniame kelyje. Vairuotojams buvo nurodyta važiuoti 30 km/ val greičiu ir laikytis vienodo atstumo tarp automobilių. Gana greitai atsirado trikdžių ir susidarė spūstis. Tuo intensyvesnis buvo eismas, tuo greičiau formavosi kamštis.

Prof. A. R. Kasimovas, kurio pagrindinė tyrimų sritis yra sprogimų smūginės bangos, su komanda nustatė, kad transporto kamščiai turi „garso barjerą". Tai tarytum „juodųjų skylių" horizontas, žemiau kurio niekas negali ištrūkti (iš „skylės" arba spūsties). Pavyzdžiui, apie transporto judėjimo sąlygas už šio barjero negalima sužinoti esant kitoje barjero pusėje (ir taip bandyti aplenkti kamštį). O pakliuvus į kamštį, jokios vairuotojų pastangos negali jo pašalinti. Belieka tik laukti...

Pastaba: šiuos tyrimus finansavo JAV Oro pajėgų Mokslo tyrimų skyrius, Nacionalinis mokslo fondas (NSF) ir Kanados Gamtos mokslų ir inžinerijos tyrimų taryba.

Mokomės iš gamtos

Nematome skruzdėlių išsirikiavusių ir laukiančių eilėje - jos puikiai susidoroja su spūstimis ir padeda vienas kitam gerokai efektyviau judėti kolonijos viduje. Jų populiacija yra didžiausia žemėje, ir jos turi didžiausias tarp vabzdžių (250 tūkst. ląstelių) smegenis. Tad Dirkas Helbingas su komanda ir ėmėsi tirti, kaip jos sprendžia spūsčių problemą. Jie nustatė, kad grįžtanti skruzdė, susidūrusi iš skruzdėlyno išėjusia, šią nustumia į laisvesnį kelią. Atlikus kompiuterinį modeliavimą, nustatyta, kad jei skruzdės ir keliauja ilgesniu keliu, jos vis tiek greičiau pasiekia tikslą.

Tai ribotų resursų paskirstymo decentralizuotais individualiais sprendimais problema. Automobiliams reiktų leisti pranešti priešpriešine juosta važiuojantiems apie jų priekyje esančias eismo sąlygas, kad jie galėtų, reikalui esant, pakeisti maršrutą.

Bandos jausmas
Kelne atlikti bandymai parodė, kad oro uoste paranku elgtis kaip gyvūnų būriui. Atskridę keleiviai nežino kur eiti, tačiau pirmieji iš lėktuvo išlipę keleiviai pamato nuorodas, o kiti seka iš paskos, kliaudamiesi pirmaisiais. Kiekvienas kažkiek informacijos turintis asmuo gali tapti minios lyderiu, o minia gali sukaupti daugiau informacijos nei pavieniai individai. Tai vadinamojo minios intelekto pagrindas. Tai suprasti svabu – pvz., kai reikia evakuoti didelę žmonių minią. D. Helbingas su kolega ištyrė musulmonų elgesį Mekoje ir nustatė, kad artėjant masinės panikos pavojui, požymiai pasirodo gerokai anksčiau. Jie parengė programą, analizuojančią Mekoje vaizdo kameromis fiksuojamą piligrimų judėjimą. Padėčiai pablogėjus policija gali nukreipti minią į mažiau užtvindytas gatves. Problema tampa panaši į eismo spūsčių valdymą.

Visi esame susidūrę su „autobusų susibūrimo“ reiškiniu – kai autobusų stotelėje ilgai laukiame autobuso, o tada atvažiuoja iškart du. Šią problemą bandoma spręsti dešimtmečius – ir matematikai kūrė matematinius modelius, kad geriau suprastų, kodėl taip nutinka.

Autobusai susiburia, nes jų važiavimai labai nestabilūs. Kol jie važiuoja pagal grafiką, - viskas yra gerai. Tačiau tereikia autobusui atsilikti nuo grafiko, jis beveik neturi šansų grįžti į jį. Jis jis labiau atsilieka tol, kol jį paveja kitas autobusas. Beje, tas pats ir su autobuso skubėjimu – jis atvažiuoja vis anksčiau ir anksčiau – ir galiausiai paveja ankstesnį autobusą.

Tai susije su tuo, kiek keleivių autobusas paima stotelėse. Kai autobusas vėluoja, jų būna susirinkę daugiau, ir daugiau laiko užtrunka visų jų sulipimas, o kai autobusas skuba, jų susirenka mažiau – ir jie sulipa greičiau. Tai galima suprasti intuityviai ir be jokios matematikos.

Tai ką daryti?
1) leisti vėluojančiam autobusui praleisti stoteles, kai nėra išlipančių, arba riboti įlipančių keleivių kiekį (vargu, ar tai lengvai pasiekiama);
2) Kita strategija – numatyti maršrutui daugiau laiko nei reikia. Tas papildomas laikas – vadinamasis „dykinėjimas“ (slack) – suteikia lankstumo grafikui. Skubantys autobusai turi pristabdyti. Tačiau tai nepadeda vėluojantiems autobusams pavyti grafiko.
3) Sekti autobusų judėjimą realiu laiku. Autobusai tampa tarsi tarpusavyje „surišti“ – jei autobusai atsidūrę per arti, jiems patariama „pastumti“ arba „patraukti“ vienas kitą (t.y., judėti lėčiau ar greičiau). Tas instrukcijas gali paskaičiuoti per simuliacijas ir bandymus išvesti algoritmai.

Daugybė mūsų kasdien susiduria su problema, kaip įsiparkuoti į siaurą vietą. Londono universiteto prof. S. Blackburn‘as, bendradarbiaudamas su „Vauxhall Motors“, sukūrė matematinį modelį, parodantį vairuotojams, kaip reikia tinkamai parkuotis.

Šis darbas buvo atliktas, kai tyrimas atskleidė, kad 57% britų nepasitiki savo parkavimosi sugebėjimais, 32% labiau linkę važiuoti kitur, nei bandyti manevruoti sudėtingesnėje vietoje. „Vauxhall Motors“ 2009 m. lapkritį užsakė parašyti apžvalgą apie parkavimosi matematiką. Joje S. Blackburn‘as parodo parkavimosi geometriją, paskaičiuodamas minimaliai būtinos vietos ilgį. Formulė prasideda automobilio sukimosi spinduliu ir atstumu tarp automobilio priekinių ir galinių ratų. Tada, panaudojus automobilio priekį ir automobilio plotį, paskaičiuojama, kiek vietos reikia, kad įtilptų automobilis. Laikantis pateikiamų nurodymų, galima tiksliai nurodyti, kada reikia pasukti vairą, kad tiksliai įtilptumėte.

Atkarpos atsitiktinio užpildymo intevalais („parkavimo“) uždavinys pirmąkart nagrinėtas A. Renji [1]. x ilgio gatvėje atsitiktinai pastatomas automobilis, kurio ilgis 1. Jei x<1 parkavimas baigtas, o priešingu atveju pirmasis automobilis atsitiktinai užima vietą [t, t+1] – taip gatvę padalindamas į atkarpas [0, t] ir [t+1, x]. Čia laikoma, kad atsitiktinis dydis t tolygiai pasiskirstęs atkarpoje [0, x-1]. Toliau tos dvi gatvės dalys toliau pildomos automobiliais pagal tą patį principą. Bendras gatvėje tilpusių automobilių kiekis žymimas N_x. A. Renji parodė, kad matematinis vidurkis (viltis) bet kuriam n>=1 tenkina

Kartu buvo paskaičiuota ir konstanta l:
Parkavimosi lambda

Vėliau P. Ney [2] ir A. Dvoretskio su H. Robinsu [3] straipsniuose buvo nagrinėjami aukštesnių N_x laipsnių aspektai.

Nuorodos:

A. Renji. On a one-dimensional problem concerning space-flling// Publ. of the Math. Inst. of Hungarian Acad. of Sciences, 3, 1958, p. 109–127
P.E. Ney. A random interval filling problem// Annals of Math. Statist., 33, 1962, p. 702–718
A. Dvoretzky, H. Robbins. On the “parking” problem”// Publ. of the Math. Inst. of Hungarian Acad. of Sciences, 9, 1964, p. 209–226

Tokį klasikinį optimizavimo uždavinį sprendė fizikai P. Krapivskis iš Bostono un-to ir S. Redneris iš Santa Fe inst-to (straipsnis J. of Statistical Mechanics 2019 m. rugsėjo nr.). Geriausia parkavimo vieta yra ta, kurioje praleidžiama mažiausiai laiko. Idealiausia vieta yra prie įėjimo, tačiau gali tekti apsukti kelis ratus, kol tokia atsilaisvins. Tad efektyvi strategija yra nuspręsti, ar verta ieškoti artimos vietos, ar skubiai parkuotis kažkur kitur.

Straipsnyje nagrinėjamos trys paprastos parkavimosi strategijos į idealizuotą vienos eilės parkavimosi aikštelę. Kai parkuojamasi į pirmą laisvą vietą, tai jie vadina „nuolankia“ startegija – kai negaištama laiko parkavimosi vietos ieškojimui paliekant laisvas arti įėjimo esančias vietas. Kai ieškoma arčiausiai įėjimo esančios vietos, tai „optimistinė“ strategija – privažiuojama iki pat įėjimo, ir jei ten nerandama vietos, apsisukama iki arčiausios laisvos vietos. „Apdairi“ strategija yra per vidurį – praleidžiama pirma tinkama vieta, tikintis, kad atsiras kita artimesnė, o tokios neradus, vėl grįžtama.

Nepaisant strategijų paprastumo, teko panaudoti keletą technikų. Ir gana įdomu, kad nuolanki strategija aptinkama mikrovamzdeliuose gyvose ląstelėse – monomeras prisijungia mikrovamzdelio gale.

Optimistinei stategijai buvo sudaryta diferencialinė lygtis. Pradėję matematiškai aprašyti šį scenarijų, jie aptiko loginį triuką, labai supaprastinantį nagrinėjamų vietų skaičių. Apdairi strategija buvo gana komplikuota, nes vertė nagrinėti gana daug vietų. Todėl mokslininkai sukūrė simuliaciją, leidusią paskaičiuoti vidutinį laisvų vietų eilėje tankį.

Tad kuri strategija geriausia? Kaip ir nurodo pavadinimas – apdairi. Bendrai imant, ji užtikrina laiką artimą optimaliam. Nuolanki strategija yra juokingai neefektyvi.

Kaip visuomenėje iškyla idėjos?

David Weinberger‘io¹⁾ „Mašina ateities spėjimui“ (2011) pasakoja apie fiziko Dirk Helbing‘o²⁾, Ciuricho Technologijų instituto (Šveicarija) sociologijos katedros vedėjo, darbus. D. Helbing‘as pasiūlė idėją galingos kompiuterinės programos, bandančios modeliuoti globalaus masto sistemas ir taip būti tarsi „pasaulio krištolo rutuliu“.

Ir čia verta prisiminti Aizeko Azimovo Harį Seldoną³⁾,apylanka.htm „psicho-istoriką“, kurio šablonų nustatymo matematika „vežė“ garsiąją „Fondo“ seriją.

¹⁾ Deividas Veinbergeris (David Weinberger, g. 1950 m.) – amerikiečių technologas, dėstytojas ir komentatorius, „Cluetrain Manifesto“, tapusio „Interneto marketingo pradžiamoksliu“, bendraautorius. Jame teigiama, kad tradiciniai marketingo būdai beviltiškai paseno.

²⁾ Dirkas Helbingas (Dirk Helbing) – šveicarų fizikas ir sociologijos profesorius, taip pat užsiimantis modeliavimu ir simuliacijomis.

Dirkas Helbingas iš Šveicarijos federalinio technologijų instituto Ciuriche sako, kad reikia plastiškų institucijų, leidžiančių piliečiams bendradarbiauti ir spręsti problemas tiesiogine demokratija, naudojant kitos kartos socialines medijas. Tai veikia mažoje šalyje, tokioje kaip Šveicarija, ir pribrendo laikas eksportuoti šią praktiką į didesnes šalis. Tai atlikti leidžianti technologija jau auga...

Jis žinomas savo socialinės jėgos modeliu ir jo taikymu savaime besiorganizuojantiems reiškiniams, pvz., pėsčiųjų miniose, eismo spūstyse ir pan.

Jis yra ir pagrindinis entuziastas „Living Earth Simulator“ projekto, kurio tikslas imituoti viską, kas vyksta pasaulyje. Tai superkompiuterinė „didžiųjų duomenų“ (big data) sistema. Deja, EK galutiniame etape 2011 m. atmetė jo finansavimą. Dešimtys pasaulio kompiuterinių mokslų centrų pritarė šiai sistemai, tačiau kai kurie mokslininkai mano, kad šis projektas yra pernelyg ambicingas ir nerealus.

³⁾ Haris Seldonas (Hari Seldon) – A. Azimovo „Fondo“ serijos veikėjas pirmose dviejose knygose: „Fondo preliudija“ ir „Pakeliui į Fondą“. Jis gyveno 11988-12069 m. ir buvo matematiku tolimoje Helikono planetoje. Jis sukūrė psichoistorijos koncepciją, skirtą ateities prognozavimui, ir išpranašavo Galaktikos sąjungos žlugimą. Mokslo žinių išsaugojimui buvo sukurtas planas įsteigiant du Fondus ir surenkant mokslininkus Galaktikos enciklopedijos parašymui.
Jo garbei netgi pavadintas sąsiauris Saturno palydovo Titano Krakeno jūroje.

⁴⁾ Michael Gastner'is - kompiuterių specialistas iš Santa Fe Instituto (JAV).

⁵⁾ Frameproof - tam tikras kodas, kurį turintis vartotojas negali tvirtinti, kad jis panaudotas kitų vartotojų.
Pirmąkart 1998 m. panaudoti D. Boneh ir J. Shaw skaitmeninių „pirštų antspaudų“ („vandens ženklų“) kontekste apsaugant duomenis. Tarkim, kai norima apsaugoti kokį produktą, parenkama l fiksuotų pozicijų duomenyse ir kiekvienoje produkto kokijoje kiekvieną poziciją pažymi viena iš p skirtingų būsenų. Tokia pažymėtų pozicijų visuma vadinama „piršto antspaudu“ (fingerprint). Tačiau kai kurie susitarę vartotojai gali palyginti savo turimas kopijas ir nustatyti pažymėtas pozicijas, - ir tuo pasinaudodami sukurti nelegalias kopijas. „Piršto antspaudas“ vadinamas c-frameproof, jei iki c asmenų susitarimas negali turėti įtakos naudotojui, nepriklausančiam „koalicijai“.

⁶⁾ Kintamo ilgio masyvai (runlength constrained arrays) plačiai naudojami skaitmeninių duomenų įrašymuose ir perdavimuose.

Aslanas R. Kasimovas - Masačūsetso Technologijos Instituto (MIT) taikomosios matematikos dėstytojas (nuo 2005 m.). 1993 m. baigė Maskvos Inžinerinės fizikos institutą. 2004 m. Ilinojaus universitete gavo teorinės ir taikomosios fizikos daktaro laipsnį.

Pagrindinė tyrinėjimų sritis - įvairūs reiškiniai susiję su smūginėmis bangomis ir srautais, vykstančiais viršgarsiniu greičiu. Šiose srityse vis dar gausu neišspręstų uždavinių. Kai kurių jo naujausių tyrinėjimų pavyzdžiai:

Kriptografija: šifrų sudarymas ir dešifravimas. Daugiausia dėmesio skiria kriptoanalizei (šifrų įveikimui), ypač šiframs, kurie remiasi matematinėmis idėjomis. Domisi ir su kriptografija susijusiais kombinatoriniais objektais.

Kombinatorika: Dirba daugelyje sričių, susijusių su kriptografija (pvz., IPP kodais, „frameproof⁵⁾“ kodais, atsitiktinai persidengiančiais grafais) bei komunikacija (kintamo ilgio masyvai⁶⁾, tobulos hash funkcijos). Neretai panaudoja tikimybines bei klaidų koregavimo kodų teorijos technikas.

Grupių teorija: Daugiausia domina kombinatorinio pobūdžio klausimai (bet ne kombinatorinė grupių teorija!), ypač grupių perrinkimas (surandant asimptotines ribas baigtinių grupių izomorfinėse klasėse), baigtinių grupių poromis generavimu bei grupių panaudojimu kriptografijoje (bet paskutiniu metu yra dėl to skeptikas).