بيت » مميز » مشكلة البائع المتجول، للصناعة والابتكار

مشكلة البائع المتجول، للصناعة والابتكار

مشكلة البائع المتجول

Imagine a busy distribution center where machines and workers move optimally between each working and storage locations. Routes need to be planned well to meet strict time limits and keep costs and other factors low. This challenge is at the heart of the historically so-called traveling salesman problem (TSP). It’s not only in the logistic applications. This piece explores how the traveling salesman problem can be used in real life and تصنيع. It looks at how one can improve their route planning in all the industry.

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

يركز هذا المنشور بشكل خاص على خوارزمية واحدة من منشورنا "أهم 10 خوارزميات ومنهجيات يجب معرفتها في الهندسة".

النقاط الرئيسية

  • تتمثل مشكلة البائع المتنقل (TSP) في إيجاد الطريق الأمثل بين عدة نقاط.
  • بدأت هذه المشكلة تحظى بالاهتمام في الفترة 1930-1940
  • يساعد المؤسسات على تعزيز الكفاءة وتقليل التكاليف في عملياتها والحد من الموارد وتحسين تقديم الخدمات.
  • تنطبق هذه المشكلة على نطاق واسع في مختلف القطاعات والصناعات، وليس فقط في مجال الخدمات اللوجستية والنقل.
  • بمجرد أن يكون هناك أكثر من 12-20 نقطة، تصبح المشكلة معقدة للغاية بحيث لا يمكن حساب حل مثالي لها
  • لقد تم اختراع العديد من الخوارزميات للعثور على خوارزميات تقريبية جيدة، وبالتالي ليست المثالية

ما هي مشكلة البائع المتجول؟

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

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

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

لماذا هي مشكلة رغم ذلك؟

 

إذا كانت هناك n مدن، فهناك (n-1)! /2 جولات فريدة من نوعها (يأتي الرقم /2 إذا كانت الجولة عبارة عن دورة ولا تهم الاتجاهات).

  • بالنسبة إلى n الصغيرة (لنقل n < 20)، تعمل الخوارزميات الدقيقة (القوة الغاشمة والبرمجة الديناميكية).
  • التقنيات التقريبية/الاستدلالية: غالبًا ما تُستخدم التقنيات التقريبية/الاستدلالية: خوارزمية الجار الأقرب، خوارزمية كريستوفيدس، الخوارزميات الجينية في الحالات الأكبر حجمًا.
  • But, in general, there is no fast الطريقة guaranteed to give the exact best answer for all instances.

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

المدن التي تمت زيارتهاالمسارات/التركيبات الممكنة
36
424
5120
6720
75040
206 × 1016 (ما يقرب من ألفي عام إذا كان حساب كل مسار يتطلب ميكروثانية واحدة)
25أكثر من عمر كوننا إذا كانت كل عملية حسابية للمسار تتطلب ميكروثانية

تاريخ مشكلة البائع المتجول

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

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

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

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

لماذا تُعدّ مشكلة صعبة على المستوى NP؟

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

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

ما هي مشكلة "NP الصعبة": في علوم الحاسوب ونظرية التعقيد الحاسوبي، "NP" تعني "NP" وقت متعدد الحدود غير حتمي. المشكلة الصعبة في NP هي على الأقل صعبة مثل أصعب المشاكل في NP، مما يعني أن كل مشكلة في NP يمكن اختزالها في زمن متعدد الحدود. على عكس مشاكل NP-المكتملة التي يمكن التحقق منها في زمن كثير الحدود, تلا توجد هنا خوارزمية معروفة تحل مسائل NP الصعبة في زمن متعدد الحدود.

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

التطبيقات الصناعية

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

مواصلات

أكثر الاستخدامات تشابهاً مع مشكلة البائع الأصلي:

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

التوجيه 

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

يمكن للشركات إعداد عقد شبكتها بأفضل طريقة لتقليل فقدان الإشارة وتعزيز الأداء في تصميم الشبكة.

التصنيع والآلات

  • إلكتروني: التصنيع و لوحة الدوائر الكهربائية الحفر: تقليل المسافة في ماكينات الحفر الآلية أو في التحكم في دبوس ثنائي الفينيل متعدد الكلور
  • الروبوتات تخطيط المسار: تحسين المسار لروبوتات المستودعات، أو مسارات أذرع الروبوتات
  • Astronomy:...

You have read 52% of the article. The rest is for our community. Already a member? تسجيل الدخول
(وأيضًا لحماية المحتوى الأصلي لدينا من روبوتات الكشط)

مجتمع الابتكار العالمي

تسجيل الدخول أو التسجيل (100% مجاناً)

اطلع على بقية هذه المقالة وجميع المحتويات والأدوات الخاصة بالأعضاء فقط.

