مدلی چند هدفه برای مسئله مکان یابی – مسیریابی با زمان های سفر و تحویل فازی

نویسندگان

دانشگاه آزاد اسلامی واحد قزوین

چکیده

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

کلیدواژه‌ها


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

A Multi-Objective Model for the Location Routing Problem with fuzzy Travel Times and Due Dates

چکیده [English]

In this study the location routing problem with fuzzy parameters is taken into account, this problem involves determining the location of the depots and routing of the vehicles in order to serve the customers. In this study a location routing problem with fuzzy travel times and due dates is considered and two objective models are proposed. The considered objectives are minimizing the total costs of the network and minimizing the total weighted tardiness. The costs of the network include the fixed installation costs and the transportation costs. In order to solve this problem a mathematical model is proposed. However since this problem is categorized into NP-hard problem; the mathematical model cannot be solved efficiently. Therefore meta-heuristic algorithms are proposed to efficiently solve this problem

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

  • Location Routing Problem
  • Facility Location
  • Fuzzy Programming
  • Multi-Criteria Decision Making
[1] Tuzun, D. & Burke, L. I. "A two-phase tabu search approach to the location routing problem". European Journal of Operational Research, Vol.116, pp. 87-99, 1999.

[2] Cornuejols, G., Fisher, M. L. & Nemhauser, G. L. "Exceptional Paper—Location of Bank Accounts to Optimize Float: An Analytic Study of Exact and Approximate Algorithms". Management Science, Vol.23, pp. 789-810, 1977.

[3] Karp, R. M."Reducibility among combinatorial problems". Springer, 1972.

[4] Gary, M. R. & Johnson, D. S. "Computers and Intractability: A Guide to the Theory of NP-completeness". WH Freeman and Company, New York, 1979.

[5] Megiddo, N. & Supowit, K. J. "On the complexity of some common geometric location problems". SIAM journal on computing, Vol.13, pp. 182-196, 1984.

[6] Shen, Z. "Integrated supply chain design models: a survey and future research directions". Journal of Industrial and Management Optimization, Vol.3, pp. 1, 2007.

[7] Prins, C., Prodhon, C. & Calvo, R. W. "Solving the capacitated location-routing problem by a GRASP complemented by a learning process and a path relinking". 4OR, Vol.4, pp. 221-238, 2006.

[8] Salhi, S. & Rand, G. K. "The effect of ignoring routes when locating depots". European Journal of Operational Research, Vol.39, pp. 150-156, 1989.

[9] Karaoglan, I., Altiparmak, F., Kara, I. & Dengiz, B. "The location-routing problem with simultaneous pickup and delivery: Formulations and a heuristic approach". Omega, Vol.40, pp. 465-477, 2012.

[10] Xu, Z., Xu, D. & Zhu, W. "Approximation results for a min–max location-routing problem". Discrete Applied Mathematics, Vol.160, pp. 306-320, 2012.

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

[12] Martínez-Salazar, I. A., Molina, J., Ángel-Bello, F., Gómez, T. & Caballero, R. "Solving a bi-objective Transportation Location Routing Problem by metaheuristic algorithms". European Journal of Operational Research, 2013.

[13] Derbel, H., Jarboui, B., Hanafi, S. & Chabchoub, H. "Genetic algorithm with iterated local search for solving a location-routing problem".Expert Systems with Applications, Vol.39, pp. 2865-2871, 2012.

[14] Laporte, G., Nobert, Y.,"An exact algorithm for minimizing routing and operating costs in depot location". European Journal of Operational Research 6, 224–226, 1981.

[15] Chan, Y., Carter, W.B., Burnes, M.D., "A multiple-depot, multiple-vehicle, location-routing problem with stochasticallyprocessed demands". Computers and Operations Research 28,803–826, 2001.

[16] Liu, S.C., Lee, S.B., "A two-phase heuristic method for the multi-depot location routing problem taking inventory control decisions into considerations". International Journal of advanced Manufacturing Technology 22, 941–950, 2003.

[17] Albareda-Sambola, M., Ferna´ndez, E., Laporte, G.,"Heuristic and lower bound for a stochastic location-routing problem". European Journal of Operational Research 179, 940-955, 2007.

 [18] Zarandi, M. H. F., Hemmati, A. & Davari, S. "The multi-depot capacitated location-routing problem with fuzzy travel times". Expert Systems with Applications, Vol.38, pp. 10075-10084, 2011.

[19] Contardo, C., Hemmelmayr, V. & Crainic, T. G. "Lower and upper bounds for the two-echelon capacitated location-routing problem" Computers & Operations Research, Vol.39, pp. 3185-3199, 2012.

[20] Mehrjerdi, Y. Z. & Nadizadeh, A. "Using greedy clustering method to solve capacitated location-routing problem with fuzzy demands". European Journal of Operational Research, 2013.

[21] Ghaffari-Nasab, N., Ahari, S. G. & Ghazanfari, M. "A hybrid simulated annealing based heuristic for solving the location-routing problem with fuzzy demands". Scientia Iranica, 2013.

[22] Deb, K., Pratap, A., Agarwal, S. & Meyarivan, T. "A fast and elitist multiobjective genetic algorithm: NSGA-II, 2002.

[23] Sivanandam, S. & Deepa, S. "Introduction to genetic algorithms". Springer, New York, 2008.

[24] Kirkpatrick, S., Jr., D. G. & Vecchi, M. P. "Optimization by simmulated annealing' Science". Vol.220, pp. 671-680, 1983.

[25] Albareda-Sambola, M., Dıaz, J.A., Fernandez, E.,"Acompact model and tight bounds for a combined locationroutingproblem". Computers and Operations Research 32,407–428, 2005.

[26] Jafari, A., Golozari, F., "Application of Ranking Function to Solve Fuzzy Location-Routing Problem with L-R fuzzy Numbers". 2nd IEEE International Conference on Information and Financial Engineering (ICIFE), 351 – 355, 2010.

[27] Kumar, R. & Singh, P."Pareto evolutionary algorithm hybridized with local search for biobjective tsp". Hybrid Evolutionary Algorithms. Springer, 2007.

[28] Nguyen, V.-P., Prins, C. & Prodhon, C. "A multi-start iterated local search with tabu list and path relinking for the two-echelon location-routing problem".Engineering Applications of Artificial Intelligence, Vol.25, pp. 56-71, 2012-a.

[29] Nguyen, V.-P., Prins, C. & Prodhon, C. "Solving the two-echelon location routing problem by a GRASP reinforced by a learning process and path relinking". European Journal of Operational Research, Vol.216, pp. 113-126, 2012-b.

[30] Srinivas, N. & Deb, K. "Muiltiobjective optimization using nondominated sorting in genetic algorithms". Evolutionary Computation, Vol.2, pp. 221-248, 1994.

[31] Zarandi, M. H. F., Hemmati, A., Davari, S. & Burhan Turksen, I. "Capacitated location-routing problem with time windows under uncertainty". Knowledge-Based Systems, 2012