Obstacle-Aware Continuous Location-Routing in Disaster-Struck Areas
Yazz Warsame, Xuzhe Dang, Stefan Edelkamp · 2025
This paper addresses the critical logistical challenges in disaster-struck urban environments, where rapid response is essential for clearing debris and rubble and delivering supplies and medical aid. We introduce a novel framework for Obstacle-Aware Continuous Location-Routing in DisasterStruck Areas. In the continuous location routing problem, facilities can be located anywhere in the environment, which may include areas obstructed by obstacles. Our approach integrates motion planning techniques to navigate obstacles effectively and identify collision-free areas for facility placement. The solution unfolds in three phases: First, we use sampling-based motion planning to construct a probabilistic roadmap, enabling collision-free trajectories between pickups. Second, we address the capacitated clustering problem through a capacitated agglomerative clustering algorithm to form pickup clusters. For each cluster, we then solve the continuous facility location problem using a reinforcement learning-based method, a grid map approach, and a modified center of gravity method. Finally, we tackle the vehicle routing problem as a multi-pickup and delivery problem with time windows, utilizing OPTIC as our planning solver. The experimental setup employs a second-order vehicle model within an obstacle-rich environment. We evaluate the performance of our methods by analyzing various routes and costs under different parameters, such as the alpha value of the reinforcement algorithm and the maximum item load. The results are measured in terms of runtime and average travel distance, demonstrating the effectiveness of our approach.