ارائه الگوریتم ژنتیک با مرتب‌سازی نامغلوب جهت حل مدل دو هدفه مسأله‌ی حمل‌و‌نقل- مکان‌یابی- مسیریابی با در نظر گرفتن تقاضای غیر قطعی

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

نویسندگان

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

2 کارشناس ارشد، گروه مهندسی صنایع، دانشکده فنی و مهندسی، دانشگاه یزد، یزد.

چکیده

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

کلیدواژه‌ها

موضوعات


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

Non-Dominated Sorting Genetic Algorithm for Bi-Objective Transportation Location Routing Problem under Demand Uncertainty

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

  • Mahboobeh Honarvar 1
  • Mehdi Khalili 2
چکیده [English]

Effective management of distribution of manufactured goods plays an important role in the success and increasing of competition' levels in manufacturing organization. Location routing problem is a problem in which location of distribution center and vehicle routing are considered simultaneously. In this paper, a two-stage stochastic programming model and a meta-heuristic approach are presented for the Transportation Location Routing Problem. Customers can order different products. Capacitated central centers transport different products to open intermediary Distribution Centers (IDCs) and then these products are distributed from IDCs between the customers. A bi-objective optimization model is developed. Two objectives, minimization of the overall costs and maximization of the total served demand, are addressed. Due to the high complexity of the problem, we use the Non-Dominated Sorting Genetic Algorithm to solve the problem. The initial parameters of this algorithm is set with Taguchi method. Computational results show the effectiveness of the proposed solution method to solve problems in different dimensions.

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

  • Multi-product Transportation Location Routing Problem
  • two-stage stochastic programming
  • Non-dominated Sorting Genetic Algorithm
  • Epsilon-Constraint method
