Uber ETA'ni qanday hisoblaydi

Bu darsda nima o‘rganasiz

Uber ilovasini ochasiz, manzilni yozasiz — va bir soniyadan kam vaqtda ekranda ikki raqam paydo bo‘ladi: “haydovchi 4 daqiqada keladi” va “manzilga 23 daqiqada yetasiz”. Bu raqamlarni hech kim alohida e’tiborga olmaydi. Lekin ular ortida butun bir tizim turadi: shahar yo‘l xaritasi graf sifatida, har bir haydovchi telefonidan har bir necha soniyada keladigan GPS nuqtalari, ulardan hisoblangan jonli tirbandlik, eng qisqa yo‘l algoritmlari va marshrut xatosini tuzatuvchi neyron tarmoq.

ETA (Estimated Time of Arrival — taxminiy yetib kelish vaqti) Uber’da faqat mijozga ko‘rsatiladigan raqam emas. U dispetcherlikning (qaysi haydovchini yuborish), narxning (safar narxi oldindan hisoblanadi), Uber Eats yetkazib berish vaqtining va hatto haydovchilar taqsimotining asosi. Shuning uchun ETA — Uber’ning eng ko‘p chaqiriladigan modeli: sekundiga yuz minglab so‘rov, har biri millisekundlarda.

Dars uchta savol atrofida quriladi.

Eng tez yo‘lni qanday topish mumkin — millisekundlarda? Dijkstra algoritmi to‘g‘ri, lekin katta grafda sekin. A*, ikki tomonlama qidiruv va Contraction Hierarchies bir necha ming barobar tezlashtiradi — bu darsning birinchi yarmi.

Yo‘lning “og‘irligi”ni qayerdan olamiz? Tezlik belgisi yolg‘on gapiradi: soat 18:00 da 60 km/soat yo‘lda mashinalar 12 km/soat bilan yuradi. Haqiqiy tezlik haydovchilarning GPS nuqtalaridan olinadi — lekin GPS shovqinli, nuqtalar siyrak va eskiradi.

Marshrut hisobi to‘g‘ri bo‘lsa ham, nega baribir xato? Svetoforlar, burilishlar, mijozni topish, to‘xtab turish joyi — grafda yo‘q narsalar. Bu yerda mashinaviy o‘rganish kiradi: u marshrut ETA’sini almashtirmaydi, balki uning xatosini bashorat qiladi.

Dars WhatsApp va Airbnb darslaridagi “real vaqt” va “hosila ko‘rinish” g‘oyalarining davomi, lekin yangi qatlam qo‘shadi: bu yerda javob hech qachon aniq emas — faqat qanchalik yaxshi taxmin ekani o‘lchanadi.

1. Muammo: “7 daqiqa” ortida nima bor

1.1 ETA qayerlarda ishlatiladi

Bu jadval ETA’ni oddiy “ko‘rsatiladigan raqam”dan tizimning valyutasiga aylantiradi. Dispetcherlik haydovchilarni masofa bo‘yicha emas, ETA bo‘yicha tanlaydi: daryoning narigi qirg‘og‘idagi 500 metr uzoqlikdagi haydovchi ko‘prikdan aylanib 12 daqiqada keladi, 2 km uzoqdagisi esa to‘g‘ri yo‘l bilan 4 daqiqada. Narx esa ETA’ga bevosita bog‘liq: safar 25 daqiqa deb hisoblansa-yu, 40 daqiqa davom etsa, oldindan aytilgan narx bilan kimdir zarar ko‘radi.

1.2 Talablar

Oxirgi qator muhim: ETA — kritik yo‘l. Airbnb’da qidiruv eskirsa ham bronlash ishlardi; Uber’da ETA servisi yiqilsa, yangi safar boshlab bo‘lmaydi. Shuning uchun darsning 10-bo‘limida ko‘ramizki, ETA tizimi bir necha qavat zaxira bilan quriladi: aniq javob bo‘lmasa — taxminiyroq, lekin har doim javob.

1.3 Konvert orqasidagi hisob

Hisob darhol bitta xulosani beradi: ETA — o‘qish yuki va juda katta o‘qish yuki. Safarning o‘zi sekundiga bir necha yuz; ETA esa undan ~300 barobar ko‘p. Har bir ETA so‘rovi yo‘l grafida qidiruv va ML model chaqiruvidan iborat bo‘lsa, ikkalasi ham millisekund tartibida bo‘lishi kerak — aks holda serverlar soni yuz minglab bo‘lardi.

Ikkinchi hisob darsning ikkinchi yarmidagi asosiy qiyinchilikni oldindan ko‘rsatadi: nuqtalar ko‘p, lekin notekis tarqalgan. Katta ko‘chada tezlikni ishonchli bilamiz, kichik ko‘chada esa oxirgi 5 daqiqada birorta ham mashina o‘tmagan bo‘lishi mumkin. Tunda — hatto katta ko‘chalarda ham. Jonli ma’lumot yetmagan joyda nima qilish — 7-bo‘limning markaziy savoli.

Uchinchi hisob yaxshi yangilik: yo‘l grafi kichik. Ma’lumot hajmi muammo emas; muammo — hisob tezligi. Grafni bitta serverga yuklab, unda sekundiga minglab eng qisqa yo‘l qidiruvi bajarish kerak. Bu darsning 5 va 6-bo‘limlaridagi algoritmik qadamlarni oqlaydi: ma’lumotni bo‘lish emas, qidiruvni aqlli qilish.

2. Nol nuqta: yo‘l grafi

ETA tizimining eng ichki mexanizmi — graf. Uni tushunmasdan qolgan hamma narsa (tirbandlik, ML, geo-indeks) “qora quti” bo‘lib qoladi.

2.1 Tugun, qirra va yo‘nalish

