view in publisher's site

An evolutionary and constructive approach to a crew scheduling problem in underground passenger transport

Operations management of subway systems is associated with combinatorial optimization problems (i.e. crew and train scheduling and rostering) which belong to the np-hard class of problems. Therefore, they are generally solved heuristically in real situations. This paper considers the problem of duty generation, i.e. identifying an optimal trips set that the conductors should complete in one workday. With regard to operational and labor conditions, the problem is to use the lowest possible number of conductors and minimize total idle time between trips. The problem is modeled and solved using a constructive hybrid approach, which has the advantage of visualizing a solution construction similar to the manual approach typically used. Our approach takes advantage of the benefits offered by evolutionary methods, which store a candidate solutions population in each stage, thus controlling the combinatorial explosion of possible solutions. The results thus obtained for problems similar to those that are solved manually in the Santiago Metro System were compared with two alternative approaches, based on tabu search and a greedy method. The hybrid method produced solutions with the minimum number of duties in six of the ten problems solved. However, the tabu search method provided better results in terms of idle time than either the hybrid method or the greedy method.

یک رویکرد تکاملی و سازنده برای مساله زمان‌بندی خدمه در حمل و نقل زمینی

مدیریت عملیات سیستم‌های مترو با مسایل بهینه‌سازی ترکیبی (یعنی خدمه و زمان‌بندی قطار و rostering)مرتبط است که متعلق به دسته مسایل np - hard است. بنابراین، آن‌ها بطور کلی heuristically را در شرایط واقعی حل می‌کنند. این مقاله مساله تولید وظیفه را در نظر می‌گیرد، یعنی شناسایی سفره‌ای بهینه که هادی‌ها باید در یک روز کاری کامل شوند. با توجه به شرایط عملیاتی و کار، مشکل استفاده از کم‌ترین تعداد هادی ممکن و حداقل کردن کل زمان بی‌کار بین سفرها می‌باشد. این مساله با استفاده از یک رویکرد ترکیبی سازنده مدل‌سازی شده و حل شده‌است، که این مزیت را دارد که ساختار راه‌حل مشابه رویکرد دستی است. رویکرد ما از مزایای روش‌های تکاملی بهره می‌برد، که در هر مرحله یک جمعیت راه‌حل‌های کاندید را ذخیره می‌کند در نتیجه انفجار ترکیبی راه‌حل‌های ممکن را کنترل می‌کند. بنابراین نتایج به‌دست‌آمده برای مشکلات مشابه با آن‌هایی که به صورت دستی در سیستم مترو سانتیاگو حل شده‌اند با دو روش جایگزین مبتنی بر جستجوی تابو و روش حریصانه مقایسه شده‌اند. روش هیبرید راه‌حل‌هایی را با حداقل تعداد وظایف در شش مورد از ده مشکل حل‌شده ایجاد کرد. با این حال، روش جستجوی تابو نتایج بهتری را از نظر زمان idle نسبت به روش هیبرید یا روش حریصانه ارایه می‌دهد.

ترجمه شده با

Download PDF سفارش ترجمه این مقاله این مقاله را خودتان با کمک ترجمه کنید
سفارش ترجمه مقاله و کتاب - شروع کنید

95/12/18 - با استفاده از افزونه دانلود فایرفاکس و کروم٬ چکیده مقالات به صورت خودکار تشخیص داده شده و دکمه دانلود فری‌پیپر در صفحه چکیده نمایش داده می شود.