This　paper　addresses　a　vehicle　routing　problem　which　considers　customers　to　require　simultaneous　pickup　and　delivery　service　(VRPSPD).　The　VRPSPD　problem　is　an　NP-hard　combinatorial　optimization　problem;　therefore　exact　methods　are　incapable　of　solving　large　scale　VRPSPD　instances.　A　tabuembedded　simulated　annealing　metaheuristic　(TSSA)　that　utilizes　four　different　neighborhood　structures　is　presented　to　deal　with　this　problem.　18　test　problems　with　100-400　customers　from　Montane　and　Galvao＇s　benchmark　are　used　to　test　the　performance　of　the　TSSA　algorithm.　Computational　results　demonstrate　that　TSSA　could　produce　high　quality　solutions.　©,　2015,　Journal　of　Computational　Information　Systems.　All　right　reserved.