Efficient and rapid rescue activities are vital in the immediate aftermath of a large-scale disaster. However, the locations of demanders (those requiring special care or assistance) and responders (those supporting or assisting the demanders) are often widely separated. In this paper, we propose a method of supporting efficient travel and navigation for rescue activities using fuzzy c-means clustering and a genetic algorithm. We also propose an optimization method that takes into consideration the difference in workload required by demanders, compatibility between responders and demanders, and the urgency of demanders. We then demonstrate the efficiency of our proposed method based on numerical simulations and field experiments using a web application that incorporates the method.