Conflict-based multi-capacity constraint route planning

Planning and scheduling mass departure is critical for tsunami disaster management. Algorithm that can generate effective evacuation plan and schedule is required. The evacuation plan and schedule have to ensure that the whole population can be moved to safety areas before the calamity of tsunami takes its impact on the land. Current heuristic solutions fail from computational complexity by assuming that the network's elements, such as nodes and edges, have infinite capacity. Their approaches generate lazy evacuation route and evacuation plan as one instance. They fail to ensure their scalability when dealing with a real problem, i.e. huge transportation networks. This paper introduces a refinement of a multi-capacity constrained heuristic routing algorithm, which embedded a conflict-based path generation for evacuation scheduling. The algorithm is exercised on tsunami scenario in a capital city (northern coast of North Sulawesi, Indonesia which has the population of more than 400,000 lives. The proposed algorithm improves the computation time significantly (80%) while maintaining the time required for executing the evacuation plan the previous solution.