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

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

نویسندگان

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

2 ، دانش آموخته‌ کارشناسی ارشد، دانشکده‌ مهندسی صنایع، دانشگاه علم و فرهنگ، تهران، ایران

چکیده

از چالش انگیزترین مسائل موجود در مدیریت زنجیره‌ی تأمین (SCM)  مسئله‌ی مکانیابی تسهیلات (FLP) و مسیریابی وسیله نقلیه  (VRP) می‌باشد که بررسی مجزای این دو مسئله، افزایش هزینه‌ها و مدت زمان برنامه‌ریزی را نتیجه می‌دهد. لذا مسئله مکانیابی_مسیریابی  (LRP) با در نظر گرفتن همزمان FLP و VRP در SCM مطرح می‌شود. مدیر شرکت‌ها همواره با این مسئله مواجه هستند که تأمین تقاضای هر مشتری تنها توسط یک وسیله نقلیه سود بیشتری را نتیجه می‌دهد یا تحویل تقاضای آنان در چند بخش منجر به افزایش سود می‌شود. برای پاسخ به این مسئله نیاز است که هزینه-های بدست آمده از حل LRP و مسئله‌ی مکانیابی_مسیریابی با در نظر گرفتن فرض تحویل چند بخشی تقاضای مشتریان    (SDLRP)مقایسه شود. لذا این مقاله به معرفی مدل SDLRP می‌پردازد، که تا به حال در مقاله‌ای دیده نشده است. با توجه به NP-Hard بودن این مسئله، مدل ریاضی پیشنهادی توسط نرم افزار CPLEX10.1 برای نمونه مسائل در اندازه‌های کوچک اجرا و دو الگوریتم جستجوی ممنوع  (TS) و آنیل شبیه‌سازی شده  (SA) برای ابعاد بزرگ مسئله ارائه می‌شود. پس از تولید مثال‌های آزمایشی جدید نتایج عددی حاصل از حل مدل توسط نرم افزار CPLEX10.1 و الگوریتم-های پیشنهادی تحلیل شده است. نتایج گویای کارایی دو الگوریتم TS و SA و برتری الگوریتم SA نسبت به الگوریتم TS می‌باشد، به این معنا که در اغلب نمونه مسائل، الگوریتم SA در زمان کوتاه‌تر جواب‌های بهتری را ارائه می‌دهد. همچنین نتایج نشان می‌دهند در نظر گرفتن فرض تحویل چندبخشی تقاضای مشتریان منجر به کاهش هزینه‌ی نهایی می‌شود، به ویژه اگر واریانس تقاضای مشتریان کوچک و میانگین آنها بین نصف و سه چهارم ظرفیت وسایل نقلیه باشد.
 
 

کلیدواژه‌ها


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

Solving Split Delivery Location Routing Problem Using Simulated Annealing Algorithm

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

  • A. Jafari 1
  • A. Sadeghi 2
1 Assistant Professor, Department of Industrial Engineering, University of Science and Culture, Tehran, Iran.
2 M.Sc. Grad., Department of Industrial Engineering, University of Science and Culture, Tehran, Iran
چکیده [English]

The most challenging problems in Supply Chain Management are Facility Location Problem (FLP) and Vehicle Routing Problem (VRP) which considering these two in separate, results in larger costs and planning time. Therefore, Location Routing Problem (LRP) will be addressed by considering VRP and FLP in SCM simultaneously. Company managers always face this problem whether serving each costumer’s demands by one vehicle ends in higher benefits or delivering their demands by more than one vehicle. Answering this issue needs comparing the obtained costs of LRP to the obtained costs of Split Delivery Location Routing Problem (SDLRP). This article presents a mixed-integer linear programming model of SDLRP. The mathematical model of this problem has never been seen in any article. Since it’s a NP-hard problem, the proposed model is run by cplex10.1 software for the small size instances, and for the large size instances, two algorithms, tabu search and simulated annealing are presented. After generating the new experimental instances, the numerical results of problem solving using cplex10.1 software and the suggested algorithms are analyzed. The results show the efficiency of the two algorithms, Tabu search and simulated annealing, and superiority of SA algorithm over TS algorithm, meaning that for most instances, the SA algorithm finds better solutions in a shorter period of time for large size instances. The results also show that considering the assumption of split delivery of customers’ demand leads to final cost reduction, especially when the demand variance is relatively small and the mean demand is greater than half the vehicle capacity but less than three quarters of the vehicle capacity.
 
 
 

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

  • Supply chain
  • Location-Routing Problem with Split Delivery
  • Tabu Search
  • Simulation Annealing

-   بشیری، م.، و کریمی، ح.، (1389)، "کاربرد
الگوریتم­های ابتکاری و فرا­ابتکاری در طراحی
سیستم­های صنعتی"، تهران: دانشگاه شاهد.

 

-     یوسفی خوشبخت، م.، دیده­ور، ف.، رحمتی، ف.، صدیق­پور، م.، (1391)، "الگوریتم موثر رقابتی فراگیر برای حل مسئله مسیریابی وسایل نقلیه باز". پژوهشنامه حمل و نقل، سال نهم، شماره اول، بهار 1392،
صص. 83-95.

-     عالم تبریز، الف.، زندیه، م.، محمد رحیمی، ع.ر.، (1387)، "الگوریتم‌های فراابتکاری در بهینه‌سازی ترکیبی (ژنتیک، شبکه عصبی، آنیل شبیه‌سازی شده، جستجوی ممنوع و الگوریتم مورچگان)"، تهران انتشارات صفار-اشراقی.

 

