Beberapa aplikasi klasik riset operasi
Ketika diterapkan untuk mengatasi masalah-masalah dalam kehidupan nyata, matematika menjadi lebih indah dan menarik. Ini adalah kasus riset operasi, sebuah subbidang matematika terapan, di mana masalah diformulasikan secara matematis sebelum diselesaikan. Selama beberapa tahun terakhir, subbidang ini berkembang sejalan dengan perkembangan daya komputasi. Saat ini, banyak organisasi menggunakan riset operasi untuk merancang keputusan operasional, taktis, dan bahkan strategis. Jika berhasil, hal ini akan menghasilkan pengurangan biaya yang signifikan dan/atau peningkatan keuntungan. Masalah yang ditangani biasanya melibatkan penugasan, penjadwalan, perutean, pemasangan, partisi, serta tugas-tugas lain dalam kerangka waktu dan / atau ruang tertentu.
Dalam artikel ini, saya ingin membahas beberapa aplikasi populer yang pernah saya lihat di lab saya di mana riset operasi telah cukup berhasil. Hal ini dapat dianggap sebagai sebuah gambaran awal untuk pola pikir yang ingin tahu. Masalah yang akan dipaparkan secara singkat adalah masalah perutean kendaraan (VRP), masalah perencanaan penerbangan (APP), masalah penjadwalan supir bus (BDSP), masalah penugasan lokomotif (LAP), dan masalah penjadwalan shift (SSP). Masalah pemotongan stok, yang juga terkenal, telah dipaparkan di salah satu artikel saya sebelumnya.
Masalah perutean kendaraan (Vehicle Routing Problem)
VRP dengan jendela waktu terdiri dari perancangan satu set rute berbiaya minimum, yang berawal dan berakhir di sebuah depot pusat, untuk armada kendaraan yang melayani sekumpulan pelanggan dengan permintaan yang telah diketahui. Pelanggan harus ditugaskan tepat satu kali ke kendaraan sehingga kapasitas kendaraan tidak terlampaui. Hal ini dapat digeneralisasi ke dalam VRP dengan jendela waktu (VRPTW) di mana, sebagai tambahan dari kondisi sebelumnya, layanan pada pelanggan harus dimulai dalam jendela waktu yang ditentukan oleh waktu paling awal dan waktu paling akhir ketika pelanggan mengizinkan dimulainya layanan. Topik ini telah dan masih banyak dipelajari dalam penelitian dan telah diterapkan pada banyak masalah kehidupan nyata. Dari definisi tersebut, kita dapat dengan mudah menyimpulkan bahwa untuk setiap organisasi yang mengoperasikan armada kendaraan dan melayani pelanggan tertentu, VRP dapat mendukung pengelolaan armada secara optimal, atau mendekati optimal, sambil mengurangi biaya dan meningkatkan keuntungan. Sebuah model sederhana disajikan di bawah ini.
Di laboratorium saya, banyak yang mengerjakan topik VRP dengan berbagai variannya. Hal ini ditangani secara heuristik atau secara tepat menggunakan teknik riset operasi tingkat lanjut seperti dekomposisi Dantzig-Wolfe dan Benders. Selain itu, mengingat banyaknya jumlah variabel, dibandingkan dengan jumlah kendala, pembuatan kolom, yang telah dipresentasikan di salah satu artikel saya sebelumnya, dilibatkan untuk membuat penyelesaian menjadi efisien dan efektif.
Masalah perencanaan maskapai penerbangan
APP adalah salah satu masalah yang paling menantang dalam bidang riset operasi. Masalah ini terdiri dari banyak submasalah yang diselesaikan secara berurutan atau simultan berdasarkan kerangka kerja optimasi yang digunakan seperti yang disajikan pada gambar di bawah ini. Submasalah tersebut adalah penjadwalan penerbangan, penugasan armada, rute pesawat, dan penjadwalan kru. Pada submasalah pertama, kita menentukan satu set penerbangan dengan waktu keberangkatan dan kedatangan tertentu dengan tujuan untuk memaksimalkan keuntungan yang diharapkan. Yang kedua, kita memilih jenis pesawat yang akan ditugaskan untuk setiap penerbangan terjadwal untuk memaksimalkan keuntungan, berdasarkan kapasitas yang berbeda dan jumlah pesawat yang tersedia. Yang ketiga, kami menugaskan masing-masing pesawat untuk penerbangan sambil memenuhi persyaratan pemeliharaan. Yang terakhir, kita menentukan jadwal kru yang mencakup semua penerbangan terjadwal dan memenuhi kendala, yang biasanya dilakukan dalam dua langkah: masalah pasangan dan masalah penugasan. Dalam pairing kru, kami menghasilkan satu set pairing yang diberikan penerbangan terjadwal sehingga biaya pairing diminimalkan dan semua penerbangan tercakup tepat satu kali, sementara dalam penugasan kru, kami membuat jadwal bulanan untuk setiap anggota kru yang diberikan satu set pairing sehingga setiap pairing tercakup tepat satu kali.
Dengan meningkatnya permintaan di industri penerbangan, masalah perencanaan penerbangan menjadi semakin kompleks. Oleh karena itu, menanganinya secara manual mungkin tidak akan menghasilkan manajemen biaya dan keuntungan yang efisien. Di sini, riset operasi, dengan kekuatan komputasi komputer saat ini, menjadi kandidat terbaik untuk menyelesaikan masalah ini dan menghasilkan keuntungan waktu, pengurangan biaya, dan peningkatan laba yang signifikan. Saat ini, hampir semua maskapai penerbangan, jika tidak semuanya, mengandalkan riset operasi untuk mengelola operasi mereka.
Masalah penjadwalan pengemudi bus
Masalah penjadwalan pengemudi bus terdiri dari mencakup setiap bagian bus
jadwal oleh pengemudi bus dengan biaya minimum. Ini bisa berupa bus sekolah, bus kota, atau konteks lainnya. Jadwal bus mendefinisikan blok kendaraan, setiap blok kendaraan, atau hanya blok, adalah perjalanan bus yang dimulai dari depot dan kembali ke depot. Di sepanjang blok tersebut, terdapat titik-titik pemberhentian di mana dapat terjadi pergantian pengemudi. Bagian dari sebuah blok yang berada di antara dua titik pemberhentian yang berurutan, dan dengan demikian selalu dilayani oleh satu pengemudi, adalah sebuah tugas. Sebuah tugas terdiri dari beberapa tugas yang berurutan dalam satu blok yang harus dilakukan oleh seorang pengemudi. Peraturan internal perusahaan bus, dan kesepakatan bersama antara serikat pengemudi dan operator angkutan mendefinisikan semua rincian yang relevan dengan tugas (hari kerja) dan kelayakan jadwal. Sebuah tugas terdiri dari satu atau beberapa bagian pekerjaan yang dilaksanakan oleh pengemudi yang sama. Dalam kasus di mana sebuah tugas terdiri dari lebih dari satu bagian pekerjaan, waktu istirahat atau waktu tidak bekerja disisipkan di antara bagian-bagian tersebut. Kelayakan suatu tugas tergantung pada panjangnya bagian pekerjaan dan panjangnya waktu istirahat. Hal ini juga dibatasi oleh batasan-batasan seperti batasan jumlah bagian pekerjaan dalam suatu tugas, total waktu kerja, waktu yang dibayar, atau total penyebaran. Kesepakatan bersama juga dapat mengklasifikasikan tugas menjadi beberapa jenis dan mendefinisikan kendala pada jadwal tenaga kerja global.
Dalam riset operasi, masalah ini biasanya ditangani dengan menggunakan jaringan yang dioptimalkan, yaitu dengan jumlah busur dan simpul sesedikit mungkin, dan dapat diselesaikan dengan lebih efisien dibandingkan dengan penyelesaian secara manual. Dengan menggunakan dekomposisi Dantzig-Wolfe yang dikombinasikan dengan pendekatan solusi pembangkitan kolom, jadwal berkualitas sangat tinggi yang tidak memerlukan penyesuaian manual dapat dihasilkan.
Masalah penugasan lokomotif
Salah satu dari sekian banyak masalah yang dihadapi oleh perusahaan transportasi kereta api adalah mengoptimalkan pemanfaatan stok lokomotif yang tersedia. Rencana penugasan peralatan menentukan komposisi rangkaian kereta yang akan digunakan pada setiap kereta yang dijadwalkan, dan menunjukkan kereta mana yang akan dicakup oleh unit peralatan yang sama. Kereta api biasanya menggunakan lokomotif dari berbagai jenis yang digabungkan untuk membentuk rangkaian kereta. Rangkaian kereta adalah sekelompok unit peralatan yang kompatibel yang melakukan perjalanan di sepanjang beberapa bagian dari jaringan kereta api secara fisik. Tujuan dari LAP adalah untuk menugaskan armada lokomotif ke satu set kereta sambil memenuhi berbagai batasan operasional dan anggaran dan mengoptimalkan satu atau lebih tujuan penting.
Dalam banyak makalah, eksperimen komputasi yang dilakukan menunjukkan bahwa bahkan untuk kasus yang berbeda, dekomposisi Benders, yang dapat dilihat sebagai dual dari dekomposisi Dantzig-Wolfe, lebih cepat daripada menyelesaikan masalah secara manual. Keunggulan metode ini bahkan lebih besar lagi pada kasus yang lebih besar. Khususnya, ketika jumlah jenis lokomotif meningkat, seseorang harus mendapatkan lebih banyak lagi dengan menguraikan masalah. Oleh karena itu, kegunaan riset operasi dibandingkan dengan penyelesaian secara manual.
Masalah penjadwalan shift
Penjadwalan shift muncul di banyak bidang seperti ritel, kesehatan, layanan pos, transportasi, dan produksi industri. Proses penjadwalan personil dapat bervariasi dari satu area ke area lainnya, namun tujuannya secara umum tetap sama. Proses ini terdiri dari penyusunan jadwal kerja sekumpulan karyawan dalam jangka waktu tertentu untuk memenuhi permintaan karyawan yang disebabkan oleh sekumpulan tugas atau pekerjaan. Jadwal yang dihitung harus menghormati berbagai batasan kerja, serikat pekerja dan legislatif, dan harus optimal sehubungan dengan satu atau beberapa kriteria seleksi seperti gaji karyawan, kualitas pekerjaan yang diberikan atau preferensi karyawan. Menemukan jadwal seperti itu adalah latihan yang sangat rumit yang lebih baik dilakukan dengan menggunakan perangkat lunak pengoptimalan. Dalam praktiknya, penjadwalan personalia tunduk pada banyak ketidakpastian. Memang, karyawan mungkin terlambat, tidak hadir atau permintaan yang diamati mungkin juga berbeda dari permintaan yang diharapkan untuk periode tertentu dalam jangka waktu tertentu.
Sama halnya dengan masalah yang disajikan di atas, SSP juga banyak dipelajari dalam literatur dan memiliki banyak aplikasi dalam kehidupan nyata. Baik heuristik maupun metode eksak digunakan untuk menyelesaikannya untuk konteks yang kompleks. Di luar kasus deterministik, SSP juga dapat diselesaikan dengan cepat secara real time, mulai dari solusi optimal atau mendekati optimal deterministik, untuk menangani gangguan yang tidak terduga, yang menunjukkan keuntungan menggunakan riset operasi.
"Optimasi yang sesungguhnya adalah kontribusi revolusioner dari penelitian modern terhadap proses pengambilan keputusan." - George Dantzig
Dengan kutipan George Dantzig, saya menyimpulkan presentasi dari beberapa aplikasi klasik riset operasi. Interaksi antara matematika, ilmu komputer, dan masalah kehidupan nyata memiliki keindahan yang unik dan mempesona yang terasa pedas ketika seluruh prosesnya berhasil diselesaikan dengan baik, yaitu mulai dari perumusan matematis masalah nyata hingga implementasi solusi yang dioptimalkan.
Disadur dari: medium.com