Get best of the week

Cara membuat model transportasi multi-agen

Halo, Habr!

Bayangkan kita memiliki tugas untuk membangun jalan baru. Anda dapat membangun jalan raya dengan dua jalur di setiap arah, tetapi bagaimana jika ini tidak cukup? Atau, sebaliknya, ternyata satu jalur cukup, tetapi untuk pelaksanaan proyek itu perlu membeli banyak bidang tanah? Dalam kedua kasus, keputusan tidak akan efektif. Untuk meminimalkan risiko seperti itu, perencana transportasi beralih ke pemodelan komputer untuk meminta bantuan. Artikel ini adalah penyimpangan singkat ke dunia pemodelan multi-agen.



Menggunakan model, yang merupakan salinan dari sistem transportasi nyata, Anda dapat memperkirakan throughput yang diperlukan pada setiap bagian dari jalan yang diproyeksikan, mencoba berbagai opsi penelusuran, atau, misalnya, memperkirakan periode pengembalian suatu proyek jika sampai pada jalan tol dalam kerangka kemitraan publik-swasta. Tetapi tugas-tugas penting lainnya dapat diselesaikan: bagaimana mengatur rute angkutan umum yang optimal dan menghitung pendapatan potensial dari operator, bagaimana menilai keberadaan kekurangan ruang parkir di area tertentu, dan banyak lainnya.

Yang paling menarik adalah siapa pun dapat membangun model serupa di era perangkat lunak bebas!

Salah satu alat pemodelan multi-agen yang paling umum adalah open source.MATSim (Simulasi Transportasi Multi-Agen) .

MATSim mensimulasikan perilaku agen individu. Agen adalah representasi komputer dari individu di dunia nyata. Setiap agen tersebut memiliki rencana harian, dengan dasar di mana ia bergerak dari satu kegiatan ke kegiatan lainnya (misalnya, pekerjaan rumah di rumah, di rumah di rumah di institut di rumah, di rumah di toko di tempat di rumah di tempat di tempat di rumah, dll.), Menciptakan dengan demikian permintaan akan infrastruktur jalan. Representasi skematis dari rencana harian terlihat seperti ini:

gambar

Untuk membuat rencana realistis bagi agen yang akan mencerminkan perilaku nyata orang pada siang hari, jumlah total penduduk agen, pemukiman kembali mereka, tempat kerja, studi, lokasi toko, pusat perbelanjaan, stasiun kereta api dan tempat kegiatan lainnya dipertimbangkan. Untuk memvalidasi permintaan, model ini juga dikalibrasi berdasarkan survei lapangan: pengakuan dan perhitungan arus kamera pengintai dan drone menggunakan jaringan saraf atau, misalnya, pengukuran manual intensitas di jalan.

gambar

Selama simulasi, agen-agen didistribusikan melalui jaringan, meniru perilaku orang yang realistis: melaksanakan rencana mereka, mobil menempati tempat di jalan dan tempat parkir, pengguna angkutan umum mengambil tempat di bus, dan juga berinteraksi satu sama lain dan, jika banyak agen memilih satu jalan pada suatu waktu, kemacetan lalu lintas dan kemacetan dibuat. Semuanya seperti di dunia nyata!

Setelah simulasi selesai, penilaian dibuat dari pemenuhan rencana harian agen, yang disebut penilaian. Agen memperoleh unit utilitas dalam proses kegiatan dan kehilangan mereka selama pergerakan. Dengan demikian, agen yang terjebak dalam kemacetan lalu lintas kehilangan lebih banyak unit utilitas daripada agen yang bergerak di sepanjang jalan bebas hambatan.

Setelah setiap iterasi, beberapa agen membangun kembali rencana mereka berdasarkan informasi tentang beban jaringan jalan sedemikian rupa untuk meningkatkan kinerja mereka: agen dapat mengubah waktu keberangkatan, mengubah moda transportasi, atau mengubah rute. Agen yang tersisa mematuhi rencana mereka sebelumnya, yang disimpan dalam memori program.

Idealnya, setelah simulasi, keseimbangan Nash harus dicapai - yaitu, situasi di mana tidak ada agen yang dapat memperbaiki posisinya tanpa memperburuk posisi agen lain. Biasanya ini adalah situasi yang berkembang dari waktu ke waktu di jalan-jalan kota, mengingat pemikiran ulang sehari-hari dari pengalaman hari sebelumnya oleh penduduknya. Untuk ini, setidaknya 200 iterasi dilakukan dalam kerangka satu skenario. Seluruh siklus kerja MATSim terlihat seperti ini:

gambar

Dari teori ke praktek!


