Research output: Contribution to Journal/Magazine › Journal article › peer-review
Research output: Contribution to Journal/Magazine › Journal article › peer-review
}
TY - JOUR
T1 - Branch and bound algorithms for the bus evacuation problem
AU - Goerigk, Marc
AU - Grün, Bob
AU - Heßler, Philipp
PY - 2013/12
Y1 - 2013/12
N2 - The bus evacuation problem (BEP) is a vehicle routing problem that arises in emergency planning. It models the evacuation of a region from a set of collection points to a set of capacitated shelters with the help of buses, minimizing the time needed to bring the last person out of the endangered region. In this work, we describe multiple approaches for finding both lower and upper bounds for the BEP, and apply them in a branch and bound framework. Several node pruning techniques and branching rules are discussed. In computational experiments, we show that solution times of our approach are significantly improved compared to a commercial integer programming solver.
AB - The bus evacuation problem (BEP) is a vehicle routing problem that arises in emergency planning. It models the evacuation of a region from a set of collection points to a set of capacitated shelters with the help of buses, minimizing the time needed to bring the last person out of the endangered region. In this work, we describe multiple approaches for finding both lower and upper bounds for the BEP, and apply them in a branch and bound framework. Several node pruning techniques and branching rules are discussed. In computational experiments, we show that solution times of our approach are significantly improved compared to a commercial integer programming solver.
KW - Branch and bound
KW - Disaster management
KW - Evacuation planning
KW - Heuristics
KW - Integer programming
U2 - 10.1016/j.cor.2013.07.006
DO - 10.1016/j.cor.2013.07.006
M3 - Journal article
AN - SCOPUS:84881121864
VL - 40
SP - 3010
EP - 3020
JO - Computers and Operations Research
JF - Computers and Operations Research
SN - 0305-0548
IS - 12
ER -