Kota tanpa kemacetan lalu lintas

Bab Dua
( tautan ke bab pertama )

Seni merancang jaringan jalan

Masalah transportasi kota melalui mata seseorang dari Ilmu Komputer

Jika saya direkomendasikan sebuah artikel berjudul “Seni Merancang Jaringan Jalan,” saya akan segera bertanya berapa banyak jaringan jalan yang dibangun dengan partisipasi penulisnya. Harus saya akui, aktivitas profesional saya jauh dari pembangunan jalan dan baru-baru ini dikaitkan dengan desain mikroprosesor, di mana saya, di antaranya, terlibat dalam konsumsi sumber daya dari pengalihan data. Kebetulan meja saya kemudian berdiri tepat di seberang jendela panorama, yang membuka pemandangan indah dari bagian panjang Jalan Raya Volgograd dan bagian dari Cincin Transportasi Ketiga dengan kemacetan lalu lintas yang tak ada habisnya dari pagi hingga sore, dari cakrawala ke cakrawala. Dan kemudian, suatu hari, tiba-tiba saya sadar: "Sialan, karena kerumitan proses pengalihan data yang saya perjuangkan dengan chip seharusnya persis sama dengan kesulitan yang ditemui aliran mobil di dalam jaringan jalan jalanan."
Mungkin, itu hanya pandangan dari luar dan penerapan metode yang tidak tradisional untuk daerah yang diteliti yang memberi saya kesempatan untuk memahami penyebab kemacetan lalu lintas dan membuat rekomendasi tentang cara mengatasi masalah mereka dalam praktik.

Jadi, apa hal baru dari pendekatan ini?

Secara historis, tujuan utama jalan dianggap sebagai peluang yang mereka berikan untuk melakukan perjalanan jarak jauh (antara Roma dan provinsi) dengan cepat. Penilaian seperti itu dibenarkan ketika datang ke jaringan jalan raya antar kota tingkat federal: kota-kota yang mereka hubungkan tampak seperti titik-titik langka kecil di atlas, dan sebagian besar mobil yang bepergian antara kota-kota ini melewati jalan mereka tanpa berbelok ke mana pun.

Namun, hanya perlu membalik beberapa halaman dan membuka peta rinci dari beberapa kota besar, karena gambar berubah segera: alamat saja, di mana perjalanan dapat dimulai atau selesai, sudah sekitar sepuluh ribu, semuanya cukup padat dan relatif ukurannya kecil. Pada saat yang sama, ratusan ribu mobil dapat bergerak di jalan-jalan kota seperti itu sekaligus, apalagi, tujuan masing-masing dari mereka bukan hanya untuk mengisi jalan yang sudah kosong, tetapi untuk memindahkan seseorang atau barang dari titik dengan alamat tertentu " X " ke titik dengan alamat tertentu " Y ". Secara keseluruhan, ini berarti bahwa sistem transportasi perkotaan harus disesuaikan untuk secara efektif menyelesaikan masalah pengalamatan paralel berganda . Dengan demikian, fungsi sistem transportasi perkotaan menjadi lebih mirip dengan jaringan telepon atau komputer daripada jaringan jalan antar kota.

Mempertimbangkan jaringan jalan sebagai sirkuit switching untuk pengembang perangkat keras atau insinyur di bidang teknologi transfer informasi adalah cara yang sepenuhnya alami untuk membicarakan masalah, tetapi di antara orang yang terlibat dalam penelitian tentang masalah transportasi, pandangan ini, sejauh yang saya tahu, baru.

Teori pensaklaran sinyal adalah ilmu teknik yang sempit, dan itu saja, tentu saja, tidak akan cukup untuk merencanakan jalan yang terpisah, persimpangan jalan atau memprediksi perilaku arus lalu lintas di bagian jalan raya yang lurus dan terisolasi. Untungnya, masalah-masalah yang tercantum di atas diteliti dengan baik hari ini, dan metode yang dikembangkan untuk menyelesaikannya telah berhasil digunakan. Teori switching, pada gilirannya, memungkinkan arsitek untuk menyingkirkan risiko ketika semua elemen jaringan jalan dieksekusi dengan sempurna, dan kota itu masih mengalami keruntuhan transportasi. Risiko ini ada karena melakukan pengalamatan serentak multipel bersifat intensif sumber daya.
tugas yang memakan waktu, kunci untuk solusi yang efektif yang tidak begitu banyak lebar jalan dan kenyamanan pertukaran transportasi, tetapi pilihan yang kompeten dari skema switching tertentu yang akan diterapkan oleh jaringan jalan yang diusulkan.

Dari karya ini, misalnya, Anda akan mengetahui mengapa jenis jaringan transportasi “arteri”, yang masih sering digunakan di kota-kota modern, “buruk” dan dengan pertumbuhan penduduk tentu akan menyebabkan kemacetan lalu lintas. Hasil lain yang menarik, yang sesuai dengan pengamatan, menjelaskan mengapa perluasan jalan saja, jika sebelum semua kemacetan terjadi secara eksklusif di sekitar persimpangan, tidak mungkin entah bagaimana memperbaiki situasi bahkan jika jumlah mobil di kota tetap sama.

Ketika saya menulis artikel ini, penting bagi saya bahwa itu dapat dimengerti oleh arsitek paling umum, dapat bermanfaat melalui karyanya. Saya mencoba memperkenalkan pembaca ke peralihan masalah dalam bahasa yang sederhana, untuk mengembangkan kriteria untuk menilai seberapa baik jaringan jalan tertentu akan mengatasi tugas mengatasi paralel, menggunakan contoh-contoh model yang saya tunjukkan bagaimana menggunakan pengetahuan ini dalam praktik.

Artikel ini ditujukan untuk kalangan luas pembaca yang sedikit akrab dengan program matematika di seluruh universitas, teori algoritma dan siap untuk mencurahkan 1 hingga 5 hari untuk itu.

Pemisahan dan penggabungan arus mobil

Jelas bagi banyak pengemudi, pengamatannya adalah bahwa kesulitan lalu lintas timbul terutama di tempat-tempat jalan di mana mobil karena alasan tertentu terpaksa berganti jalur. Contohnya termasuk garpu, penyempitan, area persimpangan dan akses jalan ke jalan raya, bagian jalan bebas hambatan di mana beberapa jalur terhalang oleh kecelakaan atau perbaikan jalan.
Pada bagian ini, upaya akan dilakukan untuk memberikan deskripsi kuantitatif tentang proses yang terjadi dalam kasus tersebut, dan kita akan mulai dengan memahami bagaimana mobil mengubah jalur dari satu jalur ke jalur lain.

Dua strategi untuk membangun kembali dalam barisan yang berdekatan

Pergerakan lalu lintas di sepanjang jalan raya memiliki ketidakrataan alami: seseorang lebih suka mengemudi sedikit lebih cepat, seseorang sedikit lebih lambat, jarak antara satu mobil berkurang dan menjadi sangat tidak nyaman untuk dikendarai, sementara di antara yang lain itu bertambah banyak sehingga memungkinkan mobil untuk masuk dari jalur yang berdekatan. Munculnya celah-celah seperti itu dalam aliran jalur yang berdekatan langsung di sisi pengemudi acak mungkin sering atau tidak terlalu. Jika, pada saat dia perlu melakukan manuver, tidak ada celah, pengemudi dapat menggunakan setidaknya dua strategi perilaku:

Strategi No. 1
Beberapa celah yang cocok mungkin terletak dekat dengan lokasinya. Jika gerakannya cukup padat, maka tidak mungkin pengemudi akan dapat menambah kecepatan dan menangkap celah yang diperlukan, tetapi memperlambat gerakan sedikit dan membiarkan aliran tetangga menyalip dirinya sendiri sehingga menyamakan jarak yang awalnya di belakang - tidak akan ada masalah besar. Biaya dari strategi ini jelas: pengemudi sendiri dan mobil yang mengemudi di belakang di jalurnya kehilangan waktu karena kebutuhan untuk mengurangi kecepatan.

Strategi No. 2
Untuk menunggu, Anda perlu bersabar dan memiliki jumlah waktu yang diperlukan untuk ini. Alternatif mungkin merupakan upaya untuk melakukan manuver yang diperlukan "di sini" dan "sekarang". Menurut ide ini, pengemudi memberi tanda pada mobil-mobil di belakangnya di mana ia akan pindah. Mereka, pada gilirannya, sebagai tanggapan terhadap sinyalnya harus sedikit melambat dan "melepaskan" ke depan, mobil-mobil yang bergerak di depan mereka, dengan demikian memberikan celah ukuran yang diperlukan, akan terbentuk dalam aliran mereka. Biaya waktu dalam kasus ini didistribusikan di antara mobil-mobil di jalur di mana pengemudi akhirnya dibangun kembali.

Dalam kehidupan nyata, kedua strategi terlibat pada saat yang sama: pertama, pengemudi melambat, menunggu celah yang relatif besar dalam aliran jalur tetangga, dan hanya kemudian memberikan sinyal kepada mobil yang bergerak di dalamnya tentang niat mereka untuk melakukan manuver membangun kembali.

Tentu saja, jalan masuk, jalan landai dan penyempitan bukan satu-satunya alasan perubahan jalur ke jalur, yang perlu diingat saat merancang jalan. Kemampuan mobil dengan kecepatan lebih tinggi untuk menyalip lalu lintas yang tidak tergesa-gesa diperlukan agar situasi di jalan raya tidak menurun menjadi satu antrian besar yang merayap dengan kecepatan traktor paling lambat. Namun demikian, masalah koeksistensi kendaraan yang bergerak dengan kecepatan yang berbeda di jalan memiliki sifat yang sedikit berbeda dan dapat dipisahkan dari masalah yang dipertimbangkan dalam artikel ini, karena proses menyalip dan pengaturan ulang yang terkait bukan untuk tindakan paksa pengemudi yang mengharuskannya untuk terburu-buru . Jika ada waktu untuk menunggu, maka menurut teori probabilitas, ini adalah kesempatan yang nyaman untuk melakukan manuver untuk diserahkan kepada pengemudi dengan sendirinya dan untuk ini tidak perlu mengganggu pergerakan pengendara lain.

Biaya satu langkah
Perilaku pengemudi pada kenyataannya bisa sangat sulit, tetapi penting bagi kami pertama-tama bahwa hasil yang diperoleh dalam kondisi model tetap masuk akal: setiap gerakan mobil yang dipaksakan dari satu jalur ke jalur lain mengenakan penalti sementara pada peserta lalu lintas.

Sekarang mari kita mengevaluasi bagaimana jumlah waktu yang hilang tergantung pada kepadatan mobil di jalan.

Kami akan mempertimbangkan pergerakan sepanjang setiap jalur sebagai aliran terpisah. Berusaha untuk tetap berada pada jarak yang nyaman dari mobil yang berada di jalur yang sama, sehingga pengemudi memesan bagian dengan panjang karakteristik tertentu d di sungai. Biarkan ρ mobil jatuh dalam aliran per satuan panjang. Kami setuju untuk menyebut kerapatan fluks kecil , atau, hal yang sama, mengatakan bahwa ρ kecil jika produk ρ × d jauh lebih kecil daripada satu.

Pada saat pengemudi menyadari kebutuhan untuk pindah ke baris berikutnya, probabilitas bahwa bagian kuantitas yang akan ditempati tidak akan bebas, pada ρ kecil akan kira-kira sebanding dengan ρ itu sendiri. Jika peristiwa yang dijelaskan benar-benar terjadi, maka total dua mobil yang bersaing untuk suatu tempat akan mengalami akibat dari manuver beberapa penundaan dalam nilai konstan rata-rata δ .

Dengan asumsi ρ kecil, probabilitas bahwa tindakan mereka pada saat ini akan mempengaruhi pergerakan mobil lain dapat diabaikan. Dengan demikian, dalam urutan kecil pertama sehubungan dengan ρ , kehilangan waktu dari satu gerakan akan menjadi α ⋅ ρ , di mana koefisien α adalah kuantitas yang dapat diukur secara empiris, tergantung pada budaya, cuaca, batas kecepatan (dan sebagainya), tetapi tetap sekitar konstan secara lokal dalam waktu dan untuk kota ini secara keseluruhan.

Intensitas kerugian di situs sebelum keluar
Mobil-mobil yang berangkat ke kongres, sebelum sampai ke tanjakan (Gbr. 2), harus, kadang-kadang bahkan beberapa kali, direkonstruksi di barisan yang berdekatan di sebelah kanan. Setiap manuver seperti itu membuat sulit untuk bergerak, dan sebagai hasilnya, kecepatan rata-rata di bagian sebelum pintu keluar terasa lebih rendah daripada di bagian "transit" (kehilangan pintu keluar, "pintu masuk" dan garpu) dari jalan tol.


gbr. 2

Untuk melewati beberapa bagian jalan dengan kecepatan lebih rendah - memutar untuk pengemudi (dan penumpang mereka) jumlah tambahan waktu yang dihabiskan untuk perjalanan. Dengan kata lain, area jalan raya yang berbatasan langsung dengan tanjakan adalah penghasil kerugian sementara yang konstan.

Misalkan kecepatan rata-rata mesin ν dan kerapatan fluks ρ pada batas depan wilayah ini adalah sama untuk semua pita.

Anggaplah, apalagi, bahwa kepadatan ρ dan laju aliran q yang meninggalkan pintu keluar (jumlah rata-rata mobil yang masuk ke tanjakan per unit waktu) secara simultan kecil, dan s adalah jumlah jalur di jalan raya. Untuk sampai ke pintu keluar, pengemudi akan membuat 1 untuk melakukan manuver pembangunan kembali. Jika kepadatan fluks di jalan jauh lebih rendah dari ρ , maka hanya manuver terakhir yang akan membuatnya praktis "gratis", sedangkan sisanya akan menyebabkan kerugian α ⋅ ρ . Rata-rata, Anda harus melakukan (0 + 1 + 2 + ... + s - 1) / s = ( s - 1) / 2 manuver "mahal".

Mengingat kesulitan yang disebabkan oleh semua mobil berangkat ke kongres, kita dapat menuliskan formula untuk intensitas kerugian sementara:

Saya _keluar = q ⋅ α ρ ⋅ ( s - 1) / 2 = ( α / 2 ν ) ⋅ q ⋅ ( sρν ) ⋅ (1 - 1 / s )

Nilai p = ( sρν ) tidak lebih dari laju aliran semua mobil yang bergerak di sepanjang jalan raya dalam arah yang dimaksud (jumlah rata-rata mobil yang melewati kolom per unit waktu). Komentar terakhir memberi kita kesempatan untuk menulis ulang formula untuk saya dalam bentuk yang lebih simetris:

I _out = ( α / 2 ν ) ⋅ pq ⋅ (1 - 1 / s )

