بهینه سازی دو هدفه برای مسئله‏ ی مکان‏یابی - مسیریابی با در نظر گرفتن قابلیت اطمینان و هزینه فازی

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

نویسندگان

1 دانش‌آموخته کارشناس ارشد مهندسی صنایع، دانشگاه آزاد سلامی، واحد تهران جنوب، تهران

2 استاد دانشکده مهندسی صنایع، پردیس دانشکده‏ های فنی، دانشگاه تهران، تهران.

3 دانشیار مهندسی صنایع ،گروه مدیریت صنعتی، دانشگاه ولی عصر(عج) رفسنجان، کرمان.

چکیده

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

کلیدواژه‌ها

موضوعات


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

Bi-Objective Optimization for a Location-Routing Problem with Reliability and Fuzzy Cost

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

  • Najmeh Bahrampour 1
  • Reza Tavakkoli-Moghaddam 2
  • Nasser Shahsavari pour 3
3 Department of Industrial Management, Vali-e-Asr university, Rafsanjan, Iran
چکیده [English]

Location and routing problems in emergencies are so important. This paper
considers a location–routing problem with reliability by the means of
considering the probability of failure occurrence. The problem has two
objectives that minimizes the total cost and maximizes the reliability.
Maximizing the reliability is expressed as minimizing the expected cost of the
failure. In this problem, three kinds of failures are considered, which are:
failure of centers, routes and vehicles. Since travel costs is dependent on many
parameters and hence it is not possible to estimate exactly so they are
considered as fuzzy number using linguistic variables. At first, mathematical
formulation of the problem is presented, and then because the problem is the
NP-hard therefore, meta-heuristics algorithms are used to solve the model.
Additionally, a bi-objective discrete firefly algorithm is providedand then in
order to evaluate the performance of the algorithm, several test problems are
implemented and compared with the NSGA-II. The results show that the biobjective
discrete firefly algorithm has a better DM measure; however, it is
only suitable for small to medium-sized problems due to the MID measure
and it loses its efficiency in larger sizes.

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

  • Location - Routing
  • Reliability
  • Failure
  • Firefly Algorithm
  • NSGA-II
  • Fuzzy cost

[1] Ahmadi Javid, A., Azad, N. (2010). Incorporating location, routing and inventory decisions in supply chain network design. Transportation Research Part E: Logistics and Transportation Review, 46(5): 582-597.

[2] Ghaffari-Nasab, N., Ahari, S.G., Ghazanfari, M. (2013). A hybrid simulated annealing based heuristic for solving the location-routing problem with fuzzy demands. Scientia Iranica, 20(3): 919-930.

[3] Hassan-Pour, H., Mosadegh-Khah, M., Tavakkoli-Moghaddam, R. (2009). Solving a multi-objective multi-depot stochastic location-routing problem by a hybrid simulated annealing algorithm. Proceedings of the Institution of Mechanical Engineers, Part B: Journal of Engineering Manufacture, 223(8): 1045-1054.

[4] Min, H., Jayaraman, V., Srivastava, R.(1998). Combined location-routing problems: A synthesis and future research directions. European Journal of Operational Research, 108(1): 1-15.

[5] Nagy, G., Salhi, S. (2007). Location-routing: Issues, models and methods. European Journal of Operational Research, 177(2): 649-672.

[6] Prodhon, C., Prins, C. (2014). A Survey of Recent Research on Location-Routing Problems. European Journal of Operational Research 238(1): 1-17.

[7] Perl, J., Daskin, M. S. (1985). A warehouse location-routing problem. Transportation Research Part B: Methodological, 19(5): 381-396.

[8] Geoffrion, A. M., Graves, G. W. (1974). Multicommodity distribution system design by Benders decomposition. Management science. 20(5): 822-844.

[9] Wu, T.-H., Low, C., Bai, J.-W. (2002). Heuristic solutions to multi-depot location-routing problems. Computers & Operations Research, 29(10): 1393-1415.

[10] Govindan, K., Jafarian, A. Khodaverdi, R., Devika, K. (2014). Two-echelon multiple-vehicle location–routing problem with time windows for optimization of sustainable supply chain network of perishable food. International Journal of Production Economics 152: 9-28.

