4-3- مسألة البائع المتجول (حالة خاصة في التخصيص)  

تتلخص هذه المسألة بمشكلة انتقال بائع من مكان معين (مراكز الانطلاق) ليزور (ن-1) مكان ، ثم يعود لمركز انطلاقه، شرط أن يتحقق ما يلي :

ـ زيارة كل مكان مرة واحدة.

ـ تكلفة السفر بين كل زوج من الأماكن يساوي ( _{ت ل ك})، علماً أنه ليس من الضروري أن يكون ت _{ل ك} = ت _{ك ل}.

ـ دالة الهدف إيجاد خطة الرحلة المثلى الذي يحقق أقل تكلفة ممكنة.

ـ أن خط الرحلة يتكون من (ن) مكان متتابع ، ويصل بين مكانين متتاليين طريق (وصلة).

ـ جميع الوصلات تشكل دائرة كاملة.

حل المسألة : 

يمكن حل المسألة وفق خطوات خوارزمية أقرب جار Nearest Neighbor Algorithm بعد أن تحوّل المسألة إلى مسألة تعيين لها (ن) عمل، وتكلفة السفر هي تكلفة التعيين، واعتماد مبدأ اختيار أرخص وصلة متبقية على التوالي. والخطوات هي التالية :

1- تشكيل مصفوفة التكلفة من (ن) سطر و (ن) ،عامود و عناصر المصفوفة تمثل تكاليف السفر ت _{ل ك} .. وحيث أن ت _{ل ك} = Φ  عندما ل = ك (تكلفة السفر بين نفس المكان معدومة).

2- استبدال عناصر القطر الرئيسي بأرقام كبيرة أكبر من أي رقم موجود في المصفوفة أو بإشارة -).

3- اختيار أصغر عنصر من عناصر المصفوفة ونضع حوله دائرة (في حالة تساوي بعض العناصر نختار أي منها كيفياً).

4- استبدال عناصر سطر وعامود العنصر الموضوع حوله دائرة بأرقام كبيرة أو إشارة (-)

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

مثال (4-15) :

لدينا مصفوفة النقل لبائع بيتزا متجول، تتضمن الأماكن التي يتوجب زيارتها مرة واحدة (توصيل الطلبات) وتكاليف زيارة كل مكان.