Tingkat kehilangan di bagian sebelah jalan akses
Situasi yang timbul di jalan raya di belakang tempat di mana jalan akses terhubung dengan itu sebagian besar mengulangi situasi di situs di depan kongres, meskipun ada beberapa perbedaan.
Biarkan aliran kecil mobil-mobil listrik q melalui jalan lateral menuangkan lalu lintas utama jalan tol (Gbr. 3).


gbr. 3

Jalannya hanya memiliki panjang yang terbatas, jadi semua mobil yang baru tiba mau tak mau harus dibangun di jalur paling kanan jalan raya. Akibatnya, kepadatan lalu lintas di jalur paling kanan secara lokal lebih tinggi daripada rata-rata di jalan, sehingga beberapa pengemudi di dalamnya memutuskan untuk mengubah jalur ke baris yang berdekatan yang tidak terlalu sibuk di sebelah kiri, yang, pada gilirannya, mengarah ke peningkatan kepadatan lokal di kedua menelanjangi Proses migrasi antar-band ini akan berlanjut sampai kepadatan aliran diratakan melintasi seluruh lebar jalan bebas hambatan. Dengan asumsi kecepatan rata-rata ν sama untuk semua n pita, kita dapat berharap bahwa, setelah menyelesaikan proses migrasi, kekuatan aliran di masing-masing pita akan meningkat tepat (1 / d ) ⋅ q .

Untuk melihat berapa banyak biaya "pengorbanan" untuk pengemudi, pertama-tama kami menghitung kekuatan semua aliran migrasi. Aliran dari tanjakan ke lajur pertama jalan raya yang sudah kita ketahui: sama dengan q . Untuk mendapatkan keseimbangan dalam bentuk peningkatan (1 / d ) ⋅ q , aliran ke jalur kedua dari sisi yang pertama harus sudah (1 - 1 / d ) ⋅ q , dari yang kedua ke yang ketiga - (1 - 2 / d ) ⋅ q , dari sisi k ke ( k + 1) th - (1 - k / s ) ⋅ q . Menurut rumus terakhir, kapasitas aliran migrasi ke jalur paling kiri adalah (1 - ( s - 1) / s ) ⋅ q = (1 / s ) ⋅ q , seperti yang diperintahkan oleh akal sehat.

Karena kita tahu hukuman waktu dari satu rekonstruksi dan kekuatan dari semua aliran migrasi, kita sekarang dapat menghitung intensitas total kerugian yang dihasilkan oleh mereka:

I _dalam = α ρ ⋅ q + α ρ ⋅ (1 - 1 / s ) ⋅ q + α ρ ⋅ (1 - 2 / s ) ⋅ q + ... + α ρ ⋅ (1 / s ) ⋅ q =

α ρ q (1 + 2 + ... + s ) / s =

α ρ q ( s + 1) / 2 =

( α / 2 ν ) ⋅ q ⋅ ( sρν ) ⋅ (1 + 1 / s ).

Mengingat kembali bahwa sρν adalah kekuatan p dari aliran semua mobil di sepanjang jalan raya, kami mendapatkan formula biaya dalam bentuk akhirnya:

I _in = ( α / 2 ν ) ⋅ pq ⋅ (1 + 1 / s ).

Tingkat kehilangan garpu simetris
Dalam paragraf sebelumnya, kami menemukan kerugian dari interaksi arus, salah satunya tentu besar, dan yang lainnya tentu kecil. Untuk menunjukkan pendekatan dalam memecahkan masalah ketika kapasitas kedua aliran sebanding dalam besarnya, mari kita pertimbangkan ekstrim lain: garpu di mana kedua arah "anak perempuan" sama-sama populer untuk pengemudi (Gbr. 4).


gbr. 4

Untuk kenyamanan, mobil yang pergi ke kanan di persimpangan akan disebut "biru", dan mobil yang berangkat ke kiri - "merah". Awalnya, mobil-mobil dari kedua "warna" bergerak campuran, tersebar di antara semua 2 s jalur jalan raya. Ketika mereka mendekati persimpangan, mobil-mobil merah mulai melayang perlahan ke jalur kiri, dan yang biru ke kanan, jalur: migrasi mengalir di kedua arah antara jalur yang berdekatan. Berbeda dengan contoh jalan akses, arus ini tidak lagi “relatif kecil”. Ngomong-ngomong, hanya di antara dua jalur tengah ada pertukaran lalu lintas yang dipaksakan, intensitasnya dalam arah mana saja (dari kiri ke kanan, atau dari kanan ke kiri) sama dengan seperempat dari kekuatan seluruh aliran yang bergerak di sepanjang jalan raya mobil. Untungnya, dalam situasi ini ada cara yang cukup baik untuk memperkirakan biaya yang dihasilkan. Pertama, kami mencatat bahwa proses membagi mobil menjadi "merah" dan "biru" kemungkinan besar dimulai jauh sebelum percabangan dan berjalan lambat, oleh karena itu, di satu sisi, seharusnya memiliki sedikit efek pada kepadatan lalu lintas di dalam baris yang terpisah, dan di sisi lain, membuat migrasi mengalir membentang jarak jauh, sehingga memberikan kesempatan untuk mewakili masing-masing sebagai kombinasi dari sejumlah besar aliran daya rendah (Gbr. 5).


gbr. 5

Karena sekarang kita berbicara tentang aliran kecil, meskipun dalam jumlah yang lebih besar, tidak ada yang mencegah kita mengurangi masalah yang sedang dipertimbangkan untuk yang sudah diselesaikan. Secara mental membagi jalan raya di tengah menjadi dua bagian yang sama, dan kemudian menghubungkannya bersama-sama dengan sejumlah besar jalan jumper jalur tunggal, yang memungkinkan mobil merah untuk sampai ke sisi kiri, dan mobil biru ke kanan (Gbr. 6). Karena simetri yang jelas, ketika menghitung kerugian yang dihasilkan, kita dapat fokus pada mesin dari satu warna, misalnya, biru, dan pada akhirnya hanya menggandakan hasilnya.


gbr. 6

Jadi, biarkan kecepatan ν dan kepadatan ρ sama untuk semua jalur dan tetap konstan di seluruh area di mana mobil dipisahkan oleh warna.Dalam hal ini, laju aliran semua mobil yang bergerak di sepanjang jalan raya adalah:

p = 2 sρv .

Ditunjuk sebagai q ₁ , q ₂ , ... q _m , mengalir mobil biru bergerak pada jumper imajiner di sisi kanan jalan tol. Misalkan sesaat sebelum tempat pemisahan di setiap lajur jalan tol, kedua warna diwakili dengan proporsi yang sama 50%, yang menyiratkan bahwa dalam total
q ₁ + q ₂ + ... + q _m adalah sρv / 2, yaitu p / 4.

Kerugian yang dihasilkan oleh aliran q_i , karena kecilnya, kita bisa menghitung dengan rumus:

I _i =I _out +I _in = (α/ 2ν)⋅(p/ 2)⋅ q _i (1 - 1 /s) + (α/ 2ν)⋅(p/ 2)⋅ q _i (1 + 1 /s) = (α/ 2ν)p q _i

Menyimpulkan ekspresi terakhir dari semuai, Cari kerugian yang dihasilkan mobil hanya biru:

Saya _biru = ( α / 2 ν ) ⋅ p ⋅ ( q ₁ + q ₂ + ... + q _m ) = ( α / 2 ν ) p ² /4.

kerugian lengkap, sebagaimana telah disebutkan, akan dua kali lipat dan jumlah dua kali:

Saya _div = ( α / 2 ν ) p ² /2.

Analisis formula yang diperoleh
Jika kita memisahkan intensitas Iyaitu, jumlah waktu total peserta yang hilang per detik oleh jumlah aliran samping q , yang menurut definisi sama dengan jumlah mobil yang menghubungkan atau meninggalkan lalu lintas di jalan tol dalam satu detik, kami mendapatkan kerugian rata-rata yang dihasilkan oleh satu mobil tersebut:

i _in = I _dalam / q = ( α / 2 ν ) ⋅ p ⋅ (1 + 1 / s )

saya _keluar = I _out / q = ( α / 2 ν ) ⋅ p ⋅ (1 - 1 /s )

Mungkin yang paling penting dalam formula ini adalah proporsionalitas langsung antara aliran daya mobil di jalan raya p dan biaya unit i . Semuanya tampak seolah-olah mobil yang ingin bergabung, atau sebaliknya - untuk meninggalkan aliran gerakan utama, sehingga menyebabkan kerusakan konstan pada setiap pengemudi di dekatnya.

Pengamatan kedua, menarik dan sangat tak terduga menyangkut efek yang sangat lemah pada intensitas kerugian yang dihasilkan dari jumlah lajur dekat jalan raya tepat di sebelah persimpangan. Seperti yang Anda lihat, melihat rumus untuk saya _keluar , kongres umumnya yang termurah untuk jalan satu jalur ( s = 1, i _out = 0), dan kesulitan yang disebabkan oleh jalan akses yang berdampingan untuk jalan raya tiga jalur dan enam jalur berbeda hanya dengan

100% ⋅ [(1 + 1/3) - (1 + 1/6) - (1 + 1/6)] / (1 + 1/3) = 12,5%.

Jika kita memperhitungkan bahwa setiap mobil yang pernah bergabung dengan lalu lintas di jalan bebas hambatan pada akhirnya harus meninggalkannya, maka tampaknya cukup legal untukmenggunakan nilai unified i _av = ( i _in + i _in bukannya i _in dan i _out ) / 2 = ( α / 2 ν ) ⋅ hlm .



Meskipun kurangnya dalam rumus untuk i _av ketergantungan eksplisit pada jumlah band, kita harus ingat bahwa output (lihat saran untuk saya dari _dalam dan I _keluar ) pada dasarnya didasarkan pada asumsi kepadatan mesin kecil di jalan, sehingga tidak mungkin untuk memberikan hasil yang memuaskan, makhluk diterapkan pada jalan raya yang terlalu sempit dengan lalu lintas terlalu banyak.

Temuan awal
Di daerah dekat persimpangan, lalu lintas pasti terjadi, mengambil waktu jauh dari pengemudi, mengurangi kecepatan rata-rata, yang terakhir mengarah pada peningkatan kepadatan mobil dan, sebagai konsekuensinya, kemungkinan kemacetan yang mungkin terjadi. Biaya waktu yang terkait dengan pemisahan dan penggabungan aliran mobil akan disebut switching.

Kerugian dari jenis yang sama ada satu atau lain cara dalam skema switching apa pun: baik itu jaringan telepon atau komputer, mikroprosesor multi-core, atau layanan pengiriman surat.

Ketika seorang pengemudi bergabung, atau, sebaliknya, meninggalkan lalu lintas di jalan raya, biaya pergantian yang dikeluarkan oleh tindakannya sebanding dengan kekuatan arus mobil yang diamati pada waktu itu di jalan raya.

Untuk mengurangi kerugian switching di seluruh kota, perlu untuk mempertimbangkan dengan hati-hati jaringan jalan yang diterapkan di dalamnya pada tahap desain. Beberapa saat kemudian kami akan menganalisis tugas ini secara terperinci, tetapi beberapa rekomendasi yang jelas dapat dicantumkan sekarang:

1. kerugian switching sebanding dengan kapasitas aliran di jalan raya - tidak perlu memperbesar jalan tanpa perlu, dua jalan raya kecil dua kali lebih baik dari yang besar;
2. beralih kerugian sebanding dengan kekuatan aliran samping - perlu merancang jaringan sehingga pengemudi harus menyingkir sesering mungkin selama perjalanannya;
3. campur tangan timbal balik yang disebabkan oleh driver arus utama dan samping harus menjadi lebih kecil pada skala kota jika Anda mencoba untuk mencegah rute yang tumpang tindih hanya di bagian pendek trek dalam satu aliran.

Prasyarat ekonomi untuk keberadaan kota.
Model Akses Kota Seragam

Mungkin hal pertama yang memulai proyek perencanaan (atau perencanaan ulang) sistem transportasi kota adalah mencoba menentukan jenis migrasi yang benar-benar dibutuhkan kota sekarang dan bagaimana kebutuhannya akan berubah di masa depan.

Analisis semacam itu dapat dilakukan jika Anda pertama kali membagi kota menjadi tidak terlalu besar, tetapi tidak terlalu kecil pada wilayah teritorial, dan kemudian untuk masing-masing pasangan zona tersebut menunjukkan berapa perkiraan jumlah perjalanan ke satu sisi atau yang lain yang dibutuhkan oleh penduduk mereka pada satu atau lain waktu hari ini. Dengan menempatkan prediksi yang dibuat dalam tabel persegi, Anda akan menerima matriks dari kebutuhan migrasi penduduk kota.

Untuk matriks ini maka bermanfaat untuk mencari jaringan yang memungkinkan pengemudi dan penumpang menghabiskan waktu sesedikit mungkin pada perjalanan yang terpisah dan membutuhkan sumber daya kota sesedikit mungkin untuk konstruksi mereka.

Ketika datang ke kota-kota yang ada, penting di sini untuk tidak membuat kesalahan dan tidak mengganti jumlah perjalanan yang benar-benar dibutuhkan orang dengan jumlah perjalanan yang secara historis didirikan di bawah pengaruh beberapa kendala atau kesulitan pada saat pekerjaan desain. Mungkin, jaringan transportasi Berlin "sebelum" dan "setelah" jatuhnya tembok pemisah dapat berfungsi sebagai ilustrasi yang paling mencolok dari apa yang telah dikatakan.

Bagian ini terutama akan membahas masalah-masalah kemanusiaan di mana saya bukan seorang spesialis, tetapi saya pikir membahasnya sebagai seorang amatir tetap lebih benar daripada sekadar menghindari masalah.

Untuk lebih mewakili kebutuhan migrasi penduduk, ada baiknya dimulai dengan pertanyaan mendasar: "Mengapa kota benar-benar membutuhkan dan fungsi berguna apa yang mereka lakukan?" .

Mari kita coba menjawabnya bukan sebagai penghuni kota (dan desa) biasa, tetapi dari sudut pandang orang yang bertanggung jawab atas proses urbanisasi di beberapa negara besar dan maju. Dari sudut pandang ini, tidak penting lagi apa motif historis yang pernah membuat begitu banyak orang memadati sebidang kecil tanah, atau alasan mengapa mereka terus melakukannya sekarang, itu penting - apa dampak ekonomi yang menciptakan kota-kota dengan ukuran satu atau lainnya dan untuk karena mekanisme apa efek ini tercapai.

Menurut pendapat saya, alasan utama keberadaan kota-kota besar adalah, di satu sisi, peluang bagi perusahaan teknologi untuk menemukan karyawan yang memiliki profesi langka, dan di sisi lain, kesempatan bagi orang yang telah menguasai profesi langka untuk menjual layanan mereka kepada perusahaan yang tertarik pada mereka dengan persyaratan kompetitif. Di kota kecil (tidak terspesialisasi), produksi banyak barang dan jasa sama sekali tidak mungkin, atau menempatkan perusahaan teknologi dan karyawannya mengimplementasikannya dalam posisi saling sandera, tanpa memberikan salah satu atau yang lain alternatif.