[11] Ghaffari-Nasab, N., Jabalameli, M. S., Aryanezhad, M. B., Makui, A. (2013). Modeling and solving the bi-objective capacitated location-routing problem with probabilistic travel times. The International Journal of Advanced Manufacturing Technology, 67(9-12): 2007-2019.

[12] Rath, S., Gutjahr, W.J.A. (2014). math-heuristic for the warehouse location–routing problem in disaster relief. Computers & Operations Research 42: 25-39.

[13] Samanlioglu, F. (2013). A multi-objective mathematical model for the industrial hazardous waste location-routing problem. European Journal of Operational Research, 2013. 226(2): 332-340.

[14] Laporte, G., Nobert, Y., Pelletier, P. (1983). Hamiltonian location problems. European Journal of Operational Research, 12(1): 82-89.

[15] Belenguer, J.-M., Benavent, E., Prins, C., Prodhon, C., Calvo, R. W. (2011). A branch-and-cut method for the capacitated location-routing problem. Computers & Operations Research, 38(6): 931-941.

[16] Contardo, C., Gendron, B., Cordeau, J.-F. (2011). A branch-and-cut-and-price algorithm for the capacitated location-routing problem.: CIRRELT.

[17] Laporte, G., Nobert, Y., Taillefer, S. (1988). Solving a family of multi-depot vehicle routing and location-routing problems. Transportation science, 22(3): 161-172.

[18] Hashemi Doulabi, S. H., Seifi, A. (2013). Lower and upper bounds for location-arc routing problems with vehicle capacity constraints. European Journal of Operational Research, 224(1): 189-208.

[19] 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(3): 407-428.

[20] Derbel, H., Jarboui, B., Hanafi, S., Chabchoub. H. (2010). An iterated local search for solving a location-routing problem. Electronic Notes in Discrete Mathematics, 36: 875-882.

[21] 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(3): 2865-2871.

[22] Jarboui, B., Derbel, H., Hanafi, S., Mladenović, N. (2013). Variable neighborhood search for location routing. Computers & Operations Research, 40(1): 47-57.

[23] Prins, C., Prodhon, C., Calvo , R.W. (2006). Solving the capacitated location-routing problem by a GRASP complemented by a learning process and a path relinking. 4OR, 4(3): 221-238.

[24] Jabal-Ameli, M., Aryanezhad, M., haffari-Nasab, N. G. (2011). A variable neighborhood descent based heuristic to solve the capacitated location-routing problem. International Journal of Industrial Engineering Computations, 2(1): 141-154.

[25] Prins, C., Prodhon, C., Calvo, R.W. (2006). A memetic algorithm with population management (MA| PM) for the capacitated location-routing problem, in Evolutionary computation in combinatorial optimization. Springer. 183-194.

[26] Ting, C.-J., Chen C.-H. (2013). A multiple ant colony optimization algorithm for the capacitated location routing problem. International Journal of Production Economics, 141(1): 34-44.

[27] Prins, C., Prodhon, C., Ruiz, A., Soriano, P., Calvo, R. W. (2007). Solving the capacitated location-routing problem by a cooperative Lagrangean relaxation-granular tabu search heuristic. Transportation Science, 41(4): 470-438.

[28] Contardo, C., Cordeau, J.-F., Gendron, B. (2014). A GRASP+ILP-based metaheuristic for the capacitated location-routing problem. Journal of Heuristics, 2014. 20(1): 1-38.

[29] Vahdani, B., Tavakkoli-Moghaddam, R., Jolai, F., Baboli, A. (2013). Reliable design of a closed loop supply chain network under uncertainty: An interval fuzzy possibilistic chance-constrained model. Engineering Optimization, 45(6): 745-765.

[30] Albareda-Sambola, M., Fernández, E., Laporte, G. (2007) Heuristic and lower bound for a stochastic location-routing problem. European Journal of Operational Research, 179(3): 940-955.

