Logistik. pengantar Hampir rumit

Kita semua suka bermimpi, terutama ketika mengunjungi tempat-tempat baru atau kembali ke tempat favorit Anda. Tidak ada yang menginspirasi begitu banyak rasa mengantisipasi acara yang direncanakan dan dibayangi oleh hanya adanya masalah organisasi, khususnya, pemilihan dan pembelian tiket pesawat. Dan untuk beberapa alasan, secara internal, kami selalu menunda masalah ini atau mengalihkannya ke operator tur, mesin metasearch, atau agregator lainnya. Dalam praktiknya masing-masing, ada situasi ketika pesan ditampilkan di layar: “Sayangnya, tidak ada yang ditemukan untuk permintaan Anda. Mungkin ada penerbangan untuk hari lain. "

Seperti yang sering terjadi, itu jauh dari selalu dalam menanggapi permintaan dengan pencarian rute bahwa hasil yang diinginkan dengan penerbangan diberikan, yang segera masuk ke checkout. Kami mulai pindah dari satu situs ke situs lainnya untuk mendapatkan jawaban yang memuaskan.

Terjadinya kasus serupa dikaitkan dengan kurangnya komunikasi langsung atau rute gabungan (menghubungkan) yang direncanakan sebelumnya, atau rute dengan transfer diusulkan yang mencakup waktu tunggu untuk penerbangan berikutnya selama lebih dari 5-6 jam, atau bahkan sepanjang hari.

Bagaimana dengan semua variasi maskapai kami mendapatkan jawaban yang jauh dari selalu memuaskan kami, dan secara umum, bagaimana algoritma untuk menemukan opsi rute dibangun secara algoritmik? Dalam hal ini, matematika terapan datang ke bantuan kami menggunakan algoritma dan kriteria evaluasi.


Peta Bandara Dunia

Saya telah berurusan dengan masalah logistik untuk waktu yang lama dan ketika saya dihadapkan dengan tugas membangun mesin pencari yang akan mencari rute yang optimal, bagi saya agak sepele. Dari pengalaman, saya bisa mengatakan sebelumnya bahwa itu dapat diselesaikan dengan metode yang cukup sederhana dan dalam waktu yang relatif singkat. Namun, jika semuanya begitu sederhana, maka artikel ini tidak akan muncul. Karena itu, setelah bergabung dengan pekerjaan, setelah beberapa saat saya menyadari bahwa itu tidak sepele.

Titik awal, seperti yang sering terjadi ketika bepergian, dan dengan pendekatan inilah saya muncul, adalah keputusan untuk membangun jaringan transportasi dalam bentuk grafik. Jaringan transportasi awalnya termasuk data tentang bandara, maskapai penerbangan, jadwal penerbangan mereka, dan menghubungkan indikator waktu.

Itu diambil sebagai dasar bahwa bandara dianggap sebagai bagian atas grafik, dan penerbangan di antara mereka adalah ujung-ujungnya. Sebagai hasilnya, kami mendapatkan kerangka, seperti kerangka, di mana saya mulai memaksakan jadwal yang memiliki karakteristik sendiri: waktu keberangkatan dan kedatangan. Selain itu, gerakan di sepanjang tepi selalu dimungkinkan hanya pada waktu tertentu, yang ditandai dengan opsi-opsi tertentu untuk memecahkan masalah:

• waktu perjalanan minimum;
• jumlah transplantasi minimum (atau memadai dalam bahasa biasa);
• interval waktu untuk transfer dari satu penerbangan ke penerbangan lain ketika memilih rute yang kompleks.

Kesulitannya terletak pada kenyataan bahwa dalam keadaan apa pun kami tidak hanya menggunakan satu kasus tertentu, kueri selalu berisi kriteria pencarian terkait, termasuk satu atau dua atau lebih penyempitan. Oleh karena itu penerapan kriteria membebankan kondisi tertentu pada perhitungan opsi rute yang diinginkan. Selain tiga yang tercantum di atas, perhitungan mencakup penggunaan kategori kelas layanan (pertama, bisnis, ekonomi), biaya, jumlah penumpang dan kategorinya, serta ketersediaan sejumlah layanan tambahan yang mempengaruhi hasil. Dengan demikian, ini sepenuhnya mulai masuk ke dalam konsep saya untuk memecahkan masalah dengan cara optimasi multi-kriteria (multi-purpose optimization), yaitu, menemukan jalur terpendek dengan beberapa kriteria (MOSP - jalur terpendek multi-tujuan).

