To　improve　the　efficiency　of　sequential　Simulated　Annealing　(SA)　for　solving　Time　Dependent　Vehicle　Routing　Problem　(TDVRP),　a　parallel-Simulated　Annealing　(p-SA)　algorithm　was　proposed.　Push　Forward　Insertion　Heuristic　(PFIH)　was　implemented　to　generate　an　initial　solution,　and　four　kinds　of　local　search　moves　within　the　structure　of　master-slave　p-SA　were　developed　to　optimize　the　initial　solution.　Computational　results　were　reported　for　56　test　problems　with　100　customers　from　Figliozzi＇s　benchmark,　and　the　results　showed　that　p-SA　could　get　5　times　speedup　when　6　threads　was　used　by　comparing　with　traditional　sequential　SA,　and　could　get　better　solutions　than　Figliozzi＇s　algorithm　within　an　accepted　computational　time.　Therefore,　p-SA　could　solve　TDVRP　effectively　and　could　be　extended　to　handle　other　variants　of　vehicle　routing　problems　and　other　combinatorial　optimization　problems.　©,　2015,　CIMS.　All　right　reserved.