A New Evolutionary Method to Deal with the Dynamic Vehicle Routing Problem

摘要

This paper investigates the dynamic version of the vehicle routing problem (DVRP), where new demands that arrive during the traveling horizon are considered and treated. When the environment changes (new demands are revealed), the solutions are to be adapted to take into consideration the new demands, while respecting the system constraints. To deal with this problem, an new Evolutionary approach combining Genetic Algorithm (GA) and a Local Search (LS) (EGALS) is proposed. The key idea of the proposed approach is to concurrently apply GA and LS to better manage the exploration-exploitation trade-off and enhance the obtained solutions. In order to assess its performance, we run the proposed approach on Solomon's benchmark and compare the obtained results against well-performing approaches from the literature, and based on several performance measures. Our experimental results showed that EGALS outperforms the existing approaches in most cases and performs closely to the rest of algorithms with the remaining instances. This confirms that the proposed approach is promising and is competitive compared with other state-of-the-art algorithms.