-     Alumur, S., Kara and B.Y. (2007), "A new model for the hazardous waste location-routing problem", Computer and Operational Research, Vol. 34,
pp. 1406–1423.

 

 

-     Ambrosino, D., Sciomachen, A. and Scutella, M. G. (2009), "A heuristic based on multi-exchange techniques for a regional fleet assignment location-routing problem", Computer and Operational Research, Vol. 36,
pp. 442–460.

 

 

-     Archetti, C., Savelsbergh, M. W. P. and Speranza, M. G. (2008), "To split or not to split: That is the question", Transportation Research Part E, Vol. 44, pp. 114-123.

 

-     Barreto, S. S. (2004), "Análise e Modelização de Problemas de localização-distribuição [Analysis and modelling of location-routing problems]", Ph.D. Thesis, University of Aveiro, Aveiro, Portugal.

 

-     Boventer, V. (1961), "The relationship between transportation cost and location rent transportation problems", Journal of Regional Science, Vol. 3, No. 2,
pp. 27-40.

-     Coutinho-Rodrigues, J., Tralhão, L. and Alçada-Almeida, L. (2012), "Solving a location-routing problem with a multiobjective approach: the design of urban evacuation plans", Journal of Transport Geography, Vol. 22,
pp. 206–218.

 

-     Duhamel, C., Lacomme, P., Prins, C. and Prodhon, C. (2010), "A GRASP*ELS approach for the capaciated location-routing problem", Computers and Operations Research, Vol. 37, pp. 1912–1923.

 

-     Escobar, W. J., Linfati, R. and Toth, P. (2012), "A two-phase hybrid heuristic algorithm for the capacitated location-routing problem", Computers & Operations Research, Vol. 40,
pp. 70-79.

 

 

-     Ghafari-Nasab, N., Ahari, S. G. and  Ghazanfari, M. (2013), " A hybrid simulated annealing based heuristic for solving the location-routing problem with fuzzy demands", Scientia Iranica, In Press, Corrected Proof.

-     Glover, F. (1986), "Future paths for integer programming and links to artificial intelligence", Computer and operation research, Vol. 13, No. 5,
pp. 533-549.

 

-     Karaoglan, I., Altiparmak, F., Kara, I. and Dengiz, B. (2011), "A branch and cut algorithm for the location-routing problem with simultaneous pickup and delivery", European Journal of Operational Research, Vol. 211 ,
pp. 318–332.

 

-     Kirkpatrick, S., Gelatt, C.D. and Veechi, M.P. (1983), "Optimization by simulated annealing", Science, Vol. 220,
pp. 671–680.

 

-     Laporte, G. and Nobert, Y. (1981),
"An exact algorithm for minimizing routing and operating costs in depot location", European Journal of Operational Research, Vol. 6,
pp. 224–226.

 

 

-     Laporte, G., Nobert, Y. and Taillefer, S. (1988), "Solving a family of multi-depot vehicle routing and location-routing problems", Transportation Science, Vol. 22, pp.161–172.

 

-     Maranzana, F. E. (1965), "On the location of supply points to minimise transport costs", Operational Research Quarterly, Vol. 15, pp. 261–270.

 

-     Metropolis, N., Rosenbluth, A.W. and Teller, A.H. (1953), "Equation of state calculations by fast computing machins", Journal of chemichal Physics, Vol. 21, pp. 1087–1092.

 

-     Min, H., Jayaraman, V. and Srivastava, R. )1998(,  "Combined location-routing problems: A synthesis and future research directions", European Journal of Operational Research,Vol. 108,
pp.­1– 15.

 

-     Ozfirat P. M. and Ozkarahan I. (2010), "A Constraint programing heuristic for a heterogeneous vehicle routing problem with split deliveries", Applied Artificial Intelligence, Vol. 24, PP. 277–294.

 

-     Prins, C., Prodhon, C., Soriano, P. and Wolfler-Calvo, R. (2007), "Solving the capacitated location-routing problem by a coperative lagrangean relaxation-ganular tabu search heuristic", Transportation Science, Vol. 41,
pp. 470–483.

 

-     Tavakkoli-Moghaddama, R., Makuib, A., Mazloomic, Z. (2010), "A new integrated athematical model for a bi-objective multi-depot location-routing problem solved by a multi-objective scatter search algorithm", Journal of Manufacturing Systems, Vol. 29,
pp. 111-119.

 

-     Tuzun, D. and Burke, L. I. (1999),
"A two-phase tabu search approach to the location routing problem", European Journal of Operational Research, Vol. 116, pp. 87–99.

 

-     Wun, S.G. (2008), "Heuristic of location-routing problems with split delivery", Master Thesis, Industrial Engineering and Management, Chinese.

 

-     Yu, V. F., Lin, S.W., Lee, W. and Ting C.J. (2010), "A simulated annealing heuristic for the capacitated location-routing problem", Computers and Industrial Engineering, Vol. 58,
pp.­288–299.

 

-     Yu, V.F. and Lin, S.Y. (2012), "A Simulated Annealing Heuristic for the Open Location Routing Problem", International Conference on Innovation and Management, Republic of Palau, July pp.15-18.

 

-     Zarandi, M. F., Hemmati, A. and Davari,
S. (2011), "The multi-depot capacitated location-routing problem with fuzzy travel times", Expert Systems with Applications, Vol. 38, pp. 10075–10084.

 

-     Zarandi, M. F., Hemmati, A., Davari, S. and Turksen, B. (2013), "Capacitated location-routing problem with time windows under uncertainty ", Original Research Article, Vol. 37, pp. 480–489.