الأبعاد

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

يوضّح هذا القسم كيفية تحديد السمات واستخدامها.

أمثلة على السمات

في ما يلي بعض الأمثلة على السمات من الأقسام السابقة.

• ينشئ مثال VRPTW سمة لتتبعها المدة التراكمية للسفر لكل مركبة. تستخدِم أداة الحلّ السمة لفرض السياسة. القيد الذي ينص على أن المركبة يمكنها زيارة موقع ما داخل موقع الإطار الزمني.

• ينشئ مثال CVRP بُعدًا الطلبات (مثل الأوزان أو أحجام الحزم التي سيتم استلامها)، والتي يتم من خلالها تتبع الحمولة التراكمية التي تسيرها المركبة على طول مسارها. تستخدِم أداة الحلّ البُعد لفرض القيد الذي يفرضه تحميل المركبة. لا يمكن أن تتجاوز سعته.

تحدِّد الأمثلة التالية بُعدًا لـ VRPTW باستخدام AddDimension .

Python

routing.AddDimension(
    callback_index,
    slack_max,
    capacity,
    fix_start_cumul_to_zero,
    dimension_name)

C++‎

routing.AddDimension(
    callback_index,
    slack_max,
    capacity,
    fix_start_cumul_to_zero,
    dimension_name)

Java

routing.addDimension(
    callbackIndex,
    slackMax,
    capacity,
    fixStartCumulToZero,
    dimensionName)

#C

routing.AddDimension(
    callbackIndex,
    slackMax,
    capacity,
    fixStartCumulToZero,
    dimensionName)

تحتوي طريقة AddDimension على المدخلات التالية:

• callback_index: فهرس طلب معاودة الاتصال الذي يعرض الكمية تشير رسالة الأشكال البيانية يتم إنشاء الفهرس، الذي يُعد مرجعًا داخليًا لأداة الحلّ إلى معاودة الاتصال، بواسطة طرق مثل RegisterTransitCallback أو RegisterUnitaryTransitCallback.
• slack_max: الحد الأقصى لـ slack، وهو متغير يستخدم لتمثيل الانتظار أوقات في المواقع. يُرجى الاطّلاع على متغيّرات Slack أدناه للحصول على التفاصيل. إذا لم تكن المشكلة تشمل وقت الانتظار، يمكنك عادةً ضبط slack_max. إلى 0.
• capacity: الحدّ الأقصى للكمية الإجمالية المتراكمة على كل مسار يمكنك استخدام capacity لإنشاء قيود مثل القيود في CVRP. إذا لم تكن مشكلتك مرتبطة يمكنك ضبط capacity على قيمة كبيرة بما يكفي ولا تفرض أي قيود على المسارات — مثل جمع كل إدخالات المصفوفة أو الصفيفة المستخدمة لتحديد عملية رد الاتصال.
• fix_start_cumulative_to_zero: قيمة منطقية إذا كانت القيمة هي true، سيتم تطبيق القيمة التراكمية من الكمية يبدأ بـ 0. وفي معظم الحالات، يجب ضبطها على True. ومع ذلك، بالنسبة إلى VRPTW أو مشاكل في قيود الموارد، بعض المركبات قد تضطر إلى البدء بعد الوقت 0 بسبب قيود الإطار الزمني، لذلك يجب عليك قم بتعيين fix_start_cumulative_to_zero على False لهذه المسائل.
• dimension_name: سلسلة لاسم السمة، مثل 'Distance'، والذي يمكنك استخدامه للوصول إلى المتغيرات في مكان آخر في البرنامج.

ينشئ برنامج CVRP نوعًا مختلفًا قليلاً من السمات باستخدام AddDimensionWithVehicleCapacity . تستخدم هذه الطريقة صفيفًا من السعات، مع إدخال واحد لكل مركبة. (في المقابل، تأخذ AddDimension قيمة واحدة لـ capacity، وبالتالي المركبات التي لها السعة نفسها).

يمكنك الاطّلاع على RoutingModel. مرجعية للطرق الأخرى التي تنشئ الأبعاد.

القسم حفظ الفترات الزمنية للحلّ في قائمة أو مصفوفة توفّر دوال تحفظ البيانات التراكمية في بُعد في قائمة أو مصفوفة.

متغيّرات Slack

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

• الوقت التراكمي للمركبة عند i هو 100 دقيقة.
• الوقت التراكمي للمركبة في j هو 200 دقيقة.
• وتبلغ مدة الرحلة من i إلى j 75 دقيقة.

لا يمكن للمركبة مغادرة الموقع 1 فور الوصول، أو تراكمها الوقت في الموقع j سيكون 175. بدلاً من ذلك، يجب أن تنتظر المركبة لمدة 25 دقيقة في الموقع 1 قبل المغادرة؛ أو بعبارةٍ أخرى، فترة الركود في الموقع i هي 25.

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

بالنسبة إلى CVRP، من ناحية أخرى، سيؤدي التغيير في التحميل المتراكم من i إلى دائمًا ما تساوي j الطلب في i، لذلك ما مِن فترة تأخّر. لمشكلات مثل هذا، يمكنك ضبط slack_max على 0.

بعد ذلك، سنقدم التعريف الرسمي لـ Slack. داخليًا، يتم تخزين البُعد نوعان من المتغيرات المرتبطة بالكميات التي تتراكم على طول المسارات:

• متغيّرات النقل العام: زيادة الكمية أو انخفاضها في كل خطوة من الطريق. إذا كان i -> j ضمن خطوة واحدة في المسار، يكون متغيّر النقل العام إما i، j الإدخال في مصفوفة النقل العام (لمعاودة الاتصال بالنقل العام)، أو ببساطة قيمة معاودة الاتصال في الموقع i (إذا كانت معاودة الاتصال تعتمد على موقع واحد فقط).
• المتغيّرات التراكمية: إجمالي الكمية المتراكمة في كل موقع جغرافي. إِنْتَ الوصول إلى المتغير التراكمي في الموقع i عن طريق dimension_name.CumulVar(i) على سبيل المثال، راجع قيود الفترة الزمنية في مثال VRPTW.

على افتراض أن مركبة تتجه من الموقع i إلى الموقع j في خطوة واحدة، ويرتبط فترة Slack بهذه المتغيرات على النحو التالي:

slack(i) = cumul(j) - cumul(i) - transit(i, j)

لمزيد من التفاصيل عن السمات، يمكنك الاطّلاع على RoutingDimension في قسم المراجع