Misalnya, ambil profesi guru sekolah sastra yang tidak terlalu langka. Menurut statistik, kebutuhan mereka adalah: sekitar 1 guru per 1000 penduduk. Di sekolah biasa, 3-4 orang mengajar sastra. Pilihan pekerjaan untuk guru sastra bisa disebut kompetitif jika ada setidaknya 4-5 sekolah menengah di kotanya, yang, dalam hal populasi, adalah sekitar 15 ribu orang.

Rupanya, orang-orang dengan spesialisasi teknik merasa nyaman di pasar tenaga kerja di kota-kota dengan populasi setidaknya 100 ribu. Tentu saja, ada juga profesi seperti itu, permintaan yang muncul hanya di kota-kota dengan sejuta orang, tetapi rasa ekonomi multi-juta kota tetap menjadi misteri bagi saya.

Setelah semua hal di atas, dua hipotesis terlihat cukup termotivasi (validitasnya, bagaimanapun, tidak mempengaruhi kebenaran konten utama artikel):

1. perjalanan paling sering orang dewasa rata-rata memiliki kebutuhan untuk melakukan perjalanan jarak jauh yang menangkap 4-5 dari pekerjaan yang paling menjanjikan baginya;
2. untuk sebagian besar populasi yang memiliki profesi langka dan paling bernilai secara ekonomi, jarak perjalanan yang paling sering mungkin sebanding dengan radius kota.

Sebagai cerminan yang disempurnakan dari hipotesis 1) dan 2), dalam contoh saya, saya akan sering menggunakan model kota dengan "akses seragam", yang mengasumsikan bahwa kekuatan arus perjalanan populer adalah sama antara dua perempatnya, atau, dengan kata lain, dalam semua sel matriks kebutuhan migrasi bernilai angka positif yang sama. Jika Anda secara acak melihat catatan perjalanan yang dilakukan di kota seperti itu pada siang hari, maka untuk perjalanan yang ditandai berikutnya, semua kuartal akan memiliki peluang yang sama untuk menjadi awal perjalanan ini dan melayani sebagai akhir, dan tidak ada hubungan antara posisi "awal" dan "final" »Perempat tidak harus diperhatikan.

Jaringan Topologi Jaringan Sederhana

Mari kita coba menerapkan ide-ide yang dijelaskan dalam paragraf sebelumnya ke beberapa jenis rencana kota yang diambil dari kehidupan.

Kota linear
Permukiman besar pertama berasal sebagian besar di sepanjang pantai, di daerah-daerah jalur tipis tanah antara laut dan tebing, atau di sepanjang jalur jalan yang sibuk, sehingga dalam proses pertumbuhan mereka memperoleh perbatasan memanjang sempit. Banyak dari permukiman ini yang bertahan hingga hari ini, mempertahankan bentuknya yang memanjang dan berubah menjadi kota modern (ilustrasi di bawah).


(daerah terpencil di Rio de Janeiro, penulis tidak diketahui)

Seringkali di kota seperti itu hanya ada satu jalan lebar di sekitarnya yang dibangun. Misalkan setiap kuartal (zona pembagian wilayah) menghasilkan aliran perjalanan dengan kapasitas tunggal, dari semua tempat seperti itu - n , dan kota itu sendiri mematuhi model migrasi "akses seragam".


gbr. 7

Mari kita coba cari kondisi yang tercantum di atas bagaimana waktu tempuh rata-rata dan luas jalan yang diperlukan berubah seiring bertambahnya n .

Jadi, biarkan semua tempat memiliki bentuk dan ukuran yang sama, dan jumlahnya bertambah sebanyak λ (lambda) kali. Jelas,

• panjang jalan utama bertambah dengan faktor λ .

Berdasarkan model yang diadopsi dari "akses seragam", 50% dari perjalanan yang dimulai di bagian kanan kota berakhir di bagian kirinya (tepat sebaliknya), oleh karena itu, dengan peningkatan jumlah perempat dengan faktor λ, kekuatan aliran yang melewati tengah kota juga akan meningkat dengan λ kali Alasan yang sama dengan kesimpulan yang sama akan benar jika, alih-alih dari tengah, kami mengambil titik apa pun untuk membagi kota dalam rasio yang diberikan (1: 3, 2: 5), yang menyiratkan bahwa

• aliran daya mobil di sepanjang jalan utama meningkat dengan faktor λ .
• jumlah lajur jalan utama yang dibutuhkan di setiap bagian meningkat dengan faktor λ .

Kurang lebih jelas bahwa rata-rata lamanya perjalanan, dan dengan itu

• waktu tempuh bersih yang dihabiskan untuk menutupi jarak meningkat dengan faktor λ .

Yang tersisa bagi kami adalah menghitung berapa kali waktu yang hilang karena biaya pergantian dalam satu perjalanan akan meningkat. Di setiap kuartal, aliran samping unit daya masuk dan keluar, yang bersama-sama menghasilkan kehilangan intensitas sementara:

I = I _dalam + I _out = ( α / 2 ν ) p ⋅ 2,

di mana p adalah laju aliran di jalan utama. Kita sudah tahu bahwa jumlah kuartal dan laju aliran di jalan utama tumbuh sebagai λ , oleh karena itu, total kerugian waktu yang dihasilkan oleh jaringan meningkat dengan faktor ² . Di sisi lain, jumlah perjalanan yang dihasilkan oleh jaringan, di mana sebagai akibatnya semua kerugian ini didistribusikan, meningkat dengan faktor λ , dari mana kita dapatkan bahwa

• waktu tempuh bersih hilang karena biaya pergantian meningkat dengan faktor λ .

Mari kita kumpulkan semua hasil dalam satu piring:

Topologi linier
Jumlah titik alamat (kuartal) kapasitas unit ................................. n
Total luas jalan ............................................... ........................................ O ( n ² )
Waktu perjalanan murni
dihabiskan untuk menutupi jarak .............................................. ..... O ( n )
Waktu perjalanan murni
hilang karena biaya switching ............................................ ......... O ( n )
Jumlah switching node ............................................... .................................... O ( n )
Jumlah switching node, dengan mempertimbangkan kekuatan sisi mengalir ..................... O ( n )

Notasi yang digunakan: " y = O ( x )", berarti bahwa jumlah x dan y secara fungsional tergantung, dan ketika x tumbuh tanpa batas, rasio x / y cenderung ke angka bukan nol hingga.

Kota sel
Metode perencanaan kedua yang cukup umum adalah mengatur balok-balok dalam bentuk matriks segi empat, mirip dengan bagaimana potongan-potongan yang dipisah-pindahkan ditempatkan dalam batang cokelat.

Kami setuju untuk menyebut kota-kota tersebut "Seluler".


(Los Angeles, foto: Stepanov Glory)

Gambar 8 menunjukkan diagram Kota Seluler, yang terdiri dari n (dengan mempertimbangkan "bagian") dari perempat, membentuk sebuah bujur sangkar biasa. Perempat dipisahkan dari satu sama lain dengan total jalan, berjalan kondisional dari barat ke timur, dan jalan lain, membentang dari selatan ke utara. Secara total, jalan-jalan ini membentuk persimpangan √ n × √ n , yang masing-masing dapat dibuat sebagai persimpangan lampu lalu lintas, atau diimplementasikan melalui jembatan jalan dan jalan layang.


gbr. 8

Terlepas dari apakah lalu lintas di jalan satu arah atau dua arah, setiap perjalanan dari titik "A" ke titik "B" di kota kotak-kotak dapat dilakukan di sepanjang rute yang berjalan di tidak lebih dari dua jalan dan tidak memerlukan lebih dari satu putaran di persimpangan. sayang.

Anggaplah, seperti dalam contoh sebelumnya, setiap triwulan menghasilkan aliran perjalanan kapasitas unit, dan kebutuhan migrasi penduduk dijelaskan oleh model "akses seragam". Mari kita hitung, sekarang untuk Kota Seluler, undang-undang yang dengannya waktu tempuh rata-rata dan konsumsi sumber daya membangun jaringan jalan dengan peningkatan jumlah perempat perubahan.

Jika jumlah kuartal meningkat dengan faktor λ , maka:

• area kota meningkat dalam λ kali, dan dimensi liniernya dengan tetap mempertahankan proporsi -
  di √ λ ,
• panjang perjalanan rata-rata dan waktu bersih untuk menutupi jarak, sebanding dengan dimensi linier, meningkat √ λ kali,
• jumlah jalan dan jumlah lingkungan yang berdekatan dengan satu jalan meningkat √ λ kali,
• kekuatan arus lalu lintas, yang proporsional dengan jumlah perempat dengan mana aliran "dalam kontak" (penjelasan tentang fakta ini akan diberikan nanti), meningkat sebesar √ λ kali,
• area yang diperlukan dari semua jalan tumbuh sebagai (jumlah jalan) × (panjang satu jalan) × (kekuatan aliran jalan) = √ λ ⋅ √ λ λ √ √ λ = λ √ λ

Aliran lateral dibagi menjadi aliran yang bergerak dari atau menuju perempat dan arus lalu lintas yang berubah dari satu jalan ke jalan lainnya di persimpangan mereka. Yang pertama, sesuai dengan kondisinya, selalu tetap sama dengan persatuan, setelah yang kedua, jika kita memperhitungkan bahwa ada lebih banyak tempat di kota daripada tempat di satu jalan, hampir semua lalu lintas yang bergerak di sepanjang itu datang atau meninggalkan jalan raya. Akibatnya, perubahan besarnya arus lateral yang kedua dapat diperkirakan dengan rumus (perubahan kekuatan aliran jalan) / (peningkatan jumlah persimpangan pada satu jalan) = √ λ / √ λ = 1. Kesetaraan rasio terakhir ke konstan menunjukkan bahwa aliran ini tidak terutama berubah dengan peningkatan jumlah kuartal, oleh karena itu, peningkatan biaya switching yang dihasilkan oleh jaringan secara keseluruhan adalah: (peningkatan jumlah total kuartal + persimpangan) × (perubahan nilai aliran pada satu jalan) = λ √ λ . Karena kekuatan aliran perjalanan yang dihasilkan oleh semua penjuru meningkat dalam λ , maka

• waktu tempuh bersih hilang karena biaya pergantian meningkat sebesar √ λ

Bayangkan hasilnya dalam bentuk tablet:

"Topologi Sel"
Jumlah titik alamat (kuartal) kapasitas unit ................................. n
Total luas jalan ............................................... .................................... O ( n √ n )
Waktu perjalanan murni
dihabiskan untuk menutupi jarak .............................................. ... O (√ n )
Waktu perjalanan murni
hilang karena biaya switching ............................................ ....... O (√ n )
Jumlah switching node ............................................... .................................... O ( n )
Jumlah switching node, dengan mempertimbangkan kekuatan sisi mengalir ..................... O ( n )

Membandingkan Linear dan Jaringan Seluler satu sama lain, sulit untuk tidak memperhatikan bahwa peningkatan sumber daya yang dibutuhkan untuk konstruksi dan waktu yang dihabiskan dalam satu perjalanan dengan pertumbuhan kota untuk jaringan pertama jauh lebih cepat daripada yang kedua. Misalnya, kota Seluler dari 100 perempat membutuhkan 10 kali lebih sedikit aspal, dan perjalanan melewatinya membutuhkan rata-rata 10 kali lebih sedikit waktu daripada yang diperlukan di kota Linear dengan ukuran yang sama. Jadi, masuk akal untuk menggunakan jaringan jalan dengan topologi linear hanya di kota-kota yang sangat kecil.

Jika untuk sementara Anda lupa tentang adanya biaya switching, maka topologi seluler dapat dianggap sebagai cara yang ideal untuk merancang jaringan jalan, karena memberikan perkiraan-O yang optimal secara asimptotik untuk panjang perjalanan rata-rata dan area jalan yang diperlukan. Memang, untuk lokasi kota yang lebih “kurang kompak” (dengan akses seragam), lamanya perjalanan tidak akan lebih lambat dari akar kuadrat wilayahnya, yang biasanya berbanding lurus dengan populasi. Hasilnya, kita mendapatkan semua O yang sama (√ n ).

Fakta bahwa rute tipikal di Kota Seluler berjalan di sepanjang "sudut" daripada garis lurus, pada prinsipnya, memberikan hak untuk mencari cara yang lebih baik untuk merencanakan kota, tetapi penghematan 20% (itulah seberapa banyak Anda bisa menang dalam batas jika mobil belajar naik melalui tembok) tidak mungkin suatu hari nanti mereka akan memaksa arsitek untuk meninggalkan pengaturan jalan dan jalan persegi panjang.

Batas yang lebih rendah dari biaya membangun (dan memelihara) jaringan dapat diperoleh dengan mengingat bahwa setiap mobil cadangan bagian dari lajur untuk pergerakannya, sebagai akibatnya, total luas jalan sebanding dengan produk dari waktu perjalanan rata-rata (panjang perjalanan rata-rata) dengan jumlah mobil di kota : O (√ n ) × O ( n ) = O ( n √ n ) (bandingkan dengan tabel untuk Kota Sel).

Jika kita berbicara tentang jumlah waktu yang hilang dalam perjalanan karena biaya pergantian, maka secara mengejutkan hubungannya dengan jumlah waktu yang diperlukan untuk menempuh jarak tidak secara asimtotik tergantung pada jumlah tempat individu di kota Cellular atau Linear (O (√ n ) / O (√ n ) = O (1), O ( n ) / O ( n ) = O (1)). Dengan kata lain, persentase waktu yang hilang dalam perjalanan karena pergantian acara di kota besar dan kecil akan sama. Dari sini kita dapat menyimpulkan bahwa jika tidak ada masalah serius dengan pengalihan biaya di kota kecil (katakanlah, mereka berjumlah 10-20%), maka di kota besar mereka tidak boleh diamati, dan jika memang ada, maka dengan sendirinya mereka mereka tidak akan pergi ke mana pun, tidak peduli bagaimana kota itu tumbuh dan membesar.

Karena kita tidak tahu alternatif mana yang benar (atau lebih tepatnya, kita tahu bahwa masalah dengan lalu lintas mobil di kota-kota besar memang ada), ada baiknya mencoba meningkatkan topologi Kota Seluler sehingga biaya pergantian di dalamnya berkurang setidaknya dengan waktu yang konstan.

Contoh berguna dari jaringan yang tidak realistis

Mari kita lihat apakah Cellology Topology mengikuti rekomendasi yang kami kembangkan dengan menganalisis pergantian arus di jalan raya.

1) Jangan memperbesar jalan tanpa perlu.
- Ya. Lalu lintas lalu lintas didistribusikan di banyak jalan (bandingkan dengan Kota Linear).

2) Hindari menciptakan kondisi saat Anda perlu melakukan banyak belokan dalam satu perjalanan.
- Ya. Setiap perjalanan kemungkinan besar akan dilakukan di sepanjang rute yang hanya membutuhkan satu belokan di jalan-jalan kota.

