بررسی و حل مسئله‏ ی امدادرسانی دوسطحی نقاط آسیب‏ دیده از بحران

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

نویسندگان

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

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

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

چکیده

امدادرسانی به نقاط آسیب ‏دیده نیازمند برنامه ‏ریزی مناسبی است. معمولاً، در حوادث پیش‏ آمده، دسترسی به همه‏ ی نقاط امکان ‏پذیر نیست؛ از این رو، امدادرسانی در دو سطح با امکانات متفاوت شاید راه‏ حل مناسبی باشد. این مقاله به بررسی مسئله‏ ی امدادرسانی دوسطحی ظرفیت‏ دار با پنجره‏ های زمانی سخت برای افرادی می‏ پردازد که در ناحیه ‏ای بحران ‏زده قرار گرفته‏ اند. هدف این مقاله تعیین مجموعه‏ ای بهینه از پایگاه‏های امداد جهت استقرار گروه‏ های امدادرسان و مسیریابی بهینه ‏ی این گروه‏ ها برای امداد رسانی به کلیه‏ ی نقاط آسیب ‏دیده، با کمترین زمان و هزینه، است. پس از معرفی یک مدل برنامه ‏ریزی خطی عدد صحیح مختلط، الگوریتم ژنتیک برای حل مسئله‏ ی مورد نظر در ابعاد بزرگ ارائه شده است. نتایج بررسی مثال‏های عددی حاکی از کارایی الگوریتم پیشنهادی است. همچنین، به منظور بررسی کارایی مدل پیشنهادی برای مسئله‏ ی امدادرسانی، مدل‏های دیگر مورد استفاده بررسی شدند و نتایج مقایسه ‏ای با دیگر مدل‏های مرتبط نظیر مسئله‏ ی مسیریابی ـ مکان‏یابی یک‏ سطحی و مسئله‏ ی تور پوششی در موقعیت امدادرسانی حاکی از عملکرد مناسب‏تر مدل پیشنهادی است.

کلیدواژه‌ها


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

Modeling and a Genetic Algorithm for the Two-Echelon Relief logistics Problem

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

  • Hossein Jamali 1
  • Mahdi Bashiri 2
  • Reza Tavakkoli-Moghaddam 3
1 Ph.D. Student of Industrial Engineering, Faculty of Engineering, Payam-e-Noor University, Tehran, Iran.
2 Associate Professor, Department of Industrial Engineering, Faculty of Engineering, Shahed University, Tehran, Iran
3 Professor, Department of Industrial Engineering, College of Engineering, University of Tehran, Tehran, Iran.
چکیده [English]

Disaster relief to the affected areas is one of the necessities for any proper planning. Usually during disaster, the accesses to areas are limited; therefore, disaster relief using two-level with different features could be a good solution. In this paper, a two-echelon capacitated relief problem with hard time windows is proposed for people who have been affected in disaster area. The aim of this paper is to determine the optimal set of relief center services to establish the optimal routing aid and relief teams to the affected areas with minimal time and cost. After the introduction of a mixed-integer linear programming, a genetic algorithm for solving the problem of large-scale is provided. The results of numerical examples show the efficiency of the proposed algorithm. In addition, to evaluate the effectiveness of the proposed model for the relief problems, other existing models are investigated and examined. Comparative results with other related models such as one-level  location-routing problem and covering tour problem in disaster relief illustrate the superior performance of our proposed model.

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

  • Two-Echelon Location Routing Problem
  • Hard Time Windows
  • genetic algorithm
  • Relief
  • Sensitivity analysis
