Ratusan ribu rute per detik per inti. Yandex. Pengalaman Rute

Beberapa minggu yang lalu, Danya Tararukhin memberi tahu Habré bagaimana layanan kami muncul, Yandex. Rute, dan bagaimana hal itu membantu perusahaan dengan logistik. Dengan membuat platform, kami memecahkan beberapa masalah menarik, salah satunya didedikasikan untuk posting hari ini. Saya ingin berbicara tentang perencanaan rute itu sendiri dan sumber daya yang diperlukan untuk ini.

Menemukan rute terbaik antara banyak titik adalah masalah optimasi diskrit klasik. Untuk mengatasinya, Anda perlu mengetahui jarak dan waktu perjalanan antara semua titik. Artinya, untuk mengetahui matriks jarak dan waktu. Dua tahun lalu, perhitungan matriks yang panjang adalah masalah yang sangat penting bagi kami dan menghalangi pengembangan. Pencarian untuk solusi optimal dengan matriks yang diketahui membutuhkan waktu 10 menit, tetapi perhitungan semua sel matriks untuk tugas-tugas besar (untuk beberapa ribu pesanan) membutuhkan waktu berjam-jam.

Untuk mengatasi masalah dengan lima ribu pesanan, Anda perlu mengetahui jarak dan waktu perjalanan antara semua titik. Ini adalah dua matriks angka dengan dimensi 5000x5000. Kami merencanakan rute kurir sepanjang hari, dan di pagi hari kurir akan tiba dari titik ke titik dalam satu waktu, dan di malam hari - untuk yang lain. Jadi, Anda perlu menghitung matriks waktu dan jarak untuk setiap jam dalam sehari. Tidak semua jam dalam sehari adalah unik, tetapi waktu gabus (pagi dan sore) perlu ditutup dengan baik. Oleh karena itu, kami sampai pada konfigurasi dengan irisan tiga belas jam. Secara total, kita membutuhkan dua kubus (waktu dan jarak) masing-masing 13x5000x5000. Ini adalah 325 juta rute, dihitung menurut grafik jalan nyata, di mana 165 juta ujungnya. Penghitungan satu rute dalam algoritma yang dioptimalkan dengan baik dari tim Yandex.Maps membutuhkan waktu sekitar 10 ms, dengan total 900 jam perhitungan.Bahkan ketika diparalelkan dengan 900 CPU, Anda harus menunggu 1 jam. Kami tidak dapat memulai layanan seperti itu, kami membutuhkan algoritma yang lebih cocok.

Untuk bacaan lebih lanjut, penting untuk mengetahui algoritma Dijkstra untuk menemukan jalur terpendek dalam grafik. Itu bisa dibayangkan sebagai "gelombang" yang berasal dari titik awal rute dan mengelilingi seluruh grafik sampai titik finish terpenuhi. Dalam hal ini, waktu berjalan algoritma sebanding dengan tepi grafik, yaitu area yang dicakup oleh gelombang:



Hampir setiap kandidat untuk wawancara pada wawancara mengetahui langkah pertama dalam mengoptimalkan tugas seperti itu: Anda dapat memulai gelombang dari dua sisi dan mengakhiri pencarian ketika gelombang bertemu. Luas total dua gelombang setengah jari-jari kurang dari satu besar.



Grafik jalan sebenarnya cukup terstruktur, dan ini dapat digunakan. Ketika Anda mencari jarak terpendek antara Moskow dan St. Petersburg, di Dijkstra klasik Anda akan dipaksa untuk menyebarkan gelombang dalam lingkaran dan memilah-milah semua jalan-jalan dan lorong-lorong di Moskow, kota-kota dan desa-desa Wilayah Moskow, jalan-jalan Tver dan Novgorod. Ini adalah jumlah perhitungan yang sangat besar, tetapi Anda dapat mempersiapkan terlebih dahulu dan mengingat rute optimal antar kota (alias pintasan) dan tidak mengulanginya dalam runtime. Kemudian, untuk menemukan rute antara dua titik di Dijkstra hirarkis, Anda perlu menghitung jarak terpendek ke jalan pintas yang diinginkan. Karena level hierarki mungkin bukan dua, tetapi 5-6, mereka secara dramatis mengurangi waktu pencarian.

Tim router Kartu telah mengimplementasikan optimasi semacam itu untuk beberapa waktu. Merekalah yang memungkinkan untuk mencapai 10 ms untuk menemukan rute antara dua titik. :) Jadi untuk saat ini, kami belum menyelesaikan masalah kami.

