We present an agent-based coalition formation approach for disaster response applications. We assume that agents are operating in a dynamic and dangerous environment, and they need to form convoys to traverse unsafe areas. We introduce a commitment-based convoy model, where the commitments are negotiated between the participant agents. We show that this leads to a complex multi-issue negotiation, with two spatial and two temporal components. We propose an approach for reducing the negotiation space through the creation of discrete offer points, and describe a possible negotiation flow. We validate the model in a scenario using the map of New Orleans flooded by hurricane Katrina.