توجيه القوس

📅 آخر تحديث: ١ أغسطس ٢٠٢٦
✍️ نُشر في: ١ أغسطس ٢٠٢٦
📷 يحتوي على 32 صور
الموسوعة الحرة

تُعدّ مسائل توجيه الأقواس ( ARP ) فئةً من مسائل التوجيه العامة (GRP)، والتي تشمل أيضًا مسائل توجيه العقد (NRP). يهدف كلٌّ من مسائل توجيه الأقواس وتوجيه العقد إلى اجتياز حواف وعقد الرسم البياني، على التوالي. [ 1 ] ويهدف توجيه الأقواس إلى تقليل المسافة والوقت الإجماليين، والذي غالبًا ما يتضمن تقليل وقت التوقف ، أي الوقت اللازم للوصول إلى الوجهة. يمكن تطبيق مسائل توجيه الأقواس على جمع القمامة ، وتخطيط مسارات حافلات المدارس ، وتوصيل الطرود والصحف، وإزالة الجليد والثلوج باستخدام مركبات الخدمة الشتوية التي ترش الملح على الطريق، [ 2 ] وتوصيل البريد ، وصيانة الشبكات، وكنس الشوارع ، ودوريات الشرطة وحراس الأمن، [ 1 ] وجرف الثلوج . [ 3 ] [ 4 ] تُصنَّف مسائل توجيه الأقواس ضمن المسائل الصعبة حسابيًا (NP-hard) ، على عكس مسائل فحص المسارات التي يمكن حلها في وقت متعدد الحدود .

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

توجد تعميمات لمشاكل توجيه الأقواس التي تُدخل العديد من ساعي البريد، على سبيل المثال مشكلة ساعي البريد الصيني k (KCPP).

خلفية

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

أساس

تتمثل مشكلة التوجيه الأساسية فيما يلي: بالنظر إلى مجموعة من العقد و/أو الأقواس التي يتعين على أسطول من المركبات خدمتها، إيجاد مسارات لكل مركبة تبدأ وتنتهي عند مستودع. مسار المركبة هو سلسلة من النقاط أو العقد التي يجب على المركبة اجتيازها بالترتيب، بدءًا من المستودع وانتهاءً به. [ 2 ]

مشكلة ساعي البريد الصيني

تهدف مسألة ساعي البريد الصيني (CPP) إلى إيجاد أقصر مسار ممكن لساعي بريد واحد. تتطلب مسألة ساعي البريد الصيني اجتياز جميع الحواف مرة واحدة، بينما تتطلب مسألة ساعي البريد الريفي (RPP) اجتياز مجموعة فرعية من الحواف بأقصر مسار ممكن. [ 1 ]

مشاكل توجيه المركبات/VRP

تؤثر مشاكل توجيه المركبات على قرارات التخطيط الاستراتيجي والتكتيكي والتشغيلي. يعتمد الدور الاستراتيجي لموقع المستودع على المسار الأمثل المتاح. يرتبط قرار حجم أسطول المركبات وأنواعها ذات المواصفات المختلفة بالجانب التكتيكي لمشاكل توجيه المركبات في بحوث العمليات . تُعد قرارات التوجيه والجدولة من قرارات التخطيط التشغيلي في مشاكل توجيه المركبات. تشمل قرارات التخطيط التشغيلي أيضًا الوقت الذي يستخدم فيه العمال المركبات، مع مراعاة قرارات الموظفين. [ 2 ] تعتمد قرارات توجيه المركبات لموقع المستودع على تكلفة نقل المواد عبر منطقة جغرافية. طبق بودين وآخرون توجيه المركبات على مشكلة خدمة النقل عند الطلب. [ 7 ]

مشكلة ساعي البريد في المناطق الريفية

في بعض الحالات، تختلف مجموعة الحواف المطلوبة عن الحواف الموجودة في الرسم البياني. ويتم تمثيل ذلك بمسألة ساعي البريد الريفي (RPP)، [ 1 ] حيث تكون الحواف المطلوبة مجموعة فرعية من نظام الحواف.

الخوارزميات

يتطلب إيجاد حل فعال باستخدام كميات كبيرة من البيانات لمسألة ساعي البريد الصيني (CPP)، ومسألة ساعي البريد في الرياح (WPP)، ومسألة ساعي البريد الريفي (RPP)، ومسألة ساعي البريد الصيني k (KCPP)، ومسألة ساعي البريد الصيني المختلطة (MCPP)، ومسألة ساعي البريد الصيني الموجه (DCPP)، [ 8 ] ومسألة حرث المنحدرات (DPP)، ومسألة الحرث مع الأسبقية (PPP)، ومسألة ساعي البريد الريفي في الرياح (WRPP)، ومسألة التوجيه العام في الرياح (WGRP) استخدام مفاهيم رياضية مدروسة، بما في ذلك أساليب التحسين الاستدلالية ، وأساليب التفرع والتقييد ، والبرمجة الخطية الصحيحة ، وتطبيقات خوارزميات مسألة البائع المتجول مثل خوارزمية هيلد-كارب التي تُحسّن منيا(ن!){\displaystyle O(n!)}ليا(2نن2){\displaystyle O(2^{n}n^{2})}[ 9 ] بالإضافة إلى هذه الخوارزميات، يمكن أيضًا حل هذه الفئات من المسائل باستخدام خوارزمية القطع المستوي ، والتحسين المحدب ، والأغلفة المحدبة ، ومضاعفات لاغرانج ، وغيرها من أساليب البرمجة الديناميكية . في الحالات التي يتعذر فيها تشغيل خوارزمية هيلد-كارب نظرًا لتعقيدها الحسابي العالي، يمكن استخدام خوارزميات كهذه لتقريب الحل في وقت معقول. [ 10 ]