Tetapi, seperti semua orang tahu, untuk menguji satu hipotesis, sejumlah lainnya harus dikutip. Sebagai pilihan lain untuk memecahkan masalah, penggunaan pemrograman nonlinear dipertimbangkan.

Mengingat bahwa lengkungan grafik ditimbang oleh vektor, solusi masalah dapat dikurangi menjadi pemrograman kuadratik (nonlinear). Dan semuanya akan sempurna jika bukan karena fakta bahwa vektor, pada kenyataannya, hanya memiliki dua karakteristik: panjang dan proyeksi pada sumbu koordinat, yang berarti kehadiran dalam fungsi objektif variabel dengan derajat tidak lebih dari dua. Namun, dalam kasus saya, komponen vektor “saling bertentangan”, yang bertentangan dengan pemrograman non-linear (kuadratik). Misalnya: "konflik" mungkin disebabkan oleh fakta bahwa setiap penerbangan memiliki kapasitas pesawat tertentu dan tidak mungkin menjual lebih banyak kursi untuk itu. Karena adanya "konflik", opsi untuk menyelesaikan masalah dengan pemrograman nonlinier harus ditinggalkan demi pemrograman multi-kriteria yang sama.

Setelah menganalisis opsi untuk memecahkan masalah, saya pergi dengan versi klasik dekomposisi dengan bagian-bagian berikut:

1. mencari berdasarkan jadwal semua rute "terpendek" dari titik keberangkatan ke titik kedatangan;
2. cari di antara jalur "terpendek" yang paling "optimal" berdasarkan kriteria.

Pada saat yang sama, setelah dekomposisi, pertanyaan dilanjutkan secara logis, tetapi atas dasar pendekatan mana yang lebih baik untuk membangun jaringan rute transportasi? Dan grafik mana yang tersedia yang lebih dapat diterima untuk menyelesaikan masalah ini?

Menurut klasik genre, tidak ada yang ditemukan, tetapi beberapa model, yang mulai saya pertimbangkan.

Model Perpanjangan Waktu

Grafik yang diperpanjang waktu adalah grafik yang diarahkan. Busur dari grafik tersebut adalah arah dari titik keberangkatan dan kedatangan penerbangan, dan puncaknya adalah slot (waktu lepas landas dan mendarat) dari penerbangan. Penggunaan model perpanjangan waktu adalah untuk memperluas grafik asli dengan bandara puncak dan busur, yang mencerminkan hubungan rute dengan menggabungkan bandara di antara mereka sendiri sesuai dengan jadwal penerbangan:



Arcs diindikasikan sebagai$$$e_{BC,3}$. Misalnya, busur menghubungkan bandara$$$B$ dengan bandara $$$$C$$dan diarahkan dari $$$B$untuk $$$C$ditentukan oleh indeks koma $$$3$menunjukkan bahwa ini bukan satu-satunya penerbangan, tetapi yang ketiga berturut-turut. Selain itu, setiap busur dapat dengan mudah ditimbang, misalnya, berat busur$$$e_{BC,3}$ dapat dihitung sebagai $$$w_{BC,3} = t_{C,9}-t_{B,6}$. Verteks di dalam satu bandara mudah diatur sesuai dengan indikator waktu setiap penerbangan, dan juga, berdasarkan waktu penghubung di dalam bandara, penerbangan dihubungkan oleh busur yang sesuai dengan waktu transfer yang tersedia dari satu penerbangan ke penerbangan lain.

Keuntungan dari grafik yang diperluas waktu adalah jalur kedatangan tercepat dapat ditemukan dalam waktu singkat, misalnya, menggunakan algoritma Dijkstra. Kerugian dari menggunakan pendekatan ini adalah peningkatan multipel dalam simpul dan tepian, yang, bagaimanapun, tidak memengaruhi sparseness grafik, karena peningkatan jumlah tepian sebanding dengan peningkatan jumlah simpul.

