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

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

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

• يمكن صياغة المسألة بشكل مكافئ في نظرية المخططات كما يلي: بالنظر إلى مخطط كامل مُثقَّل (حيث تمثل الرؤوس المدن، وتمثل الحواف الطرق، وتمثل الأوزان تكلفة أو مسافة كل طريق)، ابحث عن دورة هاميلتونية بأقل وزن. هذه المسألة أعمّ من مسألة المسار الهاميلتوني ، التي تسأل فقط عما إذا كان هناك مسار (أو دورة) هاميلتوني في مخطط غير كامل وغير مُثقَّل.
• إن شرط العودة إلى مدينة البداية لا يغير من التعقيد الحسابي للمسألة؛ انظر مسألة المسار الهاميلتوني .
• مشكلة أخرى ذات صلة هي مشكلة البائع المتجول ذات عنق الزجاجة : إيجاد دورة هاميلتونية في رسم بياني مُثقَّل بأقل وزن للحافة الأثقل . ومن الأمثلة الواقعية على ذلك تجنب الشوارع الضيقة التي تعج بالحافلات الكبيرة. ^{[ 15 ]} لهذه المشكلة أهمية عملية كبيرة، بالإضافة إلى مجالات النقل والخدمات اللوجستية الواضحة. ومن الأمثلة الكلاسيكية على ذلك تصنيع الدوائر المطبوعة : جدولة مسار آلة الحفر لحفر ثقوب في لوحة الدوائر المطبوعة. في تطبيقات التشغيل الآلي أو الحفر الروبوتية، تُمثل "المدن" الأجزاء المراد تشكيلها أو الثقوب (بأحجام مختلفة) المراد حفرها، وتشمل "تكلفة السفر" وقت إعادة تجهيز الروبوت (مشكلة تسلسل مهام آلة واحدة). ^{[ 16 ]}
• تُعرف مسألة البائع المتجول المعممة ، أو "مسألة السياسي المتجول"، بأنها مسألة تتعلق بـ"ولايات" تضم مدينة واحدة أو أكثر، ويتعين على البائع زيارة مدينة واحدة فقط من كل ولاية. يُستخدم هذا المفهوم في ترتيب حلول لمسألة مخزون القطع بهدف تقليل عدد مرات تغيير السكاكين. كما يُستخدم في عمليات الحفر في صناعة أشباه الموصلات ؛ انظر على سبيل المثال براءة الاختراع الأمريكية رقم 7,054,798 . وقد أثبت نون وبين إمكانية تحويل مسألة البائع المتجول المعممة إلى مسألة البائع المتجول القياسية بنفس عدد المدن، ولكن بمصفوفة مسافة معدلة .
• تتناول مشكلة الترتيب التسلسلي مشكلة زيارة مجموعة من المدن، حيث توجد علاقات أسبقية بين المدن.
• أحد الأسئلة الشائعة في مقابلات العمل في جوجل هو كيفية توجيه البيانات بين عقد معالجة البيانات؛ تختلف المسارات حسب وقت نقل البيانات، ولكن تختلف العقد أيضًا حسب قدرتها الحاسوبية وسعة التخزين، مما يزيد من مشكلة مكان إرسال البيانات.
• تتناول مسألة المشتري المتجول مشتريًا مكلفًا بشراء مجموعة من المنتجات. يمكنه شراء هذه المنتجات من عدة مدن، ولكن بأسعار مختلفة، ولا تقدم جميع المدن نفس المنتجات. الهدف هو إيجاد مسار بين مجموعة فرعية من المدن يقلل التكلفة الإجمالية (تكلفة السفر + تكلفة الشراء) ويتيح شراء جميع المنتجات المطلوبة.