فقط المهندسون والمصنعون والمصممون والمسوقون الحقيقيون المحترفون.
لا روبوت، ولا كاره، ولا مرسل رسائل غير مرغوب فيها.

قراءات ذات صلة

  • Combinatorial Optimization Algorithms: exact and heuristic methods like Genetic Algorithms, Simulated Annealing
  • Graph Theory and Network Analysis: هاميلتونيان cycles, shortest path algorithms
  • Operations Research: linear programming, integer programming
  • Computational Complexity Theory: NP-hardness characterization
  • Meta Heuristics and Swarm Intelligence: ant colony pptimization, particle swarm optimization in solving TSP

التعليمات

ما هي مشكلة البائع المتنقل (TSP)؟

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

لماذا يُعتبر نظام TSP مشكلة صعبة من نوع NP؟

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

ما هي بعض التطبيقات الشائعة ل TSP؟

يُستخدم TSP في العديد من المجالات، مثل جعل طرق التوصيل أكثر كفاءة وإدارة سلاسل التوريد. كما أنه مفيد في مجال الرعاية الصحية لجدولة الزيارات وفي مجال الروبوتات لتوجيه الحركات أو في تصنيع الإلكترونيات لتحديد المواقع أو اختبار المكونات الصغيرة ومسارات النحاس.

ما علاقة نظرية الرسم البياني والخوارزميات الاستدلالية بمخطط TSP؟

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

كيف يؤثر برنامج دعم التجارة في الخدمات على كفاءة سلسلة التوريد؟

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

مسرد المصطلحات المستخدمة

Deoxyribonucleic Acid (DNA): جزيءٌ مُكوَّنٌ من سلسلتين يُشكِّلان حلزونًا مزدوجًا، ويتكوَّن من نيوكليوتيدات تُشفِّر المعلومات الوراثية عبر تسلسلاتٍ من أربع قواعد: الأدينين، والثايمين، والسيتوزين، والجوانين. وهو المادة الوراثية في معظم الكائنات الحية.

Printed Circuit Board (PCB): لوح مسطح مصنوع من مادة عازلة، يدعم ويربط المكونات الإلكترونية عبر مسارات موصلة، عادةً ما تكون محفورة من صفائح نحاسية. يُشكل هذا اللوح أساسًا لتجميع الدوائر الكهربائية، ويُسهّل التوصيلات الكهربائية بين المكونات.

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

جدول المحتويات
    أضف رأسًا لبدء إنشاء جدول المحتويات

    متاح للتحديات الجديدة
    مهندس ميكانيكي، مشروع، هندسة العمليات أو مدير البحث والتطوير
    تطوير المنتج الفعال

    متاح لتحدي جديد في غضون مهلة قصيرة.
    تواصل معي على LinkedIn
    تكامل الإلكترونيات المعدنية والبلاستيكية، التصميم مقابل التكلفة، ممارسات التصنيع الجيدة (GMP)، بيئة العمل، الأجهزة والمواد الاستهلاكية متوسطة إلى عالية الحجم، التصنيع المرن، الصناعات الخاضعة للتنظيم، شهادات CE وFDA، التصميم بمساعدة الحاسوب (CAD)، Solidworks، الحزام الأسود من Lean Sigma، شهادة ISO 13485 الطبية

    نحن نبحث عن راعي جديد

     

    هل شركتك أو مؤسستك متخصصة في التقنية أو العلوم أو الأبحاث؟
    > أرسل لنا رسالة <

    احصل على جميع المقالات الجديدة
    مجاني، لا يوجد بريد عشوائي، ولا يتم توزيع البريد الإلكتروني ولا إعادة بيعه

    أو يمكنك الحصول على عضويتك الكاملة -مجانًا- للوصول إلى جميع المحتويات المحظورة >هنا<

    المواضيع المغطاة: مشكلة البائع المتجول، والتحسين الأمثل، وتخطيط المسار، والخدمات اللوجستية، والخوارزمية، والكفاءة، وخفض التكاليف، والأساليب الاستدلالية، والبرمجة الديناميكية، والبرمجة الديناميكية، و NP الصعبة، والتحسين التوافقي، وخوارزميات التقريب، وISO 9001، وISO 14001، وISO/IEC 27001، وISO 31000، وISO 50001.

    اترك تعليقا

    لن يتم نشر عنوان بريدك الإلكتروني. الحقول الإلزامية مشار إليها بـ *

    السياق التاريخي

    1828
    1850
    1854
    1854
    1896
    1911
    1925
    1827
    1848
    1850
    1854
    1895
    1900
    1914
    1925

    (إذا كان التاريخ غير معروف أو غير ذي صلة، على سبيل المثال "ميكانيكا الموائع"، يتم تقديم تقدير تقريبي لظهوره الملحوظ)

    منشورات ذات صلة

    انتقل إلى الأعلى