مدينة بلا اختناقات مرورية

الفصل 2.
( الرابط للفصل 1 )

فن تصميم شبكات الطرق

مشاكل النقل في المدينة من خلال عيون عالم الكمبيوتر

إذا كنت قد أوصيت بمقال بعنوان "فن تصميم شبكات الطرق" ، فسأطلب على الفور معرفة عدد شبكات الطرق التي تم إنشاؤها بمشاركة مؤلفها. يجب أن أعترف بأن نشاطي المهني كان بعيدًا عن بناء الطرق وكان مرتبطًا مؤخرًا بتصميم المعالجات الدقيقة حيث كنت من بين مسؤوليات أخرى منخرطة في استهلاك الموارد من تبديل البيانات. في ذلك الوقت ، كانت طاولتي تقف أمام النافذة البانورامية التي فتحت منظرًا جميلًا للجزء الطويل من الطريق السريع Volgograd وجزءًا من حلقة النقل الثالثة مع اختناقات مرورية لا نهاية لها من الصباح إلى المساء ، من الأفق إلى الأفق. في أحد الأيام ، تلقيت صدمة مفاجئة في الاعتراف: "قد تكون تعقيدات عملية تبديل البيانات التي أواجهها على شريحة مماثلة للصعوبات التي تواجهها السيارات أثناء تدفقها عبر متاهة شبكة الطرق".
من المحتمل أن هذه النظرة من الخارج وتطبيق الأساليب التي لم تكن تقليدية للمنطقة المعنية منحتني فرصة لفهم سبب الاختناقات المرورية وتقديم توصيات بشأن كيفية التغلب على المشكلة في الممارسة العملية.

فما هي حداثة النهج؟

تاريخيا ، يعتبر الغرض الرئيسي للطرق هو الفرصة التي توفرها للسفر لمسافات طويلة بسرعة (بين روما والمقاطعات). مثل هذا الحكم له ما يبرره عندما يتعلق الأمر بشبكة الطرق السريعة بين المدن على المستوى الفيدرالي: تبدو المدن التي يتصلون بها بمثابة نقاط صغيرة نادرة على الأطلس ، وتمر معظم السيارات التي تسير بين هذه المدن دون أن تتحول إلى أي مكان.

ومع ذلك ، بمجرد تسليم عدة صفحات وفتح خريطة مفصلة لمدينة كبيرة ، تتغير الصورة فورًا: يصل عدد العناوين التي يمكن أن تبدأ الرحلة أو تنتهي فيها إلى ما يقرب من عشرة آلاف ، وكلها منتشرة بكثافة للغاية صغيرة نسبيا في الحجم. في الوقت نفسه ، يمكن لمئات الآلاف من السيارات أن تتحرك في شوارع هذه المدينة في وقت واحد ، علاوة على ذلك ، فإن هدف كل منها ليس فقط ملء الطرق الفارغة بالفعل ، ولكن نقل شخص أو شحن من أشر مع عنوان محدد X إلى نقطة بعنوان محدد Y. كل هذا ، وهذا يعني أنه يجب تكييف نظام النقل الحضري لحل مشكلة المعالجة المتزامنة المتعددة بشكل فعال. وبالتالي ، فإن وظائف نظام النقل الحضري أصبحت مشابهة لشبكة الهاتف أو الكمبيوتر أكثر من شبكة الطرق بين المدن.

بالنظر إلى شبكة الطرق كدائرة تبديل لمطور الأجهزة أو مهندس في مجال تقنيات نقل المعلومات ، فهي طريقة طبيعية تمامًا للتحدث عن مشكلة ، ولكن بين الناس المشاركين في البحث حول مشاكل النقل ، فإن هذا الرأي ، على حد علمي ، الجديد.

إن نظرية تبديل الإشارات هي علم هندسي ضيق ، وهي وحدها ، بالطبع ، لا تكفي لتخطيط طريق منفصل أو تقاطع طريق أو التنبؤ بسلوك مسار حركة المرور على مقطع مستقيم ومعزول من الطريق السريع. لحسن الحظ ، فإن القضايا المذكورة أعلاه يتم بحثها جيدًا اليوم ، وقد تم بالفعل تطبيق الأساليب التي تم تطويرها لحلها. تسمح نظرية التبديل ، بدورها ، للمهندس المعماري بالتخفيف من المخاطر ، حيث تتعرض المدينة لحالة انهيار النقل على الرغم من أن جميع عناصر شبكة الطرق قد تم تنفيذها بشكل مثالي. يوجد هذا الخطر لأن إجراء معالجة متزامنة متعددة يمثل مهمة تستغرق وقتًا طويلاً في استخدام الموارد والوقت ، والمفتاح لحل فعال لا يتمثل في عرض الشوارع وراحة تبادل النقل ، ولكن في الاختيار المناسب الذي يكون التبديل فيه محددًا مخطط سيتم تنفيذ شبكة الطرق المقترحة.

من هذا البحث ، على سبيل المثال ، سوف تكتشف السبب في أن النوع "الشرياني" من شبكات النقل ، التي لا تزال تستخدم في المدن الحديثة ، "سيئ" ، ومع نمو السكان سيؤدي بالضرورة إلى اختناقات مرورية. تفسر النتيجة الأخرى المثيرة للاهتمام ، والتي تتفق جيدًا مع الملاحظات ، سببًا في أن من غير المحتمل أن يؤدي تحسين الطرق على نحو ما ، إذا حدث قبل كل الاختناقات المرورية بشكل حصري بالقرب من التقاطع ، إلى تحسين الموقف بطريقة ما حتى لو كان عدد السيارات في المدينة لا تزال هي نفسها.

عندما كتبت هذا المقال ، كان من الأهمية بمكان بالنسبة لي أن يكون مفهوما بالنسبة لمعظم المهندس المعماري العادي ، ويمكن أن يكون مفيدا من خلال عمله. حاولت تعريف القارئ بتبديل القضايا بلغة بسيطة ، ووضع معايير لتقييم مدى تعامل شبكة طرق معينة مع مهمة المعالجة المتزامنة ، وباستخدام أمثلة نموذجية أوضحت كيفية استخدام هذه المعرفة في الممارسة العملية.

هذه المقالة مخصصة لدائرة واسعة من القراء الذين لديهم دراية طفيفة بالدورة الجامعة في الرياضيات ، ونظرية الخوارزميات ، وهم على استعداد لتكريس 1 إلى 5 أيام لها.

فصل ودمج تدفقات السيارة

إنها ملاحظة واضحة للعديد من السائقين أن الصعوبات المرورية تنشأ بشكل رئيسي في تلك الأجزاء من الطريق حيث تُجبر السيارات لسبب ما على تغيير الممرات. ومن الأمثلة على ذلك شوكات الطرق والتضيقات والمناطق المتاخمة لمخارج الطرق السريعة وطرق الوصول وأقسام الطرق السريعة حيث يتم حظر بعض الممرات بحادث أو أعمال طرق.
في هذا القسم ، سيتم إجراء محاولة لتقديم وصف كمي للعمليات التي تحدث في مثل هذه الحالات ، وسنبدأ بفهم كيفية تبديل السيارات للممرات.

استراتيجيتان للتبديل إلى حارة المرور المجاورة
حركة المرور على طول الطريق السريع لها تباين طبيعي: شخص ما يفضل القيادة بشكل أسرع قليلاً ، شخص أبطأ قليلاً ، وبين بعض السيارات تنخفض المسافة وتصبح بالكاد مريحة للقيادة ، بينما بين السيارات الأخرى تزيد كثيرا مما يسمح للسيارات هناك من الممرات المجاورة. قد يكون ظهور مثل هذه الفجوات في تدفق الممر المجاور مباشرة على جانب برنامج التشغيل العشوائي متكررًا أو غير كبير. إذا كان هناك حاجة ، في الوقت الذي يحتاج فيه إلى إجراء مناورة ، فلا يمكن للسائق اللجوء إلى استراتيجيتين سلوكيتين على الأقل:

الاستراتيجية 1
قد توجد عدة فجوات مناسبة بالقرب من موقع السائق. إذا كانت الحركة كثيفة بدرجة كافية ، فمن غير المرجح أن يكون السائق قادرًا على إضافة السرعة وسد الفجوة اللازمة ، ولكن من خلال إبطاء قليلاً ، سيسمح السائق للجيران بالتغلب على السيارة بحيث تصبح مساوية للفجوة التي كان في الأصل وراء - لن يكون مشكلة كبيرة. تكاليف هذه الإستراتيجية واضحة: السائق نفسه والسيارات التي تسير في حارة سيارته تفقد بعض الوقت بسبب الحاجة إلى تقليل السرعة.

الاستراتيجية 2
من أجل الانتظار ، تحتاج إلى التحلي بالصبر والحصول على الوقت اللازم لذلك. قد يكون البديل محاولة لتنفيذ المناورة الضرورية "هنا" و "الآن". وفقًا لهذه الفكرة ، يعطي السائق إشارة إلى السيارات التي تقف خلفه في المسار الذي سيتحرك إليه. هؤلاء ، بدورهم ، استجابةً لإشارته ، يجب أن يتباطأوا قليلاً "وندع السيارات تتحرك أمامهم للمضي قدمًا" ، مما يخلق فجوة بالحجم الضروري في التدفق. يتم توزيع تكاليف الوقت في هذه الحالة بين سيارات الممر ، والتي ينتقل إليها السائق في النهاية.

في الحياة الواقعية ، يتم استخدام كلا الاستراتيجيتين في نفس الوقت: في البداية ، يتباطأ السائق وينتظر وجود فجوة كبيرة نسبيًا في مجرى الممر المجاور ، وبعد ذلك فقط ، يعطون إشارة إلى السيارات التي تتحرك فيه حول نيتهم ​​لجعل مناورة التبديل.

مما لا شك فيه ، أن طرق الوصول ومخارج الطرق السريعة والضيق ليست هي السبب الوحيد للتبديل بين الممرات ، الأمر الذي يستحق التذكر عند تصميم الطرق. تعد قدرة السيارات ذات السرعات العالية على تجاوز حركة المرور غير المستعجلة أمرًا ضروريًا لمنع الموقف على الطريق السريع عندما يتحلل إلى قائمة انتظار كبيرة يتم الزحف إليها بسرعة أبطأ جرار. ومع ذلك ، فإن مشكلة التعايش بين المركبات التي تسير على طريق بسرعات مختلفة لها طبيعة مختلفة قليلاً ويمكن فصلها عن القضايا محل الاهتمام ، لأن عملية التجاوز والتبديل بين الممرات لا يتم فرضها على السائق. إذا لم يتعجل السائق ، وفقًا لنظرية الاحتمالات ، فسوف يتم إعطاء فرصة ملائمة لأداء مناورة للسائق بشكل طبيعي ولهذا فهو لا يحتاج إلى الإخلال بحركة السائقين الآخرين.

تكلفة التبديل واحد
يمكن أن يكون سلوك السائقين في الواقع معقدًا للغاية ، ولكن من الأهمية بمكان بالنسبة لنا أن تظل النتيجة التي تم الحصول عليها في ظروف نموذجية معقولة: كل التبديل القسري بين الممرات يفرض عقوبة زمنية على المشاركين في حركة المرور.

دعونا الآن تقييم كيف يعتمد مقدار الوقت الضائع على كثافة حركة المرور على الطريق.

سننظر في الحركة على طول كل حارة كتيار منفصل. في محاولة للبقاء على مسافة مريحة من السيارات على نفس المسار ، يحجز السائقون امتدادًا للطول بطول مميز d في الجدول. دع السيارات تسقط في تيار لكل وحدة طول. نحن نتفق على وصف كثافة التدفق بأنها صغيرة ، أو القول إن that صغيرة إذا كان المنتج product × d أقل بكثير من 1.

في الوقت الذي يدرك فيه السائق الحاجة إلى الانتقال إلى الصف التالي ، فإن احتمال امتداد الطريق بطول d ، الذي كان سيشغله السائق ، لن يكون مجانيًا ، بصغر ρ ، سيكون متناسبًا تقريبًا مع ρ نفسها. إذا حدث الحدث الموصوف بالفعل ، فستجد مجموعتين تتنافسان على مكان ما تجربة كليًا ، نتيجة للمناورات ، بعض التأخير في متوسط ​​القيمة الثابتة δ .

على افتراض small صغير ، يمكننا أن نتجاهل احتمال أن تصرفاتهم في هذه اللحظة ستؤثر على حركة السيارات الأخرى. وبالتالي ، عندما تكون ρ صغيرة ، فإن ضياع الوقت من تبديل واحد سيكون α⋅ρ ، حيث يكون المعامل α هو كمية قابلة للقياس تجريبياً اعتمادًا على الثقافة والطقس وحدود السرعة (وما إلى ذلك) ، ولكن تظل ثابتة تقريبًا في هذا الوقت المحدد ولهذه المدينة ككل.

معدل شدة الخسارة على امتداد الطريق قبل الخروج
السيارات التي تتجه نحو المخرج ، قبل أن تصل إلى الطريق المنحدر (الرسم البياني 2) ، يجب أن تتحول ، في بعض الأحيان حتى عدة مرات ، إلى الصف المجاور على اليمين. كل هذه المناورة تزعج التدفق ، ونتيجة لذلك ، فإن متوسط ​​السرعة في القسم قبل الخروج أقل بشكل ملحوظ من أقسام "النقل" (المحرومة من المخارج والمداخل والشوك) من الطريق السريع.


الرسم البياني 2

لتمرير جزء من الطريق بسرعة أقل - يمثل للسائقين (ولركابهم) مقدارًا إضافيًا من الوقت الذي يقضونه في الرحلة. وبعبارة أخرى ، فإن منطقة الطريق السريع المتاخمة للخروج هي مولد ثابت لفقدان الوقت.

لنفترض أن متوسط ​​سرعة السيارة ν وكثافة التدفق ρ عند الحدود الأمامية لهذا الامتداد متماثلان في جميع الممرات.

علاوة على ذلك ، لنفترض أن الكثافة ρ ومعدل التدفق q المتجهين إلى المخرج (متوسط ​​عدد السيارات التي تسقط على المنحدر لكل وحدة زمنية) صغير في وقت واحد ، s هو عدد الممرات على الطريق السريع. للوصول إلى المخرج ، سيقوم السائق بإجراء مناورات من 1 إلى s . إذا كانت كثافة التدفق على الطريق المنحدر أقل بكثير من ρ ، فإن المناورة الأخيرة فقط ستكون للسائق من الناحية العملية "مجانًا" ، في حين أن الباقي سيتسبب في أي حال في خسائر α⋅ρ . في المتوسط ​​، سيكون عليك أداء (0 + 1 + 2 + ... + s - 1) / s = ( s - 1) / 2 مناورات "غالية".

بالنظر إلى الصعوبات التي تسببها جميع السيارات التي تتجه نحو الخروج ، يمكننا إنشاء صيغة لشدة ضياع الوقت:

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

القيمة p = ( sρν ) ليست أكثر من معدل التدفق لجميع السيارات التي تتحرك على طول الطريق السريع في الاتجاه المعني (متوسط ​​عدد السيارات التي تمر بمحطة الحافلات في كل وحدة زمنية). الملاحظة الأخيرة تعطينا الفرصة لإعادة كتابة الصيغة بالنسبة لي بشكل أكثر تناسقًا:

أنا _خارج = ( α / 2 ν ) ⋅ pq ⋅ (1 - 1 / s )

معدل شدة الخسارة في القسم المجاور لطريق الوصول
إن الموقف الناشئ على الطريق السريع خلف القسم حيث يتصل طريق الوصول به يكرر إلى حد كبير الموقف في القسم قبل الخروج ، على الرغم من وجود بعض الاختلافات. اسمح بتدفق صغير للسيارات ذات القوة q عبر المنحدر الجانبي في حركة المرور الرئيسية للطريق السريع (الرسم البياني 3).


الرسم البياني 3