الدوائر الأويلرية

أقدم إشارة موثقة إلى مجال مسائل توجيه الأقواس هي تحدي جسور كونيغسبرغ الكلاسيكي، الذي أثبت أويلر استحالته. [ 4 ] أراد أحد سكان كونيغسبرغ ، التي تُعد الآن جزءًا من كالينينغراد ، إيجاد طريقة لعبور الجسور السبعة فوق نهر بريغل دون الرجوع إلى الوراء أو إعادة تتبع خطواته، أي عبور كل جسر مرة واحدة فقط. في عام 1736، اختزل أويلر المسألة إلى مسألة عقد وحواف، وأثبت استحالة حلها. وفي عام 1873، أجرى هيرهولتزر المزيد من الأبحاث حول مسألة الدوائر المغلقة. [ 4 ]

انتشر العمل على الدوائر الأويلرية في عدد يوليو 1953 من مجلة ساينتفك أمريكان . [ 11 ] وقد طوّر هذا العمل ميغو غوان، المعروف أيضًا باسم كوان مي-كو، في كلية شانغتون للمعلمين. كان ميغو غوان مهتمًا بمسألة مختلفة بدلًا من تحديد دائرة مغلقة. عمل غوان على إيجاد أقصر مسار يمر عبر كل حافة من حواف الرسم البياني مرة واحدة على الأقل. وصف غوان هدفه في عام 1962 قائلًا: "يتعين على ساعي البريد تغطية الجزء المخصص له قبل العودة إلى مكتب البريد. تكمن المشكلة في إيجاد أقصر مسافة سير لساعي البريد." [ 4 ]

أنواع المسائل

تختلف مسائل توجيه الأقواس (ARPs) في هدفها وأساليبها الاستدلالية. ومع ذلك، من المعروف أن جميعها مسائل صعبة من نوع NP .

مشكلة ساعي البريد الريفي غير الموجه

سُميت هذه المسألة نسبةً إلى ساعي البريد وتحديه المتمثل في توصيل البريد بأي ترتيب يختاره، مع تقليل تكاليفه، مثل الوقت ومسافة السفر. وتُعرف أحيانًا باسم مسألة ساعي البريد الصيني غير الموجه . تهدف مسألة ساعي البريد الريفي غير الموجه (URPP) إلى تقليل التكلفة الإجمالية لمسار يغطي الشبكة بأكملها، أو في حالات أكثر تحديدًا، مسار يغطي كل حافة تتطلب خدمة. إذا كان لا بد من تغطية الشبكة بأكملها، يُسمى المسار الذي يغطيها بجولة تغطية . أما في حالة الحاجة إلى تغطية حواف معينة فقط، فتهدف المسألة إلى إيجاد المسار الأمثل لتلبية الطلبات، مع تقليل عدد مرات المرور عبر المسارات غير المطلوبة. [ 12 ]

مشكلة توجيه الأقواس ذات السعة غير الموجهة

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

تاريخ

طُرحت مسألة توجيه الأقواس الموحدة (URPP) لأول مرة عام 1974، وأثبت لينسترا وكان أنها مسألة صعبة الحل (NP-hard ) . ويمكن اشتقاق مسألة توجيه الأقواس الموحدة (UCARP) من مسألة توجيه الأقواس الموحدة، وبالتالي فهي أيضاً مسألة صعبة الحل (NP-hard). وفي عام 1981، تمكن عالما الحاسوب غولدن وونغ من إثبات أن حتى اشتقاق تقريب بنسبة 0.5 لمسألة توجيه الأقواس الموحدة يُعد مسألة صعبة الحل (NP-hard). وفي عام 2000، نشر درور كتاباً يصف مسائل توجيه الأقواس المختلفة.

مشكلة ساعي البريد العاصف وأنواعها

تُعدّ مسألة ساعي البريد العاصف، التي اقترحها مينيكا، صيغةً معدّلة من مسألة فحص المسار، حيث يكون المدخل عبارة عن رسم بياني غير موجّه، ولكن قد تختلف تكلفة اجتياز كل حافة فيه في اتجاه عن تكلفتها في الاتجاه المعاكس. [ 13 ] وعلى عكس حلول الرسوم البيانية الموجّهة وغير الموجّهة، تُصنّف هذه المسألة ضمن فئة NP-complete . [ 14 ] [ 15 ] وتكون تكلفة السفر في اتجاه واحد أكبر عندما تهبّ الرياح في وجهك مقارنةً بالرياح التي تهب من خلفك، وهذا هو أصل تسمية مسألة ساعي البريد العاصف. فالجهد المبذول لاجتياز الشارع في اتجاه واحد يختلف عن الجهد المبذول لاجتيازه في اتجاه آخر في يوم عاصف. [ 8 ]

تُعدّ مسألة ساعي البريد العاصف مسألة توجيه الأقواس (ARP) التي تتضمن مسألة ساعي البريد الصيني المختلط (MCPP) كحالة خاصة. [ 16 ]

