Solving Bus Evacuation Problem Using Simulated Annealing
Khusnul Novianingsih*, Kartika Yulianti, Ririn Sispiyati

Mathematics Study Program, Faculty of Mathematics and Science Education, Universitas Pendidikan Indonesia, Bandung 40132, Indonesia
*k_novianingsih[at]upi.edu

Abstract

A problem to evacuate residents in urban region to emergency shelter locations using available public transport infrastructures is considered in this paper. Well known as a bus evacuation problem, the problem is formulated as a binary integer programming model to determine the shortest routes for vehicles based on capacitated vehicle routing model. Then, Simulated Annealing Algorithm is implemented to solve the model. The algorithm starts by generating an initial solution that meets the vehicle capacity constraints at a high temperature. In each iteration, the temperature will be reduced and a new solution is generated using the exchange, insertion, or reversion method. The new solution with a better objective function value will be accepted as a temporary solution. Otherwise, it may be accepted with a certain probability. The algorithm stops if the final temperature is reached. The numerical results show that the algorithm produces the optimal vehicle routes with minimum total distance and it provides the minimum number of vehicles required to evacuate all residents.

Keywords: Bus Evacuation Problem- Evacuation Route- Simulated Annealing- Optimization-

Topic: Mathematics