طول الطريق المنحدر محدود ، لذلك يجب تبديل جميع السيارات القادمة حديثًا إلى ممر الحافة اليمنى للطريق السريع. ونتيجة لذلك ، تكون كثافة حركة المرور في الحافة اليمنى 1 أعلى محليًا من المتوسط ​​على الطريق ، ولهذا السبب يقرر بعض السائقين فيها الانتقال إلى حارة مجاورة أقل ازدحامًا على اليسار ، مما يؤدي بدوره إلى زيادة في الكثافة بالفعل على الخط الثاني. ستستمر عملية التبديل بين الممرات حتى يتم تسوية كثافة التدفق عبر عرض الطريق السريع بأكمله. على افتراض أن متوسط ​​السرعة ν سيكون هو نفسه بالنسبة لجميع الممرات n ، يمكننا أن نتوقع ، عند الانتهاء من عمليات التبديل ، أن تزيد قوة التدفق في كل منهما بمقدار (1 / s ) exactly بالضبط.

لمعرفة مقدار تكلفة التبديل بين السائقين ، نقوم أولاً بحساب قوة جميع تدفقات التبديل. التدفق من الطريق المنحدر إلى المسار الأول للطريق السريع الذي نعرفه بالفعل: إنه يساوي q . من أجل مساواة الزيادة في قدرة الممر الأول بـ (1 / s ) ⋅ q ، يجب أن يكون التدفق من الممر الأول إلى الثاني (1 - 1 / s )، q ، من الثاني إلى الثالث = ( 1 - 2 / s )، q ، من k- th إلى ( k + 1) th = (1 - k / s ) ⋅ q . وفقًا للصيغة الأخيرة ، ستكون سعة تدفق التحويل إلى ممر الحافة اليسرى (1 - ( s - 1) / s ) ⋅ q = (1 / s ) ⋅ q ، وفقًا للأمر السليم.

نظرًا لأننا نعرف الفترة الزمنية للتحول الفردي وقوة جميع تدفقات التحويل ، يمكننا الآن حساب الكثافة الإجمالية للخسائر الناتجة عن ذلك:

I _in = α ρ ⋅ 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 ).

تذكر مرة أخرى أن sρν هي قوة تدفق جميع السيارات على طول الطريق السريع ، نحصل على صيغة التكلفة في شكلها النهائي:

أنا _في = ( α / 2 ν ) ⋅ pq ⋅ (1 + 1 / s ).

معدل شدة الخسارة على مفترق متماثل
في الفقرات السابقة ، وجدنا خسائر من تفاعل التدفقات ، إحداهما كانت كبيرة بالضرورة ، والآخر صغير بالضرورة. لإثبات وجود نهج لحل المشكلات عندما تكون قدرات كلا التدفقات قابلة للمقارنة في القوة ، دعونا نأخذ بعين الاعتبار تطرفًا آخر: شوكة حيث يكون كلا الاتجاهين الفرعيين شائعين على حد سواء للسائقين (الرسم البياني 4).


الرسم البياني 4

للراحة ، سيتم تسمية السيارات التي تذهب إلى اليمين على مفترق الطرق "زرقاء" ، والسيارات التي تترك إلى اليسار - "حمراء". في البداية ، تتحرك السيارات من "الألوان" مختلطة ، ومشتتة بين جميع الممرات في الطريق السريع. مع اقترابها من الشوكة ، تبدأ السيارات الحمراء في الانحدار ببطء نحو الممرات اليسرى ، والسيارات الزرقاء باتجاه اليمين: هناك تحويلات في الاتجاهين بين الممرين المجاورين. على عكس مثال طريق الوصول ، لم تعد هذه التدفقات "صغيرة نسبيًا". بالمناسبة ، يوجد فقط بين الممرين المركزيين تبادل قسري لحركة المرور ، تكون شدته في أي من الاتجاهات (من اليسار إلى اليمين ، أو من اليمين إلى اليسار) مساوية لربع القوة الكلية تيار يتحرك على طول الطريق السريع. لحسن الحظ ، في هذه الحالة هناك طريقة جيدة بما يكفي لتقدير التكاليف الناتجة.
في البداية ، يمكننا أن نلاحظ أن عملية تقسيم السيارات إلى "أحمر" و "أزرق" على الأرجح تبدأ قبل فترة طويلة من مفترق الطرق وتتقدم ببطء ، وبالتالي ، فمن ناحية ، يجب أن يكون لها تأثير ضئيل على كثافة حركة المرور في صف منفصل من ناحية أخرى ، اجعل تيارات التبديل ممتدة على مسافات طويلة ، مما يتيح الفرصة لتمثيل كلٍ منها على هيئة مزيج من عدد كبير من تدفقات الطاقة المنخفضة (الرسم البياني 5).



الرسم البياني 5

منذ الآن نحن نتحدث عن التدفقات الصغيرة ، وإن كان ذلك بأعداد أكبر ، فلا شيء يمنعنا من تقليل المشكلة المعنية إلى تلك التي تم حلها بالفعل. يمكننا تقسيم الطريق السريع عقلياً في الوسط إلى جزأين متساويين ، ومن ثم توصيلهما مع عدد أكبر من طرق الطائر أحادية المسار ، مما يسمح للسيارات الحمراء بالوصول إلى السيارات اليسرى والزرقاء إلى اليمين (الرسم البياني 6). نظرًا للتماثل الواضح ، عند حساب الخسائر الناتجة ، يمكننا التركيز على السيارة من أي لون ، على سبيل المثال ، الأزرق ، وفي النهاية ضعفي النتيجة.


الرسم البياني 6

اجعل السرعة والكثافة متساوية في جميع الممرات وتبقى ثابتة على امتداد المنطقة بالكامل حيث يتم فصل السيارات عن طريق الألوان. في هذه الحالة ، ستكون قوة التدفق لجميع السيارات التي تتحرك على طول الطريق السريع هي:

ع = 2 sρv .

دع q ₁ ، q ₂ ، ... q _m تدل على تدفقات السيارات الزرقاء التي تتحرك على طول الطرق السريعة الوهمية إلى النصف الأيمن من الطريق السريع. لنفترض أنه قبل وقت قصير من قسم الفصل في كل حارة من الطريق السريع ، يتم تمثيل كل من الألوان بنسب متساوية من 50 ٪ ، مما يعني أنه في المجموع
q ₁ + q ₂ + ... + q _m تساوي sρv / 2 ، أو بمعنى آخر ، p / 4.

الخسائر الناتجة عن التدفق q _i بسبب صغر حجمه ، يمكننا حساب المعادلة التالية:

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

تلخيص الصيغة الأخيرة على جميع i ، نجد الخسائر الناتجة عن السيارات الزرقاء فقط:

I _blue = ( α / 2 ν ) ⋅ p ⋅ ( q ₁ + q ₂ + ... + q _m ) = ( α / 2 ν ) p 2/4.

إجمالي الخسائر ، كما ذكرنا سابقًا ، سيكون ضعف ما يصل إلى:

أنا _div = ( α / 2 ν ) ص 2/2 .

تحليل الصيغ التي تم الحصول عليها
إذا قمنا بتقسيم الكثافة I ، وهذا هو مقدار الوقت الذي يضيعه المشاركون تمامًا في الثانية ، والتدفق الجانبي q ، والذي بحكم التعريف يساوي عدد السيارات التي تربط أو تغادر الطريق السريع في ثانية واحدة ، فسنحصل على متوسط ​​الخسائر الناجمة عن إحدى هذه السيارات:

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

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

ولعل أهم شيء في هذه الصيغ هو التناسب المباشر بين تدفق الطاقة للسيارات على الطريق السريع ع وتكاليف الوحدة i . يبدو كل شيء وكأن سيارة تسعى للانضمام ، أو العكس - لترك التدفق الرئيسي ، مما يسبب اضطرابًا مستمرًا لكل سائق قريب.

الملاحظة الثانية ، المثيرة للاهتمام وغير المتوقعة للغاية تتعلق بالتأثير الضعيف للغاية على شدة الخسائر الناتجة في عدد الممرات بالقرب من الطريق السريع بجوار التقاطع مباشرة. كما ترون ، عند النظر إلى صيغة I _out ، يكون المخرج عمومًا هو الأكثر فعالية من حيث الوقت لطريق وحيد الخط ( s = 1 ، i _out = 0) ، والصعوبات الناجمة عن طريق الوصول المجاور لـ ثلاثة حارات وستة حارات الطريق السريع تختلف فقط

100 ٪ ⋅ [(1 + 1/3) - (1 + 1/6)] / (1 + 1/3) = 12.5 ٪.

إذا اعتبرنا أن كل سيارة قد انضمت من أي وقت مضى إلى حركة المرور على الطريق السريع سيضطر في النهاية إلى تركها ، عندها يبدو من المشروع استخدام قيمة موحدة بدلاً من _{الدخول والخروج} عند حساب خسائر التبادل

i _av = ( i _in + i _in ) / 2 = ( α / 2 ν ) ⋅ p .

على الرغم من أن صيغة i _av لا تعتمد بشكل صريح على عدد الممرات ، يجب أن نتذكر أن إنشاءها (انظر افتراضات I وأنا _خارج ) يعتمد بشكل كبير على افتراض انخفاض كثافة السيارات على الطريق ، لذلك من غير المرجح أن تعطي نتائج مرضية عند تطبيقها على الطريق السريع الضيق للغاية مع الكثير من الحركة.

النتائج الأولية
في المناطق القريبة من الوصلات ، تحدث العوائق المرورية حتماً ، حيث تستغرق وقتًا بعيدًا عن السائقين ، وتقلل من متوسط ​​السرعة ، ويؤدي هذا الأخير إلى زيادة في كثافة السيارات ، ونتيجة لذلك ، من المحتمل حدوث اختناقات مرورية. سيتم استدعاء الخسائر الزمنية المرتبطة بالفصل ودمج تدفقات السيارات تبديل الخسائر.

توجد خسائر من نوع مشابه بطريقة أو بأخرى في أي نظام تبديل: سواء أكان ذلك عبر الهاتف أو شبكة الكمبيوتر أو المعالج الدقيق متعدد النوى أو خدمة تسليم البريد.

عندما ينضم السائق ، أو ، على العكس ، يترك حركة المرور على الطريق السريع ، فإن تكاليف التبديل التي تتكبدها أفعاله تتناسب مع قوة تدفق السيارات التي لوحظت في ذلك الوقت على الطريق السريع.

لتقليل خسائر التحويل في جميع أنحاء المدينة ، من الضروري التفكير بعناية في شبكة الطرق المنفذة فيها في مرحلة التصميم. بعد قليل سنحلل هذه المهمة بالتفصيل ، ولكن يمكن إدراج بعض التوصيات الواضحة الآن:

1. تتناسب خسائر التبديل مع قوة التدفق على الطريق السريع - ليس من الضروري توسيع الطرق دون الحاجة ، طريقان صغيرتان صغيرتان يساوي ضعف واحد كبير ؛
2. تتناسب خسائر التحويل مع قوة التدفقات الجانبية - الأمر يستحق تصميم الشبكة بحيث يتوجب على السائق أن يتحول أقل عدد ممكن من المرات خلال رحلته ؛
3. يجب أن يكون الاضطراب المتبادل الناجم عن سائقي التدفقات الرئيسية والجانبية أقل على نطاق المدينة إذا حاولنا منع دمج الطرق التي تتداخل فقط في مقطع قصير من الطريق.

الشروط الاقتصادية لوجود المدن.
نموذج مدينة مع "وصول عشوائي" ²

(الملاحظة 2: المصطلح مأخوذ من مفهوم ذاكرة الوصول العشوائي (RAM) ويعني عشوائي الاحتمال وحتى باستهلاك الوقت).
ربما تتمثل المرحلة الأولى من أي مشروع لتصميم (أو إعادة تصميم) نظام النقل في المدينة في محاولة تحديد نوع التحول الذي تحتاجه المدينة الآن وكيف ستتغير احتياجاتها في المستقبل.

يمكن إجراء مثل هذا التحليل إذا قمنا أولاً بتقسيم المدينة إلى مناطق ليست كبيرة جدًا ، ولكن ليست مناطق صغيرة جدًا ، ثم يشير كل زوج من هذه المناطق إلى العدد التقريبي من الرحلات إلى جانب واحد أو الآخر التي يحتاجها سكانها في وقت واحد أو آخر من اليوم. عن طريق وضع التنبؤات التي تم إجراؤها في مصفوفة ، ستتلقى بذلك مصفوفة احتياجات الهجرة لسكان المدينة.

بالضبط بالنسبة لهذه المصفوفة ، يجب علينا البحث في شبكة تسمح للسائقين والركاب بقضاء أقل وقت ممكن في رحلة منفصلة ، تتطلب من سلطات المدينة أقل موارد ممكنة لتحقيق الشبكة.

عندما يتعلق الأمر بالمدن الحالية ، من المهم هنا عدم ارتكاب خطأ وعدم استبدال عدد الرحلات التي يحتاجها الناس فعليًا بعدد الرحلات التي تم إنشاؤها تاريخيًا تحت تأثير بعض العقبات أو الصعوبات في وقت أعمال التصميم. ربما ، يمكن لشبكة النقل في برلين "قبل" و "بعد" سقوط الجدار الفاصل أن تكون المثال الأكثر وضوحًا لما قيل.

سيتعامل هذا القسم بشكل أساسي مع القضايا الإنسانية التي لست متخصصًا فيها ، لكنني أعتقد أن مناقشتها كهاوي هو أكثر صحة من مجرد تجنب المشكلة.

من أجل تمثيل احتياجات الهجرة للسكان بشكل أفضل ، يجدر البدء بالسؤال الأساسي: "ما هي المدن وما وظيفتها المفيدة؟"

دعونا نحاول الإجابة عليه ليس كمقيمين عاديين للمدن (والقرى) ، ولكن من منظور الشخص المسؤول عن عملية التحضر في بعض الدول الكبيرة والمتقدمة. من وجهة النظر هذه ، لم يعد من المهم ما هي الدوافع التاريخية التي صنعها الكثير من الناس بعد أن احتشدوا في قطعة صغيرة من الأرض ، أو الأسباب التي تجعلهم يواصلون القيام بذلك الآن ، من الأهمية بمكان - ما هو التأثير الاقتصادي الذي تحدثه المدن من حجم واحد أو آخر وبأي آليات يتحقق هذا التأثير.

في رأيي ، السبب الرئيسي لوجود المدن الكبيرة هو ، من ناحية ، الفرصة لشركات التكنولوجيا للعثور على موظفين في مهن نادرة ، ومن ناحية أخرى ، فرصة للأشخاص الذين أتقنوا مهن نادرة لبيع أعمالهم خدمات للشركات المهتمة بها بشروط تنافسية. في مدينة صغيرة (غير متخصصة) ، يكون إنتاج العديد من السلع والخدمات مستحيلًا بكل بساطة ، أو يضع شركات التكنولوجيا وموظفيها في موقع الرهائن المتبادلين ، دون إعطاء أحدهما أو الآخر أي بدائل.

على سبيل المثال ، خذ مهنة غير نادرة لمعلم الأدب المدرسي. وفقًا للإحصاءات ، تبلغ الحاجة إليهم مدرسًا واحدًا تقريبًا لكل 1000 شخص. في المدرسة العادية ، يقوم 3-4 مدرسين بتدريس الأدب. يمكن أن يسمى اختيار وظيفة لمدرسة أدبية تنافسية إذا كان هناك على الأقل 4-5 مدارس ثانوية في المدينة ، والتي ، من حيث عدد السكان ، تقابل حوالي 15 ألف شخص.

على ما يبدو ، يشعر الأشخاص ذوو التخصص الهندسي بالراحة في سوق العمل في المدن التي يبلغ عدد سكانها 100 ألف على الأقل. بالطبع ، هناك أيضًا مثل هذه المهن ، التي يظهر الطلب عليها فقط في المدن التي يزيد عدد سكانها عن مليون شخص ، ولكن وجود العديد من ملايين المدن لا يكون له أي معنى اقتصادي.

بعد كل ما ذكر أعلاه ، تبدو فرضيتان منطقيتان تمامًا (لا تؤثر صحته ، مع ذلك ، على حقيقة المحتويات الرئيسية للمقال):

1. يحتاج الشخص العادي إلى السفر بشكل متكرر عبر مسافات تستحوذ على 4-5 من الوظائف الواعدة له ؛
2. بالنسبة لجزء كبير من السكان الذين يمثلون المهن النادرة والأكثر قيمة من الناحية الاقتصادية ، قد تكون المسافة بين أكثر الرحلات تكرارًا مقارنة بنصف قطر مدينتهم.