Model tergantung waktu

Grafik tergantung-waktu adalah grafik terarah tanpa transformasi tambahan pada grafik asli. Setiap busur sesuai dengan rute dengan koneksi antar bandara, sedangkan busur memiliki set data khusus yang mencakup parameter tentang waktu keberangkatan dan kedatangan penerbangan di sepanjang rute. Nilai yang diambil dari dataset ini tergantung pada saat yang tepat dalam waktu mengakses busur ini terjadi, karenanya nama "tergantung waktu".



Keuntungan dari grafik tergantung-waktu adalah grafik memungkinkan Anda menemukan jalur dengan jumlah transfer paling sedikit, kerugiannya adalah beban berlebihan pada data masing-masing busur.

Multigraf

Multigraf adalah grafik terarah dengan set karakteristik yang melekat pada model yang ditingkatkan waktu dan tergantung waktu.



Ada banyak busur di antara bandara dan selama model diperpanjang, tetapi busur ini "tertimbang" pada waktu keberangkatan dan kedatangan, dan waktu penghubung antara penerbangan di setiap bandara harus dihitung secara konstan dan berulang kali. Di sisi lain, dalam representasi multi-grafik terdapat informasi yang persis sama tentang penerbangan dibandingkan dengan model yang tergantung waktu, tetapi semua informasi ini diberikan ke banyak busur. Menemukan jalur dengan jumlah transfer paling sedikit akan sesederhana selama model yang tergantung waktu, tetapi melewati satu busur tidak memperhitungkan informasi busur lainnya, jadi setelah jalur dengan jumlah transfer paling sedikit ditemukan, Anda harus mengulangi jalur ini untuk perhitungan informasi tentang penerbangan lain (busur).

Representasi jaringan rute transportasi dalam bentuk multigraf adalah kondisi mentah untuk model yang diperpanjang waktu dan tergantung waktu. Pencarian jalur dengan kedatangan terpendek akan dilakukan oleh karakteristik transformasi yang sama dari model yang diperluas waktu, dan pencarian jalur dengan jumlah transfer paling sedikit akan dilakukan oleh model yang tergantung waktu. Dan memerlukan peningkatan waktu perhitungan jaringan. Namun, ada nuansa di sini, karena pencarian untuk jalur "terpendek" sesuai dengan dua kriteria, dalam kasus umum, sudah termasuk dalam kelas NP tugas-tugas sulit dan modifikasi algoritma Dijkstra melakukan manipulasi yang cukup kompleks dengan penandaan simpul.

Representasi kompleksitas komputasi masalah dengan multigraf model rangkaian rute dengan bandara dan penerbangan dapat dipertimbangkan melalui metode modifikasi yang paling sederhana - algoritma Dijkstra, yang hanya mencari jalur optimal Pareto. Jumlah total kriteria untuk jalur optimal Pareto tunggal tidak boleh lebih buruk atau lebih baik daripada jalur optimal Pareto lainnya untuk semua kriteria secara bersamaan. Misalnya, serangkaian jalur dengan jumlah dua kriteria berikut {(30, 10), (20, 20), (10, 30)} akan Pareto optimal.

Sebagai contoh yang lebih ilustratif, kami mempertimbangkan operasi algoritma pada grafik kecil yang busurnya ditimbang oleh vektor dua dimensi:



Pengoperasian algoritma Dijkstra yang dimodifikasi pada grafik seperti itu, serta algoritma normal untuk grafik reguler, akan terdiri dari iterasi dengan pemukulan berturut-turut dari simpul, kecuali bahwa setiap simpul mungkin tidak memiliki satu nilai optimal Pareto, tetapi beberapa. Selain itu, perlu juga menyimpan informasi tentang asal usul setiap nilai perhitungan jumlah.