3) Hindari situasi saat bepergian di satu bagian jalan, rute yang hanya memiliki sebagian kecil dari jalur umum.
- Di sini, mungkin, ada sesuatu untuk dikerjakan. Terlepas dari jumlah minimum belokan per perjalanan, rutenya sebagai bagian dari aliran jalan raya utama melewati sejumlah besar switching node (O ( n )), di mana setiap waktu yang berharga terbuang sia-sia.

Komentar terakhir memotivasi untuk menyelidiki pertanyaan berikut: "Berapa nilai minimum dari jumlah rata-rata node switching yang harus dilalui oleh perjalanan dalam jaringan jalan yang menghubungkan n blok?"

Tugas mencari jaringan semacam itu masuk akal, tentu saja, hanya dengan syarat bahwa jumlah aliran yang digabungkan atau dibagikan oleh sembarang switching node pada awalnya dibatasi dari atas oleh nilai tetap tertentu. Jika tidak, Anda selalu dapat menghadirkan jaringan jalan dengan n titik alamat dan satu persimpangan-mega.


(penulis tidak diketahui)

Jauh lebih mudah untuk menyelidiki masalah sebenarnya jika sebelumnya mungkin untuk mengungkapkan setidaknya sebagian dari pola menggunakan beberapa contoh model yang sederhana, bahkan jika tidak realistis sama sekali. Mengikuti logika ini, untuk sementara kita akan melupakan keterbatasan geometris membangun jalan bagi para pelancong untuk menempuh jarak, memusatkan semua perhatian mereka pada bagaimana jaringan abstrak memecahkan masalah penanganan paralel. Mengenai switching node, kami akan mengasumsikan untuk saat ini bahwa masing-masing dari mereka membagi aliran menjadi dua bagian (node ​​pembagian), atau menggabungkan dua aliran menjadi satu.


gbr. 9

Pohon alamat
Asumsikan bahwa kita memiliki mulai alamat titik di mana semuanya dimulai, tanpa kecuali, perjalanan, dan bahkan n menyelesaikan alamat poin di mana mereka berakhir (Gambar 9) dengan probabilitas yang sama.

Diperlukan untuk membangun jaringan transportasi yang memungkinkan perjalanan melalui sesedikit mungkin switching node.

Solusi yang jelas (untuk programmer), yang memohon sendiri di sini, adalah dengan menggunakan pohon biner seimbang, pada saat yang sama Anda perlu menempatkan titik awal tunggal di bagian atas pohon, dan tempatkan titik finish n sisa satu di setiap lembar (Gbr. 10). Jaringan yang dibangun dengan cara yang dijelaskan akan disebut pohon Alamat langsung.


gbr. 10

Mengubah arah semua aliran ke kebalikan di pohon Alamat langsung, dengan demikian kami memperoleh pohon Alamat terbalik, yang tujuannya adalah untuk menghubungkan dan memulai titik dengan satu selesai.

Dalam kasus di mana n adalah kekuatan dua, setiap rute di dalam pohon Alamat melewati persis log ₂ n switching node, yang tidak diragukan lagi (asimtotik) kurang dari indikator yang sama untuk jaringan dengan Seluler (O (√ n )), atau Linear ( O ( n )) topologi.

Dua jenis jaringan logaritmik yang paling sederhana
Menggunakan jaringan "mirip pohon" sebagai blok bangunan, tidak sulit untuk menggeneralisasi solusi sebelumnya untuk kasus ketika ada lebih dari satu titik awal, tetapi - k . Ada dua cara mudah untuk melakukan ini.

Cara pertama adalah dengan menggunakan pohon Alamat terbalik untuk pertama mengumpulkan rute dari semua perjalanan menjadi satu aliran umum, dan kemudian, menggunakan pohon Alamat langsung, membagi aliran ini menjadi sub-aliran, masing-masing ditujukan ke tujuannya (jaringan di atas pada Gambar. 11 )


gbr. 11

Jika k dan n adalah kekuatan dua, maka, pada akhirnya, rute apa pun melewati log ₂ k + log ₂ n switching node. Jaringan dibangun sesuai dengan algoritma yang baru saja dijelaskan, kami setuju untuk memanggil (searah) Logaritma dengan penggabungan awal .

Cara kedua untuk memecahkan masalah yang sama dapat diperoleh dengan membalikkan dalam solusi pertama urutan operasi merger dan pemisahan. Implementasinya adalah sebagai berikut: untuk setiap titik awal, buat satu set duplikat imajiner yang unik dari semua titik alamat selesai, dan kemudian sambungkan ke duplikat ini (sama sekali tidak imajiner) dengan pohon Alamat langsung.

Untuk menyelesaikan pembangunan jaringan, itu tetap hanya menghubungkan sekarang setiap titik selesai dengan pohon Alamat terbalik dengan k duplikat imajiner (jaringan dari bawah pada Gambar. 11).

Setiap kali n dan k adalah kekuatan dua, jumlah switching node pada jalur rute apa pun dalam jaringan yang baru dibangun akan kembali sama dengan log ₂ k + log ₂ n . Kami setuju untuk memanggil jaringan semacam ini (searah) Logaritmik dengan pemisahan awal .

Transformasi jaringan searah menjadi simetris
Secara umum, jaringan searahkami akan memanggil jaringan apa pun jika titik alamat yang terhubung olehnya dibagi secara ketat menjadi awal dan akhir. Secara default, untuk jaringan searah, akan diasumsikan bahwa ia menyediakan setidaknya satu rute pergerakan yang memungkinkan dari titik awal ke titik akhir mana pun.

Selain perjalanan seumur hidup, sulit untuk mengutip contoh di mana ketika beberapa titik alamat akan berfungsi sebagai rute hanya awal, dan yang lainnya - hanya bisa menjadi akhir mereka. Kami akan membawa alasan kami lebih dekat dengan kenyataan jika kami juga menyertakan jaringan di mana dua titik alamat terhubung oleh rute di kedua arah. Kami setuju untuk menyebut jaringan tersebut simetris .

Faktanya, tidak ada kesenjangan ideologis antara jaringan searah dan simetris: setiap jaringan simetris juga dapat digunakan sebagai jaringan searah, dan masing-masing jaringan searah, yang awalnya menghubungkan jumlah titik awal dan titik akhir yang sama, dapat ditransformasikan menjadi jaringan simetris (Gbr. 12).


gbr. 12

Gambar 13a dan 13b menunjukkan bentuk "simetris" dari Jaringan Log Pre-Merge dan Jaringan Logar pre-split. Contoh mereka menunjukkan kemungkinan mendasar menghubungkan n blok dengan jenis jaringan ini, di mana jumlah node switching yang dikunjungi selama perjalanan akan sebanding dengan logaritma jumlah blok di kota.


gbr. 13 a


gbr. 13 b


, , . , . .

, n , , , , .

Untuk mengatasi masalah yang dimaksud, kami akan menghasilkan pesan informasi bantu, mengikuti resep ini: untuk jangka waktu yang lama, kami akan mengumpulkan catatan semua perjalanan yang memiliki titik tetap di awal, dan secara acak kami akan menuliskan alamat tempat perjalanan ini berakhir. Pesan yang dihasilkan akan menjadi urutan acak yang terdiri dari nama-nama n titik alamat kota.

Salah satu cara untuk mengirimkan pesan ini ke Mars adalah dengan terlebih dahulu menyandikan semua nama dengan kata-kata biner dengan panjang yang sama, sehingga mengubah pesan asli menjadi urutan nol dan yang, dan hanya kemudian mengirim urutan yang dihasilkan melalui saluran komunikasi digital. Karena untuk pengkodean dapat dibedakan set nJika nama biner dari log panjang ₂ n diperlukan , maka panjang pesan digital adalah:

(jumlah rekaman) × log ₂ n karakter.

Hal yang paling menarik adalah bahwa menurut teori informasi, terlepas dari algoritma pengkodean yang digunakan, tidak mungkin untuk mengirimkan pesan yang sama rata-rata dengan jumlah karakter biner yang lebih sedikit.

Alternatif untuk secara langsung mentransmisikan nama-nama titik akhir yang dikodekan dapat menjadi metode di mana untuk setiap perjalanan ditunjukkan di mana dari arah yang mungkin mengubah rute di persimpangan berikutnya di jalan. Menurut asumsi kami, semua garpu di jaringan hanya bisa dua kali lipat, oleh karena itu, untuk menunjukkan arah dalam setiap kasus, tepat 1 bit diperlukan. Siapa pun yang memiliki peta kota dan mengetahui titik awalnya, rantai bit yang diadopsi akan cukup untuk melacak setiap rute dan mengembalikan urutan asli tujuan mereka. Jika jumlah rata-rata garpu (node ​​pembagian) yang dikunjungi selama satu perjalanan adalah x , maka panjang pesan biner dengan metode penyandian baru adalah: (jumlah catatan) × x.

Seperti yang dikatakan sebelumnya, metode pengkodean baru tidak bisa lebih efisien daripada metode transfer alamat biner langsung, oleh karena itu: (jumlah catatan) × x ≥ (jumlah catatan) × log ₂ n , di mana:

x ≥ log ₂ n .

Meskipun ketidaksetaraan terakhir pada awalnya disimpulkan untuk sekelompok perjalanan yang memiliki titik awal tetap yang sama, penampilannya ternyata tidak tergantung pada pilihan spesifik titik ini, jadi kami memiliki hak untuk memperluas hasilnya segera ke semua perjalanan di kota, sehingga memperoleh bagian pertama dari perkiraan yang diinginkan:

P1 ) Asalkan setiap perjalanan baru memiliki peluang yang sama untuk berakhir pada salah satu dari ntitik alamat kota, jumlah rata-rata node pembagi per rute tidak boleh kurang dari log ₂ n .

Secara mental membalikkan jam kembali, Anda akan membuat setiap perjalanan titik akhir titik awal, dan setiap simpul divisi jaringan biner simpul gabungan biner. Trik kecil ini memungkinkan Anda untuk secara otomatis mendapatkan bagian kedua yang hilang dari perkiraan dari P1:

P2 ) Asalkan setiap perjalanan yang telah selesai akan memiliki peluang yang sama untuk memulai di salah satu titik alamat n kota, jumlah rata-rata simpul merger per rute tidak boleh kurang dari log ₂ n .

Jika kita mengingat keberadaan jaringan logaritmik dengan penggabungan awal dan jaringan logaritmik dengan pemisahan awal, maka kita segera mendapatkan dua contoh jaringan yang optimal dalam hal jumlah node switching, yang, rata-rata, dikunjungi di dalamnya selama satu perjalanan. Mari kita lihat apakah kualitas ini membantu mereka mengurangi intensitas kerugian switching yang dihasilkan.

Berpindah biaya dalam jaringan Logaritmik

Jika kita membandingkan jaringan dengan penggabungan awal dan pemisahan awal, maka yang pertama terlihat jauh lebih menarik karena kesederhanaannya. Sayangnya, kesederhanaan ini juga memiliki sisi lain dari koin: menggabungkan semua rute menjadi satu aliran bertentangan dengan rekomendasi i1 , sehingga menjadi potensi penyebab kerugian waktu yang besar. Sebuah jaringan dengan pemisahan awal tampaknya mengikuti rekomendasi i1 - i3 , namun, dilihat dari Gambar 13b, ia cenderung dengan cepat meningkatkan jumlah tepi jalan dan mengganti node yang digunakan. Kualitas yang terakhir dapat membuat jaringan jenis ini terlalu mahal untuk penggunaan praktis.

Kami akan menganalisis masalah ini secara lebih rinci. Untuk mulai dengan, kami setuju bahwa kota tunduk pada model migrasi akses seragam, dan aliran perjalanan yang dihasilkan oleh salah satu titik alamatnya memiliki kapasitas unit.

Kerugian dalam jaringan dengan penggabungan awal
Pada Gambar 14 Anda dapat melihat diagram arus yang muncul dari pengaturan yang ditunjukkan dalam jaringan dengan penggabungan awal.


gbr. 14

Bagiku nyaman untuk menggambarkan jaringan itu sendiri dalam bentuk searah, menyiratkan bahwa setiap titik awal dan akhir, tidak ditandai dengan nomor yang sama dalam gambar, sebenarnya berarti titik alamat yang sama di kota.

Berdasarkan diagram, kami menghitung intensitas biaya switching yang dihasilkan dalam jaringan. Mari kita mulai dengan bagian kiri, di mana melalui pohon Alamat terbalik, semua rute dikumpulkan dalam satu aliran. Setiap switching node di bagian jaringan ini mewakili tempat di mana dua jalan raya searah bergabung menjadi satu (Gbr. 15).


gbr. 15

Jika awalnya masing-masing jalan dimuat secara efisien, maka setelah penyatuan mereka tidak perlu mengurangi jumlah lajur, sebagai akibatnya, seharusnya tidak ada pengurangan biaya terkait dalam biaya sambungan.

Misalkan aliran daya unit sudah cukup untuk secara efektif mengisi jalan di setidaknya dua jalur. Dalam hal ini, kita sampai pada kesimpulan yang agak tak terduga: penyatuan mobil mengalir di dalam jaringan Logarithmic dengan penggabungan awal terjadi benar-benar "gratis", tanpa menyebabkan kerugian sementara.

Menghitung biaya yang muncul di kanan setengah tidak jauh lebih sulit. Bagian dari jaringan ini adalah pohon Alamat langsung, setiap node yang merupakan garpu simetris di jalan yang telah kita pelajari. Ketika kekuatan aliran insiden p intensitas muncul karena kehilangan garpu sama ( α / 2 ν ) ⋅ p ² /2. Kekuatan aliran yang masuk ke root fork adalah: n , oleh karena itu, intensitas kerugian pada simpul root adalah: ( α / 2 ν ) ⋅ n ²/ 2. Di setiap generasi berikutnya dari pohon Alamat, jumlah garpu berlipat ganda, dan kekuatan aliran yang berjalan pada mereka terbelah dua. Akibatnya, rumus kehilangan di dalam seluruh pohon akan berbentuk:

I _{t_div1} = ( α / 2 ν ) ⋅ (1/2) ⋅ [ n ² + 2 ( n / 2) ² + 4 ( n / 4) ² + ... + ( n / 2) ⋅ 2 ² ] =

( α / 2 ν ) ⋅ ( n / 2) ² [1 + 1/2 + 1/4 + ... + 2 /n ] ≈ ( α / 2 ν ) ⋅ n ²

Karena kekuatan arus perjalanan yang dihasilkan bersama oleh semua titik alamat adalah n , biaya waktu per perjalanan rata-rata ( α / 2 ν ) ⋅ n , sehingga menunjukkan linier ketergantungan pada ukuran kota.

