A limited resource assignment problem with shortage in the fire department

Iranian Journal of Numerical Analysis and Optimization

مقاله 7، دوره 8، شماره 1 - شماره پیاپی 13، خرداد 2018، صفحه 129-141   

نوع مقاله: Research Article

شناسه دیجیتال (DOI): 10.22067/ijnao.v8i1.40776

نویسندگان

E.S. Alavi؛ R. Ghanbari^*

Ferdowsi University of Mashhad

چکیده

Assigning available resources to fire stations is a main task of fire depart ment’s administrator in a city. The importance of this problem increases when the number of available resources are inadequate. In this situation, the goal is to assign the limited available resources to fire stations such that the associated penalties of the shortages are minimized. Here, we first give a mathematical approach to consider some penalties for the shortage. Next, we give an integer program to minimize the sum of associated penalties. The proposed model can be used in many other problems arisen from health services, emergency management, and so on. We also propose a heuristic to efficiently solve the problem in a reasonable time. Our proposed heuristic has two phases. In the first phase, using a greedy approach, our proposed heuristic constructs a proper feasible solution. Next, in the second phase, we propose a local search to improve the quality of the solution constructed in the first phase. To show the efficiency of our proposed heuristic, we com pare our proposed heuristic with CPLEX based on the running time and the quality of obtained solutions on two groups of problems (real-word problems and randomly generated problems). The numerical results show that on the 80% of benchmark problems, the obtained solution is the same as CPLEX’s solutions. Also, the running time of our proposed algorithm is almost 10 times better than CPLEX’s running time, in average.

کلیدواژه‌ها

Resource assignment problem؛ Fire stations؛ Shortage؛ integer programming؛ Heuristics

مراجع

1. Chanta, S., Mayorga, M., and McLay, L. A. Improving emergency service in rural areas: a bi-objective covering location model for EMS systems, Ann. Oper. Res. 221 (2014), 133–159.

2. Chou, J .-S., Tsai, C. -F., Chen, Z. -Y., and Sun. M. -H. Biologicalbased genetic algorithms for optimized disaster response resource allocation, Computers & Industrial Engineering 74 (2014), 52–67.

3. Furness, A. and Muckett, M. Introduction to Fire Safety Management, Elsevier Ltd., 2007.

4. Ghanbari, R. and Mahdavi-Amiri, N. Solving bus terminal location problems using evolutionary algorithms, Applied Soft Computing, 11 (2011), 991–999.

5. Goldberg J. B. Operations research models for the deployment of emergency services vehicles, EMS Management Journal, 1 (2004), 20–39.

6. Guo, M., Li, B., Zhang, Z., Wu, S., and Song, J. Efficiency evaluation for allocating community-based health services, Computers & Industrial Engineering, 65 (2013), no. 3, 395–401.

7. Huang, Y., Fan, Y., and Cheu, R. Optimal allocation of multiple emergency service resources for protection of critical transportation infrastructure, Transportation Research Record: Journal of the Transportation Research Board 2022 (2007),1–8.

8. Maleki, M., Majlesinasab, N., and Sepehri, M. M. Two new models for redeployment of ambulances, Computers & Industrial Engineering 78(2014), 271–274.

9. Marianov, V. and ReVelle, C. The capacitated standard response fire protection siting problem: Deterministic and probabilistic models, Annals of Operations Research 40 (1992), no. 1, 303–322.

10. Papadimitriou, C. H. and Steiglitz, K. Combinatorial Optimization: Algorithms and Complexity, Prentice-Hall, Inc., Englewood Cliffs, N.J.,1982.

11. Simpson, N. C. and Hancock, P. G. Fifty years of operational research and emergency response, Journal of Opertional Research Society 60 (2009), 126–139.

12. Wright, P. D., Liberatore, M. J., and Nydick, R. L. A survey of operations research models and applications in homeland security, Interfaces 36 (2006), no. 6, 514–529.

13. Yang, L., Jones, B. F., and Yang, S. -H. A fuzzy multi-objective programming for optimization of fire station locations through genetic algorithms, European Journal of Operational Research 181 (2007), no. 2, 903–915.