OPEN ACCESS
A typical disaster surveillance and early warning system often needs to make timely and critically important preparedness decisions before disasters strike. When crowdsourcing observational data from people to enhance its sensor coverage, the system must be able to make effective use of volunteers, guide them during their exploration of the threatened area, and process reports from them in real time to extract decision support information of sufficiently good quality. This article focuses on the participant selection problem (PSP) which the system must solve in order to select participants from available volunteers given the benefits and costs of deploying them. The PSP-Greedy (PSP-G) algorithm proposed is known to be a near-optimal solution with a small fraction of execution time when compared with well-known optimization methods. The article describes an implementation of the PSP-G algorithm and the integration of the resultant PSP-G module into the Ushahidi platform. Performance data from two case studies based on Haiti Earthquake, 2010, and Typhoon Morakot, 2009, also described here, clearly show that PSP-G is a general practical solution.
crowdsourcing, disaster management, maximum general assignment, social network
[1] Sahana FOSS Disaster Management System, available at http://en.wikipedia.org/wiki/Sahana_FOSS_Disaster_Management_System
[2] Ushahidi Research, available at http://en.wikipedia.org/wiki/Ushahidi
[3] Deep Horizon Oil Spill, available at http://en.wikipedia.org/wiki/Deepwater_Horizon_ oil_spill and http://www.google.com/crisisresponse/oilspill/
[4] 2009 California Wildfires, available at http://en.wikipedia.org/wiki/2009_California_ wildfires
[5] Typhoon Morakot Aftermath, available at http://en.wikipedia.org/wiki/Typhoon_ Morakot#Taiwan_3
[6] Chu, E.T.-H., Chen, Y.L., Lin, J.-Y. & Lin, J.W.S., Crowdsourcing support system for disaster surveillance and response. Proc. of 15th International Symposium on Wireless Personal Multimedia Communications (WPMC), 2012.
[7] Chu, E.T.-H, Lin, C.Y., Tsai, P.-H. & Liu, J.W.S., Participant selection for crowdsourcing disaster information. WIT Transactions on the Built Environment, 133, pp. 205–215, 2013. doi: http://dx.doi.org/10.2495/dman130211
[8] BARON, available at http://neos.mcs.anl.gov/neos/solvers/go:BARON/GAMS.html
[9] Bonmin, available at http://neos.mcs.anl.gov/neos/solvers/minco:Bonmin/GAMS.html
[10] 2010 Haiti Earthquake, available at http://en.wikipedia.org/wiki/2010_Haiti_earthquake
[11] Typhoon Morakot, available at http://en.wikipedia.org/wiki/Typhoon_Morakot
[12] Generalized Assignment Problem, available at http://en.wikipedia.org/wiki/Generalized_assignment_problem
[13] Oncan, T., A survey of generalized assignment problem and its applications. Information Systems and Operation Research, 45(3), pp. 123–141, 2007. doi: http://dx.doi. org/10.3138/infor.45.3.002
[14] Penticoa, D.W., Assignment problems: a Golden anniversary survey. European Journal of Operational Research, 176(2), pp. 774–793, 2007. doi: http://dx.doi.org/10.1016/j. ejor.2005.09.014
[15] Knapsack Problem, available at http://en.wikipedia.org/wiki/Knapsack_problem
[16] Subset Sum Problem, available at http://en.wikipedia.org/wiki/Subset_sum_problem
[17] Kwon, T. & Cho, D.-H., Adaptive-modulation-and-coding-based transmission of control messages for resource allocation in mobile communication systems. IEEE Transactions on Vehicular Technology, 58(6), pp. 2769–2780, 2009. doi: http://dx.doi. org/10.1109/tvt.2008.2008651
[18] Bartoli, G., Tassi, A., Marabissi, D., Tarchi, D. & Fantacci, R., An optimized resource allocation scheme based on a multidimensional multiple-choice approach with reduced complexity. Proc. of ICC, pp. 1–6, 2011. doi:http://dx.doi.org/10.1109/ icc.2011.5962916
[19] Chen, J., Wang, S. & Chen, C., Method research for dynamic multi-project human resource allocation based on Multidimension model. Proc. of ICCIII, pp. 78–81, 2011. doi: http://dx.doi.org/10.1109/iciii.2011.304
[20] NEOS, available at http://neos.mcs.anl.gov/neos/solvers/index.html
[21] Lin, C.-Y., Chu, E.T.H., Ku, L.-W. & Liu, J.W.S., Active disaster response system for smart buildings. Sensors, 14(9), pp. 17451S–17470S, 2014. doi: http://dx.doi.org/10.1109/is3c.2014.134
[22] Timeline of relief efforts after the 2010 Haiti earthquake, available at http://en.wikipedia. org/wiki/Timeline_of_relief_efforts_after_the_2010_Haiti_earthquake
[23] AlphaECP, available at http://www.neos-server.org/neos/solvers/minco:AlphaECP/ GAMS.html
[24] DICOPT, available at http://www.neos-server.org/neos/solvers/minco:DICOPT/ GAMS.html