Due to the dynamic characteristics, traditional vehicle routing problems (VRP) cannot be directly applied under varied customer demand and complicated traffic situations for the logistics industry. Therefore, dynamic vehicle routing algorithms need to be developed to consider real time information for city logistics. On-line VRP problems consider real-lime information and real-lime updating, and efficiency and accuracy are major concerns. Previous researches show that hybrid meta-heuristic approaches might be able to provide efficiency and accuracy simultaneously. This research proposes a hybrid meta-heuristic algorithm based on Tabu Search (TS) and Genetic Algorithm (GA) for solving dynamic VRP for on-line operations, i.e., new requests are revealed on-line. Basically TS with adaptive memory search mechanism could generate good VRP solution and GA provides good global search mechanism. In order to illustrate the proposed algorithm, the hybrid algorithm is numerically experimented in a simulation environment, DynaTAIWAN, for a city network. Within the simulation environment, network characteristics and real-time traffic information can be described. Numerical analyses, including comparisons among different algorithms and sensitivity analysis based on different parameter values, are conducted to illustrate the performance of the proposed algorithm. For the comparisons among different algorithms, the GA algorithm and the hybrid algorithm are compared under the same simulation conditions. In the sensitivity analysis, different parameter values, including the length of candidate list, the elimination cycle, and the mutation rate, are experimented to achieve better performance. The numerical results show that the hybrid heuristic algorithm provides better performance for generating on-line VRP solutions.