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

SIA: Swarm Intelligence Algorithms

دیتاست: مسئله فروشنده دوره گرد عمومی (GTSP):

تعریف مسئله فروشنده دوره گرد عمومی (GTSP):

منظور از مسئله فروشنده دوره گرد عمومی یا Generalized Traveling Salesman Problem تغییر یافته مسئله فروشنده دوره گرد متقارن است که در آن گره ها به خوشه هایی تقسیم می شوند و هر گره از خوشه دقیقاً یکبار در هر چرخه ملاقات می شود. کاربردهای متعدد آن عبارت است از : مسیریابی هواپیما، مرتب سازی فایل های کامپیوتر و تحویل پست. در واقع مسئله فروشنده دوره گرد عمومی یک نوع دیگری از مسئله فروشنده دوره گرد معروف می باشد که در آن همانند TSP، گراف شامل n گره می باشد که هزینه بین دو گره هم مشخص می باشد. همچنین مانند مسئله TSP ، مسئله فروشنده دوره گرد عمومی نیز یک مسئله NP-hard می باشد. تفاوت آن با TSPدر این است که ، بر خلاف TSP که به دنبال حداقل هزینه مسیر در گراف است به طوری که از هر گره دقیقاً یکبار عبور کند، مجموعه گره هایی که به m خوشه تقسیم شده اند راه حل بهینه برای بدست آوردن حداقل هزینه یک چرخه ای است که دقیقاً یک گره از هر خوشه را ملاقات کند. در شکل 1 نمونه ای از GTSP با سه خوشه آورده شده است که در آن برای بدست آوردن حداقل هزینه از هر خوشه دقیقاً یک گره انتخاب شده است. این نوع از GTSP مرسوم به مسئله فروشنده دوره گرد عمومی تساوی (E-GTSP) می باشد.

شکل 1: مسئله فروشنده دوره گرد عمومی با سه خوشه

در شکل 2 یک مثال دیگر از مسئله فروشنده دوره گرد عمومی با سه خوشه با جزئیات بیشتر آورده شده است.


شکل 2: مسئله فروشنده دوره گرد عمومی با سه خوشه

نوع های دیگری از مسئله فروشنده دوره گرد عمومی وجود دارد که به جای انتخاب دقیقاً یک گره از حداقل یک گره در هر خوشه استفاده می کنند.

دیتاست های مسئله فروشنده دوره گرد عمومی:

در سال 1997 فیشیتی، سالازار گونزالس و توس یک فرآیند خوشه سازی ساده که می تواند برای ایجاد نمونه های GTSP استفاده شود معرفی کردند.

یکی از سایت هایی که در آن دیتاست های مسئله فروشنده دوره گرد عمومی وجود دارد http://www.cs.nott.ac.uk/~pszdk/gtsp.html می باشد که توسط دانیل کاراپتیان ایجاد و نگهداری می شود. برای نمونه دیتاست 3Burma14 در شکل 3 نشان داده شده است که در آن یک مسئله فروشنده دوره گرد عمومی با چهارده گره و سه خوشه می باشد و یک ماتریس 14*14 نشان دهنده فاصله گره ها از یکدیگر می باشد.

 

شکل 3: دیتاست 3Burma14

 

همچنین در فایل های جداگانه بهترین جواب هایی که تاکنون بدست آمده اند، گنجانده شده است. که در آن علاوه بر بهترین جواب مسیر راه حلی که به بهترین جواب منجر می شود نیز ذکر شده است. آخرین بروزرسانی این سایت در سال 2012 انجام شده است.

 

 [1]. John Silberholz ,Bruce L. Golden, “The Generalized Traveling Salesman Problem: A New Genetic Algorithm Approach”, Proceedings of the 10th INFORMS Computing Society Conference: 165-181.,2007.

 [2]. http://www.cs.nott.ac.uk/~pszdk/gtsp.html.

 

 

دیتاست : 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/.

 

 

دیتاست : QAPLIB

آدرس سایت که نشان دهنده آمار و نتایج مقایسات، بهترین جواب ها برای حل مسئله QAP با تعداد n مختلف،  http://anjos.mgi.polymtl.ca/qaplib/ می باشد. برای ورود به این سایت نیازمند به فیلتر شکن می باشد. بخش های مهم این سایت در ذیل به اختصار توضیح داده شده است.  

تاریخچه سایت QAPlib :

