A multi-cover routing problem for planning rapid needs assessment under different information-sharing settings

摘要

In this paper, we introduce a multi-cover routing problem (MCRP), which is motivated by post-disaster rapid needs assessment operations performed to evaluate the impact of the disaster on different affected community groups. Given a set of sites, each carrying at least one community group of interest, the problem involves selecting the sites to be visited and constructing the routes. In practice, each community group is observed multiple times at different sites to make reliable evaluations; therefore, the MCRP ensures that pre-specified coverage targets are met for all community groups within the shortest time. Moreover, we assume that the completion time of the assessment operations depends on the information-sharing setting in the field, which depends on the availability of information and communication technologies (ICT). Specifically, if remote communication is possible, each assessment team can share its findings with the central coordinator immediately after completing the site visits; otherwise, all teams must return to the origin point to share information and finalize the assessments. To address these different information-sharing settings, we define two MCRP variants with different objectives and present alternative formulations for these variants. We propose two constructive heuristics and a tabu search algorithm to solve the MCRP, and conduct an extensive computational study to evaluate the performance of our heuristics with respect to different benchmark solutions. Our results show that the proposed tabu search algorithm can achieve high-quality solutions for both MCRP variants quickly. The results also highlight the importance of considering the availability of ICT in the field while devising assessment plans.