مهمة توصيل البضائع

في هذا المنشور ، سنرى كيف تستخدم Flexport علوم الرياضيات والبيانات لحل مشاكل التسليم وتسليم البضائع في الوقت المحدد بأقل تكلفة ممكنة.

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

كل شحنة لها حجم وتكلفة ، والرحلة محدودة من حيث الحجم. قد تعتقد أنها مشكلة حقيبة ظهر مبسطة. لذلك ، هناك 1024-1 = 1023 حلًا ممكنًا (لن نرسل الطائرة فارغة تمامًا).

يمكننا إنشاء جدول بيانات لسرد الحل بأكمله واختيار الأكثر ربحية. ولكن ماذا لو كان لديك نفس رحلات المغادرة العشر ، ولكن رحلتين؟ هذا هو 59049 حلًا في 10 شحنات فقط.

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

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

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

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

وظيفة الهدف هي تقليل التكلفة الإجمالية ، المعرفة بأنها الوزن الإجمالي لجميع السلع المعينة من قبل ULD ، مضروبة في عامل الحمولة. على سبيل المثال ، إذا كان ULD1 يحتوي على 100 كيلوغرام من الازدحام ومعدل الازدحام لـ ULD1 هو 4 دولارات لكل كيلوغرام ، فإن التكلفة الإجمالية لـ ULD 1 ستكون 400 دولار. لذا ، نحتاج إلى بعض الترميز لكوننا يعانون من زيادة الوزن وقيمته.

اسمحوا ان$$$y_j^E$  - وزن ULD j فوق المعيار و $$$c_j^E$ - عامل التكلفة لنفس ULD. نحن بحاجة للحساب$$$y_j^Ec_j^E$ للجميع $$$j$. إذا$$$j \in {1, 2, 3}$عندها ستكون الوظيفة الموضوعية $$$y_1^Ec_1^E+y_2^Ec_2^E+y_3^Ec_3^E$. ينهار إلى$$$\sum y_j^Ec_j^E$. نريد تقليل القيمة ، لذا فإن هدفنا النهائي:

$$

$$\text{min} \sum_{j} y^E_j c^E_j$$

قيمة $$$c_j^E$ليست قيمة محسوبة. يتم الحصول على هذه المعلمة من جدول بيانات أو قاعدة بيانات. لكن$$$y_j^E$ حددنا الوزن الإجمالي الزائد لـ ULD $$$j$، والتي يمكننا حسابها على أنها الوزن الإجمالي لجميع المستلزمات المعينة من قبل ULD (تشير إلى ذلك $$$y_j$) ، ناقص الوزن القياسي لهذا ULD. الوزن القياسي خاص بنوع ULD وهو أيضًا معلمة. اسمحوا ان$$$U_j^P$  هو الوزن القياسي لـ ULD $$$j$بالكيلوغرام. ثم مقدار الوزن الزائد لـ ULD$$$j$ معرف ك $$$y_j^E=y_j-U_j^P$.
يعتمد الوزن الإجمالي لـ ULD ، بالطبع ، على الأوزان المخصصة لـ ULD ووزنها. لذلك ، نحتاج إلى تعبير لحسابه ، بما في ذلك التفاصيل المذكورة أعلاه.

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

دع المعلمة$$$g_i$ يمثل الوزن الإجمالي $$$i$بالكيلوغرام.
على سبيل المثال،$$$g_4=500$يعني أن حمولة 4 تزن 500 كجم.

اسمحوا ان$$$x_{i, j}$  - متغير قرار يأخذ القيمة 1 في حالة الشحن $$$i$المعينة من قبل ULD $$$j$و $$$0$غير ذلك. وبالتالي ، عندما نريد حساب جميع الشحنات التي تم تعيينها بواسطة ULD 3 ، يمكننا التكرار عبر جميع المتغيرات$$$x_{i, j}$أين $$$j=3$. إذا كان لدينا 4 شحنات ، وتم تعيين رقم الشحن 1 و 3 لـ ULD 3 ، فسيبدو كما يلي:

$$

$$x_{1,3} + x_{2,3} + x_{3,3} + x_{4,3} = 1 + 0 + 1 + 0 = 2$$

لكننا نحتاج إلى الوزن الكلي وليس الكمية. للحصول عليه ، يمكنك ببساطة ضرب كل متغير حل بمعلمة الوزن. نظرًا لأن متغير القرار يأخذ القيمة 0 ، إذا لم يتم تعيين وزن ، فسيتم إعادة تعيين هذا الوزن وعدم تضمينه في الإجمالي. لنفترض أن أوزان الشحنات من الأول إلى الرابع هي 10 و 50 و 25 و 5. ثم سيكون الوزن الإجمالي في ULD 3:

$$

$$g_1x_{1,3} + g_2x_{2,3} + g_3x_{3,3} + g4x_{4,3} = (10)(1) + (50)(0) + (25)(1) + (5)(0) = 10 + 25 = 35$$

دعونا نكتب هذا الحساب للوزن الإجمالي بشكل عام. تحديد الوزن الكلي لل ULD$$$j$ مثل $$$y_j$. ثم$$$y_1=g_1x_{1,1}+g_2x_{2,1}+ … + g_ix_{i, 1}$و $$$y_2=g_1x_{1,2}+g_2x_{2,2} +…+ g_ix_{i, 2}$. يمكن أن ننهار هذا باستخدام تدوين الجمع$$$y_1 = \sum g_ix_{i, 1}$ و $$$y_2=\sum g_ix_{i, 2}$. لأننا نريد أن يكون هذا صحيحا للجميع ممكن$$$j$، نستخدم علامة "للجميع": $$$\forall$. هذا يعطينا الشكل النهائي للحد الأقصى للوزن لدينا:

$$

$$y_j=\sum_{i \in I}g_ix_{i,j} \forall j \in J$$

وزن زائد

الآن بعد أن أصبح لدينا الوزن الإجمالي ، يمكننا تطبيق صيغتنا للحمل الإضافي:

$$

$$y_j^E = y_j-U_j^P \quad \forall j \in J$$

على سبيل المثال ، إذا $$$y_1=1500$و و $$$U_1^P=1000$ثم الوزن الزائد $$$y_1^E = 1500 - 1000 = 500$كيلوغرامات. اضرب هذا في عامل التكلفة للحصول على النتيجة بالدولار. للوهلة الأولى قد يبدو هذا كافيًا ، ولكن ماذا عن الحالة عندما لا يتجاوز الوزن الإجمالي للشحنة بأكملها لـ ULD الوزن القياسي؟ في هذه الحالة ، إذا استخدمنا صيغة "كما هي" ، فسيكون وزن الحمولة الزائدة رقمًا سالبًا. على سبيل المثال ، إذا كان الوزن القياسي هو 1650 كجم ، وكان إجمالي الوزن المخصص هو 1000 كجم ، فإن الحمل الزائد = 1000–1650 = -650. تقوم دالة الهدف بضرب هذا الرقم بعامل التحميل الزائد ونحصل على رقم سالب. كما لو أن الناقل دفع لنا للشحن أقل من تكلفة الوزن القياسي.

إليك ما نريده حقًا:$$$\text{max}(y_j^E, 0)$.
هذا هو نفسه مجرد تعيين 0 لمتغير ، وهو أمر بسيط مثل إنشاء قيد$$$y_j^E>=0$.

$$$y_j^E >= y_j - U_j^P \quad \forall j \in J$، $$$y_j^E >= 0 \quad \forall j \in J$

