كيف اخترنا البضائع لشركات النقل

طاب مسائك. اسمنا Ilya Bashtanov (المطور ، Tochka -Tochka ) و Tatyana Voronova (محلل البيانات ، مركز 2M ). ونريد الحديث عن التنفيذ الفني لمهمة اختيار البضائع لوسائل النقل.

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

المهام التي تم حلها للأعمال التجارية في هذه الحالة:

1. تحميل المركبات بأكبر قدر ممكن من الكفاءة وبالتالي زيادة إيرادات النقل.
2. لحل مشكلة التسليم في وقت مقبول للمستخدم (بما في ذلك مبدأ FIFO).

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

خوارزمية

هذه المهمة هي نوع من مشكلة التعبئة الكلاسيكية لحقيبة الظهر . مشكلة حقيبة الظهر كاملة NP . لا يمكن حل مثل هذه المشاكل في زمن كثير الحدود ، على الرغم من أنه لم يتم إثبات ذلك رياضيًا بعد. هذا يعني أن الخوارزميات الدقيقة ، مثل البحث الشامل للمتغيرات أو أصنافها المحسنة ، لا تعمل في الواقع ، لأنها معقدة$$$O(2^n)$. توفر الطرق التقريبية حلولًا لأفضل وقت. على سبيل المثال ، تفترض الخوارزمية الجشعة أن الوزن الأقصى يتم وضعه في حقيبة الظهر لأطول فترة ممكنة. تعقيدها لا يتجاوز تعقيد الفرز$$$(O(n * log n))$، ولكن النتيجة قد تكون بعيدة عن المثلى. لا يزال هناك فئة من الخوارزميات الجينية التي تعطي نتائج جيدة في وقت محدود ، لكنها غير حتمية ، والتي في حالتنا ستؤدي إلى خيارات مختلفة للإصدار أثناء المكالمات المتكررة ، سيكون من الصعب شرحها للعميل وشركات الاتصالات. ونتيجة لذلك ، وقع الاختيار على طرق تقريبية تعطي النتيجة بدقة مضمونة في وقت كثير الحدود.

اذا لدينا:

• الأوزان مع الأوزان $$$w_1,w_2,... , w_n$
• تحديد الوزن الإجمالي للسلع $$$W_\max$
• حد الشحن $$$Q_\max$

مطلوب العثور على مجموعة فرعية من البضائع ذات الوزن الإجمالي الأقصى الذي يلبي القيود.

والفكرة هي تقليل مجموعة متنوعة من السلع عن طريق خشن أوزانهم وتطبيق خوارزمية الجشع. في هذه الحالة ، يتم العثور على الحل التقريبي في وقت متعدد الحدود تمامًا ، أي حل بدقة مضمونة$$$1- \varepsilon$ تم الحصول عليه مع التعقيد كونه كثير الحدود في $$$n$و $$$\varepsilon$.

عند إدخال الخوارزمية ، لدينا لوحة تحتوي على الأوزان المستديرة للبضائع وعدد المقاعد لكل وزن. باستخدام خوارزمية الجشع ، نحاول الحصول على خيارات التصميم لإجمالي الأوزان$$$W_\max,$ $$$W_\max-1,$$$$W_\max-2,$$$$…,$$$$0$. للقيام بذلك ، بعد تحديد الوزن الإجمالي المستهدف ، في الدورة ، نختار الحمولة القصوى من الوزن من الأحمال المتبقية حتى لا يتجاوز الوزن الإجمالي المستهدف. إذا تم الوصول إلى الحد الأقصى المسموح به$$$Q_\max$، تنتهي الدورة. يتم تخزين المجموعات الناتجة في صفيف مؤقت.

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

الاختبارات

للاختبار ، اخترنا تطبيقين للخوارزمية المدروسة ، والتي تختلف في التفاصيل غير المهمة: أحدهما في Java ، والآخر في PL / pgSQL ، اللغة الإجرائية لنظام PostgreSQL DBMS. وتجدر الإشارة على الفور إلى أن الاختيار النهائي لم يتأثر فقط بنتائج الاختبار ، ولكن أيضًا بالاعتبارات المعمارية وسهولة الاستخدام وعوامل أخرى. ولكن أولاً ، كانت المهمة هي اختيار أحد تطبيقين.