[31] Fazel Zarandi, M. H., Hemmati, A., Davari, S., Turksen, B. (2013). Capacitated location-routing problem with time windows under uncertainty. Knowledge-Based Systems, 37: 480-489.

[32] Cui, G. B., Li, Y. J. (2007). Combined location routing and inventory problem with fuzzy demand in logistics system. Control and Decision, 22(9): 1000.

[33] Watson-Gandy, C., Dohrn, P. (1973). Depot location with van salesmen—a practical approach. Omega, 1(3): 321-329.

[34] De Angelis, V., Nikoi C., Mecoli. MStorchi G,. (2007). Multiperiod integrated routing and scheduling of World Food Programme cargo planes in Angola. Computersand Operations Research, 34: 1601–15.

[35] Jacobsen, S. K., Madsen, O. B. (1980). A comparative study of heuristics for a two-level routing-location problem. European Journal of Operational Research, 5(6): 378-387.

[36] Snyder, L. V., Daskin, M. S. (2005). Reliability models for facility location: the expected failure cost case. Transportation Science, 39(3): 400-416.

[37] Papadakis, I. S., Ziemba, W. T. (2001). Derivative effects of the 1999 earthquake in Taiwan to US personal computer manufacturers, in Mitigation and Financing of Seismic Risks: Turkish and International Perspectives, Springer. 261-276.

[38] Snyder, L. V. (2003). Supply chain robustness and reliability: Models and algorithms. Ph.D. dissertation, Northwestern University, Department of Industrial Engineering & Management Sciences.

[39] ReVelle, C., Hogan. K. (1989). The maximum availability location problem. Transportation Science, 23(3): 192-200.

[40] Lim, M., Daskin, M. S., Bassamboo, A., Chopra, S. (2010). A facility reliability problem: formulation, properties, and algorithm. Naval Research Logistics (NRL), 57(1): 58-70.

[141Berman, O., Krass, D., Menezes, M. B. (2007). Facility reliability issues in network p-median problems: strategic centralization and co-location effects. Operations Research, 55(2): 332-350.

[42] Cui, T., Ouyang, Y., Shen, Z.-J.M. (2010). Reliable facility location design under the risk of disruptions. Operations research, 58(4-part-1): 998-1011.

[43] Helander, M.E., Melachrinoudis, E. (1997). Facility location and reliable route planning in hazardous material transportation. Transportation science, 31(3): 216-226.

[44]Sansó, B., Soumis, F. (1991). Communication and transportation network reliability using routing models. Reliability, IEEE Transactions on, 40(1): 29-38.

[45] Li, J.-Q., Mirchandani, P.B., Borenstein, D. (2009). Real-time vehicle rerouting problems with time windows. European Journal of Operational Research, 194(3): 711-727.

[46] Wang, X., Wu, X., Hu, X. (2010). A study of urgency vehicle routing disruption management problem. in Information Engineering (ICIE), 2010 WASE International Conference on. IEEE.

[47] Mu, Q., Fu, Z., Lysgaard, J., Eglese, R. (2011). Disruption management of the vehicle routing problem with vehicle breakdown. Journal of the Operational Research Society, 62(4): 742-749.

[48] Ukkusuri, S., Yushimito, W. (2008). Location routing approach for the humanitarian prepositioning problem. Transportation Research Record: Journal of the Transportation Research Board, 2089: 18-25.

[49] Yang, X.-S. (2014). Chapter 8-Firefly Algorithms, in Nature-Inspired Optimization Algorithms, X.-S. Yang, Editor. Elsevier: Oxford. 111-127.

[50] Jati, G. K. (2011). Evolutionary discrete firefly algorithm for travelling salesman problem. Springer. http://prodhonc.free.fr/Instances/instances_us.htm.

[51] سکاک، مصطفی؛ عزیزی، وحید؛ کریمی، حسین. (1393). مسئله مکان‏یابی-مسیریابی چند دپویی ظرفیت دار با برداشت و تحویل همزمان و بارهای برش یافته: مدلسازی و حل ابتکاری، پژوهش‏های مهندسی صنایع در سیستم­های تولید2(4): 81-67.