السمات

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

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

أمثلة على الأبعاد

في ما يلي مثالان للأبعاد من الأقسام السابقة.

• ينشئ مثال VRVRW بُعدًا لتتبع وقت السفر التراكمي لكل مركبة. يستخدم برنامج التعيين البُعد لفرض قيود على إمكانية زيارة المركبة لموقع جغرافي معين فقط ضمن الإطار الزمني للموقع.

• ينشئ مثال 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

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

• يبلغ وقت السفر التراكمي للمركبة i 100 دقيقة.
• يبلغ وقت السفر التراكمي للمركبة j 200 دقيقة.
• مُدَّةُ الْمُدَّةْ هِيَ 75 دَقِيقَةْ مِنْ i إلى j.

لا يمكن للمركبة مغادرة الموقع الجغرافي i فور الوصول، أو سيكون الوقت التراكمي في الموقع j 175. بدلاً من ذلك، يجب أن تنتظر المركبة 25 دقيقة في الموقع i قبل المغادرة، بمعنى آخر، أن وقت الركود في الموقع 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(i) = cumul(j) - cumul(i) - transit(i, j)

للاطّلاع على مزيد من التفاصيل حول السمات، يُرجى مراجعة RoutingDimension في القسم المرجعي.