تم استخدام بيئتين للاختبار: سطح مكتب لاختبار التطوير وخادم للاختبار في ظروف مماثلة للظروف الحقيقية.

• dev: محطة عميل HP Probook 4740s + وحدة معالجة مركزية ثنائية النواة 32 بت 2 x Pentium® E5300 بسرعة 2.60 جيجاهرتز وذاكرة وصول عشوائي سعتها 4 غيغابايت ، Ubuntu Linux 16.04 ، PostgreSQL 10.3.
• test: 64-bit 2 x Intel Xeon CPU E5-2673 v4 @ 2.30GHz 14 , CentOS Linux 7.4, PostgreSQL 10.3

تم إعداد جدول اختبار في قاعدة بيانات PostgreSQL التي تحتوي على 7000 حمولة بأوزان عشوائية من 20 إلى 800 كجم. للاختبار ، استخدمنا الأداة المساعدة pgBench القياسية من PostgreSQL ، والتي أجرت أثناء الاختبار 500 معاملة (10 اتصالات لكل 50 معاملة). قامت كل معاملة بإجراء مكالمة واحدة للخوارزمية بمعلمات عشوائية (تقييد على الوزن من 10 إلى 1000 كجم وعلى عدد البضائع من 1 إلى 50 قطعة). يتم توزيع جميع المتغيرات العشوائية بالتساوي.

بالنسبة إلى الخوارزمية الأولى ، بدأت كل معاملة آلة Java وتمرير أرشيف JAR مع رمز الخوارزمية إليها للتنفيذ. فئة جافا الرئيسية المتصلة بقاعدة البيانات من خلال مشغل JDBC ، تلقت بيانات الاختبار من الجدول وطبقت الخوارزمية عليها.

بالنسبة للخوارزمية الثانية ، قامت كل معاملة باستدعاء الوظيفة المخزنة لقاعدة بيانات PostgreSQL ، التي تقرأ بيانات الاختبار من الجدول وتطبق الخوارزمية.

الجدول 1. نتائج الاختبار الرئيسي



بالإضافة إلى الاختبار الرئيسي ، الذي تم عرض نتائجه في الجدول 1 ، تم إجراء اختبار إضافي للخوارزمية 2 ، حيث تم مقارنة خيارات مختلفة للحصول على البيانات الأولية: من قاعدة بيانات ، من ملف ، إنشاء صفيف عشوائي. اتضح أنه بالنسبة إلى 7000 عملية تحميل ، يتطلب نقل البيانات من DBMS إلى صفيف محلي وقتًا أطول من خوارزمية التراص الفعلية.

الموجودات.

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

ونتيجة لذلك ، تم اختيار الخوارزمية الثانية التي تم استخدامها ، مع تعديلات طفيفة ، للسنة الثانية. ونتيجة لذلك ، يتم البحث عن حل بدقة مقبولة بمتوسط ​​وقت معاملة أقل من ثانية واحدة.

استغلال

كما هو الحال دائمًا ، أجرت الحياة تعديلات ، وكان علي تعديل التطبيق.

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

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

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

نتائج الأعمال

مهمة Point-Point هي عملية لوجستية فعالة ، على وجه الخصوص ، الاستخدام الأمثل للسيارة من حيث الازدحام: عند نقل الحد الأدنى من الفراغات.

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

وجد المتخصصون في Centre 2M و Tochka-Tochki حلًا رياضيًا برمجيًا مناسبًا لجميع المشاركين في عملية النقل. يمكن استخدامه للشبكة الفيدرالية ، في كل نقطة يتم طلب 7 آلاف منصة نقالة (المقابلة لحجم ملعب كرة القدم) من قبل 500 حامل للناقل والحصول على النتيجة في أقل من ثانية واحدة.

مؤلفو المقالة: ايليا باشتانوف (أنا باشتاتيانا فورونوفا ()tvoronova)