SEO – How do I change the structure of my URLs along with the sitemap for a live site?

I change the URL of my website to improve the SEO. The current sitemap contains URLs like these:

mysite/browse/1    /* 1 is the ID for fashion */
mysite/browse/2    /* 2 is the ID for real estate */

Now I changed the URLs to the following format:


I have the code ready for publication along with the new sitemap. When I release the new code, the old URLs are no longer valid, ie: mysite/browse/2 would return "404 – page not found".

I think I need to share the code and send the new sitemap to Google Search Console. However, I think it would take some time for Google to crawl the new sitemap. During this time, all my old URLs in the search result returned the error "404 – page not found".

How can I mitigate this situation?