An Exact Branch-and-Price Algorithm for Scheduling Rescue Units during Disaster Response

G. Rauchecker, G. Schryen, European Journal of Operational Research 272 (2019) 352–363.

Download
OA JOURNAL VERSION.pdf 1.47 MB
Journal Article | English
Author
Rauchecker, Gerhard; Schryen, GuidoLibreCat
Abstract
In disaster operations management, a challenging task for rescue organizations occurs when they have to assign and schedule their rescue units to emerging incidents under time pressure in order to reduce the overall resulting harm. Of particular importance in practical scenarios is the need to consider collaboration of rescue units. This task has hardly been addressed in the literature. We contribute to both modeling and solving this problem by (1) conceptualizing the situation as a type of scheduling problem, (2) modeling it as a binary linear minimization problem, (3) suggesting a branch-and-price algorithm, which can serve as both an exact and heuristic solution procedure, and (4) conducting computational experiments - including a sensitivity analysis of the effects of exogenous model parameters on execution times and objective value improvements over a heuristic suggested in the literature - for different practical disaster scenarios. The results of our computational experiments show that most problem instances of practically feasible size can be solved to optimality within ten minutes. Furthermore, even when our algorithm is terminated once the first feasible solution has been found, this solution is in almost all cases competitive to the optimal solution and substantially better than the solution obtained by the best known algorithm from the literature. This performance of our branch-and-price algorithm enables rescue organizations to apply our procedure in practice, even when the time for decision making is limited to a few minutes. By addressing a very general type of scheduling problem, our approach applies to various scheduling situations.
Publishing Year
Journal Title
European Journal of Operational Research
Volume
272
Issue
1
Page
352 - 363
LibreCat-ID

Cite this

Rauchecker G, Schryen G. An Exact Branch-and-Price Algorithm for Scheduling Rescue Units during Disaster Response. European Journal of Operational Research. 2019;272(1):352-363.
Rauchecker, G., & Schryen, G. (2019). An Exact Branch-and-Price Algorithm for Scheduling Rescue Units during Disaster Response. European Journal of Operational Research, 272(1), 352–363.
@article{Rauchecker_Schryen_2019, title={An Exact Branch-and-Price Algorithm for Scheduling Rescue Units during Disaster Response}, volume={272}, number={1}, journal={European Journal of Operational Research}, publisher={Elsevier}, author={Rauchecker, Gerhard and Schryen, Guido}, year={2019}, pages={352–363} }
Rauchecker, Gerhard, and Guido Schryen. “An Exact Branch-and-Price Algorithm for Scheduling Rescue Units during Disaster Response.” European Journal of Operational Research 272, no. 1 (2019): 352–63.
G. Rauchecker and G. Schryen, “An Exact Branch-and-Price Algorithm for Scheduling Rescue Units during Disaster Response,” European Journal of Operational Research, vol. 272, no. 1, pp. 352–363, 2019.
Rauchecker, Gerhard, and Guido Schryen. “An Exact Branch-and-Price Algorithm for Scheduling Rescue Units during Disaster Response.” European Journal of Operational Research, vol. 272, no. 1, Elsevier, 2019, pp. 352–63.
All files available under the following license(s):
Copyright Statement:
This Item is protected by copyright and/or related rights. [...]
Main File(s)
File Name
Access Level
OA Open Access
Last Uploaded
2018-12-13T15:16:37Z


Export

Marked Publications

Open Data LibreCat

Search this title in

Google Scholar