Ketika datang ke jaringan abstrak, sulit untuk memberikan estimasi yang berarti dari area jalan yang mereka gunakan. Sebagai ukuran alternatif kompleksitas struktural, kekuatan total semua aliran samping dapat dihitung. Sesuai rencana, nilai yang dihasilkan harus mencerminkan biaya sumber daya untuk mendirikan semua simpang susun yang diperlukan oleh jaringan. Saya tidak bisa mengatakan bahwa dalam praktiknya metode ini akan selalu memiliki interpretasi yang baik, tetapi saya mungkin akan bisa mendapatkan beberapa perkiraan tentang jumlah pekerjaan di depan.

Di dalam jaringan logaritmik dengan penggabungan awal, aliran samping hanya ada di pohon Alamat langsung, dan total daya mereka untuk setiap generasi node adalah sama: n / 2. Total log pohon ₂ ngenerasi node, jadi cara baru untuk menilai kompleksitas memberikan perkiraan kompleksitas: O ( n log ₂ n ).

Jaringan logaritmik dengan penggabungan awal
Jumlah titik alamat daya unit ........................................ ............ n
Rata-rata waktu perjalanan
hilang karena biaya peralihan:
perilaku asimptotik ........................ .................................................. ............................ O ( n )
nilai tepat ................ .................................................. ........................... ( α / 2 ν ) ⋅ n
Jumlah switching node ............................................... .................................. O ( n )
Jumlah switching node dengan mempertimbangkan kekuatan aliran sisi .... ............... O ( n log ₂ n )

Kerugian dalam jaringan dengan pemisahan pendahuluan Sekarang
mari kita lanjutkan ke analisis jaringan Logaritmik dengan pemisahan pendahuluan, sekali lagi dengan asumsi bahwa jaringan digunakan untuk menghubungkan titik-titik alamat daya unit di kota "akses seragam".

Gambar 16 menunjukkan fragmennya, terdiri dari satu titik alamat bersama dengan pohon Alamat langsung dan terbalik yang berdekatan dengan titik ini.


gbr. 16

Pertama, kami memperkirakan intensitas kerugian switching yang dihasilkan oleh fragmen.
Biaya yang dikeluarkan dalam pemisahan aliran dapat ditemukan dengan mengganti dalam rumus I _{t_div1} = ( α / 2 ν ) ⋅ n ² , yang diturunkan untuk pohon Alamat langsung pada contoh sebelumnya, bukan n - satu. Memang, pohon Alamat langsung pada Gambar 16 dan 14 memiliki kedalaman yang sama dan aliran arus yang serupa dalam ketebalannya sendiri ( _{kurang lebih.Kesamaan berarti kemampuan untuk mendapatkan satu set nilai dengan mengalikan nilai dari set lainnya dengan beberapa angka tetap, untuk menggambarkan, kesamaan antara segitiga di sisi mereka dapat digunakan} ). Karena ketergantungan kuadrat antara nilai biaya switching yang timbul pada garpu terpisah dan kekuatan aliran yang dipasok padanya, penurunan simultan dalam semua aliran dengan n kali akan mengurangi kerugian di seluruh pohon dengan n ² kali, oleh karena itu alih-alih yang lama ( α / 2 ν ) ⋅ n ² kami kita mendapatkan nilai yang sama dengan:

I _{t_div2} = ( α / 2 ν ).

Kami sekarang menghitung nilai biaya di bagian kiri fragmen.
Karena kecilnya aliran gabungan jalan di dalam pohon Alamat terbalik, kali ini tidak masuk akal untuk membangun lebih luas dari dua jalur. Merger dalam kondisi ini tidak lagi bebas biaya: berbeda dengan contoh sebelumnya, ada titik-titik penyempitan di jalan raya (Gbr. 17), di mana biaya pergantian akan diperlukan.


gbr. 17

Dengan anggapan bahwa pengemudi mengetahui penyempitan yang akan terjadi sebelumnya, kita dapat mengasumsikan bahwa proses perpindahan mobil dari jalan buntu lambat, terbentang ratusan meter di sepanjang jalan raya. Dalam hal ini, kami memiliki hak untuk menggunakan trik yang kami gunakan sebelumnya untuk menghitung kerugian pada garpu simetris - untuk membagi aliran migrasi total q menjadi banyak bagian kecil q _i , dan kemudian menafsirkan masing-masing sebagai aliran samping dari ramp. Kerugian yang dihasilkan oleh masing-masing subtipe tersebut dihitung dengan rumus:
I _i = ( α / 2 ν ) ⋅ p q _i ⋅ (1 + 1 / s), bagaimanapun, ada dua kehalusan.

Yang pertama adalah bahwa mobil tidak akan bermigrasi lebih jauh dari baris berikutnya.
Dan pada kenyataannya: aliran di dua jalur tengah, karena simetri yang jelas, harus selalu memiliki kepadatan yang kira-kira sama, sehingga pengemudi tidak akan memiliki banyak alasan untuk melewati garis tengah. Dari pengamatan yang dilakukan, berikut bahwa dalam formula untuk kerugian yang disebabkan oleh aliran lateral parsial, s sama dengan 1.

Ketika mesin meninggalkan jalur ekstrim, mengatur ulang dalam dua baris tengah, daya aliran di dalam pita pusat secara bertahap tumbuh, berubah dalam setiap kasus dari P / 2 ke P . Dengan demikian, kehalusan kedua adalah ketergantungan yang signifikan dari pdari jumlah subtream i , yang memaksa kita untuk tidak menulis:

I _i = ( α / 2 ν ) ⋅ p q _i ⋅ (1 + 1 / s ),
tetapi:
I _i = ( α / 2 ν ) p ( i ) ⋅ q _i ⋅ (1 + 1 / s ).
Dalam kasus ketika banyak bagian kecil di mana aliran migrasi dibagi semuanya memiliki ukuran yang sama, ketergantungan p ( i ) diekspresikan oleh grafik linier (Gbr. 18)


gbr. 18

Untuk menghitung intensitas total kerugian, kita harus menggunakan integrasi, atau (ini memungkinkan untuk membuat bentuk sederhana dari fungsi yang dapat diintegrasikan) karena p ( i ) mengambil nilai rata-rata pada grafik sama dengan 3 P / 4. Karena total aliran migrasi dari sisi setiap strip ekstrim adalah P / 2, intensitas kerugian pada merger terpisah adalah:

Saya _{menggabungkan} = 2 ⋅ ( α / 2 ν ) ⋅ (3 P / 4) ⋅ ( P / 2)

= ( α / 2 ν ) 3 P ² /4.

Untuk menemukan kerugian waktu yang dihasilkan di dalam fragmen pada pohon Alamat terbalik, kami menerapkan rumus untuk saya _gabungkan ke masing-masing _simpulnya :

I _{t_merge} = (3/4) ⋅ ( α / 2 ν ) [1 ⋅ (1/2) ² + 2 ⋅ (1/4) ² + 4 ⋅ (1/8) ² + ... + ( n / 2) ⋅ (1 / n ) ² ] ≈

≈ (3/4) ⋅ ( α / 2 ν ) [1/4 + 1/8 + 1/16 + ...] =

= (3/8) ⋅ ( α / 2 ν ) [1/2 + 1/4 + 1/8 + ...] =

= (3/8) ⋅ ( α / 2 ν ).

Total biaya yang timbul dalam fragmen akibat penggabungan dan pemisahan aliran adalah:

I _{t_merge} + I _{t_div2} = ( α / 2 ν ) [1 + 3/8] = 11/8 ( α / 2 ν ).

Jaringan logaritmik split pendahuluan hanya berisi n fragmen seperti itu, dan persis nunit flow dihasilkan oleh titik alamatnya, oleh karena itu, nilai yang baru saja kami temukan hanya sama dengan kerugian switching yang terjadi rata-rata per perjalanan.

Faktanya, itu lebih penting bagi kita bahkan bukan angka tertentu, yang sama dengan biaya peralihan tertentu, tetapi kenyataan bahwa biaya ini tetap konstan dengan meningkatnya n . Keadaan yang terakhir membuat jaringan Logaritmik dengan pemisahan awal tanpa gejala yang paling ekonomis sehubungan dengan penggantian kerugian, di antara semua jenis jaringan yang telah kita pelajari sebelumnya.

Sayangnya, kepemimpinan tidak dikenakan biaya "gratis." Meskipun ukuran kecil dari jumlah arus yang sangat kecil, setiap pohon Alamat yang termasuk dalam jaringan berisi sekitar 2 nrusuk jalan dua jalur dan sekitar n node switching berukuran penuh. Ada 2 n pohon dalam jaringan , yang berarti O ( n ² ) tepi dan node, yang membuatnya tidak hanya yang paling ekonomis dalam waktu, tetapi juga jaringan yang paling mahal untuk dibangun, di antara semua contoh yang dipertimbangkan.

Adapun jumlah aliran lateral, nilainya, seperti mudah untuk dihitung, tumbuh dengan kecepatan O ( n log2 n ) dan dalam hal ini tidak membawa banyak makna.

Jaringan logaritmik dengan pemisahan awal
Jumlah titik alamat daya unit ............................................ ............ n
Waktu perjalanan rata-rata,
hilang karena biaya switching:
asimptotik .......................................... .................................................. .......... O (1)
nilai tepat ...................................... .................................................. ........... 11/8 ( α / 2 ν ).
Jumlah switching node ............................................... .................................. O ( n ² )
Jumlah switching node dengan mempertimbangkan kekuatan aliran sisi ... ................ O ( n log ₂ n )

Jaringan seimbang logaritmik

Kehilangan switching yang sangat kecil, dengan kemungkinan penggunaan jaringan Logaritmik dengan pemisahan awal, tetapi pada saat yang sama terlalu banyak sumber daya untuk konstruksinya, menyebabkan keinginan untuk menemukan beberapa cara untuk mengubah desainnya sehingga konsumsi sumber daya berkurang secara signifikan, dan biaya switching tidak meningkat secara signifikan.

Jelas, penyebab utama banyaknya jalan dalam jaringan adalah efisiensi penggunaannya yang sangat rendah. Yang terakhir dapat dilihat dengan jelas pada Gambar 19, yang menunjukkan diagram terperinci dari aliran di dalam pohon Alamat langsung yang berdekatan dengan titik alamat ke- i .


gbr. 19

Dalam diagram, angka yang berdiri di atas tepi pohon menunjukkan kekuatan arus yang melintas di sepanjang tepi, dan interval di bawah ini adalah himpunan titik-titik alamat di mana aliran ini pada akhirnya akan didistribusikan. Dipercayai bahwa semua tepi yang ada pada diagram adalah jalan raya dua lajur, jumlah tepi pada setiap generasi pohon ditunjukkan di bagian bawah gambar.

Pada pemeriksaan lebih dekat, Anda mungkin memperhatikan bahwa aturan yang dengannya arus perjalanan dibagi dalam simpul tertentu ditentukan semata-mata oleh posisi simpul ini di dalam Pohon Alamat dan tidak bergantung pada jumlah titik alamat yang memunculkan perjalanan ini.

Jika ada beberapa aliran yang ditujukan ke set poin yang sama, dan masing-masing dari mereka tidak cukup kuat untuk mengisi jalur yang diberikan, maka mengapa tidak menggabungkan mereka bersama di satu jalan raya. Faktanya, ide dasarnya yang sederhana ini memungkinkan untuk membangun jaringan abstrak yang baik, menghasilkan kerugian switching yang relatif kecil, dan ekonomis dalam jumlah jalan yang digunakan.

Kembali ke pohon alamat saya engan titik, kita melihat bahwa datang simpul akar sungai dibagi dalam dua anak perusahaan kapasitas 1/2 masing-masing mengalir. Aliran anak tiri pertama terdiri dari perjalanan yang ditujukan ke titik-titik dari interval [1; n / 2], perjalanan kedua ditujukan ke titik-titik dari interval [( n / 2) + 1;n ].
Mengikuti ide yang diuraikan di atas, kami menyatukan anak tangga dari jenis yang sama di setiap titik ganjil dan titik alamat yang mengikutinya dalam urutan dengan nomor genap. Teknik semacam itu memungkinkan setiap pasangan titik yang dipilih untuk memiliki, bukannya empat aliran dengan kekuatan 1/2 hanya dua aliran besarnya satuan (Gbr. 20). Kami akan memberikan singkatan BN ₂ [i; i +1].


gbr. 20

Jika aliran anak tiri tidak digabungkan, tetapi masih di dalam pohon Alamat, maka pada generasi berikutnya dari node tercapai, masing-masing dari mereka lagi akan dibagi menjadi dua bagian, sama dalam kekuatan dan ukuran set titik di mana komponen perjalanan mereka dibahas.

Mengapa melanggar tradisi yang sudah ada, karena setelah penyatuan kita masih memiliki rangkaian tipe aliran yang sama seperti sebelumnya, tetapi dengan hanya sedikit perwakilan dari masing-masing jenis? - berlaku untuk masing-masing aliran keluaran BN ₂ [i; i +1] persis aturan pemisahan yang sama yang akan berlaku untuk aliran jenisnya di dalam pohon Alamat.

Tidak ada alasan mengapa konstruksi logis yang dijelaskan di atas untuk menggabungkan-memisahkan aliran yang sama tidak dapat diulang secara induktif. Gambar 21 menunjukkan diagram yang menggabungkan dua fragmen
BN ₂ menjadi satu fragmen BN ₄ , dan gambar 22 menunjukkan bagaimana algoritma terlihat dalam kasus umum.


gbr. 21


gbr. 22

Pada akhirnya, proses memperbesar fragmen akan selesai dan membawa kita ke satu-satunya elemen BN _n [1; n ], kita akan menyebutnya jaringan Seimbang dari tipe logaritmik (Gbr. 23).


gbr. 23

Mari kita periksa jaringan ini untuk kompleksitas dan besarnya kerugian switching yang dihasilkan.
Berdasarkan sifat induktif dari prosedur konstruksi Jaringan Seimbang, jumlah node switching yang termasuk dalam strukturnya dapat dijelaskan dengan persamaan pengembalian:

node (BN _k ) = 2 node (BN _{k / 2} ) + 2 k ,

dengan syarat batas:

node (BN ₁ ) = 0.

Solusi untuk sistem persamaan ini adalah fungsinya:

node (BN _n ) = 2 n log ₂ n .

Karena pembangunan BN _n memerlukan log ₂ n langkah-langkah induksi, setiap perjalanan akan melewati log ₂ n node pemisahan dan jumlah yang sama dari node penggabungan, bergantian di jalurnya (Gbr. 24).


gbr. 24

Kerugian yang dihasilkan dalam setiap simpul pemisahan:
( α / 2 ν ) ⋅ (1) 2/2 .

Kerugian yang dihasilkan dalam setiap simpul gabungan:
( α / 2 ν ) ⋅ 3 ⋅ (1/2) 2/4 = 3/16 ( α / 2 ν ).

Mengingat keduanya di Jaringan Seimbang adalah n log ₂ n , kami mendapatkan nilai pasti dari total kerugian switching:
11/16 ( α / 2 ν ) n log ₂ n ,

