Debris occurs from the ruin and wreckage of structures during a disaster. Proper removal of debris is of great importance because it blocks roads and prohibits emergency aid teams from accessing disaster affected regions. Poor disaster management, lack of efficiency and delays in debris removal cause disruptions in providing shelter, nutrition, healthcare and communication services to disaster victims, and more importantly, result in loss of lives. Due to the importance of systematic and efficient debris removal from the perspectives of improving disaster victims quality of life and allowing the transportation of emergency relief materials, the focus of this study is on providing emergency relief supplies to disaster affected regions as soon as possible by unblocking roads through removing the accumulated debris. We develop a mathematical model for the problem that requires long CPU times for large instances. Since it is crucial to act quickly in an emergency case, we also propose a heuristic methodology that solves instances with an average gap of 1% and optimum ratio of 80.83%. (C) 2015 Elsevier Ltd. All rights reserved.