یک روش ابتکاری برای یک مسئله‌ی دو هدفه حمل و نقل با کاربرد در مواقع بحران

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

نویسندگان

1 دانش آموخته کارشناسی ارشد، دانشگاه فردوسی مشهد، مشهد، ایران

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

3 دانش آموخته کارشناس ارشد، دانشگاه فردوسی مشهد، مشهد، ایران

چکیده

بحران­های ناشی از حوادث طبیعی به علت گستردگی حوزه­ی اثر و ناگهانی بودن، شرایطی ایجاد می­کنند که فرآیند تصمیم­گیری و مدیریت را برای مدیران دشوار می­سازند. در چنین مواقعی معمولاً به علت اتخاذ تصمیمات شتاب­زده، بخش قابل توجهی از منابع سازمانی و ملّی به صورتی ناکارآمد به هدر رفته؛ اثربخشی و کارایی خدماتِ ارائه شده به شکل محسوسی کاهش می‌یابد. از این رو بهره­گیری از روش­هایی که توانایی ارائه­ی راهکارهای بهینه در موضوعاتی مانند امدادرسانی به آسیب­دیدگان و به طور خاص حمل و نقل کالاهای امدادی را داشته باشند، اهمیت ویژه­ای دارد. مسئله­ی ارائه شده در این مقاله به بیان مدلی با رویکرد سیاست بهینه برای امداد­رسانی و با دو هدف 1) حداکثرسازی مجموع ارزش تقاضای تحویل داده شده به آسیب­دیدگان و 2) حداقل­سازی هزینه­ی امدادرسانی (زمان یا مسافتِ طی شده توسط وسایل نقلیه­ی امدادی) می­پردازد. از جمله فرضیاتِ کاربردی این مسئله، عدم امکانِ امدادرسانی مستقیم به برخی از نقاط به علت در دسترس نبودن راه­های ارتباطی می­باشد؛ لذا تعدادی از نقاط با تحت پوشش قرار گرفتن توسط نقاط ملاقات­شده، خدمت خود را دریافت می­کنند. به منظور حل مسئله، یک الگوریتم ترکیبی با تلفیق روش­های «جستجوی همسایگی بزرگ انطباقی (ALNS)[i]» و «جستجوی محلی چند هدفه (MDLS)[ii]» تحت نامِ ALNS×MDLS مطرح شده است. نتایج حاصل نشان­دهنده­ی کارایی روش ارائه شده می­باشد.
 
 
 

کلیدواژه‌ها


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

A Hybrid Heuristic Algorithm for a Bi-Objective Problem in Humanitarian Relief Transportation

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

  • R. Eshtehadi 1
  • M Salari 2
  • S Alayari 3
چکیده [English]

Natural disasters are abrupt events and have extended effects on vast areas. Due to these features, decision making and crisis management are complicated tasks. In this situation, hasty decisions may cause immense waste of organizational and national resources and drop in quality of services. This study provides a model to optimize emergency services with regard to two objectives, namely 1) maximizing the total satisfied demand of customers, and 2) minimizing the cost of emergency services (i.e., time or distance). One of the practical assumptions of this problem is using the covering idea to provide the customers demand in case of unavailability of communication paths to the customers. Essentially, the demand of each customer can be satisfied by directly visiting it on a vehicle route or it can be covered by other visited customers located within a given pre-specified distance of it. We propose a node-based mathematical formulation. Moreover, to obtain the Pareto frontier, we present a hybrid bi-objective heuristic algorithm by combining the adaptive large neighborhood search (ALNS) and multi-directional local search (MDLS) algorithms. The performance of the proposed algorithm is tested on a set of 72 randomly generated instances. Computational results indicate the effectiveness of the proposed algorithm.
 
 

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

  • Logistics
  • Disaster Management
  • ALNS
  • MDLS

 

