Cara Menjadwalkan Penerbangan dengan Python
Tetapkan Pesawat yang Cukup sambil Meminimalkan Biaya menggunakan CVXPY
Motivasi
Bayangkan Anda adalah pemilik sebuah maskapai penerbangan. Maskapai Anda perlu menugaskan pesawatnya yang berbasis di New York untuk mencakup semua penerbangan terjadwal yang akan datang.
Ada 10 penerbangan dan 8 urutan penerbangan. Setiap urutan penerbangan terdiri dari beberapa penerbangan.
Misalnya, urutan penerbangan dapat terdiri dari penerbangan dari New York ke Buffalo, dari Buffalo ke Chicago, dan dari Chicago ke New York.
Setiap urutan penerbangan memiliki biaya tertentu. Kita perlu memilih subset dari urutan penerbangan sehingga setidaknya ada satu pesawat untuk setiap penerbangan.
Ada banyak cara yang mungkin untuk memilih kombinasi urutan penerbangan sehingga ada pesawat yang tersedia untuk setiap penerbangan. Salah satu kombinasi yang mungkin adalah seperti ini:
Kombinasi lain yang mungkin adalah seperti ini:
Dan masih banyak lagi.
Kombinasi urutan mana yang harus dipilih maskapai penerbangan Anda agar kendala terpenuhi dan biaya diminimalkan?
Banyak maskapai besar menghadapi masalah ini. American Airlines memperkirakan bahwa sistem berbasis pemrograman matematika mereka menghemat sekitar $20 juta per tahun.
Pada artikel ini, Anda akan belajar bagaimana menggunakan pemrograman integer dan Python untuk menyelesaikan masalah ini.
Apa itu Pemrograman Integer?
Pemrograman integer melibatkan masalah dengan tujuan dan kendala. Beberapa atau semua variabel dibatasi menjadi bilangan bulat.
CVXPY adalah alat Python yang menyediakan antarmuka ke banyak pemecah pemrograman integer. Untuk menginstal CXVPY, ketik:
pip install cvxpy
Dapatkan Data
Mulailah dengan mengunduh data dari Google Drive:
Dapatkan jadwal, biaya, dan jam dari setiap urutan penerbangan.
Ubah semua bilangan positif menjadi 1:
Parameter Masukan
Tentukan parameter masukan:
Variabel Keputusan
Definisikan variabel keputusan menggunakan cp.Variable:
Paksaan
Harus ada setidaknya satu pesawat per penerbangan. Misalnya, untuk memastikan bahwa setidaknya ada satu pesawat untuk penerbangan dari New York → Buffalo, urutan penerbangan 1, 4, atau 7 harus dipilih.
Untuk memastikan bahwa setidaknya ada satu pesawat untuk penerbangan dari New York → Cincinnati, urutan penerbangan 2 atau 5 harus dipilih.
Jadi untuk penerbangan dari New York → Buffalo, kami memiliki kendala:
Generalisasi kendala ini untuk semua 10 penerbangan, kami memiliki:
Objektif
Kami ingin memilih urutan penerbangan yang meminimalkan total biaya.
Menyelesaikan masalah
Sekarang kita memiliki kendala dan tujuan, mari kita selesaikan masalahnya!
13.0
[1. 1. 1. 0. 0. 0. 0. 0.]
Itu berarti bahwa pesawat harus terbang:
- dari New York → Buffalo → Chicago → New York
- dari New York → Cincinnati → Pittsburgh → New York
- dari New York → Chicago → Cincinnati → New York
Mari tambahkan kendala itu pada masalah kita dan lihat apa yang terjadi.
Batasan Jumlah Jam
Pertama kita perlu mendapatkan array yang mewakili jumlah jam untuk setiap urutan penerbangan:
Gabungkan batasan pertama dengan batasan baru:
Menyelesaikan masalah:
20
Itu karena urutan penerbangan yang berbeda dipilih.
Tetapi mengapa urutan penerbangan kedua dan ketiga tidak dipilih? Jika kita melihat lebih dekat pada array yang mewakili jam, kita dapat melihat bahwa total jam dari 3 penerbangan pertama melebihi 1700.
Namun, total jam penerbangan urutan pertama, kelima, dan keenam lebih kecil dari 1700, yang memenuhi batasan.
Dan inilah representasi visual dari urutan penerbangan baru yang dipilih.
Kesimpulan
Selamat! Anda baru saja belajar bagaimana memilih urutan penerbangan sambil meminimalkan biaya. Saya harap artikel ini akan memotivasi Anda untuk memecahkan masalah serupa menggunakan pemrograman integer dan Python.
Jangan ragu untuk melakukan fork dan bermain dengan kode untuk artikel ini di repo Github ini:
Saya suka menulis tentang konsep ilmu data dasar dan bermain dengan berbagai algoritma dan alat ilmu data. Anda dapat terhubung dengan saya di LinkedIn dan Twitter .
Bintangi repo ini jika Anda ingin melihat kode untuk semua artikel yang saya tulis. Ikuti saya di Medium untuk tetap mendapat informasi dengan artikel ilmu data terbaru saya seperti ini:
Referensi
Chen, D.-S., Batson, RG, & Dang, Y. (2010). Pemrograman bilangan bulat terapan: pemodelan dan solusi . J.Wiley & Sons.
Suggested posts
Cara menjalankan plugin ChatGPT secara gratis menggunakan Langchain
Anda pasti pernah mendengar tentang semua plugin ChatGPT baru yang kuat seperti Browser, Code Interpreter, dll. Namun ada masalah, akses ke plugin terbatas pada daftar tunggu sehingga banyak yang tidak memiliki akses ke sana.
Bagaimana saya mentransfer dari Math ke CS
Proses penerimaan Musim Gugur 2023 akan segera berakhir, dan penangguhan/penolakan sedang terjadi. Selamat jika Anda telah diterima di program impian Anda di UW.
Related posts
Arsip Ancaman Itu: Vol 7 Black Basta
Di dunia yang saling terhubung saat ini, ancaman serangan dunia maya lebih umum dari sebelumnya. Penjahat dunia maya dan aktor negara terus-menerus berusaha mengeksploitasi kerentanan dan mencuri data berharga, yang menimbulkan risiko signifikan bagi organisasi dari semua ukuran.
Apakah Seni Pernah Apolitis?
Kemarin kami menutup pintu pada Kontes Lagu Eurovision tahun ini dengan grand final yang gemerlap dan kacau di mana penyanyi Swedia Loreen membawa pulang trofi, menjadi wanita pertama yang menang dua kali dan membawa mahkota kembali ke Swedia 50 tahun setelah ABBA memenangkan kompetisi dengan "Waterloo". Mereka kemudian menjadi salah satu aksi terbesar dalam kanon musik pop.
Mencari Informasi Tentang Nama Domain
Kutipan dari Alat Perangkat Lunak Kecil dan Tajam oleh Brian P. Hogan
Saat Anda membuat permintaan ke facebook.com, komputer Anda mencari nama domain untuk menerjemahkan nama domain tersebut menjadi alamat IP sehingga komputer Anda dapat membuat koneksi tersebut.