يمكن تعريف المشكلة على النحو التالي: "بالنظر إلى رسم بياني غير موجه ومتصل G=(V,E) بتكلفة غير سالبة."جأنا،ج{\displaystyle c_{i,j}}وجج،أنا{\displaystyle c_{j,i}}مرتبط بكل حافة{أنا،ج}∈هـ{\displaystyle \{i,j\}\in E}بما أن تكلفة اجتياز كل حافة من i إلى j، ومن j إلى i على التوالي، فإنّ مسألة ساعي البريد الريفي العاصف (WPP) تهدف إلى إيجاد مسار بأقل تكلفة على الرسم البياني G يمر بكل حافة مرة واحدة على الأقل. [ 16 ] وقد طرح مينيكا هذه المسألة. تُصنّف مسألة ساعي البريد الريفي العاصف (WPP) ضمن مسائل NP-كاملة بشكل عام، ويمكن حلّها في وقت متعدد الحدود إذا كان الرسم البياني G رسمًا بيانيًا أويلريًا، أو إذا كانت تكلفة اتجاهين متعاكسين لكل دورة في G متساوية، أو إذا كان G رسمًا بيانيًا متسلسلًا متوازيًا. تُعدّ مسألة ساعي البريد الريفي العاصف (WRPP) تعميمًا لمسألة ساعي البريد الريفي العاصف (WPP)، حيث لا يُشترط اجتياز جميع الحواف في الرسم البياني، بل فقط تلك الموجودة في مجموعة فرعية مُحدّدة من الحواف المطلوبة. على سبيل المثال، لا يُشترط على ساعي البريد عبور بعض الطرق الريفية، كما أن صعود بعض الطرق على التلال شديدة الانحدار يستغرق وقتًا أطول من نزولها. [ 10 ]

مسألة ساعي البريد الريفي العاصف (WRPP) هي تعميم لمسألة ساعي البريد الريفي العاصف (WPP)، حيث لا يُشترط عبور جميع حواف الرسم البياني، بل فقط تلك الموجودة في مجموعة فرعية مُحددة من الحواف المطلوبة. على سبيل المثال، لا يُشترط عبور بعض الطرق الريفية لساعي البريد، كما أن صعود بعض الطرق على التلال شديدة الانحدار يستغرق وقتًا أطول من نزولها. [ 10 ] لنفترض رسمًا بيانيًا غير مُوجه.جي={هـ،V}{\displaystyle G=\{E,V\}}مع تكلفتينجأناج{\displaystyle c_{ij}}وججأنا{\displaystyle c_{ji}}التكاليف المرتبطة باجتياز الحافة(أنا،ج){\displaystyle (i,j)}بدءًا من i و j على التوالي. G هو الرسم البياني المتعرج، ونحن مهتمون بمجموعة فرعية من الحواف، أو بالرموز الرياضية.هـR⊆هـ{\displaystyle E_{R}\subseteq E}.

إذا تضمنت مسألة WRPP قيدًا إضافيًا يقضي بضرورة زيارة مجموعة معينة من الرؤوس—VR⊆V{\displaystyle V_{R}\subseteq V}تتحول المشكلة إلى مشكلة التوجيه العام في الرياح (WGRP). اقترح بينافينت صياغة برمجة خطية عددية صحيحة وطرق استدلالية مختلفة وحدود دنيا لمشكلة التوجيه العام في الرياح. [ 9 ]

نشر بينافينت وآخرون تقييمًا لعدة طرق استدلالية تُستخدم لحل مسألة WRPP في غضون ثوانٍ قليلة بانحراف لا يتجاوز 1% عن الحد الأدنى على الرسوم البيانية متوسطة الحجم. وقد حسّنوا ذلك باستخدام خوارزمية البحث المبعثر التي قلّصت الفرق إلى 0.5%. ووجدت خوارزمية البحث المبعثر حلولًا بانحراف أقل من 2% عند تطبيقها على شبكات تضم مئات العقد وآلاف الحواف. [ 9 ]

في التطبيقات العملية، توجد مركبات متعددة يمكنها التحرك، مما يؤدي إلى تعميم يُسمى مسألة ساعي البريد الريفي ذي الرياح العاتية ذات عدد المركبات K (MM K-WRPP). تُعرَّف مسألة ساعي البريد الريفي ذي الرياح العاتية ذات عدد المركبات K (MM K-WRPP) على النحو التالي: بالنظر إلى رسم بياني عاصفجي={V،هـ}{\displaystyle G=\{V,E\}}، رأس مميز،1∈V{\displaystyle 1\in V}، الذي يمثل المستودع، مجموعة فرعية من الحواف المطلوبة هـR⊆هـ{\displaystyle E_{R}\subseteq E}مع عدد ثابت K من المركبات، تتلخص مسألة MM K-WRPP في إيجاد مجموعة من K مسارًا للمركبات بحيث تبدأ كل مسار وتنتهي عند المستودع، ويتم خدمة كل حافة مطلوبة بواسطة مركبة واحدة فقط. الهدف هو تقليل طول أطول مسار لإيجاد مجموعة من المسارات المتوازنة للمركبات. من التطبيقات العملية لمسائل التوجيه ذات أهداف الحد الأدنى والحد الأقصى: توجيه حافلات المدارس (ديلجادو وباتشيكو 2001)، وتوصيل الصحف إلى العملاء (أبليجيت وآخرون 2002)، وجمع النفايات (لاكوم وآخرون 2004). [ 10 ]

