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:
- Tentukan kelompok pekerja.
- Tentukan berapa banyak kendaraan yang akan dibutuhkan dan kursi mereka (gratis). Itulah yang saya tanyakan dalam pertanyaan itu [a].
- Pengguna memilih kombinasi yang disukai dan melanjutkan.
- 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.
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.
sumber
Jawaban:
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 ...
sumber