Salah satu tugas utama di Yandex.Taxi adalah bagaimana memastikan bahwa mobil tiba dengan cepat kepada pengguna, dan waktu pengemudi untuk "idle run" berkurang (yaitu, waktu ketika ia berada di telepon tanpa penumpang). Tampaknya semuanya sederhana: pengguna memilih tarif, menunjukkan keinginan tambahan (kursi anak, misalnya). Tetap menyaring driver di telepon sesuai dengan kriteria ini, pilih yang terdekat dan menawarkan pesanan kepadanya. Namun, semuanya sangat sederhana hanya pada pandangan pertama.
Hari ini saya akan memberi tahu komunitas Habr bagaimana kita memilih driver yang paling cocok dan bagaimana proses ini telah berkembang dari waktu ke waktu. Anda akan belajar tentang dua pendekatan untuk menyelesaikan masalah.
Arsitektur Pencarian Umum
Ketika pengguna mengklik tombol "Panggil taksi", objek pesanan dibuat di backend dan pemrosesan dimulai sesuai dengan mesin negara. Agar perintah dapat beralih dari status "Tertunda" ke "Pengemudi telah ditetapkan", Anda harus mencari pengemudi, menawarkan pesanan kepadanya dan menunggu konfirmasi bahwa pesanan telah diterima.
Pendekatan Serakah
Untuk waktu yang sangat lama, pendekatan
rakus bekerja di Yandex.Taxi. Dengan pendekatan ini, pada tahap mencari kontraktor, permintaan dibuat ke layanan tracker mikro yang bertanggung jawab untuk driver. Pelacak tahu segalanya tentang mobil: mulai dari warna dan pencitraan merek hingga
lokasi saat ini . Tracker memiliki geo-indeks lokal untuk driver dan konektor ke layanan routing (router) untuk membangun rute dari titik A ke titik B (dan bahkan melalui titik B, D, D). Oleh karena itu, ketika permintaan dibuat untuk mencari pengemudi, Pelacak terlebih dahulu menentukan mobil terdekat di geo-indeks lokal di sepanjang radius langsung, dengan mempertimbangkan batasan pesanan "keras" (kelas mobil, persyaratan - kursi anak, angka kuning). Kemudian, waktu dan panjang rute pasokan kendaraan ditentukan dan, dengan mempertimbangkan informasi ini, opsi terbaik dipilih.
Kemudian, logika ini berevolusi: untuk setiap pengemudi mereka mulai mengandalkan "skor" -nya pada urutan - fungsi waktu mobil itu dikirim. Dan driver sudah diberi peringkat dengan nilai skor. Fungsi ini memperhitungkan tidak hanya waktu pengiriman itu sendiri, tetapi juga banyak faktor lain: dari tingkat permintaan di titik A dan B hingga "pengalaman" pengemudi. Janji serakah ini disebut bonus.
Pendekatan buffer (balok)
Namun, dengan pendekatan serakah, pengemudi terdekat akan menerima orang yang pertama kali memesan taksi. Namun, beberapa pengguna bahkan mungkin dibiarkan tanpa mobil.
Dengan meningkatnya permintaan, ketika kompetisi untuk pemain dimulai, pendekatan serakah tidak baik. Untuk memenuhi permintaan sebanyak mungkin bahkan di jam-jam paling sibuk, kami menggunakan banyak pendekatan dan algoritma. Salah satunya adalah penunjukan (balok) penunjukan driver pada pesanan. Ini didasarkan pada tugas yang terkenal dari bidang optimasi kombinatorial -
masalah penugasan . Singkatnya, intinya: mari kita memiliki N bekerja dan berkinerja M, setiap karyawan dapat menyelesaikan tugas apa pun selama waktu p (i, j) [0 <= i <N, 0 <= j <M]. Diperlukan untuk menetapkan kontraktor tersebut untuk setiap tugas untuk mengurangi total waktu pelaksanaan semua pekerjaan (dalam hal ini, satu kontraktor hanya dapat mengambil satu pekerjaan).
Ketika memecahkan masalah penugasan seperti itu, "biaya" kami untuk melakukan pekerjaan (pesanan) oleh pelaksana (armada taksi dan pengemudi) adalah nilai dari fungsi penilaian sejak kendaraan dikirimkan kepada pengguna. Tugas ini dapat dijelaskan dalam bentuk grafik bipartit: di satu sisi, pesanan, di sisi lain, pemain. Antara pesanan dan pemain ada tepi tertimbang (penilaian). Dengan demikian, salah satu tujuan kami adalah untuk meminimalkan waktu pengiriman total kendaraan dengan memaksimalkan jumlah pesanan yang selesai (pencocokan maksimum). Salah satu cara paling terkenal untuk memecahkan masalah seperti itu adalah
algoritma Hungaria .
Jelas, dengan janji buffer, kami tidak dapat memberikan driver berdasarkan permintaan, seperti halnya dengan pendekatan serakah. Pertama, Anda perlu memasukkan urutan ke dalam antrian, kemudian bermain, dan kemudian menginformasikan tentang driver yang ditemukan. Ini sama sekali tidak cocok dengan mesin pemrosesan pesanan negara, dan itu harus diperbaiki sedikit. Untuk menguji dan membuat solusi baru tanpa mempengaruhi kolega kami, kami segera setuju bahwa kami akan melakukan segalanya dalam microservice DriverDispatcher yang terpisah. Dia akan menerima pesanan, memasukkan antrian, mencari driver dan menyimpan hasil demonstrasi.
Pertama-tama, kami harus menyiapkan Pelacak untuk profil beban baru. Jika dengan pendekatan serakah, permintaan driver secara individual jatuh pada pelacak Tracker dan dialihkan ke instansinya dengan load balancing, maka di tujuan buffer semua permintaan berasal dari satu mesin: permintaan individual hanya akan menyumbat kumpulan koneksi. Oleh karena itu, kami menambahkan kemampuan pelacak untuk memproses kumpulan permintaan yang diproses secara bersamaan di dalam pelacak. Sepanjang jalan, kami juga harus menyelesaikan masalah sejumlah permintaan untuk pemrosesan batch yang masuk akal. Di sisi klien (DriverDispatcher), kami membagi batch besar menjadi beberapa batch kecil dan mengirimkannya ke berbagai instance Tracker.
Jadi, pelacak disiapkan, penilaian dianggap baik dalam Pelacak (penunjukan serakah) dan dalam layanan baru (DriverDispatcher'e), algoritma untuk menyelesaikan masalah penugasan debugged dan bekerja dengan benar. Muncul pertanyaan tentang bagaimana mengintegrasikan semua ini ke dalam mesin pemrosesan pesanan negara. Kami menambahkan pengiriman dan penghapusan meta-informasi pesanan di DriverDispatcher ketika pesanan ditransfer dari negara bagian ke negara. Dan itu hampir berhasil. Hampir - karena iterasi mencari kontraktor untuk memesan tidak dikendalikan secara eksternal. Kami hanya bisa mengganti perjalanan ke pelacak dengan pengemudi dengan perjalanan ke layanan kami dan memberikan sopir ketika ditemukan, dan sebelum itu hanya memberikan 404. Tapi ini buruk, karena Anda perlu menawarkan pesanan kepada pengemudi segera setelah kami menemukan pesanan, dan bahkan beberapa detik keterlambatan berperan di sini: pengemudi hanya dapat berbelok ke arah yang salah, dan urutannya akan menjadi tidak relevan. Untuk melakukan ini, kami memungkinkan memanggil proses pencarian untuk seorang artis tanpa memengaruhi tugas yang direncanakan. Jadi kami menyimpan logika pencarian (dengan permintaan ulang) dan menambahkan kemampuan untuk menyebutnya di luar penjadwal.
Dengan demikian, kami dapat menggabungkan mesin keadaan utama untuk pemrosesan pesanan dengan mesin keadaan dalam pengiriman buffer tanpa mempengaruhi logika kerja dan tanpa balapan antar negara. Anda dapat menjalankan percobaan pertama pada pengguna langsung.
Ini semua sangat keren, tetapi bagaimana dengan waktu untuk mencari artis, Anda bertanya. Jika pencarian tidak dilakukan segera setelah penerimaan pesanan, maka waktu pencarian meningkat dan hasilnya dikompensasi oleh umpan yang lebih cepat? Ini tidak sepenuhnya benar: dengan bantuan berbagai teknik (termasuk menggunakan pembelajaran mesin), kami dapat mengisolasi kasus ketika menunggu masuk akal, dalam kasus lain waktu tunggu tidak berubah.
Penarikan pin
Cara lain untuk menemukan artis lebih cepat adalah mulai mencarinya SEBELUM membuat pesanan. Ketika
pin baru muncul (yaitu, pengguna hanya memasukkan data pesanan ke dalam aplikasi),
algoritma pembelajaran mesin mengevaluasi kemungkinan bahwa suatu pesanan akan mengikuti, dan memutuskan apakah akan memperhitungkannya saat buffering driver. Kami dapat menemukan mobil di muka, dan ketika pengguna mengklik tombol pesanan, segera buat penawaran ke pengemudi yang sesuai.
Kesimpulan
Mencocokkan pesanan dan driver bukanlah tugas yang mudah, itu membutuhkan memperhitungkan banyak faktor. Salah satunya adalah konteks pergerakan pengemudi saat memilih kandidat untuk dipesan. Kami akan membicarakan ini di posting berikut.
Posting Teknologi Taksi Lainnya