Algoritma pengepakan 3d untuk pengiriman barang

Saya telah menerima tugas untuk membuat estimasi pengiriman yang menyarankan akomodasi barang terbaik di sesedikit mungkin kotak:

1. Ada satu set terbatas dari ukuran kotak retangular yang diketahui

2. Ada banyak item retangular sewenang-wenang untuk dikemas di dalam kotak

3. Semakin sedikit kotak sebaiknya digunakan yang terbaik. Karena pengiriman dua kotak 1x1x1 jauh lebih mahal daripada satu kotak 1x2x1. Ini harus menjadi prioritas di sini.

4. Ini juga harus dioptimalkan untuk menggunakan kotak yang lebih kecil mungkin, sebagai prioritas tingkat kedua. (mis .: jika disajikan dengan pilihan antara satu kotak besar dan dua kecil, itu harus memilih kotak lebih besar)

5. Barang-barang dapat diputar agar sesuai dengan kotak, tetapi rotasi harus dibatasi pada kenaikan minimal 45 ° (dalam penelitian saya tampaknya beberapa konfigurasi memungkinkan rotasi 45 derajat agar lebih sesuai dengan kotak retangular di dalam kotak retangular yang lebih besar) , menjadi 90 ° rotasi standar yang harus diambil.

6. Kotak memiliki batas berat dan item memiliki bobot sewenang-wenang (mis .: item dengan ukuran 1x1x1 dapat lebih berat daripada item 2x2x2 lainnya)

Saya telah meneliti sedikit dan menemukan beberapa algoritma abstrak pada pengemasan bin dan masalah ransel dan datang dengan variasi agak kasar berikut, mirip dengan algoritma paling sesuai:

1. Sortir item dalam urutan volume menurun (lebih besar dulu) pada daftar "item untuk dikemas"

2. Untuk setiap item dalam daftar ini:

   1. Pilih kotak yang lebih kecil yang ada di daftar "kotak bekas" dan memiliki volume yang tersisa dan batas berat yang sesuai dengan item (Saya akan menggunakan cocok di sini berarti menyesuaikan dimensi dan berat)

   2. Jika tidak ada kotak seperti itu, buat kotak baru dari kumpulan ukuran kotak yang mungkin diketahui yang merupakan ukuran terkecil yang sesuai dengan dimensi dan berat item dan tambahkan ke daftar "kotak bekas".

   3. Jika sebuah kotak cocok dengan item (menggunakan fungsi pas di bawah), tambahkan ke daftar "item kotak ini" dan hapus dari daftar "item yang cocok", tandai itu posisi 3d relatif di dalam kotak.

   4. Ulangi dari 2.1 hingga tidak ada item yang akan dipasang pada daftar "items to pack".

Fungsi pemeriksaan pas digunakan pada langkah 2 di atas:

1. Periksa apakah volume sisa kotak cocok dengan volume item. Jika tidak, kembalikan salah.

2. Periksa apakah jumlah berat "item kotak" ditambah berat item saat ini kurang atau sama dengan batas berat kotak. Jika tidak, kembalikan salah.

3. Periksa daftar "item kotak" untuk memilih koordinat kotak pertama yang memiliki komponen Y terkecil dan yang memiliki ruang yang cukup untuk lebar, kedalaman, dan tinggi item, dengan mempertimbangkan item lain yang ditempatkan sebagai ruang yang tidak tersedia.

4. Jika item tidak sesuai dengan orientasi saat ini, putarlah pada salah satu dari 6 kemungkinan rotasi, jangan anggap rotasi 45 ° untuk kesederhanaan. (Rotasi yang menghasilkan ukuran di mana yang sudah diuji dapat dilewati. Misalnya: memutar kotak 180 ° memberikan dimensi yang sama dengan posisi aslinya karena semua kotak dan item memiliki ukuran yang sama untuk wajah yang berlawanan sehingga dapat dilewati.)

5. Jika item belum diputar pada semua cara yang mungkin kembali ke orientasi aslinya, coba lagi dari langkah 3.

6. Jika semua rotasi tempat dicoba dan tidak ada kecocokan ditemukan, pertimbangkan koordinat saat ini sebagai ruang yang tidak tersedia.

7. Jika tidak ada ruang untuk memeriksa, kembalikan salah. Lain, coba lagi dari langkah 3.

Saya ingin tahu apakah ada solusi terbaik untuk masalah saya, mengingat kendala yang disajikan.

Ini sepertinya bekerja pada teori tetapi saya belum mencobanya pada kode. Saya ingin tahu apakah saya akan ke arah yang benar atau ada cara yang lebih baik dan performan untuk melakukan ini.

Referensi akan sangat bagus.

Edit:

Saya telah menemukan beberapa API pihak ke-3 yang menarik yang melakukan apa yang saya inginkan, tetapi ini harus diputus, jadi saya tidak akan memiliki akses ke ini.

Beberapa contoh adalah:

• http://v2.3dbinpacking.com/demo/main
• http://www.packit4me.com/api