كتجسيد محسّن للفرضيتين 1 و 2 ، سأستخدم غالبًا نموذجي للمدينة مع إمكانية الوصول العشوائي ، على افتراض مني ، على افتراض أن قوة تدفقات السفر المطلوبة هي نفسها بين أي ربعين منها ، أو ، وبعبارة أخرى ، في جميع خلايا الهجرة يحتاج مصفوفة هناك نفس العدد الموجب. إذا نظرت بشكل عشوائي إلى سجلات الرحلات التي تمت في مثل هذه المدينة خلال اليوم ، فبالنسبة للرحلة المميزة التالية ، سيكون لدى جميع الجهات نفس الاحتمال في أن تكون سواء كانت البداية أو النهاية لهذه الرحلة ، وليس هناك علاقة بين موقع يجب مراعاة الربعين "الأولي" و "النهائي".

شبكات الطرق مع أبسط طوبولوجيا

دعونا نحاول تطبيق الأفكار الموضحة في الفقرات السابقة على بعض أنواع خطط المدن المأخوذة من الحياة.

مدينة خطية

نشأت أول مستوطنات كبيرة في الغالب على طول الساحل ، في مناطق من قطاع رقيق من الأرض بين البحر والمنحدرات ، أو على طول طرق الطرق المزدحمة ، لذلك في عملية النمو اكتسبوا حدودًا ممدودة ضيقة. لقد نجت العديد من هذه المستوطنات حتى أيامنا هذه ، حيث حافظت على شكلها المطول وتحولت إلى مدن حديثة (يرجى الرجوع إلى الرسم التوضيحي أدناه).


(منطقة مستبعدة من ريو دي جانيرو ، المؤلف غير معروف)

غالبًا ما يوجد في مثل هذه المدينة طريق واحد واسع يتم بناؤه حوله. لنفترض أن كل ربع (منطقة التقسيم الإقليمي) يولد سلسلة من الرحلات باستخدام القوة 1 ، وعدد كل هذه الأعداد يساوي n ، وأن المدينة نفسها تتبع نموذج الهجرة "الوصول العشوائي".


الرسم البياني 7

دعونا نحاول إيجاد المعلمات المذكورة أعلاه كيف يتغير متوسط ​​وقت السفر ومنطقة الطريق المطلوبة مع زيادة n .

لذلك ، اسمح لجميع الفصول بنفس الشكل والحجم ، ويتضاعف عددهم بمقدار λ (lambda). من الواضح ذلك

• يزداد طول الطريق الرئيسي بعامل λ .

نظرًا للنموذج المقبول "الوصول العشوائي" ، ستنتهي 50٪ من الرحلات التي بدأت في النصف الأيمن من المدينة في النصف الأيسر (العكس سيكون صحيحًا أيضًا) ، وبالتالي ، مع زيادة في عدد الفصول بعامل λ ، سوف تتضاعف أيضًا قوة التدفق الذي يمر عبر وسط المدينة بمرور الوقت. ستكون مناقشات مماثلة مع الاستدلال نفسه صحيحة ، بدلاً من الوسط ، نأخذ أي نقطة تقسم المدينة بنسبة معينة (1: 3 ، 2: 5) ، مما يعني أن

• تزداد قوة التدفق على طول الطريق الرئيسي بعامل λ ؛
• يتضاعف عدد ممرات الطريق الرئيسية المطلوبة في كل قسم بمرات .

أكثر أو أقل وضوحا أن متوسط ​​طول الرحلة ، ومعها

• يزيد وقت السفر الصافي الذي تم إنفاقه لتغطية المسافة بعامل λ .

كل ما تبقى للحساب هو عدد مرات زيادة الوقت الضائع بسبب تكاليف التحويل في رحلة واحدة. يدخل التدفق الجانبي مع القدرة 1 إلى كل فصل ويخرج منه ، مما يولد معًا ضياعًا للوقت بكثافة:

أنا = أنا _في + أنا _خارج = ( α / 2 ν ) p ⋅ 2 ،

حيث p هي قوة التدفق على الطريق الرئيسي. نحن نعلم بالفعل أن عدد الأرباع وقدرة التدفق على الطريق الرئيسي يزيد بعامل λ ، وبالتالي ، فإن إجمالي الوقت الضائع الناتج عن الشبكة يتضاعف بمقدار times ² مرات. من ناحية أخرى ، يزداد عدد الرحلات التي يتم إنشاؤها بواسطة الشبكة ، والتي يتم تخصيص كل هذه الخسائر لها ، بمعامل λ ، ولهذا السبب

• يزيد صافي وقت السفر الناتج عن تبديل التكاليف بعامل of.

دعنا نعرض كل النتائج في جدول واحد:

طوبولوجيا خطية
عدد نقاط العناوين (الأحياء) مع القوة 1 ........................ ن
إجمالي مساحة الطريق ............................................... ....................................... ( ن ² )
صافي وقت السفر ،
قضى لتغطية المسافة ............................................. ...................... ( ن )
صافي وقت السفر ،
ضائع بسبب تكاليف التحويل ............................................. ........................ يا ( ن )
عدد العقد التبديل .............................................. ..................... يا ( ن )
عدد نقاط التبديل ، بالنظر إلى قوة التدفقات الجانبية ............. O ( n )

الترميز المستخدم ' y = O ( x )' يعني أن المعلمتين x و y تعتمدان وظيفيًا ، وعندما تنمو x بلا حدود ، تميل النسبة x / y إلى رقم محدد ، يختلف عن الصفر ، العدد.

مدينة الخلوية

تتمثل الطريقة الثانية الشائعة للتخطيط في ترتيب الأرباع على شكل مصفوفة مستطيلة الشكل ، على غرار طريقة وضع الأجزاء المجزأة في لوح الشوكولاتة.

نحن نوافق على تسمية هذه المدن "الخلوية".


(لوس أنجلوس ، الصورة: سلافا ستيبانوف)

يُظهر الرسم البياني 8 نموذجًا لمدينة خلوية تتكون من أرباع n (مع مراعاة النصفين) ، مكونًا مربعًا منتظمًا. يتم فصل الأحياء عن بعضها البعض من خلال ما مجموعه √ ن الطرق ، وتمتد بشروط من الغرب إلى الشرق ، والطرق التي تمتد من الجنوب إلى الشمال. في الإجمال ، تشكل هذه الطرق معابر √ n × √ n ، يمكن تنفيذ كل منها إما كتقاطع لإشارات المرور أو عبر جسور / جسور على الطرق.


الرسم البياني 8

بغض النظر عما إذا كانت هناك حركة مرور في اتجاه واحد أو في اتجاهين ، يمكن تحقيق أي رحلة من النقطة A إلى النقطة B في مدينة خلوية على طول طريق لا يزيد عن شارعين ولا يوجد أكثر من منعطف عند تقاطع.

بافتراض أنه ، كما في المثال السابق ، يولد كل ربع سلسلة من الرحلات باستخدام الطاقة 1 ، وأن احتياجات الهجرة للسكان تتبع نموذج "الوصول العشوائي" ، يمكننا حساب ، الآن بالنسبة لمدينة خلوية ، القوانين التي بموجبها average travel time and the resource intensity of road network construction will change with increasing quantity of quarters.

إذا زاد عدد الأرباع بعامل λ ، عندئذ:

• تتضاعف مساحة المدينة بمقدار λ مرة ، وأبعادها الخطية مع الحفاظ على النسب - بواسطة √ λ ،
• متوسط ​​مسافة السفر والوقت الصافي لتغطيتها ، بما يتناسب مع الأبعاد الخطية ، مضروبة في λ λ مرات ،
• يتضاعف عدد الشوارع وعدد الأحياء المجاورة لشارع معين مرات λ λ ،
• قوة تدفق حركة المرور ، التي تتناسب مع عدد الفصول التي يكون فيها التدفق "على اتصال" (سيتم تقديم شرح لهذا المصطلح لاحقًا) ، ويتضاعف مرات، λ ،
• the required area of ​​all roads grows as (number of streets) × (length of one street) × (power of street flow) = √ λ ⋅ √ λ ⋅ √ λ = λ √ λ

تنقسم التدفقات الجانبية إلى تلك التي تنطلق من أو باتجاه الجهات وتلك التي تتحول من شارع إلى آخر عند التقاطعات. قوة التدفقات الأولى ، وفقا للظروف ، تظل دائما مساوية للوحدة. من خلال الحركة الثانية ، تتحرك حركة المرور تقريبًا أو تأتي أو تخرج من الطريق السريع ، إذا أخذنا في الاعتبار أن هناك أرباعًا في المدينة أكثر بكثير من الأحياء في شارع معين. نتيجة لذلك ، يمكن تقدير التغير في قوة التدفقات الثانية من خلال الصيغة (التغير في قوة التدفق) / ((زيادة عدد التقاطعات في شارع معين) = √ λ / √ λ= 1. تشير المساواة في النسبة الأخيرة إلى الثابت إلى أن هذه التدفقات لا تتغير بشكل ملحوظ مع زيادة عدد الفصول ، وبالتالي فإن الزيادة في تكاليف التبديل الناتجة عن الشبكة ككل ستكون: (الزيادة في المجموع عدد الفصول + التقاطعات) × (التغير في قيمة التدفق في شارع واحد) = λ √ λ . نظرًا لأن قوة تدفق الترحيل المتولدة من جميع الجهات زادت بعامل λ ، إذن

• يزيد صافي وقت السفر الناتج عن زيادة تكاليف التحويل بعامل √ λ

دعنا نعرض كل النتائج في جدول واحد:

طوبولوجيا الخلوية

عدد نقاط العناوين (الأحياء) مع القوة 1 ..................... ن
إجمالي مساحة الطريق ............................................... .................................... O ( n √ n )
صافي وقت السفر ،
قضى لتغطية المسافة ............................................. ................... يا (√ ن )
صافي وقت السفر ،
ضائع بسبب تكاليف التحويل ............................................. .................... يا (√ ن )
عدد العقد التبديل .............................................. .................. يا ( ن )
عدد نقاط التبديل ، بالنظر إلى قوة التدفقات الجانبية .......... O ( n )

مقارنة بين الشبكات الخطية والخلوية مع بعضها البعض ، من الصعب ألا نلاحظ أن الزيادة في كثافة الموارد اللازمة للبناء والوقت الذي تقضيه في رحلة واحدة ، مع نمو المدينة ، أسرع بكثير للشبكة الأولى من والثاني. على سبيل المثال ، تتطلب المدينة الخلوية التي تتكون من 100 ربع إسفلت أقل بعشرة أضعاف ، ويتطلب السفر خلالها متوسط ​​10 مرات أقل مقارنة مع مدينة خطية من نفس الحجم. لذلك ، فمن المنطقي استخدام شبكات الطرق ذات الهيكلية الخطية فقط في المدن الصغيرة جدًا.

إذا نسينا لفترة من الوقت وجود تكاليف التحويل ، فيمكن اعتبار الطوبولوجيا الخلوية وسيلة مثالية لتصميم شبكات الطرق ، حيث إنها تعطي تقدير O مثليًا تقريبيًا لكل من متوسط ​​طول الرحلة ومنطقة الطريق المطلوبة. في الواقع ، بالنسبة لأي موقع "مضغوط" أكثر أو أقل من المدينة (مع إمكانية الوصول العشوائي) ، فإن طول الرحلة لن ينمو أبطأ من الجذر التربيعي لمنطقة المدينة ، والذي بدوره يتناسب عادةً بشكل مباشر مع السكان . نتيجة لذلك ، نحصل على كل نفس O () n ).

حقيقة أن الطريق النموذجي في مدينة خلوية يمتد على طول "زاوية" بدلاً من خط مستقيم ، من حيث المبدأ ، ينطوي على فرصة للبحث عن أفضل الطرق لتخطيط المدن ، ولكن التوفير بمبلغ 20 ٪ (هذا هو الحد الأقصى الذي يمكننا الفوز به إذا تعلمت السيارات السفر عبر الجدران) من غير المرجح أن تجبر المهندسين المعماريين في يوم من الأيام على التخلي عن الترتيب المستطيل للشوارع والطرق.

يمكن الحصول على الحد الأدنى الممكن لتكاليف بناء الشبكة (والمحافظة عليها) من خلال تذكر أن كل سيارة تحتفظ بجزء من الممر لحركتها. نتيجة لذلك ، تتناسب المساحة الإجمالية للطرق مع ناتج متوسط ​​وقت السفر (متوسط ​​طول الرحلة) وعدد السيارات في المدينة: O (√ n ) × O ( n ) = O ( n √ n ) (مقارنة مع الجدول لمدينة الخلوية).

إذا تحدثنا عن مقدار الوقت الضائع في السفر بسبب تكاليف التبديل ، فلا عجب إذن أن علاقتها مع مقدار الوقت لتغطية المسافة لا تعتمد على عدد الأحياء في المدينة الخلوية أو الخطية (O (( n ) / O (√ n ) = O (1) ، O ( n ) / O ( n ) = O (1)). بمعنى آخر ، فإن نسبة الوقت الضائع في السفر بسبب التبديل ، في كل من المدن الكبيرة والصغيرة ، ستكون هي نفسها. من هذا المنطلق يمكننا أن نستنتج أنه إذا لم تكن هناك مشاكل خطيرة في تبديل التكاليف في مدينة صغيرة (يمكن أن نقترح أنها ربحت إلى 10-20 ٪) ، ثم في مدينة كبيرة لا يزال ينبغي عدم ملاحظتها ، وإذا كانت كذلك ، ثم سيبقون في الوجود ، بغض النظر عن كيفية نمو المدينة وتوسيعها.

نظرًا لأننا لا نعرف أيًا من البدائل صحيح (أو بالأحرى ، نحن نعلم أن مشاكل حركة المرور في المدن الكبيرة موجودة) ، فمن الجدير محاولة تحسين طوبولوجيا مدينة خلوية حتى تنخفض تكاليف التحويل فيها على الأقل بعامل بعض الأوقات الثابتة.

أمثلة مفيدة للشبكات غير الواقعية

دعونا نختبر ما إذا كانت الطوبولوجيا الخلوية تتبع التوصيات التي قمنا بتطويرها من خلال تحليل تبديل التدفقات على الطريق السريع.

1) لا تقم بتكبير الطرق دون الحاجة.
- نعم. يتم توزيع حركة المرور على العديد من الطرق (مقارنة مع مدينة خطية).

2) تجنب تصميم الشبكة حيث يتعين على السائق تحويل عدد كبير من المرات في رحلة واحدة.
- نعم. من المرجح أن يتم تنفيذ أي رحلة على طول طريق لا يتطلب سوى منعطف واحد في الشوارع.

3) حاول منع دمج الطرق التي تتداخل فقط في مقطع قصير من الطريق.
- هنا ، ربما ، هناك شيء للعمل عليه. على الرغم من الحد الأدنى لعدد المنعطفات في الرحلة الواحدة ، يمر المسار كجزء من تدفق الطريق السريع الرئيسي عبر عدد كبير من نقاط التبديل (O ( n )) ، حيث يتم إهدار وقت ثمين.

تحفز الملاحظة الأخيرة على التحقق من السؤال التالي: "ما هو الحد الأدنى لمتوسط ​​عدد نقاط التبديل التي يجب أن تمر خلالها الرحلة عبر شبكة طرق تربط n أرباع؟"

بطبيعة الحال ، تكون مهمة البحث عن مثل هذه الشبكة منطقية فقط بشرط أن يكون عدد التدفقات مجتمعة أو مقسمة بأي عقدة تبديل محددًا مسبقًا من أعلاه بقيمة ثابتة معينة. خلاف ذلك ، يمكنك دائمًا تقديم شبكة طرق تحتوي على نقاط عنوان n وتقاطع ضخم واحد.


(المؤلف غير معروف)

من الأسهل بكثير استكشاف المشكلة الحقيقية إذا كان من الممكن في السابق الكشف عن جزء على الأقل من الأنماط باستخدام بعض النماذج البسيطة ، حتى وإن لم تكن على الإطلاق ، نماذج واقعية. باتباع هذا المنطق ، سوف ننسى مؤقتًا القيود الهندسية لبناء الطرق وحاجة المسافرين إلى تغطية المسافات ، مع تركيز كل اهتمامنا على كيفية حل الشبكات المجردة لمشكلة المعالجة الموازية. فيما يتعلق بالعقد التبديل ، سنفترض الآن أن كل منهما إما يقسم التدفق إلى جزأين (عقدة القسمة) ، أو يجمع بين اثنين من التدفقات إلى واحد.