Untuk menjalankan skenario pertama, kita perlu Intellij IDEA (atau Eclipse) dengan Java 1.8.
Kami membuka IDE, mengkloning repositori MATSim dari github dan skenario pertama kami siap dijalankan! Sangat sederhana. Tapi pertama mari kita lihat file input apa yang kita gunakan. Untuk simulasi paling sederhana, ada tiga di antaranya: jaringan, paket, konfigurasi.

Jaringan


File jaringan adalah jaringan tempat agen bergerak. Terdiri dari node dan node / tautan. Setiap tautan memiliki atribut yang berbeda: jenis, panjang ruas, throughput, kecepatan maksimum, jumlah jalur, lalu lintas satu arah, moda transportasi yang diizinkan, dll.

gambar

Membuat kisi-kisi kota secara manual sulit, tidak praktis dan tidak efisien. Sebagai contoh, jaringan St. Petersburg kami terdiri dari 26 ribu node dan 46 ribu tautan. Tapi ada kabar baik. Grid dapat dikonversi dari OpenStreetMap dan kemudian diedit menggunakan JOSM, yang juga merupakan open-source.

Rencana


File rencana adalah representasi terstruktur dari rencana harian agen. Dalam skenario awal, kami memiliki 100 agen yang pergi dengan mobil (mode = "mobil") di pagi hari (end_time = "05:59") dari rumah (ketik = "h", tautan = "1") untuk bekerja (ketik = ”W”, tautan = ”20”), setelah itu setelah beberapa waktu (dur = ”02:30”) mereka kembali ke rumah.



Konfigurasi


Akhirnya, dalam file konfigurasi, semua pengaturan yang diperlukan diatur untuk menjalankan skrip. MATSim terdiri dari modul yang dapat Anda sesuaikan, tambah, atau hapus sesuai kebutuhan.
Banyak pengaturan dalam file konfigurasi bersifat intuitif, tetapi Anda juga dapat selalu melihat apa yang disebut. Buku MATSim . Sekarang kita akan mempertimbangkan hanya dua modul.
Dalam modul planCalcScore, parameter penilaian ditetapkan: misalnya, untuk kedatangan terlambat, agen menerima denda 18 unit. utilitas per jam (masing-masing, terlambat selama 10 menit sama dengan kehilangan 3 unit utilitas); kinerja beberapa aktivitas (misalnya, kinerja) menghasilkan 6 unit utilitas per jam, dan mengendarai mobil menghabiskan biaya 6 unit utilitas yang sama per jam. Untuk menemukan parameter penilaian realistis, jajak pendapat paling sering digunakan untuk menganalisis "biaya" waktu. "

Dalam modul strategi, parameter perencanaan ulang dikonfigurasikan, misalnya, berapa persen agen (ModuleProbability) akan mencoba rute baru (ReRoute) selama iterasi berikutnya.



Dengan demikian, tujuan simulasi adalah untuk membantu agen mendapatkan dari titik A ke titik B dengan biaya terendah.

Jalankan skrip


Saatnya membuka RunMatsim runner dan jalankan skrip pertama kami!

Hasil simulasi akan berada di folder output di root proyek. File utama untuk visualisasi adalah jaringan dan acara. File peristiwa berisi informasi per detik tentang semua tindakan masing-masing agen, jadi berdasarkan file ini Anda dapat mengembalikan gambaran lengkap tentang pergerakan semua agen. Anda dapat memvisualisasikan hasil menggunakan Via .
Untuk hasil yang lebih representatif, saya akan meningkatkan jumlah agen menjadi 500. Ini adalah bagaimana distribusi 500 agen terlihat setelah iterasi pertama ...



Pada awal iterasi, agen menghitung cara terpendek menggunakan DijkstraAkibatnya, intensitas lalu lintas di satu bagian jaringan melebihi throughputnya, kemacetan terbentuk. Tetapi bagaimana jika Anda memberi mereka kesempatan untuk mencoba rute yang berbeda?



Setelah 200 iterasi (~ 5 menit), agen didistribusikan kembali melalui jaringan, level beban tautan sekarang tidak melebihi 0,5, dan waktu tempuh rata-rata untuk semua agen menurun 14% (5 menit). Hore, kita sudah mengatasi gabus!

Oh, seandainya itu sesederhana itu! Pada kenyataannya, sistem transportasi jauh lebih rumit. Dalam artikel-artikel berikut, saya akan memberi tahu Anda bagaimana saya berpartisipasi dalam pengembangan model St. Petersburg dan kota-kota lain dan bagaimana kami memecahkan masalah praktis pada kasus nyata. Scientia potentia est!



Diposting oleh Andrey Kolomatsky, Analis Transportasi di OTSLab.

More articles:


All Articles