Mengingat bahwa masalah tersebut mempertimbangkan rute dengan koneksi bandara untuk penerbangan, cukup tepat untuk mengasumsikan bahwa ada cukup banyak busur di antara dua simpul, dan masing-masing dapat ditimbang oleh setidaknya tiga komponen vektor. Tetapi dengan peningkatan komponen vektor, peningkatan jalur optimal Pareto juga dapat terjadi. Selain itu, hampir semua busur antara dua simpul bisa Pareto-optimal. Dalam hal ini, jumlah lintasan akan mengandung lebih banyak lintasan Pareto-optimal. Ini dapat dilihat pada multigraf kecil yang ditimbang oleh vektor dua dimensi:



Penggunaan algoritma Dijkstra yang dimodifikasi dalam model seperti itu diperbolehkan, karena dapat bekerja pada multigraf, tetapi kecepatan pemrosesan algoritma tergantung pada jumlah simpul$$$n$, dan pada jumlah busur $$$m$. Untuk grafik sederhana yang jarang dan algoritma biasa, kompleksitasnya sesuai urutan$$$O(n\log n+m\log n)$. Namun, sulit untuk mengatakan apakah multigraf yang dihasilkan akan "jarang", karena dalam kasus umum kepadatan tepi multigraf bisa jauh lebih tinggi daripada grafik penuh. Jika kita memperhitungkan bahwa jumlah tepi grafik lengkap$$$E$ ditentukan oleh jumlah simpulnya $$$V$sesuai dengan rumus:

$$$E={\frac {V(V-1)}{2}}$

Dan kerapatan tepi didefinisikan sebagai:

$$$D={\frac {2E}{V\,(V-1)}}$

Untuk grafik lengkap $$$max(D) = 1$, tetapi untuk multigraf, nilai kerapatan tepi umumnya tidak terbatas.

Oleh karena itu, saya sampai pada kesimpulan bahwa jalur terpendek dapat ditemukan menggunakan algoritma Dijkstra, dan semua jalur terpendek lainnya dapat ditemukan menggunakan algoritma Yen. Mengingat bahwa pada tahap ini kami beroperasi dengan busur tidak tertimbang dan dapat segera membuang jalur, misalnya dengan empat transfer, maka pencarian satu jalur terpendek akan dijamin akan dilakukan dalam waktu kurang dari$$$O(n^{2})$.



Mempertimbangkan bahwa artikel ini tidak mencakup hasil implementasi langsung, saya dapat mengasumsikan sebelumnya bahwa algoritma Dijkstra yang dimodifikasi pada model multigraph tidak akan berhasil dengan mempertimbangkan interval waktu yang optimal.

Oleh karena itu, saya akan beralih ke solusi langsung dari subproblem pertama, yaitu, untuk solusi dari pertanyaan yang berkaitan dengan optimasi multikriteria, yang saya pilih dengan metode optimasi bersyarat. Metode ini terdiri dari fakta bahwa meskipun terdapat kriteria yang tidak konsisten, prioritas tertinggi selalu ada, dan yang lainnya memiliki nilai yang valid. Akibatnya, optimasi seluruh tugas datang ke optimasi pada prioritas tertinggi.

Ciri dari tugas ini adalah kenyataan bahwa perhitungan tidak hanya mencakup penerbangan langsung, yang selalu sangat menyederhanakan tugas, tetapi, sebaliknya, menghubungkan penerbangan atau transfer. Oleh karena itu, model grafik tergantung-waktu sangat cocok untuk menyelesaikan masalah, karena seringkali jumlah transfer tidak membentuk lebih dari 3-4 segmen dalam rute. Grafik tergantung-waktu, pertama-tama, membawa informasi tentang totalitas rute yang tersedia dalam bentuk penerbangan dengan koneksi antar bandara. Kemudian, perkiraan waktu keberangkatan dan kedatangan untuk docking dihitung dengan memperhitungkan grafik tidak tertimbang yang biasa. Yang perlu dilakukan pada tahap ini adalah menemukan semua rute yang valid antara bandara "A" dan "B" dengan jumlah transfer yang telah ditentukan, misalnya, tiga.



