Algoritma pengelompokan

8

Kami telah mengembangkan algoritma yang bergantung pada waktu check-in dari beberapa pekerja dan tempat tinggal mereka, menghitung cara untuk mengelompokkan mereka menjadi beberapa kendaraan dan rute yang harus diikuti oleh kendaraan untuk membawa mereka ke tempat kerja. Ini telah dicapai dengan menggunakan algoritma TSP (Traveling Salesman Problem) dan beberapa penyesuaian lainnya.

Kami ingin melampaui dan memperbaikinya. Untuk saat ini, kapasitas kursi kendaraan ditetapkan menjadi 4 (5 tempat tetapi satu ditempati oleh pengemudi) dan kami ingin menjadikan jumlah ini "variabel". Dengan kata lain, kami ingin, sebelum pelaksanaan algoritma utama, menentukan kombinasi kendaraan (dan kursi kosongnya) yang mungkin diperlukan. Penting untuk mengetahui bahwa ketika saya berbicara tentang kendaraan, saya berbicara tentang jenis kendaraan, misalnya Kendaraan A dari 4 kursi, Kendaraan B adalah dari 7 kursi, dan sebagainya. Jadi saya tidak berbicara tentang memiliki satu Audi A8 dari 5 kursi, Seat Ibiza dari 5 kursi, satu Bus dengan 20 kursi, katakanlah.

Sejauh ini, yang saya pikirkan adalah sebagai berikut:

  1. Tentukan kelompok pekerja.
  2. Tentukan berapa banyak kendaraan yang akan dibutuhkan dan kursi mereka (gratis). Itulah yang saya tanyakan dalam pertanyaan itu [a].
  3. Pengguna memilih kombinasi yang disukai dan melanjutkan.
  4. Terapkan algoritma yang sudah dikembangkan menggunakan kombinasi kendaraan dan lihat apakah mencapai solusi yang layak.

Pertanyaan saya adalah bagaimana mengembangkan algoritma [a]. Contoh berikut akan menunjukkan kepada Anda hasil dari eksekusi [a]:

Bayangkan kita memiliki orang-orang berikut untuk dikelompokkan menjadi kendaraan 4, 7, 10 kursi gratis. masukkan deskripsi gambar di sini

Setelah eksekusi [a], kita akan mendapatkan hasilnya:

  • G3 (2 pekerja): Satu kendaraan 4 kursi gratis (kendaraan dengan lebih banyak kursi gratis dibuang).
  • G2 (2 pekerja): satu kendaraan 4 kursi gratis (kendaraan dengan lebih banyak kursi gratis dibuang).
  • G1 (9 pekerja):

    • Opsi A: 3 kendaraan dari 4 kursi.
    • Opsi B: 1 kendaraan 4 kursi dan satu lagi 7.
    • Opsi C: 2 kendaraan 7 kursi.
    • Opsi D: satu kendaraan 10 kursi.

Saya sudah memikirkan perkiraan:

  • Buat jenis kendaraan dan tambahkan ke daftar yang diurutkan (kriteria penyortiran harus kursi).
  • Untuk setiap kelompok pekerja, lakukan:
    • Hitung kombinasi [b].
  • Cetak hasil di layar.

Jadi masalah utama adalah bagaimana mengembangkan [b].

Ada saran? Maaf jika saya telah menjelaskan diri saya dengan buruk.

russellhoff
sumber
1
Bukankah pengemudi harus menjadi bagian dari grup? Dari deskripsi Anda, sepertinya dia hanya mengendarai mobil. Apakah pengemudi hanya pengemudi khusus atau mereka bagian dari pekerja?
null
3
Saya akan mengatakan Anda hanya salah tentang itu. Dasar dari algoritma harus mengisi setiap kendaraan tetapi yang terakhir. Memperbaiki ukuran grup menjadi lubang besar dalam optimasi ini.
paparazzo
1
Mungkin ide yang baik untuk melihat literatur di sekitar "ukuran armada dan campuran masalah rute kendaraan" yang sejauh yang saya tahu masalah yang Anda coba selesaikan
Renaud M.
1
@ russellhoff Saya tidak tahu tentang JaCoP, tetapi Anda mungkin ingin mencoba di OR-tools. Ini adalah solver CP lain, yang memiliki Java API (mengingat perpustakaan yang Anda daftarkan tampaknya penting), yang tampaknya memberikan beberapa "spesialisasi" untuk masalah perutean kendaraan. Jika Anda melihat contoh yang mereka berikan, Anda mungkin dapat menemukan sesuatu yang dapat Anda adaptasi (Anda juga dapat melihatnya di developers.google.com/optimization/routing/tsp )
Renaud M.
1
"TSP (Traveling Salesman Problem) algoritma" - Aku tidak menyadari bahwa ada adalah algoritma tertentu untuk memecahkan TSP. AIUI, solusi paling umum adalah simulasi anil, tetapi ada juga pendekatan lain, saya percaya ...
Jules

Jawaban:

2

Saya telah menemukan solusi yang memungkinkan: memanfaatkan Masalah Kepuasan Kendala untuk menyelesaikannya.

Akan ada satu kendala per Grup, sebagai berikut:

jumlah pekerja dari kelompok <= jumlah per setiap kendaraan (jumlah kendaraan X kursi kendaraan)

Satu-satunya variabel ada jumlah kendaraan, sisanya adalah konstanta. Jadi, dalam contoh saya akan ada batasan berikut:

9 <= 4x + 7y + 10z
2 <= 4a + 7b + 10c
2 <= 4j + 7k + 10i

Saya menemukan beberapa perpustakaan (JaCoP, Drools dan OptaPlanner), dan saat ini saya menggunakan yang pertama. Tapi saya tidak tahu bagaimana mendefinisikan batasan ini dengan benar ...

russellhoff
sumber