بالإضافة إلى${\displaystyle x_{ij}}$المتغيرات كما هو موضح أعلاه، يوجد لكل منها${\displaystyle i=1,\ldots ,n}$متغير وهمي${\displaystyle u_{i}}$يتتبع هذا الترتيب الذي تتم به زيارة المدن، بدءًا من المدينة${\displaystyle 1}$والتفسير هو أن${\displaystyle u_{i}<u_{j}}$يشير إلى المدينة${\displaystyle i}$تتم زيارتها قبل المدينة${\displaystyle j.}$بالنسبة لجولة معينة (كما هو مُشفّر في قيم${\displaystyle x_{ij}}$(المتغيرات)، يمكن للمرء أن يجد قيمًا مرضية لـ${\displaystyle u_{i}}$المتغيرات عن طريق جعل${\displaystyle u_{i}}$يساوي عدد الحواف على طول تلك الجولة، عند الانتقال من المدينة${\displaystyle 1}$إلى المدينة${\displaystyle i.}$^{[ 22 ]}

لأن البرمجة الخطية تفضل المتباينات غير الصارمة (${\displaystyle \geq }$) على أساس صارم (${\displaystyle >}$)، نود فرض قيود بحيث

${\displaystyle u_{j}\geq u_{i}+1}$لو${\displaystyle x_{ij}=1.}$

مجرد اشتراط${\displaystyle u_{j}\geq u_{i}+x_{ij}}$لن يتحقق ذلك، لأن هذا يتطلب أيضاً${\displaystyle u_{j}\geq u_{i}}$متى${\displaystyle x_{ij}=0,}$وهذا غير صحيح. بدلاً من ذلك، استخدم MTZ${\displaystyle n(n-1)}$القيود الخطية

${\displaystyle u_{i}-u_{j}+1\leq (n-1)(1-x_{ij})}$لجميع المتميزين${\displaystyle i,j\in \{2,\dotsc ,n\},}$

حيث الحد الثابت${\displaystyle n-1}$يوفر ذلك هامشاً كافياً بحيث${\displaystyle x_{ij}=0}$لا يفرض علاقة بين${\displaystyle u_{j}}$و${\displaystyle u_{i}.}$

الطريقة التي${\displaystyle u_{i}}$ثم تفرض المتغيرات أن جولة واحدة تشمل جميع المدن، مما يؤدي إلى زيادة عدد الزوار بنسبة لا تقل عن${\displaystyle 1}$لكل خطوة على طول الجولة، مع السماح بالتخفيض فقط عندما تمر الجولة عبر المدينة ${\displaystyle 1.}$سيتم انتهاك هذا القيد من قبل كل جولة لا تمر عبر المدينة ${\displaystyle 1,}$لذا فإن الطريقة الوحيدة لإرضائه هي أن تمر الجولة بالمدينة ${\displaystyle 1}$كما يمر عبر جميع المدن الأخرى.

وبالتالي، فإن صياغة MTZ لمسألة البائع المتجول هي مسألة البرمجة الخطية الصحيحة التالية:

${\displaystyle {\begin{aligned}\min \sum _{i=1}^{n}\sum _{j\neq i,j=1}^{n}c_{ij}x_{ij}&\colon &&\\x_{ij}\in {}&\{0,1\}&&i,j=1,\ldots ,n;\\\sum _{i=1,i\neq j}^{n}x_{ij}={}&1&&j=1,\ldots ,n;\\\sum _{j=1,j\neq i}^{n}x_{ij}={}&1&&i=1,\ldots ,n;\\u_{i}-u_{j}+1\leq {}&(n-1)(1-x_{ij})&&2\leq i\neq j\leq n;\\2\leq u_{i}\leq {}&n&&2\leq i\leq n.\end{aligned}}}$

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

قم بتسمية المدن بالأرقام من 1 إلى n ، ثم حددها كما يلي:

${\displaystyle x_{ij}={\begin{cases}1&{\text{the path goes from city }}i{\text{ to city }}j\\0&{\text{otherwise.}}\end{cases}}}$

يأخذ${\displaystyle c_{ij}>0}$إذا كانت المسافة من المدينة i إلى المدينة j هي . عندئذٍ، يمكن كتابة مسألة البائع المتجول (TSP) على النحو التالي:

${\displaystyle {\begin{aligned}\min &\sum _{i=1}^{n}\sum _{j\neq i,j=1}^{n}c_{ij}x_{ij}\colon &&\\&\sum _{i=1,i\neq j}^{n}x_{ij}=1&&j=1,\ldots ,n;\\&\sum _{j=1,j\neq i}^{n}x_{ij}=1&&i=1,\ldots ,n;\\&\sum _{i\in Q}{\sum _{j\neq i,j\in Q}{x_{ij}}}\leq |Q|-1&&\forall Q\subsetneq \{1,\ldots ,n\},|Q|\geq 2.\\\end{aligned}}}$

يضمن القيد الأخير في صياغة DFJ، والذي يُسمى قيد استبعاد المسارات الفرعية ، عدم إمكانية تشكيل أي مجموعة جزئية فعلية Q مسارًا فرعيًا، وبالتالي فإن الحل الناتج هو مسار واحد وليس اتحاد مسارات أصغر. وبشكل بديهي، بالنسبة لكل مجموعة جزئية فعلية Q من المدن، يتطلب هذا القيد أن يكون عدد الحواف في Q أقل من عدد المدن فيها: فلو كان عدد الحواف في Q مساويًا لعدد المدن فيها، لكان ذلك يُمثل مسارًا فرعيًا لمدن Q. ولأن هذا يؤدي إلى عدد هائل من القيود المحتملة، فإنه يُحل عمليًا باستخدام توليد الصفوف . ^{[ 23 ]}

الحل الأكثر مباشرة هو تجربة جميع التباديل (التوافيق المرتبة) ومعرفة أيها الأقل تكلفة (باستخدام البحث الشامل ). يقع وقت تشغيل هذا النهج ضمن عامل كثير الحدود من${\displaystyle O(n!)}$، مضروب عدد المدن، لذا يصبح هذا الحل غير عملي حتى بالنسبة لـ 20 مدينة فقط.

تُعد خوارزمية هيلد-كارب واحدة من أقدم تطبيقات البرمجة الديناميكية ، والتي تحل المشكلة في وقت${\displaystyle O(n^{2}2^{n})}$[ ^{24 ]​}

يبدو أن تحسين هذه الحدود الزمنية أمر صعب. على سبيل المثال، لم يتم تحديد ما إذا كانت الخوارزمية الكلاسيكية الدقيقة لمسألة البائع المتجول التي تعمل في وقت محدد ستفي بالغرض.${\displaystyle O(1.9999^{n})}$موجود. ^{[ 25 ]} أفضل خوارزمية كمومية دقيقة حاليًا لمسألة البائع المتجول، والتي وضعها أمبينيس وآخرون، تعمل في وقت${\displaystyle O(1.728^{n})}$[ ^{26 ]​}

وتشمل الأساليب الأخرى ما يلي:

• خوارزميات التفرع والتقييد المختلفة ، والتي يمكن استخدامها لمعالجة مسائل البائع المتجول التي تحتوي على آلاف المدن.

• تستخدم خوارزميات التحسين التدريجي تقنيات تُذكّر بالبرمجة الخطية . وهذا الأسلوب فعال لما يصل إلى 200 مدينة.
• تُعدّ تطبيقات خوارزمية التفرع والتقييد وتوليد القطع الخاص بالمسألة ( التفرع والقطع ^{[ 27 ]} )؛ ^{[ 28 ]} الطريقة المُفضّلة لحلّ المسائل الكبيرة. ويحمل هذا النهج الرقم القياسي الحالي، حيث حلّ مسألة تضمّ 85900 مدينة، انظر Applegate et al. (2006) .

تم التوصل إلى حل دقيق لـ 15112 مدينة ألمانية من قاعدة بيانات TSPLIB في عام 2001 باستخدام طريقة القطع المستوي التي اقترحها جورج دانتزيج وراي فولكرسون وسيلمر إم. جونسون عام 1954، والمبنية على البرمجة الخطية . أُجريت الحسابات على شبكة من 110 معالجات موزعة بين جامعتي رايس وبرينستون . بلغ إجمالي وقت الحساب ما يعادل 22.6 عامًا على معالج ألفا واحد بتردد 500 ميجاهرتز . وفي مايو 2004، تم حل مسألة البائع المتجول المتمثلة في زيارة جميع مدن السويد البالغ عددها 24978 مدينة: حيث تم التوصل إلى مسار يبلغ طوله حوالي 72500 كيلومتر، وثبت أنه لا يوجد مسار أقصر منه. ^{[ 29 ]} في مارس 2005، تم حل مسألة البائع المتجول (TSP) التي تتطلب زيارة جميع النقاط البالغ عددها 33,810 نقطة على لوحة دوائر كهربائية باستخدام برنامج Concorde TSP Solver : حيث تم التوصل إلى مسار بطول 66,048,945 وحدة، وثبت عدم وجود مسار أقصر. استغرقت عملية الحساب حوالي 15.7 سنة من وقت المعالجة (Cook et al. 2006). وفي أبريل 2006، تم حل مسألة أخرى تحتوي على 85,900 نقطة باستخدام برنامج Concorde TSP Solver ، واستغرقت أكثر من 136 سنة من وقت المعالجة؛ انظر Applegate et al. (2006) .  

تم ابتكار العديد من الخوارزميات الاستدلالية والتقريبية التي تُنتج حلولاً جيدة بسرعة، ومنها خوارزمية الأجزاء المتعددة . تستطيع الطرق الحديثة إيجاد حلول لمسائل ضخمة للغاية (تشمل ملايين المدن) في غضون فترة زمنية معقولة، وتكون هذه الحلول، باحتمالية عالية، على بُعد 2-3% فقط من الحل الأمثل. ^{[ 14 ]}

تم التعرف على عدة فئات من الأساليب الاستدلالية.

الاستدلالات البنّاءة

تُمكّن خوارزمية أقرب جار (NN) (وهي خوارزمية جشعة ) البائع من اختيار أقرب مدينة لم يزرها بعد كخطوة تالية. تُنتج هذه الخوارزمية بسرعة مسارًا قصيرًا فعالًا. بالنسبة لعدد N من المدن الموزعة عشوائيًا على مستوى، تُنتج الخوارزمية في المتوسط ​​مسارًا أطول بنسبة 25% من أقصر مسار ممكن؛ ^{[ 30 ]} ومع ذلك، توجد العديد من توزيعات المدن ذات الترتيبات الخاصة التي تجعل خوارزمية أقرب جار تُعطي أسوأ مسار. ^{[ 31 ]} ينطبق هذا على كل من مسائل البائع المتجول غير المتماثلة والمتماثلة. ^{[ 32 ]} أظهر روزنكرانتز وآخرون ^{[ 33 ]} أن خوارزمية أقرب جار لها عامل تقريب${\displaystyle \Theta (\log |V|)}$في الحالات التي تحقق متباينة المثلث، يمكن لخوارزمية الشبكة العصبية، وهي نوع معدل يُسمى عامل أقرب جزء (NF)، والذي يربط مجموعة (جزءًا) من المدن غير المزارة الأقرب، إيجاد مسارات أقصر مع تكرارات متتالية. ^{[ 34 ]} كما يمكن تطبيق عامل أقرب جزء على حل أولي تم الحصول عليه بواسطة خوارزمية الشبكة العصبية لتحسينه في نموذج نخبة، حيث لا تُقبل إلا الحلول الأفضل.

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

هناك طريقة استدلالية بناءة أخرى ، وهي طريقة المطابقة المزدوجة والربط (MTS)، التي تُجري عمليتي مطابقة متتاليتين ، حيث تُنفذ المطابقة الثانية بعد حذف جميع حواف المطابقة الأولى، لإنتاج مجموعة من الحلقات. ثم تُربط هذه الحلقات لإنتاج المسار النهائي. ^{[ 35 ]}

خوارزمية كريستوفيدس وسيرديوكوف

تتبع خوارزمية كريستوفيدس وسيرديوكوف مخططًا مشابهًا، لكنها تجمع بين الشجرة الممتدة الدنيا وحل مشكلة أخرى، وهي المطابقة المثالية ذات الوزن الأدنى . ينتج عن ذلك مسارٌ لمسألة البائع المتجول (TSP) لا يتجاوز طوله 1.5 ضعف المسار الأمثل. كانت هذه الخوارزمية من أوائل خوارزميات التقريب ، وكان لها دورٌ في لفت الانتباه إلى خوارزميات التقريب كنهج عملي لحل المشكلات المعقدة . في الواقع، لم يُستخدم مصطلح "خوارزمية" على نطاق واسع ليشمل خوارزميات التقريب إلا لاحقًا؛ فقد كانت خوارزمية كريستوفيدس تُعرف في البداية باسم "الأسلوب الاستدلالي لكريستوفيدس". ^{[ 10 ]}

تعتمد هذه الخوارزمية على منظور مختلف باستخدام نتيجة من نظرية الرسوم البيانية، مما يُسهم في تحسين الحد الأدنى لمسألة البائع المتجول (TSP) الناتج عن مضاعفة تكلفة الشجرة الممتدة الدنيا. بفرض وجود رسم بياني أويلري ، يمكننا إيجاد مسار أويلري في ⁠${\displaystyle O(n)}$[ ^{6 ]} لذا ،إذا كان لدينا رسم بياني أويلري بمدن من مسألة البائع المتجول (TSP) كرؤوس، فمن السهل أن نرى أنه يمكننا استخدام هذه الطريقة لإيجاد مسار أويلري لإيجاد حل لمسألة البائع المتجول. من خلال ^{متباينة} المثلث ، نعلم أن مسار مسألة البائع المتجول لا يمكن أن يكون أطول من مسار أويلري، وبالتالي لدينا حد أدنى لمسألة البائع المتجول. هذه الطريقة موصوفة أدناه.

1. أوجد شجرة ممتدة دنيا للمسألة.
2. قم بإنشاء نسخ مكررة لكل حافة لإنشاء رسم بياني أويلري.
3. أوجد مسارًا أويلريًا لهذا الرسم البياني.
4. التحويل إلى TSP: إذا تمت زيارة مدينة مرتين، فقم بإنشاء طريق مختصر من المدينة السابقة في الجولة إلى المدينة التي تليها.

لتحسين الحد الأدنى، نحتاج إلى طريقة أفضل لإنشاء رسم بياني أويلري. وبحسب متباينة المثلث، يجب أن يكون لأفضل رسم بياني أويلري نفس تكلفة أفضل جولة لبائع متجول؛ لذا، فإن إيجاد الرسوم البيانية الأويلرية المثلى لا يقل صعوبة عن مسألة البائع المتجول. إحدى طرق القيام بذلك هي مطابقة الوزن الأدنى باستخدام خوارزميات ذات تعقيد من${\displaystyle O(n^{3})}$[ ^{6 ]​}

يبدأ تحويل الرسم البياني إلى رسم بياني أويلري بالشجرة الممتدة الدنيا؛ ثم يجب جعل جميع الرؤوس ذات الرتبة الفردية زوجية، لذا يجب إضافة مطابقة للرؤوس ذات الدرجة الفردية، مما يزيد رتبة كل رأس ذي درجة فردية بمقدار 1. ^{[ 6 ]} ينتج عن ذلك رسم بياني تكون فيه جميع الرؤوس ذات رتبة زوجية، وهو بالتالي رسم بياني أويلري. بتطبيق الطريقة المذكورة أعلاه، نحصل على خوارزمية كريستوفيدس وسيرديوكوف:

1. أوجد شجرة ممتدة دنيا للمسألة.
2. قم بإنشاء مطابقة للمشكلة مع مجموعة المدن ذات الترتيب الفردي.
3. أوجد مسارًا أويلريًا لهذا الرسم البياني.
4. التحويل إلى صيغة TSP باستخدام الاختصارات.

تبادل الأزواج

تتضمن تقنية التبادل الثنائي، أو تقنية 2-opt، إزالة حافتين بشكل متكرر واستبدالهما بحافتين مختلفتين تعيدان ربط الأجزاء الناتجة عن إزالة الحواف في مسار جديد أقصر. وبالمثل، تزيل تقنية 3-opt ثلاث حواف وتعيد ربطها لتشكيل مسار أقصر. هذه حالات خاصة من طريقة k -opt. يُعدّ مصطلح Lin–Kernighan تسمية خاطئة شائعة لتقنية 2-opt؛ إذ إن Lin–Kernighan هي في الواقع طريقة k -opt الأكثر عمومية .

بالنسبة للمسائل الإقليدية، تُعطي الطرق الاستدلالية ثنائية التحسين حلولاً أفضل بنسبة 5% تقريبًا من تلك التي تُنتجها خوارزمية كريستوفيدس. إذا بدأنا بحل أولي تم إنشاؤه باستخدام خوارزمية جشعة ، فإن متوسط ​​عدد الحركات ينخفض ​​بشكل كبير مرة أخرى ويصبح ⁠${\displaystyle O(n)}$; ومع ذلك، بالنسبة للبدايات العشوائية، فإن متوسط ​​عدد الحركات هو ⁠${\displaystyle O(n\log(n))}$على الرغم من أن هذه الزيادة طفيفة في الحجم، إلا أن عدد الحركات الأولية للمسائل الصغيرة يكون أكبر بعشر مرات عند البدء العشوائي مقارنةً بالبدء باستخدام خوارزمية جشعة. ويعود ذلك إلى أن هذه الخوارزميات من نوع 2-opt تستغل الجوانب "السيئة" في الحل، مثل التقاطعات. تُستخدم هذه الأنواع من الخوارزميات غالبًا في مسائل توجيه المركبات لإعادة تحسين حلول المسارات. ^{[ 30 ]}

تحسين مستعمرة النمل

وصف الباحث في مجال الذكاء الاصطناعي، ماركو دوريغو، عام 1993، طريقةً لتوليد "حلول جيدة" لمسألة البائع المتجول (TSP) باستخدام محاكاة لمستعمرة نمل تُسمى نظام مستعمرة النمل ( ACS ). ^{[ 37 ]} وهي تُحاكي سلوك النمل الحقيقي في البحث عن أقصر المسارات بين مصادر الغذاء وعشه، وهو سلوك ناشئ عن ميل كل نملة إلى اتباع الفيرومونات التي تتركها النملات الأخرى.

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

في مسألة البائع المتجول المترية ، والمعروفة أيضًا باسم دلتا-البائع المتجول أو Δ-البائع المتجول، فإن المسافات بين المدن تحقق متباينة المثلث .

من القيود الطبيعية جداً لمسألة البائع المتجول (TSP) اشتراط أن تشكل المسافات بين المدن مقياساً لتحقيق متباينة المثلث ؛ أي أن الاتصال المباشر من A إلى B لا يكون أبعد من الطريق عبر المدينة الوسيطة C :

${\displaystyle d_{AB}\leq d_{AC}+d_{CB}}$.

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

فيما يلي بعض الأمثلة على مقاييس TSP لمختلف المقاييس.

• في مسألة البائع المتجول الإقليدية (انظر أدناه)، المسافة بين مدينتين هي المسافة الإقليدية بين النقاط المتناظرة.
• في مسألة البائع المتجول المستقيمة، تُحسب المسافة بين مدينتين بجمع القيم المطلقة للفرق بين إحداثياتهما السينية والصادية . ويُطلق على هذا المقياس غالبًا اسم مسافة مانهاتن أو مقياس كتلة المدينة.
• في المقياس الأقصى ، تكون المسافة بين نقطتين هي القيمة القصوى للقيم المطلقة للفروق بين إحداثياتهما x و y .

يظهر المقياسان الأخيران، على سبيل المثال، في توجيه آلة تحفر مجموعة معينة من الثقوب في لوحة دوائر مطبوعة . يتوافق مقياس مانهاتن مع آلة تُعدّل إحداثية واحدة أولًا، ثم الأخرى، لذا فإن زمن الانتقال إلى نقطة جديدة هو مجموع زمنَي الحركتين. أما مقياس الحد الأقصى فيتوافق مع آلة تُعدّل كلا الإحداثيين في آنٍ واحد، لذا فإن زمن الانتقال إلى نقطة جديدة هو زمن الحركة الأبطأ من بين الحركتين.

لا يسمح تعريف مسألة البائع المتجول (TSP) بزيارة المدن مرتين، لكن العديد من التطبيقات لا تحتاج إلى هذا القيد. في مثل هذه الحالات، يمكن اختزال نموذج متناظر غير متري إلى نموذج متري. يؤدي هذا إلى استبدال الرسم البياني الأصلي برسم بياني كامل تكون فيه المسافة بين المدن${\displaystyle d_{AB}}$يتم استبدالها بأقصر طول مسار بين A و B في الرسم البياني الأصلي.

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

على غرار مسألة البائع المتجول العامة، تُعدّ مسألة البائع المتجول الإقليدية الدقيقة مسألة صعبة الحل (NP-hard)، إلا أن مشكلة مجاميع الجذور تُشكّل عائقًا أمام إثبات أن صيغة القرار الخاصة بها تنتمي إلى فئة NP، وبالتالي فهي مسألة كاملة الحل (NP-complete). وتُعتبر الصيغة المُجزأة للمسألة، مع تقريب المسافات إلى أعداد صحيحة، مسألة كاملة الحل (NP-complete). ^{[ 39 ]} وباستخدام الإحداثيات النسبية والمقياس الإقليدي الفعلي، من المعروف أن مسألة البائع المتجول الإقليدية تنتمي إلى التسلسل الهرمي للعد، ^{[ 40 ]} وهي فئة فرعية من PSPACE . أما باستخدام إحداثيات حقيقية عشوائية، فلا يمكن أن تنتمي مسألة البائع المتجول الإقليدية إلى هذه الفئات، نظرًا لوجود عدد لا يُحصى من المدخلات المحتملة. وعلى الرغم من هذه التعقيدات، فإن مسألة البائع المتجول الإقليدية أسهل بكثير من حالة المقياس العام من حيث التقريب. ^{[ 41 ]} على سبيل المثال، الشجرة الممتدة الدنيا للرسم البياني المرتبط بحالة من مسائل البائع المتجول الإقليدية هي شجرة ممتدة دنيا إقليدية ، وبالتالي يمكن حسابها في زمن متوقع قدره O ( n log n ) لعدد n من النقاط (وهو أقل بكثير من عدد الحواف). وهذا يُمكّن خوارزمية التقريب البسيطة من الدرجة 2 لمسألة البائع المتجول مع متباينة المثلث المذكورة أعلاه من العمل بسرعة أكبر.

بشكل عام، لأي قيمة c > 0، حيث d هو عدد الأبعاد في الفضاء الإقليدي، توجد خوارزمية ذات زمن متعدد الحدود تجد مسارًا بطول لا يتجاوز (1 + 1/ c ) ضعف الطول الأمثل للحالات الهندسية لمسألة البائع المتجول (TSP) في

${\displaystyle O{\left(n(\log n)^{O(c{\sqrt {d}})^{d-1}}\right)}}$

الوقت؛ وهذا ما يسمى مخطط تقريب متعدد الحدود (PTAS). ^{[ 42 ]} حصل سانجيف أرورا وجوزيف إس بي ميتشل على جائزة غودل في عام 2010 لاكتشافهما المتزامن لمخطط تقريب متعدد الحدود لمسألة البائع المتجول الإقليدية.

في الواقع العملي، لا تزال تُستخدم أساليب استدلالية أبسط ذات ضمانات أضعف.

في معظم الحالات، تكون المسافة بين عقدتين في شبكة TSP متساوية في كلا الاتجاهين. أما الحالة التي لا تتساوى فيها المسافة من A إلى B مع المسافة من B إلى A فتُسمى TSP غير متناظر. ومن التطبيقات العملية لـ TSP غير المتناظر تحسين المسارات باستخدام توجيه الشوارع (الذي يصبح غير متناظر بسبب الشوارع ذات الاتجاه الواحد، والطرق الفرعية، والطرق السريعة، وما إلى ذلك).

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

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

يفترض${\displaystyle X_{1},\ldots ,X_{n}}$نكون${\displaystyle n}$متغيرات عشوائية مستقلة ذات توزيع منتظم في المربع${\displaystyle [0,1]^{2}}$ودع${\displaystyle L_{n}^{\ast }}$ليكن طول أقصر مسار (أي حل مسألة البائع المتجول) لهذه المجموعة من النقاط، وفقًا للمسافة الإقليدية المعتادة . ومن المعروف ^{[ 9 ]} أنه، بشكل شبه مؤكد،

${\displaystyle {\frac {L_{n}^{*}}{\sqrt {n}}}\rightarrow \beta \qquad {\text{when }}n\to \infty ,}$

أين${\displaystyle \beta }$هو ثابت موجب غير معروف صراحةً. بما أن${\displaystyle L_{n}^{*}\leq 2{\sqrt {n}}+2}$(انظر أدناه)، ويترتب على ذلك من نظرية التقارب المحدود أن${\displaystyle \beta =\lim _{n\to \infty }\mathbb {E} [L_{n}^{*}]/{\sqrt {n}}}$وبالتالي، الحدود الدنيا والعليا لـ${\displaystyle \beta }$اتبع من الحدود على${\displaystyle \mathbb {E} [L_{n}^{*}]}$.

الحد شبه المؤكد${\displaystyle {\frac {L_{n}^{*}}{\sqrt {n}}}\rightarrow \beta }$مثل${\displaystyle n\to \infty }$قد لا يكون موجودًا إذا كانت المواقع المستقلة${\displaystyle X_{1},\ldots ,X_{n}}$يتم استبدالها بملاحظات من عملية إرجودية ثابتة ذات هوامش منتظمة. ^{[ 44 ]}

في الحالة العامة، يُعدّ إيجاد أقصر مسار لبائع متجول مسألةً كاملةً من فئة NPO . ^{[ 52 ]} إذا كان مقياس المسافة متريًا (وبالتالي متناظرًا)، تصبح المسألة كاملةً من فئة APX ، ^{[ 53 ]} ويُقاربها خوارزمية كريستوفيدس وسيرديوكوف في حدود 1.5. ^{[ 54 ] [ 55 ] [ 10 ]}

إذا اقتصرت المسافات على 1 و2 (مع بقائها مقياسًا)، فإن نسبة التقريب تصبح 8/7. ^{[ 56 ]} في الحالة غير المتناظرة مع متباينة المثلث ، في عام 2018، طوّر سفينسون وتارناوسكي وفيغ تقريبًا بمعامل ثابت. ^{[ 57 ]} حققت خوارزمية من تأليف فيرا تراوب وجينس فيجن نسبة أداء قدرها${\displaystyle 22+\varepsilon }$[ ^{58 ]} تم تحسين هذا العامل بشكل أكبر ^إلى${\displaystyle 17+\varepsilon }$[ ^{59 ]} أفضل حد معروف لعدم التقريب هو 75/74 ^{. [ 60 ]}

يمكن تقريب مسألة تعظيم إيجاد أطول مسار لبائع متجول في حدود 63/38. ^{[ 61 ]} إذا كانت دالة المسافة متناظرة، فيمكن تقريب أطول مسار في حدود 4/3 باستخدام خوارزمية حتمية ^{[ 62 ]} وفي حدود${\displaystyle (33+\varepsilon )/25}$بواسطة خوارزمية عشوائية . ^{[ 63 ]}