Abstract: In to day's distribution environment,under intensive competition,making customer receive goods as soon as possible becomes a increasingly significant consideration. Motivated from a real express company problem,this paper provides the math formulation for a vehicle routing problem with pick-up and delivery. The objective has two parts:vehicle traveling time and customers latencies. An insertion based new Tabu search algorithm is proposed to solve the problem quite efficiently. The computation results show that the new Tabu search algorithm is quite faster than the traditional one,and it could get rather good solution quality,especially for the small size problem.

Key words: pick-up and delivery, vehicle routing problem, Tabu search