Shahar xaritasini graf sifatida tasvirlash oddiy ko‘rinadi: chorrahalar — tugunlar, ular orasidagi yo‘l bo‘laklari — qirralar. Lekin detallarda bir nechta muhim tanlov bor.

Qirralar yo‘nalishli. Ikki tomonlama ko‘cha — ikkita qirra (A→B va B→A), bir tomonlamasi — bitta. Ikki yo‘nalishning tezligi ham har xil: ertalab shaharga kiruvchi tomon tirband, chiquvchi bo‘sh.

Og‘irlik — vaqt, masofa emas. Qirra og‘irligi = uzunlik ÷ tezlik. Shu sababli “eng qisqa yo‘l” aslida “eng tez yo‘l”. Masofa ham saqlanadi (narx uchun kerak), lekin qidiruv vaqt bo‘yicha.

Burilishlar ham narxga ega. Chapga burilish (o‘ng tomonlama harakatda) qarama-qarshi oqimni kesib o‘tadi va svetofor kutishini qo‘shadi; ba’zi chorrahalarda burilish taqiqlangan. Buni ifodalashning ikki usuli bor:

1) Tugunga asoslangan graf + burilish jadvali:
   (kiruvchi qirra, chiquvchi qirra) -> jarima (soniya) yoki taqiq
   Kichik xotira, lekin qidiruv algoritmi murakkablashadi

2) Qirraga asoslangan graf ("edge-expanded", "line graph"):
   har bir yo'l bo'lagi — tugun; har bir ruxsat etilgan burilish — qirra
   Burilish jarimasi — oddiy qirra og'irligi; algoritm o'zgarmaydi
   Narxi: tugunlar ~2-3 barobar ko'p

Ko‘pchilik ishlab chiqarish dvigatellari ikkinchi usulni yoki uning ixcham variantini ishlatadi: algoritmlarni oddiy qoldirish xotiradan qimmatroq.

Bu hisob darsning keyingi qismi uchun muhim bir narsani ko‘rsatadi: yo‘l grafidagi og‘irliklar o‘rtacha qiymatlar va ularning xatosi tasodifiy emas, tizimli. Svetoforlarni har chorrahada modellashtirish mumkin emas (ularning ishlash rejimi ma’lum emas), lekin ularning o‘rtacha ta’sirini o‘tgan safarlardan o‘rganish mumkin. 5-bo‘limning 10–11-qadamlari aynan shu: marshrut hisobi “fizikani” beradi, ML esa qolgan tizimli xatoni.

2.2 Xarita qayerdan keladi

Graf o‘zi — xarita ma’lumotidan olingan hosila. Manbalar:

Uber dastlab tashqi xarita provayderlariga tayangan, 2015-yildan esa o‘z xarita jamoasini qurgan (xarita va marshrutlash kompaniyasi deCarta’ni sotib olish shu yilga to‘g‘ri keladi). Sabab ETA bilan bevosita bog‘liq: tashqi xaritadagi xato (yopilgan ko‘cha, noto‘g‘ri bir tomonlama belgisi) to‘g‘ridan-to‘g‘ri noto‘g‘ri marshrut va noto‘g‘ri narxga aylanadi, va uni tuzatish uchun boshqa kompaniyaga murojaat qilish kerak edi.

Burilish taqig'i tekshiruvi (har chorraha, har hafta):
  kutilgan: taqiqlangan burilishlar soni ~ 0 (xato GPS dan bir nechta)
  kuzatilgan: N ta iz aynan shu burilishni qilgan
  N > chegara (masalan, 50) va ulushi > 10% -> xarita jamoasiga navbat

Yopilgan yo'l tekshiruvi:
  bo'lakdagi kunlik izlar: oldingi 4 hafta o'rtachasi 300
  oxirgi 3 kun: 0, qo'shni bo'laklar odatdagidek
  -> "ehtimol yopilgan": marshrutlashda og'irlikni vaqtincha oshirish

2.3 Nuqtadan grafgacha: “qayerda turibman?”

Mijoz xaritada nuqta tanlaydi; haydovchi GPS koordinata yuboradi. Graf esa faqat tugun va qirralarni biladi. Shuning uchun har qidiruvdan oldin biriktirish (snapping) kerak: nuqtaga eng yaqin qirrani topish.

Bu oddiy ko‘rinadi, lekin ikkita tuzog‘i bor. Birinchisi — yo‘nalish: ko‘p qatorli yo‘lning qaysi tomonida turibsiz? Yo‘lning narigi tomonidagi mijozga yetish uchun haydovchi keyingi burilishgacha borib, qaytishi kerak — bu 2–5 daqiqa farq. Ikkinchisi — kirish joyi: katta bino yoki aeroportda mijoz turgan joy va mashina to‘xtay oladigan joy har xil.

Eng yaqin qirrani tez topish uchun geo-indeks kerak — bu yerda 5-bo‘limda batafsil ko‘radigan H3 kataklari yoki R-daraxt ishlatiladi: nuqta atrofidagi bir necha katakdagi qirralar olinadi va ular orasidan eng yaqini tanlanadi.

Bu tuzoq 5-bo‘limning 13-qadamida (“oxirgi 100 metr”) qayta uchraydi: ETA’ning katta qismi xatosi uzoq magistraldan emas, safarning boshi va oxiridan keladi.

3. v0: to‘g‘ri chiziq va o‘rtacha tezlik

Eng sodda ishlaydigan ETA grafsiz ham quriladi. Ikki nuqta orasidagi to‘g‘ri chiziq masofasini (Yer sharida — haversine formulasi) hisoblaymiz, uni yo‘llar egriligi uchun koeffitsientga ko‘paytiramiz va shahar o‘rtacha tezligiga bo‘lamiz:

from math import radians, sin, cos, asin, sqrt

