Implementing 301 redirects -- when to update the XML sitemap?

When is best to delete old URLs and add new URLs

[Techpaulogy]

I am planning to implement 301 redirects for my site's URLs to something more user-friendly. The question is, when do I reflect these URL redirects in the XML sitemap submitted to Google (and Yahoo)?

1) Keep original sitemap with old 301 URLs and let Google find the new ones

2) Add new URLs to the original sitemap, so both the new pages and old 301 pages are submitted

3) Create new sitemap with new URLs (delete all the 301 URLs from the sitemap)