مد لسازی مسئله ی تور پوششی در شرایط امدادرسانی برای مدیریت بحران

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

نویسندگان

1 گروه مهندسی صنایع، دانشگاه پیام نور، تهران، ایران

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

چکیده

این مقاله به بررسی مکان یابی مراکز امدادرسانی افرادی که در یک ناحیه ی بحران زده قرار دارند، می پردازد و یک مدل سازی جدید برای آن
ارائه می دهد. در چنین وضعیتی به دلیل محدودیت امکانات، این امر که تیم امدادرسان همه ی نقاط آسیب دیده را بازدید کند ممکن نیست و مردم
روستاها باید برای به دست آوردن کالاهای حیاتی به شهرها مراجعه نمایند. شهرها باید در یک فاصله ی قابل دسترسی برای اهالی روستاها قرار
گیرند. هدف این مسئله تشکیل یک تور همیلتونی روی زیر مجموعه ای از این شهرها با حداقل زمان )طول( است، به طوری که همه ی روستاهای
حادثه دیده نیز پوشش یابند. برای حل مسئله ی مذکور در ابعاد بزرگ، الگوریتم فراابتکاری ژنتیک ارائه و استفاده شده است. به منظور اعتبارسنجی
مدل پیشنهادی، سه مسئله با ابعاد کوچک حل شده و جواب های به دست آمده از الگوریتم ژنتیک پیشنهادی با جواب های دقیق به دست آمده
توسط نرم افزار گیمز ) Gams ( مقایسه شده است. نتایج به دست آمده نشان می دهند که الگوریتم پیشنهادی کارا و همگرا به جواب بهینه است.
همچنین مسئله ی تور پوششی و مسئله ی فروشنده ی دوره گرد متناظر با آن، توسط الگوریتم ژنتیک حل گردیده و جواب ها نشان می دهند که
استفاده از مسئله ی تور پوششی برای مسائل امدادرسانی به مراتب کاراتر است. همچنین این مقاله به تحلیل حساسیت مسئله ی تور پوششی
می پردازد که نتایج بررسی، شرایط الزام استفاده از مدل تور پوششی برای مسائل امداد رسانی را معین می کند.

کلیدواژه‌ها


1. Altay, N., Green, W.G. (2006). OR/MS research in disaster
operations management. European Journal of
Operational Research, vol. 175(1), 475-493.
2. Gendreau, M., Laporte, G., Semet, F. (1997). The covering
tour problem. Operation Research, vol. 45(4),
568-576.
3. Current, J.R., Schilling, D.A. (1989). The covering
salesman problem. Transportation Science, vol. 23(3),
208-213.
4. Current, J.R., Schilling, D.A. (1994). The median tour
and maximal covering tour problems: Formulations
and heuristic. European Journal of Operational Research,
vol. 73(1),114-126.
5. Hachicha, M., Hodgson, M.J., Laporte, G., Semet, F.
(2000). Heuristic for the multi-vehicle covering tour
problem. Computers and Operations Research, vol.
27(1), 29-42.
6. Motta, L., Ochi, L.S., Martinhon, C. (2001). Grasp
metaheuristics for the generalized covering tour
problem, Paper presented at the MIC2001-4th Metaheuristics
Int Conf. Porto, Portugal.
7. Baldacci, R., Boschetti, M.A., Maniezzo, V., Zamboni,
M. (2005). Scatter search methods for the covering
tour problem Metaheuristic optimization via memory
and evolution, Springer, 59-91.
8. Jozefowiez, N., Semet, F., Talbi, E.-G. (2007). The biobjective
covering tour problem. Computers & Operations
Research, vol. 34(7), 1929-1942.
9. Nolz, P.C., Doerner, K.F., Gutjahr, W.J., Hartl, R.F.
(2010). A bi-objective metaheuristic for disaster relief
operation planning Advances in multi-objective
nature inspired computing, Springer, 167-187.
10. Tricoire, F., Graf, A., Gutjahr, W. J. (2012). The bi-objective
stochastic covering tour problem. Computers
& Operations Research, vol. 39(7),1582-1592.
11. Naji-Azimi, Z., Renaud, J., Ruiz, A., Salari, M. (2012).
A covering tour approach to the location of satellite
distribution centers to supply humanitarian aid.
European Journal of Operational Research, vol. 222(3),
596-605.
12. Salari, M., Naji-Azimi, Z. (2012). An integer programming-
based local search for the covering salesman
problem. Computers & Operations Research, vol.
39(11), 2594-2602.
13. Ebrahimi, A., Sahraeian, R. (2012). The Maximal
Backup Covering Tour Problem, Paper presented at
the 6th International Conference on Industrial Engineering
and Industrial Management.
14. Oliveira, W. A., Mello, M. P., Moretti, A. C., Reis, E.
F. (2013). The multi-vehicle covering tour problem:
building routes for urban patrolling, arXiv preprint
arXiv:1309.5502.
15. Lopes, R., Souza, V.A., da Cunha, A.S. (2013). A
Branch-and-price Algorithm for the Multi-Vehicle
Covering Tour Problem, Electronic Notes in Discrete
Mathematics, vol. 44, 61-66.
16. Hà, M.H., Bostel, N., Langevin, A., Rousseau, L.-M.
(2013). An exact algorithm and a metaheuristic for
the multi-vehicle covering tour problem with a constraint
on the number of vertices. European Journal of
Operational Research, vol. 226(2), 211-220.
17. Prins, C. (2009). A GRASP× evolutionary local search
hybrid for the vehicle routing problem Bio-inspired
algorithms for the vehicle routing problem, Springer,
35-53.
18. Allahyari, S., Salari, M., Vigo, D. (2015). A hybrid
metaheuristic algorithm for the multi-depot covering
tour vehicle routing problem. European Journal of
Operational Research, vol. 242(3), 756-768.
19. Kammoun, M., Derbel, H., Ratli, M., Jarboui, B.
(2015). A variable neighborhood search for solving
the multi-vehicle covering tour problem. Electronic
Notes in Discrete Mathematics, vol. 47, 285-292.
20. Lien, Y.-N., Jang, H.-C., & Tsai, T.-C. (2009). A
MANET based emergency communication and information
system for catastrophic natural disasters.
Paper presented at the 29th IEEE International
Conference on Distributed Computing Systems
Workshops. Montreal, QC, Canada.