تعيين المسار

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

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

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

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

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

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

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

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

• 0. ابدأ بتحميل كل حركة المرور باستخدام إجراء الكل أو لا شيء.
• 1. احسب أوقات السفر الناتجة وأعد تعيين حركة المرور.
• 2. الآن، ابدأ في إعادة التعيين باستخدام الأوزان. احسب أوقات السفر الموزونة في التحميلين السابقين واستخدمها للتعيين التالي. يحصل التكرار الأخير على وزن 0.25 ويحصل التكرار السابق على وزن 0.75.
• 3.استمر.

يبدو أن هذه الإجراءات تعمل بشكل "جيد جدًا"، ولكنها ليست دقيقة.

طبق دافرموس (1968) خوارزمية فرانك-وولف (1956، فلوريان 1976)، والتي يمكن استخدامها للتعامل مع مشكلة توازن المرور. لنفترض أننا نفكر في شبكة طرق سريعة. لكل رابط هناك دالة تحدد العلاقة بين المقاومة وحجم المرور. طور مكتب الطرق العامة (BPR) دالة ازدحام الرابط (أو تأخير الحجم، أو أداء الرابط)، والتي سنسميها S _a (v _a )

${\displaystyle S_{a}\left({v_{a}}\right)=t_{a}\left({1+0.15\left({\frac {v_{a}}{c_{a}}\right)^{4}}\right)}$

• t _a = زمن انتقال التدفق الحر على الرابط أ لكل وحدة زمنية
• v _a = حجم حركة المرور على الرابط أ لكل وحدة زمنية (بشكل أكثر دقة: التدفق الذي يحاول استخدام الرابط أ ).
• ج _أ = سعة الرابط أ لكل وحدة زمنية
• S _a (v _a ) هو متوسط ​​وقت السفر لمركبة على الرابط أ

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

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

يمكن إيجاد التوازن الأمثل للمستخدم عن طريق حل مشكلة البرمجة غير الخطية التالية

${\displaystyle \min \sum _{a}{\int _{0}^{v_{a}}{S_{a}\left(x\right)}}dx}$

خاضع ل:

${\displaystyle v_{a}=\sum _{i}{\sum _{j}{\sum _{r}{\alpha _{ij}^{ar}x_{ij}^{r}}}}}$

${\displaystyle \sum _{r}{x_{ij}^{r}=T_{ij}}}$

${\displaystyle v_{a}\geq 0,\;x_{ij}^{r}\geq 0}$

أين هو عدد المركبات على المسار r من نقطة الأصل i إلى نقطة الوجهة j . لذا فإن القيد (2) ينص على أن كل السفر يجب أن يتم - i = 1 ... n؛ j = 1 ... n${\displaystyle x_{ij}^{r}}$

${\displaystyle \alpha _{ij}^{ar}}$= 1 إذا كان الرابط a على المسار r من i إلى j؛ وإلا يكون صفرًا. لذا فإن القيد (1) يجمع حركة المرور على كل رابط. يوجد قيد لكل رابط على الشبكة. القيد (3) يضمن عدم وجود حركة مرور سلبية.

سيوضح مثال من Eash وJanson وBoyce (1979) الحل لمشكلة البرنامج غير الخطي. هناك رابطان من العقدة 1 إلى العقدة 2، وهناك دالة مقاومة لكل رابط (انظر الشكل 1). تتوافق المساحات الموجودة أسفل المنحنيات في الشكل 2 مع التكامل من 0 إلى a في المعادلة 1، ويبلغ مجموعها 220674. لاحظ أن دالة الرابط b مرسومة في الاتجاه المعاكس.

${\displaystyle S_{a}=15\left({1+0.15\left({\frac {v_{a}}{1000}}\right)^{4}}\right)}$

${\displaystyle S_{b}=20\left({1+0.15\left({\frac {v_{b}}{3000}}\right)^{4}}\right)}$

${\displaystyle v_{a}+v_{b}=8000}$

الشكل 1: شبكة ذات مسارين

الشكل 2: الحل البياني لمشكلة تعيين التوازن

الشكل 3: توزيع المركبات التي لا تلبي شرط التوازن

في حالة التوازن، يوجد 2152 مركبة على الرابط أ و5847 مركبة على الرابط ب . وقت السفر هو نفسه على كل طريق: حوالي 63.

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

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

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

لقد كان نموذج ويلسون المزدوج للإنتروبيا المقيد بمثابة نقطة انطلاق للجهود المبذولة على المستوى الكلي. ويتضمن هذا النموذج القيد

${\displaystyle t_{ij}c_{ij}=C}$

حيث تمثل تكاليف السفر عبر الرابط، وتشير إلى حركة المرور على الرابط، وC هي قيد الموارد الذي يجب تحديد حجمه عند ملاءمة النموذج مع البيانات. وبدلاً من استخدام هذا الشكل من القيد، يمكن استخدام دالة المقاومة المتزايدة بشكل رتيب المستخدمة في تعيين حركة المرور. تحدد النتيجة الحركات من منطقة إلى منطقة وتعين حركة المرور للشبكات، وهذا منطقي للغاية من الطريقة التي يتخيل بها المرء عمل النظام - تعتمد حركة المرور من منطقة إلى منطقة على المقاومة الناجمة عن الازدحام. ${\displaystyle c_{ij}}$${\displaystyle t_{ij}}$

وبدلاً من ذلك، قد يتم تضمين دالة مقاومة الارتباط في دالة الهدف (وإزالة دالة التكلفة الإجمالية من القيود).

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

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

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

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

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

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

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

إن بيان المشكلة والخوارزمية لهما تطبيقات عامة في الهندسة المدنية ـ الهيدروليكا، والهياكل، والبناء. (انظر هندريكسون وجانسون 1984).

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

لقد وجد أن راكبي الدراجات يفضلون مسارات الدراجات المخصصة ويتجنبون التلال شديدة الانحدار. ^[2]

لطالما تم النظر إلى وسائل النقل العام في سياق تحديد المسار ^[3] وأُجريت العديد من الدراسات حول اختيار مسار النقل العام. ومن بين عوامل أخرى، يحاول مستخدمو وسائل النقل العام تقليل إجمالي وقت السفر، والوقت أو المسافة التي يقطعونها سيرًا على الأقدام، وعدد التحويلات. ^[4]

• اختيار المسار (توضيح)

• دافرموس، ستيلا سي. و إف تي سبارو، مشكلة تخصيص حركة المرور لشبكة عامة. مجلة بحوث المكتب الوطني للمعايير، 73 ب، ص 91-118. 1969.
• فلوريان، مايكل المحرر، أساليب توازن المرور، سبرينغر فيرلاغ، 1976.
• إيش، رونالد، وبروس إن. جانسون، وديفيد بويس، مهمة رحلة التوازن: المزايا والآثار المترتبة على الممارسة، سجل أبحاث النقل 728، ص 1-8، 1979.
• إيفانز، سوزان ب. "استنتاج وتحليل بعض النماذج للجمع بين توزيع الرحلات والتعيين". أبحاث النقل، المجلد 10، ص 37-57 1976
• هندريكسون، سي تي وبي إن جانسون، "صيغة تدفق الشبكة المشتركة للعديد من مشاكل الهندسة المدنية"، أنظمة الهندسة المدنية 1(4)، ص 195-203، 1984