Gdje napuniti?

2023-10-01

Primjena dinamičkog programiranja u prometnim procesima s primjerom eksploatacije električnih vozila.

Sve političke agende, opće i stručne, govore da uvođenje EV (električnih vozila) predstavlja ključno prometno rješenje u promicanju zelenih politika. Europska unija nakon 2035. godine promišlja zabranu prodaje novih automobila i kombi vozila pogonjenih benzinskim i dizelskim gorivima. EV su osnovni preduvjet razvoja samoupravljivih automobila. Jedan dosta popularan Internet članak iz lipnja 2022. godine pokazuje veliki nesrazmjer razvoja potrebne infrastrukture za potporu EV kroz sliku opremljenosti pojedine EU zemlje elektro punionicama.

Pronašao sam još jedan zanimljiv Internet izvor koji opisuje karakteristike 346 električnih vozila i njihove domete. Prema podatcima iz srpnja 2023. godine najmanji domet od 135 km ima Renault Twingo Electric, a najveći od 685 km Lucid Air Dream Edition R. Ista stranica tvrdi da je prosječan domet 353 km (srpanj 2023.) pa ću i ja poštivati tu vrijednost. Istina je također da tehnologija ide veliki koracima naprijed; vjerojatno će baterije biti lakše i brže punjive (moguće i većinom samopunjive), ali na današnjoj razini razvoja EV dva su ključna pitanja za korisnike EV: (1) domet i (2) gdje napuniti. Ako mora na put s EV vozač mora unaprijed planirati kako i gdje puniti baterije – gdje su raspoložive elektro punionice. Od Zagreba do Splita udaljenost je od 390 km (kombinacija autoceste i državne ceste) do 410 km samo autocestom. Kako god kombiniramo, ako krenemo iz Zagreba prema Splitu (ili obrnuto) i natrag s punom baterijom, za ukupno prijeđenih 780 – 820 km trebat ćemo dva punjenja s EV prosječnog dometa 350 km, a s boljim (i puno skupljim) EV trebat ćemo (eventualno) jednom puniti baterije. U tvrtki gdje radim imamo jedno EV samo za prometovanje Zagrebom pa to iskustvo nije mjerodavno za ovu temu.

Dinamičko programiranje nije bilo sastavni dio matematičkih kolegija tijekom moje fakultetske izobrazbe. Prvi susret sam imao u sklopu poslijediplomskog studija. U životu sam "pješice" (olovka i papir) riješio dva zadatka iz područja dinamičkog programiranja. Cijelo to raspisivanje te "šuma" mogućih odluka u (među)fazama čini cijelim postupak (pre)napornim za (prosječnog) čovjeka, a bogomdanim za računala. Računala su stvorena za rekurzije, a dinamičko programiranje predstavlja rekurzivni postupak u kojem algoritam preuzima (najbolju) vrijednost prethodno izračunatog stanja (memoizacija), ako je potrebno za daljnje rješavanje. Najpoznatiji i sveprisutan algoritam dinamičkog programiranja nalazi se u aplikacijama izračuna najkraćeg puta u mreži; od internetskih besplatnih alata tipa Google Maps pa do komercijalnih navigacijskih aplikacija.

Ideja ove teme je ponuditi rješenje izbora mjesta za punjenje EV u slučaju putovanja na duljoj relaciji. Ako punimo baterije na kratkim relacijama onda beskorisno trošimo resurse, a ako to radimo izvan granice dometa onda moramo prijeći u štedljivi mod baterije i unaprijed planirati putovanje manjom brzinom. Ne možemo očekivati da će punionice biti raspoređene "optimalno"; baš u točkama područja dometa kretanja našeg vozila. Dinamičko programiranje poznaje takav problem koji se najčešće naziva "problem hotela". U Internet pretraživač utipkajte "dynamic programming hotel problem" i dobit ćete brojne video i tekstualne primjere ovog problema. Dosta je popularan jer omogućuje brojne varijacije uvjeta (ograničenja), a time i brojne stvarne aplikacije. Opći problem je sljedeći:

Može se penalizirati razlika ili kvadrat razlike između preporučene i ostvarene udaljenosti. Rješenje će se tražiti u kombinaciji putovanja gdje je takva penalizacija minimalna. Kako to izgleda pokazuje primjer s kvadratom udaljenosti. Preporučuje se putovati 10 jedinica dnevno. Između ishodišta i odredišta nalazi se puno hotela, a ideja je putovati s najmanje gubitaka i zaustavljanja. Ako prvi dan putujemo 6 jedinica, a drugi dan 9 jedinica, penalizacija je:

putovanje od ishodišta do h(1) = 6: [10 – (6 – 0)]^2 = 16,
putovanje od h(1) = 6 do h(2) = 15: [10 – (15 – 6)]^2 = 1.

Na prvi pogled nije nešto posebno, malo zdravog razuma, par izračuna i evo rješenja! Recimo da putujemo na (puno) veću udaljenost i da imamo na raspolaganju 15 hotela. Onda imamo "samo" 32.768 rješenja. Zato se koristi dinamičko programiranje i gornja jednadžba (funkcija cilja) da bi se u razumnom vremenu i s razumnim (ograničenim) računalnim resursima pronašlo optimalno rješenje.

