Optimizacija putnih planova temeljenih na LLM

6. lipnja 2025. – Alex Zhai, Software Engineer, i Pranjal Awasthi, Research Scientist, Google Research

U ovom članku predstavit ćemo metodu za rješavanje planiranja putovanja koristeći velika jezika modela (LLM) za interpretaciju kvalitativnih ciljeva i optimizacijske algoritme za rukovanje kvantitativnim ograničenjima. Mnogi stvarni zadaci planiranja uključuju teže “kvantitativne” ograničenja (npr. budžet ili zahtjevi za rasporedom) i mekše “kvalitativne” ciljeve (npr. korisničke preferencije izražene prirodnim jezikom). Razmislite o nekom tko planira tjedan dugo putovanje. Tipično, ovo planiranje bi bilo podložno raznim jasno kvantificiranim ograničenjima kao što su budžet, logistika putovanja i posjete atrakcijama samo kada su otvorene, uz brojne ograničenja temeljena na osobnim interesima i preferencijama koji nisu lako kvantificirati. Velika jezika modela (LLM) trenirani su na ogromnim skupovima podataka i unutarnje su ugrađene impresivne količine svjetskih znanja, često uključujući razumijevanje tipičnih ljudskih preferencija. Stoga su dobro sposobni uzeti u obzir nešto ne-kvantificirane dijelove planiranja putovanja, kao što je idealno vrijeme za posjetiti prirodnu ljepotu ili je li restoran dječji prijatelj. Međutim, manje su pouzdani pri rukovanju kvantitativnim logističkim ograničenjima koja mogu zahtijevati detaljne i aktualne informacije o stvarnom svijetu (npr. cijene autobusa, rasporedi vlaka itd.) ili složene međusobno djelujuće zahtjeve (npr. minimiziranje putovanja tijekom više dana). Kao rezultat, planovi generirani LLM-om mogu ponekad uključivati nepraktične elemente, kao što je posjeta muzeju koji bi mogao biti zatvoren do vremena kada se možete tamo doći.

Nedavno smo predstavili AI putne ideje u Pretraživanju, funkciju koja predlaže dnevne rasporede u odgovoru na upite za planiranjem putovanja. U ovom blogu opisat ćemo neki od radova koji su ušli u pokretanje ove funkcije: osiguravanje da generirani rasporedi budu praktični i izvršni. Naš rješenje koristi hibridni sustav koji koristi LLM za predlaganje početnog plana kombiniranog s algoritmom koji zajednički optimizira za sličnost s LLM planom i real-world faktore kao što su vrijeme putovanja i radno vrijeme. Ovaj pristup integrira sposobnost LLM-a za rukovanje mekim zahtjevima s algoritmičkom preciznošću potrebnom za ispunjavanje teških logističkih ograničenja.

Kako to radi

Dobiveni upit korisnika prvo se prenosi LLM-u, koji za naš sustav predstavlja verziju naših najnovijih Gemini modela. LLM predlaže početni putni plan koji uključuje popis aktivnosti uz relevantne detalje kao što su predloženo trajanje i razina važnosti za korisnikov upit. Početni plan je dobro prilagođen korisničkim interesima, ali može imati problema s izvršnošću, kao što je predlaganje ustanove koja je nedavno zatvorena.

!Diagram našeg hibridnog LLM i optimizacijskog sustava

LLM predlaže početni plan, a zatim izvršavamo optimizaciju ukljućujući real-world ograničenja za proizvodnju konačnog rasporeda. Da bismo riješili probleme s izvršnošću, dodali smo nekoliko komponenata iznad LLM-a. Prvo, osnova početnog rasporeda s aktualnim radnim vremenima i vremenima putovanja. Paralelno, koristimo pretraživačke pozadinske sustave za dohvaćanje dodatnih relevantnih aktivnosti koje poslužuju kao potencijalne zamjene u slučaju da LLM-predloženi plan treba biti modificiran. Početni plan, zamjenske aktivnosti i osnova podataka zatim se unose u optimizacijski algoritam za pronalaženje putnog plana sličnog početnom planu koji također osigurava izvršnost.

Postoji dva glavna stadija algoritma. Prvi stadij radi na razini jednog dana unutar putovanja. Za svaki podskup aktivnosti (do razumne maksimalne veličine), određujemo optimalni raspored tih aktivnosti u danu. Zatim mu dodijelimo ocjenu kvalitete koja se prvenstveno temelji na sličnosti s originalnim planom i izvršnosti rasporeda pod ograničenjima radnog vremena i vremena putovanja (npr. potpuno neizvršni raspored bi dobio ocjenu nula). Budući da je broj aktivnosti unutar dana malen, pronašli smo da se ocjene mogu izračunati potrošnim pretraživanjem s dovoljno optimiziranom implementacijom temeljenom na dinamičkom programiranju. U drugom stadiju, tražimo ukupni raspored (tj. skupove aktivnosti za svaki dan) koji maksimalizira ukupnu ocjenu dana pod ograničenjem da se aktivnosti dva dana ne mogu preklapati. To je težinski varijanta problema pakiranja skupova, koji je dobro poznat kao NP-potpun i stoga računalno neizvodljiv. Međutim, budući da se optimizacijski cilj pokušava ostati blizu početnog rasporeda po dizajnu, pronašli smo da su lokalni pretraživački heuristici djelotvorni. Počevši od početnog rasporeda, izvršavamo lokalne prilagodbe zamjenom aktivnosti između parova dana dokle god bi to povećalo ukupnu ocjenu. Ovaj postupak se ponavlja do konvergencije, rezultirajući konačnim rasporedom.

!Optimizacija rasporeda s lokalnim prilagodbama

FAQ

Koje su prednosti korištenja LLM-a za planiranje putovanja?

Korištenje LLM-a za planiranje putovanja pruža nekoliko prednosti. Prvo, LLM-ovi mogu interpretirati kvalitativne ciljeve izražene prirodnim jezikom, što omogućava korisnicima da izražavaju svoje preferencije na način koji im je najprirodniji. Drugo, LLM-ovi imaju unutarnje znanje o svijetu koje im omogućava da predlože relevantne aktivnosti i lokacije. Treće, LLM-ovi mogu brzo generirati više različitih planova, što korisnicima omogućava da izaberu onaj koji najbolje odgovara njihovim potrebama.

Koje su nedostaci korištenja LLM-a za planiranje putovanja?

Iako LLM-ovi pružaju mnoge prednosti, postoje i neki nedostaci. Prvo, LLM-ovi mogu biti neprecizni pri rukovanju kvantitativnim ograničenjima kao što su budžet i raspored. Drugo, LLM-ovi mogu generirati nepraktične planove ako nisu dobro osnovani s aktualnim informacijama. Treće, LLM-ovi mogu biti ograničeni u svojoj sposobnosti da razumiju složene međusobno djelujuće zahtjeve.

Kako se LLM-ovi koriste u kombinaciji s optimizacijskim algoritmima za planiranje putovanja?

LLM-ovi se koriste u kombinaciji s optimizacijskim algoritmima za planiranje putovanja tako da LLM generira početni plan koji se zatim optimizira s algoritmom koji uvažava kvantitativne ograničenja. Ovaj hibridni pristup omogućava da se iskoriste prednosti oba pristupa, pružajući korisnicima praktične i izvršne planove.

Koliko dugo traje optimizacija rasporeda?

Vrijeme potrebno za optimizaciju rasporeda ovisi o broju aktivnosti i složenosti ograničenja. U našem sustavu, optimizacija obično traje nekoliko sekundi, ali može biti duža za složenije planove s velikim brojem aktivnosti.