حل مسئله مسیریابی- موجودی با در نظر گرفتن محدودیت عرضه کالا با استفاده از الگوریتم های فراابتکاری

نویسنده

دانشگاه پیام نور واحد دیر

چکیده

مسئله مسیریابی-موجودی (IRP)2 در بستر مدیریت موجودی توسط فروشنده (VMI)3 مطرح شده است. این مسئله از آن جهت مورد توجه است که دو جز از مدیریت زنجیره تأمین (SCM)4 را به­ یکدیگر پیوند می­ دهد و در واقع ترکیبی از دو مسئله کنترل موجودی5 و مسئله مسیریابی وسیله نقلیه (VRP)6 است. در تحقیق پیش­رو مسئله مسیریابی-موجودی چندین دوره­ای برای مجموعه­ ای از مشتریان با احتساب هزینه­ های حمل و ­نقل و کمبود به‌ صورت سفارش معوقه7 مورد بررسی قرار­گرفته است. نرخ تقاضا قطعی و اقلام از یک نوع می­­ باشند. در ضمن محدودیت تأمین کالا برای مشتریان وجود دارد که این محدودیت تاکنون در تحقیقات صورت پذیرفته در نظر ­گرفته نشده است. هم­چنین ناوگان حمل با ظرفیت متفاوت برای هر وسیله جهت توزیع محصول در ­دسترس است. بر­خلاف اکثر مسایل مسیریابی-موجودی که امکان بازدید از یک مشتری با وسایل نقلیه متفاوت در طول یک دوره میسر می­ باشد؛ در این مسئله در هر دوره حداکثر یک بار می­توان جهت برطرف نمودن تقاضای آن دوره، از آن مشتری دیدن نمود. مسئله با دو روش حل گردید که هر یک از روش­ها شامل دو فاز می­ باشد. در فاز اول که بین دو روش مشترک است میزان محصول ارسالی با ارائه یک سیاست تفکیک ثابت8 پیشنهادی برای هر مشتری تعیین می­ گردد، سپس با استفاده از الگوریتم­ های ژنتیک (GA)9 و جستجوی همسایگی متغیر (VNS)10، مسیر ارسال مشخص می­ شود. کدنویسی با استفاده از نرم افزار Matlab صورت پذیرفت. دو معیار مدت زمان اجرای برنامه و مقدار تابع هدف که همان سود حاصل از ارسال می­ باشد، مبنای مقایسه روش­ ها قرار می­ گیرد. در نهایت با مقایسه روش­ها با توجه به معیارها، برتری روش اول مشخص گردید.از آنجایی­که مسئله مسیریابی-موجودی جز مسایل با درجه پیچیدگی سخت می­ باشد روش حل پیشنهادی در این تحقیق می­ تواند از آن جهت حایز اهمیت باشد که جواب به­ دست آمده در سطح قابل قبول و زمان حل نیز کاملاً رضایت­ بخش می­ باشد.

کلیدواژه‌ها


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

Solving of Inventory Routing Problem by Meta Heuristics with Supply Constraints

چکیده [English]

