خيارات التوجيه

يصف هذا القسم بعض خيارات أداة حل التوجيه.

حدود البحث

تؤدي حدود البحث إلى إنهاء أداة الحلّ بعد الوصول إلى الحدّ المحدّد، مثل الحد الأقصى لطول المدة أو عدد الحلول التي يتم العثور عليها. يمكنك ضبط حد بحث من خلال معلَمات البحث الخاصة بأداة الحل. يمكنك الاطّلاع على الحدود الزمنية المسموح بها للحصول على مثال.

يصف الجدول التالي حدود البحث الأكثر شيوعًا.

الاسم	Type	القيمة التلقائية	الوصف
solution_limit	int64	كينت 64max	يقتصر على عدد الحلول التي يتم إنشاؤها أثناء البحث
time_limit.seconds	int64	كينت 64max	الحد بالثواني إلى الوقت المستغرَق : في البحث.
lns_time_limit.seconds	int64	100	الحد بالثواني إلى الوقت الذي تم قضاؤه في : عملية البحث المكتملة لكل مجاور بحث محلي

استراتيجية الحلّ الأولى

استراتيجية الحل الأولى هي الطريقة التي تستخدمها أداة الحلّ للعثور على حلّ مبدئي. يسرد الجدول التالي خيارات first_solution_strategy.

Option	الوصف
AUTOMATIC	يتيح أداة الحلّ اكتشاف الاستراتيجية التي سيتم استخدامها وفقًا للنموذج الذي يتم حلّه.
PATH_CHEAPEST_ARC	بدءًا من العقدة "بدء"، عليك توصيلها بالعُقدة التي ينتج عنها شريحة المسار الأقل تكلفة، ثم توسيع المسار من خلال تكرار العُقدة الأخيرة التي تمت إضافتها إلى المسار.
PATH_MOST_CONSTRAINED_ARC	يشبه PATH_CHEAPEST_ARC، ولكن يتم تقييم الأقواس باستخدام أداة اختيار مستندة إلى المقارنة، وبالتالي سيتم تفضيل القوس الأكثر تقييدًا أولاً. لتخصيص أداة اختيار لنموذج التوجيه، استخدِم طريقة ArcIsMoreConstrainedThanArc().
EVALUATOR_STRATEGY	يشبه PATH_CHEAPEST_ARC، باستثناء أنّ تكاليف القوس يتم تقييمها باستخدام الدالة التي تم تمريرها إلى SetFirstSolutionEvaluator().
SAVINGS	خوارزمية التوفير (Clarke & Wright) مرجع كلارك، ج. & Wright, J.W. "جدولة المركبات من مستودع رئيسي إلى عدد من نقاط التسليم" ، أبحاث العمليات، مجلد 12, 1964، الصفحة 568-581.
SWEEP	خوارزمية المسح الضوئي (Wren وHoliday). الإشارة إلى "أنتوني رين" و"آلان هوليداي" لأجهزة الكمبيوتر من واحد أو أكثر من مستودعات إلى عدد من عمليات التشغيل التشغيلية ربع سنوي (1970-1977)، مجلد 23، رقم 3 (أيلول (سبتمبر) 1972)، صفحة 333-344.
CHRISTOFIDES	خوارزمية "كريستوفس" (في الواقع هي صيغة من خوارزمية "كريستوفديس" باستخدام مطابقة مطابِقة بدلاً من مطابقة قصوى)، ما لا يضمن عامل 3/2 من التقدير التقريبي لمندوب مبيعات متنقّل حسب المقياس يعمل على نماذج التوجيه العامة للمركبات من خلال تمديد مسار حتى لا يمكن إدراج عُقد عليه. تتمثّل مرجع "نيكو كريستوفيس" في تحليل أسوأ حالات الحالات الإرشادية الجديدة لمشكلة رجل المبيعات المسافرين، التقرير 388، المدرسة العليا العليا في الإدارة الصناعية، CMU، 1976.
ALL_UNPERFORMED	جعل جميع العُقد غير نشطة. ولا يتم العثور على حل إلا إذا كانت العُقد اختيارية (وهي أحد عناصر التقييد الذي يفرضه الفصل مع تكلفة محدودة للعقوبة).
BEST_INSERTION	ويمكنك بشكل منتظم إنشاء حلّ من خلال إدخال عقدة أرخص في موضعها الأرخص. وتستند تكلفة الإدراج إلى دالة التكلفة العالمية لنموذج التوجيه. اعتبارًا من عام 2022، لن تعمل هذه الميزة إلا على النماذج التي تتضمن عُقدًا اختيارية (مع تكاليف محدودة للعقوبات).
PARALLEL_CHEAPEST_INSERTION	أنشِئ حلاً مُكرَّرًا من خلال إدراج عقدة أرخص في موضعها الأقلّ تكلفة. وتستند تكلفة الإدراج إلى دالة التكلفة المتعلّقة بالقوس. أسرع من BEST_INSERTION.
LOCAL_CHEAPEST_INSERTION	ويمكنك بشكل منتظم إنشاء حلّ من خلال إدراج كل عقدة في موضعها الأرخص. وتستند تكلفة الإدراج إلى دالة التكلفة القوسية. ويختلف عن PARALLEL_CHEAPEST_INSERTION حسب العقدة التي تم اختيارها لإدراجها، ويتم وضع العُقد هنا في ترتيب إنشائها. أسرع من PARALLEL_CHEAPEST_INSERTION.
GLOBAL_CHEAPEST_ARC	وصِّل عقدتَين بشكل مكرر ينتجان شريحة المسار الأقل تكلفة.
LOCAL_CHEAPEST_ARC	اختَر العقدة الأولى التي تليها بدون ربط، وربطها بالعقدة التي تنتج أرخص مسار.
FIRST_UNBOUND_MIN_VALUE	اختَر العُقدة الأولى التي تحتوي على خلفية غير مرتبطة ووصِّلها بالعقدة المتاحة الأولى. هذا يعادل استراتيجية CHOOSE_FIRST_UNBOUND مع ASSIGN_MIN_VALUE (cf. constraint_solver.h).