R_KM = 6371.0
DETOUR = 1.35        # yo'llar to'g'ri chiziqdan ~35% uzun (shahar o'rtachasi)
AVG_KMH = 25.0       # shahar bo'yicha o'rtacha tezlik

def haversine_km(lat1, lon1, lat2, lon2):
    p1, p2 = radians(lat1), radians(lat2)
    dp, dl = p2 - p1, radians(lon2 - lon1)
    a = sin(dp / 2) ** 2 + cos(p1) * cos(p2) * sin(dl / 2) ** 2
    return 2 * R_KM * asin(sqrt(a))

def eta_minutes(a, b):
    km = haversine_km(*a, *b) * DETOUR
    return km / AVG_KMH * 60

def nearest_driver(rider, drivers):
    return min(drivers, key=lambda d: eta_minutes(d.pos, rider))

Bu kod ishlaydi. Kichik shaharda, tekis ko‘chalar to‘rida, tirbandliksiz paytda uning xatosi o‘rtacha 20–30% atrofida — ilk startap uchun yetarli. Bir millisekunddan kam vaqt oladi, xarita va server kerak emas, dispetcherlik ham shu funksiya bilan ishlaydi. Uber’ning ilk kunlari haqida ochiq ma’lumot kam, lekin ko‘plab taksi ilovalari aynan shunday boshlagan: “eng yaqin mashina” va “taxminan N daqiqa”.

Muammo shundaki, bu 20–30% o‘rtacha. Taqsimotning dumida xato 200–300% ga yetadi — va dispetcherlik aynan shu dumda noto‘g‘ri qaror qiladi.

4. Nima sindi

4.1 Daryo va ko‘prik

Koeffitsientni shahar bo‘yicha emas, hudud juftligi bo‘yicha o‘rganish mumkin (daryoning ikki qirg‘og‘i orasida — 2.5, bir qirg‘oq ichida — 1.3). Bu tuzatish, lekin u graf muammosini jadval bilan yashirish: jadval kattalashadi va baribir yangi ko‘prik yoki yopilgan ko‘chani bilmaydi. To‘g‘ri yechim — haqiqiy yo‘l grafi va unda eng tez yo‘l qidiruvi.

4.2 Tezlik belgisi yolg‘on gapiradi

Keyingi qadam tabiiy: 2-bo‘limdagi graf, og‘irlik = uzunlik ÷ tezlik chegarasi, va Dijkstra. Marshrut endi to‘g‘ri (ko‘prik orqali), lekin vaqt baribir xato.

Ikki xil xato bor. Birinchisi — muntazam: hech kim tezlik chegarasida yurmaydi, svetoforlar va burilishlar (2.1) vaqt qo‘shadi. Uni tarixiy o‘rtacha tezliklar bilan tuzatish mumkin. Ikkinchisi — vaqtga bog‘liq: bir xil yo‘l soat 11 da va 18 da uch barobar farq qiladi. Bu uchun bitta og‘irlik yetmaydi — og‘irlik kun va soatning funksiyasi bo‘lishi kerak. Uchinchisi esa hali ko‘rinmaydi: bugun soat 18:00 dagi tirbandlik o‘tgan seshanbadagidan boshqacha bo‘lishi mumkin (avariya, yomg‘ir, konsert). Bu jonli ma’lumot talab qiladi.

4.3 Dijkstra sekinlashadi

Dijkstra’ning muammosi — u yo‘nalishni bilmaydi. Manzil shimolda bo‘lsa ham, u janubga, g‘arbga va sharqqa teng tezlikda kengayadi, chunki faqat “manbadan qancha uzoq” ni biladi. Aylana ichidagi hamma tugunni ko‘rib chiqish — isrof: ularning ko‘pchiligi manzilga olib bormaydi. 5-bo‘lim 2–4-qadamlari bu isrofni bosqichma-bosqich yo‘q qiladi.

4.4 GPS shovqini: haydovchi qayerda?

Jonli tezlik va haydovchi joylashuvi GPS’dan keladi. GPS aniqligi ochiq joyda ~5 m, baland binolar orasida (“shahar kanyoni”) signal devorlardan qaytib, 30–50 m gacha xato qiladi. Tunnel va ko‘p qavatli yo‘l ayrilishlarida — signal umuman yo‘q.

Bu muammo alohida nuqtaga qarab hal qilinmaydi — nuqtalar ketma-ketligiga qarash kerak: mashina 4 soniyada 25 metr yon tomonga sakrab, keyin qaytib kela olmaydi. Bu 5-bo‘limning 6-qadamidagi map matching g‘oyasi.

4.5 Oxirgi yuz metr

Marshrut to‘g‘ri, tezliklar to‘g‘ri — lekin haydovchi baribir kechikdi. Nima uchun? U manzilga yetib keldi, lekin mijozni topa olmadi: bino ichki hovli orqali, kirish boshqa ko‘chadan, to‘xtash taqiqlangan. Yoki aeroportda — mashinalar uchun alohida chiqish yo‘li, piyodalar uchun boshqa.

Bu raqamlar faraz, lekin tuzilma ishlab chiqarish tizimlarida qayta-qayta tasdiqlangan: ETA’ning eng katta xatolari grafning “ichida” emas, grafning chegarasida — nuqta grafga qanday biriktirilgani va safar qanday boshlanib, qanday tugashida. Marshrutlash algoritmi bu haqda hech narsa bilmaydi. Buni o‘tgan safarlardan o‘rganish mumkin — ML qatlami (5-bo‘lim 10–11-qadamlar) shu uchun kerak.

5. Evolyutsiya: o‘n to‘rt qadam

Qadamlar uch guruhda. Qidiruv tezligi (1–5): Dijkstra’dan jonli og‘irliklarni ko‘taradigan ierarxik marshrutlashgacha. Og‘irliklar haqiqati (6–9): GPS nuqtalaridan jonli va tarixiy tezliklar, vaqtga bog‘liq marshrut. Grafdan tashqari (10–14): ML bilan xatoni tuzatish, geo-indeks va dispetcherlik, safarning boshi va oxiri, Uber Eats.