الرسم البياني 9

شجرة العنوان
دع هناك نقطة بداية واحدة ، حيث تبدأ جميع الرحلات ، دون استثناء ، ونقاط عنوان النهاية n الأخرى التي تنتهي عندها باحتمال متساوٍ (الرسم البياني 9).

يجب بناء شبكة نقل تتيح للسائق المرور عبر أقل عدد ممكن من نقاط التبديل.

الحل الواضح (للمبرمجين) ، الذي يوحي نفسه هنا ، هو استخدام شجرة ثنائية متوازنة ، وفي نفس الوقت نحتاج إلى وضع نقطة بداية واحدة في أعلى الشجرة ، ووضع نقاط النهاية المتبقية n واحدة في كل من أوراقها (الرسم البياني 10). ستتم تسمية الشبكة التي تم إنشاؤها بالطريقة الموصوفة باسم شجرة العنوان المباشرة.


الرسم البياني 10

عند تغيير اتجاهات جميع التدفقات في شجرة العنوان المباشر إلى الاتجاه المعاكس ، نحصل على شجرة العنوان العكسي ، والغرض منها هو ربط نقاط البداية n بنقطة إنهاء واحدة.

في الحالات التي يكون فيها n قوة من اثنين ، يمر أي مسار داخل شجرة العنوان تمامًا عبر عقد تبديل السجل ₂ n ، مما لا شك فيه (بدون تقارب) أقل من نفس المؤشر لشبكة الخلوية (O (( n )) ، أو طوبولوجيا خطية (O ( n )).

أبسط أنواع الشبكات اللوغاريتمية

باستخدام الشبكات "الشبيهة بالشجرة" ككتل بناء ، ليس من الصعب تعميم الحل السابق للحالة عندما تكون هناك نقاط بداية k . هناك طريقتان سهلتان للقيام بذلك.

تتمثل الطريقة الأولى في استخدام شجرة العنوان العكسي لجمع مسارات جميع الرحلات أولاً في دفق واحد مشترك ، ثم ، باستخدام شجرة العنوان المباشرة ، قسّم هذا الدفق إلى تدفقات فرعية موجهة إلى وجهتها (المخطط 11 ، المخطط العلوي ).


الرسم البياني 11

إذا كانت k و n هما قوتان ، في النهاية ، في أي مسار ، يمر أي مسار عبر العقد التبديل ₂ k + log ₂ n . نوافق على الرجوع إلى الشبكات المصممة وفقًا للخوارزمية الموصوفة للتو على أنها شبكات لوغاريتمية أحادية الاتجاه مع دمج أولي .

يمكن تحقيق الطريقة الثانية لحل نفس المشكلة من خلال عكس ترتيب عمليات الدمج والقسمة في الحل الأول. يمكن وصف تطبيقه على النحو التالي: لكل نقطة بداية ، نقوم بإنشاء مجموعة فريدة من التكرارات التخيلية لجميع نقاط النهاية ، وبعد ذلك ، نقوم بتوصيلها بهذه التكرارات (لم تعد وهمية) بشجرة عنوان مباشرة.

لإكمال تصميم الشبكة ، يبقى فقط الاتصال الآن بكل نقطة نهاية مع التكرارات التخيلية k من خلال تطبيق شجرة العنوان العكسي (المخطط 11 ، المخطط السفلي).

عندما يكون كل من n و k قوة اثنين ، فإن عدد نقاط التبديل على طول أي مسار داخل الشبكة المبنية حديثًا سيكون مساوياً مرة أخرى لتسجيل ₂ ك + سجل ₂ ن . نحن نتفق على الإشارة إلى شبكات مثل الشبكات اللوغاريتمية ذات الاتجاه الواحد ذات التقسيم الأولي .

تحويل الشبكات ذات الاتجاه الواحد إلى شبكات متماثلة
بشكل عام ، نشير إلى أي شبكة في اتجاه واحد إذا تم تقسيم نقاط العناوين المتصلة بها بشكل صارم إلى نقاط بداية ونهاية. بشكل افتراضي ، بالنسبة للشبكات ذات الاتجاه الواحد ، سيتم افتراض أنه يوفر مسارًا واحدًا على الأقل من السفر المحتمل من أي نقطة بداية إلى أي نقطة إنهاء.

إلى جانب رحلة تدوم مدى الحياة ، من الصعب العثور على أمثلة حيث تكون بعض نقاط العناوين بمثابة بداية للطريق فقط ، والبعض الآخر سيكون هو نهايته فقط. سنجعل تفكيرنا أقرب إلى الواقع إذا قمنا أيضًا بتضمين شبكات ترتبط فيها أي من نقطتي العناوين بطرق في كلا الاتجاهين. نحن نوافق على الإشارة إلى هذه الشبكات على أنها متماثلة.

في الواقع ، لا توجد فجوة أيديولوجية بين الشبكات ذات الاتجاه الواحد والشبكات المتماثلة: يمكن أيضًا استخدام كل شبكة متماثلة كشبكة ذات اتجاه واحد ، ويمكن لكل شبكة ذات اتجاه واحد ، والتي تربط في البداية عدد متساوٍ من نقاط البداية والنهاية ، تتحول إلى واحد متماثل (الرسم البياني 12).


الرسم البياني 12

يوضح المخططان 13 أ و 13 ب الأشكال "المتماثلة" للشبكة اللوغاريتمية مع الدمج الأولي والشبكة اللوغاريتمية ذات التقسيم الأولي. تثبت الأمثلة الخاصة بهم الإمكانية الأساسية لربط n quarters بمثل هذا النوع من الشبكات ، حيث يتناسب عدد عقد التبديل خلال أي رحلة مع لوغاريتم عدد الأحياء في المدينة.


الرسم البياني 13 أ


الرسم البياني 13 ب

دقة أقل تقدير الحد

لقد تم بالفعل تجميع مجموعة واسعة من الشبكات حتى الآن ، كل منها تشمل الوظيفة الخاصة التي تصف تبعية متوسط ​​عدد نقاط التبديل على طول الرحلة على عدد نقاط العناوين في المدينة. ومع ذلك ، ما زلنا لا نعرف مدى صغر هذا العدد من حيث المبدأ لعدد معين من الأوساط. يمكن الحصول على تقدير الحد الأدنى باستخدام نهج المعلومات.

في الواقع ، اسمح لبعض شبكات الطرق بتوصيل نقاط عنوان n ببعضها البعض ، واحتياجات الترحيل للسكان بحيث تكون لأي رحلة ، بغض النظر عن المكان الذي بدأت فيه ، فرصة متساوية لإنهاء أي مكان في المدينة.

لحل المشكلة المعنية ، سنقوم بإنشاء رسالة إعلامية إضافية ، باتباع هذه الوصفة: لفترة طويلة من الوقت ، سنقوم بجمع سجلات جميع الرحلات التي لها نقطة بداية ثابتة ، وكتابة عشوائيًا للعناوين التي توجد فيها هذه الرحلات انتهى. ستكون الرسالة الناتجة عبارة عن تسلسل عشوائي يتكون من أسماء نقاط عنوان المدينة.

تتمثل إحدى طرق إرسال هذه الرسالة إلى المريخ أولاً في تشفير جميع الأسماء إلى كلمات ثنائية بنفس الطول ، وبالتالي تحويل الرسالة الأصلية إلى تسلسل يساوي 0 ثانية و 1 ثانية ، وثانياً إرسال التسلسل الناتج عبر قناة اتصال رقمية. نظرًا للتشفير الذي يمكن تمييزه لمجموعة الأسماء n ، تكون الكلمات الثنائية لطول log ₂ n مطلوبة ، وسيكون طول الرسالة الرقمية:

(عدد السجلات) × سجل ₂ حرف

الشيء الأكثر إثارة للاهتمام هو أنه وفقًا لنظرية المعلومات ، بغض النظر عن خوارزمية الترميز المستخدمة ، من المستحيل ببساطة إرسال الرسالة نفسها بعدد أقل من الأحرف الثنائية.

يمكن أن يكون البديل عن النقل المباشر للأسماء المشفرة لنقاط النهاية هو الطريقة التي يُشار إليها بكل رحلة في الاتجاه المحتمل الذي تحول فيه المسار عند مفترق الطرق التالي. وفقًا لافتراضاتنا ، يمكن أن يكون لكل الشوكات الموجودة في الشبكة فرعين فقط ، لذلك ، للإشارة إلى الاتجاه في كل حالة ، يلزم 1 بت بالضبط. بالنسبة لأي شخص لديه خريطة للمدينة ويعرف نقطة البداية ، ستكون سلسلة البتات كافية لتتبع كل مسار واستعادة التسلسل الأصلي لوجهاتهم. إذا كان متوسط ​​عدد الشوك (العقد المقسمة) التي تمت زيارتها خلال رحلة واحدة هو x ، فسيكون طول الرسالة الثنائية مع طريقة الترميز الجديدة: (عدد السجلات) ×.

كما قيل سابقًا ، لا يمكن أن تكون طريقة الترميز الجديدة أكثر كفاءة من طريقة نقل العنوان الثنائي المباشر ، وبالتالي: (عدد السجلات) × × ≥ (عدد السجلات) × السجل ₂ ن ، لهذا السبب:

س ≥ سجل ₂ ن .

على الرغم من أن عدم المساواة الأخير قد تم استنتاجه في البداية لمجموعة من الرحلات التي كانت لها نقطة بداية ثابتة مشتركة ، فقد تبين أنها مستقلة عن الاختيار المحدد لهذه النقطة. لهذا السبب يمكننا تمديد النتيجة لجميع الرحلات في المدينة في وقت واحد ، وبالتالي الحصول على الجزء الأول من التقدير المعني:

P1 ) شريطة أن يكون لكل رحلة جديدة احتمال متساوٍ في الإنهاء في أي من نقاط العنوان n في المدينة ، لا يمكن أن يكون متوسط ​​عدد نقاط التقسيم لكل مسار أقل من log ₂ n .

بعقل عقارب الساعة إلى الوراء ، يمكننا تحويل كل نقطة نهاية الرحلة إلى نقطة البداية ، وكل عقدة ثنائية لتقسيم الشبكة - العقدة الثنائية للدمج. تسمح لنا هذه الحيلة الصغيرة بالحصول تلقائيًا من P1 على الجزء الثاني المفقود من التقدير:

P2 ) شريطة أن يكون لكل رحلة مكتملة فرص متساوية للبدء في أي من نقاط العنوان n في المدينة ، فإن متوسط ​​عدد العقد المدمجة في كل مسار لا يمكن أن يكون أقل من log ₂ n .

إذا استذكرنا وجود شبكة لوغاريتمية مع دمج أولي وشبكة لوغاريتمية مع التقسيم الأولي ، فسنحصل على الفور على مثالين للشبكات المثلى من حيث عدد نقاط التبديل ، والتي يتم زيارتها داخلها خلال المتوسط رحلة واحدة. دعونا نرى ما إذا كانت هذه الجودة تساعد في تقليل شدة خسائر التحويل التي تم إنشاؤها.

تبديل التكاليف في الشبكات اللوغاريتمية

إذا قارنا الشبكات بدمج أولي وتقسيم أولي ، فإن القسم الأول يبدو أكثر جاذبية بسبب بساطته. لسوء الحظ ، فإن هذه البساطة لها جانب عكسي للعملة: دمج جميع المسارات في تيار واحد يتعارض مع توصية i1 ، وبالتالي يحتمل أن يتسبب في خسائر كبيرة في الوقت. يبدو أن الشبكة ذات التقسيم الأولي تفي بالمتطلبات i1 - i3 ، ومع ذلك ، انطلاقًا من المخطط 13b ، فإنها تميل إلى زيادة سريعة في عدد أطراف الطريق وعقد التبديل المستخدمة. قد تجعل الجودة الأخيرة الشبكات من هذا النوع باهظة الثمن للاستخدام العملي.

سنقوم بتحليل هذه الأسئلة بمزيد من التفصيل. بادئ ذي بدء ، نحن نوافق على أن المدينة تتبع نموذج الترحيل مع "الوصول العشوائي" ، وأن التدفق الناتج عن أي من نقاط عناوينها له قوة 1.

خسائر في الشبكات مع دمج الأولي

في الرسم البياني 14 ، يمكنك رؤية رسم بياني للتدفقات الناشئة عن الشروط المذكورة أعلاه داخل الشبكة مع الدمج الأولي.


الرسم البياني 14

بدا لي من المريح تصوير الشبكة نفسها بشكلها أحادي الاتجاه ، مما يعني أن كل نقطة بداية ونهاية ، موقعة بالأرقام نفسها في المخطط ، تعني في الواقع نقطة العنوان نفسها في المدينة.

بناءً على الرسم البياني ، يمكننا حساب كثافة تكاليف التحويل الناتجة في الشبكة. لنبدأ من النصف الأيسر ، حيث من خلال شجرة العنوان العكسي ، يتم تجميع جميع المسارات في تدفق واحد. تمثل كل عقدة تبديل في هذا الجزء من الشبكة المكان الذي يتم فيه دمج طريقين سريعين باتجاه واحد في مخطط واحد (الرسم البياني 15).


الرسم البياني 15

إذا تم تحميل كل من الطرق في البداية بكفاءة ، فبعد الدمج ، لن تكون هناك حاجة لتقليل عدد الممرات ، ونتيجة لذلك ، لا ينبغي أن يكون هناك أي تكاليف تحويل ذات صلة.

لنفترض أن التدفق باستخدام الطاقة 1 يكفي بالفعل لتحميل الطريق بفعالية على طول مسارين على الأقل. في هذه الحالة ، سنصل إلى نتيجة غير متوقعة إلى حد ما: دمج تدفقات السيارة داخل شبكة اللوغاريتمية مع الدمج الأولي يحدث تمامًا "مجانًا" ، دون التسبب في أي خسائر زمنية.

حساب التكاليف التي تنشأ في النصف الأيمن ليس أكثر صعوبة. هذا الجزء من الشبكة عبارة عن شجرة عناوين مباشرة ، كل عقدة منها عبارة عن شوكة متناظرة درسناها بالفعل. عندما يكون التدفق الوارد مع القدرة p ، تكون شدة الخسائر الناتجة عند الشوكة ( α / 2 ν ) ⋅ p 2/2 . قوة التدفق التي تدخل مفترق الجذر هي: n ، وبالتالي ، فإن شدة الخسائر في عقدة الجذر هي: ( α / 2 ν ) ⋅ n 2/2 . في كل جيل جديد من شجرة العنوان ، يتضاعف عدد الشوكات ، وتكون قوة التدفق الوارد إلى النصف. نتيجة لذلك ، ستتخذ صيغة الخسائر داخل الشجرة بأكملها الشكل التالي:

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 ²

نظرًا لأن قوة تدفق الرحلات التي تولدها جميع نقاط العناوين بشكل مشترك هي n ، فإن متوسط ​​تكلفة الوقت لكل رحلة ( α / 2 ν ) ⋅ n ، مما يدل على الاعتماد الخطي على حجم المدينة.

عندما يتعلق الأمر بالشبكات المجردة ، من الصعب إعطاء أي تقدير ذي معنى لمنطقة الطرق التي يستخدمونها. كمقياس بديل للتعقيد الهيكلي ، يمكن حساب إجمالي الطاقة لجميع التدفقات الجانبية. كما هو مخطط له ، يجب أن تعكس القيمة الناتجة كثافة الموارد لبناء جميع التبادلات التي تتطلبها الشبكة. لا أستطيع أن أقول أنه من الناحية العملية ، سيكون لهذه الطريقة دائمًا تفسير جيد ، لكن من المحتمل الحصول على فكرة تقريبية عن مقدار العمل الذي ينتظرنا.

داخل الشبكة اللوغاريتمية مع الدمج الأولي ، لا توجد التدفقات الجانبية إلا في شجرة العنوان المباشرة ، وتكون قوتها الإجمالية لكل جيل من العقد متماثلة: n / 2. في المجموع ، هناك سجل ₂ n لأجيال من العقد في الشجرة ، وبالتالي فإن طريقة جديدة لتقييم التعقيد تعطي تقديرا للتعقيد: O ( n log ₂ n ).

