Strategies for Evacuating from an Affected Area with One or Two Groups

摘要

This paper considers the problem faced by a group of evacuees who must leave from an affected area as quickly as possible. We seek the strategies that achieve a bounded ratio of evacuation path length without any boundary information to that with. We restrict the affected area to a convex region in the plane, and investigate the problem in two scenarios: general plane and plane in grid network. In these two scenarios, we first present efficient strategies with one or two groups and analyze the competitive ratios of them. In general plane, we give a 30.47-competitive strategy for one group evacuation and a 15.58-competitive strategy for two groups evacuation. In grid network, we give a 33-competitive strategy for one group evacuation and a 19-competitive strategy for two groups evacuation.