زمانبندی ناوگان در شرایط فازی

نوع مقاله : مقاله پژوهشی

نویسنده

گروه علوم کامپیوتر، دانشکده مهندسی صنایع و کامپیوتر، دانشگاه صنعتی بیرجند، بیرجند، ایران.

چکیده

در این مقاله مسئله زمانبندی ناوگان در شرایط فازی (FMDVSP) مورد بررسی قرار گرفته است. به دلیل شرایط غیرقطعی در شبکه‌های حمل ونقل، تابع هدف و قیود مسئله FMDVSP به صورت فازی در نظر گرفته شده است. به منظور مدل سازی مسئله به صورت یک مسئله جریان چندمحموله‌ای فازی از رابطه اعتبار فازی استفاده شده است. همچنین برای حل کارای مسئله FMDVSP، ترکیبی از الگوریتم‌ شاخه و قیمت و الگوریتم‌های ابتکاری (الگوریتم ) پیشنهاد شده است. الگوریتم‌ ابتکاری مزایده در بطن الگوریتم شاخه و قیمت برای تولید ستون‌های اولیه در روش تولید ستون بکار رفته است. همچنین برای بهبود جواب روش تولید ستون در هر گره از درخت شاخه و قیمت، الگوریتم ابتکاری جستجوی محلی پیشنهاد شده است. به منظور بررسی کارایی الگوریتم پیشنهاد شده در مثال-های بزرگ-مقیاس دو مجموعه از مسائل استاندارد در نظر گرفته شده است. همچنین به عنوان یک مطالعه موردی، الگوریتم پیشنهادی برای زمانبندی اتوبوس‌ها در شبکه BRT تهران بکار رفته است.

کلیدواژه‌ها


عنوان مقاله [English]

Fuzzy vehicle scheduling problem

نویسنده [English]

  • Malihe Niksirat
Department of Computer Sciences, Birjand University of Technology, Birjand, Iran.
چکیده [English]

Vehicle scheduling problem is an important combinatorial optimization problem arising in the management of transportation companies. It consists in assigning a set of timetabled trips to a set of vehicles so as to minimize a given objective function and efficiency use of the resources. In this paper, vehicle scheduling problem under undeterministic conditions is considered. The problem is formulated as a credibility-based fuzzy integer multicommodity flow problem. An approach based on the combination of branch-and-price and heuristic algorithms is used to generate vehicle schedules. The heuristic algorithms are applied to accelerate branch-and-price algorithm. Two sets of benchmark examples are considered to demonstrate the applicability of the proposed algorithm in the large-scale instances. The results show that, the proposed method generates vehicle schedules with different decision maker's satisfaction degrees. The algorithm is applied to solve classical multi-depot vehicle scheduling problem as well. In this case, the results show that the proposed algorithm improves the integrality gap in comparison with the state-of-the-art algorithms. Also the proposed 〖B&P〗_H algorithm decreases the computational time in comparison with the normal branch-and-price algorithm. Finally, the approach is used to generate bus schedules in Tehran BRT network. Computational results show that the proposed method generates bus schedules with the minimum number of delayed trips.

کلیدواژه‌ها [English]

  • vehicle scheduling
  • transportation network
  • branch and price algorithm
  • heuristic algoriithm