Abstract: The half open multidepot vehicle routing problem (HOMDVRP) was proposed to meet the requirement of modern logistic industry in China. In terms of similarity and difference among HOMDVRP, multidepot vehicle routing problem and open vehicle routing problem, a mathematical model was built. In order to solve this new NPhard problem, the saving algorithm, the sequence insertion algorithm and parallel regretted insertion algorithm were proposed base on the classical heuristics for the vehicle routing problem. Meanwhile, three kinds of local search methods were adopted when the heuristics were designed. The results were analyzed by studying the impact of parameters and local search methods on the performance of the heuristics. Simultaneously, the performances of different heuristics were assessed by comparing them with benchmark instances.