─        Altay, Nezih and Green Iii, Walter G. (2006), ''OR/MS research in disaster operations management'', European Journal of Operational Research, 175 (1), pp.475-93.

 ─        Azi, Nabila, Gendreau, Michel, and Potvin, Jean-Yves (2010), "An adaptive large neighborhood search for a vehicle routing problem with multiple trips" (CIRRELT).

 ─        Barbarosoğlu, Gülay, Özdamar, Linet, and Cevik, Ahmet (2002), ''An interactive approach for hierarchical analysis of helicopter logistics in disaster relief operations'', European Journal of Operational Research, 140 (1), pp.118-33.

 ─        Campbell, Ann Melissa, Vandenbussche, Dieter, and Hermann, William (2008), ''Routing for relief efforts'', Transportation science, 42 (2), pp.127-45.

 ─        Caunhye, Aakil M., Nie, Xiaofeng, and Pokharel, Shaligram (2012), ''Optimization models in emergency logistics: A literature review'', Socio-Economic Planning Sciences, 46 (1), pp.4-13.

 ─        Current, John R and Schilling, David A (1989), ''The covering salesman problem'', Transportation science, 23 (3), pp.208-13.

 ─        Dessouky, Maged, et al. (2006), ''Rapid distribution of medical supplies'', Patient Flow: Reducing Delay in Healthcare Delivery (Springer), pp.309-38.

 ─        Doerner, Karl, Focke, Axel, and Gutjahr, Walter J (2007), “Multicriteria tour planning for mobile healthcare facilities in a developing country”, European Journal of Operational Research, No. 179 (3), pp.­1078-96.

 ─        Eksioglu, Burak, Vural, Arif Volkan, and Reisman, Arnold (2009), “The vehicle routing problem: A taxonomic review”, Computers & Industrial Engineering, No. 57 (4), pp. 1472-83.

 ─        Enz, R., Zimmerli., P., Schwarz., S., (2009), “natural catastrophes and man-made disasters in 2008”, Sigma, 2.

 ─        Federal Emergency Management Agency (2008), ''IS-26 guide to points of distribution(PODs)''.

 ─        Gendreau, Michel, Laporte, Gilbert, and Semet, Frédéric (1997) “The covering tour problem”, Operations Research, No. 45 (4), pp. 568-76.

 ─        Golden, Bruce L, Raghavan, Subramanian, and Wasil, Edward A (2008), ''The vehicle routing problem [electronic resource]": latest advances and new challenges (43: Springer).

 ─        Hake, T. (2012), “Haiti earthquake relief efforts hampered by logistics problems”, <http://www.examiner.com/natural-disasters-innational/Haitiearthquakereliefefortshamperedbylogisticsproblems >.

 ─        Hodgson, M John, Laporte, Gilbert, and Semet, Frédéric (1998), “A Covering Tour Model for Planning Mobile Health Care Facilities in SuhumDistrict, Ghama”, Journal of Regional Science, No. 38 (4), pp. 621-38.

 ─        Jia, Hongzhong, Ordóñez, Fernando, and Dessouky, Maged (2007), “A modeling framework for facility location of medical services for large-scale emergencies”, IIE transactions, Np. 39 (1), pp. 41-55.

 ─        Knott, Roger (1987), “The logistics of bulk relief supplies”, Disasters, No. 11 (2), pp. 113-15.

 ─        Li, Feiyue, Golden, Bruce, and Wasil, Edward (2007), “The open vehicle routing problem: Algorithms, large-scale test problems, and computational results”, Computers & Operations Research, No. 34 (10), pp. 2918-30.

 ─        Liu, Ran, Jiang, Zhibin, and Geng, Na (2012), “A hybrid genetic algorithm for the multi-depot open vehicle routing problem”, OR Spectrum, pp. 1-21.

 ─        Mete, Huseyin Onur and Zabinsky, Zelda B (2010), “Stochastic optimization of medical supply location and distribution in disaster management”, International Journal of Production Economics, No. 126 (1), pp. 76-84.

─         

─        Naji-Azimi, Zara, et al. (2012), “A covering tour approach to the location of satellite distribution centers to supply humanitarian aid”, European Journal of Operational Research, No. 222 (3), pp. 596-605.

 ─        Nolz, Pamela C, et al. (2010), “A bi-objective metaheuristic for disaster relief operation planning”, Advances in multi-objective nature inspired computing (Springer), pp. 167-87.

 ─        Pisinger, David and Ropke, Stefan (2007), “A general heuristic for vehicle routing problems”, Computers & Operations Research, No. 34 (8), pp. 2403-35.

 ─        Rawls, Carmen G and Turnquist, Mark A (2010), “Pre-positioning of emergency supplies for disaster response”, Transportation research part B: Methodological, No. 44 (4), pp. 521-34.

 ─        economics (2012), “Pre-positioning and dynamic delivery planning for short-term response following a natural disaster”, Socio-Economic Planning Sciences, No. 46 (1), pp. 46-54.

 ─        Ropke, Stefan and Pisinger, David (2006), “An adaptive large neighborhood search heuristic for the pickup and delivery problem with time windows”, Transportation science, No. 40 (4), pp. 455-72.

 ─        Salari, Majid, Toth, Paolo, and Tramontani, Andrea (2010), “An ILP improvement procedure for the Open Vehicle Routing Problem”, Computers & Operations Research, No. 37 (12), pp. 2106-20.

 ─        Schott, Jason R (1995), “Fault Tolerant Design Using Single and Multicriteria Genetic Algorithm Optimization”, (DTIC Document).

 ─        Schrage, Linus (1981), “Formulation and structure of more complex/realistic routing and scheduling problems”, Networks, No. 11 (2), pp. 229-32.

 ─        Tarantilis, CD and Kiranoudis, CT (2002), “Distribution of fresh meat”, Journal of Food Engineering, No. 51 (1), pp. 85-91.

 ─        Tricoire, Fabien (2012) “Multi-directional local search”, Computers & Operations Research, No. 39 (12), pp. 3089-101.

 ─        Tzeng, Gwo-Hshiung, Cheng, Hsin-Jung, and Huang, Tsung Dow (2007), “Multi-objective optimal planning for designing relief delivery systems”, Transportation Research Part E: Logistics and Transportation Review, No. 43 (6), pp. 673-86.

 ─        Van Hentenryck, Pascal, Bent, Russell, and Coffrin, Carleton (2010), “Strategic planning for disaster recovery with stochastic last mile distribution”, Integration of AI and OR techniques in constraint programming for combinatorial optimization problems (Springer), pp. 318-33.

 ─        Van Wassenhove, Luk N (2005), “Humanitarian aid logistics: supply chain management in high gear†”, Journal of the Operational Research Society, No. 57 (5), pp. 475-89.

 ─        Yi, Wei and Kumar, Arun (2007), “Ant colony optimization for disaster relief operations”, Transportation Research Part E: Logistics and Transportation Review, No. 43 (6), pp. 660-72.

 ─        Zitzler, E. (1999), “Evolutionary Algorithms for multi-objective optimization: method and applications”, P.h.D Thesis, dissertation ETH No. 13398 (Swaziland Federal Institute of Technology Zorikh).

 ─        Zitzler, Eckart, Deb, Kalyanmoy, and Thiele, Lothar (2000), “Comparison of multiobjective evolutionary algorithms: Empirical results”, Evolutionary computation, No. 8 (2), pp. 173-95.