用於志工選擇問題之評估研究

Performance evaluation for Participant Selection Problem

林均彥(Chun-Yen Lin)

指導教授 ： 張韻詩

國立清華大學/電機資訊學院/資訊工程學系/碩士(2016年)

摘要

此論文致力於解決一個組合最佳化的問題叫做Participant Selection Problem (志工指派問題)。PSP為解決如何挑選適合的志工進行勘災，以利提供災情資訊於彌補感測器無法覆蓋之地區。我們規劃四種PSP模型用來處理不同災害情境下的志工分配應對，其中我們專注於PSP-Frugal與PSP-Practical這兩個PSP模型的效能評估。我們透過MATLAB在不同機率分布下亂數產生的各個志工的貢獻值及花費值，以及根據不同變異係數用於表示災區之間的嚴重程度。此論文透過現有且強力的最佳化求解器及一個啟發式演算法PSP-G來解決PSP問題，並從中比較各個求解器及演算法的效能。我們希望透過實驗來得知在特定災害情況下選擇適合的求解器來解決PSP，以利於災害中心在指派志工上能更加有效率。

關鍵字

組合最佳化 ； 廣義指派問題 ； 整數線性規劃 ； 效能評估

並列摘要

This main focus of this thesis is to solve a combinatorial optimization problem called the Participant Selection Problem (PSP). PSP aims to find an assignment of selected participants assigned to regions that their reports can eliminate blind spots and improve resolution in sensor coverage. We formulated four variants of PSP to take into account of requirements and constraints in the participant selection for some disaster scenarios. This thesis presents the performance evaluation of PSP-Frugal and PSP-Practical because they are practical assignments for real situations. We generated synthetic parameters of PSS and TAS with different probability distributions by MATLAB. PSS includes the number of volunteers, the benefit and cost values of each volunteer, and the total budget. TAS includes the number of regions and the values of the regions. We use the evaluated solvers and the PSP-G heuristic algorithm to solve the PSP, and compared relative performance by figure of merits. We hope to show some insights that which evaluated solvers and the PSP-G algorithm can produce good solutions in available time with different characteristics of problem instances.

並列關鍵字

combinatorial optimization ； generalized assignment problem ； integer linear programming ； performance evaluation

參考文獻

[8] Charu C. Aggarwal and Tarek Abdelzaher, "Integrating Sensors and Social Networks," Social Network Data Analytics, Springer, pp. 379-412, 2011.

[9] R. F. Ahmad, A. S. Malik, A. Qayyum and N. Kamel, "Disaster monitoring in urban and remote areas using satellite stereo images: A depth estimation approach," 2015 IEEE 11th International Colloquium on Signal Processing Its Applications, pp. 150-155, March 2015.

[13] GAMS (General Algebraic Modeling System), http://www.gams.com/

[15] Wang Suxin, Wang Leizhen, Li Yongqing and Sun Jianyong, "Study on ant colony optimization for people assign to job problem", The 2012 24th Chinese Control and Decision Conference (CCDC), pp. 872-874, May 2012.

[17] Lu Zaixin and W.W. Li, "Approximation algorithms for maximum target coverage in directional sensor networks", The 2014 IEEE 11th International Conference on Networking, Sensing and Control, pp. 155-160, April 2014.