كانت أفضل خوارزمية MM K_WRPP قريبة جدًا من الحل الأمثل عند وجود مركبتين أو ثلاث مركبات، بفارق أقل من 0.4% في المتوسط. ويزداد هذا الفارق إلى حوالي 1.00% و1.60% عند وجود أربع وخمس مركبات على التوالي.

بحسب دوسولت وآخرون وبينافينت وآخرون، يمكن لخوارزمية التلدين المحاكي متعددة الأهداف (MOSA) حل القيود المختلفة المفروضة على مسألة توجيه الأقواس (WRPP). تُعدّ مسألة توجيه الأقواس مسألةً مهمةً تُعمّم العديد من مسائل توجيه الأقواس أحادية المركبة. في التطبيقات العملية للرياضيات، يُفضّل الحل الذي يُقلّل التكاليف الإجمالية لجميع مسارات المركبات وطول أطول مسار. من الصعب أن تكون في موقع تتأخر فيه شحنتك لساعات باستمرار. [ 8 ] ينبغي أن نبدأ بافتراض أن وجود عدة مركبات ذات سعة محددة وقابلة للقياس لخدمة العملاء أكثر واقعية من وجود مركبة واحدة ذات سعة غير قابلة للقياس. قام رباني وآخرون بقياس أداء خوارزميات ونماذج MOSA باستخدام تطوير متعدد الأهداف لخوارزمية بحث الوقواق - التي طورها يانغ وآخرون، [ 17 ] والتي تُعرف أيضًا باسم بحث الوقواق متعدد الأهداف ويُختصر إلى MOCS. [ ٨ ] وخلصوا إلى أن طرق MOSA أكثر كفاءة من طرق MOCS. وفي المستقبل، يمكن إجراء مقارنات مع طرق أخرى من طرق الاستدلال الميتا-هيروستيكي، بما في ذلك خوارزمية الفرز الجيني غير المهيمنة (NSGA)، وخوارزمية تحسين سرب الجسيمات متعددة الأهداف (MOPSO)، وخوارزمية المنافسة الإمبريالية متعددة الأهداف.

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

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

التطبيقات

تم اختزال العديد من المسائل التوافقية إلى مسألة ساعي البريد الصيني، بما في ذلك إيجاد القطع الأقصى في الرسم البياني المستوي ودائرة ذات طول متوسط ​​أدنى في الرسم البياني غير الموجه. [ 18 ]

كاسحات الثلج

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

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

بالنظر إلى الرسم البياني غير الموجهجي={V،أ}{\displaystyle G=\{V,A\}}أينV{\displaystyle V}هي مجموعة الرؤوس والعقد وأ{\displaystyle A}هي مجموعة الأقواس. كل قوس ممثل بـ(vأنا،vج){\displaystyle (v_{i},v_{j})}له أربعة تكاليف:جأناج+{\displaystyle c_{ij}^{+}}، والتي تُعرَّف بأنها تكلفة حرث الأرض منvأنا{\displaystyle v_{i}}لvج{\displaystyle v_{j}}،ججأنا+{\displaystyle c_{ji}^{+}}، تكلفة الحراثة منvج{\displaystyle v_{j}}لvأنا{\displaystyle v_{i}}،جأناج-{\displaystyle c_{ij}^{-}}تكلفة السفر بدون ركاب منvأنا{\displaystyle v_{i}}لvج{\displaystyle v_{j}}، وججأنا-{\displaystyle c_{ji}^{-}}تكلفة السفر بدون ركاب منvج{\displaystyle v_{j}}لvأنا{\displaystyle v_{i}}يفترض هذا الإعداد أنvج{\displaystyle v_{j}}يتميز بارتفاع أعلىvأنا{\displaystyle v_{i}}مما يؤدي إلى البيان التالي:جأناج+≫ججأنا+≫جأناج-≥ججأنا-{\displaystyle c_{ij}^{+}\gg c_{ji}^{+}\gg c_{ij}^{-}\geq c_{ji}^{-}}عمليًا، يكون وقت الحراثة عند النزول ضعف وقت الحراثة عند الصعود، كما أن إزالة الأوراق الميتة ضعف وقت الحراثة. تجد الخوارزميةك{\displaystyle k}ستبدأ كل مسارات الرحلات وتنتهي عند المستودع.v0{\displaystyle v_{0}}، قم بحرث القوس مرتين لأن الجانب الأيسر والجانب الأيمن من الشارع يتطلبان مرورين للحرث.

الحل الأمثل هو الذي يقلل من أقصى طول للمسار. وقد وجد دوسولت وغولدن وواسيل خوارزمية لم تتجاوز الحد الأدنى بنسبة 5.5% في أكثر من 80 تجربة. ازداد الانحراف مع ازدياد تعقيد النموذج، وذلك لوجود عدد أكبر من التقريبات غير المُحسَّنة مقارنةً بالتقريبات المُحسَّنة مع نمو النموذج. قد يتضمن تحسين خوارزمية DPP الخاصة بدوسولت وآخرين فرض عقوبات على الانعطافات على شكل حرف U والانعطافات يسارًا، أو عبور التقاطع مباشرةً، مما يستغرق وقتًا إضافيًا ويدفع الثلج إلى منتصف التقاطع، على التوالي. (انظر مسألة ساعي البريد الريفي الموجه مع عقوبات الانعطاف، والتي يُشار إليها غالبًا باسم DRPP-TP أدناه).

مشكلة ساعي البريد الصيني ( k - CPP)