Mempertimbangkan bahwa pada tahap ini grafik tidak berbobot, dimungkinkan untuk menemukan jalur terpendek menggunakan pencarian pertama yang biasa, dan semua jalur terpendek lainnya menggunakan algoritma Yen. Karena pencarian pertama kali dilakukan dalam waktu linier, kita dapat mengatakan bahwa waktu pencarian untuk semua jalur, dengan 3 transfer yang sama, akan linier.

Ketika mengevaluasi penggunaan algoritma untuk menemukan rute yang optimal dan ketersediaan data pada frekuensi pembaruan jadwal, kita dapat mengatakan bahwa ide matriks yang dihitung sebelumnya dengan semua jalur "terpendek" dalam arah dibenarkan. Tentu saja, pada tahap awal pembuatan matriks, solusi seperti itu akan berubah menjadi perhitungan yang melelahkan, tetapi kemudian, di masa depan, itu akan memungkinkan Anda untuk hampir secara instan menemukan jalur "terpendek" dan segera membuat penyesuaian pada matriks itu sendiri.

Namun, pertanyaannya tetap, dan rute rute "terpendek" mana dengan koneksi dan transfer yang paling "pendek"? Jika tidak, kami memiliki sejumlah data yang tidak memungkinkan kami mengambil keputusan. Serangkaian kriteria sering dikurangi menjadi yang paling optimal dalam hal ini, yaitu:

• waktu perjalanan minimum;
• jumlah minimum transfer.

Kedua kriteria dapat memiliki interval atau nilai waktu yang dapat disesuaikan, sehingga hanya menggabungkan rute dan "on the fly" memeriksa kepatuhan dengan nilai yang diizinkan:



Mengingat bahwa jumlah maksimum transfer bervariasi antara 3-4, beberapa kombinasi penerbangan akan segera dikecualikan , menuntun kami ke solusi subproblem berikut - untuk mengidentifikasi di antara rute kriteria yang paling "optimal" untuk varietas.

Sistem kriteria adalah masalah utama dalam pembentukan penerbitan rute, karena konsep "optimal" akan tergantung pada preferensi penumpang tertentu, dan ia seringkali hanya setelah menerima jawaban atas permintaan yang dapat mengatur rute yang diterima dengan mengatur serangkaian filter yang berbeda. Dan bahkan jika Anda memberinya rute yang dipesan sesuai dengan jalur "terpendek", hasilnya akan berupa array data yang tidak akan memungkinkan penumpang untuk memutuskan dan akan mengarah pada pencarian opsi yang tak ada habisnya. Oleh karena itu, pembentukan berbagai opsi rute yang memperhitungkan berbagai kombinasi aplikasi filter, baik secara kolektif maupun individual, merupakan parameter yang sangat penting yang memengaruhi seluruh tugas.

Lalu apa yang perlu dipertimbangkan dan bagaimana? Membuat filter peringkat adalah tugas yang sangat memakan waktu, karena satu set filter, jumlah mereka dan tingkat pengaruh satu sama lain dapat secara signifikan mengubah hasil pencarian untuk jalur yang optimal sebagai hasil dari perbaikan algoritma pencarian. Lalu terdiri dari apa itu? Kita semua tahu parameter penerbangan utama - informasi tentang maskapai, tanggal dengan waktu keberangkatan / kedatangan, bandara keberangkatan / kedatangan, offset zona waktu, koneksi dan transfer, tetapi kita sering lupa tentang data seperti yang diperlukan dan waktu yang cukup untuk tiba di bandara atau waktu perjalanan antar bandara untuk membuat koneksi dalam kasus ketika keberangkatan selanjutnya dari titik lain di lokasi. Dan kita tidak boleh lupa tentang kategori penumpang kita,serta kuantitas mereka untuk penawaran berikutnya tidak hanya rute optimal dalam waktu, tetapi juga dalam harga, tergantung pada kebijakan tarif.

