Bagaimana kami memilih kargo untuk operator

Selamat sore. Nama kami adalah Ilya Bashtanov (pengembang, Tochka-Tochka ) dan Tatyana Voronova (analis data, 2M Center ). Dan kami ingin berbicara tentang pelaksanaan teknis tugas memilih barang untuk transportasi.

Inti dari masalah adalah sebagai berikut. Ada barang di gudang yang perlu diangkut dari kota A ke kota B. Kita dapat mengasumsikan bahwa hanya berat barang yang diperhitungkan, dan ukurannya lebih atau kurang standar (palet euro). Pengangkut yang ingin mengambil barang yang lewat ingin membawa sebanyak mungkin, tetapi dibatasi oleh berat dan jumlah paket. Penting untuk membentuk baginya beberapa varian lot dari barang yang tersedia di gudang.

Tugas yang diselesaikan untuk bisnis dalam hal ini:

1. Muat kendaraan seefisien mungkin dan dengan demikian meningkatkan pendapatan transportasi.
2. Untuk memecahkan masalah pengiriman dalam waktu yang dapat diterima bagi pengguna (termasuk prinsip FIFO).

Proyek itu segera tampak menarik. Pertama, dari sudut pandang matematika: diusulkan untuk mengimplementasikan algoritma untuk menyelesaikan masalah optimisasi kombinatorial klasik. Kedua, PostgreSQL diusulkan sebagai DBMS, popularitasnya terus meningkat dalam beberapa tahun terakhir karena sejumlah besar fitur, keandalan, dan karakteristik kinerja yang baik. Dan, tentu saja, pentingnya tugas praktis dan skala proyek, yang melibatkan banyak peserta yang berbeda, juga menjadi insentif besar.

Algoritma

Tugas ini merupakan varian dari masalah pengemasan backpack klasik . Masalah ransel adalah NP-lengkap . Masalah seperti itu tidak dapat diselesaikan dalam waktu polinomial, meskipun secara matematis ini belum terbukti. Ini berarti bahwa algoritma yang tepat, seperti pencarian lengkap varian atau varietas yang dioptimalkan, tidak bekerja dalam praktik, karena mereka memiliki kompleksitas$$$O(2^n)$. Metode perkiraan memberikan solusi untuk waktu terbaik. Sebagai contoh, algoritma serakah mengasumsikan bahwa berat maksimum dimasukkan ke dalam ransel selama mungkin. Kompleksitasnya tidak melebihi kompleksitas penyortiran$$$(O(n * log n))$, tetapi hasilnya mungkin jauh dari optimal. Masih ada kelas algoritma genetika yang memberikan hasil yang baik dalam waktu yang terbatas, tetapi mereka tidak deterministik, yang dalam kasus kami akan mengarah pada opsi yang berbeda untuk mengeluarkan selama panggilan berulang, akan sulit untuk menjelaskan kepada pelanggan dan operator. Akibatnya, pilihan jatuh pada metode perkiraan yang memberikan hasil dengan akurasi yang dijamin dalam waktu polinomial.

Jadi kita punya:

• Bobot dengan bobot $$$w_1,w_2,... , w_n$
• Batasi berat total barang $$$W_\max$
• Batas muatan $$$Q_\max$

Diperlukan untuk menemukan subset barang dengan berat total maksimum yang memenuhi kendala.

Idenya adalah untuk mengurangi variasi barang dengan mengelompokkan bobotnya dan menerapkan algoritma serakah. Dalam hal ini, solusi perkiraan ditemukan dalam waktu sepenuhnya polinomial, yaitu solusi dengan akurasi yang terjamin$$$1- \varepsilon$ diperoleh dengan kompleksitas menjadi polinomial dalam $$$n$dan $$$\varepsilon$.

Pada input algoritme, kami memiliki piring yang berisi bobot bulat barang dan jumlah kursi untuk setiap berat. Menggunakan algoritma serakah, kami mencoba untuk mendapatkan opsi penataan untuk total bobot$$$W_\max,$ $$$W_\max-1,$$$$W_\max-2,$$$$…,$$$$0$. Untuk melakukan ini, setelah menetapkan berat total target, dalam siklus kami memilih muatan maksimum dari muatan yang tersisa agar tidak melebihi berat total target. Jika jumlah maksimum yang diijinkan tercapai$$$Q_\max$, siklus berakhir. Kombinasi yang dihasilkan disimpan dalam array sementara.

Jumlah kombinasi yang mungkin dapat menjadi besar, dan mudah bagi pengguna untuk memilih dari sejumlah kecil opsi, tetapi pada saat yang sama masih harus ada pilihan. Tugas tambahan muncul untuk memilih kombinasi yang disukai. Agar tidak rumit, kami memutuskan untuk selalu memberikan dua opsi, jika memungkinkan. Untuk sebuah gudang, pertama-tama disarankan untuk mengirim muatan terberat, jadi kami memberi peringkat kombinasinya dalam urutan menurun dengan bobot terbesar kargo. Jika kombinasi dengan berat maksimum maksimum lebih dari dua, kami memberikan dua: dengan jumlah barang terbesar dan paling sedikit.

Tes

Untuk pengujian, kami memilih dua implementasi dari algoritma yang dipertimbangkan, yang berbeda dalam detail yang tidak signifikan: satu di Jawa, yang lain di PL / pgSQL, bahasa prosedural dari DBMS PostgreSQL. Harus dicatat segera bahwa pilihan akhir dipengaruhi tidak hanya oleh hasil tes, tetapi juga oleh pertimbangan arsitektur, kegunaan dan faktor lainnya. Tapi pertama-tama, tugasnya adalah memilih satu dari dua implementasi.

