X
تبلیغات
وکیل جرایم سایبری

SIA: Swarm Intelligence Algorithms

دیتاست : TSPLIB

اصلی ترین آدرس سایت که نشان دهنده آمار و نتایج مقایسات، بهترین جواب ها برای حل مسئله TSP با تعداد n مختلف می باشد  http://elib.zib.de/pub/mp-testdata/tsp/tsplib/tsplib.html  است. در ادامه دو سایت که به TSPLib پرداخته است معرفی می شود:

سایت اول:

توضیحات آدرس سایت http://elib.zib.de/pub/mp-testdata/tsp/tsplib/tsplib.html :

در سال 1991 اولین دیتاست TSP در مقاله TSPLIB-A traveling Salesman problem Library توسط Reinelt Gerhard ارائه گردید. در سایت های مربوط به دیتاست TSP  از نماد شکل 1 استفاده شده است.

شکل 1: نماد دیتاست TSPlib

در این سایت TSPLib را یک کتابخانه ای از نمونه های ساده برای TSP معرفی کرده است که شامل منابع و انواع مختلف می باشد. نمونه هایی از دسته بندی مسئله در ذیل آورده شده است:1. مسئله فروشنده دوره گرد (TSP) 2. مسئله دور هامیلتونی (HCP) 3. مسئله فروشنده دوره گرد نامتقارن (ATSP) 4. مسئله مرتب سازی ترتیبی (SOP) 5. مسئله مسیریابی وسیله نقلیه طرفیت دار (CVRP). در این سایت به معرفی و دیتاست هر کدام از دسته ها پرداخته است. در اینجا فقط به مسئله فروشنده دوره گرد پرداخته می شود.

مسئله فروشنده دوره گرد (TSP): این مسئله شامل n گره و فاصله هایی برای هر زوج از گره ها می باشد. هدف پیدا کردن جمع کل حداقل به طوری که هر گره فقط یکبار ملاقات شود. همچنین در این مسئله فاصله بین گره i تا j برابر است با j تا i . همان طور که در شکل 2 نشان داده شده است، در قسمت TSP data آن مسائل مختلف از TSP با اندازه های مختلف تعریف شده است. که معمولاً اندازه مسئله بزرگ می باشد. داده هایی که برای هر مسئله تعریف شده است به صورت مختصات بوده و در واقع یک ماتریس ارائه می دهد که دو ستونی است و هر سطر نشان دهنده مختصات یک نقطه است. در قسمت Best known solutions for symmetric TSPs فقط بهترین جواب برای هر مسئله ارائه گردیده است. آخرین بروزرسانی این سایت در سال 1997 انجام شده است. در این سایت همچنین دو سایت http://elib.zib-berlin.de/pub/Packages/mp-testdata/tsp/index.html ،                          http://nhse.cs.rice.edu/softlib/catalog/tsplib.html برای بررسی بیشتر TSPlib معرفی شده است. که متاسفانه این سایت ها غیرفعال شده اند.

 

شکل 2 : نمونه مسئله از سایت  http://elib.zib.de/pub/mp-testdata/tsp/tsplib/tsplib.html

سایت دوم:

در سایت https://www.iwr.uni-heidelberg.de/groups/comopt/software/TSPLIB95/index.html در سال 2013 به منظور سهولت دسترسی به داده ها فرمت xml نیز برای نمایش داده ها ارائه شده است. این سایت یک بروزرسانی از سایت اول می باشد. همچنین در این سایت داده ها و بهترین راه حل ها نیز در سال 2007 بروزرسانی گردیده است. لازم به توضیح است که در صفحه اصلی این سایت علاوه بر TSP به مسائل دیگر نیز پرداخته شده است.

 

 [1]. Gerhard  Reinelt, “TSPLIB-A traveling Salesman problem Library”,1991.

[2]. http://elib.zib.de/pub/mp-testdata/tsp/tsplib/tsp/.