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

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

نویسندگان

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

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

چکیده

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

کلیدواژه‌ها


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

Modeling for the Covering Tour Problem in Relief Condition for Disaster Management

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

  • Hossein Jamali 1
  • Mahdi Bashiri 2
1 Faculty of industrial Engineering, Payam-e-Noor University, Tehran, Iran
2 Faculty of Industrial Engineering, Shahed University, Tehran, Iran
چکیده [English]

This paper deals with examining the locations of crisis relief zone for events of disruption and crisis to present
a new modeling for it. Due to limited resources in such situations, it may be impossible for rescue teams to
visit all the places; therefore, people in rural areas need to travel to the cities for seeking essential commodities.
Cities should be located in an accessible distance for rural areas. The goal of this paper is to develop a Hamiltonian
tour on a subset of cities located at the shortest distance in order to cover all affected rural areas during disaster. A
genetic algorithm was proposed to solve the large-scale problems. In order to validate the proposed model, three
small-scale problems were solved and the associated results were compared with optimum solutions obtained
by GAMS software. The obtained results indicated that the proposed algorithm was efficient and convergent to
optimal solutions. In addition, the corresponding covering tour problem and traveling salesmen problem were
solved by the proposed algorithm. The comparison of results indicated that the covering tour problem was more
efficient. Also, the sensitivity analysis was conducted for the covering tour problem identifying essential conditions
of using the covering problem for crisis relief problems.

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

  • Covering tour Problem
  • Modeling
  • Hard Time Windows
  • Relief
  • and Genetic Algorithm
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.