[1] Karaoglan, I., Altiparmak, F., Kara, I., Dengiz, B. (2012). “The location-routing problem with simultaneous pickup and delivery: Formulations and a heuristic approach”, Omega, 40: 465-477.
[2] Salhi, S., Rand, G.K. (1989). “The effect of ignoring routes when locating depots”, European Journal of Operational Research, 39: 150-156.
[3] Boventer, E. (1961). “The relationship between  transportation costs and location rent in transportation problems”, Journal of Regional Science, 3: 27-40
[4] Maranzana, F. (1964). “On the location of supply points to minimize transport costs”. OR, 261-270
[5] Aksen, D., Altinkemer, K. (2008). “A location-routing problem for the conversion to the “click-and-mortar” retailing: The static case”, European Journal of Operational Research, 186: 554-575.
[6] Madsen, O.B. (1983). “Methods for solving combined two level location-routing problems of realistic dimensions, European Journal of Operational Research, 12:295-301.
[7] Murty, K.G., Djang, P.A. (1999). “The US Army national guard's mobile training simulators location and routing problem”, Operations Research, 47(2): 175-182
[8] Rath, S., Gutjahr, J. (2014). “A math-heuristic for the warehouse location–routing problem in disaster relief, Computers & Operations Research, 42: 25-39
[9] Kulcar, T. (1996). “Optimizing solid waste collection in Brussels”, European Journal of Operational Research, 90: 71-77.
[10] Nagy, G., Salhi, S. (2007). “Location-routing: Issues, models and methods”, European Journal of Operational Research, 177: 649-672.
[11] Prodhon, C., Prins, C. (2014). “A Survey of Recent Research on Location-Routing Problems”, European Journal of Operational Research, In Press.
[12] Birge, J.R.. Louveaux, F. (2011). “Introduction to stochastic programming”, Springer.
[13] Laporte, G., Louveaux, F., Mercure, H. (1989). “Models and exact solutions for a class of stochastic location-routing problems”, European Journal of Operational Research, 39(1): 71-78.
[14] Mete, H.O., Zabinsky, Z.B. (2010). “Stochastic optimization of medical supply location and distribution in disaster managemen”, International Journal of Production Economics, 126(1): 76-84.
[15] Michael, R.G., Johnson, D.S. (1979). Computers and Intractability: A guide to the theory of NP-completeness, WH Freeman & Co, San Francisco
[16] Laporte, G., Nobert, Y. (1981). An exact algorithm for minimizing routing and operating costs in depot location, European Journal of Operational Research, 6: 224-226.
[17] Albareda-Sambola, M., Dı́az, J.A., Fernández, E. (2005). A compact model and tight bounds for a combined location-routing problem, Computers & Operations Research, 32: 407-428.
[18] Belenguer, J.-M., Benavent, E., Prins, C., Prodhon, C., Wolfler Calvo, R. (2011). A branch-and-cut method for the capacitated location-routing problem, Computers & Operations Research, 38: 931-941.
[19] Baldacci, R., Mingozzi, A. Wolfler Calvo, R. (2011). An exact method for the capacitated location-routing problem, Operations Research, 59: 1284-1296.
[20] Derbel, H., Jarboui, B., Hanafi, S., Chabchoub, H. (2012). Genetic algorithm with iterated local search for solving a location-routing problem, Expert Systems with Applications, 39: 2865-2871.
[21] ستاک، مصطفی؛ عزیزی، وحید، کریمی، حسین. (1393). مسأله مکان‌یابی مسیریابی چنددپویی ظرفیت‌دار با برداشت و تحویل همزمان و بارهای برش‌یافته: مدلسازی و حل ابتکاری، پژوهشهای مهندسی صنایع در سیستمهای تولید، 2(4): 67-81.
[22] جعفری، عزیزاله، صادقی سروستانی، آیلین. (1393). مدلسازی مسئله مکانیابی- مسیریابی باز با تحویل چندبخشی و حل آن با استفاده از الگوریتم انجماد تدریجی، پژوهشهای مهندسی صنایع در سیستمهای تولید، 2(3): 61-47
[23] حسینی، سید محمدحسن، خلجی علیایی، سهیلا. (1394). مدل‌سازی ریاضی مسأله مکان‌یابی- مسیریابی با در نظر گرفتن ظرفیت، تنوع و محدودیت تردد وسایل حمل و نقل و توسعه یک مدل حل مبتنی بر الگوریتم کلونی مورچگان، پژوهشهای مهندسی صنایع در سیستمهای تولید، 3(5): 91-105.
[24] Kachitvichyanukul, V., Luong, H., Pitakaso, R., (2012). “A Comparison of ILS and VNS Heuristics for Multi-stages and Multi-objectives Location-routing Problem”, Proceedings of the Asia Pacific Industrial Engineering & Management Systems Conference.
[25] Martínez-Salazar, I., Molina, J., Ángel-Bello, F., Gómez, T., Caballero, R. (2014). “Solving a bi-objective Transportation Location Routing Problem by metaheuristic algorithms”, European Journal of Operational Research, 234: 25-36.
[26] Berube, F. J., Gendreau, M., Potvin, J. (2009), “An exact-constraint method for bi-objective combinatorial optimization problems: Application to the Traveling Salesman Problem with Profits: European Journal of Operational Research, 194: 39-50.
[27] Goldberg, D.E. (1989). “Genetic algorithms in search, optimization, and machine learning”.
[28] Deb, K., et al. (2002). “A fast and elitist multi-objective genetic algorithm: NSGA-II”, Evolutionary Computation, IEEE Transactions on, 6: 182-197.
[29] Schaffer, J.D. (1985). “Multiple Objective Optimization with Vector Evaluated Genetic Algorithms, in Proceedings of the 1st International Conference on Genetic Algorithms”, L. Erlbaum ssociates Incorporated, 93-100.
[30] Zitzler, E., Thiele, L. (1999). “Multi objective evolutionary algorithms: a comparative case study and the strength Pareto approach” Evolutionary Computation, IEEE Transactions on, 3: 257-271
[31] Behnamian, J., Fatemi Ghomi, S., Zandieh, M. (2009). “A multi-phase covering Pareto-optimal front method to multi-objective scheduling in a realistic hybrid flowshop using a hybrid metaheuristic”, Expert Systems with Applications, 36: 11057-11069.
[32] Taguchi, G. (1986). “Introduction to quality engineering: designing quality into products and processes”.
[33] Prins, C., Prodhon, C., Wolfler-Calvo, R. (2004). Nouveaux algorithmes pour le problème de localisation et routage sous contraintes de capacité, MOSIM.