Karena mode pencarian point-to-point sudah sangat dioptimalkan, kami dapat mengoptimalkan perhitungan seri dalam matriks. Baris adalah jarak dari satu titik ke titik lainnya. Saat kami mencari jarak ke titik terjauh, kami secara bersamaan menghitung jarak ke titik terdekat. Oleh karena itu, menghitung deret sama dengan menghitung jarak ke titik terjauh.



Kami melihat pada saat menghitung seri menggunakan algoritma ini dan ingat bahwa perhitungan berurutan dari 5000 rute akan memakan waktu sekitar 5000 * 10 ms = 50 s:


Grafik menunjukkan waktu perhitungan satu baris dalam matriks jarak ukuran 1 * N untuk N yang berbeda (menurut data nyata). Dapat dilihat bahwa perhitungan deretan ukuran 1 * 5000 yang menarik bagi kami cocok menjadi 1,3 detik. Garis tren telah ditambahkan ke grafik, yang menunjukkan bahwa waktu perhitungan tumbuh sedikit lebih lambat daripada linear di N, urutan N ** 0,74

Sudah tidak buruk! Dengan algoritma ini, kita dapat menghitung kubus kita dalam 13 * 5000 * 1,3 s = 84 500 s = hampir 24 jam. Dengan mudah paralel dengan baris, dan saat menggunakan 50 CPU, jarak dihitung dalam setengah jam. Urutan kompleksitas algoritma perhitungan kubus adalah O (N ** 1.74):


13 N*N 50 CPU ( 13*N/50). , 5000 , . 10 000, : .

Dalam formulir ini, dua setengah tahun yang lalu, kami meluncurkan versi pertama API kami, yang memecahkan masalah logistik. Klien sering mengeluh tentang waktu keputusan yang lama, dan mereka mudah dimengerti: Anda memulai tugas yang harus diselesaikan, tunggu 1 jam, Anda mendapatkan solusi dan Anda mengerti bahwa Anda lupa memperbaiki waktu shift dengan pengemudi, Anda memperbaikinya dan semuanya dimulai dari awal lagi. Pengemudi mulai merasa gugup, karena mereka berisiko masuk ke jam sibuk pagi hari, atau bahkan tidak punya waktu untuk mengirimkan pesanan tepat waktu. Itu perlu untuk melakukan sesuatu. Kami tidak ingin "melempar" masalah dengan besi: kami sedang bersiap untuk beban berat, itu akan membutuhkan banyak besi, dan pembelian server tidak terjadi sekaligus.

Sebuah studi artikel akademik menunjukkan bahwa, ternyata, ada algoritma dengan kompleksitas linier untuk tugas ini *! (Dalam artikel dengan referensi, ada ikhtisar besar dari semua jenis metode modern percepatan Dijkstra, termasuk untuk kasus matriks.) Menghitung matriks dalam waktu linier tidak cocok di kepala saya. Salah satu pengembang kami mengajukan diri untuk membuat prototipe, dan inilah yang terjadi:


Waktu untuk menghitung satu matriks ukuran N * N pada satu CPU menggunakan algoritma "matriks cepat". Kompleksitas diperoleh pada urutan O (N ** 1,1). Ns tinggi tersingkir dari garis tren, karena generasi jawaban dan pengunduhannya melalui jaringan sudah lebih mempengaruhi waktu.

115 detik per 5000x5000 matriks menggunakan inti tunggal dan ketergantungan yang hampir linier pada N. Fiksi telah menjadi kenyataan! Ide algoritma menggabungkan dua ide yang dijelaskan di atas: Dijkstra untuk seri dan pencarian hierarkis. Jelas, mulai menghitung baris kedua, di beberapa titik kita akan kembali berkeliling area yang sama dari grafik yang baru saja kita lalui, menghitung baris sebelumnya. Oleh karena itu, mari kita mengingat jarak terpendek ke semua tujuan di simpul grafik hierarkis. Ketika kita mulai menghitung seri berikutnya, maka, setelah mencapai simpul seperti itu, kita akan segera mendapatkan hampir semua jarak ke titik lain.



Setahun setengah yang lalu, ini memungkinkan kami menghemat setengah jam dengan eLogistik dan secara signifikan mengurangi asupan zat besi. Sebelumnya, untuk satu permintaan besar, kami membutuhkan 50 core selama setengah jam, tapi sekarang - 13 core selama 2 menit. Ini adalah sekitar 200.000 rute per detik per inti. Itu kasus langka ketika algoritma baru tidak hanya menutup kelas masalah, tetapi memperluas ide kami tentang kemungkinan.

---

_{^{* Artikel “Perencanaan Rute dalam Jaringan Transportasi”, lihat paragraf 2.7.2 “Jalur Terpendek Batch”}}