Berbagai penawaran harus menanamkan tingkat kepercayaan tertentu pada setiap pelancong, tidak peduli seberapa paradoksal ini terdengar. Keyakinan berdasarkan prinsip-prinsip matematika dan terdiri dalam penyediaan sekumpulan proposal minimum dengan opsi rute yang mempertimbangkan preferensi akun dan mengurangi risiko force majeure. Dan dalam hal ini, force majeure tidak hanya kemungkinan penundaan penerbangan atau perubahan waktu dan bandara keberangkatan / kedatangan, tetapi juga indikator seperti situasi alam, teknologi, dan epidemiologis yang mengharuskan pembatalan seluruh atau sebagian penerbangan.

Kemampuan untuk mengelola data dalam realitas kita memerlukan banyak pertanyaan setiap kali: apakah semuanya diperhitungkan, apa lagi yang bisa ditambahkan. Dan dalam keinginan untuk membangun jaringan rute transportasi ini, muncul paradoks terkait dengan fakta bahwa algoritma harus optimal dan sederhana pada saat bersamaan. Tetapi Anda sering harus mengorbankan sesuatu, dari sini di suatu tempat meminimalkan kriteria awal hingga jumlah minimum yang menurut saya paling dapat diterima.

Jika kita mengikuti jalur pemilihan kriteria, kemudian mengabaikan kriteria sekunder, kita dapat membedakan opsi-opsi yang mempertimbangkan tidak hanya waktu seluruh perjalanan, biaya dan kenyamanan, jumlah transfer dan durasi transfer mereka, tetapi, misalnya, informasi tentang kemacetan bandara dan data komunikasi antar bandara. saat mengganti satu bandara ke bandara lain. Ini dibenarkan oleh fakta bahwa ketika membentuk koneksi, dengan mempertimbangkan keberadaan beberapa bandara di satu kota yang memiliki komunikasi berbeda dengan bandara eksternal, tidak hanya lalu lintas udara, tetapi waktu pergerakan ketika situasi seperti itu muncul akan dihitung dalam perhitungan waktu dan pembentukan rute. Dan mereka memiliki tempat untuk menjadi ...

Sistem pengambilan keputusan dalam memilih rute "optimal" dalam situasi di mana kami memiliki serangkaian kriteria yang memengaruhi preferensi hanyalah batu sandungan, yang tidak saya pikirkan sama sekali pada tahap awal. Bahkan mengarahkan mereka ke sistematisasi tertentu, ada cukup banyak perbedaan dalam aplikasi mereka satu sama lain, jadi kami akan mempertimbangkannya secara terpisah.

Kenyamanan

Arti konsep "kenyamanan" dipahami oleh setiap orang secara berbeda, tetapi level berikut diterima oleh maskapai penerbangan:

• kelas satu;
• Kelas bisnis;
• Kelas ekonomi.

Dalam pendekatan saya, saya mengakui bahwa parameter "kenyamanan" dapat diukur dan mengambil nilai dari 1 hingga 10, dan membentuk kondisi berikut: semakin rendah indikator ini untuk penerbangan tertentu, semakin tidak nyamannya dalam sistem peringkat. Dalam hal ini, masalah segera muncul yang terkait dengan non-aditivitas dari jumlah seperti itu, yaitu jumlah dari indikator kenyamanan kedua penerbangan tidak akan mencerminkan kenyamanan mereka secara keseluruhan. Misalnya, ada dua kombinasi rute:

• rute pertama dengan dua segmen, serangan pertama dengan kenyamanan 10, yang kedua dengan kenyamanan 1;
• rute kedua dengan dua segmen, serangan pertama dengan kenyamanan 6, yang kedua dengan kenyamanan 5.

