آنها نقشه کارآمدترین سفر جاده ای از طریق ایالات متحده را طراحی می کنند

48 کاپیتول ایالت در 8 1/2 روز

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

با در نظر گرفتن این موضوع محقق از ترکیبی از الگوریتم های ژنتیک، نقشه های گوگل و بهینه سازی چند هدفه پارتو استفاده کرد ، یا همان چیزی است که در یک سفر جاده ای از طریق ایالات متحده، کمال را کشف کرد بازدید از 48 مرکز ایالتی که 21420 کیلومتر را در 8 روز و نیم طی می کنند . البته تا زمانی که ترافیک نباشد. علاوه بر این، همچنین تعیین کرد که می توان سفر را از هر نقطه از مسیر بدون تغییر در نتیجه نهایی آغاز کرد.

همانطور که انجام داد؟ اولسون با در دست داشتن فهرست کاپیتول ها باید فاصله واقعی بین این ساختمان ها را از طریق جاده و نه در یک خط مستقیم تعیین می کرد. برای انجام این کار، به Google Maps API مراجعه کرد که فواصل 2256 مسیر ممکن را محاسبه کرد.

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

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