حل مدل ریاضی جدید برای مسأله ی مسیریابی وسایل نقلیه چند هدفه و چند قرارگاهی با الگوریتم ژنتیک مرتب شده ی غیرمغلوب

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

نویسندگان

1 عضو هیات علمی دانشکده مهندسی صنایع، پردیس دانشکده-های فنی، دانشگاه تهران

2 دانشگاه آزاد اسلامی

چکیده

مسأله مسیریابی وسایل نقلیه در حالت‌های متنوعی قابل بررسی است که دو نوع بسیار مهم و کاربردی از این مسایل؛ مسأله مسیریابی وسایل نقلیه با پنجره زمانی سخت و مسیریابی وسایل نقیله چند قرارگاهی با وسایل نقلیه متفاوت می‌باشد. بیشتر مسایلی که در این زمینه‌ها مطرح شده‌اند، مربوط به مسایل تک هدفه با هدف حداقل کردن هزینه می‌باشند، اما پیچیدگی‌های مسایل واقعی عموماً کاربرد مسایل تک هدفه را به چالش می‌کشد. از این­رو در این مقاله برای انطباق مسایل با دنیای واقعی، در ابتدا یک مدل چند هدفه ارائه می‌گردد که در آن علاوه بر حداقل کردن هزینه‌های کل، عدم تعادل در فواصل سفر و عدم تعادل در بار وسایل نقیله نیز مد نظر قرار می‌گیرد. از آنجایی که این مسأله جزء مسایل NP-سخت می‌باشد، به­منظور حل مدل ارائه شده از الگوریتم ژنتیک مرتب شده غیرمغلوب استفاده شده است. در نهایت برای نشان دادن کارآیی الگوریتم‌ پیشنهادی، جواب‌های به دست آمده در ابعاد کوچک با جواب‌های به دست آمده از روش محدودیت اپسیلون مقایسه شد. نتایج به دست آمده، نشان می‌دهند که درصد خطای توابع هدف نسبت به روش محدودیت اپسیلون در تمامی مسایل حل شده کمتر از 4 درصد می‌باشد که این موضوع کارآیی الگوریتم‌ پیشنهادی را نشان می‌دهد.

کلیدواژه‌ها

موضوعات

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

Solving a New Mathematical Model for a Multi-Objective and Multi-Depot Vehicle Routing Problem by a Non-dominated Sorting Genetic Algorithm

نویسندگان [English]

  • Reza Tavakkoli-Moghaddam 1
  • Shaqayeq Masoudi 2
  • Hamed Eghbali 2
1 Professor, School of Industrial Engineering, College of Engineering, University of Tehran
2 Islamic Azad University
چکیده [English]

The vehicle routing problem (VRP) can be studied in variant cases, in which two related important problems are the VRP with hard time windows and the multi-depot VRP with heterogeneous vehicles. Most problems presented in this field are single-objective problems with the aim of the minimum cost; however, the complexity of real problems usually doubts the use of single objective problems. This paper considers not only the minimum travel cost, but also the distance travelled by the used vehicles and their loads. Since this problem is the NP-hard one, the non-dominated sorted genetic algorithm - II is used. To show its efficiency for solving small-sized problems, the obtained results are evaluated with the results obtained by the ε-constraint method. The results show that the obtained gap of the objective function values is less than 4% in all the solved problems indicating the efficiency of the proposed algorithm.

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

  • Vehicle routing
  • Multi Depots
  • Time Windows
  • ε-Constraint
  • Multi-objective optimization

مراجع

[1]       Baños, R., Ortega, J., Gil, C. (1959). Márquez, A.L. & de Toro, F. A hybrid meta-heuristic for multi- objective vehicle routing problems with time windows, Computers & Industrial Engineering 2013; 65(286-296).
[2]       Dantzig, G.B. & Ramser, J.H. The truck dispatching problem, Management Science, 6(80-91).
[3]       Clarke, G., Wright, J.W. (1964). Scheduling of vehicles from a central depot to a number of delivery points, Operations Research, 12:568–581.
[4]       Tavakkoli-Moghaddam, R., Safaei, N., Gholipour, Y. (2006). A hybrid simulated annealing for capacitated vehicle routing problems with the independent route length, Applied Mathematics and Computation, 176:445-454.
[5]      توکلی مقدم، ر.، نوروزی، ن.، سلامت بخش، ع.ر.، علینقیان، م.، (1390)، مسأله مسیریابی وسایل نقلیه با در نظر گرفتن ایجاد توازن در توزیع کالاها با استفاده از الگوریتم بهبود یافته بهینه سازی انبوه ذرات، پژوهشنامه حمل و نقل، سال هشتم، شماره 4، زمستان: 375-363.
[6]       Mirabi, M., Fatemi Ghomi, S.M.T. & Jolai F. Efficient stochastic hybrid heuristics for the multi-depot vehicle routing problem, Robotics and Computer-Integrated Manufacturing 2010; 26(564-569).
[7]       Bettinelli, A., Ceselli, A. Righini, G. (2011). A branch-and-cut-and-price algorithm for the multi-depot heterogeneous vehicle routing problem with time windows, Transportation Research - Part C, 19:723-740.
[8]       Ghoseiri, K., Ghannadpour, S.F. (2010). Multi-objective vehicle routing problem with time windows using goal programming and genetic algorithm, Applied Soft Computing, 10:1096-1107.
[9]       Noori, S. & Ghannadpour, S.F. (2012). High-level relay hybrid metaheuristic method for multi-depot vehicle routing problem with time windows, Journal of Mathematical Modeling and Algorithms, 11:159-179.
[10]   Ghannadpour, S.F., Noori, S., Tavakkoli-Moghaddam, R. (2014). A multi-objective vehicle routing and scheduling problem with uncertainty in customers’ request and priority, Journal of Combinatorial Optimization, 28:414-446.
[11]  کهفی، ع.، توکلی مقدم، ر. (1394)، حل مدل مسیریابی وسایل نقلیه چندانباره مبتنی بر کاهش ریسک با استفاده از یک الگوریتم خفاش چندهدفه، مهندسی حمل و نقل، سال ششم، شماره سوم: 507-522.
[12]  صباغ، م، س.، علینقیان، م.، زمانلو، ک. (1394)، مسأله مسیریابی وسایل نقلیه وابسته به زمان با محدودیت­های بارگیری دوبعدی: مدلسازی و حل، نشریه پژوهش­های مهندسی صنایع در سیستم­های تولید، دوره سوم، شماره پنجم:43-59.
[13]   Kritikos, M.N. Ioannou, G. (2013). The heterogeneous fleet vehicle routing problem with overloads and time windows, Int. J. of Production Economics, 144:68-75.
[14]   Lenstra, J.K. Rinnooy Kan, A.H.G. (1981). Complexity of vehicle and scheduling problem, Networks, 11:221-227.
نشریه پژوهش های مهندسی صنایع در سیستم های تولید
دوره 3، شماره 6 - شماره پیاپی 6
پاییز و زمستان 94
بهمن 1394
صفحه 167-175

فایل ها

هم رسانی

ارجاع به این مقاله

آمار