Napravit ću jedan teoretski primjer, ali s dva dodatna atributa kako bi algoritam bio životniji (realniji). Prvi atribut je cijena svakog "hotela", odnosno cijena punjenja baterija u pojedinoj točki. Zašto? Zato jer je politika cijena punjenja EV heterogena na području EU, što pokazuje i sljedeća slika troška kWh za EV. Internet izvor iz kojeg je slika preuzeta ima datum objave 8. svibanj 2023. pa možemo reći da je slika aktualna u vrijeme nastanka ove teme. Neki dulji put na području EU može se dogoditi jedino kroz više zemalja, a to znači i različite cijene punjenja baterija.

Drugi čimbenik je povećani trošak u slučaju da se prođe maksimalna preporučena udaljenost, odnosno domet EV. Kako sam objasnio, u tom slučaju treba voziti sporije i "štedjeti bateriju" da bi se dosegla punionica izvan uobičajenog dometa EV, a to treba penalizirati.

Problem je prikazan u tablici. Treba proći 1.450 km. Između je na raspolaganju 15 elektro punionica s različitim troškovima usluge.

Kao i svi drugi (današnji) oportunisti iskoristio sam ChatGPT da mi "napiše" Python skriptu. Funkcija cilja je malo drugačija od prethodno prikazane. Sadrži dva čimbenika: prvi je nazvan costs – troškovi punjenja na svakoj punionici (prikazani u tablici), a drugi je penalty – povećani trošak putovanja ukoliko se koristi punionica izvan maksimalne preporučene udaljenosti. Stavio sam 30 za penalty, što je 3,75 puta više od troška najskuplje punionice. Domet (preporučena udaljenost) je 350. U slučaju vožnje dulje od 350 km aktivira se penalty vrijednost. Svako zainteresiran za dinamičko programiranje i rješenje ovog problema može na Internetu naći opis algoritma i razlog zašto se problem rješava od kraja prema početku. Nisam mijenjao nazive u izvornom programu pa se traži optimalan slijed "hotela", a ne "elektro punionica".

Rješenje je prikazano na slici. Položaj (visina) kvadrata i broj u kvadratu pokazuju troškove punjenja. Optimalan slijed putovanja je: 0, 1, 4, 7, 9, 13 i 17. Ukupan trošak je 25. Međusobne udaljenosti nisu veće od 350 km (najdulja je između 9. i 13. lokacije: 1.182 – 839 = 343 km) pa se ne aktivira penalty vrijednost.

Ako povećamo domet na 400 km, onda je rješenje: 0, 1, 5, 9, 13 i 17 s troškovima 19. Ako je penalty vrijednost 24 ili manja uz domet 350 km onda je optimalno rješenje: 0, 1 i 17 s troškovima 24. Radi se o nerealnom rješenju jer predmnijeva vožnju EV od 1.363 km bez zaustavljanja. Ove dvije varijacije ulaznih ograničenja pokazuju (ne)fleksibilnost modela za postizanje željenih (ne)realnih uvjeta. Brojne su i druge (ne)posredne mogućnosti prilagodbe modela stvarnim (željenim) uvjetima. Primjerice, ako želimo bezuvjetno zaustavljanje u nekoj točki (preuzimanje i/ili izmjena putnika i/ili tereta), stavit ćemo negativne troškove pa će rješenje sigurno uključiti i tu točku. U model možemo uključiti i vremenske veličine; penaliziramo punionice koje privlače više korisnika i treba (dulje) čekati ili imaju druga ograničenja, npr. manji broj brzih punionica pa je izvjesna vjerojatnost korištenja sporijeg punjača.

Izgledan je scenarij da će u vrijeme potpune dominacije EV, ako i kada do toga dođe, ovakvi izračuni biti (puno) manje potrebni ili čak i izlišni jer će tržište nuditi kapacitivnije baterije s puno bržim punjenjem, moguće i EV koja će imati razvijena rješenja samopunjivih baterija, a sve će to doprinijeti puno većem dometu u okruženju velikog broja punionica.

Da ovakvi modeli (promišljanja) nisu bez sadašnjosti/budućnosti pokazuje još jedna realna (praktična) primjena. Za prijevoz tereta na dulje relacije, kroz više država, hoteli se mogu zamijeniti benzinskim postajama, ili mjestima gdje vozači mogu (moraju) obaviti dnevnu stanku, dnevni i tjedni odmor (ako je dulje putovanje) i/ili mjestima gdje se nalaze štićena parkirališta za sigurno noćenje kamiona s teretom. Kada će nastupiti vrijeme električnih kamiona onda će ovakva planiranja biti nužan uvjet obavljanja posla.

Sve što uključuje kretanje, tehničko-tehnološka ograničenja prijevoznog sredstva (domet) i troškove ili neke druge ograničene parametre prometnog procesa, a puno je takvih problema (izazova, dilema) iz područja prometne tehnike, može naći odgovore na neka (ili mnoga) pitanja korištenjem metoda i modela dinamičkog programiranja.