Edit 2:

Contoh dunia nyata masalah yang harus dipecahkan adalah:

• Saya memiliki 4 ukuran kotak WxHxD: 10x12x18, 12x16x24, 16x20x30, 24x32x40
• Saya memiliki pesanan 4 item, yaitu 1 ukuran 6x8x10, 2x 22x14x30, dan 1x 22x4x20

Bagaimana saya memasukkan barang-barang ini ke dalam sejumlah kotak dengan satu ukuran atau lebih menggunakan kotak sesedikit mungkin, menggunakan kotak sekecil mungkin dan menyisakan ruang kosong sesedikit mungkin?

Tempat sampah sangat sulit secara komputasi. Pikirkan setengah dari masalah: Anda ingin mengemas produk dalam kotak pengiriman tanpa ada pemborosan di dalam kotak. Solusi optimal untuk itu akan membutuhkan melalui semua himpunan bagian yang mungkin dan semua kemungkinan pengaturan 3d dari produk yang perlu dikirim dalam satu truk. Saya akan memberi Anda solusi optimal untuk itu karena saya punya teman yang melakukan enam hal yang mustahil sebelum sarapan.

Sekarang Anda hanya perlu mendapatkan semua kotak di truk tanpa pemborosan. Teman saya melakukan hal mustahil kedua dan memberi Anda solusi. Sayangnya, dengan ukuran kotak yang Anda pilih di atas, ada ruang kosong di truk yang dapat dikurangi jika Anda memilih kotak yang berbeda (baik yang lebih besar atau lebih kecil) pada tugas pertama. Jika Anda mengubah ukuran satu kotak, paling baik Anda harus mengemas kembali truk; paling buruk, Anda mungkin harus mengemas ulang semua kotak yang sama sulitnya dengan masalah yang kami mulai. Dan, seperti pada tahap pertama, Anda harus mencoba semua pengaturan 3d yang mungkin.

Saya menemukan The Algorithm Design Manual milik Skiena sangat membantu untuk berpikir tentang kelas algoritma apa yang cocok dengan jenis masalah yang mana, tetapi saya sebagian besar belajar bahwa solusi yang baik untuk masalah biasa bahkan yang meledak di dalam Anda hadapi dengan kesulitan komputasi. Sebagian besar dari apa yang Anda butuhkan masuk ke dalam kelas masalah bin-packing dan artikel itu adalah titik loncatan yang baik. Perlu dicatat bahwa beberapa algoritma terbaik untuk ini adalah produk komersial karena tugas ini muncul di mana-mana dalam logistik (berapa jumlah kereta mobil terkecil yang dapat saya bawa barang-barang saya? Dan semacamnya). Ada banyak uang yang harus dihasilkan jika heuristik yang tepat dapat menghemat 100 gerbong kereta per bulan.

Sayangnya, literatur tentang mengoptimalkan heuristik tidak hampir sebesar algoritma. Jika Anda mencoba melakukannya sendiri, saya jamin Anda akan bermimpi tentang memindahkan prisma persegi panjang pada bulan kedua Anda. Saya memiliki masalah yang sulit, jika saya harus melakukannya lagi, saya mungkin akan mencari ahli (atau perangkat lunak kesopanan mereka).

Terima kasih kepada @JTrana untuk perluasan komentar saya yang bagus.

Ketika membuat algoritma baru, dan saya baru saja melakukan algoritma pengemasan sendiri (saya tahu masih memiliki beberapa potensi optimasi), saya selalu melakukan pendekatan yang paling sederhana:

Bagaimana saya sebagai manusia melakukannya, dan mencoba menerjemahkannya ke dalam sebuah algoritma: Dari (AI) robotik saya, Rolf Pfeifer, saya masih ingat, bahwa kecerdasan yang jelas kadang-kadang dapat dibuat dengan beberapa aturan yang sangat sederhana, jadi alih-alih melakukan rekayasa ulang Saya mencoba untuk underengineer

1. Identifikasi barang yang terlalu besar (barang yang tidak cocok dengan kotak apa pun)
2. Cobalah untuk menemukan kotak terbaik yang mungkin (dengan membandingkan volume total dan dimensi item)
3. Pesan barang dari besar ke kecil dan kotak (spasi) dari kecil ke besar
4. Pasangkan barang terbesar ke dalam ruang sekecil mungkin
5. Jika item terbesar tidak menemukan melompati dan coba berikutnya sampai tidak ada yang lebih cocok

6. Untuk item yang tersisa, cari kotak terbaik baru. ...

   X. selalu berpikir tentang peristiwa luar biasa (item kebesaran, bentuk aneh, jika sebuah kotak hanya berisi 1 item tidak akan lebih baik untuk mengirim item tanpa kotak ?, dll) tetapi Anda dapat membuat heuristik juga dalam bentuk keputusan pohon.