itu per satu perjalanan adalah:
11/16 ( α / 2 ν ) log ₂ n

Jaringan seimbang logaritmik
Jumlah titik alamat daya unit ............................................. ....... n
Waktu tempuh rata-rata
hilang karena biaya switching:
asimptotik ................................................. .................................................. ... O (log ₂ n )
nilai tepatnya ................................................ ............................................... 11/16 ( α / 2 ν ) log ₂ n
Jumlah switching node ............................................... .................................. O ( n log ₂ n )
Jumlah switching node, dengan mempertimbangkan kekuatan sisi mengalir ................... O ( n log ₂ n )

Angka-angka yang ditemukan di atas memungkinkan Balanced Network dianggap sebagai kompromi yang baik antara jumlah kehilangan waktu yang diperkenalkan dan keseluruhan kompleksitas struktural. Penggunaannya sebagai jaringan jalan kota nyata pada prinsipnya mungkin, tetapi secara ekonomis tidak mungkin dilakukan. Tampak bagi saya bahwa area di mana penggunaan Jaringan Seimbang sebenarnya dapat sangat bermanfaat adalah sistem informasi berskala besar dengan persyaratan ketat untuk jumlah penundaan sinyal, seperti komunikasi seluler, Internet, komputasi terdistribusi, komputer multiprosesor. Bagi kami, nilai utama dari Jaringan Seimbang adalah metode yang digunakannya. Beberapa saat kemudian, dengan menggunakan modifikasi dari metode ini, kita akan dapat meningkatkan jaringan Pusat Linear dan Seluler yang sangat penting dalam hal praktis.

Mengapa kota-kota bersejarah akan mengalami kemacetan lalu lintas

Pernyataan saya mungkin tampak tidak terduga, tetapi jawaban mengapa kota-kota berkembang secara alami, biasanya menderita kemacetan, sudah ditemukan oleh kami di paragraf sebelumnya. Jadi terdiri dari apa itu?

Faktanya adalah, banyak kota bersejarah yang selamat dari era benteng abad pertengahan (misalnya, hampir semua ibu kota "Dunia Lama") mewarisi dari waktu ini struktur radial jalan-jalan. Sayangnya (untuk penghuni modern mereka), jaringan jalan dengan topologi yang serupa tidak mengalami skala yang baik: lokasi jalan radial yang padat di dekat pusat menjadi terlalu jarang di pinggiran. Akibatnya, dalam proses pertumbuhan populasi, jalan-jalan yang semula terletak di sela-sela beberapa jalan menuju benteng menjadi lebih besar dan jalan-jalan yang tampak di pinggirannya pendek dan tidak memperoleh signifikansi transit yang cukup untuk bertambah luas. Akibatnya, jaringan jalan yang kita lihat sekarang di kota-kota bersejarah besar sekarang paling sering merujuk pada sistem transportasi tipe-Arteri, dan dalam terminologi kami - ke tipe jaringan Logaritma dengan penggabungan awal (tidak lengkap).


(Jalan Moskow, foto: Stepanov Slava)

Jika kita berbicara tentang panjang jalan yang harus dikendarai oleh pengemudi di sepanjang jalan, implementasi jenis jaringan ini tidak buruk: jarak yang ditempuh seringkali sedikit berbeda dari jarak garis lurus, dan nilai rata-rata di kota, seperti seharusnya untuk sistem transportasi yang “layak” , tumbuh pada tingkat O (√ n ). Masalahnya adalah bahwa dengan perluasan kota pada jaringan Logaritmik dengan penggabungan awal, biaya pergantian yang dihasilkannya meningkat terlalu cepat: jumlah waktu perjalanan rata-rata karena mereka tergantung pada jumlah orang yang tinggal di kota sebagai O ( n ) Jelas bahwa mulai dari beberapa n , kali ini akan menang atas waktu yang jelas untuk mengatasi jarak, dengan kata lain, kemacetan akan muncul di kota.

Tak ayal, reorganisasi sistem transportasi di kota-kota bersejarah besar adalah tugas yang bisa diselesaikan. Namun, penting untuk dipahami di sini bahwa pembangunan lain, dua, atau lima arteri transportasi besar, meskipun sedikit memperbaiki situasi di kota, tetapi akar penyebab kemacetan lalu lintas tidak akan dihilangkan. Rupanya, satu-satunya cara untuk mengatasi kekurangan jaringan Logarithmic dengan penggabungan awal adalah dengan menggunakan jaringan lain. Kandidat yang baik di sini mungkin jaringan dengan topologi Seluler, yang tingkat pertumbuhan waktu untuk menempuh jarak, setidaknya, bertepatan dengan tingkat pertumbuhan kerugian switching.


(Malam Berlin, foto: Vincent Laforet)

Mungkin itu sebabnya Berlin modern, meskipun memiliki jalan arteri besar, sudah dibedakan oleh struktur mesh yang terlihat jelas.

Ada banyak solusi menarik di dunia tentang cara membuat penghuni kota bersejarah lebih mobile, tetapi hadiah utama dalam perjuangan aksesibilitas transportasi mungkin harus diberikan kepada para insinyur Barcelona.


(Barcelona memperbarui jaringan jalan, foto: Vincent Laforet)

Pandangan rinci pada Jaringan Kota Linear dan Seluler

Setelah metode analisis ditemukan dan disempurnakan pada jaringan abstrak, sekarang saatnya untuk menerapkannya pada kasus kota yang lebih realistis dengan topologi Linear dan Cell. Pada bagian ini kami akan mencoba untuk menganalisis secara rinci fitur dari tautan transportasi mereka, menetapkan nilai numerik dari intensitas kehilangan switching, menemukan bagaimana nilainya tergantung pada ukuran kuartal, dan mendiskusikan kemungkinan variasi dan peningkatan.

Kota linear
Kali ini, perhatikan contoh kota di mana ada dua jalan satu arah: Barat dengan gerakan ke utara dan Timur dengan gerakan ke selatan (Gbr. 25).


gbr. 25

Biarkan setiap kuartal menghasilkan aliran perjalanan unit daya. Dalam hal ini, satu rute perjalanan yang mengarah dari satu blok ke akun lain untuk 1 / n arus lalu lintas.

Sebagai permulaan, kami mendefinisikan kekuatan aliran samping di jalan raya. Barat
jalan adalah satu-satunya cara untuk mencapai kuartal dengan nomor i dari
( n - i ) perempat di selatannya, dan satu - satunya cara yang dari perempat saya adalah untuk sampai ke ( i - 1) perempat yang terletak di utara itu. Oleh karena itu, kapasitas arus pertukaran lalu lintas antara Zapadnaya Street dan kuartal ke-1 sama dengan:

q _{W_out} = ( n - i ) / n - untuk aliran samping meninggalkan West Street,
q _{W_in} = ( i - 1) / n - untuk aliran samping yang berdekatan dengan gerakan di atasnya. Jelas bahwa kekuatan sisi mengalir di Jalan Vostochnaya tergantung pada saya secara simetris:
q _{E_out} = ( i - 1) / n adalah kekuatan yang pergi,
q _{E_in} = ( n - i ) / n adalah kekuatan aliran samping yang berdekatan dengan lalu lintas di East Street.

Tentu saja, jumlah arus yang keluar dari kuartal ke-1:

q _{E_in} + q _{W_in} = ( n - 1) / n ,
cocok dengan jumlah arus yang masuk:
q _{E_out} + q _{E_out} = ( n - 1) / n ,
dan kedua nilai ini tidak bergantung pada i dengan cara apa pun (setiap kuartal memiliki aliran perjalanan sebesar 1 / n besarnya, yang keduanya dimulai dan berakhir di dalam dirinya sendiri).

Untuk menemukan kekuatan arus utama, kami menggambar garis imajiner melintasi Western Highway pada tingkat yang sama dengan kuartal ke-1. Secara total, baris ini akan melewati:
(jumlah perempat dari bawah) × (jumlah perempat dari atas) = ​​( n - i ) ( i - 1) rute yang bersama-sama membuat aliran dengan nilai:

P _W ( i ) = ( n - i ) ( i - 1) / n .

Formula yang sama:
(jumlah perempat dari bawah) × (jumlah perempat dari atas) / n ,
harus diekspresikan dan kekuatan arus lalu lintas P _E di East Street, dengan kata lain:

P _E ( i ) = P _W ( i ) = P ( i ).

Mengetahui kekuatan semua arus utama dan aliran samping, kita dapat menghitung intensitas kerugian yang terjadi pada jaringan di area dekat kuartal ke-1:

I ( i ) = ( α / 2 ν ) ⋅ P ( i ) ⋅ [( q _{E_in} + q _{W_in} ) ⋅ (1 + 1 / s ) + ( q _{E_out} + q _{E_out} ) ⋅ (1 - 1 / s )] =
= ( α / 2 ν ) ⋅ P ( i ) ⋅ [(1 - 1 / n ) ⋅ (1 + 1 / s ) + (1 - 1 / n ) ⋅ (1 - 1 / s )] =
= ( α / 2 ν ) ⋅ 2 P ( i ) ⋅ (1 - 1 / n ) =
= 2 ( α / 2 ν ) ⋅ (1 - 1 / n ) ⋅ ( n - i ) ( i - 1) / n =
= 2 ( α / 2 ν ) ⋅ (1 - 1 / n ) ⋅ ( n - i ) ⋅ ( i - 1) ⋅ (1 / n ).

Jika kita menjumlahkan ekspresi terakhir atas i , maka kita mendapatkan intensitas kerugian yang dihasilkan oleh seluruh jaringan secara keseluruhan.

I = ∑ _i I ( i )
= ∑ _i 2 ( α / 2 ν ) ⋅ (1 - 1 / n ) ⋅ ( n - i ) ⋅ ( i - 1) ⋅ (1 / n ) =
= 2 ( α / 2 ν ) ⋅ (1 - 1 / n ) ⋅ n ² ⋅ ∑ _i (1 - i / n ) ⋅ ( i / n - 1 / n ) ⋅ (1 / n ) ≈
≈ 2 ( α / 2 ν ) ⋅ n ² ⋅ ∑ _i ( i / n ) ⋅ (1 - i / n ) ⋅ (1 / n ).

Jumlah ∑ _i ( i / n ) ⋅ (1 - i / n ) ⋅ (1 / n ) dapat diganti dengan integral dengan akurasi yang baik oleh integral:

∫ t (1 - t ) d t ( t ∈ [0; 1]) = 1/2 - 1/3 = 1/6.

Di mana kita mendapatkan bahwa intensitas switching kerugian di kota Linear dengan n blok kapasitas unit adalah:

I = ( α / 2 ν ) n 2/3.

Hingga saat ini, kami hanya mempertimbangkan contoh di mana perempat selalu menghasilkan aliran daya unit. Mari kita lihat apakah rumus untuk kerugian switching dari Kota Linear berubah jika tidak ada sumber daya unit tunggal untuk setiap kuartal, tetapi - λ (kuartal akan menjadi λ kali lebih besar).

Ambil kota dengan blok m . Jika blok daya yang dihasilkan mengalir 1, maka kerugian switching adalah ( α / 2 ν ) m 2/3. Peningkatan daya produksi perjalanan dengan faktor λ setiap triwulan menyebabkan peningkatan λ dari aliran utama dan samping secara bersamaan, oleh karena itu, biaya pada setiap pertukaran, dan oleh karena itu di dalam jaringan secara keseluruhan, meningkat dengan faktor ² , dan rumus kerugian berupa:

I = ( α / 2 ν ) m ² ⋅ λ 2/3 .

Secara umum, tidak masalah bagaimana kerugian switching tergantung pada jumlah perempat di kota, hal utama bagi kami adalah bagaimana mereka bergantung pada aliran daya dari semua perjalanan yang dihasilkan di dalamnya, atau dengan kata lain, pada jumlah n unit sumber daya. Dalam kasus yang dipertimbangkan, n sama dengan m ⋅ λ , oleh karena itu:

I = ( α / 2 ν ) m ² ⋅ λ 2/3 =
= ( α / 2 ν ) ( m ⋅ λ ) 2/3 =
= ( α / 2 ν ) n 2/3.

Dengan kata lain, kerugian switching di Kota Linear tidak tergantung pada kecilnya divisi menjadi kuartal.

Kota sel
Bayangkan sebuah kota seluler di mana jalan-jalan jalan tegak lurus tingginya berada pada tingkat yang berbeda. Ini dimungkinkan, misalnya, jika semua jalan jalanan yang mengarah dari utara ke selatan dibesarkan di jembatan, dan jalan yang membentang dari barat ke timur dibangun di permukaan bumi. Jika, di samping itu, semua jalan memiliki lalu lintas dua arah, maka peta jalan di kota tersebut akan dirujuk ke Topologi Seluler Standar (Gbr. 26).

Maksudnya di sini, tentu saja, bukan untuk membawa jaringan yang dijelaskan di atas dengan serius ke dalam praktik: itu tidak akan terlihat terlalu estetis dengan latar belakang lanskap kota dan, apalagi, karena kebutuhan untuk persimpangan multi-level, itu akan memakan sebagian ruang jalan yang baik. Namun demikian, jaringan murni hipotetis ini adalah cara yang baik untuk mendapatkan perkiraan yang diperlukan, yang nantinya dapat dengan mudah diperluas ke jaringan jalan yang benar-benar menarik dari sudut pandang penerapannya di kota-kota nyata.

Seperti biasa, kami akan menganggap bahwa kebutuhan migrasi penduduk dijelaskan oleh model “akses seragam”, dan kami akan memulai pertimbangan kami dengan kasus ketika kapasitas semua aliran perjalanan yang dihasilkan oleh kuartal terpisah adalah 1.

Dalam contoh dengan Standard Cellular City, akan lebih mudah untuk menjauh dari tradisi yang sudah ada dan mempertimbangkan titik alamat bukan sebagai seperempat yang terpisah, tetapi sebagai zona teritorial dengan bentuk persegi, yang menangkap persimpangan jalan raya dan seperempat dari semua lingkungan yang berdekatan dengannya. Gambar 27 menunjukkan posisi relatif dari beberapa zona tersebut dan menunjukkan pola lalu lintas di dalam salah satunya. Diagram ini dengan jelas menunjukkan bahwa setiap pengemudi, meninggalkan seperempatnya, memiliki kesempatan untuk naik ke jalan raya, bergerak ke arah salah satu dari empat Bagian Dunia.


gbr. 26

Untuk menemukan nilai biaya peralihan yang dihasilkan oleh kota, kami menghitung kekuatan semua arus utama dan aliran samping di masing-masing zona teritorialnya. Bentuk dan pengaturan timbal balik dari zona memungkinkan kita untuk menggunakan analogi catur untuk menyelesaikan masalah terakhir, mengingat zona sebagai sel-sel lapangan, dan pergerakan mobil di antara mereka - pergerakan kapal (Gbr. 27). Dari satu sel ke sel lainnya, asalkan mereka berada dalam "posisi umum" satu sama lain, benteng dapat dipindahkan dalam dua gerakan, dan jika kedua sel terletak pada horisontal yang sama atau satu vertikal, maka dalam satu.


