تصميم خوارزمية توجيه المركبات / جدولة الموارد

Question

أول مشاركة لي هنا - على أمل أن تتمكن من مساعدتي في تصميم خوارزمية كنت أفكر فيها لفترة قصيرة الآن - لست متأكدًا من الطريقة التي يجب اتباعها (VRPTW أو جدولة الموارد أو أي شيء آخر تمامًا !؟)

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

هدفنا هو ضمان نقل جميع الكثير من النفايات المقطورة أثناء

• تقليل عدد المقطورات والسيارات المستخدمة
• تلبية جميع الأوقات ويندوز لإسقاط النفايات
• "موازنة" المقطورات - أي في نهاية اليوم لدينا العديد من المقطورات في كل موقع كما كان هناك في بداية اليوم

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

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

أي أفكار حول الاقتراب ستكون موضع تقدير!

Answer 1

وأنا أتفق مع Jiri ... تريد خوارزمية مجدية تقترب بشكل معقول من حل مقبول بسرعة ثم يتم صقلها من هناك.

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

1. ابدأ] توليد سكان عشوائي من الكروموسومات N (حلول مناسبة للمشكلة)
2. اللياقة] تقييم اللياقة f (x) لكل كروموسوم x في السكان

3. السكان الجدد] إنشاء عدد جديد من السكان من خلال التكرار الخطوات التالية حتى يكتمل عدد السكان الجدد

   اختيار] حدد كروموسومات الوالدين من السكان وفقًا للياقتهم (أفضل اللياقة البدنية ، الفرصة الأكبر للاختيار)

   كروس] مع احتمال كروس عبر الوالدين لتشكيل ذرية جديدة (أطفال). إذا لم يتم إجراء تقاطع ، فإن النسل هو نسخة دقيقة من الآباء.

   طفرة] مع احتمال الطفرة تحور ذرية جديدة في كل موضع (موضع في الكروموسوم).

   قبول] ضع ذرية جديدة في عدد سكان جديد

4. استبدال] استخدم السكان المولدين الجدد لمزيد من الخوارزمية
5. اختبار] إذا كانت حالة النهاية راضية ، توقف وإعادة أفضل الحل في السكان الحالي
6. حلقة] اذهب إلى الخطوة 2

تتمثل الحيلة في هذا في تشفير قيودك إلى "كروموسوم" وكتابة وظيفة "اللياقة". يجب أن تأخذ وظيفة اللياقة مدخلات لنتائج حل محتمل وتصحيح درجة مدى جودة الحل الذي يتم أو يطرده إذا انتهك أي من القيود.

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

Answer 2

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

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

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

Answer 3

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

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

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

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

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

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

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

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

Answer 4

النهج العام:

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

حل:

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

الملاحظة:

أنت تحل المشكلة على شبكة قد تكون فيها التحركات الأخيرة هي نقل مقطورة فارغة.

حظا طيبا وفقك الله !

Answer 5

البحث المحلي هي بديل للخوارزميات الوراثية. في ال مسابقة الجدول الزمني الدولي 2007, ، تغلبت خوارزميات البحث المحلية (مثل البحث عن Tabu و tabu telling) بوضوح على إدخالات الخوارزمية الوراثية (من 1 إلى 4 في المركز LS مقابل المركز الخامس لـ GA في المسار 1 من حوالي 80 منافسًا IIRC).

أيضًا ، ألقِ نظرة على بعض المكتبات هناك ، مثل Optaplanner (بحث Tabu ، الصلب المحاكاة ، القبول المتأخر ، المصدر المفتوح ، Java) ، JGAP (الخوارزميات الوراثية ، المصدر المفتوح ، Java) ، Opents (Tabu Search ، ...