Inventory-routing problem (IRP) is introduced in vendor managed inventory (VMI) concept. The importance of IRP is combining two elements of supply chain management. Indeed IRP integrates inventory control and vehicle routing problem.
In this research multi period IRP for a set of customer with considering transportation and shortage costs is investigated. Each customer faces a demand at a deterministic rate and one type. In addition in this problem there is a product supply limitation that there is no attention to this limitation in literature. The inventory of the customers are replenished by a fleet of heterogeneous vehicle of limited and various capacity. Unlike most of the problems in literature that several vehicle can visit one customer in a period, in this problem a customer will be visited no more than once in a time period. The problem has been solved by two methods that which of them contains two steps. In the first step, that is common between methods, the quantity of sent products for every customer is determined by a proposal fixed partition policy (FPP).Then the sequences of customers are determined by genetic algorithm and variable neighborhood search algorithm. Finally the methods are compared by two criteria, run time and the profit of dispatching. Since the inventory routing problem is a NP-hard problem, the solving method proposed in this study can be useful because the dispatching revenue is in reasonable rate and run time is quite satisfaction.

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

  • Inventory Routing Problem
  • Supply Chain Management
  • genetic algorithm
  • Variable Neighborhood Search

]1[Dror, M., Trudeau, P.,Savings by split delivery routing, Transportation Science,23, 141–145,1989.

]2[Campbell, A., Clarke, L., Savelsbergh, M.W.P,Inventory routing in practice: The vehicle routing problem, SIAM Monographs on Discrete Mathematics and Applications, 309–330,2002.

]3[Campbell, A.M., Savelsbergh, M.W.P., A decomposition approach for the inventory-routing problem. Transportation Science, 38(4), 488–502, 2004.

]4[Anily, Sh.,Bramel, J., An asymptotic 98.5%-effective lower bound on fixed partition policies for the inventory-routing problem, Discrete Applied Mathematics,145, 22-39 ,2004.

]5[Aghezzaf, E. , Raa, B., Van Landeghem, H., 2006, Modeling inventory routing problems in supply chains of high consumption products, European Journal of Operational Research,169, 1048–1063,2006.

]6[Zhao, Q. , Wang Sho. , Lai K.K.,A partition approach to the inventory/routing problem, European Journal of Operational Research, 177, 786–802, 2007.

]7[Abdelmaguid, T. F. ,Dessouky, M. M. , Ordonez, F., Heuristic approaches for the inventory-routing problem with backlogging, Computers & Industrial Engineering, 56, 1519–1534, 2009.

]8[Bard, J., F. ,Nananukul, N., Heuristics for a multiperiod inventory routing problem with production decisions, Computers & Industrial Engineering, 57, 713–723, 2009.

]9[Cheng, L., Duran, M.A.,Logistics for world-wide crude oil transportation using discrete event simulation and optimal control, Computers and Chemical Engineering ,28, 897–911, 2004.

]10[Yu, Y., Chen, H., Chu, F., A new model and hybrid approach for large scale inventory routing problems, European Journal of Operational Research, 189,1022–1040, 2008.

]11[Christiansen, M., KjetilFagerholt , K., Flatberg, T., Haugen, Q., Kloster,O., Lund,E., Maritime inventory routing with multiple products: A case study from the cement industry, European Journal of Operational Research,208, 86-94, 2011.

]12[Zhong, Y., Aghezzaf, E., Combining DC-programming and steepest-descent to solve the single-vehicle inventory routing problem, Computers & Industrial Engineering, 61, 313-321, 2011.

]13[Zipkin, P., Federgruen, A.,An efficient algorithm for computing optimal (s,S) policies,Operations Research, 32, 1268-1285, 1984.

]14[Federgruen, A., Prastacos, G., Zipkin, P., An allocation and distribution model for perishable products,Operations Research, 34, 75-82, 1986.

]15[Liu, Sh., Lee, W.,A heuristic method for the inventory routing problem with time windows, Expert Sistem with Application, 38,13223-13231, 2011.

]16[Andersson, H., Hoff ,A., Christiansen, M., Hasle, G., Løkketangen, A., Industrial aspects and literature survey: Combined inventory management and routing, Computers & Operations Research, 37 ,1515–1536, 2010.

[17]عالم تبریز، ا. زندیه، م. محمد رحیمی، ع.، الگوریتم­های فرا ابتکاری در بهینه­سازی ترکیبی (ژنتیک، شبکه عصبی، آنیل شبیه­سازی شده، جستجوی ممنوع، الگوریتم مورچگان)، چاپ دوم، نشر اشراقی، 1389.

]18[Mladenovi´c, N., Hansen, H., Variable neighborhood search, Computers and Operations Research, 24 (11): 1097–1100, 1997.

]19[Bräysy, O., A Reactive Variable Neighborhood Search for the Vehicle Routing Problem with Time Windows. SINTEF AppliedMathematics, Department of Optimization, 124, 2003.

]20[Polacek, M., Hart, R., Doerner, K., Reimann, M., A Variable Neighborhood Search for the Multi Depot Vehicle Routing Problem with Time Windows, Journal of Heuristics,10, 613-627, 2004.

]21[Polacek, M., Doerner, K., Hart, R., Maniezzo, V., A variable neighborhood search for the capacitated arc routing problem with intermediate facilities, Journal of Heuristics, 14, 405-423, 2008.

]22[Hemmelmayr, V.C., Doerner, K.F., Hartl, R.F.,A Variable Neighborhood Search Heuristic for Periodic Routing Problems. European Journal of Operational Research,195 , 791–802, 2009.