1. Altay N., Green; III, W.G. (2006). OR/MS Research in Disaster Operations Management. European Journal of Operational Research, 175, 475-493.
2. Jacobsen, S. K.; Madsen, O. B. G. (1980). A Comparative Study of Heuristics for a Two-Level Routing-Location Problem. European Journal of Operational Research, 5, 378-387.
3. Madsen, O. B. G. (1983). Methods for Solving Combined Two Level Location-Routing Problems of Realistic Dimensions. European Journal of Operational Research, 12, 295-301.
4. Nagy, G.; Salhi, S. (1996). Nested Heuristics Methods for the Location-Routing Problem. Journal of Operational Research Society, 47, 1166-1174.
5. Tuzun, D.; Burke, L. I. (1999). A Two-Phase Tabu Search Approach for the Location-Routing Problem. European Journal of Operational Research, 116, 87-99.
6. Boccia, M. et al. (2010). A Metaheuristic for a Two Echelon Location-Routing Problem. Festa P. (eds.) Experimental Algorithms: Lecture Notes in Computer Science, Springer, 6049, 288-301.
7. Nikbakhsh, E.; Zegordi, S. H. (2010). A Heuristic Algorithm and a Lower Bound for the Two-Echelon Location-Routing Problem with Soft Time Window Constraints. SCIENTIA IRANIKA, 17, 36-47.
8. Nolz, P. C. et al. (2010). A Bi-Objective Metaheuristic for Disaster Relief Operation Planning. Coello C. A. et al. in Multi Objective Nature Inspired Computing, SCI, 272, 167-187.
9. Crainic, T. G.; Sforza, A.; Sterle, C. (2011a). Location-Routing Models for Two-Echelon Freight Distribution System Design. Technical Report CIRRELT-2011, 40.
10. Crainic, T. G.; Sforza, A.; Sterle, C. (2011b). Tabu Search Heuristic for a Two-Echelon Location-Routing Problem. Technical Report CIRRELT-2011-07.
11. Rath, S.; Gutjahr, W. J. (2011). A Math-Heuristic for the Warehouse Location-Routing Problem in Disaster Relief. Computers and Operations Research, doi:10.1016/j.cor.2011.07.016.
12. Belenguer, J. et al. (2011). A Branch-and-Cut Method for the Capacitated Location-Routing Problem. Computers and Operations Research, 38, 931-941.
13. Contardo, C.; Cordeau, J. F.; Gendron, B. (2013). A Computational Comparison of Flow Formulations for the Capacitated Location-Routing Problem. Discrete Optimization, 10, 263-295.
14. Contardo, C.; Crainic, T. G.; Hemmelmayr, V. (2012). Lower and Upper Bounds for the Two-Echelon Capacitated Location-Routing Problem. Computers and Operations Research, 39, 3215-3228.
15. Nguyen, V.-P.; Prins, C.; Prodhon, C. (2012a). Solving the Two-Echelon Location-Routing Problem by a GRASP Reinforced by a Learning Process and Path Relinking. European Journal of Operational Research, 216, 113-126.
16. Nguyen, V.-P.; Prins, C.; Prodhon, C. (2012b). A Multi-Start Iterated Local Search with Tabu List and Path Relinking for the Two-Echelon Location-Routing Problem. Engineering Applications of Artificial Intelligence, 25, 56-71.
17. Pirkwieser, S.; Raidl, G. R. (2010). Variable Neighborhood Search Coupled with ILP-Based Very Large Neighborhood Searches for the (Periodic) Location-Routing Problem. M. J. Blesa, C. Blum, G. Raidl, A. Roli and M. Sampels Hybrid Metaheuristics: Lecture Notes in Computer Science, Springer, 6373, 174-189.
18. Schwengerer, M.; Pirkwieser, S.; Raidl, G. R. (2012). A Variable Neighborhood Search Approach for the Two-Echelon Location-Routing Problem. J.-K. Hao and M. Middendorf (eds.) Evolutionary Computation in Combinatorial Optimization: Lecture Notes in Computer Science, Springer, 7245, 13-24.
19. Naji-Azimi, Z. et al. (2012). A Covering Tour Approach to the Location of Satellite Distribution Centers to Supply Humanitarian Aid. European Journal of Operational Research, 222, 596-605.
20. Govindan, K. et al. (2013). Two-Echelon Multiple-Vehicle Location-Routing Problem with Time Windows for Optimization of Sustainable Supply Chain Network of Perishable Food. Int. J. Production Economics, http://dx.doi.org/10.1016/j.ijpe.2013.12.028.
21. Wang, H.; Du, L.; Ma, Sh. (2014). Multi-Objective Open Location-Routing Model with Split Delivery for Optimized Relief Distribution in Post-Earthquake. Transportation Research Part E, 69, 160-179.
22. Prodhon, C.; Prins, C. (2014). A Survey of Recent Research on Location-Routing Problems. European Journal of Operational Research, http://dx.doi.org/10.1016/j.ejor.2014.01.005.
23. Gendreau, M.; Laporte, G.; Semet, F. (1997). The Covering Tour Problem. Operation Research, 45, 568-576.