Akibatnya, jumlah dan nilai rata-rata aritmatika dari parameter "kenyamanan" dari setiap jalur akan sama, tetapi mereka tidak akan mencerminkan keadaan sebenarnya. Namun, mengingat perlunya mempertimbangkan kenyamanan agregat dari dua rute, sangat disarankan dalam situasi ini untuk menggunakan nilai rata-rata mereka bersama dengan standar deviasi, yang akan memungkinkan kita untuk memperkirakan "penyebaran" tingkat kenyamanan. Artinya, pada pertimbangan awal, kami memperhatikan kenyamanan rata-rata, dan kemudian, dengan besarnya standar deviasi, kami mempertimbangkan bagaimana kenyamanan ini sangat berbeda satu sama lain. Dengan demikian, kriteria ini terbagi menjadi dua yang sangat "dekat". Meskipun, di sisi lain, bahkan tanpa pemeriksaan yang teliti, jelas bahwa asumsi tingkat kenyamanan yang "terukur" sangat jauh dari kenyataan,karena kami memiliki level kelas yang terkenal. Dan kedua, juga jelas bahwa kenyamanan seluruh perjalanan dalam beberapa jenis ketergantungan fungsional pada kriteria lain, misalnya, durasi penerbangan, jumlah transfer dengan durasi mereka, peringkat maskapai dan armada udaranya. Apakah masuk akal untuk fokus pada kriteria ini adalah pertanyaan. Setelah semua, pendekatan ini didasarkan pada sistem akuntansi untuk totalitas cara "optimal". Oleh karena itu, di masa depan kita akan menggunakan representasi kenyamanan dalam bentuk dua indikator: rata-rata aritmatik dari indikator kenyamanan penerbangan dan standar deviasi mereka.jumlah transfer dengan durasinya, peringkat maskapai dan armada udaranya. Apakah masuk akal untuk fokus pada kriteria ini adalah pertanyaan. Setelah semua, pendekatan ini didasarkan pada sistem akuntansi untuk totalitas cara "optimal". Oleh karena itu, di masa depan kita akan menggunakan representasi kenyamanan dalam bentuk dua indikator: rata-rata aritmatik dari indikator kenyamanan penerbangan dan standar deviasi mereka.jumlah transfer dengan durasinya, peringkat maskapai dan armada udaranya. Apakah masuk akal untuk fokus pada kriteria ini adalah pertanyaan. Memang, pendekatan ini didasarkan pada sistem akuntansi untuk totalitas cara "optimal". Oleh karena itu, di masa depan kita akan menggunakan representasi kenyamanan dalam bentuk dua indikator: rata-rata aritmatik dari indikator kenyamanan penerbangan dan standar deviasi mereka.

Durasi transfer

Ada dua jenis koordinasi rute:

• transfer (pra-disepakati antar maskapai);
• perkaitan.

Yang menarik dari daftar ini adalah konsep "koneksi", yang merupakan hasil dari kombinasi dua atau lebih maskapai pada rute yang sama dengan periode waktu yang disepakati, berdasarkan waktu koneksi minimum yang diperlukan, tetapi tidak selalu cukup untuk mentransfer dari satu penerbangan ke penerbangan lainnya. Oleh karena itu, untuk menggabungkan penerbangan, dalam rute seperti itu, perlu untuk menghitung waktu yang cukup yang diperlukan untuk menyelesaikan koneksi.

Di sini kita memiliki disonansi, karena seringkali penerbangan seperti itu dapat dikecualikan dari opsi untuk penawaran, tetapi, karena adanya kriteria seperti itu, ada situasi ketika menghubungkan dengan menunggu sementara lebih dari satu hari adalah "optimal" untuk penumpang kami. Oleh karena itu, masuk akal untuk tidak membuang rute dengan waktu transplantasi yang terlalu lama, karena, walaupun jarang, mereka mungkin masih diminati.

Bandara

kemacetan Indikator kemacetan bandara dapat diperkirakan ketika menghitung “optimal” rute dengan penilaian tingkat mengisi mereka pada penjualan tiket penerbangan, dengan mempertimbangkan partisipasi bandara di rute. Jelas, dalam asumsi ini, waktu koneksi minimum akan memiliki beberapa ketergantungan fungsional pada kemacetan bandara.

Jumlah transfer

Jumlah transplantasi per se adalah jumlah yang kontradiktif. Lagi pula, seringkali dengan cara ini Anda dapat mengurangi biaya seluruh rute. Di sisi lain, ada kategori penumpang yang kehadiran bahkan satu perubahan menciptakan sejumlah masalah. Jangan lupa situasi ketika rute transfer adalah yang paling "optimal" karena fakta bahwa tiket kelas bisnis yang mahal tetap berada pada rute yang diinginkan atau, katakanlah, ada tiket dengan tarif tanpa kemungkinan pertukaran / pengembalian uang, yang mensyaratkan kemungkinan penolakan. opsi yang diusulkan.