شبكات لوغاريتمية مع دمج أولي

عدد نقاط العنوان مع القوة 1 .......................................... .......... ن
متوسط ​​وقت السفر
فقد بسبب تكاليف التبديل:
مقاربين ................................................. .................................................. ... يا ( ن )
القيمة الدقيقة ............................................ .................................................. ..... ( α / 2 ν ) ⋅ n
عدد العقد التبديل .............................................. ................................ يا ( ن )
عدد نقاط التبديل ، بالنظر إلى قوة التدفقات الجانبية ........................ O ( n log ₂ n )

خسائر في الشبكات مع التقسيم الأولي

ننتقل الآن إلى تحليل الشبكة اللوغاريتمية مع التقسيم الأولي ، مرة أخرى على افتراض أن الشبكة تستخدم لتوصيل نقاط العناوين بالطاقة 1 في المدينة مع "الوصول العشوائي".
يوضح الرسم البياني 16 جزءًا منه يتكون من نقطة عنوان واحدة جنبًا إلى جنب مع أشجار العناوين المباشرة والعكسية المجاورة لهذه النقطة.


الرسم البياني 16

بادئ ذي بدء ، يمكننا تقدير شدة خسائر التحويل الناتجة عن الجزء.
يمكن العثور على التكاليف المتكبدة أثناء تقسيم التدفقات من خلال المعادلة التالية I _{t_div1} = ( α / 2 ν ) ⋅ n ² ، والتي تم استنتاجها لشجرة العنوان المباشر في المثال السابق ، 1 بدلاً من n . في الواقع ، فإن أشجار العناوين المباشرة في المخططين 16 و 14 لها نفس العمق وتتضمن تدفقات مماثلة في الطاقة (ملاحظة: التشابه يعني القدرة على الحصول على مجموعة واحدة من القيم بضرب القيم من مجموعة أخرى بواسطة عدد ثابت. ، لتوضيح ، التشابه بين المثلثات من جانبهم). نظرًا للعلاقة التربيعية بين قيمة تكاليف التبديل التي تحدث عند مفترق واحد وقوة التدفق الوارد ، فإن التقليل المتزامن لجميع التدفقات بمقدار n مرة سيقلل من الخسائر في الشجرة بأكملها بمقدار ² مرات ، وبالتالي ، بدلاً من ذلك من القديم ( α / 2 ν ) ⋅ n ² ، نحصل على قيمة تساوي:

أنا _{t_div2} = ( α / 2 ν ).

يمكننا الآن حساب قيمة التكاليف في النصف الأيسر للجزء.
نظرًا للقيمة الصغيرة للتدفقات المدمجة للطريق داخل شجرة العنوان العكسي ، فلن يكون من المعقول هذه المرة بناء طريق أوسع من مسارين. لم يعد الدمج في مثل هذه الظروف مجانيًا: على عكس المثال السابق ، توجد مناطق ضيقة على الطريق السريع (الرسم البياني 17) ، حيث ستحدث تكاليف التبديل بالضرورة.


التين. 17

على افتراض أن السائق على دراية بالضيق المقبل مقدمًا ، يمكننا أن نفترض أن عملية التبديل من حارة المسدود بطيئة ، حيث تمتد مئات الأمتار على طول الطريق السريع. في هذه الحالة ، لدينا الحق في اللجوء إلى الخدعة التي استخدمناها سابقًا لحساب الخسائر في الشوكة المتناظرة - لتقسيم إجمالي تدفق الترحيل q إلى العديد من الأجزاء الصغيرة q _i ومن ثم تفسير كلٍ منها على أنه دفق جانبي من الطريق المنحدر. يتم احتساب الخسائر الناتجة عن كل بديل من هذا القبيل من خلال الصيغة:

I _i = ( α / 2 ν ) ⋅ p q _i ⋅ (1 + 1 / s ) ، ومع ذلك ، هناك نوعان من التفاصيل الدقيقة هنا.

الأول هو أن السيارات لن تهاجر أبعد من الصف التالي.
في الواقع: يجب أن يكون للتدفقات في الممرين المركزيين ، بسبب التناظر الواضح ، دائمًا نفس الكثافة تقريبًا ، لذلك لن يكون لدى السائقين سبب وجيه لعبور الخط الأوسط. من الملاحظة التي تمت ، يمكن استنتاج أنه في صيغة الخسائر الناجمة عن التدفق الجانبي الجزئي ، s تساوي 1.

عندما تغادر السيارات الممرات الحافة ، وتتحول إلى ممرين مركزيين ، تزداد تدريجياً قوة التدفق داخل الممرات المركزية ، وتتغير في كل حالة من P / 2 إلى P. وبالتالي ، فإن الدقة الثانية هي الاعتماد الكبير لـ p على عدد substream i ، مما يجعلنا نكتب:

ليس
I _i = ( α / 2 ν ) ⋅ p q _i ⋅ (1 + 1 / s ) ،
ولكن:
I _i = ( α / 2 ν ) p ( i ) ⋅ q _i ⋅ (1 + 1 / s ).

في حالة وجود أجزاء متساوية في العديد من الأجزاء الصغيرة ، التي تم تقسيم تدفق الترحيل إليها ، يتم التعبير عن الاعتماد p ( i ) بواسطة رسم بياني خطي (الرسم 18)


الرسم البياني 18

لحساب معدل شدة الخسارة ، يجب أن نلجأ إلى التكامل ، أو (يجعل هذا من الممكن إجراء شكل بسيط بشكل خاص لوظيفة قابلة للتكامل) كعلامة p ( i ) متوسط ​​القيمة على الرسم البياني مساوي 3 P / 4. نظرًا لأن إجمالي تدفق الترحيل من جانب كل ممر حافة هو P / 2 ، فإن شدة الخسائر في عقدة دمج منفصلة ستكون:

أنا _دمج = 2 ⋅ ( α / 2 ν ) ⋅ (3 P / 4) ⋅ ( P / 2) =

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

للعثور على الوقت الضائع الذي تم إنشاؤه داخل جزء على شجرة العنوان العكسي ، يمكننا تطبيق الصيغة الخاصة _بالدمج في كل من العقد:

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

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

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

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

ستكون التكاليف الإجمالية الناشئة عن الجزء الناتج عن دمج التدفقات وتقسيمها كما يلي:

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

لا تحتوي الشبكة اللوغاريتمية ذات التقسيم الأولي إلا على أجزاء من هذه الشظايا ، ويتم بالضبط تدفقات n بالقدرة 1 من خلال نقاط عنوانها ، وبالتالي فإن القيمة التي وجدناها تواً تساوي تمامًا خسائر التحويل لكل رحلة متوسطة.

في الواقع ، من المهم بالنسبة لنا ليس حتى رقم معين ، وهو ما يساوي تكاليف التبديل المحددة ، ولكن تظل هذه التكاليف ثابتة مع زيادة n . هذا الأخير يجعل من الشبكة اللوغاريتمية ذات التقسيم الأولي مقاربة أكثر اقتصادا فيما يتعلق بتبديل الخسائر بين جميع أنواع الشبكات التي درسناها في وقت سابق.

لسوء الحظ ، القيادة ليست حرة. على الرغم من القيمة الصغيرة المتدنية للعدد الكبير من التدفقات ، تحتوي كل شجرة عنوان مدرجة في الشبكة على حوالي 2 n أطراف طريق من حارات وحوالي n عقد تبديل بالحجم الكامل. هناك 2 أشجار في الشبكة ، والتي تعني الأطراف ( n ² ) والعقد ، مما يجعلها ليست فقط الأكثر اقتصادا من حيث كفاءة الوقت ، ولكن أيضا أغلى شبكة للبناء ، من بين جميع الأمثلة التي تم النظر فيها.

بالنسبة لمجموع التدفقات الجانبية ، فإن قيمتها ، كما يمكن حسابها بسهولة ، تنمو بسرعة O ( n log2 n ) وفي هذه الحالة لا تحمل معنى كبير.

الشبكات اللوغاريتمية مع التقسيم الأولي

عدد نقاط العنوان مع القوة 1 .......................................... ............ ن
متوسط ​​وقت السفر
فقد بسبب تكاليف التبديل:
مقاربين ................................................. .................................................. ...... يا (1)
القيمة الدقيقة ............................................ .................................................. ........ 11/8 ( α / 2 ν ).
عدد العقد التبديل .............................................. ................................... ( ن ² )
عدد نقاط التبديل ، بالنظر إلى قوة التدفقات الجانبية ........................... O ( n log ₂ n )

شبكة لوغاريتمية متوازنة

خسائر التبديل الصغيرة بشكل استثنائي وفي نفس الوقت استهلاك الموارد الكبير لبناء الشبكة ، الناشئة عن تطبيق شبكة لوغاريتمية مع التقسيم الأولي ، تجعلنا نريد إيجاد طريقة لتغيير تصميمه بحيث يتم تقليل استهلاك الموارد بشكل كبير في حين أن تكاليف التحويل لن تزيد بشكل كبير.

من الواضح أن السبب الرئيسي وراء عدد كبير للغاية من الطرق في الشبكة هو الكفاءة المنخفضة للغاية لاستخدامها. يظهر هذا الأخير بشكل واضح في الرسم البياني 19 ، والذي يعرض مخططًا تفصيليًا للتدفقات داخل شجرة العنوان المباشرة المجاورة لنقطة العنوان ith.


الرسم البياني 19

في الرسم البياني ، يشير الرقم الموجود أعلى طرف الشجرة إلى قوة التدفق الذي يمر على طول الطرف ، والنطاق أدناه هو مجموعة نقاط العنوان التي سيتم توزيع هذا التدفق في النهاية عليها. نحن نفترض أن جميع الأطراف المعروضة في المخطط هي طرق سريعة مؤلفة من حاراتين ، ويشار إلى عدد الأطراف في كل جيل من الشجرة في أسفل الشكل.

بعد دراسة متأنية ، قد تلاحظ أن القاعدة التي يقسم بها التدفق في عقدة معينة يتم تحديدها فقط من خلال موقع هذه العقدة داخل شجرة العنوان ولا تعتمد على عدد نقطة العنوان التي بدأت هذه الرحلات. .

إذا كان هناك عدة تدفقات موجهة إلى نفس مجموعة النقاط ، وكل تدفقات ليست قوية بما يكفي لملء المسار المخصص لها ، فلماذا لا نجمعها معًا في طريق سريع واحد. في الواقع ، هذه الفكرة البسيطة بشكل أساسي تجعل من الممكن بناء شبكة مجردة جيدة تنتج خسائر تحويل صغيرة نسبيًا وتكون اقتصادية من حيث عدد الطرق المستخدمة.

بالرجوع إلى شجرة العنوان بنقطة i ، نرى أن التدفق الذي يدخل في عقدة الجذر ينقسم إلى تدفقات ابنين بسعة 1/2 لكل منهما. يتكون تدفق الابن الأول من رحلات موجهة إلى نقاط من النطاق [1 ؛ n / 2] ، تتكون الثانية من رحلات موجهة إلى نقاط من النطاق [( n / 2) + 1 ؛ ن ].

