Solving the Life Detector Routing Problem over a Street Network: A Multi-Start-based Approach

Abstract Life detectors were successfully used in the search-and-rescue actions after several major earthquakes around the world. To efficiently find buried victims after massive earthquakes in urban areas, emergency response agencies need to design the least-distance tour for life detectors to visit collapsed buildings and find trapped people. The life detector routing problem (LDRP) aims to find the least-distance tour for a life detector to scan a set of collapsed buildings in an urban street network. This study develops two algorithmic frameworks to solve large-scale problem instances of the LDRP, namely the double-loop-based method and the multi-start-based method. To evaluate the performance of these methods, three meta-heuristics are incorporated in the proposed frameworks, including simulated annealing, Tabu search, and iterated greedy algorithms. The algorithms are evaluated using test instances that are generated based on real-world urban street networks. The computational results show that the proposed frameworks are more effective than a classical two-stage heuristic for solving the test instances of the LDRP. The results also indicate that, with similar computational efforts, the multi-start-based method outperforms the double-loop-based method. Moreover, the average total distance for visiting all of the collapsed buildings decreases with the increase in the detection radius. The findings and the results provide a valuable reference to emergency response agencies in the search-and-rescue actions after massive earthquakes.