A novel discretization scheme for the close enough traveling salesman problem

این مقاله به یک نوع از فروشنده فروشنده سفر اقلیدسی اشاره دارد که در آن مسافر از یک گره عبور می کند، اگر از طریق محله مجموعه گره عبور کند. این مشکل به عنوان یک فروشنده معروف به اندازه کافی معروف است. ما یک طرح جدید تشریح موثر را معرفی می کنیم که به ما امکان می دهد که هر دو حد پایین و بالایی را برای راه حل بهینه محاسبه کنیم. علاوه بر این، ما یک الگوریتم کاهش گراف را اعمال می کنیم که به طور قابل توجهی حجم مسئله را کاهش می دهد و محاسبات محدوده را سرعت می بخشد. ما اثربخشی و عملکرد رویکرد ما را در چندین مثال معیار ارزیابی می کنیم. نتایج محاسباتی نشان می دهد که الگوریتم ما سریع تر از الگوریتم های دیگر موجود در ادبیات است و محدودیت هایی که ارائه می دهد تقریبا همیشه دقیق تر است.