مسئله فروشنده دوره گرد
31 خرداد 1401
دقیقه
ویلی لومان فروشنده دوره گردی است که در بوستون زندگی میکند. او میبایست به هریک از شهرهای فهرست شده در تصویر 1-38 سر بزند و بعد به بوستون برگردد. ویلی میبایست به چه ترتیبی شهرها را بازدید کند تا بتواند کل مسافتی که میپیماید را به حداقل برساند؟
آخرین بهروزرسانی: 27 دی 1401
در سری مقاله های آموزش اکسل، در فصل گذشته به واردکردن داده ها از فایل متنی یا یک سند پرداختیم، در این مقاله به بررسی مسئله فروشنده دوره گرد میپردازیم.
چگونه میتوان از اکسل برای حل مسئلههای دارای ترتیبدهی استفاده کنیم؟
معمولاً مسئلههای کسبوکار نیاز به انتخاب یک ترتیب یا اولویتبندی بهینه دارند. در اینجا دو مثال از آنها را آوردهایم:
- یک کارگاه مواد چاپی میبایست به چه ترتیبی 10 کار را انجام دهد تا کل زمان تأخیر در آمادهشدن آنها را به حداقل برساند؟ مسائلی ازایندست به نام مسئلههای برنامهریزی کارگاه معروف هستند.
- فروشنده دوره گردی در بوستون زندگی میکند و میخواهد پیش از بازگشت به خانه به ده شهر دیگر سر بزند. او به چه ترتیبی میبایست به این شهرها برود تا مسافت کل مسافرتش را به حداقل برساند؟ این یکی از مثالهای مسئله کلاسیک فروشنده دوره گرد (تی اس پی) است.
در اینجا دو مثال دیگر از مسئلههای فروشنده دوره گرد (Traveling Salesperson Problems) را آوردهایم:
- امروز راننده مخصوص تحویل کالا میبایست در 20 مکان توقف کند. او به چه ترتیبی میبایست بستهها را تحویل دهد تا زمانی را که در جاده میگذراند به حداقل برساند؟
- روباتی میبایست ده سوراخ ایجاد کند تا بتواند یک برد مدارچاپی را تولید نماید. چه ترتیبی از سوراخ کردن صفحات باعث کاهش زمان کل موردنیاز برای تولید یک برد مدار میگردد؟
ابزار Solver نرمافزار Excell 2019 حل کردن مسئلههای اولویتبندی (ترتیب گذاری) را بسیار آسان کرده است. برای انجام این کار به کادر محاورهای Solver Parameters (بر روی گزینه Solver در گروه گزینههای Analyze در تب Data کلیک میکنیم) مراجعه کرده و سپس از لیست Select A Solving Method گزینه Evolutionary را انتخاب میکنیم. اکنون سلولهای متغیر را انتخاب کرده و در هنگام تنظیم محدودیتها (قیدها) از لیست مقایسه در میانه کادر محاورهای Add Constraint گزینه Dif را انتخاب میکنیم.
انتخاب گزینه AllDifferent به شما اطمینان میدهد چنانچه 10 سلول متغیر داشته باشید، اکسل مقادیر 1…2 الی 10 را به سلولهای متغیر تخصیص میدهد و هریک از این رقمها تنها یکبار تخصیص داده میشوند. بهطورکلی چنانچه محدودهای از n سلول متغیر را برای متفاوت بودن انتخاب کنید، اکسل اطمینان حاصل میکند که سلولهای متغیر مقادیر را 1..2 … الی n فرض کرده و هر مقدار ممکن دقیقاً تنها یکبار مورداستفاده قرار میگیرد. بیایید ببینیم چگونه از گزینه Dif برای پیداکردن آسان راهحل مسئله فروشنده دوره گرد استفاده کنیم.
چگونه میتوان از اکسل برای حل یک مسئله فروشنده دوره گرد (TSP) استفاده کرد؟
بیایید مسئله زیر را حل کنیم.
ویلی لومان فروشنده دوره گردی است که در بوستون زندگی میکند. او میبایست به هریک از شهرهای فهرست شده در تصویر 1-38 سر بزند و بعد به بوستون برگردد. ویلی میبایست به چه ترتیبی شهرها را بازدید کند تا بتواند کل مسافتی که میپیماید را به حداقل برساند؟ کار انجام شده برای این مسئله در فایل Tsp.xlsx است.
برای مدلسازی این مسئله در صفحه گسترده، میبایست توجه کرد که هر نوع نظمبندی و یا جابهجایی اعداد 1 تا 11 نمایشگر ترتیب بازدید از شهرها است. مثلاً ترتیب:
2-4-6-8-10-1-3-5-7-9-11 میتواند بهعنوان سفر از بوستون (شهر 1) به دالاس (شهر 3) به لسآنجلس (شهر 5) و بالاخره به سانفرانسیسکو (شهر 10) پیش از بازگشت به بوستون در نظر گرفته شود. ازآنجاییکه ترتیب موقعیت شهر شماره 1 در نظر گرفته میشود برای ویلی
10! = 10x9x8x7x6…x2x1 = 3,628,800
ترتیب ممکن پیمودن مسیر برای درنظرگرفتن وجود دارد.
برای شروع میبایست کل مسافت طی شده برای هریک از ترتیبهای سرزدن به شهرها را تعیین نمایید. تابع INDEX برای این وضعیت بهترین ابزار است. از فصل چهارم بنام “تابع INDEX” بهخاطر دارید که دستور زبان تابع INDEX عبارت است از: INDEX(Range,row#,column#)
در اینجا اکسل محدوده سلولهایی به نام Range را جستجو کرده و مدخلی را که در row# و Column# مشخص شده را انتخاب میکند. در این مورد میتوانید از تابع INDEX برای یافتن کل مسافت پیموده شده برای بازدید از تمامی شهرها را پیدا کنید.
کار را با واردکردن ترتیبی از اعداد صحیح 1 تا 11 در محدوده F16:F26 شروع میکنیم. سپس محدوده G4:Q12 را distances(فواصل) نامگذاری کرده و در سلول G16 فرمول =INDEX(distances,F26,F16) را وارد میکنیم. این فرمول فاصله میان آخرین شهر فهرست شده (در سلول F26) و اولین شهر فهرست شده (در سلول F16) را تعیین میکند. پس از آن فرمول =INDEX(distances,F26,F16) را در سلول G17 وارد کرده و آن را در محدوده G18:G26 کپی میکنیم. این فرمول در سلول G17 فاصله میان اولین و دومین شهر فهرست شده و الی آخر را محاسبه میکند. اکنون میتوانم سلول هدف (کل فاصله پیموده شده) را در سلول G27 با فرمول =INDEX(distances,F26,F16) محاسبه کنم.
در این مرحله آمادهایم که ابزار Solver را احضار کنیم. تصمیم بر این است که مقدار سلول G27 را به حداقل برسانیم (در کادر محاورهای Solver Parameters در کادر Set Objetives سلول G27 را انتخاب کرده و گزینه Min را انتخاب میکنیم)، سپس روی گزینه Add کلیک کرده تا محدودیتی اضافه کرده و در کادر محاورهای Constraint محدوده F16:F26 را انتخاب میکنیم. سپس عبارت Dif را بهعنوان AllDiffrent انتخاب نموده و روی دکمه Ok کلیک میکنیم تا محدودیت را اضافه کنیم. این به ما اطمینان میدهد که Solver همواره سلولهای متغیر را در محدوده انتخاب شده نگه دارد و مقادیر 2،1 الی 11 را برای آن فرض کند.
هر مقدار تنها یکبار ظاهر خواهد شد. کادر محاورهای Solver Parameters در تصویر 2-38 نشان داد شده است. پیش از اجرای Solver نرخ جهش را تا 0.5 بالا میبریم (در سمت راست Select A Solving Method روی گزینه Options کلیک کرده و سپس در کادر محاورهای Options روی تب Evolutionary کلیک کرده و مقدار را در کادر محاورهای Mutation Rate بهروز میکنیم)
میبینیم حداقل فاصله مسافرت 8.995 مایل است. برای دیدن ترتیب بازدید از شهرها کار را بهسادگی با اولین ردیف دارای رقم 1 شروع میکنیم (که به شهر ویلی یعنی بوستون مرتبط است) و شهرها را در ترتیب فهرست شده دنبال میکنیم. شهرها به ترتیب زیر بازدید شدهاند: بوستون، نیویورک، پیتسبورگ، شیکاگو، دنور، سیاتل، سانفرانسیسکو، لسآنجلس، فینکس، دالاس، میامی، بوستون. ترتیبهای دیگری برای بازدید از شهرها وجود دارد که بازهم حداقل جمع مسافت گذرانده شده یعنی 8.995 را به ما میدهد.
در آخر باید اشاره کرد که برخی اوقات مدل Solver را بهگونهای تنظیم میکنید که برخی از سلولهای متغیر شما را مقید سازد که عدد صحیح ارائه کنند، اما آن سلولهای متغیر اعداد کسری برمیگردانند. برای ازبینبردن این مشکل ابزار Solver را انتخاب کنید و پس از انتخاب Options اطمینان حاصل کنید که گزینه Ignor Integer Constraints Option انتخاب نشده باشد.
مسئلههای این فصل
یک کارگاه شغلی کوچک میبایست شش کار مختلف را برنامهریزی کند. موعد مقرر و تعداد روزهای موردنیاز برای تکمیل هر کار در جدول زیر مشخص شدهاند. این کارها به چه نظمی میبایست برنامهریزی شوند تا کل روزهای انجام کارهایی که دیرکرد دارند به حداقل برسد؟
فایلی به نام NBamiles.xlsx حاوی فواصل میان تمام استادیومهای برگزاری بازیهای NBA است. فرض کنید در نیویورک زندگی میکنید و میخواهید هریک از استادیومها را یکبار دیده و بعد به نیویورک برگردید. این شهرها را به چه ترتیبی میبایست بازدید کنید تا کل فاصله مسافرت شده را به حداقل برسانید؟
فرش کنید که در آتلانتا زندگی میکنید میخواهید 29 مدیرکل را به خانههایشان برسانید. هر بار که به منطقهای میرسید یکی از مدیران کل را در منطقه خانهاش پیاده میکنید. به چه ترتیب میبایست این مدیران را به خانه برسانید تا بتوانید کل فاصله پیموده شده توسط آن مدیران کل را به حداقل برسانید؟
در مسئله ویلی لومان فرض کنید که میبایست بلافاصله پس از دنور، به نیویورک بروید. راهحل این مسئله چیست؟
یک مکعب جادویی سه در سه تمام ارقام صحیح 1 تا 9 را در خود قرار میدهد تا حساب هر ستون، هر ردیف و دو قطر مورب آن از هر گوشه برابر با 15 باشد. از روش Evolutionary Solver استفاده کنید تا یک مکعب جادویی 3 در 3 طراحی نمایید.