Ant colony optimization to solve the rescue problem as a vehicle routing problem with hard time windows

Abstract

The rescue problem is an adaptation of a standard Vehicle Routing Problem where a set of patients suffering from various medical conditions has to be picked up by a set of ambulances and brought back to the hospital. Optimizing this problem is important to improve the use of life emergency vehicles in daily or disaster situations. Although this problem is usually modeled as a Capacitated Vehicle Routing Problem, different formulations are proposed in the literature including multi-objective optimization with shortest route and maximization of the number of patients that will survive or remain stable. Ant Colony Optimization (ACO) and Genetic Algorithms (GA) are frequently used, where ACO performs better on objectives specific to the rescue problem. We model the problem as a single-objective Vehicle Routing Problem with Time Windows (VRPTW) using hard time windows. Each patient is assigned a degree of injury and a corresponding maximum time window. An immediate return to the hospital for critically injured patients is also introduced. The rescue problem turns to a VRPTW with hard time windows for different problem sizes and is solved with ACO. The results suggest that with a sufficiently large fleet, it can be ensured that critically injured patients are reached in good time.