لذا ، قمنا بتنفيذ الدالة max () في البرمجة الرياضية: a = max (b، c) ، أي a> = b && a> = c. دعونا نلقي نظرة على تعريفاتنا.
دالة الهدف:$$$\text{min} \sum_{j} y^E_j c^E_j$
$$$c_j^E$: نسبة ULD الزائدة $$$j$
$$$y_j^E$: ULD الزائد $$$j$؛ $$$y_j^ = y_j - U_j^P$
$$$U_j^P$: الوزن القياسي ULD $$$j$
$$$g_i$: وزن الشحن الإجمالي $$$i$
$$$x_{i, j}$: متغير القرار ؛ $$$x_{i, j}=1$إذا شحنة $$$i$المعينة من قبل ULD $$$j$، $$$0$غير ذلك.
$$$y_j$: الوزن الإجمالي لجميع الشحنات التي عينتها ULD $$$j$؛ $$$y_j=\sum_{i \in I}g_ix_{i,j} \quad \forall j \in J$

يجب أن يطير كل حمولة

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

هذا يعني انه$$$x_{i, j}$يمكن أن يكون 1 فقط لقيمة واحدة $ j $. على سبيل المثال ، إذا كنا نفكر في شحن 13 ، ثم$$$x_{13,1}+x_{13,2}+ x_{13,3}+ … + x_{13, J}=1$. نريد تطبيق هذا القيد لكل شحنة.$$$i$ (الذي نكتبه $$$\forall i\in I$) ، ويمكننا طي الإضافة باستخدام عامل الجمع ($$$\sum$) ، إذن الحد النهائي لدينا هو:

$$

$$\sum_{j \in J} x_{i, j}=1\quad\forall i \in I$$

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

قيود الحجم والوزن

دعونا نقرر $$$U_j^M$كأقصى حمولة بالكيلوغرام من ULD $$$j$و $$$U_j^$كحد أقصى للحجم بالمتر المكعب ULD $$$j$. دعونا نقرر$$$v_i$، والحجم بالمتر المكعب من البضائع $$$i$. لقصر النموذج على سعة الحمولة القصوى والحجم الأقصى ، لدينا الشروط:

$$

$$y_j<=U_j^M \quad \forall j \in J$$

$$

$$\sum_{i \in I} x_{i,j} v_ i <= U_j^V \quad \forall j \in J$$

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

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

الوقت الذي تكون فيه الشحنة جاهزة بالفعل للدمج مع شحنات أخرى في ULD وتحميلها على الرحلة. لنستخدم$$$Q_i^-$لتمثيل الوقت الذي تكون فيه الشحنة جاهزة $$$i$.
الوقت الذي يجب أن يتم فيه تفريغ البضائع في الوجهة غير مفصل ومتاح للاستلام ، كقاعدة عامة ، من محطة الشحن. لنستخدم $ Q_i ^ + $ لتمثيل الموعد النهائي للتسليم$$$i$.
الوقت الذي يجب فيه تسليم جميع البضائع إلى محطة الشحن لتحميلها على متن الطائرة. لنستخدم$$$T_j^ -$لتمثيل وقت لقطة الشحنة ULD $ j $.
وقت وصول الرحلة: هذا هو الوقت الذي تصبح فيه البضائع على الرحلة متاحة في مستودع الوجهة. لنستخدم$$$T_j^+$ لتمثيل وقت وصول رحلة ULD $$$j$

المصدر والوجهة

قدِّم مجموعة أخرى $$$J_i$، والتي نعرّفها كمجموعة من الرحلات ، يتزامن مصدرها ووجهتها مع مغادرة البضائع واستلامها $$$i$. بمعنى آخر ، إذا كانت المغادرة 85 من هونج كونج والوجهة في لندن ، فإن $ J_ {85} $ هي مجموعة جميع ULDs مع المغادرة من هونج كونج والوجهة في لندن.
الآن يمكننا استخدامها$$$j \in J_i$ للحصول على مجموعة ULD التي تتطابق مع مسار تجارة الشحن $$$i$أو يمكننا استخدامها $$$j \notin J_i$للحصول على مجموعة ULD لا تتطابق. لحظر ربط البضائع بـ ULD ، التي لا تتوافق مع مصدرها ووجهتها ، نقوم ببساطة بتقييدها$$$x_{i,j} = 0$لجميع هذه الرحلات. يتم وصف القيد بالكامل كما يلي:

$$

$$\sum_{j \notin J_i} x_{i,j}=0 \quad \forall i \in I$$

موعد التسليم

عند العمل مع الطوابع الزمنية في التحسين ، من المناسب تقديم اللحظات الضرورية في وقت Unix. مزايا النهج:

1. تخزين التواريخ كأرقام.
2. لا حاجة للتعامل مع المناطق الزمنية.
3. يستخدم حلالا المقارنات المباشرة أكثر وأقل.

يجب أن تصل الرحلة قبل موعد التسليم:
$$$\sum_{j \in J_i}T_j^+x_{i,j}<=Q_i^+ \quad \forall i \in I \quad$
يرجى ملاحظة أنه ، تمامًا مثل القيود المذكورة أعلاه على المغادرة والوجهة ، فقد أشرنا إلى أن هذا التقييد ينطبق فقط على ULD في المجموعة $$$J_i$أين $$$J_i$ هي مجموعة من ULDs التي تتطابق مع إرسال واستلام الشحنة $$$i$. هذا كل شئ! دعونا نلقي نظرة على النموذج بأكمله.

نموذج كامل

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

المعلمات

$$$I$: مجموعة من جميع الشحنات. تم إرسال شحنة واحدة$$$i$
$$$J$: مجموعة من جميع ULD. ULD الفردية صغيرة$$$j$.
$$$J_i$: مجموعة من جميع ULDs التي تتطابق مع المرسل والمستقبل $$$i$.
$$$g_i$الوزن الصافي للشحن $$$i$بالكيلوغرام.
$$$v_i$: الحجم بالمتر المكعب للشحن $$$i$
$$$c_j^E$: نسبة ULD الزائدة $$$j$بالدولار الأمريكي للكيلوغرام الواحد
$$$U_j^M$: سعة الوزن القصوى ULD $$$j$بالكيلوغرام
$$$U_j^V$: الطاقة القصوى المحيطة بـ ULD $$$j$بالمتر المكعب
$$$U_j^P$: الوزن القياسي ULD $$$j$بالكيلوغرام

$$$T_j^-$: وقت التسليم المسموح به لمحطة ULD $$$j$.
$$$T_j^+$: وقت وصول ULD $$$j$.
$$$Q_i^-$: وقت الشحن جاهز $$$i$. 
$$$Q_i^+$: فترة التسليم $$$i$.

متغيرات القرار ووظيفة الهدف:
$$$y_j$: الوزن الإجمالي لـ ULD $$$j$
$$$y_j^E$: ULD الزائد $$$j$بالكيلوغرام.
$$$x_{i,j}$: 1 عند الإرسال $$$i$المعينة من قبل ULD $$$j$0 خلاف ذلك.

الوظيفة المستهدفة

$$

$$\text{Minimize} \sum y_j^Ec_j^E$$

محددات

$$$y_j$ - الوزن الكلي للشحنات على ULD $ j $: $$$y_j=\sum_{i \in I} g_ix_{i,j} \quad \forall j \in J$
الوزن الزائد jE هو الحد الأقصى (0 ، yj-UjP):
$$$y_j^E >=y_j-U_j^P \quad \forall j \in J$
$$$y_j^E >=0 \quad \forall j \in J$
يجب تعيين كل تسليم بالضبط إلى 1 ULD: $$$\sum_{j \in J} x_{i,j}=1 \quad \forall i \in I$.
ULD$$$j$ لا يمكن أن يتجاوز الوزن الأقصى: $$$y_j<=U_j^M \quad \forall j \in J$
ULD $$$j$لا يمكن أن تتجاوز السعة القصوى: $$$\sum_{i \in I}x_{i,j}v_i <= U_j^V \quad \forall j \in J$

خطوات أخرى

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