حالة البحث

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

print("Solver status: ", solver.status())

يؤدي هذا إلى طباعة عدد صحيح مع المعاني التالية:

القيمة	الوصف
0	ROUTING_NOT_SOLVED: لم يتم حل المشكلة بعد.
1	ROUTING_SUCCESS: تم حل المشكلة بنجاح.
2	ROUTING_PARTIAL_SUCCESS_LOCAL_OPTIMUM_NOT_REACHED: تم حل المشكلة بنجاح بعد الاتصال بـ RoutingModel.Solve()، باستثناء أنه لم يتم الوصول إلى تحسين محلي. يسمح لك تخصيص المزيد من الوقت بتحسين الحل.
3	ROUTING_FAIL: لم يتم العثور على حل للمشكلة.
4	ROUTING_FAIL_TIMEOUT: تم الوصول إلى الحدّ الزمني المسموح به قبل العثور على حلّ.
5	ROUTING_INVALID: الطراز أو معلمات النموذج أو العلامات غير صالحة.
6	ROUTING_INFEASIBLE: ثبت أنها غير قابلة للتنفيذ.

خيارات البحث المحلي

يسرد الجدول التالي خيارات لاستراتيجيات البحث المحلي (تُعرف أيضًا باسم البيانات الوصفية). اطّلِع على القسم تغيير استراتيجية البحث للحصول على أمثلة حول ضبط هذه الخيارات.

Option	الوصف
AUTOMATIC	تتيح أداة الحلّ اختيار المتغيّر الوصفي.
GREEDY_DESCENT	تقبل إجراء تحسينات على الجيران المحليين في شبكة البحث (خفض التكلفة) إلى أن يتم تحقيق الحد الأدنى المحلي.
GUIDED_LOCAL_SEARCH	استخدام البحث المحلي الإرشادية للهروب من الحد الأدنى المحلي. (cf. البحث المحلي الموجَّه) يُعد هذا عادةً أكثر الطرق متماثلة لتوجيه المركبات.
SIMULATED_ANNEALING	يُستخدم محاكاة التلذّب للهروب من الحد الأدنى المحلي (cf. محاكاة المحاكاة)).
TABU_SEARCH	استخدام ميزة "البحث باستخدام مفتاح التبويب (Tab)" للخروج من القيمة المصغّرة المحلية (cf. Searchu Search)
GENERIC_TABU_SEARCH	يتم استخدام بحث Tabu حول القيمة الموضوعية للحل لتجنُّب الحد الأدنى من النتائج المحلية.

التحكم في النشر

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