A Three-Phase Heuristic Method for the Bus Evacuation Problem with Evacuee Self-Relocation

Background: Efficient bus evacuation requires a routing plan that serves all pickup demand while respecting vehicle and shelter capacities. The two-phase heuristic method proposed by Bish constructs a feasible plan and then improves bus routes; however, it does not account for evacuees’ ability to relocate between nearby pickup points. Objective: This study develops a three-phase heuristic method that incorporates selective evacuee self-relocation and route repair. Methods: The proposed method is evaluated using an illustrative instance, three small benchmark instances, and the Kampung Pencut network in Lembang, West Java, Indonesia. Results: For Kampung Pencut, Phase 1 yields a makespan of 446 s, which decreases to 386 s in Phase 2 and 334 s in Phase 3. The additional self-relocation phase reduces the makespan by 13.47% relative to Phase 2 and by 25.11% relative to Phase 1. For the three small benchmark instances without self-relocation, the bus-routing heuristic matches the exact solutions, achieving a 0% optimality gap. The observed CPU times range from 189 to 287 s, compared with 750 to 1,676 s for exact optimization. The speed analysis indicates greater relative improvements at lower bus speeds, with makespan reductions of 19.78% at 20 km/h and 19.30% at 30 km/h. Conclusion: These results suggest that self-relocation can reduce the workload on critical bus routes, particularly when bus travel times are high.