ارايه مدل و الگوريتم براي مساله زمان ‌بندي ناوگان چندپايانه اي توسعه يافته با در نظر گرفتن محدوديت هاي توازن تعداد ناوگان

Development of Model and Algorithm for Depot Balancing Multi-Depot Vehicle Scheduling Problem Considering Depot Balancing

هدف مساله زمان‌بندي ناوگان چندپايانه ­اي (MDVSP) انجام سفرهاي برنامه­ ريزي شده با استفاده بهينه از منابع موجود مي‌باشد. اين مساله در مديريت سيستم حمل­ ونقلي بسيار با اهميت است. يكي از راهكارهاي مفيد براي مديريت بهتر چنين سيستمي در نظر گرفتن محدوديت­ هاي شرايط واقعي مساله است. يكي از محدوديت­ هايي كه در كاربردهاي واقعي مساله MDVSP ديده مي شود، محدوديت­ متوازن­ سازي پايانه ­ها مي ­باشد. به منظور متوازن­ سازي تعداد ناوگان عزيمت شده از هر پايانه و همچنين تعداد رانندگان تخصيص‌يافته به هر پايانه، در اين مقاله محدوديت جديدي پيشنهاد شده است. اين نرمال‌سازي از تجمع بيش از حد ناوگان در يك يا چند پايانه و ترافيك ناشي از آن جلوگيري كرده و باعث توازن منابع بين پايانه­ ها مي­ شود. با افزودن اين محدوديت به مدل مساله، يك مدل گسترش­­ يافته براي مساله MDVSP پيشنهاد شده است كه در آن محدوديت متوازن­ سازي به صورت يك محدوديت نرم مدل­ سازي شده است. با توجه به اين‌كه در كاربردهاي واقعي اين مساله با نمونه­ هاي بزرگ-مقياس مواجه هستيم، براي حل مساله با در نظر گرفتن محدوديت جديد، از رويكرد تجزيه به همراه ايده­ هاي مزايده-محور استفاده شده است. براي ارزيابي مدل و روش حل ارايه شده از نرم افزار CPLEX به منظور مقايسه نتايج استفاده شده است. نتايج محاسباتي نشان مي ­دهد كه رويكرد پيشنهادي مي­ تواند در زمان مطلوب مساله موردنظر را با دقت مناسب حل كرده و همزمان محدوديت مورد نظر را برآورده سازد.

The main of multi-depot vehicle scheduling problem (MDVSP) is to schedule the timetabled trips using limited resources, optimally. The problem is very important in the management of the transportation systems. One of the most useful ways to better manage these systems is to consider the real conditions including depot balancing constraints. To normalize the number of vehicles departed from each depot and the number of drivers assigned to each depot, new constraints are proposed in this paper. This normalization prevents excessive accumulation of vehicles in one or more depots and it balances labor between depots. We suggest a new mathematical formulation for MDVSP in which the balancing constraints are considered as soft constraints. To solve the problem with the new constraints an auction-based heuristic algorithm with decompositions ideas is proposed. The CPLEX software is used to evaluate the proposed model and the presented method in order to compare the results. The computational results show that the proposed algorithm solves the problem in appropriate time.