gbr. 27

Untuk menghindari banyak reservasi yang tidak nyaman, kami berasumsi bahwa langkah di mana benteng tidak bergerak di mana pun juga diizinkan menurut aturan kami. Rute pergerakan rook, yang terdiri dari dua gerakan, salah satunya harus dilakukan secara vertikal dan yang lainnya secara horizontal, disebut yang paling sederhana. Adalah masuk akal untuk mempertimbangkan gerakan “di tempat” baik secara vertikal maupun horizontal pada saat yang bersamaan. Dalam hal ini, pernyataan itu benar bahwa setiap dua sel di papan terhubung satu sama lain dengan tepat dua rute paling sederhana yang berbeda.

Untuk pengemudi, rute "paling sederhana" adalah cara termudah untuk mendapatkan dengan gangguan minimal dari satu zona teritorial ke zona lainnya, jadi masuk akal untuk mengasumsikan bahwa perjalanan nyata akan berlangsung di sepanjang jalur rute dasar. Menurut model “akses seragam” yang dihasilkan oleh titik alamat (zona teritorial), aliran daya unit harus didistribusikan secara merata antara semua titik alamat n = d ² kota, sehingga kapasitas arus perjalanan yang melewati satu jalur rute adalah 1 / (2 n ).

Kami menghitung aliran berapa yang melewati sel ( i , j ) dalam arah dari selatan ke utara. Rute paling sederhana melintasi sel ( i , j ) dari selatan ke utara hanya dalam dua situasi. Yang pertama (Gbr. 28 di sebelah kiri):

1a) sel awal rute terletak di salah satu (kontur) garis ( d - i ) terakhir;
2a) titik akhir rute adalah salah satu ( i - 1) sel pertama dari vertikal ke-4 (kolom);
3a) rute dimulai dengan bagian horizontal, atau terletak seluruhnya di dalam kolom j .


gbr. 28

Kondisi yang menggambarkan situasi kedua terlihat simetris (Gbr. 28 di sebelah kanan):

1b) titik awal rute adalah salah satu sel ( d - i ) terakhir dari vertikal j ;
2b) sel terakhir dari rute berada dalam salah satu kontur pertama ( i - 1)
3b) rute dimulai dengan bagian vertikal, atau seluruhnya terletak di dalam kolom j .

Di papan catur hanya ada 2 × [ d ⋅ ( i - 1) + 1 ⋅ ( i - 1)] × ( d - i ) cocok untuk persyaratan rute paling sederhana, yang bersama-sama menciptakan aliran daya:

P _SN ( i , j ) = ( d + 1) ⋅ ( i - 1) ⋅ ( d - i ) / n (= P _SN ( i )).

Memperbaiki j , kita mendapatkan fungsinya

( P _SN ) _j ( i ) = P _SN ( i , j = Const),

menggambarkan ketergantungan kekuatan aliran yang bergerak ke utara di sepanjang jalan raya vertikal ke- j , pada jarak ke batas atas kota, diukur dalam sel.
Ada beberapa pengamatan yang kurang lebih jelas tentang fungsi ( P _SN ) _j ( i ), mari kita bahas.

Kita mulai, mungkin, dengan keadaan yang akan sulit untuk diabaikan: P _SN ( i , j ) sebenarnya independen dari argumen kedua. Akibatnya, fungsi ( P _SN ) _j ( i ) = P _SN ( i ) memiliki bentuk yang sama untuk semua nilai j , dengan kata lain, posisi spesifik jalan di dalam Kota Seluler tidak memengaruhi bebannya. Secara formal, pernyataan terakhir terbukti hanya untuk jalan raya yang mengarah ke utara, tetapi karena simetri kota itu secara otomatis meluas ke jalan raya arah lain juga.

Sekarang mari kita lihat rumus itu sendiri untuk P _SN ( i ):

( d + 1) ⋅ ( i - 1) ⋅ ( d - i ) / (2 n ).

Seperti yang kita lihat, seluruh ketergantungan P _SN pada i terletak pada ekspresi ( i - 1) ⋅ ( d - i ). Ungkapan ini dapat diartikan sebagai produk dari panjang interval kanan dan kiri di mana segmen bilangan bulat panjang d terbelah setelah elemen ke- i dihilangkan darinya (Gbr. 29a).


gbr. 29a


gbr. 29b

Jelas bahwa jika Anda mengubah "kanan" menjadi "kiri" dan "kiri" menjadi "kanan" (Gbr. 29b), hasil pekerjaan akan tetap sama. Dari pengamatan sederhana seperti itu, pada dasarnya, ada dua kesimpulan yang sangat berguna bagi kita:

1. fungsi P _SN ( i ) simetris sehubungan dengan titik tengah jalan i = ( d + 1) / 2, dengan kata lain, kekuatan aliran pada jarak Δ dari batas bawah kota sama persis dengan jarak Δ dari batas atas.
2. Secara keseluruhan, kota itu sendiri simetris ke atas dan ke bawah, oleh karena itu, untuk mendapatkan fungsi ( P _NS ) _j ( i ), yang menggambarkan aliran daya di jalan raya j , tetapi dalam arah selatan, cukup dengan hanya mencerminkan grafik fungsi ( P _SN) ) _j ( i ) pada baris i = ( d + 1) / 2. Karena ( P _SN ) _j ( i ) = P _SN ( i ), dan grafik P _SN ( i ) sehubungan dengan garis i = ( d + 1) / 2 adalah simetris, maka ( P _NS ) _j ( i ) = P _SN ( i) ) = P _vert ( i ), dengan kata lain, arus lalu lintas langsung dan yang akan datang memiliki kekuatan yang sama di mana saja di kota. Grafik perkiraan P _SN ( i ) ditunjukkan pada Gambar 30 (diyakini bahwa d >> 1, i >> 1, d - i >> 1).

gbr. 30

Kekuatan arus utama sepanjang jalan raya horisontal mudah ditemukan dengan menggunakan simetri rotasi, secara formal, proses ini bermuara pada penggantian sederhana i oleh j di P _SN ( i ) dan versi kecil dari indeks yang lebih rendah.

Hal selanjutnya yang harus dilakukan adalah menemukan kekuatan sisi yang mengalir. Perjalanan yang mengalir masuk atau keluar dari lalu lintas di jalan raya vertikal di dalam sel ( i , j ) dapat dengan mudah dibagi menjadi empat kategori:

1. q _{in_transit} : — i - , — j - , ( i , j ) ( 31a);
2. q _{out_transit} : — j - , ( i , j ), — i - ( 31b);
3. q _in : — ( i , j ), — i - ( 31c);
4. q _out : — i - . — ( i , j ) ( 31d).

gbr. 32: abcd

, , , :

q ₀ = d ⋅ ( d − 1) /(2 n )

, , . ( i , j ) :

I _vert ( i , j ) = ( α /2 ν ) ⋅ P _vert( i ) ⋅ [( q _dalam + q _{in_transit} ) ⋅ (1 + 1 / s ) + ( q _out + q _{out_transit} ) ⋅ (1 - 1 / s )]
= 4 ( α / 2 ν ) ⋅ ( d + 1) ( i - 1) ( d - i ) ⋅ d ( d - 1) / 2 n ² ≈
≈ 2 ( α / 2 ν) ⋅ d ⁵ ⋅ ( i / d ) (1 - i / d ) ⋅ (1 / d ) ⁴ =
= 2 ( α / 2 ν ) ⋅ d ² ⋅ ( i / d ) (1 - i / d ) ⋅ (1 / d ).

Untuk mengetahui biaya yang timbul di jalan-jalan vertikal di seluruh kota, kita perlu menjumlahkan I _vert ( i , j ) :

I _vert = ∑ _ij I _vert ( i , j ) =
= 2 ( α /2 ν ) ⋅ d ² ⋅ ∑ _ij ( i / d )(1 − i / d ) ⋅ (1/ d ).

j , d :

∑ _ij ( i / d )(1 − i / d ) ⋅ (1/ d ) = d ⋅ ∑ _i ( i / d )(1 − i / d ) ⋅ (1/ d ).

:

∑ _i ( i / d )(1 − i / d ) ⋅ (1/ d ) ≈ ∫ t (1 − t ) d t ( t ∈[0; 1] ) = 1/2 − 1/3 = 1/6.

,

I _vert = ( α /2 ν ) ⋅ d ³ /3 = ( α /2 ν ) ⋅ n √ n /3.

, I _horiz , , , :

I _horiz = I _vert = ( α /2 ν ) ⋅ n √ n /3.

Dengan demikian, intensitas switching kerugian dalam seluruh jaringan Kota Seluler Standar adalah:

I = I _vert + I _horiz = 2/3 ⋅ ( α / 2 ν ) ⋅ n √ n ,

dan biaya rata-rata per perjalanan adalah

2/3 ⋅ ( α / 2 ν ) ⋅ √ n

Pengaruh ukuran sel pada nilai kerugian switching
, — . , λ .
m . , I ₁ = 2/3 ⋅ ( α /2 ν ) ⋅ m √ m . λ λ , λ ² . :

I = 2/3 ⋅ ( α /2 ν ) λ ² ⋅ m √ m

, λ , : n = λ m . I n λ :

I = 2/3 ⋅ ( α /2 ν ) λ ² ⋅ m √ m =
= 2/3 ⋅ ( α /2 ν ) ⋅ √ λ ⋅ ( λ √ λ ) ⋅ ( m √ m ) =
= 2/3 ⋅ √ λ ( α /2 ν ) ⋅ ( λ m )√( λ m ) =
= 2/3 ⋅√ λ ( α / 2 ν ) ⋅ n √ n .

Biaya rata-rata per perjalanan dalam kondisi baru adalah 2/3 ⋅ √ λ ( α / 2 ν ) ⋅ √ n , menjadi √ λ kali lebih tinggi dari nilainya di kota yang terdiri dari unit kapasitas unit.

Formula terakhir memberi tahu kita bahwa untuk populasi yang sama, kepadatan populasi, dan luas total semua jalan, biaya pergantian biaya lebih tinggi, semakin besar ukuran perempat pada saat mendesain kota dipilih oleh arsiteknya. Jika populasi kota tidak terdistribusi secara merata di wilayahnya, tentu saja, Anda perlu memperhatikan bukan pada dimensi geometris, tetapi pertama-tama untuk jumlah rata-rata orang di dalam kuartal dan aktivitas migrasi mereka.


(Pusat Kota New York foto: Vincent Laforet)

Pernyataan di atas sangat penting ketika merancang area dengan gedung pencakar langit. Karena kombinasi kepadatan populasi yang tinggi dan mobilitasnya yang tinggi, maka diinginkan untuk membuat tempat di daerah-daerah yang tinggi beberapa kali lebih kecil daripada biasanya untuk membangun lantai standar. Dalam peradaban, di mana konstruksi gedung pencakar langit memiliki sejarah panjang, praktik mengisolasi bahkan bangunan besar terpisah sebagai blok tersebar luas.

Traffic Light Cellular City
Dalam setiap kasus, ketika garis-garis dua jalan yang sibuk berpotongan pada peta, arsitek harus membuat pilihan: mengangkat salah satu dari jalan-jalan ini ke jembatan, membiarkan aliran yang lain lewat dengan bebas dari bawah, atau menyadari persimpangan dalam bentuk persimpangan biasa, dan menyelesaikan konflik aliran yang mengakibatkan lalu lintas peraturan Opsi kedua menarik dengan kesederhanaannya, kurangnya kebutuhan untuk membangun struktur teknik berskala besar, dan di samping itu, ia menyediakan cara mudah untuk menyeberang jalan bagi pejalan kaki, karena alasan-alasan ini di kota-kota yang sering mereka sukai.


(pusat kota Los Angeles sore, foto: Boris Shein)

Penggunaan lampu lalu lintas di jaringan dengan topologi sel memiliki karakteristiknya sendiri. Dalam Bab 1, ditunjukkan bahwa dengan sinkronisasi lampu lalu lintas, mobil, saat mereka bergerak di sepanjang jalan yang sama, bahkan tidak harus berhenti di persimpangan: lampu hijau akan selalu menyala ke arah mereka. Fenomena semacam ini biasanya disebut rezim gelombang hijau . Untuk membuatnya, arus lalu lintas harus dibagi menjadi dua zona bergantian dari dua jenis: diisi dengan mobil dan bebas dari mereka. Selanjutnya, mode pengoperasian lampu lalu lintas seperti itu dipilih sehingga dalam periode waktu ketika "bagian" berikutnya melewati persimpangan di sepanjang salah satu jalan, bagian mobil yang sebelumnya bergerak di sepanjang jalan tegak lurus telah melewatinya, dan yang berikutnya belum tiba (Gbr. 33).


gbr. 33

Kemampuan untuk mengarahkan lalu lintas dalam mode hijau membawa biaya sendiri dan memberlakukan batasan tertentu pada tata ruang jalan-jalan kota.

Melihat kembali pada Gambar 33, mudah untuk melihat bahwa pada waktu tertentu tepat setengah dari area semua jalan sebenarnya tidak digunakan. Untuk mengimbangi yang sederhana, pada separuh jalan yang digunakan, kekuatan lokal mobil mengalir dan jumlah jalur yang diperlukan untuk mereka harus dua kali lebih banyak daripada di kota dengan jalan layang.

Keadaan terpenting kedua yang terkait dengan penggunaan gelombang hijau adalah peraturan ketat tentang ukuran tempat yang diizinkan: panjangnya (untuk jalan dua arah) harus merupakan kelipatan dari panjang gelombang hijau yang diisi (bagian dari aliran di dalam di mana gerakan tanpa hambatan dimungkinkan), yaitu sekitar 500 meter. Seperti disebutkan dalam paragraf sebelumnya, daerah dengan kepadatan penduduk yang tinggi memerlukan frekuensi peningkatan lokasi jalan, sehingga pembatasan dari bawah pada jarak antara jalan raya berpotensi dapat menyebabkan kesulitan lalu lintas.

Sangat menarik untuk dicatat bahwa dalam mode gelombang hijau, aturan sedikit berubah sesuai dengan rute perjalanan yang dialihkan di dalam jaringan. Misalnya, koneksi mobil lain ke arus lalu lintas utama di jalan raya dapat dilakukan di antara zona yang diisi, sehingga tidak menyebabkan biaya switching yang serius (titik "1", Gbr. 34a).


gbr. 34

Tentu saja, mobil ini sendiri harus kehilangan waktu menunggu zona kosong terdekat sebelum masuk ke jalan raya, dan setelah itu masih berdiri di lampu lalu lintas hingga zona penuh berikutnya mencapainya (titik "2", Gbr. 34a), Namun, besarnya kerugian ini tidak tergantung pada ukuran kota atau pada kesibukan lalu lintas di jalan, sehingga mereka dapat diabaikan dalam skala besar.

