Dynamic vehicle routing using hybrid genetic algorithms

Abstract

This paper presents a novel approach to solving the single-vehicle pickup and delivery problem with time windows and capacity constraints. While dynamic programming has been used to find the optimal routing to a given problem, it requires time exponential in the number of tasks. Therefore, it often fails to find the solutions under real-time conditions in an automated factory. This research explores anytime problem solving using genetic algorithms. By utilizing optimal but possibly partial solutions from dynamic programming, the hybrid genetic algorithms can produce near-optimal solutions for problems of sizes up to 25 percent bigger than what can be solved previously. This paper reports the experimental results of the proposed hybrid approach with four different crossover operators as well as three mutation operators. The experiments demonstrated the advantages of the hybrid approach with respect to dynamic task requests.