کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
6853008 1436971 2018 66 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Online spatio-temporal matching in stochastic and dynamic domains
ترجمه فارسی عنوان
تطبیق فضایی و زمان بندی آنلاین در حوزه های تصادفی و پویا
کلمات کلیدی
ترجمه چکیده
تطبیق زمانبندی آنلاین سرورها / خدمات به مشتریان یک مشکل است که در بسیاری از زمینه های مرتبط با حمل و نقل مشترک (به عنوان مثال، تاکسی، تقسیم سواری، سوپر شاتل و غیره) و خدمات تحویل (مانند غذا، تجهیزات ، لباس، سوخت خانگی، و غیره). یکی از ویژگی های کلیدی این مشکلات این است که تطبیق سرورها / خدمات به مشتریان در یک مرحله تأثیر مستقیم بر تطبیق در مرحله بعدی دارد. به عنوان مثال، برای تاکسی کارآمد است تا مشتریان را از مرحله اول تطبیق به مشتریان نزدیکتر کند. به طور سنتی، رویکردهای حرص و طمع / نزدیک به تصویب رسید تا مشکلات مربوط به هماهنگی آنلاین در مقیاس بزرگ را رفع کنند. در حالی که آنها راه حل هایی را به شیوه ای مقیاس پذیر ارائه می دهند، به علت ماهیت مینیوپی آنها، کیفیت تطبیق به دست آمده قابل توجه است (در نتایج تجربی ما نشان داده شده است). در این مقاله، ما یک فرمولبندی بهینه سازی تصادفی چند مرحلهای را برای بررسی سناریوهای تقاضای بالقوه آینده (از داده های گذشته) ارائه می کنیم. پس از آن ما یک پیشرفت برای حل مشکلات مقیاس بزرگ را به طور موثر و کارآمد آنلاین ارائه می کنند. ما همچنین مرزهای تئوری بدترین حالت را در عملکرد رویکردهای مختلف ارائه می دهیم. در نهایت، ما بهبود قابل ملاحظه ارائه شده توسط تکنیک های ما بر روی رویکردهای نزدیک و دو روش دیگر چند مرحله ای از ادبیات (برنامه ریزی پویا تقریبی و فرمول سازی بهینه سازی چند مرحله ای ترکیبی) در سه مجموعه داده های تاکسی واقعی نشان می دهد.
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر هوش مصنوعی
پیش نمایش مقاله
تطبیق فضایی و زمان بندی آنلاین در حوزه های تصادفی و پویا
چکیده انگلیسی
Online spatio-temporal matching of servers/services to customers is a problem that arises at a large scale in many domains associated with shared transportation (e.g., taxis, ride sharing, super shuttles, etc.) and delivery services (e.g., food, equipment, clothing, home fuel, etc.). A key characteristic of these problems is that the matching of servers/services to customers in one stage has a direct impact on the matching in the next stage. For instance, it is efficient for taxis to pick up customers closer to the drop off point of the customer from the first stage of matching. Traditionally, greedy/myopic approaches have been adopted to address such large scale online matching problems. While they provide solutions in a scalable manner, due to their myopic nature, the quality of matching obtained can be improved significantly (demonstrated in our experimental results). In this paper, we present a multi-stage stochastic optimization formulation to consider potential future demand scenarios (obtained from past data). We then provide an enhancement to solve large scale problems more effectively and efficiently online. We also provide the worst-case theoretical bounds on the performance of different approaches. Finally, we demonstrate the significant improvement provided by our techniques over myopic approaches and two other multi-stage approaches from literature (Approximate Dynamic Programming and Hybrid Multi-Stage Stochastic optimization formulation) on three real world taxi data sets.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Artificial Intelligence - Volume 261, August 2018, Pages 71-112
نویسندگان
, , ,