حل مشكلة مسارات المركبات محددة الحمولة cdvpp باستخدام خوارزمية البحث المحرم
الطالب : علي غني نوري المشرف : أ.م.د. عبد الجبار خضر بخيت
تمت في كلية الادارة والاقتصاد – جامعة بغداد ، مناقشة رسالة الماجستير في تخصص بحوث العمليات للطالب ( علي غني نوري ) عن دراسته الموسومة ” حل مشكلة مسارات المركبات محددة الحمولة cdvpp باستخدام خوارزمية البحث المحرم مع تطبيق عملي “.
ان مجال اعمال النقل وتقديم الخدمات اللوجستية اصبح من الاساسيات المؤثرة لإدارة وامداد البضائع والخدمات في انظمة التوزيع ولعدد كبير وهائل من تطبيقات العالم الحقيقي حيث بدأت المؤسسات والمراكز التجارية اعتماد استعمال الإجراءات والانظمة التي تعتمد التخطيط في ادارة النقل اللوجستي والذي من شانه ان يساعد في تغيرات مؤثرة في تخفيض الكلف الاجمالية وفي الواقع ان عملية النقل تمثل نسبة ليست بالقليلة من الكلف عادة من كلف السلع والخدمات وعملية تطوير هذه الاساليب تساعد في زيادة تكامل نظم المعلومات في العمليات الانتاجية والتجارية والنقل اللوجستي وكذلك تطور عوامل اخرى وربط هذه الاساليب والادوات التي يتم تنفيذها في السنوات الاخيرة والتي تأخذ بالاعتبار معظم الخصائص لمشاكل التوزيع التي تم تطبيقها في العالم الحقيقي.
ففي هذا البحث تم دراسة مشكلة توجيه العربة (VRP) التي تصنف من المشاكل (NP-HARD) او المشاكل ذات الامثلية التوافقية الصعبة وتهتم هذه المشكلة بتصميم مسارات لمجموعة من العربات التي تجهز عدد من العملاء المنتشرين بمواقع مختلفة ويكون الهدف لهذه المشكلة هو تقليل التكلفة الاجمالية للتسليم مع الاخذ بالاعتبار القيود المفروضة للمشكلة. ويتم دراسة مشكلة توجيه العربة المحددة السعة (CVRP) وهي احد اصناف المشكلة واهمها والتي تهتم بتصميم التوزيع الأمثل للمسارات في ضل قيود سعات العربات المحددة وتتضمن الرسالة الانموذج الرياضي المستعمل واهم الطرق المستعملة وتطورها في حل المشكلة واستخدام خوارزمية البحث المحرم (TS) في حل مسائل المشكلة ويتم مقارنة الاداء للخوارزمية وكفاءتها مقارنتا مع اساليب فوق استدلالية اخرى استعملت لحل المشكلة متمثلة بالخوارزمية الجينية (GA) وخوارزمية سرب الطيور (PSO) ومن خلال حل مسائل قياسية معروفة للمشكلة والتي اظهرت من خلال التجارب الحسابية ان الخوارزمية التي استعملت للحل قادرة على ايجاد حلول للمشكلة مقبولة وجيدة خلال اوقات حسابية معقولة حيث استطاعات ان تتوصل لمتوسط الانحرافات عن الحلول القياسية لمجموعة المسائل القياسية بحوالي (1.764) وان خوارزمية البحث المحرم TS)) قد توصلت لنتائج تغلبت على معظم نتائج الخوارزميات الاخرى المستعملة في الحل .كما تم تطبيق اسلوب المشكلة باستعمال خوارزمية البحث المحرم ((TS في الشركة العامة لتصنيع الحبوب لعملية التوزيع من احدى المطاحن الى مجموعة من الوكلاء المنتشرين جغرافيا وقد استطاعت الطريقة ان تتوصل لرسم وتصميم افضل مسارات ممكنة للعربات المتاحة باقل مسافة تقطع وباقل عدد من العربات و تم التوصل لأقل مسافة توافقية ممكن ان تقطع لمجموعة العربات وكانت المسافة المقطوعة (442 km) لمجموعة المسارات التي رسمت لتغطية (69) وكيل وباستعمال (8) عربات غطت (8) مسارات وحققت الطلب الاجمالي المحدد من خلال زيارة جميع الوكلاء باستعمال عدد عربات اقل من المتاح.
و تتمثل المشكلة بوجود كميات يتطلب نقلها من مستودع (يعتبر نقطة انطلاق لمجموعة عربات تمتلك سعات محددة لكل عربة)الى جهات طالبة ومخصص لها تلك الكميات والمشكلة تكون في الية توجيه عدد العربات المتوفرة في ضل القيود المتولدة والمفروضة للمشكلة واختيار وتحديد افضل المسارات لتلبية وتحقيق تلك الكميات ورسم تلك المسارات على تحقيق اقل مسافة لمجموعة المسارات في وجود الشروط ان الطلب لكل مسار لا يتعدى قدرة كل عربة وان يتم تحقيق الطلب لكل عقدة او زبون من خلال عربة واحدة وان لا يتعدى عدد المسارات العربات المتاحة.
ويهدف البحث على تقليل الكلف الاجمالية المترتبة على توجيه العربات من خلال توجيه اسطول العربات بصورة توافقية وتوزيع الطلب الاجمالي بشكل مثالي على العربات من خلال تخصيص المسار الافضل والامثل لكل عربة وتخفيض عدد العربات المتاح وتقليل المسافات المقطوعة من خلال تقليل تشتت المسارات.
ويتضمن البحث اربعة افصل رئيسية ,الفصل الاول يضم المقدمة ومشكلة وهدف البحث والاستعراض المرجعي لتطور البحث العلمي للمشكلة ,الفصل الثاني يضم الجانب النظري والذي يبين اساسيات وتفاصيل المشكلة واهم الطرق والاساليب التي تستعمل في حل المشكلة ,الفصل الثالث الجانب العملي يتألف من مبحثين الاول يهتم بالتجارب العددية واستعمال مسائل قياسية معروفة للمشكلة لاختبار كفاءة واداء الخوارزميات المستعملة في حل المشكلة والمبحث الثاني يهتم بالجانب العملي التطبيقي للمشكلة وجوانب جمع البيانات الحقيقية لتطبيق الاسلوب في حل وتحليل المشكلة التطبيقية وتفسير النتائج النهائية التي تم الحصول عليها ,اما الفصل الرابع فيضم اهم الاستنتاجات والتوصيات والدراسات المستقبلية للمشكلة.
وتم التوصل الى مجموعة من الاستنتاجات ندرج منها :
1. من خلال التجارب العددية تبين ان خوارزمية البحث المحرم TS فعالة وكفؤة في حل مسائل مشكلة توجيه العربة المحددة السعة (CVRP) حيث كان متوسط متوسطات الفجوة النسبية لقيم الخوارزمية مع الحلول القياسية حوالي (1.764) لمجموعة المسائل القياسية للمشكلة.
2. ان مشكلة توجيه العربة المحددة السعة (CVRP) يزداد تعقيدها كلما كان حجم المسألة اكبر وتزداد الصعوبة في ايجاد الحلول لها وهذا ما تبين من خلال ملاحظة الحلول للمسائل القياسية و نلاحظ ان المسألة كلما كبر حجمها يزداد نسبة الفجوة عن الحل القياسي المعروف.
3. ان خوارزمية البحث المحرم (TS) اثبتت كفاءتها في ايجاد الحل للمشكلة سواء في التجارب العددية او التطبيق العملي حيث انها تغلبت على الخوارزميات الفوق الارشادية (Meta heuristic) التي استعملت معها لحل مسائل المشكلة حيث تشير النتائج على تفوق خوارزمية البحث المحرم (TS) على الخوارزمية الجينية (GA) وخوارزمية سرب الطيور (PSO) والخوارزمية المهجنة لسرب الطيور مع الخوارزمية الجينية (GA-PSO) ما عدى الخوارزمية المهجنة لسرب الطيور مع البحث المحرم (TS-PSO) التي استطاعت ان تتغلب على خوارزمية البحث المحرم (TS) بشكل نسبي سواء في ايجاد الحلول في التجارب العددية او التطبيق العملي.
وقد تم التوصل الى مجموعة من التوصيات منها :
1. استعمل في هذه الرسالة اسلوب مشكلة توجيه العربة المحددة السعة (CVRP) لمستودع واحد(المطحنة) ومجموعة وكلاء محدد ويمكن ان يعمم الاسلوب ليشمل مجموعة المطاحن لدى الشركة العامة لتصنيع الحبوب وعدد كبير من الوكلاء المرتبطين بالشركة واعتماد اعداد العربات المتاح لدى الشركة بالإضافة للعربات الخاصة بالشركات المتعاقدة مع الشركة العامة لنقل الطحين والمنتوجات الاخرى لدى الشركة .وبالتالي اعتماد الاسلوب و تعميمه يمكن ان يولد استراتيجية ثابتة وواضحة يمكن ان تعتمد شهريا في عملية التوزيع بأفضل مسافات ومسارات يتم تخصيصها وباقل كلف ممكنة.
2. نوصي الشركة العامة لتصنيع الحبوب بضرورة المحاولة في زيادة وتوفير عدد العربات ذات السعات الكبيرة بغية انتفاء الحاجة لطرح توزيع الطحين والمواد الغذائية التي توزعها لمناقصات للشركات الخاصة للنقل اي حصر التوزيع والنقل بالشركة دون اللجوء لشركات القطاع الخاص والذي بدوره سيسهم في توفير الفروقات المادية وكلف ليست بالقليلة و التي سيكون لها دور في المساعدة في تطوير عمل الشركة وتطوير المطاحن المرتبطة بها ويسهل عملية التوزيع والتخطيط كونها ستعتمد البنيه التحتية الخاصة بها.
3. ضرورة تطبيق مشكلة توجيه العربة (VRP) في عمليات التوزيع والنقل وخاصة ان الاسلوب للمشكلة قد ثبت كفاءته وفاعليته في رسم افضل مسارات بين الوكلاء وتقليل عدد العربات اللازمة للخدمة و كون معظم المؤسسات الحكومية وشركات القطاع الخاص في البلد تعتمد التوزيع العشوائي في تلبية الطلبات او جمعها والذي كثيرا ما يساهم في ضياع الوقت ومضاعفة التكاليف المصاحبة للتوزيع والذي بدوره يؤدي الى تشتت تحقيق الطلبات في اوقاتها المحددة.