Situasinya benar-benar berbeda jika sebuah mobil mencoba untuk meninggalkan lalu lintas di jalan raya (Gbr. 34b). Di sini, dalam semua kemungkinan, sudah tidak ada cara rumit bagaimana membuat kerugian switching yang dibuatnya lebih sedikit. Selain itu, karena penggandaan kekuatan lokal dari aliran di dalam zona yang terisi, pemindahan mobil yang dipilih secara sewenang-wenang dari mobil itu menghabiskan biaya waktu dua kali lipat biaya di kota dengan jalan layang. Secara total, "pintu masuk" yang lebih murah dan "jalan keluar" yang lebih mahal dari aliran jalan saling mengimbangi, membuat Traffic Light Cell City dalam hal ini hampir tidak lebih baik, tetapi tidak lebih buruk dari Standar.

Kota Seluler Satu Arah
Selain penggunaan lampu lalu lintas, ada setidaknya satu kesempatan lagi untuk menjauh dari persimpangan mengerikan dari Standard City. Ini terdiri dari jalan yang membagi secara spasial (Gbr. 35) dengan arah gerakan yang berlawanan.


gbr. 35

Sebagai hasil dari perubahan tersebut, jumlah jalan akan berlipat ganda, semuanya akan menjadi satu sisi, tetapi yang paling penting, simpang susun akan sangat disederhanakan (Gbr. 36).


gbr. 36
, , , , () . , .

Jalan "Linear".

Bagaimana cara mengganti kerugian dapat dikurangi di Jaringan Seluler? Jawaban atas pertanyaan ini akan memungkinkan kita untuk berhasil memilih analogi dan sedikit mengerti.

Pertimbangkan modifikasi Jaringan Seluler yang agak tidak biasa, yang menyiratkan bahwa semua jalan raya yang membentang dari barat ke timur adalah dua arah, sedangkan di jalan yang tegak lurus dengan mereka, lalu lintas hanya diperbolehkan dalam satu arah: baik utara atau selatan, dan arah ini bergantian dari jalan ke jalan.

Seperti biasa, kita akan berasumsi bahwa kota mematuhi model akses seragam, dan setiap triwulan menghasilkan aliran perjalanan daya unit bersyarat.

Dalam hal ini, tampaknya masuk akal bahwa inti di dalam seperempat ( i , j) arus perjalanan, meninggalkannya, didistribusikan di antara jalan-jalan terdekat sebagai berikut: 1/4 dari itu sampai ke jalan horizontal dari atas, 1/4 lebih ke jalan horizontal dari bawah, 1/4 ⋅ i / d mengalir ke utara di sepanjang jalan raya vertikal dan
1/4 ⋅ (1 - i / d ) - di sepanjang jalan raya vertikal kedua ke selatan (Gbr. 37).

gbr. 37

Memang, menurut algoritma pembangunan rute yang telah dibahas sebelumnya, menurut statistik, setengah dari perjalanan akan dimulai dari bagian horizontal, dan untuk pengemudi yang lebih menyukai setengah ini, pada umumnya harus tidak peduli apakah jalur mereka terletak di utara kuartal ( i , j ) atau ke selatan itu. Setengah perjalanan yang tersisa akan dimulai dengan bagian lalu lintas vertikal dan akan dibagi antara jalan raya selatan dan utara berkenaan dengan jumlah perempat jalan ( i , j ) selatan ke jumlah perempat yang terletak di utara itu.

Adapun aliran perjalanan diarahkan ke dalam ( i , j), maka aturan pembagiannya relatif terhadap jalan raya yang mengelilingi kuartal akan simetris (Gbr. 38).


gbr. 38

Di antara empat persimpangan yang berdekatan dengan kuartal ( i , j ), kami mempertimbangkan secara terpisah aliran lateral di persimpangan jalan raya horisontal bawah dan jalan vertikal dengan lalu lintas utara (Gbr. 38). Alur mobil yang bergerak dari jalan horizontal ke vertikal adalah:
1/2 ⋅ (jumlah perempat pada horizontal) × (jumlah perempat pada vertikal tidak lebih rendah dari ( i , j )) ⋅ 1 / d ² =
= 1/2 ⋅ d ⋅ i / d ² =
= 1/2 ⋅ i / d .
:
1/2 ⋅ ( ( i , j ))×( ) ⋅ 1/ d ² =
= 1/2 ⋅ ( d − i ) ⋅ d / d ² =
= 1/2 ⋅ (1 − i / d ).

Sekarang mari kita mengalihkan perhatian kita dari Kota Seluler sebagai keseluruhan ke salah satu dari jalan-jalan vertikalnya, sebut saja My_street. Karena simetri, kami tidak akan membatasi alasan kami sama sekali, jika kami menganggap bahwa pergerakan di sepanjang My_street diarahkan dari selatan ke utara (Gbr. 39).


gbr. 39

Gambar 40 menggambarkan grafik kekuatan arus utama dan samping mengalir di jalan raya di sepanjang My_street, yang, seperti diketahui oleh pembaca, sangat mirip dengan grafik serupa untuk jalan raya satu arah dari Kota Linear (Gbr. 26).



gbr. 40

Dalam contoh-contoh ini, pola aliran bertepatan sepenuhnya jika di dalam My_street, aliran lateral yang berkaitan dengan masing-masing pasangan tempat yang berlawanan dan jalan raya horizontal di bawahnya secara resmi ditugaskan ke satu sel teritorial imajiner. Seperti dapat dilihat dari tabel sebelumnya, jaringan jalan Kota Linear menghasilkan beberapa kerugian switching terbesar di antara jaringan arsitektur yang telah kita pelajari. Dari sudut pandang ini, pola lalu lintas dalam jalan kota sel tunggal terlihat sangat tidak efisien dan merupakan elemen yang harus dicoba untuk ditingkatkan sejak awal.

Jaringan Lanjutan untuk Kota Linear
Jadi, kita dihadapkan dengan tugas meningkatkan Jaringan Linear sehingga tidak berubah menjadi "kotak". Keadaan yang memperkenalkan inefisiensi terbesar dalam pengoperasian Linear Network adalah penyatuan semua rute menjadi hanya dua arus lalu lintas yang sangat besar. Dalam situasi ini, langkah yang masuk akal adalah membagi aliran di sepanjang kedua jalan raya menjadi Q bagian yang sama. Karena biaya waktu yang disebabkan oleh setiap mobil yang bergabung atau meninggalkan lalu lintas sebanding dengan intensitas lalu lintas di atasnya, sebagai akibat dari membagi garis jalan menjadi bagian-bagian Q yang terisolasi (Gbr. 41a), mengganti kerugian di dalam kota Linear seharusnya telah berkurang dengan faktor Q.


gbr. 41

, — , -, . , , «» , ( 41b).

. , . , r _k , Δ _k = ( x _k , x _{k +1} ] () x _k (, ). , () x _k , r _k q _in | Δ _k |/ n ( 1/ n Δ _k ), , r _k , - .

[1, x _k ] Δ _k , , , Δ _k , q _out x _k / n ( 42).


gbr. 42

«» , | Δ _k |/ n , , x _k >> | Δ _k |, . p _k r _k P _k x _k ⋅ | Δ _k |/ n . r _k :

I _k = ( α /2 ν ) ⋅ ∑ _x [ q _in ( x ) ⋅ p _k ( x ) ⋅ (1 + 1/ s ) ] + ( α /2 ν ) ⋅ ∑ _x [ q _out ( x ) ⋅ p _k ( x ) ⋅ (1 − 1/ s ) ] =

= ( α /2 ν ) ⋅ (1 + 1/ s ) ∑ _x [ | Δ _k |/ n ⋅ p _k ( x ) ] + ( α /2 ν ) ⋅ (1 − 1/ s ) ∑ _x [ x _k / n ⋅ p _k ( x ) ] =

= ( α /2 ν ) ⋅ (1 + 1/ s ) ⋅ ( x _k ⋅ | Δ _k | / n ) ⋅ ( ∑ _x p _k ( x )) / x _k + ( α / 2 ν ) ⋅ (1 - 1 / s ) ⋅ ( x _k ⋅ | Δ _k | / n ) ⋅ ( ∑ _x p _k ( x )) / | Δ _k |, di

mana jumlah pertama diambil alih bagian x ∈ [1,x _k ], — x ∈ Δ _k . :

( ∑ _x p _k ( x ) )/ x _k , x ∈ [1, x _k ]

( ∑ _x p _k ( x ) )/| Δ _k |, x ∈ Δ _k

, r _k . , P _k /2.
x _k ⋅ | Δ _k |/ n
P _k ,
:

I _k = 2 ( α /2 ν ) ⋅ P _k ⋅ P _k /2 = ( α /2 ν ) ⋅ P _k ²

x _k , . , P _k , k , , :

x _k ⋅ | Δ _k | = Const.

, | Δ _k | = x _{k + 1} − x _k , :

x _{k + 1} − x _k = Const/ x _k .

x k ,

x _{k + 1} − x _k = x ( k + 1) − x ( k )

d x /d k ⋅ 1,

:

d x /d k = Const/ x <=> x d x = Const ⋅ d k .

x _k :

x _k = ₁ √( k + ₂ ).

_{1 2} , . , , 1, . , .

, x _k , pada dasarnya diasumsikan bahwa grafik kekuatan arus pada semua jalan raya harus dekat dengan pandangan segitiga, dan perjalanan itu sendiri harus dimulai terutama di luar segmen di mana mereka diarahkan. Persyaratan ini dapat dipenuhi dengan akurasi yang wajar jika kita secara resmi membagi segmen pertama menjadi dua bagian yang sama (parabola didekati oleh segitiga sama kaki dan sebagian besar perjalanan sepanjang jalan raya pertama memang diarahkan dari bagian selatan segmen nomor 1 ke bagian utara), tanpa menambah jumlah jalan ( gbr 43).


gbr. 43

x ₁ x _k . :

x ₂ = 2 x ₁

√( 2 + ₂ ) = 2 ⋅ √( 1 + ₂ ) =>

₂ = − 2/3.

, Q , x _{Q + 1} :

₁ √( Q + 1 − 2/3) = n + 1,

₁ ≈ ( n + 1)/√ Q .

:

x _k ≈ ( n + 1) ⋅ √( k − 2/3)/√ Q ,

| Δ _k | ≈ d x /d k = ( n + 1)/ 2√( k − 2/3) ⋅ √ Q

P _k = x _k ⋅ | Δ _k |/ n =

= ( n + 1) ²/ 2 n ⋅ Q ≈ n / 2 Q

I _k = ( α / 2 ν ) ⋅ P _k ² =

= ( α / 2 ν ) ⋅ ( n / 2 Q ) ² .

Karena semua jalan raya 2 Q menghasilkan kerugian dengan intensitas yang sama, nilai biaya pengalihan dalam keseluruhan jaringan adalah:

I = 2 Q ⋅ ( α / 2 ν ) ⋅ (n / 2 Q ) ² = ( α /2 ν ) ⋅ n ² / 2 Q .

, : Q Q ( 1/3 1/2 ). , , .

« »
Untuk kesederhanaan, kita akan puas dengan contoh kota di mana semua jalan satu arah. Dengan menggunakan analogi antara Kota Linear dan jalan-jalan individual Kota Seluler, kami membagi jalan raya di sepanjang yang terakhir menjadi bagian Q. Secara default, diyakini bahwa meninggalkan kuartal, Anda bisa mendapatkan jalan raya yang lewat di dekat itu. Pada saat yang sama, di antara semua jalan raya yang terletak di sepanjang satu jalan, ada belokan menuju seperempat khusus dengan salah satunya. Dalam proses menetapkan aturan, keseragaman dan kesederhanaannya sangat penting. Lihatlah Gambar 44:


gbr. 44

semua jalan memiliki pandangan yang sama dan aturan yang sama, jalan mana di blok akun mana yang membuka akses. Gambar 45 menunjukkan diagram belokan yang diizinkan di antara jalan raya. Melihat gambar ini sulit untuk tidak bingung. Hal yang sama sering dikatakan tentang skema metro di beberapa kota besar. Namun, dalam kedua kasus, semuanya menjadi jelas dan sederhana jika Anda tahu logika ide tersebut. Aturan logis dari belokan yang diizinkan terdengar cukup sederhana: jika mengemudi di sepanjang jalan raya, Anda melintasi jalan yang tegak lurus dengan gerakan Anda dan Anda dapat berubah menjadi seperempat yang terletak tepat di belakangnya, Anda dapat berbelok ke salah satu jalan ini.


gbr. 45

Topologi Skyscraper Lift kompatibel dengan lampu lalu lintas dan jalan layang. Sulit, tetapi dapat digeneralisasi ke jaringan yang tidak harus dari struktur seluler atau linier. Yang terakhir ini sangat penting untuk kota-kota bersejarah, di mana tidak mungkin bahwa itu akan tepat untuk menghancurkan setengah dari monumen bersejarah untuk meletakkan banyak jalan lurus kecil, tetapi di mana sudah ada jalan yang cukup besar yang dapat menampung beberapa dua atau tiga jalan raya.

Tentang masalah transportasi dan pekerjaan matematika

Sangat menyenangkan untuk menyelesaikan pekerjaan semi-tahunan yang melelahkan. Pekerjaan yang saya tulis, tentu saja, tidak menyelesaikan semua masalah dan kesulitan desain jalan - bisnis ini membutuhkan sejumlah besar orang yang sangat beragam. Namun demikian, hasilnya memberikan peluang untuk melihat kesalahan penting di kota-kota yang sudah dibangun dan memberikan metode bagaimana menghindari kesalahan tersebut di masa depan. Artikel ini tidak dimaksudkan sebagai buku referensi yang mencakup semua kasus yang mungkin dihadapi oleh seorang insinyur dalam praktiknya - saya menganggap tugas utama saya untuk memberikan sudut pandang baru, untuk mengembangkan cara baru untuk bernalar dan berbicara tentang suatu masalah, untuk memberikan minimum yang diperlukan contoh-contoh model sederhana yang disiapkan oleh pembaca. sudah bisa mengembangkan diri.

Menjadi sedih ketika Anda menyadari betapa banyak waktu yang hilang oleh warga kota dalam kemacetan hanya karena pada waktu yang tepat tidak ada ahli matematika yang bisa menghabiskan malam pada masalah yang sepenuhnya bisa dipecahkan. Berapa banyak dari masalah ini yang masih melingkupi kehidupan kita atau bersembunyi di profesi Anda? Apakah seseorang duduk di dekat Anda di tempat kerja yang alatnya memiliki pensil dan selembar kertas?

Saya harap semuanya berubah menjadi lebih baik.

Terima kasih atas perhatian dan semoga sukses!
Sergey Kovalenko.

2019
magnolia@bk.ru


(Foto: Vincent Laforet)