مدلسازی مسئله مکانیابی-مسیریابی باز با تحویل چندبخشی و حل آن با استفاده از الگوریتم انجماد تدریجی

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

نویسندگان

1 دانشیار مهندسی صنایع/ دانشگاه علم و فرهنگ

2 کارشناسی ارشد/ دانشگاه علم و فرهنگ

چکیده

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

کلیدواژه‌ها

موضوعات


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

Modeling the split delivery open location routing problem and solving it by simulated annealing

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

  • Azizollah Jafari 1
  • A. Sadeghi Sarvestani 2
1 University of science and culture
2 University of science and culture
چکیده [English]

Location-routing problem is one of the most challenging problems in supply chain management. In real world, many companies hire vehicles for servicing demands of customers, so these vehicles do not return to these companies after ending services. On the other hand, managers are constantly faced with the problem of whether serving each costumer’s demand by one vehicle will result in higher benefits or delivering their demands by more than one vehicle will lead to increased profits. Therefore, in response to this challenge and in order to get closer to the real world, a new problem which is called split delivery open location-routing problem is modeled in this study. Since the problem is a NP-Hard, Tabu search and simulated annealing algorithms are used for solving it. The mathematical model is run by cplex10.1 software for the small size instances. In addition, in order to improve the proposed solution algorithms, a heuristic algorithm for generating suitable initial solution is presented. Finally, after generating the new experimental instances and tuning parameters of the proposed algorithms, the numerical results of the problem solving by cplex10.1 software and the suggested algorithm are analyzed. The results show the efficiency of the two algorithms and superiority of simulated annealing algorithm over tabu search algorithm. The results also indicate that considering the assumption of split delivery lead to final cost reduction, especially when the demand variance is relatively small and the mean is greater than half the vehicle capacity and less than three quarters of the vehicle capacity.

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

  • Supply chain management
  • Split delivery open location-routing problem
  • Tabu search
  • Simulation annealing
  • Design of experiment