باتباع الفكرة الموضحة أعلاه ، نجمع بين تدفقات الابن من نفس النوع في كل نقطة فردية ونقطة العنوان التي تتبعها بالترتيب بعدد زوجي. تتيح لنا هذه التقنية أن يحصل كل زوج من النقاط المحددة ، بدلاً من أربعة تدفقات بقوة 1/2 ، على اثنين فقط من التدفقات بقوة 1 (الرسم 20). سنقوم بتسمية الجزء الذي تم الحصول عليه من شبكة المستقبل باسم BN ₂ [i؛ أنا +1.


الرسم البياني 20

إذا لم يتم الجمع بين تدفقات الابن ، ولكن كان لا يزال داخل شجرة العنوان ، ثم في الجيل التالي من العقد ، سيتم تقسيم كل منها مرة أخرى إلى قسمين ، متساوين في القوة وحجم مجموعات العناوين يشير إلى التي الرحلات تتجه.

لماذا كسر التقليد المعمول به ، لأنه بعد عملية الجمع لا يزال لدينا نفس مجموعة أنواع التدفق كما كان من قبل ، ولكن مع عدد أقل من ممثلي كل نوع فقط. إلى كل من الإخراج يتدفق من BN ₂ [i؛ i +1] ، يمكننا تطبيق نفس قاعدة التقسيم التي تنطبق على تدفق من نوعه داخل شجرة العنوان.

لا يوجد سبب لعدم تكرار البناء المنطقي الموصوف أعلاه للجمع بين تقسيم التدفقات ذاتها. يُظهر الرسم البياني 21 مخططًا للجمع بين شظيتين
BN ₂ في جزء واحد من BN ₄ ، من ناحية أخرى ، يظهر الرسم 22 نفس الخوارزمية في الحالة العامة.


الرسم البياني 21


الرسم البياني 22

في النهاية ، سيتم الانتهاء من عملية توسيع الشظايا وتقودنا إلى العنصر الوحيد BN _n [1 ؛ ن ]. سوف نسميها الشبكة اللوغاريتمية المتوازنة (الرسم البياني 23).


الرسم البياني 23

دعنا نتفحص هذه الشبكة لمعرفة مدى تعقيد وقيمة خسائر التحويل الناتجة.
بناءً على الطبيعة الاستقلالية لتصميم الشبكة المتوازنة ، يمكن وصف عدد نقاط التبديل المضمنة في بنيتها بالمعادلة المتكررة:

العقد (BN _k ) = العقدتان (BN _{k / 2} ) + 2 k ،

مع القيد التالي:

العقد (BN ₁ ) = 0.

الحل لهذا النظام من المعادلات هو وظيفة:

العقد (BN _n ) = 2 n log ₂ n .

نظرًا لأن تصميم BN _n يتطلب خطوات الحث في السجل ₂ n ، فكل رحلة سوف تمر عبر عقد التقسيم log ₂ n ونفس عدد العقد المدمجة ، بالتناوب بينهما في طريقها (الرسم 24).


الرسم البياني 24

الخسائر الناتجة داخل كل عقدة تقسيم:
( α / 2 ν ) ⋅ (1) 2/2 .

الخسائر الناتجة داخل كل عقدة دمج:
( α / 2 ν ) ⋅ 3 ⋅ (1/2) 2/4 = 3/16 ( α / 2 ν ).

بالنظر إلى أن عدد كل منهما في الشبكة المتوازنة هو n log ₂ n ، يمكننا الحصول على القيمة الدقيقة لخسائر التحويل الكلية:
11/16 ( α / 2 ν ) n log ₂ n ،

والتي لكل رحلة واحدة هي:
11/16 ( α / 2 ν ) log ₂ n

شبكة لوغاريتمية متوازنة

عدد نقاط العنوان مع القوة 1 .......................................... .......... ن
متوسط ​​وقت السفر
فقد بسبب تكاليف التبديل:
مقاربين ................................................. .................................................. ... O (سجل ₂ ن )
القيمة الدقيقة ............................................ .................................................. .... 11/16 ( α / 2 ν ) log ₂ n
عدد العقد التبديل .............................................. ............................... O ( n log ₂ n )
عدد نقاط التبديل ، بالنظر إلى قوة التدفقات الجانبية ....................... O ( n log ₂ n )

الأرقام التي تم الحصول عليها أعلاه تسمح لنا أن نعتبر الشبكة المتوازنة حلاً وسطًا جيدًا بين مقدار الخسائر الزمنية المقدمة والتعقيد الهيكلي العام. إن استخدامه كشبكة طرق لمدينة حقيقية أمر ممكن من حيث المبدأ ، لكنه بالكاد ممكن من الناحية الاقتصادية. يبدو لي أن المجال الذي يمكن أن يكون فيه استخدام الشبكة المتوازنة ذا فائدة كبيرة هو أنظمة المعلومات واسعة النطاق ذات المتطلبات الصارمة لمدى تأخر الإشارة ، مثل الاتصالات الخلوية والإنترنت والحوسبة الموزعة وأجهزة الكمبيوتر متعددة المعالجات . بالنسبة لنا ، فإن أكبر قيمة للشبكة المتوازنة هي الطريقة التي صممت بها. بعد ذلك بقليل ، باستخدام تعديل لهذه الطريقة ، سنكون قادرين على تحسين شبكات المدن الخطية والخلوية التي تعتبر بالغة الأهمية من الناحية العملية.

لماذا المدن التاريخية محكوم عليها بالاختناقات المرورية؟

قد يبدو بياني غير متوقع ، لكن الإجابة على السؤال الخاص بالسبب في أن المدن النامية بشكل طبيعي ، والتي تعاني عادةً من الاختناقات المرورية ، قد وجدناها بالفعل في الفقرات السابقة. إذن ما هو جوهر ذلك؟

الحقيقة هي أن العديد من المدن التاريخية التي نجت بعد عصر الحصون في العصور الوسطى (على سبيل المثال ، كل عواصم العالم القديم تقريبًا) ورثت منذ ذلك الوقت البنية الشعاعية للشوارع. لسوء الحظ (بالنسبة لسكانها المعاصرين) ، فإن شبكة الطرق ذات البنية المماثلة لا تتطور بشكل جيد: أصبح الترتيب الكثيف للطرق الشعاعية بالقرب من المركز نادرًا للغاية على الأطراف. ونتيجة لذلك ، في عملية النمو السكاني ، أصبحت الشوارع التي كانت موجودة في البداية على هامش الطرق القليلة المؤدية إلى القلعة أكبر وأصبحت الشوارع التي ظهرت على الهامش قصيرة ولم تكتسب أهمية عبور كافية للنمو فيها اتساع. نتيجة لذلك ، تشير شبكة الطرق التي نراها الآن في المدن التاريخية الكبيرة في أغلب الأحيان إلى أنظمة النقل من النوع الشرياني ، وفي مصطلحاتنا ،إلى الشبكات اللوغاريتمية مع دمج (غير مكتمل) أولي.


(طرق موسكو ، الصورة: سلافا ستيبانوف)

إذا تحدثنا عن طول الطرق التي يجب أن يقودها السائق ، فإن تنفيذ هذا النوع من الشبكات ليس سيئًا: المسافة التي يتم قطعها غالبًا ما تختلف قليلاً عن مسافة الخط المستقيم ، وعن متوسط ​​القيمة في المدينة ، كما يجب أن يكون لأنظمة النقل "اللائقة" ، ينمو بمعدل O (√ n ). تكمن المشكلة في أنه مع توسيع المدينة في الشبكة اللوغاريتمية مع دمج أولي ، تزداد تكاليف التحويل الناتجة عنها بسرعة كبيرة: يعتمد مقدار الوقت الذي تمدد فيه الرحلة بسببها في المتوسط ​​على العدد من الناس الذين يعيشون في المدينة مثل O ( ن ). فمن الواضح أن تبدأ من بعض ن، هذه المرة سوف تسود على الوقت الصافي للتغلب على المسافة ، بمعنى آخر ، ستظهر اختناقات مرورية في المدينة.

مما لا شك فيه ، أن إعادة تنظيم نظام النقل في المدن التاريخية الكبيرة هي مهمة يمكن حلها. ومع ذلك ، من المهم أن نفهم أن بناء واحد أو اثنين أو خمسة شرايين نقل كبيرة ، وإن كان تحسنًا طفيفًا في الوضع في المدينة ، لكنه لن يلغي السبب الجذري لاختناقات المرور. من الواضح أن الطريقة الوحيدة للتغلب على عيوب الشبكة اللوغاريتمية مع الدمج الأولي هي استخدام شبكة أخرى. قد يكون المرشح الجيد هنا شبكة ذات طوبولوجيا خلوية ، ينمو خلالها الوقت اللازم لتغطية المسافة ، على الأقل ، بنفس معدل نمو خسائر التحويل.


(ليلة برلين ، الصورة: فنسنت لافوريت)

ربما هذا هو السبب في أن برلين الحديثة ، على الرغم من الطرق السريعة الشريانية الكبيرة ، تتميز بالفعل ببنية خلوية واضحة للعيان.

هناك العديد من الحلول المثيرة للاهتمام في العالم حول كيفية جعل سكان المدن التاريخية أكثر قدرة على الحركة ، ولكن على الأرجح ينبغي منح الجائزة الرئيسية في الكفاح من أجل الوصول إلى وسائل النقل لمهندسي برشلونة.


(شبكة الطرق المحدثة في برشلونة ، الصورة: فنسنت لافوريت)

نظرة فاحصة على شبكات المدن الخطية والخلوية

بعد أن تم العثور على أساليب التحليل وشحذها على شبكات مجردة ، حان الوقت الآن لتطبيقها على الحالات الأكثر واقعية للمدن مع طوبولوجيا الخطية والخلوية. سنحاول في هذا القسم تحليل جميع ميزات شبكات النقل الخاصة بهم بكل التفاصيل وتحديد القيمة العددية لمعدل شدة خسائر التحويل ، ومعرفة كيف تعتمد قيمتها على حجم الأرباع ، ومناقشة الاختلافات والتحسينات المحتملة.

مدينة خطية
هذه المرة ، سننظر في مثال لمدينة يوجد بها طريقان سريعان في اتجاه واحد: طريق سريع غربي به حركة مرور باتجاه الشمال والطريق السريع الشرقي مع حركة مرور باتجاه الجنوب (الرسم 25).


الرسم البياني 25

اسمح لكل ربع بتوليد تدفق باستخدام الطاقة 1. في هذه الحالة ، تبلغ قوة مسار واحد من ربع إلى آخر واحد إلى 1 / ن .

بادئ ذي بدء ، سوف نحدد قوة التدفقات الجانبية في الطرق السريعة. الطريق هو الطريق الغربية الوحيدة في الحصول على ربع انا من الربع ( ن - ط ) جنوبا يقع، والطريقة الوحيدة للحصول على الربع من أنا هو ربع إلى ( ط - 1) شمالا تقع. وهذا يعني أن قوة تبادل الحركة تتدفق بين الطريق السريع الغربي والربع الأول هي:

q _{W_out} = ( n - i ) / n- قوة التدفق الجانبي _{الخارجة من} الطريق السريع الغربي ،
q _{W_in} = ( i - 1) / n - قوة التدفق الجانبي الوارد.

من الواضح أن قوة التدفقات الجانبية في الطريق السريع الشرقي تعتمد على i بطريقة متناظرة:
q _{E_out} = ( i - 1) / n - قوة التدفق الجانبي _{الخارجة من} الطريق السريع الشرقي ،
q _{E_in} = ( n - i ) / ن - قوة تدفق الجانب الوارد.

بالطبع من، مجموع التدفقات ترك ط -th الربع:
ف _{E_in} + ف _{W_in}= ( n - 1) / n ،

يتزامن مع مجموع التدفقات التي _تدخله :
q _{E_out} + q _{E_out} = ( n - 1) / n ،

وكلتا القيمتين لا تعتمدان على i (يحتوي كل ربع على التدفق باستخدام القوة 1 / n ، يتكون هذا التدفق من الرحلات التي تبدأ وتنتهي في الربع المحدد).

لحساب قوة ولمن التدفقات الرئيسية، <BR> سنقوم من رسم خط وهمي عبر الطريق السريع الغربي على نفس | المستوى مع ط -th الربع. في المجموع ، سوف يعبر هذا الخط:
(عدد الفصول جنوبًا) × (عدد الفصول شمالًا) = (n - i ) ( i - 1) من الطرق التي تنشئ معًا تدفقًا باستخدام الطاقة:

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

نفس الصيغة:
(عدد الفصول شمالًا) × (عدد الفصول شمالًا) / n ،
يجب أن تعبر عن قوة تدفق حركة المرور في الطريق السريع الشرقي P _E ، بمعنى آخر:

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

قوة معرفة جميع الرئيسية والجانبية تدفقات، يمكننا حساب الخسائر معدل الكثافة التي تحدث في الشبكة في منطقة قريبة من ط الربع -th:

I ( ط ) = ( α / 2 ν ) ⋅ P ( ط ) ⋅ [( 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 ).

إذا قمنا بتلخيص التعبير الأخير عبر i ، فسنحصل على معدل شدة الخسائر الناتج عن الشبكة بالكامل ككل.

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 ).

وΣ مبلغ _ط ( ط / ن ) ⋅ (1 - ط / ن ) ⋅ (1 / ن ) لأي كبير ن يمكن استبدالها مع دقة جيدة من خلال تكامل:

∫ ر (1 - ر ) د ر ( ر ∈ [ 0 ؛ 1]) = 1/2 - 1/3 = 1/6.

بناءً على ذلك ، يمكننا الحصول على شدة تبديل الخسائر في مدينة Linearن أرباع مع السلطة 1 إلى كميات:

I = ( α / 2 ν ) ن ² /3.

حتى هذه المرحلة ، أخذنا في الاعتبار فقط الأمثلة التي تتدفق فيها الأوساط دائمًا بالقوة 1. فلننظر فيما إذا كانت صيغة تبديل خسائر مدينة خطية ستتغير إذا لم يكن هناك مصدر واحد للتدفق مع القدرة 1 لكل ربع ، ولكن - λ (ستصبح الأرباع أكبر بمقدار λ مرات).

دعونا نأخذ مدينة مع أرباع م . إذا أرباع لدت تدفقات الطاقة 1، ثم الخسائر التحول سيكون ( α / 2 ν ) م ² /3.

زيادة في رحلة لقوة الإنتاج من خلال كل ربع بعامل امدا يؤدي إلى زيادة في أن كلا الرئيسية والجانبية التدفقات بعامل امدا . ونتيجة لذلك، فإن التكاليف في كل تقاطع، وبالتالي داخل الشبكة ككل، وزيادة بعامل λ ² مرات، والتحويلات خسائر الصيغة في:

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

إلى حد كبير ، لا يهم كيف تعتمد خسائر التحويل على عدد الأحياء في المدينة ، فالشيء الرئيسي بالنسبة لنا هو كيف تعتمد على قوة التدفق لجميع الرحلات التي يتم إنشاؤها داخلها ، أو بمعنى آخر ، على الرقم نمصادر قوة 1. في هذه الحالة، ن تساوي م ⋅ λ ، لذلك:

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

بمعنى آخر ، لا يعتمد تبديل الخسائر في مدينة Linear على مدى صغر اختيار تجزئة أراضيها إلى أرباع.

مدينة الخلوية

تخيل مدينة خلوية يتم فيها تخصيص الطرق السريعة في الشوارع العمودية على ارتفاعات / مستويات مختلفة. سيكون هذا ممكنًا ، على سبيل المثال ، إذا تم رفع جميع الطرق السريعة المتجهة من الشمال إلى الجنوب على الجسور ، وتم بناء الطرق السريعة الممتدة من الغرب إلى الشرق على سطح الأرض. بالإضافة إلى ذلك ، إذا كانت جميع الطرق السريعة لها حركة مرور في اتجاهين ، فسيتم إحالة شبكة الطرق في مثل هذه المدينة إلى الطوبولوجيا الخلوية القياسية (الرسم 26).

النقطة المهمة هنا ، بالطبع ، هي عدم تفعيل الشبكة الموضحة أعلاه على محمل الجد: لن تبدو جميلة من الناحية الجمالية على خلفية مشهد المدينة ، وعلاوة على ذلك ، بسبب الحاجة إلى تقاطعات متعددة المستويات ، فإنها ستأكل حتى أفضل نصف مساحة الشارع. ومع ذلك ، فإن هذه الشبكة الافتراضية البحتة هي طريقة جيدة للحصول على التقديرات اللازمة ، والتي يمكن في وقت لاحق توسيعها بسهولة لشبكات الطرق المثيرة للاهتمام حقًا من وجهة نظر قابليتها للتطبيق في المدن الحقيقية.

كالمعتاد ، سنفترض أن احتياجات الترحيل للمقيمين موصوفة بواسطة نموذج "الوصول العشوائي" ، وسوف نبدأ نظرنا في الحالة عندما تكون قوة جميع التدفقات الناتجة عن ربع معين 1.

في مثال المدينة الخلوية القياسية ، من المريح التنحي عن التقليد المعمول به والنظر إلى نقطة العنوان ليس ربع منفصل ، بل منطقة إقليمية ذات شكل مربع داخل تقاطع الطرق السريعة و 1 / 4s من جميع الجهات المتاخمة لها. يوضح الرسم البياني 27 الموضع النسبي للعديد من هذه المناطق ويظهر نمط حركة المرور بداخلها. يوضح هذا الرسم البياني بوضوح أن أي سائق ، يغادر الربع ، لديه فرصة للدخول في الطريق السريع ، ويتحرك في اتجاه أي جانب من جوانب العالم الأربعة.


الرسم البياني 26

لحساب قيمة تكاليف التحويل الناتجة عن المدينة ، سنقوم بحساب قوة جميع التدفقات الرئيسية والجانبية داخل كل منطقة من مناطقها الإقليمية. يسمح لنا شكل المناطق وموقعها المتبادل باللجوء إلى تشبيه الشطرنج لحل المشكلة المعنية ، مع اعتبار المناطق كخلايا حقل ، وحركة السيارات بينها - كحركات من الرخ (الرسم 27). في حالة عامة ، يمكن نقل الرخ من خلية واحدة إلى أخرى في حركتين ؛ إذا كانت كلتا الخليتين على نفس الخط الأفقي أو العمودي ، ثم - في خطوة واحدة.


الرسم البياني 27

لتجنب العديد من الحجوزات غير المريحة ، نفترض أن الحركة التي لا تنتقل إليها الغراب في أي مكان مسموح بها أيضًا وفقًا لقواعدنا. مسار حركة الغراب ، الذي يتكون من حركتين ، أحدهما يتم إجراؤه بالضرورة عموديًا ، والآخر - أفقياً ، سوف يطلق عليه الأسهل. من المعقول اعتبار الخطوة "توقفًا" عموديًا وأفقيًا في نفس الوقت. في هذه الحالة ، اتضح أن أي خليتين على اللوحة متصلتان ببعضهما البعض بواسطة طريقين أبسط مختلفين تمامًا.

بالنسبة للسائقين ، فإن أبسط طريق هو أسهل طريقة للوصول ، مع الحد الأدنى من التداخل ، من منطقة إقليمية إلى أخرى ، لذلك فمن المعقول افتراض أن الرحلات الحقيقية ستتم على طول خطوط الطريق الأولية. وفقًا لنموذج "الوصول العشوائي" ، يجب توزيع التدفق مع القدرة 1 الناتجة عن نقطة العنوان (المنطقة الإقليمية) بالتساوي بين جميع نقاط العنوان في المدينة = n ² d . لذلك ، فإن قوة التدفق التي تمر على طول خط مسار واحد هي 1 / (2 n ). يمكننا حساب التدفق باستخدام القوة التي تمر عبر الخلية ( i ، j ) في الاتجاه من الجنوب إلى الشمال. أبسط طريق يعبر الخلية ( i ، j

) من الجنوب إلى الشمال في حالتين فقط. أولها (الرسم البياني 28 على اليسار):

1 أ) تقع خلية بداية المسار في واحد من آخر الخطوط (الصفوف) الأفقية ( d - i ) ؛
2 أ) نقطة النهاية للمسار هي واحدة من أول خلايا ( i - 1) من الخط العمودي j (العمود) ؛
3 أ) يبدأ المسار بقسم أفقي ، أو يقع بالكامل داخل العمود j .


رسم 28

الشروط واصفا الثانية متناظرة الوضع نظرة (رسم 28، والحق في):

1A) نقطة بداية الطريق هي واحدة من الماضي ( د - ط ) خلايا ي -th خط عمودي،
2 أ) تقع خلية النهاية للمسار في أحد الخطوط الأفقية ( 1 - 1) الأولى ؛
3 أ) يبدأ المسار بقسم عمودي أو يقع بالكامل داخل العمود j .

على رقعة الشطرنج لا يوجد سوى 2 × [ d ⋅ ( i - 1) + 1⋅ ( i - 1)] × ( d - i) أبسط الطرق المناسبة للمتطلبات ، والتي تنشئ معًا تدفقًا مع القدرة:

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

تحديد j ، سوف نحصل على الوظيفة

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

يصف اعتماد طاقة التدفق التي تتحرك شمالًا على طول الطريق السريع العمودي j- jth على المسافة إلى الحدود العليا للمدينة ، المقاسة في الخلايا.
هناك العديد من الملاحظات الواضحة أو الأقل فيما يتعلق بالوظائف ( P _SN ) _j ( i ) ، دعنا نناقشها.

