An improved genetic algorithm for Time Dependent Vehicle Routing Problem

Vehicle Routing Problem (VRP) is one of the core issues of logistic distribution. But the traditional VRP doesn´t consider the traffic condition of road network. Time Dependent Vehicle Routing Problem (TDVRP) is to study the problem of vehicle routing optimization in dynamic network with fluctuant link travel time. The traditional VRP has been proven to be an NP-hard problem, so it is more difficult to solve TDVRP considering traffic conditions. In this paper, we extended 3 efficient routing construction algorithms (NNC, Solomon insertion I, and IMPACT algorithm) of traditional VRP to TDVRP. Then we designed an improved genetic algorithm (GA) for TDVRP, based on these routing construction algorithms and local search operations. Computational results of test problems showed that this improved GA algorithm has high efficiency.