يمكن صياغة مسألة ساعي البريد الصيني من الرتبة k على النحو التالي: "بالنظر إلى رسم بياني متصل ذي أوزان حواف G ، وعددين صحيحين p و k ، حدد ما إذا كان هناك على الأقل k مسار مغلق بحيث يكون كل ضلع من أضلاع G موجودًا في واحد منها على الأقل، ويكون الوزن الإجمالي للأضلاع في هذه المسارات على الأكثر p ؟" تُعد عملية الحصول على حل مسألة ساعي البريد الصيني من الرتبة k مسألة NP كاملة. وقد أثبت غوتين، وموتشياتشيا، ويو في عام 2013 أن مسألة ساعي البريد الصيني من الرتبة k قابلة للحل باستخدام معلمات ثابتة. [ 19 ] ويثبت المؤلفون أن مسألة ساعي البريد الصيني من الرتبة k تقبل نواة معيا(ك2سجل⁡(ك)){\displaystyle O(k^{2}\log(k))}الرؤوس والنسخة الموجهة من k -CPP هي NP كاملة.

مشكلة ساعي البريد الريفي (RPP) وتعميماتها

تُفرض مسألة ساعي البريد الريفي (RPP) مساراتٍ إلزامية ومطلقة، لكن ليس على الشخص الذي يجتاز الرسم البياني أن يسلك اتجاهًا واحدًا مُحددًا. تُصنف مسألة ساعي البريد الريفي ضمن المسائل الصعبة حسابيًا (NP-hard) والكاملة، تمامًا كما هو الحال مع مسائل kCPP وDPP وPPP. درس بينيفانت تعميمًا لهذه المسألة يُسمى مسألة ساعي البريد الريفي الموجهة مع عقوبات الانعطاف (DRPP-TP). [ 20 ] وقد قاربت خوارزمية بينيفانت الحل بتحويل مسألة DRPP-TP إلى مسألة بائع متجول غير متناظرة (ATSP).

الأساليب الاستدلالية والخوارزميات

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

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

تتضمن طرق حل مشكلة URPP بعد إجراء المعالجة المسبقة خوارزمية مستوى القطع ومنهجية التفرع والقطع . [ 21 ]

تعقيد

هذه قائمة بالتعقيدات الحسابية لمشاكل توجيه الأقواس المختلفة.

متغير CPالتعقيد الكلاسيكيتقريبالتعقيد المُعَلم
غير موجهيا(|V|3){\displaystyle O(|V|^{3})}خوارزمية الوقت [ 22 ]
إخراجيا(|V|3){\displaystyle O(|V|^{3})}خوارزمية الوقت [ 22 ]

يا((|هـ|-|V|)|V|2){\displaystyle O((|E|-|V|)|V|^{2})}خوارزمية الوقت [ 23 ]

مختلطNP-complete [ 24 ]

يا(|V|3){\displaystyle O(|V|^{3})}يمكن حلها في زمن معين إذا كانت درجة كل رأس زوجية [ 22 ]

يا(الأعلى{|V|3،|أ|(الأعلى{|أ|،|هـ|})2}){\displaystyle O(\max\{|V|^{3},|A|(\max\{|A|,|E|\})^{2}\})}عامل الزمن 3/2 [ 25 ]يا(2|هـ|⋅|V|3){\displaystyle O(2^{|E|}\cdot |V|^{3})}خوارزمية الوقت [ 26 ]

في FPT بالنسبة إلى |A| [ 26 ]

في البرمجة المتطرفة فيما يتعلق بعرض الشجرة [ 27 ]

عاصفNP-complete [ 28 ]

P في بعض الحالات الخاصة [ 28 ] [ 29 ]

العامل 3/2 [ 30 ]
التسلسل الهرمي kNP-complete [ 31 ]

يا(ك|V|4){\displaystyle O(k|V|^{4})}يمكن حل المسألة في زمن محدد إذا كانت علاقة الأسبقية خطية.

مين-سوم ك ساعي بريديا(|V|3){\displaystyle O(|V|^{3})}خوارزمية زمنية مع رأس مكتب البريد، [ 32 ] وإلا فهي كاملة NP [ 33 ]في FPT بالنسبة إلى k بدون رأس مكتب البريد [ 34 ]
الحد الأدنى والحد الأقصى لعدد ساعي البريدNP-complete [ 35 ]يا(|V|3){\displaystyle O(|V|^{3})}-عامل الزمن (2-1/ك) [ 35 ]

قائمة بأنواع توجيه القوس