Tetapi dalam jumlah transfer, sub-kriteria lain ditetapkan - ini adalah probabilitas untuk berpindah dari satu bandara ke bandara lain. Oleh karena itu, pembentukan koneksi sering kali merupakan tugas yang sulit, karena dalam menghitung rute, perlu untuk mengatur waktu untuk berpindah antar bandara, dan ini mensyaratkan perlunya memesan tiket untuk transportasi di dalam kota untuk bergerak dalam sub-paragraf.

Kriteria "waktu perjalanan" dan "biaya" adalah jumlah yang benar-benar aditif, oleh karena itu mereka bergantung pada indikator langsung dengan sistem peringkat. Dan semua akan baik-baik saja jika bukan karena kebutuhan untuk memasukkan total waktu perjalanan dengan perhitungan waktu untuk tiba di bandara atau keberangkatan dari itu ke tujuan, serta ketika menghubungkan akuntansi untuk kebutuhan biaya tambahan untuk bergerak antar bandara. Pada tahap ini, izinkan saya mengabaikan klarifikasi ini.

Struktur hierarki tujuan global

Anggaplah definisi "optimalitas" harus dipahami sebagai yang terbaik selalu dan untuk semua, dan tidak hanya untuk penumpang, tetapi juga untuk maskapai penerbangan, bandara dan, mungkin, penyedia layanan perjalanan lainnya.

Dalam hal ini, membagi satu target yang sangat kompleks menjadi sub-tujuan adalah satu-satunya jalan keluar. Kerusakan seperti itu mungkin terlihat seperti ini:



Cukup jelas bahwa untuk memenuhi semua bidang minat, seseorang harus mencapai lebih sedikit "global", tetapi sampai batas tertentu tujuan yang saling bertentangan. Bagaimana cara mencapai ini? Mungkin ini adalah topik yang bagus untuk artikel lain. Tetapi melihat ke depan, kita dapat mengatakan bahwa membagi tujuan yang kompleks menjadi sub-tujuan yang lebih sederhana juga dikaitkan dengan optimisasi dan teori grafik, yaitu pencarian struktur hierarki yang optimal.

Sistem pengambilan keputusan agak terkait erat dengan metode seperti kriteria Laplace, Wald, Savage, dan Hurwitz, oleh karena itu, dengan memiliki serangkaian rute "terpendek", saya tidak dapat membantu mengetahui mana di antara mereka yang akan "paling optimal" berdasarkan mereka.

Salah satu pendekatan paling universal untuk memecahkan masalah optimisasi multiguna adalah pencarian solusi optimal oleh Pareto dan Slater. Jika kita mengevaluasi berbagai rute "terpendek" sesuai dengan kriteria optimalitas Slater, maka jalur optimal akan dianggap sebagai yang terbaik dengan semua kriteria pada saat yang sama. Suatu jalur dianggap Pareto optimal jika semua jalur lain lebih baik daripada itu di beberapa parameter, tetapi lebih buruk di yang lain, yaitu. seseorang tidak dapat memperbaiki jalan dengan setidaknya satu kriteria tanpa memperburuknya dengan yang lain.

Semua solusi optimalitas Pareto dan Slater dapat dengan mudah ditunjukkan secara grafis untuk masalah minimisasi dengan dua kriteria:



Himpunan titik dengan parameter kriteria optimal Pareto ditunjukkan dengan warna hijau, dan solusi optimal Slater ditunjukkan dengan warna kuning. Set poin Slater-optimal juga berisi set poin Paretto-optimal. Dalam kerangka masalah yang sedang dipertimbangkan, semua titik ini akan menjadi ujung vektor mulai dari asal ruang tujuh dimensi.

Sebagai kesimpulan, saya dapat mengatakan bahwa ini hanya puncak gunung es, yang memungkinkan Anda untuk memberikan gagasan awal tentang apa yang ditemui mesin pencari saat membentuk rute optimal.