The Computational Cost of Feasibility Checking in the Dial-a-Ride Problem (DARP)

سال انتشار: 1400
محل انتشار: چهاردهمین کنفرانس بین المللی انجمن ایرانی تحقیق در عملیات
کد COI اختصاصی: ICIORS14_067
زبان مقاله: انگلیسی
تعداد مشاهده: 474

نویسندگان

Department of Computer Engineering and Information Technology Shiraz University, Shiraz, Iran

چکیده

Dial-a-Ride Problem (DARP) is one of the shared mobility problems for door-to-door people transportation. In algorithms proposed to tackle the DARP, checking the feasibility of a path is relatively time consuming. This issue has motivated researchers to come up with several methods for dealing with this challenge efficiently. The ۸-step procedure proposed in ۲۰۰۳ is the most popular one, and the approach introduced in ۲۰۱۱, called the Firat procedure, is the one with the least time complexity. As the original Firat procedure has not been proposed for the standard DARP, in this paper, it is discussed in detail how this method is adapted to be used for solving feasibility problems raised in the standard DARP. Moreover, using the benchmark instances for the DARP, the performance of this procedure is compared with the ۸-step procedure in practice. The experimental results indicate that, although the time complexity of the Firat procedure is better than that of the ۸-step scheme, the Firat method does not demonstrate its superiority in practice.

کلیدواژه ها

Shared Mobility Systems, Dial-a-Ride Problem (DARP), Pickup and Delivery Problem with Time Windows (PDPTW), Shared-Taxi Problem, Feasibility Checking

مقالات مرتبط جدید

اطلاعات بیشتر در مورد COI

COI مخفف عبارت CIVILICA Object Identifier به معنی شناسه سیویلیکا برای اسناد است. COI کدی است که مطابق محل انتشار، به مقالات کنفرانسها و ژورنالهای داخل کشور به هنگام نمایه سازی بر روی پایگاه استنادی سیویلیکا اختصاص می یابد.

کد COI به مفهوم کد ملی اسناد نمایه شده در سیویلیکا است و کدی یکتا و ثابت است و به همین دلیل همواره قابلیت استناد و پیگیری دارد.