Improved GRASP with Tabu Search for Vehicle Routing with Both Time Window and Limited Number of Vehicles

In this paper, we study a new useful extension of vehicle routing problem (VRP) - VRP with both time window and limited number of vehicles (m-VRPTW). We propose an improved Greedy Randomized Adaptive Search Procedure (GRASP) framework by techniques of multiple initializations, solution reuse and mutation improvement, with four specified heuristics for m-VRPTW: short left time first, near customer first, short waiting time first and long route first. From the experimental results on benchmark data, it is shown that our algorithm not only well solves the m-VRPTW problem, but also obtains accurate solution for classical VRPTW problem with stable performance in short running time. In fact, the search techniques proposed in this paper can be easily applied for other meta-heuristics for problem solving ...