The　vehicle　routing　problem　with　simultaneous　pickup　and　delivery　(VRPSPD)　is　an　NP-hard　combinatorial　optimisation　problem　that　has　received　considerable　attention　in　the　past　few　decades.　A　parallel　simulated　annealing　(parallel-SA)　algorithm　that　uses　four　different　neighbourhood　structures　has　been　developed　to　solve　this　problem.　The　parallel-SA　algorithm　follows　the　traditional　sequential　SA　algorithm　with　an　integrated　asynchronous　and　synchronous　multiple　Markov　chains　(MMC)　approach　and　incorporates　a　master-slave　structure　in　the　algorithm.　Computational　results　are　reported　for　72　test　problems　with　50　to　400　customers　from　Dethloff＇s　medium-scale　benchmark,　Salhi　and　Nagy＇s　medium-to-large-scale　benchmark　and　Montane　and　Galvao＇s　large-scale　benchmark.　Computational　results　indicate　that　the　proposed　parallel-SA　algorithm　is　competitive　with　other　well-known　algorithms　for　VRPSPD　from　both　quality　of　solution　and　computational　time.