A hybrid evolutionary algorithm for dynamic route planning

Abstract

This paper considers a dynamic route planning problem (DRPP) involving the optimization of a route for a single vehicle traveling between a given source and given destination. Although route planning has been widely studied, most of the available applications are primarily targeted at finding the shortest path (SP) routes, which is insufficient for dynamic route planning in real life scenario. For example, the travel time for the SP may not correspond to the overall shortest time (ST) route due to varying road conditions. In this paper, the proposed Hybrid Evolutionary Algorithm for solving the Dynamic Route Planning Problem (HEADRPP) is believed to be capable of solving this problem. The proposed HEADRPP comprises a Fuzzy Logic Implementation (FLI) and a Graph Partitioning Algorithm (GPA) incorporated into a Genetic Algorithm (GA) core, and offers both optimized SP and ST routes to the user. In this paper, the proposed HEADRPP is successfully tested on a 138 node network extracted from the Singapore Map, and its performance on SP optimization is compared with a pure GA and an ant based algorithm. Overall the performance of the proposed HEADRPP is shown to be robust to the dynamic nature of the DRPP. © 2007 IEEE.