Hlavní navigace

Algoritmus pro sdílení taxi v reálném čase

Jan Fikar

Vědci z MIT a Cornellu zveřejnili algoritmus pro optimalizované sdílení dopravních prostředků více lidmi v reálném čase. Algoritmus musí při optimalizaci prohledávat velmi velký prostor parametrů. Naštěstí se ukazuje, že není potřeba najít globální optimum a stačí méně časově náročné lokální optimum rychle nalezené pomocí tzv. „hladového algoritmu“.

Algoritmus byl vyzkoušen na reálných datech z jednoho týdne v květnu 2013 v New Yorku, kdy 13,5 tisíc taxi obsloužilo přibližně 3 milióny zákazníků. Výsledky algoritmu ukazují, že stejné požadavky mohlo obsloužit jen 2 tisíce dodávek s 10 místy, nebo 3 tisíce taxi se 4 místy. Při tom 98 % zákazníků by čekalo méně než 2,8 minut a délka jízdy by se prodloužila o méně než 3,5 minuty.

(zdroj: arstechnica)

Našli jste v článku chybu?