Teks ini muncul karena keceriaan kopi acak di Yandex - sistem membuat janji untuk dua karyawan acak jika mereka mengindikasikan bahwa mereka ingin berpartisipasi dalam pertemuan tersebut. Teman bicara saya menemukan cerita tentang apa yang saya lakukan menarik, dan sekarang saya dapat menawarkannya kepada khalayak yang lebih luas.Sebelum Habr, saya memberikan kuliah tamu di Fakultas Ilmu Komputer HSE dan Yandex - Saya memberi tahu para siswa FCS hal yang persis sama, yang akan saya ceritakan sekarang (di akhir posting ada video) Yaitu, bagaimana bepergian dengan pengemudi yang mengirimkan pesanan dari toko online meyakinkan tim kami untuk membuat layanan baru tentang logistik. Saya harap saya bisa menyampaikan perasaan saya kepada Anda dari daerah ini: Saya pergi ke Gazelles dan Largus, mendengarkan keluhan dari karyawan tentang Bibi pemilih dari Noginsk dan menyaksikan bagaimana urutan tiga skuter untuk tiga anak berubah menjadi drama . Dan pada akhirnya, mari kita bicara tentang teknologi.Bagian 1. Bagaimana semuanya dimulai
Beberapa tahun yang lalu, berjalan di sekitar kantor memikirkan apakah sudah waktunya bagi saya untuk mengubah sesuatu dalam hidup saya, saya hampir secara tidak sengaja bertemu dengan seorang rekan yang sangat saya hormati pada salah satu proyek masa lalu saya. Ternyata dia beralih ke startup internal, dan mereka hanya mencari analis. Jadi saya berakhir di sebuah divisi bernama B2BGeo. Kelompok kecil ini pada waktu itu seharusnya melakukan beberapa hal untuk perusahaan berdasarkan layanan-geografis Yandex - hanya saja tidak ada yang tahu yang mana. Secara historis, karyawan geoservice telah membuat desktop Yandex.Maps, Maps, Navigator, dan aplikasi seluler Metro. Selain itu, unit ini mencakup infrastruktur yang mengesankan: pengembangan mesin perutean, layanan peta, pengenalan rambu-rambu jalan, ekstraksi data dari gambar satelit, dan banyak lagi. Baik peta web dan Yandex.Navigator adalah aplikasi,ditujukan untuk pengguna massal. Dari layanan untuk perusahaan, kami hanya memiliki satu set pemetaan API: widget peta JS untuk situs, MapKit untuk aplikasi, dan API pembuatan rute REST.Jadi tim B2BGeo, sebelum mulai menjual produk untuk perusahaan, harus membuat produk ini. Kami menghabiskan beberapa waktu untuk riset pasar dan membuat prototipe. Prototipnya menarik, misalnya, peta kualitas sinyal seluler di dalam gedung. Kemudian operator seluler tidak menggunakan data dalam jumlah besar yang mereka miliki, mengukur kualitas terutama di jalan-jalan dan dengan cara yang agak primitif. Contoh lain dari prototipe adalah router universal yang dapat disesuaikan dengan pembelajaran mesin. Ngomong-ngomong, selanjutnya disebut router dan router bukan peralatan jaringan, melainkan program pembangunan rute.Beberapa prototipe tidak lepas landas, yang lain tidak akan tertarik pada sejumlah perusahaan. Dibutuhkan sesuatu yang lebih besar. Di masa depan, ini akan membalikkan dunia dan membuka cakrawala baru, dan untuk permulaan akan membawa manfaat signifikan melalui teknologi geoteknologi. Kami memiliki sesi strategis: kami meninggalkan kantor dan bertukar pikiran selama dua hari. Berdasarkan hasil sesi, kami mengidentifikasi industri di mana ada prospek yang cukup bagi kami. Pilihan kami jatuh pada logistik.Di Rusia, banyak kendaraan komersial, banyak perusahaan angkutan dan kurir membawa sesuatu ke suatu tempat. Dan semuanya, kemungkinan besar, membuat rute mereka secara manual atau dengan bantuan program yang mungkin tidak berfungsi dengan baik, karena mereka tidak memperhitungkan kemacetan lalu lintas. Dan di belakang kami ada seluruh Yandex dengan banyak perangkat keras, hanya sejumlah kecil perusahaan (hanya contoh langka - Google) yang memiliki data sampel, dan pemrogram yang baik. Kompetensi dalam bidang ini langka dan berharga: Uber pada titik tertentu membeli seluruh tim kartografi.Didorong oleh prospek ini, kami sepakat dengan salah satu agregator pengiriman (sebuah perusahaan yang mengirimkan pesanan dari berbagai toko online) sehingga mereka akan membiarkan kami melihat pekerjaan mereka dari dalam ke luar, "membenamkan diri dalam industri ini." Anggota tim kecil kami bepergian dengan kurir yang mengantarkan pesanan, dan duduk di sebelah ahli logistik yang merencanakan rute.Bagian 2. Perendaman dalam industri
Jam 8 pagi, salah satu zona industri di belakang Third Ring Road, tempat gudang dan kantor agregator berada. Sebuah ruangan kecil, mengingatkan kantor pos: sudut dipagari dengan meja, komputer logistik, telepon, printer. Kursi berminyak dan kursi komputer dengan dermantine yang retak. Sebuah kotak dengan ponsel Cina murah, kertas dengan nomor terpaku di masing-masing - mereka dibagikan kepada pengemudi. Ada sofa-jamuan sederhana di sepanjang dinding, dudukan dengan cetakan di pintu keluar: aturan transportasi, semacam instruksi internal, daftar denda - misalnya, 200-300 rubel akan dibebankan dari pengemudi untuk pesanan yang tidak terkirim. Agregator juga memiliki kantor normal, di mana direktur, manajer dan pembukuan duduk di meja yang indah, tetapi peristiwa-peristiwa penting bagi kita terjadi di ruangan kecil ini.
Pengemudi merokok di luar, tetapi di sana sejuk, sebagian besar ada di dalam, sehingga penuh sesak dan pengap di dalam ruangan. Mat-remat di tiga lantai, banyak suram di pagi hari, seseorang ingin mendapatkan paket faktur dan pergi untuk memuat, seseorang memiliki halangan, dia tidak bahagia. Situasinya tegang, ada dua ahli logistik, dan mereka ada di dalam sabun. Kami diberitahu bahwa ini adalah hari yang normal, tepat di pagi hari, ketika berangkat ke rute, selalu ada taman. Pada malam hari, ketika perencanaan berjalan, ada juga yang tenggelam, di suatu tempat dalam satu jam ketegangan akan berkurang, dan ahli logistik akan dapat beristirahat.Beberapa pengemudi diberitahu bahwa Yandex akan ikut dengan Anda. Mereka terkejut dan tidak terlalu puas - tidak jelas mengapa mereka begitu bahagia dan apakah mereka telah membuat kita mengikuti mereka. Kami, pekerja kantoran , pekerja IT dengan ransel, sangat kontras dengan laki-laki suram ini.Saya mendapatkan Gazelle, ia memiliki seorang pengemudi dan seorang forwarder, saya duduk ketiga dengan sebuah ransel di tangan saya dan mencoba untuk tidak mengambil terlalu banyak ruang. Pesanan sudah dimuat ke dalam tubuh, kita mulai.
Belakangan saya mengetahui bahwa biasanya mendahului keberangkatan mobil di rute.Misalkan hari ini hari Rabu, Anda memesan kulkas di situs kecil yang Anda temukan di Yandex.Market, toko ini memiliki harga terbaik dan ulasan yang masuk akal. Pengiriman hanya mungkin pada hari Jumat, itu cocok untuk Anda. Situs ini benar-benar hanya sebuah karya pamer, untuk situs yang sangat kecil, manajer yang mengkonfirmasi pesanan umumnya dapat menjadi satu-satunya karyawan. Kulkas Anda terletak di suatu tempat di gudang dekat Podolsk bersama dengan kulkas lain dari perusahaan yang sama (toko kecil tidak memiliki gudang sendiri - pada kenyataannya, penjualannya berasal dari gudang pabrik). Manajer menyimpan kulkas ini dan mengirimkan pesanan ke agregator pengiriman. Selama hari Rabu, agregator mengumpulkan pesanan dan pada hari Kamis mengirimkan truk besar ke Podolsk untuk kulkas Anda dan lainnya yang dipesan di toko lain.Semua ini datang ke gudang yang disewa oleh agregator di zona industri Moskow.Pada Kamis malam, ketika semua barang yang akan dikirim pada hari Jumat dikumpulkan di gudang, petugas logistik duduk untuk bekerja. Pada 4-5 pagi mereka harus mendistribusikan pesanan dengan mesin, pekerja gudang akan menaruh barang-barang di tumpukan, setiap mesin memiliki tumpukan sendiri - Anda harus meninggalkan mereka sedikit waktu untuk pekerjaan ini. Banyak yang akan dimuat ke dalam mobil, dan itu akan menyenangkan pelanggan.
Untuk mendistribusikan pesanan dengan mesin, ahli logistik menggunakan program yang dibeli secara khusus. Terintegrasi dengan 1C: Perusahaan, data pada mesin (berat dan volume kargo yang diijinkan, biaya pekerjaan sehari) dan pada barang (berat, volume, alamat dan interval pengiriman, kontak pelanggan, komentar) dimasukkan ke dalamnya. Beberapa mobil milik agregator, yang ini memiliki tumit (Lada Largus) dan Gazelles (Gazelle / Ford Transit / Hyundai Porter). Ada juga kurir sewaan untuk kendaraan pribadi, biasanya dengan station wagon (kami melihat Ford Focus, Mitsubishi Pajero dan bahkan beberapa Lexus lama).Program ini ditulis oleh programmer yang baik, ia tahu bagaimana mendistribusikan muatan pada mobil dan membangun rute (berdasarkan waktu atau jarak tempuh) yang optimal untuk menghindari pesanan, mengingat banyak parameter. Tetapi ahli logistik tidak menggunakan fungsi ini dengan cara apa pun. Tapi dia aktif menggunakan visualisasi pesanan di peta. Program ini memungkinkan Anda untuk menggambar poligon-area pada peta dan menampilkan statistik kargo dan rute di dalam area ini. Para ahli logistik membagi semua Wilayah Moskwa dan Moskwa hingga Beton Besar (jalan raya A108) menjadi zona dengan tipe kira-kira sebagai berikut:
Di pusat, ada beberapa area kecil, dan kemudian sektor radial mulai yang membentang di sepanjang jalan raya utama dan meliputi wilayah tersebut.Di setiap zona seperti itu, pengemudi tertentu bekerja, yang biasanya akrab dengannya, mengetahui jalan, fitur lalu lintas, tahu di mana polisi lalu lintas, apa batasan dan rambu untuk truk. Logistician, pada gilirannya, tahu berapa banyak pesanan yang bisa dilakukan kru. Dia memberi lebih berpengalaman di bawah 30 pesanan, dan bagi mereka yang sudah mulai bekerja baru-baru ini, 20-25 pesanan. Dia melihat berapa banyak pesanan di daerah tertentu, dan jika ada terlalu banyak, dia melemparkannya ke yang berikutnya. Atau menambahkan dari tetangga: katakanlah, ahli logistik berteman dengan beberapa pengemudi dan memberi mereka perintah "ringan", yang kemungkinan besar akan segera tiba. Dan pengemudi yang tidak dicintai dapat mengganggu. Misalnya, untuk melemparkan pesanan untuk klien, tentang siapa yang diketahui sebelumnya bahwa dia pilih-pilih, akan membutuhkan pengiriman secara ketat pada waktu yang ditentukan, akan mencetak semua barang, akan memeriksanya untuk waktu yang lama. Selain,Logistician dapat memberikan pesanan pengemudi lebih sedikit: untuk setiap pesanan pengemudi menerima 200 rubel, ia tertarik untuk memiliki lebih banyak.Kemampuan untuk merencanakan rute dalam program sepenuhnya diabaikan. Kemungkinan ini tidak masuk akal dalam sistem seperti itu: jika ahli logistik memberi tahu pengemudi bagaimana dia harus melakukan pemesanan, pengemudi akan menjawabnya: "Anda duduk di kantor di sana, dan saya di area ini seperti punggung tangan saya". Jadi ahli logistik hanya memberikan pesanan untuk mobil, tugas untuk pengemudi dirumuskan sebagai tumpukan di gudang dan tumpukan faktur cetak.Jadi, kembali ke Gazelle. Wilayah kami adalah jalan raya Penggemar dan lebih jauh menuju Noginsk, akan ada sekitar 15 pesanan ke Moscow Ring Road, saya akan pergi ke sana. Pengemudi berangkat ke Cincin Transportasi Ketiga, di mana pengirim mengambil paket faktur dan mentransfernya dalam urutan yang benar. Urutan yang benar adalah ini:- Pertama, kita akan berkendara di sepanjang jalan raya Penggemar menuju Moscow Ring Road dan menerima semua pesanan yang ada di sebelah kanan. Kami tidak selalu membawanya di sebelah kiri, mungkin ada kemacetan saat melintasi jalan raya, lebih baik membawanya di malam hari. Lalu kita akan pergi ke wilayah itu, kita akan membawanya ke sana. Di malam hari kita akan kembali dan membawa sisanya.- Tapi, misalnya, urutan pertama di tumpukan - dengan keinginan "setelah 14 jam"? Biarkan saja malam ini?- Mungkin untuk malam hari, tetapi lebih baik untuk mencoba menyetujui untuk memberikannya sekarang.Proses negosiasi segera ditunjukkan. Pada jam 9:30, pengirim menelepon pesanan setelah 14 jam:- Halo, pengiriman, kami sudah berada di daerah Anda, dapatkah Anda menerima pesanan? ... Kami akan pergi ke daerah setelah daerah Anda, dan kami tidak akan kembali ke sini sebelum malam. Mungkin kami akan kembali setelah sembilan, atau mungkin kami akan tetap sepenuhnya di kawasan ini, ini adalah bisnis yang tidak dapat diprediksi, kami mungkin harus menunda pengiriman pada hari berikutnya ... Ya, maka kami akan tiba dalam 15 menit.Saat itulah saya menyadari dari mana datangnya para kurir, yang mengatakan: "Halo, saya sudah bersama Anda!" - dan sepenuhnya mengabaikan komentar dan interval pengiriman saya!Kolega yang mengendarai mobil lain memberi tahu saya bahwa ada seorang sopir atau pengirim yang dengan jujur menelepon klien satu jam sebelum pengiriman. Punyaku tidak terlalu ramah, mereka memanggil sekitar lima belas menit, mengucapkan komentar pelanggan dengan keras. Keinginan sederhana ("jangan panggil interkom, anak sedang tidur") diperhitungkan, tetapi segala sesuatu yang mempengaruhi rute biasanya diabaikan. Berganti-ganti faktur, forwarder mengambil pesanan yang harus dibawa ke sebuah desa beberapa kilometer dari Noginsk.- Oh, bibi ini lagi. Ingat, dia mendapat perintah, lalu kembali menikah? Sekarang pesanan baru.- Ya, angkat mesin cuci lagi. Yang menarik lainnya adalah: "tolong kirim dari 12 ke 16". Bagaimana dia membayangkannya?- Ya, secara umum, mereka tidak mengerti apa yang mereka tulis.Saya kira begitu: jika Anda memesan mesin cuci di Noginsk, maka duduklah di sana dan tunggu dengan tenang sampai dibawa. Entah setuju dengan tetangga, atau cuti kerja. Kita tidak bisa pergi dengannya Noginsk ini setiap hari.Saya turun di dekat Moscow Ring Road, dan sopirnya membawa Gazelle lebih jauh di sepanjang Gorky Highway. Faktanya, mereka bukan orang jahat, dan meskipun ada desas-desus terhadap pelanggan (jumlahnya setidaknya dua pertiga dari semua percakapan), mereka kemungkinan besar akan berhasil mengantarkan mesin cuci ke 16. Hanya jika mereka tidak melakukannya, mereka bahkan tidak akan repot-repot.Perjalanan kedua saya berlangsung di mobil yang lebih kecil: muatan yang dibawa Largus ke Distrik Administratif Barat Laut. Kargonya kecil, tidak ada lemari es, jadi sopirnya sendirian. Paman bergaul, kami banyak berbicara tentang dia. Dia mengatakan bahwa secara umum dia adalah master olahraga dalam gulat, bekerja sebagai pelatih, tetapi sekarang semuanya tuli, jadi dia moonlight sebagai kurir. Uang kecil, tetapi kenaikannya menyenangkan: sekitar 2 ribu diperoleh per hari. Sangat mudah untuk mengirimkan pesanan, berfungsi saat diinginkan. Tentu saja, ada nuansa: Anda menemukan pelanggan yang tidak menyenangkan, Anda harus makan sandwich yang disimpan di dalam mobil, Anda sedang terburu-buru, Anda bahkan tidak pergi ke toilet, Anda harus bertanya kepada pelanggan. Tapi secara keseluruhan, dia cukup makmur, baginya itu lebih cenderung hiburan.Itu lucu: kolega, terutama perempuan, karyawan jasa pengiriman juga menceritakan kisah bahwa "Kurir itu bukan pekerjaan utama, tetapi murni untuk jiwa", "Secara umum, saya biasanya pergi bertingkah laku", dll.Saya ingat bahwa kami mengadakan di daerah Rublevka atau Krylatsky percakapan seperti itu:- Setelah di Kota ia memesan, di sana mereka memiliki apartemen di gedung pencakar langit, koridor semuanya terbuat dari marmer, saya pergi ke apartemen - karpet, lukisan dalam bingkai emas, beberapa mantel bulu menggantung, yang tidak ada di sana. Pesanan untuk 5.800, jadi dia meminta perubahan 200 rubel, hitung ?!- Jadi, mungkin dia punya mantel bulu dan lukisan justru karena dia menyimpan bahkan 200 rubel.Setelah kata-kataku, pengemudi berpikir keras. Dan satu jam kemudian, kami tiba di Schukino dan saya "memahami segalanya" tentang bisnis ini.Dalam pena overhead berikutnya, sebuah catatan dibuat bahwa semuanya tidak sesuai dengan pesanan: dari tiga skuter anak yang dibeli dengan nilai total 20 ribu rubel, hanya dua yang ada di dalam mobil. Sopir itu memanggil ahli logistik. Ternyata wanita itu memesan tiga skuter pada hari Senin, tetapi kemarin, Rabu, skuter ketiga secara keliru dimasukkan ke dalam mobil yang salah. Dan itu adalah mobil pribadi, untuk beberapa alasan dia tidak kembali ke gudang di malam hari, seperti yang dilakukan pengemudi "biasa", dan skuter itu tetap mengendarainya. Kita bisa mencoba mencegatnya, tetapi hari ini dia menjalankan bisnisnya, tidak mungkin untuk menyeberang. Lain kali ia akan bekerja besok (Jumat), tetapi ini tidak akurat. Dijamin untuk menyatukan kembali ketiga skuter dan membawanya sekaligus hanya mungkin pada hari Sabtu.Berbekal informasi ini, pengemudi memanggil klien. Ada seorang wanita yang sangat tidak senang. Dia berkata: pada hari Sabtu jam 10 pagi mereka memiliki liburan keluarga, di mana mereka ingin memberikan skuter kepada ketiga anaknya. Karena itu, dia sangat membutuhkannya dalam jumlah tiga potong, dia tidak setuju untuk penebusan parsial dan tidak mengerti bagaimana itu mungkin sama sekali - dia memesan pada hari Senin, dan sekarang kita, toko skuter, menggantinya seperti itu. Pengiriman pada hari Sabtu pada waktu yang tidak ditentukan tidak sesuai untuknya. Besok dia ada di rumah sebelum makan malam, jika kamu tidak bisa hari ini atau besok pagi, dia membatalkan pesanan dan mengutuk toko sampai ke lutut ketiga (dan kamu bisa memahaminya).Bagian 3. Minimum lokal
Toko membeli layanan pengiriman pesanan dari perusahaan kurir. Untuk skuter yang tidak terkirim, ia akan mendenda perusahaan kurir sebesar 500 rubel. Perusahaan akan mendenda pemilik toko dan pengemudi yang tidak membawa skuter kembali tepat waktu dengan 200-300 rubel. Wanita yang kesal akan memberinya 20 ribu ke toko yang lebih gesit, dan satu bintang di Yandex.Market akan menamparnya. Toko dapat memberikan layanan terbaik, tetapi "jarak terakhir" dilakukan oleh orang-orang suram di Gazelles dan Largus. Jika mereka berperilaku buruk dengan pelanggan, toko tidak akan dapat memengaruhi ini.Pada saat yang sama, toko biasanya mencari pengiriman biaya terendah - dalam arti bahwa jika Anda membayar sopir lebih rendah, mereka akan pergi bekerja sebagai sopir taksi atau di tempat lain. Driver mengoptimalkan penghasilan hariannya - Anda perlu melakukan lebih banyak pesanan dan tidak didenda. Jika kita menyusun fungsi biaya global yang menggambarkan sistem secara keseluruhan, maka fungsi ini pasti akan sesuai dengan minimum lokalnya, “sumur potensial”.
Jelas ada masalah besar dan sistemik di lubang ini. Pertama, pekerjaan yang paling sulit diserahkan kepada karyawan yang paling tidak terampil: pengemudi mengendalikan mesin dan merencanakan rute dan berkomunikasi dengan klien. Dia juga membawa uang. Dia memiliki keterampilan dan spesialisasi tambahan - misalnya, kemampuan untuk mengirimkan 30 pesanan per hari di area tertentu. Ternyata perusahaan harus melatih pengemudi yang tidak berpengalaman, dan yang berpengalaman untuk tidak kehilangan, karena mereka (sayangnya untuk perusahaan) sulit untuk diganti.Kedua, proses pengiriman benar-benar tidak dapat diprediksi. Klien tidak tahu jam berapa mereka akan datang kepadanya. Pelanggan biasanya ditawari jendela pengiriman luas - empat, enam jam atau lebih. Ini menciptakan ketidaknyamanan yang luar biasa baginya: tidak selalu mungkin untuk duduk di satu tempat selama enam jam. Dan bahkan driver tidak selalu bisa masuk ke windows ini. Peluang untuk membuat jendela yang lebih sempit nyaman bagi pelanggan (dua jam, atau lebih baik satu jam) hanya mungkin bagi perusahaan besar yang mampu mendorong lebih keras dan melompat keluar dari lubang potensial ke keadaan yang lebih optimal. Kita berbicara tentang perusahaan dengan pengiriman dan kurir mereka sendiri. Kurir “milik sendiri” akan berguna bagi semua perusahaan: dengan cara ini Anda dapat mengontrol kualitas pekerjaan mereka dan bahkan melakukan semacam peningkatan (ketika kurir menawarkan seseorang untuk dibeli sesuai pesanan).Tetapi menjaga staf kurir itu sangat mahal - hanya perusahaan terbesar seperti WildBerries atau Lamoda yang mampu membelinya.Ketiga, ahli logistik terus menerus berbuat curang. Trik seperti mobil yang kelebihan muatan dan melanggar shift pengemudi dianggap biasa (bukan 8 jam, mereka bekerja 10-12). “Tidak apa-apa - jika tidak sesuai dengan volume, maka ia akan memasukkan kelebihannya ke dalam taksi” - bahkan ini terjadi. Untuk ini, dikenakan denda, terutama untuk truk yang kelebihan muatan: untuk denda itu sendiri (dari seratus ribu rubel per perusahaan) akan ditambahkan kompensasi untuk kerusakan pada roadbed. Ini dianggap sebagai perkalian dari koefisien kelebihan beban dengan jarak dan dapat dengan mudah mencapai ratusan ribu rubel. Pemilik armada akan senang mengemudi tanpa henti. Tetapi anggaplah ahli logistik memiliki pilihan:- “Sorong palet ekstra, sedikit melebihi”- “Tambahkan mobil ekstra, tambah biaya, tapi tanpa melanggar”- “Duduk selama setengah jam dan buat rencana dengan baik”Seringkali ia memilih yang pertama.Gambaran menyedihkan seperti itu menginspirasi kami dengan optimisme yang luar biasa. Kami melakukan beberapa wawancara dengan perusahaan-perusahaan di cabang logistik lainnya, seperti pengiriman barang besar, pengiriman dokumen. Semua hipotesis kami bahwa dunia tidak sempurna di tempat ini telah dikonfirmasi. Jadi, sebelum kita membuka jendela peluang yang besar. Kami dengan penuh semangat mulai bekerja.Bagian 4. MVRP dan kemacetan lalu lintas
Di bawah ini adalah rincian teknis dari produk kami, jadi mari kita mulai dengan definisi. MVRP adalah masalah beberapa rute kendaraan, yaitu tugas di mana Anda perlu berkeliling beberapa lokasi secara optimal, memiliki armada beberapa mobil. Kami menggunakan terminologi di mana tugas serupa untuk satu mesin disebut SVRP (VRP tunggal). Ini berbeda dari masalah salesman bepergian klasik (TSP, masalah salesman bepergian) dengan adanya jendela pengiriman. Tampaknya tidak ada terminologi yang menyatu: dalam sebuah artikel Wikipedia, tugas yang kami selesaikan disebut singkatan VRPPDTW yang kompleks (VRP dengan mode antar-jemput dan jendela pengiriman).Program yang memecahkan masalah seperti itu secara tradisional disebut "pemecah". Untuk keserbagunaan, Anda perlu menempatkan banyak opsi dan batasan di solver:Contoh opsi tambahan— , .
— (, ), .
— ( , ).
— . , : , .
— .
— .
— (, -), : . , * .
— «» , . , , - .
— : , .
Ada beberapa jenis algoritma yang dapat digunakan dalam solver. Misalnya, ada grup besar universal open source dan pemecah kendala berbayar (Google OR-Tools, OptaPlanner, Choco-solver). Dalam masing-masing dari mereka, fungsional dibangun yang dioptimalkan dengan mempertimbangkan pembatasan yang diperlukan. Pemecah masalah seperti itu biasanya dapat menyelesaikan sejumlah tugas: tugas VRP, penjadwalan, alokasi sumber daya yang optimal di cloud.Ada juga banyak solusi komersial yang dirancang khusus untuk tugas-tugas MVRP dan siap untuk diintegrasikan dengan sistem manajemen perusahaan. VeeRoute, Maxoptra, Antor dikenal di Rusia.Solver Yandex.Routing menggunakan kombinasi algoritma simulasi anildan algoritma genetika. Kami tidak tahu apa yang digunakan pesaing, tetapi kemungkinan besar serupa. Menurut pengukuran kami, dalam VRP-task constraint-solvers sangat kalah dengan solver komersial.
Solusi masalah TSP di bundaran negara bagian di AmerikaSaya akan segera melakukan reservasi: topik pemecahan masalah MVRP sangat besar sehingga kami tidak akan membahasnya secara rinci dalam artikel, melainkan menulis artikel terpisah.Input utama untuk pemecah adalah matriks jarak antara titik-titik yang terlibat dalam perencanaan (titik pesanan ditambah satu atau lebih depo). Sebenarnya, ini bukan satu matriks, tetapi dua: berdasarkan jarak tempuh dan waktu perjalanan. Melalui matriks inilah optimasi dilakukan. Seperti yang telah disebutkan, Yandex, tidak seperti pengembang solusi komersial lainnya, memiliki informasi lalu lintas. Bagi kami, matriksnya tidak konstan, tetapi berubah dalam waktu, dan kami memperhitungkannya dalam solver. Sejauh yang kita tahu, tidak ada yang melakukan ini di dunia: bahkan mengetahui segala sesuatu tentang kemacetan lalu lintas, sulit untuk membangun seperangkat matriks jarak dengan diskritisasi yang wajar (cukup untuk memastikan bahwa rute yang dihasilkan baik). Faktanya adalah bahwa jumlah sel matriks tumbuh kuadratik dari jumlah pesanan.Misalkan kita sedang menyelesaikan tugas VRP untuk mengirimkan 10.000 pesanan menggunakan armada 500 mobil. Lalu kami mendapatkan dua matriks besar yang berubah waktu. Mengunduhnya di jaringan saja akan memakan banyak waktu, tetapi kontennya harus dihitung terlebih dahulu. Jika ini tidak dilakukan dengan cukup efisien, kita perlu menunggu beberapa jam sampai matriks dibangun dan diunduh, dan baru kemudian solver dapat diluncurkan. Algoritma Dijkstra membantu kita di sini: perhitungan matriks jarak besar dapat diwujudkan dalam waktu yang hampir linier (dari ukuran matriks). Tetapi tim kami juga akan membicarakan hal ini dalam artikel terpisah dalam beberapa minggu mendatang.Jadi, kami membuat solver cerdas, memparalelkannya ke sekelompok mobil, membuat router dengan matriks jarak sangat cepat yang memperhitungkan kemacetan lalu lintas, dan juga menemukan cara untuk memasukkan matriks ini ke dalam solver. Alhasil, mereka mendapat kesempatan dalam 15 menit untuk menyelesaikan masalah mengemudi di sekitar 3.000 lokasi. Hasil di peta:
Bagian 5. Hasil dan kesulitan implementasi
Anda dapat membandingkan rute kami dan rute yang dibangun oleh ahli logistik yang merencanakan perjalanan secara manual atau (kadang-kadang) dalam mode semi-otomatis menggunakan program pesaing. Dalam kasus tertentu, solusi kami memungkinkan Anda untuk mengalahkan para ahli logistik dengan rata-rata 20% dengan rute kecil secara optimal. Pada saat yang sama, waktu untuk mendapatkan rute selesai jauh lebih rendah - 15 menit, bukan beberapa jam. Di masa depan yang indah, ahli logistik harus berubah dari orang yang kelelahan dan gugup menyebarkan pesanan dengan mobil di tengah malam, menjadi anggota masyarakat yang terhormat. Dia akan menggunakan perencanaan otomatis kami dan sesekali mengoreksi kasing tunggal dengan tangannya.Implementasi berjalan paling lancar ketika pelanggan membeli solusi kami pada saat membuka layanan pengiriman mereka. Tetapi sebagian besar pelanggan kami bukanlah hal baru. Mereka sudah memiliki solusi yang diterapkan untuk logistik, dan semakin besar klien, semakin kuat ia telah ditumbuhi segala macam fitur dari proses perusahaan ini, dan hanya kruk. Pengembangan dan dukungan mereka dilakukan oleh layanan IT mereka sendiri atau yang disewa. Diyakini bahwa perusahaan besar (bahkan jika keunggulan produk kami jelas bagi mereka) dapat mengimplementasikan Routing hanya bersama dengan pembaruan besar infrastruktur TI. Dan ini biasanya terjadi setiap beberapa tahun. Pada Mei 2018, layanan bayi baru lahir kami diumumkan di konferensi YaC 2018 dalam kemitraan dengan IKEA. Enam bulan kemudian, implementasi dimulai, kami mulai bertukar data,dan setahun kemudian pada konferensi industri tentang logistik, manajer proyek di IKEA berbicara tentang hasilnya.Hasilnya positif, tetapi sedikit tidak terduga bagi kami. Misalnya, memberi tahu pelanggan meningkatkan kepuasan mereka dan secara signifikan mengurangi jumlah panggilan ke pusat panggilan (sebelum, tanpa mengetahui apa pun tentang nasib sofa, orang-orang gugup dan mulai menelepon).Atau contoh lain - dengan pekerja industri minyak., . , . , « » — . , , , «» ( , YouTube , ). , ( , ), , . : — , , , . . .
Artinya, ternyata instalasi awal kita tidak sepenuhnya benar. Kami berpikir bahwa kami akan menjual jalan memutar poin yang efektif, tetapi ternyata perusahaan membutuhkan produk yang berbeda yang mempengaruhi indikator yang berbeda, dan tidak hanya dan tidak terlalu banyak pada efisiensi. Untungnya, kami menyediakan beberapa lagi dengan produk teknologi inti.Perusahaan kecil lebih baik dalam mengatasi kesulitan integrasi, tetapi mungkin menghadapi faktor manusia. Sangat sulit untuk meyakinkan pengemudi untuk mengikuti rute yang direncanakan dan menjaga ponsel dengan aplikasi pelacakan dihidupkan. Ini agak mengingatkan kita pada cerita-cerita tentang para petani abad ke-19 yang memecahkan mesin potong dan bajak mekanis. Segala sesuatu, tentu saja, tidak begitu menyedihkan, tetapi ada perlawanan terhadap kemajuan.Kesimpulan
Dalam waktu singkat, kami berhasil membangun produk yang, kami harap, akan mengubah semua logistik di negara ini (atau paling tidak sangat berpengaruh). Pelanggan dan Yandex kami saat ini percaya pada kami. Yang terakhir juga penting: ya, startup internal lebih tenang daripada startup di luar perusahaan, tetapi kita juga perlu menunjukkan hasilnya.Kami mulai dengan penekanan pada perusahaan besar, dalam rencana masa depan kami - untuk menurunkan ambang batas untuk memasuki layanan. Anda dapat bermain-main dengan menyelesaikan tugas SVRP secara langsung di Yandex.Maps: ketika Anda menambahkan titik keempat ke rute, tombol "Optimalkan" muncul, yang memanggil pemecah kami.
Video cerita yang sama untuk siswa FCS di HSE:Semua rute terbaik!