لنبدأ بظرف يصعب التغاضي عنه: P _SN ( i ، j ) مستقل عملياً عن الوسيطة الثانية. ونتيجة لذلك ، فإن الوظائف ( P _SN ) _j ( i ) = P _SN (i ) لها نفس الشكل لكل قيم j ، بمعنى آخر ، لا يؤثر الموضع المحدد للطريق السريع داخل المدينة الخلوية على حمله. من الناحية الرسمية ، تم إثبات العبارة الأخيرة فقط للطريق السريع المتجه إلى الشمال ، ولكن نظرًا لتناظر المدينة ، فإنه ينطبق تلقائيًا على الطريق السريع في الاتجاهات الأخرى أيضًا.

الآن ، دعونا نلقي نظرة على صيغة P _SN ( i ) نفسها:

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

كما نرى ، فإن الاعتماد الكامل على P _SN منأنا على أنا تكمن في التعبير ( أنا - 1) ⋅ ( د - أنا ). يمكن تفسير هذا التعبير على أنه نتاج أطوال الامتدادات اليمنى واليسرى حيث يتم تقسيم القسم الصحيح من الطول d بعد أن يتم استبعاد العنصر i (المخطط 29 أ) منه.


الرسم البياني 29a


الرسم البياني 29b من

الواضح أنه إذا قمت بتغيير "اليمين" إلى "اليسار" و "اليسار" إلى "اليمين" (الرسم البياني 29b) ، فستظل نتيجة المنتج كما هي. بناءً على هذه الملاحظة البسيطة ، يمكننا استخلاص استنتاجين مفيدين جدًا بالنسبة لنا:

1. the function P _SN ( i ) is symmetric with respect to the midpoint of the street i = (d + 1)/2, in order words, the flow power at a distance Δ from the lower boundary of the city is exactly the same as at a distance from the lower boundary of the city is exactly the same as at a distance Δ from the upper boundary.
2. On the whole, the city itself is symmetrical up and down, therefore, to get the function ( P _NS ) _j ( i ), which describes the power flow on the j -th highway, but in a southward direction, it's enough to simply mirror the function graph ( P _SN ) _j ( i ) in the line i = ( d + 1)/2. Since ( P _SN ) _j ( i ) = P _SN ( i ), and the graph P _SN ( i ) with respect to the line i = ( d + 1)/2 is symmetric, then ( P _NS ) _j ( i ) = P _SN ( i ) = P _vert ( i ),, in other words,
3. direct and oncoming traffic flows have equal power at any point of the city. A closer graph of P _SN ( i )is shown in Chart 30 (it is believed that d >> 1, i >> 1, d − i >> 1).

الرسم البياني 30

، يمكن العثور بسهولة على قوى التدفقات الرئيسية على طول الطرق السريعة الأفقية باستخدام التناظر الدوراني ؛ بشكل رسمي ، يمكن تنفيذ هذه العملية من خلال الاستبدال البسيط لـ i بواسطة j في P _SN ( i ) وتصحيح صغير للمؤشر السفلي.

الخطوة التالية التي يجب اتخاذها هي العثور على قوة التدفقات الجانبية. يمكن تقسيم الرحلات التي تدخل أو تترك حركة المرور على طريق سريع عمودي داخل الخلية ( i ، j ) إلى أربع فئات:

1. the flow q _{in_transit} : start point is in any cell of the i -th horizontal, finish point is in any cell of the j -th vertical, except for the ( i , j ) itself (Chart 31a);
2. the flow q _{out_transit} : start point is in any cell of the the j -th vertical, except for the ( i , j ) itself, finish point is in any cell of the i -th horizontal (Chart 31b);
3. the flow q _in : start point is the ( i , j ) itself, finish one is any cell outside the i -th horizontal (Chart 31c);
4. the flow q _out : start point is in any cell outside the i -th horizontal, finish point is the ( i , j ) itself (Chart 31d);

رسم 32: ABCD

وبعد سرد عدد من خطوط الطريق التي تنتمي إلى كل فئة منفصلة، يمكننا أن نستنتج أن صلاحيات جميع التدفقات أربعة هي نفسها وعلى قدم المساواة:

ف ₀ = د ⋅ ( د - 1) / (2 ن )

وبعد أن قيم قوى التدفقات الرئيسية والجانبية في طريق سريع عمودي ، ليس من الصعب حساب قيمة تكاليف التبديل المعنية. داخل خلية واحدة ( i ، j ) ستكون تكاليف التبديل مساوية لـ:

I _vert ( i ، j ) = ( α / 2 ν ) ⋅ P_vert ( i ) ⋅ [( q _in + 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 / د ).

للعثور على التكاليف المتكبدة في جميع الشوارع الرأسية داخل المدينة بأكملها ، نحتاج إلى جمع I _vert ( i ، j) لكلا المؤشرين:

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

قيمة منذ summands لا تعتمد على ي بأي شكل من الأشكال، ملخصا على الرقم القياسي الثاني ما يعادل ضرب من قبل د :

Σ _ط ( ط /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 _فير = ( α / 2 ν ) ⋅ د ³ /3 = ( α / 2 ν ) ⋅ ن √ ن / 3.

الجواب يمكن أن نتساءل ما هي قيمة التكاليف I _horiz ، التي تنشأ في الطرق السريعة الأفقية، وذلك باستخدام التناظر المدينة:

I _horiz = I _فير = ( α / 2 ν ) ⋅ ن √ ن / 3.

لذلك ، فإن معدل شدة فقد التحويل داخل الشبكة بالكامل للمدينة الخلوية القياسية يساوي:

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

وفي الرحلة ، في المتوسط ​​، ستكون تكاليف التبديل

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

تأثير حجم الخلية على قيمة خسائر التحويل

تمثل الأحياء التي تولد التدفقات باستخدام الطاقة 1 قيودًا مصطنعة إلى حد ما على ظروف المشكلة. يمكننا تمديد النتائج التي تم الحصول عليها أعلاه إلى الحالات التي تكون فيها قوة التدفق الناتجة عن خلية واحدة تساوي λ .
دع المدينة تتكون من م هذه الخلايا. إذا كانت جميع خلايا الطاقة 1، ثم شدة الخسائر الإجمالية التحول سيكون I ₁ = 2/3 ⋅ ( α / 2 ν ) ⋅ م √ م . زيادة عدد الرحلات بعامل λ سوف تتضاعف ب λأضعاف قوى جميع التدفقات الرئيسية والجانبية في الطرق السريعة ، الأمر الذي سيؤدي بدوره إلى الزيادة بمقدار λ ² في جميع تكاليف التحويل الناتجة داخل المدينة. سوف تأخذ الصيغة الجديدة لمعدل شدة الخسارة بالشكل التالي:

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

إذا افترضنا أن الخلية تتكون من λ نقاط عنوان بقوة 1 ، فإن الإجمالي عدد هذه النقاط سيكون: n = λm . دعنا نعبر عن أنني دالة n و λ :

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

ومتوسط تكلفة الرحلة في ظل الظروف الجديدة ستكون 2/3 ⋅ √ λ ( α / 2 ν ) ⋅ √ ن ، ويجري √ λ أعلى من قيمتها في المدينة تتكون من أرباع 1 مع السلطة.

تُخبرنا الصيغة الأخيرة أنه بالنسبة لنفس السكان والكثافة السكانية والمساحة الكلية لجميع الطرق ، كلما كان حجم الأحياء التي اختارها مهندسها أكبر ، زادت تكاليف التبديل. في حالة عدم توزيع سكان المدينة بشكل غير متساو على أراضيها ، بالطبع ، نحتاج إلى الاهتمام ليس بالأبعاد الهندسية ، ولكن أولاً وقبل كل شيء لمتوسط ​​عدد الأشخاص داخل الحي ونشاط هجرتهم.


(صورة مركز مدينة نيويورك: فنسنت لافوريت)

الملاحظة المذكورة أعلاه مهمة بشكل خاص عند تصميم مناطق بها مباني ناطحة سحاب. نظرًا للجمع بين الكثافة السكانية العالية وتنقلها العالي ، من الأهمية بمكان تصميم أماكن في المناطق الشاهقة أصغر بعدة مرات من المساحة المعتادة للمباني القياسية. في الحضارات ، حيث تاريخ بناء ناطحات السحاب له تاريخ طويل ، فإن ممارسة عزل المباني الكبيرة المنفصلة حتى الربع منتشر على نطاق واسع.

مدينة الخلوية مع أنظمة إشارة المرور
في كل حالة ، عند تقاطع خطوط طريقين سريعين مزدحمين على الخريطة ، يجب على المهندس المعماري الاختيار: إما أن يرفع أحد هذه الطرق إلى الجسر ، أو يسمح لتدفق الآخر بالمرور بحرية أسفله ، أو يدرك التقاطع في شكل تقاطع ، وحل نزاع التدفق من خلال تنظيم إشارة المرور. غالبًا ما يتم اختيار الخيار الثاني في المدن لأنه بسيط بشكل جذاب ، ولا يعني الحاجة إلى إنشاء هياكل هندسية واسعة النطاق ، بالإضافة إلى أنه يوفر للمشاة وسيلة سهلة لعبور الطريق.


(الأحياء التجارية في لوس أنجلوس في فترة ما بعد الظهر ، الصورة: بوريس شين)

استخدام إشارات المرور في الشبكات ذات الهيكل الخلوي له خصائصه الخاصة. في الفصل الأول ، تبين أنه مع التزامن الصحيح لإشارات المرور ، لا يتعين على السيارات ، أثناء تحركها على طول الشارع نفسه ، التوقف عند التقاطعات: سوف يضيء ضوء أخضر دائمًا في اتجاهها. عادة ما يسمى هذا النوع من الظاهرة إدارة حركة الموجة الخضراء. لإنشائها ، يجب تقسيم التدفقات المرورية إلى قسمين بديلين: مليئين بالسيارات وخالية منها. بعد ذلك ، يتم تحديد مثل هذا النمط من تشغيل إشارات المرور في الفترة الزمنية التي يمر فيها "الجزء" التالي بالتقاطع على طول أحد الشوارع ، والجزء السابق من السيارات التي تتحرك على طول الشارع المتعامد قد مر بالفعل ، والجزء التالي واحد لم يصل بعد (الرسم البياني 33).


الرسم البياني 33

تتحمل إدارة حركة المرور على الموجة الخضراء تكاليفها الخاصة وتفرض قيودًا معينة على تخطيط شوارع المدينة.

بالنظر إلى الرسم البياني 33 مرة أخرى ، من السهل أن نرى أنه في أي وقت من الأوقات لا يتم استخدام نصف مساحة جميع الطرق بالضبط. للتعويض عن هذا التوقف ، في النصف المستخدم بنشاط ، يجب أن تكون القوة المحلية لتدفق السيارات وعدد الممرات اللازمة لها أكبر مرتين في مدينة بها جسور.

ثاني أهم الظروف المرتبطة باستخدام الأمواج الخضراء هو التنظيم الصارم لحجم الأرباع المسموح به: طولهما (للشوارع ثنائية الاتجاه) يجب أن يكون مضاعفًا لطول الموجة الخضراء المملوءة (جزء من التدفق) من خلالها الحركة دون عوائق ممكنة) ، التي تصل إلى حوالي 500 متر. كما هو مذكور في الفقرة السابقة ، تتطلب المناطق ذات الكثافة السكانية العالية زيادة في تواتر مواقع الطرق ، وبالتالي فإن القيود المفروضة على المسافة بين الطرق السريعة (الحجم المسموح به للأرباع) يمكن أن تسبب صعوبات مرورية.

من المثير للاهتمام أن نلاحظ أنه في إدارة حركة مرور الموجة الخضراء ، تتغير قواعد التحويل داخل الشبكة قليلاً. على سبيل المثال ، يمكن إجراء إضافة سيارة أخرى إلى حركة المرور الرئيسية في الفترات الفاصلة بين المناطق المملوءة ، دون التسبب في أي تكاليف تحويل خطيرة (النقطة 1 في الرسم البياني 34 أ).


الرسم البياني 34

بالطبع ، يجب أن تفقد هذه السيارة نفسها بعض الوقت في انتظار أقرب منطقة خالية قبل الدخول إلى الطريق السريع ، وبعد ذلك تقف عند إشارة المرور حتى تصل إليها المنطقة المملوءة التالية (النقطة 2 ، الرسم البياني 34 أ) لا تعتمد قيمة هذه الخسائر على حجم المدينة أو على ازدحام حركة المرور في الشارع ، وبالتالي ، يمكن إهمالها على نطاق واسع.

يختلف الموقف تمامًا إذا حاولت سيارة مغادرة حركة المرور على الطريق السريع (الرسم البياني 34b). هنا ، على ما يبدو ، لم تعد هناك طرق صعبة لكيفية تقليل خسائر التحويل الناتجة عن برنامج التشغيل. علاوة على ذلك ، بسبب مضاعفة القوة المحلية للتدفق داخل المناطق المملوءة ، فإن ترك سيارة منتقاة عشوائياً منها يتسبب في تكاليف الوقت ضعف تكلفة المدينة مع الجسور. إجمالاً ، فإن "الدخول" الأرخص والأكثر تكلفة "الخروج" يقابلان بعضهما البعض ، مما يجعل المدينة الخلوية لحركة المرور في هذا الصدد ليست أفضل تقريبًا ، ولكن ليس أسوأ من المعيار.

مدينة الجسر الخلوي مع حركة المرور في اتجاه واحد

بالإضافة إلى استخدام إشارات المرور ، هناك فرصة واحدة على الأقل لتجنب التبادلات الوحشية للمدينة القياسية. إنه يعني تقسيم الطرق السريعة ذات الاتجاهين المكاني (الرسم 35).


الرسم البياني 35

نتيجة لهذه التغييرات ، سيتضاعف عدد الشوارع ، وستصبح جميعها شوارع أحادية الاتجاه ، ولكن الأهم من ذلك أن التبادلات سيتم تبسيطها إلى حد كبير (الرسم 36).


الرسم البياني 36

نظرًا لأن عدد الطرق السريعة المتجهة إلى كل جانب من جوانب العالم وعدد الرحلات التي تمر بها ظلت كما هي ، فإن قوى جميع التدفقات تترافق مع تكاليف التحويل في المدينة الخلوية ذات الاتجاه الواحد والمدينة القياسية مع 2 مرات أكبر (خطيا) أرباع ، يجب أن يتزامن. إذا قارنا المدن القياسية والمدينة ذات الاتجاه الواحد بأحجام الربع نفسها ، فستكون خسائر التحويل في المدينة الثانية أعلى مرتين.

شبكات الطرق المتقدمة

الشارع "الخطي"

كيف يمكن تقليل خسائر التحويل في شبكة خلوية؟ يمكن العثور على إجابة هذا السؤال من خلال تحديد القياس الصحيح ، بمساعدة القليل من الذكاء.

دعونا ننظر في تعديل غير عادي إلى حد ما للشبكة الخلوية ، مما يعني أن جميع الطرق السريعة الممتدة من الغرب إلى الشرق هي في اتجاهين ، في حين أن الطرق السريعة العمودية لها ليست إلا في اتجاه واحد: إما شمالًا أو جنوبًا ، وهذه الاتجاهات تتبدل من الشارع إلى الشارع.

كما هو الحال دائمًا ، سوف نفترض أن المدينة تتبع نموذج الوصول العشوائي ، وأن كل ربع منها يولد تدفقًا باستخدام الطاقة 1.

في هذه الحالة ، يبدو من المعقول تمامًا أن يكون التدفق قد نشأ داخل الربع ( i ، j) يتم توزيعه بين أقرب الشوارع على النحو التالي: 1/4 سيذهب إلى الطريق الأفقي شمالًا ، 1/4 - إلى الطريق الأفقي جنوبًا ، 1/4⋅ i / d - إلى الطريق السريع العمودي إلى الشمال و 1 / 4 ⋅ (1 - i / d ) - إلى الطريق السريع العمودي الثاني إلى الجنوب (الرسم البياني 37).

الرسم البياني 37 في

الواقع ، وفقًا لخوارزميات المسار التي تمت مناقشتها مسبقًا ، وفقًا للإحصاءات ، ستبدأ نصف الرحلات من قسم أفقي ، وبالنسبة للسائقين الذين يفضلون هذا النصف ، ينبغي ألا يهم ما إذا كان مسارهم يقع شمالًا أم لا. جنوبا من الربع ( ط ، ي ). سيبدأ النصف المتبقي من الرحلات من قسم عمودي لحركة المرور وسيتم تقسيمه بين الطرق السريعة المتجهة إلى الجنوب والشمال كنسبة من عدد الأرباع التي تقع جنوبًا من الربع ( i ، j ) إلى عدد الفترات الواقعة شمالا منه.

بالنسبة لتدفق الرحلات المتجهة إلى الداخل للربع ( i ، j) ، ستكون قاعدة تقسيمها فيما يتعلق بالطرق السريعة المحيطة بالربع متماثلة (الرسم البياني 38).


الرسم البياني 38 من

بين التقاطعات الأربعة المتاخمة للربع ( i ، j ) ، يمكننا أن ننظر بشكل منفصل في التدفقات الجانبية عند تقاطع الطريق السريع الأفقي السفلي والشارع العمودي مع حركة المرور إلى الشمال (الرسم 38). تدفق السيارات التي تدخل في التقاطع وتتجه من الشارع الأفقي إلى العمودي هو:
1 / 2⋅ (عدد الفصول على الأفقي) × (عدد الفصول على العمودي لا تقل عن ( i ، j )) ⋅ 1 / d ² =
= 1/2 ⋅ d ⋅ i / d ² =
= 1/2 ⋅ i/ د .

قوة التدفق الجانبي في الاتجاه المعاكس هي:
1 / 2⋅ (عدد الفصول على العمودي أقل تمامًا من ( i ، j )) × (عدد الفصول على العمودي) ⋅ 1 / d ² =
= 1/2 ⋅ ( d - i ) ⋅ d / d ² =
= 1/2 ⋅ (1 - i / d ).

دعونا الآن نحول انتباهنا من مدينة Cellular ككل إلى أي واحد من شوارعها العمودية ، دعنا نسميها My_street. بحكم التماثل ، لن نحدد تفكيرنا بأي شكل من الأشكال ، إذا افترضنا أن الحركة على طول My_street موجهة من الجنوب إلى الشمال (الرسم 39).


الرسم البياني 39

يصور الرسم البياني 40 قوة التدفقات الرئيسية والجانبية على الطريق السريع على طول My_street ، والتي ، كما قد يلاحظ القارئ ، تشبه بشكل لا يصدق الرسوم البيانية المماثلة للطريق السريع أحادي الاتجاه لمدينة خطية (الرسم 26).



الرسم البياني 40

في هذه الأمثلة ، تتزامن المخططات الانسيابية تمامًا إذا كانت التدفقات الجانبية المتعلقة بكل زوج من الأرباع المتعارضة والداخلية الأفقية تحتها داخل خلية My_street مخصصة رسميًا لخلية إقليمية خيالية واحدة. كما يتضح من الجداول السابقة ، فإن شبكة الطرق في مدينة Linear تنتج بعضًا من أكبر خسائر التحويل بين الشبكات التي درسناها بالفعل. من وجهة النظر هذه ، يبدو نمط حركة المرور داخل حدود شارع واحد لمدينة Cellular غير فعال للغاية وهو عنصر يجب تحسينه في المقام الأول.

شبكة المدينة الخطية المتقدمة

لذلك ، نحن نواجه مهمة تحسين شبكة Linear بحيث لا تتحول إلى شبكة "مربعة". يتمثل الظرف الذي يمثل أكبر قدر من عدم الكفاءة في تشغيل الشبكة الخطية في دمج جميع المسارات في اثنين فقط من تدفقات حركة المرور الكبيرة جدًا. في هذه الحالة ، تتمثل الخطوة المعقولة في تقسيم التدفقات على طول طريقي الشارع الرئيسيين إلى أجزاء Q متساوية. نظرًا لأن تكاليف الوقت الناجمة عن كل سيارة تنضم إلى حركة المرور أو تخرج منها تتناسب مع كثافة حركة المرور عليها ، نتيجة لتقسيم خطوط الشوارع إلى أجزاء Q معزولة (الرسم البياني 41 أ) ، يجب أن تكون خسائر التحويل داخل مدينة Linear قد انخفضت Q مرة .


الرسم البياني 41

حتى بعد بناء عشرة طرق قريبة ، لا يمكننا أن نأمل أن يتم توزيع السائقين بأنفسهم بالتساوي - لسوء الحظ ، لا يبدو أن هناك فرصة للنجاح. سيكون القرار الأكثر تفكيرًا هو تصميم الشبكة بحيث لا يؤدي كل طريق إلى جميع الجهات ، ولكن فقط إلى "شريحة" صغيرة من المدينة ، حيث سيكون من الصعب الوصول إليها دون استخدام طريق معين (الرسم البياني 41b ).

يمكنك رؤية فكرة مماثلة في مخطط حركة المصاعد داخل المباني متعددة الطوابق حيث يسمح لك كل مصعد بالدخول إليها والخروج منها ليس في جميع الطوابق ، ولكن فقط ضمن نطاق معين من الارتفاعات. بقبول هذا المفهوم ، دعونا نلقي نظرة فاحصة على الطريق r _k ، الذي يتيح الوصول إلى الجزء Δ_k = ( x _k ، x _{k +1} ] للرحلات التي بدأت (وليس بدقة) جنوبًا من xk (يُعتقد أن ترقيم الأرباع يتم تنفيذه من أسفل إلى أعلى)

.من كل ربع يكون العدد أقل (وليس بدقة) ) من العاشر _{من ك} ، و ف _في ، تيار مع قوة دلتا _وك | / ن (1 / ن إلى كل الربع داخل دلتا _للك ) يدخل الطريق ص _ك ، وفي نفس | وقت يفترض IT وهذا هو هناك أي إمكانية بدوره من ص _كتجاه أي من الأحياء المذكورة إما بسبب قواعد المرور المعمول بها ، أو بسبب تصميم خاص لشبكة الطرق.

