Pemuatan Bus yang Efisien

Ini adalah sesuatu yang saya lakukan untuk sebuah perusahaan perjalanan bus di masa lalu, dan saya tidak pernah senang dengan hasilnya. Saya sedang memikirkan proyek lama itu baru-baru ini dan berpikir saya akan meninjau kembali masalah itu.

Masalah:

Perusahaan perjalanan bus memiliki beberapa bus dengan kapasitas penumpang yang berbeda (mis. 15 bus 50 penumpang, 25 bus 30 penumpang ... dll). Mereka berspesialisasi dalam menawarkan transportasi ke grup yang sangat besar (300+ penumpang per grup). Karena setiap kelompok perlu melakukan perjalanan bersama, mereka perlu mengelola armada mereka secara efisien untuk mengurangi limbah.

Misalnya, 88 penumpang lebih baik dilayani oleh tiga bus 30 penumpang (2 kursi kosong) daripada dua bus 50 penumpang (12 kursi kosong). Contoh lain, 75 penumpang akan lebih baik dilayani oleh satu bus 50 penumpang dan satu bus 30 penumpang, campuran jenis.

Apa algoritma yang baik untuk melakukan ini?

Ini adalah (semacam) contoh dari masalah pengemasan bin, yang sering dikacaukan dengan masalah knapsack. Di tempat sampah, Anda memiliki nampan dengan kapasitas tertentu, dan Anda mencoba mendistribusikan benda dengan berbagai ukuran ke nampan. Idenya adalah untuk menggunakan jumlah sampah sesedikit mungkin.

Anda tidak benar-benar berusaha meminimalkan jumlah sampah, tetapi Anda mencoba meminimalkan jumlah kursi kosong. Dan mungkin saja Anda mencoba untuk meminimalkan jumlah kursi kosong di seluruh armada, yaitu, Anda memiliki empat grup tur dengan berbagai ukuran, dan Anda ingin mengakomodasi semuanya dengan jumlah kursi kosong paling sedikit. Saya tidak dapat memikirkan contoh langsung, tetapi saya membayangkan mungkin untuk membuat armada dan satu set kelompok tur sehingga Anda akan lebih baik dengan solusi di bawah standar untuk beberapa kelompok karena memungkinkan Anda untuk menghindari menggunakan solusi yang lebih buruk untuk beberapa grup lain.

Itu semakin buruk. Bagaimana jika Anda memiliki 20,30, dan 50 bus penumpang. Masing-masing menggunakan jumlah bahan bakar yang berbeda, tetapi lebih efisien menjalankan satu 50 daripada menjalankan 20 dan 30. Tetapi dari ukuran tunggal kami (paling sedikit jumlah kursi kosong), masuk akal untuk menjalankan baik untuk 50 tur penumpang.

Juga, bus-bus dengan angka aneh, seperti 28 atau 39, akan condong banyak pintasan kami.

Jadi, tergantung pada kompleksitas situasinya, Anda dapat melakukan satu dari dua hal:

Pertama, dan pohon pencarian lengkap: gunakan setiap kemungkinan kombinasi bus. Jika Anda hanya memiliki 3 atau 4 ukuran bus, ini mungkin solusi yang masuk akal. Kalau tidak, sesuatu seperti penurunan kecocokan Terbaik akan menghasilkan hasil yang masuk akal, tetapi tidak optimal.

Inilah solusi cepat dan kotor di Python:

def add50(passengers, buses):
    proposed = buses + [50]
    if sum(proposed) < passengers:
        return add50(passengers, proposed)
    return proposed

def add30(passengers, buses):
    proposed = buses + [30]
    if sum(proposed) < passengers:
        proposed30 = add30(passengers, proposed)
        proposed50 = add50(passengers, proposed)
        return proposed30 if sum(proposed30) < sum(proposed50) else proposed50
    return proposed

print add30(88, [])
print add30(75, [])
print add30(105, [])

Ketika saya menjalankannya, saya mendapatkan:

[30, 30, 30]
[30, 50]
[30, 30, 50]

Kode melakukan pencarian mendalam-pertama melalui skenario yang mungkin. Karena pesanan tidak masalah ( [30, 50]sama dengan [50, 30]), kami dapat membuat ruang pencarian jauh lebih kecil dengan hanya menambahkan bus dengan ukuran yang sama atau lebih besar. Itu sebabnya add30()bisa menelepon add50(), tetapi tidak sebaliknya.

Saya akan menjawab ini dari perspektif pelanggan. Saya tidak ingin algoritma kode keras untuk aplikasi ini. Ada terlalu banyak variabel yang dapat berubah seiring waktu. Meskipun tidak ada apa pun tentang bus Anda yang dapat mengubah bobot faktor-faktor yang dapat berubah atau faktor-faktor baru dapat ditemukan yang tidak pernah saya pikirkan (misalnya kelebihan waktu, undang-undang, dan biaya pengemudi lainnya).

Karena itu, saya ingin dapat membuat tabel pencarian saya sendiri berdasarkan sejumlah jumlah penumpang yang diminta dan saya akan membuat pengaturan sendiri untuk kombinasi bus terbaik. Contoh: 31-50 = 1 X 50, 51-60 = 2 X 30. Apakah ini benar-benar perlu dihitung? Lebih mudah untuk mengubah pengaturan daripada sekelompok formula yang memfaktorkan kursi, bensin, dan pengemudi. Cari tahu kombinasi terbaik dan lakukan dengan itu dan punya banyak ruang bagi pengguna untuk mengubah pengaturan ini sesuai keinginan mereka.

Faktor-faktor baru dapat ditemukan. Apakah bus yang lebih besar membayar tarif tol yang secara eksponensial lebih tinggi? Bisakah saya mendapatkan driver yang lebih murah untuk bus kecil ketika undang-undang baru untuk sertifikasi tambahan dan lisensi naik pada driver bus lebih dari 30 penumpang?

Mereka menyewa konsultan baru dengan logika berbeda dengan formula mereka dan aplikasi Anda mungkin perlu ditulis ulang. Maksud Anda, Anda harus memperhitungkan biaya parkir?