Dua lingkungan pengujian digunakan: desktop untuk pengembangan pengujian dan server untuk pengujian dalam kondisi yang mirip dengan yang asli.

• dev: Stasiun klien HP Probook 4740s + 32-bit 2 x Pentium® Dual-Core CPU E5300 @ 2.60GHz dan RAM 4 GB, Ubuntu Linux 16.04, PostgreSQL 10.3.
• test: 64-bit 2 x Intel Xeon CPU E5-2673 v4 @ 2.30GHz 14 , CentOS Linux 7.4, PostgreSQL 10.3

Tabel uji disiapkan dalam database PostgreSQL yang berisi 7000 beban dengan bobot acak dari 20 hingga 800 kg. Untuk pengujian, kami menggunakan utilitas pgBench standar dari PostgreSQL, yang melakukan 500 transaksi selama pengujian (masing-masing 10 koneksi dari 50 transaksi). Setiap transaksi membuat satu panggilan algoritma dengan parameter acak (pembatasan berat dari 10 hingga 1000 kg dan jumlah barang dari 1 hingga 50 buah). Semua variabel acak didistribusikan secara merata.

Untuk algoritma pertama, setiap transaksi memulai mesin Java dan melewati arsip JAR dengan kode algoritma untuk dieksekusi. Kelas Java utama yang terhubung ke database melalui driver JDBC, menerima data uji dari tabel dan menerapkan algoritma pada mereka.

Untuk algoritma kedua, setiap transaksi melakukan panggilan ke fungsi tersimpan dari database PostgreSQL, yang membaca data uji dari tabel dan menerapkan algoritma.

Tabel 1. Hasil tes utama



Selain tes utama, hasil yang ditunjukkan pada tabel 1, tes tambahan algoritma 2 dilakukan, di mana berbagai pilihan untuk memperoleh data awal dibandingkan: dari database, dari file, generasi array acak. Ternyata untuk 7000 beban, mentransfer data dari DBMS ke array lokal membutuhkan lebih banyak waktu daripada algoritma susun yang sebenarnya.

Temuan

1. Dalam tugas kami, kinerja lebih tergantung pada arsitektur sistem dan kecepatan interaksi dengan database daripada pada algoritma yang digunakan. Ini dikonfirmasi oleh tes tambahan algoritma 1, di mana pemilihan data dari database mengambil sebagian besar waktu.
2. Opsi 2 skala sedikit lebih baik, tampaknya karena persyaratan RAM yang lebih sederhana (tabel database sementara digunakan untuk menyimpan hasil antara).

Akibatnya, algoritma kedua dipilih, yang, dengan perubahan kecil, digunakan untuk tahun kedua. Akibatnya, solusi dicari dengan akurasi yang dapat diterima dengan waktu transaksi rata-rata kurang dari 1 detik.

Eksploitasi

Seperti biasa, hidup membuat penyesuaian, dan saya harus mengubah implementasi.

Pada kenyataannya, operator menyimpan kiriman dalam lelang Yankee dengan harga mengambang. Sebenarnya, opsi penjualan dengan lelang ini tidak, tetapi ini adalah topik percakapan terpisah di situs lain. Selain berat kargo maksimum dan jumlah maksimum, operator menetapkan dua kota (awal dan akhir rute) dan waktu pemuatan yang diinginkan. Setelah itu, prosedur pemilihan untuk setiap pasangan gudang (di kota-kota pengirim dan tujuan) menyaring kargo berdasarkan beberapa kriteria, khususnya, dengan mempertimbangkan jam kerja gudang dan biaya transportasi maksimum di mana pengeluaran masih ditanggung oleh pembayaran pengirim, dan mentransfer bobot mereka ke algoritma susun. Pada output algoritma, daftar bobot diperoleh, sesuai dengan set barang tertentu yang dipilih, yang dikeluarkan sebagai penawaran lelang.

Awalnya, bobot dibulatkan ke nilai yang merupakan kelipatan 10 kg. Selama operasi, menjadi jelas bahwa keakuratan terlihat sangat buruk, dan hasilnya mulai bertentangan dengan akal sehat, misalnya, dengan adanya barang dengan berat 12 dan 19 kg, sistem dapat memilih yang pertama. Timbangan gudang memberikan data dengan akurasi 1 kg, dan untuk volume dan beban saat ini, kinerja algoritma untuk nilai integer dari timbangan ternyata cukup dapat diterima, sehingga mereka menolak pembulatan. Di masa depan, dengan peningkatan jumlah pengiriman, direncanakan untuk menggunakan pembulatan ke nilai yang merupakan kelipatan 5 kg.

Overhead untuk pengoperasian algoritma susun dengan volume data saat ini dan intensitas kueri tidak kritis. Secara signifikan dibutuhkan lebih banyak sumber daya pada tahap pemilihan kargo, serta untuk proses operasi sistem lainnya.

Temuan bisnis

Misi Point-Point adalah proses logistik yang efektif, khususnya, penggunaan kendaraan yang optimal dalam hal kemacetan: ketika mengangkut minimum void.

Tujuan global menyelesaikan masalah optimisasi dalam angkutan barang: menghemat sumber daya berkontribusi pada pertumbuhan ekonomi, menciptakan peluang tambahan untuk usaha kecil dan menengah, dan memperbaiki lingkungan.

Spesialis dari Centre 2M dan Tochka-Tochki menemukan solusi perangkat lunak-matematika yang cocok untuk semua peserta dalam proses transportasi. Ini dapat digunakan untuk jaringan federal, di setiap titik yang 7 ribu palet (sesuai dengan ukuran lapangan sepak bola) diminta oleh 500 operator dan dengan hasil yang diperoleh dalam waktu kurang dari 1 detik.

Penulis artikel: Ilya Bashtanov (i-bash), Tatyana Voronova (tvoronova)