السيارات المتراكمة على القطعة [1، س _ك ] في نهاية المطاف سوف توزع بالتساوي بين الربعين داخل Δ _ك ، لذلك، إذا لم تكن هناك رحلات التي تبدأ ونقطة النهاية تكمن داخل Δ _ك ، ثم يتدفق الجانب ف _بها في الاتجاه سيكون لكل من الربعين في هذا القسم القدرة x _k / n (الرسم البياني 42).


الرسم البياني 42

في الواقع ، مساهمة الرحلات "الداخلية" في قوة التدفقات الجانبية موجودة ، ومع ذلك ، فإن قيمة هذه المساهمة لا تتجاوز أبدًا | دلتا _للك | / ن ، وبالتالي، في حالة عندما س _ك >> | Δ _ك | ، يمكن إهمالها ببساطة. سيتم تمثيل القدرة p _k للتيار الرئيسي على طول r _k مع إجراء التبسيط برسم بياني يتكون من قسمين مستقيمين بحد أقصى P _k يساوي x _k ⋅ | دلتا _للك | / ن. يمكن العثور على القيمة التقريبية لخسائر التبديل في الطريق 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 [| Δ _ك | / ن ⋅ ص _ك ( خ )] + ( α / 2 ν ) ⋅ (1-1 / ق ) Σ _س [ س _ك / ن ⋅ ع _ك ( س ) =

= ( α / 2 ν ) ⋅ (1 + 1 / ثانية) ⋅ ( x _k ⋅ | Δ _k | / n ) ⋅ ( ∑ _x p _k ( x )) / x _k + ( α / 2 ν ) ⋅ (1 - 1 / s ) ⋅ ( x _k ⋅ | Δ _k | / n ) ⋅ ( ∑ _x p _k ( x )) / | دلتا _للك |،

حيث يتم أخذ المبلغ الأول على قطعة x ∈ [1، x _k ] ، والثاني على x ∈ Δ _k . التعبير عن و:

( Σ _س ص _ك ( خ )) / س _ك ، س ∈ [1، س _ك ] و

( Σ _س ص _ك ( خ )) / | Δ _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 _ك ²

دعونا الآن نحاول حساب تسلسل x _k من أرقام تلك الأحياء التي يجب أن تقسم بها مدينة خطية إلى شرائح. كمعيار لاختيار الأجزاء ، يمكننا أن نأخذ في الاعتبار أن الحد الأقصى لقدرة حركة المرور التي تتدفق P _k في الطرق التي تقترب منها يجب أن يكون له نفس القيمة ، مستقلة عن k ، بمعنى آخر:

x _k ⋅ | Δ _ك | = كون.

تذكر ذلك | Δ _ك | = x _{k + 1} - x _k ، يمكننا استنتاج معادلة الفرق:

x _{k + 1} - x_ك = كون / س _ك .

بافتراض أن 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 = C ₁ √ ( k + C ₂ ).

يبقى لنا أن نحدد قيمة الثوابت C ₁ و C ₂ بناءً على شروط الحدود ، ومع ذلك ، هناك دقة مهمة في هذه المسألة. على عكس الوضع في القطاعات الأخرى ، بدأت جميع السيارات التي تصل من الطريق السريع الغربي إلى أرباع الجزء برقم 1 ، رحلاتها داخل نفس الشريحة. نتيجة لذلك ، فإن الرسم البياني لقدرة التدفق في أول طريق سريع إلى الشمال سيكون له شكل مكافئ منتظم مقلوب.

في الوقت نفسه ، فإن الشروط المسبقة التي تم الحصول عليها من الصيغة x _k افترضت أساسًا أن الرسوم البيانية لتدفق الطاقة على جميع الطرق السريعة يجب أن تكون قريبة من العرض الثلاثي ، ويجب أن تبدأ الرحلات نفسها خارج القطاع الذي يتم توجيهه فيه بشكل أساسي. ل. يمكن تلبية هذه المتطلبات بدقة معقولة إذا قسمنا الجزء الأول رسميًا إلى جزأين متساويين ، دون زيادة عدد الطرق. معظم الرحلات التي تتم على طول الطريق السريع الأول تبدأ في النصف الجنوبي ، وتنتهي في النصف الشمالي. بالنظر إلى هذه العوامل فقط ، فإننا لا نرتكب خطأً كبيرًا في حساب خسائر التحويل ، ولكن الآن سيكون لمخطط رسم التدفق الرئيسي شكل ثلاثي (التخطيط 43).


الرسم البياني 43

هو منتصف الجزء الأول الذي يجب اعتباره النقطة × ₁ في صيغة x _k . هذا يسمح لنا بالحصول على شرط الحدود الأول:

x ₂ = 2 x ₁ أو

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

C ₂ = - 2/3.

يمكن الحصول على شرط الحدود الثاني من شرط أن تكون الطرق وشرائح كل شيء بالضبط Q ، مما يعني أن x _{Q + 1} يجب أن تكون لاحقة للربع مع أكبر عدد في المدينة:

C₁ √ ( Q + 1 - 2/3) = ن + 1، من حيث

C ₁ ≈ ( ن + 1) / √ Q .

لذلك:

x _k ≈ ( n + 1) ⋅ √ ( k - 2/3) / √ Q ،

| Δ _ك | D ≈ س / د ك = ( ن + 1) / 2√ ( ك - 2/3) ⋅ √ Q

P _ك = س _ك ⋅ | Δ _ك | / ن =

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

I _ك = ( α / 2 ν ) ⋅ P _ك ² =

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

نظرًا لأن جميع الطرق السريعة 2 Q تسبب خسائر بنفس الكثافة ، فإن قيمة تكاليف التبديل داخل الشبكة بالكامل ستكون:

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

كما ترون ، تم تحقيق النتيجة المرجوة: بعد تقسيم الطرق السريعة الرئيسية إلى Qالأجزاء ، انخفضت الخسائر بالفعل بعامل Q (باستثناء الزيادة من 1/3 إلى 1/2 معامل ثابت ، مقارنة مع الصيغة للمدينة الخطية المعتادة). حسنًا ، نحن في منتصف الطريق ، يبقى تطبيق هذه النتيجة لتحسين المدينة من خلال البنية الخلوية.

"Skyscraper Elevator" في إحدى المدن الخلوية من

أجل البساطة ، سننظر في مثال لمدينة تكون فيها جميع الشوارع في اتجاه واحد. باستخدام القياس بين المدينة الخطية والشوارع الفردية لمدينة الخلوية ، يمكننا تقسيم الطريق السريع على طول الأخير إلى Qأجزاء. افتراضيًا ، يُعتقد أنه عند مغادرة الربع ، يمكن للسائق اختيار أي طريق سريع يمر بالقرب منه. في الوقت نفسه ، من بين جميع الطرق السريعة الموضوعة على طول شارع واحد ، هناك اتجاه نحو ربع معين من واحد منهم بالضبط. في عملية وضع القواعد ، يعتبر توحيدها وبساطتها في غاية الأهمية. دعنا نلقي نظرة على الرسم البياني 44:


الرسم البياني 44

جميع الشوارع لديها نفس الرأي ونفس القواعد التي من أي طريق يفتح الوصول إلى أي ربع. يُظهر الرسم البياني 45 مخططًا للتحولات المسموح بها بين الطرق السريعة. بالنظر إلى هذه الصورة ، من الصعب عدم الخلط. كثيرا ما يقال الشيء نفسه عن مخطط تحت الأرض في بعض المدن الكبيرة. ومع ذلك ، في كلتا الحالتين ، يصبح كل شيء واضحًا وبسيطًا إذا كنت تعرف منطق الفكرة. تبدو القاعدة المنطقية للتحولات المسموح بها بسيطة للغاية: إذا كنت تقود على طول طريق سريع ، فإنك تعبر الطرق بشكل عمودي على حركتك ويمكنك أن تتحول إلى ربع يقع خلفها مباشرةً ، يمكنك أن تتحول إلى أي من هذه الطرق.


الرسم البياني 45

تتوافق طوبولوجيا "Skyscraper elevator" مع تقاطعات إشارات المرور والجسور. من الصعب ، لكن من الممكن تعميمها على شبكات ليست بالضرورة ذات بنية خلوية أو خطية. هذا الأخير مهم حقًا بالنسبة للمدن التاريخية ، حيث من غير المحتمل أن يكون قرار هدم نصف المعالم التاريخية أمرًا صائبًا من أجل تصميم العديد من الشوارع الصغيرة المستقيمة ، ولكن يوجد بالفعل شوارع كبيرة جدًا يمكنها استيعاب عدة شوارع - أو الطرق السريعة ثلاثة حارات.

حول مشاكل النقل وعمل عالم الرياضيات

من الجيد إكمال 6 أشهر من العمل الشاق. العمل الذي كتبته ، بالطبع ، لا يحل جميع مشاكل وصعوبات تصميم الطرق - فهذه المسألة تتطلب عددًا كبيرًا من الأشخاص متعددي المهارات ومتعدد المهارات. ومع ذلك ، فإن نتائجها توفر فرصة لرؤية الأخطاء المهمة في المدن التي بنيت بالفعل وتوفر طرقًا لكيفية تجنب هذه الأخطاء في المستقبل. لم يكن القصد من هذا المقال أن يكون بمثابة كتاب مرجعي يغطي جميع الحالات التي يمكن للمهندس مواجهتها في الممارسة العملية - فكرت في هدفي الرئيسي هو إعطاء وجهة نظر جديدة ، وتطوير طريقة جديدة للسبب والتحدث عن المشكلة ، لتوفير القارئ مع الحد الأدنى الضروري من الأمثلة النموذجية البسيطة التي يمكن للقارئ توسيعها.

يصبح الأمر محزنًا عندما تدرك مقدار الوقت الذي ضيعه سكان المدينة في الاختناقات المرورية لمجرد أنه في الوقت المناسب لم يكن هناك عالم رياضيات يمكنه قضاء المساء في مشكلة قابلة للحل تمامًا. كم من هذه المشاكل لا تزال تحيط حياتنا أو تختبئ في مهنتك؟ هل الشخص جالس بالقرب منك في مكان العمل وأدواته قلم رصاص وورقة؟

آمل أن يتغير كل شيء نحو الأفضل.

أود أن أعرب عن خالص امتناني لجانين لاكروا (اسم مستعار) لعملها في ترجمة هذا النص من النص الأصلي إلى الروسية.
شكرا لاهتمامكم وحظا سعيدا!
سيرجي كوفالينكو

2019
magnolia@bk.ru


(الصورة: فنسنت لافوريت)