یک مقاله تحقیقاتی نوشته شده توسط Tenindra Abeywickrama (Grab) ، Victor Liang (Grab) و Kian-Lee Tan (NUS) بر اساس کارشان که به عنوان بهترین مقاله داده های علمی بزرگ قابل اندازه برای سال 2021 انتخاب شد.
مطابقت مسافران مناسب با رانندگان شریک برای خدمات سروکاری واحد سروکاری یک وظیفه بسیار مهم است. انجام این کار به صورت ناکارآمد می تواند منجر به رسیدن مسافران به مقصد خود در مدت زمان بیشتری شود و رانندگان درآمد خود را از دست دهند. شاید چالش بیشتری از همه وجود داشته باشد که این یک فرآیند پیوسته است که با جریان مداوم درخواست های سفر جدید و رانندگان شریک جدید در دسترس است. بنابراین محاسبه مطابقت ها یک وظیفه بسیار پرسرعت است که نیازمند ظرفیت باالیی است.
ما کشف کردیم که یک جزء از الگوریتم معمولاً استفاده شده برای پیدا کردن مطابقت ها تأثیر قابل توجهی بر کارایی دارد که تا به حال به سمت خود رفته است. با این حال ، همچنین یک ویژگی مفید از مطابقت های بهینه در دنیای واقعی کشف کردیم که به ما امکان بهبود الگوریتم را در یک سناریو جالب تمرین کار می دهد.
یک مثال واقعی
بیایید یک الگوریتم مطابقت ساده را همانطور که در شکل 1 نشان داده شده است در نظر بگیریم ، که مسافران و رانندگان شریک بر اساس زمان سفر مطابقت داده می شوند. در این شکل ، سه راننده شریک (D1 ، D2 و D3) و سه مسافر (P1 ، P2 و P3) داریم.
پیدا کردن زمان سفر شامل محاسبه سریعترین مسیر از هر راننده شریک به هر مسافر می شود ، به عنوان مثال مسیرهای نقطه ای از D1 به P1 ، P2 و P3 به ترتیب. پیدا کردن تخصیص رانندگان شریک به مسافران که زمان سفر کل را کمینه کند ، شامل نمایش مسئله به صورت انتزاعی تر در یک گراف دو قسمتی است که در زیر نشان داده شده است.
در گراف دو قسمتی ، مجموعه مسافران و مجموعه رانندگان شریک دو مجموعه دوقسمتی را تشکیل می دهند. یال هایی که آنها را به یکدیگر متصل می کنند ، زمان سفر سریعترین مسیرها را نشان می دهند و هزینه های آنها در ماتریس هزینه در سمت راست نشان داده می شود.
یافتن تخصیص بهینه به عنوان حل مسئله مطابقت دوقسمتی با وزن حداقل (همچنین شناخته شده به عنوان مسئله اختصاص) است. این مسئله معمولاً با استفاده از یک تکنیک به نام الگوریتم Kuhn-Munkres (همچنین شناخته شده به عنوان روش مجارستانی) حل می شود.
اگر ما الگوریتم را روی سناریوی نشان داده شده در شکل 1 اجرا کنیم ، تطبیق بهینه را در ماتریس هزینه نشان داده شده در شکل بصورت قرمز پیدا خواهیم کرد. با این حال ، یک مرحله مهم وجود دارد که تا به حال کمتر به آن توجه کرده ایم ، و آن محاسبه ماتریس هزینه است. همانطور که مشخص می شود ، این قدم تأثیر قابل توجهی بر عملکرد در تنظیمات واقعی دارد.
تأثیر ماتریس هزینه
کارهای گذشته که مسئله اختصاص را حل می کنند ، فرض می کنند که ماتریس هزینه به عنوان ورودی داده می شود ، اما ملاحظه می کنیم که زمان مورد نیاز برای محاسبه ماتریس هزینه همیشه آسان نیست. این به خصوص در سناریوی واقعی صحیح است. اولاً ، مطابقت رانندگان شریک و مسافران یک فرآیند پیوسته است ، همانطور که قبلاً اشاره کردیم. هزینه ها ثابت نیستند ؛ با گذشت زمان تغییر می کنند زیرا رانندگان شریک حرکت می کنند و درخواست های مسافر جدید دریافت می کنند.
این به معنای این است که ماتریس باید هر بار که ما سعی در مطابقت داریم (به عنوان مثال هر X ثانیه) محاسبه شود. نه تنها پیدا کردن کوتاه ترین مسیر بین یک مسافر و راننده شریک هزینه محاسباتی گران تمام جفت مسافران و رانندگان شریک است. در واقع ، در جهان واقعی ، زمان لازم برای محاسبه ماتریس بیشتر از زمان لازم برای محاسبه تخصیص بهینه است! یک بررسی ساده از پیچیدگی زمانی نشان می دهد که این صحیح است.
اگر m تعداد رانندگان شریک / مسافرانی که سعی در مطابقت انجام می دهیم باشد ، الگوریتم KM معمولاً در O(m ^ 3) اجرا می شود. اگر n تعداد گره های شبکه جاده باشد ، زمان محاسبه ماتریس هزینه در O(m x n log n) با استفاده از الگوریتم دیکستراست.
می دانیم که n برای شبکه جاده سنگاپور در حدود 400،000 است (و برای شهرهای بزرگتر از این بزرگتر است) ، بنابراین می توانیم انتظار داشته باشیم O(m x n log n) مسلط بر O(m^3) برای m <1500 باشد ، که از این نوع سناریوی مورد انتظار در جهان واقعی است. برای تأیید این موضوع ، آزمایشات را روی شبکه جاده سنگاپور انجام دادیم که در شکل 2 نشان داده شده است.
در شکل 2a می توانیم ببینیم که m باید بیش از 2500 باشد تا زمان تخصیص زمان محاسبه ماتریس را فراتر بگیرد. حتی اگر از یک تکنیک مدرن و پیشرفته مانند سلسله مراتب تقلیلی3 برای محاسبه مسیر سریعتر استفاده کنیم ، مشاهده می شود که این امر صحیح است ، همانطور که در شکل 2b نشان داده شده است. این نشان می دهد که می توانیم عملکرد کلی مطابقت را به طور قابل توجهی بهبود بخشیم اگر بتوانیم زمان محاسبه ماتریس را کاهش دهیم.
یک بصیرت خارج کننده: محلیت فضایی مطابقت
در حین مطالعه مکان های واقعی مسافران و رانندگان شریک ، یک ویژگی جالب را مشاهده کردیم که آن را “محلیت فضایی مطابقت” نامیدیم. متوجه می شویم که مسافری که به هر راننده شریک در یک مطابقت بهینه اختصاص داده شده است ، یکی از نزدیک ترین مسافران به راننده شریک است (ممکن است این نزدیک ترین نباشد). این موضوع به طور قابل توجهی در ادراک قرار می گیرد ، زیرا مسافران و رانندگان شریک در سراسر یک شهر پراکنده خواهند بود و احتمالاً بهترین مطابقت برای یک راننده شریک خاص در سمت دیگر شهر وجود ندارد.
در شکل 3 ، یک سناریوی نمونه را نشان می دهیم که محلیت فضایی مطابقت را نشان می دهد. این یک مورد ایده آل برای نشان دادن این اصل است ، اما از واقعیت بسیار دور نیست. بر اساس ماتریس هزینه نشان داده شده ، بسیار آسان است که ببینیم کدام تخصیص کمترین زمان سفر کل را می دهد.
اکنون سوال این است که آیا ما حتی باید سایر هزینه ها را محاسبه کنیم تا تطابق بهینه را پیدا کنیم؟ به عنوان مثال ، می توانیم هزینه از D3 به P1 را که بسیار دور از هم و احتمالاً تطابق نخواهند یافت ، محاسبه نکنیم؟
الگوریتم Kuhn-Munkres تکمیلی
اگر به درستی باشد ، راهی برای بهره برداری از محلیت فضایی مطابقت و کاهش زمان محاسبه هزینه وجود دارد. ما الگوریتم KM تکمیلی را ارائه می دهیم که تنها هنگام نیاز به محاسبه هزینه ها ، و (به امید خدا) اجتناب از محاسبه همه آنها انجام می دهد. الگوریتم KM تغییر یافته ما یک تکنیک پایینی قابل قبول را به کار می برد تا این کار را بدون افزودن هزینه قابل توجهی انجام دهد ، همانطور که در بخش بعدی شرح خواهیم داد.
بازیابی شیء نزدیکترین به نقطه پرس و جستجو با سرعت بالاتر برای مسئله مطالعۀ شده ای است (معمولاً به عنوان جستجوی k-Nearest Neighbour شناخته می شود). ما این مفهوم را برای پیاده سازی یک صف اولویت Q برای هر راننده ui به کار می بریم ، همانطور که در شکل 4 نشان داده شده است. این صف های اولویت امکان بازیابی نزدیکترین مسافران را به منظور حداقل جستجوی زمان یک مسافر را با استفاده از یک کمینه به عنوان یک کمینه شود. پایینی اولویت این صف به عنوان یک هزینه حداقلی برای کل یال های دوقسمتی مرتبط با آن راننده شریک که هنوز دقیقاً هزینه را محاسبه نکرده ایم ، استفاده کنید.
اکنون ، الگوریتم KM می تواند به طور معمول ادامه یابد و با استفاده از هزینه یال مجازی که توسط صف اولویت مربوطه نشان داده می شود ، از محاسبه دقیق هزینه یال خودداری کند. البته ، ممکن است شرایطی وجود داشته باشد که هزینه یال مجازی برای KM کافی دقیق نباشد تا تطابق بهینه را محاسبه کند. برای حل این مشکل ، قواعد رفع مشکل را پیشنهاد می کنیم که متوجه می شوند هنگامی که هزینه یال مجازی کافی نیست.
اگر یک قاعده فعال شود ، صف را با بازیابی عنصر بالا و محاسبه یال های دقیق ، تنظیم می کنیم ، اینجاست که بخش "تکمیلی" پیدا می شود. در تقریباً تمامی موارد ، این کار همچنین عضو بالایی کی (کمینه شده) را در صف اولویت افزایش می دهد.
اگر علاقه مندید تا بیشتر در مورد این موضوع بدانید ، می توانید با خواندن مقاله تحقیقاتی ما5 به تفصیل به قوانین بازتاب ، کارکردهای داخلی الگوریتم و اثبات های ریاضی صحت آن بپردازید.
برای این لحظه ، کافی است بگوییم که الگوریتم KM تکمیلی به همان نتیجه دقیق الگوریتم اصلی KM می رسد. این فقط به صورت تکمیلی و بهره گیری از روشی بهینه گفته می شود ، آرزو می کند که بتوانیم نتیجه را بدون محاسبه همه هزینه های ممکن پیدا کنیم. این کاملاً مناسب است برای بهره برداری از محلیت فضایی مطابقت. علاوه بر این ، نه تنها زمان را با اجتناب از محاسبه هزینه های دقیق صرفه جویی می کنیم ، بلکه از محاسبه مسیرهای سریعتر و زمانهای سفر بیشتر به مسافران دورتر که محاسباتی گران تر از آنهایی است که برای مسافران نزدیک تر است استفاده نمی کنیم.
تحقیقات تجربی
رقابت
ما یک بررسی تجربی دقیق را برای تأیید عملکرد عملی تکنیک های پیشنهادی انجام دادیم. ما دو نسخه از تکنیک KM تکمیلی خود را پیاده سازی کردیم که در پیاده سازی صف اولویت و تکنیک کوتاهترین مسیر استفاده شده متفاوت بودند.
- IKM-DIJK: از الگوریتم دیکسترا برای محاسبه مسیرهای کوتاه استفاده می کند. صف های اولویت به سادگی صف اولویت جستجوی دیکسترا از هر راننده شریک است. این هیچ هزینه اضافی نسبت به