مشكلةاختصاروصفملاحظات المخرجاتأمثلة
مشكلة توجيه القوسARPحدد مسارًا بأقل تكلفة لمجموعة فرعية محددة من أقواس الرسم البياني، مع أو بدون قيود. [ 36 ]جسور كونيغسبرغ السبعة
مشكلة ساعي البريد الصينيCPPرسم بياني غير موجه G ذو رؤوس V وحواف مرجحة Eاجتاز كل حافة مرة واحدة على الأقل بأقل تكلفة"يتعين على ساعي البريد تغطية الجزء المخصص له قبل العودة إلى مكتب البريد. تكمن المشكلة في إيجاد أقصر مسافة سير لساعي البريد." [ 37 ]
مشكلة ساعي البريد الريفيRPPرسم بياني غير موجه G ذو رؤوس V وحواف مرجحة Eاجتز مجموعة فرعية من الحواف E مرة واحدة على الأقل بأقل تكلفة
مشكلة ساعي البريد الريفي الموجهDRPP
مشكلة ساعي البريد الريفي مع غرامات الانعطافRPP-TP، RPPTP
مشكلة ساعي البريد العاصفWPP [ 38 ]
مشكلة ساعي البريد الريفي في المناطق العاصفةWRPP
مشكلة عمال تنظيف الشوارعSPP
مشكلة الحراثةm-PP
مشكلة المحراث ذي السعة الكهربائيةسي-بي بي
مشكلة المحراث المنحدرDPP [ 39 ]
مشكلة المحراث المنحدر مع عقوبات الانعطافDPP-TP [ 39 ] [ 40 ]
مشكلة محراث المنحدرات الريفية مع عقوبات الانعطافRDPP-TP
مشكلة توجيه القوس ذي السعةسمك الشبوط
مشكلة ساعي البريد الريفي في ظل الرياح العاتيةk-WRPP
مشكلة المحراث الهابط ذي الحد الأدنى والحد الأقصى مع عدة محاريثMM k-DPP
مشكلة ساعي البريد الريفي العاصف (Min-Max)MM k-WRPP
مشكلة الحراثة ذات الأسبقيةبرنامج الشراكة بين القطاعين العام والخاص
مسألة المحراث المنحدر الممتد من نوع Min-MaxMM k-DPPE
مشكلة ساعي البريد الصيني ذي السعة المحدودةCCPP
مشكلة ساعي البريد الصيني الموجهةDCPP
مشكلة ساعي البريد الريفي الموجهDRPP
مشكلة توجيه القوس ذي السعة الممتدةإيكارب
مشكلة ساعي البريد الصيني الهرميةبرنامج الرعاية الصحية الأولية
مشكلة توجيه القوس الكهربائي ذي السعة المختلطةMCARP
مشكلة ساعي البريد الصيني المختلطMCPP
مشكلة رافعة التكديسمؤسسة SCPيجب اجتياز بعض الأقواس مرة واحدة على الأقل في اتجاه واحد، ولكن يمكن اجتيازها عدة مرات في الاتجاه الآخر.
مشكلة البائع المتجولTSP
مشكلة توجيه القوس ذي السعة غير الموجهةUCARP
مشكلة ساعي البريد الريفي غير الموجهURPP
مشكلة في توجيه المركباتVRP
مشكلة ساعي البريد الريفي متعدد المستودعات (Min-Max)MMMDRPP [ 1 ]
مشكلة توجيه المركبات العامةGVRP [ 41 ]

انظر أيضاً