Tentu saja ada peringatan lebih lanjut semakin Anda dapatkan, saya hanya memberikan ide-ide ini sebagai titik awal. Dari sana ada banyak cara yang memungkinkan. Salah satu alternatifnya adalah dengan membagi sebuah kotak menjadi kubus kecil (mis. 5cmx5cmx5cm) dan melacaknya sebagai terisi / gratis. Pendekatan lain bisa disebut 3d tetris, dll.

Dengan pendekatan ini, Anda tidak perlu khawatir tentang ledakan kombinasatori. Di sisi lain, ledakan kombinasi dapat terjadi jika kita berbicara tentang muatan barang yang sangat banyak, tetapi sekali lagi: Apakah Anda benar-benar berpikir suatu perusahaan akan memeriksa item daftar kemasan berdasarkan item? Tidak, mereka akan mendekati solusi membagi dan menaklukkan: Membagi kompleksitas dengan menggunakan volume standar (misalnya palet, atau kotak berukuran tetap). Jadi, bahkan demi praktik, pertimbangkan bahwa tidak hanya melatih, terkadang waktu karyawan juga berupa uang. kereta bisa memuat x palet, setiap palet memiliki volume tetap, jadi bungkus item ke palet, tapi sekali lagi, mungkin palet terdiri dari beberapa pesanan, jadi gunakan kotak tetap untuk item, yang kemudian dimuat ke palet, yang kemudian dimuat ke dalam kereta.

Setidaknya begitulah saya sebagai manusia akan menangani tugas tersebut, dapatkan kotak terbaik, lalu muat item terbesar satu per satu di ruang terkecil yang tersedia (dan tambahkan sedikit pratinjau).

Seperti dalam algoritme saya, pada akhirnya Anda mungkin tidak akan memiliki solusi terbaik, tetapi heuristik yang jauh lebih baik yang kemudian dapat Anda perbaiki lebih lanjut.

Kadang-kadang lebih mudah untuk memulai dengan langkah pertama dan menyelesaikan masalah di jalan Anda, tentu saja idealnya bukan semacam langkah di atas langkah tepi, tetapi sedikit pintar ... kadang-kadang Anda mungkin terpaksa, untuk mencari alternatif dan memilih yang terbaik atau menerapkan "langkah mundur".

Tapi seperti yang saya pelajari dari guru AI saya (Rolf Pfeifer, maaf repot-repot dengan itu lagi): Kadang-kadang Anda dapat menciptakan perilaku cerdas yang tampak dengan beberapa peraturan yang sangat sederhana dan muncul beberapa perilaku dalam contoh yang disebutkan mereka memprogram mobil jarak jauh kecil untuk belok kiri jika mereka mendeteksi hambatan di sisi kanan, belok kanan jika ada hambatan di sisi kiri dan lurus jika tidak ada hambatan atau jika hambatan ada di depan. 3 atau 4 robot seperti itu, dimasukkan ke dalam persegi 3m x 3m dengan banyak bola ping-pong mengarah pada fakta luar biasa bahwa robot tampaknya membersihkan, mendorong bola ping-pong ke sudut-sudut, meskipun robot adalah hanya diprogram untuk menghindari rintangan.

PD: Satu-satunya penyimpangan dunia nyata yang saya temukan dari pendekatan ini adalah ketika saya paruh waktu bekerja sebagai tukang panggung untuk konser besar seperti metallica, iron maiden, britney spear, paul mcCartney, U nama itu ... Pengemudi truk yang bekerja di tur internasional memiliki daftar pengepakan yang tepat item demi item. Perhitungan dilakukan sekali (saya tidak tahu oleh manusia atau mesin), dan kemudian direplikasi. Kadang-kadang ketika mereka mengepak pertama kali, mereka bahkan membuat gambar lapis demi lapis dan menempelkannya di dalam truk agar kru setempat tahu persis, kotak mana yang harus diisi kapan dan di mana. Tetapi ini juga merupakan kebutuhan pengemasan khusus karena untuk satu tur mereka selalu bekerja dengan kotak dan truk yang sama.

Heuristik yang Anda sebutkan di pos Anda tampak menarik.

Saya akan menyarankan beberapa modifikasi untuk meningkatkan solusi akhir.

Diberikan solusi dengan semua item yang dikemas dalam satu kotak, cobalah untuk menggabungkan konten dua kotak kecil dalam satu kotak yang lebih besar (ini akan membantu dalam meningkatkan kriteria Anda menggunakan sesedikit mungkin kotak).

Atau, setiap kali Anda memulai kotak baru, alih-alih menggunakan kotak terkecil yang dapat mengakomodasi item saat ini, Anda bisa memilih kotak terbesar yang dapat menampungnya, dan begitu setiap item ditugaskan ke sebuah kotak, coba tetapkan semua item dari kotak ke kotak yang lebih kecil.

Juga, dalam fungsi pemasangan Anda, alih-alih mempertimbangkan posisi kotak Anda yang lain sebagai tetap, Anda dapat membayangkan mengubah urutan pemuatan. Ini akan memungkinkan Anda menemukan solusi yang lebih baik dengan mengorbankan waktu berjalan yang lebih lama.