مقدمه‌ای بر بهینه‌سازی آنلاین: مسأله آسانسور

برای گفتگویی کوتاه درباره ماهیت بهینه سازی آنلاین یک مثال را دنبال می‌کنیم؛ موقعیتی که برای بسیاری از ما آشناست: شما خواب مانده‌اید و همین باعث شده است که برای جلسه صبح امروز دیر کنید و دچار تأخیر شوید! این موضوع وقتی بدتر می‌شود که در مسیر رسیدن به جلسه، تمام چراغ‌های راهنمایی و رانندگی را قرمز بیابید و حتی زمانی که پس از خلاص شدن از ترافیک، به ساختمان اداری می‌رسید، قرن‌ها طول بکشد تا آسانسور بیاید! چه کسی این آسانسور را طراحی کرده است؟! حتما باید راهی وجود داشته باشد که بتوان با استفاده از اندکی ریاضیات، کنترلی تمام‌عیار برای آسانسور طراحی کرد.

اجازه دهید وضعیت یک آسانسور را در یک ساختمان ۲۵ طبقه بررسی کنیم که در حال حاضر در طبقه چهارم قرار دارد. A می‌خواهد از طبقه از پنت‌هوس این برج – یعنی طبقه ۲۵ – به طبقه دوم برود، B می‌خواهد از طبقه دوم به طبقه اول برود و C نیز می‌خواهد از طبقه اول به طبقه آخر برود (شکل زیر). راه‌حل کنونی ما ساده است: اگر ابتدا B و سپس C و بالاخره A را سوار کنیم، به کوتاه‌ترین مسیر دست یافته‌ایم.

درست زمانی‌که ما در حال پایین‌رفتن از طبقه سوم می‌گذریم، ناگهان D در طبقه سوم ظاهر می‌شود و می‌خواهد که به طبقه دوم برده شود. خب، چه باید بکنیم؟ باید همان مسیر اولیه را ادامه دهیم و سپس به سراغ D برویم یا اینکه باید تغییرِ مسیر داده و ابتدا D را سوار کنیم؟

در هر صورت، ما زمان ارزشمندی را از دست می‌دهیم زیرا مسافت غیرضروری را می‌پیماییم؛ درصورتی‌که اگر از قبل می‌دانستیم که D ظاهر خواهد شد، می‌توانستیم از آن اجتناب کنیم.

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

اما اگر پیش از سوار کردن D، فرد E در طبقه پنجم ظاهر شود باید چه کنیم؟ باید ابتدا E را سوار کنیم؟ …

شاید مسأله آسانسور به این سادگی‌ها هم نباشد!

این یادداشت، ترجمه‌ای نسبتاً دقیق از جزوه درسی بهینه‌سازی آنلاین دانشگاه صنعتی کایزرسلاوترن نوشته اسون کرومکه و کلمنس تیلن در سال ۲۰۱۴ است:

Krumke, S. O. & Thielen, C. (2014). Introduction to Online Optimization. Course notes of the course “Online Optimization” at the University of Kaiserslautern.