مراجع

  1. 1 2 3 4 5 تشين، هوانفا؛ تشنغ، تاو؛ شاو-تايلور، جون (2018-01-02). "تصميم مسار متوازن لمسألة ساعي البريد الريفي متعدد المستودعات (MMMDRPP): حالة دورية شرطة" . المجلة الدولية لعلوم المعلومات الجغرافية . 32 (1): 169-190 . Bibcode : 2018IJGIS..32..169C . doi : 10.1080/13658816.2017.1380201 . ISSN 1365-8816 . S2CID 29526595 .  
  2. 1 2 3 4 عمر، مسعود (2007). "التوجيه الفعال لمركبات إزالة الثلوج" .
  3. 1 2 3 4 دوسولت، بنيامين؛ جولدن، بروس؛ واسيل، إدوارد (أكتوبر 2014). "مشكلة المحراث المنحدر مع عدة محاريث" . مجلة جمعية بحوث العمليات . 65 (10): 1465-1474 . doi : 10.1057/jors.2013.83 . ISSN 0160-5682 . S2CID 36977043 .  
  4. 1 2 3 4 إيزلت، هـ. أ.؛ جيندرو، ميشيل؛ لابورت، جيلبرت (أبريل 1995). "مسائل توجيه الأقواس، الجزء الأول: مسألة ساعي البريد الصيني" . بحوث العمليات . 43 (2): 231-242 . doi : 10.1287/opre.43.2.231 . hdl : 11059/14013 . ISSN 0030-364X . 
  5. ↑ ديلجادو سيرنا، كريستينا ر.؛ باتشيكو بونروسترو، خواكين (2001)، "مسائل توجيه المركبات من نوع مينماكس: تطبيق على النقل المدرسي في مقاطعة بورغوس" ، في فوس، ستيفان؛ دادونا، يواكيم ر. (محرران)، جدولة النقل العام بمساعدة الحاسوب ، برلين، هايدلبرغ: سبرينغر، ص 297-317 ، doi : 10.1007/978-3-642-56423-9_17 ، ISBN  978-3-642-56423-9تم الاطلاع عليه بتاريخ 2022-05-01
  6. ↑ بودين، لورانس؛ جولدن، بروس (1981). "التصنيف في توجيه المركبات وجدولة الرحلات" . الشبكات . 11 (2): 97-108 . doi : 10.1002/net.3230110204 .
  7. ↑ بودين، لورانس د.؛ سيكستون، توماس ر. (فبراير 1983). مشكلة خدمة النقل حسب الطلب لمشتركي المركبات المتعددة (تقرير فني). كلية الدراسات العليا البحرية. hdl : 10945/63226 . NPS55-83-002.
  8. 1 2 3 4 رباني، مسعود؛ علمدار، صفورة فاميل؛ فرخي أصل، حامد (2016-02-01). "مسألة ساعي البريد الريفي ذي السعة المحدودة والرياح القوية مع عدة مركبات: خوارزمية محاكاة التلدين متعددة الأهداف الهجينة" (ملف PDF) . المجلة الدولية لإدارة التوريد والعمليات . 2 (4): 1003-1020 . doi : 10.22034/2015.4.03 . ISSN 2383-1359 . 
  9. 1 2 3 بينافينت، إي؛ كوربيران، أ.؛ بينيانا، إي. بلانا، أنا. Sanchis، JM (ديسمبر 2005)، “خوارزميات إرشادية جديدة لمشكلة ساعي البريد الريفية العاصفة” ، بحوث الكمبيوتر والعمليات ، 32 (12): 3111–28 ، دوى : 10.1016/j.cor.2004.04.007 ، hdl : 10251/94488
  10. 1 2 3 4 بينافينت، إنريكي؛ كوربيران، أنخيل؛ سانشيس، خوسيه م. (يوليو 2010). "خوارزمية فوقية لحل مشكلة ساعي البريد الريفي ذي الرياح العاتية من نوع min-max مع K مركبة" . علوم الإدارة الحاسوبية . 7 (3): 269-287 . doi : 10.1007/s10287-009-0119-2 . hdl : 10251/100790 . ISSN 1619-697X . S2CID 41426793 .  
  11. ↑ "ليونهارد أويلر وجسور كونيغسبرغ" . مجلة ساينتفك أمريكان . يوليو 1953. تاريخ الاسترجاع: 30 أبريل 2022 .
  12. 1 2 H. A.، إيزلت؛ ميشيل، جيندرو (1995). "مسائل توجيه الأقواس، الجزء الثاني: مسألة ساعي البريد الريفي" . بحوث العمليات . 43 (3): 399-414 . doi : 10.1287/opre.43.3.399 .
  13. ↑ مينيكا، إدوارد (يوليو 1979). "مشكلة ساعي البريد الصيني للشبكات المختلطة" . مجلة علوم الإدارة . 25 (7): 643-648 . doi : 10.1287/mnsc.25.7.643 .
  14. ↑ غوان، ميغو (1984)، "حول مسألة ساعي البريد العاصف"، الرياضيات التطبيقية المنفصلة ، ​​9 (1): 41-46 ، doi : 10.1016/0166-218X(84)90089-1 ، MR 0754427 .
  15. ^ لينسترا، جي كيه؛ رينوي كان، AHG (1981)، “تعقيد توجيه المركبات ومشاكل الجدولة” (PDF) ، الشبكات ، 11 (2): 221–7 ، دوى : 10.1002/net.3230110211
  16. 1 2 3 كوربيران، أنجيل؛ أوزوالد، ماركوس؛ بلانا، إسحاق؛ رينيلت، جيرهارد؛ سانشيز، خوسيه م. (أبريل 2012). "نتائج جديدة حول مسألة ساعي البريد ذي الرياح" . البرمجة الرياضية . 132 ( 1-2 ): 309-332 . doi : 10.1007/s10107-010-0399-x . hdl : 10251/150344 . ISSN 0025-5610 . S2CID 12808962 .  
  17. ↑ يانغ، شين-شي (2010). "تحسين الهندسة باستخدام خوارزمية البحث عن الوقواق". المجلة الدولية للنمذجة الرياضية والتحسين العددي . 1 (4) 35430: 330-343 . arXiv : 1005.2908 . doi : 10.1504/IJMMNO.2010.035430 . S2CID 34889796 . 
  18. ↑ أ. شريجفر، التحسين التوافقي، متعددات السطوح والكفاءة، المجلد أ، سبرينغر. (2002).
  19. ↑ غوتين، غريغوري؛ موتشياشيا، غابرييل؛ يو، أندرس (18-11-2013). "التعقيد المُعَلم لمسألة ساعي البريد الصيني من الرتبة k " . علوم الحاسوب النظرية . 513 : 124-128 . arXiv : 1308.0482 . doi : 10.1016/j.tcs.2013.10.012 . ISSN 0304-3975 . S2CID 2867281 .  
  20. ↑ بينافينت، إنريكي؛ سولير، ديفيد (نوفمبر 1999). "مشكلة ساعي البريد الريفي الموجه مع عقوبات الانعطاف" . علوم النقل . 33 (4): 408-418 . doi : 10.1287/trsc.33.4.408 . ISSN 0041-1655 . 
  21. ↑ هيرتز، آلان. “الاتجاهات الحديثة في توجيه القوس” (PDF) . مدرسة البوليتكنيك - جيراد.
  22. إدموندز ، جاك؛ جونسون، إليس ل. (1973). " المطابقة، وجولات أويلر، وساعي البريد الصيني" . البرمجة الرياضية . 5 ( 1): 88-124 . doi : 10.1007/bf01580113 . ISSN 0025-5610 . S2CID 15249924 .  
  23. ↑ ياكسيونغ، لين؛ يونغتشانغ، تشاو (يناير 1988). "خوارزمية جديدة لمسألة ساعي البريد الصيني الموجه" . الحوسبة وبحوث العمليات . 15 (6): 577-584 . doi : 10.1016/0305-0548(88)90053-6 . ISSN 0305-0548 . 
  24. ↑ باباديميتريو، كريستوس هـ. (يوليو 1976). "حول تعقيد اجتياز الحواف" . مجلة ACM . 23 (3): 544-554 . doi : 10.1145/321958.321974 . ISSN 0004-5411 . S2CID 8625996 .  
  25. ↑ راغافاتشاري، بالاجي؛ فيراسوامي، جياكيسافان (يناير 1999). "خوارزمية تقريبية بنسبة 3/2 لمسألة ساعي البريد المختلطة" . مجلة SIAM للرياضيات المتقطعة . 12 (4): 425-433 . doi : 10.1137/s0895480197331454 . ISSN 0895-4801 . 
  26. 1 2 غوتين، غريغوري؛ جونز، مارك؛ شينغ، بين (2014)، "التعقيد البارامتري لمسألة ساعي البريد الصيني k-Arc" ، الخوارزميات - ESA 2014 ، برلين، هايدلبرغ: سبرينغر برلين هايدلبرغ، ص 530-541 ، arXiv : 1403.1512 ، doi : 10.1007/978-3-662-44777-2_44 ، ISBN  978-3-662-44776-5، S2CID 3472348 ، تم الاسترجاع بتاريخ 2022-05-09 
  27. ↑ فيرنانديز، كريستينا ج.؛ لي، أورلاندو؛ واكاباياشي، يوشيكو (يناير 2009). "مسائل التغطية الدورية الدنيا ومسائل ساعي البريد الصيني على الرسوم البيانية المختلطة ذات عرض الشجرة المحدود" . الرياضيات التطبيقية المنفصلة . 157 (2): 272-279 . doi : 10.1016/j.dam.2007.10.032 . ISSN 0166-218X . 
  28. 1 2 غوان، ميغو (سبتمبر 1984). "حول مسألة ساعي البريد العاصف" . الرياضيات التطبيقية المتقطعة . 9 (1): 41-46 . doi : 10.1016/0166-218x(84)90089-1 . ISSN 0166-218X . 
  29. ↑ وين، زاو (مايو 1989). "حول مسألة ساعي البريد العاصف على الرسوم البيانية الأويلرية" . البرمجة الرياضية . 44 ( 1-3 ): 97-112 . doi : 10.1007/bf01587080 . ISSN 0025-5610 . S2CID 206800125 .  
  30. ↑ فيراسوامي، جياكيسافان (1999). خوارزميات التقريب لمسائل ساعي البريد (أطروحة دكتوراه). جامعة تكساس في دالاس.
  31. ↑ درور، موشيه؛ ستيرن، هيلمان؛ ترودو، بيير (1987). "جولة ساعي البريد على رسم بياني مع علاقة أسبقية على الأقواس" . الشبكات . 17 (3): 283-294 . doi : 10.1002/net.3230170304 . ISSN 0028-3045 . 
  32. ↑ "المؤتمر العالمي الثاني عشر للحاسوب - مؤتمر الاتحاد الدولي لمعالجة المعلومات 1992" . الحوسبة في الصناعة . 20 (1): 124-126 . يناير 1992. doi : 10.1016/0166-3615(92)90137-c . ISSN 0166-3615 . 
  33. ↑ توماسِن، كارستن (يونيو 1997). "حول تعقيد إيجاد غطاء الدورة الأدنى للرسم البياني" . مجلة SIAM للحوسبة . 26 (3): 675-677 . doi : 10.1137/s0097539794267255 . ISSN 0097-5397 . 
  34. ↑ كوربيران، أنخيل (2015).توجيه الأقواس: المشاكل والأساليب والتطبيقاترقم الكتاب المعياري الدولي ( ISBN) 978-1-61197-366-2.
  35. 1 2 فريدريكسون، جريج ن.؛ هيشت، ماثيو س.؛ كيم، تشول إي. (مايو 1978). "خوارزميات تقريبية لبعض مسائل التوجيه" . مجلة SIAM للحوسبة . 7 (2): 178-193 . doi : 10.1137/0207017 . ISSN 0097-5397 . S2CID 7562375 .  
  36. ↑ إيزلت، هـ (مايو 1995). "مشاكل توجيه الأقواس، الجزء الثاني: مشكلة ساعي البريد الريفي" . ص 399. بروكويست 219174102 .  
  37. ↑ غوان، ميغو (1962). "البرمجة الرسومية باستخدام النقاط الفردية أو الزوجية". الرياضيات الصينية .
  38. ↑ دوسولت، بنيامين؛ غولدن، بروس؛ غروير، كريس؛ واسيل، إدوارد (2013-04-01). "الحرث مع مراعاة الأسبقية: صيغة معدلة لمسألة ساعي البريد العاصف" . الحوسبة وبحوث العمليات . 40 (4): 1047-1059 . doi : 10.1016/j.cor.2012.10.013 . ISSN 0305-0548 . 
  39. 1 2 دوسولت، بنيامين؛ جولدن، بروس؛ واسيل، إدوارد (2014-10-01). "مشكلة المحراث المنحدر مع عدة محاريث" . مجلة جمعية بحوث العمليات . 65 (10): 1465-1474 . doi : 10.1057/jors.2013.83 . ISSN 1476-9360 . S2CID 36977043 .  
  40. ↑ دوسو، بنيامين (2012). "نمذجة وحل مشاكل توجيه الأقواس في كنس الشوارع وإزالة الثلوج" . بروكويست .
  41. ↑ غياني، جيانباولو؛ إمبورتا، جينارو (2000-04-01). "تحويل فعال لمسألة توجيه المركبات المعممة" . المجلة الأوروبية لبحوث العمليات . 122 (1): 11-17 . doi : 10.1016/S0377-2217(99)00073-9 . ISSN 0377-2217 .