import heapq

def dijkstra(adj, s, t):
    """adj[u] = [(v, soniya), ...]. Qaytaradi: (vaqt, yo'l)."""
    dist, prev = {s: 0.0}, {}
    pq = [(0.0, s)]
    while pq:
        d, u = heapq.heappop(pq)
        if u == t:
            break                      # t "o'rnatildi" — javob aniq
        if d > dist[u]:
            continue                   # eskirgan navbat yozuvi
        for v, w in adj[u]:
            nd = d + w
            if nd < dist.get(v, float("inf")):
                dist[v], prev[v] = nd, u
                heapq.heappush(pq, (nd, v))
    path, x = [t], t
    while x != s:
        x = prev[x]; path.append(x)
    return dist[t], path[::-1]

def h(u):  # optimistik: hech qaysi yo'l bundan tez bo'lolmaydi
    return haversine_km(pos[u], pos[t]) / V_MAX_KMH * 3600

mu = eng yaxshi topilgan yo'l (ikki to'lqin kesishgan har bir qirrada yangilanadi)
To'xtash: oldinga navbat boshi + orqaga navbat boshi >= mu

P(nuqta | yo'l r) ~ exp( -0.5 x (masofa(nuqta, r) / sigma)^2 )
sigma ~ 5-10 m (ochiq joyda), 20-30 m (baland binolar orasida)

d = | yo'l_masofasi(r1 -> r2) - to'g'ri_chiziq(p1, p2) |
P(r2 | r1) ~ exp( -d / beta ),   beta ~ bir necha metr

nuqtalar: p1   p2   p3   p4   p5
nomzodlar: M,X  M,X  M,X  M,X  M,X      (M — magistral, X — xizmat yo'li)

p3 xizmat yo'liga 5 m yaqinroq (GPS xatosi), lekin:
  M -> X -> M o'tishi: yo'l bo'yicha ~400 m (burilish va qaytish),
  to'g'ri chiziq ~67 m -> ehtimol ~0
  M -> M -> M: yo'l bo'yicha 67 m -> ehtimol yuqori
Viterbi: M M M M M  (p3 ham magistralga)

v = (n x v_jonli + k x v_tarixiy) / (n + k)

yakuniy_ETA = marshrut_ETA + model(belgilar)
nishon (o'qitishda) = haqiqiy_vaqt - marshrut_ETA

ETA = max( tayyorlash_vaqti, kuryer -> restoran )
      + restoranda kutish va topshirish
      + restoran -> mijoz (safar ETA si)
      + binoga kirish va eshikkacha

6. Marshrutlash: ierarxiya ichida

5-bo‘limda Contraction Hierarchies natijasi berildi. Bu bo‘limda uning ichiga kiramiz: tugunlar qanday tartiblanadi, yorliqlar qachon kerak va nega qidiruv faqat “yuqoriga” yurib, baribir to‘g‘ri javob topadi.

6.1 Qisqartirish: bitta tugunni olib tashlash

Tugun v ni qisqartirishda uning har bir kiruvchi qo‘shnisi u va har bir chiquvchi qo‘shnisi w juftligini ko‘ramiz. Agar u → v → w yo‘li u dan w ga yagona eng qisqa yo‘l bo‘lsa, v ni olib tashlaganda bu yo‘l yo‘qoladi — shuning uchun yorliq u → w qo‘shiladi. Agar v siz ham shunday yoki qisqaroq yo‘l bo‘lsa (“guvoh yo‘l”, witness path), yorliq kerak emas.

Oldin:            u --3--> v --4--> w          u --9--> w  (to'g'ridan)
v qisqartirildi:  u --7--> w  (yorliq, chunki 7 < 9 va boshqa yo'l yo'q)

Oldin:            u --3--> v --4--> w          u --5--> x --1--> w
v qisqartirildi:  yorliq yo'q — guvoh yo'l u-x-w = 6 < 7

Guvoh yo‘lni izlash — u dan kichik, cheklangan Dijkstra (v ni chetlab). Cheklov muhim: agar izlashni erta to‘xtatsak, guvoh topilmay, ortiqcha yorliq qo‘shiladi — bu xato emas (javob baribir to‘g‘ri), faqat graf kattalashadi.

6.2 Tartib: kimni birinchi qisqartirish

Tartib sifati hamma narsani belgilaydi. Asosiy evristika — qirralar farqi (edge difference): tugunni qisqartirish qancha yorliq qo‘shadi, minus qancha qirra olib tashlaydi. Kam “zarar” beradigan tugunlar birinchi.

Qiziq kuzatuv: ierarxiya yo‘l turlarini bilmasdan ularni qayta kashf qiladi. Magistral tepada, chunki uni olib tashlash ko‘p yorliq talab qiladi — ko‘p eng qisqa yo‘llar undan o‘tadi. Bu “muhimlik”ning eng aniq ta’rifi: qancha eng qisqa yo‘l shu tugundan o‘tadi.

Oldinga qidiruv s dan: faqat daraja(v) > daraja(u) bo'lgan qirralar
Orqaga qidiruv t dan (teskari qirralar): xuddi shunday, faqat yuqoriga
Javob: min over v ( d_oldinga(v) + d_orqaga(v) )

6.3 Muqobil marshrutlar

Haydovchi ilovasi ko‘pincha bitta emas, 2–3 marshrut ko‘rsatadi: “eng tez”, “pullik yo‘lsiz”, “biroz uzoq, lekin barqaror”. Eng tez yo‘lni topish oson; yaxshi muqobil topish qiyinroq. Oddiy yondashuv (“eng tez yo‘lni taqiqlab, qayta qidirish”) deyarli bir xil yo‘lni beradi — bitta bo‘lak farq bilan.

Yaxshi muqobil uchta mezonga javob beradi: asosiy yo‘l bilan kam umumiy qism (masalan, 50% dan kam), vaqti ko‘p farq qilmaydi (masalan, 20% dan uzun emas), va mahalliy mantiqiy — kichik aylanmalar yo‘q (“magistraldan chiqib, 200 m yurib, qaytib kirish” kabi). Ikki tomonlama qidiruvdagi “uchrashuv nuqtalari” (via-node) nomzodlari orasidan shu mezonlarga mos keladiganlar tanlanadi.

7. Tirbandlik: GPS nuqtasidan tezlikkacha

7.1 Nimani o‘lchaymiz

GPS nuqtasida “tezlik” maydoni ham bor (telefon o‘zi hisoblaydi). Uni to‘g‘ridan-to‘g‘ri ishlatish jozibali, lekin bu lahzalik tezlik: svetoforda 0, keyin 50. Marshrutlash uchun kerak bo‘lgan narsa boshqa — bo‘lakni o‘tish vaqti, svetofor kutishini ham o‘z ichiga olgan.

Shu sababli 5-bo‘lim 6–7-qadamlaridagi quvur nuqtalarni emas, bo‘lak o‘tishlarini yig‘adi. Map matching bu yerda faqat “qaysi yo‘l” emas, “qaysi paytda kirdi va chiqdi” savoliga ham javob beradi (ikki nuqta orasidagi vaqt yo‘l uzunligi bo‘yicha taqsimlanadi).

7.2 Avariyani aniqlash

Jonli tezlik sekin o‘zgarsa — oddiy tirbandlik. Keskin tushsa — ehtimol avariya yoki yo‘l yopilishi. Ularni farqlash muhim: avariya bo‘lakni deyarli yopadi va marshrutlash undan butunlay qochishi kerak.

Navbat chegarasining orqaga harakat tezligi:
  w = (q_kelish - q_ketish) / (k_navbat - k_kelish)
  q — oqim (mashina/soat), k — zichlik (mashina/km)

Magistral: kelish oqimi 3 000 mash/soat, zichlik 30 mash/km
  avariyadan keyin o'tkazuvchanlik 1 000 mash/soat, navbat zichligi 150 mash/km
  w = (3 000 - 1 000) / (150 - 30) = ~17 km/soat
  -> 10 daqiqada navbat ~2.8 km orqaga cho'ziladi

7.3 Kam ma’lumot va tunda

Tun soat 3 da shaharda haydovchilar kam — jonli kuzatuvlar deyarli yo‘q. 8-qadamdagi aralashtirish avtomatik ravishda tarixiy profilga o‘tadi. Lekin tarixiy profil ham tunda kam kuzatuvdan qurilgan — ishonchsiz. Bu yerda yana bir qatlam yordam beradi: ierarxik zaxira.

Bo'lak, shu 15 daqiqalik oraliq (kuzatuvlar yetarli bo'lsa)
  -> bo'lak, shu soat (4 ta oraliq birlashtirilgan)
    -> bo'lak, "tun" guruhi
      -> yo'l turi + shahar bo'yicha o'rtacha (masalan, "tunda magistral")
        -> tezlik chegarasi x koeffitsient

Har bosqichda kuzatuvlar soni tekshiriladi. Bu Airbnb darsidagi narx tavsiyasi va Reddit’dagi yangi post reytingi bilan bir xil g‘oya: kam ma’lumotda umumiyroq guruhga tayanish.

8. ML qatlami: ma’lumot, baholash va xizmat

8.1 “Haqiqiy vaqt” nima?

ML modeli haqiqiy vaqtdan o‘rganadi. Lekin safarning “haqiqiy” davomiyligi qaysi lahzadan qaysi lahzagacha? Bu savol ko‘rinishidan oddiy, lekin nishon (label) ta’rifi modelning nimani o‘rganishini to‘liq belgilaydi.

Birinchi qatordagi tuzoq qiziq: agar haydovchilar “yetib keldim” tugmasini 100 metr oldin bossa (mijoz tezroq chiqishi uchun), haqiqiy nishonlar muntazam qisqa bo‘ladi va model ETA’ni kam ko‘rsatishni o‘rganadi. Yechim — nishonni tugmadan emas, GPS izidan olish: mashina olib ketish joyiga 30 metr yaqinlashib, to‘xtagan lahza.

8.2 O‘qitish va xizmat bir xil ko‘rishi kerak

Eng xavfli xato — o‘qitish va xizmat nomuvofiqligi (training-serving skew). Misol: o‘qitishda “hududdagi joriy o‘rtacha tezlik” belgisi kun oxirida, to‘liq ma’lumot bilan hisoblangan; xizmatda esa u real vaqtda, 2 daqiqa kechikish bilan keladi. Model o‘qitishda “kelajakni ko‘rgan” belgiga o‘rgangan, xizmatda esa u yo‘q.

8.3 Baholash: bitta raqam yetmaydi

Oxirgi qatorda MAPE (foizli xato) — lekin faqat qisqa safarlarda ehtiyotkorlik bilan: 1 daqiqalik ETA da 1 daqiqa xato — 100%, 60 daqiqalik ETA da — 1.7%. Foizli ko‘rsatkich qisqa safarlarni haddan ortiq jazolaydi, mutlaq ko‘rsatkich esa uzun safarlarni. Shuning uchun baholash segmentlar bo‘yicha: kelish va safar alohida, shahar bo‘yicha, masofa guruhlari bo‘yicha, aeroport va oddiy joylar alohida.

8.4 Onlayn tajriba: ETA hamma narsaga ta’sir qiladi

Yangi ETA modelini qanday sinash kerak? Oddiy A/B test: foydalanuvchilarning yarmi yangi model, yarmi eski. Lekin ETA oddiy xususiyat emas.

1. Vaqt bo'yicha almashtirish (switchback):
   butun shahar 30 daqiqa yangi model, 30 daqiqa eski, tasodifiy tartibda
   + ifloslanish yo'q (bir vaqtda faqat bitta model)
   - soatlar orasidagi farqlar shovqin qo'shadi -> ko'p hafta kerak

2. Geografik bo'lish:
   bir tuman — yangi, boshqasi — eski
   - tumanlar har xil; chegarada ifloslanish

3. Soya rejimi (shadow):
   yangi model hisoblaydi, lekin natijasi ishlatilmaydi — faqat yoziladi
   + xavfsiz: bashorat aniqligini haqiqat bilan solishtirish mumkin
   - dispetcherlikka ta'sirini ko'rsatmaydi

9. Bugungi arxitektura

Diagrammada ikki oqim bor. So‘rov oqimi yuqoridan pastga: dispetcherlik ETA servisidan so‘raydi, u marshrutlashdan va modeldan. Ma’lumot oqimi pastdan yuqoriga: haydovchi GPS’i → quvurlar → og‘irliklar → marshrut. Bir xil haydovchi ilovasi ikkala oqimning ikki uchida: u ETA so‘raydi va shu bilan birga ETA uchun ma’lumot beradi. Bu o‘z-o‘zini ta’minlovchi halqa: qancha ko‘p safar — shuncha aniq tezlik — shuncha yaxshi ETA — shuncha samarali dispetcherlik — shuncha ko‘p safar.

Tarixdagi eng muhim burilish — 2015-yil. Undan oldin xarita va marshrut tashqi provayderdan olingan “kommunal xizmat” edi. Undan keyin — asosiy mahsulotning bir qismi. Sabab 1-bo‘limdagi jadvalda: ETA dispetcherlik, narx va Eats’ning kiritmasi. Kompaniyaning asosiy iqtisodiy qarorlari boshqa birovning xaritasiga bog‘liq bo‘lishi mumkin emas edi.

10. Ishonchlilik: har doim javob bor

10.1 Zaxira zinapoyasi

1.2-bo‘limda aytilgandek, ETA yo‘q — safar yo‘q. Shuning uchun ETA servisi “yiqilmaydi”, balki sifat pasayadi: har pog‘onada kamroq aniq, lekin tezroq va ishonchliroq javob.

Zinapoyaning har pog‘onasi alohida sinovdan o‘tkaziladi. Zaxira yo‘lining eng katta xavfi — u yillar davomida ishlatilmaydi va kerak bo‘lganda buzilgan bo‘lib chiqadi (jadval yangilanmagan, format o‘zgargan). Himoya: har kuni kichik ulush so‘rovlar ataylab pastki pog‘onalar orqali o‘tkaziladi va ularning aniqligi kuzatiladi.

10.2 Yomg‘irli juma kechqurun

Bu kun tizimning barcha qismlarini birga sinaydi: jonli quvurning tezligi, tarixiy va jonli ma’lumotni aralashtirish, ML’dagi tashqi belgilar, avariyani aniqlash va servislarning kengayishi. Eng muhim kuzatuv — 18:10 qatori: bunday kunda ETA katta bo‘ladi, va tizimning vazifasi uni kichik ko‘rsatish emas, to‘g‘ri ko‘rsatish. Kam ko‘rsatilgan ETA mijozni kutishga undaydi va keyin bekor qilishga — bu ham mijozni, ham haydovchini yo‘qotadi.

1. Mijoz manzilni kiritdi -> bitta hisob: marshrut, ETA, masofa, narx
2. Natija taklif sifatida saqlanadi: quote_id, muddati (masalan, 5 daqiqa)
3. Ekran ham, buyurtma ham shu quote_id ga ishora qiladi
4. "Buyurtma berish" bosilganda narx qayta hisoblanmaydi —
   taklifdagi qiymat ishlatiladi (muddati o'tmagan bo'lsa)

11. Xavfsizlik va maxfiylik

11.1 GPS’ni aldash

Haydovchi telefoni — ma’lumot manbai. Va har qanday tashqi ma’lumot manbai kabi, u qasddan buzilishi mumkin. GPS joylashuvini soxtalashtiruvchi ilovalar keng tarqalgan. Nima uchun haydovchi buni qiladi?

Tezlik agregatsiyasi uchun mediana (7-qadam) va “turli haydovchilar” sharti (7.2) tabiiy himoya beradi: bitta soxta haydovchi bo‘lak tezligini o‘zgartira olmaydi. Buning uchun ko‘plab muvofiqlashtirilgan soxta hisoblar kerak — bu firibgarlikka qarshi tizimning (Airbnb darsi, 11-bo‘lim) vazifasi.

11.2 Joylashuv — eng sezgir ma’lumot

GPS izlari — odamning qayerda yashashi, ishlashi, kim bilan uchrashishi haqidagi ma’lumot. Mijozning safarlar tarixi uning uy manzilini, ish joyini va odatlarini ochib beradi. 2014-yilda Uber ichki vositasi orqali xodimlarning mijozlar joylashuvini ko‘rishi (“God View” deb atalgan) haqidagi xabarlar katta janjalga sabab bo‘ldi va keyinchalik kirish nazoratini kuchaytirishga olib keldi.

Xom GPS nuqtasi:      haydovchi_id, safar_id, vaqt, lat, lon, ...
                      -> faqat map matching bosqichida, qisqa muddat

Bo'lak o'tishi:       bo'lak_id, kirish_vaqti, o'tish_vaqti, holat
                      -> haydovchi_id yo'q; faqat "turli haydovchi" sanog'i
                         uchun qisqa muddatli xesh (soatlik tuz bilan)

Agregat tezlik:       bo'lak_id, oraliq, mediana, n
                      -> hech qanday shaxsiy ma'lumot yo'q

12. Iqtisod: bitta daqiqaning narxi

ETA hisoblashning o‘zi arzon. Qimmat narsa — ETA xatosi. Bu bo‘limda ikkalasini hisoblaymiz va nima uchun Uber ETA aniqligiga katta sarmoya kiritishini ko‘ramiz.

Ikki hisob nisbati — ETA iqtisodining mohiyati: hisob narxi va aniqlik qiymati o‘rtasida uch-to‘rt tartib farq bor. Model 10 barobar qimmat bo‘lib, xatoni 1% kamaytirsa ham, bu foydali. Shuning uchun DeepETA kabi og‘irroq model — kechikish byudjetiga sig‘sa — iqtisodiy jihatdan aniq qaror.

Narx formulasi (soddalashtirilgan):
  narx = asosiy + a x masofa + b x vaqt,   b = 0.2 $/daqiqa

Bashorat: 25 daqiqa -> vaqt qismi 5.0 $
Haqiqat: 32 daqiqa  -> haydovchiga vaqt qismi 6.4 $
Farq: 1.4 $ platforma zarari (bitta safarda)

Agar ETA muntazam 10% kam bo'lsa (bias -10%):
  o'rtacha safar 20 daq -> 2 daq x 0.2 $ = 0.4 $ har safarda
  31 M safar/kun x (faraz: 50% oldindan narxli) x 0.4 $ = ~6 M $/kun

13. Sig‘im rejalashtirish

13.1 Marshrut serverlari: hudud bo‘yicha bo‘lish

Graf kichik (1.3), lekin dunyo grafi va unga bog‘liq ma’lumotlar (bo‘laklar, profillar, sozlangan og‘irliklar) bitta serverga sig‘ishi qiyin, va sig‘sa ham — samarasiz: Toshkentdagi so‘rov uchun Braziliya yo‘llari kerak emas. Tabiiy bo‘lish — hudud (shahar yoki metropoliya).

13.2 GPS quvuri

Ikki xil bo‘limlash kaliti — haydovchi va bo‘lak — oqimli tizimlarning klassik naqshi. Map matching haydovchi izining ketma-ketligini talab qiladi (holat — izning oxiri), agregatsiya esa bo‘lak bo‘yicha yig‘ishni. Ular orasida qayta bo‘limlash (Kafka mavzusidan boshqa mavzuga) turadi. Bu WhatsApp darsidagi “foydalanuvchi bo‘yicha va guruh bo‘yicha” ikki xil kalitga o‘xshaydi.

1. Versiyali og'irliklar:
   har yangilanish — versiya raqami (masalan, daqiqa belgisi)
   so'rov "v=17:42" bilan keladi, server shu versiyani ishlatadi
   serverlar oxirgi 2-3 versiyani saqlaydi
   -> bir mijozning so'rovlari izchil

2. Yopishqoq marshrutlash:
   bitta seans so'rovlari bitta serverga (seans ID bo'yicha xesh)
   -> oddiy, lekin server yiqilsa — sakrash

3. Ekranda silliqlash:
   ilova yangi ETA ni darhol emas, sekin o'zgartiradi
   (6 -> 7 -> 8, keskin sakrashsiz), katta farqni esa darhol

14. Kuzatuv: haqiqat kech keladi

14.1 Metrikalar

Jadvaldagi asosiy muammo — aniqlik metrikalari kech keladi. Safar ETA’sining xatosi faqat safar tugagandan keyin (20–40 daqiqa) ma’lum. Agar model bugun soat 14:00 da buzilgan bo‘lsa, aniqlik grafigi buni 14:30 da ko‘rsatadi.

14.2 Kiritmalar va chiqishlar monitoringi

Erta signallarning ikki turi bor. Kiritma monitoringi: har belgi uchun taqsimot (o‘rtacha, nollar ulushi, bo‘sh qiymatlar) hozirgi soat va o‘tgan haftaning shu soati bilan solishtiriladi. Chiqish monitoringi: bashorat qilingan ETA’larning taqsimoti — masalan, marshrut ETA’si va yakuniy ETA nisbati. Agar model birdaniga katta tuzatishlar bera boshlasa, bu ham signal.

q = model(belgilar)                      # bashorat qilingan qoldiq
chegara = max(2 daq, 0.5 x marshrut_ETA)  # masalan
q = min(max(q, -chegara), +chegara)
yakuniy = marshrut_ETA + q

15. Antinaqshlar

Birinchi qator — v0 ning merosi va eng uzoq yashaydigan antinaqsh, chunki u o‘rtacha to‘g‘ri. Muammo o‘rtachada emas, qarorda: dispetcherlik taqqoslaydi, va taqqoslash tizimli xatolarga sezgir (4-bo‘lim Check). Bu antinaqshning chuqur sababi — arzon proksi o‘lchovni (masofa) haqiqiy maqsad (vaqt) o‘rniga optimallashtirish.

Ikkinchi qator — ma’lumot yig‘ishdan qochish. Tezlik belgisi tayyor turibdi, haqiqiy tezlik esa GPS quvuri, map matching va agregatsiyani talab qiladi. Lekin ETA tizimining butun qiymati aynan shu quvurda: algoritm hamma uchun bir xil (Dijkstra ochiq), ma’lumot esa — faqat sizda.

Uchinchi qator qiziq, chunki xato faqat ma’lumotda ko‘rinadi, kodda emas. Biriktirish funksiyasi to‘g‘ri ishlaydi — nuqtaga eng yaqin yo‘lni topadi. Lekin savol noto‘g‘ri qo‘yilgan: “bu nuqta qaysi yo‘lga eng yaqin” emas, “bu iz qaysi yo‘ldan o‘tgan”. Ketma-ketlikka qarash (HMM) — alohida nuqtalarga qarashdan farqli savol.

To‘rtinchi qator — eng nozik va eng xavfli, chunki natija deyarli to‘g‘ri. Optimistik bo‘lmagan evristika bilan A* 98% hollarda eng tez yo‘lni topadi, 2% da 3–5% uzunroq yo‘lni. Hech bir aniq test buni ushlamaydi; faqat tasodifiy juftliklarda Dijkstra bilan solishtirish (amaliyotdagi kabi) ko‘rsatadi.

Beshinchi qator — “ML hamma narsani hal qiladi” tuzog‘i. 14-qadamdagi Check uning uch zaif tomonini ko‘rsatdi. Gibrid yondashuv kamroq “chiroyli”, lekin fizikani (graf, jonli og‘irliklar) va o‘rganishni (qoldiq) to‘g‘ri ajratadi.

Bo'lak e: w(e, t)
  17:00 da kirilsa: 10 daqiqa (tirbandlik) -> chiqish 17:10
  17:02 da kirilsa: 3 daqiqa (tirbandlik tarqaldi) -> chiqish 17:05

16. Trade-off‘lar

Jadvaldagi har juftlik bitta o‘qda yotadi: yangilik va barqarorlik. Statik CH va uzun oyna — barqaror, lekin eskirgan. Moslashtiriladigan marshrutlash va qisqa oyna — yangi, lekin murakkab yoki shovqinli. Yaxshi tizim bitta nuqtani tanlamaydi: katta ko‘chalarda qisqa oyna, kichiklarida uzun (8-qadamdagi aralashtirish buni avtomatik qiladi); yaqin kelajak uchun jonli, uzoq kelajak uchun tarixiy (9-qadam).

xato r = haqiqat - bashorat
Huber(r) = 0.5 x r^2               agar |r| <= delta
           delta x (|r| - 0.5 x delta)   aks holda

Asimmetrik: L(r) = w x Huber(r)        agar r > 0 (kam ko'rsatdik, kech keldi)
                   (1 - w) x Huber(r)  agar r <= 0 (ko'p ko'rsatdik)

w = 0.5 -> simmetrik (o'rtachaga yaqin)
w = 0.7 -> kam ko'rsatish 2.3 barobar qimmat -> bashorat yuqori kvantilga siljiydi

17. Intervyu savollari

17.1 Algoritmlar

17.2 Ma’lumot va ML

17.3 Tizim va miqyos

18. Amaliyot

To‘rt daraja. Ikkinchi daraja uchun kod docs/amaliyot/uber-eta/ da: eta.py — oltita funksiya TODO; city.py — tayyor sintetik shahar (70 × 70 chorraha, magistrallar, bir tomonlama ko‘chalar, daryo va uchta ko‘prik), GPS o‘tishlari va safarlar generatori; check.py — 20 ta tekshiruv, taxminan 3 soniya. Faqat Python standart kutubxonasi.

19. Lug‘at

20. Raqamlar manbasi

Bir safarga ETA so‘rovlari, sekundiga so‘rovlar, GPS nuqtalari chastotasi va hajmi, bo‘laklar soni va kuzatuvlar zichligi, burilish va svetofor vaqtlari, xato taqsimotlari, model yaxshilanishlari, kechikish byudjetlari, xarajatlar va sig‘im hisoblari — illyustratsiya uchun taxminiy. Ular yuqoridagi ochiq raqamlardan va algoritmlar bo‘yicha nashr etilgan natijalardan kelib chiqqan, tartib jihatidan ishonchli, lekin aniq emas. Darsning asosiy xulosalari — graf kichik, qidiruv esa aqlli bo‘lishi kerak; og‘irliklar haqiqati GPS quvurida; ML fizikani emas, qolgan xatoni o‘rganadi; hisob arzon, xato qimmat — bu raqamlarning bir necha barobarlik xatosiga ham chidamli.

21. Manbalar

• Edsger W. Dijkstra (1959), “A Note on Two Problems in Connexion with Graphs”, Numerische Mathematik
• Peter E. Hart, Nils J. Nilsson, Bertram Raphael (1968), “A Formal Basis for the Heuristic Determination of Minimum Cost Paths”, IEEE Transactions on Systems Science and Cybernetics
• Andrew V. Goldberg, Chris Harrelson (2005), “Computing the Shortest Path: A* Search Meets Graph Theory”, SODA
• Robert Geisberger, Peter Sanders, Dominik Schultes, Daniel Delling (2008), “Contraction Hierarchies: Faster and Simpler Hierarchical Routing in Road Networks”, WEA
• Daniel Delling, Andrew V. Goldberg, Thomas Pajor, Renato F. Werneck (2011), “Customizable Route Planning”, SEA
• Julian Dibbelt, Ben Strasser, Dorothea Wagner (2014), “Customizable Contraction Hierarchies”, SEA
• Hannah Bast va boshq. (2016), “Route Planning in Transportation Networks”, Algorithm Engineering (sharh)
• Paul Newson, John Krumm (2009), “Hidden Markov Map Matching Through Noise and Sparseness”, ACM SIGSPATIAL GIS
• M. J. Lighthill, G. B. Whitham (1955), “On Kinematic Waves II”; P. I. Richards (1956), “Shock Waves on the Highway”
• Harold W. Kuhn (1955), “The Hungarian Method for the Assignment Problem”
• Uber muhandislik blogi (2022), “DeepETA: How Uber Predicts Arrival Times Using Deep Learning”
• Uber muhandislik blogi (2018), “H3: Uber’s Hexagonal Hierarchical Spatial Index”; H3 hujjatlari (h3geo.org)
• Uber muhandislik blogi (2017), “Meet Michelangelo: Uber’s Machine Learning Platform”
• 9th DIMACS Implementation Challenge — Shortest Paths (2006)
• Uber yillik hisobotlari (2023–2024)