در مقدمه سایت اشاره به مسئله تخصیص درجه دوم دارد که یکی از مسائل بزرگ بهینه سازی ترکیبی می باشد. QAPlib اولین بار در سال 1991 به منظور تست جامع QAP منتشر شده است. این بستر به همراه کلیه نمونه ها برای جامعه علمی قابل دسترس در آن سالها بوده است. با توجه به تقاضا برای این نمونه ها، و بازخورد علی از محققان زیاد، در سال 1994 توسط  بارکارد، کاریچ و رندل یک بروزرسانی اساسی انجام شد. در این بروزرسانی نمونه های جدید زیادی که توسط محققان در کارهای خودشان انجام داده بودند به مجموعه قبلی اضافه شدند. علاوه بر این، یک لیستی شامل بهترین راه حل ممکن و بهترین راه حل (کوچک ترین) برای حل مسئله QAP برای نمونه های مختلف ارائه گردید.

در سال 1996 این اطلاعات در وب جهانی قرار گرفت. و از سوی دیگر با توجه به فعالیت ها روی QAP زیاد شده بود یک لیست کوتاهی از رساله ها در مورد QAP به این مجموعه اضافه شد. پس از آن نیز در سال 2000 برخی از نمونه ها یی که تاکنون حل نشده بودند به این لیست اضافه شدند. در سال 2002 تاکید بر راه حل هاب بهینه ای است که تاکنون به دست نیامده اند. که این بهینه ها معمولاً از طریق تکنیک های جدید محدودسازی (Branch) ، طرح های جدید شاخه و حد و محیط محاسباتی حل موازی بدست می آیند. در این سال همچنین نمونه های جدید، بهبودها در بهترین راه حل و لیستی از افرادی که روی QAP کار می کنند به سایت اضافه گردید. لازم به توضیح است که از سال 1991 تا سال 1997 این سایت توسط استفان کاریچ نگهداری شده است. از سال 1997 تا 2002 توسط ارندا سلا نگهداری شده است. این سایت هم اکنون توسط بنیاد ملی علوم تحت گرنت به شماره CMMI 0400155 پشتیبانی می گردد.

این وب سایت به طور منظم بروزرسانی می شود البته به کمک افرادی که روی QAP کار می کنند. و نویسندگان در این سایت از طرفی دعوت به کمک برای اضافه کردن بهبودها روی نمونه از سوی محققان روی QAP را دارد و از طرفی از تمام افرادی که روی QAP کار می کنند قدردانی و تشکر را به عمل می آورند. این روند ادامه دارد و آخرین بروزرسانی آن در سپامبر 2017 بوده است.

 

بخش دیتاست سایت QAPlib:

برای ورود به دیتاست باید وارد قسمت problem Instances and Solutions شد که لینک مستقیم آن http://anjos.mgi.polymtl.ca/qaplib/inst.html می باشد. یکی از مهمترین بخش های سایت قسمت دیتاست است. که در آن هر کدام از نمونه ها طبق حروف الفبا ما نمونه ها با اندازه مختلف در آن گنجانده شده است. به طوری کلی این نمونه ها از بخش هایی با نام های :

Burkard and J. Offermann [BuOf:77]

N. Christofides and E. Benavent [ChBe:89]

A.N. Elshafei [Elshafei:77]

B. Eschermann and H.J. Wunderlich [EsWu:90]

S.W. Hadley, F. Rendl and H. Wolkowicz [HaReWo:92]

J. Krarup and P.M. Pruzan [KrPr:78]

Y. Li and P.M. Pardalos [LiPa:92]

C.E. Nugent, T.E. Vollmann and J. Ruml [NuVoRu:68]

C. Roucairol [Roucairol:87]

M. Scriabin and R.C. Vergin [ScVe:75]

J. Skorin-Kapov [Skorin:90]

L. Steinberg [Steinberg:61]

E.D. Taillard [Taillard:91,Taillard:94]

U.W. Thonemann and A. Bölte [ThBo:94]

M.R. Wilhelm and T.L. Ward [WiWa:87]

 تشکیل شده است. همان طور که مشخص است هر بخش با توجه به مرجع ایجاد کننده آن نامگذاری شده است. به عنوان مثال بخش Burkard and J. Offermann [BuOf:77] توسط بارکارد و افرمن ایجاد شده است که شامل نمونه های مختلف با اندازه های متفاوت می باشد. (شکل 1)

شکل 1: نمونه های مختلف ارائه شده توسط بارکارد و افرمن از مسئله QAP

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

اطلاعات تماس با سایت:

برای تماس با سایت می توان به ایمیل های زیر پست های خود را ارسال کرد:

petermhahn@gmail.com  , miguel-f.anjos@polymtl.ca.

منابع:

 [1]. http://anjos.mgi.polymtl.ca/qaplib/